大整数模rsa运算加解密代码用c语言或c++

以下是用C++实现的大整数模RSA运算加解密代码：

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

class BigNum {
private:
    int *num;       // 存储大整数的数组
    int size;       // 数组大小
    int sign;       // 符号，1表示正数，-1表示负数
public:
    BigNum() {
        num = new int[1];
        num[0] = 0;
        size = 1;
        sign = 1;
    }
    BigNum(const BigNum &b) {
        num = new int[b.size];
        memcpy(num, b.num, b.size * sizeof(int));
        size = b.size;
        sign = b.sign;
    }
    BigNum(string str) {
        int len = str.length();
        num = new int[len];
        size = len;
        if (str[0] == '-') {
            sign = -1;
            len--;
        }
        else {
            sign = 1;
        }
        for (int i = 0; i < len; i++) {
            num[i] = str[len - i - 1] - '0';
        }
    }
    ~BigNum() {
        delete[] num;
    }
    void operator=(const BigNum &b) {
        delete[] num;
        num = new int[b.size];
        memcpy(num, b.num, b.size * sizeof(int));
        size = b.size;
        sign = b.sign;
    }
    bool operator==(const BigNum &b) const {
        if (sign != b.sign) {
            return false;
        }
        if (size != b.size) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            if (num[i] != b.num[i]) {
                return false;
            }
        }
        return true;
    }
    bool operator!=(const BigNum &b) const {
        return !(*this == b);
    }
    bool operator>(const BigNum &b) const {
        if (sign > b.sign) {
            return true;
        }
        if (sign < b.sign) {
            return false;
        }
        if (size > b.size) {
            return true;
        }
        if (size < b.size) {
            return false;
        }
        for (int i = size - 1; i >= 0; i--) {
            if (num[i] > b.num[i]) {
                return true;
            }
            if (num[i] < b.num[i]) {
                return false;
            }
        }
        return false;
    }
    bool operator<(const BigNum &b) const {
        return !(*this > b || *this == b);
    }
    bool operator>=(const BigNum &b) const {
        return !(*this < b);
    }
    bool operator<=(const BigNum &b) const {
        return !(*this > b);
    }
    BigNum operator+(const BigNum &b) const {
        if (sign != b.sign) {
            return *this - b.sign * (-b);
        }
        BigNum res;
        int len = max(size, b.size);
        res.num = new int[len + 1];
        memset(res.num, 0, (len + 1) * sizeof(int));
        res.size = len;
        res.sign = sign;
        int carry = 0;
        for (int i = 0; i < len; i++) {
            int a = i < size ? num[i] : 0;
            int b = i < b.size ? b.num[i] : 0;
            int sum = a + b + carry;
            res.num[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry > 0) {
            res.num[len] = carry;
            res.size = len + 1;
        }
        else {
            res.size = len;
        }
        return res;
    }
    BigNum operator-(const BigNum &b) const {
        if (sign != b.sign) {
            return *this + b.sign * (-b);
        }
        if (sign == -1) {
            return (-b) - (-*this);
        }
        if (*this < b) {
            return -(b - *this);
        }
        BigNum res;
        int len = max(size, b.size);
        res.num = new int[len];
        memset(res.num, 0, len * sizeof(int));
        res.size = len;
        res.sign = 1;
        int borrow = 0;
        for (int i = 0; i < len; i++) {
            int a = i < size ? num[i] : 0;
            int b = i < b.size ? b.num[i] : 0;
            int diff = a - b - borrow;
            if (diff >= 0) {
                res.num[i] = diff;
                borrow = 0;
            }
            else {
                res.num[i] = diff + 10;
                borrow = 1;
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            if (res.num[i] == 0) {
                res.size--;
            }
            else {
                break;
            }
        }
        if (res.size == 0) {
            res.sign = 1;
        }
        return res;
    }
    BigNum operator*(const BigNum &b) const {
        BigNum res;
        res.num = new int[size + b.size];
        memset(res.num, 0, (size + b.size) * sizeof(int));
        res.size = size + b.size;
        res.sign = sign * b.sign;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < b.size; j++) {
                res.num[i + j] += num[i] * b.num[j];
            }
        }
        for (int i = 0; i < res.size - 1; i++) {
            res.num[i + 1] += res.num[i] / 10;
            res.num[i] %= 10;
        }
        while (res.size > 1 && res.num[res.size - 1] == 0) {
            res.size--;
        }
        return res;
    }
    BigNum operator/(const BigNum &b) const {
        if (b == 0) {
            exit(1);
        }
        if (*this == 0) {
            return 0;
        }
        BigNum res;
        BigNum a = abs(*this);
        BigNum b1 = abs(b);
        res.num = new int[a.size];
        memset(res.num, 0, a.size * sizeof(int));
        res.size = a.size;
        res.sign = sign * b.sign;
        BigNum cur(0);
        for (int i = a.size - 1; i >= 0; i--) {
            cur = cur * 10 + a.num[i];
            int l = 0;
            int r = 9;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (b1 * mid <= cur) {
                    l = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            res.num[i] = l;
            cur -= b1 * l;
        }
        while (res.size > 1 && res.num[res.size - 1] == 0) {
            res.size--;
        }
        return res;
    }
    BigNum operator%(const BigNum &b) const {
        if (b == 0) {
            exit(1);
        }
        if (*this == 0) {
            return 0;
        }
        BigNum res;
        BigNum a = abs(*this);
        BigNum b1 = abs(b);
        res.num = new int[b1.size];
        memset(res.num, 0, b1.size * sizeof(int));
        res.size = b1.size;
        res.sign = sign;
        for (int i = a.size - 1; i >= 0; i--) {
            res = res * 10 + a.num[i];
            res -= res / b1 * b1;
        }
        if (res.size == 0) {
            res.sign = 1;
        }
        return res;
    }
    BigNum operator^(const BigNum &b) const {
        BigNum res(1);
        BigNum a = *this;
        BigNum b1 = b;
        while (b1 != 0) {
            if (b1 % 2 == 1) {
                res = res * a;
            }
            a = a * a;
            b1 = b1 / 2;
        }
        return res;
    }
    BigNum abs() const {
        BigNum res = *this;
        res.sign = 1;
        return res;
    }
    string to_string() const {
        string res = "";
        if (sign == -1) {
            res += "-";
        }
        for (int i = size - 1; i >= 0; i--) {
            res += num[i] + '0';
        }
        return res;
    }
};

BigNum gcd(const BigNum &a, const BigNum &b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool is_prime(const BigNum &n) {
    if (n < 2) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    if (n % 2 == 0) {
        return false;
    }
    BigNum d = n - 1;
    while (d % 2 == 0) {
        d = d / 2;
    }
    for (int i = 0; i < 10; i++) {
        BigNum a = rand() % (n - 2) + 2;
        BigNum x = a ^ d % n;
        if (x == 1 || x == n - 1) {
            continue;
        }
        bool flag = false;
        for (int j = 0; j < d.size - 1; j++) {
            x = x * x % n;
            if (x == n - 1) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            return false;
        }
    }
    return true;
}

BigNum random_prime(int bits) {
    srand(time(nullptr));
    while (true) {
        BigNum p;
        p.num = new int[bits];
        memset(p.num, 0, bits * sizeof(int));
        p.size = bits;
        p.sign = 1;
        p.num[0] = rand() % 9 + 1;
        for (int i = 1; i < bits; i++) {
            p.num[i] = rand() % 10;
        }
        p.num[bits - 1] |= 1;
        if (is_prime(p)) {
            return p;
        }
        delete[] p.num;
    }
}

BigNum mod_inverse(const BigNum &a, const BigNum &n) {
    BigNum t(0);
    BigNum r(n);
    BigNum newt(1);
    BigNum newr(a);
    while (newr != 0) {
        BigNum q = r / newr;
        BigNum tmp = t - q * newt;
        t = newt;
        newt = tmp;
        tmp = r - q * newr;
        r = newr;
        newr = tmp;
    }
    if (r > 1) {
        exit(1);
    }
    if (t < 0) {
        t = t + n;
    }
    return t;
}

BigNum rsa_encrypt(const BigNum &m, const BigNum &e, const BigNum &n) {
    return m ^ e % n;
}

BigNum rsa_decrypt(const BigNum &c, const BigNum &d, const BigNum &n) {
    return c ^ d % n;
}

int main() {
    BigNum p = random_prime(512);
    BigNum q = random_prime(512);
    BigNum n = p * q;
    BigNum phi = (p - 1) * (q - 1);
    BigNum e = 65537;
    BigNum d = mod_inverse(e, phi);
    string message = "Hello, world!";
    BigNum m(message);
    BigNum c = rsa_encrypt(m, e, n);
    BigNum m1 = rsa_decrypt(c, d, n);
    cout << "Message: " << message << endl;
    cout << "Encrypted: " << c.to_string() << endl;
    cout << "Decrypted: " << m1.to_string() << endl;
    return 0;
}

在这个代码中，我们定义了一个`BigNum`类，用于处理大整数运算。这个类支持加、减、乘、除、幂运算，以及比较大小、取绝对值、转换为字符串等操作。

我们还定义了一个`gcd`函数，用于计算两个大整数的最大公约数，以及一个`is_prime`函数，用于判断一个大整数是否为质数。在实现`is_prime`函数时，我们使用了Miller-Rabin算法，这是一种常用的质数测试算法。

最后，我们实现了RSA加密和解密算法，通过调用`rsa_encrypt`和`rsa_decrypt`函数，可以对一个字符串进行加密和解密。在这个例子中，我们使用了512位的质数p和q，以及65537作为加密指数e。