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

From: Nasrul Zikri <[email-masked]>
Date: Wed, 20 Nov 2019 05:51:13 +0000

Hello Guilin,

The parameters from RFC 3526 have been added to by other RFC (RFC 5114, RFC 7919). I think that Group 23 and 24 (from RFC 5114) may give you the structure you want. Group 23 describe 2048-bit MODP Group with 224-bit Prime Order Subgroup, and Group 24 describe 2048-bit MODP Group with 256-bit Prime Order Subgroup.

For Group 24, The hexadecimal value of the prime is:

   p = 87A8E61D B4B6663C FFBBD19C 65195999 8CEEF608 660DD0F2
       5D2CEED4 435E3B00 E00DF8F1 D61957D4 FAF7DF45 61B2AA30
       16C3D911 34096FAA 3BF4296D 830E9A7C 209E0C64 97517ABD
       5A8A9D30 6BCF67ED 91F9E672 5B4758C0 22E0B1EF 4275BF7B
       6C5BFC11 D45F9088 B941F54E B1E59BB8 BC39A0BF 12307F5C
       4FDB70C5 81B23F76 B63ACAE1 CAA6B790 2D525267 35488A0E
       F13C6D9A 51BFA4AB 3AD83477 96524D8E F6A167B5 A41825D9
       67E144E5 14056425 1CCACB83 E6B486F6 B3CA3F79 71506026
       C0B857F6 89962856 DED4010A BD0BE621 C3A3960A 54E710C3
       75F26375 D7014103 A4B54330 C198AF12 6116D227 6E11715F
       693877FA D7EF09CA DB094AE9 1E1A1597

   The hexadecimal value of the generator is:

   g = 3FB32C9B 73134D0B 2E775066 60EDBD48 4CA7B18F 21EF2054
       07F4793A 1A0BA125 10DBC150 77BE463F FF4FED4A AC0BB555
       BE3A6C1B 0C6B47B1 BC3773BF 7E8C6F62 901228F8 C28CBB18
       A55AE313 41000A65 0196F931 C77A57F2 DDF463E5 E9EC144B
       777DE62A AAB8A862 8AC376D2 82D6ED38 64E67982 428EBC83
       1D14348F 6F2F9193 B5045AF2 767164E1 DFC967C1 FB3F2E55
       A4BD1BFF E83B9C80 D052B985 D182EA0A DB2A3B73 13D3FE14
       C8484B1E 052588B9 B7D2BBD2 DF016199 ECD06E15 57CD0915
       B3353BBB 64E0EC37 7FD02837 0DF92B52 C7891428 CDC67EB6
       184B523D 1DB246C3 2F630784 90F00EF8 D647D148 D4795451
       5E2327CF EF98C582 664B4C0F 6CC41659

   The generator generates a prime-order subgroup of size:

   q = 8CF83642 A709A097 B4479976 40129DA2 99B1A47D 1EB3750B
       A308B0FE 64F5FBD3

I hope this is helpful.

Tk,
Nasrul

> 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? 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. In FRC 3526, the suggested exponent size for group ID 14 is 220 bits or more.
>
> 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. 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.
>
> Thanks in advance,
>
> Guilin