RSA 是 CTF 裡 最經典的密碼學演算法 之一，幾乎每場比賽都會有相關題目。

它是一種非對稱加密，與對稱加密（像 Caesar、Vigenère）不同。

什麼是 RSA?

• RSA 是 非對稱式加密 的代表。
• 特點：
  • 有 公鑰 (public key) 和 私鑰 (private key)。
  • 公鑰可以公開給所有人用來加密。
  • 私鑰則由擁有者保管，用來解密。

👉 這樣就能實現安全的通訊。

RSA 的計算基礎

1. 選擇兩個大質數 p ,q，計算 n = p × q
2. 計算歐拉函數 φ(n)=(p−1)(q−1)
3. 選一個公開指數 e，通常是 65537。
4. 計算私鑰 d，滿足：e×d ≡ 1(mod φ(n))

• 公鑰：(n,e)
• 私鑰：(n,d)

加解密公式

• 加密：c ≡ m^e(mod n)

• 解密：m ≡ c^d(mod n)

其中：

• m：明文
• c：密文

Python 操作 RSA

使用 pycryptodome 套件：

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA

c = <given_c>
n = <given_n>
e = <given_e>


p = ?
q = ?
#透過 https://factordb.com/ 或其他方法解出p跟q

phin = (p-1)*(q-1)

d = pow(e,-1,phin)
m = pow(c,d,n)
msg = hex(m)
msg = msg[2:]
msg = bytes.fromhex(msg)
print(msg)

好複雜，來看看題目吧

picoCTF - EVEN RSA CAN BE BROKEN???

這題進行nc連線後會得到三個參數:N、e、c
我們可以去 https://factordb.com/ 拆解N

得到p為2，q則為N/2
寫進我們上面的範例程式中

好欸獲得flag了~

CTF 常見 RSA 題型

1. Wiener's Attack (d 太小)
2. 模數分解（n 太小，被直接分解成 p, q）
3. Bleichenbacher’s attack
4. Chosen Ciphertext Attack
5. Common Modulus Attack

以上就是一些簡單的RSA知識!，明天會講有關雜湊函式的內容
想看更多，歡迎明天再來ㄛ~