04.05.17 - A collaboration between EPFL and the University of Leipzig led to a new record in the field of cryptography. The research team was able to break a code of exceptional length with very advanced mathematical methods and massive computational power.

Cryptography, also known as the art of protecting messages, is an area combining mathematics and computer science, which is of a paramount importance to the well-functioning of our existing networks. Passwords, credit cards or even emails, all pass through cryptographic methods before being sent over in networks, prompting both hackers and researchers alike to try and find their flaws and weaknesses.

Many cryptographic methods are based on the simple fact that the difficulty to solve certain mathematical problems increases greatly when the numbers processed become larger. The codes generated by these methods are extremely complicated to break but the task is not impossible.

In this case, a team of mathematicians and computer scientists from the IC School and the University of Leipzig has set a new record. Their accomplishment relates to a problem known as the discrete logarithm, a complex problem to solve, which secure Internet communication may depend on, especially websites using https and Virtual Private Networks (VPN).

The principle of solving the discrete logarithm is of a similar complexity as factoring large numbers, but far from easy to understand. To illustrate, an easily solvable problem using small numbers, such as the factorization of 15 in three and five, becomes extremely difficult using much larger numbers. In the case of the new record set, a number consisting of 232 digits, which equals 768 bits, gave a hard time to the researchers.

Although most cryptographic methods on the Internet use much larger encryption keys, than the one used by the researchers, there are still many older systems using similar key lengths. If you are asking yourselves whether the researchers’ achievement will affect message security on the Internet, you will be reassured to know that it took over a year and a half of calculations, on more than 3,500 cores, which is the equivalent of more than 300 computers, to break the code. "We now know that these systems still offer a decent level of security,” said IC Professor Arjen Lenstra from the Laboratory for Cryptologic Algorithms.

It is possible to use longer keys to make the process of code breaking more difficult, but no one is able to predict the future of algorithmic breakthroughs and computational power. Alternative methods of protecting messages, such as the discrete logarithm problem on elliptic curves, are already in use and – so far, you may rest assured, as no efficient mathematical methods are known to break them. 

The research Computation of a 768-Bit Prime Field Discrete Logarithm (Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata and Colin Stahlke) was presented at Eurocrypt 2017, the Annual International Conference on the Theory and Applications of Cryptographic Techniques in Paris this May, and it received the mention of a Runner-up to the Best Paper Award. Further information: Laboratory for Cryptologic Algorithms

Authors:Inka Sayed, Jeremy HottingerSource:IC | Computer and Communication Sciences