# 2020程安 Crypto筆記02 (RSA) ###### tags: `程式安全` `crypto` ## RSA :::info 1. 取一個prime p 2. 取一個prime q 3. 得到 n = p * q 4. 取一個跟$\phi(n)$互質的整數 e 5. 計算e在mod $\phi(n)$下e的反元素d, > d = ${e^{-1}}$ (mod $\phi(n)$) > ed = 1 (mod $\phi(n)$) `因為n可質因數分解成pxq -> ϕ(n) = (p-1)(q-1)` `Note:` `ϕ(p)是歐拉函式,代表從1~p跟p互質的數有多少` `如果p是質數, 則 ϕ(p) = p-1 (n只跟自己不互質)` `再若p是合數,且可質因數分解成p1xp2x...xpn, ϕ(p) = (p1-1)(p2-1)...(pn-1)` 6. 加密明文m, 計算${m^e}$ = c:密文 解密密文c, 計算${c^d}$ = m `Note: 即公鑰為(e,n), 密鑰為(d,n)` `RSA要求0<=m<n` ::: ### 攻擊原理 - 攻擊者只知道公鑰$(e,n)$,且已知$n$為兩質數相乘 因此只要能**對$n$做質因數分解**,就可以得到$p$及$q$ 就能知道 $\phi(n) = (p-1)(q-1)$ 進而再利用$e$及$\phi(n)$去算出私鑰的$d$ ### 質因數分解 - 先備定理(二次剩餘) $若a為mod\ n的二次剩餘\ (a\in QR_n)\ ,\ 則z^2 = a\ (mod\ n)有四個解(2組解):$ $\ \ \ \ \{x,n-x\}\ =\ \{x,-x\}\ in\ Z_n^*$ $\ \ \ \ \{y,n-y\}\ =\ \{y,-y\}\ in\ Z_n^*$ - 作法 1. 已知$x = 1\ \vee\ n-1 \in Z_n^*$, 使得$x^2 = 1\ (mod\ n)$成立 2. 解$z^2 = 1\ (mod\ n)$, $z在mod n$下最多有4個解(其中一組為已知$\{1, n-1\} = \{1, -1\}$) `Note: n-x = -x (mod n)` 3. 假設另一組的其中一解的pattern為$Z(g) = g^{2^{t-1}*r}$ :::success <原理> 1. 已知$m^{ed} = m\ (mod\ n)$ $\rightarrow m^{ed-1} = 1\ (mod\ n)$ 2. 又 $ed -1 = 0\ (mod\ \phi(n))$ $\rightarrow ed - 1 = \phi(n) * k = k(p-1)(q-1)$ $\Longrightarrow$ 因為$(p-1)$及$(q-1)$皆必為**偶數**,故設$ed-1 = 2^t * r$ 3. 代回1. 故 $(m^{2^{t-1}*r})^2 - 1 = 0\ (mod\ n)$ ,求解$Z = m^{2^{t-1}*r}$ $\rightarrow (Z+1)(Z-1) = 0\ (mod\ n)$ (改寫成$Z^2 - 1 = 0\ (mod\ n)$格式, 不然好醜QQ) 4. 暴力try $(g, t, r)$ 解$Z$ (1) 如果 $Z(g) = \pm1$ (已知解),找下一個$(g,t,r)$ (2) 如果 $Z(g) \neq \pm1$ (找到未知解了), 則計算$gcd(Z-1, n)$及$gcd(Z+1, n)$ $\ \ \ \ \rightarrow$`如果結果都在1~n之間,就是p和q,否則找下一個(g,t,r)` :::success <原理> 4. 由3., 此時有兩種case case1: $(Z-1)$或$(Z+1)$可被n整除 case2: $p$整除$(Z-1)$且$q$整除$(Z+1)$,或是相反 $\rightarrow$ 因此直接計算$gcd(Z-1, n)$及$gcd(Z+1, n)$ `如果計算結果為1或n,代表case1` `若可以找到兩個結果都在1~n之間,代表case2成立,兩個結果就是p和q` ### 攻擊 #### Fermat factorization(p相關): - 原因: $|p-q|$ 太小 - Fermat Factorization: 假設 $p$ , $q$ 皆為奇數, $n = p * q$ 令 $a = \frac{p+q}{2},\ b = \frac{|p-q|}{2}$ 則 $p = a-b,\ q=a+b$ 此時 $n = (a-b)(a+b) = a^2 - b^2$ - 如果 $|p-q|$ 夠小,就會造成 $b$ 也很小, 因此攻擊者只需要從最接近且小於$\sqrt{n}$的整數開始帶入$a$,往下找直到 $n - a^2$ 可以開出平方根 = $b$,就可以帶入 $a,b$ 求 $p,q$ :::warning **Example:** 給 $n = 65537$ 1. $65537 > 81^2$, 取 $a = 81$ 2. $65537 - 81^2 = 4$, 因此可得解為$\pm2$, 取$b = 2$ 3. 可得 $p = a + b = 83, q = a-b=79$ ::: #### Pollard's p-1 algo(p相關) - 原因 : $p-1$ 的最大質因數很小 - 概念 若$p$為$n$的一個質因數,已知$n$求$p$ 1. 要找到一個跟$n$不互質的數$s$ 如此一來$s$跟$n$就會有公因數$p$ (即 $p|gcd(s,n)$) 2. 若$x = 1\ (mod\ p)$, 則 $p|gcd(x-1, n)$ --> 如何找$x$? 3. 由費馬小定理可知: 當$p$為質數且$x$跟$p$互質, 則$x^{p-1} = 1\ (mod\ p)$ --> 考慮 $2^{p-1} = 1\ (mod\ p)$ --> 但 $p$ 未知QQ 4. 費馬小定理還有個性質: 如果左右同乘相同值,結果亦相同 --> 考慮一個$(p-1)$的最大公因數$B$ --> 則$(p-1)|B!$, 令 $B! = k(p-1)$ 由於 $2^{p-1} = 1\ (mod\ p)$ $\Longrightarrow 2^{B!} = (2^{p-1})^k = 1^k = 1\ (mod\ p)$ 5. 故由2. 已知 $x = 2^{B!} = 1\ (mod\ p)$, 可得知 $p|gcd(2^{B!}-1, n)$ --> 因此當B很小時, $2^{B!}-1$ 就也很小,求得的$gcd$也會比較小,更容易做質因數分解來求得p!! - implementation: ```python def pollard(n): a = 2 b = 2 while(True): a = pow(a, b, n) # 2^B! (mod n) s = gcd(B - 1, n) if (1<s<n): # 找到gcd return s else: # gcd = 1 b += 1 ``` #### William's p+1 Algo(p相關) - 原因: $p+1$ 的最大質因數太小 #### Cycling Attack(p相關) - 原因: 考慮 $p-1$ 的最大質因數 $r$, $r-1$的最大質因數太小 #### 沒選好e 1. e太大: 加密很慢