05. August 2019, 10:13 Uhr | Joachim Kroll
An international team of mathematicians has developed a new method for overcoming cryptographic codes and set a new world record. This means that a certain variant of encryption systems can no longer be used securely.
Cryptography systems use numbers with hundreds of digits to protect, for example, bank data for online payments or confidential information in e-mail traffic. The security of the widely used public key encryption methods is essentially based on two algorithmic problems, the discrete logarithm problem and the factorization problem. These are highly difficult mathematical problems that have taken billions of years to solve even when using current supercomputers.
Five researchers from the University of Passau, the École Polytechnique Fédérale de Lausanne (EPFL), the Dutch Centrum Wiskunde & Informatica (CWI) and the English University of Surrey have now cracked such a problem: they computed discrete logarithms in a mathematical domain, a so-called binary body, with exactly 30750 bits, which corresponds to decimal numbers with 9257 digits. This size beats the previous record in a body with 9234 bits or 2780 decimal places set in 2014 by Robert Granger (Surrey), Thorsten Kleinjung (EPFL) and Jens Zumbrägel (Passau). This trio had already cracked a 128-bit-safe industry standard in 2014, which is also based on the discrete logarithm problem.
Since then, Granger, Kleinjung and Zumbrägel have developed an even faster algorithm. Some cryptography experts had previously continued to assume the security of corresponding encryption methods and even recommended these explicitly for use with numbers from approx. 16000 bits in size. Together with Arjen K. Lenstra (EPFL) and Benjamin Wesolowski (CWI), the research trio has now solved the discrete logarithm problem in 30750 bits - demonstrating that such recommendations are not tenable. The new record took three years on different computer clusters. This corresponds to about 2900 years on a single-core PC as it was standard until 2005. Even if three years still sound like a long time: The mathematical advances of recent years and the immense increase in computing power make it clear that this variant of encryption systems already no longer offers absolute security.
According to Dr. Robert Granger, Lecturer in Secure Systems at the University of Surrey, the world record is a fantastic achievement which shows that this hitherto essential part of the cryptographic world should now be a thing of the past. On the other hand, there are also constructive applications of such fast algorithms, even in cryptography itself, which is why Granger speaks of a win-win situation. Prof. Dr. Jens Zumbrägel, professor of mathematics with a focus on cryptography at the University of Passau, adds: "Such large-format calculations help us to understand where dangers lurk and can lead to insights that are applied in other scenarios. Therefore, these experiments are immensely important for assessing the security of today's cryptography." However, Zumbrägel also makes it clear that other cryptosystems, which are based on factorization or discrete logarithms in prime bodies or elliptic curves, are still secure as things stand.