Tags: crypto
Rating:
We are given a .json file with N(modules), e(encryption) and ct(encrypted message)
{"N": 148818474926605063920889194160313225216327492347368329952620222220173505969004341728021623813340175402441807560635794342531823708335067243413446678485411066531733814714571491348985375389581214154895499404668547123130986872208497176485731000235899479072455273651103419116166704826517589143262273754343465721499,
"e": 3,
"ct": 4207289555943423943347752283361812551010483368240079114775648492647342981294466041851391508960558500182259304840957212211627194015260673748342757900843998300352612100260598133752360374373}
We can see that the encryption(e) is very small and also that c is relatively very small compared to N
Because these two things we can try and take the cube root (root 3) of our encrypted message (ct)
So now that we know what to do lets write the code for it.
I wrote the code in python using gmpy2 and pycrypto libraries
(gmpy2 for the cube root and pycrypto to make the numbers bytes and from then to strings)
First of all lets import our libraries:
import gmpy2 #to do the cube root
from Crypto.Util.number import long_to_bytes #to print it in a readable way
Secondly lets write what is n(modules), e(encryption) and c(ct) are (from now on I will say c instead of ct or encrypted text/cipher):
n = 148818474926605063920889194160313225216327492347368329952620222220173505969004341728021623813340175402441807560635794342531823708335067243413446678485411066531733814714571491348985375389581214154895499404668547123130986872208497176485731000235899479072455273651103419116166704826517589143262273754343465721499
e = 3
c = 4207289555943423943347752283361812551010483368240079114775648492647342981294466041851391508960558500182259304840957212211627194015260673748342757900843998300352612100260598133752360374373
Now lets take the cube root of c and store it in a variable:
gmpy2.get_context().precision=2048 #So it will be precise, I'm not going to fully explain what gmpy2 or this command does herer, feel free to go look at the documentation
m = gmpy2.root(c,e) #taking the cube root(e or 3) of the message
Lastly we need to print the deciphered message:
print(long_to_bytes(m).decode()) #prints the deciphered message
All the code together (in python 3.8.5 and with less comments):
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 148818474926605063920889194160313225216327492347368329952620222220173505969004341728021623813340175402441807560635794342531823708335067243413446678485411066531733814714571491348985375389581214154895499404668547123130986872208497176485731000235899479072455273651103419116166704826517589143262273754343465721499
e = 3
c = 4207289555943423943347752283361812551010483368240079114775648492647342981294466041851391508960558500182259304840957212211627194015260673748342757900843998300352612100260598133752360374373
gmpy2.get_context().precision=2048 #setting precision to be 2048
m = gmpy2.root(c,e) #getting the cube root(root 3) of c
print(long_to_bytes(m).decode()) #printing the flag/message
Running the code (saved the code as flag-Bootless_RSA.py):
--> python3 flag-Bootless_RSA.py
dvCTF{RS4_m0dul0_inf1nity}
This is my first writeup ever!