curve ellittiche e algoritmo ECDSA

[arulbero]

Ho inserito un indice (all'inizio del primo post) per mettere un po' di ordine in questo thread.

Ho aggiunto anche la parte relativa alla firma e alla verifica, più avanti vedo di inserire magari anche qualche esempio specifico.

[1714932766]

1714932766

[1714932766]

1714932766

[1714932766]

1714932766

[arulbero]

Dopo quasi 3 anni mi sono deciso a continuare questo thread, aggiungendo le parti relative alla firma di un messaggio (già fatta) e la firma di una transazione bitcoin (ancora da fare).

Si tratta di una sezione più operativa, con esempi di codice in python funzionanti (tranne casi particolari che non affronterò).

Ricordo comunque che si tratta di materiale a scopo didattico, solo per imparare, non usate questi software per cose serie.

Questo il link al nuovo thread (continuazione di questo):

https://bitcointalk.org/index.php?topic=5091462

[jack0m]

Ti ringrazio per la guida, anche se in ritardo... purtroppo non so quando riuscirò mai a trovare in tempo per studiarmi per bene l'argomento.

Una cosa però avevo provato a studiarla ma non l'ho mai capita: come fai a dimostrare che l'insieme dei numeri interi non negativi e minori di p (numero primo) sia un campo finito? Ovvero, come dimostri che per ogni elemento di quell'insieme esiste un inverso, anch'esso nello stesso insieme?

[arulbero]

Una cosa però avevo provato a studiarla ma non l'ho mai capita: come fai a dimostrare che l'insieme dei numeri interi non negativi e minori di p (numero primo) sia un campo? Ovvero, come dimostri che per ogni elemento di quell'insieme esiste un inverso, anch'esso nello stesso insieme?

Si può dimostrare che Zn è un campo finito se e solo se n è primo.

Al momento mi ricordo solo come si fa a dimostrare che se n non è primo, allora Zn non è un campo.

Premessa:
in un campo qualsiasi deve valere la legge di annullamento del prodotto, ovvero a x b = 0 implica necessariamente che almeno uno tra a e b sia uguale a 0.

Infatti se per assurdo a x b = 0 con a,b entrambi diversi da 0, posso moltiplicare entrambi i membri per b^-1 (ogni elemento diverso da 0 ha il suo inverso in un campo):

a x b x b^-1 = 0 x b^-1

a x 1 = 0

a = 0 che va contro l'ipotesi che a sia diverso da 0.
 


Tornando a Zn, se n non è primo, allora n = a x b, con a,b diversi da 0.

Ma Zn = {0, 1, 2, ..., n -1} è definito come l'insieme delle classi dei resti modulo n ovvero n = 0 in Zn.

Quindi se n non è primo, è possibile trovare due numeri diversi da 0 il cui prodotto fa 0, ma in un campo la legge di annullamento del prodotto deve valere sempre, quindi si conclude che Zn non è un campo.


EDIT: aggiungo inoltre che ogni campo finito Fq ha necessariamente p^n elementi, dove p è un numero primo. Ogni campo finito contiene un sottocampo finito di p elementi isomorfo a Zp, e tutti i campi finiti di p elementi sono isomorfi a Zp (link)

[jack0m]

Una cosa però avevo provato a studiarla ma non l'ho mai capita: come fai a dimostrare che l'insieme dei numeri interi non negativi e minori di p (numero primo) sia un campo? Ovvero, come dimostri che per ogni elemento di quell'insieme esiste un inverso, anch'esso nello stesso insieme?

Si può dimostrare che Zn è un campo finito se e solo se n è primo.

Al momento mi ricordo solo come si fa a dimostrare che se n non è primo, allora Zn non è un campo.

Premessa:
in un campo qualsiasi deve valere la legge di annullamento del prodotto, ovvero a x b = 0 implica necessariamente che almeno uno tra a e b sia uguale a 0.

Infatti se per assurdo a x b = 0 con a,b entrambi diversi da 0, posso moltiplicare entrambi i membri per b^-1 (ogni elemento diverso da 0 ha il suo inverso in un campo):

a x b x b^-1 = 0 x b^-1

ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?
Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

[arulbero]

ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?

Infatti ho solo dimostrato che Zn non è un campo quando n non è primo.

Dimostrare che un insieme è un campo è ovviamente più laborioso (dimostrazione completa , da pag. 35 a pag. 46!), devi infatti dimostrare che le operazioni di somma e moltiplicazioni sono ben definite, godono delle proprietà associative e commutative e che tutti gli elementi hanno l'opposto e il reciproco (in sostanza che sono definite implicitamente anche le operazioni di sottrazione e divisione per un numero diverso da zero).

Come hai ben osservato, la parte più interessante è l'ultima, ovvero dimostrare che ogni elemento (a parte lo 0) di Zp ha sempre un inverso.


Premessa:

Identità di Bezout: dati a e b numeri interi relativi diversi da 0 e detto d = MCD(a,b), allora esistono x,y interi tali che

a*x + b*y = d

x e y non sono unici, per trovarne un paio basta applicare l'algoritmo di Euclide per la determinazione del MCD (ce ne sono in realtà  infinite coppie).

Supponiamo vera l'identità di Bezout (vedi pag. 45 del link), vediamo che x e y non sono unici.

Notiamo infatti che a*b + b*(-a) = 0, quindi k * [a*b + b*(-a)] = 0 per ogni k intero

da ciò segue che per ogni k intero, a*(b*k) + b(-a*k) = 0 quindi

0 + a*x + b*y = d ->  a*(b*k) + b(-a*k) + a*x + b*y = d

da cui si ricava che x' = b*k + x    e   y' = -a*k + y possono assumere infiniti valori.



Teorema: se p é primo allora ogni elemento diverso da 0 di Zp ha un inverso in Zp

Sia a un numero diverso da 0 di Zp, con p primo.

Poichè p è primo, MCD(a,p)=1

Per l'identità di Bezout esistono x e y interi tali che:

a*x + p*y = 1

ovvero a*x = 1 -y*p  ovvero a*x  = 1 mod p (a*x = 1 mod p significa che esiste q intero tale che a*x= q*p + 1)

quindi x è l'inverso di a mod p
CVD

Ti consiglio caldamente la lettura delle pagine dalla 42 alla 46, spiegano bene la questione a partire dal concetto di divisore, di MCD, identità di Bezout e teorema su Zp.

Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

Penso che dalla dimostrazione che ti ho dato ora questo punto sia diventato chiaro.

Ultima osservazione, bisognerebbe stare attenti a come sono definiti gli elementi degli insiemi in algebra, io ho utilizzato una notazione 'leggera' per cui Zp = { 0, 1, 2, ...., n-1} mentre in realtà bisognerebbe scrivere Zp = { [ 0], [1], [2], ...., [n-1]} perchè gli elementi di Zp sono le classi di congruenza modulo n, penso che anche l'insieme Z'n di cui parli tu sia la stessa cosa, altrimenti non è chiaro neanche come è definita l'addizione e la moltiplicazione tra elementi.

Detta in altri termini, Zp = { 0, 1, 2, ...., n-1} NON è un campo con le usuali operazioni di addizioni e moltiplicazione!
Invece Zp = { [ 0], [1], [2], ...., [n-1]} lo è, una volta definite le operazioni + e * sui suoi particolari elementi.

Ad esempio Z'6 = {[ 0], [1], [5]} ( Z'6 ha 3 elementi, è isomorfo quindi a Z3 = {[ 0], [1], [2]} ) (per fare i calcoli basta sostituire [5] con [2])

dove

[ 0]  * [ 0] = [ 0]                [ 0]  +  [ 0] = [ 0]
[ 0]  * [ 1] = [ 0]                [ 0]  +  [ 1] = [ 1]
[ 0]  * [ 5] = [ 0]                [ 0]  +  [ 5] = [ 5]
[ 1]  * [ 0] = [ 0]                [ 1]  +  [ 0] = [ 1]
[ 1]  * [ 1] = [ 1]                [ 1]  +  [ 1] = [ 5]
[ 1]  * [ 5] = [ 5]                [ 1]  +  [ 5] = [ 0]
[ 5]  * [ 0] = [ 0]                [ 5]  +  [ 0] = [ 5]
[ 5]  * [ 1] = [ 5]                [ 5]  +  [ 1] = [ 0]
[ 5]  * [ 5] = [ 1]                [ 5]  +  [ 5] = [ 1]

[jack0m]

ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?

Infatti ho solo dimostrato che Zn non è un campo quando n non è primo.

Dimostrare che un insieme è un campo è ovviamente più laborioso (dimostrazione completa , da pag. 35 a pag. 46!), devi infatti dimostrare che le operazioni di somma e moltiplicazioni sono ben definite, godono delle proprietà associative e commutative e che tutti gli elementi hanno l'opposto e il reciproco.

Come hai ben osservato, la parte più interessante è l'ultima, ovvero dimostrare che ogni elemento (a parte lo 0) di Zp ha sempre un inverso.


Premessa:

Identità di Bezout: dati a e b numeri interi relativi diversi da 0 e detto d = MCD(a,b), allora esistono x,y interi tali che

a*x + b*y = d

x e y non sono unici, per trovarne un paio basta applicare l'algoritmo di Euclide per la determinazione del MCD (ce ne sono in realtà  infinite coppie).

Supponiamo vera l'identità di Bezout (vedi pag. 45 del link), vediamo che x e y non sono unici.

Notiamo infatti che a*b + b*(-a) = 0, quindi k * [a*b + b*(-a)] = 0 per ogni k intero

da ciò segue che per ogni k intero, a*(b*k) + b(-a*k) = 0 quindi x = b*k e y = -a*k  possono assumere infiniti valori.



Teorema: se p é primo allora ogni elemento diverso da 0 di Zp ha un inverso in Zp

Sia a un numero diverso da 0 di Zp, con p primo.

Poichè p è primo, MCD(a,p)=1

Per l'identità di Bezout esistono x e y interi tali che:

a*x + p*y = 1

ovvero a*x = 1 -y*p  ovvero a*x  = 1 mod p (a*x = 1 mod p significa che esiste q tale che a*x= q*p + 1)

quindi x è l'inverso di a mod p
CVD

Ti consiglio caldamente la lettura delle pagine dalla 42 alla 46, spiegano bene la questione a partire dal concetto di divisore, di MCD, identità di Bezout e teorema su Zp.

Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

Penso che dalla dimostrazione che ti ho dato ora questo punto sia diventato chiaro.

Ultima osservazione, bisognerebbe stare attenti a come sono definiti gli elementi degli insiemi in algebra, io ho utilizzato una notazione 'leggera' per cui Zp = { 0, 1, 2, ...., n-1} mentre in realtà bisognerebbe scrivere Zp = { [ 0], [1], [2], ...., [n-1]} perchè gli elementi di Zp sono le classi di congruenza modulo n, penso che anche l'insieme Z'n di cui parli tu sia la stessa cosa, altrimenti non è chiaro neanche come è definita l'addizione e la moltiplicazione tra elementi.

Detta in altri termini, Zp = { 0, 1, 2, ...., n-1} NON è un campo con le usuali operazioni di addizioni e moltiplicazione!
Invece Zp = { [ 0], [1], [2], ...., [n-1]} lo è, una volta definite le operazioni + e * sui suoi particolari elementi.

Ad esempio Z'6 = {[ 0], [1], [5]} ( Z'6 ha 3 elementi, è isomorfo quindi a Z3 = {[ 0], [1], [2]} )

dove
[ 0]  * [ 0] = [ 0]
[ 0]  * [1] = [ 0]
[ 0]  * [5] = [ 0]
[ 1]  * [ 0] = [ 0]
[ 1]  * [1] = [ 1]
[ 1]  * [5] = [ 5]
[ 5]  * [ 0] = [ 0]
[ 5]  * [1] = [ 5]
[ 5]  * [5] = [ 1]

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?
EDIT: vedo nel link Geometria e Algebra, ma non so se l'hai segnalato solo come riferimento

[arulbero]

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?

Direi un classico corso di Algebra. Certo era solo un riferimento, visto che mi hai chiesto dei campi finiti ho fatto una rapida ricerca con google. 

Io insegno matematica al liceo, non all'università.

[jack0m]

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?

Direi un classico corso di Algebra. Certo era solo un riferimento, visto che mi hai chiesto dei campi finiti ho fatto una rapida ricerca con google. 

Io insegno matematica al liceo, non all'università.

mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.

[arulbero]

mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.

Non è mai troppo tardi per mettersi a studiare, l'importante è che ti interessi veramente, ormai di materiale in rete ce n'è in abbondanza.

[jack0m]

mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.

Non è mai troppo tardi per mettersi a studiare, l'importante è che ti interessi veramente, ormai di materiale in rete ce n'è in abbondanza.

già, di materiale senz'altro, ma di tempo no purtroppo

[il_minatore]

Sono un po OT, ma volevo sapere: partendo da un indirizzo, posso sapere se è stato generato a partire da una pubkey compressa o meno? Grazie

[arulbero]

Sono un po OT, ma volevo sapere: partendo da un indirizzo, posso sapere se è stato generato a partire da una pubkey compressa o meno? Grazie

No, non si può sapere. Nel momento in cui passi la stringa '04' + 'X' + 'Y' alla funzione ripemd160(sha256()) il risultato è solo una stringa di 160 bit, lo stesso otterresti se mettessi in input '02' + 'X'.

Di più, la stringa di 160 bit (l'address è sostanzialmente un numero di 160 bit presentato all'essere umano in base 58) potrebbe essere l'impronta di qualsiasi cosa. Ad esempio, se consideri la frase 'Ciao come stai' e la dai in pasto così:  ripemd160(sha256('Ciao come stai')) ottieni un numero di 160 bit, se ora passi la sua codifica in base 58 a qualcuno perchè lui ti paghi su quell'indirizzo, la transazione avverrà con destinazione quell'indirizzo, poichè non è possibile dall'indirizzo stesso ricavare nulla su come sia stato effettivamente generato (se non che la sua codifica in base 58 è stata ottenuta aggiungendo il byte 00 all'inizio della stringa di 160 bit).
Quindi in tal caso nessuno potrebbe smuovere più quei fondi.

[il_minatore]

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      

Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie

[picchio]

...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie

Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

[il_minatore]

Per molti sarà banale, per uno come me che non è del mestiere ho trovato questo materiale molto utile. Vedere il codice a volte aiuta a capire la teoria   :

https://rosettacode.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

https://rosettacode.org/wiki/RSA_code

https://rosettacode.org/wiki/Bitcoin/public_point_to_address

[il_minatore]

...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie

Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)

[picchio]

...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie

Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)

A memoria, certo di sbagliarmi, prego correggermi.
prv=privete key
pub=public key
G= generatore

pub=G+G+G ...+G=prv*G (o G*prv se commutativo, non ricordo).

[arulbero]

...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie

Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)

L'ho spiegato qui con un codice python applicato a una chiave reale:

https://bitcointalk.org/index.php?topic=5091462.msg48983013#msg48983013

nella libreria micro_ecdsa la funzione che effettua il passaggio dalla chiave privata alla chiave pubblica è la funzione mul che moltiplica il generatore G per una chiave privata d (uno scalare) e restituisce la chiave pubblica corrispondente d*G. Quindi per trovare la chiave pubblica relativa a 'd' basta chiamare la funzione mul(d,Gx, Gy), dove Gx e Gy sono le coordinate del punto G scelto dalla SEC. Ti consiglio di scaricarti lo script pyhton e provare a generare delle chiavi pubbliche a partire dalle chiavi private. Lascia stare gli indirizzi, quelli vengono dopo.

La funzione 'mul' invece di fare banalmente d*G = G+G+G+.... un numero d di volte (essendo d dell'ordine di 2^256 ci impiegherebbe un'eternità) crea tutte le potenze di 2 tipo 2*G, 4*G, 8*G, 16*G, 32*G, ... , 2^255*G e poi somma tra loro quelle che servono. Ho anche fatto un esempio concreto con una chiave piccola tipo 25 = 11001 in base 2. In quel caso basta generare 1G, 2G, 4G, 8G, 16G e poi sommare rispettivamente: 16G + 8G +1G (che corrispondono ai 3 'uno' della sequenza 11001) per ottenere 25G (che è la chiave pubblica relativa alla chiave privata 25).  Nella libreria ci sono anche la formula per l'addizione di due punti e la formula per il raddoppio di un punto che sono i mattoncini base per la funzione mul.

EDIT: altri link utili:

https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

[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      

Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.

mod 11 viene applicato al risultato della radice quadrata (in generale viene applicato al risultato di qualsiasi operazione quando questo risultato supera 11).

Prendiamo per esempio la riga del 2:

x = 2 --> x^3 = 8 --> x^3 + 7 = 8 + 7 = 15 = 4 mod 11 --> sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11) lascia perdere i valori negativi (semplicemente 9 = -2 mod 11, li ho inseriti solo per far vedere che le radici quadrate sono sempre opposte, anche in questi insiemi strani; anche con i numeri normali se ti dico x^2 = 4, chi è x? Tu rispondi: 2 o -2)