---
# System prepended metadata

title: 2020程安 Crypto筆記02 (RSA)
tags: [crypto, 程式安全]

---

# 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太大: 加密很慢