Refreshed documentation for ElGamal. Small corrections to DSA and RSA.

3 files changed, 236 insertions, 24 deletions

diff --git a/lib/Crypto/PublicKey/DSA.py b/lib/Crypto/PublicKey/DSA.py
index 1f4484a..185ed01 100644
--- a/lib/Crypto/PublicKey/DSA.py
+++ b/lib/Crypto/PublicKey/DSA.py
@@ -25,9 +25,9 @@
 """DSA public-key signature algorithm.
 
 DSA_ is a widespread public-key signature algorithm. Its security is
-based on the discrete logarithm problem, that is, given a multiplicative
-group, a generator *g*, and an element *h*, the difficulty
-of finding another element *x* such that *g^x = h*. The problem is believed
+based 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 problem is believed
 to be difficult, and it has been proved such (and therefore secure) for
 more than 30 years.
 
@@ -36,15 +36,17 @@ DSA is reasonably secure for new designs.
 The algorithm can only be used for authentication (digital signature).
 DSA cannot be used for confidentiality (encryption).
 
-The group is actually a sub-group over a finite finite field of prime order *p*.
-The sub-group order is *q*, and it always holds that *(p-1)* is a multiple of *q*. 
+The group is actually a sub-group over the integers modulo *p*, with *p* prime.
+The sub-group order is *q*, which is prime too; it always holds that *(p-1)* is a multiple of *q*.
 The cryptographic strength is linked to the magnitude of *p* and *q*.
 In 2012, a sufficient size is deemed to be 2048 bits for *p* and 256 bits for *q*.
 For more information, see the most recent ECRYPT_ report.
 
-The actual value of *g* is not important. *(p,q,g)* are called *domain
-parameters*; they are not sensitive but must be shared by both parties (the
-signer and the verifier).
+The values *(p,q,g)* are called *domain parameters*;
+they are not sensitive but must be shared by both parties (the signer and the verifier).
+
+The DSA signature is twice as big the size of *q* (64 bytes if *q* is 256 bit
+long).
 
 This module provides facilities for generating new DSA keys and for constructing
 them from known components. DSA keys allows you to perform basic signing and
@@ -66,6 +68,7 @@ verification.
     >>>     print "Incorrect signature"
 
 .. _DSA: http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
+.. _DLP: http://www.cosic.esat.kuleuven.be/publications/talk-78.pdf
 .. _ECRYPT: http://www.ecrypt.eu.org/documents/D.SPA.17.pdf
 """
 
@@ -130,14 +133,18 @@ class _DSAobj(pubkey.pubkey):
         :attention: selection of *K* is crucial for security. Generating a
          random number larger than *q* and taking the modulus by *q* is
          **not** secure, since smaller values will occur more frequently.
-         Generating a random larger systematically smaller than *q-1*
-         (e.g. *floor((q-1)/8)* bytes) is also **not** secure. In general,
+         Generating a random number systematically smaller than *q-1*
+         (e.g. *floor((q-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: It is strongly recommended to have M be a digest created
+         via a cryptographic hash, otherwise an attacker may mount an
+         existential forgery attack.
+
         :Return: A tuple with 2 longs.
 
         .. __: http://www.di.ens.fr/~pnguyen/pub_NgSh00.htm
diff --git a/lib/Crypto/PublicKey/ElGamal.py b/lib/Crypto/PublicKey/ElGamal.py
index 62a9c3a..2b4d511 100644
--- a/lib/Crypto/PublicKey/ElGamal.py
+++ b/lib/Crypto/PublicKey/ElGamal.py
@@ -23,10 +23,83 @@
 # SOFTWARE.
 # ===================================================================
 
-"""ElGamal public-key algorithm (encryption and signature)."""
+"""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 (*g*, *p*, *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
+(*g*, *p*, *b* where *b*=g^a*) is given to the sender.
+
+The ElGamal ciphertext is twice as big as *p*.
+
+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
 
@@ -35,11 +108,27 @@ class error (Exception):
 
 # Generate an ElGamal key with N bits
 def generate(bits, randfunc, progress_func=None):
-    """generate(bits:int, randfunc:callable, progress_func:callable)
+    """Randomly generate a fresh, new ElGamal key.
+
+    :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.
 
-    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.
+    :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 prime p
@@ -78,10 +167,29 @@ def generate(bits, randfunc, progress_func=None):
     obj.y = pow(obj.g, obj.x, obj.p)
     return obj
 
-def construct(tuple):
-    """construct(tuple:(long,long,long,long)|(long,long,long,long,long)))
-             : ElGamalobj
-    Construct an ElGamal key from a 3- or 4-tuple of numbers.
+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()
@@ -93,8 +201,106 @@ def construct(tuple):
     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: It is strongly recommended to have M be a digest created
+         via 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
@@ -128,19 +334,15 @@ class ElGamalobj(pubkey):
         return 0
 
     def size(self):
-        "Return the maximum number of bits that can be handled by this key."
         return number.size(self.p) - 1
 
     def has_private(self):
-        """Return a Boolean denoting whether the object contains
-        private components."""
         if hasattr(self, 'x'):
             return 1
         else:
             return 0
 
     def publickey(self):
-        """Return a new key object containing only the public information."""
         return construct((self.p, self.g, self.y))
 
 
diff --git a/lib/Crypto/PublicKey/RSA.py b/lib/Crypto/PublicKey/RSA.py
index a4c40a2..4f40ec0 100644
--- a/lib/Crypto/PublicKey/RSA.py
+++ b/lib/Crypto/PublicKey/RSA.py
@@ -32,10 +32,13 @@ secure for new designs.
 The algorithm can be used for both confidentiality (encryption) and
 authentication (digital signature). It is worth noting that signing and
 decryption are significantly slower than verification and encryption.
-The cryptograhic strength is primarily linked to the length of the modulus.
+The cryptograhic strength is primarily linked to the length of the modulus *n*.
 In 2012, a sufficient length is deemed to be 2048 bits. For more information,
 see the most recent ECRYPT_ report.
 
+Both RSA ciphertext and RSA signature are as big as the modulus *n* (256
+bytes if *n* is 2048 bit long).
+
 This module provides facilities for generating fresh, new RSA keys, constructing
 them from known components, exporting them, and importing them.