Title: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on December 31, 2018, 11:32:47 AM
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 secp256k1Firma di un messaggioRicordo brevemente l'algoritmo di firma: 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 >>>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 >>>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 ~$ 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 ~$ 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: 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: r = 0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de
s è uguale a k^-1 * (r*d + e) mod n >>>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 (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) Abbiamo ottenuto quindi la firma: r = 0xbbec2d615c78aa43815c618648897518ca36904e2bcd1b7950da9819c53709de s = 0x5c40b6ed461d4c1856595432f126050fde4eefd7ab6135bbc2edaf536abe237d
Questi valori vanno codificati in base64: >>>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=
VerificaOttenuta la firma codificata in base 64 H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2 vU2q+I30=se vogliamo verificare online la correttezza di questo messaggio possiamo farlo così: -----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 (http://brainwalletx.github.io/#verify?vrAddr=1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC&vrMsg=Ciao%20oggi%2031%20dicembre%20sto%20provando%20a%20firmare%20un%20messaggio&vrSig=H7vsLWFceKpDgVxhhkiJdRjKNpBOK80beVDamBnFNwneXEC27UYdTBhWWVQy8SYFD95O79erYTW7wu2vU2q%2BI30%3D)! 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) >>> 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 : #!/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: ~/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=
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on December 31, 2018, 11:33:03 AM
A questo punto uno potrebbe dire ma perchè usare la libreria mini_ecdsa già fatta invece di costruirne una da zero? D'altra parte abbiamo fatto tanta teoria, cerchiamo quindi di costruire da zero una libreria molto succinta, che fa l'essenziale (non nel modo più veloce possibile), quindi la chiameremo micro_ecdsa. Cerchiamo di renderla inoltre compatibile sia con python2 che con python3 e andiamo infine a riadattare anche lo script signmsg.pyLo scopo è imparare in profondità i meccanismi di funzionamento e costruire una libreria più snella possibile da studiare (circa 40 200 righe con l'aggiunta di cose extra rispetto all'algoritmo ECDSA) La libreria micro_ecdsaPer costruire una libreria da importare poi in altri script python è sufficiente creare un file con suffisso ".py" contenente le definizioni delle funzioni che ci servono. Nel nostro caso costruiamo un file micro_ecdsa.py da tenere nella stessa directory degli script che dovranno utilizzare questa libreria. Iniziamo: PARAMETRI DELLA CURVA SECP256K1 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva
ADDIZIONE TRA 2 PUNTI DELLA CURVA A + B -> C (formula (https://bitcointalk.org/index.php?topic=1339031.msg13658595#msg13658595)) def add(ax, ay, bx, by):
bxax_inv = pow(bx-ax, p-2, p) # 1/(x2-x1) m = ( (by-ay) * bxax_inv ) % p # m = (y2-y1)/(x2-x1) cx = (m * m - ax - bx) % p # x3 = m^2 - x1 -x2 cy = (m * (ax - cx) - ay) % p # y3 = m*(x1 - x3) - y1 return cx, cy
RADDOPPIO DI UN PUNTO DELLA CURVA A -> 2*A (formula (https://bitcointalk.org/index.php?topic=1339031.msg13658595#msg13658595)) def double(ax, ay):
due_inv = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffff7ffffe18 #1/2 modulo p ay_inv = pow (ay, p-2, p) # 1/y m = ((3 * due_inv) % p ) * (ax * ax * ay_inv % p) % p # m = 3x^2/2*y aax = (m * m - 2* ax) % p # x_2a = m^2 - 2x aay = (m * (ax - aax) - ay) % p # y_2a = m*(x - x_2a) -y return aax, aay
MOLTIPLICAZIONE DI UNO SCALARE QUALSIASI PER UN PUNTO DELLA CURVA d , A --> d*A l'idea: 25 * A significa A+A+A+....A venticinque volte (sarebbe molto oneroso fare ripetutamente tutte le addizioni necessarie, soprattutto considerando che lo scalare d, la chiave privata, di solito è dell'ordine di 2^256, 2^256 addizioni sono un'infinità !!!) Allora si decompone semplicemente 25 nella sua rappresentazione binaria 11001 (1*2^4 + 1*2^3 + 1*2^0): questo vuol dire che devo fare solo 3 -1 addizioni (quelle relative agli 1 presenti - 1) e 4 raddoppi (in generale dovrò fare al massimo 255 raddoppi e 255 addizioni tra punti della curva, in media 255 raddoppi e 127 addizioni) def mul(d,ax,ay):
dax, day = 0, 0 if (d%2 == 1): dax, day = ax, ay #solo se d e' dispari q=d//2 while q>0: ax, ay = double(ax,ay) if (q%2 > dax): #puo' succedere solo se dax=0 e q%2=1 cioe' la prima volta dax, day = ax, ay #solo se d e' pari elif (q%2): dax, day = add(ax, ay, dax, day) q=q//2 return dax, day
Sarebbe comodo avere anche un paio di funzioni per : 1) generare da una chiave privata il suo address 2) poter importare una chiave privata in formato WIF (di solito è quello il formato nel quale si ottiene dai wallet, una stringa anzichè un numero) Quindi, pur non facendo parte a rigor di logica della curva ellittica e dell'algoritmo ECDSA, le aggiungiamo: DALLA CHIAVE PRIVATA ALL'ADDRESS def priv_to_addr(d,compressed): #prende in input una chiave privata in formato esadecimale, #restituisce in output una stringa contenente l'address corrispondente #vedi https://gobittest.appspot.com/Address #vedi https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc#bitcoin-addresses
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
Px, Py = mul(d,Gx,Gy) # P = d*G
if (compressed == 1): if (Py % 2) == 0: P_string = '02' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari else: P_string = '03' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari else: #uncompressed P_string = '04' + hex(Px)[2:].rstrip('L').rjust(64,'0') + hex(Py)[2:].rstrip('L').rjust(64,'0') h = sha256(a2b_hex(P_string)).digest() #sha256
h1 = hashlib.new('ripemd160') #ripmed160 h1.update(h)
a = b'\x00' + h1.digest() #aggiunge byte 00 all'inizio h2 = sha256(sha256(a).digest()).digest() #doppio sha256 per controllo
addr = a + h2[:4]
address = b58encode(addr) #ultimo passaggio: codifica in base 58
return address
CHIAVE PRIVATA: DAL FORMATO WIF (STRINGA) A NUMERO def wif_to_hex(k,compressed): #prende in input una chiave privata in formato WIF (string), #restituisce in output la chiave privata come numero (long) #https://gobittest.appspot.com/PrivateKey
a = b58decode(k, compressed + 37) # decodifica --> stringa di byte version = a[0] checksum = a[-4:] b = a[:-4] # Version plus hash160 is what is checksummed
if (compressed == 1): key = b[1:-compressed] # elimina primo byte e l'ultimo (compressed) else: key = b[1:] # elimina solo primo byte (uncompressed)
h = sha256(sha256(b).digest()).digest() if h[0:4] == checksum : c = b2a_hex(key) # da stringa di byte a stringa di caratteri esadecimali d = int(c, 16) # trasforma una stringa in un numero
return d
else: print ("Errore: l'indirizzo non e' valido!") exit()
In più ci saranno altre due funzioni ausiliarie che servono per la codifica/decodifica in base58 (dal momento che sia gli address bitcoin che le chiavi private in formato wif usano quella codifica; queste 2 funzioni relative alla base58 le ho prese da qui https://bitcointalk.org/index.php?topic=1026.msg12557#msg12557 e https://github.com/stequald/bitcoin-sign-message/blob/master/signmessage.py#L125 , la funzione di decodifica ho dovuto integrarla rispetto all'originale per renderla compatibile con python3) Mettiamo quindi tutto insieme: MICRO_ECDSA.PY import hashlib #se non c'e'ripemd160 nel tuo sistema --> https://stackoverflow.com/questions/42601709/hashlib-cant-find-ripemd160 from hashlib import sha256 from binascii import a2b_hex, b2a_hex import struct #per la conversione di un intero in byte
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva
def inv(a,k): #a --> a^-1 mod k u, v = a%k, k x1, x2 = 1, 0 while u != 1 : #q = v//u #r = v-q*u q, r = divmod(v,u) x = x2-q*x1 v = u u = r x2 = x1 x1 = x return x1%k
def add(ax, ay, bx, by): #A + B -> C
bxax_inv = inv(bx-ax, p) #1/(x2-x1) m = ( (by-ay) * bxax_inv ) % p #m = (y2-y1)/(x2-x1) cx = ( m*m - ax - bx) % p cy = (m * (ax - cx) - ay) % p return cx, cy
def double(ax, ay): #A --> 2*A
due_inv = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffff7ffffe18 #1/2 modulo p ay_inv = inv(ay, p) # 1/y m = ((3 * due_inv) % p ) * (ax * ax * ay_inv % p) % p # m = 3x^2/2*y aax = (m * m - 2* ax) % p # x_2a = m^2 - 2x aay = (m * (ax - aax) - ay) % p # y_2a = m*(x - x_2a) -y return aax, aay
def mul(d,ax,ay):
dax, day = 0, 0 if (d%2 == 1): dax, day = ax, ay #solo se d e' dispari q=d//2 while q>0: ax, ay = double(ax,ay) if (q%2 > dax): #puo' succedere solo se dax=0 e q%2=1 cioe' la prima volta dax, day = ax, ay #solo se d e' pari elif (q%2): dax, day = add(ax, ay, dax, day) q=q//2 return dax, day
########################################################################################### #Funzioni legate agli address #Generazione di un address a partire da una chiave privata + codifica in base58 #formato wif per le chiavi private
# vedi --> https://github.com/stequald/bitcoin-sign-message/blob/master/signmessage.py#L125 # --> https://bitcointalk.org/index.php?topic=1026.msg12557#msg12557
# 58 character alphabet used __b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' __b58base = len(__b58chars)
def b58encode(v): #encode v, which is a string of bytes, to base58. long_value = 0
if bytes == str: # python2 for (i, c) in enumerate(v[::-1]): long_value += ord(c) << (8*i) # 2x speedup vs. exponentiation else: # python3 for (i, c) in enumerate(v[::-1]): long_value += ord(chr(c)) << (8*i) # 2x speedup vs. exponentiation result = '' while long_value >= __b58base: div, mod = divmod(long_value, __b58base) result = __b58chars[mod] + result long_value = div result = __b58chars[long_value] + result
# Bitcoin does a little leading-zero-compression: # leading 0-bytes in the input become leading-1s nPad = 0 if bytes == str: # python2 for c in v: if c == '\0': nPad += 1 else: break
else: # python3 for c in v: if chr(c) == '\0': nPad += 1 else: break
return (__b58chars[0]*nPad) + result
def b58decode(v, length): """ decode v into a string of len bytes.""" long_value = 0 for (i, c) in enumerate(v[::-1]): long_value += __b58chars.find(c) * (__b58base**i)
div, mod = divmod(long_value, 256) result = struct.pack("B", mod) #converte numero intero tra 0 e 255 in 1 byte https://docs.python.org/2/library/struct.html long_value = div
while long_value >= 256: div, mod = divmod(long_value, 256) result = struct.pack("B", mod) + result #stringa di byte long_value = div result = struct.pack("B", long_value) + result nPad = 0 for c in v: if c == __b58chars[0]: nPad += 1 else: break result = struct.pack("B", 0)*nPad + result
if length is not None and len(result) != length: return None return result
def priv_to_addr(d,compressed): #prende in input una chiave privata in formato esadecimale, #restituisce in output una stringa contenente l'address corrispondente # vedi https://gobittest.appspot.com/Address # vedi https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc#bitcoin-addresses
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
Px, Py = mul(d,Gx,Gy) # P = d*G
if (compressed == 1): if (Py % 2) == 0: P_string = '02' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari else: P_string = '03' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari else: #uncompressed P_string = '04' + hex(Px)[2:].rstrip('L').rjust(64,'0') + hex(Py)[2:].rstrip('L').rjust(64,'0')
h = sha256(a2b_hex(P_string)).digest() #sha256
h1 = hashlib.new('ripemd160') #ripemd160 h1.update(h)
a = b'\x00' + h1.digest() #aggiunge byte 00 all'inizio h2 = sha256(sha256(a).digest()).digest() #doppio sha256 per controllo
addr = a + h2[:4]
address = b58encode(addr) #ultimo passaggio: codifica in base 58
return address
def wif_to_hex(k,compressed): #prende in input una chiave privata in formato WIF (string), #restituisce in output la chiave privata come numero (long) #https://gobittest.appspot.com/PrivateKey
a = b58decode(k, compressed + 37) # decodifica --> stringa di byte version = a[0] checksum = a[-4:] b = a[:-4] # Version plus hash160 is what is checksummed
if (compressed == 1): key = b[1:-compressed] # elimina primo byte e l'ultimo (compressed) else: key = b[1:] # elimina solo primo byte (uncompressed)
h = sha256(sha256(b).digest()).digest() if h[0:4] == checksum : c = b2a_hex(key) # da stringa di byte a stringa di caratteri esadecimali d = int(c, 16) # trasforma una stringa in un numero
return d
else: print ("Errore: l'indirizzo non e' valido!") exit()
Possiamo così aggiornare anche lo script sign_msg.py (150 righe, molte di commenti) con le seguenti novità: 1) utilizza la libreria micro_ecdsa anzichè mini_ecdsa 2) funziona sia con python2 che python3 4) può importare la chiave privata in formato wif (stringa) anzichè hex (numero) 5) implementa un paio di controlli (per esempio verifica che l'indirizzo fornito sia compatibile con la chiave privata che si usa per firmare) 6) controlla la lunghezza di r e s aggiungendo eventuali zeri per mantenere 32 byte + 32 byte 7) prima della stampa finale fa una verifica autonoma sulla correttezza del risultato trovato 8 ) nella libreria micro_ecdsa è stata aggiunta una funzione 'inv' che calcola l'inverso di un elemento in un gruppo finito in modo più efficiente (si vedano nell'ultimo paragrafo intitolato teoria dei campi finiti (https://bitcointalk.org/index.php?topic=1339031.msg13658589#msg13658589) i link relativi all'identità di Bezout e all'algoritmo che implementa la procedura per trovare l'inverso) SIGN_MSG.PY #!/usr/bin/env python
from micro_ecdsa import add, mul, inv, priv_to_addr, wif_to_hex from hashlib import sha256 from binascii import a2b_hex, b2a_hex, b2a_base64 import subprocess #se si vuole generare k casualmente con /dev/urandom
#DATI DA IMPOSTARE MANUALMENTE msg = 'Ciao oggi 31 dicembre 2018 sto provando a firmare un messaggio' #inserire qui il messaggio scelto
#d = 0xd02e0eb2ef0ce08168fe746b58a91d485be97e71d2e2061f7807248a739f68d2 #inserire qui la propria chiave privata in formato hex #oppure d = 'L4CPJpu97pDVe3dscT6V6UJ4c68eENqHRhZGW39sYzjQf1WaLQX5' #inserire qui la propria chiave privata in formato WIF come stringa
address = '1FWBBmKhoPu3f6EZPhA6QiqTKoyz7Gj5CC' compressed = 1 #se e' compresso segnare 1, altrimenti 0
if (type(d) == str): d = wif_to_hex(d,compressed) #dal formato wif al numero + controllo validita' del formato della chiave
verifica = 0 #0 se non ti interessa, 1 per attivarla (la verifica rende molto piu' lenta tutta l'operazione) verifica_online = 0 ########################################################################################################################
#DATI CURVA SECP256K1 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
#CONTROLLO CHE LA CHIAVE PRIVATA d CORRISPONDA ALL'ADDRESS FORNITO address2 = priv_to_addr(d, compressed)
#assert address2 == address, "Errore! L'address fornito non coincide con la chiave privata!" if(address2 != address): print ("Errore! L'address fornito non coincide con la chiave privata!\n") exit()
#CHIAVE PRIVATA USA E GETTA E RELATIVA CHIAVE PUBBLICA (qui si setta la prima parte della firma, r) # di per se' k puo' essere completamente random # oppure va calcolato cosi' --> https://tools.ietf.org/html/rfc6979#section-3.3' #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
assert (k % n) != 0, "Che incredibile sfortuna! k trovato non e' accettabile!" #k non dev'essere ne' 0 ne' n k = k % n #non strettamente necessario
Qx, Qy = mul(k,Gx,Gy) # Q = k*G
assert (Qx % n) != 0, "Che incredibile sfortuna! Qx trovato non e' accettabile!" #Qx non dev'essere ne' 0 ne' n if (Qx < n): r = Qx i = 0; else: r = Qx - n; i = 2; if (Qy%2 == 1): i = i+1; if (compressed == 0): i = i + 27 else: i = i + 31 #per il significato di i si veda https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v
#FORMATTAZIONE MESSAGGIO msg_formattato = "\x18Bitcoin Signed Message:\n" + chr( len(msg) ) + msg e = sha256(sha256(msg_formattato.encode('utf-8')).digest()).digest() e = int(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 = inv(k,n) s = k_inv * (r * d + e) % n
#VERIFICA prima di codificare la firma e stamparla a video insieme al messaggio, #verifichiamo che la firma corrisponda effettivamente all'indirizzo bitcoin (e quindi alla chiave privata) #in nostro possesso if (verifica == 1):
# calcoliamo P2 = r^-1 * (s*Q -e*G) # calcoliamo P = d*G # verifichiamo che P = P2 prima di procedere r_inv = inv(r,n) ax, ay = mul((r_inv * s) % n, Qx, Qy) #r^-1*s*Q e = e % n bx, by = mul((r_inv * (n-e)) % n, Gx, Gy) #-r^-1*e*G = r^-1*(n-e)*G P2x, P2y = add(ax,ay,bx,by) #r^-1*(s*Q - e*G) Px, Py = mul(d,Gx,Gy)
if (Px != P2x) or (Py != P2y): print ("Errore! La firma trovata non e' corretta!\n") exit()
#CODIFICA DELLA FIRMA IN BASE 64 #per fare le cose bene controlliamo che sia r che s siano formati da 64 cifre esadecimali, #in caso contrario aggiungiamo degli zeri all'inizio della stringa che rappresenta il numero; #la codifica della firma di un messaggio consiste sempre in una sequenza di 65 byte, #mentre nel caso delle firme delle transazioni bitcoin si usa la codifica DER #vedi https://bitcoin.stackexchange.com/questions/12554/why-the-signature-is-always-65-13232-bytes-long #e https://bitcointalk.org/index.php?topic=653313.0 # https://github.com/bitcoin/bitcoin/pull/13666
r_string = hex(r)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari s_string = hex(s)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari sig = b2a_base64( a2b_hex( hex(i)[2:] + r_string + s_string ) ) sig = sig.decode('utf-8')[:-1] #per il significato di i si veda https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v
#STAMPA RISULTATO FINALE print ('') print ('-----BEGIN BITCOIN SIGNED MESSAGE-----') print (msg) print ('-----BEGIN SIGNATURE-----') print (address) print (sig) print ('-----END BITCOIN SIGNED MESSAGE-----') print ('')
#VERIFICA ONLINE if (verifica_online == 1):
print ('Verifica qui --> ') msg2 = msg.replace(' ','%20') print ('http://brainwalletx.github.io/#verify?vrAddr=' + address + '&vrMsg=' + msg2 + '&vrSig=' + sig) print ('')
Se non l'avete già fatto, ora che siete in grado di firmare un messaggio con un vostro indirizzo bitcoin fatelo e poi andate qui (https://bitcointalk.org/index.php?topic=996318.9700) e lasciate una testimonianza che colleghi il vostro nick a quell'indirizzo. Fatelo come buon proposito di inizio anno!
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on December 31, 2018, 11:33:15 AM
reserved
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: picchio on December 31, 2018, 11:36:40 AM
C'e' un motivo per il quale hai moderato il 3d?
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on December 31, 2018, 12:07:59 PM
C'e' un motivo per il quale hai moderato il 3d?
Dopo il thread nel quale avevo avuto interventi del tipo "mi aiuti a ricavare la chiave privata da quella pubblica?" preferisco mantenere un minimo di controllo almeno sui miei thread, così alleggerisco anche il lavoro dei moderatori del forum. Al momento comunque non mi è mai capitato di eliminare messaggi altrui.
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: Makkara on January 02, 2019, 02:06:24 PM
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on January 02, 2019, 05:25:56 PM
Si trovano tante librerie che fanno tutto, ma si fa sempre fatica a trovare una spiegazione dettagliata di questo tipo, con i singoli passaggi, grazie Arulbero. 8)
Prego! ;)
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: Piggy on January 04, 2019, 07:43:58 AM
Lavoro interessante e preciso come al solito, grazie :)
Appena ho un po di tempo lo provo un pò, stavo cercando di creare un implementazione minimale di una blockchain ( a scopo didattico ), quindi mi tornerà parecchio utile.
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: arulbero on January 04, 2019, 10:26:14 AM
Lavoro interessante e preciso come al solito, grazie :)
Appena ho un po di tempo lo provo un pò, stavo cercando di creare un implementazione minimale di una blockchain ( a scopo didattico ), quindi mi tornerà parecchio utile.
Il lavoro non è ancora finito, voglio aggiungere nell'ultimo script anche come passare dalla chiave pubblica all'address e come passare dalla chiave privata in formato esadecimale a quella in formato wif e viceversa. Ho aggiornato più volte lo script, quindi il consiglio è di non salvare lo script oggi per lavorarci tra 1 mese, ma copiarlo quando ti servirà (perchè nel frattempo lo avrò aggiustato/migliorato). Per esempio l'altro giorno ho aggiornato lo script che avevo pubblicato qui (https://bitcointalk.org/index.php?topic=5065574.msg47924812#msg47924812) per la generazione degli address, in quanto mi sono accorto che con python2 i numeri in formato esadecimale sotto i 18 caratteri venivano rappresentati con stringhe senza la L finale di long. Per quanta riguarda il lavoro di questo thread, la maggior parte delle difficoltà l'ho avuta nel continuare a pensare alle conversioni tra i vari formati (e a reperire le informazioni adeguate), in particolar modo le codifiche delle firme (r,s) sono diverse per quanto riguarda 1) le firme dei messaggi: sono sempre 1 byte + 32 byte + 32 byte --> base64 2) le firme delle transazioni: sia r che s possono essere minori di 32 byte, ma anche 33 byte causa la codifica DER che impone che se il primo bit è 1 quel numero è considerato negativo e quindi viene aggiunto il byte 00 all'inizio perchè torni positivo, r e s sono interi quindi con segno a lunghezza variabile; comunque la firma in questo caso viene salvata in formato esadecimale Quindi penso che aggiungerò uno script su come fare a costruire da zero una transazione e firmarla (non penso mi occuperò dell'invio alla rete). Un altro progetto futuro sarebbe quello di scrivere un parser per blockchain molto succinto (max 200 righe, mi piacciono i programmi corti). Trovo molto divertente cercare di capire come funzionano i meccanismi di questo sistema, il tuo progetto didattico è rivolto a degli studenti ?
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: picchio on January 04, 2019, 10:46:57 AM
Lavoro interessante e preciso come al solito, grazie :)
Appena ho un po di tempo lo provo un pò, stavo cercando di creare un implementazione minimale di una blockchain ( a scopo didattico ), quindi mi tornerà parecchio utile.
Tempo fa trovai un esempio in JS molto base ... ora ho provato a cercarlo ma mi sono accorto che ormai esistono parecchie implementazioni "didattiche". Io ti segnalo: https://www.coiners.it/come-creare-una-blockchain-in-javascript/ che fa riferimento a https://github.com/lhartikk/naivechain ...
Title: Re: ECDSA parte 2: firma di un messaggio e di una transazione bitcoin
Post by: Piggy on January 04, 2019, 01:06:47 PM
Tempo fa trovai un esempio in JS molto base ... ora ho provato a cercarlo ma mi sono accorto che ormai esistono parecchie implementazioni "didattiche". Io ti segnalo: https://www.coiners.it/come-creare-una-blockchain-in-javascript/ che fa riferimento a https://github.com/lhartikk/naivechain ...
Si, qualcosa del genere ma in grado di pocessare e salvare semplici transazioni provenienti da diversi indirizzi. Trovo molto divertente cercare di capire come funzionano i meccanismi di questo sistema, il tuo progetto didattico è rivolto a degli studenti ?
Per chiunque abbià voglia di capire capire e sperimentare le meccaniche chiave senza avere l'hoverhead che si trova nei sorgenti delle blockchain in produzione.
|