Broken RSA

We need to recover the plaintext from the incorrectly generated RSA parameters, in this case, e = 16 and the modulo n is a prime. As the public exponent and the totient of n is not coprime, this implies

The first, and intended solution is to take advantage of the fact that e = 2 ^ 4, hence we only need to calculate the square root of the plaintext in the finite field four times.

Kudos to Robin_Jadoul on Cryptohack for this solution.

xxxxxxxxxx
n = ...
e = 16
ct = ...
def go(e, x):
    if e <= 1:
        if b"crypto" in long_to_bytes(x):
            return long_to_bytes(x)
        return None
    if x ^ ((n - 1) // 2) != 1:
        return
    r1 = x.square_root()
    r2 = -r1
    if res := go(e // 2, r1):
        return res
    return go(e // 2, r2)

print(go(e, GF(n)(ct)))

Another solution takes advantage of the fact that the modulo is a prime. With m being the plaintext message, we can see it is a root of the polynomial X^e - ct over Z/nZ[X]. As n is prime, calculating the square root multiple times when the modulus is a prime is quick. nth_root is insanely slow in comparison, as the underlying method is not optimised for non coprime power.

Kudos to AZ on Cryptohack for this solution.

xxxxxxxxxx
n = ...
e = 16
ct = ...
Z.<X> = GF(n)[]
P = X^e - ct
for r, _ in P.roots():
    h = hex(r)[2:]
    if b'crypto'.hex() in h:
        print(bytes.fromhex(h))

Lastly, the God solution. Don't know how it works, root of unity is that strong I guess. I think I will leave this to the future me to figure out! This works for composite n, as seen in this writeup.

xxxxxxxxxx
import Crypto.Util.number as cun
from pprint import pprint


def roots_of_unity(e, phi, n, rounds=250):
    # Divide common factors of `phi` and `e` until they're coprime.
    phi_coprime = phi
    while gcd(phi_coprime, e) != 1:
        phi_coprime //= gcd(phi_coprime, e)

    # Don't know how many roots of unity there are, so just try and collect a bunch
    roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))

    assert all(pow(root, e, n) == 1 for root in roots)
    return roots, phi_coprime


n = ...
e = 16
ct = ...

# n is prime
# Problem: e and phi are not coprime - d does not exist
phi = n - 1

# Find e'th roots of unity modulo n
roots, phi_coprime = roots_of_unity(e, phi, n)

# Use our `phi_coprime` to get one possible plaintext
d = inverse_mod(e, phi_coprime)
pt = pow(ct, d, n)
assert pow(pt, e, n) == ct

# Use the roots of unity to get all other possible plaintexts
pts = [(pt * root) % n for root in roots]
pts = [cun.long_to_bytes(pt) for pt in pts]
pprint(pts)

This runs very quick. The following is the way that the algorithm works.

As we cannot find a unique m, we can instead find x satisfying

$x$$x$ in this case is called a root of unity modulo n which can be computed fairly easily. The algorithm for calculating this is in the roots_of_unity method in the Python script.

Denote $g=gcd(e,\varphi (n))$$g = gcd(e, \phi(n))$, hence we have $e=kg$$e = kg$ and $\varphi (n)=lg$$\phi(n) = lg$ for some integers $k$$k$ and $l$$l$. phi_coprime is $l$$l$ (as we are dividing $\varphi (n)$$\phi(n)$ by $gcd(e,\varphi (n))$$gcd(e, \phi(n))$). The returned solution is within some number of rounds, as there can be collisions of the solutions, in mathematical terms, there exists some $a,b$$a, b$ where $a\ne b$$a \neq b$ such that:

Indeed, if the elements $a$$a$ are of order divides phi_coprime, or $l$$l$, then $a^l=1$$a ^ l = 1$ (Lagrange's theorem).

The set of the solutions indeed satisfy the assert line because

d = inverse_mod(e, phi_coprime), or $ed=1+zl$$ed = 1 + zl$ for some $z$$z$.

Denote the original plaintext as $m$$m$ and the corresponding ciphertext ct as $c$$c$, and the possible plaintext obtained from pt = pow(ct, d, n) as M.

For the assert line, we have:

Hence $M$$M$ is one of the possible plaintext. Combining this with the root of unity, we should have a set of possible plaintexts. Finding one with indications of the flag should give us the solution.