Quantum encryption algorithm cracked in minutes by computer running Magma
A cryptosystem that was meant to withstand decryption by powerful quantum computers that may be developed in the future has been cracked by a single computer running a Magma program. Magma is a large software system for computing with abstract mathematical objects that has been developed by University of Sydney mathematicians together with mathematicians from other countries.
Quantum-resistant cryptography aims to develop encryption systems that are secure against both classical computers and quantum computers that may come into use in the future. The cryptosystem in question is SIKE (Supersingular Isogeny Key Encapsulation), whose resistance to being broken is being tested by the United States Department of Commerce’s National Institute of Standards and Technology (NIST).
SIKE was developed by researchers at a number of universities and the corporations Amazon, Infosec Global, Texas Instruments and Microsoft, who set a USD 50,000 bounty for anyone who could crack it. In July 2022, SIKE was chosen from a large number of candidates as one of four contenders for key exchange that would withstand attack by post-quantum computers.
A common method of encrypting data at present is to use the RSA public-key cryptosystem that relies for its security on the difficulty of factoring large integers. However, this type of cryptosystem can be easily solved using quantum computers. In contrast, SIKE is an isogeny-based system known as the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol.
SIKE is based on a pair of elliptic curves defined over a finite field together with certain mappings, known as isogenies, between the two curves. SIKE’s security relies on the difficulty of finding a specific isogeny between the two elliptic curves, or equivalently, of finding a path between them in the isogeny graph. This problem was believed to be hard to solve using either classical or quantum computers.
New research by Wouter Castryck and Thomas Decru in Belgium produced an algorithm that can quickly solve SIDH, the hard problem that underpins SIKE. An implementation of the algorithm in Magma by Castryck and Decru was able to crack hard challenge test examples using a single computer in a matter of minutes.
Magma is a large computational algebra system first released in 1991. The general design of Magma was developed by Professor John Cannon FAA of the University’s School of Mathematics and Statistics. It has been implemented and is actively developed by a small group of researchers at Sydney with contributions from more than 500 mathematicians located in other countries.
It can solve a multitude of computationally hard problems in different fields of mathematics, including algebra, number theory, geometry and combinatorics, and is often the best software available for such problems. In particular, Magma has extensive machinery for working with elliptic curves over finite fields, which makes it highly applicable to problems in cryptography.
Read more coverage of the news on ARS Technica, Hacker News and Tech Monitor.
- Interview with Jessica Fintzen - 2024 March 25
- “Geometry: the archetype of beauty” public lecture and photo gallery - 2024 March 15
- IMU-SMRI Mathematical Colloquia and Panels: 25–26 March 2024 at the University of Sydney - 2024 March 13