Understanding the recent Fujitsu discrete log calculation

The recent announcement by Fujitsu Laboratories, NICT and Kyushu University researchers concerning their record-setting discrete logarithm calculation has led to all sorts of incorrect statements on the Internet and on mailing lists. Here's an attempt to discuss what's really true about this work and what's not. And, with any luck, without too much math. (It's just too hard to typeset with this blog's interface.)

First, let's look at what this work really showed.

The researchers managed to calculate a discrete logarithm in a particular finite field. That's the calculation that would let you break lots of public-key cryptosystems (almost all of them except RSA), so the success of this should be interesting to people working in information security. In this particular case, the researchers calculated a discrete log in GF(3582) using about 148.2 days of number crunching. That's a bit of an improvement over the previous record for similar number crunching, and the Wikipedia page on discrete logarithm records now lists this work as the record holder for a field of characteristic 3.

But what does that really tell us about the security of practical cryptosystems?

First, note that 3582 is about the same as 2923, so it's reasonable to say that this calculation cracked a key equivalent to 923 bits in size. That's not even close to what current standards recommend, where 1,024-bit keys will be obsolete no later than next year (2013) and replaced by 2,048-bit keys going forward. Even the most optimistic researchers don't think that they'll be able to crack a 2,048-bit key any time soon, so nothing that people are using today should be affected by this. (Unless they're using some dusty, pre-dot-com era software. Don't do that.)

The approach used by these researchers uses an attack based on the "function field sieve," an algorithm that dates back to 1994 that only works well in particular cases – in certain finite fields of small characteristic. The 1999 paper that's linked to here says that it's asymptotically faster than the previously known algorithms when applied to finite fields GF(pn) where p6n. If p is a large prime and n is small, we're far from satisfying that inequality, and the function field sieve is actually worse than other algorithms.

And in what's used in the real world, we have big primes instead of small ones, or that p is always big and n is always small. That means that for real-world systems, this attack isn't actually very useful. (It's actually slower than other attacks, so you wouldn't want to even try it.)

So to make that a bit clearer, this work is an interesting implementation of an approach that's been known since 1994, but it's not relevant to any discrete-log based cryptosystems that are in use today, and that includes those that use pairing-based approaches.

Leave a Reply

Your email address will not be published. Required fields are marked *