Come fa l'algoritmo di Shor a rompere RSA ed ECC?

Trasforma in facili i problemi difficili su cui si basano. RSA è sicuro perché nessuno riesce a scomporre un numero molto grande nei suoi due fattori primi in tempi ragionevoli; la crittografia a curve ellittiche è sicura perché nessuno riesce a ricavare il numero segreto dietro un punto pubblico della curva. Peter Shor dimostrò nel 1994 che un computer quantistico può trovare in entrambi i problemi uno schema ripetuto nascosto, un periodo, da cui il segreto si ricava rapidamente. Su una macchina abbastanza grande l'attacco richiede un tempo praticabile invece che impossibile. Chiavi più lunghe non salvano RSA né ECC: rendono l'attacco quantistico solo un po' più lento. Per questo la risposta è nuova matematica, come i problemi sui reticoli alla base di ML-KEM e ML-DSA, per i quali non si conosce alcun algoritmo quantistico efficiente. Le stime pubblicate della macchina necessaria sono ancora molto lontane da tutto ciò che è stato costruito.

← Tutte le 33 domande su Crittografia post-quantisticaTutti i temi