it-swarm-eu.dev

Come stimare il tempo necessario per decifrare la crittografia RSA?

Come stimare il tempo necessario per decifrare la crittografia RSA? Intendo il tempo necessario per decifrare la crittografia Rsa con lunghezza della chiave di 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360 e 16384?

67
Predator

Vedi questo sito per un riepilogo delle stime di forza chiave utilizzate da vari ricercatori e organizzazioni.

Il tuo "512 bit in 12μs" è completamente falso. Vediamo da dove viene. Il 1999 è stato l'anno in cui è stata eseguita la prima fattorizzazione generale a 512 bit, su una sfida pubblicata da RSA (la società) e chiamata RSA-155 (perché il numero consisteva in 155 cifre decimali - in binario , la lunghezza è di 512 bit). Questa fattorizzazione ha richiesto 6 mesi. Al evento Eurocrypt organizzato lo stesso anno (a maggio; a quel tempo era iniziato lo sforzo di fattorizzazione a 512 bit ma non era ancora stato completato), Adi Shamir , dal Weizmann Institute, ha presentato un dispositivo teorico chiamato TWINKLE che, presumibilmente, può aiutare un po 'in uno sforzo di fattorizzazione. Dovrebbe consistere in un numero enorme di diodi che lampeggiano a frequenze accuratamente selezionate, in una sorta di tubo nero. Shamir ha portato un dispositivo personalizzato che, a 10 metri di distanza, sembrava una macchina da caffè. Ha chiesto alle persone di spegnere la luce, in modo che il partecipante di Eurocrypt possa meravigliarsi dei diodi rossi quattro che lampeggiano a intervalli di 2, 3, 5 e 7 secondi. Ooh! e Aah! sono andati, sebbene la macchina reale, sarebbe stata costruita, richiederebbe qualche milione di diodi e frequenze nei 10 o 100 gigahertz. Quindi l'idea è divertente (almeno per i ricercatori in crittografia, che sono noti per avere uno strano senso dell'umorismo) ma non è ancora andato oltre il passo dello schizzo teorico. Shamir è un grande showman.

Tuttavia, TWINKLE è solo "aiuto". L'algoritmo di fattorizzazione più noto si chiama General Number Field Sieve ; i due algoritmi che vengono dopo sono Quadratic Sieve e Elliptic Curve Method . Un numero a 512 bit è fuori dalla portata di QS ed ECM con la tecnologia di oggi e a fortiori con la tecnologia del 1999. GNFS è molto complesso (matematicamente parlando), soprattutto perché richiede un'attenta selezione di alcuni parametri critici ("selezione polinomiale"). Quindi ci deve essere uno sforzo iniziale da parte di cervelli molto intelligenti (con computer di grandi dimensioni, ma i cervelli sono i più importanti qui). Successivamente, GNFS è costituito da due parti, il setaccio e il riduzione lineare. Il setaccio può essere realizzato in parallelo su centinaia o migliaia di macchine, che devono comunque essere relativamente grandi (in RAM), ma questo è fattibile. La riduzione lineare comporta il calcolo di cose con una matrice che è troppo grande per adattarsi a un computer (per diversi ordini di grandezza, e anche se assumiamo che detto computer abbia terabyte di RAM veloce). Esistono algoritmi per mantenere la matrice (che è piuttosto scarsa) in un formato compresso e poterlo ancora calcolare, ma questo è difficile. Nella fattorizzazione a 512 bit, il setaccio ha richiesto circa l'80% del tempo totale, ma per numeri maggiori la riduzione lineare è il collo di bottiglia.

TWINKLE riguarda solo l'accelerazione della parte di setacciamento. Non fa nulla per la riduzione lineare. In altre parole, accelera la parte che è facile (relativamente parlando). Perfino una metà di setacciamento potenziata con TWINKLE non sarebbe in nessun posto vicino a 12μs. Invece, sarebbe piuttosto utile ridurre a quattro settimane uno sforzo di setacciatura di quattro mesi. Il che è buono, in modo scientifico, ma non un record, soprattutto perché la riduzione lineare domina per dimensioni maggiori. La cifra di 12 μs sembra derivare da una confusione con una bestia ancora più mitica, la Quantum Computer , che potrebbe facilmente fattorizzare grandi numeri se si potesse costruire un QC con 512 "qubit". D-Wave ha recentemente annunciato un computer quantistico con 128 qubit, ma si è scoperto che questi non erano qubit "reali" e non sono adatti per la fattorizzazione (possono ancora fare teoricamente alcune approssimazioni efficienti nei problemi di ottimizzazione, il che è fantastico ma fondamentalmente non applicabile alla crittografia, perché gli algoritmi crittografici non sono suscettibili di approssimazioni - sono progettati in modo che un singolo bit sbagliato rimescoli il tutto). Il miglior controllo di qualità "reale" finora sembra essere il prototipo di IBM con, per quanto ricordo, ha 5 qubit, che consente di stabilire che 15 è uguale a 3 volte 5.

L'attuale record di fattorizzazione RSA è per n numero intero a 768 bit , annunciato nel dicembre 2009. Ci sono voluti quattro anni e ha coinvolto i teorici dei numeri più intelligenti che vivono attualmente sulla Terra, tra cui Lenstra e Montgomery, che hanno un po 'di dio- come lo stato in quelle cerchie. Di recente ho appreso che la selezione dei parametri per una fattorizzazione numerica a 1024 bit è iniziata (questa è la parte "intelligente"); il setaccio è tecnicamente fattibile (sarà costoso e comporterà anni di tempo di calcolo su molti cluster universitari) ma, per il momento, nessuno sa come eseguire la parte di riduzione lineare per un numero intero di 1024 bit. Quindi non aspettarti una pausa di 1024 bit in qualsiasi momento presto.

In questo momento, un dilettante dedicato che utilizza il codice pubblicato (ad es. Msieve ) può ottenere una fattorizzazione a 512 bit se ha accesso a computer potenti (diverse decine di PC di grandi dimensioni e almeno un orologio pieno di RAM veloce ) e alcuni mesi di tempo libero; fondamentalmente, "dilettante dedicato" significa "studente annoiato di informatica in una ricca università". Qualsiasi cosa oltre i 512 bit è fuori dalla portata di un dilettante.

Riepilogo: nel tuo codice, puoi restituire "praticamente infinito" come tempo di cracking per tutte le lunghezze di chiave. Un utente tipico non romperà una chiave RSA a 1024 bit, né ora né in dieci anni. Ci sono circa una dozzina di persone sulla Terra che possono, con qualsiasi credibilità, affermare che è concepibile, con una probabilità bassa ma diversa da zero, che potrebbe essere in grado di fattorizzare un singolo 1024- numero intero in un momento non specificato prima dell'anno 2020.

(Tuttavia, è estremamente facile eseguire l'implementazione di RSA o di qualsiasi applicazione che utilizza RSA in modo tale da poter recuperare i dati riservati in suo possesso senza disturbare affatto con la chiave RSA. Se utilizzi chiavi RSA a 1024 bit, puoi essere sicuro che quando la tua applicazione verrà hackerata, non sarà attraverso una fattorizzazione chiave RSA.)

90
Thomas Pornin

Risposta breve : Il metodo più semplice sarebbe usare il teorema del numero primo , ma fai attenzione che è un'approssimazione. Stimare quanto tempo ci vorrà per provare ognuno di quei numeri primi; il tempo per primo * il numero di numeri primi ti dà il tempo totale. Questo ti darà una stima per la ricerca della forza bruta.

È inoltre possibile utilizzare la stima del tempo di esecuzione per setaccio quadratico o setaccio campo numero generale . Ciò fornirà stime per gli algoritmi di factoring effettivamente utilizzati dalle persone che infrangono i numeri RSA.

Sfondo lungo :

Tempo della teoria dei numeri!

Innanzitutto, diamo un'occhiata alla dimensione dei numeri di cui stai parlando. Dato 2 ^ 3 = 8, che è 1000 in binario, possiamo vedere che questo è un numero a quattro bit, il minimo possibile. Quindi, 2 ^ 2 = 4 è un numero di 3 bit (100). Quindi per un dato x, il valore minimo possibile per garantire che abbiamo abbastanza bit è 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. Questo è il formato del numero hai a che fare con qui, vale a dire la dimensione del n essere presi.

La prossima grande domanda è: come viene costruita? n=pq Come sai dalla definizione di RSA, quindi stai cercando due numeri primi come fattori di quel numero. La domanda diventa quindi come determinare se un numero è primo e possiamo contarli?

Quindi per definizione un numero è irriducibile se, per qualsiasi numero x minore di esso, \gcd(p, x) = 1 ad eccezione di x=1. Tuttavia, possiamo migliorarlo. Dovresti rendertene conto abbastanza rapidamente che per qualsiasi numero, è primo o no. Se non è un numero primo, allora il suo gcd e almeno un primo devono essere maggiori di 1 (altrimenti sarebbe primo). Concludiamo da ciò che qualsiasi numero intero non primo deve essere divisibile per un insieme di numeri primi. Una prova matematica formale non è in realtà un grande salto da qui.

Questo è chiamato il teorema fondamentale dell'aritmetico e semplifica leggermente le cose. Quindi ora, quando ci alleniamo se un numero è primo, non abbiamo più bisogno di provare tutti i numeri, solo i numeri che già sappiamo sono primi!

Questo è chiaramente ancora molto lento, quindi facciamo un'altra osservazione - dati i fattori si verificano in coppia, il più basso dei due numeri è al massimo la radice quadrata del numero. Se siamo limitati a N (l'insieme dei numeri naturali), questo rappresenta un limite superiore al valore più grande possibile che dobbiamo controllare. Quindi ora, per qualsiasi numero N, dobbiamo cercare ogni numero intero partendo da 2 e andando a sqrt (N) per ogni numero che determiniamo come primo in quell'elenco. Possiamo quindi, se troviamo un numero primo, dedurre se esso influenza N stesso. Non ho intenzione di stimare il tempo di esecuzione di questo perché senza dubbio dirò la cosa sbagliata, ma ci vorrà molto tempo.

Ora vedi la forza di RSA. Scegli un numero primo molto grande e finisci con una lunga strada da percorrere. Allo stato attuale, dobbiamo iniziare da 2, che è chiaramente terribile.

Test di primalità mira a migliorare quello usando una varietà di tecniche. Il metodo ingenuo è quello che abbiamo appena discusso. Penso che una discussione dettagliata di queste tecniche sia probabilmente più appropriata per la matematica, quindi lasciatemi riassumere: tutti i tempi di autonomia sono spazzatura e usarlo come un modo per contare i numeri primi sarebbe orrendo.

Quindi, non possiamo contare il numero di numeri primi in modo affidabile inferiore a un numero senza prendere per sempre, poiché è effettivamente analogo alla fattorizzazione dei numeri interi. Che dire di una funzione che in qualche modo conta i numeri primi in un altro modo?

Immettere \pi(n) = \frac{n}{\log(n) - 1.08366}, un tentativo di Teorema dei numeri primi un'approssimazione del numero di numeri primi. È, tuttavia, esattamente quello; lo scopo di tale funzione è di contare esattamente il numero di numeri primi ma al momento ti dà semplicemente una stima. Per i tuoi scopi, questo potrebbe essere considerato abbastanza buono.

Tuttavia, è assolutamente ancora un'approssimazione. Dai un'occhiata al resto dell'articolo. Tra le altre cose, altre stime dipendono dall'ipotesi di Riemann.

Ok, allora, che dire di fattorizzazione in numeri interi ? Bene, il secondo metodo migliore fino ad oggi è chiamato Quadratic Sieve e il migliore è chiamato setaccio campo numerico generale . Entrambi questi metodi toccano alcuni matematici abbastanza avanzati; supponendo che tu sia serio riguardo ai numeri primi di factoring, mi metterei a leggere su questi. Certamente dovresti essere in grado di usare le stime per entrambi come miglioramenti nell'uso del teorema dei numeri primi, poiché se stai per fattorizzare i numeri primi grandi, vuoi usare questi e non una ricerca di forza bruta.

Ma voglio sapere di quanto?

Ok, abbastanza giusto. La fattorizzazione in numeri interi su un computer quantistico può essere effettuata in tempi ridicolmente brevi, supponendo che saremo in grado di implementare Algoritmo di Shor . Vorrei sottolineare, tuttavia, ciò richiede un computer quantistico. Per quanto ne so, lo sviluppo di computer quantistici della scala in grado di rompere RSA è attualmente lontano. Vedi sviluppi dell'informatica quantistica .

In ogni caso, l'algoritmo di Shor sarebbe esponenzialmente più veloce. La pagina su di essa fornisce una stima per il tempo di esecuzione di quello, che potresti voler includere nelle tue stime.

25
user2213

Un'altra opzione è quella di creare un grande database di possibili chiavi e utilizzarlo come tabella di ricerca. Apparentemente non hai nemmeno bisogno di TUTTI i numeri primi, solo un paio ti farà attraversare una grande percentuale di traffico Internet.

Fonte: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny