Challenge Source

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
    with open(file, 'rb') as fin:
        flag = fin.read()
    return flag

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
    n = p * q
    e = 0x10001
    return n, e

def encrypt_message(m, e, n):
    return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b^2 * q)
print(a^2 * p + q)

Idea

Well, this is just classic RSA encryption. On its own, this scheme is definitely not breakable. However, the author provides some additional values $h_0, h_1$ so that somehow, we can use them to decrypt the encrypted value $c$:

where $a$, $b$ is some random value $\in [0, 2^{1024})$.

My teammate immediately recognized (god 😢) that:

For which you can reason it by doing the following calculations:

Let's set $\frac{b}{a}\frac{q}{p} + \frac{a}{b}\frac{p}{q}$ to be $k$.

If $k$ is small enough to $a$ and $b$, we can approximate it to be

Since $\frac{q}{p}, \frac{b}{a}$ and their reciprocals involve in the sum making up $k$, the bigness of $k$ depends on $\frac{max(p, q)}{min(p, q)}$ and $\frac{max(a, b)}{min(a, b)}$. And you can reason that for any two numbers $x, y$ generated at random in the same interval, the ratio $\frac{max(x, y)}{min(x, y)}$ is expected to be small.

During local test, I realized that $k$ is very small (like, $2$ or $3$ or something...). In fact, let's plot $k$ for different values of $p, q, a, b$ and see how it goes 🙂

Probability density graph of k.

The left column represents the percentage of occurances for a certain $k$. And you can see for ALMOST ALL cases, $k$ will just land around on some value $\le 6$. (yes, while you can argue that the spike of $2$ is just 5%, so the rest could be much bigger, however, the probability of $k$ landing $> 20$ is just 12%)

Also, you can notice that the plot is flat before a sudden spike around $k = 2$. This happens because $k$ can be represented in the form of $\frac{1}{x} + x$, and from AM-GM Inequality, $\frac{1}{x} + x \ge 2\sqrt{\frac{1}{x}x} = 2$ for any $x > 0$.

Anyways, this means in most cases, we can expect:

or if you are really skeptical, you can bound it to be $\le ab + 10000$, just to be sure 🙂 This means that we can find $ab$ just by bruteforcing 10000 values around $\sqrt{\frac{h_0h_1}{n}}$.

Get $p$

Knowing $ab$, we now have 4 equations with 4 variables to solve:

for which we can lend the power of magic Sagemath to solve for $p,q$.

from sage.all import *
from tqdm import trange

c = ...
n = ...
h0 = ...
h1 = ...

P = PolynomialRing(QQ, names=('b', 'q'))
b, q = P.gens()

ab_approx = Integer(isqrt(Integer(h0*h1) / Integer(n)))
for delta in trange(0, 1000):
    ab = ab_approx - delta

    # Here, I substitude a*b = ab and p*q = n 
    # to reduce number of equations & vars
    eqs = [
        n + b**2 * q*q - h0*q,
        ab**2 * n + q*q * b**2 - h1 * b**2 * q
    ] 

    # Copied from somebody's Coppersmith multivariate solver :v
    H = Sequence(eqs, P)
    I = H.ideal()
    if I.dimension() == -1:
        H.pop()
    elif I.dimension() == 0:
        for root in I.variety(ring=ZZ):
            print(root)

# q = 109813633407350440684752357104087423730270808390261227637462376676953120335377705330415425210793126533507813859480119893163026376723863463313335381388502153679899248105338398482841127131263152039296390164162491463575378945424202721526857339615769738614581032689687091169497613753054146273393581209744585087263

Get Flag

Since we have $p,q$, we can now recover the private exponent and solve for flag 🙂

from Crypto.Util.number import *

c = ...
n = ...
h0 = ...
h1 = ...

e = 65537
q = ...
p = n // q
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))

# b"midnight{1_kN0w_3n0ugh_4b0ut_RSA}\n\xa9\xbd\xd17\xec'\xed\x9c\x19RD\x8f\x9c8\xe4\xb9\x11\xf3\xb5/\xdeC\xff\xe5c\x89_3\xd7F\x1f^\x12 +A\xc3\xc7\\HC\xd9!\xd6`\x86\xa8B\xc0A)4q\x85x<\xbd\xe7@\xa9\xa3\x08\xc2\xb0\xdf\x03\xb9\xbd.\x8f\xa3\xe5\xd8\x8b\xf0\xadw7\xb7\xe1\xa2j\x95\xd9\xe5!\xee\xf2u\xf32\xf1V\x1c"