# RSA 筆記

選擇兩大質數p, q和一整數e
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

加密m
c = pow(m, e, n)
解密c
m = pow(c, d, n)

* 驗證正確性
* 費馬小定理
* 中國餘數定理
* 因數分解工具
* http://www.factordb.com/index.php
* p, q太接近
* fermat factorization
* p − 1 的最大質因數很小
* Pollard’s p - 1 Algorithm
* p + 1 的最大質因數很小
* Williams’s p + 1 Algorithm
* r − 1 的最大質因數很小
* Cycling Attack
* r 是 p − 1 的最大質因數
* e太小
* direct eth root
* broadcast attack
* d太小
* Wiener’s attack
* 重複使用參數
* 兩個n有相同質因數
* Common Factor Attack
* 相同n不同e
* Common Modulus Attack
* 不允許解密指定密文
* Chosen Ciphertext Attack
* 只幫你解出最低位元
* LSB Oracle Attack
* 回傳最高位元是否為0x0002(PKCS#1 v1.5)
* Bleichenbacher
* 看不懂ㄉ
* Coppersmith Method
* 已知訊息格式(padding未隨機)
* Stereotyped messages
* 加密多個明文且明文有關連(m1 = f(m2))
* Franklin-Reiter Related Message Attack
* m1 = 2
kM + r1, m2 = 2
kM + r2
r1,r2 是 padding，M 是真正的明文
* Coppersmith Short-Pad Attack

###### tags: `CTF`