|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] RE: IPS security draft: SRP groups (resend)I previously hit the Send button when I had meant to hit the Save button. This is the message I had intended to send. I was unsuccessful at getting Mathematica to prove the primality of the SRP moduli. If we cannot prove the primality of our chosen moduli I thought why not use moduli, such as the well known groups from RFC 2412, whose primality has been proven. Tom Wu told me that would not be a problem provided we found generators other than 2 (the generator that is given in RFC 2412), because 2 in not useful (for these moduli) in SRP (I don't know why such is the case). Using Mathematica I have been able to find other generators for a couple of the well known groups. The 768-bit modulus from RFC 2412 has 7 as a generator. The 1024-bit prime from RFC 2412 has 5 as a generator. I have used the PrimitiveRoot function in the NumberTheory package of Mathematica. As a simple (incomplete) verification I have raised the generator to the power equal to one less than the moduli and have gotten an answer that is congruent to 1 as would be expected for any generator. What I can't tell from that simple verification is if I also get a number congruent to 1 when I raise the generator to some lower power - which would mean the "generator" is not really a generator. Vince |-----Original Message----- |From: CAVANNA,VICENTE V (A-Roseville,ex1) |Sent: Friday, July 12, 2002 9:11 AM |To: 'Paul Koning'; CAVANNA,VICENTE V (A-Roseville,ex1) |Cc: Black_David@emc.com; ips@ece.cmu.edu; tom@arcot.com |Subject: RE: IPS security draft: SRP groups | | |Hi Paul, | |I suspected as much, since I don't have a supercomputer on my |desktop. Mathematica apparently also has the capability to |perform a mathematical proof of primality and to produce a |"certificate" using which Mathematica's results may be |independently and easily verified. When I attempted to perform |the proof on the smallest modulus (the one with 768 bits) my |computer was rendered useless for over 20 minutes which just |happened to be my threshold of tolerance for this morning. I |will try again when I leave the office tonight and if I get |any useful results I will look deeper into the method. | |Vince | | | ||-----Original Message----- ||From: Paul Koning [mailto:ni1d@arrl.net] ||Sent: Friday, July 12, 2002 7:15 AM ||To: vince_cavanna@agilent.com ||Cc: Black_David@emc.com; ips@ece.cmu.edu; tom@arcot.com ||Subject: RE: IPS security draft: SRP groups || || ||>>>>> "vince" == vince cavanna <vince_cavanna@agilent.com> writes: || || vince> Hi David, I can't prove so, but Mathematica from Wolfram || vince> certifies as prime (in a matter seconds) all five moduli || vince> specified in the iSCSI security draft for use in SRP! I used || vince> the PrimeQ built-in function. PrimeQ first tests for || vince> divisibility using small primes, then uses the MillerRabin || vince> strong pseudoprime test base 2 and base 3, and then uses a || vince> Lucas test. I have not explored the nature of these tests. || ||Miller-Rabin is a probabilistic test. As for "Lucas" -- the Handbook ||of Applied Cryptography lists "Lucas-Lehmer primality test for ||Mersenne numbers". That suggests that this test has no meaning for ||numbers that aren't Mersenne numbers (such as randomly chosen ||numbers). || ||So I think you have a probabilistic primality test here, similar to ||what Tom did. That's certainly useful confirmation, but it doesn't ||sound like we have the primality proofs yet. (Unfortunately, HAC is ||not sufficiently helpful in pointing to an algorithm to to so...) || || paul || |
Home Last updated: Wed Jul 17 22:18:57 2002 11372 messages in chronological order |