Se si combinassero tutti i microprocessori sulla terra in un enorme cluster computazionale, in che misura le chiavi RSA di grandi dimensioni potrebbero essere calcolate in un tempo ragionevole (diciamo alcuni anni)?
So leggendo le risposte a questo domanda che il prossimo obiettivo della vita reale è 1024 bit, ma qui sono più interessante nelle risposte puramente teoriche.
Il record corrente per l'interruzione di RSA è 768 bit. L'unico algoritmo noto che è sufficientemente efficiente per queste dimensioni chiave da prevedere è il Setaccio campo numerico generale . Questo algoritmo consiste in due parti grandi, il sieving e poi un po 'di algebra lineare pesante.
Quando GNFS è stato utilizzato per la prima volta per decifrare una chiave RSA a 512 bit, il setaccio è stato il collo di bottiglia; richiede molte macchine con quantità di RAM che non erano banali in quel momento. Tuttavia, per chiavi più grandi, è l'algebra lineare che diventa il collo di bottiglia, perché non è facile parallelizzare e richiede un computer molto grande con molto ( molto ) di veloce ( molto veloce ) RAM.
Con tutti i computer sulla Terra, è possibile eseguire il setacciamento per uno sforzo di fattorizzazione a 1024 bit; bastano poche migliaia di computer con poche dozzine di gigabyte di RAM ciascuno. Tuttavia, per l'algebra lineare corrispondente, tutti questi computer non equivalgono a nulla. Invece, devi costruire un nuovo computer per scopi speciali con una nuova architettura.
Ad esempio, considera i maggiori supercomputer esistenti . Sono tutti accumuli di molti microprocessori - sono supercomputer orientati alla CPU, molto bravi nel gestire numeri su compiti che possono essere resi sufficientemente paralleli (molti calcoli per unità di trasferimento dati). Per la seconda metà di GNFS, è necessario un supercomputer orientato alla RAM, migliore dei trasferimenti di dati tra CPU rispetto ai calcoli effettivi. L'architettura teorica per un tale computer è stata studiata e abbiamo alcune buone ragioni per credere che sia tecnologicamente fattibile, ma sarebbe comunque uno sforzo molto sostanziale, che inizia proprio alla fase della fonderia dei chip.
Riepilogo: anche con una botnet che controlla tutti i computer di Earth, non crei una chiave RSA a 1024 bit. Con tutti i soldi di Apple, potresti probabilmente costruire una macchina per scopi speciali in grado di decifrare una chiave RSA a 1024 bit (ma buona fortuna nel farlo discretamente : non puoi spendere miliardi di dollari senza presentarti, almeno, sulle statistiche economiche). Per chiavi più grandi (ad esempio 1536 bit o più): non pensarci nemmeno.
Leggi altre domande sui tag distributed-computing brute-force rsa asymmetric