Tabelle Rainbow come soluzione a grande factoring

Question

In spiegazioni ho letto sulla crittografia della chiave pubblica, si dice che un numero elevato è inventato moltiplicando insieme 2 numeri estremamente grandi. Dal momento che il factoring del prodotto di grandi PREMS è quasi incredibilmente che richiede tempo, hai sicurezza.

Questo sembra un problema che potrebbe essere valido in modo valido con tavoli Rainbow. Se conosci la dimensione approssimativa dei primi utilizzati e sappi che ci sono 2 di loro, potresti costruire rapidamente una tabella arcobaleno. Sarebbe un grande tavolo potente, ma potrebbe essere fatto e il compito potrebbe essere parallelizzato attraverso l'hardware.

Perché i tavoli rainbow sono un modo efficace per battere il tasto pubblico Crypto basato sulla moltiplicando PREMES di grandi dimensioni?

Disclaimer: ovviamente decine di migliaia di persone consapevoli di sicurezza smart-smart non sono appena capitate da decenni cosa pensavo in un pomeriggio. Presumo che io stia fraintendendo questo perché stavo leggendo spiegazioni del laico semplificato (ad esempio: se vengono utilizzati più di 2 numeri) ma non conosco ancora abbastanza sapere dove è il mio gap di conoscenza.

Modifica: So che "Rainbow Table" si riferisce all'utilizzo pre-calcolato hashhes in una tabella di ricerca, ma quanto sopra sembra come un attacco del tavolo arcobaleno quindi sto usando Il termine qui.

---

.

Modifica 2: Come indicato nelle risposte, non c'è modo di memorizzare solo tutti i primi, molto meno tutti i loro prodotti.

.
• Questo sito dice che ci sono circa Questo molti PREMES di 512 bit: ((2 ^ 511) * 1) / (512 log (2))= 4.35 × 10 ¹⁵¹
• the massa del sole è 2 × 10 ^{30 kg o 2 × 10 33 G}
• questo è 2,17 × 10 ^{124 PREMES per grammo del sole.}
• qty. di 512 numeri di bit che possono adattarsi in un kilobyte: 1 kb= 1024 bytes= 8192 bit / 512= 16
• che può adattarsi in un terabyte: 16 * 1024 * 1024 * 1024= 1,72 × 10 ¹⁰
• petabyte: 16 * 1024 * 1024 * 1024 * 1024= 1.72 × 10 ¹³
  
• Exabyte: 16 * 1024 * 1024 * 1024 * 1024 * 1024= 1,72 × 10 ¹⁶

Anche se 1 exabyte pesava 1 grammo, non siamo in nessun posto vicino a raggiungere il 2,17 × 10 ^{124 necessario per poter adattarsi a tutti questi numeri in un disco rigido con la massa del sole}

Answer 1

Da uno dei miei libri preferiti di sempre, crittografia applicata di Bruce Schneier

.

"Se qualcuno ha creato un database di tutti i primi, non sarà In grado di utilizzare quel database per rompere gli algoritmi dei tasti pubblici? Sì, ma non può farlo.Se potessi archiviare un Gigabyte di informazioni su un disco che pesa un grammo, quindi una lista di solo le prime 512 bit peserebbero così tanto che supererebbe il limite del chandasekhar e il crollo in a buco nero ... quindi non puoi recuperare i dati comunque "

In altre parole, è impossibile o irrealizzabile o entrambi.

Answer 2

I primi utilizzati in RSA e diffie-hellman sono in genere nell'ordine di 2 ^{512 .In confronto, ci sono solo circa 2 256 atomi nell'universo noto.Ciò significa 2 512 è abbastanza grande da assegnare 2 256 numeri univoci ad ogni atomo nell'universo.}

Non c'è semplicemente alcun modo per memorizzare / calcolare tanti dati.

---

.

Da parte, presumo che tu intenda "un grande tavolo di primes" - i tavolini Rainbow sono specificamente adattati per hash, e non hanno alcun significato reale qui.

Answer 3

Penso che il problema principale sia che le tabelle arcobaleno pregenerate per alcuni algoritmi usano una gamma piuttosto "piccola" (di solito qualcosa nell'intervallo di 128 bit).Questo di solito non copre l'intera gamma, ma accelera il processo della forza bruta.Di solito consumano qualche TB di spazio.

In Prime FactorIzation, le prime sono molto più grandi (sono consigliati bit sicuri RSA, 2048 bit).Quindi i tavoli Rainbow non sarebbero "potenti grandi", ma impossibili da conservare ovunque (usando come milioni di TB di spazio).

Inoltre, i tavoli Rainbow utilizzano anche le catene ad hash ulteriori accelerano il processo ( wikipedia ha unBuona spiegazione) che non può essere utilizzata per le prime.