用c语言实现大数版本的rsa算法不用库

好的，下面是一个简单的使用C语言实现大数版本的RSA算法的示例：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

/* 定义大数结构体 */
typedef struct bignum {
    int digit[1000]; // 用数组存储大数
    int len; // 大数的位数
    bignum() {
        memset(digit, 0, sizeof(digit));
        len = 0;
    }
} bignum;

/* 按正常加法计算 a + b */
bignum add(bignum a, bignum b) {
    bignum c;
    int carry = 0;
    for (int i = 0; i < a.len || i < b.len; i++) {
        int sum = a.digit[i] + b.digit[i] + carry;
        c.digit[c.len++] = sum % 10;
        carry = sum / 10;
    }
    if (carry) c.digit[c.len++] = carry;
    return c;
}

/* 按正常减法计算 a - b */
bignum sub(bignum a, bignum b) {
    bignum c;
    for (int i = 0, carry = 0; i < a.len; i++) {
        int t = a.digit[i] - carry - b.digit[i];
        if (t < 0) {
            t += 10;
            carry = 1;
        } else carry = 0;
        c.digit[c.len++] = t;
    }
    while (c.len > 1 && c.digit[c.len - 1] == 0) c.len--;
    return c;
}

/* 按正常乘法计算 a * b */
bignum mul(bignum a, int b) {
    bignum c;
    int carry = 0;
    for (int i = 0; i < a.len; i++) {
        int t = a.digit[i] * b + carry;
        c.digit[c.len++] = t % 10;
        carry = t / 10;
    }
    while (carry) {
        c.digit[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}

/* 按正常除法计算 a / b，返回商 */
bignum div(bignum a, int b, int& r) {
    bignum c;
    c.len = a.len;
    for (int i = a.len - 1; i >= 0; i--) {
        r = r * 10 + a.digit[i];
        if (r < b) c.digit[i] = 0;
        else {
            c.digit[i] = r / b;
            r %= b;
        }
    }
    while (c.len > 1 && c.digit[c.len - 1] == 0) c.len--;
    return c;
}

/* 按正常除法计算 a / b，返回余数 */
int mod(bignum a, int b) {
    int r = 0;
    for (int i = a.len - 1; i >= 0; i--) {
        r = r * 10 + a.digit[i];
        r %= b;
    }
    return r;
}

/* 比较 a 和 b 的大小，若 a > b ，返回 1，否则返回 -1，相等返回 0 */
int compare(bignum a, bignum b) {
    if (a.len > b.len) return 1;
    else if (a.len < b.len) return -1;
    else {
        for (int i = a.len - 1; i >= 0; i--) {
            if (a.digit[i] > b.digit[i]) return 1;
            else if (a.digit[i] < b.digit[i]) return -1;
        }
        return 0;
    }
}

/* 生成指定位数的随机大数 */
bignum gen(int len) {
    bignum a;
    srand(time(NULL));
    a.len = len;
    for (int i = 0; i < len; i++) {
        a.digit[i] = rand() % 10;
    }
    while (a.len > 1 && a.digit[a.len - 1] == 0) a.len--;
    return a;
}

/* 求 base^exponent mod modnum */
bignum pow_mod(bignum base, bignum exponent, bignum modnum) {
    bignum ans;
    ans.digit[0] = 1;
    ans.len = 1;
    while (compare(exponent, bignum()) > 0) {
        if (exponent.digit[0] & 1) ans = ans * base % modnum;
        base = base * base % modnum;
        exponent = div(exponent, 2, exponent.digit[0]);
    }
    return ans;
}

/* 判断一个数是否为素数，若是返回 1，否则返回 0 */
int is_prime(bignum n) {
    if (n.len == 1 && n.digit[0] == 2) return 1;
    else if (n.digit[0] % 2 == 0) return 0;
    else {
        bignum m = sub(n, bignum {1}), d = m;
        int s = 0;
        while (d.digit[0] % 2 == 0) {
            d = div(d, 2, d.digit[0]);
            s++;
        }
        for (int i = 0; i < 10; i++) { // 进行 10 次素性测试
            bignum a = gen(n.len - 1);
            if (compare(a, bignum()) == 0) a.digit[0] = 1;
            if (compare(a, m) >= 0) a = sub(a, m);
            bignum x = pow_mod(a, d, n), y = x;
            for (int j = 0; j < s; j++) {
                x = y * y % n;
                if (compare(x, bignum() {1}) == 0 && compare(y, bignum() {1}) != 0 && compare(y, m) != 0) return 0;
                y = x;
            }
            if (compare(y, bignum() {1}) != 0) return 0;
        }
        return 1;
    }
}

/* 生成一个随机的指定位数的素数 */
bignum gen_prime(int len) {
    bignum p = gen(len);
    while (!is_prime(p)) {
        p = add(p, bignum() {2});
    }
    return p;
}

/* 扩展欧几里得算法，用于求 ax + by = gcd(a, b) 的一组解 */
void exgcd(bignum a, bignum b, bignum& x, bignum& y, bignum& gcd) {
    if (compare(b, bignum()) == 0) { // b = 0
        gcd = a;
        x = bignum() {1};
        y = bignum();
    } else {
        exgcd(b, mod(a, b), y, x, gcd);
        y = sub(y, mul(div(a, b, a.digit[0]), x));
    }
}

/* 生成公钥和私钥 */
void gen_key(bignum& p, bignum& q, bignum& n, bignum& e, bignum& d) {
    p = gen_prime(64); // 生成 64 位的素数 p
    q = gen_prime(64); // 生成 64 位的素数 q
    n = p * q; // 计算 n
    bignum phi = mul(sub(p, bignum() {1}), sub(q, bignum() {1})); // 计算 φ(n)
    e = bignum() {65537}; // 选取 e = 65537
    bignum x, y, gcd;
    exgcd(e, phi, x, y, gcd); // 计算 ax + by = gcd(e, φ(n)) 的一组解，即 d = x
    if (compare(d, bignum()) < 0) d = add(d, phi);
}

/* 加密 */
bignum encrypt(bignum m, bignum e, bignum n) {
    return pow_mod(m, e, n);
}

/* 解密 */
bignum decrypt(bignum c, bignum d, bignum n) {
    return pow_mod(c, d, n);
}

int main() {
    bignum p, q, n, e, d;
    gen_key(p, q, n, e, d);
    printf("p = "); // 输出 p
    for (int i = p.len - 1; i >= 0; i--) printf("%d", p.digit[i]);
    printf("\n");
    printf("q = "); // 输出 q
    for (int i = q.len - 1; i >= 0; i--) printf("%d", q.digit[i]);
    printf("\n");
    printf("n = "); // 输出 n
    for (int i = n.len - 1; i >= 0; i--) printf("%d", n.digit[i]);
    printf("\n");
    printf("e = "); // 输出 e
    for (int i = e.len - 1; i >= 0; i--) printf("%d", e.digit[i]);
    printf("\n");
    printf("d = "); // 输出 d
    for (int i = d.len - 1; i >= 0; i--) printf("%d", d.digit[i]);
    printf("\n");
    bignum m = gen(64); // 生成一个 64 位的随机数 m
    printf("m = "); // 输出 m
    for (int i = m.len - 1; i >= 0; i--) printf("%d", m.digit[i]);
    printf("\n");
    bignum c = encrypt(m, e, n); // 加密
    printf("c = "); // 输出密文
    for (int i = c.len - 1; i >= 0; i--) printf("%d", c.digit[i]);
    printf("\n");
    bignum m1 = decrypt(c, d, n); // 解密
    printf("m1 = "); // 输出解密结果
    for (int i = m1.len - 1; i >= 0; i--) printf("%d", m1.digit[i]);
    printf("\n");
    return 0;
}

这是一个简单的实现，可能会有一些不足之处。在实际使用时需要注意算法的正确性和安全性。