Comment 5 for bug 985164

Legrandin (gooksankoo) wrote :

> Do you know if there is a way to take an existing key and find out whether it has this problem? (Even better, to compute the order of the sub-group?)

One way is to factor p-1 and find all its divisors. The divisors are also all the possible orders a sub-group of Zp can have.
The generator g is safe (with respect to this problem) if g^d mod p is not 1 for all divisors other than p-1.
That may not be enough though: when the key is used for signing, one should also check that g and g^{-1} don't divide p-1 (see patch). Those are at least the additional contraints I have found so far for the key...

> Also, given that this is a *random* sub-group, does this actually help an attacker? I'm going to fix this anyway, but I want to get an understanding of how bad this is. I don't know much about ElGamal encryption.

g is also made public, so that would be only relevant if the attack was based on some precomputation I think. The main problem I see is that the signature space (when the key is used for signing) or the public key space (when the key is used for encryption) may be greatly reduced from log(p) bits down to up 1 bit (worst case if the order of g is 2). That's already bad enough, but it could be that such fact may also be used to work out the private key (which the RFC you have found seem to imply).

> Is it okay if I just merge your entire tree (up to 6f312637208cc70b231892109564e2aebc92728a)?

I can submit a complete/tested/polished set of changes in one week time. As you can guess, the changes are mostly about improving documentation of the public key module: right now, qnew and maybe pycrypt.rst are still missing. I run into this problem by reviewing the Elgamal code.