# What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA

I was a bit confused. DSA, ElGamal and others are based on the assumption that DLP is a hard problem to solve. The DLP problem can be defined in different cyclic structures, but making progress in one of this structures does not imply any progress in breaking DLP in other structures?

Also, the question Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? contains the following:

So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite moduli, you can also solve it for prime moduli.

So, we now have a improved algorithm that can solve the DLP problem for $2^{6120}$ composite moduli? Does this mean anything for RSA 1024, 2048? DSA? Or are the DLP assumtions only valid in the cyclic structure where there are used?

And why is the exponent that large? RSA, Diffie Hellman all use exponents 1024, or 2048?.

(This question could be flagged as duplicated. But because i could not pose these questions as answer i asked a new question.)

I hope the question is clear. And as always, thanks for your help!

-
The quote is perhaps a bit misleading. The intended meaning was probably "Furthermore, if you can solve DLP for any arbitrary composite moduli, you can also solve it for prime moduli." The word "any" matters in so far that the DLP problem is differently hard in different groups, and the hardness is not just a function of the bit length of the modulus. – Henrick Hellström May 31 '13 at 11:24

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that this finite field was previously thought to be of cryptographic interest (e.g. for pairing schemes), at least when $n$ is of the forms explained here enabling the new attacks.

One way to see the Galois finite field with $2^n$ elements, $GF(2^n)$ or $\mathbb{F}_{2^n}$, is as the set of $n$-bit vectors representing the coefficients of a binary polynomial of degree $n-1$, with as additive law the addition of binary polynomials, and as multiplicative law (of interest in the DLP) the multiplication of binary polynomial followed by reduction modulo some suitable binary polynomial of degree $n$.

RSA and DSA work on different algebraic structures:

• RSA works on the finite unit ring of integers modulo $N$, with $N$ a public composite of secret factorization, which factors are huge primes. Notice that the number of elements in this ring is $N$, and thus not of the form $2^n$.
• DSA works on the finite field of integers modulo $P$ for a public prime $P$ (such that $P-1$ is divisible by some suitably large prime, which is the order of a multiplicative subgroup; thanks to Samuel Neves for pointing my earlier serious mistake on that). Notice that the number of elements in this field is $P$, and thus not of the form $2^n$.

Because of these different algebraic structures, I can confidently tell that the algorithms used in these recent announcements are not directly usable against RSA and DSA. In my not so informed opinion, for the same reason, they are not directly usable against schemes based on the DLP on elliptic curve groups, including when the base field of the elliptic curve is some of the $GF(2^n)$ that are common practice for ECDSA. In fact I can not spot any cryptographic scheme in wide use that is directly impacted.

As of future advances against RSA, DSA, and Elliptic Curve cryptographic schemes, that may be enabled by these recent developments, my opinion is near worthless, for I'm not a competent number theorist. But I can still commit my feeling: I'm not too worried for the security of RSA, DSA, DH; and ECDSA or ECDH over elliptic curve groups with base field $GF(P)$, or even $GF(2^n)$.

Additions: The $n$ in the new attacks is large (compared to $2048$ or $4096$, previously thought safe and very safe levels) because the attackers can, and bigger values better demonstrate the power of their techniques.

-
Thanks for the very clear explanation! – 11d060a946665fb769d865f4bbb48c May 31 '13 at 17:48
One tiny detail: DSA usually works over subgroups of order $q$ modulo $p$. So the primes are often of the form $qr + 1$, where $q \approx 2^{2b}$, $b$ being the target security level. – Samuel Neves May 31 '13 at 20:21
@Samuel Neves: thanks for pointing that serious mistake! Fixed. – fgrieu May 31 '13 at 20:59