LEAKY RSA

crypto

---

Challenge

Standard RSA public key (N, e=257) and ciphertext c, plus one extra leaked value that ties p and q together through small unknown integer multipliers — effectively a noisy hint at p + q scaled by the public exponent. That's enough structure to factor N directly instead of attacking the cipher.

Solution

For small guessed multipliers kp, kq (both < e, since that's the scale the leak was built at), the leak equation rearranges into a quadratic in p whose discriminant is checkable as a perfect square. Brute force both multipliers, and whichever pair makes the discriminant a perfect square and divides N evenly hands you p and q directly:

for kp in range(1, e):
    for kq in range(1, e):
        S = e * leak - 2 + kp + kq
        delta = S**2 - 4 * kp * kq * N
        if delta >= 0:
            ok, root = is_sq(delta)
            if ok:
                for cand in ((S + root) // (2 * kp), (S - root) // (2 * kp)):
                    if N % cand == 0:
                        p, q = cand, N // cand
                        phi = (p - 1) * (q - 1)
                        d = pow(e, -1, phi)
                        m = pow(c, d, N)
                        print(long_to_bytes(m))

Once p and q pop out, computing the private exponent and decrypting c is textbook RSA.