RSA Public-key Cryptosystem

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} \]

Leave a Comment

Your email address will not be published. Required fields are marked *

13 − three =

Scroll to Top