Paul Rubin phr-n2002b at NOSPAMnightsong.com
Wed Sep 4 23:07:22 CEST 2002

```"Gumuz" <gumuz at looze.net> writes:
> although this is just a play-learn-project and security is not really an
> issue, i'd like to include encryption in it as well to get experience in
> this, too.

If you want to learn programming cryptography, the book you want is
"Applied Cryptography" by Bruce Schneier.  You might like to implement
everything yourself rather than using a library.

> Actually, I am trying to create a sort of simple instant messenger
> server+client.

I think this should use Diffie-Hellman key exchange to choose the
decryption keys.  DH is a way for two people to agree on a key based
on random parameters they each choose.  The traditional version goes:

Alice and Bob agree beforehand on public parameters g and P,
where P is a big prime number (like 300 digits) with certain
properties and g is a generator of Z//p.  If you don't understand
that, don't worry too much--there are standard values of g and P
that you can use.

To start talking to each other, Alice chooses a secret random number x,
and Bob chooses a secret random number y.  They do not reveal these
numbers to anyone.  Alice instead computes the number X = g**x mod P
and sends X to Bob.  Bob computes Y = g**y mod P and sends Y to Alice.
Computing these modular exponentials is trivial in python because
of Python's built-in long integers and its 3-argument pow function.
You can just say Y = pow(g,y,P).

Since Alice receives Y from Bob and knows x already, she can compute
K = Y**x mod P.  Notice Y**x mod P == (g**y)**x mod P = g**(yx) mod P.
Bob likewise can compute K = X**y mod P = (g**x)**y mod P = g**(xy) mod P.
Since multiplication is commutative, xy==yx so both have found the same K.
The coolness here is the computation required knowing at least one of
the secrets, x or y.  An eavesdropper knowing neither secret doesn't
have any easy way to find K.

At the end of the conversation, Alice and Bob should both erase their
secret values x, y, and K from computer memory.  That means the
conversation can never be recovered by a third party, even by forcing
Alice and Bob to reveal their passwords, turn over their computers, etc.
The keys are gone forever, like burning a document.

Note you will also have to protect against "man in the middle"
attacks, and deal with some other subtleties, to make DH secure--the
description above is just to sketch the process.  See Applied