Curve ellittiche e algoritmo ECDSA

[ratings]

Un interessante post dell’utente arulbero ci istruisce sull’algoritmo ECDSA utilizzato da Bitcoin per garantire che i fondi possono essere spesi solo dai loro legittimi proprietari.

L’articolo viene inserito così come è stato pubblicato sul forum bitcointalk:

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.algoritmo ECDSA

Le curve ellittiche in generale hanno equazione y^2 = Ax^3+Bx+C,  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:

y^2=x^3+7

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 y=ax+b o le parabole y=ax^2+bx+c) ma sono solo i valori che corrispondono a elementi di un insieme molto particolare, detto campo, che indicheremo con K. Anche i numeri reali costituiscono un campo, nel caso di secp256k1 “ovviamente” K è un sottoinsieme finitodi R, 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 K.

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 E(K) o E(Fp).
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 possibile 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:

A+A+A+A+A+A+A

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.

Nella secp256k1 si è deciso di partire dal punto G

G = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

e 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-1 (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.

Definizioni matematiche

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 reciproco (un numero che moltiplicato al primo dà come risultato 1, l’elemento neutro della moltiplicazione).

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; l’insieme dei numeri interi relativi non è un campo perchè a parte il numero 1 nessun altro numero ha il suo reciproco. 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 è

p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1

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.

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), dove p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1, quindi siamo nel primo caso.

Teoria dei campi

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 ed è isomorfo a  Z/pZ , cioè dal punto di vista delle sue proprietà algebriche è equivalente al campo delle classi di resto modulo p.

Cosa vuol dire campo delle classi di resto modulo p?

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

addizioni: 2+3=0, poichè 2+3=5 e 5 equivale a 0,  3+4=2, poichè 3+4=7 e 7 equivale a 2.

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

 

Approfondimenti:
Teoremi sui punti di E(Fp)

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:

y^2=x^3 + Ax + B,  con A, B appartenenti a K

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

E(K) = (x,y) in E, con x,y in K   a cui si aggiunge il punto O (punto all’infinito)

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

y^2= x^3+ Ax + B    con  A,B coordinate in Fp.

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 forma 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.
Nel caso quindi 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)
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).
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.

Addizione in E(K): dalla geometria all’algebra

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.

Esempio di punti a coordinate in un campo finito (F_11)

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.