# Challenge Author Writeup for LACTF 2024/very-hot

The challenge gave two files: one with the source and one with the output produced by the source.

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}')

n: 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
e: 65537
ct: 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985

In order to understand how to tackle this challenge, we need to first review how RSA functions.

RSA involves the construction of a public modulus by choosing two large numbers p and q and multiplying them together:

$n = pq$

Messages are encrypted by raising it to the power of an exponent, usually chosen to be 65537 (which in our case, it is), modulo n.

$m^e\bmod n = c$

Messages can be decrypted by first calculating the totient of the modulus, and then finding the modular inverse of the encryption exponent modulo that totient. This new number, d, is the decryption exponent.

$\phi(n) = (p-1)(q-1)$
$ed \equiv 1 \pmod{\phi(n)}$

Messages are decrypted by raising the ciphertext to the power of d mod n. This works because of [Euler's Totient Theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem).

$c^d\bmod n = m$

From this scheme, we can see that knowledge of the prime factors p and q allow us to decrypt any message using this public modulus and exponent. Therefore, the security of RSA relies primarily on how hard it is to find the factors of n, which usually is very difficult based on how the factors were chosen. As with many RSA challenges, we are only given n and e along with the ciphertext, which would normally not be enough information to decrypt the ciphertext.

However, inspecting the source gives us very important information on how this value of n was generated. In particular we need to pay attention to these lines of code:

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

We can see that this value of n is unusual in two ways: it is the product of three prime factors, and these prime factors are bounded by the constraint that they have to be apart from each other by 6. This gives us very important information on the factorization of n.

We must first address that n is the product of three factors, which is unusual since usually only two factors are used to generate n. Would this significantly affect how we decrypt the message?

If we recall that RSA decryption works on the basis of Euler's Totient Theorem, we can observe that $c^d\bmod n = m$ if $ed \equiv 1 \pmod{\phi(n)}$ for any n, as long as n is coprime to c. That doesn't necessarily mean n has to be the product of two prime numbers, so those two steps can proceed as normal. However, how can we calculate this totient of n is the product of three primes rather than only two?

We can actually [calculate the totient](https://en.wikipedia.org/wiki/Euler%27s_totient_function) for any number easily as long as we know its prime factorization. For our number n, this formula turns out to simply be $\phi(n) = (p-1)(q-1)(r-1)$. Again, once we find this prime factorization of n, the security of the cryptosystem topples and we can find the decrypted flag.

Normally, p is not related to q in any way other than being around the same bit size. But in this case, the source code gives us an explicit relationship between our prime factors: q = p + 6, and r = p + 12. That means we can take the equation

$n = pqr$

and instead rewrite it in terms of only one variable, p

$n = p(p+6)(p+12)$

which leaves us with a single-variable polynomial where solving for the value of that variable is quite easy. Once we find p, we can find the other prime factors simply by adding 6 and 12, and from there the encryption is broken.

Here is the script for solving the polynomial to find p, written in sage:

# solve for p

F.<p> = ZZ[]
n = 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
f = p * (p + 6) * (p + 12) - n
print(f.roots())

# p = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077

and here is the python script to calculate the rest of the values and decrypt c:

from Crypto.Util.number import long_to_bytes

n = 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
e = 65537
ct = 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985

p = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077
q = p + 6
r = p + 12

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

flag = long_to_bytes(pow(ct,d,n))
print(flag)