---
# System prepended metadata

title: RSA 筆記
tags: [CTF]

---

# 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`