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)
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)
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://bitcointalksearch.org/topic/m.12557 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://bitcointalksearch.org/topic/m.12557
# 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
#!/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!