Mathematical theorem used to crack US government encryption algorithm

In the digital age and the move towards quantum computing, protecting data from hacking attacks is one of our biggest challenges, and one that experts, governments and industries around the world whole are trying to answer. While this is an effort to build a more connected and secure future, it can certainly learn from the past.

In July, the US National Institute of Standards and Technology (NIST) selected four encryption algorithms and posed challenge problems to test their security, offering a $50,000 reward to anyone who could crack them. It happened in less than an hour: one of the algorithm’s promising candidates, named SIKE, was hacked with a single personal computer. The attack didn’t rely on a powerful machine, but on powerful mathematics based on a theorem developed by a Queen’s professor decades ago.

Ernst Kani has been researching and teaching since the late 1970s, first at the University of Heidelberg, Germany, then at Queen’s, where he joined the Department of Mathematics and Statistics in 1986. His main area of research is arithmetic geometry, an area of ​​mathematics that uses the techniques of algebraic geometry to solve number theory problems.

The problems that Dr. Kani tries to solve date back to ancient times. His specific area of ​​research was started by Diophantus of Alexandria around 1,800 years ago and is a set of problems known as Diophantine questions. One of the most famous questions in the field is Fermat’s Last Theorem, posed by Pierre Fermat in 1637 and which took the mathematical community 350 years to prove – an achievement of Princeton professor Andrew Wiles in 1994. Wiles has received numerous awards and honors for this work. , including an honorary doctorate from Queen’s in 1997.

Neither Diophantus nor Fermat dreamed of quantum computers, but Dr. Kani’s work on Diophantine questions resurfaced during the NIST test series. The successful hackers – Wouter Castryck and Thomas Decru, both researchers at the Katholieke Universiteit Leuven, Belgium – based their work on the “glue and divide” theorem developed by the Queen’s mathematician in 1997.

In fact, Dr. Kani was not concerned with cryptographic algorithms when he developed the theorem. This work began in the 1980s, in collaboration with another German mathematician, Gerhard Frey, whose work was crucial in solving Fermat’s last theorem. Drs. Kani and Frey wanted to advance research on elliptic curves, a special type of equation that would later be used for cryptographic purposes.

The objectives of the two researchers at that time were purely theoretical. They wanted to manipulate mathematical objects to learn more about their own properties. “Doing pure math is an end in itself, so we don’t think about real-world applications,” says Dr Kani. “But, later, many of these studies are useful for different purposes. When Fermat proposed his theorem hundreds of years ago, his intention was to be able to factorize certain large numbers. The application to cryptography n came much later in 1978. Basically, all the methods we use today for data encryption are based on mathematics.”

Donuts and curves

Mathematicians often refer to mathematics as a beautiful thing. For those not working in the field, it can be difficult to see this beauty, or even to have a high-level understanding of what these research projects are – it takes a bit of imagination.

Imagine a doughnut-shaped object, with a hole in the middle: it’s a visual model of an elliptical curve, also known as a genus one curve. Drs. Kani and Frey wanted to combine two genus-one curves to form a new object – a genus-two curve, something we can imagine as two donuts glued tightly side by side. They aimed to use some properties of the constructed genus two curve to infer some properties of the original two genus one curves, which were “glued” together.

In his 1997 paper, Dr. Kani generalized the original construction by gluing together an arbitrary pair of elliptical curves. But in this case, the construction sometimes fails – it can build an object in which the two donuts only touch at one point. The article analyzes the precise conditions of when this occurs (ie, when the construction fails or “splits”). Castryck and Decru used this characterization of failure in their method of attacking the proposed SIKE encryption scheme.

“Our problem had nothing to do with cryptography, that’s why I was surprised when I heard about the algorithm attack. It was pretty ingenious, what they did there !” says Dr. Kani. “One of the co-authors of the SIKE algorithm expressed surprise that genus two curves could be used to get information about elliptical curves. But that was precisely our original strategy in the 1980s and 1990 (and after).”

Although cryptographers and computer engineers may not always know all the advanced techniques of mathematics, many different skills and forms of knowledge can be combined to advance the way we store and transmit data.

“Cryptography uses a lot of sophisticated math, especially arithmetic geometry. Computer experts and math experts need to work together to advance this field,” says Dr. Kani, who continues to teach undergraduate courses and graduate studies and to work in arithmetic geometry, in particular on problems involving curves of genus two and elliptic curves.