RE: IPS security draft: SRP groups

[vince_cavanna@agilent.com]

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 whose primality has been proven such as the well known groups in Oakley. Tom Wu told me that would not be a problem provided we found generators for them other than 2 (the generator that is given in Oakley RFC), since 2 in not useful for SRP. 

Using Mathematica I have been able to find other generators for the groups. The 768-bit modulus from IPSEc has 7 as a generator. The 1024-bit prime from IPsec RFC-2539 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.

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 Miller­Rabin
|| 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
||
|