Solution

The first step of the question is to realize that the question is testing RSA. and that the value of N is determined by 2 randomly generated prime numbers, before the plaintext is put to the power of the public exponent before modulus b the value of N. We shall call the 2 primes p and q.

Euler’s totient function, denoted as φ(n), is a mathematical function that counts the number of positive integers less than ‘n’ that are coprime (relatively prime) to ‘n’. In the context of RSA, φ(n) is used to calculate the private exponent ‘d’ for decryption.

For RSA, φ(n) is calculated as follows: φ(n) = (p - 1) * (q - 1)

n, e, and c are the modulus, public exponent, and ciphertext, respectively. These are commonly part of an RSA public key.

The code calculates φ(n) as (p - 1) * (q - 1) and stores it in the variable euler. It then computes the private exponent ‘d’ using the modular inverse of ‘e’ (public exponent) with respect to ‘euler’ in the line: d = pow(e, -1, euler)

Finally, it decrypts the ciphertext ‘c’ using the private exponent ‘d’ and the modulus ‘n’ using the following line: answer = pow(c, d, n)

‘d’ is used to decrypt the ciphertext ‘c’. This is based on the mathematical relationship that if you raise the ciphertext ‘c’ to the power of ‘d’ modulo ‘n’, you recover the original plaintext message. The formula is as follows: plaintext = c^d mod n

At last, after decryption, the code uses long_to_bytes to convert the numeric result ‘answer’ to its byte representation, which should be the original plaintext message: b’LNC24{pR1m3s_4eva!}’

Flag: LNC2024{pR1m3s_4eva!}

View challenge source on GitHub