Am încercat recent să reproduc rezultatele întrebării adresate de Ruggero și la care Samuel Neves a răspuns aici: Înțelegerea Twist Security în ceea ce privește curbele Weierstrass scurte
În încercarea mea de a replica acest lucru, am constatat că atacul nu funcționează pentru anumite puncte. Inițial, presupunerea mea a fost că acest lucru a fost din cauza factorului de răsucire $d$ in cazul meu nu a fost $-1 \mod p$. Prin urmare, am pus această întrebare: Atacul punctual nevalid pe răsucirea pătratică a curbei eliptice atunci când -1 este un reziduu pătratic. Cu toate acestea, pe măsură ce am explorat mai departe, mi-a devenit clar că nu acesta este motivul pentru care atacul nu funcționează. În schimb, cu chiar codul răspunsului inițial, pot demonstra în mod fiabil că o implementare reală a unei scări doar X funcționează pentru punctele de ordine 100+, dar nu funcționează (în mod fiabil) pentru punctele de ordin inferior.
Am modificat scriptul lui Samuel aici pentru a arăta în mod determinist acest comportament pentru un punct de ordine 7:
# Câmpuri de configurare
p = 2^127-1
d = -1 # non pătrat în câmp
K = GF(p)
K2.<z> = GF(p^2)
# această curbă are ordinea primă, dar o răsucire netedă de 2^44
a = -3
b = 2045
E = Curba eliptică (K, [a, b])
Et = Curbă eliptică(K, [d^2*a, d^3*b])
E2 = Curba eliptică(K2, [a, b])
# precalculați comenzi
print (E.order().factor());
print (Et.order().factor());
print (E2.order().factor());
# generează un logaritm discret de rezolvat
s = 123456789123456789123456789
P = E([0, 26743016104147931148362869907315104519])
Q = s * P
P_ = E2.lift_x(K(163965092228135290549051973720749297665))
fapt = 7
P_ *= Et.order() // fapt
print(P_)
Q_ = s * P_ # interogare -- pretindeți că acest lucru se face cu o scară doar x
# rezolvați jurnalul direct pe E2
x1 = P_[0]
print("x1_p2", x1)
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))
# mapa la Et (opțional) și rezolvă
x1 = d * P_[0]
print("x1_t", x1)
x2 = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))
pentru rezultat în [ 153050600407045353908344231774077597412, 109343643823296263382915152331234715795 ]:
pentru x în [ K(rezultat), K(rezultat) * d ]:
pentru c în [ Et, E2 ] :
încerca:
P = c.lift_x(x)
cu excepția ValueError ca e:
print(e)
continua
print(P, P.order())
imprimare (fapt s %)
print (s_, -s_ % fapt) # fie unul, fie altul
print (s__, -s__ % fapt) # fie unul, fie altul
Valorile 15305... și 1093... sunt cele pe care le oferă o implementare de scară doar X atunci când sunt date coordonatele x1_p1 sau x1_t.
Rețineți că acest cod și implementarea mea de scară doar X funcționează perfect pentru toate punctele cu comanda 73 sau mai sus. Pur și simplu nu funcționează pentru comenzile 3 sau 7. Iată rezultatul scriptului:
170141183460469231713519983870624230867
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909 * 170141183460469231713519983870624230867
(31638283026303721859929793126783073834: 8180858091114185696092778095200036260*z + 4090429045558046091114185696092778095200036260*z + 4090429045558046042904558490463)
x1_p2 31638283026303721859929793126783073834
x1_t 138502900434165509871757510589101031893
No point with x-coordinate 153050600407045353908344231774077597412 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(153050600407045353908344231774077597412 : 120638375417041763806996747829917991029*z + 145389779438755497769342025772901048378 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315: 41244633631159509998704366741778119200: 1) 56713727820818632820586741778119200: 1)
(17090583053423877823343071941806508315: 289618265475739437693303623242555518848: 1) 17014118265475739437693303623242555518848: 1) 1701411826547573943769330362324255518848: 1)
No point with x-coordinate 109343643823296263382915152331234715795 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(109343643823296263382915152331234715795 : 127120934962706688155967022405858199927 : 1) 170141185967027120934962706688155967022405858199927: 1)
No point with x-coordinate 60797539637172968348772151384649389932 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(60797539637172968348772151384649389932 : 17145369941110587676988010143957064222 : 1) 17014118369941110587676988010143957064222: 1) 17014118369941110587676988010143957064222: 1)
1
1 6
1 6
De ce funcționează acest atac în teorie (ca înmulțirea Q_ = s * P_ simulează), dar funcționează în practică doar pentru puncte de ordin rezonabil?
