Subject: Re: IPS security draft: SRP groups

From: "Bernard Aboba" <[email-masked]>
Date: Wed, 03 Jul 2002 22:53:28 -0700

In answer to your question, here is a suggestion from Dan Simon for 
determining the appropriate generators for the IKE primes, for use with SRP.

-----Original Message-----
From: Dan Simon
Sent: Friday, June 07, 2002 2:36 PM
To: [email-masked]
Subject: SRP groups

To determine if a given g is a generator of the whole group (a necessary
property for SRP), you need to know the factorization of (p - 1); you
raise the candidate to the power of x for all x which are factors (not
just prime factors) of p - 1, and reject it if you ever get 1 (mod p).  In 
the case of the IKE primes, which are of the form p - 1 = 2q, q prime, just 
test that neither g^2 nor g^q are 1 (mod p); any g that passes that test 
will do.  If the SRP primes were generated randomly, then their predecessors 
(i.e., p - 1) may not be easy to factor; but if they are, then you can 
choose a generator for them as I've described.

                Hope that helps,

                          Dan

---------- Forwarded message ----------
Date: Wed, 10 Apr 2002 21:19:18 -0700
From: Tom Wu <[email-masked]>
To: Bernard Aboba <[email-masked]>
Cc: [email-masked]
Subject: Re: SRP groups
Bernard,

I generated the non-IKE primes randomly.  I did not go through the full
process of generating numbers with optimized forms, nor did I attempt to 
prove them prime using a rigorous test.  This was primarily because, at the 
time I generated them, those prepackged groups were intended mainly as a 
timesaver for people installing the SRP distribution; I expected many admins 
to generate their own groups, using the Open Source tconf tool in the SRP 
distribution, for their own peace of mind.

The secondary reason was that the requirements/constraints for SRP
groups are not quite the same as the IKE groups.  The IKE groups have
the prime as 7 (mod 8) because of the lower-bits optimization, and g =
2, which can be faster with some bignum implementations.  This means
that g generates the group of size (p-1)/2, whereas SRP requires that g
generate the largest group of size (p-1), i.e. a primitive root.

That said, I'd have no problem with re-using the IKE primes as the prime for 
SRP groups, using a different "g" such that it is a primitive root. That's 
already been done for bitlengths 768 and 1024.

Tom

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos: 
http://photos.msn.com/support/worldwide.aspx

---

From: Paul Koning <[email-masked]>
Date: Fri, 5 Jul 2002 14:49:26 -0400

> determining the appropriate generators for the IKE primes, for use with SRP.

Ok.  I didn't know that but I probably would have learned it if I had
done the necessary reading about groups and generators.  But the point
of my question wasn't "is it possible to compute g" but rather "how
about supplying g in the spec" (since the g=2 from IKE is not
appropriate).   It seems a bit redundant for everyone to repeat the
search for a suitable g...

So what's the story about unlisted groups?  Is an implementation that
accepts only the groups listed in appendix A, but not any "locally
generated" ones, a compliant implementation?  If not, why not?

> distribution, for their own peace of mind.

Ok, so now I'm confused.  Dan says "you need to know the factorization
of p-1" but presumably that is not known for a randomly chosen p.  

> already been done for bitlengths 768 and 1024.

That being the case, it would be good for those values for g to be
listed in the spec.

       paul