上一篇博客已经简单的完成了RSA加密，建议看完上一篇博客再来查看本文章：
https://blog.csdn.net/Watery________1314/article/details/96719658
这次我们将对之前的简单加密进行优化，实现大数加密，还有一部分性能优化。
首先要添加外部依赖库boost库，具体添加库方法请见：
https://blog.csdn.net/Watery________1314/article/details/96981400
添加好boost库后我们就可以对之前的数据进行优化了，这里引入以下三个头文件：
#include
#include
#include
先将之前的数据类型long替换成int1024_t，其次对产生素数函数produce_prime()和生成dkey函数produce_dkey()分别进行优化。
1.产生素数函数produce_prime()
bm::int1024_t RSA::produce_prime()
{
//srand(time(nullptr));
bm::int1024_t prime = 0;
//mt19937:一种随机数产生器
boost::random::mt19937 gen(time(nullptr));
//指定随机数的范围 2 ~ (1<<128)
boost::random::uniform_int_distribution dist(2, bm::int1024_t(1) << 128);
while (1)
{
prime = dist(gen);
if (is_prime_bigInt(prime))
break;
}
return prime;
}
这里使用了boost库中的mt19937（一种随机数产生器）来产生一个随机数，这里的随机数范围发生了变化，我们这里让它最大可以到(1<<128)，这里的判断是否为素数也进行一个优化，如下代码：
bool RSA::is_prime_bigInt(const bm::int1024_t digit)
{
boost::random::mt11213b gen(time(nullptr));
if (miller_rabin_test(digit, 25, gen)) //素数测试算法miller_rabin_test（）
{
if (miller_rabin_test((digit - 1) / 2, 25, gen))
{
return true;
}
}
return false;
}
这里的判断是否是素数，并不是按照之前的那种从2开始一个个模运算来判断的方法，这里使用了素数测试算法Miller-Rabin，这个算法我看了一下，没有理解的很深刻，如果有需要可以去看看其他博客。
2.生成ekey函数produce_ekey()
bm::int1024_t RSA::produce_dkey(bm::int1024_t ekey, bm::int1024_t orla)
{
bm::int1024_t x, y;
exgcd(ekey, orla, x, y);
return (x % orla + orla) % orla;
}/*
扩展的欧几里得算法
x = y1;
y = x1 - [a/b]*y1
*/bm::int1024_t RSA::exgcd(bm::int1024_t ekey, bm::int1024_t orla,
bm::int1024_t &x, bm::int1024_t &y)
{
if (orla == 0)
{
x = 1;
y = 0;
return ekey;
}
bm::int1024_t ret = exgcd(orla, ekey % orla, x, y);
bm::int1024_t x1 = x, y1 = y;
x = y1;
y = x1 - (ekey / orla) * y1;
return ret;
}
这里就需要看一下扩展的欧几里得算法：
扩展的欧几里得算法：不仅要求出(a,b)的最大公约数gcd，也要求出其中的一组解(x,y), 满足等式ax + by = gcd。从上
面的算法可知当b=0时，gcd即可求出，所以可以在求出gcd的同时也求出(x,y)。
我们观察一下等式，ax + by = gcd， 当b = 0时， 等式变成了ax = gcd，此时我们返回a的值，a既是所求的最大公约
数gcd，故此时x = 1, y可以是任意值， 所以，简单的一组解即为(1, 0)。
现在再让我们回头看模的逆元的等式：ab%n = 1。 ab - 1为n的倍数， 即 ab + kn = 1, 这里放入加密算法中对应的即
为： ed + kφ(n) = 1, 其中e为加密密钥， d为解密密钥， e与φ(n)互质，他们的最大公约数即为1，所以这里的解密密
钥d和k就相当于等式的一组解，此解可以用扩展的欧几里得算法求解。
这里我们假设d = x, k = y, e = a, φ(n) = b, 则等式ed + kφ(n) = 1即变为ax + by = 1, 通过欧几里得递归算法，当b=0
时，可求得一组解(1,0)和最大公约数1。递归的时候，在获取最终结果之前，已经求出了下一个状态：b 和 a%b 的最大公约数，假设此时求得了一组解(x1,y1)，使得bx1 + (a % b)y1 = 1。
而这里 a % b = a - [a / b] * b， 其中[a/b]表示向下取整， 带入上述等式，即为：
bx1 + (a - [a / b] * b)y1 = 1，继续变形：
bx1 + ay1 - [a/b]*by1 = 1，继续变形：
ay1 + b(x1 - [a/b]y1) = 1
当我们去求解(x,y)使ax + by = 1，可以看到此解和bx1 + (a % b)y1 = 1的关系如下：
x = y1， y = x1 - [a/b]y1
即在递归的过程中最终的结果可以通过上次递归的结果推导出来，关系如上所示。算法最终求得一组解(x,y)和最大公
约数1。此时我们一般会找出最小的那个解对应的x，只需要x%b即可。如果x为一个解，则ax + by = 1, 则它的通解为x + k*b，使a(x + k * b) % b = 1，这里ax % b = 1, (k * b) % b = 0, 总体结果还是为1。所以a关于b的逆元x是一个关于b的同余数，所以一定存在一个最小的正整数，它是a关于b的逆元，而最小的肯定在(0,b)之间。
有时候我们得到的解x是一个负数，所以统一处理，可以直接进行操作： (x % b +b) % b。这里的b也就是程序中的orla，替换即可。
以上就是对之前程序的优化，下面将附上完整的代码：
１.RSA.h
#pragma once
#include
#include
#include
#include
#include
namespace bm = boost::multiprecision;
struct Key
{
bm::int1024_t pkey;
//公钥(ekey, pkey): (e,n)
bm::int1024_t ekey;
//私钥(dkey, pkey): (d, n)
bm::int1024_t dkey;
};
class RSA
{
public:
RSA();
Key getKey()
{
return _key;
} void ecrept(const char* plain_file_in, const char* ecrept_file_out,
bm::int1024_t ekey, bm::int1024_t pkey);
//加密
void decrept(const char* ecrept_file_in, const char* plain_file_out,
bm::int1024_t dkey, bm::int1024_t pkey);
//解密 std::vector ecrept(std::string& str_in, bm::int1024_t ekey, bm::int1024_t pkey);
//字符串加密
std::string decrept(std::vector& ecrept_str, bm::int1024_t dkey, bm::int1024_t pkey);
//解密为字符串 void printInfo(std::vector& ecrept_str);
//打印信息
private:
bm::int1024_t ecrept(bm::int1024_t msg, bm::int1024_t key, bm::int1024_t pkey);
//加密单个信息
bm::int1024_t produce_prime();
//产生素数
bool is_prime(bm::int1024_t prime);
//是否为素数
bool is_prime_bigInt(bm::int1024_t prime);
void produce_keys();
bm::int1024_t produce_pkey(bm::int1024_t prime1, bm::int1024_t prime2);
//计算pq乘积n
bm::int1024_t produce_orla(bm::int1024_t prime1, bm::int1024_t prime2);
//计算欧拉函数φ(n)
bm::int1024_t produce_ekey(bm::int1024_t orla);
//产生e
bm::int1024_t produce_gcd(bm::int1024_t ekey, bm::int1024_t orla);
//产生最大公约数
bm::int1024_t produce_dkey(bm::int1024_t ekey, bm::int1024_t orla);
//产生d
bm::int1024_t exgcd(bm::int1024_t ekey, bm::int1024_t orla,
bm::int1024_t &x, bm::int1024_t &y);
private:
Key _key;
};
// 1. 随机选择两个不相等的质数p和q(实际应用中，这两个质数越大，就越难破解)。
// 2. 计算p和q的乘积n，n = pq。
// 3. 计算n的欧拉函数φ(n)。
// 4. 随机选择一个整数e，条件是1 < e < φ(n)，且e与φ(n) 互质。
// 5. 计算e对于φ(n)的模反元素d，使得de≡1 mod φ(n)，即：
//(de)modφ(n) = 1
// 6. 产生公钥(e, n)，私钥(d, n)。
2.RSA.cpp
#include"RSA.h"
#include
#include
#include
#includeRSA::RSA()
{
produce_keys();
}void RSA::ecrept(const char* plain_file_in, const char* ecrept_file_out,
bm::int1024_t ekey, bm::int1024_t pkey)//加密
{
std::ifstream fin(plain_file_in, std::ifstream::binary);
std::ofstream fout(ecrept_file_out, std::ofstream::binary);
if (!fin.is_open())
{
std::cout << "open file failed" << std::endl;
return;
}
const int NUM = 128;
char buffer[NUM];
bm::int1024_t buffer_out[NUM];
int curNum;
while (!fin.eof())
{
fin.read(buffer, NUM);
curNum = fin.gcount();
for (int i = 0;
i < curNum;
++i)
{
buffer_out[i] = ecrept(buffer[i], ekey, pkey);
}
fout.write((char *)buffer_out, curNum * sizeof(bm::int1024_t));
}
fin.close();
fout.close();
}
void RSA::decrept(const char* ecrept_file_in,const char* plain_file_out,
bm::int1024_t dkey, bm::int1024_t pkey)//解密
{
std::ifstream fin(ecrept_file_in, std::ifstream::binary);
std::ofstream fout(plain_file_out, std::ofstream::binary);
if (!fin.is_open())
{
std::cout << "open file failed" << std::endl;
return;
}
const int NUM = 256;
bm::int1024_t buffer[NUM];
char buffer_out[NUM];
int curNum;
while (!fin.eof())
{
fin.read((char *)buffer, NUM * sizeof(bm::int1024_t));
curNum = fin.gcount() / sizeof(bm::int1024_t);
for (int i = 0;
i < curNum;
++i)
{
buffer_out[i] = (char)ecrept(buffer[i], dkey, pkey);
}
fout.write(buffer_out, curNum);
}
fin.close();
fout.close();
}std::vector RSA::ecrept(std::string& str_in, bm::int1024_t ekey, bm::int1024_t pkey)//字符串加密
{
std::vector vecout;
size_t sz = str_in.size();
for (const auto& e : str_in)
{
vecout.push_back(ecrept(e, ekey, pkey));
}
return vecout;
}
std::string RSA::decrept(std::vector& ecrept_str, bm::int1024_t dkey, bm::int1024_t pkey)//解密为字符串
{
std::string strout;
for (const auto& e : ecrept_str)
{
strout.push_back((char)ecrept(e, dkey, pkey));
}
return strout;
}void RSA::printInfo(std::vector& ecrept_str)//打印信息
{
for (const auto & e : ecrept_str)
{
std::cout << e << ' ';
}
std::cout << std::endl;
}//模幂运算(a^b)%c
bm::int1024_t RSA::ecrept(bm::int1024_t msg, bm::int1024_t key, bm::int1024_t pkey)
{
bm::int1024_t msg_out = 1;
//A0:a^(2^0) = a^1 = a
bm::int1024_t a = msg;
bm::int1024_t b = key;
bm::int1024_t c = pkey;
while (b)
{
if (b & 1)
//msg_out = (A0 * A1 ...Ai ... An) % c
msg_out = (msg_out * a) % c;
b >>= 1;
//Ai = (A(i - 1) * A(i - 1)) % c
a = (a * a) % c;
}
return msg_out;
}//随机产生一个素数
bm::int1024_t RSA::produce_prime()
{
//srand(time(nullptr));
bm::int1024_t prime = 0;
//mt19937:一种随机数产生器
boost::random::mt19937 gen(time(nullptr));
//指定随机数的范围 2 ~ (1<<128)
boost::random::uniform_int_distribution dist(2, bm::int1024_t(1) << 128);
while (1)
{
prime = dist(gen);
if (is_prime_bigInt(prime))
break;
}
return prime;
}bool RSA::is_prime(bm::int1024_t prime)
{
if (prime < 2)
return false;
for (bm::int1024_t i = 2;
i < sqrt(prime);
++i)
{
if (prime % i == 0)
return false;
}
return true;
}bool RSA::is_prime_bigInt(const bm::int1024_t digit)
{
boost::random::mt11213b gen(time(nullptr));
if (miller_rabin_test(digit, 25, gen)) //素数测试算法miller_rabin_test（）
{
if (miller_rabin_test((digit - 1) / 2, 25, gen))
{
return true;
}
}
return false;
}void RSA::produce_keys()
{
bm::int1024_t prime1 = produce_prime();
bm::int1024_t prime2 = produce_prime();
while (prime1 == prime2)
prime2 = produce_prime();
_key.pkey = produce_pkey(prime1, prime2);
bm::int1024_t orla = produce_orla(prime1, prime2);
_key.ekey = produce_ekey(orla);
_key.dkey = produce_dkey(_key.ekey, orla);
}bm::int1024_t RSA::produce_pkey(bm::int1024_t prime1, bm::int1024_t prime2)
{
return prime1 * prime2;
}bm::int1024_t RSA::produce_orla(bm::int1024_t prime1, bm::int1024_t prime2)
{
return (prime1 - 1) * (prime2 - 1);
}//随机选择一个整数e，条件是1 < e < φ(n)，且e与φ(n) 互质
bm::int1024_t RSA::produce_ekey(bm::int1024_t orla)
{
bm::int1024_t ekey;
srand(time(nullptr));
while (1)
{
ekey = rand() % orla;
if (ekey > 1 && produce_gcd(ekey, orla) == 1)
break;
}
return ekey;
}//求最大公约数
bm::int1024_t RSA::produce_gcd(bm::int1024_t ekey, bm::int1024_t orla)
{
//gcd(a, b)------gcd(b ,a%b)
bm::int1024_t ret;
while (ret = ekey % orla)
{
ekey = orla;
orla = ret;
}
return orla;
}bm::int1024_t RSA::produce_dkey(bm::int1024_t ekey, bm::int1024_t orla)
{
bm::int1024_t x, y;
exgcd(ekey, orla, x, y);
return (x % orla + orla) % orla;
}/*
扩展的欧几里得算法
x = y1;
y = x1 - [a/b]*y1
*/bm::int1024_t RSA::exgcd(bm::int1024_t ekey, bm::int1024_t orla,
bm::int1024_t &x, bm::int1024_t &y)
{
if (orla == 0)
{
x = 1;
y = 0;
return ekey;
}
bm::int1024_t ret = exgcd(orla, ekey % orla, x, y);
bm::int1024_t x1 = x, y1 = y;
x = y1;
y = x1 - (ekey / orla) * y1;
return ret;
}
3.test.cpp
#include"RSA.h"
#includevoid teststring()
{
RSA rsa;
Key key = rsa.getKey();
std::string strin;
while (1)
{
std::cout << "输入要加密的信息：" << std::endl;
std::cin >> strin;
std::vectorstrecrept = rsa.ecrept(strin, key.ekey, key.pkey);
std::string strout = rsa.decrept(strecrept, key.dkey, key.pkey);
std::cout << "加密后的信息：" << std::endl;
rsa.printInfo(strecrept);
std::cout << "解密后的信息：" << std::endl;
std::cout << strout << std::endl;
std::cout << std::endl;
}
}void testFile()
{
RSA rsa;
Key key = rsa.getKey();
std::string filename;
std::cout << "输入文件名：" << std::endl;
std::cin >> filename;
rsa.ecrept(filename.c_str(), (filename + ".ecrept.jpg").c_str(), key.ekey, key.pkey);
rsa.decrept((filename + ".ecrept.jpg").c_str(), (filename + ".decrept.jpg").c_str(), key.dkey, key.pkey);
//IO标准库使用C风格字符串而不是C++ string类型字符串作为文件名，所以需要用c_str获取C风格字符串
//c风格的字符串是可以隐式转换成string的，但string无法隐式转换成c风格的字符串
//为了把string转换成ifstream可以接受的类型，必须把string转换为c风格的字符串。
}//void testRandom()
//{
// //mt19937:一种随机数产生器
// boost::random::mt19937 gen(time(nullptr));
// std::cout << "random" << std::endl;
// //指定随机数的范围 0 ~ (1<<786)
// boost::random::uniform_int_distribution dist(0, bm::cpp_int(1) << 768);
// std::cout << dist(gen) << std::endl;
//}int main()
{
//teststring();
testFile();
//testBigInt();
system("pause");
return 0;
}
【RSA加解密（优化---大数加密）】
推荐阅读
