Filter
Top Products
Chapter 3 Cryptography 53
Cryptography Overview
below. To compute ciphertext c from a plaintext message m, find c = m
e
mod n. To
decrypt, determine the private key d, the inverse of e, and compute m = c
d
mod n. The
relationship between e and d ensures that the algorithm correctly recovers the original
message m, because c
d
= (m
e
)
d
= m
ed
≡ m
1
= 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 c
d
= (m
e
)
d
= m
ed
= m
1
= 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 = m
e
=2
3
=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.
c
d
=8
27
mod 55
Rather than computing 8
27
directly, a shortcut would be to compute:
8
16+8+2+1
=8
16
·8
8
·8
2
·8
1
= 2 mod 55