⭐ Merited by fillippone (8) ,Piggy (5) ,picchio (3) ,LordStapy (3) ,coinlocket$ (2) ,duesoldi (1) ,jqprez (1)
Indice:
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 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:
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. Quindi quando parliamo di "piano cartesiano" intendiamo in realtà i punti (coppie di coordinate) che appartengono al prodotto cartesiano K x K.
Anche i numeri reali costituiscono un campo, nel caso della secp256k1 "ovviamente" K è un sottoinsieme finito di 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). Per quanto detto prima E(K) è un sottoinsieme di K x K.
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.
- Curve ellittiche: punti, coordinate, scalari
- Definizioni di algebra
- Teoremi sulle curve ellittiche
- Addizione tra due punti:
- 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 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. Quindi quando parliamo di "piano cartesiano" intendiamo in realtà i punti (coppie di coordinate) che appartengono al prodotto cartesiano K x K.
Anche i numeri reali costituiscono un campo, nel caso della secp256k1 "ovviamente" K è un sottoinsieme finito di 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). Per quanto detto prima E(K) è un sottoinsieme di K x K.
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:
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 (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.