信息系统安全绕不开的话题就是加密、认证、完整、权限和不可否认性，这也是安全空间的五大特性。而对于安全，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加密算法的讲解就全部结束了。