项目介绍

    本项目是介绍基于Boost大数库实现RSA文件加密工具，RSA体制是一种分组密码，其明文和密文均为 0~n-1 之间的整数，通常n的大小为 1024 位二进制数或 309 位十进制数，也就是说 n 小于21024。RSA的安全性取决于两个素数因式分解的难度，故借助Boost大数库来提高RSA加密算法的安全性。

基础知识

1、对称加密与非对称加密

  • 密钥
        密钥是一种参数，它是在明文转换为密文或将密文转换为明文的算法中输入的参数。密钥分为对称密钥与非对称密钥。

  • 对称加密
        甲方利用一种规则对文件进行加密，乙方拿到这个文件需要用同一种规则进行解密。由于加密与解密的过程使用同一种规则（称为密钥），所以在传递密钥称为该算法致命的弱点。

  • 非对称加密
         乙方生成两把密钥（公钥公开，私钥保密）；甲方获取乙方的公钥，然后用它对信息加密；乙方得到加密后的信息，用私钥解密。
    非对称加密算法解决了密钥传递以及保存困难的问题，所以现在使用的非对称加密算法更多一些。

    对称加密与非对称加密相当于HTTP协议与HTTPS协议，他们之间最大的区别就在于：HTTP在网络中发送的信息是以明文的形式发送的，可以被别人截取、破译出信息内容，存在极大的安全问题；HTTPS 在发送信息时对数据进行了一层加密，导致信息内容比容易泄漏。

  • RSA算法是由数学家Rivest、Shamir 和 Adleman 设计且可以实现非对称加密算法。
2、RSA算法原理
  • 加密公式
    在RSA算法中最关键的任务就是计算出公钥与密钥，下面给出计算公钥与密钥的公式：

  1. 加密过程，即获得公钥（e,n）的过程

    密文 = 明文emod(n)

  2. 解密过程，即获得密钥（d,n）的过程

    明文 =密文dmod(n)

  • RSA算法的加密解密流程
    【项目】文件加密工具-编程知识网
    上图为RSA算法的加解密流程图，那么接下来就要计算公钥 e 与密钥 d ，其中涉及到一些数论知识也会详细的进行介绍。

  • RSA算法过程
    【项目】文件加密工具-编程知识网

  • 举例说明

  1. 随机选取两个不相等的素数p,q
    例如选取51 和 47（素数选取的越大，越难破解）

  2. 求两个素数的乘积n，n=p*q
    n = 51 * 47 = 2397
    n 的长度就是密钥长度。2397写成二进制是1001 0101 1101，一共有12位，所以这个密钥就是12位。
    在实际应用中，RSA密钥一般是1024位，重要场合则为2048位（目前被破解的最长RSA密钥是768个二进制位。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全）

  3. 求n的欧拉函数φ(n),φ(n) = (p-1)*(q-1)
    φ(n) = (51 – 1) * (47 – 1) = 2300

  4. 求公钥e，要求：1<e<φ(n)且e与φ(n)互质(e随机选取)
    假设随机取得 e = 17（说明公钥不是唯一的）

  5. 求私钥d，e*d mod φ(n) = 1
    17 * d mod(2300) = 1，解得d = 1353

3、RSA算法涉及到的数论基础知识
  • 质数及相关定理
  1. 素数(质数)：除过1和本身，不能被其它数整除的数；
  2. 互质数：公约数只有1的两个数，叫做互质数。
  3. 两个质数一定是互质数，如17和37；
  4. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系；
  5. 如果两个数之中，较大的那个数是质数，则两者构成互质关系；
  6. 1和任意一个自然数是都是互质关系；
  7. 相邻的两个自然数是互质数；
  8. 相邻的两个奇数是互质数。
  • 欧拉函数及性质
    欧拉函数是小于或等于n的正整数中与n互质的数的数目φ(n)，计算通式如下:
    【项目】文件加密工具-编程知识网
  1. 欧拉函数是积性函数（对于数论函数 f(n) 不恒等于0，当 (m,n) = 1 时，满足 f(mn) = f(m)f(n) ，则称 f(n) 为积性函数），则φ(mn) = φ(m)*φ(n)
  2. 若n为质数，则φ(n) = n – 1由上述性质可得φ(mn) = (m – 1) * (n – 1)

所以在进行RSA 加密时，一般随机选取两个质数，是为了方便计算欧拉函数φ(n)。

  • 欧拉定理
    若 gcd(a,n)=1(表示a 和 n互质),则

    aφ(n) ≡ 1(modn)
    ≡ 是同余符号，表示等式两边的余数相等，即aφ(n) mod n = 1

  • 快速模幂运算

    在进行加密 / 解密的时候，我们做的其实是一个模幂运算，假设我们计算一个数比如 71024%29 是非常消耗计算资源的，在整个计算过程中最麻烦的就是71024的这个过程，存在以下两个缺点：

  • 缺点1：在我们在之后计算指数的过程中，计算的数字不断增大，非常的占用我们的计算资源，而且时间复杂度为O(n)；
  • 缺点2：我们计算的中间过程数字大的恐怖，我们现有的计算机是没有办法记录这么长的数据的，会导致溢出。

为了解决上述的这两个缺点，我们采用模幂运算，首先来介绍以下同余定理

  • 同余定理

有如下公式：

(a + b) % c = ((a % c) + (b % c)) % c
(a - b) % c = ((a % c) - (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % ca^b % c = (a * a * a……a)%c= ((a%c)*(a%c)*(a%c)*……*(a%c))%c= (a % c)^b % c
  • 快速模幂运算

快速模幂运算的作用就是减少幂运算的次数

对于任何一个整数的模幂运算：a^b % ca^b % c对于b的二进制展开形式b = b₀*2⁰ + b₁ * 2¹ + …… + bn * 2^n这里b0对应的是b二进制的第一位, 二进制值只有两种可能，0或者1
将a^b运算就可以拆解成a^b = a^(b₀*2⁰ + b₁ * 2¹ + …… + bn * 2^n)= a^(b₀*2⁰) * a^(b₁ * 2¹) * …… * a^(bn * 2^n)由于不是b的每个二进制都是 1 ，因此去掉二进制位是 0 的位（因为 a^0 = 1)，就变成了a^b = a^(bi * 2^i) * …… * a^(bn * 2^n)，这里的bi~bn都是 1= a^(2^i) * …… * a^(2^n)则	    a^b%c = (a^(2^i) * …… * a^(2^n))%c由同余定理可得a^b%c = (a^(2^i)%c * …… * a^(2^n)%c)%c令 Ai = (a^(2^i))%c，所以(a^b)%c = (Ai * …… * An)%c；其中 A0 = a^(2^0) % cA1 = a^(2^1) % cA2 = a^(2^2) % cAi = a^(2^i) % cA(n-1) = a^(2^(n-1)) % cAn = a^(2^n) % c= (a^2^(n-1)^2) % c= (a^2^(n-1) * a^2^(n-1)) % c因此 An = (A(n - 1) * A(n - 1)) % c

快速幂的时间复杂度就是O(logn)，无限接近常数的时间复杂度无疑比朴素的时间复杂度优秀很多，在数据量越大的时候，这种优化效果越明显。
在快速模幂算法中加入同余定理，就可以解决数据大小超出内存限制的问题。

double myPow(double x, int n) {if(x == 1 || n == 0){return 1.0;}double res = 1;long num = n;if(num < 0){num = -num;x = 1/x;}while(num){if(num & 1){res *= x;}x *= x;num >>= 1;}return res;}
  • 模反元素

    根据欧拉定理，如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1可以被 n 整除，或者说 ab 被 n 除的余数是 1,即

ab ≡ 1(modn)
这时，b就叫做a的”模反元素”，或者称为模的逆元。

  • 模反元素优化

    模反元素也称为模的逆元，如果使用暴力搜索，求逆元d的时间复杂度为O(n)，这对于大数是行不通的，所以需要更快速的算法。

假设a,b的最大公约数gcd，由欧几里得定理可得gcd(a,b) = gcd(a,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]表示向下取整，），可变形为：ay1 + b(x1 – [a/b]y1) = 1

则可得到以下关系：x = y1, y = x1 – [a/b]y1

4、Boost大数库
  • 产生大数随机数
    boost库中也提供产生大数随机数的接口，它在random.hpp文件中
#include <boost/multiprecision/random.hpp>
namespace rp = boost::random;
void test()
{
//mt19937:一种随机数产生器
rp::mt19937 gen(time(nullptr));
cout << "random" << endl;
//指定随机数的范围 0 ~ (1<<786)
rp::uniform_int_distribution<mp::cpp_int> dist(0, mp::cpp_int(1)<<768);
cout << dist(gen) << endl;
}
  • 大数素性检测
    普通的素数检测方法对于大数的效率太慢，大数的素性检测有专门的算法，比如fermat检测，Miller-Rabin等算法。boost库中实现了Miller-Rabin方法。
#include <boost/multiprecision/miller_rabin.hpp>
namespace rp = boost::random;
Rsa::is_prime_bigInt(const mp::int1024_t digit)
{
/*
参考boost文档：
https://www.boost.org/doc/libs/1_58_0/libs/multiprecision/doc/html/boost_multiprecision/tut/primetest.html
*/
rp::mt11213b gen(time(nullptr));
if (miller_rabin_test(digit, 25, gen))
{
if (miller_rabin_test((digit - 1) / 2, 25, gen))
{
return true;
}
}
return false;
}

项目开发

1、RSA算法的实现过程
  • 基本结构
#define NUMBER 256
struct Key
{//公钥：(e,n) ，私钥(d,n)DataType m_ekey;DataType m_dkey;DataType m_pkey;
};/*
步骤：
①：随机选取两个不相等的素数p,q
②：求两个素数的乘积n，n=p*q
③：求n的欧拉函数f(n),f(n) = (p-1)*(q-1)
④：求公钥e，1<e<f(n)且e与f(n)互质(e随机选取)
⑤：求私钥d，e*d mod f(n) = 1
*/class RSA
{Key m_key;
public:RSA();void ecrept(const char * filename, const char * fileout);void decrept(const char * filename, const char * fileout);DataType ecrept(DataType data, DataType ekey, DataType pkey);//加密DataType decrept(DataType data, DataType dkey, DataType pkey);//解密DataType getPrime();DataType getPkey(DataType prime1, DataType prime2);//求nDataType getOrla(DataType prime1, DataType prime2);DataType getEkey(DataType orla);DataType getDkey(DataType ekey, DataType orla);DataType getGcd(DataType data1, DataType data2);//获取最大公约数void getKeys();Key getallKey();
};
  • 判断素数
bool RSA::isPrime(DataType data)
{if (data <= 0){return false;}for (int i = 2; i <= sqrt(data); i++){if (data % i == 0){return false;}}return true;
}
  • 获取素数
DataType RSA::getPrime()
{srand(time(NULL));//随机种子DataType prime;while (true){prime = rand() % 100 + 2;if (isPrime(prime)){break;}}return prime;
}
  • 获取两个素数的乘积
DataType RSA::getPkey(DataType prime1, DataType prime2)
{return prime1*prime2;
}
  • 计算欧拉函数
DataType RSA::getOrla(DataType prime1, DataType prime2)
{return (prime1 - 1)*(prime2 - 1);
}
  • 获取公钥
DataType RSA::getEkey(DataType orla)
{srand(time(NULL));DataType ekey;while (true){ekey = rand() % orla;if (ekey > 1 && getGcd(ekey, orla) == 1){return ekey;}}
}
  • 获取私钥
DataType RSA::getDkey(DataType ekey, DataType orla)
{DataType dkey = orla / ekey;while (true){if ((ekey * dkey) % orla == 1){return dkey;}dkey++;}
}
  • 加密/解密过程
DataType RSA::ecrept(DataType data, DataType ekey, DataType pkey)
{DataType Ai = data;DataType msgE = 1;while (ekey){if (ekey & 1) //如果该二进制位是 1 才会将这一位的幂运算结果乘到结果中{msgE = (msgE * Ai) % pkey; //同余定理解决数据溢出}ekey >>= 1;Ai = (Ai * Ai) % pkey; //快速幂中把下一个二进制位的幂运算结果算出来}return msgE;
}DataType RSA::decrept(DataType data, DataType dkey, DataType pkey)
{return ecrept(data, dkey, pkey);
}
2、基于Boost大数库实现RSA算法

    由于破解私钥的难度取决去因式分解的复杂程度，而在C++标准库中的数并不是很大,上述的算法中不能获得较大的素数，所以私钥会比较容易破解成功，从而导致RSA加密算法的安全性不能得到保证，所以我们借助boost库中的cpp_int库，即大数库来增强实现我们的RSA加密流程。

boost库中有从128位到1024位的大数可以供我们使用。boost大数库参考文档

typedef boost::multiprecision::int1024_t DataType;
namespace brdm = boost::random;
  • 判断素数
bool RSA::isPrimeBigInt(DataType data)
{brdm::mt11213b gen(time(NULL));if (miller_rabin_test(data, 25, gen)){if (miller_rabin_test((data - 1) / 2, 25, gen));{return true;}}return false;
}
  • 获得素数
DataType RSA::getPrime()
{DataType prime;//mt19937是一种随机数产生器brdm::mt19937 gen(time(NULL));//这里我采用最大的随机数是1 << 256位，也就是2^256。brdm::uniform_int_distribution<DataType> dist(0, DataType(1) << 256);while (true){prime = dist(gen);if (isPrimeBigInt(prime)){break;}}return prime;
  • 获得公钥
DataType RSA::getEkey(DataType orla)
{brdm::mt19937 gen(time(NULL));brdm::uniform_int_distribution<DataType> dist(2, orla);DataType ekey;while (true){ekey = dist(gen);if (getGcd(ekey, orla) == 1)//两个数的最大公约数为1表示互质{return ekey;}}
  • 获得私钥
DataType RSA::getDkey(DataType ekey, DataType orla)
{DataType x = 0, y = 0;exGcd(ekey, orla, x, y);//变换，让解密秘钥是一个比较小的正值(扩展的欧几里得定理)return (x% orla + orla) % orla;
}
  • 模反元素优化
DataType RSA::exGcd(DataType a, DataType b, DataType &x, DataType& y)
{if (b == 0){x = 1;y = 0;return a;}DataType gcd = exGcd(b, a%b, x, y);DataType x1 = x, y1 = y;x = y1;y = x1 - a / b *y1;return gcd;
}
  • 文件加密
void RSA::ecrept(const char * filename, const char * fileout)
{std::ifstream fin(filename, std::ifstream::binary);//模式，有二进制模式/文本文件模式std::ofstream fout(fileout, std::ifstream::binary);if (!fin.is_open()){perror("input file open failed!");return;}char* buffer = new char[NUMBER];DataType* bufferout = new DataType[NUMBER];while (!fin.eof()){fin.read(buffer, NUMBER);//gcount()可以获取最近一次读取的字节数int curNum = fin.gcount();for (int i = 0; i < curNum; i++){bufferout[i] = ecrept((DataType)buffer[i], m_key.m_ekey, m_key.m_pkey);}fout.write((char*)bufferout, curNum * sizeof(DataType));}delete[] bufferout;delete[] buffer;fin.close();fout.close();
}
  • 文件解密
void RSA::decrept(const char * filename, const char * fileout)
{std::ifstream fin(filename, std::ifstream::binary);//模式，有二进制模式/文本文件模式std::ofstream fout(fileout, std::ifstream::binary);if (!fin.is_open()){perror("input file open failed!");return;}DataType* buffer = new DataType[NUMBER];char* bufferout = new char[NUMBER];while (!fin.eof()){fin.read((char*)buffer, NUMBER * sizeof(DataType));//gcount()可以获取最近一次读取的字节数int num = fin.gcount();//实际读取的字节num /= sizeof(DataType);for (int i = 0; i < num; i++){bufferout[i] = (char)decrept(buffer[i], m_key.m_dkey, m_key.m_pkey);}fout.write(bufferout, num);}delete[] bufferout;delete[] buffer;fout.close();fin.close();
}

    以上就是关于RSA加密算法的主要内容，由于是产生的素数是大数，所以在代码运行的过程中可能会比较慢。

  • 完整源代码见:基于boost大数库实现RSA加密算法