RE: IPS security draft: SRP groups (follow-up)

[vince_cavanna@agilent.com]

Upon re-reading previous email on this subject I noticed the memo from Bernard Aboba showing the procedure Dan Simon  gave to find group generators when the moduli that define the group are of the form p-1=2q, q prime, as is the case for the IKE moduli (primes). 

I also now understand that SRP simply requires a true generator (generates all elements of the group) whereas IKE allows the use of 2 which, though misleadingly called a generator, is not strictly speaking a generator. I thought SRP only allowed a subset of generators which made no sense to me. I now realize SRP requires a true generator and it is IKE that allows a non-generator. 

In any case, using Dan Simon's procedure it is very easy to compute generators for any of the IKE moduli and thus I see no problem using IKE moduli as the primary moduli for SRP. The moduli are certifiably prime and the generators are easy to compute deterministically. I have verified that the generators I computed pass the two tests that Dan Simon gave. If there is interest in pursuing this approach I will compute generators for the rest of the IKE moduli.

Vince
 

|-----Original Message-----
|From: CAVANNA,VICENTE V (A-Roseville,ex1) 
|Sent: Monday, July 15, 2002 2:02 PM
|To: 'ips@ece.cmu.edu'
|Cc: 'tom@arcot.com'; CAVANNA,VICENTE V (A-Roseville,ex1); 
|'Paul Koning';
|'Black_David@emc.com'; THALER,PAT (A-Roseville,ex1); SHEEHY,DAVE
|(A-Americas,unix1)
|Subject: 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 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
|||
||
|