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
It's a great task.
For First we decode the public key to get `n` and `e`.
```python
key = open('public.pem', "r").read()
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:
print(c.decrypt(f.read()))
```
Note: The code might not work correctly if you have a different version of the crypto module
