ricavare la chiave privata dalla chiave pubblica in casi particolari

[arulbero]

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.

[1715666562]

1715666562

[arulbero]

Se qualcuno vuole fare un test, basta che scelga una chiave privata random tra 1 e 2^60 (in formato esadecimale tra 01 e 1000000000000000), la inserisca qui e fornisca la chiave pubblica corrispondente.

In teoria dovrei essere in grado in pochi minuti di ricavare la chiave privata.


Sarebbe interessante fare un test del tipo: genero una chiave privata random, pubblico la chiave pubblica corrispondente e il suo indirizzo. Quindi fornisco anche un intervallo di valori che contiene la chiave privata, intervallo di ampiezza grande ma non troppo (per esempio potrebbe essere 2^80 o 2^100).
Come incentivo si potrebbe inviare dei btc a quell'indirizzo e vedere quanto tempo qualcuno impiega a trovare quella chiave privata.

Si avrebbe così una misura indiretta della capacità esistente di attaccare il meccanismo delle chiavi private/pubblica in bitcoin.

[keyjoke]

Public Key (130 characters [0-9A-F]):
0434F0C95547AC04E441E54903687AC5A8711961F3CF88748A1346ED2425B7A97C3C14315D12BAB 9629F1C3F568959E9F30BC653B0DFFDCA4B47E771D8203A9D22

Public Key (compressed, 66 characters [0-9A-F]):
0234F0C95547AC04E441E54903687AC5A8711961F3CF88748A1346ED2425B7A97C

[arulbero]

Public Key (130 characters [0-9A-F]):
0434F0C95547AC04E441E54903687AC5A8711961F3CF88748A1346ED2425B7A97C3C14315D12BAB 9629F1C3F568959E9F30BC653B0DFFDCA4B47E771D8203A9D22

Public Key (compressed, 66 characters [0-9A-F]):
0234F0C95547AC04E441E54903687AC5A8711961F3CF88748A1346ED2425B7A97C

Intervallo dove sta la chiave privata? Ho provato nell'intervallo 0x01 -  0x1000000000000000 ma non ho trovato nulla.

Al momento il mio programma funziona solo in un intervallo da 01 in poi, devo fare qualche piccola modifica per traslare l'intervallo di ricerca. Se non mi fornisci anche l'intervallo di ricerca non posso trovarla (evidentemente  )

[keyjoke]

0000000000000000000000000000000000000000000000000000000000000001 - 0000000000000000000000000000000000000000000000010000000000000000

sorry, my bad (scusa ho sbagliato)

this is new
0000000000000000000000000000000000000000000000000000000000000001 - 0000000000000000000000000000000000000000000000001000000000000000

Public Key (130 characters [0-9A-F]):
04ACB7E3CC5581796BD2B620C34D6BC1CD0D32B17FCACE8CC8A3F1A36B25FEE45BB9D868CB3FA1C B2F8907EFFC8CAD069E51CAA48F3DE53A62EAD79A2FA2D3A8E8
Public Key (compressed, 66 characters [0-9A-F]):
02ACB7E3CC5581796BD2B620C34D6BC1CD0D32B17FCACE8CC8A3F1A36B25FEE45B

[arulbero]

this is new
0000000000000000000000000000000000000000000000000000000000000001 - 0000000000000000000000000000000000000000000000001000000000000000

Public Key (130 characters [0-9A-F]):
04ACB7E3CC5581796BD2B620C34D6BC1CD0D32B17FCACE8CC8A3F1A36B25FEE45BB9D868CB3FA1C B2F8907EFFC8CAD069E51CAA48F3DE53A62EAD79A2FA2D3A8E8
Public Key (compressed, 66 characters [0-9A-F]):
02ACB7E3CC5581796BD2B620C34D6BC1CD0D32B17FCACE8CC8A3F1A36B25FEE45B

1 minuto e 19 secondi:

Code:

Private key : 0000000000000000000000000000000000000000000000000777666655554444
Public key  : acb7e3cc5581796bd2b620c34d6bc1cd0d32b17fcace8cc8a3f1a36b25fee45b b9d868cb3fa1cb2f8907effc8cad069e51caa48f3de53a62ead79a2fa2d3a8e8

[Makkara]

Il codice è in javascript giusto? Potresti mettere il tutto da qualche parte dove sia visibile se non è un problema? Grazie

[keyjoke]

Sì, è fantastico. Posso anche provare il tuo programma? Sto lavorando su un argomento simile.

[arulbero]

Il codice è in javascript giusto? Potresti mettere il tutto da qualche parte dove sia visibile se non è un problema? Grazie

Sì, è fantastico. Posso anche provare il tuo programma? Sto lavorando su un argomento simile.

Il programma è in puro C, dubito proprio che in javascript si possano ottenere prestazioni del genere.

Al momento il mio programma è difficilmente usabile, ci sono pochi commenti, alcune parti sono scritte in assembly e funzionano solo su alcuni processori (ad esempio l'istruzione mulx è supportata dal mio Xeon ma non da tutti i processori).

Di fatto per scrivere questo programma ho modificato un programma che ho trovato in rete sostituendo la libreria secp256k1 con una libreria scritta da me per il progetto LBC collider.

Vi consiglio per adesso di provare il programma "break-short" che vi ho linkato, funziona anche se ha prestazioni ben peggiori del mio, ma almeno è più comprensibile. In quel programma bisogna definire l'ampiezza del "passo gigante":

 #define GSTEP (1<<23)

in questo caso con 2^23 vuol dire che farà una ricerca in uno spazio di 2^46 chiavi.
Tenete conto che non potete superare la memoria (RAM) del vostro PC (dove si mette l'hash table), quindi difficilmente potrà funzionare sopra un valore di 2^27 / 2^28 (dipende da quanta RAM avete). Se avete dubbi sull'utilizzo di quel programma chiedete pure.

Nel mio programma per andare oltre il vincolo della RAM la riscrivo completamente ogni volta che devo andare sopra quel valore, partizionando lo spazio di ricerca.

Consiglio vivamente di leggersi http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/  per capire cosa sta facendo esattamente il programma.

[Makkara]

Scusa, avevo capito male io, appena ho un po di tempo leggo l'articolo e provo un pò il programma originale.

Avevo scambiato il secondo link per generare le chiavi per il programma che hai scritto 

[bill32767]

Il codice ? in javascript giusto? Potresti mettere il tutto da qualche parte dove sia visibile se non ? un problema? Grazie

S?, ? fantastico. Posso anche provare il tuo programma? Sto lavorando su un argomento simile.

Di fatto per scrivere questo programma ho modificato un programma che ho trovato in rete sostituendo la libreria secp256k1 con una libreria scritta da me per il progetto LBC collider.

Sarei felice di avere il programma C o puoi aiutarmi su come eseguire questo: (https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89) su visual studio, cio? dove inserire l'intervallo di ricerca, chiave pubblica e indirizzo bitcoin sullo script. Grazie.

[bill32767]

Se qualcuno vuole fare un test, basta che scelga una chiave privata random tra 1 e 2^60 (in formato esadecimale tra 01 e 1000000000000000), la inserisca qui e fornisca la chiave pubblica corrispondente.

In teoria dovrei essere in grado in pochi minuti di ricavare la chiave privata.


Sarebbe interessante fare un test del tipo: genero una chiave privata random, pubblico la chiave pubblica corrispondente e il suo indirizzo. Quindi fornisco anche un intervallo di valori che contiene la chiave privata, intervallo di ampiezza grande ma non troppo (per esempio potrebbe essere 2^80 o 2^100).
Come incentivo si potrebbe inviare dei btc a quell'indirizzo e vedere quanto tempo qualcuno impiega a trovare quella chiave privata.

Si avrebbe così una misura indiretta della capacità esistente di attaccare il meccanismo delle chiavi private/pubblica in bitcoin.

Ho un indirizzo bitcoin, chiave pubblica e intervallo ma non posso inviarti un PM, per favore mi consenta di farlo. Grazie.

[arulbero]

Prego chiunque legga questo thread di leggere con attenzione tutti i miei post prima di contattarmi.

Solo oggi ho ricevuto 2 messaggi personali nei quali mi si chiedeva di:

1) indovinare una chiave privata all'interno di un intervallo di oltre 2^255 chiavi!
2) indovinare chiavi private relative ad address con migliaia di bitcoin

Per quanto riguarda il punto 1), ripeto che non ho trovato assolutamente il modo di risolvere il problema del logaritmo discreto nelle curve ellittiche, detto in termini più semplici devo già conoscere la maggior parte dei 256 bit della chiave privata per poter ricavare i rimanenti in un tempo umano: ripeto, ne posso "indovinare" 70, ma gli altri 190 li dovete già sapere

Per il punto 2), se fossi in grado di trovare la chiave privata per sbloccare 10000 bitcoin, perchè dovrei farlo per voi? Non vi sembra un po' assurdo?

Ho aperto questo thread perchè ritenevo interessante dal punto di vista tecnico riuscire a misurare fin dove è possibile invertire il processo chiave privata -> chiave pubblica, e mi ritrovo invece sommerso di richieste di newbie che non hanno nemmeno capito di cosa si sta parlando.

Non posso trovare nessuna chiave privata a partire solo dalla relativa chiave pubblica. Tutti i blocchi minati da Nakamoto utilizzano transazioni con output P2PK, quindi ci sarebbero un sacco di bitcoin a "disposizione" e pensate di ottenerli con il mio programma?  

Lasciate perdere.

[Makkara]

Solo oggi ho ricevuto 2 messaggi personali nei quali mi si chiedeva di:

1) indovinare una chiave privata all'interno di un intervallo di oltre 2^255 chiavi!
2) indovinare chiavi private relative ad address con migliaia di bitcoin

E va bhe dai cosa ci vuoi fare, hai aperto il thread con dei buoni propositi, ma il titolo del thread era troppo ghiotto per alcuni 

[bill32767]

Prego chiunque legga questo thread di leggere con attenzione tutti i miei post prima di contattarmi.


Non posso trovare nessuna chiave privata a partire solo dalla relativa chiave pubblica. Tutti i blocchi di satoshi utilizzano transazioni con output P2PK, quindi ci sarebbero un sacco di bitcoin a "disposizione" e pensate di ottenerli con il mio programma?  

Lasciate perdere.

 

Mi dispiace tanto disturbarti, grazie per tutto il tuo aiuto fino ad ora. Per favore, permettimi di inviarti un PM per l'ultima volta, grazie, grazie.

[fucilator_3000]

Ciao, vengo dal post in lingua inglese

Mandami un PM, cosi posso darti il contatto Telegram e spiegarti invece la mia idea!

[Makkara]

Ciao, vengo dal post in lingua inglese

Mandami un PM, cosi posso darti il contatto Telegram e spiegarti invece la mia idea!

Quale sarebbe l'idea talmente segreta da non poter essere spiegata su questo thread?    Fregare i bitcoin dall'indirizzo di satoshi? 

[fucilator_3000]

Ciao, vengo dal post in lingua inglese

Mandami un PM, cosi posso darti il contatto Telegram e spiegarti invece la mia idea!

Quale sarebbe l'idea talmente segreta da non poter essere spiegata su questo thread?    Fregare i bitcoin dall'indirizzo di satoshi? 

In realtà no, assolutamente no

Volevo discutere a livello "teorico e matematico"

[gbianchi]

Per il punto 2), se fossi in grado di trovare la chiave privata per sbloccare 10000 bitcoin, perchè dovrei farlo per voi? Non vi sembra un po' assurdo?

Invece e' e interessante come argomento...

Secondo me a parte tutti i tecnicismi, e' l'ennesima dimostrazione del perche' gli strumenti non
potranno mai salvarci.

Per quanto bitcoin (con tutti i suoi difetti) fosse filosoficamente un ottimo strumento,
e' attualmente utilizzato quasi solamente come strumento speculativo.

perche'? perche' il numero di "furbi" e' nettamente superiore al numero degli intelligenti.

Potra' sembrare un argomentazione banale e superficiale, ma purtroppo e' la realta'.
I furbi, quelli che vedono fondamentalmente solo il brevissimo periodo, (ossia gli speculatori)
surclassano come numero gli intelligenti (ossia quelli che hanno una visione piu' di lungo periodo)

E quasto vale dappertutto, in politica, in finanza, sul lavoro, ovunque.

La nostra cultura ci ha educato alla furbizia e non all'intelligenza e questi
sono i risultati.

Porre una domanda del genere e' estremamente stupido, se uno e' intelligente, invece e'
lecito se uno e' furbo.

Cosi' come e' lecito per un furbo pensare di arricchirsi guardando dei grafici e immaginando
che possano essere strumenti che permettono di prevedere il futuro.

O pensare che uno possa con un corso insegnarti metodi per diventare ricco.

Questa e' la nostra cultura, e non siamo capaci di uscirne.


 

[fucilator_3000]

Per il punto 2), se fossi in grado di trovare la chiave privata per sbloccare 10000 bitcoin, perchè dovrei farlo per voi? Non vi sembra un po' assurdo?

Invece e' e interessante come argomento...

Secondo me a parte tutti i tecnicismi, e' l'ennesima dimostrazione del perche' gli strumenti non
potranno mai salvarci.

Per quanto bitcoin (con tutti i suoi difetti) fosse filosoficamente un ottimo strumento,
e' attualmente utilizzato quasi solamente come strumento speculativo.

perche'? perche' il numero di "furbi" e' nettamente superiore al numero degli intelligenti.

Potra' sembrare un argomentazione banale e superficiale, ma purtroppo e' la realta'.
I furbi, quelli che vedono fondamentalmente solo il brevissimo periodo, (ossia gli speculatori)
surclassano come numero gli intelligenti (ossia quelli che hanno una visione piu' di lungo periodo)

E quasto vale dappertutto, in politica, in finanza, sul lavoro, ovunque.

La nostra cultura ci ha educato alla furbizia e non all'intelligenza e questi
sono i risultati.

Porre una domanda del genere e' estremamente stupido, se uno e' intelligente, invece e'
lecito se uno e' furbo.

Cosi' come e' lecito per un furbo pensare di arricchirsi guardando dei grafici e immaginando
che possano essere strumenti che permettono di prevedere il futuro.

O pensare che uno possa con un corso insegnarti metodi per diventare ricco.

Questa e' la nostra cultura, e non siamo capaci di uscirne.


 

Non sono pienamente d'accordo...

Chi possiede Bitcoin lo può fare assolutamente per entrambi i motivi insieme. Perché non fare trading in modo da accumulare sempre più BTC?

Non ci vedo nulla di male nella speculazione onestamente...

Non mi riferisco chiaramente a chi è entrato durante la scorsa Bull Run, non sapendo niente di blockchain o della filosofia del Bitcoin, ma solamente per tirarci un guadagno immediato, quelli sono stupidi ma l'hanno pagata molto cara (si sono bruciati il conto) ed è bene così!

[arulbero]

Per quanto bitcoin (con tutti i suoi difetti) fosse filosoficamente un ottimo strumento,
e' attualmente utilizzato quasi solamente come strumento speculativo.

perche'? perche' il numero di "furbi" e' nettamente superiore al numero degli intelligenti.

Potra' sembrare un argomentazione banale e superficiale, ma purtroppo e' la realta'.
I furbi, quelli che vedono fondamentalmente solo il brevissimo periodo, (ossia gli speculatori)
surclassano come numero gli intelligenti (ossia quelli che hanno una visione piu' di lungo periodo)

E quasto vale dappertutto, in politica, in finanza, sul lavoro, ovunque.

La nostra cultura ci ha educato alla furbizia e non all'intelligenza e questi
sono i risultati.

Esiste anche una componente morale che stai trascurando.

Vedere lontano (essere intelligenti) vuol dire occuparsi anche di cose lontane nel tempo (futuro) e nello spazio (altre persone diverse da me). In breve: andare oltre se stessi.

Guardare solo all'immediato (essere furbi) vuol dire occuparsi solo di ciò che è vicino nel tempo (brevissimo periodo) e nello spazio (ci si occupa solo del proprio tornaconto o di quello degli immediati vicini: parenti/amici).

Ma io rimango fiducioso, bitcoin è uno strumento ideato evidentemente da persone intelligenti, non furbe!  

[gbianchi]

Ma io rimango fiducioso, bitcoin è uno strumento ideato evidentemente da persone intelligenti, non furbe!  

Se vuoi la radice del ragionamento che proponevo e' proprio questa.

Siamo pieni di esempi di cose ideate da persone intelligenti,
e poi utilizzate malamente da una marea di furbi.

Cioe' per quanto tu inventi strumenti potenti e potenzialmente utilissimi,
poi vengono "trapiantati" nella realta', e la realta' e' fatta principalmente da furbi.

Nonostante io sia abbastanza sgamato e nella vita ne abbia viste tante,
mi ero illuso che l'idea di bitcoin potesse essere cosi' potente da cambiare un po' le cose.

Ma mi sono reso conto che non e' cosi', e che lo strumento per l'ennesima volta
non sara' sufficente a migliorare il nostro modo di essere.

Ovviamente qui siamo ampiamente OT e in un ragionamento che sconfina dal
filosofico all'umanistico.

[rrupoli]

Ho aperto questo thread perchè ritenevo interessante dal punto di vista tecnico riuscire a misurare fin dove è possibile invertire il processo chiave privata -> chiave pubblica, e mi ritrovo invece sommerso di richieste di newbie che non hanno nemmeno capito di cosa si sta parlando.

Non posso trovare nessuna chiave privata a partire solo dalla relativa chiave pubblica. Tutti i blocchi minati da Nakamoto utilizzano transazioni con output P2PK, quindi ci sarebbero un sacco di bitcoin a "disposizione" e pensate di ottenerli con il mio programma?  
Lasciate perdere.

Uno degli aspetti più affascinanti dell'universo Bitcoin che solletica la mente di migliaia di individui consiste nell'esistenza di centinaia di indirizzi di cui molto probabilmente nessuno possiede più la chiave privata, i cosiddetti "zombie address" o indirizzi dormienti che contengono patrimoni milionari.

Per chi non ne avesse mai sentito parlare, qui si può fare un'idea di quante siano queste vere e proprie miniere d'oro a cielo aperto:    

https://bitinfocharts.com/top-100-dormant_5y-bitcoin-addresses.html

Prendiamo per esempio l'indirizzo zombie più goloso in assoluto:
1FeexV6bAHb8ybZjqQMjJrcCrHGW9sb6uF

Esso contiene la bellezza di quasi 80000 bitcoin, per un valore equivalente di 518 milioni di dollari al cambio attuale.

L'attrazione fatale per molti consiste nell'idea romantica di potersi arricchire in maniera SPUDORATA indovinando "semplicemente" una sequenza alfanumerica digitata a caso sulla tastiera del proprio laptop.

E' l'illusione della ricchezza facile, della vincita multimilionaria al superenalotto senza nemmeno dover spendere i soldi per la giocata.

E' il biglietto della lotteria di capodanno gratuito che si può giocare quante volte si vuole, digitando una ad una le cifre ogni volta oppure usando un software che giochi per noi milioni di biglietti gratuiti della lotteria al secondo.

Nella storia del genere umano non si è mai verificata una situazione tale da poter letteralmente accarezzare con mano una ricchezza così imponente che dista da noi solo una manciata di lettere e numeri da pigiare su una tastiera, senza compiere alcuna azione che potrebbe essere classificata come "illegale" essendo tali bitcoin considerati ormai persi per sempre nello sterminato spazio bidimensionale costellato dai punti di una curva ellittica.
Bitcoin che non appartengono de facto più a nessuno, che nessuno potrà mai rivendicare come propri essendo per definizione il proprietario di quei bitcoin solo ed unicamente il possessore della chiave privata dell'indirizzo che li contiene.

L'idea che battendo a caso una sequenza di lettere e numeri su una tastiera possa renderci _istantaneamente_ schifosamente ricchi cambiando la nostra vita per sempre è un'idea estremamente potente e romantica non solo per i newbies ma anche per coloro in grado di cogliere le più sottili sfumature matematiche insite nei meccanismi a protezione del sistema Bitcoin.

Al di là di queste piacevoli considerazioni oniriche, tornando con i piedi per terra, possiamo attribuire un ruolo importante a tali indirizzi zombie che contengono immani ricchezze:
questi indirizzi rappresentano le sirene di allarme del sistema Bitcoin, il canarino nella miniera la cui morte ci avvisa della presenza di gas venefico.

Finche questi indirizzi rimarranno inespugnati continuando a custodire inalterato il loro prezioso carico, potremo continuare ad essere ragionevolmente confidenti sul fatto che il sistema Bitcoin non è ancora stato violato.
 
E soprattutto è possibile continuare a sognare ad occhi aperti senza rischiare di cadere vittime di pericolose ludopatie, in fondo non ci costa nulla...  

[arulbero]

Uno degli aspetti più affascinanti dell'universo Bitcoin che solletica la mente di migliaia di individui consiste nell'esistenza di centinaia di indirizzi di cui molto probabilmente nessuno possiede più la chiave privata, i cosiddetti "zombie address" o indirizzi dormienti che contengono patrimoni milionari.

Per chi non ne avesse mai sentito parlare, qui si può fare un'idea di quante siano queste vere e proprie miniere d'oro a cielo aperto:
....  

Al di là di queste piacevoli considerazioni oniriche, tornando con i piedi per terra, possiamo attribuire un ruolo importante a tali indirizzi zombie che contengono immani ricchezze:
questi indirizzi rappresentano le sirene di allarme del sistema Bitcoin, il canarino nella miniera la cui morte ci avvisa della presenza di gas venefico.

Finche questi indirizzi rimarranno inespugnati continuando a custodire inalterato il loro prezioso carico, potremo continuare ad essere ragionevolmente confidenti sul fatto che il sistema Bitcoin non è ancora stato violato.

Concordo in pieno con il tuo post.
Aggiungo solo che ci sono canarini nella miniera più sensibili rispetto ai mega address dormienti; qualora infatti quest'ultimi dovessero essere svuotati, sarebbe già troppo tardi: il sistema sarebbe irrimediabilmente andato prima che uno possa uscirne (e in tal caso il canarino avrebbe perso la sua funzione premonitrice).

L'alternativa più sensibile a cui alludo è la famosa "puzzle transaction":  https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

https://bitcointalk.org/index.php?topic=2141947.msg21464880#msg21464880

che è stata costruita inviando a 160 indirizzi diversi quote crescenti di bitcoin (all'indirizzo 50 -> 0.50 btc, all'indirizzo 100 -> 1 btc, all'indirizzo 160 -> 1.60 btc). Ciascuno di questi indirizzi è stato generato a partire da una chiave di lunghezza (e quindi "entropia") crescente: la chiave dell'indirizzo 1 ha una lunghezza di 1 bit, quella dell'indirizzo 2 ha una lunghezza di 2 bit, e così via.

Al momento sono state scoperte le prime 56 chiavi private, e si sta cercando di violare la numero 57. Questo fatto fornisce un'idea della capacità dell'insieme degli attaccanti alla rete di bitcoin di generare address e di violarli. Al momento sappiamo che una chiave con più di 60 bit di entropia non è rinvenibile (almeno nel breve periodo, diciamo 1 anno).  

Ricordo che, essendo gli indirizzi sequenze di 160 bit, è questo il numero che quantifica la sicurezza di bitcoin. Ogni chiave privata controlla in realtà 2^96 indirizzi distinti (limitiamoci agli indirizzi P2PKH). Per questo sarebbe sufficiente utilizzare 2^160 chiavi (circa) per poter accedere a qualsiasi bitcoin esistente in qualsiasi indirizzo P2PKH.

Per farsi un'idea delle grandezze in gioco e del loro ordine, guardiamo alla potenza computazionale della rete di mining che ha raggiunto un hashing power (potenza relativa solo allo sha256, senza il calcolo del passaggio chiave privata -> chiave pubblica e senza ripemd160) di circa 2^90 hash all'anno. E questo avviene a fronte di incentivi potentissimi quali sono i 12.5 bitcoin x 144 blocchi al giorno x 365 giorni all'anno = 657000 bitcoin all'anno.

Ora pur assumendo che si costruiscano delle macchine che effettuino alla stessa velocità anche le operazioni mancanti per ottenere gli address (e come notava rrupoli gli incentivi naturali ci sarebbero), saremmo ben al di sotto delle 2^100 chiavi private "provate" all'anno. Meno di 1/2^60 di quelle necessarie per accedere a tutti i bitcoin.

Il discorso cambia invece per le chiavi P2PK e per tutti gli indirizzi P2PKH che hanno già esposto la loro chiave pubblica. Come già osservato nel primo post di questo thread, in quel caso sarebbero sufficienti 2^128 passi (anche se ciascuno più complesso rispetto alla semplice generazione "consecutiva" di chiavi pubbliche) per poter violare un address specifico. Ma al momento non ci sono macchine degne di nota specializzate nel calcolo chiave privata -> chiave pubblica.

[bill32767]

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.

INDIRIZZO BTC: 1LzhS3k3e9Ub8i2W1V8xQFdB8n2MYCHPCa
PUB KEY: 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
PK HEX RANGE: 2 ^ 55 - 2 ^ 56 36028797018963968 - 72057594037927936

Per favore aiutatemi con la chiave privata (in hex) di quanto sopra, grazie.