RSA Theory
The RSA algorithm is a public key algorithm that can be used to send an encrypted message without a separate exchange of secret keys. It can also be used to sign a message.
This page looks at the mathematics behind the algorithm. We discuss the RSA algorithm and its implementation in more detail on our RSA Algorithm page.
Contents
- The RSA cryptosystem
- Key generation
- RSA Encryption scheme
- RSA Signature scheme
- First proof
- Second proof
- Longer proof of the RSA algorithm
- Using λ(n) instead of φ(n)
- Revision History
- Rate this page
- Feedback
- Comments
You will need some understanding of elementary number theory. First a quick summary of the RSA cryptosystem.
The RSA cryptosystem
Recommended reading
- An Introduction to Mathematical Cryptography by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman.
- Davenport, H, The Higher Arithmetic: An Introduction to the Theory of Numbers, Cambridge University Press, 1999
Affiliate disclosure: we get a small commission for purchases made through the above links
Key generation
- Choose two distinct primes $p$ and $q$ of approximately equal size so that their product $n = pq$ is of the required bit length.
- Compute $\phi(n)=(p-1)(q-1)$.
- Choose a public exponent $e$, $1 \lt e \lt \phi(n)$, which is coprime to $\phi(n)$, that is, $\gcd(e,\phi(n))=1$.
- Compute a private exponent $d$ that satisfies the congruence $ed \equiv 1 \pmod {\phi(n)}$.
- Make the public key $(n, e)$ available to others. Keep the private values $d$, $p$, $q$, and $\phi(n)$ secret.
RSA Encryption scheme
Encryption rule: ciphertext, $c =\sc{RSA}\sc{PUBLIC}(m)=m^e \bmod n$, where $1 \lt m \lt n-1$.
Decryption rule: plaintext, $m =\sc{RSA}\sc{PRIVATE}(c)=c^d \bmod n$.
Inverse transformation: $m =\sc{RSA}\sc{PRIVATE}(\sc{RSA}\sc{PUBLIC}(m)$).
RSA Signature scheme
Signing: signature, $s = \sc{RSA}\sc{PRIVATE}(m)=m^d \bmod n$, where $1 \lt m \lt n-1$.
Verification: check, $v = \sc{RSA}\sc{PUBLIC}(s)=s^e \bmod n$.
Inverse transformation: $m = \sc{RSA}\sc{PUBLIC}(\sc{RSA}\sc{PRIVATE}(m))$
First, note that the inverse transformations for encryption and signing are equivalent, since
$\sc{RSA}\sc{PUBLIC}(\sc{RSA}\sc{PRIVATE}(m)) = (m^d \bmod n)^e \bmod n = m^{ed} \bmod n$
So we only need to show that the decryption rule works; that is, for $(n, e, d)$ as defined above,
All proofs of how RSA works boil down to the fact that for any integer $x$, $x^{1+k\phi(n)} \equiv x \pmod n$.
Note that the algorithm strictly works for $0 \le m \lt n$, but we exclude the values $m = 0, 1$ and
$m = n-1$ from the cryptosystem because there is no secrecy for such messages.
—Can you think why? Put your answers in the comments below.
First proof
The first proof is short. It uses the Euler-Fermat Theorem. It works for messages $m$ that are relatively prime to the modulus $n$, that is where $\gcd(m, n) = 1$.
Proof.
Consider the case where $\gcd(m,n) =1$. The relation $ed \equiv 1 \pmod {\phi(n)}$ gives that $ed = 1 + k\phi(n)$ for some integer $k$. Now suppose $c = m^e\bmod n$. This is equivalent to $c\equiv m^e\pmod n$. So, working modulo $n$, \[ \begin{align*} c^d &\equiv m^{ed} \\ &\equiv m^{1+k\phi(n)} \\ &\equiv m\cdot(m^{\phi(n)})^k \\ &\equiv m\cdot 1^k, \text{ because }m^{\phi(n)}\equiv 1 \text{ by the Euler-Fermat theorem, since } \gcd(m,n)=1 \\ &\equiv m \pmod n. \end{align*} \]Hence $c = m^e \bmod n \implies c^d \equiv m\pmod n \implies m = c^d \bmod n$. Thus the decryption rule is proven. $\blacksquare$
Second proof
The first proof does not include the special cases where the message $m$ is divisible by one of the prime factors, $p$ or $q$. There are $p$ numbers where $q|m$: that is, $m = 0, q, 2q, 3q, ..., (p-1)q$. Similarly there are $q$ numbers where $p|m$, and thus $p+q-1$ possible numbers where $\gcd(m, n)\gt 1$ (zero occurs twice). Note that $p$ and $q$ cannot both divide $m$ since we restrict $m \lt n = pq$.
The second proof specifically considers the case where $\gcd(m, n) \gt 1$, but it could easily be written to include the first case above (if $\gcd(q, n)=1$ then just say "Similarly for q" after the result mod $p$). It uses Fermat's Little Theorem and the rule† that if $s$ and $t$ are coprime and $a \equiv b \pmod s$ and $a \equiv b \pmod t$, then $a \equiv b \pmod {st}$.
Proof. a ≡ b (mod s) ⇒ s|a-b; and a ≡ b (mod t) ⇒ t|a-b. Since s and t are coprime then st|a-b. Hence a ≡ b (mod st). $\blacksquare$
Proof. Suppose one of the primes, say $q$, divides $m$. Then $m \equiv 0 \pmod q$ and so, trivially, we have
\[ 0 \equiv m^{1+k\phi(n)} \equiv m \pmod q \]If $q$ divides $m$ then $p$ cannot also divide $m$ since $m \lt n = pq$ and so we must have $\gcd(m, p) = 1$. By Fermat's Little Theorem we have
\[ \begin{align*} m^{p-1} &\equiv 1 \pmod p \\ m^{(p-1)(q-1)} &\equiv 1^{q-1} \equiv 1\pmod p, \quad\text{raising both sides to the power } q-1 \\ m^{\phi(n)} &\equiv 1, \quad\text{since }\phi(n) = \phi(pq) = (p-1)(q-1) \\ m^{k\phi(n)} &\equiv 1^k \equiv 1\pmod p, \quad\text{raising both sides to the power }k \\ m^{1+k\phi(n)} &\equiv m \pmod p, \quad\text{multiplying both sides by }m \end{align*} \]Now since $m^{1+k\phi(n)}\equiv m \pmod q$ and $m^{1+k\phi(n)}\equiv m \pmod p$, and $p$ and $q$ are coprime, then it follows that (see † above)
\[ m^{1+k\phi(n)}\equiv m \pmod {pq} \equiv m \pmod n, \quad\text{for all integers }m. \]We have $ed\equiv 1\pmod {\phi(n)} \implies ed = 1 + k\phi(n)$. So, if $c \equiv m^e \pmod n$ then $c^d\equiv m^{ed} \equiv m^{1+k\phi(n)} \equiv m \pmod n$; that is, $m = c^d \bmod n$
Hence $c = m^e \bmod n \implies m = c^d \bmod n$ and the decryption rule is proven. $\blacksquare$
Longer proof of the RSA algorithm
We wrote this proof of the RSA algorithm (pdf, 93 kB) back in 2006, and that in turn is a revised version of something we wrote in 2002. It uses very elementary principles of number theory. Apologies to all university tutors who have received plagiarised versions in students' assignments. The PDF document was written in LaTex and generated on a Windows system using the wonderful TeXniCenter.
Using λ(n) instead of φ(n)
The original version of RSA defined the secret exponent as $d=e^{-1} \pmod {\phi(n)}$ where $\phi$ is the the Euler totient function and $\phi(n)=\phi(pq)=(p-1)(q-1)$. In fact you can use the smaller Charmichael function instead, so that an alternative secret exponent (we'll call it $d'$) is defined by $d'=e^{-1}\pmod {\lambda(n)}$, where \[ \lambda(n) =\text{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\gcd(p-1,q-1)} \] and $\text{lcm}$ denotes the least common multiple.
Later refinements of the RSA algorithm like PKCS#1 use this definition.
But it doesn't matter which one you use. Both $d$ and $d'$ will give you the same results.
Note that the proofs above use the fact that $x^{1+k\phi(n)}\equiv x\pmod n$ for any integer $x$. Well, by definition, $x^{\lambda(n)}\equiv 1\pmod n$, so we can just write $x^{1+k\lambda(n)}\equiv x\pmod n$, and all the proofs above will still work.
Both values of $d$ and $d'$ will uniquely decrypt a ciphertext $c$ encrypted with $c=m^e\bmod n$, and both will give the same signature $s=m^d\bmod n = m^{d'}\bmod n$.
In fact, any secret exponent of the form $d'+r\lambda(n)$ will work, for any integer $r$. Since $\lambda(n)$ divides $\phi(n)$, then our $d$ is one of these.
For practical values of n in the thousands of bits, the difference between $d$ and $d'$ is a couple of bits and makes no practical difference.
Revision History
- 24 August 2025: improved wording in proofs, edited to use MathJax.
- 1 November 2011: added alternative shorter proofs.
- 2 October 2006: re-written and published in LaTex format.
- 18 September 2004: updated HTML format.
- April 2002: first published a proof in HTML format.
Rate this page
Feedback
To contact us, please send us a message. To make a comment see below.
This page last updated 9 September 2025
Comments