Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've see many articles, most of them basically the same, praising Fujitsu for cracking what is referred to as a 923 bit pairing based encryption. I understand that in comparing RSA to AES you've got something like a power of 10 for the key lengths to be equally strong. From what I read it seems that this pairing based algorithm is a public key algorithm but somehow involving 3 keys. I don't know much about the various algorithms but I have read that in the public key space eliptic curve algorithms can get away with much smaller keys than RSA. I've seem some articles that rate the complexity of various algorithms based on key length, but I don't know nearly enough to understand the papers on this. Is this new record similar to breaking something encrypted with a 923 bit key using RSA? I've seen articles that I believe are badly overstating this by saying things like "if they can break a 923 bit algorithm, how secure is the standard 256 bits?" I assume that's comparing apples and oranges, but I don't know nearly enough to really know. Does anyone know how to compare these things?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

One could roughly take the following reasoning: in the press release, it is mentioned that

We have succeeded in breaking the pairing-based cryptography for 148.2 days in total using the computers of 21 servers (252 CPU cores) at NICT, Kyushu University and Fujitsu Laboratories. This computational cost is equivalent to the total time of computing Intel Xeon processor of 1 CPU core for 102 years.

Taking the Xeon CPU near me (a X3680 clocked at 3.33GHz) with AES-NI instructions, one can roughly expect that one needs less than 32 clock cycles to compute a key-schedule and an encryption, which results in about $\frac{3.33\cdot10^9}{32} \approx 10^8$ AES evaluations per second for one CPU core, or $365.25\cdot24\cdot86400\cdot 10^8 \approx 2^{56}$ AES evaluations a year, i.e. a total effort of about $2^{63}$ AES evaluations. Lenstra's extended equations put this effort in parallel with breaking an RSA key of 613 to 725 bits. Remember that this is slightly less than the current RSA factoring record of 768 bits.

share|improve this answer
    
Hi cryptopathe, Thanks for the information. Putting it in terms of cpu power seems like a good way of comparing these dissimilar algorithms. Based on the link you provided, if I understand correctly, this is roughly eqivilant to cracking AES with about a 66 bit key length (or so). This does put it into perspective. Thanks again. –  Mitchell Kaplan Jun 22 '12 at 7:51

There is nothing really new about this research. It is just a fast implementation of a construction known since 1994.

Source:

http://superconductor.voltage.com/2012/06/understanding-the-recent-fujitsu-discrete-log-calculation.html

share|improve this answer
    
Thank you Mark, that was very helpful. –  Mitchell Kaplan Jun 22 '12 at 6:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.