The RSA algorithm

RSA (Rivest, Shamir, Adleman, 1977; published in 1978) bases its security on two facts:

• It is easy to multiply two large primes and obtain a number $n$;
• It is extremely hard (with current computers, impractical for primes of $300$ digits) to factorise $n$ recovering $p$ and $q$.

Operating scheme.

1. Alice chooses two large primes $p,q$ and computes $n=pq$ and $\varphi(n) = (p-1)(q-1)$.
2. She chooses $e$ coprime with $\varphi(n)$ (public encoding key).
3. She computes $d$ such that $ed\equiv 1\pmod{\varphi(n)}$ (private decoding key). $d$ is the modular inverse of $e$.
4. She publishes $(n,e)$. She keeps secret $d$, $p$, $q$.
5. Bob, to send the message $m\in\{0,\ldots,n-1\}$, computes $c = m^e\bmod n$ and sends $c$.
6. Alice decodes: $m = c^d\bmod n$, thanks to Euler $c^d \equiv m^{ed} \equiv m^{1+k\varphi(n)} \equiv m\cdot 1 \equiv m\pmod n$.

Remark — Why it works in practice

All the encoding/decoding operations are done in polynomial time ($O(\log^3 n)$ with fast exponentiation). The only step that would require exponential time is factorising $n$: with primes $p,q$ of $1024$ bits each ($\approx 300$ decimal digits) no known computer can do it in reasonable time. RSA’s security rests on this asymmetry. The scenario will change if and when quantum computing makes Shor’s algorithm feasible: it is one of the reasons for the development of post-quantum cryptography.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Crittografia rsa · Funzione di eulero
Skills: Modellizzare
People: Adleman · Rivest · Shamir