"D" is for Dumb Mistakes

Challenge:

To show off their 1337 programming skills, DEADFACE attempted to create their own encryption process to help them communicate privately. Although the encryption process is working, the decryption process is flawed. The De Monne security team was able to find DEADFACE's code and can see that they are trying to use the RSA algorithm with these variables:

• Prime numbers of 1049 and 2063
• Exponent of 777887

Recompute the decryption key (d) and submit the flag as flag{d=VALUE}

Solution:

My non-math brained understanding of the RSA key generation process is as follows:

1. Choose two random primes, p and q (these should be large for the encryption to be effective)
2. Calculate n = pq (n is half of the each key)
3. Calculate Euler's totient, a.k.a Phi of n (This is a count of the number of positive integers less than n and coprime to n. Since we know the factors of n this is simply ϕ(n) = (p−1) * (q−1))
4. Choose an integer e that is between 1 and ϕ(n), and is coprime to ϕ(n) (this is the second half of the public key)
5. Choose an integer d where ed mod φ(n) = 1 (this is the second half of the private key)
   5a. This can be calculated as d = (k * ϕ(n) + 1) / e while substituting k for 1,2,3,4,5... phi until d is an integer.
   5b. Can also be solved with d = e^-1mod phi

Given that p, q and e are provided in the challenge description we can solve for d using Python's built-in pow(number, power, modulus) function:

• number- the base value that is raised to a certain power
• power - the exponent value that raises number
• modulus - divides the result of number raised to a power and finds the remainder e.g. number ^ power % modulus

$ python3 -q
>>> p = 1049
>>> q = 2063
>>> e = 777887
>>> phi = (p - 1) * (q - 1)
>>> d = pow(e, -1, phi)
>>> print(d)
1457215

The accepted flag was: flag{d=1457215}