PicoCTF19 miniRSA

Challenge

Lets decrypt this: ciphertext? Something seems a bit small

N: 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e: 3

ciphertext (c):  
2205316413931134031074603746928247799030155221252519872649594750678791181631768977116979076832403970846785672184300449694813635798586699205901153799059293422365185314044451205091048294412538673475392478762390753946407342073522966852394341

Hints

RSA tutorial

How could having too small an e affect the security of this 2048 bit key?

Make sure you dont lose precision, the numbers are pretty big (besides the e value)

Solution

We know c = m^e % n where m is the plaintext. E is small, so we could conceivably compute the cube root.

RSACTFTool

$ python RsaCtfTool.py -e 3 -n TODO --uncipher TODO

c = 2205316413931134031074603746928247799030155221252519872649594750678791181631768977116979076832403970846785672184300449694813635798586699205901153799059293422365185314044451205091048294412538673475392478762390753946407342073522966852394341
def find_cubic_root(n):
    a = 1
    b = n
    while b - a > 1:
        mid = (a + b) // 2
        if mid**3 > n:
            b = mid
        else:
            a = mid

    if a ** 3 == n:
        return a
    elif b ** 3 == n:
        return b
    else:
        return 0

m = find_cubic_root(c)
h = hex(m)
print(h)
p = str(hex(m)[2:]).decode('hex')
print(p)

Flag

picoCTF{n33d_a_lArg3r_e_0a41ef50}