rsa加密算法c语言实现

以下是RSA加密算法的C语言实现：

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

#define MAX 10000
#define PRIME 10

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int is_prime(int n)
{
    int i;
    if (n < 2)
        return 0;
    for (i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return 0;
    return 1;
}

int mod(int a, int b, int n)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % n;
        a = (a * a) % n;
        b >>= 1;
    }
    return res;
}

int generate_prime()
{
    int p = rand() % MAX;
    while (!is_prime(p))
        p = rand() % MAX;
    return p;
}

int generate_key(int *e, int *d, int *n)
{
    int p, q, phi, gcd_res;
    p = generate_prime();
    q = generate_prime();
    *n = p * q;
    phi = (p - 1) * (q - 1);
    *e = rand() % (phi - 2) + 2;
    gcd_res = gcd(*e, phi);
    while (gcd_res != 1)
    {
        *e = rand() % (phi - 2) + 2;
        gcd_res = gcd(*e, phi);
    }
    for (*d = 1; *d < phi; (*d)++)
        if ((*e * (*d)) % phi == 1)
            break;
}

void encrypt(int *m, int *c, int e, int n)
{
    *c = mod(*m, e, n);
}

void decrypt(int *c, int *m, int d, int n)
{
    *m = mod(*c, d, n);
}

int main()
{
    int m, c, e, d, n;
    srand(time(NULL));
    generate_key(&e, &d, &n);
    printf("Public key: (%d, %d)\n", e, n);
    printf("Private key: (%d, %d)\n", d, n);
    printf("Enter a message to encrypt: ");
    scanf("%d", &m);
    encrypt(&m, &c, e, n);
    printf("Encrypted message: %d\n", c);
    decrypt(&c, &m, d, n);
    printf("Decrypted message: %d\n", m);
    return 0;
}

该程序中，首先实现了一些辅助函数，如求最大公约数、判断是否为质数、模运算等。然后使用随机数生成两个质数，计算出n和φ(n)，随机生成一个e，计算d，并输出公钥和私钥。接着输入待加密的消息m，进行加密并输出密文c，最后进行解密并输出明文m。