Trovare i fattori primi a grandi numeri utilizzando CPU appositamente predisposte

Question

La mia comprensione è che molti algoritmi crittografici a chiave pubblica oggigiorno dipendono da numeri primi grandi per creare le chiavi, ed è la difficoltà nel factoring del prodotto di due numeri primi che rende la crittografia è difficile da rompere. Mi rendo anche conto che uno dei motivi per cui il factoring di numeri così grandi è così difficile è che la dimensione dei numeri utilizzati significa che nessuna CPU può operare efficientemente sui numeri, dal momento che le nostre minuscole CPU a 32 e 64 bit non corrispondono per numeri 1024, 2048 o anche 4096 bit. Per elaborare questi numeri, è necessario utilizzare librerie matematiche Big Integer specializzate e tali librerie sono intrinsecamente lente poiché una CPU può contenere (e elaborare) piccoli blocchi (come 32 o 64 bit) contemporaneamente.

Quindi ...

Perché non si può costruire un chip custom altamente specializzato con 2048 registri bit, e circuiti aritmetici giganti, molto nello stesso modo in cui abbiamo scalato da 8 a 16 a 32 a 64 CPU bit, è sufficiente crearne uno più grande? Questo chip non avrebbe bisogno della maggior parte dei circuiti sulle CPU convenzionali, dopotutto non avrebbe bisogno di gestire cose come memoria virtuale, multithreading o I/O. Non avrebbe nemmeno bisogno di essere un processore generico che supporti le istruzioni memorizzate. Solo il minimo indispensabile per eseguire i calcoli aritmetici necessari su numeri ginormous.

Non so molto sul design IC, ma mi ricordo di aver imparato come funzionano le porte logiche, come costruire un mezzo addizionatore, un full adder, quindi collegare insieme un gruppo di adders per fare aritmetica multi-bit . Basta scalare. Un sacco.

Ora, sono abbastanza certo che ci sia un buon motivo (o 17) che quanto sopra non funzionerà (poiché altrimenti una delle tante persone più intelligenti di me lo avrebbe già fatto) ma io sono interessato a conoscere perché non funzionerà.

(Nota: Questa domanda potrebbe essere necessaria una rielaborazione, come io non sono nemmeno ancora sicuro se la domanda ha un senso)

Answer 1

Ciò che dice @cube e il fatto che una gigantesca unità logica aritmetica richiederebbe più tempo per stabilizzare i segnali logici e includere altre complicazioni nella progettazione digitale. La progettazione della logica digitale include qualcosa che si dà per scontato nel software, vale a dire che i segnali attraverso la logica combinatoria prendono un tempo piccolo ma non zero per propagarsi e stabilizzarsi. Un moltiplicatore 32x32 deve essere progettato con attenzione. Un moltiplicatore 1024x1024 non solo richiederebbe un'enorme quantità di risorse fisiche in un chip, ma sarebbe anche più lento di un moltiplicatore 32x32 (sebbene forse più veloce di un moltiplicatore 32x32 calcolando tutti i prodotti parziali necessari per eseguire una moltiplicazione 1024x1024). Inoltre non è solo il moltiplicatore a causare il collo di bottiglia: hai percorsi di memoria.Dovresti dedicare un po 'di tempo a raccogliere i 1024 bit da un circuito di memoria largo solo 32 bit e ad archiviare i 2048 bit risultanti nel circuito di memoria.

Quasi certamente è meglio avere un gruppo di sistemi "convenzionali" a 32 o 64 bit che lavorano in parallelo: si ottiene la velocità senza la complessità del progetto hardware.

modificare: se qualcuno ha accesso ACM (io non), forse dare un'occhiata a this paper per vedere cosa dice.

Answer 2

suo perché questo aumento di velocità sarebbe solo in O (n), ma la complessità di factoring il numero è qualcosa come O (2^n) (rispetto al numero di bit). Quindi, se rendi questo überprocessor e riduci i numeri 1000 volte più velocemente, dovrei solo rendere i numeri più grandi di 10 bit e torneremo di nuovo all'inizio.

Answer 3

Come indicato sopra, il problema principale è semplicemente quante possibilità si devono passare per calcolare un numero. Detto questo, esistono computer specializzati per fare questo genere di cose.

Il vero progresso per questa sorta di crittografia è il miglioramento degli algoritmi di factoring dei numeri. Attualmente, l'algoritmo generale più noto è lo general number field sieve.

Storicamente, sembra che siamo in grado di calcolare numeri due volte più grandi ogni decennio. Parte di questo è un hardware più veloce, e parte di esso è semplicemente una migliore comprensione della matematica e di come eseguire il factoring.

Answer 4

Non posso commentare la possibilità di un approccio esattamente come quella che hai descritto, ma la gente fare simili cose molto spesso utilizzando FPGA:

• Crack DES keys
• Crack GSM conversations
• Open source graphics card

Answer 5

Perché don ' t provi a costruire un computer di tipo quantico ed esegui Shor's algorithm su di esso?

" ... Se un computer quantistico con un numero sufficiente di qubit dovesse essere costruito, l'algoritmo di Shor potrebbe essere utilizzato per rompere schemi di crittografia a chiave pubblica come il sistema RSA ampiamente utilizzato. RSA si basa presupponendo che il factoring di grandi numeri sia computazionalmente non fattibile, per quanto è noto questa ipotesi è valida per i computer classici (non quantici), non è noto alcun algoritmo classico che possa tenere conto del tempo polinomiale, tuttavia l'algoritmo di Shor mostra che il factoring è efficiente su un computer quantistico, quindi un computer quantistico sufficientemente grande può rompere RSA ... "-Wikipedia

Answer 6

Shamir & Tromer suggeriscono un approccio simile, utilizzando una sorta di grid computing:

questo articolo viene illustrato un nuovo design per un'implementazione hardware personalizzato della fase di vagliatura, che riduce [il costo di setacciatura, relativa a TWINKLE,] a circa $ 10 milioni. Il nuovo dispositivo, chiamato TWIRL, può essere visto come un'estensione del dispositivo TWINKLE . Tuttavia, a differenza di TWINKLE, lo non dispone di componenti optoelettronici e pertanto è possibile produrre utilizzando la tecnologia VLSI standard su wafer di silicio. L'idea alla base è quella di utilizzare una singola copia dell'input per risolvere molti sottoproblemi in parallelo. Poiché lo storage di input domina i costi, se il sovraccarico di parallelizzazione dello viene mantenuto basso, l'aumento di velocità dello viene ottenuto essenzialmente gratuitamente. In effetti, la sfida principale di consiste nel realizzare questo parallelismo in modo efficiente pur consentendo una memorizzazione compatta dell'input. Affrontare questo comporta una miriade di considerazioni, che vanno da dalla teoria dei numeri alla tecnologia VLSI.