發佈：
更新：
瀏覽：
分類：RSA 公鑰密碼系統簡單筆記。
選擇鑰匙
- 找出兩個巨大的質數 p, q
- 計算數值 N = p * q
- 取另一個數字 e，使得 e 和 (p-1)(q-1) 互質
- 解出 e * d ≡ 1 (mod (p-1)(q-1)) 中的 d。計算 d 值可用歐幾里德演算法求出
- 公開 e, N 為公鑰，大家可共享 e 值，但是 N 必須是唯一的
- 以 d 則為私鑰
\begin{aligned}
& p \text{ and } q \text{ are primes} \\
& N = p * q \\
& \text{Find an integer } e \text{ where } e \in \mathbb{N}^+, \gcd(e, (p-1)(q-1)) = 1 \\
& \text{Calculate the answer } d \text{ where } e * d \equiv 1 \pmod {(p-1)(q-1)}
\end{aligned}
加解密
- 編碼：將訊息 M (< N) 加密的計算方法為使用公鑰 e 運算得到密文 C，意即所有人皆可加密後送給私鑰持有者：
\[
\begin{aligned}
C = M^e \bmod {N}
\end{aligned}
\]
- 解碼：密文 C 解密回訊息 M 的方法為使用私鑰 d 運算，意即只有私鑰持有者才能解密：
\[
\begin{aligned}
M = C^d \bmod {N}
\end{aligned}
\]
- 簽名：訊息 M (< N) 的簽名方法為使用私鑰 d 運算得到簽名 S，意即只有私鑰持有者才能簽名（同解碼）：
\[
\begin{aligned}
S = M^d \bmod {N}
\end{aligned}
\]
- 檢驗：簽名 S 檢驗方法為使用公鑰 e 運算去驗證訊息 M，意即所有人都可以用公鑰去驗證該簽名是否由私鑰持有者所簽：
\[
\begin{aligned}
M = S^e \bmod {N}
\end{aligned}
\]