THE GARDEN

Discrete Log Signature Forgery via Smooth-Order Modulus Lifting (n=p², Pohlig-Hellman + Hensel Lift)

Updated 13 Sep 2026

• •

  What it is

  • •

    A substantially more powerful generalization of the basic DSKS attack, for verifiers that reject a self-supplied modulus if it's prime (blocking the simplest $e=1$ trick) but don't check how it's composite. Choosing $n = p^2$ for a specially-constructed smooth prime $p$ (one where $p-1$ factors entirely into small primes) — large enough that $S^e \bmod n = S^e$ never wraps for the exponents involved — turns "find an $e$ making $S^e \equiv D \pmod n$ for an arbitrary target digest $D$" into a two-stage, efficiently solvable problem: first, Pohlig-Hellman efficiently solves the discrete log $S^{e_0} \equiv D \pmod p$ (fast specifically because $p-1$ is smooth); second, a Hensel-lifting step extends that solution from mod $p$ up to mod $p^2$, finding the correction term $y$ in $e = e_0 + y(p-1)$ that makes the full congruence $S^e \equiv D \pmod{p^2}$ hold exactly. Because a fresh, valid $e$ can be derived this way for any chosen target digest $D$, the same fixed signature $S$ can be "verified" as authentic against arbitrarily many different attacker-chosen messages.

• •

  When to apply

  • •

    A DSKS-style attack is blocked by a naive isPrime(n) check on the attacker-supplied modulus, but the verifier doesn't validate the structure of a composite modulus beyond that — and, ideally, the attacker needs to forge signatures over more than one message using the same fixed base signature $S$.

• •

  Math

  • •

    Writing any valid exponent as $e = e_0 + y(p-1)$ for $y \in [0,p-1]$ (since $\phi(p^2)=p(p-1)$), and using $S^{p-1} \equiv 1 + kp \pmod{p^2}$ for $k = \frac{S^{p-1}-1}{p} \bmod p$ (Fermat, lifted): $S^{e_0}(1+ykp) \equiv D \pmod{p^2} \;\Rightarrow\; y \equiv k^{-1}\cdot\frac{D\cdot S^{-e_0}-1}{p} \pmod p$. This "$1+kp$" binomial-vanishing structure is exactly the same mechanism as Discrete Log Reduction via Chosen Composite Modulus n=q² (Paillier's Trick), just used here to lift an existing solution rather than to trivialize a discrete log from scratch.

• •

  Worked example

  • •

    A toy 24-bit smooth prime $p$ (with $p-1$ built entirely from tiny prime factors) and a primitive-root base $S$: brute-force solving $S^{e_0}\equiv D \pmod p$ for a random target $D$ (standing in for real Pohlig-Hellman on a larger smooth prime), then applying the Hensel lift formula for $y$ and assembling $e=e_0+y(p-1)$, produced an exponent satisfying $S^e \equiv D \pmod{p^2}$ exactly.

• •

  Python

  • •

    k = ((pow(S, p-1, p*p) - 1) // p) % p
    k_inv = pow(k, -1, p)
    # e0 found via Pohlig-Hellman (feasible because p-1 is smooth)
    diff = (D * pow(S, -e0, p*p) - 1) % (p*p)
    y = ((diff // p) * k_inv) % p
    e = e0 + y * (p - 1)
    assert pow(S, e, p*p) == D
    

• •

  Related

  • •

    Duplicate Signature Key Selection (DSKS) Attack

  • •

    Discrete Log Reduction via Chosen Composite Modulus n=q² (Paillier's Trick)

• •

  Cards

  • •

    Why must p specifically be chosen as a smooth prime for this attack to be efficient?

    • •

      Pohlig-Hellman's efficiency depends on p-1 factoring into small primes — a smooth p-1 is exactly what makes the discrete log mod p tractable.

  • •

    What's the role of the Hensel lift step, beyond just solving the discrete log mod p?

    • •

      It extends a solution valid mod p up to one valid mod p², since φ(p²)=p(p-1) means the true exponent space is p times larger than what solving mod p alone determines.

◌ Explore connections in Graph view