Addizione tra 2 punti in E(F_11): esempioVediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.
Proviamo tutti i casi possibili:
x x^3+7 x^3+7 mod 11 Sqrt(x^3+7) mod 11
0 7 7
1 8 8
2 15 4 2 o 9 2 o -2 --> (2,2), (2,-2)
3 34 1 1 o 10 1 o -1 --> (3,1), (3, -1)
4 71 5 4 o 7 4 o -4 --> (4,4),(4,-4)
5 132 0 0 0 --> (5,0)
6 223 3 5 o 6 5 o -5 --> (6,5),(6,-5)
7 350 9 3 o 8 3 o -3 --> (7,3),(7,-3)
8 519 2
9 736 10
10 1007 6
Abbiamo quindi trovato che
E(F_11 )={(2,2),(2,-2),(3,1),(3,-1),(4,4),(4,-4),(5,0),(6,5),(6,-5),(7,3),(7,-3)} ∪{O}
Si noti che in questo caso particolare l'ordine del gruppo E(F_11) è 12 ed è superiore al numero degli elementi di F_11, mentre con la curva secp256k1 l'ordine di E(K) è minore (seppur dello stesso ordine di grandezza) del numero degli elementi di K.
Viene comunque rispettata la stima di Hasse: |#E (Fp) - (p + 1)| < 2rad(p)
infatti
|12-12|<2*sqrt(11)
Visualizzazione nel piano cartesiano di E(F_11 ):
Si noti come E(F_11) non costituisca visivamente un sottoinsieme di E(R), poichè bisogna tenere conto anche del modulo 11.
Nel grafico si è scelto di rappresentare gli 11 valori possibili per la coordinata y tra -5 e +6 anzichè tra 0 e 10 per mantenere visivamente la simmetria rispetto all'asse x. Si noti come questo insieme di punti non costituisca affatto un sottoinsieme dei punti della curva a coefficienti reali che soddisfa la stessa equazione; infatti il campo di "gioco" adesso è costituito da una griglia di punti a coordinate intere (11 valori possibili per le x, 11 per le y), e ogni volta che il calcolo di x^3+7 fa "sforare" una coordinata da un lato del quadrato si ricomincia dal lato opposto - questo vuol dire lavorare in modulo 11.
Da questo grafico si evince inoltre come l'operazione di "addizione" tra punti perda il significato geometrico originale in questa situazione (non ci sono curve con secanti e tangenti nel senso classico di questi termini), anche se sorprendemente l'operazione algebrica sulle coordinate determina ancora una struttura di gruppo per l'insieme E(F_11)
Addizione tra 2 punti in E(F_11)A=(2,2) B=(3,1) A+B = ?
Quindi A+B=F
In questo caso particolare il risultato era facilmente prevedibile per via geometrica, poichè per passare da A, B, F' e F non si "rimbalza" mai sui lati di questo particolare biliardo quadrato.
Ma se volessimo addizionare A e F, cosa otterremmo?
A=(2,2) e F=(7,3); A+F=?
(La pendenza sarebbe 1:5, cioè l'inverso di 5 che in F_11 corrisponde a 9 (poichè 9*5=45=1 modulo 11)
Quindi A+F=E'
Come si può notare, in questo particolare biliardo se si tocca un lato si riparte dalla parte opposta (oppure se preferite potete pensare di stare avvolgendo uno spago intorno a un rocchetto a forma di ciambella, con "pendenza" del filo costante uguale a quella del tratto iniziale AF, e lo scopo è di continuare così fino a intercettare un altro punto del gruppo che si trova sulla superficie della ciambella. A priori non è noto quanti avvolgimenti (diagonali) bisogna fare intorno al rocchetto prima di raggiungere un altro punto, in questo caso è bastato solo 1 avvolgimento.)
E' proprio il tipo di relazione non banale tra il punto di partenza e quello di arrivo (pur essendo nota la "direzione" iniziale) a rendere crittograficamente interessanti le curve ellittiche.
Infine calcoliamo un "multiplo" di un punto, per esempio 2*A, utilizzando le formule appropriate:
A=(2,2) 2*A=
Quindi 2*A = D.
La creazione di una chiave pubblica (individuare un punto della curva) procede proprio in questo modo: si parte da un punto G (detto generatore del gruppo), lo si moltiplica per uno scalare random d (la chiave privata) e quindi si ottiene la chiave pubblica d*G (un punto della curva). Pur essendo noti a tutti sia il punto G che la chiave pubblica d*G, è computazionalmente intrattabile il problema di ricavare il legame tra G e d*G, cioè di fatto è impossibile ricavare la chiave privata d che corrisponde al numero di volte in cui bisogna sommare G a se stesso per ottenere la chiave pubblica.