An international team of mathematicians has hailed the end of a variant of a code that is widely used to protect online transactions.
These algorithms, which stretch to hundreds of digits, are created to help protect banking details, but these can be broken if discrete logarithm problems can be solved. These are infamously difficult mathematical problems that should take trillions of years to solve, even with a state-of-the-art supercomputer. The numbers used need to be large enough to stop criminals, while being small enough for practical online usage.
Five researchers from the University of Surrey, Ecole Polytechnique Federale de Lausanne, Switzerland (EPFL), the University of Passau, Germany, and Centrum Wiskunde & Informatica (CWI), The Netherlands, have built on their previous record-breaking techniques to solve the problem in an object called a finite field, which has 2^30750 elements. The 30750-bit number beats the previous record of 9234 bits set in 2014 by Robert Granger, Thorsten Kleinjung and Jens Zumbrägel.
After a flurry of theoretical breakthroughs, in 2014 the trio of Granger, Kleinjung and Zumbrägel broke an industry standard 128-bit secure system based on this problem and designed an even faster algorithm, which had not been tested until now. However, some cryptographers have proposed to continue using these “small characteristic” problem variants for large enough numbers, such as those of 16000 bits. The 30750-bit break, which took three years to run on various computer clusters – the equivalent of 2900 years on a desktop computer with a single core – demonstrates that such proposals are very unwise.
Dr. Benjamin Wesolowski, researcher at CWI and member of the international team that made the record-breaking result possible, says: "The algorithm used is a combination of several building blocks that each solve some smaller problems. One of these building blocks, called Degree 2 elimination, is at the core of recent theoretical breakthroughs. With advanced mathematical methods, I developed a new Degree 3 elimination that allowed the calculations to go much faster". He adds: "This research is about the so-called 'DL problem for small characteristic', and has no bearing on the 'large characteristic' case, the variant used today in security systems." Wesolowski is a member of the Cryptology research group at CWI, headed by Prof. Ronald Cramer. This group investigates fundamental cryptographic questions from a broad scientific perspective, particularly from mathematics, computer science and physics.
Dr. Robert Granger, Lecturer in Secure Systems at the University of Surrey, said: “This is a fantastic achievement for our team, proving that this once integral part of the cryptographic world should be consigned to history. However, there are also constructive applications of such fast algorithms, even in cryptography, so this is a win-win situation. Also, it happens that 30750 is the seating capacity of the AMEX, home of the mighty Seagulls – Brighton and Hove Albion Football Club. So if there were a full house and every fan tossed a coin, guessing the discrete logarithm would be as hard as correctly guessing every single coin toss.”
Jens Zumbrägel, Professor in Mathematics and Cryptography at the University of Passau, added: "Large-scale computations like this help us to understand where the dangers lie and can lead to insights that can be applied in other scenarios, so they are fundamental for assessing the security of cryptography in use today."
More information:
- the technical announcement about the small characteristic discrete logarithm problem on the Number Theory List can be found here: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1907&L=NMBRTHRY&P=51
- Benjamin Wesolowski's contact data at CWI
- Benjamin Wesolowski's personal website
- the Cryptology research group at CWI
A copy of the technical news item:
Dear Number Theorists,
We are pleased to announce a new record computation of discrete
logarithms in the finite field GF(2^30750). The previous record in a
finite field was announced on 31 Jan 2014 in the field GF(2^9234) [2].
Our computation made essential use of the elimination step of the
quasi-polynomial algorithm [3], and is the first large-scale example
to test its potential.
To represent the field GF(2^30750) we use the field extension
GF((2^30)^1025) = GF(2^30)[x] = GF(2^30)[X] / (X^1025 + X + t^3),
where GF(2^30) = GF(2)[t] = GF(2)[T] / (T^30 + T + 1). As usual we
define our target element using binary digits of the mathematical
constant pi (cf. Magma script below) and chose x + t^9 as a presumed
generator. As in previous computations, such as [2], the special case
of a twisted Kummer extension enabled us to reduce considerably the
complexity of the linear algebra step and of the descent stage.
Our computation uses a combination of several algorithms to optimise
its running time. Apart from the descent method of [3], it features
- a highly customised classical descent, starting with an initial
split of the target element of degree 1024,
- new methods to perform descents from degrees 7 ~> 6, 5 ~> 4 as
well as 3d ~> 2d,
- a robust degree 2 ~> 1 elimination [1] with improved efficiency.
In contrast to many previous computations, including [2], our
algorithm obviates Grobner basis computations during the descent.
We implemented the algorithms in C and C++, using Shoup's NTL library,
and ran them between 23 Feb 2016 to 28 May 2019 on various of EPFL's
high-performance clusters based on the Intel Xeon architecture (Ivy
Bridge at 2.6 GHz or Haswell at 2.5 GHz).
The running times (in core hours) for the various steps are
- relation generation 1 h,
- linear algebra 32'498 h,
- initial split 248'140 h,
- classical descent 17'077'836 h,
- non-classical descent 8'122'744 h,
totalling in 25'481'219 core hours, or 2'907 core years.
Details of our computation will appear soon on the IACR eprint server
and on the arXiv.
Robert Granger (University of Surrey, UK)
Thorsten Kleinjung (EPFL, Switzerland)
Arjen Lenstra (EPFL, Switzerland)
Benjamin Wesolowski (CWI, The Netherlands)
Jens Zumbragel (University of Passau, Germany)
---
References
[1] F. Gologlu, R. Granger, G. McGuire, J. Zumbragel. Solving a 6120-bit
DLP on a Desktop Computer. Selected Areas in Cryptography SAC 2013.
[2] R. Granger, T. Kleinjung, J. Zumbragel. Discrete Logarithms
in GF(2^9234). NMBRTHRY list, 31 Jan 2014.
https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401
[3] R. Granger, T. Kleinjung, J. Zumbragel. On the discrete logarithm
problem in finite fields of fixed characteristic. Trans. Amer. Math.
Soc. 370, no. 5 (2018), pp. 3129-3145.
---
For the 'Magma verification script': see the original message.
See also: https://www.surrey.ac.uk/news/researchers-hail-demise-online-security-algorithm
