Then Notes 隨筆

RSA 加密演算法

cover

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

歐拉函數

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

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

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

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

ϕ(n)=npn(11p)\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})

範例

質數特性

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

歐拉定理

對任意互質的兩數 aann 有以下性質

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

RSA 演算法

  1. 選擇兩個大質數 ppqqpqp \ne q
  2. n=p×qn = p \times q
  3. ϕ(n)=(p1)(q1)\phi(n) = (p - 1) \cdot (q - 1)
  4. 選擇一個 ee 使其與 ϕ(n)\phi(n) 互質且小於 ϕ(n)\phi(n),即 gcd(ϕ(n),e)=1,1<e<ϕ(n)gcd(\phi(n), e) = 1, 1 < e < \phi(n)
  5. 計算 de1(modϕ(n)), d<ϕ(n)d \equiv e^{-1} \pmod{\phi(n)}, \space d < \phi(n)
    • 公鑰:{e, n}\{e, \space n\}
    • 私鑰:{d, n}\{d, \space n\}

範例

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

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

若明文為 8888,則

快速模冪演算法

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

x, y, nx, \space y, \space n 皆為整數且 x, y0, n1x, \space y \ge 0, \space n \ge 1,求 xymodnx^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;
}

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

xyresult
輸入887187
177388
2132144
333011