DonAsako - RSA Key Construction — From Two Primes to a Working Key Pair

Overview

An RSA key pair is built from two large prime numbers. From these two primes, we derive everything else: a public key that anyone can use to encrypt messages, and a private key that only the owner can use to decrypt them.

The whole construction follows five simple steps:

Pick two large primes $p$ and $q$
Compute the modulus $N = pq$
Compute $\phi(N)$
Choose a public exponent $e$
Compute the private exponent $d$ from $e$ and $\phi(N)$

That's it. The rest of the chapter walks through each step in detail.

Info

The security of RSA relies on the difficulty of factoring $N$. Even with the public key $(N, e)$, recovering $d$ requires factoring $N$ back into $p$ and $q$ — which is computationally infeasible for large enough $N$.

Generating $p$ and $q$

The first step is to pick two large prime numbers. "Large" here means hundreds of digits long: a typical modern key uses primes of around 1024 bits each (about 300 decimal digits).

To produce a modulus $N$ of bit length $t$, we pick $p$ and $q$ each of bit length $t/2$: $$ p, q \in \left[2^{(t-1)/2},\ 2^{t/2}\right) $$ This guarantees $N = pq$ has exactly $t$ bits.

Example

For $t = 2048$, we want $p$ and $q$ of $1024$ bits each, so: $$ p, q \in [2^{1023},\ 2^{1024}) $$

In practice, we don't pick a number and check if it's prime by trial division — the numbers are far too large. Cryptographic libraries use a fast probabilistic test called Miller–Rabin to find primes of any chosen size in milliseconds.

We will see further down that $p$ and $q$ also need to satisfy two additional conditions (a distance constraint and a compatibility check with $e$). For now, just keep in mind: two random large primes.

Exercices

1| What bit length should $p$ and $q$ have to produce a 3072-bit RSA modulus?

Solution

$1536$ bits each. In general, for a modulus of $t$ bits we pick primes of $t/2$ bits.

2| You generate $p = 1\,000\,003$ and $q = 1\,000\,033$. Both are prime, so why is this a bad RSA key?

Solution

$p$ and $q$ are far too close. $|p - q| = 30$, which is tiny compared to $\sqrt{N} \approx 10^6$. Fermat's factorization recovers them almost instantly, regardless of the size of $N$.

Computing $N$ and $\phi(N)$

\[ N = pq \]

\[ \phi(N) = (p-1)(q-1) \]

A tighter alternative used by modern standards (PKCS#1 v2.2, FIPS 186-4) is Carmichael's function: $$ \lambda(N) = \mathrm{lcm}(p-1,\ q-1) $$ Using $\lambda(N)$ instead of $\phi(N)$ produces a smaller $d$, which makes decryption faster. Both are valid: any $d$ satisfying $ed \equiv 1 \pmod{\lambda(N)}$ also works as a decryption exponent.

Exercices

1| Compute $N$, $\phi(N)$ and $\lambda(N)$ for $p = 11$ and $q = 23$.

Solution

$N = 11 \cdot 23 = 253$
$\phi(N) = 10 \cdot 22 = 220$
$\lambda(N) = \mathrm{lcm}(10, 22) = 110$

Note that $\lambda(N) = \phi(N)/2$ here because $\gcd(10, 22) = 2$.

Choosing the public exponent $e$

The standard choice is: $$ e = 2^{16} + 1 = 65537 $$ Three reasons:

It is prime, so $\gcd(e, p-1) = 1$ holds unless $(p-1)$ is a multiple of $65537$ — easy to check.
Its binary form is 10000000000000001 — only two bits set, so $m^e \bmod N$ is fast (16 squarings + 1 multiplication).
It is large enough to avoid attacks against very small exponents (e.g. Håstad's broadcast attack with $e = 3$).

Avoid $e = 3$ in production: it requires careful padding to remain secure.

Exercices

1| For $p = 23$ and $q = 67$, can we use $e = 11$ as the public exponent?

Solution

We need $\gcd(e, \phi(N)) = 1$. Here $\phi(N) = 22 \cdot 66 = 1452$. Since $11 \mid 22$, we have $\gcd(11, 1452) = 11 \neq 1$.

No, $e = 11$ is invalid, because it has no inverse modulo $\phi(N)$, so $d$ cannot be computed. We would need to pick a different $e$ (or different primes).

Computing the private exponent $d$

$d$ is the modular inverse of $e$ modulo $\phi(N)$ (or $\lambda(N)$): $$ d \equiv e^{-1} \pmod{\phi(N)} $$ This is computed using the Extended Euclidean Algorithm. The inverse exists if and only if $\gcd(e, \phi(N)) = 1$ — which is why we enforced that condition earlier.

Exercices

1| With $p = 11$, $q = 23$, $e = 3$, compute the private exponent $d$ using $\phi(N)$.

Solution

$\phi(N) = 220$. We need $3d \equiv 1 \pmod{220}$.

Using the Extended Euclidean Algorithm (or trial): $3 \cdot 147 = 441 = 2 \cdot 220 + 1$, so:

\[ d = 147 \]

2| Same key as above, compute $d$ using $\lambda(N)$ instead. Compare.

Solution

$\lambda(N) = 110$. We need $3d \equiv 1 \pmod{110}$.

$3 \cdot 37 = 111 = 110 + 1$, so $d = 37$.

Smaller exponent → faster decryption, for the same security. This is why modern standards prefer $\lambda(N)$.

CRT form of the private key

Decryption $m = c^d \bmod N$ is slow because $d$ is huge (around $t$ bits). The Chinese Remainder Theorem gives a ~4× speed-up by working modulo $p$ and $q$ separately.

The CRT private key stores five values instead of one: $$ \begin{aligned} d_p &= d \bmod (p - 1) \ d_q &= d \bmod (q - 1) \ q_{\text{inv}} &= q^{-1} \bmod p \end{aligned} $$ together with $p$ and $q$. This is the form used internally by pycryptodome, OpenSSL, and the PEM/DER serialization formats.

Additional constraints on $p$ and $q$

Now that we've seen the whole construction, we can come back to the two extra conditions $p$ and $q$ must satisfy for the key to be safe and well-formed.

Distance constraint

$p$ and $q$ must not be too close to each other. If $|p - q|$ is small, Fermat's factorization recovers them in seconds, regardless of how large $N$ is. A safe rule: $$ |p - q| > 2^{t/2 - 100} $$ In practice, picking $p$ and $q$ independently at random makes this almost always true, but a check doesn't hurt.

Compatibility with $e$

For $d$ to exist, we need $\gcd(e, \phi(N)) = 1$. Since $\phi(N) = (p-1)(q-1)$, this is equivalent to: $$ \gcd(e, p-1) = 1 \quad \text{and} \quad \gcd(e, q-1) = 1 $$ If a candidate prime fails this test, discard it and draw a new one.

A note on Miller–Rabin

Miller–Rabin is a probabilistic primality test: it can occasionally declare a composite number "prime" by mistake. With 40 rounds, the probability of such a false positive is below $2^{-80}$, cryptographically negligible. All standard libraries use enough rounds by default.

Python implementation

From scratch

from Crypto.Util import number
from math import gcd


def generate_rsa_key(t: int = 2048, e: int = 65537):
    while True:
        p = number.getPrime(t // 2)
        if gcd(e, p - 1) == 1:
            break
    while True:
        q = number.getPrime(t // 2)
        if q != p and gcd(e, q - 1) == 1:
            break

    N = p * q
    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)

    public_key = (N, e)
    private_key = (N, d)
    return public_key, private_key, (p, q)


pub, priv, (p, q) = generate_rsa_key(2048)
print(f"Public key:  {pub}")
print(f"Private key: {priv}")

Using pycryptodome

For real-world usage, prefer the library — it handles primality, CRT form, and serialization correctly:

from Crypto.PublicKey import RSA


key = RSA.generate(2048)

N = key.n
e = key.e
d = key.d
p = key.p
q = key.q

# CRT components
dp = key.d % (p - 1)
dq = key.d % (q - 1)
q_inv = key.u  # q^-1 mod p

# Export
pem_private = key.export_key()
pem_public = key.publickey().export_key()

Summary

Key construction recap

Pick $p, q$ prime, each of $t/2$ bits, with $\gcd(e, p-1) = \gcd(e, q-1) = 1$
$N = pq$
$e = 65537$
$d \equiv e^{-1} \pmod{\phi(N)}$
Public key: $(N, e)$ and Private key: $d$ (or its CRT form)

Security considerations (key size, entropy source, side-channels) are covered in chapter 7.

Final exercise

1| Build a complete toy RSA key with $p = 17$, $q = 19$, $e = 5$. Give $(N, e, d)$.

Solution

$N = 17 \cdot 19 = 323$
$\phi(N) = 16 \cdot 18 = 288$
Check $\gcd(5, 288) = 1$ ✓
Find $d$ such that $5d \equiv 1 \pmod{288}$ : $5 \cdot 173 = 865 = 3 \cdot 288 + 1$, so $d = 173$

Public key: $(323, 5)$ and Private key: $173$.

2| Trap exercise: someone hands you the parameters $p = 13$, $q = 13$, $e = 5$. Why is this not a valid RSA key?

Solution

$p = q$. RSA requires two distinct primes:

The construction breaks: $N = p^2$ and $\phi(N) = p(p-1)$, not $(p-1)^2$.
More importantly, the security collapses: factoring $N = p^2$ is trivial, just compute $\sqrt{N}$.

RSA Key Construction — From Two Primes to a Working Key Pair

Overview

Generating \(p\) and \(q\)

Exercices

Computing \(N\) and \(\phi(N)\)

Exercices

Choosing the public exponent \(e\)

Exercices

Computing the private exponent \(d\)

Exercices

CRT form of the private key

Additional constraints on \(p\) and \(q\)

Distance constraint

Compatibility with \(e\)

A note on Miller–Rabin

Python implementation

From scratch

Using pycryptodome

Summary

Final exercise