curve ellittiche e algoritmo ECDSA

[arulbero]

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:

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.

[1714189511]

1714189511

[1714189511]

1714189511

[1714189511]

1714189511

[arulbero]

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 è
  
                                              

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

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: <a> = 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> = 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+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.

[arulbero]

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:

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 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)

[arulbero]

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

[arulbero]

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.

[arulbero]

• 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

Crittografia e algoritmo ECDSA

La crittografia viene utilizzata per rendere possibili uno dei due seguenti scenari:

1.   A vuole mandare un messaggio segreto a B, in modo che solo B possa leggerne il contenuto (A deve codificare un messaggio mediante una chiave pubblicata da B e quindi nota a tutti, inviarlo a B che lo decodifica mediante la chiave privata che "inverte" l'azione di quella determinata chiave pubblica; in tutto questo processo il messaggio rimane segreto al resto del mondo)

2.   A  vuole inviare un messaggio pubblico a B; poichè il messaggio è pubblico A deve tutelare se stesso (e B) dal fatto che qualcun altro si interponga tra A e B e possa modificare il nome del mittente del messaggio o qualunque altra parte del messaggio stesso (A firma il messaggio con la sua chiave privata, lo invia a B che verifica a sua volta con la chiave pubblica relativa che il messaggio sia stato effettivamente firmato da chi possiede la chiave privata relativa e non sia stato modificato, in tutto questo processo il messaggio è sempre visibile al resto del mondo)

Nel sistema Bitcoin i messaggi si chiamano transazioni (perchè spostano del valore - rappresentato dalla moneta Bitcoin - da un utente a un altro). Quindi d'ora in poi considereremo i termini "messaggi" e "transazioni" come sinonimi.   Poichè tutte queste transazioni devono essere pubbliche, la crittografia nel sistema Bitcoin viene utilizzata per rispondere alle esigenze evidenziate nello scenario 2, cioè viene utilizzata per certificare di fronte a tutto il mondo che una transazione sia stata effettivamente effettuata dall'autore dichiarato nel messaggio e che la transazione non sia stata manomessa in alcuna sua parte.

Il metodo crittografico scelto per certificare le transazioni nel mondo dei Bitcoin si basa su un algoritmo di firma digitale che lavora con curve ellittiche detto ECDSA (Elliptic Curve Digital Signature Algorithm).

Le curve ellittiche entrano in scena nelle seguenti tre situazioni:

•   GENERAZIONE DI UNA CHIAVE PUBBLICA A PARTIRE DA UNA CHIAVE PRIVATA: quando si genera un indirizzo di un portafoglio; l'algebra delle curve ellittiche è alla base del meccanismo che permette di ricavare da una chiave privata una chiave pubblica; la chiave pubblica viene poi trasformata con un ulteriore passaggio (vedi http://gobittest.appspot.com/Address) in un indirizzo Bitcoin

•   FIRMA DIGITALE DI UNA TRANSAZIONE/MESSAGGIO CON LA CHIAVE PRIVATA: quando A deve effettuare un pagamento; A deve firmare mediante la propria chiave privata la transazione/messaggio di pagamento, per certificare in modo visibile a tutti la validità di questo atto di pagamento; la firma di A è necessaria per muovere dei fondi da un certo indirizzo, questa firma è ottenuta applicando in modo appropriato la chiave privata alla transazione (o meglio: al doppio hash della transazione) da eseguire

•   VERIFICA DELLA FIRMA DIGITALE MEDIANTE LA CHIAVE PUBBLICA: quando un nodo della rete, addetto alla convalida delle transazioni, alla trasmissione di quest'ultime alla rete e alla loro registrazione in un registro pubblico detto "block chain", deve verificare mediante la chiave pubblica che la transazione sia stata firmata effettivamente dalla chiave privata corrispondente (pur senza conoscerla) e che la transazione non sia stata modificata in alcuna sua parte



Generazione di una chiave pubblica a partire da una chiave privata


Si fissa un punto G della curva (che nel caso della secp256k1 è stato fissato dalla SEC), si sceglie un numero casuale d tra 1 e n - 1 (dove n è l'ordine di G), e si ottiene così la chiave pubblica P = d*G.

Facciamo un esempio nel caso semplificato di

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}

Scegliamo un punto base. Proviamo con A = (2,2)

Osserviamo che o(A) = 4  (l'ordine di A) infatti

A+A=2*A=D    (vedi calcolo effettuato in precedenza,  D(5,0) )

A+A+A=3*A=2*A+A=D+A=A'



A+A+A+A= 4*A = 3*A+A = A'+A = O

Poichè A ha ordine un numero non primo, non è un buon candidato per essere scelto come punto base. (NB: in questo caso o(A) = 4, quindi il cofattore o(E) : o(A) sarebbe uguale a 3 )

Proviamo con B = (3,1). Si può verificare che esso ha periodo 12, cioè B genera tutto E(F_11) (<B> = E(F_11)) (NB: in questo caso il cofattore è 1, così come succede per la curva secp256k1, da ciò si deduce che E(F_11) è un gruppo ciclico, anche se non ha un numero primo di elementi).

Quindi:

E = E(F_11)  

G (il punto base della curva) = B

d (la chiave privata) = 4 (numero scelto a caso tra 1 e 11)

P (la chiave pubblica corrispondente a d=4) = 4*B = 2*(2*B) = (3,-1) .



Firma digitale di un messaggio mediante una chiave privata

Che cos'è una firma? E' una coppia di numeri r , s  (entrambi di lunghezza max 256 bit, minori di n) che si ottengono a partire da:

il messaggio m** , la chiave privata d, un numero casuale k

**ciò che si firma realmente non è il messaggio originale, ma una sua "impronta digitale" (detta "message digest", una stringa di 256 bit), impronta che è il risultato di un doppio hash del messaggio originale; nel caso particolare in cui si firma non un messaggio qualunque ma una transazione è da sottolineare come si effettua il doppio sha256 della transazione quando essa è ancora in una forma incompleta e non definitiva (è chiaro che nel momento in cui si firma una transazione la firma stessa non può essere già presente nella transazione stessa! Quindi a rigore in quel caso non si firma neanche tutto il messaggio, messaggio che però deve alla fine contenere anche la firma come sua parte essenziale --> a sottolineare la natura "spuria" della firma rispetto al resto della transazione è recentemente intervenuto il soft fork "segregated witness" (firma separata), dove di fatto la firma viene considerata una parte a se stante della transazione ed è trattata in modo particolare.

Algoritmo di generazione della firma

1. Scegliere un numero intero casuale k nell'intervallo [1,n-1]  (dove n è l'ordine della curva)

2. Calcolare il punto della curva X1 = k*G = (x1,y1), convertire x1 in uno scalare e porre  r = x1 mod n
(ritornare al passo 1 se r = 0; qui G è il generatore della curva, lo stesso utilizzato per passare dalle chiavi private alle chiavi pubbliche; la conversione di x1 in intero implica passare dal campo Fp delle coordinate all'insieme degli scalari)

3. Calcolare e = hash(m)    (nel caso della secp256k1, si utilizza la funzione crittografica sha256 applicata 2 volte, in questo modo si traduce un messaggio in uno scalare di 256 bit confrontabile con gli altri scalari; applicare 2 volte l'hash rende l'operazione più resistente al cosiddetto "length extension attack"  --> https://en.wikipedia.org/wiki/Length_extension_attack)

4. Calcolare  s = k^-1 * (r*d + e)  mod n
(ritorna al passo 1 se s = 0)

5. La firma è la coppia (r, s)

Osservazioni:

tutte le operazioni (a parte il passaggio 2) si fanno sugli scalari, quindi si lavora sempre modulo n (non p!)

r è  la coordinata x di un punto del tutto casuale della curva che si ottiene moltiplicando G per uno scalare k generato al momento (scalare che si può vedere come un'altra chiave privata "usa e getta" generata al volo per l'occasione); r è la prima parte della firma

s è ottenuto a partire dalla coordinata r che viene moltiplicata per la chiave privata d; a questo prodotto viene poi aggiunta l'informazione e che dipende dal messaggio m (e = sha256(sha256(m))); il tutto è moltiplicato per l'inverso di k modulo n;  

s è ottenuto quindi a partire da r, per mezzo del messaggio m e della chiave privata d  
la verifica consiste nel procedimento inverso:  si parte da s e si ricostruisce r usando il messaggio m e la chiave pubblica P corrispondente alla chiave privata d (nella verifica non si utilizza mai nè la chiave privata d nè il numero casuale k, che devono rimanere sconosciuti!)


Nota bene:

firmare due transazioni con lo stesso numero k casuale (che produce quindi lo stesso valore di r) rende immediatamente ricavabile dalla chiave pubblica la chiave privata: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
problemi legati a cattive firme: https://bitcointalk.org/index.php?topic=271486.msg2907468#msg2907468


Verifica della firma digitale mediante la chiave pubblica


VERIFICA DELLA FIRMA DIGITALE MEDIANTE LA CHIAVE PUBBLICA

Algoritmo di verifica della firma

Date la coppia di firme (r, s) del messaggio m and la chiave pubblica P:

1.  Controllare che r e s appartengano entrambi all'intervallo [1,n-1]

2.  Calcolare e = hash(m)    

3. Calcolare w = s^-1  mod n
(qui si utilizza la seconda parte della firma)
  
4. Calcolare  u1 = e*w mod n,     u2 = r*w mod n
(qui si utilizza il messaggio m e la seconda parte della firma per u1, entrambe le parti della firma per u2)

5. Calcolare il punto X = (x0,y0) =  u1*G + u2*P  
 (se X è il punto all'infinito rifiuta; questo è il punto dove si utilizza la chiave pubblica P )

6. Convertire x0 in un intero e porre  v = x0 mod n.

7. Confronta v e r, se v = r allora la firma è corretta.

------------------------------------------------------------------------------------------------------------
Dimostriamo perchè questa verifica è corretta:

Notiamo innanzitutto che k = u1+u2*d, infatti:

k = s^-1 * (e + r*d)  (vedi punto 4 dell'algoritmo di firma)
  = s^-1*e + s^-1 * r*d = u1 + u2*d  mod n  (ricordiamo che   u1=s^-1*e ,  u2=s^-1*r )

Quindi X = u1*G + u2*P = u1*G + u2*d*G = (u1+u2*d)*G = k*G = X1  (ricordiamo che P = d*G ,  X1 = k*G),     ovvero X = X1
-------------------------------------------------------------------------------------------------------------

Nota bene: chi verifica non calcola mai esplicitamente nè k nè d, queste due informazioni rimangono sempre ignote;
chi verifica spezza il percorso che lo porta a X in due parti, cioè decompone k che non conosce in due parti:  k = u1 + u2*d  (il verificatore calcola solo u1 e u2, non conosce d e quindi nemmeno k!)

u1 = s^-1*e (termine che usa il contributo del messaggio e serve  per muoversi dal generatore G verso X)
u2 = s^-1 * r (questa parte serve per muoversi da P invece che da G sempre per raggiungere X; in questo modo il risultato corretto è ottenuto pur non conoscendo la chiave privata d)

Il verificatore grazie a s, che condensa diverse informazioni, riesce a determinare i seguenti due punti,
                                                           A = u1*G    e    B = u2*P
la somma di questi due punti deve dare finalmente X

Alla fine si ottiene quindi che il verificatore ha ricostruito con le informazioni in suo possesso l'identità del punto X che coincide con il punto X1 da cui è partito colui che ha fatto la firma, quindi x0 = x1  ( v = r   mod n )

Riassumendo:

chi fa la firma determina un punto X casuale e fornisce pubblicamente la posizione di X (prima parte della firma), il messaggio, la chiave pubblica e un valore s (seconda parte della firma) che dipende dalla posizione di X, dal messaggio e dalla chiave privata d

chi verifica l'autenticità del messaggio, verifica se, partendo dalla seconda parte della firma s, riesce a invertire il processo per riottenere la prima parte della firma r (che corrisponde alla posizione di X, già nota); per invertire questo processo deve utilizzare due informazioni base: il messaggio m e la chiave pubblica P.



Note finali:

1) quando si firma un messaggio vero e proprio (non una transazione) con un client bitcoin tipo Bitcoin Core viene richiesto esplicitamente di inserire l'indirizzo di chi sta firmando. Bitcoin Core infatti provvede a recuperare la chiave privata associata all'indirizzo in automatico (NB: è possibile firmare solo con un indirizzo di cui si possiede la chiave privata!).
Anche nel caso della verifica, però, viene richiesto solo l'indirizzo, non la chiave pubblica. Ma come è possibile recuperare la chiave pubblica dall'indirizzo? In generale non è possibile. Però nel caso in cui si abbiano a disposizione, oltre all'indirizzo, la firma e il messaggio stesso allora si può ricostruire la chiave pubblica, infatti:

               X = u1*G + u2*P -->  X = s^-1*e*G + s^-1*r*P  

in quest'ultima equazione il destinatario del messaggio che deve effettuare la verifica ha a disposizione tutti i valori tranne uno,  P, che costituisce quindi l'incognita dell'equazione e che si ricava quindi in funzione degli altri dati:

s*X = e*G + r*P
r*P = s*X - e*G
                                P = r^-1 (s*X - e*G)

A questo punto chi verifica si limita a trasformare la chiave pubblica P nell'indirizzo corrispondente e a controllare infine se quest'ultimo coincide con l'indirizzo che gli è stato trasmesso.

Quindi nel caso di un messaggio normale firmato con una chiave bitcoin la verifica non consiste più nel ricavare r a partire da s e da P (oltre che da m), ma invece consiste nel ricavare la chiave pubblica P dalla firma r,s (e dal messaggio m) e nel confrontare quindi l'indirizzo che P genera con quello inviato in chiaro dal firmatario.

2) se (r,s) è una firma valida per il messaggio m, lo è anche (r,-s)  (sostanzialmente il verificatore che parte da -s trova -X1, ma due punti opposti X1 e -X1 hanno sempre la stessa ascissa, quindi anche da -s si riottene sempre r).

Questo fatto consentiva, fino a qualche tempo fa, di prendere una transazione che arrivava nella mempool (quindi una transazione non ancora confermata) e modificare il segno di s. Questa modifica non cambiava di una virgola address di partenza, importo e address di arrivo della transazione, ma provocava un cambio del TXID (cioè del codice identificativo della transazione), che è un hash della transazione intera, firma compresa. In questo caso si parla di "Transaction Malleability".

Bitcoin Core dalla versione 0.11.1 non consente più questa flessibilità che poteva portare problemi:

Inherent ECDSA signature malleability We require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). See reference: Low S values in signatures

quindi all'algoritmo della firma, per precisione, va aggiunto adesso un ulteriore passaggio:

se s è maggiore di (n+1)/2 allora sostituisci s con (n - s)

le versioni più recenti di Bitcoin Core non propagano più quindi transazioni nelle quali le firme presentano una s maggiore di (n+1)/2.




Esempio pratico di firma e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1

[picchio]

Intanto grazie del 3d.
Faccio le domande come a scuola ... ne approfitto!

... 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 giro si trova che dipende da solo due parametri, in pratica https://en.wikipedia.org/wiki/Elliptic_curve indica solo i tuoi B=a, C=b mentre A=1, y^2 ha coefficiente 1 in entrambe. Sono equivalenti le trattazioni?

[picchio]

Vediamo se riesco a comporre una domanda formalmente corretta. Sarebbe già un buon inizio ...
- come viene definita la somma nel gruppo E(K) tra le coppie (a, b) e (c, d) con a, b, c, d in K?
- qual'è l'elemento neutro del gruppo E(K) rispetto alla somma?
- esiste un algoritmo per calcolare n*(a, b) con n, a, b in K, senza fare (a, b) + (a, b) ... + (a, b) n volte?

[arulbero]

- come viene definita la somma nel gruppo E(K) tra le coppie (a, b) e (c, d) con a, b, c, d in K?
- qual'è l'elemento neutro del gruppo E(K) rispetto alla somma?

A queste due domande ho tentato di rispondere nei post 4 e 5 di questo thread.

- esiste un algoritmo per calcolare n*(a, b) con n, a, b in K, senza fare (a, b) + (a, b) ... + (a, b) n volte?

Certo, si basa proprio su n*(a,b), si tratta in sostanza di dividere n in 2^m passi e applicare ricorsivamente la formula di duplicazione 2*(a,b) (però per essere più preciso devo andare a cercarlo)

[picchio]

...
mentre 2*A = A+A si ottiene così

x_2A=((3〖x^2〗_A)/(2y_A ))^2-〖2x〗_A
〖          y〗_2A=((3〖x^2〗_A)/(2y_A ))(x_A-x_2A )-y_A

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.

Non capisco i simboli 〖 ... 〗si puo' riscrivere senza?

[arulbero]

...
mentre 2*A = A+A si ottiene così

x_2A=((3〖x^2〗_A)/(2y_A ))^2-〖2x〗_A
〖          y〗_2A=((3〖x^2〗_A)/(2y_A ))(x_A-x_2A )-y_A

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.

Non capisco i simboli 〖 ... 〗si puo' riscrivere senza?

Avevo copiato da Word e in effetti non si capiva molto. Guarda adesso se si capisce.

[picchio]

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

Scritto cosi' non si capisce bene, magari usa (Gx, Gy) tipo:
G =(79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,  483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8).

CIao
P
EDIT: sto punto G l'ho gia' sentito da qualche parte e mi pare sia anche quello un punto di partenza ma non ricordo dove ...

[picchio]

Riflettendo ora risulta molto chiaro il funzionamento dei vanity gen che permettono di essere sicuri.
Basta dare chiave pubblica e il miner vanity somma G alla chiave k volte fino ad ottenere l'indirizzo desiderato, comunica k al proprietario della chiave privata "n" e genera un indirizzo privato n+k  che magicamente diventa il vanity richiesto.

Dubbi residui:
- come critto un messaggio? Ossia poi, di fatto, come funziona?
- l'applicazione che porta da "private key" a E(Fp) è iniettiva? (in caso sarebbe anche suriettiva visto che hanno lo stesso numero di elementi).
NB: Gran tread! Grazie.

[arulbero]

Riflettendo ora risulta molto chiaro il funzionamento dei vanity gen che permettono di essere sicuri.
Basta dare chiave pubblica e il miner vanity somma G alla chiave k volte fino ad ottenere l'indirizzo desiderato, comunica k al proprietario della chiave privata "n" e genera un indirizzo privato n+k  che magicamente diventa il vanity richiesto.

Dubbi residui:
- come critto un messaggio? Ossia poi, di fatto, come funziona?

Per quanto riguarda l'algoritmo ECDSA, sto preparando la spiegazione!

Non avevo mai pensato al funzionamento del vanity gen, in effetti dovrebbe essere proprio come lo hai descritto!

l'applicazione che porta da "private key" a E(Fp) è iniettiva? (in caso sarebbe anche suriettiva visto che hanno lo stesso numero di elementi).

Sì, una volta scelto il punto base G, detto per questo anche punto generatore di E(FP), c'è una corrispondenza biunivoca tra l'insieme dei naturali compresi tra 1 e n-1 e i punti della curva

Si fissa G (è stato scelto "Standards for Efficient Cryptography" (SEC), vedi http://www.secg.org/sec2-v2.pdf a pagina 9).
Fissato G, è univoco l'ordine con cui percorrere tutti i punti della curva:

1 --> G
2 --> 2*G
3 --> 3*G
..
..
n-1 --> (n-1)*G


la prima colonna è quella delle chiavi private (scalari)
la seconda colonna è quella delle chiavi pubbliche corrispondenti (punti di E(Fp)) (NB: lo scalare 0 non è considerato una chiave privata accettabile nel protocollo bitcoin, quindi 0*G ( o n*G, che è lo stesso) non lo ho inserito nelle possibilità.)

Per ogni chiave privata c'è un'unica chiave pubblica e viceversa.

Le 2 colonne hanno entrambe n-1 elementi (sono circa 2^256, un po' di meno di p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 che è l'ordine del campo delle coordinate). La corrispondenza biunivoca tra i due insiemi è garantita dalla matematica che ho spiegato nei post precedenti (E(Fp) è un gruppo ciclico, l'elemento G è un generatore che permette di riottenere tutti gli altri punti)

La corrispondenza però non è più biunivoca se aggiungiamo una terza "colonna", quella degli indirizzi, che non c'entrano però con le curve ellittiche.

insieme scalari (fissato G)     <-->    insieme di punti di E(Fp)  -->   indirizzi


L'insieme degli indirizzi ha circa 2^160 elementi distinti possibili. Per passare dall'insieme E(Fp) all'insieme degli indirizzi ci sono 2 operazioni, un hash256 e un ripemd160 che traducono una stringa di 256 bit in una di 160 bit (la quale viene poi rappresentata in base 58, ma questo è solo un problema appunto di rappresentazione del risultato finale).

Quindi ci sono tantissime chiavi private (con relative chiave pubbliche) che producono lo stesso indirizzo.***

***EDIT2: in realtà c'è anche un altro problema quando traduciamo un punto della curva in un indirizzo. Poichè la funzione hash lavora in modo stupido solo sulla rappresentazione del punto, se scriviamo un punto di E(Fp) nella sua forma compressa (cioè con solo la coordinata x e il "segno" della y, aggiungendo come prefisso 02 se y è pari e 03 se y è dispari), avremo che lo stesso punto può essere tradotto in due indirizzi completamente diversi (ma controllati sempre dalla stessa chiave privata)

Riporto qui il passo dedicato alla questione in "Mastering Bitcoin"

Compressed public keys

As we saw previously, the public key is a point on the elliptic curve consisting of a pair of coordinates (x,y). It is usually presented with the prefix 04 followed by two 256-bit numbers, one for the x coordinate of the point, the other for the y coordinate. The prefix 04 is used to distinguish uncompressed public keys from compressed public keys that begin with a 02 or a 03.

Here’s the public key generated by the private key we created earlier, shown as the coordinates x and y:

x = F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A
y = 07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

Here’s the same public key shown as a 520-bit number (130 hex digits) with the prefix 04 followed by x and then y coordinates, as 04 x y:

K=04F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

Compressed public keys were introduced to bitcoin to reduce the size of transactions and conserve disk space on nodes that store the bitcoin blockchain database. Most transactions include the public key, required to validate the owner’s credentials and spend the bitcoin. Each public key requires 520 bits (prefix \+ x \+ y), which when multiplied by several hundred transactions per block, or tens of thousands of transactions per day, adds a significant amount of data to the blockchain.

As we saw in the section “Public Keys”, a public key is a point (x,y) on an elliptic curve. Because the curve expresses a mathematical function, a point on the curve represents a solution to the equation and, therefore, if we know the x coordinate we can calculate the y coordinate by solving the equation y2 mod p = (x3 + 7) mod p. That allows us to store only the x coordinate of the public key point, omitting the y coordinate and reducing the size of the key and the space required to store it by 256 bits. An almost 50% reduction in size in every transaction adds up to a lot of data saved over time!

Whereas uncompressed public keys have a prefix of 04, compressed public keys start with either a 02 or a 03 prefix. Let’s look at why there are two possible prefixes: because the left side of the equation is y2, that means the solution for y is a square root, which can have a positive or negative value. Visually, this means that the resulting y coordinate can be above the x-axis or below the x-axis. As you can see from the graph of the elliptic curve in Figure 4-2, the curve is symmetric, meaning it is reflected like a mirror by the x-axis. So, while we can omit the y coordinate we have to store the sign of y (positive or negative), or in other words, we have to remember if it was above or below the x-axis because each of those options represents a different point and a different public key. When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier. Therefore, to distinguish between the two possible values of y, we store a compressed public key with the prefix 02 if the y is even, and 03 if it is odd, allowing the software to correctly deduce the y coordinate from the x coordinate and uncompress the public key to the full coordinates of the point.

Here’s the same public key generated previously, shown as a compressed public key stored in 264 bits (66 hex digits) with the prefix 03 indicating the y coordinate is odd:

K = 03F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A

This compressed public key corresponds to the same private key, meaning that it is generated from the same private key. However, it looks different from the uncompressed public key. More importantly, if we convert this compressed public key to a bitcoin address using the double-hash function (RIPEMD160(SHA256(K))) it will produce a different bitcoin address. This can be confusing, because it means that a single private key can produce a public key expressed in two different formats (compressed and uncompressed) that produce two different bitcoin addresses. However, the private key is identical for both bitcoin addresses.

EDIT: a voler essere pignoli, per ottenere un indirizzo è sufficiente sostituire nel meccanismo una qualsiasi stringa di 256 bit al posto dell'hash256 delle coordinate di un punto della curva ellittica. Non vorrei dire una stupidaggine ma penso che il sistema bitcoin - blockchain sia del tutto indipendente dalla teoria delle curve ellittiche e dall'algoritmo di firma digitale ECDSA.

[gbianchi]

EDIT: a voler essere pignoli, per ottenere un indirizzo è sufficiente fornire una stringa di 256 bit al posto di un punto della curva ellittica. Non vorrei dire una stupidaggine ma penso che il sistema bitcoin - blockchain sia del tutto indipendente dalla teoria delle curve ellittiche e dall'algoritmo di firma digitale ECDSA.

piu' o meno si... nel senso che il merkle tree di bitcoin funzionerebbe con qualsiasi altro sistema di crittografia, pero' fu scelto ECDSA perche
attualmente e' uno di quelli che garantisce alti livelli di sicurezza con chiavi corte... ad esempio con gli algoritmi basati su fattorizzazione tipo  RSA servono 1024 bit o piu' per
avere livelli decenti di sicurezza.... questo sarebbe drammatico per le dimesnioni della blockchain che gia' e' bella pesa...

Inoltre nei client adesso c'e' implementato tutto il codice per la ECDSA

ad esempio la OP_CHECKSIG fa il check presupponendo implicitamente questo particolare modo crittografia,
ossia non ha un parametro che dice "controlla usando  RSA" oppure "controlla usando il sistema di crittografia x"
quindi ci sarebbe da implementare pesantemente sui client .... ma teoricamente e' possibile.

[arulbero]

EDIT: a voler essere pignoli, per ottenere un indirizzo è sufficiente fornire una stringa di 256 bit al posto di un punto della curva ellittica. Non vorrei dire una stupidaggine ma penso che il sistema bitcoin - blockchain sia del tutto indipendente dalla teoria delle curve ellittiche e dall'algoritmo di firma digitale ECDSA.

piu' o meno si... nel senso che il merkle tree di bitcoin funzionerebbe con qualsiasi altro sistema di crittografia, pero' fu scelto ECDSA perche
attualmente e' uno di quelli che garantisce alti livelli di sicurezza con chiavi corte... ad esempio con gli algoritmi basati su fattorizzazione tipo  RSA servono 1024 bit o piu' per
avere livelli decenti di sicurezza.... questo sarebbe drammatico per le dimesnioni della blockchain che gia' e' bella pesa...

Inoltre nei client adesso c'e' implementato tutto il codice per la ECDSA

ad esempio la OP_CHECKSIG fa il check presupponendo implicitamente questo particolare modo crittografia,
ossia non ha un parametro che dice "controlla usando  RSA" oppure "controlla usando il sistema di crittografia x"
quindi ci sarebbe da implementare pesantemente sui client .... ma teoricamente e' possibile.

Io intendevo, in maniera ancora più radicale, si potrebbe evitare proprio (a livello teorico, ovviamente sarebbe scomodissimo) di utilizzare il concetto di firma e quindi i comandi tipo OP_CHECKSIG.  
Alla fin dei conti sarebbe sufficiente scrivere uno script con i comandi consentiti dalla sintassi del linguaggio SCRIPT e farne l'hash. Mi riferisco al concetto di P2SH (pay to script hash).

Pay-to-script-hash addresses

Another important part of the P2SH feature is the ability to encode a script hash as an address, as defined in BIP0013. P2SH addresses are Base58Check encodings of the 20-byte hash of a script, just like bitcoin addresses are Base58Check encodings of the 20-byte hash of a public key. P2SH addresses use the version prefix "5", which results in Base58Check-encoded addresses that start with a "3"

Ad esempio: scrivo uno script del tipo

"fornisci l'hash del blocco 1000 e confrontalo con 0000125...."

oppure

"x + 10 = 30, fornisci x"

poi ne faccio l'hash e ripemd160 e la stringa che ottengo diventa il mio "indirizzo", l'analogo della stringa da 160 bit che ottengo facendo sha256 e poi ripemd160 partendo dalle coordinate di un punto sulla curva ellittica.

Prima della versione 0.9.2 di Bitcoin Core, di fatto si utilizzava questa modalità solo per gli indirizzi multisig, ora è permessa tutta la flessibilità consentita dal linguaggio SCRIPT.

PS: ovviamente vincolare dei fondi a uno script come quello proposto da me sopra non avrebbe senso alcuno, poichè qualora volessi sbloccare quei fondi dovrei trasmettere alla rete una transazione con lo script in chiaro il cui hash256 corrisponde al mio indirizzo + il dato richiesto per lo sblocco, e quindi sarebbe facilissimo sostituire la mia transazione modificando al volo il destinatario prima che essa sia inclusa in un blocco.
Il concetto di firma è proprio quello di poter generare una stringa con la quale dimostrare di avere la chiave privata senza bisogno di renderla pubblica.
Il senso del mio discorso era che il sistema bitcoin fondamentalmente lavora con coppie di stringhe A e B, la stringa/indirizzo B con la funzione di vincolare i btc all'indirizzo/stringa B, la stringa A con la funzione di svincolare i btc dall'indirizzo B. Nel caso delle curve ellittiche, A è la chiave privata, B l'hash della chiave pubblica, ma non è strettamente necessario che sia così.
 

[arulbero]

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

Scritto cosi' non si capisce bene, magari usa (Gx, Gy) tipo:
G =(79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,  483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8).

CIao
P
EDIT: sto punto G l'ho gia' sentito da qualche parte e mi pare sia anche quello un punto di partenza ma non ricordo dove ...

Ho migliorato nel post 1 la presentazione di G, aggiungendo anche il controllo che effettivamente appartenga alla curva secp256k1.

Ho anche aggiunto una precisazione alla risposta alla tua domanda sulla corrispondenza biunivoca tra chiavi private e pubbliche nel post 14.

[picchio]

...
L'insieme degli indirizzi ha circa 2^160 elementi distinti possibili. Per passare dall'insieme E(Fp) all'insieme degli indirizzi ci sono 2 operazioni, un hash256 e un ripmed160 che traducono una stringa di 256 bit in una di 160 bit (la quale viene poi rappresentata in base 58, ma questo è solo un problema appunto di rappresentazione).

Quindi ci sono tantissime chiavi private (con relative chiave pubbliche) che producono lo stesso indirizzo.***

***EDIT2: in realtà c'è anche un altro problema quando traduciamo un punto della curva in un indirizzo. Poichè la funzione hash lavora in modo stupido solo sulla rappresentazione del punto, se scriviamo un punto di E(Fp) nella sua forma compressa (cioè con solo la coordinata x e il "segno" della y, aggiungendo come prefisso 02 se y è pari e 03 se y è dispari), avremo che lo stesso punto può essere tradotto in due indirizzi completamente diversi (ma controllati sempre dalla stessa chiave privata)
...

Interessante, non solo ci sono molti meno indirizzi bitcoin (2^160) ma addirittura ogni chiave privata ne controlla 2... non hanno pensato di imporre la rappresentazione compressa prima di calcolare l'address BTC?
Esagerazione: Non e' che poi alla fine facciamo la fine degli IPv4 che alla fine non bastano?

[picchio]

...
Dubbi residui:
- come critto un messaggio? Ossia poi, di fatto, come funziona?

Per quanto riguarda l'algoritmo ECDSA, sto preparando la spiegazione!

[/quote]
Ti segnalo http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/ che spiega come hanno hackerato la PS3 sfruttando un baco dell'implementazione da parte di sony ... poi corretto.
Se ho capito sony usava sempre uno stesso numero che dovrebbe essere casuale, assomiglia alla chiave privata, e serve per firmare un documento. Con qualche formula inversa sono arrivati alla chiave privata. Cita i passaggi ma non ho ancora potuto analizzarli meglio. Non so se sono giusti.

[arulbero]

...
Dubbi residui:
- come critto un messaggio? Ossia poi, di fatto, come funziona?


Per quanto riguarda l'algoritmo ECDSA, sto preparando la spiegazione!

Ti segnalo http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/ che spiega come hanno hackerato la PS3 sfruttando un baco dell'implementazione da parte di sony ... poi corretto.
Se ho capito sony usava sempre uno stesso numero che dovrebbe essere casuale, assomiglia alla chiave privata, e serve per firmare un documento. Con qualche formula inversa sono arrivati alla chiave privata. Cita i passaggi ma non ho ancora potuto analizzarli meglio. Non so se sono giusti.

Per produrre una firma, oltre alla chiave privata e al messaggio da firmare, è necessario generare ogni volta un numero casuale. Se firmi due messaggi per mezzo della chiave privata utilizzando sempre lo stesso numero "casuale", è banale ricavare dalla firma la chiave privata.
Questo è il motivo per cui è necessario avere un buon generatore di numeri pseudo casuali, non solo per generare buone chiavi private, ma anche per poter firmare in sicurezza senza esporre la chiave privata (che è poi il senso generale della firma).