# 2: The RSA Function

- Page ID
- 7398

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*, where^{e}% N*m*∈ ℤ_{N} - The inverse RSA function is:
*c*↦*c*, where^{d}% N*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 *d*power. 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*is:

^{e}% N- easy to compute given
*N*and*e* - hard to invert given
*N*and*e*but not*d* - easy to invert given
*d*