ECDSA parte 2: firma di un messaggio e di una transazione bitcoin

Continuo il thread iniziato qui:

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

Vediamo come firmare un messaggio qualsiasi con la chiave privata di un indirizzo bitcoin.

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

Firma di un messaggio

Ricordo brevemente l'algoritmo di firma:

Quote from: arulbero on November 04, 2018, 03:06:43 PM

Let (r,s) be the signature, m the message, e = H(m) the message digest, G the curve generator, d the private key, P=d*G the public key.

ECDSA works this way:
1) pick a random nonce k (a private key you use once) in [1,n-1]
2) k -> k*G = Q(xq,yq) then r = xq mod n (r is more or less like the x coordinate of Q)
3) s = k^-1 * (r*d + e) mod n

----------------------------------------------------------------------------------------------------------------
Premessa tecnica:
1) utilizzo per iniziare python 2 in modalità interattiva, poi passeremo allo script
quindi
>>> prompt python
~$ prompt shell

2) python è in grado di gestire operazioni tra numeri molto grandi senza problemi, anche modulo n
per quanto riguarda invece il calcolo tra punti della curva è necessario avvalersi di una libreria, in questa prima parte ci avvaliamo di una libreria "mini_ecdsa" (non scritta da me) ad uso didattico, in seguito ne scriveremo una da zero
per scaricarla : git clone https://github.com/qubd/mini_ecdsa.git
per utilizzarla : quando si è entrati in modalità interattiva, execfile('mini_ecdsa.py') (con il percorso relativo corretto)

3) la parte più rognosa per me è stata la manipolazione delle stringhe e le varie codifiche, per usare correttamente sha256 e le varie conversioni tra ascii e altri formati binari bisogna importare 2 altre librerie, "hashlib" e "binascii"
-------------------------------------------------------------------------------------------------------------------
Dati iniziali:

MESSAGGIO DA FIRMARE

Code:

>>>import hashlib
>>>import binascii
>>>
>>>msg = 'Ciao oggi 31 dicembre sto provando a firmare un messaggio'
>>>
>>>msg_formattato = "\x18Bitcoin Signed Message:\n" + chr( len(msg) ) + msg
>>>
>>>e = hashlib.sha256(hashlib.sha256(msg_formattato).digest()).digest()
>>>print binascii.b2a_hex(e)
5ae332695b7d534336b1245b720a771cb4eeaefd3d53583aad108327de30a38c

PARAMETRI DELLA CURVA SECP256K1

Code:

>>>execfile('mini_ecdsa.py')
>>>
>>>p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo
>>>n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva

>>>C = CurveOverFp(0, 0, 7, p)
y^2 = x^3 + 7 over F_115792089237316195423570985008687907853269984665640564039457584007908834671663

>>>G = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) #generatore del gruppo dei punti della curva

GENERAZIONE CHIAVE PRIVATA - CHIAVE PUBBLICA - INDIRIZZO

Code:

~$ hexdump -n 32 -e '8/4 "%08X" 1 "\n"' /dev/urandom
D02E0EB2EF0CE08168FE746B58A91D485BE97E71D2E2061F7807248A739F68D2

>>>d = 0xd02e0eb2ef0ce08168fe746b58a91d485be97e71d2e2061f7807248a739f68d2 (la chiave privata generata mediante urandom)

>>>P = C.mult(G,d) # P = d*G
>>> print P
(56648515016038393520262952982723707918005872252984079682254662011250519474519,34439720842813318822435587706376241065257505597204067160331538221043835853710)

>>>xp = 56648515016038393520262952982723707918005872252984079682254662011250519474519
>>>yp = 34439720842813318822435587706376241065257505597204067160331538221043835853710

>>> print hex(xp)
0x7d3dec5b3f7bda2eacaa48dfadee6922c741771463b60ce5586371842afe8157L

>>> print hex(yp)
0x4c2430f3c7fd57de7ede4e2723558e804f59c4930ac9023afa0c816fe5c5db8eL

>>>address_compressed = '1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC'

GENERAZIONE CHIAVE PRIVATA USA E GETTA - CHIAVE PUBBLICA

Code:

~$ hexdump -n 32 -e '8/4 "%08X" 1 "\n"' /dev/urandom
890E92FAEF7387295984ABE9D583EB269BBA942077F29B227C825788E13FE9BE

>>>k = 0x890e92faef7387295984abe9d583eb269bba942077f29b227c825788e13fe9be (chiave privata usa e getta)

>>> Q = C.mult(G,k) # Q = k*G
>>> print Q
(84999791795797315190007927603153314605480098556488635859498606522553519770078,13375324783711542103436223255037217772249325984154197258846945690589726740778)

>>> xq = 84999791795797315190007927603153314605480098556488635859498606522553519770078

>>> print hex(xq)
0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de

Riassumendo i dati fondamentali:

Code:

e = 0x5ae332695b7d534336b1245b720a771cb4eeaefd3d53583aad108327de30a38c (doppio hash del messaggio)

d = 0xd02e0eb2ef0ce08168fe746b58a91d485be97e71d2e2061f7807248a739f68d2 (chiave privata)
P = (0x7d3dec5b3f7bda2eacaa48dfadee6922c741771463b60ce5586371842afe8157, 0x4c2430f3c7fd57de7ede4e2723558e804f59c4930ac9023afa0c816fe5c5db8e)

k = 0x890e92faef7387295984abe9d583eb269bba942077f29b227c825788e13fe9be (chiave privata usa e getta)
Q = (0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de, 0x1d922a618d45e1ba97a4cc0bb53598b73ad408c9cb728d302b2987dab2cf912a)

La firma di questo messaggio consiste in una coppia di valori 'r' e 's', entrambi devono essere compresi tra 1 e n-1.

r è uguale a xq mod n, e poichè in questo caso xq < n, i due valori coincidono:

Code:

r = 0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de

s è uguale a k^-1 * (r*d + e) mod n

Code:

>>>k_inv = pow(k, n-2, n) #qui si sfrutta il teorema di Fermat per il quale se n è primo allora a^n = a --> a^(n-1) = 1 --> a^(n-2) = 1/a mod n
>>>
>>>s = k_inv * (r * d + e) % n
>>>print hex(s)
0x5c40b6ed461d4c1856595432f126050fde4eefd7ab6135bbc2edaf536abe237dL

piccolo teorema di Fermat

Abbiamo ottenuto quindi la firma:

r = 0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de
s = 0x5c40b6ed461d4c1856595432f126050fde4eefd7ab6135bbc2edaf536abe237d

Questi valori vanno codificati in base64:

Code:

>>>r_string = hex(r)[2:-1] #eliminiamo 0x iniziale e L (long) finale
>>>s_string = hex(r)[2:-1]
>>>
>>>print r_string #di per sè bisognerebbe anche controllare che il numero di caratteri sia sempre 64
bbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de
>>>
>>> s_string = hex(s)[2:-1]
>>> print s_string
5c40b6ed461d4c1856595432f126050fde4eefd7ab6135bbc2edaf536abe237d
>>>
>>>i=0
#questo parametro i è 0 se xq < n e yq è pari, è 1 se xq < n e e yq è dispari, è 2 se xq >= n e yq è pari, è 3 se xq >= n e yq è dispari
#l'unico carattere da premettere a r e s nella firma finale è chr(27+i) se si sta usando un address non compresso,
#chr(31+i) se invece si sta usando un address compresso
>>>sig = binascii.b2a_base64( chr(31+i) + binascii.a2b_hex(r_string) + binascii.a2b_hex(s_string) )
>>> print sig
H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2vU2q+I30=

Verifica

Ottenuta la firma codificata in base 64

H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2 vU2q+I30=

se vogliamo verificare online la correttezza di questo messaggio possiamo farlo così:

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
Ciao oggi 31 dicembre sto provando a firmare un messaggio
-----BEGIN SIGNATURE-----
1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC
H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2vU2q+I30=
-----END BITCOIN SIGNED MESSAGE-----

Effettivamente risulta verificato!

Se non siamo soddisfatti da questo tipo di verifica esterna e ne vogliamo realizzare una interna possiamo procedere così:

innanzitutto ricordiamo la teoria:

poichè s = k^-1 * (r*d + e) mod n si ha che

k = s^-1*r*d + s^-1*e
k*G = s^-1*r*d*G + s^-1*e*G

Q = s^-1*r*P + s^-1*e*G (poichè k*G = Q e d*G = P, P è la chiave pubblica)

di solito questa è la verifica che si fa quando si invia la chiave pubblica P.

Quando si invia invece l'address come nel nostro caso si ricava invece autonomamente la chiave pubblica dalla firma e dal messaggio, supponendo valida la relazione precedente si ha che:

s*Q = r*P + e*G

da cui si ottiene che P = r^-1 * (s*Q - e*G)

quindi una volta ottenuto la chiave pubblica P possiamo controllare che l'address generato sia effettivamente quello proposto (ovvero la chiave pubblica sia quella giusta)

Code:

>>> A = C.mult(Q,s) #s*Q
>>> B = C.mult(G,n-e) #-e*G
>>> R = C.add(A,B) #s*Q - e*G
>>> P = C.mult(R,pow(r,n-2,n)) #r^-1 * (s*Q - e*G)
>>> print P
(56648515016038393520262952982723707918005872252984079682254662011250519474519,34439720842813318822435587706376241065257505597204067160331538221043835853710)

effettivamente abbiamo ritrovato la chiave pubblica di partenza, se generiamo l'address compresso da questa chiave pubblica si ottiene il nostro indirizzo di partenza.

SCRIPT PYTHON
(funziona solo con python2 e mancano diversi controlli sulla lunghezza delle stringhe ma più avanti
c'è una versione più completa che funziona anche con python3)

Riassumendo l'intero discorso, condensiamo tutto in uno script sign_msg.py :

Code:

#!/usr/bin/env python

execfile('mini_ecdsa.py') #https://github.com/qubd/mini_ecdsa
import hashlib, binascii
import subprocess #se si vuole generare k casualmente con /dev/urandom

#DATI DA IMPOSTARE MANUALMENTE
msg = 'Ciao oggi 31 dicembre sto provando a firmare un messaggio' #inserire qui il messaggio scelto

d = 0xd02e0eb2ef0ce08168fe746b58a91d485be97e71d2e2061f7807248a739f68d2 #inserire qui la propria chiave privata

address = '1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC'
compressed = 1 #se e' compresso segnare 1, altrimenti 0
########################################################################################################################

#DATI CURVA SECP256K1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva

print
C = CurveOverFp(0, 0, 7, p)

G = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) #generatore del gruppo dei punti della curva

#CHIAVE PUBBLICA
P = C.mult(G,d) # P = d*G (P serve solo per la verifica, non per la firma in se')

#CHIAVE PRIVATA USA E GETTA E RELATIVA CHIAVE PUBBLICA (qui si setta la prima parte della firma, r)
#k deve essere diverso da 0 e minore di n, qui diamo per scontato che sia cosi'
#k = 0x890e92faef7387295984abe9d583eb269bba942077f29b227c825788e13fe9be
k = subprocess.Popen(['hexdump', '-n', '32', '-e','8/4 "%08X"', '/dev/urandom'], stdout=subprocess.PIPE).communicate()[0]
k = int(k,16) #trasforma una stringa in un numero, se si vuole si puo' inserire qui a mano un altro valore

Q = C.mult(G,k) # Q = k*G
if (Q.x < n):
r = Q.x
i = 0;
else:
r = Q.x - n;
i = 2;
if (Q.y%2 == 1):
i = i+1;
if (compressed == 0):
i = i + 27
else:
i = i + 31

#FORMATTAZIONE MESSAGGIO
msg_formattato = "\x18Bitcoin Signed Message:\n" + chr( len(msg) ) + msg
e = hashlib.sha256(hashlib.sha256(msg_formattato).digest()).digest()
e = int(binascii.b2a_hex(e),16) #trasforma una stringa di byte in un numero

#FIRMA DEL MESSAGGIO
#(firmare vuol dire trovare a partire da r casuale un valore s che dimostri di possedere la chiave privata d;
#il valore s dipende ovviamente sia dalla chiave privata d che dal messaggio e)
k_inv = pow(k, n-2, n)
s = k_inv * (r * d + e) % n

#CODIFICA DELLA FIRMA IN BASE 64
#per fare le cose seriamente qui bisognerebbe controllare che sia r che s siano formati da 64 cifre esadecimali,
#in caso contrario bisognerebbe aggiungere degli zeri all'inizio del numero;
#qui questo controllo NON viene fatto
sig = binascii.b2a_base64( chr(i) + binascii.a2b_hex(hex(r)[2:-1]) + binascii.a2b_hex(hex(s)[2:-1]) )
sig = sig[:-1]

print
print '-----BEGIN BITCOIN SIGNED MESSAGE-----'
print msg
print '-----BEGIN SIGNATURE-----'
print address
print sig
print '-----END BITCOIN SIGNED MESSAGE-----'

#VERIFICA ONLINE
print
print 'Verifica qui --> '
p1 = subprocess.Popen(["echo", msg], stdout=subprocess.PIPE)
msg2 = subprocess.Popen(["sed", "s/ /%20/g"], stdin=p1.stdout, stdout=subprocess.PIPE).communicate()[0]
p1.stdout.close()
print 'http://brainwalletx.github.io/#verify?vrAddr=' + address + '&vrMsg=' + msg2[:-1] + '&vrSig=' + sig
print

Proviamolo:

Code:

~/src2/mini_ecdsa$ python sign_msg.py
y^2 = x^3 + 7 over F_115792089237316195423570985008687907853269984665640564039457584007908834671663

-----BEGIN BITCOIN SIGNED MESSAGE-----
Ciao oggi 31 dicembre sto provando a firmare un messaggio
-----BEGIN SIGNATURE-----
1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC
H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2vU2q+I30=
-----END BITCOIN SIGNED MESSAGE-----

Verifica qui -->
http://brainwalletx.github.io/#verify?vrAddr=1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC&vrMsg=Ciao%20oggi%2031%20dicembre%20sto%20provando%20a%20firmare%20un%20messaggio&vrSig=H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2vU2q+I30=