by Lawrence Ioannou
This can also be viewed in its original poster form.

Bob wants to receive a private message (plaintext) from Alice so that no eavesdropper (Eve) may read it. Alice (in private) encrypts a message using a secret key and sends the encrypted message (ciphertext) to Bob who (in private) decrypts the message with the same secret key that Alice used. Problems

1. Alice and Bob each must have a copy of the secret key prior to Alice sending the ciphertext to Bob;if Alice and Bob are far apart, then they need a secure channel to communicate this key, but do not have access to one (if they did, Alice could just use it to send Bob the private message!);
2. with every other sender from whom Bob would like to receive private messages, he must establish a secret key just as he did with Alice.

Solution: Remove Alice's need for a secret key - make the encryption key (and thus the entire encryption procedure) public.

Bob wants to receive private messages from Alice as well as anyone else who pleases to send Bob private messages (Andrea, Artur,...). Thus he publishes an encryption key. This allows anyone to encrypt a message and send the ciphertext to Bob so that Bob can recover the message.One can think of Bob's publishing an encryption key as setting up a publicly accessible postbox for himself. Just as anyone can drop a letter into a postbox, anyone can encrypt a message and send it to Bob. The only participant who needs a secret key is Bob. He can create the key himself in private. Thus no prior secret communication is necessary. A postbox with a one-way chute and a trapdoor that opens with a secret key is implemented mathematically by a trapdoor (one-way) function, i.e. a function that is easy to compute but whose inverse is difficult to compute without some extra secret information. Alice uses the trapdoor function to encrypt the message. The output of the function is the ciphertext. She sends the ciphertext to Bob, who can decrypt (invert the function) because he has the secret key.

The idea behind public-key cryptography is to make encryption easy and publicly accessible to everyone, but to make decryption difficult for everyone except the intended recipient of the message, Bob. It is useful to view encryption as part of a mathematical function ƒ, mapping plaintexts to ciphertexts, and decryption as the mathematical inverse of ƒ. Five properties required of ƒ are

1. ƒ is one-to-one (so it is uniquely invertible);
2. ƒ is easy to compute (so encryption is easy);
3. ƒ ^-1 is difficult to compute (so decryption is difficult for the senders);
4. ƒ has a domain that is easy to sample from (so Bob can generate a key easily);
5. there is an easy-to-compute function d of the input of ƒ that makes computing ƒ ^-1 easy (so Bob can decrypt easily). Properties (i)-(iii) say that ƒ is one-way, while properties (iv) and (v) make ƒ a trapdoor function.

As an example, a function that is widely believed to be a trapdoor function is

ƒ(x,e,p,q) = (x^e mod pq, pq, e),

where p and q are prime numbers, x is the (encoded) plaintext, and y=x^e mod pq is the ciphertext (a mod b is the remainder after dividing a by b). In this case, the function d from property (v) is

d(x,e,p,q)=e^-1 mod (p-1)(q-1), that is, ed mod (p-1)(q-1) = 1.

This trapdoor function f is the basis for the RSA Cryptosystem: (e,pq) is the public encryption key and (p,q,d) is the secret decryption key.

Some mathematical definitions

Z_n = {0,1,2,3,..,n-1}

a = b (mod n) means that b-a = kn for some k

gcd(a,b) = greatest common divisor of a and b

Φ(n) = the number of positive integers a less than n such that gcd(a,n) = 1



A main ingredient of the RSA Cryptosystem is Euler’¡Çs theorem

a^Φ(n) = 1 (mod n) if gcd(a,n) = 1

If Bob wants to use the RSA Cryptosystem to receive private messages from anyone, he

• finds two large prime numbers p and q, and computes n = pq and Φ(n) = (p-1)(q-1);
• finds an element of Z_n with gcd(e,n) = 1, and computes d such that ed = 1 (mod Φ(n));
• publishes the encryption key (e,n) and keeps secret the decryption key (p,q,d).

If Alice wants to send a message x to Bob (it is assumed that all messages that Bob would like to receive are in one-to-one correspondence with the elements of Z_n), she computes y = x^e mod n, and sends y to Bob (across a public, insecure channel).To decrypt Alice's message, Bob finally computes x=y^d mod n.

Note that

• Bob can use the Miller-Rabin primality testing algorithm to find p and q;
• Bob uses the Extended Euclidean Algorithm to test that gcd(e,n)=1 and to compute d;
• if gcd(x,n)=1, then Euler's theorem guarantees that the decryption works
  
  y^d = (x^e)^d = x^ed = x^{kΦ(n) + 1} = (x^Φ(n))^kx = (1)^kx = x (mod n);
  
  
• if gcd(x,n) ≠ 1, then the Chinese Remainder Theorem guarantees sound decryption;
• knowledge of Φ(n) allows d to be easily computed, thus the security of the RSA Cryptosystem depends on the assumption that n is difficult to factor and Φ(n) is difficult to compute when n is large (hence the need for large p and q).

There are public-key cryptosystems other than the RSA Cryptosystem

• McEliece Cryptosystem: this cryptosystem is based on the NP-complete problem of decoding a linear code in algebraic coding theory;
• ElGamal Cryptosystem: this cryptosystem is based on the difficulty of the discrete logarithm problem for finite fields
• Elliptic Curve Cryptosystems: these are modifications of other systems (e.g. the ElGamal Cryptosystem) that work in the domain of elliptic curves rather than finite fields; these systems are widely used in handheld wireless devices because they remain secure with smaller keys compared to other systems (computing with smaller keys requires less battery power)

A public-key cryptosystem can never provide unconditional security, since an eavesdropper who observes a ciphertext y can use the public encryption rule eK to encrypt every possible plaintext x until she discovers the unique x such that y = e_K(x)

Many public-key cryptosystems can be broken with a quantum computer. For example, the RSA cryptosystem can be broken because quantum computers can factor large numbers quickly. For more information, see Nielsen, Michael A. and Chuang, Isaac L., Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000

It was disclosed in 1997 that public-key cryptography, including the RSA cryptosystem, was first invented at the British intelligence agency GCHQ in the late 1960s and early 1970s by Ellis and Cocks (for more information click here); however, in 1976, Diffie and Hellman independently discovered public-key cryptography and, in 1977, Rivest, Shamir, and Adleman independently discovered the RSA cryptosystem.

More information about one-way and trapdoor functions and the notions of easy and difficult computational problems can be found in Papadimitriou, Christos H., Computational Complexity, Addison-Wesley, Reading, Massachusetts, 1994.

More information about RSA, its security, and cryptography in general can be found in Stinson, Douglas R., Cryptography: Theory and Practice, CRC Press, Boca Raton, 1995.

Quantum Cryptography is another method that solves the problem of key distribution. Read our mini tutorial here.