Re: Proven Primes
Tom St Denis writes: > What is the benefit of having leading/trailing bits fixed? As far as I > know it doesn't make any form of index calculus attack any harder to > apply. The Handbook of Applied Cryptography, http://www.cacr.math.uwaterloo.ca/hac/, has a chapter on efficient implementations which might provide some insight. You can take advantage of the left FFF's by using the modular reduction algorithm described in section 14.3.4 of the HAC. This is good for the case where the modulus is slightly less than a power of 2. Or you can take advantage of the right FFF's by using Montgomery exponentiation, described in section 14.3.2 of the HAC and also in algorithm 14.94. Montgomery multiplication uses a value m' = - m^(-1) mod b, where m is the modulus and b is the bignum base, typically 2^32 or 2^64. With these moduli m' becomes 1, simplifying the calculations. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
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
On Tuesday, Mar 11, 2003, at 11:28 US/Eastern, tom st denis wrote: --- Tero Kivinen <[EMAIL PROTECTED]> wrote: SOPHIE GERMAIN PRIME SEARCH FIXED 64 bits. INDEX 0: PRIME (bits 512), index = 131, 0.989151 seconds: 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bb ea63b139b22514a08798e3404ddef9519b3cd3a439d What is the benefit of having leading/trailing bits fixed? As far as I know it doesn't make any form of index calculus attack any harder to apply. Performance. See RFC 2412, Appendix E. http://www.ietf.org/rfc/rfc2412.txt -J - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
- Original Message - From: "tom st denis" <[EMAIL PROTECTED]> To: "Cryptography" <[EMAIL PROTECTED]> Sent: Tuesday, March 11, 2003 11:28 AM Subject: Re: Proven Primes > > --- Tero Kivinen <[EMAIL PROTECTED]> wrote: > > SOPHIE GERMAIN PRIME SEARCH > > FIXED 64 bits. > > INDEX 0: > > PRIME (bits 512), index = 131, 0.989151 seconds: > > > 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b 139b22514a08798e3404ddef9519b3cd3a439d > > What is the benefit of having leading/trailing bits fixed? As far as I > know it doesn't make any form of index calculus attack any harder to > apply. No, but you can speed up modulo multiplication. The OAKLEY RFC says: 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. At one point in time some of my colleagues got the optimization with the high order bits set to 1 in C code going on very well, I don`t remember if we implemented the optimization with the low order bits set to 1. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
--- Tero Kivinen <[EMAIL PROTECTED]> wrote: > SOPHIE GERMAIN PRIME SEARCH > FIXED 64 bits. > INDEX 0: > PRIME (bits 512), index = 131, 0.989151 seconds: > 0xc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a439d What is the benefit of having leading/trailing bits fixed? As far as I know it doesn't make any form of index calculus attack any harder to apply. Tom __ Do you Yahoo!? Yahoo! Web Hosting - establish your business online http://webhosting.yahoo.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
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 "unsubs
Re: Proven Primes
Tero Kivinen wrote: 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). Thanks. 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? Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - 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]
Re: Proven Primes
Tom St Denis <[EMAIL PROTECTED]> has a program that constructs provable primes, by bootstrapping them from smaller proven primes. The trouble is that his stuff is off the air at the moment. You might write to him, though. It's pretty quick, IIRC. Greg. At 06:45 PM 3/8/2003 +, Ben Laurie wrote: Jack Lloyd wrote: I believe the IPSec primes had been proven. All are SG primes with a g=2 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. 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 :-( Thanks! Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Jack Lloyd wrote: I believe the IPSec primes had been proven. All are SG primes with a g=2 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. 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 :-( Thanks! Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
> I thought that finding them was the hard part, and verifying one once found > was relatively easy. I used the probable prime test in the Java BigInteger > package. It sounds like, from some of the list traffic, that there are > better tests. Chapter 4 of the HAC gives a good introduction to all of this. http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf There are probabilistic primality tests (e.g. Miller-Rabin), there are primality proving algorithms (e.g. Jacoby Sum Test, ECPP), some of which give a certificate of primality that can be verified using a different algorithm. Some of the tests work on integers of special forms (e.g. Mersenne numbers), others work on all integers. There are also algorithms that generate integers that are guaranteed to be prime (e.g. Maurer's algorithm), these are not tests... --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Bill Frantz wrote:
>I guess I'm dumb, but how to you verify a proof of Sophie Germain primeness
>with less effort than to run the tests yourself?
There are ways to prove that p is prime so that the receiver
can verify the proof more easily than it would be to construct
a proof. The verification process is deterministic (there is
no chance of error), unlike probabilistic primality tests.
Here's a simple method, due to Pratt. It turns out that p is
prime if and only if the multiplicative group (Z/pZ)^* of integers
modulo p is cyclic. To show that the group is cyclic, we can
give a generator g. To show that g is a generator, we can factor
p-1 and show that g^{(p-1)/q} != 1 (mod p) for all prime q that
divide p-1. Thus, the proof of primality for p will be
proof(p) = (g, q_1, proof(q_1), q_2, proof(q_2), ...)
where q_1, q_2, ... is the list of prime factors of p and where
proof(q_i) is a recursive proof of primality for q_i.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
And the proof? Sorry, an exercise for the student. :-) I thought that finding them was the hard part, and verifying one once found was relatively easy. I used the probable prime test in the Java BigInteger package. It sounds like, from some of the list traffic, that there are better tests. Well, it's harder in that to find a prime or SG prime, you need to try the probable prime test on bunch of candidates until one passes. With the Java BigInteger probable prime package, can you specify what probability it uses for primality (i.e. the probability is 2**-N or 4**-N, what's N?) - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
At 10:04 AM 3/7/2003 +, Ben Laurie wrote: Indeed. The commonly used one is ECPP which uses elliptic curves cunningly to not only prove primality, but to produce a certificate which can be quickly verified. Probabilistic prime tests are just that - probable. ECPP actually proves it. Does anyone, in practice, care about the distinction, if the probability that the prime test has failed can be proved to be far less than the chance that a hardware failure has caused a false positive ECPP test? To restate the question: all calculation methods have a certain possibility of failure, whether due to human or mechanical error, however minute that possibility may be. If I can use a probabalistic primality test to reduce the possibility of error due to algorithm failure to a point that it's well below the possibility of error due to hardware failure, what's the practical difference? Thanks, - Tim - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
At 2:04 AM -0800 3/7/03, Ben Laurie wrote: >BTW, a terminology nit - a Sophie Germain prime is one such that p and >2p+1 are prime - I'll be that what you've given me is one such that p >and (p-1)/2 are prime, right? Yes. And I do know that the Sophie Germain prime is the smaller of the two related primes. Cheers - Bill - Bill Frantz | Due process for all| Periwinkle -- Consulting (408)356-8506 | used to be the | 16345 Englewood Ave. [EMAIL PROTECTED] | American way. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Bill Frantz wrote:
At 9:21 PM -0800 3/6/03, Ben Laurie wrote:
Bill Frantz wrote:
At 3:47 AM -0800 3/6/03, Ben Laurie wrote:
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.
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.
Having set a computer to the problem of coming up with a Sophie Germain
prime for the E startup protocol (Diffie-Hellman), I offer you:
static final BigInteger g = new BigInteger("2");
static final BigInteger modulus =
new
BigInteger("11973791477546250983817043765044391637751157152328012"
+
"72278994477192940843207042535379780702841268263028"
+
"59486033998465467188646855777933154987304015680716"
+
"74391647223805124273032053960564348124852668624831"
+
"01273341734490560148744399254916528366159159380290"
+
"29782321539388697349613396698017627677439533107752"
+ "978203");
And the proof?
Sorry, an exercise for the student. :-)
I thought that finding them was the hard part, and verifying one once found
was relatively easy. I used the probable prime test in the Java BigInteger
package. It sounds like, from some of the list traffic, that there are
better tests.
Indeed. The commonly used one is ECPP which uses elliptic curves
cunningly to not only prove primality, but to produce a certificate
which can be quickly verified.
Probabilistic prime tests are just that - probable. ECPP actually proves it.
I guess I'm dumb, but how to you verify a proof of Sophie Germain primeness
with less effort than to run the tests yourself?
Running the probabalistic tests can only prove that it's composite -
they can never prove primality.
BTW, a terminology nit - a Sophie Germain prime is one such that p and
2p+1 are prime - I'll be that what you've given me is one such that p
and (p-1)/2 are prime, right?
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
At 9:21 PM -0800 3/6/03, Ben Laurie wrote:
>Bill Frantz wrote:
>> At 3:47 AM -0800 3/6/03, Ben Laurie wrote:
>>
>>>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.
>>>
>>>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.
>>
>>
>> Having set a computer to the problem of coming up with a Sophie Germain
>> prime for the E startup protocol (Diffie-Hellman), I offer you:
>>
>> static final BigInteger g = new BigInteger("2");
>> static final BigInteger modulus =
>> new
>>BigInteger("11973791477546250983817043765044391637751157152328012"
>> +
>>"72278994477192940843207042535379780702841268263028"
>> +
>>"59486033998465467188646855777933154987304015680716"
>> +
>>"74391647223805124273032053960564348124852668624831"
>> +
>>"01273341734490560148744399254916528366159159380290"
>> +
>>"29782321539388697349613396698017627677439533107752"
>> + "978203");
>
>And the proof?
Sorry, an exercise for the student. :-)
I thought that finding them was the hard part, and verifying one once found
was relatively easy. I used the probable prime test in the Java BigInteger
package. It sounds like, from some of the list traffic, that there are
better tests.
I guess I'm dumb, but how to you verify a proof of Sophie Germain primeness
with less effort than to run the tests yourself?
Cheers - Bill
-
Bill Frantz | Due process for all| Periwinkle -- Consulting
(408)356-8506 | used to be the | 16345 Englewood Ave.
[EMAIL PROTECTED] | American way. | Los Gatos, CA 95032, USA
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Bill Frantz wrote:
At 3:47 AM -0800 3/6/03, Ben Laurie wrote:
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.
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.
Having set a computer to the problem of coming up with a Sophie Germain
prime for the E startup protocol (Diffie-Hellman), I offer you:
static final BigInteger g = new BigInteger("2");
static final BigInteger modulus =
new BigInteger("11973791477546250983817043765044391637751157152328012"
+ "72278994477192940843207042535379780702841268263028"
+ "59486033998465467188646855777933154987304015680716"
+ "74391647223805124273032053960564348124852668624831"
+ "01273341734490560148744399254916528366159159380290"
+ "29782321539388697349613396698017627677439533107752"
+ "978203");
And the proof?
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
At 3:47 AM -0800 3/6/03, Ben Laurie wrote:
>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.
>
>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.
Having set a computer to the problem of coming up with a Sophie Germain
prime for the E startup protocol (Diffie-Hellman), I offer you:
static final BigInteger g = new BigInteger("2");
static final BigInteger modulus =
new BigInteger("11973791477546250983817043765044391637751157152328012"
+ "72278994477192940843207042535379780702841268263028"
+ "59486033998465467188646855777933154987304015680716"
+ "74391647223805124273032053960564348124852668624831"
+ "01273341734490560148744399254916528366159159380290"
+ "29782321539388697349613396698017627677439533107752"
+ "978203");
Cheers - Bill
-
Bill Frantz | Due process for all| Periwinkle -- Consulting
(408)356-8506 | used to be the | 16345 Englewood Ave.
[EMAIL PROTECTED] | American way. | Los Gatos, CA 95032, USA
-
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]
Re: Proven Primes
- Original Message - From: "Ben Laurie" <[EMAIL PROTECTED]> To: "Anton Stiglic" <[EMAIL PROTECTED]> > [Talking about the ECPP package...] > I'm not convinced any of those binaries are going to run on my system > (which is FreeBSD), and anyway, if I'm going to use a binary to do ECPP > I may as well shove it through Mathematica - much prettier UI :-) > > Is their no free implementation of ECPP? Is there at least a free verifier? It's been a while since I tried it, I don't remember which platform and OS I used (a pentium with some sort of Linux) but I know that I didn't have any problems using it. I think that ECPP comes with a Maple certificate verifier, which might be what you are looking for. I think you can also convert certificates to Mathematica format. So once you have these certificates of primality it's easy to verify them. But I haven't tried any of those features... --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
Anton Stiglic wrote: - Original Message - From: "Ben Laurie" <[EMAIL PROTECTED]> To: "Cryptography" <[EMAIL PROTECTED]> Sent: Thursday, March 06, 2003 6:47 AM Subject: Proven Primes 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. I'm not aware of such a list. If you can't find any you can generate the list yourself using ECPP (Elliptic Curve Primality Proving), an implementation of which is available here http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html The result of ECPP is guaranteed (no probability of error), and provides a certificate of primality for integers that are proven to be prime. A competing algorithm is the Jacobi Sums test, but it is much more complicated, so implementation errors are not to be disregarded, with ECPP the verification of a primality certificate is simple to implement, so you can make sure that there were no errors in the implementation of the proving algorithm. I'm not convinced any of those binaries are going to run on my system (which is FreeBSD), and anyway, if I'm going to use a binary to do ECPP I may as well shove it through Mathematica - much prettier UI :-) Is their no free implementation of ECPP? Is there at least a free verifier? There is also the new algorithm by Agrawal, Kayal and Saxena, but I don't believe that it is efficient in practice for the sizes of integers you are looking at. Also note that if you assume the Extended Riemann Hypothesis (ERH) to be true, you can use the Miller-Rabin algorithm in a deterministic fashion in polynomial time with no probability error. Oh? The ECPP package is easy to use and fast. The site gives benchmarks for proving 512-bit primes: Pentium III (450MHz)4.4 sec Solaris 5.7 9.5 sec Alpha EV56 (500MHz) 4 sec I suggest you generate potential Sophie Germain primes q using your favorite library (I use OpenSSL for example) and then use the ECPP package to verify that in fact both q and 2q + 1 are really prime. Sounds like a plan. Thanks very much for the info. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
I believe the IPSec primes had been proven. All are SG primes with a g=2 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. On Thu, 6 Mar 2003, Ben Laurie wrote: > 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. > > 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. > > Cheers, > > Ben. > > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Proven Primes
- Original Message - From: "Ben Laurie" <[EMAIL PROTECTED]> To: "Cryptography" <[EMAIL PROTECTED]> Sent: Thursday, March 06, 2003 6:47 AM Subject: Proven Primes > 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. I'm not aware of such a list. If you can't find any you can generate the list yourself using ECPP (Elliptic Curve Primality Proving), an implementation of which is available here http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html The result of ECPP is guaranteed (no probability of error), and provides a certificate of primality for integers that are proven to be prime. A competing algorithm is the Jacobi Sums test, but it is much more complicated, so implementation errors are not to be disregarded, with ECPP the verification of a primality certificate is simple to implement, so you can make sure that there were no errors in the implementation of the proving algorithm. There is also the new algorithm by Agrawal, Kayal and Saxena, but I don't believe that it is efficient in practice for the sizes of integers you are looking at. Also note that if you assume the Extended Riemann Hypothesis (ERH) to be true, you can use the Miller-Rabin algorithm in a deterministic fashion in polynomial time with no probability error. The ECPP package is easy to use and fast. The site gives benchmarks for proving 512-bit primes: Pentium III (450MHz)4.4 sec Solaris 5.7 9.5 sec Alpha EV56 (500MHz) 4 sec I suggest you generate potential Sophie Germain primes q using your favorite library (I use OpenSSL for example) and then use the ECPP package to verify that in fact both q and 2q + 1 are really prime. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
ENC: Proven Primes
> -Mensagem original- > De: Ben Laurie [mailto:[EMAIL PROTECTED] > Enviada em: quinta-feira, 6 de março de 2003 08:47 > Para: Cryptography > Assunto: Proven Primes > > 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. > > 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. You might look at the IKE groups The Internet Key Exchange (IKE) http://www.ietf.org/rfc/rfc2409.txt "More MODP Diffie-Hellman groups for IKE" http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ike-modp-groups-05. txt Regards, Mads - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Proven Primes
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. 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. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
