NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Structure of a Public Key Cryptosystem.

Each separate user constructs a public encryption algorithm E and a private decryption algorithm D. Thus Alice has a pair E_A and D_A, and similarly Bob has E_B and D_B.

Each matching pair E and D of algorithms has the properties:

1. D(E(M)) = M, for any plaintext M for which the algorithm E is defined.

2. Both E and D can be calculated ``efficiently''.

3. For an opponent (``Boris'') who knows E, it is still an ``intractible'' computation to discover D.

   The RSA public key cryptosystem also has the following pleasant property:

4. E(D(M)) = M, for any plaintext M (the same set of plaintexts as in 1 above).

The word ``efficient'' means that that calculation uses an acceptable amount of resources, while ``intractible'' means roughly that this computation uses more resources than the secrecy of the message is worth. (This varies with time, as computations get cheaper.)

Alice makes her public algorithm publically available, by publishing it or by putting online, and so does every other user. She keeps her secret algorithm completely to herself. (No one else must know it.)

---

Modes of Operation for Public Key Cryptosystems.

Here the term ``key'' is used to mean the same as ``algorithm'' above. Suppose as above that Alice and Bob have public key and private key pairs: (E_A, D_A) for Alice and (E_B, D_B) for Bob. There is some key distribution authority that keeps the public keys E_A and E_B and makes them available to anyone requesting them. (Using signature techniques discussed later, the authority can convince a requester that he or she is getting the correct keys.)

Bob sends a secret message M to Alice: Bob gets Alice's public key E_A from the authority. Bob calculates E_A(M) = C and sends C to Alice. Only Alice knows the decryption key, so only Alice can compute D_A(C) = D_A(E_A(M)) = M. Unless there is some failure in the system, Alice knows that no one intercepting the transmission of C will be able to recover the message M. However, anyone might have sent her this message, and even Bob might have leaked the message to others.

Bob signs a message M and sends it to Alice: This mode uses the special property 4. above of the RSA cryptosystem. (Other systems usually don't have property 4., but it is still possible to create digital signatures in a more complicated way.) Bob uses his secret decryption key on the message itself (rather than on ciphertext). For RSA, the collection of all possible messages is the same as the collection of all possible ciphertexts: any integer less than some fixed integer n. Thus Bob calculates D_B(M) = S. At the other end, Alice can retrieve Bob's public key E_B from the key authority and use it to recover the message, by calculating E_B(S) = E_B(D_B(M)) = M. Anyone can fetch Bob's public key and do this calculation, so there is no secrecy here, but assuming the system does not break down (that the key authority works and that the cryptosystem is not leaked or stolen or broken), only Bob can have signed this message, so it must have originated with him.

Bob can use this same method to broadcast a message intended for everyone, and anyone can verify using Bob's public key that the message can only have originated with him.

Bob signs a secret message M and sends it to Alice: This can be done in two ways, with Bob using his secret key D_B and Alice's public key E_A: Calculate either E_A(D_B(M)) = C, or D_B(E_A(M)) = C'. In either case, Alice reverses the process, using her secret key D_A and Bob's public key E_B. There is one other slight problem with the RSA cryptosystem, because the maximum size of plaintext or ciphertext is less than an integer n_A for Alice, and is less than a different integer n_B for Bob. What happens then depends on which of these two integers is larger, for if n_A is the larger, then E_A(M) might be too large to be handled by D_B using a single block, so one would have the awkward business of breaking this into two blocks. However, in this case one can calculate D_B(M) first, and this is definitely less than the block size of the key E_A. In case the sizes are reversed, just do the two steps above in the opposite order also, so there is no need for more than one block even for a signed and secret message.

Notice that Alice knows the message must have originated with Bob, and that no one else can read it, giving both authentication and secrecy.

Bob uses a hash function to sign an arbitrarily long message using only one block: Here one just signs the hash code of the message. These matters will be discussed more thoroughly in the section on hash functions.