Я изучал основы ecc и обнаружил, что примеры из Интернета либо используют непрерывную кривую домена, либо используют очень маленькое простое число. п как 17 в дискретном домене, чтобы показать точки.
Мне очень любопытно, если я смогу найти точку с действительно большим п на практике. Например, secp256k1 использует очень большой п=2^256–2^32–977 в домене (p,a,b,G,n,h).
Ниже приведен код Python, который я использую для вычета возможного целого числа y из решения уравнения с диапазоном целых чисел. Икс. К моему удивлению, нет находки даже в диапазоне 1 миллион!
Итак, мой вопрос: правильный ли код ниже? А во-вторых, если это правильно или исправлено каким-то настоящим экспертом, то в каком диапазоне значений мне попробовать?
P.S.
Мне интересно, как точка генератора г тоже выбирается. Но для этого может потребоваться более глубокое понимание темы.
импортировать математику
# secp256k1
# у**2 = х**3 + 7 (по модулю р)
Р = 2**256 - 2**32 - 977
А = 0
В = 7
# нист P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
А = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
определение in_curve(x):
кривая = х**3 + А*х + В
y_float = math.sqrt (кривая)
если abs(math.modf(y_float)[0]) < 0,0001 или \
(1 - абс (math.modf (y_float) [0]) < 0,0001):
# печать (y_float)
# ошибка: y_int = int(math.modf(y_float)[1])
y_int = int (круглый (y_float))
если y_int * y_int == (кривая):
печать (y_int)
вернуть y_int
возврат Нет
для x в диапазоне (1, 1000000):
у = in_curve (х)
если y не None:
напечатать (х, у)
Обновление 1
Предыдущий код неверен, так как sqrt() с плавающей запятой вызовет недопустимую ошибку при преобразовании обратно в целое число.
Но после замены math.sqrt() к math.isqrt(), это все еще не делает вещи разумными.
Обновление 2
Спасибо за советы от всех ответивших в теме. Используя точку генератора для проверки моего алгоритма, я теперь ясно знаю, почему я терпел неудачу.
Дело в том, что помимо использования % для всех умножений и сложений я должен также используйте модульный квадратный корень, чтобы найти решение, вместо целый квадратный корень вместе с %. Это абсолютно неправильное использование % наверняка.
Модифицированный код проходит тест с некоторыми тестовыми векторами.
импорт модульный_sqrt
# например Я использовал код из https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python.
# пожалуйста, спросите разрешения, если использование выходит за рамки образовательного хобби, и всегда указывайте заслугу порядочного человека ;-)
# nist P256, взято с https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
А = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Гр = 36134250956749795798585127919587881956611106672985015071877198253568414405109
защита get_y_in_curve(x):
у2 = х**3 + А*х + В
y_int = модульный_sqrt (y2, P)
если y_int и ((y_int * y_int) % P) == (y2 % P):
вернуть y_int
возврат Нет
утверждать get_y_in_curve(Gx) == Gy
