RSA Security 5.2.2 manual Cryptography Overview

Cryptography Overview

below. To compute ciphertext c from a plaintext message m, find c = me mod n. To decrypt, determine the private key d, the inverse of e, and compute m = cd mod n. The relationship between e and d ensures that the algorithm correctly recovers the original message m, because cd = (me)d = med ≡ m1 = m mod n. Only the entity that knows d can decrypt.

The security of the system relies on the fact that if you know p, q and e, it is easy to compute d; but if you know only n and e, it is more difficult to determine d. This is due to the following property of the math: the value d is actually not the inverse of e mod n, but rather the inverse of e mod (p–1)(q–1). The value you pick for e must be relatively prime to (p–1)(q–1), which means e and (p–1)(q–1) share no common factors, so that there exists d such that ed ≡ 1 mod (p–1)(q–1). Therefore, you find the private value using a modulus of (p–1)(q–1), but when you apply the RSA algorithm to encryption or decryption, you use a modulus of n = p·q.

Why, if d is the inverse of e mod (p–1)(q–1), does cd = (me)d = med = m1 = m mod n? Aren’t we mixing moduli? That is the quirk of the math; it may seem counterintuitive, but this mixing of moduli is what makes the algorithm work. A complete proof of this fact is beyond the scope of this chapter, so if you want to learn more about the underlying mathematical principle, find a math book that discusses Euler’s phi- function.

Incidentally, in practice, you would generally pick e, the public exponent first, then find the primes p and q, which satisfy the requirement that e be relatively prime to (p– 1)(q–1).

Consider the following example with small numbers. Choose public exponent e = 3. Then, let p = 5 and q = 11, which means n = 55 and (p–1)(q–1) = 40. This is a valid p and q combination because 3 is relatively prime to 40. The inverse of 3 mod 40 is 27.

(3·27) = 81

81– (2·40) = 81 – 80 = 1 3·27 = 1 mod 40

Apply the RSA algorithm with these parameters to the “plaintext message” m = 2.

c = me = 23 = 8 mod 55

This yields an encrypted message of 8.

To decrypt, raise the message to the power of the inverse of 3, which is 27.

cd = 827 mod 55

Rather than computing 827 directly, a shortcut would be to compute:

816+8+2+1 = 816·88·82·81 = 2 mod 55

C h a p t e r 3 C r y p t o g r a p h y 5 3