# 2020程安 Crypto筆記03 (RSA相關攻擊整理)
###### tags: `程式安全` `crypto`

## RSA相關攻擊情境整理
`Note:
明文m加密為密文c,攻擊者已知公鑰(n,e)及密文c`
`RSA要求0<=m<n`

| 攻擊名稱 | Condition | result | 備註|
| -------- | -------- | -------- | --- |
| Common Factor Attack | 兩把公鑰的$n_1, n_2$有共同質因數 | 求$gcd(n_1, n_2)$ |
| Common Modulus Attack | 已知兩把$n$相同,且$gcd(e1,e2)=1$的公鑰,用這兩把公鑰加密明文$m$,$c_1 = m^{e_1}\ (mod\ n), c_2 = m^{e_2}\ (mod\ n)$ | 根據貝祖定理, 必存在一組整數解$(x,y)$,使$ax + by = gcd(a,b)$,因此利用擴展歐基里德算出$e_1x + e_2y = gcd(e_1,e_2)=1$的整數解$(x,y)$,則可得${c_1}^x\cdot {c_2}^y = {m^{e_1}}^x{m^{e_2}}^y = m^{e_1x+e_2y} = m^1 = m\ (mod\ n)$
| Fermat Factorization | $\vert p-q\vert$很小 | 利用$n=a^2 - b^2$,先由$a = \lfloor \sqrt n\rfloor$往下找 ,若可得$b \in \mathbb{Z}$,則$p=a+b, q=a-b$ | $\because b =\frac{\vert p-q\vert }{2}$,若$b$很小就很快能找到 |
| Direct $e^{th}$ root | $m, e$都很小, $s.t.\ m^e < n$| $\because m^e = c < n$,因此直接求$\sqrt[e]{c} = m$ | 因此通常會先把明文$m$補padding到跟$n$差不多長 |
| | $m,e$很小,但$m^e$還是比$n$大一點點 | $\because m^e = c\ (mod\ n)$, 故假設$m^e = c + nk$, 暴力try $k$, 可求$\sqrt[e]{c + nk} = m$
| Broadcast Attack | 用$e$個不同的$n$對同一個$m$做加密, $\forall i \le e,\ c_i = m^e\ (mod\ n_i)$ | 用中國餘式定理可得$m^e = c\ (mod\ (n_1\cdot n_2\cdot\ ...\cdot n_e))$, 又 $m^e = c < n_1 \cdot n_2\cdot\ ...\cdot n_e$, 可求$\sqrt[e]{c} = m$ |
| Pollard p-1 | $p-1$的最大質因數$B$很小 | $\because p-1 \vert (1 \cdot 2 \cdot ...\cdot B) \Rightarrow 2^{B!} = 2^{k(p-1) } = 1^k = 1\ (mod\ p), \therefore p \vert 2^{B!}-1$, 故可求$gcd(2^{B!}-1, n) = p$ | 費馬小定理: 若$a$跟$p$互質, 則$a^{p-1} = 1\ (mod\ p)$ |
| Wiener Attack | $q<p<2q$ 且 $d < \frac{1}{3} n^{\frac{1}{4}}$ ($d$很小) | 暴力try $\frac{e}{n}$的收斂連分數,令分子為$k$,分母為$d$,代入$ed-1=k\phi(n)$,得$\phi(n)$,又$\phi(n) = n - (p+q) +1$,故可得$(p+q)$,此時再求$x^2-(p+q)x+N=0$的兩根即為$p,q$ | ex $\frac{42667}{64741} = 0 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{13}}}}$,則其收斂連分數集合為 $\{0+\frac{1}{1}, 0 + \frac{1}{1+\frac{1}{1}}, 0 + \frac{1}{1+\frac{1}{1+\frac{1}{1}}}, 0 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{13}}}},... \}$ |
| Choosen Ciphertext Attack(選擇密文攻擊) | 有個oracle給他密文可以得到明文,但不能解特定密文$c$ | $\because c= m^e\ (mod\ n)$,兩邊同乘$2^e$,得$c\cdot 2^e = m^e\cdot 2^e = (2M)^e\ \ (mod\ n)$,因此把$c\cdot 2^e$丟進oracle可得$2M \%n$, 可求$2^{-1}\cdot (2M\%n) = m\ (mod\ n)$ | |
| LSB Oracle Attack | 有個oracle給他密文會得到明文的最低那個bit | 第一round,兩邊同乘$2^e$,拿$c\cdot 2^e$丟給oracle可得$2m\%n$的最後一個bit,若此bit為0($2m\%n$為偶數),則$0\le 2m < n$,,反之若為奇數,則$2n>2m>n$, 下一輪考慮$4m\%n$ | 因為$2m$必為偶數,$n$必為奇數,因此$2m>n \Leftrightarrow 2m\%n =(2m-n)$為奇數,$2m<n \Leftrightarrow 2m\%n = (2m)$為偶數,第2輪,參考Note |

- Note: LSB Oracle Attack