The RSA function is defined as follows:
- Let p and q be distinct primes (later we will say more about how they are chosen), and let N = pq. N is called the RSA modulus.
- Let e and d be integers such that ed ≡ϕ(N) 1. That is, e and d are multiplicative inverses mod ϕ(N) — not mod N! e is called the encryption exponent, and d is called the decryption exponent. These names are historical, but not entirely precise since RSA by itself does not achieve CPA security.
- The RSA function is: m ↦ me % N, where m ∈ ℤN
- The inverse RSA function is: c ↦ cd % N, where c ∈ ℤN .
Essentially, the RSA function (and its inverse) is a simple modular exponentiation. The most confusing thing to remember about RSA is that e and d “live” in ℤ∗ϕ(N), while m and c “live” in ℤN.
Let’s make sure the the function we called the “inverse RSA function” is actually in inverse of the RSA function. The RSA function raises its input to the e power, and the inverse RSA function raises its input to the dpower. So it suffices to show that raising to the ed power has no effect modulo N.
Since ed ≡ϕ(N) 1, we can write ed = tϕ(N) + 1 for some integer t. Then:
Note that we have used the fact that mϕ(N) ≡N 1 from Euler’s theorem.
In these notes we will not formally define a desired security property for RSA. Roughly speaking, the idea is that even when N and e can be made public, it should be hard to compute the operation c ↦ cd % N. In other words, the RSA function m ↦ me % N is:
- easy to compute given N and e
- hard to invert given N and e but not d
- easy to invert given d