資訊系統安全繞不開的話題就是加密、認證、完整、權限和不可否認性，這也是安全空間的五大特性，而對于安全，CIA是最基本的要求，隨著時間的推移，我們的傳輸安全技術也在不停向前發展，從早期的古典加密，到機械加密，再到現在的電子加密，逐步發展，
我們今天網路上比較流行的加密、授權都是通過pki/ca認證，通過pmi授權，而pki的核心就是加密技術就是RSA-一種非對稱加密，
1977年，三位密碼學家發明這種加密演算法，RSA就是他們名字的首字母，沒有什么含義，
RSA加密演算法設計的數學定理比較多，雖然他是最簡單的非對稱加密，但是足夠大部分人研究一下的了，
1、歐拉函式：
任意一個正整數n，小于或等于n的正整數中與n互質的數的數目，
他有很多特性，我們只是簡單說幾個吧，不懂得自己百度吧，
如果p是質數，phi（p）= p-1
如果m,n互質，phi（mn）= phi(m)*phi(n)
通用公式：n = p1^r1*p2^r2*p3^r3...........pk^rk，其中pi為質數
phi(n) = n*(1-p1^-1)(1-p2^-1)................(1-pk^-1)
phi(8) = 8*(1-1/2) = 4
phi(10) = 10*(1-1/2)*(1-1/5) = 4
phi(1324) = phi(2^2*331) = 1324*(1-1/2)*(1-1/331) = 660
2、余數定理性質
（a*b）%n = （a%n）*（b%n）= （（a%n）*b）%n
（a^m)%n = (a%n)^m%n = (a%n)^m
3、歐拉定理
如果n是一個正整數，a是任意一個非0整數，且n和a互質，那么：
a^phi(n) = 1 (mod n)
因此，費馬小定理是歐拉定理的特例
a^(n-1) = 1 (mod n)
4、RSA加密程序
a、先選擇兩個較大的質數p、q，令n = p*q
b、令k = phi（n）= （p-1）*（q-1）
c、選取任意整數e，條件是1<e<phi(n)，且e與phi（n）互質，比存在模范元素d
d、求模反元素d，使得（d*e）%phi（n）= 1 （mod phi（n））
即、d*e = k*t + 1，其中t為某一整數，那么依據歐拉定理，沒錯，這里用的歐拉定理
e^phi(k) % k = (e * e^(phi(k)-1)) % k = 1 (mod k) = (e*d) % k
所以，一定存在模范元素d = e^(phi(k)-1)，但這個模反元素是通過2元一次不定方程求解的，也就是擴展歐幾里得定理，來求解，
e、得到d后，我們非對稱密鑰系統形成，公鑰（e, n）；私鑰 （d，n）
假設要加密的明文為C，并且C和n互質，這個條件至關重要，其實只要n足夠大就可以了，
X為加密后密文，則：
加密程序：X = （C^e) % n
解密程序：C = （X^d）% n
5、證明RSA的正確性
也就是 C = （（（C^e) % n ) ^ d ) %n
（（（C^e) % n ) ^ d ) %n
=（（C^e) ^ d ) %n
=（C^(e*d) ) %n
= (C^(kt+1))%n
=(C*C^(kt))%n
=C%n * (C^k%n)t
=C%n * 1%n
=C%n
=C
故，RSA演算法得到了證明，注意這里的C和n一定要互質，因為用到了歐拉定理，
6、擴展歐幾里得定理
這名字是不是看上去特別高大上，其實也是一個挺不好理解的定理，我們先看一下什么時歐幾里得定理，其實就是輾轉相除求余數，最后一個余數等于0時，被除數就是最大公約數，
擴展歐幾里得：
b<>0，gcd（a，b）= gcd（b，a%b）
而ax+by =c的解，變成求ax + by = gcd（a，b）的特解，前提是C時gcd（a，b）的倍數，
a mod b=a?(?a/b?×b)
這時ax1+by1 = bx2 +a%by2
= bx2+(a?(?a/b?×b))y2
， =ay2 + b(x2??a/b?×y2)
故，x1 = y2
y1 = x2??a/b?×y2
到此，我們得到了一組特解，也就可以求它的通解了，
7、舉一個簡單的例子：
取p、q分別為61、53，顯然這是兩個質數，n = p*q = 61*53 = 3233
令 k = phi（n）= （p-1）*（q-1）= 60*52 = 3120
取e = 17，這里只是一個例子，實際中不會這樣取值的，
（e*d ）% phi（n）= （e*d）% k = 1 (mod k)
即，e*d = kt +1
得到，17d = 3120t +1
整理一下：17d - 3120t =1，即a = 17，b = -3120，求d，t的通解或特解，
def exgcd(a, b):
if b == 0:
return a, 1, 0
else:
x, y, q = exgcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q
這樣，我們就生成了（17，3223）為公鑰，而（2753，3223）則為私鑰，
到此我們關于RSA加密演算法的講解就全部結束了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300966.html
標籤：其他
上一篇：iptables防火墻