c语言rsa算法实现

RSA算法是一种非对称加密算法，其中C语言实现一般包括以下步骤：

1. 生成公钥和私钥
在RSA算法中，公钥和私钥是成对出现的。公钥可以公开给任何人使用，而私钥只能由拥有者保管。生成公钥和私钥的方法如下：

1.1 选择两个质数p和q，计算它们的乘积n=p*q；
1.2 计算欧拉函数φ(n)=(p-1)*(q-1)；
1.3 随机选择一个整数e，满足1<e<φ(n)且e与φ(n)互质，即e和φ(n)的最大公约数为1；
1.4 计算d，满足(d*e)%φ(n)=1，即d是e关于模φ(n)的逆元。

此时，公钥为(n, e)，私钥为(d, p, q)。

2. 加密数据
RSA算法中，数据的加密过程如下：

2.1 将要加密的数据m转化为整数；
2.2 计算c=m^e mod n，其中^表示乘方运算，mod表示取模运算；
2.3 加密后的数据c即为密文。

3. 解密数据
RSA算法中，数据的解密过程如下：

3.1 将密文c转化为整数；
3.2 计算m=c^d mod n；
3.3 解密后的数据m即为原始数据。

以下是一个简单的C语言实现RSA算法的示例代码：

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

// 求最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 求逆元
int inv(int a, int b)
{
    int t1 = 0, t2 = 1, r1 = b, r2 = a % b, q, t;
    while (r2 != 0)
    {
        q = r1 / r2;

        t = t1 - q * t2;
        t1 = t2;
        t2 = t;

        r1 = r2;
        r2 = r1 % r2;
    }
    if (r1 > 1)
        return -1;
    if (t1 < 0)
        t1 += b;
    return t1;
}

// 判断是否为质数
int is_prime(int n)
{
    int i;
    if (n <= 1)
        return 0;
    for (i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return 0;
    return 1;
}

// 生成公钥和私钥
void gen_key(int *n, int *e, int *d)
{
    int p, q, phi_n;
    do
    {
        p = rand() % 100 + 2;
    } while (!is_prime(p));
    do
    {
        q = rand() % 100 + 2;
    } while (!is_prime(q));
    *n = p * q;
    phi_n = (p - 1) * (q - 1);
    do
    {
        *e = rand() % phi_n + 2;
    } while (gcd(*e, phi_n) != 1);
    *d = inv(*e, phi_n);
}

// 加密
int encrypt(int m, int e, int n)
{
    return (int)pow(m, e) % n;
}

// 解密
int decrypt(int c, int d, int n)
{
    return (int)pow(c, d) % n;
}

int main()
{
    int n, e, d; // 公钥和私钥
    int m;       // 原始数据
    int c;       // 密文
    printf("请输入要加密的数据：");
    scanf("%d", &m);
    gen_key(&n, &e, &d); // 生成公钥和私钥
    c = encrypt(m, e, n); // 加密数据
    printf("公钥：(%d,%d)\n", n, e);
    printf("私钥：(%d,%d)\n", d, n);
    printf("加密后的数据：%d\n", c);
    printf("解密后的数据：%d\n", decrypt(c, d, n)); // 解密数据
    return 0;
}