1. 前言
非对称加密是现代密码学历史上最为伟大的发明，可以很好的解决对称加密需要的提前分发密钥问题。
加密密钥和解密密钥是不同的，通常被人们称为公钥和私钥。这样来做解决了密钥的不安全传输的问题，在不安全的通道上也是可以使用的。但是没有什么是十全十美的，其缺点也是十分明显的。一般比对称加解密算法慢两到三个数量级。
和对称加密算法的安全性保障不同，其基于安全可信的通道。非对称加密算法的安全性是基于数学问题来保障的，目前主要有基于大数质因子分解、离散对数、椭圆曲线等几种思路。
其中比较有代表性的算法是：RSA、ElGamal、椭圆曲线（ Elliptic Curve Crytosystems，ECC）系列算法。
RSA算法是经典的公钥算法，利用了对大数进行质因子分解困难的特性。
Diffie-Hellman 密钥交换：基于离散对数无法快速求解，可以在不安全的通道上，双方协商一个公共密钥。
ElGamal由 Taher ElGamal 设计，利用了模运算下求离散对数困难的特性。被应用在PGP 等安全工具中。
椭圆曲线算法（ Elliptic curve cryptography，ECC）：基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。ECC系列算法一般认为具备较高的安全性，但是正如我们所知道的那样，安全性越高的算法加解密过程往往比较耗时。
非对称加密由于速度较慢，一般适用于签名或者密钥协商，不适合用在大量数据的加解密。
其实，非对称加密采用了单向陷门函数的原理，其中，RSA采用了大数分解困难的问题，即已知n，很难分解为正确的素数p和q，但是已知p和q，可以很快的求出n。
另外一种单向陷门函数是幂模，其应用比如DH密钥交换。
其中，截图来自我们老师上课的PPT。
2. 数学基础
| 因子：整数a,b,如果存在m，使a=mb，称为b整除a，记为b | a，称b是a的因子。 |
最大公因子：所有同时整除a和b的整数中，最大的那个，称为a和b的最大公因子，记为(a,b)。
互素：最大公约数等于1。
模运算： 如果 a(mod n) =b (mod n)，则称a与b模n同余，记为a≡ bmodn。 同余的性质如下： ① 若n|(a-b)， 则a≡b mod n。 ② (a mod n)≡(b mod n)， 则a≡b mod n。（同上） ③ a≡b mod n,则b≡a mod n。（交换） ④ a≡b mod n,b≡c mod n,则a≡c mod n。（传递性）
2.1 欧几里得算法
采用递归的思想。
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
扩展欧几里得算法
欧几里得算法还有一种高级用法，即在求得和的最大公因子的公式，求出两个系数k1和k2，使得k1a+k2b=(a,b)
只需在欧几里得算法的基础上扩展一下，这就是扩展欧几里得算法。
def egcd(a, b):
if b == 0:
return a, 1, 0
gcd, k1, k2 = egcd(b, a % b)
return gcd, k2, k1 - a / b * k2
乘法逆元
当(a,b)=1时，即a,b互素时，有时候我们很希望求得一个数k,0<=k<b，使ka mod b=1，这样的数我们称为a的乘法逆元， 起始这看起来就像是在0到b-1这些整数中找到 的倒数一样。那怎么找到这样的数呢?
扩展欧几里得算法可以帮我们解决这个问题。
由于(a,b)=1，根据扩展欧几里得算法，可求得两个系数k1和k2，使得k1a+k2b=(a,b)=1，所以有 k1a=-k2b+1，所以k1amodb=1，所以(k1modb)amodb=1，而0<=(k1modb)<b，所以k1modb就是我们想要的那个乘法逆元。
定理：
任何整数模n后得到{0,1,…,n-1}中的数，把这个集合记为Zn:={0,1,…,n-1}。
定理 4-1 当(a,n)=1时，存在a的乘法逆元b∈Zn* ，满足ab≡ 1(mod n)。 证明：由于(a,n)=1，所以存在整数b,c满足ba+cn=1，等式两边同时模n即可。
费马定理和欧拉定理： 费马定理(Fermat)： 定理4-2 若p是素数，a是整数且(a, p)=1（a,p互素），则
证明：由于(a, p)=1，所以{amodp, 2amodp, …,(p-1)amodp}={1,2,…,p-1} 因此， a×2a×…×(p-1)a modp=1×2×…×p-1modp 于是， (p-1)!ap-1≡ (p-1)!modp 两边同乘以(p-1)!模p的逆即可得到 ap-1≡1modp。 Fermat定理也可以写成如下形式： 若p是素数， a是整数且(a, p)=1，则ap≡amodp
## 2.2 欧拉函数
对任意一个正整数 n，在1 到 n的这 n个整数里，显然有些和 n是互素的，而有些和 n是不互素的，那些和 n互素的整数的数量就是 n的欧拉函数，记作φ(n)。那么 φ(n)该怎么计算呢？
我们都知道任意整数n都可以表示成它的所有素因子的乘积：
所以所有那些和 n不互素的数，一定和n 有其中某个素因子作为公共因子。
所以我们只要从1到 n中的所有整数中，是p1,p2…ps 的倍数的依次剔除，剩下的就是与n 互素的数。
例如， p1的倍数一共有多少个呢，由于p1的倍数在1到 n中是均匀分布的，所以占据的比例是1/p1 ，剔除p1的倍数后，还剩下n(1-1/p1)个；在剩下的数中，由于p2的倍数在1到n中也是均匀分布的，所以占据的比例是1/p2，所以再剔除p2的倍数后，剩下n(1-1/p1)(1-1/p2)个。以此类推，当把所有素因子的整数倍都剔除后，剩下的数共有n(1-1/p1)(1-1/p2)…(1-1/ps)个。即
由此可见，求欧拉函数的关键在于求出n的的所有素因子，即对n做素因子分解。
素因子分解可以用于加解密。
欧拉定理：
现在要进入最精彩的一个部分——欧拉定理了。欧拉定理是RSA所依赖的直接数学基础。我们先给出欧拉定理的结论，再予以证明。
φ(n)是n的欧拉函数。
当（a,n）=1 时，a^φ(n)≡1(modn)。也就是说，当 a和 n互素时，φ(n)个a相乘再模 n等于1。
我们先把在 1到 n之间，与n互素的那φ(n)个数都列出来，将它们相乘，然后模n，用符号表示如下：
| P=x1,x2…xφ(n) mod n,考虑其中任一个 xi，由于它和n互素，而a也和n互素，所以 axi也和 n互素，所以axi mod n 也和n互素。考虑任何两个xi,xj，一定有axi mod n 不等于 axj mod n 。因为若axi mod n 等于 axj mod n ，则 n | a(xi-xj)，由于a和 n互素，所以n | (xi-xj)，所以xi≡xj(modn)，由于 xi和 xj各不相同，所以xi≡xj(modn)不可能。 |
也就是说，下列这些元素都与n互素，且两两各不相等。
ax1mod n,x2mod n…xφ(n) mod n.
所以这些元素和x1,x2…xφ(n)是同一拨。
所以如果将这些元素相乘，应当和 P，即
由于x1,x2…xφ(n)通通与n互素，等式两边可以约去，从而得到a^φ(n)≡1(modn)
欧拉定理推论
a^kφ(n)≡1(modn),也即a^(kφ(n)+1)≡a(modn)
这个结论就有意思了， a经过若干次幂再模n后又等于a，如果我们能把这个操作拆成两步，第一步不就是相当于加密，第二步不就相当于是解密了吗？
那怎么拆呢？如果我们能找到两个数e和d，使得ed=kφ(n)+1不就可以得到:
a^ed mod n=(a^e mod n)^d mod n
这就相当于做 e次幂模 n是加密，做 d次幂模 n是解密。
哇哦！如果e 和 d不相等，这不就是一种非对称密码吗，加密和解密使用不同的密钥。
可是，怎样找到这样的 e和d 呢？
我们希望找到的 e和 d满足ed=kφ(n)+1其实就是满足:ed mod φ(n)=1
这不就是说e和d互为乘法逆元吗！
因此，我们只需要先找一个 e，使得 e和φ(n)互素，即(e,φ(n))=1，然后再用扩展欧几里得算法求出d不就行啦！
等等，还差一点，还记得我们一开始介绍公钥密码时讲过，公钥密码除了机密和解密的密钥不同之外，还要求除了私钥的拥有者之外的其他人,无法由公钥求出私钥。那怎样才能让已知公钥不能求出私钥呢？
无论是由d求 e或者由e求d，其关键都在于等式ed mod φ(n)=1,如果私钥的拥有者能计算出φ(n) ，而其他人不能求出 φ(n)，不就行了吗？
那怎么才能做到这一点呢？还记得我们在介绍欧拉函数时所讲的那个特殊情况了吗？n 等于两个大素数的乘积，那么知道这两个大素数p,q 的人很容易求得欧拉函数，而仅知道n，而不知道那两个素因子 的人就很难求得欧拉函数！
2.3 平方剩余
n是一个正整数， a是一个非零整数， 如果方程 x^2≡amodn有解，则称a是模n的平方剩余，否则称为非平方剩余。 例4-20：x^2≡1mod7有解， x=1, x=6； x^2≡2mod7有解， x=3, x=4； x^2≡3mod7无解； x^2≡4mod7有解， x=2, x=5； x^2≡5mod7无解； x^2≡6mod7无解；
2.4 中国剩余定理CRT
2.5 离散对数
根据欧拉定理：如果(a, n)=1，则a^φ(n)≡1 mod n。
更一般的形式：如果(a, n)=1，则至少存在一个整 数m(比如m=φ(n)使得下式成立
a^m ≡ 1 mod n,称满足上述等式最小正整数m为a模n的阶，记为ordn(a) 。
设p为素数，若存在一个正整数α，使得α、α2、…、αp-1关于模p互不同余，则称α为模p的一个原根。于是有如下运算：
α的幂乘运算：y=αx(mod p)，1≤x≤p-1
α的对数运算：x=logαy，1≤y≤p-1
只要p足够大，求解离散对数问题时相当复杂的，并没有比较通用的解法。所以离散对数问题具有较好的单向性。
2.6 幂模
正向计算容易，而反向计算难的一个函数被称为单向陷门函数。幂模正是一种单向陷门函数。
幂模：就是先做一次幂运算，再做一次模运算。g^x mod n = y。
模运算有以下特别好的性质：
（a mod n）* (b mod n) mod n= a*b mod n。也就是说，先模再乘和先乘再模，只要最后都模了同一个模数，结果都是一样的。
交换律：
单向性：
g^x mod n = y。
已知g和x很容易求出y，已知g和y求x困难。
3. DH密钥交换
由于幂模运算的单向性，离散对数和大整数素因子分解一样都是一种陷门函数，所以同样可以基于幂模运算设计一套公钥密码。
DH算法用于密钥协商，不能用于加密或解密。需要加密的话，可以使用协商出来的对称密钥进行加密。
基于幂模运算的公钥密码：
利用幂模运算的交换律和单向性设计一种密钥协商机制——DH密钥交换。
假设通信双方Alice和Bob需要使用对称密码进行加密通信，对称密码所使用的密钥我们通常称为会话秘钥，那么可以用一下的DH密钥交换过程在不安全的信道上实现会话密钥的安全协商。
第一步，双方协商公共参数g和n；
第二步，Alice和Bob分别在0到n-1之间随机生成xa,xb作为各自的私钥，这个私钥是要保密的；
第三步，Alice和Bob分别计算ya=g^xa mod n，yb=g^xb mod n作为各自的公钥；
第四步，Alice和Bob将各自的公钥发送给对方；
第五步，此时Alice收到了Bob发来的yb，Bob收到了Alice发来的ya，然后分别计算ka=yb^xa mod n,kb=ya^xb mod n，并分别使用ka和kb作为对称密码的密钥。
正确性：
由于幂模运算满足交换律，所以：
所以，他们协商出的会话密钥一定是相同的！并且，由于xa和xb都是随机生成的，所以还确保了会话密钥的随机性。
4. RSA密码体制
关于RSA的讲解请参考这里。RSA算法
5. 数字签名方案DSA
6. Rabin密码体制
Rabin利用合数模下求解平方根的困难性构造了一种安全的公钥体制。Rabin公钥体制已经被证明：对该体制的破译的难度等价于大整数分解。
Rabin体制是RSA的一种特例，RSA中选取的公开钥e满足1＜e＜φ(n)，且gcd(e, φ(n))=1，而Rabin体制则选择e=2。
下面我们来学习下Rabin体制密钥的产生：
-
密钥生成：随机选取两个大素数p,q，在模4下与3同余，即这两个素数的形式为4k+3，以模数n=pq为公钥。
-
加密：设m为待加密消息，计算密文c=m^2 mod n, 0<=m<n。
-
解密：
