E se RSA fosse rotto?

Gli algoritmi attualmente popolari rientrano in tre categorie:

• Basato sul factoring (RSA, Rabin)
• Basato sul problema del logaritmo discreto in campi finiti (Diffie-Hellman, DSA, ...)
• Basato sul problema dei logaritmi discreti sulle curve ellittiche (EC-DH, ECDSA, ...)

Gli algoritmi di factoring attualmente migliori e il calcolo di logaritmi discreti in un campo finito sono abbastanza simili (setacci di campi numerici basati sul calcolo dell'indice), quindi è probabile che cadano insieme. Attualmente non esiste un modo noto per applicare questi algoritmi alle curve ellittiche più popolari.

Tutti condividono una debolezza comune: se otteniamo computer quantistici sufficientemente grandi in grado di eseguire l'algoritmo di Shor, si rompono tutti.

Esistono algoritmi che utilizzano diversi problemi matematici che si ritiene siano in grado di resistere ai computer quantistici. Il NIST sta attualmente organizzando un concorso per standardizzare tale algoritmo. Molti di questi sono dotati di aspetti negativi importanti, come dimensioni di chiavi / messaggi / firma o brevetti di grandi dimensioni.

• Basato su reticolo - NTRU è un vecchio e ben noto esempio, ma l'adozione è stata ostacolata dai brevetti
• Basato sul codice: McEliece è il più noto. La dimensione della chiave è grande.
• multivariata-quadratica-equazioni
• Firme hash - solo firma. Quelli semplici possono essere usati solo una volta. Quelli riutilizzabili sono complessi e producono grandi firme o richiedono al firmatario di tenere traccia di quanti messaggi hanno firmato.
• Scambio di chiavi isogeniche supersingolari

La maggior parte di questi algoritmi è ancora sperimentale, ma dovremmo ottenere alcune implementazioni standard utilizzabili man mano che la competizione NIST progredisce.

Sembra che ci siano persone là fuori che affermano di avere una soluzione al problema: link (anche se sono scettico ) Inoltre, se i numeri RSA non sono più sicuri, allora si può essere sicuri che la nuova matematica (e ci deve essere molto più di un altro algoritmo del tipo tradizionale) sotteso a quella possibile soluzione potrebbe anche indebolire altri crittosistemi come la CE, DSA ecc. Quindi sì, penso che sarebbe abbastanza uno shakedown.