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.

[1713591062]

1713591062

[1713591062]

1713591062

[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ì!