前置技术
约定符号：
- （a, b) = c
代表a，b的最大公约数是c，如果（a, b) = 1,则说明a，b互质。
- a mod b = c
a除以b,余数是c
- a≡b (mod c)
a和b除以c后余数相同，即a-b可以被c整除
欧拉函数
具体描述
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
如:
计算8的欧拉函数，和8互质的有 1、3、5、7
φ(8) = 4
一些性质及证明
参数为质数
如果x是质数，则φ(x) = x - 1
证明：
x为质数时，从1到x-1自然都跟x互质
积性函数
如果x ，y互质，则有φ(xy) = φ(x)φ(y)
证明所需前置定理：
公式一：如果，x，y互质，则一定存在两个整数a,b使得ax + by = 1
证明：
因为x,y互质，所以最大公约数会是1，使用辗转相除法计算，便可以将其分解成若干个x和若干个y相加
**公式二: 如果y≡x(mod a）,(a,x) = 1,则（a,y）= 1
**
证明：
假设a,y的最大公约数大于1，假设为n，但因为a和x互质，因此再假设x = kn + d,假设a = ln,y = oa + x不难得出
y = oln + kn + d
可以看出z并不能被n整除，矛盾，因此a和y互质
中国剩余定理:
如果1≤x≤a,1≤y≤b，a，x互质，b，y互质，则一定存在唯一的1≤z≤ab，使其同时满足z≡x(mod a)和z≡y(mod b)
这是中国剩余定理的一小部分，也是证明积性只需用到的部分
证明：
首先由公式一可知，必然存在一个整数c，同时满足两个条件：
c = ka = jb + 1 (由公式一变形可得)
即：
c mod a = 0,c mod b = 1
同理，也构造一个整数d，使得：
d mod b = 0,d mod a = 1。
然后构造一个数
t = yc+xd:<br>
显然:
t mod a = yka + x(1+a) mod a = x mod a
即 :
t ≡ x (mod a)
同理可证
t ≡ y (mod b)
此时取z = t mod ab，这个z是小于ab的
这个时候有
z mod a = (t - kab) mod a = t mod a
同理对b也一样
因此同样也会满足
z≡x(mod a)和z≡y(mod b)
接下来证明唯一性：
假设存在z2也满足1≤z2≤ab,假设其比z小
则z-z2 = ka = jb,这个时候1<z2<ab
由于z - z2即可被a整除又可被b整除，a,b又互质，说明z - z2 = kab(k至少为1)，跟上一条得出的范围矛盾
因此，z是唯一的。
证明积性函数
假设有集合
S(n) = {1≤x≤n|(x,n) = 1} <nr>
代表n中所有与n互质的元素，显然S(n)的元素个数就是Φ(n)
设有集合S2为：
S2 ={(x,y),x ∈ S(a),y ∈ S(b) }代表S(a),S(b)中取值的排列组合，不难得出S2中的数量就是Φ(a)Φ(b)
对于所有满足1≤x≤ab,(ab,x) = 1 的x，我们可以得出（a,x）=（b,x）= 1,进一步得出（a,x mod a）=（b,x mod b）= 1。因此S(ab)中每个元素都可以按照x mod a,x mod b的规则映射到S2中。
根据刚才的中国剩余定理，对于S2里的每一个x,y,必然有一个1≤z≤ab,使得z≡x(mod a)和z≡y(mod b)，由公式二得出(a,z) = (b,z) = 1,因此（ab,z）= 1,因此S2的(x,y)集合也可以映射到S(ab)中。
因此，S2和S(ab)大小相同，也就是Φ(ab) = Φ(a)Φ(b)
欧拉定理
(m^φ(n)) mod n = 1 （m,n互质）
证明
这里直接贴百度百科的：
- 将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （总共有φ(n)个数）
- 构造这些数：
m1=m*x1;m2=m*x2;m3=m*x3……mφ(n)=m*xφ(n)
这些数有如下特性：
- 这些数中的任意两个都不模n同余，因为如果有mS≡mR (mod n) （这里假定mS更大），就有：
mS-mR=m(xS-xR)=qn
即n能整除m(xS-xR)。但是m与n互质，m与n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。
- 这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么
m*xi=pn+qr=r*k
m*xi与n不互质，而这是不可能的。(因为m*xi=pn+qr=r*k，说明m*xi含有因子r，又因为前面假设n含有因子r，所以m*xi和n含有公因子r，因此m*xi与n不互质)
那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n中与n互质的所有数，而余数又小于n.
上面两点可知，数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).
故得出：
m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
进一步得出
m^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)
为了方便：K{m^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{,[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么m[φ(n)]-1必须能被n整除，即
即m^[φ(n)]≡1 （mod n）
费马小定理
(m^(n-1)) mod n ≡ 1 （n为质数，m，n互质）
证明
当n为质数时 φ(n) = n - 1,代入欧拉定理便可得证
模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除，那么d就是e对于x的"模反元素"
即：
(ed-1) mod x = 0
证明
其实稍微变形就是ed+kx = 1,就是上面的公式一。
RSA加密
加解密流程
加密
m^e mod n = C ，e为公钥,n为两个大质数相乘，确保m,n互质
解密
C^d mod n = m ， d为私钥，d跟φ(n)互质
原理
展开得
m^(ed) mod n = m
从欧拉定理：
(m^φ(n)) mod n = 1
这个时候如果取一个与φ(n)互质的d，则一定可以找到模反元素e，使得
(ed-1) mod φ(n) = 0
变形可得
ed = kφ(n) + 1
回到欧拉定理的公式，等式两边分别k次方：
m^(kφ(n)) mod n = 1
两边乘以m:
m^(kφ(n)+1) mod n = m
这样，kφ(n)+1便可以替换成ed了：
m^(ed) mod n = m
加密解密，其实就是这个公式拆成两个步骤。
n,e虽然是公开的，但是要想求出d，根据模反定理：
ed = kφ(n) + 1
这个n是两个质数相乘，设n=p1 * p2,因此φ(n) = φ(p1) * φ(p2) = (p1 - 1) * (p2 - 1),最后演变成要求n的因式分解求出p1,p2，这个n通常很大，不容易算出
使用终端RSA加密
OpenSSL库可以实现加密
生成私钥
openssl genrsa -out private.pem 1024
private.pem是一个长度为1024bit的私钥
取出私钥中的公钥
openssl rsa -in private.pem -pubout -out public.pem
public.pem是公钥
使用公钥加密文件
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
其中message.txt是一段文本，输出的enc.txt是加密后的文本，也可以使用私钥加密
使用私钥解密文件
openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
输出的dec.txt是解密后的文本，也可以使用公钥加密
