Supponiamo che io stia usando RSA per il mio sistema di sicurezza. Ora qualcuno scopre di trovare un algoritmo del tempo polinomiale per RSA. Quindi quale misura dovrebbe essere tale che RSA non mai si rompa . Forse un gran numero di bit usati o qualcos'altro.
Se è provato che P = NP allora questo significa che un algoritmo del tempo polinomiale per la rottura di RSA esiste . Trovare quell'algoritmo potrebbe essere impegnativo, però. D'altra parte, P potrebbe essere distinto da NP e tuttavia il factoring potrebbe accettare un algoritmo tempo-polinomiale. La fattorizzazione di interi non è un problema NP-completo .
Inoltre, il "polinomio" è un comportamento asintotico, che descrive come si comporta il tempo di esecuzione di un algoritmo su input sufficientemente grandi . Nulla dice che le dimensioni delle chiavi RSA comuni siano "sufficientemente grandi" perché il comportamento asintotico sia una stima ragionevolmente accurata delle prestazioni su queste dimensioni chiave. Infine, "polinomio" non significa necessariamente "veloce"; un algoritmo con costo O (n 12 ) (per un modulo RSA di n bit) sarebbe costato 2 120 per una chiave RSA a 1024 bit, ovvero totalmente irraggiungibile nella pratica.
Questo è il problema con il ragionamento su scenari ipotetici mal definiti: tutto può succedere, davvero. Quindi la domanda non può essere risolta, se non per sentimenti istintivi. Il mio budello mi dice che se viene trovato un algoritmo di fattorizzazione polinomiale, allora sarà probabilmente abbastanza costoso per dimensioni "normali" di interi e usare una matematica sufficientemente avanzata che avremo alcuni mesi o anni prima compaiono implementazioni pratiche che dovrebbero dare il tempo necessario per passare a qualcos'altro (ad es. curve ellittiche). Ma, naturalmente, le mie viscere sono solo organi digestivi, bravi a scomporre il cibo in nutrimenti; cosa sanno veramente della crittografia?
Leggi altre domande sui tag cryptography encryption