picoCTF_Mind your Ps and Qs 實戰解析

前言

這題主要是在考 RSA 加密演算法，為此我還特地去研究了費馬小定理、尤拉定理、RSA演算法證明，但也因此把自己弄得頭昏眼花。讓我們一起看看這困難的一題吧。

題述

• link：picoCTF - picoGym Challenges
• Description：In RSA, a small e value can be problematic, but what about N? 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進制。

耶~終於打完了。

聽說幫這篇按讚的話對發票都會中喔╰(*°▽°*)╯❤️