Topic: curve ellittiche e algoritmo ECDSA - page 5. (Read 25483 times)

Addizione tra 2 punti in E(F_11): esempio


Vediamo 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.

Addizione tra 2 punti in E(R): definizione


Per capire meglio la struttura di E(K) dobbiamo però definire meglio l'operazione di addizione tra punti che caratterizza questo gruppo ciclico.


Visualizziamo la curva di equazione y^2=x^3+7 (per ora lasciamo "libere" le coordinate di assumere valori reali, quindi per adesso lavoriamo in E(R)):



Cosa vuol dire "sommare" due punti A e B di questa curva?
Si definisce C := A+B il punto della curva che si ottiene nel seguente modo:
1)   si considera la terza intersezione della retta che passa per A e B con la curva (questa retta interseca quasi* sempre la curva in un terzo punto)
2)   si prende il simmetrico del punto così ottenuto rispetto all'asse x (che appartiene ancora alla curva, in quanto essa stessa è simmetrica rispetto all'asse x)



In questo modo si definisce un'operazione "somma" tra i punti della curva che dà come risultato sempre un altro punto della curva; bisogna poi verificare che questa operazione sia anche associativa (e lo è, inoltre è anche evidentemente commutativa), che esista l'elemento neutro* e che ogni elemento abbia il suo inverso. Si ha quindi che E(R)** è un gruppo abeliano (vuol dire commutativo).

Alcune note:

*se si considerano due punti simmetrici rispetto all'asse x, in quel caso la retta che li unisce è parallela all'asse y; poichè la somma di due punti deve dare come risultato sempre un altro punto del gruppo, si deve aggiungere ai punti della curva un punto O all'infinito che diventa lo zero (l'elemento neutro) di questo gruppo;  ne consegue che due punti che sono simmetrici rispetto all'asse x sono uno l'opposto dell'altro, poichè la loro somma dà O come risultato
                                          
                                                                  O=A+B




Ma per sommare invece un punto A a se stesso, come scegliere la direzione della retta passante per A?
Basta prendere la tangente alla curva proprio in A:



**una caratteristica notevole delle curve ellittiche è che anche se i valori delle coordinate appartengono a un sottocampo di R, i punti così ottenuti costituiscono ancora un gruppo utilizzando la stessa operazione somma definita in precedenza (E(K) è quindi un sottogruppo di E(R)). Nel caso di E(K), come abbiamo già visto in precedenza, esso è un gruppo ciclico (quindi abeliano) e ha inoltre un numero primo di elementi, si tratta cioè di un gruppo i cui elementi si possono tutti generare a partire da un qualsiasi suo elemento G ≠ 0:

G                              = 1*G              
G+G                          = 2*G
G+G+G                     =  3*G
G+G+G+G                 =  4*G
............
G+G+G+......+G        = (n-1)*G
G+G+G+.....+G+G    =  n*G  = 0 (che è come dire che (n-1)*G è l'opposto di G!)



L'operazione "somma", che ha in origine una costruzione puramente geometrica, si può tradurre nelle seguenti formule utilizzando la geometria analitica:




NB: giova ricordare che tutte le operazioni sopra indicate vanno fatte modulo p nel caso della curva secp256k1 poichè le coordinate in quel caso sono elementi di Fp.
Dovevo specificare che:

NB2:
se A è diverso da B, e xA = xB allora A+B = 0 (punto all'infinito), quindi in tal caso non si applica la formula della somma di due punti (semplicemente una retta verticale non ha coefficiente angolare, quindi è inutile tentare di dividere per 0)

se A = B, e yA=0 allora A+B=2A = 0 (punto all'infinito), quindi in tal caso non si applica la formula di duplicazione (questo caso può essere visto come un caso particolare del caso precedente)

Osservazione:

A e B sono opposti se e solo se A=m*G e B=(n-m)*G, in tal caso infatti A+B = m*G + (n-m)*G = n*G = zero

ma A e B sono opposti, per costruzione geometrica, anche se e solo se hanno stessa x e y opposta (o y=0)

da ciò si deduce che se m è la chiave privata relativa al punto A(x,y), allora n-m è la chiave privata relativa al punto simmetrico A'(x,-y).

Teoremi sulle curve ellittiche


Per le curve ellittiche in generale, valgono i seguenti tre teoremi:

1) Sia K un campo e supponiamo che sia data una curva ellittica E di equazione:


Sia E(K) l'insieme dei punti della curva E a coordinate in K

Allora E(K) è un sottogruppo del gruppo di tutti i possibili punti di E (dove con E possiamo pensare a E(R) con R insieme dei numeri reali)  (teorema di Poincarè, intorno al 1900)


2) Se Fp è un campo finito, allora il gruppo dei punti E(Fp) è sempre o ciclico o prodotto di due gruppi ciclici.


3) Sia E l'insieme dei punti della curva ellittica

Allora |#E (Fp) - (p + 1)|< 2rad(p)
(stima sul numero di punti di E(Fp) di Hasse, 1922)

Il primo teorema ci assicura un fatto notevole, e cioè che l'insieme dei punti di una qualsiasi curva ellittica a coordinate in un campo finito costituisce sempre un gruppo (vedremo rispetto a quale operazione di "addizione" particolare)  

Questo fatto è sensazionale, cioè se definisco un'operazione algebrica su E(R) (cioè sulla classica curva nel piano cartesiano), poi con la stessa operazione su E(K), dove K è un qualsiasi sottocampo di R, sono sicuro di trovare ancora un sottogruppo di E(R),  cioè sono sicuro ad esempio che la somma di 2 punti sulla curva a coordinate in F7 è ancora un punto a coordinate in F7 che sta sulla curva !

Il secondo teorema ci dice qualcosa di importante sulla struttura algebrica di E(Fp) (nel caso specifico della secp256k1, i punti della curva costituiscono proprio un gruppo ciclico)

Il terzo teorema ci fornisce una stima sul numero degli elementi di questo gruppo, stima che si basa sul numero degli elementi del campo delle coordinate. In sostanza esso ci dice che la differenza tra il numero n dei punti della curva e il numero p degli elementi del campo è trascurabile rispetto al numero p degli elementi del campo. Quindi dal momento che il nostro campo Fp ha p elementi, allora anche la curva E(Fp) dovrà avere un numero n di elementi che è all'incirca pari a p più o meno 2 radice di p.
 
Per l'uso crittografico però non è sufficiente la stima ma bisogna conoscere il numero esatto degli elementi (e in generale non è affatto banale riuscire a calcolare questo numero).

Nel caso della curva secp256k1 i suoi punti costituiscono un gruppo ciclico e il numero dei suoi elementi (è sempre un numero primo) è  

n=115792089237316195423570985008687907852837564279074904382605163141518161494337
  
Se confrontiamo n con p

n=115792089237316195423570985008687907852837564279074904382605163141518161494337  (numero di punti, compreso il punto all'infinito)
p=115792089237316195423570985008687907853269984665640564039457584007908834671663  (valori possibili per le coordinate dei punti)

osserviamo che il numero di punti della curva è dello stesso ordine di grandezza del numero degli elementi del campo (un po' inferiore, la differenza è dell'ordine di radice di p).
Il numero di punti è importantissimo, poichè ci fornisce il periodo del gruppo che è lo "spazio" all'interno del quale girano gli algoritmi di firma digitale. Da notare che n (come p) è rappresentabile mediante una stringa di 256 bit (da qui il nome secp256k1), misura comoda per l'implementazione nel calcolatore.
Il numero di elementi di questo gruppo è quindi all'incirca simile al numero degli elementi del campo.


A questo punto potremmo anche chiederci quanti sono i diversi valori che effettivamente sono assunti dalle coordinate x e y dei punti della curva.

Per stabilire quanti sono gli elementi x che vengono mappati in y dalla funzione:

y = sqrt(x^3 + 7)

dobbiamo prendere il numero n - 1 (il numero dei punti che hanno effettivamente le coordinate in Fp e che corrisponde quindi al massimo numero di potenziali valori distinti sia per x che per y) e dividerlo per 2 : per ogni valore effettivamente assunto dalla coordinata x di un punto infatti ci sono due possibili valori di y, y = sqrt(x^3 + 7) e y = - sqrt(x^3 + 7) , ricordiamo che l'equazione da soddisfare è y^2 = x^3 + 7 mod p, ovvero per ogni x tale che x^3 + 7 ammetta la radice quadrata in Fp ci sono 2 radici quadrate (2 valori possibili di y).

Quindi avremo (n - 1) / 2 valori distinti per x (si noti che questo equivale a dire che all'incirca poco meno della metà dei valori di Fp sono assunti dalla coordinata x dei punti della curva dal momento che p è poco più grande di n).

Per quanto riguarda invece il numero dei diversi valori assunti dalla coordinata y, bisogna prendere n - 1 e dividerlo per 3 (per dettagli sul motivo si veda questo post)

Definizioni di algebra


Un campo è un insieme di elementi (numeri) per i quali sono definite due operazioni matematiche - addizione e moltiplicazione - ciascuna delle quali applicata a ogni coppia di elementi dell'insieme dà come risultato un elemento dell'insieme stesso.

Le due operazioni devono soddisfare la proprietà associativa e commutativa, deve valere la proprietà distributiva della moltiplicazione rispetto all'addizione, infine per ogni elemento del campo deve essere presente nel campo stesso il suo opposto (un numero che sommato al primo dà come risultato il numero 0, elemento neutro dell'addizione) e per ogni elemento del campo (tranne lo 0) deve essere presente anche il suo inverso (un numero che moltiplicato al primo dà come risultato 1, l'elemento neutro della moltiplicazione). In sostanza l'esistenza degli opposti e degli inversi è un po' come dire che sono implicitamente definite anche le operazioni di sottrazione (a - b = a + (-b)) e di divisione per un elemento diverso dallo zero ( a / b = a * b^(-1)).

Per fare degli esempi, l'insieme dei numeri naturali con le usuali operazioni di addizione e moltiplicazione non è un campo, poichè nessun altro numero naturale a parte lo 0 ha il suo opposto all'interno di quell'insieme (in maniera equivalente, l'insieme dei naturali non è chiuso rispetto alla sottrazione); l'insieme dei numeri interi relativi non è un campo perchè a parte il numero 1 nessun altro numero ha il suo reciproco (non è chiuso rispetto alla divisione). L'insieme dei numeri razionali è invece un campo infinito, così come lo è l'insieme dei numeri reali.

Un'ultima osservazione sul numero di elementi che compongono il campo finito K a cui appartengono le coordinate dei punti della curva secp256k1; questo numero è
  
                                              
dove p sta a indicare che si tratta di un numero primo; per la teoria dei campi ogni campo finito deve avere un numero di elementi che sia primo (p) o potenza di un primo (p^n).
Nel caso della secp256k1, E = E(Fp), Fp è il campo delle coordinate, dove p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1, quindi siamo nel primo caso.


Un gruppo è un insieme in cui è definita una sola operazione che soddisfa la proprietà associativa, è presente l'elemento neutro rispetto a quella operazione e inoltre il gruppo contiene l'inverso di ogni suo elemento.

Quindi per quanto detto in precedenza:

1) un campo K  è un gruppo commutativo rispetto all'operazione di addizione
2)  K - {l'elemento neutro dell'addizione} è un gruppo commutativo rispetto all'operazione di moltiplicazione


Ordine di un gruppo

Sia G un gruppo. L'ordine di G è il numero (finito o infinito) degli elementi di G e si indica con o(G).

Ordine di un elemento di un gruppo

Sia G un gruppo con elemento neutro "e".  Sia "a" un elemento di G diverso da "e".
L'ordine (additivo) di a è il più piccolo intero positivo n tale che a+a+a+a+....+a = n*a= e, se tale intero n non esiste si dice che a ha ordine infinito. L'ordine di a (finito o infinito) si indica con o(a).

(l'espressione "ordine di un elemento a" deriva dal fatto che scegliere un punto a di partenza (un generatore) equivale di fatto a imporre un ordine con cui descrivere tutti gli altri elementi del gruppo: 2*a, 3*a, 4*a, 5*a, ... ordine che dipende quindi dal punto di vista particolare di a; l'insieme dei punti della curva secp256k1 costituisce un gruppo additivo, e gli scalari 2, 3, 4, 5, ... rappresentano l''ordine' con cui si ottengono i vari punti a partire da un punto particolare chiamato "g", il generatore della curva scelto dalla SEC. I 'numeri d'ordine' 2, 3, 4, 5,... corrispondono alle chiavi private dei punti/chiavi pubbliche: 2*g, 3*g, 4*g, 5*g, ...).

NB: se invece consideriamo un gruppo G moltiplicativo, allora l'ordine (moltiplicativo) di un elemento a è per analogia il più piccolo intero positivo m tale che a*a*a*...*a = a^m = e , dove 'e = 1' in questo caso è l'elemento neutro della moltiplicazione.


Dato un elemento 'a' di ordine m, l'insieme {a^0 = 1, a^1, a^2, ...., a^(m-1)} è a sua volta un sottogruppo di G.  Se esiste almeno un elemento 'a' il cui ordine coincide con l'ordine del gruppo, allora 'a' si dice generatore del gruppo, poichè il sottogruppo di G generato dalle potenze di 'a' coincide con G stesso. Notazione: = G.
In questo caso G si dice gruppo ciclico. I gruppi ciclici sono tutti isomorfi a Zp (o a Z se hanno ordine infinito).

Nel caso del gruppo G dei punti della curva secp256k1, esso è un gruppo ciclico di ordine n rispetto all'operazione di addizione, e l'elemento g scelto dalla SEC si chiama appunto generatore della curva perchè = G (il generato di g coincide con G e per costruzione tutti i generati sono gruppi ciclici perchè ottenuti appunto facendo il 'ciclo' su tutte le potenze/multipli di un elemento dato).

  = {g, g+g, g+g+g, 4*g, 5*g, ....., (n-1)*g} = G = E(Fp)   (si noti in questo caso la notazione additiva anzichè quella moltiplicativa)

Ma n è primo, e questo fatto conferisce un'ulteriore importante proprietà algebrica a questa curva: poichè n è primo si può dedurre che ogni elemento di G escluso lo 'zero' (il punto all'infinito) genera mediante tutti i suoi multipli tutto G.

Questo fatto in generale non è vero per tutti i gruppi ciclici, ovvero un gruppo per essere ciclico deve avere almeno un elemento il cui ordine coincide con quello del gruppo stesso, ma non è detto che tutti gli altri elementi del gruppo diversi dall'elemento neutro abbiano questa proprietà.

Si può dimostrare però una relazione interessante (e banale a livello aritmetico) tra l'ordine di un gruppo finito e l'ordine possibile di un qualsiasi suo elemento (ovvero: c'è una relazione precisa tra l'ordine del gruppo finito e l'ordine di un suo qualsiasi sottogruppo).


Teorema di Lagrange

Il teorema di Lagrange è un teorema basilare nello studio dei gruppi finiti. Esso afferma che ogni sottogruppo di un gruppo finito ha ordine (cioè ha un numero di elementi) che divide l'ordine del gruppo (cioè il numero di elementi del gruppo).

|G|=|A| * |G:A|  per ogni sottogruppo A di G (|A| indica il numero di elementi di A, per G:A vedere qui  e qui ma si tratta di dettagli non importanti al fine della comprensione del nostro discorso).

NB:
Tecnicamente si dice che l'ordine del sottogruppo deve dividere l'ordine del gruppo, e il risultato del rapporto ordine del gruppo / ordine del sottogruppo (numero elementi del gruppo / numero elementi del sottogruppo) è un numero intero detto "cofattore". Se si va qui (https://en.bitcoin.it/wiki/Secp256k1 si osservi il parametro h nell'ultima riga) si vedrà che nella secp256k1 il cofattore del gruppo generato dal punto base è uguale a 1, cioè l'ordine del punto base scelto dalla SEC è esattamente uguale all'ordine di E(Fp), entrambi sono n.


Ma questo fatto non è un caso: la curva secp256k1 infatti costituisce un gruppo finito con un numero primo n di elementi, e ora grazie al teorema di Lagrange possiamo dedurre da questo fatto che

1) G è ciclico poichè un suo elemento diverso da 0 deve avere ordine maggiore di 1 (altrimenti non genera un sottogruppo) e l'unico ordine maggiore di 1 che sia anche divisore di 'n' primo è 'n' stesso.

2) l'ordine di ogni suo elemento (a parte lo 0) deve coincidere per forza con l'ordine del gruppo (che essendo primo non ha altri divisori all'infuori di se stesso), cioè è possibile generare ogni elemento del gruppo a partire da un qualsiasi altro suo elemento (elemento neutro escluso). La scelta del punto base della SEC quindi è del tutto arbitraria (qualsiasi altro punto sarebbe andato bene).

3) per ogni elemento a di G vale che a^ordine(G) = 'e'  (elemento neutro). Questo fatto è la traduzione del punto 2) e si ottiene applicando semplicemente la definizione di ordine di un elemento.

quest'ultima equazione nel caso della curva G si declina osservando che n*a = punto all'infinito per ogni a di G, nel caso del campo Fp delle sue coordinate diventa in notazione moltiplicativa a^(p-1) = 1 mod p (si vedano le prossime righe per la spiegazione, e qui per le ricadute pratiche a livello di calcoli)


Teoria dei campi finiti

Nel caso dei campi, che ripetiamo sono gruppi commutativi rispetto all'operazione di addizione e, tolto lo zero, sono anche gruppi commutativi rispetto alla moltiplicazione, è sempre bene specificare quando si parla di ordine di un elemento se si intende ordine additivo o ordine moltiplicativo.

Nel caso di Fp, il campo delle coordinate della nostra curva, l'ordine additivo di ogni elemento 'a' è p, mentre l'ordine moltiplicativo è p - 1.
Questo implica che

1) a+a+a+....+a = p*a = 0  mod p

2) a*a*a*a*...*a = a^(p-1) = 1  mod p

Dall'ultima uguaglianza si ricava anche che a^(p-2) = a^-1 mod p, ovvero si ricava un modo pratico (anche se computazionalmente oneroso) per calcolare l'inverso di ogni elemento. Per un metodo più efficiente si veda l'identità di Bezout (pagg. 43 -45, soprattutto l'esempio pratico 3.35) e l'algoritmo che implementa il tutto.

Per la teoria dei campi ogni campo finito deve avere un numero di elementi che sia primo (p) o potenza di un primo (p^n).

Se il campo ha un numero primo di elementi allora è un gruppo ciclico (rispetto all'operazione di addizione) ed è isomorfo a  Z/pZ , cioè dal punto di vista delle sue proprietà algebriche è equivalente al campo delle classi di resto modulo p. In particolare quindi il campo Fp delle coordinate della nostra curva è isomorfo a Z/pZ.  

Ma si può dimostrare anche che Fp - {0} è un gruppo ciclico rispetto all'operazione di moltiplicazione pur avendo p-1 elementi (cioè un numero pari di elementi).



Cosa vuol dire campo delle classi dei resti delle divisioni tra interi modulo p? (per una trattazione esaustiva si veda qui)

Facciamo un esempio nel caso p=5,  Z/5Z = { [ 0], [1], [2], [3], [4]}

Perchè le parentesi quadre? Perchè 3 = 8 = -2 = 28 = 23 = 33 = -7 = --- --> tutti questi numeri sono equivalenti poichè si possono scrivere nella forma  3 + 5*k  per qualche k intero, ovvero diminuiti di 3 sono tutti multipli di 5.

Quindi poichè i resti delle divisioni di tutti questi numeri per 5 sono tutti uguali a 3 si introduce la classe di equivalenza dei numeri interi per i quali i resti della divisione per 5 coincidono appunto con 3 --> { 3, 8, 13, 18, 23, 28, 33, ....., -2, -7, -12, -17, ....} = [3]  

L'insieme di tutte queste classi di equivalenza (con i resti che possono variare quindi tra 0 e 4) si indica con Z5.


addizioni: [2]+[3] = [ 0], poichè (2 + k1*5) + (3 + k2*5) = 5 + (k1+k2)* 5 = 0 + (1+k1+k2)*5  = [ 0]

analogamente (trascuro le parentesi per comodità):  3+4=2, poichè 3+4=7 e 7 equivale a 2 modulo 5.

moltiplicazioni: 2*3=1, poichè 2*3=6 e 6 equivale a 1 in questo campo.

Indice:

• Curve ellittiche: punti, coordinate, scalari
• Definizioni di algebra
• Teoremi sulle curve ellittiche
•  Addizione tra due punti:
  
  • definizione in cioè nel continuo
  • esempio in cioè nel discreto
• Crittografia e algoritmo ECDSA
  
  • Generazione di una chiave pubblica da una chiave privata
  • Firma digitale di un messaggio mediante una chiave privata
  • Verifica della firma digitale mediante la chiave pubblica
  • Esempio pratico di firma di un messaggio e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1
  • Libreria micro_ecdsa
  • Esempio pratico di firma di una transazione bitcoin

---

Curve ellittiche: punti, coordinate, scalari:

Vediamo una breve trattazione matematica delle curva secp256k1 (così chiamata, secondo la classicazione "Standards for Efficient Cryptography" (SEC), vedi http://www.secg.org/sec2-v2.pdf a pagina 9), la curva impiegata nel protocollo Bitcoin.

Le curve ellittiche in generale hanno equazione ,  e poco hanno a che fare con l'ellisse, nonostante il loro nome.  

In particolare la curva ellittica secp256k1 utilizzata nel mondo Bitcoin è la curva di equazione:


cioè è l'insieme dei punti P(x,y) del "piano cartesiano" le cui coordinate x e y soddisfano quell'equazione particolare.  


Le coordinate dei punti delle curve ellittiche

I valori che può assumere la coordinata x (e di conseguenza anche la coordinata y) non sono però tutti gli infiniti valori reali (come succede invece a scuola quando si studiano le rette o le parabole ) ma sono solo i valori che corrispondono a elementi di un insieme molto particolare, detto campo, che indicheremo con . Quindi quando parliamo di "piano cartesiano" intendiamo in realtà i punti (coppie di coordinate) che appartengono al prodotto cartesiano .
Anche i numeri reali costituiscono un campo, nel caso della secp256k1 "ovviamente" è un sottoinsieme finito di , ma rimane sempre un campo ("ovviamente" nel senso che applicazioni pratiche e infinito non vanno d'accordo!)

Quindi i punti della curva secp256k1 hanno come coordinate possibili solo gli elementi del campo finito .


I punti della curva secp256k1


I punti della curva costituiscono a loro volta un insieme finito (ovviamente, visto che le coordinate possibili di questi punti sono in numero finito) detto gruppo, che indicheremo con o . Per quanto detto prima è un sottoinsieme di .
Si dimostra che E(Fp) è un gruppo ciclico; inoltre il numero di elementi di questo gruppo è a sua volta un numero primo che è all'incirca simile al numero totale degli elementi del campo (ma non è uguale, sono 2 numeri primi diversi, vedi approfondimenti)


Oltre alle coordinate (campo K) e ai punti della curva (gruppo ciclico E(K)), è presente una terza tipologia di elementi, che non hanno dietro una struttura algebrica a differenza degli elementi citati finora: gli scalari.

Gli scalari

Dove intervengono gli scalari?

Esempio: quando sommiamo un punto A con se stesso 7 volte:


possiamo indicare questa somma come 7*A.
Gli scalari quindi in questo contesto sono sostanzialmente dei semplici numeri interi che servono solo come contatori e che non hanno alcuna struttura algebrica dietro.  Gli scalari in questo caso sono importantissimi però poichè è proprio su quest'ultimi che lavora in gran parte l'algoritmo di firma digitale. In sostanza gli scalari tengono conto di quanti "movimenti" abbiamo fatto nello spazio dei punti del gruppo ciclico E(K).

Le chiavi private sono esse stesse degli scalari! (mentre le chiavi pubbliche sono punti della curva).


Nel nostro caso, i punti della secp256k1 costituiscono quindi un gruppo ciclico formato da un numero primo di elementi, da ciò si ottiene che partendo da un punto qualsiasi della curva (diverso dallo 0) si possono ottenere tutti gli altri punti della curva (vedere il post 2 sulle considerazioni matematiche).

Nella secp256k1 si è deciso di partire dal punto G = (Gx, Gy):

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
      32670510020758816978083085130507043184471273380659243275938904335757337482424)

Si osservi innanzitutto che entrambe le coordinate sono minori di p=115792089237316195423570985008687907853269984665640564039457584007908834671663

Facciamo un rapido controllo per verificare che G appartenga veramente alla curva seckp256k1, ovvero che Gx^3+7-Gy^2 sia uguale a 0 modulo p:



tutto ok!

Da G è possibile raggiungere tutti gli altri punti della curva moltiplicando il punto G stesso per uno scalare qualsiasi che va da 1 a n
(n = 115792089237316195423570985008687907852837564279074904382605163141518161494337)

G                              = 1*G              
G+G                          = 2*G
G+G+G                     =  3*G
G+G+G+G                 =  4*G
............
G+G+G+......+G        = (n-1)*G
G+G+G+.....+G+G    =  n*G  = 0  

L'espressione "moltiplicare G per uno scalare s" è solo un altro modo di dire "sommare il punto base G a se stesso s volte"

s è la chiave privata che il vostro software wallet pesca random tra 1 e n-1, s*G è la chiave pubblica relativa

NB: le chiavi private "0" o "n" non sono valori consentiti nell'ECDSA, quindi se inviate bitcoin all'indirizzo che si ottiene facendo l'hash del punto all'infinito che è associato a quegli scalari (punto che per pura convenzione si rappresenta mediante le coordinate (0,0)), nessuno sarà in grado di spendere quei bitcoin, poichè la chiave privata "0" (oppure "n") nonostante matematicamente sia associata al punto all'infinito non è considerata valida per firmare le transazioni.