[project @ akuchling-20020513063907-d0ccf4cffe4846c7]

[project @ 2002-05-12 23:39:07 by akuchling]
Restore PublicKey docs

1 files changed, 222 insertions, 0 deletions

diff --git a/Doc/pycrypt.tex b/Doc/pycrypt.tex
index 5bee569..030ae27 100644
--- a/Doc/pycrypt.tex
+++ b/Doc/pycrypt.tex
@@ -644,6 +644,228 @@ that can be used to discern it from wheat data without running
 the MAC.
 \end{methoddesc}
 
+\section{Crypto.PublicKey: Public Key Algorithms}
+So far, the encryption algorithms described have all been \dfn{private
+key} ciphers.  That is, 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 \dfn{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:
+
+\begin{tableii}{c|l}{}{Algorithm}{Capabilities}
+\lineii{RSA}{Encryption, authentication/signatures}
+\lineii{ElGamal}{Encryption, authentication/signatures}
+\lineii{DSA}{Authentication/signatures}
+\lineii{qNEW}{Authentication/signatures}
+\end{tableii}
+
+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:
+\begin{verbatim}
+>>> 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
+\end{verbatim}
+
+       
+Public key modules make the following functions available:
+
+\begin{funcdesc}{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.)
+\end{funcdesc}
+
+\begin{funcdesc}{generate}{size, randfunc, progress_func=\code{None}}
+Generate a fresh public/private key pair.  \var{size} is a
+algorithm-dependent size parameter; 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.  \code{randfunc}
+is a random number generation function; it should accept a single
+integer \var{N} and return a string of random data \var{N} bytes long.
+You should always use a cryptographically secure random number
+generator, such as the one defined in the \code{randpool} module;
+\emph{don't} just use the current time and the \code{whrandom} module.
+
+\var{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.
+\end{funcdesc}
+
+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
+\code{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.
+
+\begin{funcdesc}{canencrypt}{}
+Returns true if the algorithm is capable of encrypting and decrypting
+data; returns false otherwise.  To test if a given key object can sign
+data, use \code{key.canencrypt() and key.hasprivate()}.
+\end{funcdesc}
+
+\begin{funcdesc}{cansign}{}
+Returns true if the algorithm is capable of signing data; returns false
+otherwise.  To test if a given key object can sign data, use
+\code{key.cansign() and key.hasprivate()}.
+\end{funcdesc}
+
+\begin{funcdesc}{decrypt}{tuple}
+Decrypts \var{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 \var{string} is
+too long.
+\end{funcdesc}
+
+\begin{funcdesc}{encrypt}{string, K}
+Encrypts \var{string} with the private key, returning a tuple of
+strings; the length of the tuple varies from algorithm to algorithm.  
+\var{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 \var{string} is
+too long.  For ElGamal objects, the value of \var{K} expressed as a
+big-endian integer must be relatively prime to \code{self.p-1}; an
+exception is raised if it is not.
+\end{funcdesc}
+
+\begin{funcdesc}{hasprivate}{}
+Returns true if the key object contains the private key data, which
+will allow decrypting data and generating signatures.
+Otherwise this returns false.
+\end{funcdesc}
+
+\begin{funcdesc}{publickey}{}
+Returns a new public key object that doesn't contain the private key
+data. 
+\end{funcdesc}
+
+\begin{funcdesc}{sign}{string, K}
+Sign \var{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.  \var{K} should be a
+string of random data that is as long as possible.  Different algorithms
+will return tuples of different sizes.  \code{sign()} raises an
+exception if \var{string} is too long.  For ElGamal objects, the value
+of \var{K} expressed as a big-endian integer must be relatively prime to
+\code{self.p-1}; an exception is raised if it is not.
+\end{funcdesc}
+
+\begin{funcdesc}{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 \emph{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.
+\end{funcdesc}
+
+\begin{funcdesc}{verify}{string, signature}
+Returns true if the signature is valid, and false otherwise.
+\var{string} is not processed in any way; \code{verify} does
+not run a hash function over the data, but you can easily do that yourself.
+\end{funcdesc}
+
+\subsection{The ElGamal and DSA algorithms}
+For RSA, the \var{K} parameters are unused; if you like, you can just
+pass empty strings.  The ElGamal and DSA algorithms require a real
+\var{K} value for technical reasons; see Schneier's book for a detailed
+explanation of the respective algorithms.  This presents a possible
+hazard that can  
+inadvertently reveal the private key.  Without going into the
+mathematical details, the danger is as follows. \var{K} is never derived
+or needed by others; theoretically, it can be thrown away once the
+encryption or signing operation is performed.  However, revealing
+\var{K} for a given message would enable others to derive the secret key
+data; worse, reusing the same value of \var{K} for two different
+messages would also enable someone to derive the secret key data.  An
+adversary could intercept and store every message, and then try deriving
+the secret key from each pair of messages.
+
+This places implementors on the horns of a dilemma.  On the one hand,
+you want to store the \var{K} values to avoid reusing one; on the other
+hand, storing them means they could fall into the hands of an adversary.
+One can randomly generate \var{K} values of a suitable length such as
+128 or 144 bits, and then trust that the random number generator
+probably won't produce a duplicate anytime soon.  This is an
+implementation decision that depends on the desired level of security
+and the expected usage lifetime of a private key.  I cannot choose and
+enforce one policy for this, so I've added the \var{K} parameter to the
+\code{encrypt} and \code{sign} functions.  You must choose \var{K} by
+generating a string of random data; for ElGamal, when interpreted as a
+big-endian number (with the most significant byte being the first byte
+of the string), \var{K} must be relatively prime to \code{self.p-1}; any
+size will do, but brute force searches would probably start with small
+primes, so it's probably good to choose fairly large numbers.  It might be
+simplest to generate a prime number of a suitable length using the
+\code{Crypto.Util.number} module.
+
+\subsection{Security Notes for Public-key Algorithms}
+Any of these algorithms can be trivially broken; for example, RSA can be
+broken by factoring the modulus \emph{n} into its two prime factors.
+This is easily done by the following code:
+
+\begin{verbatim}
+for i in range(2, n): 
+    if (n%i)==0: print i, 'is a factor' ; break
+\end{verbatim}
+
+
+However, \emph{n} is usually a few hundred bits long, so this simple
+program wouldn't find a solution before the universe comes to an end.
+Smarter algorithms can factor numbers more quickly, but it's still
+possible to choose keys so large that they can't be broken in a
+reasonable amount of time.  For ElGamal and DSA, discrete logarithms are
+used instead of factoring, but the principle is the same.
+
+Safe key sizes depend on the current state of computer science and
+technology.  At the moment, one can roughly define three levels of
+security: low-security commercial, high-security commercial, and
+military-grade.  For RSA, these three levels correspond roughly to 512,
+768, and 1024 bit-keys.  For ElGamal and DSA, the key sizes should be
+somewhat larger for the same level of security, around 768, 1024, and
+1536 bits.
+
 \section{Crypto.Util: Odds and Ends}
 This chapter contains all the modules that don't fit into any of the
 other chapters.