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

[arulbero]

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:

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=

[arulbero]

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

Lo 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_ecdsa

Per 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

Code:

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

ADDIZIONE TRA 2 PUNTI DELLA CURVA   A + B -> C (formula)

Code:

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)

Code:

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)

Code:

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

Code:

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

Code:

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

Code:

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 i link relativi all'identità di Bezout e all'algoritmo che implementa la procedura per trovare l'inverso)


SIGN_MSG.PY

Code:

#!/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 e lasciate una testimonianza che colleghi il vostro nick a quell'indirizzo.

Fatelo come buon proposito di inizio anno!

[arulbero]

reserved

[picchio]

C'e' un motivo per il quale hai moderato il 3d?

[arulbero]

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.

[Makkara]

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.

[arulbero]

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.

Prego! 

[Piggy]

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.

[arulbero]

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

[picchio]

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

[Piggy]

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.