[Web] RSA 原理

Web：RSA 原理

工具：

Python: Pycrypto

Go: crypto/rsa

功能：公開金鑰密碼系統

優缺點比較

• 秘密金鑰密碼系統（Secret-Key Cryptosystem）
• 優點
• 效率高
• 缺點
• 只有一把秘密金鑰，散佈有安全疑慮
• 公開金鑰密碼系統（Publick-Key Cryptosystem）
• 優點
• 兩把公私鑰，只需提供公鑰，安全性高
• 缺點
• 效率低
• 常見做法
1. A 取得 B 的公開金鑰
2. A 以亂數產生一次性秘密金鑰，並且用 B 的公開金鑰加密，傳送給 B
3. B 將收到的資料用其私密金鑰解開，取得 A 產生的秘密金鑰
4. A 和 B 開始用此秘密金鑰通訊

RSA 原理

數學前導

互質關係

• 兩個正整數，除了 1 以外，無其他公因數，則稱這兩個數是互質關係（coprime）
• 常見規則
• 任意兩個質數，例：17 和 101
• 一個數是質數，另一個數只要不是前者的倍數，例：3 和 10
• 如果兩個數之中，較大的數為質數，例： 97 和 57
• 1 和任意一個自然數，例：1 和 99
• p 是大於 1 的整數，則 p 和 p-1 為互質關係，例：57 和 56
• p 是大於 1 的奇數，則 p 和 p-2 為互質關係，例：17 和 15
  假設 p 和 p-2 有非 1 的公因數 k
  則 p-(p-2) = 2 必然也是 k 的倍數，而 k 不為 1 故 k=2
  但 p 和 p-2 皆是奇數，故矛盾得證互質
  

歐拉函數

• 任意正整數 \(n\)，請問在小於等於 \(n\) 的正整數之中，有多少個與 \(n\) 構成互質關係？
  計算這個值的方法就叫做歐拉函數，以 \(\varphi(n)\) 表示
  例：正整數 8，1 到 8 之中為可構成互質關係的是 1、3、5、7，所以 \(\varphi (n) = 4\)
• 公式推導
1. 若 \(n=1\)，則 \(\varphi (1)=1\)
2. 若 \(n\) 為質數，則 \(\varphi (n)=n-1\)
3. 若 \(p\) 為質數，當 \(n=p^k\)，則 \(\varphi (n)=p^k-p^{k-1}=p^k(1-\frac{1}{p})\)
   因只有 \(p\) 的倍數才不與 \(n\) 互質
   也就是 \(1\times p\)、\(2\times p\)、\(3\times p\)、…、\(p^{(k-1)}\times p\)，共 \(p^{(k-1)}\) 個
   \(k=1\) 則 \(n\) 為質數，也就是第二個情況
4. 若 \(p_1\) 和 \(p_2\) 互質，當 \(n=p_1p_2\)，則 \(\varphi (n)=\varphi (p_1p_2)=\varphi (p_1)\varphi (p_2)\) 證明
5. 任意大於 1 的正整數，都可質因數分解成 \(n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}\)
   $$ \begin{align*} \because (4)\ \varphi (n)&=\varphi (p_1^{k_1})\varphi (p_2^{k_2})\cdots \varphi (p_r^{k_r})\\ \because (3)\ &= p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\\ &= n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\\ \end{align*} $$ 例：\(\varphi (100)=\varphi (2^2\times 5^2)=100(1-\frac{1}{2})(1-\frac{1}{5})=40\)
   

歐拉定理
當兩個正整數 \(a\) 和 \(n\) 互質時
$$ \begin{align*} & a^{\varphi (n)}\equiv 1(mod\ n)\\ \Rightarrow & a^{\varphi (n)}= 1 + kn\\ \end{align*} $$ 也就是 \(a^{\varphi (n)}\) 被 \(n\) 除後，餘數為 1
換句話說，也是 \(1+ n\)的倍數
當將 \(\varphi (n)\) 乘上任意倍數 \(s\)，餘數仍不變，如下
$$ \begin{align*} a^{\varphi (n)} &= 1 + kn\\ a^{s\cdot \varphi (n)} &= (1 + kn)^s\\ &= 1^s+1^{s-1}\cdot kn+1^{s-2}\cdot (kn)^2+\cdots +(kn)^s \\ &= 1 + {k}'n \end{align*} $$ 當改成兩個正整數 a 與質數 \(p\) 互質，也就是費馬小定理

$$ \begin{align*} & a^{\varphi (p)}\equiv 1(mod\ p)\\ & a^{p-1}\equiv 1(mod\ p)\\ \Rightarrow & a^{p-1}= 1 + kp\\ \end{align*} $$

模反元素
如果兩個正整數 \(a\) 和 \(n\) 互質
那麼一定可以找到整數 \(b\)，使得 \(ab-1\) 被 \(n\) 整除
也就是說 \(ab\) 被 \(n\) 除的餘數是 1
此時的 b 便是 a 的模反元素，而且模反元素不只一個
可用歐拉定理證明
$$ \begin{align*} a^{\varphi (n)} &= a \cdot a^{\varphi (n)-1}\\ &=a \cdot b\\ &\equiv 1(mod\ n)\\ \\ &\Rightarrow a \cdot (a^{\varphi (n)-1}+kn)\\ &=a \cdot b\\ &= a \cdot a^{\varphi (n)-1} + a \cdot kn\\ &\equiv 1(mod\ n)\\ \end{align*} $$

公私密鑰生成步驟

1. 隨機選擇兩個不相等的質數 \(p\) 和 \(q\)，例：2 和 5
2. 計算 \(n=pq\)，例：\(n=2 \times 5 = 10\)
   0d10 = 0b1010，密錀長度也就是 4 位，通常為 1024 位，重要資訊為 2048 位
3. 計算歐拉函數，且因 \(p\) \(q\) 是質數，\(\varphi(n)=(p-1)(q-1)\)
   例：\(\varphi(10)=(2-1)(5-1)=4\)
4. 隨機選擇一個整數 \(e\)，條件為 \(1<e<\varphi(n)\)，且 \(e\) 與 \(\varphi(n)\) 互質
   例：\(e=3\)，實務上通常選擇質數 65537
5. 計算 \(e\) 對 \(\varphi(n)\) 的模反元素 \(d\)
   \(ed \equiv  1 (mod\ \varphi(n))\)
   也就是 \(ed=1+k\varphi(n)\)，可用擴展歐幾里得算法
   例：代入得 \(3d=1+4k\) 求整數解，故 \((d,k) = (7,5)\)
   若是 \((d,k) = (3,2)\)，也是其中一個解，為了與 \(e\)區分，在此不採用
6. 公鑰為\((n,e)\)，私鑰為\((n,d)\)
   例：公鑰為\((10,3)\)，私鑰為\((10,7)\)
   實際應用中，公鑰和私鑰會採用 PEM 格式表達

加密和解密

• 加密用公鑰 \((n,e)\)
• 假設傳送訊息 \(m\)，\(m\) 必須為整數
  字串可取 ascii 值或 unicode 值，且 \(m < n\)
• \(m^e\equiv c(mod\ n)\)
  例：\((n,e)=(10,3)\) \(m=8\Rightarrow 8^3\equiv 2(mod\ 10)\)，得到 \(c=2\) 將之傳送
• 解密用私鑰 \((n,d)\)
• \(c^d\equiv m(mod\ n)\)
  例：\((n,d)=(10,7)\) \(c=2\Rightarrow 2^7\equiv 8(mod\ 10)\)，得到 \(m=8\) 解密成功
  事實上若 \((n,d)=(10,3)\) \(c=2\Rightarrow 2^3\equiv 8(mod\ 10)\)，會得到相同結果
  故重點在 \(ed \equiv  1 (mod\ \varphi(n))\)，詳情可看推導證明

私鑰解密證明

$$ \begin{align*} m^e &\equiv c(mod\ n)\\ m^e &= c+kn\\ c &= m^e-kn\\ \\ c^d &\equiv m(mod\ n)\\ (m^e-kn)^d &\equiv m(mod\ n)\\ m^{ed}+m^{e(d-1)}(-kn)+\cdots +(-kn)^d &\equiv m(mod\ n)\\ m^{ed} &\equiv m(mod\ n)\\ \because ed \equiv 1 (mod\ \varphi(n)) & \therefore ed=1+h\varphi(n)\\ m^{1+h\varphi(n)} &\equiv m(mod\ n)\\ \end{align*} $$

1. 若 \(m,n\) 互質
   根據歐拉定理 \(m^{\varphi(n)}\equiv 1(mod\ n)\)
   故 $$ \begin{align*} m^{1+h\varphi(n)} &=m\cdot (m^{\varphi(n)})^h \\ &=m\cdot (1+kn)^h \\ &=m\cdot (1^h+1^{h-1}kn+\cdots +(kn)^h) \\ m^{1+h\varphi(n)} &\equiv m(mod\ n)\\ \end{align*} $$ 可得證
   
2. 若 \(m,n\) 不互質，且 \(n=pq\)，\(p,q\) 又是質數，故 \(m\) 有兩種可能 \(kp\) 或 \(kq\)
   當 \(m=kp\) 則 \(k\) 與 \(q\) 絕對互質
   因 \(q\) 為質數，若不互質，唯一可能性就是 \(k=q\)
   那代表 \(m=pq=n\)，但 \(m<n\) 所以這不可能發生
   故根據歐拉定理
   
   $$ \begin{align*} (kp)^{q-1}&\equiv 1(mod\ q)\\ \left [(kp)^{q-1} \right ]^{h(p-1)}&\equiv 1(mod\ q)\\ kp \cdot \left [(kp)^{q-1} \right ]^{h(p-1)}&\equiv kp(mod\ q)\\ kp \cdot (kp)^{h(q-1)(p-1)}&\equiv kp(mod\ q)\\ (kp)^{1+h(q-1)(p-1)}&\equiv kp(mod\ q)\\ (kp)^{1+h\varphi(n)}&\equiv kp(mod\ q)\\ (kp)^{ed}&\equiv kp(mod\ q)\\ (kp)^{ed}&= kp + tq\\ \end{align*} $$
   因左式 \((kp)^{ed}\) 可以被 \(p\) 整除，故右式 \(kp + tq\) 也可以
   又因 \(p,q\) 互質，故 \(t\) 可被 \(p\) 整除
   令 \(t={t}'p\)
   
   $$ \begin{align*} (kp)^{ed}&= kp + tq\\ &= kp + {t}'pq\\ &=m + {t}'n\\ m^{ed} &\equiv m(mod\ n) \end{align*} $$
   反之 \(m=kq\) 亦然
   

可靠性

生成過程中，共有 \(p,q,n,\varphi(n),e,d\) 等數字
公開的則是公鑰的 \((n,e)\)，因私鑰為 \((n,d)\)，若 \(d\) 被洩漏等同私鑰洩漏
而該如何得知 \(d\) 呢？
因 \(ed=1+k\varphi(n)\)，所以只要知道 \(\varphi(n)\) 就可以得到 \(d\)
得到 \(\varphi(n)\) 有兩種方法

1. 直接求解
2. 利用 \(n=pq\) 做因數分解，得到 \(p,q\) 代入 \(\varphi(n)=(p-1)(q-1)\)

以上兩種方法目前皆無有效方法，唯有暴力破解，當 \(n\) 越大就表示越不可能破解

參考

公開金鑰密碼系統
公開金鑰密碼：能在網路上安全的傳送密碼，要感謝神奇的質數？ ——《用數學的語言看世界》
RSA加密演算法
RSA Key Generator
Online Certificate Decoder, decode
RSA算法原理（一）
RSA-Pycrypto
Go Package rsa
RSA 秘钥的 PEM 格式解析