Hi, Thanks for a nice explaination Joshua! 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].
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. - Nilay On Tue, Jul 8, 2008 at 10:40 PM, Joshua Hill <[EMAIL PROTECTED]> wrote: > On Tue, Jul 08, 2008 at 03:27:08PM +0530, Nilay Tripathi wrote: > > Generating 'p' randomly as a safe prime and using 'g' order as 5, the > > keys generated are not consistently passing Sec 5.6.2.4 KAT test. > > It would be a good idea for you to understand why this is, rather than > just iterate until it passes. > > Setting 'g' to 5 won't always work! The expectation of SP800-56 is that > the generator (g) generates the q-ordered multiplicative subgroup of Z_p. > Because p is a safe-prime, the only possible value for q is (p-1)/2 (this > can be otherwise stated as "q is a Sophie Germain prime and p=2q+1"). > Because of this selection for p, the multiplicative group Z_p is very > simple: it has a subgroup of size 2q (the whole group) a subgroup of > size q, a subgroup of size 2 and a subgroup of size 1. > > g=5 is going to be either order q or order 2q. To be consistent with > SP800-56 you need it to be order q. If you run the required public key > validation test on a public key where g is 2q-ordered, then it will > fail roughly half the time. This doesn't mean that you need to just > keep trying until it works, this means that your selection for g wasn't > compliant with SP800-56 in the first place! > > When generating domain parameters you can test to see if you have an > order-q generator by taking g^q mod p and verifying that it equals 1. > If it instead equals (p-1) then you have a 2q-ordered generator; you > should either choose a different generator or choose a different value > for p. > > Josh >
