Come tutti ben sapete non è possibile ricavare in tempi umani da una chiave pubblica la sua chiave privata.
L'associazione chiave pubblica - chiave privata appare del tutto casuale se vista dal punto di vista della chiave pubblica, e quindi l'unico modo per ricavare la chiave privata sembrerebbe quello di provare tutte le chiavi private da 1 in poi finchè non si ottiene quella corretta. Poichè nella curva ellittica usata da bitcoin quel numero è dell'ordine di 2^256, questo è anche l'ordine di grandezza dei tentativi necessari con un attacco brute force.
Esistono però algoritmi che migliorano la situazione, essi permettono infatti di ricavare la chiave privata in 2^128 step invece che in 2^256. Per questo si dice di solito che la sicurezza di bitcoin è quantificabile in 128 bit. Alcuni di questi algoritmi (Pollard Rho) si basano sul paradosso dei compleanni; questo paradosso (paradosso solo in apparenza) mette insieme i seguenti fatti:
1) utilizzando tutte le 2^256 chiavi pubbliche, si possono costruire in tutto 2^512 coppie distinte di chiavi pubbliche
2) tra quelle 2^512 coppie ci sono 2^256 coppie formate da 2 chiavi pubbliche identiche tra loro
Dal punto 1) e dal punto 2) si evince come in media ci sia 1 coppia di chiavi pubbliche identiche tra loro ogni 2^256 coppie di chiavi (2^256/2^512 = 1/2^256).
Ora osserviamo che
3) sono sufficienti 2^128 chiavi pubbliche distinte per costruire (all'incirca) 2^256 coppie distinte di chiavi pubbliche
Il risultato finale è che se genero 2^128 chiavi pubbliche, ho di fatto anche generato 2^256 coppie di chiavi, e in media ho ottenuto 1 coppia di chiavi identiche, cioè ho generato almeno 2 volte la stessa chiave.
Sfruttando questo fatto e una opportuna "random walk" simulata, si riesce in soli 2^128 step a generare 2 volte una stessa chiave pubblica, e questa particolare collisione permette di ricavare la chiave privata che si stava cercando.
Altri algoritmi, come "Baby Step Giant Step" si basano invece solo sul fatto che per generare 2^256 chiavi pubbliche basta calcolare solo 2 liste di 2^128 chiavi e poi confrontarle (qui si utilizzano le proprietà algebriche della curva per cui ogni chiave P=d*G si può decomporre in P = P1+P2.), per i dettagli vedere
http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/Utilizzando quest'ultimo approccio (che non è di natura probabilistica a differenza di Pollard Rho) è possibile ricavare da una chiave pubblica la chiave privata sempre in 2^128 step. Il vantaggio di questo metodo è che è possibile fare una ricerca anche solo su un sottospazio di tutte le chiavi pubbliche possibili, a patto ovviamente di avere delle informazioni approssimative riguardo la chiave privata (cioè se si sa già dove si trova più o meno la chiave privata).
Nei mesi scorsi ho scritto un picccolo programma in C (modificandone uno trovato in rete) che mi permette di ricavare la chiave privata in pochissimo tempo se si conosce la posizione della chiave privata all'interno di un range di valori dell'ordine di 2^60 - 2^70.
In pratica, per fare un esempio, se una persona sceglie una chiave privata tra 1 e 2^70 (oppure tra x e x + 2^70) e fornisce la chiave pubblica corrispondente, il programma riesce a ricavare la chiave privata corretta.
Il programma deve conoscere però l'intervallo dove cercare.Ovviamente 2^70 è una piccolissima frazione di 2^256, lo so che non ho scoperto nulla, ma è molto interessante verificare che, mentre per generare anche solo 2^60 chiavi pubbliche sarebbero necessari molti anni anche con la scheda video più potente, basta invece una semplice cpu per ricavare in pochi minuti la chiave cercata.
)