Перебор по эллиптической кривой

У меня есть все параметры эллиптической кривой. И координаты точек Q и P. Я хочу решить Q=k*P (где k — неизвестное), проверив все возможные k.

Поэтому я использовал этот класс

тогда:

a=-1
b=0
p=134747661567386867366256408824228742802669457
curve = EllipticCurve(a,b,p)
P=[18185174461194872234733581786593019886770620,74952280828346465277451545812645059041440154]
Q=[76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090]
for i in range(2902021510595963727029):
    result = curve.multPoint(i,P)
    if result[0]==Q[0] and result[1]==Q[1]:
        print (i)
        break

Это правильный подход к решению этой проблемы?


python ecdsa elliptic-curve brute-force
person Chaker    schedule 14.05.2015    source источник
comment
Обратите внимание, что в ваших параметрах a = -1 и b = 0, поэтому уравнение эллиптической кривой y ^ 2 = x ^ 3 + ax + b фактически становится y ^ 2 = x ^ 3 -1 * x. Это уже не сильная эллиптическая кривая. Удачи вам с CTF!   -  person Nils Pipenbrinck    schedule 16.05.2015

Ответы (2)


arrow_upward
3
arrow_downward

Это не лучший подход, потому что вы пытаетесь выполнить 2902021510595963727029 операций. Даже если вам удастся выполнить миллиард операций в секунду, это займет 92 тысячи лет до конца.

По сути, вы пытаетесь нарушить безопасность ECDSA. Если вы найдете способ сделать это, то можно будет определить закрытый ключ ECDSA с учетом соответствующего открытого ключа. Это был бы прорыв в криптографии, и вы бы стали знамениты. Есть много умных людей, которые думали об этой проблеме до вас и не нашли решения.

Проблема, которую вы пытаетесь решить, называется дискретным логарифмом.

person David Grayson    schedule 15.05.2015
comment
Это для задачи CTF, так что, вероятно, это решаемо. - person b0fh; 15.05.2015
comment
Что ж, это решаемо, если они намеренно выбрали маленькое значение k или, может быть, если параметры кривой подобраны неудачно. Возможно, вам следует спросить на cryptography.stackexchange.com, если ни у кого здесь нет идей. - person David Grayson; 15.05.2015

arrow_upward
0
arrow_downward

Кривая уязвима как для атаки MOV, так и для более старой атаки FR, которая работает аналогично, поэтому мы можем использовать пары Вейля или Тейта (соответственно).

q = 134747661567386867366256408824228742802669457
Zq = Zmod(q)
E = EllipticCurve(Zq, [0,0,0,-1,0])
P = E(18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154)
Q = E(76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090)
n = P.order()
k = GF(n)(q).multiplicative_order()
R = E.random_element()
w1 = P.tate_pairing(R, n, k)
w2 = Q.tate_pairing(R, n, k)
print w1, w2

с w2=w1^k нам нужно решить задачу дискретного логарифмирования в кольце целых чисел по модулю p. Это может занять некоторое время, но все же выполнимо, учитывая небольшой модуль.

PS: это ответ.

person Chaker    schedule 18.05.2015