Tags: crypto rsa
Rating:
# Very hot
## Description
```
I didn't think that using two primes for my RSA was sexy enough, so I used three.
```
## Provided Files
```
src.py
out.txt
```
## Writeup
I started off by taking a look at the provided files.
`src.py`:
```py
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG
FLAG = bytes_to_long(FLAG.encode())
p = getPrime(384)
while(not isPrime(p + 6) or not isPrime(p + 12)):
p = getPrime(384)
q = p + 6
r = p + 12
n = p * q * r
e = 2**16 + 1
ct = pow(FLAG, e, n)
print(f'n: {n}')
print(f'e: {e}')
print(f'ct: {ct}')
```
`out.txt`:
```
n: 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
e: 65537
ct: 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985
```
Looking at `src.py` I saw that `N` is being calculated by `3 prime numbers` which is not best practice and can introduce potential vulnerabilities.
The problem here is that calculating `r` from `q` and `q` from `p` like seen in the script makes it reversable.
Knowing this I wrote a small python script to calculate the prime numbers from `N`.
```py
from sympy import Symbol, solve
p = Symbol('p')
n = 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
# cubic equation
equation = p**3 + 18*p**2 + 72*p - n
# solve equation to find p
solutions = solve(equation, p)
# extract real solution for p
p_value = None
for sol in solutions:
if sol.is_real:
p_value = sol
break
if p_value is not None:
# Calculate q and r
q = p_value + 6
r = p_value + 12
print("p:", int(p_value))
print("q:", int(q))
print("r:", int(r))
```
This revealed the `prime numbers` to me.
```
p: 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077
q: 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842083
r: 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842089
```
Taking the prime numbers I was now easily able to decrypt the `ciphertext`.
```py
from Crypto.Util.number import inverse, long_to_bytes
p = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077
q = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842083
r = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842089
n = p * q * r
e = 65537
ct = 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985
# calculate totient of n
phi = (p - 1) * (q - 1) * (r - 1)
# calculate private exponent
d = inverse(e, phi)
# decrypt ciphertext
pt = pow(ct, d, n)
# convert and decode
flag = long_to_bytes(pt).decode()
print(flag)
```
Executing that solution script finishes the challenge.
```
kali@kali python3 solve.py
lactf{th4t_w45_n0t_so_53xY}
```
