2: The RSA Function

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 ↦ m^e % N, where m ∈ ℤ_N
• The inverse RSA function is: c ↦ c^d % 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.

Security Properties

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 ↦ c^d % N. In other words, the RSA function m ↦ m^e % N is:

• easy to compute given N and e
• hard to invert given N and e but not d
• easy to invert given d