THE GARDEN

RSA Fixed-Point Leakage (Unconcealed Messages) → Factorization

Updated 13 Sep 2026

• •

  What it is

  • •

    For any RSA key, there are always exactly $\gcd(e{-}1, p{-}1) \cdot \gcd(e{-}1, q{-}1)$ "unconcealed" messages $m$ for which encryption does nothing: $m^e \equiv m \pmod N$ (harmless in practice, since real messages essentially never happen to be one of these by chance). But observing that a known message failed to be concealed leaks real information: the order of $m$ modulo $N$ divides $e{-}1$. Writing $e{-}1 = 2^s t$ ($t$ odd) and repeatedly squaring $m^t$, the sequence must hit $1 \pmod N$ eventually (Fermat) — and the value just before it first hits 1 is, with good probability, a non-trivial square root of unity modulo N: some $x \ne \pm 1$ with $x^2 \equiv 1 \pmod N$. Such a value can only exist because $N$ is composite (a prime modulus has only $\pm1$ as square roots of unity), and $\gcd(x-1, N)$ then reveals a non-trivial factor directly — the same core idea that powers the Miller-Rabin primality test's ability to catch composite numbers.

• •

  When to apply

  • •

    An RSA encryption function explicitly reveals (or you can detect) that a specific known plaintext happened to encrypt to itself — $m^e \equiv m \pmod N$ — even without ever seeing $p$ or $q$.

• •

  Math

  • •

    order$(m) \mid (e-1)$. Write $e - 1 = 2^s t$, $t$ odd. Compute $x_0 = m^t \bmod N$, then $x_{i+1} = x_i^2 \bmod N$. The first index where $x_i$ is some value other than $\pm 1$ but squares to 1 gives $\gcd(x_i - 1, N)$ as a non-trivial factor (if the sequence instead hits $-1$ before ever showing a non-trivial root, that particular witness is a dead end).

• •

  Worked example

  • •

    Toy RSA with $e{=}17$ ($e{-}1{=}16{=}2^4$) and $p,q \equiv 1 \pmod{16}$ (chosen so unconcealed messages of high order are plentiful): constructing $m$ as a CRT-combination of a non-trivial 16th-root-of-unity mod $p$ and mod $q$ confirmed $m^{17} \equiv m \pmod N$ exactly, then repeatedly squaring $m$ and computing $\gcd(x-1, N)$ found a genuine, non-trivial factor of $N$ on the first iteration where $x \ne \pm 1$.

• •

  Python

  • •

    from math import gcd
    x = m
    for _ in range(20):          # more than enough for e-1's 2-adic valuation
        x = pow(x, 2, N)
        g = gcd(x - 1, N)
        if 1 < g < N:
            p, q = g, N // g
            break
    

• •

  Related

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What does it mean for a message to be "unconcealed" by RSA encryption?

    • •

      m^e ≡ m (mod N) — encrypting it returns the exact same value, so its multiplicative order divides e-1.

  • •

    Why does finding a non-trivial square root of unity mod N reveal a factor of N?

    • •

      A prime modulus only has ±1 as square roots of unity; a composite N having another one means gcd(x-1, N) splits off a genuine, non-trivial factor.

◌ Explore connections in Graph view