Tags: crypto rsa

Rating:

# A Prime Problem
- Solves - 15
- Points - 400
#
# Description
Suppose I generate primes p and q for RSA in the following way:

Choose a random 2048 bit integer
p is next prime after that integer
Choose another random integer r where 0 < r ≤ 2^1023
q is next prime after r + p
n = p*q Can you factor n and recover the flag?

Hint: CVE-2022-26320
# Attachments
[Файл public.pem](./sources/public.pem)
[Файл key_gen_flag.bin](./sources/key_gen_flag.bin)
# Solution

For First we decode the public key to get n and e.

python
rsakey = RSA.importKey(key)
print(rsakey.n, rsakey.e)

Then, after getting the information from the hint, we understand that we need to use the Fermat factorization method. Let's write the code and find p and q:

python
def isqrt(n):
x = n
y = (x + n // x) // 2
while (y < x):
x = y
y = (x + n // x) // 2
return x

def fermat(n):
t0 = isqrt(n) + 1
counter = 0
t = t0 + counter
temp = isqrt((t * t) - n)
while ((temp * temp) != ((t * t) - n)):
counter += 1
t = t0 + counter
temp = isqrt((t * t) - n)
s = temp
p = t + s
q = t - s
return p, q


Then we calculate the closed exponent d.

python
phi = (p-1)*(q-1)
d = pow(e, -1, phi)


Now we have everything we need, so we just create a private key and decode the file with the flag:

python
comps = tuple([rsakey.n, rsakey.e, d, p, q])
private_key = RSA.construct(comps, consistency_check=False)
c = PKCS1_OAEP.new(Rprivate_key)
with open('key_gen_flag.bin', 'rb') as f: