Q: RFC 5114 (Additional DH Groups...), 2048-bit MODP Group, and Safe Prime
Jeffrey Walton
RFC 5114 specifies additional DH groups for use with IETF standards.
Section 2.2 offers a 2048 MODP group with 224 prime order.
http://tools.ietf.org/html/rfc5114#section-2.2.
Using Crypto++, I load the parameters in a DH object, and then
validated the parameters - OK. I then calculated q = (p-1)/2 and
performed a primality test, which subsequently *failed*. Below is the
factorization of q using ecm (I took a guess at B1 rather than looking
up Dickman’s function for an estimate). ecm cross validates the Crypto+
+ result.
I thought calculating q was trivial, but apparently its not. I think
I've got my wires crossed some where, but I can't seem to see the
forest through the trees.
Can anyone point out my mistake?
Jeff
$ ecm -v 1999 < rfc5114-2-2-q.txt
GMP-ECM 6.2 [powered by GMP 4.3.2] [ECM]
Input number is
0x56883f0f4891d4e86b307d53caace28fd106b272b41dcfe8daa58acbdb0e853af37d0a0efcad2b6dd7cd1e203dd0ef8af59eb445184e0c070ef35c2d093a5053369fc0a956b56109481be4f6f7ed26fc6c8f47f7aadb9ca5bd6adbe85b609103e4fcc688f69a6dfb635d059645de13df350070505ce24b8459dfc518b848c41b409430985e44c2ed8b01738a20aec99813c139e3ef18f7ee39887b890fead03a0acc3ecd6e052436e6fc9d66221941c398aebaf0cc6320d24066c350dcf2c3f45f30734e6494595ce290b9720982174d91f885870b73cbb1e4da9ee7a5d40514f1fdb9e0b5c73adcbf79b1f17fd18fb8e7cef29c2738dc0e05626fff06087327
(617 digits)
Using MODMULN
********** Factor found in step 1: 9
Found composite factor of 1 digits: 9
Composite cofactor
(0x56883f0f4891d4e86b307d53caace28fd106b272b41dcfe8daa58acbdb0e853af37d0a0efcad2b6dd7cd1e203dd0ef8af59eb445184e0c070ef35c2d093a5053369fc0a956b56109481be4f6f7ed26fc6c8f47f7aadb9ca5bd6adbe85b609103e4fcc688f69a6dfb635d059645de13df350070505ce24b8459dfc518b848c41b409430985e44c2ed8b01738a20aec99813c139e3ef18f7ee39887b890fead03a0acc3ecd6e052436e6fc9d66221941c398aebaf0cc6320d24066c350dcf2c3f45f30734e6494595ce290b9720982174d91f885870b73cbb1e4da9ee7a5d40514f1fdb9e0b5c73adcbf79b1f17fd18fb8e7cef29c2738dc0e05626fff06087327)/
9 has 616 digits
$
Greg Rose
Jeffrey Walton <nolo...@gmail.com> wrote:
>RFC 5114 specifies additional DH groups for use with IETF standards.
>Section 2.2 offers a 2048 MODP group with 224 prime order.
>http://tools.ietf.org/html/rfc5114#section-2.2.
>
>Using Crypto++, I load the parameters in a DH object, and then
>validated the parameters - OK. I then calculated q = (p-1)/2 and
>performed a primality test, which subsequently *failed*. Below is the
Yes, because (p-1)/2 is not meant to be prime for
this kind of D-H group. This is one of the ones
where you work in a subgroup of known order rather
than most of the group.
>I thought calculating q was trivial, but apparently its not. I think
>I've got my wires crossed some where, but I can't seem to see the
>forest through the trees.
You don't need to calculate it, it is given to you:
" The generator generates a prime-order subgroup of size:
q = 801C0D34 C58D93FE 99717710 1F80535A 4738CEBC BF389A99
B36371EB"
If you check, you will discover that this divides
into p-1.
So your secret key is a number between 2 and q, and
this limits the square-and-multiply iterations to 224,
rather than 2048.
Why this complication, you ask? Well, besides the
efficiency increase by using smaller exponents,
there was a realization due to Schnorr that there
are two kinds of Discrete Logarithm problems to be
solved. When working in a modulo-P field, there
are sub-exponential ways of calculating discrete
logarithms. So you need to have longer keys. There
are also attacks that work on the more general
discrete logarithm problem, but they are all
square-root attacks, thus fully exponential. Now
it turns out that no-one knows a way to apply any
more specialized attack to a prime-order subgroup
of the multiplicative group of integers mod P.
So the idea is that you choose an "equivalent
strength" for your underlying block cipher, eg.
triple-DES has 112 bits. Now, to get that level of
strength your hash function needs to be 224 bits
because of birthday attacks. For the public key
side, your resistance to eg. Pollard's algorithms
also needs 224 bits, which determines the subgroup
size. But to resist the more general attacks, you
either need something like elliptic curves, or an
even bigger P (and 2048 bits is considered by many
to be roughly equivalent to 224 bits).
Hope that helps,
Greg.
--