RSA 加密演算法是一種非對稱加密(公開金鑰加密)演算法。RSA 的演算法是基於歐拉函數(Euler's totient function)與歐拉定理(Euler's theorem)而來。

歐拉函數

歐拉函數 $\phi(n)$ 是 $\leq n$ 的正整數中與 $n$ 互質的個數

我們把 $n$ 做質因數分解可以得到:

$$n = p_1^{k_1} \cdot p_2^{k_2} \dots p_r^{k_r}$$

就可以計算歐拉函數 $\phi(n)$

$$\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})$$

範例

  • $\phi(30)$
    • $30 = 2 \cdot 3 \cdot 5$
    • $(1, 7, 11, 13, 17, 19, 23, 29)$
    • $\phi(30) = 30 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 8$
  • $\phi(36)$
    • $36 = 2^2 \cdot 3^2$
    • $(1, 5, 7, 11, 13, 15, 17, 19, 23, 25, 29, 31)$
    • $\phi(36) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

質數特性

對於兩個質數 $p$ 和 $q$,且 $p \ne q$(非常重要!)、合數 $n = p \times q$

  • $\phi(p) = p - 1, \space \phi(q) = q - 1$
  • $\phi(n) = \phi(pq) = \phi(p) \cdot \phi(q) = (p - 1) \cdot (q - 1)$
  • 例:$\phi(10) = \phi(2) \cdot \phi(5) = (2 - 1) \cdot (5 - 1) = 4$

歐拉定理

對任意互質的兩數 $a$ 和 $n$ 有以下性質

$$ a^{\phi(n)} \equiv 1 \pmod n $$

RSA 演算法

  1. 選擇兩個大質數 $p$ 和 $q$,$p \ne q$
  2. $n = p \times q$
  3. $\phi(n) = (p - 1) \cdot (q - 1)$
  4. 選擇一個 $e$ 使其與 $\phi(n)$ 互質且小於 $\phi(n)$,即 $gcd(\phi(n), e) = 1, 1 < e < \phi(n)$
  5. 計算 $d \equiv e^{-1} \pmod{\phi(n)}, \space d < \phi(n)$
    • 公鑰:$\{e, \space n\}$
    • 私鑰:$\{d, \space n\}$
  • 加密:
    • 明文 $M < n$
    • 密文 $C = M^e \pmod n$
  • 解密
    • 密文 $C$
    • 明文 $M = C^d \pmod n$

範例

範例為了方便計算,所以用很小的質數做示範,實際應用場景中會使用超大質數。

  1. 選擇兩個質數 $p = 17, \space q = 11$
  2. $n = p \cdot q = 17 \times 11 = 187$
  3. $\phi(n) = (p - 1)(q - 1) = 16 \times 10 = 160$
  4. 選擇 $e$ 使其與 $\phi(n) = 160$ 互質且小於 $160$,我們選擇 $e = 7$
  5. 計算 $d$ 使得 $de \equiv 1 \pmod{\phi(n)}$ 且 $d < 160$。因為 $23 \times 7 = 161, \space 161 \bmod 160 = 1$,故 $d = 23$
    • 公鑰:$\{7, \space 187\}$
    • 私鑰:$\{23, \space 187\}$

若明文為 $88$,則

  • 加密
    • 明文:$88 < 187$
    • 加密:$88^7 \bmod{187} = 11$
  • 解密
    • 密文:$11$
    • 明文:$11^{23} \bmod 187 = 88$

快速模冪演算法

從剛剛的例子我們會發現要計算 $88^7$ 與 $11^{23}$,這是非常大的數字呢!如果要算出這個數字相當耗費資源。不過後面既然會需要 $\bmod 187$,其實就不用真的乘開了,而這個問題在數學上稱之為模冪(modular exponentiation)運算。

若 $x, \space y, \space n$ 皆為整數且 $x, \space y \ge 0, \space n \ge 1$,求 $x^y \bmod n$,可以透過下列演算法計算:

int mod_exp(int x, int y, int n)
{
    x %= n;
    if (x == 0)
        return 0;

    int result = 1;
    while (y > 0) {
        // y % 2 == 1
        if (y & 1)
            result = (result * x) % n;

        y /= 2;
        x = (x * x) % n;
    }

    return result;
}

我們會發現,$88^7 \bmod 187$ 只需要 3 次迴圈就可以算完:

x y result
輸入 88 7 187
1 77 3 88
2 132 1 44
3 33 0 11