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$ 有以下性質

# 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 次迴圈就可以算完：