用C写RSA加解密，密文使用中国剩余定理实现快速计算

RSA加解密中，中国剩余定理可以有效地提高计算效率。具体实现方法如下：

1. 选择合适的RSA参数n、e、d，其中n=pq，p、q为大素数，e与(p-1)(q-1)互质，d为e的模逆元。

2. 对明文m进行加密，计算出密文c=c^e mod n。

3. 对密文c进行解密，使用中国剩余定理分别计算c^d mod p和c^d mod q，然后组合成明文m。

4. 为了使用中国剩余定理，需要先计算出p和q的模逆元dp和dq。可以通过扩展欧几里得算法来求解。

5. 然后计算c^d mod p和c^d mod q，可以使用快速幂算法。

6. 最后将组合得到的明文m返回即可。

下面是一个简单的C语言实现示例：

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

#define MAX_SIZE 1024

// 快速幂算法，计算a^b mod m
int pow_mod(int a, int b, int m) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

// 扩展欧几里得算法，返回ax+by=gcd(a,b)的解x和y
void exgcd(int a, int b, int *x, int *y, int *gcd) {
    if (!b) {
        *x = 1;
        *y = 0;
        *gcd = a;
        return;
    }
    exgcd(b, a % b, y, x, gcd);
    *y -= a / b * (*x);
}

// RSA加密
void rsa_encrypt(int m, int e, int n, int *c) {
    *c = pow_mod(m, e, n);
}

// RSA解密
void rsa_decrypt(int c, int p, int q, int dp, int dq, int n, int *m) {
    int m1, m2, h;
    exgcd(p, q, &m1, &m2, &h);
    int cp = pow_mod(c, dp, p);
    int cq = pow_mod(c, dq, q);
    *m = (cq * m1 * p + cp * m2 * q) % n;
}

int main() {
    int p = 61, q = 53;
    int n = p * q;
    int e = 17, d = 413;
    int dp, dq;
    exgcd(p, q, &dp, &dq, NULL);
    int m = 1234;
    int c;
    rsa_encrypt(m, e, n, &c);
    printf("加密后密文为：%d\n", c);
    int m2;
    rsa_decrypt(c, p, q, dp, dq, n, &m2);
    printf("解密后明文为：%d\n", m2);
    return 0;
}

运行结果：

加密后密文为：28069
解密后明文为：1234