上信息安全课，老师布置了几个大作业，其中一个为RSA加密算法的实现，不能用Java写。出于兴趣，决定尝试。完成之后，为了便于查找，于是写下这篇文章，以备后续查看。也供大家一起学习，一起进步。
1、预备知识
1.1 快速幂算法
顾名思义，快速幂就是快速算底数的$n$次幂。其时间复杂度为${\rm{O(log n)}}$，与朴素的$O\left( n \right)$相比，效率有了极大的提高。具体可以参考百度百科：快速幂。
1.2 扩展欧几里得算法
扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
\[ax{\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {a,b} \right).\]
如果$a$是负数，可以把问题转化成
$\left| a \right|\left( { - x} \right){\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {\left| a \right|,b} \right)$（$\left| a \right|$为a的绝对值），然后令$x\prime {\rm{ }} = {\rm{ }}\left( { - x} \right)$。具体可以参考*：扩展欧几里得。
1.3 米勒-拉宾素性检验算法
要测试${\rm{N}}$是否为素数，首先将${\rm{N - 1}}$分解为${2^s}d$。在每次测试开始时，先随机选一个介于 [ 1 , N − 1 ] {\displaystyle [1,N-1]} 
$[1,N - 1]$的整数$a$，之后如果对所有的$r \in [0,s - 1]$，若${a^d}\bmod N \ne 1$且 a 2 r d mod N ≠ − 1 {\displaystyle a^{2^{r}d}\mod N\neq -1} 
${a^{{2^r}d}}\bmod N \ne - 1$，则$N$是合数。否则，$N$有$3/4$的概率为素数。
构成该算法的思想是，如果${a^d} \ne 1\left( {{\rm{mod n}}} \right)$以及$n = 1{\rm{ }} + {\rm{ }}{2^s}d$是素数，则值序列
\[{a^d}mod n,{a^{2d}}mod n,{a^{4d}}mod n, \ldots ,{a^{{2^s}d}}mod n\]
将以$1$结束，而且在头一个$1$的前边的值将是$n-1$(当$p$是素数时，对于${y^2} \equiv 1\left( {mod p} \right)$，仅有的解是$y \equiv \pm 1\left( {mod p} \right)$，因为$\left( {y + 1} \right)\left( {y - 1} \right)$必须是$p$的倍数)。注意，如果在该序列中出现了$n-1$，则该序列中的下一个值一定是$1$,因为${\left( {n-1} \right)^2} \equiv {n^2}-2n + 1 \equiv 1\left( {mod n} \right)$。具体可以参考*：米勒-拉宾素性检验。
1.4 RSA加密算法
1.4.1 公钥与私钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：
1、随意选择两个大的质数$p$和$q$，$p$不等于$q$，计算$N = pq$。
2、根据欧拉函数，求得$r = \varphi (N) = \varphi (p)\varphi (q) = (p - 1)(q - 1)$。
3、选择一个小于$r$的整数$e$，使$e$与$r$互质。并求得$e$关于$r$的模反元素，命名为$d$(求$d$令$ed \equiv 1(\bmod \;r)$）。(模反元素存在，当且仅当$e$与$r$互质）
4、将$p$和$q$的记录销毁。
$\left( {N,e} \right)$是公钥，$\left( {N,d} \right)$是私钥。Alice将她的公钥$\left( {N,e} \right)$传给Bob，而将她的私钥$\left( {N,d} \right)$藏起来。
1.4.2 加密消息
假设Bob想给Alice送一个消息$m$，他知道Alice产生的$N$和$e$。他使用起先与Alice约好的格式将$m$转换为一个小于$N$，且与$N$互质的整数$n$，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为$n$。用下面这个公式他可以将$n$加密为$c$：
\[{n^e} \equiv c({\rm{mod\;}}N)\]
计算$c$并不复杂。Bob算出$c$后就可以将它传递给Alice。
1.4.3 解密消息
Alice得到Bob的消息$c$后就可以利用她的密钥$d$来解码。她可以用以下这个公式来将$c$转换为$n$：
\[{c^d} \equiv n({\rm{mod\;}}N)\]
得到$n$后，她可以将原来的信息$m$重新复原。
解码的原理是
\[{c^d} \equiv {n^{ed}}({\rm{mod}}\:N)\]
已知$ed \equiv 1(\bmod \;r)$，即$ed = 1 + h\varphi (N)$。由欧拉定理得：
\[{n^{ed}} = {n^{1 + h\varphi (N)}} = n{\left( {{n^{\varphi (N)}}} \right)^h} \equiv n{(1)^h}(\bmod \;N) \equiv n(\bmod \;N)\]
RSA也可用作数字签名。具体可以参考*：RSA。
2、模块设计
2.1 BigInteger类
因为该加密算法涉及的数可能很大，而C++中并没有像Java一样，内置大整数类BigInteger，故需自己实现，我的实现大概是模仿Java的BigInteger设计的。
该模块包含两个文件：BigInteger.h和BigInteger.cpp。代码如下所示。
BigInteger.h代码如下。
/**
* @Name : BigInteger.h
* @Date : 2017-04-11-22.11.39
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #ifndef __BIGINTEGER_H__
#define __BIGINTEGER_H__ #include <string>
#include <vector>
#include <ostream>
class BigInteger {
public:
typedef long long long_t;
typedef unsigned base_t;
BigInteger(): is_negative(false) { data.push_back(); }// 默认为0
BigInteger(const BigInteger &); // 利用给定的大整数初始化
BigInteger(const std::string &);// 利用给定的十六进制字符串初始化
BigInteger(const long_t &); // 利用给定的long_t类型数据初始化
~BigInteger() {} BigInteger add(const BigInteger &); // 大整数加法
BigInteger subtract(const BigInteger &);// 大整数减法
BigInteger multiply(const BigInteger &) const;// 大整数乘法
BigInteger divide(const BigInteger &); // 大整数整除
BigInteger remainder(const BigInteger &); // 大整数取余
BigInteger mod(const BigInteger &); // 大整数取模
BigInteger divideAndRemainder(const BigInteger &, BigInteger &);// 大整数整除和取余
BigInteger pow(const BigInteger &); // 大整数幂乘
BigInteger modPow(const BigInteger &, const BigInteger &) const;// 大整数幂模运算
BigInteger modInverse(const BigInteger &);// 用扩展欧几里得算法求乘法逆元 BigInteger shiftLeft(const unsigned); // 移位运算,左移
BigInteger shiftRight(const unsigned); // 移位运算,右移 int compareTo(const BigInteger &) const;// 比较运算
bool equals(const BigInteger &) const;// 判断是否等于给定数
static BigInteger valueOf(const long_t &);// 将给定数转换为大整数并返回
std::string toString() const; // 将大整数转换为十六进制字符串
BigInteger abs() const; // 求大整数的绝对值
protected:
// 以下运算符重载函数主要用于像基本类型一样使用大整数类型
friend BigInteger operator + (const BigInteger &, const BigInteger &);
friend BigInteger operator - (const BigInteger &, const BigInteger &);
friend BigInteger operator * (const BigInteger &, const BigInteger &);
friend BigInteger operator / (const BigInteger &, const BigInteger &);
friend BigInteger operator % (const BigInteger &, const BigInteger &);
friend bool operator < (const BigInteger &, const BigInteger &);
friend bool operator > (const BigInteger &, const BigInteger &);
friend bool operator == (const BigInteger &, const BigInteger &);
friend bool operator <= (const BigInteger &, const BigInteger &);
friend bool operator >= (const BigInteger &, const BigInteger &);
friend bool operator != (const BigInteger &, const BigInteger &); // 重载版本,使其能用于long_t类型
friend BigInteger operator + (const BigInteger &, const long_t &);
friend BigInteger operator - (const BigInteger &, const long_t &);
friend BigInteger operator * (const BigInteger &, const long_t &);
friend BigInteger operator / (const BigInteger &, const long_t &);
friend BigInteger operator % (const BigInteger &, const long_t &);
friend bool operator < (const BigInteger &, const long_t &);
friend bool operator > (const BigInteger &, const long_t &);
friend bool operator == (const BigInteger &, const long_t &);
friend bool operator <= (const BigInteger &, const long_t &);
friend bool operator >= (const BigInteger &, const long_t &);
friend bool operator != (const BigInteger &, const long_t &); friend std::ostream & operator << (std::ostream &, const BigInteger &);
BigInteger operator = (const std::string & str) { return (*this) = BigInteger(str); }
BigInteger operator = (const long_t & num) { return (*this) = BigInteger(num); }
private:
BigInteger trim(); // 去掉高位无用的0
int hexToNum(char); // 十六进制字符转换为十进制数
public:
static const int base_bit = ; // 2^5=32,大整数每位存储的二进制位数
static const int base_char = ; // 组成大整数的一位需要的十六进制位数
static const int base_int = ; // 大整数一位对应的二进制位数
static const int base_num = 0xffffffff;// 截取低位的辅助
static const int base_temp = 0x1f; // 截取模32的余数的辅助
static const BigInteger ZERO; // 大整数常量0
static const BigInteger ONE; // 大整数常量1
static const BigInteger TWO; // 大整数常量2
static const BigInteger TEN; // 大整数常量10
private:
bool is_negative;// 是否为负数
std::vector<base_t> data;// 按位数据存储,高位在后
class bit { // 便于大整数运算的二进制处理类
public:
bit(const BigInteger &);// 根据大整数初始化 size_t size() { return length; } // 返回大整数对应的二进制位数
bool at(size_t); // 返回第i位二进制是否为1
private:
std::vector<base_t> bit_vector; // 二进制数据存储,每一个元素对应32位二进制
size_t length; // 二进制的总位数
};
friend class RSA; // RSA为其友元类
}; #endif // __BIGINTEGER_H__
BigInteger.cpp代码如下。
/**
* @Name : BigInteger.cpp
* @Date : 2017-04-11-22.16.42
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #include <algorithm>
#include <cassert>
#include <cctype>
#include "BigInteger.h" // 以下表示为静态常量赋值
const BigInteger BigInteger::ZERO = BigInteger();
const BigInteger BigInteger::ONE = BigInteger();
const BigInteger BigInteger::TWO = BigInteger();
const BigInteger BigInteger::TEN = BigInteger(); /**
* 函数功能:根据给定的大整数构造一个新的大整数
* 参数含义:val代表给定的大整数
*/
BigInteger::BigInteger(const BigInteger & val) {
*this = val;
} /**
* 函数功能:根据给定的十六进制字符串数据构造一个大整数
* 参数含义:str代表给定的数据
*/
BigInteger::BigInteger(const std::string & str): is_negative(false) {
std::string t(str);
if (t.size() && t.at()=='-') {
if (t.size() > )
is_negative = true;
t = t.substr();
}
int cnt = (-(t.size()%))%;// 数的长度不是8的倍数,补足0
std::string temp; for (int i=; i<cnt; ++i)
temp.push_back(''); t = temp+t; for (size_t i=; i<t.size(); i+=base_char) {
base_t sum = ;
for (int j=; j<base_char; ++j) { // 8位十六进制组成大整数的一位
char ch = t[i+j];
int num = hexToNum(ch);
sum = ((sum<<) | (num));
}
data.push_back(sum);
}
reverse(data.begin(), data.end());// 高位在后
*this = trim();// 去除高位的0
} /**
* 函数功能:根据给定的long_t类型数据构造一个大整数
* 参数含义:num代表给定的数据
*/
BigInteger::BigInteger(const long_t & num): is_negative(false) {
long_t t = num;
if (t < ) {
is_negative = true;
t = -t;
}
do {
base_t temp = (t&base_num); // 每次截取低32位
data.push_back(temp);
t >>= base_int;
} while (t);
} /**
* 函数功能:大整数加法运算
* 参数含义:val代表加数
*/
BigInteger BigInteger::add(const BigInteger & val) {
BigInteger ans(*this);
if (ans.is_negative == val.is_negative) {// 同号
int len = val.data.size()-ans.data.size(); while ((len--) > ) // 被加数位数少,高位补0
ans.data.push_back(); int carry = ; // 进位
for (size_t i=; i<val.data.size(); ++i) {
base_t temp = ans.data[i];
ans.data[i] += val.data[i]+carry; // 无符号数相加,超出取其余数
// 进位:一种是有无进位都超出,一种是有进位才超出(比如十进制相加,9+9+1,得9,9+0+0,得9)
carry = (temp>ans.data[i] ? : (temp>(temp+val.data[i]) ? : ));
} for (size_t i=val.data.size(); i<ans.data.size() && carry!=; ++i) {// 还有进位
base_t temp = ans.data[i];
ans.data[i] += carry;
carry = temp > ans.data[i];
} if (carry) // 还有进位
ans.data.push_back(carry);
}
else { // 异号
BigInteger a = abs();
BigInteger b = val.abs();
int flag = a.compareTo(b);
// 绝对值相等,则结果为0,否则用绝对值大的减去小的,符号随绝对值大的
if (flag == -) {
ans = b.subtract(a);
ans.is_negative = val.is_negative;
}
else if (flag == )
ans = ZERO;
else {
ans = a.subtract(b);
ans.is_negative = is_negative;
}
}
return ans;
} /**
* 函数功能:大整数减法运算
* 参数含义:val代表减数
*/
BigInteger BigInteger::subtract(const BigInteger & val) {
BigInteger ans(*this);
BigInteger a = abs();
BigInteger b = val.abs();
if (ans.is_negative == val.is_negative) {// 同号
int flag = a.compareTo(b);
if (flag == ) {// a的绝对值大于b的绝对值,直接减
int borrow = ; // 借位
// 大数减小数
for (size_t i=; i<val.data.size(); ++i) {
base_t temp = ans.data[i];
ans.data[i] -= val.data[i]+borrow;
// 借位:一种是有无借位都超出,另一种是有借位才超出(比如十进制相减,9-0-0,得9,9-9-1,得9)
borrow = temp<ans.data[i] ? : (temp-borrow<val.data[i] ? : );
}
for (size_t i=val.data.size(); i<ans.data.size() && borrow!=; ++i) {// 还有借位
base_t temp = ans.data[i];
ans.data[i] -= borrow;
borrow = temp < (base_t)borrow;
}
ans = ans.trim();// 去掉高位多余的0
}
else if (flag == )
ans = ZERO;
else {// a的绝对值小于b的绝对值
ans = b.subtract(a);
ans.is_negative = !is_negative;
}
}
else { // 异号
ans = a.add(b); // 转换为加法
ans.is_negative = is_negative;
}
return ans;
} /**
* 函数功能:大整数乘法运算
* 参数含义:val代表乘数
*/
BigInteger BigInteger::multiply(const BigInteger & val) const {
if (equals(ZERO) || val.equals(ZERO))
return ZERO;
// 将位数少的作为乘数
const BigInteger & big = data.size()>val.data.size() ? (*this) : val;
const BigInteger & small = (&big)==(this) ? val : (*this); BigInteger ans;
bit t(small); // 转换为二进制进行运算 for (int i=t.size()-; i>=; --i)
if (t.at(i)) {
BigInteger temp(big);
temp.is_negative = false;
temp = temp.shiftLeft(i); // 移位对齐
ans = ans.add(temp);
}
ans.is_negative = !(is_negative == val.is_negative);
return ans;
} /**
* 函数功能:大整数整除运算
* 参数含义:val代表除数
*/
BigInteger BigInteger::divide(const BigInteger & val) {
BigInteger temp;
BigInteger ans = divideAndRemainder(val, temp);
return ans;
} /**
* 函数功能:大整数取余运算
* 参数含义:val代表除数
*/
BigInteger BigInteger::remainder(const BigInteger & val) {
BigInteger ans;
divideAndRemainder(val, ans);
return ans;
} /**
* 函数功能:大整数取模运算(不同于取余,该函数总是返回正余数)
* 参数含义:m代表模数
*/
BigInteger BigInteger::mod(const BigInteger & m) {
BigInteger ans = remainder(m);
if (ans.is_negative)
ans = ans.add(m);
return ans;
} /**
* 函数功能:大整数整除运算和取余运算,整除结果直接返回,取余结果由m传回
* 参数含义:val表示除数,m表示取余结果
*/
BigInteger BigInteger::divideAndRemainder(const BigInteger & val, BigInteger & m) {
assert(!val.equals(ZERO));
BigInteger a = abs();
BigInteger b = val.abs();
int flag = a.compareTo(b);
if (flag == )// 绝对值相等
return (is_negative==val.is_negative) ? BigInteger() : BigInteger(-);
if (flag == -) {
m = *this;
return ZERO;
}
BigInteger ans; bit bit_b(b);
// 位数对齐
while (true) {// a的绝对值大于b的绝对值
bit bit_a(a);
int len = bit_a.size()-bit_b.size();
BigInteger temp;
// 找到移位
while (len >= ) {
temp = b.shiftLeft(len);
if (temp.compareTo(a) != )// 找到最大的左移位数使得当前的a大于等于b
break;
--len;
}
if (len < ) // 当前的a小于b了
break;
base_t num = ;
while (temp.compareTo(a) != ) {
a = a.subtract(temp);
++num; // 统计当前的a最多大于等于几个移位后的b
}
temp = BigInteger(num);
if (len)
temp = temp.shiftLeft(len);// 移位后表明当前的a是b的几倍
ans = ans.add(temp);
}
ans.is_negative = !(is_negative==val.is_negative);
m.data = a.data;
m.is_negative = is_negative;
return ans;
} /**
* 函数功能:大整数幂乘运算
* 参数含义:exponent代表指数
*/
BigInteger BigInteger::pow(const BigInteger & exponent) {
BigInteger ans();
bit t(exponent); // 转化为二进制,快速求幂
for (int i=t.size()-; i>=; --i) {
ans = ans.multiply(ans);
if (t.at(i))
ans = multiply(ans);// 从高位开始,位权累加效应
}
return ans;
} /**
* 函数功能:大整数模幂运算
* 参数含义:exponent代表指数,m代表模数
*/
BigInteger BigInteger::modPow(const BigInteger & exponent, const BigInteger & m) const {
assert(!m.equals(ZERO));
BigInteger ans();
bit t(exponent);
for (int i=t.size()-; i>=; --i) {
ans = ans.multiply(ans).mod(m);
if (t.at(i))
ans = multiply(ans).mod(m);
}
return ans;
} /**
* 函数功能:扩展欧几里得算法求乘法逆元
* 参数含义:m代表求逆元时的模数
*/
BigInteger BigInteger::modInverse(const BigInteger & m) {
assert(!is_negative); // 当前大整数为正数
assert(!m.is_negative); // m为正数
if (equals(ZERO) || m.equals(ZERO))
return ZERO; // 有一个数为0,就不存在乘法逆元
BigInteger a[], b[], t[];
// 以下进行初等变换
a[] = ; a[] = ; a[] = *this;
b[] = ; b[] = ; b[] = m; for (t[]=a[].mod(b[]); !t[].equals(ZERO); t[]=a[].mod(b[])) {
BigInteger temp = a[].divide(b[]);
for (int i=; i<; ++i) {
t[i] = a[i].subtract(temp.multiply(b[i]));// 不超过一次a[2]-temp*b[2]就变为大数减小数
a[i] = b[i];
b[i] = t[i];
}
}
if (b[].equals(ONE)) {// 最大公约数为1,存在乘法逆元
if (b[].is_negative)// 逆元为负数
b[] = b[].add(m);// 变为正数,使其在m的剩余集中
return b[];
}
return ZERO;// 最大公约数不为1,无乘法逆元
} /**
* 函数功能:移位运算,左移
* 参数含义:len代表移位的位数
*/
BigInteger BigInteger::shiftLeft(const unsigned len) {
int index = len>>base_bit; // 大整数每一位需要移动多少位
int shift = len&base_temp; // 还剩下多少位
BigInteger ans(*this); int inc = (shift==) ? index : index+;// 有多余的位要多开大整数的一位
for (int i=; i<inc; ++i)
ans.data.push_back(); // 高位补0 if (index) {
inc = (shift==) ? : ;// 有多余的位要预留一位
for (int i=ans.data.size()-inc; i>=index; --i)
ans.data[i] = ans.data[i-index];
for (int i=; i<index; ++i)
ans.data[i] = ;
}
if (shift) {
base_t t = base_num;
t <<= base_int-shift; // 用于截取高位
// 左移
base_t temp = ;
for (size_t i=; i<ans.data.size(); ++i) {
base_t tmp = ans.data[i];
ans.data[i] = (tmp<<shift) | temp;// 左移后加上大整数低位的高位
temp = (tmp&t)>>(base_int-shift);// 获取该大整数位的高位
}
}
ans = ans.trim();
return ans;
} /**
* 函数功能:移位运算,右移
* 参数含义:len代表移位的位数
*/
BigInteger BigInteger::shiftRight(const unsigned len) {
bit val(*this);
if (len >= val.size())// 当前大整数位数小于等于移位位数,返回0
return ZERO;
int index = len>>base_bit;// 大整数每一位需要移动多少位
int shift = len&base_temp;// 还剩下多少位
BigInteger ans(*this); if (index) {
for (int i=; i<index; ++i)
ans.data[i] = ans.data[i+index];
for (int i=; i<index; ++i)
ans.data.pop_back(); // 高位删除
}
if (shift) {
base_t t = base_num;
t >>= base_int-shift; // 用于截取低位
// 右移
base_t temp = ;
for (int i=ans.data.size()-; i>=; --i) {
base_t tmp = ans.data[i];
ans.data[i] = (tmp>>shift) | temp;// 右移后加上大整数高位的低位
temp = (tmp&t)<<(base_int-shift);// 获取该大整数位的低位
}
}
ans = ans.trim();
return ans;
} /**
* 函数功能:大整数比较函数,-1表示本大整数要小,0表示相等,1表示本大整数要大
* 参数含义:val代表要与之比较的大整数
*/
int BigInteger::compareTo(const BigInteger & val) const {
if (is_negative != val.is_negative) {// 符号不同,负数必小
if (is_negative == true)
return -;
return ;
}
int flag = ;
if (data.size() < val.data.size())// 位数较小
flag = -;
else if (data.size() > val.data.size())// 位数较大
flag = ;
else { // 位数相等,从高位开始一一比较
for (std::vector<base_t>::const_reverse_iterator it=data.rbegin(), ite=val.data.rbegin(); it!=data.rend(); ++it, ++ite)
if ((*it) != (*ite)) {
flag = (*it)<(*ite) ? - : ; // 高位小,则小
break;
}
}
if (is_negative) // 如为负数,小的反而大
flag = -flag;
return flag;
} /**
* 函数功能:大整数是否相等函数
* 参数含义:val表示要与之比较的大整数
*/
bool BigInteger::equals(const BigInteger & val) const {
return (is_negative==val.is_negative) && (data==val.data);// 符号和数据都要相等
} /**
* 函数功能:将一个long_t类型的数据转换为大整数并返回
* 参数含义:num表示给定的数
*/
BigInteger BigInteger::valueOf(const long_t & num) {
return BigInteger(num);
} /**
* 函数功能:将大整数转换为十六进制字符串并返回
*/
std::string BigInteger::toString() const {
std::string ans;
base_t t = base_num;
t <<= base_int-; // 用于截取高4位
for (int i=data.size()-; i>=; --i) {
base_t temp = data[i];
for (int j=; j<base_char; ++j) {
base_t num = t&temp;// 每次截取高4位
num >>= base_int-; // 将高4位移到低4位
temp <<= ;
if (num < )
ans.push_back((char)(''+num));
else
ans.push_back((char)('A'+num-));
}
}
while (ans.size()> && ans.at()=='')// 去掉高位无用的0
ans = ans.substr();
if (ans.empty()) // 空串说明为0
ans.push_back('');
if (is_negative) // 为负数加上负号
ans = "-"+ans;
return ans;
} /**
* 函数功能:返回大整数的绝对值
*/
BigInteger BigInteger::abs() const {
BigInteger ans;
ans.data = data;// 只复制数据,符号默认为正
return ans;
} // 以下运算符重载函数主要是为了使得能使用
// 大整数类型像使用基本类型一样,不一一介绍
BigInteger operator + (const BigInteger & a, const BigInteger & b) {
BigInteger t(a);
return t.add(b);
} BigInteger operator - (const BigInteger & a, const BigInteger & b) {
BigInteger t(a);
return t.subtract(b);
} BigInteger operator * (const BigInteger & a, const BigInteger & b) {
BigInteger t(a);
return t.multiply(b);
} BigInteger operator / (const BigInteger & a, const BigInteger & b) {
BigInteger t(a);
return t.divide(b);
} BigInteger operator % (const BigInteger & a, const BigInteger & b) {
BigInteger t(a);
return t.remainder(b);
} bool operator < (const BigInteger & a, const BigInteger & b) {
return a.compareTo(b) == -;
} bool operator > (const BigInteger & a, const BigInteger & b) {
return b < a;
} bool operator == (const BigInteger & a, const BigInteger & b) {
return a.equals(b);
} bool operator <= (const BigInteger & a, const BigInteger & b) {
return !(a > b);
} bool operator >= (const BigInteger & a, const BigInteger & b) {
return !(a < b);
} bool operator != (const BigInteger & a, const BigInteger & b) {
return !(a == b);
} BigInteger operator + (const BigInteger & a, const BigInteger::long_t & b) {
return a+BigInteger(b);
} BigInteger operator - (const BigInteger & a, const BigInteger::long_t & b) {
return a-BigInteger(b);
} BigInteger operator * (const BigInteger & a, const BigInteger::long_t & b) {
return a*BigInteger(b);
} BigInteger operator / (const BigInteger & a, const BigInteger::long_t & b) {
return a/BigInteger(b);
} BigInteger operator % (const BigInteger & a, const BigInteger::long_t & b) {
return a%BigInteger(b);
} bool operator < (const BigInteger & a, const BigInteger::long_t & b) {
return a < BigInteger(b);
} bool operator > (const BigInteger & a, const BigInteger::long_t & b) {
return a > BigInteger(b);
} bool operator == (const BigInteger & a, const BigInteger::long_t & b) {
return a == BigInteger(b);
} bool operator <= (const BigInteger & a, const BigInteger::long_t & b) {
return a <= BigInteger(b);
} bool operator >= (const BigInteger & a, const BigInteger::long_t & b) {
return a >= BigInteger(b);
} bool operator != (const BigInteger & a, const BigInteger::long_t & b) {
return a != BigInteger(b);
} std::ostream & operator << (std::ostream & out, const BigInteger & val) {
out << val.toString();
return out;
} /**
* 函数功能:创建该大整数的一个副本,去除掉高位无用的0后并返回
*/
BigInteger BigInteger::trim() {
size_t cnt = ;
// 检查高位为0的元素的数量
for (std::vector<base_t>::const_reverse_iterator it=data.rbegin(); it!=data.rend(); ++it) {
if ((*it) == )
++cnt;
else
break;
}
if (cnt == data.size()) // 只有零的情况保留
--cnt;
BigInteger ans(*this);
for (size_t i=; i<cnt; ++i)
ans.data.pop_back();
return ans;
} /**
* 函数功能:根据给定的字符确定它所对应的十进制数
* 参数含义:ch代表给定的字符
*/
int BigInteger::hexToNum(char ch) {
int ans = ;
if (isdigit(ch))
ans = ch-'';
else if (islower(ch))
ans = ch-'a'+;
else
ans = ch-'A'+;
return ans;
} /**
* 函数功能:根据给定的大整数初始化
* 参数含义:val代表给定的大整数
*/
BigInteger::bit::bit(const BigInteger & val) {
bit_vector = val.data;
base_t temp = bit_vector[bit_vector.size()-];// 大整数最高位
length = bit_vector.size()<<base_bit; // 大整数一位占二进制32位
base_t t = <<(base_int-); // 用于截取一个数的二进制最高位 if (temp == ) // 大整数最高位为0,减去32
length -= base_int;
else {
while (!(temp & t)) {// 从高位开始检测大整数的二进制位,为0长度减一
--length;
t >>= ; // 右移一位表示检测下一位
}
}
} /**
* 函数功能:检测大整数的第id位二进制位是否为1
* 参数含义:id代表第id位
*/
bool BigInteger::bit::at(size_t id) {
size_t index = id>>base_bit;// 确定其在大整数第几位
size_t shift = id&base_temp;// 确定其在大整数那一位的二进制第几位
base_t t = bit_vector[index];
return (t & (<<shift));
}
2.2 RSA类
该类主要实现RSA相关功能，例如加密和解密等。
该模块也有两个文件：RSA.h和RSA.cpp。代码如下所示。
RSA.h代码如下。
/**
* @Name : RSA.h
* @Date : 2017-04-11-22.25.57
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #ifndef __RSA_H__
#define __RSA_H__ #include <ostream>
#include "BigInteger.h"
class RSA {
public:
RSA() {}
RSA(const unsigned len) { init(len); } // 利用len初始化对象
~RSA() {} void init(const unsigned);// 初始化,产生公私钥对 BigInteger encryptByPublic(const BigInteger &); // 公钥加密
BigInteger decryptByPrivate(const BigInteger &);// 私钥解密 // 以下主要用于数字签名
BigInteger encryptByPrivate(const BigInteger &);// 私钥加密
BigInteger decryptByPublic(const BigInteger &); // 公钥解密
protected:
friend std::ostream & operator << (std::ostream &, const RSA &);// 输出相关数据
private:
BigInteger createOddNum(unsigned);// 生成一个大奇数,参数为其长度
bool isPrime(const BigInteger &, const unsigned);// 判断是否为素数
BigInteger createRandomSmaller(const BigInteger &);// 随机创建一个更小的数
BigInteger createPrime(unsigned, const unsigned);// 生成一个大素数,参数为其长度
void createExponent(const BigInteger &);// 根据提供的欧拉数生成公钥、私钥指数
public:
BigInteger n, e;// 公钥
private:
BigInteger d;// 私钥
BigInteger p, q;// 大素数p和q
BigInteger eul;// n的欧拉函数
}; #endif // __RSA_H__
RSA.cpp代码如下。
/**
* @Name : RSA.cpp
* @Date : 2017-04-11-22.27.51
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #include <cassert>
#include <sstream>
#include <ctime>
#include "RSA.h" /**
* 函数功能:初始化RSA对象的相关信息
* 参数含义:len表示大素数的二进制位数
*/
void RSA::init(const unsigned len) {
srand((unsigned)time(NULL));
// 产生大素数p和q
p = createPrime(len, );// 出错概率为(1/4)^15
q = createPrime(len, );
// 计算出n
n = p*q;
// 计算出n的欧拉函数
eul = (p-)*(q-);
// 设置加解密指数e和d
createExponent(eul);
} /**
* 函数功能:使用公钥进行加密
* 参数含义:m表示要加密的明文
*/
BigInteger RSA::encryptByPublic(const BigInteger & m) {
return m.modPow(e, n);
} /**
* 函数功能:使用私钥进行解密
* 参数含义:c表示要解密的密文
*/
BigInteger RSA::decryptByPrivate(const BigInteger & c) {
return c.modPow(d, n);
} /**
* 函数功能:使用私钥进行加密
* 参数含义:m表示要加密的明文
*/
BigInteger RSA::encryptByPrivate(const BigInteger & m) {
return decryptByPrivate(m);
} /**
* 函数功能:使用公钥进行解密
* 参数含义:c表示要解密的密文
*/
BigInteger RSA::decryptByPublic(const BigInteger & c) {
return encryptByPublic(c);
} /**
* 函数功能:输出RSA相关数据
* 参数含义:out表示输出流,rsa表示要输出的RSA对象
*/
std::ostream & operator << (std::ostream & out, const RSA & rsa) {
out << "n: " << rsa.n << "\n";
out << "p: " << rsa.p << "\n";
out << "q: " << rsa.q << "\n";
out << "e: " << rsa.e << "\n";
out << "d: " << rsa.d;
return out;
} /**
* 函数功能:生成一个长度为len的奇数
* 参数含义:len代表奇数的二进制长度
*/
BigInteger RSA::createOddNum(unsigned len) {
static const char hex_table[] = {'', '', '', '', '', '', '', '',
'', '', 'A', 'B', 'C', 'D', 'E', 'F'};
len >>= ; // 十六进制数据,每位占4位二进制
if (len) {
std::ostringstream oss;
for (size_t i=; i<len-; ++i)
oss << hex_table[rand()%];
oss << hex_table[];// 最后一位为奇数
return BigInteger(oss.str());
}
return BigInteger("F");
} /**
* 函数功能:判断一个数是否为素数,采用米勒拉宾大素数检测算法,失误率为(1/4)^k
* 参数含义:num代表要判定的数,k代表测试次数
*/
bool RSA::isPrime(const BigInteger & num, const unsigned k) {
assert(num != BigInteger::ZERO);// 测试num是否为0
if (num == BigInteger::ONE)
return false; // 1不是素数
if (num == BigInteger::TWO)
return true; // 2是素数 BigInteger t = num-;
BigInteger::bit b(t);// 二进制数
if (b.at() == ) // 减一之后为奇数,原数为偶数
return false;
// num-1 = 2^s*d
size_t s = ; // 统计二进制末尾有几个0
BigInteger d(t);
for (size_t i=; i<b.size(); ++i) {
if (!b.at(i)) {
++s;
d = d.shiftRight();// 计算出d
}
else
break;
} for (size_t i=; i<k; ++i) {// 测试k次
BigInteger a = createRandomSmaller(num);// 生成一个介于[1,num-1]之间的随机数a
BigInteger x = a.modPow(d, num);
if (x == BigInteger::ONE)// 可能为素数
continue;
bool ok = true;
// 测试所有0<=j<s,a^(2^j*d) mod num != -1
for (size_t j=; j<s && ok; ++j) {
if (x == t)
ok = false; // 有一个相等,可能为素数
x = x.multiply(x).mod(num);
}
if (ok) // 确实都不等,一定为合数
return false;
}
return true; // 通过所有测试,可能为素数
} /**
* 函数功能:随机生成一个比val小的数
* 参数含义:val代表比较的那个数
*/
BigInteger RSA::createRandomSmaller(const BigInteger & val) {
BigInteger::base_t t = ;
do {
t = rand();
} while (t == );// 随机生成非0数 BigInteger mod(t);
BigInteger ans = mod%val; // 比val要小
if (ans == BigInteger::ZERO)// 必须非零
ans = val-BigInteger::ONE;
return ans;
} /**
* 函数功能:生成一个二进制长度为len的大素数
* 参数含义:len代表大素数的长度,k代表素数检测的次数
*/
BigInteger RSA::createPrime(unsigned len, const unsigned k) {
assert(k > );
BigInteger ans = createOddNum(len);// 先生成一个奇数
while (!isPrime(ans, k)) {// 素性检测
ans = ans.add(BigInteger::TWO);// 下一个奇数
}
return ans;
} /**
* 函数功能:根据提供的欧拉数生成公钥、私钥指数
* 参数含义:eul表示提供的欧拉数
*/
void RSA::createExponent(const BigInteger & eul) {
e = ;
d = e.modInverse(eul);
}
2.3 EncryptDecrypt类
该类主要用于封装加解密的一些操作，比如判断数据是否合法，输入输出加解密信息等。
该模块同样有两个文件：EncryptDecrypt.h和EncryptDecrypt.cpp。代码如下所示。
EncryptDecrypt.h代码如下。
/**
* @Name : EncryptDecrypt.h
* @Date : 2017-04-11-22.29.58
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #ifndef __ENCRYPTDECRYPT_H__
#define __ENCRYPTDECRYPT_H__ #include <string>
#include "RSA.h"
class EncryptDecrypt {
public:
EncryptDecrypt() {}
~EncryptDecrypt() {} void menu(); // 菜单显示
bool encrypt(); // 加密
bool decrypt(); // 解密
void print(); // 打印RSA相关信息
void reset(); // 重置RSA相关信息
protected:
void load(int); // 根据给定位数加载RSA对象
bool islegal(const std::string &);// 判断输入字符串是否合法
private:
RSA rsa;
}; #endif // __ENCRYPTDECRYPT_H__
EncryptDecrypt.cpp代码如下。
/**
* @Name : EncryptDecrypt.cpp
* @Date : 2017-04-11-22.32.18
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #include <iostream>
#include <ctime>
#include "EncryptDecrypt.h" /**
* 函数功能:菜单显示
*/
void EncryptDecrypt::menu() {
std::cout << "**********Welcome to use RSA encoder**********" << std::endl;
std::cout << " e: encrypt 加密 " << std::endl;
std::cout << " d: decrypt 解密 " << std::endl;
std::cout << " p: print 显示 " << std::endl;
std::cout << " r: reset 重置 " << std::endl;
std::cout << " q: quit 退出 " << std::endl;
std::cout << "input your choice:" << std::endl;
} /**
* 函数功能:加密运算
*/
bool EncryptDecrypt::encrypt() {
std::string str;
std::cout << "输入16进制数据:" << std::endl;
std::cout << ">";
std::cin >> str;// 输入明文
if (!std::cin || !islegal(str))
return false;
BigInteger m(str);
clock_t start = clock();
BigInteger c = rsa.encryptByPublic(m);
clock_t finish = clock(); std::cout << std::fixed;
std::cout.precision();
std::cout << "用时: " << (double)(finish-start)/CLOCKS_PER_SEC << "s." << std::endl;
std::cout << "明文: " << m << std::endl;
std::cout << "密文: " << c << std::endl;
return true;
} /**
* 函数功能:解密运算
*/
bool EncryptDecrypt::decrypt() {
std::string str;
std::cout << "输入16进制数据:" << std::endl;
std::cout << ">";
std::cin >> str;// 输入密文
if (!std::cin || !islegal(str))
return false;
BigInteger c(str);
clock_t start = clock();
BigInteger m = rsa.decryptByPrivate(c);
clock_t finish = clock(); std::cout << std::fixed;
std::cout.precision();
std::cout << "用时: " << (double)(finish-start)/CLOCKS_PER_SEC << "s." << std::endl;
std::cout << "密文: " << c << std::endl;
std::cout << "明文: " << m << std::endl;
return true;
} /**
* 函数功能:输出RSA相关信息
*/
void EncryptDecrypt::print() {
std::cout << rsa << std::endl;
} /**
* 函数功能:重置RSA相关信息
*/
void EncryptDecrypt::reset() {
std::cout << "输入密钥长度: ";
int len;
std::cin >> len;
load(len>>);
} /**
* 函数功能:根据给定位数len加载rsa
*/
void EncryptDecrypt::load(int len) {
std::cout << "初始化..." << std::endl;
clock_t start = clock();
rsa.init(len); // 初始化
clock_t finish = clock();
std::cout << "初始化完成." << std::endl;
std::cout << std::fixed;
std::cout.precision();
std::cout << "用时: " << (double)(finish-start)/CLOCKS_PER_SEC << "s." << std::endl;
} /**
* 函数功能:判断输入字符串str是否合法
* 参数含义:str代表输入的字符串
*/
bool EncryptDecrypt::islegal(const std::string & str) {
for (std::string::const_iterator it=str.begin(); it!=str.end(); ++it) {
if (!isalnum(*it)) // 不是字母或者数字
return false;
if (isalpha(*it)) {
char ch = tolower(*it);
if (ch > 'f') // 超过十六进制字符'f'
return false;
}
}
return true;
}
2.4 主文件
该模块就只有一个文件：Main.cpp。主要用于使各个模块结合起来，执行相应操作。
Main.cpp代码如下。
/**
* @Name : Main.cpp
* @Date : 2017-04-11-22.19.24
* @Author : Silenceneo (silenceneo_xw@163.com)
* @Link : http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
*/ #include <iostream>
#include "EncryptDecrypt.h" int main() {
EncryptDecrypt encrypt_decrypt;
encrypt_decrypt.reset();// 设置密钥长度 char ch;
std::string str;
bool ok = true; do {
encrypt_decrypt.menu();// 菜单显示
std::cout << ">";
std::cin >> str;
if (str.empty()) {
std::cout << "输入错误!请重新输入!" << std::endl;
continue;
}
ch = str.at();
switch(ch) {
case 'e':
case 'E':
if (!encrypt_decrypt.encrypt())
std::cout << "加密失败,请重试!" << std::endl;
break;
case 'd':
case 'D':
if (!encrypt_decrypt.decrypt())
std::cout << "解密失败,请重试!" << std::endl;
break;
case 'p':
case 'P':
encrypt_decrypt.print();// 打印相关信息
break;
case 'r':
case 'R':
encrypt_decrypt.reset();// 重新设置密钥长度
break;
case 'q':
case 'Q':
ok = false; // 退出
break;
default:
break;
}
} while (ok);
return ;
}
至此，RSA加密算法已经介绍完毕了，如有任何错误，欢迎指出，不胜感激。
附录
RSA加密算法 Java版本
附上Java版本的RSA加密算法，仅供参考。
RSA.java代码如下。
import java.math.BigInteger;
import java.util.Random; public class RSA {
public BigInteger n, e;// 公钥
private BigInteger d;// 私钥
private BigInteger p, q;
private BigInteger eul;// n的欧拉函数 /**
* 函数功能:初始化RSA对象的相关信息
* 参数含义:len表示大素数的二进制位数
*/
public void init(int len) {
Random random = new Random();
// 产生大素数p和q
p = BigInteger.probablePrime(len, random);
q = BigInteger.probablePrime(len, random);
// 计算出n
n = p.multiply(q);
// 计算出n的欧拉函数
eul = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
// 设置加解密指数e和d
createExponent(eul);
} /**
* 函数功能:使用公钥进行加密
* 参数含义:m表示要加密的明文
*/
public BigInteger encryptByPublic(BigInteger m) {
return m.modPow(e, n);
} /**
* 函数功能:使用私钥进行解密
* 参数含义:c表示要解密的密文
*/
public BigInteger decryptByPrivate(BigInteger c) {
return c.modPow(d, n);
} // 以下主要用于数字签名
/**
* 函数功能:使用私钥进行加密
* 参数含义:m表示要加密的明文
*/
public BigInteger encryptByPrivate(BigInteger m) {
return decryptByPrivate(m);
} /**
* 函数功能:使用公钥进行解密
* 参数含义:c表示要解密的密文
*/
public BigInteger decryptByPublic(BigInteger c) {
return encryptByPublic(c);
} /**
* 函数功能:从一个欧拉数中生成公钥、私钥指数
* 参数含义:eul表示提供的欧拉数
*/
private void createExponent(BigInteger eul) {
// TODO Auto-generated method stub
e = new BigInteger("65537");
d = e.modInverse(eul);
} /**
* 函数功能:输出RSA相关数据
*/
public void print() {
System.out.println("n: " + n);
System.out.println("p: " + p);
System.out.println("q: " + q);
System.out.println("e: " + e);
System.out.println("d: " + d);
}
}
EncryptDecrypt.java代码如下。
import java.math.BigInteger;
import java.util.Scanner; public class EncryptDecrypt {
private RSA rsa = new RSA();
public Scanner in = new Scanner(System.in); /**
* 函数功能:菜单显示
*/
public void menu() {
System.out.println("**********Welcome to use RSA encoder**********");
System.out.println(" e: encrypt 加密 ");
System.out.println(" d: decrypt 解密 ");
System.out.println(" p: print 显示 ");
System.out.println(" r: reset 重置 ");
System.out.println(" q: quit 退出 ");
System.out.println("input your choice:");
} /**
* 函数功能:加密运算
*/
public boolean encrypt() {
System.out.println("输入10进制数据:");
System.out.print(">");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger m = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger c = rsa.encryptByPublic(m);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("明文: " + m);
System.out.println("密文: " + c);
return true;
} /**
* 函数功能:解密运算
*/
public boolean decrypt() {
System.out.println("输入10进制数据:");
System.out.print(">");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger c = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger m = rsa.decryptByPrivate(c);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("密文: " + c);
System.out.println("明文: " + m);
return true;
} /**
* 函数功能:输出RSA相关信息
*/
public void print() {
rsa.print();
} /**
* 函数功能:重置RSA相关信息
*/
public void reset() {
System.out.print("输入密钥长度: ");
int len = in.nextInt();
load(len>>1);
} /**
* 函数功能:根据给定位数len加载rsa
*/
private void load(int len) {
// TODO Auto-generated method stub
System.out.println("初始化...");
long start = System.currentTimeMillis();
rsa.init(len);
long finish = System.currentTimeMillis();
System.out.println("初始化完成.");
System.out.println("用时:" + (finish-start) + "ms.");
} /**
* 函数功能:判断输入字符串str是否合法
* 参数含义:str代表输入的字符串
*/
private boolean islegal(String str) {
// TODO Auto-generated method stub
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (!Character.isDigit(ch)) {
return false;
}
}
return true;
}
}
Main.java代码如下。
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
EncryptDecrypt encryptDecrypt = new EncryptDecrypt();
encryptDecrypt.reset();
do {
encryptDecrypt.menu();
System.out.print(">");
String str = encryptDecrypt.in.next();
if (str==null || str.isEmpty()) {
System.out.println("输入错误,请重新输入!");
continue;
}
char ch = str.charAt(0);
switch(ch) {
case 'e':
case 'E':
if (!encryptDecrypt.encrypt()) {
System.out.println("加密失败,请重试!");
}
break;
case 'd':
case 'D':
if (!encryptDecrypt.decrypt()) {
System.out.println("解密失败,请重试!");
}
break;
case 'p':
case 'P':
encryptDecrypt.print();
break;
case 'r':
case 'R':
encryptDecrypt.reset();
break;
case 'q':
case 'Q':
encryptDecrypt.in.close();
System.exit(0);
break;
default:
break;
}
} while (true);
}
}