diff options
Diffstat (limited to 'frozen_deps/Crypto/PublicKey/ElGamal.py')
| -rw-r--r-- | frozen_deps/Crypto/PublicKey/ElGamal.py | 373 |
1 files changed, 0 insertions, 373 deletions
diff --git a/frozen_deps/Crypto/PublicKey/ElGamal.py b/frozen_deps/Crypto/PublicKey/ElGamal.py deleted file mode 100644 index 99af71c..0000000 --- a/frozen_deps/Crypto/PublicKey/ElGamal.py +++ /dev/null @@ -1,373 +0,0 @@ -# -# ElGamal.py : ElGamal encryption/decryption and signatures -# -# Part of the Python Cryptography Toolkit -# -# Originally written by: A.M. Kuchling -# -# =================================================================== -# The contents of this file are dedicated to the public domain. To -# the extent that dedication to the public domain is not available, -# everyone is granted a worldwide, perpetual, royalty-free, -# non-exclusive license to exercise all rights associated with the -# contents of this file for any purpose whatsoever. -# No rights are reserved. -# -# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS -# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN -# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN -# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -# SOFTWARE. -# =================================================================== - -"""ElGamal public-key algorithm (randomized encryption and signature). - -Signature algorithm -------------------- -The security of the ElGamal signature scheme is based (like DSA) on the discrete -logarithm problem (DLP_). Given a cyclic group, a generator *g*, -and an element *h*, it is hard to find an integer *x* such that *g^x = h*. - -The group is the largest multiplicative sub-group of the integers modulo *p*, -with *p* prime. -The signer holds a value *x* (*0<x<p-1*) as private key, and its public -key (*y* where *y=g^x mod p*) is distributed. - -The ElGamal signature is twice as big as *p*. - -Encryption algorithm --------------------- -The security of the ElGamal encryption scheme is based on the computational -Diffie-Hellman problem (CDH_). Given a cyclic group, a generator *g*, -and two integers *a* and *b*, it is difficult to find -the element *g^{ab}* when only *g^a* and *g^b* are known, and not *a* and *b*. - -As before, the group is the largest multiplicative sub-group of the integers -modulo *p*, with *p* prime. -The receiver holds a value *a* (*0<a<p-1*) as private key, and its public key -(*b* where *b*=g^a*) is given to the sender. - -The ElGamal ciphertext is twice as big as *p*. - -Domain parameters ------------------ -For both signature and encryption schemes, the values *(p,g)* are called -*domain parameters*. -They are not sensitive but must be distributed to all parties (senders and -receivers). -Different signers can share the same domain parameters, as can -different recipients of encrypted messages. - -Security --------- -Both DLP and CDH problem are believed to be difficult, and they have been proved -such (and therefore secure) for more than 30 years. - -The cryptographic strength is linked to the magnitude of *p*. -In 2012, a sufficient size for *p* is deemed to be 2048 bits. -For more information, see the most recent ECRYPT_ report. - -Even though ElGamal algorithms are in theory reasonably secure for new designs, -in practice there are no real good reasons for using them. -The signature is four times larger than the equivalent DSA, and the ciphertext -is two times larger than the equivalent RSA. - -Functionality -------------- -This module provides facilities for generating new ElGamal keys and for constructing -them from known components. ElGamal keys allows you to perform basic signing, -verification, encryption, and decryption. - - >>> from Crypto import Random - >>> from Crypto.Random import random - >>> from Crypto.PublicKey import ElGamal - >>> from Crypto.Util.number import GCD - >>> from Crypto.Hash import SHA - >>> - >>> message = "Hello" - >>> key = ElGamal.generate(1024, Random.new().read) - >>> h = SHA.new(message).digest() - >>> while 1: - >>> k = random.StrongRandom().randint(1,key.p-1) - >>> if GCD(k,key.p-1)==1: break - >>> sig = key.sign(h,k) - >>> ... - >>> if key.verify(h,sig): - >>> print "OK" - >>> else: - >>> print "Incorrect signature" - -.. _DLP: http://www.cosic.esat.kuleuven.be/publications/talk-78.pdf -.. _CDH: http://en.wikipedia.org/wiki/Computational_Diffie%E2%80%93Hellman_assumption -.. _ECRYPT: http://www.ecrypt.eu.org/documents/D.SPA.17.pdf -""" - -__revision__ = "$Id$" - -__all__ = ['generate', 'construct', 'error', 'ElGamalobj'] - -from Crypto.PublicKey.pubkey import * -from Crypto.Util import number - -class error (Exception): - pass - -# Generate an ElGamal key with N bits -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*. - Recommended value is 2048. - randfunc : callable - Random number generation function; it should accept - a single integer N and return a string of random data - N bytes long. - progress_func : callable - Optional function that will be called with a short string - containing the key parameter currently being generated; - it's useful for interactive applications where a user is - waiting for a key to be generated. - - :attention: You should always use a cryptographically secure random number generator, - such as the one defined in the ``Crypto.Random`` module; **don't** just use the - current time and the ``random`` module. - - :Return: An ElGamal key object (`ElGamalobj`). - """ - obj=ElGamalobj() - # Generate a safe prime p - # See Algorithm 4.86 in Handbook of Applied Cryptography - if progress_func: - progress_func('p\n') - 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') - 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 - # Generate private key x - if progress_func: - progress_func('x\n') - 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) - return obj - -def construct(tup): - """Construct an ElGamal key from a tuple of valid ElGamal components. - - The modulus *p* must be a prime. - - The following conditions must apply: - - - 1 < g < p-1 - - g^{p-1} = 1 mod p - - 1 < x < p-1 - - g^x = y mod p - - :Parameters: - tup : tuple - A tuple of long integers, with 3 or 4 items - in the following order: - - 1. Modulus (*p*). - 2. Generator (*g*). - 3. Public key (*y*). - 4. Private key (*x*). Optional. - - :Return: An ElGamal key object (`ElGamalobj`). - """ - - obj=ElGamalobj() - if len(tup) not in [3,4]: - raise ValueError('argument for construct() wrong length') - for i in range(len(tup)): - field = obj.keydata[i] - setattr(obj, field, tup[i]) - return obj - -class ElGamalobj(pubkey): - """Class defining an ElGamal key. - - :undocumented: __getstate__, __setstate__, __repr__, __getattr__ - """ - - #: Dictionary of ElGamal parameters. - #: - #: A public key will only have the following entries: - #: - #: - **y**, the public key. - #: - **g**, the generator. - #: - **p**, the modulus. - #: - #: A private key will also have: - #: - #: - **x**, the private key. - keydata=['p', 'g', 'y', 'x'] - - def encrypt(self, plaintext, K): - """Encrypt a piece of data with ElGamal. - - :Parameter plaintext: The piece of data to encrypt with ElGamal. - It must be numerically smaller than the module (*p*). - :Type plaintext: byte string or long - - :Parameter K: A secret number, chosen randomly in the closed - range *[1,p-2]*. - :Type K: long (recommended) or byte string (not recommended) - - :Return: A tuple with two items. Each item is of the same type as the - plaintext (string or long). - - :attention: selection of *K* is crucial for security. Generating a - random number larger than *p-1* and taking the modulus by *p-1* is - **not** secure, since smaller values will occur more frequently. - Generating a random number systematically smaller than *p-1* - (e.g. *floor((p-1)/8)* random bytes) is also **not** secure. - In general, it shall not be possible for an attacker to know - the value of any bit of K. - - :attention: The number *K* shall not be reused for any other - operation and shall be discarded immediately. - """ - return pubkey.encrypt(self, plaintext, K) - - def decrypt(self, ciphertext): - """Decrypt a piece of data with ElGamal. - - :Parameter ciphertext: The piece of data to decrypt with ElGamal. - :Type ciphertext: byte string, long or a 2-item tuple as returned - by `encrypt` - - :Return: A byte string if ciphertext was a byte string or a tuple - of byte strings. A long otherwise. - """ - return pubkey.decrypt(self, ciphertext) - - def sign(self, M, K): - """Sign a piece of data with ElGamal. - - :Parameter M: The piece of data to sign with ElGamal. It may - not be longer in bit size than *p-1*. - :Type M: byte string or long - - :Parameter K: A secret number, chosen randomly in the closed - range *[1,p-2]* and such that *gcd(k,p-1)=1*. - :Type K: long (recommended) or byte string (not recommended) - - :attention: selection of *K* is crucial for security. Generating a - random number larger than *p-1* and taking the modulus by *p-1* is - **not** secure, since smaller values will occur more frequently. - Generating a random number systematically smaller than *p-1* - (e.g. *floor((p-1)/8)* random bytes) is also **not** secure. - In general, it shall not be possible for an attacker to know - the value of any bit of K. - - :attention: The number *K* shall not be reused for any other - operation and shall be discarded immediately. - - :attention: M must be be a cryptographic hash, otherwise an - attacker may mount an existential forgery attack. - - :Return: A tuple with 2 longs. - """ - return pubkey.sign(self, M, K) - - def verify(self, M, signature): - """Verify the validity of an ElGamal signature. - - :Parameter M: The expected message. - :Type M: byte string or long - - :Parameter signature: The ElGamal signature to verify. - :Type signature: A tuple with 2 longs as return by `sign` - - :Return: True if the signature is correct, False otherwise. - """ - return pubkey.verify(self, M, signature) - - def _encrypt(self, M, K): - a=pow(self.g, K, self.p) - b=( M*pow(self.y, K, self.p) ) % self.p - return ( a,b ) - - def _decrypt(self, M): - if (not hasattr(self, 'x')): - raise TypeError('Private key not available in this object') - ax=pow(M[0], self.x, self.p) - plaintext=(M[1] * inverse(ax, self.p ) ) % self.p - return plaintext - - def _sign(self, M, K): - if (not hasattr(self, 'x')): - raise TypeError('Private key not available in this object') - p1=self.p-1 - if (GCD(K, p1)!=1): - raise ValueError('Bad K value: GCD(K,p-1)!=1') - a=pow(self.g, K, self.p) - t=(M-self.x*a) % p1 - while t<0: t=t+p1 - b=(t*inverse(K, p1)) % p1 - return (a, b) - - def _verify(self, M, sig): - if sig[0]<1 or sig[0]>self.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) - if v1==v2: - return 1 - return 0 - - def size(self): - return number.size(self.p) - 1 - - def has_private(self): - if hasattr(self, 'x'): - return 1 - else: - return 0 - - def publickey(self): - return construct((self.p, self.g, self.y)) - - -object=ElGamalobj |