Safe Encryption

Task description

An RSA encryption and decryption oracle, where the private exponent is the flag itself.

The setup

d = bytes_to_long(FLAG)
e = inverse(d, phi)

The server never prints N directly, only e, and offers to encrypt or decrypt anything sent to it. With the flag at roughly 20 bytes (about 160 bits) and N a standard 1024-bit modulus, d is far smaller than N, well under the bound where Wiener’s attack (1990) applies: whenever d < N^(1/4) / 3, the convergents of the continued fraction expansion of e/N are guaranteed to include k/d for some small k, making d recoverable directly from e and N alone, no factoring of N required.

The one thing missing is N itself.

Recovering N without being told it

RSA encryption is multiplicative: encrypting a and encrypting b and multiplying the two results together is the same, modulo N, as encrypting a * b directly. That means for any two values where we also know their product’s encryption, encrypt(a) * encrypt(b) - encrypt(a*b) is an exact multiple of N, since the two sides agree modulo N but not as plain integers.

Four such combinations, taking the GCD across all of them, converge quickly on N itself:

c2, c3, c5, c6, c7, c10, c14, c15 = [encrypt(m) for m in [2,3,5,6,7,10,14,15]]

multiples = [c2*c3 - c6, c2*c5 - c10, c2*c7 - c14, c3*c5 - c15]
N = multiples[0]
for m in multiples[1:]:
    N = gcd(N, m)
# strip small spurious common factors, then verify encrypt(1) == 1

Recovering d with Wiener’s attack

With N and e both in hand, computing the continued fraction expansion of e/N and checking each convergent k/d against the condition that (e*d - 1) divides evenly by k, and that the resulting phi candidate leads to a valid factorization of N (checked via the quadratic formula on p + q and p * q), finds the one convergent that’s actually RSA’s real private exponent:

def wiener_attack(e, N):
    for k, d in convergents(continued_fraction(e, N)):
        if k == 0 or (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        s = N - phi + 1
        disc = s * s - 4 * N
        if disc >= 0 and isqrt(disc) ** 2 == disc:
            return d

long_to_bytes(d) gives the flag directly, since d is exactly what the flag’s bytes were converted into at keygen time.

The two lessons together

Using a short, guessable value as an RSA private exponent is the textbook precondition for Wiener’s attack; the Boneh-Durfee attack extends the same idea to a slightly larger bound. Separately, hiding N from the output doesn’t actually hide it from an attacker who gets an encryption oracle, since RSA’s own multiplicative structure (E(a) * E(b) = E(a*b) mod N) leaks N out through a handful of chosen encryptions and a GCD.