前言

這次在 picoCTF 選了一題 RSA 的題目：miniRSA，想自己挑戰的讀者一樣先不要往下看~~

Write-up

miniRSA

從題目下載下來的檔案內容如下：

N: 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e: 3

ciphertext (c): 2205316413931134031074603746928247799030155221252519872650073010782049179856976080512716237308882294226369300412719995904064931819531456392957957122459640736424089744772221933500860936331459280832211445548332429338572369823704784625368933

我們可以先看看 wiki 中 RSA 的說明：

(N,e) 是公鑰，(N,d) 是私鑰

回到題目，當中給了 N、 e、c 三個值，應該是要我們用 (N,e) 來嘗試破解出明文。

題目的 hint 2 說：How could having too small an e affect the security of this 2048 bit key?

RSA 的加密算法是：
c = m^e mod N

因此我們需要找出讓以下式子成立的 i：
i x N + c = m^e

或者說得更精確一點是要找出上式成立時的 m，總之我們撰寫一段程式如下：

import gmpy2

N = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e = 3
c = 2205316413931134031074603746928247799030155221252519872650073010782049179856976080512716237308882294226369300412719995904064931819531456392957957122459640736424089744772221933500860936331459280832211445548332429338572369823704784625368933

for i in range(1000):
    m, exact = gmpy2.iroot(c + i * N, e)
    if exact:
        print("i = ", i)
        print("m = ", bytes.fromhex(hex(m)[2:]))
        break

iroot(x, n) 的用途是求 x 的 n 次方根
Ref: https://gmpy2.readthedocs.io/en/latest/mpz.html#gmpy2.iroot

執行之後，m 轉成 bytes 就是我們要的 flag！

後記

iTHome 好像不支援 LaTex，只好全部都改回來 XD