RSA public-key encryption
The RSA cryptosystem, named after its inventors R. Rivest, A. Shamir, and L. Adleman, is the most widely used public-key cryptosystem. It may be used to provide both secrecy and digital signatures and its security is based on the intractability of the integer factorization problem (§3.2). This section describes the RSA encryption scheme, its security, and some implementation issues; the RSA signature scheme is covered in §11.3.1.
8.1 Algorithm Key generation for RSA public-key encryption
SUMMARY: each entity creates an RSA public key and a corresponding private key. Each entity A should do the following:
- 1. Generate two large random (and distinct) prunes p and q, each roughly the same size.
- 2. Compute n = pq and & = (p - 1 )(q - 1). (See Note 8.5.)
- 3. Select a random integer e, 1 < e < Ф, such that gcd(e, ф) = 1.
- 4. Use the extended Euclidean algorithm (Algorithm 2.107) to compute the unique integer d, 1 < d < ф, such that ed= 1 (mod ф).
- 5. A’s public key is (n, e); A’s private key is d.
- 8.2 Definition The integers e and d in RSA key generation are called the encryption exponent and the decryption exponent, respectively, while n is called the modulus.
- 8.3 Algorithm RSA public-key encryption
SUMMARY: В encrypts a message m for A, which A decrypts.
- 1. Encryption. В should do the following:
- (a) Obtain .4’s authentic public key (n, e).
- (b) Represent the message as an integer m in the interval [0, n — 1].
- (c) Compute c = me mod n (e.g., using Algorithm 2.143).
- (d) Send the ciphertext c to A.
- 2. Decryption. To recover plaintext m from c, A should do the following:
- (a) Use the private key d to recover m = cd mod n.
Proof that decry ption works. Since ed = 1 (mod
there exists an integer к such that ed = 1 + кф. Now, if gcd(m, p) = 1 then by Fermat’s theorem (Fact 2.127),
Raising both sides of this congruence to the power k(q - 1) and then multiplying both sides by m yields
On the other hand, if gcd(m, p) = p, then this last congruence is again valid since each side is congruent to 0 modulo p. Hence, in all cases
By the same argument,
Finally, since p and q are distinct primes, it follows that
8.4 Example (RSA encryption with artificially small parameters)
Key generation. Entity A chooses the primes p = 2357, q = 2551, and computes n = pq = 6012707 and ф = (p - l)(g -1) = 6007800. A chooses e = 3674911 and, using the extended Euclidean algorithm, finds d = 422191 such that ed = 1 (mod &). A's public key is the pair (n = 6012707, e = 3674911), while A’s private key is d = 422191. Encryption. To encrypt a message m = 5234673, В uses an algorithm for modular exponentiation (e.g., Algorithm 2.143) to compute
and sends this to A.
Decryption. To decrypt c, A computes
8.5 Note (universal exponent) The number Л = lcm(p - 1, q — 1), sometimes called the universal exponent of n, may be used instead of ф = (p - 1)( - 1) in RSA key generation (Algorithm 8.1). Observe that A is a proper divisor of o. Using A can result in a smaller decryption exponent <7, which may result in faster decryption (cf. Note 8.9). However, if p and q are chosen at random, then gcd(p—1, q—1) is expected to be small, and consequently & and A will be roughly of the same size.