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 have a question regarding the key generation process of methods that are based on the discrete logarithm problem. This site gives some good insights, but I don't fully grasp it I think: http://www.keylength.com/

For example I know that till lately one should have used 1024 bit group modulus and a 160 bit long secret key and that picking the secret key size is always roughly double the security level (hence here 80 bit security) one wants to achieve.

My question is: How does the groups modulus size relate to the security level? Does the group generator always have to be the same size as the group modulus?

share|improve this question
    
It doesn't. $\;$ –  Ricky Demer May 25 '13 at 20:06
    
You might technically use a 2 bit group generator with a 2048 bit group modulus and a 256 bit secret key. –  Henrick Hellström May 26 '13 at 0:58
    
I suspect he misused the terminology, and is actually asking about the group (modulus) size. –  Samuel Neves May 26 '13 at 1:14
    
Yes thats what I mean I think. –  user7018 May 26 '13 at 19:22
add comment

1 Answer 1

The best known estimates are still the two that can be found in RFC 3526. Both estimates (with regard to the modulus size) are based on the estimated number of operations required to compute discrete logarithms using number field sieve based methods. The reason the estimates differ, is because of the second estimate does not account for memory/time trade offs that would require arguably unrealistic amounts of storage space.

   +--------+----------+---------------------+---------------------+
   | Group  | Modulus  | Strength Estimate 1 | Strength Estimate 2 |
   |        |          +----------+----------+----------+----------+
   |        |          |          | exponent |          | exponent |
   |        |          | in bits  | size     | in bits  | size     |
   +--------+----------+----------+----------+----------+----------+
   |   5    | 1536-bit |       90 |     180- |      120 |     240- |
   |  14    | 2048-bit |      110 |     220- |      160 |     320- |
   |  15    | 3072-bit |      130 |     260- |      210 |     420- |
   |  16    | 4096-bit |      150 |     300- |      240 |     480- |
   |  17    | 6144-bit |      170 |     340- |      270 |     540- |
   |  18    | 8192-bit |      190 |     380- |      310 |     620- |
   +--------+----------+---------------------+---------------------+

These estimates do not account for post-quantum cryptography. Arguably, it is not entirely improbable that we will see major break-troughs in quantum cryptography, rendering these estimates moot, long before the difference between estimated 128 bit strength and 256 bit strength will become relevant for most practical purposes. Then again, there might of course be applications that generate a lot of traffic and has to bump the estimated security strength, to guarantee that the advantage of an attacker stays well below $2^{-128}$ even in a shorter term.

share|improve this answer
add comment

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.