How RSA works

The fundamental idea behind RSA is to try to construct a trap-door or one-way function on a set $X$ , that is, an invertible function

$$E : X \rightarrow X$$

such that it is easy for Nikita to compute $E^{-1}$ , but extremely difficult for anybody else to do so.

Here is how Nikita makes a one-way function $E$ on the set of integers modulo $n$ .

1. Using a method hinted at in Section 2.4, Nikita picks two large primes $p$ and $q$ , and lets $n=pq$ .
2. It is then easy for Nikita to compute
   $$\varphi (n) = \varphi (p)\cdot \varphi (q) = (p-1)\cdot (q-1).$$

3. Nikita next chooses a random integer $e$ with
   $$1<e<\varphi (n)$$ and $$\gcd(e,\varphi (n))=1.$$

4. Nikita uses the algorithm from Section 2.3.2 to find a solution $x=d$ to the equation
   $$ex \equiv 1\pmod{\varphi (n)}.$$

5. Finally, Nikita defines a function $E:\mathbb{Z}/n\mathbb{Z}{} \rightarrow \mathbb{Z}/n\mathbb{Z}{}$ by
   $$E(x) = x^e \in \mathbb{Z}/n\mathbb{Z}{}.$$
   Anybody can compute $E$ fairly quickly using the repeated-squaring algorithm from Section 2.3.2.

Nikita's public key is the pair of integers $(n,e)$ , which is just enough information for people to easily compute $E$ . Nikita knows a number $d$ such that $ed\equiv 1\pmod{\varphi (n)}$ , so, as we will see, she can quickly compute $E^{-1}$ .

To send Nikita a message, proceed as follows. Encode your message, in some way, as a sequence of numbers modulo $n$ (see Section 3.2.2)

$$m_1, \ldots, m_r \in \mathbb{Z}/n\mathbb{Z}{},$$

then send

$$E(m_1), \ldots, E(m_r)$$

to Nikita. (Recall that $E(m) = m^e$ for $m\in \mathbb{Z}/n\mathbb{Z}{}$ .)

When Nikita receives $E(m_i)$ , she finds each $m_i$ by using that $E^{-1}(m) = m^d,$ a fact that follows from the following proposition.

Proposition 3.2 (Decryption key)   Let $n$ be an integer that is a product of distinct primes and let $d,e\in\mathbb{N}$ be such that $p-1\mid de-1$ for each prime $p\mid n$ . Then $a^{de} \equiv a\pmod{n}$ for all $a\in\mathbb{Z}$ .

Proof. Since $n\mid a^{de}-a$ if and only if $p\mid a^{de}-a$ for each prime divisor $p$ of $n$ , it suffices to prove that $a^{de}\equiv a\pmod{p}$ for each prime divisor $p$ of $n$ . If $\gcd(a,p)\neq 1$ , then $a\equiv 0\pmod{p}$ , so $a^{de}\equiv a\pmod{p}$ . If $\gcd(a,p)=1$ , then Theorem 2.1.19 asserts that $a^{p-1}\equiv 1\pmod{p}$ . Since $p-1\mid de-1$ , we have $a^{de-1} \equiv 1\pmod{p}$ as well. Multiplying both sides by $a$ shows that $a^{de}\equiv a\pmod{p}$ . $\qedsymbol$

Thus to decrypt $E(m_i)$ Nikita computes

$$E(m_i)^d = (m_i^{e})^{d}=m_i.$$

SAGE Example 3.2   We implement the RSA cryptosystem using SAGE. The function rsa below creates a key with (at most) the given number of bits, i.e., if bits is 20, it creates a key $n=pq$ where $n$ is approximately $2^{20}$ . Typical real-life cryptosystems would choose $512$ , $1024$ , or $2048$ bit keys (try generating large keys yourself using SAGE--how long does it take?).

sage: def rsa(bits):
...    # only prove correctness up to 1024 bits
...    proof = (bits <= 1024)  
...    p = next_prime(ZZ.random_element(2**(bits//2 +1)), 
...                proof=proof)
...    q = next_prime(ZZ.random_element(2**(bits//2 +1)), 
...                proof=proof)
...    n = p * q
...    phi_n = (p-1) * (q-1)
...    while True:
...        e = ZZ.random_element(1,phi_n)
...        if gcd(e,phi_n) == 1: break
...    d = lift(Mod(e,phi_n)^(-1))
...    return e, d, n
...
sage: def encrypt(m,e,n):
...    return lift(Mod(m,n)^e)
...
sage: def decrypt(c,d,n):
...    return lift(Mod(c,n)^d)
...    
sage: e,d,n = rsa(20)
sage: c = encrypt(123, e, n)
sage: decrypt(c, d, n)           
123