--- lib/Crypto/PublicKey/ElGamal.py +++ lib/Crypto/PublicKey/ElGamal.py @@ -38,39 +38,54 @@ Generate an ElGamal key of length 'bits', using 'randfunc' to get random data and 'progress_func', if present, to display the progress of the key generation. + + The key will be safe for use for both encryption and signature + (although it should be used for **only one** purpose). + """ 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) @@ -118,6 +133,8 @@ 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)