Con quale velocità un chip dedicato può eseguire le operazioni di modulo di squadratura sequenziale per interrompere una capsula crittografica temporizzata?

Non ho una risposta definitiva perché ci vorrebbe un po 'di analisi. Dipende anche dalla CPU, da quanti bit ecc. Ma per un numero di ballpark.

Sono stati creati FPGA che eseguiranno un'operazione di divisione in 1 ciclo di clock. Una CPU / ALU per uso generico può richiedere da 20 a 100 cicli di clock. I processori DSP impiegheranno probabilmente meno cicli di clock. Quindi possiamo dire che un FPGA è 100 volte più veloce.

Questa è solo l'operazione di divisione (che ti dà anche il modulo).

Dovresti comunque tenere conto dei trasferimenti di memoria. Un FPGA dedicato dovrebbe fare questo? Una CPU di uso generale avrebbe sicuramente bisogno di farlo. Questo rende l'FPGA ancora più veloce se potesse eliminare la maggior parte dei suoi trasferimenti di memoria. A questo punto il miglioramento 1000x sembra realistico.

Tuttavia, non ho letto l'algoritmo, ma suppongo che ci siano alcuni aggiornamenti / ricerche sulla tabella, questo probabilmente richiederebbe trasferimenti di memoria da / verso l'FPGA, il che rallenta l'elaborazione dell'FPGA per essere più equivalente all'elaborazione della CPU . Anche se l'FPGA ha dedicato memoria extra veloce, ciò causerebbe comunque un calo di circa 1000 volte.

Comunque, la mia stima sarebbe un miglioramento della velocità 100x-1000x con un FPGA nelle migliori circostanze.

UPDATE

Mi sono imbattuto in questo articolo link (un po 'datato 2008) ma probabilmente ancora applicabile. Si chiama "Where's the Beef? Perché gli FPGA sono così veloci" Hanno fatto diversi confronti temporali tra cui la crittografia AES a 128 bit. Per la crittografia AES sono stati in grado di ottenere un aumento di 4000 volte dall'implementazione del software semplicistico a un FPGA altamente ottimizzato. Sebbene, penso che ci siano state anche ottimizzazioni del software che potrebbero essere ridotte a un numero di 4000 volte.

Non so se l'hardware avanzato FPGA / Custom sia migliorato notevolmente rispetto alle moderne CPU di oggi, quindi non so quanto siano applicabili queste informazioni . Tuttavia, ritengo che il 100x a 1000x sia una buona stima in quanto suppongo che il software sarebbe ottimizzato.

CPU:

Il problema dipende davvero dalla velocità della CPU. Abbiamo già discostato dalla gamma di ballpark presentata nell'articolo, poiché nel 2012 non avevamo CPU a 10GHz disponibili in commercio. In questo caso, sarebbe piuttosto difficile perché abbiamo a che fare con diversi fattori:

• Velocità della CPU
• Dimensione cache L1 e L2
• Velocità del bus
• Ottimizzazione dell'algoritmo
• Architettura della CPU disponibile
• Velocità di memoria
• Manca la cache

Quindi seguirò "l'algoritmo dei 35 anni" in base alla previsione originale.

GPU:

Una GPU non aiuterà in questo caso. Questi dispositivi sono tutti sulla paraellelizzazione e non aiuteranno questo tipo di algoritmo.

FPGA / ASIC:

In questo scenario, è completamente possibile progettare un FPGA / ASIC che farebbe un'intera operazione in un tick. Dal momento che non ci interessa il risultato effettivo della divisione e ci interessa solo il risultato N, potremmo teoricamente renderlo abbastanza veloce. Tuttavia è estremamente difficile stimare la velocità esatta che potremmo ottenere. Questo si baserebbe su molti fattori:

• L'algoritmo che usiamo.
• La dimensione / velocità dei componenti.
• I componenti hardware effettivi utilizzati.
• La qualità dei componenti utilizzati.
• Il processo di compilazione utilizzato.

Se potessimo stimare che il nostro FPGA / ASIC funzionerebbe a 1 MHz, che completerebbe il problema in ~ 2,53 anni.

D'altra parte, se potessimo in qualche modo sviluppare e FPGA / ASIC che funzionerebbero a 1 GHz, allora completeremmo il problema in ~ 22 ore.