原创：岐山凤鸣
引用需注明本站域名。
公钥密码学
对称密码的局限：
- 密钥管理困难：两两用户分别用一对密钥，需要\(n * (n - 1) / 2\)个密钥，复杂度是\(n^2\)
- 数字签名无法实现：无法实现抗抵赖
- 密钥必须经过安全的信道分配
公钥密码：
- 算法是非对称算法，密钥分为公钥和私钥
- 公钥可以公开
- 基于数学函数（单向陷阱门函数）而不是替代置换
应用：
- 加密/解密
- 数字签名
- 密码交换
公钥算法的条件：
- 产生一对密钥计算可行
- 已知公钥和明文，产生密文是计算可行的
- 接收方用私钥来解密密文是计算可行的
- 通过公钥判断私钥是计算不可行的
- 只知道公钥和密文是无法恢复明文的
单向陷阱门函数f：
- 已知x，求y=f(x)容易
- 给定y，计算y=f(x)的x是困难的
- 存在z，当z已知的时候，已知y，计算y=f(x)的x是容易的
寻找单向陷阱门函数是公钥密码体制应用的关键。也是那些经典算法的源头。
RSA算法
理论基础：两个大素数相乘容易，分解成两个大素数很难
换句话说：已知n = pq，求\(\phi(n)\)很难，其中\(\phi(n) = (p-1)(q-1)\)
获得密钥
待获得的密钥：公钥(n, e1), 私钥(n, e2)
计算过程：
首先人为约定n=pq, 计算\(\phi(n) = (p-1)(q-1)\)，然后随机选取一个不太小的数字e1
找到e2, 使得\((e1*e2)mod(\phi(n)) = 1\), 也就是e1模\(\phi(n)\)的乘法逆元
至此得到了e1和e2，即两个密钥，随机选取一个作为公钥，另一个作为私钥即可。
加密过程
明文M加密得到密文C：
\(C = M^{e_1}mod(n)\)
密文M解密得到明文M:
\(M = C^{e_2}mod(n)\)
例子
人为找到两个素数p=17, q=11, 计算n=187, \(\phi(n) = 16*10 = 160\), 随机选取e1=7, 模160的乘法逆元是23, 即e2=23
则公钥(187,7), 私钥(187,23)
加密明文M=88,计算密文：
\(C = M^7 mod(187) = 88^7 mod(187) = 11\)
解密密文C=11,计算明文;
\(M = C^23 mod(187) = 11^23 mod(187) = 88\)
解决。
ps：其中计算88^7 mod 187的过程是((88^4 mod 187) * (88^3 mod 187) mod 187)
为什么e不能选的太小
例如：e=3，这个e够小了，明文M，然后向三个实体发送，选取三个不同的公钥(e, n1), (e, n2), (e, n3), 得到三个密文：
\(C_1 = M^3mod(n_1)\)
\(C_2 = M^3mod(n_2)\)
\(c_3 = M^3mod(n_3)\)
然后攻击者得到了这三个C，要求得明文，可以进行下列运算：
\(X = C_1mod(n_1)\)
\(X = C_2mod(n_2)\)
\(X = C_3mod(n_3)\)
将上面三个式子代入下面三个式子，然后使用中国剩余定理，计算出来X=m^3, 那么计算出来X，就自然而然得到了明文M，安全性失败。
RSA的缺点
- 速度慢，比DES慢了至少100倍
- 产生密钥太麻烦
- 分组长度太大
代码(未使用字符串进行精度优化，只能支持特别小的数字)
#include <iostream>
#include <cmath>
using namespace std;
#define long long int
inline int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1; y=0; return a;
}
int ans=exgcd(b,a%b,x,y);
int tmp=x; x=y;
y=tmp-a/b*y;
return ans;
}
inline int niyuan(int a,int P){
int x=0,y=0;
int gcd=exgcd(a,P,x,y);
if(x>0){
for(int t=0;;t--){
if((x+P/gcd*t)<=0) return x;
else x=x+P/gcd*t;
}
}
else{
for(int t=0;;t++){
if((x+P/gcd*t)>0){
x=x+P/gcd*t;
return x;
}
}
}
}
int main(int argc, char *argv[])
{
int n;
int p, q, e1, e2;
cout<<"Please input the prime1 p:"<<endl;
cin>>p;
cout<<"Please input the prime2 q:"<<endl;
cin>>q;
n = p * q;
cout<<"Please input the e1"<<endl;
cin>>e1;
e2 = niyuan(e1, (p-1)*(q-1));
cout<<"e2 is : "<<e2<<endl;
cout<<"Please input the Message: "<<endl;
int m, c;
cin>>m;
c = (int)(pow(m, e1)) % n;
cout<<"Atfer encryption, C is: "<<c<<endl;
return 0;
}
Diffie-Hellman算法
作用：允许两个用户可以安全交换【一个秘密信息】，用于后续的通讯工程
安全性依赖：计算离散对数的难度
素数的原始根
假设原始根为a，则：
a mod p, a^2 mod p, …., a^(p - 1) mod p
是
1, 2, 3, …., p - 1的一个置换
加密过程
人为规定一个大素数P，一个大的整数g，g最好是P的原始根，P与g无需保密
A选取一个大的随机数x，计算\(X = g^x mod (P)\)
B选取一个大的随机数x2, 计算\(X_2 = g^{x_2} mod (P)\)
A把X给B，B把\(X_2\)给A
A计算K = \(X_2^Xmod(P)\), B计算K = \(X^X_2mod P\), 很明显两个K是相等的
最终得到了K，A和B都能知道这个相同的秘密值了，可以把这个数字用作密钥接下来去用
例子
人为令P=47，选取生成元3，即a=3
A生成随机数8， 计算\(X = 3^8 mod 47 = 28\)，传给B
B生成随机数10， 计算\(X_2 = 3^10 mod 47 = 17))，传给A
A计算\(K_A = 17^8 mod (47) = 4\)
B计算\(K_B = 28^10 mod (47) = 4\)
这个4就可以用来做会话密钥了
安全性
y mod p = g^x mod p
已知x，计算y很容易
已知y，计算x很难
中间人攻击
A选取x_0, 计算出来了X，发给B
X被我截获，我选取x_00，计算出来了X_改，发给B
B把我当成了A，接收到了X改，选取x_1，得到X_b，发给我
我再发给A，至此完成攻击
ps：我必须一直伪装，不然就会被发现 ps：我永远不知道真正的K，即\(a^{x_0*x_1}\)
防范中间人攻击
- 使用共享的对称密钥加密DH交换
- 使用公钥加密DH交换
- 使用私钥签名DH交换
代码(未进行字符串优化，精度很小，仅限于很小的数字)
#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, char *argv[])
{
int P, a;
cout<<"Please input P:"<<endl;
cin>>P;
cout<<"Please input a:"<<endl;
cin>>a;
int x, x1;
cout<<"Now you are Alice, please input x: "<<endl;
cin>>x;
cout<<"OK, X is = "<<((int)pow(a, x)%P)<<endl;
cout<<"Now you are Bob, please input x2:"<<endl;
cin>>x1;
cout<<"OK, X2 is = "<<((int)pow(a, x1)%P)<<endl;
cout<<"Now you are Alice, you get the message from B:"<<((int)pow(a, x1)%P)<<endl;
cout<<"So K is = "<<((int)pow(((int)pow(a, x1)%P), x)%P)<<endl;
cout<<"Now you are Bob, you get the message from A:"<<((int)pow(a, x)%P)<<endl;
cout<<"So K is = "<<((int)pow(((int)pow(a, x)%P), x1)%P)<<endl;
cout<<"Over"<<endl;
return 0;
}