Challenge description
In this challenge, we face a standard RSA implementation:
1p = getPrime(1024)
2q = getPrime(1024)
3n = p * q
4e = 0x10001
p and q are two big primes, and e = 0x10001 is the standard choice for public exponent.
These parameters are used to encrypt the flag:
1FLAG = open('flag.txt', 'rb').read().strip()
2c = pow(bytes_to_long(FLAG), e, n)
3print(f'{n = }')
4print(f'{c = }')
Together with the ciphertext c and the base n we are also given some hints:
1hints = []
2for _ in range(2):
3 a, b = randint(0, 2**12), randint(0, 2**312)
4 hints.append(a * p + b * q)
5
6print(f'{hints = }')
Solution
We know that to decrypt RSA it is enough to factor n.
However n = p*q where p and q are 1024-bits primes, and hence direct factorization is not an option.
We must find a way to use the hints instead.
The first observation is the following.
Let us call our hints h1 = a1*p + b1*q and h2 = a2*p + b2*q.
Then if only we knew a1 and a2 we could compute
$$H = a_1 h_2 - a_2 h_1 = (a_1b_2 - a_2b_1)q$$
Now this number shares a factor q with our public modulus n; we can efficently compute gcd(n, H) = q, and then recover p = n // q.
Of course the same reasoning applies to b1*h2 - b2*h1 which gives us p.
This would allow us to recover the flag.
However we do not know either a1 and a2 or b1 and b2.
Looking at the code b1 and b2 are two random integers between 0 and 2**312, but a1 and a2 are both lower than 2**12 = 8192, which means we can brute-force it.
The total number of possible combinations of (a1, a2) is 2**26 = 67108864, which is expensive but still doable.
However, we can easily reduce it further by looking at coprime a1 and a2 (meaning that gcd(a1, a2) = 1).
This is because if a1 and a2 have one factor in common we can divide the whole expression by this common factor and get another (duplicate) solution.
For every possible pair of coprime a1 and a2 we just compute H and check gcd(n, H).
If this is 1 it means we picked the wrong pair.
Otherwise we got a factor of n, and we can use it to solve the challenge.
1from sage.all import gcd
2import time
3
4def bf_hints(hints, n):
5 h1, h2 = hints
6 tic = time.time()
7
8 for a1 in range(2**12):
9 if a1 % 100 == 0:
10 print(f'{a1 = }/{2**12} [t = {round(time.time()-tic, 2)} s]') # Print elapsed time
11 tic = time.time()
12
13 for a2 in range(2**12):
14 if gcd(a1, a2) != 1:
15 # Skip if a1 and a2 are not coprime
16 continue
17
18 guess = a1 * h1 - a2 * h2
19 q = gcd(n, guess)
20 if q != 1:
21 # Win
22 print(f'Hit: {a1 = } {a2 = }')
23 return int(q)
Notice that this may still take a couple of minutes: for this reason I added a line of code to check our progress once in a while and print the elapsed time.
The function gcd is taken from SageMath since it’s faster, but math.gcd would work as well.
Now we can load n and hints from the output we are given, and run this function.
1q = bf_hints(hints, n)
2
3assert n % q == 0
4p = n // q
Once we have p and q we can compute
$$\varphi = (p-1)(q-1),$$
and then
$$d = e^{-1} \bmod \varphi,$$
the private exponent we need to invert the ciphertext. In this way we finally recover the flag:
1phi = (p-1)*(q-1)
2
3d = pow(e, -1, phi)
4m = pow(c, d, n)
5
6print(m.to_bytes((m.bit_length() + 7) // 8, "big")) # b'DUCTF{gcd_1s_a_g00d_alg0r1thm_f0r_th3_t00lbox}'