[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Oakley primes and EC groups



The following is a augmentation of Appendix F of the Oakely-01 draft,
giving the recommended parameters for 4 of the Well-Known Groups.
This includes a heavy-duty elliptic curve group.  A 1536-bit prime is
still in progress; that will complete the 5 WKG's (this prime will
have 90-bits of "strength").

-----

APPENDIX F The Well-Known Groups

   The group identifiers:

      0   No group (used as a placeholder and for non-DH exchanges)
      1   A modular exponentiation group with a 768 bit modulus
      2   A modular exponentiation group with a 1024 bit modulus
      3   A modular exponentiation group with a 1536 bit modulus (TBD)
      4   An elliptic curve group over GF[2^155]
      5   An elliptic curve group over GF[2^185]

      values 2^31 and higher are used for private group identifiers

   Richard Schroeppel performed all the mathematical and computational
   work for this appendix.

   Classical Diffie-Hellman Modular Exponentiation Groups

   The primes for groups 1 and 2 were selected to have certain
   properties.  The high order 64 bits are forced to 1.  This helps the
   classical remainder algorithm, because the trial quotient digit can
   always be taken as the high order word of the dividend, possibly +1.
   The low order 64 bits are forced to 1.  This helps the Montgomery-
   style remainder algorithms, because the multiplier digit can always
   be taken to be the low order word of the dividend.  The middle bits
   are taken from the binary expansion of pi.  This guarantees that they
   are effectively random, while avoiding any suspicion that the primes
   have secretly been selected to be weak.

   Because both primes are based on pi, there is a large section of
   overlap in the hex representations of the two primes.  The primes are
   chosen to be Sophie-Germain primes (i.e., (P-1)/2 is also prime), to
   have the maximum strength against the square-root attack.  The
   starting trial numbers were repeatedly incremented by 2^64 until
   suitable primes were located.

   Because these two primes are congruent to 7 (mod 8), 2 is a quadratic
   residue of each prime.  All powers of 2 will also be quadratic
   residues.  This prevents an opponent from learning the low order bit
   of the Diffie-Hellman exponent.  Using 2 as a generator is efficient
   for some modular exponentiation algorithms.  [Note that 2 is
   technically not a generator in the number theory sense, because it
   omits half of the possible residues mod P.  From a cryptographic
   viewpoint, this is a virtue.]

F.1. Well-Known Group 1:  A 768 bit prime

   The prime is 2^768 - 2^704 - 1 + 2^64 * { [2^638 pi] + 149686 }.  Its
   decimal value is
          155251809230070893513091813125848175563133404943451431320235
          119490296623994910210725866945387659164244291000768028886422
          915080371891804634263272761303128298374438082089019628850917
          0691316593175367469551763119843371637221007210577919

   This has been rigorously verified as a prime.

   The representation of the group in OAKLEY is

      Type of group:                    "MODP"
      Size of field element (bits):      768
      Prime modulus:                     21 (decimal)
         Length (32 bit words):          24
         Data (hex):
            FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
            29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
            EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
            E485B576 625E7EC6 F44C42E9 A63A3620 FFFFFFFF FFFFFFFF
      Generator:                         22 (decimal)
         Length (32 bit words):          1
         Data (hex):                     2

      Optional Parameters:
      Group order largest prime factor:  24 (decimal)
         Length (32 bit words):          24
         Data (hex):
            7FFFFFFF FFFFFFFF E487ED51 10B4611A 62633145 C06E0E68
            94812704 4533E63A 0105DF53 1D89CD91 28A5043C C71A026E
            F7CA8CD9 E69D218D 98158536 F92F8A1B A7F09AB6 B6A8E122
            F242DABB 312F3F63 7A262174 D31D1B10 7FFFFFFF FFFFFFFF
      Strength of group:                 26 (decimal)
         Length (32 bit words)            1
         Data (hex):
            00000042


F.2. Well-Known Group 2:  A 1024 bit prime

   The prime is 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }.
   Its decimal value is
         179769313486231590770839156793787453197860296048756011706444
         423684197180216158519368947833795864925541502180565485980503
         646440548199239100050792877003355816639229553136239076508735
         759914822574862575007425302077447712589550957937778424442426
         617334727629299387668709205606050270810842907692932019128194
         467627007

   The primality of the number has been rigorously proven.

   The representation of the group in OAKLEY is
      Type of group:                    "MODP"
      Size of field element (bits):      1024
      Prime modulus:                     21 (decimal)
         Length (32 bit words):          32
         Data (hex):
            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 ECE65381
            FFFFFFFF FFFFFFFF
      Generator:                         22 (decimal)
         Length (32 bit words):          1
         Data (hex):                     2

      Optional Parameters:
      Group order largest prime factor:  24 (decimal)
         Length (32 bit words):          32
         Data (hex):
            7FFFFFFF FFFFFFFF E487ED51 10B4611A 62633145 C06E0E68
            94812704 4533E63A 0105DF53 1D89CD91 28A5043C C71A026E
            F7CA8CD9 E69D218D 98158536 F92F8A1B A7F09AB6 B6A8E122
            F242DABB 312F3F63 7A262174 D31BF6B5 85FFAE5B 7A035BF6
            F71C35FD AD44CFD2 D74F9208 BE258FF3 24943328 F67329C0
            FFFFFFFF FFFFFFFF
      Strength of group:                 26 (decimal)
         Length (32 bit words)            1
         Data (hex):
            0000004D

F.3. Well-Known Group 3:  An Elliptic Curve Group Definition

   The curve is based on the Galois field GF[2^155] with 2^155 field
   elements.  The irreducible polynomial for the field is u^155 + u^62 +
   1.  The equation for the elliptic curve is

   Y^2 + X Y = X^3 + A X + B

   X, Y, A, B are elements of the field.

   For the curve specified, A = 0 and

    B = u^18 + u^17 + u^16 + u^13 + u^12 + u^9 + u^8 + u^7 + u^3 + u^2 +
   u + 1.

   B is represented in binary as the bit string 1110011001110001111; in
   decimal this is 471951, and in hex 7338F.

   The generator is a point (X,Y) on the curve (satisfying the curve
   equation, mod 2 and modulo the field polynomial).

   X = u^6 + u^5 + u^4 + u^3 + u + 1

   and

   Y = u^8 + u^7 + u^6 + u^3.

   The binary bit strings for X and Y are 1111011 and 111001000; in
   decimal they are 123 and 456.

   The group order (the number of curve points) is
        45671926166590716193865565914344635196769237316
   which is 12 times the prime

         3805993847215893016155463826195386266397436443.
   (This prime has been rigorously proven.)  The generating point (X,Y)
   has order 4 times the prime; the generator is the triple of some
   curve point.

   OAKLEY representation of this group:
      Type of group:                    "EC2N"
      Size of field element (bits):      155
      Irreducible field polynomial:      21 (decimal)
         Length (32 bit words):          5
         Data (hex):
            08000000 00000000 00000000 40000000 00000001
      Generator:
         X coordinate:                   22 (decimal)
             Length (32 bit words):      1
             Data (hex):                 7B
         Y coordinate:                   22 (decimal)
             Length (32 bit words):      1
             Data (hex):                 1C8
      Elliptic curve parameters:
         A parameter:                    23 (decimal)
             Length (32 bit words):      1
             Data (hex):                 0
         B parameter:                    23 (decimal)
             Length (32 bit words):      1
             Data (hex):                 7338F

      Optional Parameters:
      Group order largest prime factor:  24 (decimal)
         Length (32 bit words):          5
         Data (hex):
            00AAAAAA AAAAAAAA AAAAB1FC F1E206F4 21A3EA1B
      Group order:                       25 (decimal)
         Length (32 bit words):          5
         Data (hex):
            08000000 00000000 000057DB 56985371 93AEF944
      Strength of group:                 26 (decimal)
         Length (32 bit words)            1
         Data (hex):
            0000004C


F.4. Well-Known Group 4:  A Large Elliptic Curve Group Definition

   This curve is based on the Galois field GF[2^185] with 2^185 field
   elements.  The irreducible polynomial for the field is

   u^185 + u^69 + 1.

   The equation for the elliptic curve is

   Y^2 + X Y = X^3 + A X + B.

   X, Y, A, B are elements of the field.  For the curve specified, A = 0
   and

   B = u^12 + u^11 + u^10 + u^9 + u^7 + u^6 + u^5 + u^3 + 1.

   B is represented in binary as the bit string 1111011101001; in
   decimal this is 7913, and in hex 1EE9.

   The generator is a point (X,Y) on the curve (satisfying the curve
   equation, mod 2 and modulo the field polynomial);

   X = u^4 + u^3 and Y = u^3 + u^2 + 1.

   The binary bit strings for X and Y are 11000 and 1101; in decimal
   they are 24 and 13.  The group order (the number of curve points) is

        49039857307708443467467104857652682248052385001045053116,

   which is 4 times the prime

        12259964326927110866866776214413170562013096250261263279.

   (This prime has been rigorously proven.)

   The generating point (X,Y) has order 2 times the prime; the generator
   is the double of some curve point.

   OAKLEY representation of this group:

      Type of group:                    "EC2N"
      Size of field element (bits):      185
      Irreducible field polynomial:      21 (decimal)
         Length (32 bit words):          6
         Data (hex):
            02000000 00000000 00000000 00000020 00000000 00000001
      Generator:
         X coordinate:                   22 (decimal)
             Length (32 bit words):      1
             Data (hex):                 18
         Y coordinate:                   22 (decimal)
             Length (32 bit words):      1
             Data (hex):                 D
      Elliptic curve parameters:
         A parameter:                    23 (decimal)
             Length (32 bit words):      1
             Data (hex):                 0
         B parameter:                    23 (decimal)
             Length (32 bit words):      1
             Data (hex):                 1EE9

      Optional parameters:
      Group order largest prime factor:  24 (decimal)
         Length (32 bit words):          6
         Data (hex):
            007FFFFF FFFFFFFF FFFFFFFF F6FCBE22 6DCF9210 5D7E53AF
      Group order:                       25 (decimal)
         Length (32 bit words):          6
         Data (hex):
            01FFFFFF FFFFFFFF FFFFFFFF DBF2F889 B73E4841 75F94EBC
      Strength of group:                 26 (decimal)
         Length (32 bit words)            1
         Data (hex):
            0000005B