RSA算法的原理及实验，用C语言实现

RSA（Rivest-Shamir-Adleman）算法是一种非对称加密技术，它基于数论难题——大整数分解困难。其基本原理分为三个步骤：

1. **密钥生成**：选择两个大素数p和q，计算n=p*q，然后取欧拉函数φ(n)=(p-1)*(q-1)。选取一个小于φ(n)的整数e（通常取e=65537），满足gcd(e, φ(n))=1（即e与φ(n)互质）。公钥由n和e组成，私钥则由n和d（d是e关于模φ(n)的逆元）组成。

2. **加密**：将明文m转换成小数范围内的整数M，并用公钥加密，通过公式：C ≡ M^e (mod n)，得到密文C。

3. **解密**：使用私钥进行解密，即C^d mod n = M，恢复出原始消息M。

在C语言中实现RSA的一个简化版本，你需要编写一些函数来处理大数运算和寻找模逆元。以下是一个简单的框架：

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

// ...其他大数处理函数...

// 寻找模逆元
int extended_euclidean(int a, int b, int *x, int *y) {
    // ... 实现扩展欧几里得算法 ...
}

// 求私钥d
int calculate_d(int e, int phi_n) {
    int x, y;
    if (!extended_euclidean(e, phi_n, &x, &y))
        return -1; // 如果找不到模逆元，则返回错误
    else
        return (x % phi_n + phi_n) % phi_n; // 加上phi_n确保结果在0到phi_n之间
}

// 加密函数
void rsa_encrypt(int message, int e, int n, int* encrypted_message) {
    *encrypted_message = pow(message, e, n);
}

// 解密函数
int rsa_decrypt(int encrypted_message, int d, int n) {
    return pow(encrypted_message, d, n); // 返回解密后的消息
}

int main() {
    int p, q, n, phi_n, e, d, message, encrypted_message;
    // ... 生成密钥并获取用户输入等 ...

    // ... 使用上述函数进行加密、解密操作 ...
    return 0;
}

注意这只是一个简化的例子，实际应用中会更复杂，需要处理溢出、大数乘法和加法等问题。同时，这个代码并不包含所有必要的大数操作，如大数乘法和取模，这些可能需要借助外部库或自定义函数来实现。对于完整的安全实现，还需要考虑更多的安全措施，比如随机性和保密性。