RSA Key Generation and the Prime Search

An RSA key pair is a triple of integers: a modulus $n = pq$, a public exponent $e$, and a private exponent $d$ satisfying $ed \equiv 1 \pmod{\lambda(n)}$. Everything else in the key — the primes, the CRT coefficients — is bookkeeping derived from those. Generating the key means finding $p$ and $q$ such that the resulting structure is not merely valid but safe, and the two requirements pull in different directions.

What the private exponent must satisfy

Euler’s theorem gives $a^{\varphi(n)} \equiv 1 \pmod n$ for any $a$ coprime to $n$, where $\varphi(n) = (p-1)(q-1)$. Carmichael’s function $\lambda(n) = \mathrm{lcm}(p-1, q-1)$ is a smaller exponent with the same property, and using it produces a smaller $d$. Both work for decryption; the smaller one is standard in modern implementations because it makes the private operation cheaper.

The public exponent $e$ must be coprime to $\lambda(n)$, and $d$ is its modular inverse. That inverse always exists under the coprimality condition, and is computed by the extended Euclidean algorithm in $O(\log n)$ steps.

The common choice $e = 65537 = 2^{16} + 1$ is not arbitrary. It is prime, so it is coprime to $\lambda(n)$ unless one of $p-1$ or $q-1$ happens to be a multiple of 65537 — which key generation checks and rejects. It is small enough that the public operation is cheap and large enough that the small-exponent attacks on $e = 3$ do not apply directly. With $e = 3$, textbook RSA without padding leaks the message whenever $m^3 < n$, because the cube root over the integers is the message itself; with proper padding that attack is blocked, but $e = 65537$ removes the class entirely at negligible cost.

The prime search

Generating $p$ means drawing random odd integers of the target size and testing until one is prime. The density of primes near $2^b$ is about $1/(b \ln 2)$ by the prime number theorem, so a $b$-bit search expects roughly $b \ln 2 \approx 0.69b$ candidates. For 1024-bit primes that is about 710 trials, each requiring a primality test on a number that is almost always composite.

The standard test is Miller-Rabin. For a candidate $n$, write $n - 1 = 2^s r$ with $r$ odd, pick a base $a$, and compute $a^r \bmod n$. If the result is 1 or $n-1$, the candidate passes this round. Otherwise square repeatedly up to $s-1$ times looking for $n-1$; if it never appears, $n$ is certainly composite. A composite that passes a round is called a strong pseudoprime to that base, and the probability that a random composite passes $k$ independent rounds is bounded by $4^{-k}$.

import secrets

def miller_rabin(n, rounds=40):
    if n < 2:
        return False
    for small in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % small == 0:
            return n == small
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(rounds):
        a = secrets.randbelow(n - 3) + 2
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

The error bound of $4^{-k}$ is worth reading carefully. It applies to random bases against an adversarially chosen composite only in the average sense; a composite can be constructed to pass specific bases. Since the candidate here is chosen by the key generator, not by an attacker, and the bases are drawn randomly, the bound is the right one. Forty rounds put the error below $2^{-80}$, which is why that count appears in key-generation code. Deterministic variants exist for bounded sizes — testing all bases below a threshold proves primality outright for $n$ under a known limit — but for 1024-bit candidates the probabilistic test is the practical choice.

Structure the search must avoid

A prime that passes Miller-Rabin is prime. It is not necessarily a good RSA prime, and several properties are checked separately.

Size and difference. If $p$ and $q$ are close, Fermat factorization finds $n$ quickly: the method writes $n = a^2 - b^2 = (a-b)(a+b)$ and searches upward from $\lceil\sqrt{n}\rceil$. When $|p - q|$ is small the search terminates in a few steps. Generators draw $p$ and $q$ independently from the full range and reject pairs whose difference is below a threshold.

Small factors of $p-1$ and $q-1$. If $p - 1$ is smooth, the Pollard $p-1$ algorithm recovers $p$ by exponentiating to a product of small prime powers. The defence is to require that $p-1$ and $q-1$ each have a large prime factor. Some generators enforce this directly by constructing $p = 2kq’ + 1$; others test for it. The condition is the same one that motivates safe primes in Diffie-Hellman, described in Discrete Logarithms and Why Group Order Decides Their Difficulty, applied to the factors rather than to the group.

Coprimality with $e$. If $e$ divides $p-1$, then $e$ divides $\lambda(n)$ and no inverse exists. The check is one modular reduction per candidate and is done before any primality testing.

Distinctness. $p = q$ collapses $n$ into a perfect square, and $\varphi(n)$ becomes $p(p-1)$, which makes the key trivially factorable. The check is an equality test.

Deriving the private exponent and the CRT form

With $p$, $q$, and $e$ fixed, $d = e^{-1} \bmod \lambda(n)$. The extended Euclidean algorithm produces it in time proportional to the number of bits, and the result is a full-size exponent — around 2048 bits for a 2048-bit modulus, which is why the private operation costs what it does.

The private key is then stored in Chinese remainder form, because decryption with it is roughly four times faster. Instead of computing $m = c^d \bmod n$ directly, the implementation reduces the problem to two half-size exponentiations:

$$m_1 = c^{d \bmod (p-1)} \bmod p, \qquad m_2 = c^{d \bmod (q-1)} \bmod q$$

and combines them with Garner’s formula using the precomputed coefficient $q_{\mathrm{inv}} = q^{-1} \bmod p$:

def rsa_decrypt_crt(c, p, q, dp, dq, qinv):
    m1 = pow(c, dp, p)          # exponent is half the bit length
    m2 = pow(c, dq, q)
    h = (qinv * (m1 - m2)) % p
    return m2 + h * q

Each exponentiation now uses a modulus of half the bits and an exponent of half the bits. Since exponentiation cost grows roughly with the cube of the modulus size, two half-size exponentiations cost about $2 \cdot (1/8) = 1/4$ of one full-size one. The precomputed values $d_p = d \bmod (p-1)$, $d_q = d \bmod (q-1)$, and $q_{\mathrm{inv}}$ are stored in the key file alongside $p$ and $q$. PKCS #1 defines this as the second representation of the private key, and it is the one implementations actually use.

Faults and the reason for the verify step

The CRT form introduces a failure mode that the plain form does not have. If one of the two exponentiations is corrupted — by a hardware fault, a memory error, or a faulty computation — the result $m$ is wrong in a way that reveals the factorization. The attacker computes $\gcd(m^e - c, n)$, which yields $p$ or $q$ with high probability, and the key is broken.

The countermeasure is to verify the output: re-encrypt $m$ with the public exponent and compare to $c$. That costs one public operation, roughly 17 modular multiplications, against thousands for the private one. It is cheap insurance and is required by standards for implementations exposed to fault injection. The check also catches implementation bugs in the CRT recombination, which is where sign errors and off-by-one reductions tend to appear.

Key generation ends when the pair passes all the structural checks, but the resulting key is only as good as the randomness that produced the primes. A generator seeded from a predictable source produces primes an attacker can enumerate; the failure is invisible in the key’s arithmetic, which is entirely valid. This is why key generation draws from the operating system’s cryptographic random source and why the primes, not just the seed, are treated as secret material.

The size choices that make these parameters appropriate for a given security level are compared in Key Size Equivalence Across RSA, Diffie-Hellman, and Curves. The padding that turns the raw operation into a secure encryption scheme is covered in RSA Padding and Why Textbook RSA Fails.