前言
這題主要是在考 RSA 加密演算法，為此我還特地去研究了費馬小定理、尤拉定理、RSA演算法證明，但也因此把自己弄得頭昏眼花。讓我們一起看看這困難的一題吧。
題述
- link：picoCTF - picoGym Challenges
- Description：In RSA, a small
evalue can be problematic, but what aboutN? Can you decrypt this? values - hint：Bits are expensive, I used only a little bit over 100 to save money
把 values 下載下來後會長下面這樣
c 為密文、n 和 e 為公鑰。要想拿到明文還需要私鑰(d)，而要怎麼拿到私鑰呢？
開始解題
首先我們要了解 RSA 的加密方式，如下：
C 是密文，M 是名文。
由第 5 點我們知道 d 可以利用逆模運算得到，而在 python 中逆模函數有兩種。
第一種 inverse：
想要用 inverse 需要先安裝它的套件，因此我們可以在 Terminal 中下這個指令。
pip 不行可以用 pip3 試試。
當我們引入 inverse 的函式庫後就可以使用了。
inverse(2,3) 會等於 2 是因為 2*2 mod 3 = 1
第二種 pow：
其實 pow 函式比較廣為人知的是他開次方的用法，不過，如果我們使用下列方法就可以變成逆模運算。
最新版的 python 可以直接在 pow 中間加一個 -1 變成逆模運算。
萬事俱備只欠東風，而這個東風就是我們的 𝜑。由算式中我們可以看到 e 乘 d 後是 mod 𝜑，而 𝜑 是由 (p-1)(q-1) 而來，又 N=p*q，所以只要我們分解出 p、q 就可以知道 𝜑，就可以得到 d，就可以拿到 M，就可以解出 flag 了(YA~)。
而 p、q 也有兩種分解方法。
第一種 factordb.com
這是一個可以幫我們分解出質因數的網頁，不過，有時他也會有解不出來的時候需要看運氣。
第二種 yafu
- 下載解壓縮完
- 點開 yafu-x64
- 輸入 factor(要分解的數)
- 點開 factor 文件檔就可以看到分解出來的數
不過，這個跑很慢，所以建議是第一種方法不行再試 yafu。
接著利用 python 拿到 flag，如下。
倒數第二行是測試用不用理它。
最後一行的 hex() 是將 int 轉為 16 進制，bytes.fromhex() 是將 hex 轉為 bytes，而 [2:] 是因為 hex() 輸出的前兩個字是 0x，0x 是為了告訴電腦這是 16 進制。
耶~終於打完了。
聽說幫這篇按讚的話對發票都會中喔╰(°▽°)╯❤️