elikaski/ecc_attacksAttacchi noti alla crittografia a curve ellittiche
Negli ultimi anni l'approccio della crittografia a curve ellittiche è diventato popolare grazie alla sua alta efficienza e alla sua forte sicurezza. Lo scopo di questo articolo è presentare questo argomento in un modo relativamente più chiaro rispetto a quanto esiste oggi su internet.
In questo articolo presenterò cosa sono le curve ellittiche, le operazioni di base che si possono eseguire su di esse e come possono essere usate in un contesto crittografico. La maggior parte di questo articolo consiste in esempi di attacchi noti su implementazioni errate o su usi scorretti di esse. Nel corso dell'articolo cerco di separare la spiegazione in una parte intuitiva e ad alto livello e una parte matematica che entra più nei dettagli. Il lettore è invitato a concentrarsi su quale delle due parti lo interessa in quel punto e a saltare le parti meno rilevanti.
Buona lettura!
In generale, una curva ellittica è una sorta di linea curva. Un esempio è la parabola, la cui equazione è della forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ e appare così:
Nel contesto della crittografia, è consuetudine usare curve ellittiche la cui equazione è della forma
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Ad esempio, una curva ellittica corrispondente all'equazione $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ appare così:
L'equazione della curva definisce la relazione tra la coordinata 𝑥 di un punto sulla curva e la sua coordinata 𝑦. In un contesto crittografico, limitiamo 𝑥, 𝑦, 𝑎, 𝑏 a essere interi e limitiamo i calcoli a essere modulo un grande numero primo. Quindi l'equazione della curva ellittica è:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Questo significa che abbiamo un numero finito di punti sulla curva. In linguaggio matematico, la curva è definita su un campo finito di ordine 𝑝. Di conseguenza, ora non necessariamente ogni coordinata 𝑥 avrà un punto corrispondente sulla curva, perché può accadere che la coordinata 𝑦 corrispondente non sia un intero.
L'insieme dei punti sulla curva è costituito da coppie di interi (𝑥, 𝑦) che soddisfano l'equazione della curva. Oltre a questi punti, viene definito un altro punto speciale chiamato "Infinito", denotato con 𝒪. In linguaggio matematico, questo punto è l'elemento neutro dell'insieme dei punti sulla curva rispetto all'operazione di addizione, che definiremo nella prossima sezione. Il numero di punti sulla curva (incluso il punto 𝒪) è chiamato "ordine della curva".
Un'altra osservazione è che le curve ellittiche sono simmetriche rispetto all'asse X. Ciò significa che se il punto 𝑃 = (𝑥, 𝑦) è sulla curva, allora anche il punto −𝑃 = (𝑥, −𝑦) è sulla curva. In effetti, questi punti sono considerati "inversi" l'uno dell'altro (da qui la notazione −𝑃 per il secondo punto), e il risultato dell'operazione di addizione tra loro è definito come l'elemento neutro 𝒪.
Un teorema chiamato Teorema di Hasse fornisce una stima di #𝐸, l'ordine della curva, ed è dell'ordine di grandezza di Θ(𝑝). Più precisamente:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Dati due punti sulla curva, è possibile definire un'operazione di addizione tra di essi, che produce un terzo punto anch'esso sulla curva. Per trovare geometricamente questo punto, tracciamo una linea tra i due punti dati e la prolunghiamo fino a quando interseca la curva in un terzo punto. Questo punto viene riflesso rispetto all'asse 𝑋, e il punto risultante è definito come il risultato dell'addizione.
Ecco un diagramma che mostra come, dati i punti 𝑃 e 𝑄, si possa trovare il punto 𝑃 + 𝑄:
Una domanda che può sorgere da questa descrizione è: cosa succede se la linea tracciata tra i due punti non interseca di nuovo la curva? In questo caso si dice che la linea interseca la curva all'"infinito", e il risultato dell'addizione è il punto 𝒪. Nota che questo caso si verifica se la linea tracciata è verticale, cioè stiamo cercando di sommare un punto 𝑃 con il suo punto inverso, −𝑃:
Da questo derivano due identità fondamentali. Per ogni punto 𝑃 vale che:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Un'altra domanda che sorge dalla descrizione geometrica è: come si somma un punto a se stesso? Abbiamo visto che per sommare due punti diversi 𝑃 e 𝑄, tracciamo una linea tra loro e guardiamo il punto di intersezione del suo prolungamento con la curva. Intuitivamente, lasceremo 𝑃 costante e osserveremo la linea che si crea mentre spostiamo 𝑄 "sempre più vicino" a 𝑃, finché 𝑄 non si fonde con 𝑃. Quello che otterremo è una linea sempre più "tangente" alla curva nel punto 𝑃, ed è esattamente la linea che considereremo quando vogliamo sommare 𝑃 a se stesso:
Per sommare un punto 𝑃 a se stesso, tracciamo una tangente alla curva nel punto 𝑃 e la prolunghiamo finché non interseca la curva in un secondo punto. Questo punto viene riflesso rispetto all'asse 𝑋, e il punto risultante è definito come il risultato dell'addizione. È consuetudine indicare il risultato dell'addizione come 𝑃 + 𝑃 = 2𝑃. Di nuovo, se la tangente non interseca la curva in un secondo punto, si dice che interseca la curva all'"infinito", e il risultato dell'addizione in questo caso è il punto 𝒪.
Queste descrizioni geometriche visive illustrano bene il funzionamento dell'addizione di punti e ci aiutano a capirla. Ma come la calcoliamo effettivamente? Con equazioni matematiche, ovviamente!
