On Wed, Jul 09, 2008 at 05:53:42PM +0530, Nilay Tripathi wrote:
> As a solution, since g is supposed to fall in the multiplicative group of
> order q OR 2q, the g can be therefore adjusted such that it satisfies either
> of [g^q mod p = 1] or [g^2q mod p = 1].
When p is a safe prime, a few things happen that make this discussion
simpler.
As long as you don't choose g=1 or g=p-1, you're going to get a generator
of either the q-ordered or 2q-ordered group.
All elements in the multiplicative group are in the 2q-ordered group by
definition (the 2q-ordered group is the full group!). As such, _all_
selections for g (even 1 and p-1) will satisfy [g^(2q) mod p = 1].
The public key validation routine required by NIST SP800-56 is
effectively a test to make sure that the public key resides within the
q-ordered group. If it does not, that test fails. If you've chosen g
to generate the q-ordered group, all public keys will automatically be
in the q-ordered group.
More to the point, if you haven't selected g such that it generates the
q-ordered group, you're not in compliance with NIST SP800-56. If you're
required to be compliant with that document (because of, for example,
a FIPS 140 validation), that will be a problem.
> Since that can be found in a deterministic way, setting up proper 'g' on a
> randomly generated safe prime 'p' is easier and predictable. And it passes
> the test in one go.
I don't understand. If you only care that the public key is either
in the q-ordered group or the 2q-ordered group and not in the 1 or 2
ordered group, then don't bother with a test using modular exponentiation.
A simple range test will suffice: make sure 1<y<p-1, and you're done.
That's clearly not what NIST SP800-56 requires, but that's fine from a
security perspective. If you have be be NIST SP800-56 compliant, then
you are required to use a q-ordered element for g, and that will also
make it so that you consistently pass the public key validation test as
specified in that document.
Josh
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [EMAIL PROTECTED]
