Diffie and Hellman introduced a new approach to cryptography, and challenged cryptologist to design a general-purpose encryption algorithm that satisfies the public-key encryption requirements. One of the first responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir, Len Adleman at MIT. Since then, the Rivest-Shamir-Adleman (RSA) scheme has become the most widely accepted and implemented general-purpose approach to public-key encryption.

The RSA scheme is a block cipher. Each plaintext block is an integer between 0 and n − 1 for some n, which leads to a block size ≤ log2(n). The typical size for n is 1024 bits. The details of the RSA

algorithm are described as follows.

**Key generation:**

- Pick two large prime numbers p and q, p /= q;
- Calculate n = p × q;
- Calculate _(n) = (p − 1)(q − 1);
- Pick e, so that gcd(e, _(n)) = 1, 1 < e < _(n);
- Calculate d, so that d ・ e mod _(n) = 1, i.e., d is the multiplicative inverse of e in mod _(n);
- Get public key as KU = {e, n};
- Get private key as KR = {d, n}.

**Encryption:**

For plaintext block P < n, its ciphertext C = Pe mod n.

**Decryption:**

For ciphertext block C, its plaintext is P = Cd mod n.

**RSA is secure:**

The premise behind RSA’s security is the assumption that factoring a big number (n into p, and q) is hard. And thus it is difficult to determine _(n). Without the knowledge of _(n), it would be hard to

derive d based on the knowledge of e. However factoring n is not the only way to break RSA.