Cryptography, the art of secret writing, is about as old as the dissemination of writing itself, its history as exciting as it is revealing. It is used in our everyday lives in the form of encryption and signature systems. Such 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.
Industry Standard Cracked
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, which was set in 2014 by Robert Granger (Surrey), Thorsten Kleinjung (EPFL) and Jens Zumbrägel (Passau). This trio had already cracked a 128-bit secure 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 assumed the security of corresponding encryption methods and even recommended them explicitly for use with numbers of 16000 bits and larger. The research team has now solved the discrete logarithm problem in 30750 bits and demonstrated that such recommendations are not tenable. The new record took three years on different computer clusters. On a single-core PC, as it was standard until 2005, this corresponds to about 2900 years. 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 no longer offers absolute security.
Other Cryptosystems Are Still Secure
According to Dr. Robert Granger, Lecturer in Secure Systems at the University of Surrey, the world record is a fantastic achievement that 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 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, for example, are still secure as things stand at present.