pycrypt.tex

python的加密库

\documentclass{howto}

\title{Python Cryptography Toolkit}

\release{2.0.1}

\author{A.M. Kuchling}
\authoraddress{\url{www.amk.ca}}

\begin{document}
\maketitle

\begin{abstract}
\noindent
The Python Cryptography Toolkit describes a package containing various
cryptographic modules for the Python programming language.  This
documentation assumes you have some basic knowledge about the Python
language, but not necessarily about cryptography.

\end{abstract}

\tableofcontents


%======================================================================
\section{Introduction}

\subsection{Design Goals}
The Python cryptography toolkit is intended to provide a reliable and
stable base for writing Python programs that require cryptographic
functions.

A central goal of the author's has been to provide a simple,
consistent interface for similar classes of algorithms.  For example,
all block cipher objects have the same methods and return values, and
support the same feedback modes.  Hash functions have a different
interface, but it too is consistent over all the hash functions
available.  Some of these interfaces have been codified as Python
Enhancement Proposal documents, as \pep{247}, ``API for Cryptographic
Hash Functions'', and \pep{272}, ``API for Block Encryption
Algorithms''.  

This is intended to make it easy to replace old algorithms with newer,
more secure ones.  If you're given a bit of portably-written Python
code that uses the DES encryption algorithm, you should be able to use
AES instead by simply changing \code{from Crypto.Cipher import DES} to
\code{from Crypto.Cipher import AES}, and changing all references to
\code{DES.new()} to \code{AES.new()}.  It's also fairly simple to
write your own modules that mimic this interface, thus letting you use
combinations or permutations of algorithms.

Some modules are implemented in C for performance; others are written
in Python for ease of modification.  Generally, low-level functions
like ciphers and hash functions are written in C, while less
speed-critical functions have been written in Python.  This division
may change in future releases.  When speeds are quoted in this
document, they were measured on a 500 MHz Pentium II running Linux.
The exact speeds will obviously vary with different machines,
different compilers, and the phase of the moon, but they provide a
crude basis for comparison.  Currently the cryptographic
implementations are acceptably fast, but not spectacularly good.  I
welcome any suggestions or patches for faster code.

I have placed the code under no restrictions; you can redistribute the
code freely or commercially, in its original form or with any
modifications you make, subject to whatever local laws may apply in your
jurisdiction.  Note that you still have to come to some agreement with
the holders of any patented algorithms you're using.  If you're
intensively using these modules, please tell me about it; there's little
incentive for me to work on this package if I don't know of anyone using
it.

I also make no guarantees as to the usefulness, correctness, or legality
of these modules, nor does their inclusion constitute an endorsement of
their effectiveness.  Many cryptographic algorithms are patented;
inclusion in this package does not necessarily mean you are allowed to
incorporate them in a product and sell it.  Some of these algorithms may
have been cryptanalyzed, and may no longer be secure.  While I will
include commentary on the relative security of the algorithms in the
sections entitled "Security Notes", there may be more recent analyses
I'm not aware of.  (Or maybe I'm just clueless.)  If you're implementing
an important system, don't just grab things out of a toolbox and put
them together; do some research first.  On the other hand, if you're
just interested in keeping your co-workers or your relatives out of your
files, any of the components here could be used.

This document is very much a work in progress.  If you have any
questions, comments, complaints, or suggestions, please send them to me.

\subsection{Acknowledgements}
Much of the code that actually implements the various cryptographic
algorithms was not written by me.  I'd like to thank all the people who
implemented them, and released their work under terms which allowed me
to use their code.  These individuals are credited in the relevant
chapters of this documentation.  Bruce Schneier's book \emph{Applied
Cryptography} was also very useful in writing this toolkit; I highly
recommend it if you're interested in learning more about cryptography.

Good luck with your cryptography hacking!

A.M.K.

\email{[e-mail]}

Washington DC, USA

June 2005


%======================================================================
\section{Crypto.Hash: Hash Functions}

Hash functions take arbitrary strings as input, and produce an output
of fixed size that is dependent on the input; it should never be
possible to derive the input data given only the hash function's
output.  One simple hash function consists of simply adding together
all the bytes of the input, and taking the result modulo 256.  For a
hash function to be cryptographically secure, it must be very
difficult to find two messages with the same hash value, or to find a
message with a given hash value.  The simple additive hash function
fails this criterion miserably and the hash functions described below
meet this criterion (as far as we know).  Examples of
cryptographically secure hash functions include MD2, MD5, and SHA1.

Hash functions can be used simply as a checksum, or, in association with a
public-key algorithm, can be used to implement digital signatures.
 
The hashing algorithms currently implemented are:

\begin{tableii}{c|l}{}{Hash function}{Digest length}
\lineii{MD2}{128 bits}
\lineii{MD4}{128 bits}
\lineii{MD5}{128 bits}
\lineii{RIPEMD}{160 bits}
\lineii{SHA1}{160 bits}
\lineii{SHA256}{256 bits}
\end{tableii}

All hashing modules share the same interface.  After importing a given
hashing module, call the \function{new()} function to create a new
hashing object. You can now feed arbitrary strings into the object
with the \method{update()} method, and can ask for the hash value at
any time by calling the \method{digest()} or \method{hexdigest()}
methods.  The \function{new()} function can also be passed an optional
string parameter that will be immediately hashed into the object's
state.

Hash function modules define one variable:

\begin{datadesc}{digest_size}
An integer value; the size of the digest
produced by the hashing objects.  You could also obtain this value by
creating a sample object, and taking the length of the digest string
it returns, but using \member{digest_size} is faster.
\end{datadesc}

The methods for hashing objects are always the following:

\begin{methoddesc}{copy}{}
Return a separate copy of this hashing object.  An \code{update} to
this copy won't affect the original object.
\end{methoddesc}

\begin{methoddesc}{digest}{}
Return the hash value of this hashing object, as a string containing
8-bit data.  The object is not altered in any way by this function;
you can continue updating the object after calling this function.
\end{methoddesc}

\begin{methoddesc}{hexdigest}{}
Return the hash value of this hashing object, as a string containing
the digest data as hexadecimal digits.  The resulting string will be
twice as long as that returned by \method{digest()}.  The object is not
altered in any way by this function; you can continue updating the
object after calling this function.
\end{methoddesc}

\begin{methoddesc}{update}{arg}
Update this hashing object with the string \var{arg}.
\end{methoddesc}

Here's an example, using the MD5 algorithm:

\begin{verbatim}
>>> from Crypto.Hash import MD5
>>> m = MD5.new()
>>> m.update('abc')
>>> m.digest()
'\x90\x01P\x98<\xd2O\xb0\xd6\x96?}(\xe1\x7fr'
>>> m.hexdigest()
'900150983cd24fb0d6963f7d28e17f72'
\end{verbatim}


\subsection{Security Notes}

Hashing algorithms are broken by developing an algorithm to compute a
string that produces a given hash value, or to find two messages that
produce the same hash value. Consider an example where Alice and Bob
are using digital signatures to sign a contract.  Alice computes the
hash value of the text of the contract and signs the hash value with
her private key.  Bob could then compute a different contract that has
the same hash value, and it would appear that Alice signed that bogus
contract; she'd have no way to prove otherwise.  Finding such a
message by brute force takes \code{pow(2, b-1)} operations, where the
hash function produces \emph{b}-bit hashes.

If Bob can only find two messages with the same hash value but can't
choose the resulting hash value, he can look for two messages with
different meanings, such as "I will mow Bob's lawn for $10" and "I owe
Bob $1,000,000", and ask Alice to sign the first, innocuous contract.
This attack is easier for Bob, since finding two such messages by brute
force will take \code{pow(2, b/2)} operations on average.  However,
Alice can protect herself by changing the protocol; she can simply
append a random string to the contract before hashing and signing it;
the random string can then be kept with the signature.

None of the algorithms implemented here have been completely broken.
There are no attacks on MD2, but it's rather slow at 1250 K/sec.  MD4
is faster at 44,500 K/sec but there have been some partial attacks on
it.  MD4 makes three iterations of a basic mixing operation; two of
the three rounds have been cryptanalyzed, but the attack can't be
extended to the full algorithm.  MD5 is a strengthened version of MD4
with four rounds; an attack against one round has been found XXX
update this.  MD5 is still believed secure at the moment, but people
are gravitating toward using SHA1 in new software because there are no
known attacks against SHA1.  The MD5 implementation is moderately
well-optimized and thus faster on x86 processors, running at 35,500
K/sec.  MD5 may even be faster than MD4, depending on the processor
and compiler you use.

All the MD\var{n} algorithms produce 128-bit hashes; SHA1 produces a
larger 160-bit hash, and there are no known attacks against it.  The
first version of SHA had a weakness which was later corrected; the
code used here implements the second, corrected, version.  It operates
at 21,000 K/sec.  SHA256 is about as half as fast as SHA1.  RIPEMD has
a 160-bit output, the same output size as SHA1, and operates at 17,600
K/sec.

\subsection{Credits}
The MD2 and MD4 implementations were written by A.M. Kuchling, and the
MD5 code was implemented by Colin Plumb.  The SHA1 code was originally
written by Peter Gutmann.  The RIPEMD code was written by Antoon
Bosselaers, and adapted for the toolkit by Hirendra Hindocha.  The
SHA256 code was written by Tom St.~Denis and is part of the
LibTomCrypt library (\url{http://www.libtomcrypt.org/}); it was
adapted for the toolkit by Jeethu Rao and Taylor Boon.


%======================================================================
\section{Crypto.Cipher: Encryption Algorithms}

Encryption algorithms transform their input data, or \dfn{plaintext},
in some way that is dependent on a variable \dfn{key}, producing
\dfn{ciphertext}. This transformation can easily be reversed, if (and,
hopefully, only if) one knows the key.  The key can be varied by the
user or application and chosen from some very large space of possible
keys.

For a secure encryption algorithm, it should be very difficult to
determine the original plaintext without knowing the key; usually, no
clever attacks on the algorithm are known, so the only way of breaking
the algorithm is to try all possible keys. Since the number of possible
keys is usually of the order of 2 to the power of 56 or 128, this is not
a serious threat, although 2 to the power of 56 is now considered
insecure in the face of custom-built parallel computers and distributed
key guessing efforts.

\dfn{Block ciphers} take multibyte inputs of a fixed size
(frequently 8 or 16 bytes long) and encrypt them.  Block ciphers can
be operated in various modes.  The simplest is Electronic Code Book
(or ECB) mode.  In this mode, each block of plaintext is simply
encrypted to produce the ciphertext.  This mode can be dangerous,
because many files will contain patterns greater than the block size;
for example, the comments in a C program may contain long strings of
asterisks intended to form a box.  All these identical blocks will
encrypt to identical ciphertext; an adversary may be able to use this
structure to obtain some information about the text.

To eliminate this weakness, there are various feedback modes in which
the plaintext is combined with the previous ciphertext before
encrypting; this eliminates any repetitive structure in the
ciphertext.   

One mode is Cipher Block Chaining (CBC mode); another is Cipher
FeedBack (CFB mode).  CBC mode still encrypts in blocks, and thus is
only slightly slower than ECB mode.  CFB mode encrypts on a
byte-by-byte basis, and is much slower than either of the other two
modes.  The chaining feedback modes require an initialization value to
start off the encryption; this is a string of the same length as the
ciphering algorithm's block size, and is passed to the \code{new()}
function.  There is also a special PGP mode, which is an oddball
variant of CFB used by the PGP program.  While you can use it in
non-PGP programs, it's quite non-standard.

The currently available block ciphers are listed in the following table,
and are in the \code{Crypto.Cipher} package: