Written by Austin Zhou, Writeup by Jester
You stumble upon a RSA encrypted message that looks different... All you know is the public key. Can you decrypt the message? Data
The message is about RSA.
To solve this problem, we must (obviously) first understand RSA. RSA encryption utilizes extremely large numbers to encrypt messages. A message, m, is converted to hex/decimal, then modular arithmetic is performed using a public key and public exponent.
To decrypt, we must obtain the private key.To do this, we must factor the public key. Normally, this would be impossible, but since the public key is relatively small, it can be done.
So, we get factors p and q:
p = 1398023584459
q = 29065965967667
We also need the totient, which is (p-1) * (q-1).
totient = 40634905927850661848135028
The private key, d, is equivalent to the inverse mod of the public key and the totient.
Then, we also need the public exponent. But wait! That's not provided in the problem.
Even after writing a script to brute force it, it would be nearly impossible to find the flag among the huge piles of ascii text... or is it?
This is where the hint comes in. It says "The message is about RSA." Clearly, it is quite an obvious (and worthless) hint at first glance.
Using this surprisingly useful hint, we can write a python script that brute forces the public key, and if the outputted string has "rsa" in it, then it will print it out.
Our code:
def egcd(a, b): #inverse mod function (its not built in :O)
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m): #inverse mod function
g, x, y = egcd(a, m)
if g != 1:
return -1
else:
return x % m
c = int("ac470f7350ea67d7a0696",16)
p = 1398023584459
q = 29065965967667
while 1: #loops infinitely until flag is found
d = modinv(i,(p-1)*(q-1)) #uses inverse mod
if(d!=-1):
answer = (hex(pow(c,d,p*q))) #turns into hex after powmod
answer = answer[2:-1]
if(len(answer)%2==1):
answer = '0' + answer
xyzwhatever = answer.decode("hex") #turns hex to ascii
if("rsa" in xyzwhatever.lower()): #prints flag if "rsa" is in it (.lower() prevents case sensitivity)
print(i) #prints public exponent used
print xyzwhatever #prints possible flags
After running the code, we get the flag!
rsa_2_easy