rsa算法实现超级大数（超过unsigned long long）的加解密和数字签名（c++实现）

经过我的不屑努力，和网上某些大神的帮助，我终于编写成功了rsa算法的加解密程序，现在就无偿贡献给大家

加密程序：

#include 　 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include  

#include  

#include 

#include 

#include 

#include 

#include  

#include 

#include 

#include

#include 

#include  

#include  

#include  

#include  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include　　　

#include 　　　　 

#include 　　　　 

#include 

#include 

#include

#include 

#include 

#include

#include 

#include

using namespace std; 

string n, e,  p, j, b, a[100010],n2,d,lo;

unsigned long long i,c;

inline int compare(string str1, string str2) {//相等返回0，大于返回1，小于返回-1

    if (str1.size() > str2.size()) return 1; //长度长的整数大于长度小的整数

    else if (str1.size() < str2.size()) return -1;

    else                              return str1.compare(str2); //若长度相等，则头到尾按位比较

}

string SUB_INT(string str1, string str2);

string ADD_INT(string str1, string str2) {//高精度加法

    int sign = 1; //sign 为符号位

    string str;

    if (str1[0] == '-') {

        if (str2[0] == '-') {

            sign = -1;

            str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));

        }

        else {

            str = SUB_INT(str2, str1.erase(0, 1));

        }

    }

    else {

        if (str2[0] == '-') {

            str = SUB_INT(str1, str2.erase(0, 1));

        }

        else { //把两个整数对齐，短整数前面加0补齐

            string::size_type L1, L2;

            int i;

            L1 = str1.size();

            L2 = str2.size();

            if (L1 < L2) {

                for (i = 1; i <= L2 - L1; i++) str1 = "0" + str1;

            }

            else {

                for (i = 1; i <= L1 - L2; i++) str2 = "0" + str2;

            }

            int int1 = 0, int2 = 0; //int2 记录进位

            for (i = str1.size() - 1; i >= 0; i--) {

                int1 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) % 10;

                int2 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) / 10;

                str = char(int1 + '0') + str;

            }

            if (int2 != 0) str = char(int2 + '0') + str;

        }

    }

    //运算后处理符号位

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string SUB_INT(string str1, string str2) {//高精度减法

    int sign = 1; //sign 为符号位

    string str;

    int i, j;

    if (str2[0] == '-') {

        str = ADD_INT(str1, str2.erase(0, 1));

    }

    else {

        int res = compare(str1, str2);

        if (res == 0) return "0";

        if (res < 0) {

            sign = -1;

            string temp = str1;

            str1 = str2;

            str2 = temp;

        }

        string::size_type tempint;

        tempint = str1.size() - str2.size();

        for (i = str2.size() - 1; i >= 0; i--) {

            if (str1[i + tempint] < str2[i]) {

                j = 1;

                while (1) {//zhao4zhong1添加

                    if (str1[i + tempint - j] == '0') {

                        str1[i + tempint - j] = '9';

                        j++;

                    }

                    else {

                        str1[i + tempint - j] = char(int(str1[i + tempint - j]) - 1);

                        break;

                    }

                }

                str = char(str1[i + tempint] - str2[i] + ':') + str;

            }

            else {

                str = char(str1[i + tempint] - str2[i] + '0') + str;

            }

        }

        for (i = tempint - 1; i >= 0; i--) str = str1[i] + str;

    }

    //去除结果中多余的前导0

    str.erase(0, str.find_first_not_of('0'));

    if (str.empty()) str = "0";

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string MUL_INT(string str1, string str2) {//高精度乘法

    int sign = 1; //sign 为符号位

    string str;

    if (str1[0] == '-') {

        sign *= -1;

        str1 = str1.erase(0, 1);

    }

    if (str2[0] == '-') {

        sign *= -1;

        str2 = str2.erase(0, 1);

    }

    int i, j;

    string::size_type L1, L2;

    L1 = str1.size();

    L2 = str2.size();

    for (i = L2 - 1; i >= 0; i--) { //模拟手工乘法竖式

        string tempstr;

        int int1 = 0, int2 = 0, int3 = int(str2[i]) - '0';

        if (int3 != 0) {

            for (j = 1; j <= (int)(L2 - 1 - i); j++) tempstr = "0" + tempstr;

            for (j = L1 - 1; j >= 0; j--) {

                int1 = (int3 * (int(str1[j]) - '0') + int2) % 10;

                int2 = (int3 * (int(str1[j]) - '0') + int2) / 10;

                tempstr = char(int1 + '0') + tempstr;

            }

            if (int2 != 0) tempstr = char(int2 + '0') + tempstr;

        }

        str = ADD_INT(str, tempstr);

    }

    //去除结果中的前导0

    str.erase(0, str.find_first_not_of('0'));

    if (str.empty()) str = "0";

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string DIVIDE_INT(string str1, string str2, int flag) {//高精度除法。flag==1时,返回商; flag==0时,返回余数

    string quotient, residue; //定义商和余数

    int sign1 = 1, sign2 = 1;

    if (str2 == "0") {  //判断除数是否为0

        quotient = "ERROR!";

        residue = "ERROR!";

        if (flag == 1) return quotient;

        else         return residue;

    }

    if (str1 == "0") { //判断被除数是否为0

        quotient = "0";

        residue = "0";

    }

    if (str1[0] == '-') {

        str1 = str1.erase(0, 1);

        sign1 *= -1;

        sign2 = -1;

    }

    if (str2[0] == '-') {

        str2 = str2.erase(0, 1);

        sign1 *= -1;

    }

    int res = compare(str1, str2);

    if (res < 0) {

        quotient = "0";

        residue = str1;

    }

    else if (res == 0) {

        quotient = "1";

        residue = "0";

    }

    else {

        string::size_type L1, L2;

        L1 = str1.size();

        L2 = str2.size();

        string tempstr;

        tempstr.append(str1, 0, L2 - 1);

        for (int i = L2 - 1; i < L1; i++) { //模拟手工除法竖式

            tempstr = tempstr + str1[i];

            tempstr.erase(0, tempstr.find_first_not_of('0'));//zhao4zhong1添加

            if (tempstr.empty()) tempstr = "0";//zhao4zhong1添加

            for (char ch = '9'; ch >= '0'; ch--) { //试商

                string str;

                str = str + ch;

                if (compare(MUL_INT(str2, str), tempstr) <= 0) {

                    quotient = quotient + ch;

                    tempstr = SUB_INT(tempstr, MUL_INT(str2, str));

                    break;

                }

            }

        }

        residue = tempstr;

    }

    //去除结果中的前导0

    quotient.erase(0, quotient.find_first_not_of('0'));

    if (quotient.empty()) quotient = "0";

    if ((sign1 == -1) && (quotient[0] != '0')) quotient = "-" + quotient;

    if ((sign2 == -1) && (residue[0] != '0')) residue = "-" + residue;

    if (flag == 1) return quotient;

    else         return residue;

}

string DIV_INT(string str1, string str2) {//高精度除法,返回商

    return DIVIDE_INT(str1, str2, 1);

}

string MOD_INT(string str1, string str2) {//高精度除法,返回余数

    return DIVIDE_INT(str1, str2, 0);

}

string P(string  a, string b, string c)

{

    string ans = "1";

    a = MOD_INT(a , c);

    while (b > "0")

    {

        if (MOD_INT(b, "2") == "1")

            ans = MOD_INT(MUL_INT(ans, a), c);

        b = DIV_INT(b, "2");

        a = MOD_INT( MUL_INT(a , a) , c);

    }

    return ans;

}

string nm(char l)

{

    int ch=int(l);

    if (ch < 0)ch = abs(ch) * 1000;

    string ok="",ko="";

    while (ch != 0)

    {

        ok += char(ch % 10) + '0';

        ch /= 10;

    }

    for (int poo = ok.size() - 1; poo >= 0; poo--)

    {

        ko += ok[poo];

    }

    return ko;

}

int main()

{

    

    string m,op="";

    char po;

    cout << "输入要加密的信息" << endl;

    getline(cin, m);

    cout << "输入n和e"<> n>> e;

    cout << "输入n和d" << endl;

    cin >> n2 >> d;

    cout << "密文：";

    for (i = 0; i < m.size(); i++)

    {

        po = m[i];

        op = nm(po);

        p = P(op, e, n);

        

        

        a[c] = p;

        cout << p << " ";

        c++;

    }

    

    cout << "-1  签名：";

    for (i = 0; i < c; i++)

    {

        a[i] = P(a[i], d, n2);

        

            

            

        

        

        cout << a[i]<<" ";

    }

    cout << "-1";

    

    return 0;

}

在是解密：

#include 　 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include  

#include  

#include 

#include 

#include 

#include 

#include  

#include 

#include 

#include

#include 

#include  

#include  

#include  

#include  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 　　　

#include 　　　　 

#include 　　　　 

#include 

#include 

#include 　　　　

#include 

#include 

#include 

#include 

#include 

using namespace std;

string n , d,  p[100010], j, b,  e, n2, a[100010],  f[100000];

long long i,s = 0, c = 0;

inline int compare(string str1, string str2) {//相等返回0，大于返回1，小于返回-1

    if (str1.size() > str2.size()) return 1; //长度长的整数大于长度小的整数

    else if (str1.size() < str2.size()) return -1;

    else                              return str1.compare(str2); //若长度相等，则头到尾按位比较

}

string SUB_INT(string str1, string str2);

string ADD_INT(string str1, string str2) {//高精度加法

    int sign = 1; //sign 为符号位

    string str;

    if (str1[0] == '-') {

        if (str2[0] == '-') {

            sign = -1;

            str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));

        }

        else {

            str = SUB_INT(str2, str1.erase(0, 1));

        }

    }

    else {

        if (str2[0] == '-') {

            str = SUB_INT(str1, str2.erase(0, 1));

        }

        else { //把两个整数对齐，短整数前面加0补齐

            string::size_type L1, L2;

            int i;

            L1 = str1.size();

            L2 = str2.size();

            if (L1 < L2) {

                for (i = 1; i <= L2 - L1; i++) str1 = "0" + str1;

            }

            else {

                for (i = 1; i <= L1 - L2; i++) str2 = "0" + str2;

            }

            int int1 = 0, int2 = 0; //int2 记录进位

            for (i = str1.size() - 1; i >= 0; i--) {

                int1 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) % 10;

                int2 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) / 10;

                str = char(int1 + '0') + str;

            }

            if (int2 != 0) str = char(int2 + '0') + str;

        }

    }

    //运算后处理符号位

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string SUB_INT(string str1, string str2) {//高精度减法

    int sign = 1; //sign 为符号位

    string str;

    int i, j;

    if (str2[0] == '-') {

        str = ADD_INT(str1, str2.erase(0, 1));

    }

    else {

        int res = compare(str1, str2);

        if (res == 0) return "0";

        if (res < 0) {

            sign = -1;

            string temp = str1;

            str1 = str2;

            str2 = temp;

        }

        string::size_type tempint;

        tempint = str1.size() - str2.size();

        for (i = str2.size() - 1; i >= 0; i--) {

            if (str1[i + tempint] < str2[i]) {

                j = 1;

                while (1) {//zhao4zhong1添加

                    if (str1[i + tempint - j] == '0') {

                        str1[i + tempint - j] = '9';

                        j++;

                    }

                    else {

                        str1[i + tempint - j] = char(int(str1[i + tempint - j]) - 1);

                        break;

                    }

                }

                str = char(str1[i + tempint] - str2[i] + ':') + str;

            }

            else {

                str = char(str1[i + tempint] - str2[i] + '0') + str;

            }

        }

        for (i = tempint - 1; i >= 0; i--) str = str1[i] + str;

    }

    //去除结果中多余的前导0

    str.erase(0, str.find_first_not_of('0'));

    if (str.empty()) str = "0";

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string MUL_INT(string str1, string str2) {//高精度乘法

    int sign = 1; //sign 为符号位

    string str;

    if (str1[0] == '-') {

        sign *= -1;

        str1 = str1.erase(0, 1);

    }

    if (str2[0] == '-') {

        sign *= -1;

        str2 = str2.erase(0, 1);

    }

    int i, j;

    string::size_type L1, L2;

    L1 = str1.size();

    L2 = str2.size();

    for (i = L2 - 1; i >= 0; i--) { //模拟手工乘法竖式

        string tempstr;

        int int1 = 0, int2 = 0, int3 = int(str2[i]) - '0';

        if (int3 != 0) {

            for (j = 1; j <= (int)(L2 - 1 - i); j++) tempstr = "0" + tempstr;

            for (j = L1 - 1; j >= 0; j--) {

                int1 = (int3 * (int(str1[j]) - '0') + int2) % 10;

                int2 = (int3 * (int(str1[j]) - '0') + int2) / 10;

                tempstr = char(int1 + '0') + tempstr;

            }

            if (int2 != 0) tempstr = char(int2 + '0') + tempstr;

        }

        str = ADD_INT(str, tempstr);

    }

    //去除结果中的前导0

    str.erase(0, str.find_first_not_of('0'));

    if (str.empty()) str = "0";

    if ((sign == -1) && (str[0] != '0')) str = "-" + str;

    return str;

}

string DIVIDE_INT(string str1, string str2, int flag) {//高精度除法。flag==1时,返回商; flag==0时,返回余数

    string quotient, residue; //定义商和余数

    int sign1 = 1, sign2 = 1;

    if (str2 == "0") {  //判断除数是否为0

        quotient = "ERROR!";

        residue = "ERROR!";

        if (flag == 1) return quotient;

        else         return residue;

    }

    if (str1 == "0") { //判断被除数是否为0

        quotient = "0";

        residue = "0";

    }

    if (str1[0] == '-') {

        str1 = str1.erase(0, 1);

        sign1 *= -1;

        sign2 = -1;

    }

    if (str2[0] == '-') {

        str2 = str2.erase(0, 1);

        sign1 *= -1;

    }

    int res = compare(str1, str2);

    if (res < 0) {

        quotient = "0";

        residue = str1;

    }

    else if (res == 0) {

        quotient = "1";

        residue = "0";

    }

    else {

        string::size_type L1, L2;

        L1 = str1.size();

        L2 = str2.size();

        string tempstr;

        tempstr.append(str1, 0, L2 - 1);

        for (int i = L2 - 1; i < L1; i++) { //模拟手工除法竖式

            tempstr = tempstr + str1[i];

            tempstr.erase(0, tempstr.find_first_not_of('0'));//zhao4zhong1添加

            if (tempstr.empty()) tempstr = "0";//zhao4zhong1添加

            for (char ch = '9'; ch >= '0'; ch--) { //试商

                string str;

                str = str + ch;

                if (compare(MUL_INT(str2, str), tempstr) <= 0) {

                    quotient = quotient + ch;

                    tempstr = SUB_INT(tempstr, MUL_INT(str2, str));

                    break;

                }

            }

        }

        residue = tempstr;

    }

    //去除结果中的前导0

    quotient.erase(0, quotient.find_first_not_of('0'));

    if (quotient.empty()) quotient = "0";

    if ((sign1 == -1) && (quotient[0] != '0')) quotient = "-" + quotient;

    if ((sign2 == -1) && (residue[0] != '0')) residue = "-" + residue;

    if (flag == 1) return quotient;

    else         return residue;

}

string DIV_INT(string str1, string str2) {//高精度除法,返回商

    return DIVIDE_INT(str1, str2, 1);

}

string MOD_INT(string str1, string str2) {//高精度除法,返回余数

    return DIVIDE_INT(str1, str2, 0);

}

string P(string  a, string b, string c)

{

    string ans = "1";

    a = MOD_INT(a, c);

    while (b > "0")

    {

        if (MOD_INT(b, "2") == "1")

            ans = MOD_INT(MUL_INT(ans, a), c);

        b = DIV_INT(b, "2");

        a = MOD_INT(MUL_INT(a, a), c);

    }

    return ans;

}

int main()

{

    bool m = 1;

    cout << "输入要解密的信息" << endl;

    do

    {

        cin >> p[s];

        f[s] = p[s];

        s++;

    } while (p[s - 1] != "-1");

    cout << "输入要解密的签名" << endl;

    do

    {

        cin >> a[c];

        c++;

    } while (a[c - 1] != "-1");

    cout << "输入n和d" << endl;

    cin >> n >> d;

    cout << "输入n和e" << endl;

    cin >> n2 >> e;

    s--;

    c--;

    for (i = 0; i < s; i++)

    {

        p[i] = P(p[i], d, n);

        int num = atoi(p[i].c_str());

        if (num > 200)

        {

            num = (num / 1000);

            num = -num ;

        }

        cout << char(num);

    }

    for (i = 0; i < c; i++)

    {

        a[i] = P(a[i], e, n2);

        //b = a[i];

        //for (j = 0; j < e - 1; j++)

        //{

         //   a[i] *= b;

           // a[i] = a[i] % n2; 

        //}

        //cout << a[i] << " ";

    }

    for (i = 0; i < c; i++)

    {

        //cout << endl;

        //cout << f[i] << " " << a[i] << " " << endl;

        if (a[i] != MOD_INT(f[i],n2))m = 0;

    }

    if (m)

    {

        cout << " 是宣称用户";

    }

    else

    {

        cout << " 不是宣称用户";

    }

    return 0;

}

rsa算法实现超级大数（超过unsigned long long）的加解密和数字签名（c++实现）

Java相关栏目本月热门文章