非对称加密、解密算法RSA的C++实现
信息安全技术实验报告
———非对称加密、解密算法RSA的C++实现
计算机学院
2008级12班
学号：53081224
姓名：胡守峰
非对称加密、解密算法RSA的C++实现
【我的目的】根据课上老师所讲“非对称加密、解密算法RSA”的有关知识，
编写其的C++语言实现。
【我的加密思想】第一步，用户首先输入两个素数p和q，并求出
n = p*q，然后再求出n的欧拉函数值phi。
第二步，在[e，phi]中选出一个与phi互素的整数e，并根据e*d ≡1（mod phi），求出e的乘法逆元。至此我们已经得到了公开密钥{e，n}和秘密密钥{d，n}。
第三步，让用户输入要进行加密的小于n一组正整数（个数不超过MAXLENGTH=500），输入以-1为结束标志，实际个数存入size中，正整数以clear[MAXLENGTH]保存。
第四步，对第三步所得的明文clear[MAXLENGTH]进行加密。遍历clear[size]，对每一个整数用以下算法进行加密,并将加密后的密文保存在Ciphertext[MAXLENGTH]中。
注意：此处不能用m2[j] = clear[j] ^ e整数的幂，因为当e和clear[j]较大时，会发生溢出，至使出现无法预料的结果。
第五步，输出加密后的密文。
【我的解密思想】第一步，根据在以上算法中求出的解密密钥[d,phi],对加
密后的密文Ciphertext[MAXLENGTH]进行解密，结果保存在DecryptionText[MAXLENGTH]中，算法如下：
第二步，输出对加密前的明文和加密并解密后的密文进行比较，判断两个数组是否一致，从而得知算法是否正确。
【我的实验】
1、RSA加密、解密算法的C++实现(可以在VC6.0上运行)：
#include
#include
using namespace std;
#define MAXLENGTH 500 //明文最大长度，即所允许最大整数个数
int size = 0;//保存要进行加密的正整数的个数
int p, q; //两个大素数
int n, phi; //n = p * q，phi = (p-1) * (q-1) 是n的欧拉函数值
int e; //{e, n}为公开密钥
int d; //{d, n}为秘密密钥
int clear[MAXLENGTH], Ciphertext[MAXLENGTH];//分别用于存放加//密前的明//文和加密后的密文
int DecryptionText[MAXLENGTH];//存放解密后的明文
////////////////////////////////////////////////////////////
//以下为加密算法
void Encryption()
{//加密算法
cout << " 请输入两个较大的素数：" ;
cin >> p >> q ;
cout << " p = " << p << ", q = " << q << endl;
n = p * q;//求解n，
phi = (p - 1) * ( q - 1 );//求解n 的欧拉函数值
cout << " n = " << n << ", phi = " << phi << endl;
cout << " 请从[0，" << phi - 1 << "]中选择一个与" << phi << " 互素的数e：";
cin >> e;
float d0;
for( int i = 1; ; i++)
{///求解乘法逆元e * d ≡1 (mod phi)
d0 = (float)(phi*i+1) / e;
if( d0 - (int)d0 == 0 )
break;
}
d = (int)d0;
cout << endl;
cout << " e = " << e << ", d = " << d << endl;
cout << " 公开密钥Pk = {e,n} = {" << e << "," << n << "}" << endl;
cout << " 秘密密钥Sk = {d,n} = {" << d << "," << n << "}" << endl;
cout << endl;
cout << " 请输入要加密的小于" << n << " 正整数（以-1结束）：" << endl;
cout << " 加密前的明文为：";
for( i = 0; i < MAXLENGTH; i++)
Ciphertext[i] = 1;
int count;
for(int j = 0; j { cin >> clear[j]; if( clear[j] == -1 ) break; count = e; while(count > 0) {//对明文进行加密Ciphertext =（clear）^ e mod n Ciphertext[j] = (Ciphertext[j] * clear[j]) % n; //加密算法 count-- ; } } cout << " 密文为：" ; size = j;//实际密文长度 for(int k=0; k cout << Ciphertext[k] << " "; cout << endl ; } ////////////////////////////////////////////////////////////// //以下为解密算法 void Decryption() {//解密算法 for(int i = 0; i < MAXLENGTH; i++) DecryptionText[i] = 1; int count; for(int j = 0; j < size; j++) { count = d; while(count > 0) {//对密文进行解密DecryptionText =（Ciphertext）^ d (mod n) DecryptionText[j] = ((DecryptionText[j] * Ciphertext[j]) %n); count-- ; } } cout << " 解密后的明文为："; for( int k = 0; k < size; k ++) cout << DecryptionText[k] << " "; cout << endl ; cout << " 加密前的明文为："; for( k = 0; k < size; k++) cout << clear[k] << " "; cout << endl; } void main() { Encryption(); char c; cout << endl; cout << "是否要解密（Y or N）: "; cin >> c; if(c == 'y' || c == 'Y') Decryption(); else return ; } 2、运行结果： ① ② ③ 3、实验分析： ①输入两个大素数p和q时，没有进行判断所输入的是不是素数 ②对phi求解e的乘法逆元时，必须保证e和phi互素，在这里我们也没有进 行判断。 ③由于以上原因，当我们所用数据较大时，会出现错误，例如运行结果③。 ④当我们输入要进行加密的明文时，必须保证每个正整数小于n，我们没有做 防范措施，也会出现错误结果。 【参考资料】1、 算法描述——密钥的产生 ①选两个保密的大素数p 和q 。 ②计算n=p ×q ，φ(n)=(p-1)(q-1),其中φ(n)是n 的欧拉函数值。 ③选一整数e ，满足1 ⑤以{e,n}为公开钥,{d,n}为秘密钥。 算法描述——加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n ，即分组长度小于log 2n 。然后对每个明文分组m ，作加密运算： c ≡m e mo d n 算法描述——解密 对密文分组的解密运算为： m≡c d mod n 2、百度文库：https://www.sodocs.net/doc/127573665.html,/view/539299.htm A=B^e2 mod n；B=A^e1 mod n;