# 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: mme % N, where m ∈ ℤN
• The inverse RSA function is: ccd % 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 = (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 ccd % N. In other words, the RSA function mme % N is:

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