Individuazione di fattori primi per numeri di grandi dimensioni utilizzando CPU appositamente predisposte

Question

La mia comprensione è che molti algoritmi crittografici a chiave pubblica oggigiorno dipendono da grandi numeri primi per comporre le chiavi, ed è la difficoltà nel factoring del prodotto di due numeri primi che rende difficile la crittografia. Comprendo anche che uno dei motivi per cui il factoring di numeri così grandi è così difficile, è che la mera dimensione dei numeri utilizzati significa che nessuna CPU può operare in modo efficiente sui numeri, poiché le nostre minuscole CPU a 32 e 64 bit non corrispondono per numeri 1024, 2048 o addirittura 4096 bit. Le librerie matematiche specializzate di Big Integer devono essere utilizzate per elaborare quei numeri e tali librerie sono intrinsecamente lente poiché una CPU può contenere (ed elaborare) solo piccoli blocchi (come 32 o 64 bit) alla volta.

...

Perché non riesci a costruire un chip personalizzato altamente specializzato con registri a 2048 bit e circuiti aritmetici giganti, più o meno allo stesso modo in cui abbiamo scalato da CPU da 8 a 16 a 32 a 64 bit, costruendone solo uno MOLTO più grande ? Questo chip non avrebbe bisogno della maggior parte dei circuiti sulle CPU convenzionali, dopo tutto non avrebbe bisogno di gestire cose come la memoria virtuale, il multithreading o l'I / O. Non dovrebbe nemmeno essere un processore generico che supporti le istruzioni memorizzate. Solo il minimo indispensabile per eseguire i calcoli aritmetici necessari su numeri enormi.

Non so molto sulla progettazione di circuiti integrati, ma ricordo di aver appreso come funzionano le porte logiche, come costruire un mezzo sommatore, un sommatore completo, quindi collegare insieme un sacco di additivi per fare l'aritmetica multi-bit. Basta ridimensionare. Molto.

Ora, sono abbastanza certo che ci sia una buona ragione (o 17) per cui quanto sopra non funzionerà (poiché altrimenti una delle molte persone più intelligenti di me l'avrebbe già fatto) ma sono interessato nel sapere perché non funzionerà.

(Nota: potrebbe essere necessario rielaborare questa domanda, poiché non sono ancora sicuro se la domanda abbia senso)

Answer 1

Cosa ha detto @cube e il fatto che un'unità logica aritmetica gigante impiegherebbe più tempo a stabilizzare i segnali logici e includere altre complicazioni nella progettazione digitale. La progettazione della logica digitale include qualcosa che dai per scontato nel software, vale a dire che i segnali attraverso la logica combinatoria impiegano un tempo piccolo ma diverso da zero per propagarsi e stabilizzarsi. Un moltiplicatore 32x32 deve essere progettato con cura. Un moltiplicatore 1024x1024 non solo richiederebbe un'enorme quantità di risorse fisiche in un chip, ma sarebbe anche più lento di un moltiplicatore 32x32 (anche se forse più veloce di un moltiplicatore 32x32 che calcola tutti i prodotti parziali necessari per eseguire un moltiplicatore 1024x1024). Inoltre non è solo il moltiplicatore che è il collo di bottiglia: hai percorsi di memoria. Dovresti impiegare un sacco di tempo a raccogliere i 1024 bit da un circuito di memoria largo solo 32 bit e a memorizzare i 2048 bit risultanti nel circuito di memoria.

Quasi certamente è meglio ottenere un sacco di "convenzionali" Sistemi a 32 o 64 bit che lavorano in parallelo: ottieni la velocità senza la complessità di progettazione hardware.

modifica: se qualcuno ha accesso ACM (io no), forse dai un'occhiata a questo documento per vedere cosa dice.

Answer 2

È perché questo speedup sarebbe solo in O (n), ma la complessità del factoring del numero è qualcosa come O (2 ^ n) (rispetto al numero di bit). Quindi, se hai creato questo überprocessor e fattorizzato i numeri 1000 volte più velocemente, dovrei solo aumentare i numeri di 10 bit in più e torneremmo di nuovo all'inizio.

Answer 3

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

Il vero progresso per questo tipo di crittografia sono i miglioramenti negli algoritmi di factoring numerico. Attualmente, l'algoritmo generale più veloce è il setaccio campo numero generale .

Storicamente, sembriamo essere in grado di fattorizzare i numeri due volte più grande 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 fattibilità di un approccio esattamente come quello che hai descritto, ma le persone fanno simili molto frequentemente usando FPGA:

• Crack DES keys
• Crack GSM conversations
• Scheda grafica open source

Answer 5

Shamir & amp; Tromer suggerisce un approccio simile, usando una sorta di grid computing :

  

In questo articolo viene descritto un nuovo design per un hardware personalizzato   attuazione della fase di setacciatura, che   riduce [il costo della setacciatura, rispetto a TWINKLE,] a circa $ 10 milioni. Il nuovo dispositivo,   chiamato TWIRL, può essere visto come un'estensione di   Dispositivo TWINKLE. Tuttavia, a differenza di TWINKLE esso   non ha componenti optoelettronici e può   quindi essere prodotto utilizzando la tecnologia VLSI standard   su wafer di silicio. L'idea alla base è di usare   una singola copia dell'input per risolvere molti sottoproblemi   in parallelo. Poiché lo storage di input domina i costi, se il   il sovraccarico di parallelizzazione viene mantenuto basso quindi il risultato   lo speedup si ottiene essenzialmente gratuitamente. In effetti, il   la sfida principale sta nel raggiungere questo parallelismo in modo efficiente consentendo allo stesso tempo una memorizzazione compatta dell'ingresso.   Affrontare questo comporta una miriade di considerazioni, che vanno   dalla teoria dei numeri alla tecnologia VLSI.

Answer 6

Perché non provi a costruire un computer super quantico ed esegui Algoritmo di Shor su di esso?

  

" ... Se dovesse essere costruito un computer quantistico con un numero sufficiente di qubit, l'algoritmo di Shor potrebbe essere usato per rompere schemi di crittografia a chiave pubblica come lo schema RSA ampiamente usato. L'RSA si basa sul presupposto che il factoring di grandi numeri è impossibile dal punto di vista computazionale. Per quanto è noto, questo presupposto è valido per i computer classici (non quantistici); non è noto alcun algoritmo classico in grado di tenere conto del tempo polinomiale. Tuttavia, l'algoritmo di Shor mostra che il factoring è efficiente su un computer quantistico, quindi un computer quantico sufficientemente grande può rompere RSA. ... " -Wikipedia