RSA算法
- RSA
- 一、數學原理
- 二、實作代碼
-
- 1 生成素數
- 2 生成秘鑰
- 3 對資料進行加密、解密
- 總結
RSA
RSA是一種非對稱加密體制，由公鑰和私鑰組成，數學原理是實數域的模餘法。在使用私鑰對資料進行加密後，可用公鑰對資料進行解密。
在RSA算法中，設公鑰為（D, N），私鑰為（E, N），加密過程可以表示為 明 文 E m o d N = 密 文 明文^{E} \ mod\ N=密文 明文E mod N=密文
解密算法一緻，把E換成Ｄ， 密 文 Ｄ m o d N = 明 文 密文^{Ｄ} \ mod\ N=明文 密文Ｄ mod N=明文
當然，能這樣計算對N、E、D是有要求的。
RSA是目前公認的安全算法，對它進行破解需要進行大數的質數分解，目前除了窮舉法沒有發現其他方法能計算，而窮舉法在足夠大的大數面前計算是需要非常漫長的時間的，是以當RSA算法采用的N、E、D足夠大時，就認為是安全的。目前來說需要N達到1024bits。
一、數學原理
-
歐拉函數的性質：
若 n = q p ， p 和 q 是 兩 個 質 數 , 則 φ ( n ) = ( q − 1 ) ( p − 1 ) n = qp，p和q是兩個質數,\ 則{\varphi}(n) = (q-1)(p-1) n=qp，p和q是兩個質數, 則φ(n)=(q−1)(p−1)
-
歐拉定理：若a與n互質，即 g c d ( a , n ) = 1 , 則 a φ ( n ) ≡ 1 m o d n gcd(a,n)=1, 則a^{\varphi(n)}\ {\equiv}\ 1\mod\ n gcd(a,n)=1,則aφ(n) ≡ 1mod n
進一步，若n是質數， a n − 1 ≡ 1 m o d n a^{n-1}\ {\equiv}\ 1\mod n an−1 ≡ 1modn， a n ≡ a m o d n a^{n}\ {\equiv}\ a\mod n an ≡ amodn
- 費馬小定理：若n是質數，a與n互質，，則 a n − 1 ≡ 1 m o d n a^{n-1}\ {\equiv}\ 1 \mod \ n an−1 ≡ 1mod n，
- 逆元：如果 a b ≡ 1 m o d n , 則 a 和 b 互 為 逆 元 ab\ {\equiv}\ 1\mod\ n, 則a和b互為逆元 ab ≡ 1mod n,則a和b互為逆元
-
RSA加密的條件：
· n = p × q n = p{\times}q n=p×q
· L = φ ( n ) = ( p − 1 ) ( q − 1 ) L = {\varphi}(n) = (p-1)(q-1) L=φ(n)=(p−1)(q−1)
· 随機選取 1 < e < L ， 使 得 g c d ( e , L ) = 1 1<e<L，使得gcd(e,L)=1 1<e<L，使得gcd(e,L)=1
·計算 e d ≡ 1 m o d L ed\ {\equiv}\ 1\mod\ L ed ≡ 1mod L
·公鑰對 =（n, d），私鑰對 =（n, e）
繼續設明文 = M，密文 = C，現在來證明可以用上述方法加解密的條件。
M E m o d N = C , C D m o d N = M M^{E}\ mod\ N = C,\ C^{D}\mod\ N = M ME mod N=C, CDmod N=M
根據模法， C D − k N = M C^{D}\ -\ kN = M CD − kN=M，代回第一個式子，
( C D − k N ) E ≡ 1 m o d N (C^{D}\ -\ kN)^{E}\ {\equiv}\ 1\mod\ N (CD − kN)E ≡ 1mod N C D E ≡ C m o d N C^{DE}\ {\equiv}\ C\mod\ N CDE ≡ Cmod N由于 E × D ≡ 1 m o d φ ( N ) E\times D\equiv 1\mod\ \varphi(N) E×D≡1mod φ(N)，也即 E D − k φ ( N ) = 1 ED-k\varphi(N) = 1 ED−kφ(N)=1
若gcd(C, N) = 1，根據歐拉定理， C φ ( N ) ≡ 1 m o d N C^{{\varphi}(N)}\ {\equiv}\ 1\mod\ N Cφ(N) ≡ 1mod N C k φ ( N ) + 1 ≡ C m o d N C^{k{\varphi}(N)+1}\ {\equiv}\ C\mod\ N Ckφ(N)+1 ≡ Cmod N C E D ≡ C m o d N C^{ED}\ {\equiv}\ C \mod\ N CED ≡ Cmod N若C與N不互質，由于N是兩個質數的積，是以gcd(C,N)=q or gcd(C,N)=p。設 C = k 1 q o r C = k 2 p C= k_{1}q\ or \ C=k_{2}p C=k1q or C=k2p，假設C = kp，而且gcd(m,q)=1，由歐拉定理和歐拉函數的性質， ( k p ) q − 1 ≡ 1 m o d q (kp)^{q-1} \ {\equiv} \ 1 \mod \ q (kp)q−1 ≡ 1mod q ( ( k p ) q − 1 ) k 2 ( p − 1 ) ≡ ( k p ) q − 1 ≡ 1 m o d q ((kp)^{q-1})^{k_{2}(p-1)}\ {\equiv}\ (kp)^{q-1} \ {\equiv} \ 1 \mod \ q ((kp)q−1)k2(p−1) ≡ (kp)q−1 ≡ 1mod q ( k p ) k 2 φ ( n ) ≡ 1 m o d q (kp)^{k_{2}{\varphi}(n)} \ {\equiv} \ 1 \mod \ q (kp)k2φ(n) ≡ 1mod q C k 2 φ ( n ) − a q = 1 C^{k_{2}{\varphi}(n)}-aq = 1 Ck2φ(n)−aq=1兩邊同時乘上C, C k 2 φ ( n ) + 1 = a C q + C = a k p q + C = a k N + C = k 3 N + C C^{k_{2}{\varphi}(n)+1}=aCq+C=akpq+C=akN+C=k_{3}N+C Ck2φ(n)+1=aCq+C=akpq+C=akN+C=k3N+C也即 C E D ≡ C m o d N C^{ED}\ {\equiv}\ C\mod\ N CED ≡ Cmod N，原式得證。
-
素數檢驗（Miller-Rabbin算法）
涉及到兩個定理：
5.1 費馬小定理：參見3，但是費馬小定理的逆定理不一定成立
5.2 二次探測定理：如果 p是一個素數， 0 < x < p 0<x<p 0<x<p，則方程 x 2 ≡ 1 m o d p x^{2}\ {\equiv}\ 1 \mod p x2 ≡ 1modp 的解為 x = 1 x=1 x=1 或 x = p − 1 x=p-1 x=p−1
算法内容：
· 設一個數為x，分解為 2 s t = x − 1 2^{s}t\ =\ x-1 2st = x−1，t為x不斷除以2得到的最大奇數
· 随機取a， a = a t a=a^{t} a=at，對a進行s次平方（也即計算 b = a 2 m o d x , a = b b = a^{2}\mod x,a = b b=a2modx,a=b），如果其中有次平方的結果為b=1而且此時a不為1或x-1，則不滿足二次探測定理
· 如果 a x − 1 m o d x ≠ 1 a^{x-1}\mod x {\neq}1 ax−1modx=1，則不滿足費馬小定理
如果可以，a取小于x的足夠多的質數或者随機選取a進行多次檢測。Miller-Rabbin算法隻能保證x大機率是一個素數，不過這個機率已經足夠大了。
-
快速幂
計算 a x m o d n = ? a^x\mod n=? axmodn=?，當a和x很大的時候，中間結果超出存儲容量又或者數字太大計算複雜，此時需要快速計算這個指數模餘值，可以如下進行：
對x分解為二進制形式，則有 a x m o d n = a 2 b k + 2 b k − 1 + ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + 2 b 0 m o d n = ( ( a 2 b k m o d n ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ( a 2 b 0 m o d n ) ) m o d n a^{x}mod\ n= a^{2^{b_{k}}+2^{b_{k-1}}+······+2^{b_0}}mod\ n =((a^{2^{b_k}} mod\ n)······(a^{2^{b_0}} mod\ n))mod\ n axmod n=a2bk+2bk−1+⋅⋅⋅⋅⋅⋅+2b0mod n=((a2bkmod n)⋅⋅⋅⋅⋅⋅(a2b0mod n))mod n
二、實作代碼
重新看下RSA算法的流程，
· n = p × q n = p{\times}q n=p×q
· L = φ ( n ) = ( p − 1 ) ( q − 1 ) L = {\varphi}(n) = (p-1)(q-1) L=φ(n)=(p−1)(q−1)
· 随機選取 1 < e < L ， 使 得 g c d ( e , L ) = 1 1<e<L，使得gcd(e,L)=1 1<e<L，使得gcd(e,L)=1
·計算 e d ≡ 1 m o d L ed\ {\equiv}\ 1\mod\ L ed ≡ 1mod L
·公鑰對 =（n, d），私鑰對 =（n, e）
由于RSA的安全性取決于n的大小，是以生成的p和q越大越好，那麼需要
- 生成大素數p和q
- 計算L = (p-1)*(q-1)
- 随機選取與L互質的e，2<e<L
- 計算e對L的逆元d
- 銷毀p、q，儲存n,e,d
1 生成素數
用基礎算法列出1-1000的素數，從2到 x \sqrt x x
求x是非能被1和他自身外的其他數整除。
def createPrime():
ret = []
for i in range(1000):
for j in range(2,ceil(sqrt(i))+1):
if i % j == 0:
break
if j == ceil(sqrt(i)):
ret.append(i)
return ret
先實作快速幂算法，再用Miller-Rabbin算法生成一個大的素數，這個大有多大看需求。
# 1000以内的質數
prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
def quickPowerMod(a,x,n):
# 計算a**x % n
c = b = 1
binary = bin(x)[2:]
binary = reversed(binary)
for it in binary:
if it == '0':
# 結果不動，乘子指數加一
a = (a ** 2) % n
else:
# 結果乘上目前權重，乘子指數加一
b = (a * b) % n
a = (a ** 2) % n
return b
def MillerRabin(num):
# 偶數
if num & 1 == 0:
return False
# 将num分解為 (2**s)*t = num-1
s = 1
# 這時t必定是偶數，将其分解到為奇數
t = num - 1
while t & 1 == 0:
s += 1
t = t // 2
for it in prime_list:
if it >= num:
break
a = quickPowerMod(it,t,num)
# 二次探測定理
for i in range(s):
b = a * a % num
if b == 1 and a != 1 and a != num-1:
return False
a = b
if a != 1:
# (it**t) 同餘 1 mod num, 費馬小定理
return False
return True
def createBigPrime():
pMin = 10 ** 54
pMax = 10 ** 64
a = random.randint(pMin,pMax)
while not MillerRabin(a):
a = random.randint(pMin, pMax)
return a
2 生成秘鑰
接下來編寫函數生成公鑰私鑰對，求逆元的時候有幾種算法，由于明文和N關系未知，選取擴充歐幾裡得算法，又需要求最大公因子和最小公倍數的函數，這兩個很簡單，直接上代碼。
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
def lcm(a,b):
c = gcd(a, b)
return a * b // c
def inverseGCD(a,b):
# 遞推求擴充歐幾裡得算法
if b == 0:
return 1, 0
else:
k = a // b
x2, y2 = inverseGCD(b, a % b)
x1, y1 = y2, x2 - k * y2
# 注意x1可能為負，在外面再求一次模
return x1, y1
def createKeys():
q = createBigPrime()
p = createBigPrime()
n = q * p
# n的歐拉函數
L = (p - 1) * (q - 1)
e = random.randint(2,L)
while gcd(e,L) != 1:
e = random.randint(2,L)
# 計算e * d 同餘 1 mod L
# 擴充歐幾裡得算法求逆元
d, _ = inverseGCD(e,L)
d = d % L
#d = e**(L-2)
with open('e.txt', 'w') as f:
f.write(str(e))
with open('d.txt', 'w') as f:
f.write(str(d))
with open('n.txt', 'w') as f:
f.write(str(n))
return n, e, d
3 對資料進行加密、解密
有了私鑰對，加密隻是進行一個求快速幂的過程。
m = 8916534261681675
n,e,d = createKeys()
print('私鑰對：\n',n,e)
print('公鑰對：\n',n,d)
en = quickPowerMod(m,e,n)
print('原消息: ', m)
print('加密後：', en)
de = quickPowerMod(en,d,n)
print('解密後：', de)
看下結果
已經完成正确的加解密！
總結
RSA算法用到數論、離散數學的基礎，加密速度慢，而且每次加密過程中消息大小M不能大于N。但RSA算法是公認非常安全的算法。
如果想對大小超出N的消息加密，一般需要先用DES、SHA等對原消息計算成一定長度的摘要，再對摘要進行RSA加密。
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)