Mathematical theory used to crack the US government encryption algorithm

Credit: CC0 Public domain

In the digital age and the shift to quantum computing, protecting data from hacking attacks is one of our biggest challenges, one that experts, governments and industries around the world work hard to address. 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 problems to test their security, offering a $50,000 reward to anyone who managed to crack them. It happened in less than an hour: one of the promising candidate algorithms, called SIKE, was hacked with a single personal computer. The attack was not based on a powerful machine, but on powerful mathematics based on a theory developed by a Queen’s professor decades ago.

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

The problems Dr. Kani works to fix the trait that dates back to ancient times. Her specific field of inquiry was introduced by Diophantus of Alexandria about 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 by Princeton professor Andrew Wiles in 1994. Wiles has received many awards and honors for this work, including an honorary doctorate from Queen’s in 1997.

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

In fact, Dr. Kani wasn’t concerned with cryptographic algorithms when he developed the theorem. That work began in the 1980s, in collaboration with another German mathematician, Gerhard Frey, whose work was crucial in solving Fermat’s Last Theorem. dr. Kani and Frey wanted to further research into elliptic curves, a particular type of equation that would later be used for cryptographic purposes.

The goals of both researchers at that time were purely theoretical. They were interested in manipulating mathematical objects to learn more about their properties. “Doing pure math is an end in itself, so we don’t think about real-world applications,” said Dr. Kani explains. “But, later, many of those studies will be useful for different purposes. When Fermat proposed his theorem hundreds of years ago, his intent was to be able to factor certain large numbers. Application to cryptography came only very far later, in 1978. Basically, all the methods we use today for encrypting data are based on mathematics.”

Donuts and curves

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

Imagine an object shaped like a doughnut, with a hole in the middle – it’s a visual model of an elliptic curve, also known as a curve of gender one. dr. Kani and Frey wanted to combine two curves of gender one to form a new object: a curve of gender two, something we can imagine as two donuts stuck solidly next to each other. They aimed to use some properties of the constructed gender two curve to infer some properties of the two original gender one curves, which were “glued” together.

In his 1997 article, Dr. Kani generalized the original construction by gluing together an arbitrary pair of elliptic curves. But in that case the construction sometimes fails: it could construct an object where the two donuts only touch at one point. The paper analyzes the precise conditions for when this happens (i.e. when construction fails or “cracks”). 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 encryption, which is why I was surprised when I learned about the algorithm hack. It was pretty ingenious, what they did there!” says Dr. Can I. “One of the co-authors of the SIKE algorithm expressed surprise that gender two curves could be used to obtain information about elliptic curves. But this was precisely our original strategy in the 1980s and 1990s (and later).”

While cryptographers and computer engineers aren’t always proficient in all the powerful techniques of mathematics, many different skills and forms of knowledge can be combined to improve the way we store and transmit data.

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

More information:
Original article: The Number of Curves of Genus Two with Elliptic Differentials

Provided by Queen’s University

Citation: Mathematical Theorem Used to Crack US Government Encryption Algorithm (2022, Nov 23) Retrieved Nov 23, 2022 from html

This document is subject to copyright. Except in all propriety for the purpose of private study or research, no part may be reproduced without written permission. The content is provided for informational purposes only.

Leave a Comment

%d bloggers like this: