RSA 加密演算法是一種非對稱加密(公開金鑰加密)演算法。RSA 的演算法是基於歐拉函數(Euler’s totient function)與歐拉定理(Euler’s theorem)而來。
# 歐拉函數
歐拉函數 ϕ(n) 是 ≤n 的正整數中與 n 互質的個數。
我們把 n 做質因數分解可以得到:
n=p1k1⋅p2k2…prkr
就可以計算歐拉函數 ϕ(n)
ϕ(n)=n∏p∣n(1−p1)
# 範例
- ϕ(30)
- 30=2⋅3⋅5
- (1,7,11,13,17,19,23,29)
- ϕ(30)=30⋅21⋅32⋅54=8
- ϕ(36)
- 36=22⋅32
- (1,5,7,11,13,15,17,19,23,25,29,31)
- ϕ(36)=36⋅21⋅32=12
# 質數特性
對於兩個質數 p 和 q,且 p=q(非常重要!)、合數 n=p×q
- ϕ(p)=p−1, ϕ(q)=q−1
- ϕ(n)=ϕ(pq)=ϕ(p)⋅ϕ(q)=(p−1)⋅(q−1)
- 例:ϕ(10)=ϕ(2)⋅ϕ(5)=(2−1)⋅(5−1)=4
# 歐拉定理
對任意互質的兩數 a 和 n 有以下性質
aϕ(n)≡1(modn)
# RSA 演算法
- 選擇兩個大質數 p 和 q,p=q
- n=p×q
- ϕ(n)=(p−1)⋅(q−1)
- 選擇一個 e 使其與 ϕ(n) 互質且小於 ϕ(n),即 gcd(ϕ(n),e)=1,1<e<ϕ(n)
- 計算 d≡e−1(modϕ(n)), d<ϕ(n)
- 公鑰:{e, n}
- 私鑰:{d, n}
- 加密:
- 明文 M<n
- 密文 C=Me(modn)
- 解密
- 密文 C
- 明文 M=Cd(modn)
# 範例
範例為了方便計算,所以用很小的質數做示範,實際應用場景中會使用超大質數。
- 選擇兩個質數 p=17, q=11
- n=p⋅q=17×11=187
- ϕ(n)=(p−1)(q−1)=16×10=160
- 選擇 e 使其與 ϕ(n)=160 互質且小於 160,我們選擇 e=7
- 計算 d 使得 de≡1(modϕ(n)) 且 d<160。因為 23×7=161, 161mod160=1,故 d=23
- 公鑰:{7, 187}
- 私鑰:{23, 187}
若明文為 88,則
- 加密
- 明文:88<187
- 加密:887mod187=11
- 解密
- 密文:11
- 明文:1123mod187=88
# 快速模冪演算法
從剛剛的例子我們會發現要計算 887 與 1123,這是非常大的數字呢!如果要算出這個數字相當耗費資源。不過後面既然會需要 mod187,其實就不用真的乘開了,而這個問題在數學上稱之為模冪(modular exponentiation)運算。
若 x, y, n 皆為整數且 x, y≥0, n≥1,求 xymodn,可以透過下列演算法計算:
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;
}
我們會發現,887mod187 只需要 3 次迴圈就可以算完:
| x | y | result |
---|
輸入 | 88 | 7 | 187 |
1 | 77 | 3 | 88 |
2 | 132 | 1 | 44 |
3 | 33 | 0 | 11 |