Re: Proven Primes
Ben Laurie writes: I actually just finished finding the 16384 bit Diffie-Helman group with same kind of parameters. It took about 9.5 months to generate. The 12288 bit group took only about 15 days to generate. I have to admit to surprise at the time involved - what s/w are you using to do the generating? We have our own software and crypto library to generate those primes. To create ~500 bit group it takes about 10 seconds. To create ~1000 bit group it takes about minute. Here are ike style primes between 512-1024 where the bits is incremented by 32 every time. These are not proven, but running primo or similar on them shouldn't take that long, so you can do it yourself if you need a proven prime: SOPHIE GERMAIN PRIME SEARCH FIXED 64 bits. INDEX 0: PRIME (bits 512), index = 131, 0.989151 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a439d PRIME (bits 544), index = 11486, 2.32198 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b374a PRIME (bits 576), index = 145480, 17.2525 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df2614c7e PRIME (bits 608), index = 37293, 5.66688 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1c719 PRIME (bits 640), index = 335775, 42.4739 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d56e1e3 PRIME (bits 672), index = 5214, 2.83781 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485c9d3 PRIME (bits 704), index = 65808, 10.8744 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625f7fd5 PRIME (bits 736), index = 229946, 34.0901 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44fc522 PRIME (bits 768), index = 149686, 24.5593 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a63a3620 PRIME (bits 800), index = 168625, 28.5964 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0c01ef66 PRIME (bits 832), index = 13056, 5.62474 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406eaec PRIME (bits 864), index = 173063, 32.9709 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee3b1001 PRIME (bits 896), index = 26718, 9.01863 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a8a0802 PRIME (bits 928), index = 636907, 119.4 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5aea8dbfb PRIME (bits 960), index = 139761, 31.0893 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4d41d6 PRIME (bits 992), index = 15349, 8.29022 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe64928a245 FINISHED (0 primes found in the interval 512 to 1024). -- [EMAIL PROTECTED] SSH Communications Security http://www.ssh.fi/ SSH IPSEC Toolkithttp://www.ssh.fi/ipsec/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe
Re: Proven Primes
tom st denis writes: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a439d What is the benefit of having leading/trailing bits fixed? Those primes are generated using the rules defined in the RFC 2412. As far as I know it doesn't make any form of index calculus attack any harder to apply. High order bits makes classical remainder algorithms faster, and low order bits helps the Mongomery-style algoritms. From the RFC 2412: -- 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 hexadecimal 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 on the discrete logarithm problem. 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 (AKA the subgroup confinement problem). 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.] -- [EMAIL PROTECTED] SSH Communications Security http://www.ssh.fi/ SSH IPSEC Toolkithttp://www.ssh.fi/ipsec/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Proven Primes
Ben Laurie writes: Jack Lloyd wrote: Check RFC 2412, draft-ietf-ipsec-ikev2-05.txt, and draft-ietf-ipsec-ike-modp-groups-05.txt However, I don't seen any primality proof certificates included in the texts. I considered adding the ecpp certificates to draft-ietf-ipsec-ike-modp-groups document, but as the certificates are several magabytes in total, there is no point of adding them to this kind of document (the document would be several hundred pages long consisting only numbers...). RFC 2412 looks good, however, as you say, no certificates are included, nor is it made clear that (p-1)/2 has been proven. I-Ds are less useful to me, since I can't give a long-term reference for them :-( The draft-ietf-ipsec-ike-modp-groups used to have pointer to the ftp site having the certificates (ftp://ftp.ssh.fi/pub/ietf/ecpp-certificates), but that was removed during the IESG review, because url references are not stable enough in general (the ftp://ftp.ssh.fi/pub/ietf/ecpp-certificates site is supposed to be there forever). That site also includes certificates of modp groups from the RFC 2412 (and (p-1)/2 also). I actually just finished finding the 16384 bit Diffie-Helman group with same kind of parameters. It took about 9.5 months to generate. The 12288 bit group took only about 15 days to generate. Proving them will propably take even longer than generating them... -- [EMAIL PROTECTED] SSH Communications Security http://www.ssh.fi/ SSH IPSEC Toolkithttp://www.ssh.fi/ipsec/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Proven Primes
Ben Laurie writes:
I'm looking for a list or lists of sensibly sized proven primes - all
the lists I can find are more interested in records, which are _way_ too
big for cryptographic purposes.
Directory
ftp://ftp.ssh.com/pub/ietf/ecpp-certificates
contains ecpp certificates for IKE primes (768, 1024, 1536, 2048,
3072, 4096, 6144, 8192 bit Diffie-Hellman groups), i.e proven
Sophie-Germain primes.
The ikeprime-.txt is the prime itself and the
ikeprime-xxx{,-primo}-certificate.txt is the certificate for it. I
used two different programs to prove those primes primo and ecpp. The
primo was faster, thus bigger groups are only proven by that.
There is also certificates for (p - 1) / 2, but those are mostly
redundant as most certificates starts with N-1 test, which will
actually proves the (p - 1) / 2 also.
By sensibly sized I mean in the range 512-8192 bits. I'm particularly
after Sophie Germain primes right now, but I guess all primes are of
interest.
--
[EMAIL PROTECTED]
SSH Communications Security http://www.ssh.fi/
SSH IPSEC Toolkithttp://www.ssh.fi/ipsec/
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
