Concetto di tavolo arcobaleno per numeri primi

È improbabile. I primi coinvolti sono enormi , quindi lo spazio delle chiavi è enorme. Quanto enorme dipende dalla dimensione della chiave, ma selezioniamo i primi 512 bit per un esempio con limite inferiore.

La funzione di conteggio dei primi ci fornisce una stima di quanti numeri primi sono al di sotto di un determinato numero. È difficile calcolare con precisione, ma una stima vicina è definita come π(x) = x / ln(x) , dove ln è il logaritmo naturale. Pertanto, possiamo calcolare una stima del numero previsto di numeri primi al di sotto del valore più alto in un valore n -bit calcolando π(2^n) . Se vogliamo escludere tutti i numeri che non sono esattamente n -bit, calcoliamo π(2^n) - π(2^(n-1)) . Questo non è tecnicamente richiesto , ma ci dà un bel limite inferiore di quanti numeri primi grandi ci sono per quella dimensione della chiave.

Per n = 512 il numero di numeri primi necessari per un elenco completo è 1.885 × 10 ¹⁵¹ . Se possiamo memorizzare ogni numero primo in una voce a 512 bit, questo è 1,207 × 10 ¹⁵³ byte , che è 132 ordini di grandezza più di quanto abbiamo capacità di archiviazione su disco nel mondo.

Quindi no, non è fattibile.

Tavola arcobaleno: ogni "colore" prende un input casuale (l'hash di output dell'ultima iterazione o l'hash originale) e restituisce un output che si associa a qualsiasi pattern desiderato (ad es. tutte le lettere). Viene quindi sottoposto a hash e ricondotto all'input.

Poiché possiamo anche specificare una funzione di riduzione che prende qualsiasi stringa casuale e la mappa in modo deterministico a qualsiasi modello di output che vogliamo, questo funziona per le password. Non esiste una funzione definibile per prendere un valore di input e produrre un numero che è noto per essere primo come risultato, tuttavia.

Ogni numero che non è noto come primo perché lo hai già testato dovrà essere sottoposto a test per la primitività. Pertanto, a meno che un numero non venga memorizzato come valore primo conosciuto, non vi è alcun compromesso di tempo / memoria.

Ciò di cui stai parlando qui non è fattibile. Crypto non calcola semplicemente i primi grandi, avresti bisogno di calcolare il prodotto di due numeri primi.

Quello che dovresti fare è calcolare milioni di numeri primi e dar loro da mangiare in un array incredibilmente grande. Quindi dovresti duplicare quell'array in modo da avere una matrice bidimensionale. Quindi sarà necessario moltiplicare ogni singola voce nella prima dimensione rispetto a ogni singola voce nella seconda dimensione e memorizzare i due numeri primi e il risultato in un secondo array. Questo secondo array sarebbe gigantesco, e per gigantesco intendo completamente incapace di essere immagazzinato in qualsiasi capacità, ma sarebbe in grado di contenere le tue risposte.

Certamente non è facile ma ... "dove c'è una volontà c'è un modo" SE volevi tutti i numeri primi dal numero 2 - > 512bit in una tabella quindi tutti i possibili prodotti allora sì questo sarebbe irrisolvibilmente grande. Ma torniamo indietro e speculiamo sul motivo per cui qualcuno potrebbe volerlo. Supponiamo che qualcuno abbia uno scenario in cui stessero usando un paio di numeri primi simili a lunghezza di bit per fare un grande numero che sarebbe difficile per gli altri fattori di un paio di numeri primi (sembra familiare ...?) Non tutte le combinazioni possibili di sarebbero necessari i numeri primi, in quanto verrebbero utilizzati solo bit-length simili. Questo drammatico riduce le dimensioni della tabella. Ad ogni modo essere pedante sarebbe una tabella Cubo di Rainbow in quanto ciò richiede più dimensioni. La capacità di determinare factr di questi numeri primi grandi è certamente difficile in quanto la dimensione dei cubi residenti in memoria (quando tenuta in RAM per un'analisi efficiente) è troppo grande per un PC economico, tuttavia ci sono certamente alcune grandi organizzazioni che detengono strutture multidimensionali giganti di questo tipo di proporzioni (come Google per le loro ricerche). Sembra altamente improbabile che non ci siano organizzazioni con risorse pesanti là fuori che già hanno calcolato e usano tali primi cubi. La difficoltà di factoring della coppia di numeri primi è la difficoltà del "titolo" per es. RSA, ma non sottovalutare la difficoltà addizionale prodotta dal passaggio per generare la chiave privata perché ha un calcolo modulare.

Come già detto sopra, non c'è spazio vicino allo spazio di archiviazione richiesto in tutto il mondo. Scommetto che prima ancora di arrivare a quella quantità di memoria, un computer quantistico che esegue l'algoritmo di Shor (o un algoritmo simile) avrebbe annullato la necessità.