Dramatis Personae:
Alice - a user
Bob - a server
Eve - an eavesdropper (a passive enemy)
Mallory - a malicious troublemaker (an active enemy)
Before we can authenticate, it would be nice to have secure communications.
So first of all, let's have a look at the Diffie-Hellman technique for
establishing a secret in public. The patent on Diffie-Hellman has expired.
This is based on the equation N = (Y**X) MOD P --- where
** means "to the power of" and MOD means "remainder after division".
Bob chooses two numbers, Y and P. Although it's not essential, he'll probably make P prime. He must ensure that Y < P. The secrecy or otherwise of these numbers is unimportant; personally, I'd choose new ones for each session, though...
Bob now chooses a third number, B. This number should be chosen randomly. rand() is not good enough for this. You might want to roll some dice, and store the numbers you get somewhere really safe, where they can't be sniffed.
Bob calculates the number b, where b = (Y**B) MOD P.
Bob sends b, Y and P to Alice. This can be done "in clear".
Alice chooses a number A. She calculates the number a, where a = (Y**A) MOD P.
Alice sends a to Bob "in clear".
Alice calculates K = (b ** A) MOD P.
Bob calculates K = (a ** B) MOD P.
Alice and Bob have now arrived at a number they can both use for a key. The most important thing about it is that K has not been sent over the wire. Eve can listen to all the transmissions up to this point, and will not be able to determine K.
(This is rather impressive - well done, Diffie and Hellman!)
Note: you want the key, K, to be perhaps 128 or even 256 bits long. This means that P needs to be something like a 40 or even 80 digit number (and, personally, I'd make it prime - choose a prime that's about 40% to 60% of the way between two powers of two). Also, choose Y, A and B such that the modulo is actually relevant to the calculation.
In other words, you need a bignum package. Miracl, GMP, or (at a pinch)
the one at www.snippets.org will
do.
Whichever algorithm you decide on, we'll call it E. Also, we'll overload P to mean plaintext (we're done with Diffie-Hellman now), and C means ciphertext. K still means the key we generated in the previous section.
C = E(P, K) means that we use E to encrypt P with K, giving us C.
Bob generates a session ID in some arbitrary manner - ideally it should have a strong random element - e.g. keyboard latency or /dev/random or something like that. Lava lamps for preference. :-) If it includes the date, so much the better.
Bob encrypts this session ID with his private key, and then with Alice's public key. Finally, he encrypts it with K, and sends it to Alice. She, in the meantime, has generated her own session ID, and encrypted it with her own private key and then with Bob's public key, and then with K, and sent it to Bob.
Alice re-encrypts Bob's session ID with her private key, and then with Bob's public key, and then with K. Bob re-encrypts Alice's session ID with his private key and then with Alice's public key, and then with K.
Each of them, on re-receipt of their own session ID, breaks it open
to check that it's the same as the one they originally sent. If so, it's
a wrap - authentication is complete.
That's it - I hope you enjoyed it. If you find any flaws in this protocol,
please let me know...
Alice selects two really big prime numbers, p and q. These numbers must be protected - their secrecy is vital.
She calculates N = p * q
Now she picks another number e (where e and (p-1)*(q-1) are relatively prime).
Alice's public key comprises e and N.
Bob can encrypt a message meant for Alice as follows:
C = (P**e) MOD N.
C = Ciphertext, P = plaintext
Alice calculates her private key d as follows:
e * d = 1 MOD ((p - 1) * (q - 1))
(Euclid's algorithm will help you find d.)
To decrypt:
P = (C ** d) MOD N.
When someone works out how to factorise large numbers easily, the security
of this method will fail.