Re: [Cfrg] One question about MODP: the structure of DLP prime in a finite field

> -----Original Message-----
> From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Wang Guilin
> Sent: Monday, November 18, 2019 9:46 PM
> To: cfrg@irtf.org
> Cc: Wang Guilin <Wang.Guilin@huawei.com>
> Subject: [Cfrg] One question about MODP: the structure of DLP prime in a
> finite field
> 
> Dear everyone,
> 
> Highly appreciate if anyone can help on the following question.
> 
> RFC 3526 (https://tools.ietf.org/html/rfc3526) offers a number of DLP
> parameters in a finite field. An example is group ID 14, detailed specification
> copied below.
> 
> =========================
> This group is assigned id 14.
> 
>    This prime is: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
> 
>    Its hexadecimal value is:
>       FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
>       29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
>       EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
>       E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
>       EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
>       C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
>       83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
>       670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
>       E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
>       DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
>       15728E5A 8AACAA68 FFFFFFFF FFFFFFFF
> 
>    The generator is: 2.
> =========================
> 
> The question is: What is the structure or factors of prime p-1, where the
> value of p is given above?

The prime factors of p-1 are known to be 2 and q = (p-1)/2.

> Also, if we do not know the factors of p-1, it is risky
> to just use g=2 as a generator as the order of 2 could be quite small.

The order of g=2 is known to be q

>  In FRC
> 3526, the suggested exponent size for group ID 14 is 220 bits or more.

Yes; the reasoning is that there are two style of attacks to solve the discrete log problem:

- A NFS attack against the group (which is estimated to take approximately 2**110 effort
- A Giant-step-baby-step attack against the exponent; if the exponent is N bits, this takes about 2**(N/2) effort

Selecting an exponent size of 220 makes these two attacks approximately the same effort; selecting an exponent from a smaller range would actively decrease security, while selecting from a significantly larger range would increase the work required without increasing security.

Personally, I'd use a slightly larger range (perhaps 256 bits); our estimates for NFS might be a bit off, and increasing the exponent size modestly doesn't increase time that much...

> 
> My real reason to ask this question is: We want to test SPEKE (a PAKE
> protocol) by using group ID 14. However, to run SPEKE, we need to know a
> prime factor q of p-1, i.e. (p-1)=qk, where k is an integer. Ideally, the bit
> length of q is between 220-256.

Actually, the length of q is 2047 bits; it's not obvious to me what a large q would be an issue in this situation...

>  Once we know such a prime factor q for p-1,
> then both client and server in SPEKE can calculate a generator something like
> g=(H(pw, salt))^k. Then, they can run DH key exchange normally by using g.
> 
> So, the difficulty here is: Without knowing the factors of p-1 in group ID 14, it
> seems not possible to generate such a generator g in SPEKE.

As above, that's not an issue...

> 
> Thanks in advance,
> 
> Guilin
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg