THE GARDEN

RSA (Textbook Construction)

Updated 13 Sep 2026

• •

  What it is

  • •

    RSA is a public-key cryptosystem built on modular exponentiation. Key generation picks two large primes $p, q$, forms the modulus $N=pq$, computes Euler's totient $\phi(N)=(p-1)(q-1)$, and picks a public exponent $e$ coprime to $\phi(N)$ (commonly 65537) with a matching private exponent $d \equiv e^{-1} \pmod{\phi(N)}$. Encryption is $c \equiv m^e \pmod N$; decryption is $m \equiv c^d \pmod N$ — these invert each other precisely because $ed \equiv 1 \pmod{\phi(N)}$, so by Euler's theorem $m^{ed} \equiv m \pmod N$. Signing reverses the roles: the signer computes $S \equiv H(m)^d \pmod N$ using their own private key, and anyone can verify by checking $S^e \equiv H(m) \pmod N$ using the signer's public key — proving the signer (and only the signer) produced $S$, without needing to keep $m$ secret.

• •

  When to apply

  • •

    The starting point for reasoning about any RSA challenge — every attack in this domain (weak parameters, small exponents, shared moduli, leaked private data) is a deviation from this baseline that breaks one of its security assumptions.

• •

  Symbols and assumptions

  • •

    $p,q$ are distinct primes; $N=pq$; $\varphi(N)=(p-1)(q-1)$. Public exponent $e$ is coprime to $\varphi(N)$; private exponent $d$ satisfies $ed\equiv1\pmod{\varphi(N)}$. Message representative: $0\le m<N$.

• •

  Math — step by step

  • •
    1. Choose $d=e^{-1}\bmod\varphi(N)$, so $ed=1+k\varphi(N)$ for an integer $k$. Encrypt $c=m^e\bmod N$ and decrypt $c^d\bmod N$.
  • •
    2. For a unit $m$, Euler’s theorem gives $m^{ed}=m(m^{\varphi(N)})^k\equiv m$. For arbitrary $m$, prove the equality separately modulo $p$ and $q$: if $m$ is zero the claim is immediate; otherwise Fermat applies. CRT then gives equality modulo $N$.
  • •
    3. Factoring $N$ exposes $\varphi(N)$ and hence $d$. These equations describe textbook RSA; secure encryption additionally needs an appropriate randomized encoding such as OAEP.
• •

  Worked example

  • •

    Take $p=5,q=11$: $N=55$, $\varphi=40$. Choose $e=3$; $d=27$ because $3\cdot27=81=1+2\cdot40$.

  • •

    Encrypt $m=7$: $c=7^3\bmod55=343\bmod55=13$. For decryption, $13^2\equiv4$, $13^4\equiv16$, $13^8\equiv36$, $13^{16}\equiv31$.

  • •

    Since $27=16+8+2+1$, $13^{27}\equiv31\cdot36\cdot4\cdot13\equiv16\cdot4\cdot13\equiv9\cdot13\equiv7\pmod{55}$. Check: pow(pow(7, 3, 55), 27, 55) == 7.

• •

  Common pitfalls worth recognizing on sight

  • •

    $e = 1$: encryption is the identity function, $c = m$ — no decryption needed.

  • •

    $N$ is prime, not a semiprime: $\phi(N) = N - 1$ directly, no factoring needed.

  • •

    $p = q$: $N = p^2$ — see RSA with p = q (Repeated Prime Factor).

  • •

    Small $e$ (e.g. 3) without proper padding — see Low-Exponent Cube-Root Attack (Unpadded RSA) and Hastad's Broadcast Attack.

• •

  Python

  • •

    from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
    N = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    c = pow(bytes_to_long(message), e, N)
    m = long_to_bytes(pow(c, d, N))
    

• •

  Related

  • •

    Chinese Remainder Theorem

  • •

    Extended Euclidean Algorithm

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What relationship between e, d, and φ(N) makes RSA encryption and decryption invert each other?

    • •

      ed ≡ 1 (mod φ(N)), so by Euler's theorem m^(ed) ≡ m (mod N).

  • •

    How does RSA signing differ from RSA encryption in terms of which key is used?

    • •

      Signing uses the signer's own private key on the message (or its hash); encryption uses the recipient's public key.

◌ Explore connections in Graph view