diff options
author | Legrandin <gooksankoo@hoiptorrow.mailexpire.com> | 2012-04-18 23:13:08 +0200 |
---|---|---|
committer | Legrandin <gooksankoo@hoiptorrow.mailexpire.com> | 2012-04-18 23:13:08 +0200 |
commit | 9f912f13df99ad3421eff360d6a62d7dbec755c2 (patch) | |
tree | 056bf1fe1a0b9eca4774663072fac392f98c0644 | |
parent | c8e21380a6059a56bd88267a5e744ddd8badfe66 (diff) | |
download | pycrypto-9f912f13df99ad3421eff360d6a62d7dbec755c2.tar.gz |
Fix to bug #985164 (ElGamal key generation). Fix to missing range check in signature verification.
-rw-r--r-- | lib/Crypto/PublicKey/ElGamal.py | 64 |
1 files changed, 40 insertions, 24 deletions
diff --git a/lib/Crypto/PublicKey/ElGamal.py b/lib/Crypto/PublicKey/ElGamal.py index 2b4d511..a9efe75 100644 --- a/lib/Crypto/PublicKey/ElGamal.py +++ b/lib/Crypto/PublicKey/ElGamal.py @@ -110,6 +110,9 @@ class error (Exception): def generate(bits, randfunc, progress_func=None): """Randomly generate a fresh, new ElGamal key. + The key will be safe for use for both encryption and signature + (although it should be used for **only one** purpose). + :Parameters: bits : int Key length, or size (in bits) of the modulus *p*. @@ -131,37 +134,48 @@ def generate(bits, randfunc, progress_func=None): :Return: An ElGamal key object (`ElGamalobj`). """ obj=ElGamalobj() - # Generate prime p + # Generate a safe prime p + # See Algorithm 4.86 in Handbook of Applied Cryptography if progress_func: progress_func('p\n') - obj.p=bignum(getPrime(bits, randfunc)) - # Generate random number g + while 1: + q = bignum(getPrime(bits-1, randfunc)) + obj.p = 2*q+1 + if number.isPrime(obj.p, randfunc=randfunc): + break + # Generate generator g + # See Algorithm 4.80 in Handbook of Applied Cryptography + # Note that the order of the group is n=p-1=2q, where q is prime if progress_func: progress_func('g\n') - size=bits-1-(ord(randfunc(1)) & 63) # g will be from 1--64 bits smaller than p - if size<1: - size=bits-1 - while (1): - obj.g=bignum(getPrime(size, randfunc)) - if obj.g < obj.p: + while 1: + # We must avoid g=2 because of Bleichenbacher's attack described + # in "Generating ElGamal signatures without knowning the secret key", + # 1996 + # + obj.g = number.getRandomRange(3, obj.p, randfunc) + safe = 1 + if pow(obj.g, 2, obj.p)==1: + safe=0 + if safe and pow(obj.g, q, obj.p)==1: + safe=0 + # Discard g if it divides p-1 because of the attack described + # in Note 11.67 (iii) in HAC + if safe and divmod(obj.p-1, obj.g)[1]==0: + safe=0 + # g^{-1} must not divide p-1 because of Khadir's attack + # described in "Conditions of the generator for forging ElGamal + # signature", 2011 + ginv = number.inverse(obj.g, obj.p) + if safe and divmod(obj.p-1, ginv)[1]==0: + safe=0 + if safe: break - size=(size+1) % bits - if size==0: - size=4 - # Generate random number x + # Generate private key x if progress_func: progress_func('x\n') - while (1): - size=bits-1-ord(randfunc(1)) # x will be from 1 to 256 bits smaller than p - if size>2: - break - while (1): - obj.x=bignum(getPrime(size, randfunc)) - if obj.x < obj.p: - break - size = (size+1) % bits - if size==0: - size=4 + obj.x=number.getRandomRange(2, obj.p-1, randfunc) + # Generate public key y if progress_func: progress_func('y\n') obj.y = pow(obj.g, obj.x, obj.p) @@ -326,6 +340,8 @@ class ElGamalobj(pubkey): return (a, b) def _verify(self, M, sig): + if sig[0]<1 or sig[0]>p-1: + return 0 v1=pow(self.y, sig[0], self.p) v1=(v1*pow(sig[0], sig[1], self.p)) % self.p v2=pow(self.g, M, self.p) |