Эллиптические кривые для ECDSA: выбор "генератора"

Question

G(Gx, Gy) - который также называется генератором - это точка на эллиптической кривой (EC) на конечном поле. Конечный размер поля = p основной модуль.

Скажем, у нас есть EC(Fp): y**2 = x**3 + ax + b (mod p)
Как суть G быть выбранным на этом?

Должен ли каждый пункт быть найден на EC(Fp) и затем выбран один из них?
Или же Gx\ Gy должны быть как-то конкретны?

Единственное, что я знаю: GПорядок должен быть простым числом.

PS Извините за мой английский и спасибо.

Answer 1

Обычное практическое решение — использовать заранее вычисленный набор параметров. Некоторые из них вы найдете в разделе 2 sec2v2 . Популярным выбором для ИТ-безопасности является secp256r1 . Это даетp,a,bи стандарт. Порядок этого является основным.

Для и лишить ведущих04байт в несжатой версии , а оставшиеся 64 байта разделить на две 32-байтовые байтовые строки, которыеGxиGyв двоичном формате с прямым порядком байтов.

Как на нем выбрать точку?

Поскольку кофакторhпоскольку эта кривая равна 1 (как и для всех кривых в разделе 2 sec2v2), любая точка на кривой, которая не является точкой на бесконечности, также имеет порядок простого числаn. Его можно найти, взяв случайноеx, вычисленияy**2 mod pприменяя уравнение кривой, пока не получим квадратичный остаток, который можно проверить с помощью символа Лежандра . Один из двух подходящийyзатем может быть найден путем извлечения модульного квадратного корня, например, с помощью Тонелли – Шэнкса .

Для определения собственных параметров, представляющих криптографический интерес, обычно используется алгоритм Шуфа-Элкиса-Аткина . Он встроен в PARI/GP и доступен в SageMath. Помните, что существуют и другие желательные критерии, помимо кофактора 1 и простого порядка, для выбора безопасной эллиптической кривой.

Для параметров игрушки один из вариантов — найти порядок случайной точки на случайной эллиптической кривой (определяемой как дляG) до тех пор, пока не будет найден один простого порядка.