5 Crypto.PublicKey: Public-Key Algorithms

So far, the encryption algorithms described have all been private key ciphers. The same key is used for both encryption and decryption so all correspondents must know it. This poses a problem: you may want encryption to communicate sensitive data over an insecure channel, but how can you tell your correspondent what the key is? You can't just e-mail it to her because the channel is insecure. One solution is to arrange the key via some other way: over the phone or by meeting in person.

Another solution is to use public-key cryptography. In a public key system, there are two different keys: one for encryption and one for decryption. The encryption key can be made public by listing it in a directory or mailing it to your correspondent, while you keep the decryption key secret. Your correspondent then sends you data encrypted with your public key, and you use the private key to decrypt it. While the two keys are related, it's very difficult to derive the private key given only the public key; however, deriving the private key is always possible given enough time and computing power. This makes it very important to pick keys of the right size: large enough to be secure, but small enough to be applied fairly quickly.

Many public-key algorithms can also be used to sign messages; simply run the message to be signed through a decryption with your private key key. Anyone receiving the message can encrypt it with your publicly available key and read the message. Some algorithms do only one thing, others can both encrypt and authenticate.

The currently available public-key algorithms are listed in the following table:

Algorithm  Capabilities 
RSA Encryption, authentication/signatures
ElGamal Encryption, authentication/signatures
DSA Authentication/signatures
qNEW Authentication/signatures

Many of these algorithms are patented. Before using any of them in a commercial product, consult a patent attorney; you may have to arrange a license with the patent holder.

An example of using the RSA module to sign a message:

>>> from Crypto.Hash import MD5
>>> from Crypto.PublicKey import RSA
>>> RSAkey = RSA.generate(384, randfunc)   # This will take a while...
>>> hash = MD5.new(plaintext).digest()
>>> signature = RSAkey.sign(hash, "")
>>> signature   # Print what an RSA sig looks like--you don't really care.
('\021\317\313\336\264\315' ...,)
>>> RSAkey.verify(hash, signature)     # This sig will check out
1
>>> RSAkey.verify(hash[:-1], signature)# This sig will fail
0

Public-key modules make the following functions available:

construct(tuple)
Constructs a key object from a tuple of data. This is algorithm-specific; look at the source code for the details. (To be documented later.)

generate(size, randfunc, progress_func=None)
Generate a fresh public/private key pair. size is a algorithm-dependent size parameter, usually measured in bits; the larger it is, the more difficult it will be to break the key. Safe key sizes vary from algorithm to algorithm; you'll have to research the question and decide on a suitable key size for your application. An N-bit keys can encrypt messages up to N-1 bits long.

randfunc is a random number generation function; it should accept a single integer N and return a string of random data N bytes long. You should always use a cryptographically secure random number generator, such as the one defined in the Crypto.Util.randpool module; don't just use the current time and the random module.

progress_func is an 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.

If you want to interface with some other program, you will have to know the details of the algorithm being used; this isn't a big loss. If you don't care about working with non-Python software, simply use the pickle module when you need to write a key or a signature to a file. It's portable across all the architectures that Python supports, and it's simple to use.

Public-key objects always support the following methods. Some of them may raise exceptions if their functionality is not supported by the algorithm.

can_blind()
Returns true if the algorithm is capable of blinding data; returns false otherwise.

can_encrypt()
Returns true if the algorithm is capable of encrypting and decrypting data; returns false otherwise. To test if a given key object can encrypt data, use key.can_encrypt() and key.has_private().

can_sign()
Returns true if the algorithm is capable of signing data; returns false otherwise. To test if a given key object can sign data, use key.can_sign() and key.has_private().

decrypt(tuple)
Decrypts tuple with the private key, returning another string. This requires the private key to be present, and will raise an exception if it isn't present. It will also raise an exception if string is too long.

encrypt(string, K)
Encrypts string with the private key, returning a tuple of strings; the length of the tuple varies from algorithm to algorithm. K should be a string of random data that is as long as possible. Encryption does not require the private key to be present inside the key object. It will raise an exception if string is too long. For ElGamal objects, the value of K expressed as a big-endian integer must be relatively prime to self.p-1; an exception is raised if it is not.

has_private()
Returns true if the key object contains the private key data, which will allow decrypting data and generating signatures. Otherwise this returns false.

publickey()
Returns a new public key object that doesn't contain the private key data.

sign(string, K)
Sign string, returning a signature, which is just a tuple; in theory the signature may be made up of any Python objects at all; in practice they'll be either strings or numbers. K should be a string of random data that is as long as possible. Different algorithms will return tuples of different sizes. sign() raises an exception if string is too long. For ElGamal objects, the value of K expressed as a big-endian integer must be relatively prime to self.p-1; an exception is raised if it is not.

size()
Returns the maximum size of a string that can be encrypted or signed, measured in bits. String data is treated in big-endian format; the most significant byte comes first. (This seems to be a de facto standard for cryptographical software.) If the size is not a multiple of 8, then some of the high order bits of the first byte must be zero. Usually it's simplest to just divide the size by 8 and round down.

verify(string, signature)
Returns true if the signature is valid, and false otherwise. string is not processed in any way; verify does not run a hash function over the data, but you can easily do that yourself.


Subsections