4096 bit strong prime for Diffle-Hellman
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 :-)
On Tue, 14 Nov 1995, Eric Young wrote:
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.
As a matter of interest, how long did it take you to generate this, and with what hardware? I left a 120Mhz Pentium searching for 15 hours overnight without any success (it managed to eliminate 10 candidate primes as not strong in that time). Regards, - Andy ----------------------------------------------------------------------- Andrew Brown Internet <asb@nexor.co.uk> Telephone +44 115 952 0585 PGP (2048/9611055D): 69 AA EF 72 80 7A 63 3A C0 1F 9F 66 64 02 4C 88 All views expressed here are my own and not those of my employer
On Thu, 16 Nov 1995, Andy Brown wrote:
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. As a matter of interest, how long did it take you to generate this, and with what hardware? I left a 120Mhz Pentium searching for 15 hours overnight without any success (it managed to eliminate 10 candidate primes as not strong in that time).
Well, I left it running for about 50 hours over last weekend without a hit. Then I restarted it on Monday night and got a hit in about 12 hours :-). (I thought it has finished sooner but I looked again at the 'script(1)' output and it did take 12 hours). It is sort of hard to tell how longs things would take, due to the hit or miss nature of this kind of search for primes. This is on a SGI with a 200mhz R4400 which is about the same speed as a 120mhz pentium when using my maths libraries. I'm doing the 'pick' an odd random number 'p', sieve p and (p-1)/2 over the first 2000 primes, adding in steps until a number passes the sieve. For a generator of 2, p mod 24 == 11 should be true. When it passes, then do Miller-Rabin tests on P and (P-1/2) enough times to be happy that the number is probably a prime :-). I believe that there are improvement that I can put in there for the initial search for candidate primes The actuall numbers for the search are as follows, 1057 numbers passed the 'strong prime sieve'. 7 numbers passed the prime test 1 number passed both the prime and strong prime test. I suspect the ratio of 132 cadidates for 'strong' prime testing for each 'prime' could be brought down quite a bit but since I only need strong primes for DH parameters, I probably will not spend the time on improving my initial sieve right now. eric PS, I just 'found' another 2048 bit strong prime last friday night, 2929 numbers passed the 'strong prime sieve'. 29 numbers passed the prime test (101 candidates per hit) 1 number passed both the prime and strong prime test, 4h12m run time. -- Eric Young | Signature removed since it was generating AARNet: eay@mincom.oz.au | more followups than the message contents :-)
On Tue, 14 Nov 1995, Eric Young wrote:
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
Urk, that reads very badly what I ment is that since a different public/private key is used per session, if a private key is revealed, any previous and future comunication between the 2 entities is not compromised, only the particular session using that public/private key pair. Also since the key pair is generated on the fly, they don't need to be recorded on disk etc, so they only way to get the private key is to 'hack' the application at runtime (or modify it in advance). eric (who is have a bad day converting his thoughts to english...).
participants (2)
-
Andy Brown -
Eric Young