前言
RSA算法是1978年\(R.Rivest,A.Shamir,L.Adleman\)三位科学家提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，大多用于架构非对称加密
密钥的产生：
- 选取两个保密的大素数\(p\)和\(q\)。
- 计算\(n=p \times q,\phi (n)=(p-1)(q-1)\)，其中\(\phi (n)\)是\(n\)的欧拉函数值
- 选取一个整数\(e\)，满足\(1<e<\phi (n)\) ,并且\(\gcd (\phi (n),e)=1\)
- 计算\(d\)，满足\(d \times e \equiv 1 \mod \phi (n)\)，即\(d\)是\(e\)在\(\mod \phi(n)\)下的乘法逆元，因\(e\)与\(\phi(n)\)互素，由模运算可知，他的乘法逆元一定存在
- 以\({d,n}\)为公开钥，\({d,n}\)为秘密钥
加密
- 首先将明文比特串分组，使得每个分组对应的十进制数小于\(n\)，即分组长度小于\(\log n\)，然后对每个明文分组\(m\)，作加密运算：
\(c\equiv m^{e}\mod n\)
解密
- 对密文分组的解密运算为：
\(m \equiv c^{d} \mod n\)
实现
判断素数
判断素数
int IsPrime(int n)
{
int temp=(int)sqrt(n);
for(int i=2;i<=temp;i++)
{
if(n%i==0)
return 0;//n不是素数的话返回0
}
return 1;//n是素数的话返回1
}
选取素数
两个素数p,q是手动输入的。
p,q应满足：p为素数，q为素数，p,q互不相等
计算n和n的欧拉函数
计算n和n的欧拉函数值
void N(int p,int qint &n,int &Euler_n)
{
n=p*q;
Euler_n=(p-1)*(q-1);
}
GCD
求两个数的最大公约数
int GreatestCommonDivisor(int a,int b)
{
int t;
if(a<b)
{
// 交换两个数，使大数放在a的位置上。
t=a;
a=b;
b=t;
}
while(b!=0)
{
// 利用辗转相除法，直到b为0为止。
t=a%b;
a=b;
b=t;
}
return a;
}
求e
选取e
void E(int Euler_n,int &e)
{
e=rand()%(Euler_n-1)+1; //e取值是1<e<Euler_n 即 [2,Euler_n]范围内的随机数
do // gcd(e,Euler_n)=1 ，e与Euler_n互素，最大公约数=1
{
e=rand()%(Euler_n-1)+1; //e取值是1<e<Euler_n 即 [2,Euler_n]范围内的随机数
}
while(GreatestCommonDivisor(Euler_n,e)!=1);//当e与Euler_n最大公约数!=1时，循环不断地刷新e的值
}
求逆元d
求逆元d
void D(int e,int Euler_n ,int &d)
{
int Sign_of_Inverse_Element=0;//判断是否求出逆元的标志：Sign_of_Inverse_Element。当Sign_of_Inverse_Element=1，则求出了逆元
do
{
for(int i=1;i<Euler_n;i++)
{
if((i*e)%Euler_n==1)
{
Sign_of_Inverse_Element=1; //Sign_of_Inverse_Element=1时表面求出了逆元d
d=i;
}
}
}
while(Sign_of_Inverse_Element!=1);
}
对明文m的加密
对于明文m的加密
void E_m(int m,int e,int n,int &c)
{
int product=1;//product表示m自身不断相乘的积
for(int i=1;i<=e;i++)//用e来控制m的指数
{
product=(product*m)%n;
}//注意不要忘记%n
c=product;
}
对密文c的解密
对密文c的解密
void D_c(int c,int d,int n,int& After_m)
{
int product=1;//product表示c自身不断相乘的积
for(int i=1;i<=d;i++)//用d来控制c的指数
{
product=(product*c)%n;
}//注意不要忘记%n
After_m=product;
}
整体代码
整体代码
#include<iostream>
using namespace std;
#define Size 10//明文串大小
//判断素数
int IsPrime(int n)
{
int temp = (int)sqrt(n);
for (int i = 2; i <= temp; i++)
{
if (n % i == 0) return 0;//n不是素数的话返回0
}
return 1;//n是素数的话返回1
}
//选取两个素数
void InputPrime(int &p, int &q)
{
int P, Q;
cout << "请输入两个不相等的大素数: p,q" << endl;
cin >> P >> Q;
do
{
/*if(P == Q)
{
cout << "p,q不能相等，请重新输入两个大素数: p, q" << endl;
cin >> P >> Q;
}
if(IsPrime(P) != 1)
{
cout << P<<"不满足是素数，请重新输入大素数: p" << endl;
cin >> P;
}
if(IsPrime(Q) != 1)
{
cout << Q<< "不满足是素数，请重新输入大素数: q" << endl;
cin >> Q;
}
*/
/* do
{
cout << "p,q不能相等，请重新输入两个大素数: p, q" << endl;
cin >> P >> Q;
} while (P == Q);
do
{
cout << P << "不满足是素数，请重新输入大素数: p" << endl;
cin >> P;
} while (IsPrime(P) != 1);
do
{
cout << Q << "不满足是素数，请重新输入大素数: q" << endl;
cin >> Q;
} while (IsPrime(Q) != 1);
*/
while (IsPrime(Q) != 1)
{
cout << Q << "不满足是素数，请重新输入大素数: q" << endl;
cin >> Q;
}
while (IsPrime(P) != 1)
{
cout << P << "不满足是素数，请重新输入大素数: p" << endl;
cin >> P;
}
while(P==Q)
{
cout << "p,q不能相等，请重新输入两个大素数: p, q" << endl;
cin >> P >> Q;
}
} while (IsPrime(P) !=1||IsPrime(Q)!=1||Q==P);
p = P;
q = Q;
}
//计算n和n的欧拉函数值
void N(int p , int q, int &n,int &Euler_n)
{
n = p * q;
Euler_n = (p - 1) * (q - 1);
}
//求两个数的最大公约数
int GreatestCommonDivisor(int a, int b)
{
int t;
if (a < b)
{
// 交换两个数，使大数放在a的位置上。
t = a;
a = b;
b = t;
}
while (b != 0)
{
// 利用辗转相除法，直到b为0为止。
t = a % b;
a = b;
b = t;
}
return a;
}
//选取e
void E(int Euler_n,int &e)
{
e = rand() % (Euler_n - 1) + 1; //e取值是1<e<Euler_n 即 [2,Euler_n]范围内的随机数
do // gcd(e,Euler_n)=1 ，e与Euler_n互素，最大公约数=1
{
e = rand() % (Euler_n - 1) + 1; //e取值是1<e<Euler_n 即 [2,Euler_n]范围内的随机数
} while (GreatestCommonDivisor(Euler_n , e)!=1);//当e与Euler_n最大公约数!=1时，循环不断地刷新e的值
}
//求逆元d
void D(int e,int Euler_n ,int &d)
{
int Sign_of_Inverse_Element=0;//判断是否求出逆元的标志：Sign_of_Inverse_Element。当Sign_of_Inverse_Element=1，则求出了逆元
do
{
for (int i = 1; i <Euler_n; i++)
{
if ((i * e) % Euler_n == 1)
{
Sign_of_Inverse_Element = 1; //Sign_of_Inverse_Element=1时表面求出了逆元d
d = i;
}
}
} while (Sign_of_Inverse_Element !=1);
}
//对于明文m的加密 (这里认为m是由输入字符转成的二进制的十进制值)
void E_m(int m, int e,int n, int &c )
{
int product = 1;//product表示m自身不断相乘的积
for (int i = 1; i <=e; ++i)//用e来控制m的指数
{ product = (product *m)%n; }//注意不要忘记%n
c = product;
}
//对密文c的解密
void D_c(int c, int d, int n, int& After_m)
{
int product = 1;//product表示c自身不断相乘的积
for (int i = 1; i <= d; ++i)//用d来控制c的指数
{product = (product * c) %n;}//注意不要忘记%n
After_m= product;
}
//Bob想要收到别人的消息就要先制作公钥和私钥
void Bob_Make_PublicKey_And_PrivateKey(int &p , int &q, int& n, int& e,int& d)
{
int p1, q1, n1, Euler_n1, e1, d1;
//Bob制作公钥的过程
InputPrime(p1, q1);//选取两个素数
p = p1;
q = q1;
N(p1, q1, n1, Euler_n1); //计算n和 n的欧拉函数值Euler_n
n = n1;
E(Euler_n1, e1);//选取e
e = e1;
cout << "Bob (广播发送): “想给我发消息用这个公钥：{ e=" << e1 << ", n=" << n1 << "} ”" << endl;
//Bob制作公钥的过程
D(e1, Euler_n1, d1);//求逆元d
d = d1;
cout << "Bob (自言自语): “只有我自己知道这个私钥：{ d=" << d1 << ", n=" << n1 << "} ”" << endl<<endl;
}
//Alice发送密文给Bob
void Alice_Send_Ciphertext_to_Bob(int n, int e, int C[])//全局变量C[]
{
int M2[Size], C2[Size];
//Alice对明文M[]加密
cout << "Alice(自言自语)：“我要发送给Bob的明文：";
for (int i = 0; i < Size; i++)
{
M2[i] = rand() % n;//为了简要输入输出，这里就随机生成明文串的值
E_m(M2[i], e, n, C2[i]);//加密
C[i] = C2[i];
cout << M2[i] << " ";
if (i == Size - 1) { cout <<" ”"<< endl; }
}
//Alice发送密文给Bob
cout << "Alice(信道发送)：“我要发送给Bob的密文：";
for (int i = 0; i < Size; i++)
{
cout << C[i] << " ";
if (i == Size - 1) { cout << " ”" << endl<<endl; }
}
}
//Bob解开密文
void Bob_Decode_Ciphertext_From_Alice( int n, int d,int C[])全局变量C[]
{
int After_M3[Size];
//Bob收到的密文
cout << "Bob (信道接收): “Alice给我的密文： ";
for (int i = 0; i < Size; i++)
{
cout << C[i] << " ";
if (i == Size - 1) { cout << " ”" << endl; }
}
//Bob解密后得到的明文
cout << "Bob (自言自语): “解 密后的明文为： ";
for (int i = 0; i < Size; i++)
{
D_c(C[i], d, n, After_M3[i]);
cout << After_M3[i] << " ";
if (i == Size - 1) { cout <<" ”"<< endl; }
}
}
int main()
{
int p, q ;
int d;
//攻击者只知道下面这些全局变量。这些全局变量是在广播或者信道中传播的
int n, e;//公钥
int C[Size];//密文串
Bob_Make_PublicKey_And_PrivateKey(p, q, n, e, d);
Alice_Send_Ciphertext_to_Bob(n, e, C);
Bob_Decode_Ciphertext_From_Alice(n, d, C);
}
//这个main（）函数也能运行，是一开始的版本，繁琐且不能体现Alice和Bob的交流过程
/*
int main()
{
int p, q,n, Euler_n,e,d;
int M[Size];//明文串
int C[Size];//密文串
int After_M[Size]; //解密后的明文
InputPrime( p, q);//选取两个素数
N(p, q, n, Euler_n); //计算n和 n的欧拉函数值->Euler_n
E(Euler_n, e);//选取e
D(e, Euler_n, d);//求逆元d
//生成明文并加密
cout << "明文为：";
for (int i = 0; i < Size; i++)
{
M[i] = rand() % n;//为了简要输入输出，这里就随机生成明文串的值
E_m(M[i], e, n, C[i]);//加密
cout <<M[i]<< " ";
if (i == Size-1) { cout << endl; }
}
// 输出密文
cout << "密文为：";
for (int i = 0; i < Size; i++)
{
cout << C[i] << " ";
if (i == Size - 1) { cout << endl; }
}
//解密密文并输出解密后的明文
cout << "解密后的明文为：";
for (int i = 0; i < Size; i++)
{
D_c(C[i], d, n, After_M[i]);
cout << After_M[i] << " ";
if (i == Size - 1) { cout << endl; }
}
}
*/