We have to solve RSA with a leak from which we can recover quite easily $ed - 1$.

Event Link:TeamItaly CTF 2023

## Challenge Description

First of all, we have a weird `keygen`

function:

1
2
3
4
5
6
7
8
9
10
11
12
13

p, q = getStrongPrime(1024), getStrongPrime(1024)
def RSAgen(e = None):
d = 0
if not e:
while(d.bit_length() < 2047):
e = getPrime(2047)
d = pow(e, -1, (p-1)*(q-1))
else:
d = pow(e, -1, (p-1)*(q-1))
return (p*q, p, q, e, d)
n = p*q

So if we do not provide `e`

, we get a pair with both `e`

and `d`

of size `2047`

bits. Otherwise is just common RSA. Then we are given a `leak`

:

1
2
3
4
5

key = RSAgen()
k = randint(600, 1200)
f = factorial(k)
leak = (pow(key[3], 2) + (key[3]*key[4] - 1)*f)*getPrime(256) + k

So we have that the `leak`

\(l = (e^2 + (ed - 1)f)y + k\), where $600 \leq k \leq 1200$ is an unknown number, $f = k!$ and $y$ is a `256`

-bit prime. Finally the same `n`

is used to encrypt the flag.

## Solution

First thing we notice that, knowing $f$, \(l / f \approx (ed - 1)y\), since $f$ is huge and $ye^2$ and $k$ are small. This has a `256`

-bit factor in common with `leak - k`

. So we can just bruteforce `k`

and see when we get a hit.

1
2
3
4
5
6
7
8
9
10

for k in range(600, 1200):
fact = factorial(k)
y_ed = (leak - k) // fact
y = gcd(y_ed, leak - k)
if y > (1<<100):
print(f'{k = } {y = }')
# k = 1000
# y = 109301875007644313321646793756620023172464141085890087796540184816578976056823

In this way we get `y`

for free as `gcd(y_ed, leak - k)`

. So we have \(ed - 1\), which is a multiple of `phi`

. This is easily solvable, see for instance here. The described algorithm gives us a factor of `n`

:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def find_factor(ed, n):
h = ed
while h % 2 == 0:
h = h // 2
h = int(h)
for cnt in range(100):
print(f'{cnt = }')
a = random.randint(2, n-2)
g = gcd(a, n)
if g != 1:
print(f'{g = }')
return g
b = pow(a, h, n)
while True:
g = gcd(b-1, n)
if g == 1:
b = pow(b, 2, n)
continue
if g == n:
break
print(f'{g = }')
return g