RSA public-key cryptosystem
Exchanging messages
In RSA, we use number theory to develop a way to exchange messages securely rather than simply a key. As with DHKE, modular exponentiation plays an important part.
As usual, Alice wishes to send a message to Bob. Bob makes this possible by generating a pair of keys, one public and one private. He publishes to the world the public one. Alice uses the public key to encrypt a message for Bob and sends him the ciphertext. Bob uses his private key to decrypt.
Unlike the private-key systems we’ve seen, in this system different (but related!) keys are used for encryption and for decryption.
Generating keys
Bob does the following:
1. Generates two large prime numbers 𝑝, 𝑞.
2. Forms their product 𝑛 = 𝑝 ⋅ 𝑞
3. Modulo (𝑝 − 1)(𝑞 − 1), finds a value 𝑒 that has a
multiplicative inverse. Let 𝑑 be that inverse. In other
words𝑒−1 ≡𝑑𝑚𝑜𝑑(𝑝−1)(𝑞−1).
4. Publishes 𝑛, 𝑒 and keeps 𝑝, 𝑞, 𝑑 secret. I have emphasized
this by coloring private values red, public values green.
Alice sends a message
Alice wishes to send the message 𝑚, which is an integer less than 𝑛. She computes 𝑐 = 𝑚𝑒 𝑚𝑜𝑑 𝑛 and sends 𝑐 to Bob. Bob calculates 𝑐𝑑 𝑚𝑜𝑑 𝑛. As we will see, this will equal 𝑚.
Doing the calculations
Encryption and decryption require calculating modular exponents. This can be done very efficiently, although the number of steps will depend on the number of bits in the public keys. Here’s the pseudocode, adapted from an exponentiation algorithm called repeated squaring.
ModExp(b, e, m)
if e == 0 then return 1
if e % 2 == 0 then
return ModExp(b*b % m, e/2, m) % m
else
return b * ModExp(b, e-1, m) % m
For key generation, we will need a way generate large prime numbers and for finding modular multiplicative inverses. Note that the security of RSA rests on the belief that multiplication is a one-way function. For some
values 𝑎, 𝑏, it is difficult to quickly compute the factors of 𝑎 ⋅ 𝑏. In other words, factoring some integers is hard.
Proof that decryption works
Here is a series of equations that shows how Bob’s decryption of Alice’s ciphertext yields the Alice’s plaintext. Notation: 𝑎 ≡𝑛 𝑏 means the same thing as 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛.
𝑦𝑑 ≡𝑛 (𝑥𝑒)𝑑 (1)
≡𝑛 𝑥𝑒𝑑 (2)
≡𝑛 𝑥1+𝑘(𝑝−1)(𝑞−1) (3)
≡𝑛 𝑥1+𝑘𝜑(𝑛) (4)
≡𝑛 𝑥 ⋅ 𝑥𝑘𝜑(𝑛)
(5) ≡𝑛 𝑥 ⋅ (𝑥𝜑(𝑛))𝑘 (6)
≡𝑛 𝑥 ⋅ 1𝑘 (7) ≡𝑛𝑥 (8)
Equivalence (1): by definition of 𝑦
Equivalence (2): by rules of exponentiation
Equivalence (3): because 𝑒𝑑 ≡(𝑝−1)(𝑞−1) 1
Equivalence (4): by definition 𝑛, 𝜙(𝑛) = (𝑝 − 1)(𝑞 − 1) Equivalence (5): by rules of exponentiation
Equivalence (6): by rules of exponentiation
Equivalence (7): Euler’s theorem
Equivalence (8): simple
Explanation of equivalences 3, 4, and 7
Equivalence (3): Recall that once 𝑒 was chosen, 𝑑 was computed as the multiplicative inverse of 𝑒 modulo (𝑝 − 1)(𝑞 − 1). That is,
𝑒𝑑 ≡ 1 𝑚𝑜𝑑 (𝑝 − 1)(𝑞 − 1)
This equivalence means that there is some integer 𝑘 such that
𝑒𝑑 = 𝑘(𝑝 − 1)(𝑞 − 1) + 1 Equivalence (4): Recall that 𝜙(𝑛) = (𝑝 − 1)(𝑞 − 1).
Equivalence (7): Euler’s theorem states that if gcd(𝑥, 𝑛) = 1 then 𝑥𝜙(𝑛) ≡𝑛 1. We assume that Alice’s message 𝑥 does not share a factor greater than 1 with 𝑛. If it did, then Alice could factor Bob’s 𝑛 and so discover his secret keys. The probability of that is extremely small.