用C语言编写 RSA 密码算法程序

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它基于大数因子分解的困难性。在C语言中编写RSA算法涉及几个关键步骤：

1. **密钥生成**：选择两个大素数p和q，计算n=p*q，然后找到欧拉函数phi(n)。选取一个e作为公钥指数（如65537），满足gcd(e, phi(n))=1。然后计算私钥d，使得(d * e) % phi(n) = 1。

2. **加密**：对于明文m，加密过程就是m^e mod n，结果即为密文c。

3. **解密**：解密过程则是c^d mod n，得到原始消息m。

4. **模块运算**：由于涉及到大整数乘法和取模操作，可以使用扩展欧几里得算法等高效算法库来进行。

下面是一个简单的C语言RSA加密的例子（仅作教学参考，实际应用需要考虑性能优化和安全性）：

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

// ...省略其他辅助函数...

// RSA核心功能 - 加密和解密
void rsa_encrypt(int* p, int* q, int e, int m) {
    int n = p[0] * q[0];
    int c = pow(m, e, n);
    printf("Encrypted message: %d\n", c);
}

void rsa_decrypt(int* p, int* q, int d, int c) {
    int m = pow(c, d, (*p * *q));
    printf("Decrypted message: %d\n", m);
}

int main() {
    // 省略密钥生成部分
    int p[] = {61, 53}, q[] = {31, 37};
    int e = 65537;
    int d; // 私钥
    // ...获取d...

    int m = 123; // 明文

    rsa_encrypt(p, q, e, m); // 加密
    rsa_decrypt(p, q, d, c); // 解密

    return 0;
}

请注意，这只是一个基础示例，实际的RSA实现会更复杂，并且你需要处理错误边界、密钥安全存储以及输入验证等问题。