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 :-)