Cryptography, the art of writing secret codes, is as old as writing itself and has an intriguing, revealing history. In our daily life, we benefit from the insights of the discipline whenever we use encryption and signature systems. Those systems work with numbers stretching to hundreds of digits to protect banking data during online transactions and confidential information in email communications, for instance. The security of the widely used public-key encryption process is based on two algorithmic problems: the discrete logarithm problem and the factorisation problem. Both are extremely complicated mathematical problems that would take even the most advanced supercomputers billions of years to solve.
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 managed to solve such a problem now. They calculated discrete logarithms in a finite field which contains exactly 30750 bits, which corresponds to decimal figures with 9257 places. This achievement beats the previous record of 9234 bits or 2780 decimal places set in 2014 by Robert Granger (Surrey), Thorsten Kleinjung (EPFL) and Jens Zumbrägel (Passau). Back in 2014, the trio already broke an industry-standard 128-bit secure system also based on the discrete logarithm problem.
Granger, Kleinjung and Zumbrägel have developed an even faster algorithm since. Until their breakthrough, some cryptographers were confident that the corresponding encryption methods were secure and, in some cases, explicitly recommended their use for digits with a size of 16000 bits or more. In collaboration with Arjen K. Lenstra (EPFL) and Benjamin Wesolowski (CWI), the three researchers now solved the discrete logarithm problem in 30750 bits, effectively proving that such recommendations are insupportable. The new break took three years to run on various computer clusters, a period equivalent to around 2900 years on a single-core desktop computer as commonly used until 2005. Three years may still sound like a long time. But the mathematical progress of the past years and the enormous increase in computing capacity demonstrate that the encryption system in question can no longer guarantee absolute security.
These experiments are fundamental for assessing the security of cryptography in use today.
Prof Jens Zumbrägel, University of Passau
Dr Robert Granger, Lecturer in Secure Systems at the University of Surrey, believes that the world record constitutes an astonishing achievement that ought to confine this currently substantial component of cryptography to the past. He further pointed out that such rapid algorithms can serve more constructive purposes, too, even in the field of cryptography itself, calling it a win-win situation. Prof. Jens Zumbrägel, Professor of Mathematics with a focus on cryptography, added: “Large-scale computations like this help us to understand where the dangers lie and can grant us insights which can be applied in other scenarios. These experiments are fundamental for assessing the security of cryptography in use today." Zumbrägel further emphasised that other cryptographic systems based, for instance, on factorisation or discrete logarithms in prime fields or elliptic curves, are still considered secure at present.