This was the first actual crypto challenge I solved. With the help of some similar challenge writeups online I found the vulnerability and used it to break the encryption.

The Challenge

We get a simple python file containing some cryptographic operations.


from Crypto.Util.number import *

flag = b"REDACTED"

p = getPrime(1024)
q = getPrime(1024)
n = p*q

m = bytes_to_long(flag)

c = pow(m,3,n)


It generates two random 1024-bit prime numbers and encrypts the flag in a similar way to RSA.
At the bottom, it gives us the output of variables c and n with the real flag.


It multiplies the two primes together into a variable n, and also converts the string flag into a number with the bytes_to_long function and puts it into m.
Then it uses the pow function with 3 arguments. The first argument means the base number, the second argument is the exponent, and the third argument is the modulus. It is often represented by the % operator, so this function does the same as m**3 % n. The modulus is the remainder after dividing by that number (Example: 14 % 3 = 2).

The trick that makes sure that you can't just reverse this operation is the modulus. Because you will need to go through every possible multiple that it could have been the remainder of. Here is how it looks (Remember, we have c, and want m for the flag):

c = m**3 % n
c + n*k = m**3 where k increments by 1 every time
m = (c + n*k)**(1/3) (take the cube root)

It looks like we have a nice equation we can fill in now, but we still have k that needs to be incremented until we have our original value.
And since we don't know what the original value is, we don't know when we have our correct value of k.


The trick here is the fact that we raise m to only the 3rd power, meaning the value of m**3 is not going to be very big, and then by taking the % n of it, the divider part of it will not be very large. This means we don't have to try that many values of k before we get there.
Now we can keep trying values of k until the m we get has the first letters of 'CTF'. When it is, there is a very high chance that this is the flag, and we can print the whole value.

The gmpy2 module has a really fast and useful function for calculating roots with big numbers. I use the iroot(m, 3) to calculate the perfect root. It returns a tuple of first the value after taking the root, and then a boolean value saying if it is perfect or not. Using the inverse function of long_to_bytes we can also get back the flag instead of just a number. Then combine the two to take the cube root of the attempt, and then see if it starts with the letters 'CTF' when decoded.

All of this combined in a script looks like this:


from Crypto.Util.number import *
from gmpy2 import iroot

c = 15478048932253023588842854432571029804744949209594765981036255304813254166907810390192307350179797882093083784426352342087386691689161026226569013804504365566204100805862352164561719654280948792015789195399733700259059935680481573899984998394415788262265875692091207614378805150701529546742392550951341185298005693491963903543935069284550225309898331197615201102487312122192298599020216776805409980803971858120342903012970709061841713605643921523217733499022158425449427449899738610289476607420350484142468536513735888550288469210058284022654492024363192602734200593501660208945967931790414578623472262181672206606709
n = 21034814455172467787319632067588541051616978031477984909593707891829600195022041640200088624987623056713604514239406145871910044808006741636513624835862657042742260288941962019533183418661144639940608960169440421588092324928046033370735375447302576018460809597788053566456538713152022888984084306297869362373871810139948930387868426850576062496427583397660227337178607544043400076287217521751017970956067448273578322298078706011759257235310210160153287198740097954054080553667336498134630979908988858940173520975701311654172499116958019179004876438417238730801165613806576140914402525031242813240005791376093215124477

k = 0
while True:
    m = c + n*k  # Reversed function, try this m
    attempt = long_to_bytes(iroot(m, 3)[0])
    if attempt[:3] == b"CTF":  # If the first part is 'CTF'
    k += 1  # Increment

This will try values of k until m starts with 'CTF', when it is it will print the k value where it matched, and decode the number.
After running it we quickly get our low value of k to be 1831, and the decoded number as the flag!