Puncte:2

Atacul punctual nevalid pe răsucirea pătratică a curbei eliptice atunci când -1 este un reziduu pătratic

drapel ma

Replic un atac punctual nevalid asupra ECC folosind curbe Weierstrass scurte. Pentru aceasta am scris o implementare "proastă" care nu validează punctele care sunt pe curbă înainte de a intra în multiplicarea scalară. Pentru schița atacului, împrumut foarte mult din descrierea excelentă a lui Samuel Neves pe care a oferit-o aici: Înțelegerea Twist Security în ceea ce privește curbele Weierstrass scurte

Pot replica asta fără nicio problemă când $d = -1$ este un nereziduu pătratic în $\mathbb{F}_p$, apoi totul funcționează imediat. Cu toate acestea, când $p$ este astfel încât $-1$ este un reziduu pătratic și, prin urmare, trebuie să aleg o valoare diferită pentru $d$, totul se destramă.

Pentru simplitate, la prima rulare nu folosesc curbe în $\mathbb{F}_{p^2}$ pentru că pentru mici $p$ enumerarea exhaustivă pentru a găsi puncte de ordin scăzut nu este o problemă.

De exemplu, să spunem că curba mea este definită peste $\mathbb{F}_{101}$; Aici, $-1$ este un reziduu patratic mod $p$, de cand $10 \cdot 10 = -1 \mod 101$. Curba mea este dată de

$E: y^2 = x^3 + 13x + 29$

Si cu $d = 2$, un mod pătratic fără reziduuri 101,

$E^d: y^2 = x^3 + 52x + 30$

Ordinul de $E^d$ este $111 = 3 \cdot 37$. Am ales două puncte $E^d$ care au ordinele 3 și respectiv 37:

$P_1 = (28, 62)$

$P_2 = (8, 7)$

Când rulez aceste valori prin multiplicarea mea scalară fără validare de puncte (pentru cheia privată $d = 58$, am urmatoarea iesire:

$S_1 = (94, 53)$

$S_2 = (32, 14)$

Nici $S_1$ nici $S_2$ este un punct pe răsucirea pătratică $E^d$. Pot ridica oricare dintre coordonatele X $E^d$, dar atunci ordinea punctelor este greșită.

Iată codul meu exemplu:

Fp = GF(101)
D = Fp(2)
    
print(D, „este pătrat?”, D.is_square())
(a, b) = (13, 29)

E = Curba eliptică(Fp, [a, b])
Et = Curba eliptică(Fp, [ a*D^2, b*D^3 ])

print("Et.order()", factor(Et.order()))

puncte_atac = [
    Et(28, 62),
    Et(8, 7),
]
imprimare(E)
print(Et)
pentru P în puncte_de_atac:
    print(P, P.order())

# cheie privată d = 58
mul_results = [ 
    Et(94, 53), 
    Et(32, 14), 
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())

Care iese:

2 este pătrat? Fals
Et.order() 3 * 37
Curba eliptică definită de y^2 = x^3 + 13*x + 29 peste Câmp finit de dimensiunea 101
Curba eliptică definită de y^2 = x^3 + 52*x + 30 peste Câmp finit de dimensiunea 101
(28:62:1) 3
(8 : 7 : 1) 37
TypeError: Coordonatele [94, 53, 1] nu definesc un punct pe curba eliptică definit de y^2 = x^3 + 52*x + 30 peste Câmp finit de dimensiunea 101

Cum pot efectua acest atac pentru o răsucire pătratică unde $d \neq -1$?

kelalaka avatar
drapel in
S-ar putea să nu fie problema ta. De asemenea, codul original nu mai funcționează pe SageMath. Mare probabil că există o schimbare în bibliotecă care împiedică astfel de calcule...
drapel ma
Nu am destulă reputație pentru a comenta în cealaltă postare, dar soluția de la Neves funcționează, doar că nu iese din cutie: instrucțiunile de tipărire au nevoie de paranteze și apelurile .lift_x(randint(...)) trebuie înlocuite prin .lift_x(K(randint(...))), apoi totul funcționează ca un farmec. L-aș putea reproduce perfect cu d = -1, dar așa cum am scris -1 este un reziduu pătratic în unele câmpuri (cum ar fi GF(101), așa cum se arată aici).
kelalaka avatar
drapel in
Am modificat răspunsul, poți verifica și asta?
drapel ma
Mulțumesc, codul de acolo funcționează acum, dar încă nu răspunde la întrebarea mea (adică folosește în mod explicit d = -1) -- ai idee cum să-l faci să ruleze cu un alt d?
kelalaka avatar
drapel in
Da, știu. Geometria algebrică (curbele eliptice fac parte din ea) ar trebui făcută pe închiderea algebrică. Răspunsul lui Samuel Neves, după cum puteți vedea, funcționează la închidere, nu sunteți.
kelalaka avatar
drapel in
Vezi lucrarea Curve25519 despre atacul subgrupurilor mici.
Ruggero avatar
drapel kr
Presupun că cu d!=-1 trebuie să convertiți punctul dvs. din $E$ și $E^{d}$ și nu puteți utiliza pur și simplu coordonatele x. Ar fi de ajutor dacă puteți posta un script înțelept pentru înmulțirea dvs. scalară, deoarece utilizarea lui $y$ mă încurcă, de ce să nu faceți un atac de curbă invalid (fără să vă deranjați cu răsucirea)?
drapel ma
@kelalaka Exemplul pe care îl dau aici este doar pentru simplitate -- el lucrează pe câmpul de extensie pătratică, dar nici asta nu funcționează pentru d != -1 dacă îi modificați scriptul pentru a utiliza alți parametri de domeniu. Adică, asta nu este cauza principală a problemei, mă tem. Am omis-o aici pentru concizie pentru a avea un exemplu minim care să demonstreze problema.
drapel ma
@Ruggero Am trecut cu vederea răspunsul tău. Da, cred că este nevoie de o conversie, dar nu pot să-mi dau seama cum: înainte de a o introduce ca intrare în scară sau după ieșirea scarii (sau eventual ambele). O conversie este cu siguranță necesară și, de asemenea, rețineți că -1^2 = 1, adică dacă o putere pară a fost înmulțită/împărțită cu, nu am ști niciodată în cazul d=-1. Observația ta despre scara doar X este corectă. În disperarea mea, am încercat totul: Simplu mul-and-add (funcționează și pentru d=-1!), Brier/Joye X-ladder și additive X-only ladders. Toate calculează corect, așa că cu siguranță lipsesc conversia.
Puncte:0
drapel ma

Aceasta nu este o problemă ca d să fie un QNR care nu este -1.

În schimb, este o problemă de module mici. Pot demonstra acest lucru în mod fiabil folosind un script modificat al lui Samuel Neves: Atacul cu puncte nevalid dă rezultate greșite pentru puncte de ordin scăzut

Acest lucru nu răspunde deloc De ce nu funcționează, dar cel puțin asta demonstrează asta $d \neq -1$ nu este cauza principală a problemei mele.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.