RSA算法的C++string实现(模幂算法和欧几里得算法的使用)后附思路
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了RSA算法的C++string实现(模幂算法和欧几里得算法的使用)后附思路，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8400字，纯文字阅读大概需要13分钟。
内容图文
void resetNumA(string numAStr); //使用string重置numB void resetNumB(string numBStr); //将数组转换为字符串，用于输出 string getNumString(int* num); //判断两个数字哪个大 int compare(string numAStr, string numBStr); //加法 string sum(string numAStr, string numBStr); //减法 string sub(string numAStr, string numBStr); //乘法 string mul(string numAStr, string numBStr); //除 string div(string numAStr, string numBStr); //取余 string mod(string numAStr, string numBStr); //模幂算法 string getMod(string m, string pow, string n); //求2的n次方函数 string mul_2(int i); //求m的n次方 string mul_m(string m, string n); #endif
#include<iostream>
#include"operation.h"
#include<string>
#include<vector>
using namespace std;
//结果支持的最大位数
const static int M = 2000;
int numA[M];
int numB[M];
//使用string重置numA
void resetNumA(string numAStr)
{
memset(numA, 0, M * sizeof(int));
//将字符串的每一位都转换成数字传入数组
for (int i = 0; i < numAStr.length(); i++)
{
numA[i] = numAStr[numAStr.length() - i - 1] - '0';
}
}
//使用string重置numB
void resetNumB(string numBStr)
{
memset(numB, 0, M * sizeof(int));
//将字符串的每一位都转换成数字传入数组
for (int i = 0; i < numBStr.length(); i++)
{
numB[i] = numBStr[numBStr.length() - i - 1] - '0';
}
}
//将数组转换为字符串，用于输出
string getNumString(int* num)
{
string numString;
bool isBegin = false;
for (int i = M - 1; i >= 0; i--)
{
if (num[i] != 0)
{
isBegin = true;
}
if (isBegin)
{
numString += num[i] + '0';
}
}
return numString;
}
//判断两个数字哪个大
int compare(string numAStr, string numBStr)
{
int i = 0;
int la = 0;
while (numAStr[i] == '0') {
la++;
i++;
}
i = 0;
int lb = 0;
while (numBStr[i] == '0') {
lb++;
i++;
}
string a(numAStr.substr(la, numAStr.length()));
string b(numBStr.substr(lb, numBStr.length()));
if (a.length() > b.length())
{
return 1;
}
else if (a.length() < b.length())
{
return -1;
}
else
{
for (int i = 0; i < a.length(); i++)
{
if (a[i]>b[i])
{
return 1;
}
if (a[i]<b[i])
{
return -1;
}
}
return 0;
}
}
//加法
string sum(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr);
for (int i = 0; i < M; i++)
{
//结果保存在numA中
numA[i] += numB[i];
//数字大于9则进位
if (numA[i]>9)
{
numA[i] -= 10;
numA[i + 1]++;
}
}
return getNumString(numA);
}
//减法
string sub(string numAStr, string numBStr)
{
bool isNegative = false;
//如果numA比numB小
//则结果为负数
//调换位置进行计算
if (compare(numAStr, numBStr) == -1)
{
isNegative = true;
string temp = numAStr;
numAStr = numBStr;
numBStr = temp;
}
else if (compare(numAStr, numBStr) == 0)
{
return "0";
}
resetNumA(numAStr);
resetNumB(numBStr);
for (int i = 0; i < M; i++)
{
//减数小于被减数就借位
if (numA[i]<numB[i])
{
numA[i] = numA[i] + 10 - numB[i];
numA[i + 1]--;
}
else
{
numA[i] -= numB[i];
}
}
if (isNegative)
{
return "-" + getNumString(numA);
}
else
{
return getNumString(numA);
}
}
//乘法
string mul(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr);
vector<string> nums;
for (int i = 0; i < numBStr.length(); i++)
{
//初始化一个临时数据来保存被乘数与乘数的某一位相乘的结果
int temp[M];
memset(temp, 0, M * sizeof(int));
for (int j = i; j < numAStr.length() + i; j++)
{
temp[j] += numA[j - i] * numB[i] % 10;
temp[j + 1] = numA[j - i] * numB[i] / 10;
//如果大于9，那么就做进位处理
if (temp[j]>9)
{
temp[j] -= 10;
temp[j + 1]++;
}
}
nums.push_back(getNumString(temp));
}
//每位相乘的结果再用加法加起来
string result = nums[0];
for (int i = 1; i < nums.size(); i++)
{
result = sum(result, nums[i]);
}
return result;
}
//除,结果精确到个位
string div(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr);
string result;
string left;
if (compare(numAStr, numBStr) == -1)
{
return "0";
}
//标记第一个不为0的位数的出现
bool flag = false;
for (int i = 0; i < numAStr.length(); i++)
{
left += numAStr[i];
//余数比除数大
if (compare(left, numBStr) == 1)
{
flag = true;
int count = 1;
string temp = numBStr;
while (true)
{
//每循环一次加上一个余数
temp = sum(temp, numBStr);
//余数仍然大于除数，继续累加
if (compare(left, temp) == 1)
{
count++;
}
//余数小于除数
//可以计算结果
else if (compare(left, temp) == -1)
{
result += count + '0';
left = sub(left, sub(temp, numBStr));
break;
}
//此时余数刚好是除数的倍数
else if (compare(left, temp) == 0)
{
count++;
result += count + '0';
left = "";
break;
}
}
}
//刚好除尽
else if (compare(left, numBStr) == 0)
{
flag = true;
result += "1";
left = "";
}
//余数比除数小，跳到下一位
else if (flag)
{
result += "0";
}
}
return result;
}
//取模
string mod(string numAStr, string numBStr)
{
string result = "0";
if (compare(numAStr, numBStr) == -1)
{
return numAStr;
}
else if (compare(numAStr, numBStr) == 0) {
return result;
}
else {
string d = div(numAStr, numBStr);
string x = mul(numBStr, d);
result = sub(numAStr, x);
return result;
}
}
//加密解密模幂算法
string getMod(string m, string pow, string n)
{
string temp;
while (compare(pow,"1") == 1) {
if(mod(pow,"2")=="1")
temp = temp + "1";
else
temp = temp + "0";
pow = div(pow,"2");
}
temp = temp + "1";
int length = temp.length();
string T[M];
string M = "1";
T[0] = mod(m, n);
for (int i = 1; i < length; i++) {
T[i] = mod(mul(T[i-1],T[i-1]),n);
}
for (int i = 0; i < length; i++) {
if (temp[i] == '1') {
M = mul(M, T[i]);
}
}
string result = mod(M, n);
return result;
}
//求2的n次方函数
string mul_2(int i) {
string result = "2";
for (int j = 1; j < i; j++) {
result = mul(result, "2");
}
if (i == 0)
return "1";
else
return result;
}
//求m的t次方函数
string mul_m(string m,string t) {
string result = m;
string j;
for ( j = "1"; compare(j, t) == -1; j = sum(j, "1")) {
result = mul(result, m);
}
return result;
}
#include<iostream>
#include"operation.h"
using namespace std;
int main() {
string char_number_p;
string char_number_q;
string temp[3000][4];
//p=17,q=11
//p=17,q=19
//p=41,q=43
//67,71
//797 809
//49993 49999
//116747 110221
//1000017077
//141008192341187
char_number_p="100010001707701";
char_number_q="141008192341187";
string n = mul(char_number_p, char_number_q);
string tmp1 = "1";
string On = mul(sub(char_number_p, tmp1),sub(char_number_q, tmp1));
string e = "65537";
//拓展欧几里得算法
temp[0][0] = e;
temp[0][1] = "";
temp[0][2] = On;
temp[0][3] = "";
int i = 1;
do {
temp[i][0] = temp[i - 1][0];
temp[i][1] = "";
temp[i][2] = temp[i - 1][2];
temp[i][3] = "";
if (compare(temp[i][0], temp[i][2]) == 1) {
temp[i][0] = mod(temp[i][0], temp[i][2]);
}
else {
temp[i][2] = mod(temp[i][2], temp[i][0]);
}
i++;
} while (compare(temp[i - 1][0], "1") == 1);
int value = i - 1;
temp[value][1] = "1";
value--;
while (value >= 0) {
if (temp[value + 1][1] != "")
temp[value][3] = div(sub(mul(temp[value][0], temp[value + 1][1]), "1"), temp[value][2]);
else if (temp[value + 1][3] != "")
temp[value][1] = div(sum(mul(temp[value][2], temp[value + 1][3]), "1"), temp[value][0]);
value--;
}
string d = temp[0][1];
cout << "e:" << e << endl;
cout << "p*q:" << n << endl;
cout << "O(n):" << On << endl;
cout << "d:" << d << endl;
cout << "密钥{ " << e << " , " << n << " }" << endl;
cout << "公钥{ " << d << " , " << char_number_p <<" , "<< char_number_q << " }" << endl;
string miwen;
cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
cout << "密文:" << miwen << endl;
string C1 = getMod(miwen, e, n);
cout << "加密后的明文:" << C1 << endl;
string M1 = getMod(C1, d, n);
cout << "解密后的密文:" << M1 << endl;
cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
string C2 = getMod(miwen, e, n);
cout << "加密后的明文:" << C2 << endl;
string M2 = getMod(C2, d, n);
cout << "解密后的密文:" << M2 << endl;
cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
string C3 = getMod(miwen, e, n);
cout << "加密后的明文:" << C3 << endl;
string M3 = getMod(C3, d, n);
cout << "解密后的密文:" << M3 << endl;
system("pause");
return 0;
}
以上为测试实现的代码。
思路：先实现string类型的加减乘除的重写，以及用到的其他的操作函数，比较，取模，加解密函数，以及其他的m的n次方的操作。
然后在主函数里面嵌入欧几里得算法，调用求得d，之后就是简单的调用加解密函数
pq的值也是测试得到的
这是运行截图：
//拓展欧几里得算法
temp[0][0] = e;
temp[0][1] = "";
temp[0][2] = On;
temp[0][3] = "";
int i = 1;
do {
temp[i][0] = temp[i - 1][0];
temp[i][1] = "";
temp[i][2] = temp[i - 1][2];
temp[i][3] = "";
if (compare(temp[i][0], temp[i][2]) == 1) {
temp[i][0] = mod(temp[i][0], temp[i][2]);
}
else {
temp[i][2] = mod(temp[i][2], temp[i][0]);
}
i++;
} while (compare(temp[i - 1][0], "1") == 1);
int value = i - 1;
temp[value][1] = "1";
value--;
while (value >= 0) {
if (temp[value + 1][1] != "")
temp[value][3] = div(sub(mul(temp[value][0], temp[value + 1][1]), "1"), temp[value][2]);
else if (temp[value + 1][3] != "")
temp[value][1] = div(sum(mul(temp[value][2], temp[value + 1][3]), "1"), temp[value][0]);
value--;
}
string d = temp[0][1];
这部分拓展的欧几里得算法也可以单独使用，这里是用空间换取的时间效率。
内容总结
以上是互联网集市为您收集整理的RSA算法的C++string实现(模幂算法和欧几里得算法的使用)后附思路全部内容，希望文章能够帮你解决RSA算法的C++string实现(模幂算法和欧几里得算法的使用)后附思路所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】