Эллиптические кривые для ECDSA: выбор "генератора"
G(Gx, Gy)
- который также называется генератором - это точка на эллиптической кривой (EC) на конечном поле. Конечный размер поля = p
основной модуль.
Скажем, у нас есть EC(Fp): y**2 = x**3 + ax + b (mod p)
Как суть G
быть выбранным на этом?
Должен ли каждый пункт быть найден на EC(Fp) и затем выбран один из них?
Или же Gx
\ Gy
должны быть как-то конкретны?
Единственное, что я знаю: G
Порядок должен быть простым числом.
PS Извините за мой английский и спасибо.
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
) до тех пор, пока не будет найден один простого порядка.