Subject: RE: IPS security draft: SRP groups (resend)

From: [email-masked]
Date: Mon, 15 Jul 2002 15:02:18 -0600

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: [email-masked]; [email-masked]; [email-masked]
|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:[email-masked]]
||Sent: Friday, July 12, 2002 7:15 AM
||To: [email-masked]
||Cc: [email-masked]; [email-masked]; [email-masked]
||Subject: RE: IPS security draft: SRP groups
||
||
||>>>>> "vince" == vince cavanna <[email-masked]> 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
||
|

---

From: [email-masked]
Date: Mon, 15 Jul 2002 19:25:13 -0400

Vince,

> 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).

Tom's already posed the required generators for the IKE groups
to the list.  In addition, Tero Kivinen was in the process of
proving the primality of Tom's SRP primes last night.  With
luck we'll have a post to the list with pointers to the proof
certificates soon.

Thanks,
--David
---------------------------------------------------
David L. Black, Senior Technologist
EMC Corporation, 42 South St., Hopkinton, MA  01748
+1 (508) 249-6449            FAX: +1 (508) 497-8018
[email-masked]       Mobile: +1 (978) 394-7754
---------------------------------------------------

---

From: [email-masked]
Date: Mon, 15 Jul 2002 18:03:53 -0600

Hi David,
Sounds good, but I don't understand the motivation to use any primes other than those from IKE when we know those primes are certifiable and that a generator suitable for SRP can be easily and deterministically determined. Is there value in giving the user multiple choices for primes of a given size?
Vince 

|-----Original Message-----
|From: [email-masked] [mailto:[email-masked]]
|Sent: Monday, July 15, 2002 4:25 PM
|To: [email-masked]; [email-masked]
|Subject: RE: IPS security draft: SRP groups (resend)
|
|
|Vince,
|
|> 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).
|
|Tom's already posed the required generators for the IKE groups
|to the list.  In addition, Tero Kivinen was in the process of
|proving the primality of Tom's SRP primes last night.  With
|luck we'll have a post to the list with pointers to the proof
|certificates soon.
|
|Thanks,
|--David
|---------------------------------------------------
|David L. Black, Senior Technologist
|EMC Corporation, 42 South St., Hopkinton, MA  01748
|+1 (508) 249-6449            FAX: +1 (508) 497-8018
[email-masked]       Mobile: +1 (978) 394-7754
|---------------------------------------------------
|