Red Hot Cyber

Cybersecurity is about sharing. Recognize the risk, combat it, share your experiences, and encourage others to do better than you.
Search

Cryptography at Risk: MIT develops a Quantum Algorithm to crack RSA.

Tara Lie : 27 August 2024 13:11

Modern encryption methods, such as RSA, are based on the fact that even the most powerful classical computers are not able to quickly decompose a large number into prime factors. However, quantum computers promise to considerably accelerate this process, thanks to an algorithm proposed by Peter Shor in 1994, which demonstrated that a quantum computer could break RSA encryption.

Over the last 30 years, scientists have been actively developing quantum computers, but up until now they have not been able to create a powerful enough device to execute Shor’s algorithm. It requires a quantum computer with about 20 million qubits, while modern quantum computers have about 1100. 

Some researchers concentrate on the construction of powerful quantum computers, while others are searching to improve Shor’s algorithm in such a way that it can function on less powerful devices. A year ago, Oded Regev, a scientist from New York University proposed a theoretical improvement to the algorithm that would allow it to run faster but require more memory.

Vorresti toccare con mano la Cybersecurity e la tecnologia? Iscriviti GRATIS ai WorkShop Hands-On della RHC Conference 2025 (Giovedì 8 maggio 2025)

Se sei un ragazzo delle scuole medie, superiori o frequenti l'università, oppure banalmente un curioso di qualsiasi età, il giorno giovedì 8 maggio 2025 presso il teatro Italia di Roma (a due passi dalla stazione termini e dalla metro B di Piazza Bologna), si terranno i workshop "hands-on", creati per far avvicinare i ragazzi alla sicurezza informatica e alla tecnologia. Questo anno i workshop saranno:

  • Creare Un Sistema Ai Di Visual Object Tracking (Hands on)
  • Social Engineering 2.0: Alla Scoperta Delle Minacce DeepFake
  • Doxing Con Langflow: Stiamo Costruendo La Fine Della Privacy?
  • Come Hackerare Un Sito WordPress (Hands on)
  • Il Cyberbullismo Tra Virtuale E Reale
  • Come Entrare Nel Dark Web In Sicurezza (Hands on)

  • Potete iscrivervi gratuitamente all'evento, che è stato creato per poter ispirare i ragazzi verso la sicurezza informatica e la tecnologia.
    Per ulteriori informazioni, scrivi a [email protected] oppure su Whatsapp al 379 163 8765


    Supporta RHC attraverso:


    Ti piacciono gli articoli di Red Hot Cyber? Non aspettare oltre, iscriviti alla newsletter settimanale per non perdere nessun articolo.

    Based on this idea, researchers from MIT developed a new approach that combines the speed of Regev’s algorithm with the memory efficiency of Shor’s algorithm. The new algorithm is not only as fast as Regev’s, but requires even less qubits and is also noise resistant in quantum systems, rendering it more practical to implement.

    This new algorithm could play an important role in future when it will be necessary to develop new cryptography methods that are able to resist powerful quantum computers. If quantum computers become large enough, traditional encryption methods such as RSA will no longer be secure, and it will be necessary to use new cryptographic technologies.

    The research was presented at the International Cryptological Conference 2024. The MIT scientists even proposed a new method to calculate exponents on a quantum computer by using Fibonacci numbers, allowing operations to be performed using only two quantum memory registers. This makes the calculator process more efficient and reduces the required amount of memory.

    Additionally, they also proposed a method for error correction that allows for the incorrect results to be filtered out and only use the correct ones, which makes the algorithm more suitable for practical implementation.

    In future, the researchers hope to make the algorithm even more efficient and to test it on a real quantum computer. However, the question remains of whether this result brings us closer to the breaking of RSA encryption, since current improvements only become useful when factoring numbers significantly larger than 2048 qubits.

    Therefore, this development from MIT represents a significant step towards the creation of practical quantum algorithms that could have a significant impact on future data security.

    Tara Lie
    Cyber Security manager from Perth, Western Australia, focused on governance, risk quantification and compliance. Graduate of cyber security and pure mathematics, with a second-major in Italian Studies. Tara has earned a Master's degree in Cyber Security, and is pursuing her PhD researching cyber security in the post-quantum era.