picoCTF
Mini Rsa (both) [300 pts]
Challenge Description:
Let’s decrypt this: ciphertext? Something seems a bit small.
Note that the methods for this challenge work for both the Mini RSA challenge worth 70 points and the miniRSA challenge worth 300 points. The numbers in this writeup, however, are those of the miniRSA challenge. The Mini RSA challenge, though, does not require such a complex method. I do think learning this method is much more helpful though :)
We’re given an RSA ciphertext:
N: 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e: 3
ciphertext (c): 2205316413931134031074603746928247799030155221252519872649649212867614751848436763801274360463406171277838056821437115883619169702963504606017565783537203207707757768473109845162808575425972525116337319108047893250549462147185741761825125
The e value seems rather small. Maybe we can exploit that!
Since \(m^{e}\equiv c\;(mod\;n)\),
\(m=\sqrt[e]{c+kn},\;k\in \mathbb{N}\)
Thus, we can just use a program to progressively increment k until we find a valid value of m.
The implementation follows as such:
from gmpy2 import iroot #iroot allows for large integer roots
c = 2205316413931134031074603746928247799030155221252519872649649212867614751848436763801274360463406171277838056821437115883619169702963504606017565783537203207707757768473109845162808575425972525116337319108047893250549462147185741761825125
e = 3
n = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
for i in range(n):
m = c + n * i
a = iroot(m, e)
if a[1]: # if the result is exact (rational)
print(a)
break
a = format(a[0], 'x') # format as hex
print(a)
ascii_str = bytes.fromhex(a).decode("ASCII") # convert to ascii
print(ascii_str)
picoCTF{n33d_a_lArg3r_e_606ce004}