rsa加密算法c语言实现

RSA加密算法是一种非对称加密算法，它需要生成一对公钥和私钥，其中公钥可以公开，用于加密数据，而私钥则用于解密数据。下面是RSA加密算法的C语言实现：

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

#define MAX_PRIME 1000

typedef unsigned long long uint64_t;

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

// 生成指定范围内的随机质数
int generate_prime(int min, int max) {
    int n;
    do {
        n = rand() % (max - min + 1) + min;
    } while (!is_prime(n));
    return n;
}

// 计算最大公约数
int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 计算乘法逆元
int inverse(int a, int b) {
    int q, r, x1 = 1, x2 = 0, y1 = 0, y2 = 1, x, y;
    while (b > 0) {
        q = a / b;
        r = a % b;
        x = x1 - q * x2;
        y = y1 - q * y2;
        a = b;
        b = r;
        x1 = x2;
        x2 = x;
        y1 = y2;
        y2 = y;
    }
    return x1;
}

// 生成公钥和私钥
void generate_keys(uint64_t *p, uint64_t *q, uint64_t *n, uint64_t *e, uint64_t *d) {
    *p = generate_prime(100, MAX_PRIME);
    *q = generate_prime(100, MAX_PRIME);
    *n = *p * *q;
    uint64_t phi_n = (*p - 1) * (*q - 1);
    do {
        *e = rand() % phi_n;
    } while (gcd(phi_n, *e) != 1);
    *d = inverse(phi_n, *e);
}

// 加密数据
uint64_t encrypt(uint64_t m, uint64_t e, uint64_t n) {
    uint64_t c = 1;
    while (e > 0) {
        if (e & 1) {
            c = (c * m) % n;
        }
        m = (m * m) % n;
        e >>= 1;
    }
    return c;
}

// 解密数据
uint64_t decrypt(uint64_t c, uint64_t d, uint64_t n) {
    uint64_t m = 1;
    while (d > 0) {
        if (d & 1) {
            m = (m * c) % n;
        }
        c = (c * c) % n;
        d >>= 1;
    }
    return m;
}

int main() {
    uint64_t p, q, n, e, d;
    generate_keys(&p, &q, &n, &e, &d);
    printf("p = %llu\nq = %llu\nn = %llu\ne = %llu\nd = %llu\n", p, q, n, e, d);
    uint64_t m = 12345;
    uint64_t c = encrypt(m, e, n);
    printf("ciphertext = %llu\n", c);
    uint64_t m2 = decrypt(c, d, n);
    printf("plaintext = %llu\n", m2);
    return 0;
}

在本代码中，我们使用了C语言的随机数生成函数rand()，因此需要包含stdlib.h头文件。该代码实现了生成公钥和私钥、加密和解密数据的功能，其中加密和解密过程都是通过模幂运算实现的。