Write-up on CTFlearn’s challenge 120 - RSA noob. Simple maths… Challenge author: intelagent.
Crypto, 60 points
These numbers were scratched out on a prison wall. Can you help me decode them? https://mega.nz/#!al8iDSYB!s5olEDK5zZmYdx1LZU8s4CmYqnynvU_aOUvdQojJPJQ
Let’s download the file from the Mega link and take a look at its content to see what we are facing.
e: 1 c:9327565722767258308650643213344542404592011161659991421 n: 245841236512478852752909734912575581815967630033049838269083
From the name of the flag and the values it contains, we can know this is an RSA encryption challenge.
RSA (Rivest-Shamir-Adleman) is an asymmetric cryptosystem (cipher) widely used for secure data transmissions. The main algorithm behind it is based on simple maths. Let’s take a simple look at it.
Each “user” of the RSA cryptosystem owns 3 values.
n, the modulus, which is public.
e, the exponent, which is also public.
d, the private exponent, which is, unlike the others, private.
Let’s say we have two users, Alice and Bob. They each have a unique n and d, but their e is the same, shared by the system they are using. Bob wants to send a message to Alice, so he performs this calculation:
c = m^e mod n
Where m is the message he wants to send and n is Alice’s public modulus.
Alice receives that message and performs the decryption calculation below.
m = c^d mod n
c being the ciphertext Bob send her and d being her private key.
The magic behind those operations comes from the process to generate the keys, often called keygen. I won’t go in much details about that because it involves quite complex maths that are not required to understand that challenge.
Learn more about RSA here.
In our situation, the variables which ables us to exploit are e. Remember the encryption calculation, the message is raised to the power of e. If e is 1, as it is in this challenge, the operation can be reduced to that.
c = m mod n
That means that if the message m was less than n, then the ciphertext is exactly equal to the message.
Let’s check that with python (
First, we need to do is to import binascii, it will be useful later on.
>>> import binascii
Second, get the hexadecimal value of the ciphertext. The last
[2:] just strips out the “0x” at the beginning of the hex value.
Finally, copy that string (with the quotes) and pass in the binascii.unhexlify function. That function will take a string out of out hexadecimal value.
Voilà, you are now supposed to get the flag! Don’t forget to remove the b’’ format characters before entering it.