THE GARDEN

RSA with Non-Coprime Exponent (e Shares a Factor with φ(N))

Updated 13 Sep 2026

• •

  What it is

  • •

    Standard RSA decryption requires $d \equiv e^{-1} \pmod{\phi(N)}$, which only exists when $\gcd(e, \phi(N)) = 1$. If instead $\gcd(e, \phi(N)) = d_0 > 1$, no single decryption exponent recovers the message uniquely — but decryption isn't hopeless: factor $d_0$ out of $\phi(N)$ to get $k = \phi(N)/d_0$. If $\gcd(e, k) = 1$ (common once the "bad" factor is stripped out), a partial inverse $a \equiv e^{-1} \pmod k$ exists, and raising the ciphertext to $a$ recovers the true message up to an ambiguity of exactly $d_0$ possible values: $(m_0/m)^{d_0} \equiv 1 \pmod N$. Enumerating all $d_0$ roots of unity and multiplying each against $m_0$ gives every candidate plaintext; the real one is picked out by checking which decodes to readable text (or a known prefix).

• •

  When to apply

  • •

    An RSA challenge deliberately generates $e$ (or leaks a modulus) such that $\gcd(e, \phi(N)) > 1$ — a tell is $e$ being composite and unusual, or the source explicitly warning the implementation is "broken."

• •

  Math

  • •

    With $d_0 = \gcd(e, \phi(N))$ and $k = \phi(N)/d_0$: $a \equiv e^{-1} \pmod k$; $m_0 \equiv c^a \pmod N$ satisfies $(m_0/m)^{d_0} \equiv 1 \pmod N$. When $N$ is prime, the $d_0$-th roots of unity mod $N$ form a cyclic subgroup, generated by $r = h^{(N-1)/d_0} \bmod N$ for random $h$ — provided $r$ has order exactly $d_0$, not a proper divisor of it. Checking $r^{d_0/q} \ne 1$ for every prime factor $q$ of $d_0$ before using it avoids silently enumerating too few candidates.

• •

  Worked example

  • •

    Toy 48-bit prime $n$ with $n \equiv 9 \pmod{16}$ (so $\gcd(16, n{-}1) = 8$ exactly) and $e=16$: recovering a partial inverse mod $k=(n{-}1)/8$, then enumerating all 8 roots of unity (checking each candidate root has order exactly 8, not 2 or 4) correctly reproduced the true message among the 8 candidates every trial. A naive check of just "$r \ne 1$" occasionally selected an order-2 or order-4 root instead, producing only 2 or 4 distinct candidates and silently missing the true message — an easy trap to fall into.

• •

  Python

  • •

    from math import gcd
    d0 = gcd(e, n - 1)          # n prime, phi(n) = n-1
    k = (n - 1) // d0
    a = pow(e, -1, k)
    m0 = pow(c, a, n)
    
    def order_d0_root(d0):
        while True:
            h = random.randrange(2, n - 2)
            r = pow(h, (n - 1) // d0, n)
            if all(pow(r, d0 // q, n) != 1 for q in prime_factors(d0)):
                return r
    
    r = order_d0_root(d0)
    candidates = {(m0 * pow(r, i, n)) % n for i in range(d0)}
    

• •

  SageMath

  • •

    Not particularly relevant — Python's pow(x, -1, m) already handles the modular inverse cleanly. (A more general Sage-friendly variant — using inverse_mod and brute-collecting roots of unity — handles the case where e isn't a clean prime power, useful if d0 has multiple distinct prime factors.)

• •

  Related

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What condition on e and φ(N) breaks the uniqueness of standard RSA decryption?

    • •

      gcd(e, φ(N)) > 1 — no single modular inverse of e exists mod φ(N).

  • •

    How many candidate plaintexts does this ambiguity produce, and how do you find the real one?

    • •

      Exactly gcd(e, φ(N)) candidates (the d0-th roots of unity mod N); the real one is identified by checking which decodes to sensible text.

◌ Explore connections in Graph view