HomeSciencePhysicsMathematical theorem used to crack US government encryption algorithm

Mathematical theorem used to crack US government encryption algorithm

Credit: CC0 Public Domain

In the digital age and moving towards quantum computing, protecting data from hacking attacks is one of our greatest challenges, and one that experts, governments and industries around the world are working hard on. 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 ran a series of challenge problems to test their security, offering a $50,000 reward to whoever succeeded in cracking them. It happened in less than an hour: One of the promising algorithm candidates, called SIKE, was hacked with a single personal computer. The attack was not based on a powerful machine, but on powerful math based on a theorem developed decades ago by a Queen’s professor.

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

The problems that Dr. Kani tries to solve, going back to ancient times. His particular area of ​​inquiry was developed by Diophantus of Alexandria about 1800 years ago and is a series of problems known as Diophantine questions. One of the most famous questions in the field is Fermat’s Last Theorem, formulated by Pierre Fermat in 1637 and which took the math community 350 years to prove – an achievement by Princeton professor Andrew Wiles in 1994. Wiles received many 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 issues resurfaced during the NIST round of testing. The successful hackers – Wouter Castryck and Thomas Decru, both researchers at the Catholic University of Leuven, in Belgium – based their work on the “glue and split” theorem developed by the Queen’s mathematician in 1997.

In fact, Dr. Kani was not concerned about 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. drs. Kani and Frey wanted to advance research into elliptic curves, a type of equation that would later be used for cryptographic purposes.

The goals of both researchers at the time were purely theoretical. They were interested in manipulation mathematical objects to learn more about their own properties. “Doing pure math is an end in itself, so we’re not thinking about real-world applications,” explains Dr. Kani out. “But later on, many of those studies are useful for various purposes. When Fermat proposed his theorem hundreds of years ago, his intention was to be able to decompose certain large numbers. The application to cryptography did not come until much later, in 1978. In fact, all methods we use today for data encryption are based on mathematics.”

Donuts and curves

Mathematicians often call mathematics a beautiful thing. For those not working in the field, it can be challenging to see this beauty, or even to have an understanding of what these research projects are all about – it takes some imagination.

Imagine an object in the shape of a donut with a hole in the middle: this is a visual model of an elliptical exerciser curve, also known as a genus one curve. drs. 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 glued tightly together. They tried to use some properties of the constructed genus 2 curve to derive certain properties of the two original genus 1 curves, which were “glued” together.

In his 1997 paper, Dr. Kani the original construction by gluing together any pair of elliptic curves. But in that case the construction sometimes fails – it can construct an object in which the two donuts only touch at one point. The article analyzes the precise circumstances under which this occurs (i.e. when the structure fails or “splits”). Castryck and Decru used this characterization of the flaw in their method to attack the proposed SIKE encryption scheme.

“Our problem had nothing to do with cryptography, which is why I was surprised when I heard about the algorithm attack. It was quite ingenious what they did there!” says Dr. Kani. “One of the co-authors of the SIKE algorithm expressed surprise that curves of gender two can be used to obtain elliptic curve information. But this was precisely our original strategy in the 1980s and 1990s (and then).”

Although cryptographers and computer engineers are not always well versed 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 advanced math, especially arithmetic geometry. Computer experts and math experts need to work together to advance this area,” said Dr. problems with genus two curves and elliptic curves.

More information:
Original paper: The number of turns of genus two with elliptic differentials

Brought to you by
Queen’s University


Quote: Mathematical Theorem Used to Crack US Government Encryption Algorithm (2022, November 23) Retrieved November 23, 2022 from https://phys.org/news/2022-11-mathematical-theorem-encryption-algorithm.html

This document is copyrighted. Other than fair dealing for private study or research, nothing may be reproduced without written permission. The content is provided for informational purposes only.

Must Read
Physicists Baffled by Proton Structure Anomaly
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments