From: Eric Young <eay@mincom.oz.au>
Date: Tue, 14 Nov 1995 09:02:19 +0800
To: cypherpunks@toad.com
Subject: 4096 bit strong prime for Diffle-Hellman
Message-ID: <Pine.SOL.3.91.951114090156.23102A-100000@orb>
MIME-Version: 1.0
Content-Type: text/plain



A bit of a ramble about Diffle-Hellman parameters.....

Just for anyone interested, I 'found' a suspected 4096 strong prime (p and
(p-1)/2 are prime) for use with Diffie-Hellman, generator of 2.
If any-one wants for testing the primality, please let
me know if it passes.  I'm currently using the Miller-Rabin primality
test with my own bignum library.
I'm just generating some 'default' DH parameter sets for distribution
with the next version of my crypto library (SSLeay), I'll send out Phil
Karn's 1024 and 2048 bit values and this one if other people are happy
with it.

Some quick times (in seconds) for the use of a 4096 bit prime with DH on a
SGI (200mhz R4400).  The RSA operation is PKCS#1 private key encrypt, the
DH operation is a PKCS#3 public/private key generation followed by the
generation of session key, the maths routines are from SSLeay.

modulus     DH     RSA
 512      0.23   0.041
1024      1.71   0.248
2048     12.88   1.702
4096    102.18  13.150

The RSA times as you will notice are about the same speed for twice the DH
bit size.  This is due to the RSA operation being reduced to 2 a^b%m
operation where m has the values of p and q where (p-1)*(q-1) is the RSA
modulus, half the bit size. The DH operation is 2 a^b%m operations,
(generating the 'public key' and then raising by the peer's public key). 
Does any-one know of any tricks to speeding the DH operation up (not
counting implementing a better a^b%m function, I'm going to do this later
when I have time :-).  From what I can see, there is not much that can be
done except perhaps some tricks in the initial g^rand%p, since the
generator is a known value. 

Even if the private DH values are pre-calculated, this will only halve the
time of the DH operation and if this is done it looses the advantage of DH
in that if the private/public pair are 'generated on the fly',
pre-recorded session will not be able to be decoded if the private key is
revealed at a later point in time.  This is the major advantage I can see
of a DH key exchange over the use of an RSA based system so I would 
object to loosing this feature. 

With these times I think that 4096 bit DH is not going to be used for
quite a while :-).

eric

The suspected 4096 bit strong prime.

In C, first byte is most significate (big endian)
unsigned char dh4096_p={
        0xFE,0xEA,0xD1,0x9D,0xBE,0xAF,0x90,0xF6,0x1C,0xFC,0xA1,0x06,
        0x5D,0x69,0xDB,0x08,0x83,0x9A,0x2A,0x2B,0x6A,0xEF,0x24,0x88,
        0xAB,0xD7,0x53,0x1F,0xBB,0x3E,0x46,0x2E,0x7D,0xCE,0xCE,0xFB,
        0xCE,0xDC,0xBB,0xBD,0xF5,0x65,0x49,0xEE,0x95,0x15,0x30,0x56,
        0x81,0x88,0xC3,0xD9,0x72,0x94,0x16,0x6B,0x6A,0xAB,0xA0,0xAA,
        0x5C,0xC8,0x55,0x5F,0x91,0x25,0x50,0x3A,0x18,0x0E,0x90,0x32,
        0x4C,0x7F,0x39,0xC6,0xA3,0x45,0x2F,0x31,0x42,0xEE,0x72,0xAB,
        0x7D,0xFF,0xC7,0x4C,0x52,0x8D,0xB6,0xDA,0x76,0xD9,0xC6,0x44,
        0xF5,0x5D,0x08,0x3E,0x9C,0xDE,0x74,0xF7,0xE7,0x42,0x41,0x3B,
        0x69,0x47,0x66,0x17,0xD2,0x67,0x0F,0x2B,0xF6,0xD5,0x9F,0xFC,
        0xD7,0xC3,0xBD,0xDE,0xED,0x41,0xE2,0xBD,0x2C,0xCD,0xD9,0xE6,
        0x12,0xF1,0x05,0x6C,0xAB,0x88,0xC4,0x41,0xD7,0xF9,0xBA,0x74,
        0x65,0x1E,0xD1,0xA8,0x4D,0x40,0x7A,0x27,0xD7,0x18,0x95,0xF7,
        0x77,0xAB,0x6C,0x77,0x63,0xCC,0x00,0xE6,0xF1,0xC3,0x0B,0x2F,
        0xE7,0x94,0x46,0x92,0x7E,0x74,0xBC,0x73,0xB8,0x43,0x1B,0x53,
        0x01,0x1A,0xF5,0xAD,0x15,0x15,0xE6,0x3D,0xC1,0xDE,0x83,0xCC,
        0x80,0x2E,0xCE,0x7D,0xFC,0x71,0xFB,0xDF,0x17,0x9F,0x8E,0x41,
        0xD7,0xF1,0xB4,0x3E,0xBA,0x75,0xD5,0xA9,0xC3,0xB1,0x1D,0x4F,
        0x1B,0x0B,0x5A,0x09,0x88,0xA9,0xAA,0xCB,0xCC,0xC1,0x05,0x12,
        0x26,0xDC,0x84,0x10,0xE4,0x16,0x93,0xEC,0x85,0x91,0xE3,0x1E,
        0xE2,0xF5,0xAF,0xDF,0xAE,0xDE,0x12,0x2D,0x12,0x77,0xFC,0x27,
        0x0B,0xE4,0xD2,0x5C,0x11,0x37,0xA5,0x8B,0xE9,0x61,0xEA,0xC9,
        0xF2,0x7D,0x4C,0x71,0xE2,0x39,0x19,0x04,0xDD,0x6A,0xB2,0x7B,
        0xEC,0xE5,0xBD,0x6C,0x64,0xC7,0x9B,0x14,0x6C,0x2D,0x20,0x8C,
        0xD6,0x3A,0x4B,0x74,0xF8,0xDA,0xE6,0x38,0xDB,0xE2,0xC8,0x80,
        0x6B,0xA1,0x07,0x73,0x8A,0x8D,0xF5,0xCF,0xE2,0x14,0xA4,0xB7,
        0x3D,0x03,0xC9,0x12,0x75,0xFB,0xA5,0x72,0x81,0x46,0xCE,0x5F,
        0xEC,0x01,0x77,0x5B,0x74,0x48,0x1A,0xDF,0x86,0xF4,0x85,0x4D,
        0x65,0xF5,0xDA,0x4B,0xB6,0x7F,0x88,0x2A,0x60,0xCE,0x0B,0xCA,
        0x0A,0xCD,0x15,0x7A,0xA3,0x77,0xF1,0x0B,0x09,0x1A,0xD0,0xB5,
        0x68,0x89,0x30,0x39,0xEC,0xA3,0x3C,0xDC,0xB6,0x1B,0xA8,0xC9,
        0xE3,0x2A,0x87,0xA2,0xF5,0xD8,0xB7,0xFD,0x26,0x73,0x4D,0x2F,
        0x09,0x67,0x92,0x35,0x2D,0x70,0xAD,0xE9,0xF4,0xA5,0x1D,0x84,
        0x88,0xBC,0x57,0xD3,0x2A,0x63,0x8E,0x0B,0x14,0xD6,0x69,0x3F,
        0x67,0x76,0xFF,0xFB,0x35,0x5F,0xED,0xF6,0x52,0x20,0x1F,0xA7,
        0x0C,0xB8,0xDB,0x34,0xFB,0x54,0x94,0x90,0x95,0x1A,0x70,0x1E,
        0x04,0xAD,0x49,0xD6,0x71,0xB7,0x4D,0x08,0x9C,0xAA,0x8C,0x0E,
        0x5E,0x83,0x3A,0x21,0x29,0x1D,0x69,0x78,0xF9,0x18,0xF2,0x5D,
        0x5C,0x76,0x9B,0xDB,0xE4,0xBB,0x72,0xA8,0x4A,0x1A,0xFE,0x6A,
        0x0B,0xBA,0xD1,0x8D,0x3E,0xAC,0xC7,0xB4,0x54,0xAF,0x40,0x8D,
        0x4F,0x1C,0xCB,0x23,0xB9,0xAE,0x57,0x6F,0xDA,0xE2,0xD1,0xA6,
        0x8F,0x43,0xD2,0x75,0x74,0x1D,0xB1,0x9E,0xED,0xC3,0xB8,0x1B,
        0x5E,0x56,0x96,0x4F,0x5F,0x8C,0x33,0x63,
        };
unsigned char dh4096_g={
        0x02,
        };

Or as a ASN.1 encoded pkcs#3 object.

-----BEGIN DH PARAMETERS-----
MIICCAKCAgEA/urRnb6vkPYc/KEGXWnbCIOaKitq7ySIq9dTH7s+Ri59zs77zty7
vfVlSe6VFTBWgYjD2XKUFmtqq6CqXMhVX5ElUDoYDpAyTH85xqNFLzFC7nKrff/H
TFKNttp22cZE9V0IPpzedPfnQkE7aUdmF9JnDyv21Z/818O93u1B4r0szdnmEvEF
bKuIxEHX+bp0ZR7RqE1AeifXGJX3d6tsd2PMAObxwwsv55RGkn50vHO4QxtTARr1
rRUV5j3B3oPMgC7Offxx+98Xn45B1/G0Prp11anDsR1PGwtaCYipqsvMwQUSJtyE
EOQWk+yFkeMe4vWv367eEi0Sd/wnC+TSXBE3pYvpYerJ8n1MceI5GQTdarJ77OW9
bGTHmxRsLSCM1jpLdPja5jjb4siAa6EHc4qN9c/iFKS3PQPJEnX7pXKBRs5f7AF3
W3RIGt+G9IVNZfXaS7Z/iCpgzgvKCs0VeqN38QsJGtC1aIkwOeyjPNy2G6jJ4yqH
ovXYt/0mc00vCWeSNS1wren0pR2EiLxX0ypjjgsU1mk/Z3b/+zVf7fZSIB+nDLjb
NPtUlJCVGnAeBK1J1nG3TQicqowOXoM6ISkdaXj5GPJdXHab2+S7cqhKGv5qC7rR
jT6sx7RUr0CNTxzLI7muV2/a4tGmj0PSdXQdsZ7tw7gbXlaWT1+MM2MCAQI=
-----END DH PARAMETERS-----

eric
--
Eric Young                  | Signature removed since it was generating
AARNet: eay@mincom.oz.au    | more followups than the message contents :-)