Ciao a tutti i lettori!
Sempre per la serie “la crittografia non ci basta mai”, con questa sequenza di post, vorrei spiegarvi un tipo di crittografia che fa uso delle curve ellittiche, nato più o meno nel 1985 grazie ai lavori di Miller e Koblitz. E’ così difficile da attaccare che il governo americano la usa per i segreti più importanti…quindi diciamo che forse ne vale la pena di saperne qualcosina in più! 🙂
Non lasciatevi spaventare dal nome, ci andrò piano piano! In questa prima parte parlerò delle curve ellittiche e di alcune loro proprietà. Iniziamo dall’inizio, ovviamente. Perciò…cos’è una curva ellittica?
Curve Ellittiche…non Ellissi!
Vediamo di iniziare dal caso più semplice. Una curva ellittica reale $$\mathcal{E}$$ è l’insieme di coppie (x,y) di numeri reali che soddisfano l’equazione $$y^2 = x^3 + ax + b$$ dove a,b sono due numeri reali. Per motivi che risulteranno chiari presto, dobbiamo aggiungere a questo insieme un punto O detto punto all’infinito. Possiamo vedere O come in punto di coordinate $$(\infty, \infty)$$ anche se è veramente una scrittura impropria!
Nella figura potete vedere un esempio di curva ellittica.
Finora non abbiamo fatto né detto niente, abbiamo solo definito questi nuovi oggetti. Ma ora viene il bello: in una curva ellittica è possibile sommare i punti!
Come si fa? Per comodità definiamo prima il negativo di un punto Q di coordinate $$(x_Q, y_Q)$$ facente parte della curva. Lo definiamo così: $$-Q=(x_Q, -y_Q)$$ , cioè cambiamo segno solo alla seconda coordinata. Così facendo si vede che esso appartiene ancora alla curva (vedi la figura…c’è simmetria rispetto l’asse x!). Prendiamo ora P,Q due punti sulla curva ellittica $$\mathcal{E}$$. Se disegniamo la retta passante per P e Q, essa interseca la curva in un altro punto detto P*Q. Definiamo P+Q = -P*Q. Potete vedere in figura la rappresentazione geometrica dell’operazione.
Ci sono ovviamente eccezioni. Prima di tutto, non abbiamo parlato mai del punto all’infinito (eppure se l’abbiamo nominato…a qualcosa servirà!), poi non abbiamo considerato i casi in cui si fa Q+(-Q) e P+P. Come si fanno?
Nel caso P+P si prende la tangente al punto P ed essa interseca la curva in un altro punto P*P e quindi P+P=-P*P.
Invece, come vedete dalla figura qui sopra, la retta passante per Q e (-Q) non interessa altri punti della curva. Quindi diciamo che interseca il punto all’infinito O e quindi (poiché -O=O=Q*(-Q) ) si ha Q+(-Q)=O. Ecco a cosa serve!
Inoltre P+O=P=O+P per ogni punto della curva. E’ una sorta di zero!
Ma è davvero una addizione?!?
Cosa abbiamo appreso? E’ davvero una addizione? Per rispondere alla domanda dobbiamo verificarne le proprietà:
C’è l’elemento neutro (lo zero)? Sì, è O.
E’ associativa? Non lo dimostriamo ma sì, lo è.
Ammette inversi? Sì, P —> (-P).
E’ commutativa? P+Q=Q+P, certamente!
Quindi è una somma proprio nel modo in cui la conosciamo noi. Questo è un esempio brillante e geometrico di come possiamo definire operazioni simili a quelle che conosciamo utilizzando altri “numeri”…in questo caso usando punti!
Abbiamo quindi dotato $$\mathcal{E}$$ di un operazione binaria associativa e commutativa, rendendolo ciò che in matematica si chiama gruppo abeliano. Questo in particolare è detto gruppo di Mordell, e prende il nome dall’omonimo matematico.
Date le coordinate dei punti, esistono formule esplicite per le coordinate del punto somma, ma le omettiamo!
Diamo un ordine alle cose
Non l’abbiamo detto, ma sappiamo anche moltiplicare un punto P per un numero intero n: infatti, $$nP = P+\dots+P$$ n volte.
Possiamo quindi ordinare i punti sulla curva in base a quante volte dobbiamo sommarli con se stessi per ottenere O.
Quindi, l’ordine del punto P è il minimo n, se esiste, per cui nP=O. Altrimenti si dice che P ha ordine infinito.
Per il momento questa definizione non è rilevantissima ma è comunque interessante capire come è possibile classificare i punti su una curva ellittica.
E le congruenze?
All’inizio avevo scritto “vediamo di fare il caso più semplice”…beh ora facciamo un caso leggermente più complicato. Invece di prendere le coppie di numeri reali che soddisfano questa equazione, si potrebbe pensare di cambiare insieme da cui scegliamo i numeri. Quindi potremmo pensare di prendere numeri complessi, razionali o interi…o, perché no, anche insiemi di numeri finiti. In vari miei post passati (“valli a legge”) parlavo delle congruenze, ovvero definivo come numeri dei “gruppi di numeri” (scusate il gioco di parole). Si può ovviamente usare questo insieme di numeri e definire la relativa curva ellittica.
Tutto ciò è interessante e ad oggi ci sono molte congetture irrisolte su questi argomenti. Ora non è il momento, ma chissà magari un giorno ve ne parlerò!
Is this the end?
Of course not! La prossima volta entreremo nel vivo della crittografia e di come usare questa nuova operazione che abbiamo appena definito. Ad maiora!
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
L’articolo è stato scritto in maniera encomiabile per la semplicità, ma al tempo stesso la chiarezza di esposizione!