用c语言实现RSA加密算法

RSA加密算法是一种非对称密钥加密算法，其中加密和解密使用的是不同的密钥。以下是一个简单的RSA加密算法的C语言实现：

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

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

long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

int isPrime(long long n) {
    long long i;
    if (n <= 1 || (n != 2 && n % 2 == 0)) {
        return 0;
    }
    for (i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

long long generatePrime(long long low, long long high) {
    long long n, i;
    do {
        n = rand() % (high - low + 1) + low;
    } while (!isPrime(n));
    return n;
}

long long generatePublicKey(long long p, long long q) {
    long long n = p * q;
    long long phi = (p - 1) * (q - 1);
    long long e;
    do {
        e = rand() % (phi - 2) + 2;
    } while (gcd(phi, e) != 1);
    return e;
}

long long generatePrivateKey(long long p, long long q, long long e) {
    long long n = p * q;
    long long phi = (p - 1) * (q - 1);
    long long d = 1;
    while ((d * e) % phi != 1) {
        d++;
    }
    return d;
}

long long encrypt(long long message, long long e, long long n) {
    return modExp(message, e, n);
}

long long decrypt(long long message, long long d, long long n) {
    return modExp(message, d, n);
}

int main() {
    long long p, q, n, phi, e, d;
    long long message, encrypted, decrypted;

    srand((unsigned int) time(NULL));

    p = generatePrime(100, 1000);
    q = generatePrime(100, 1000);
    n = p * q;
    phi = (p - 1) * (q - 1);
    e = generatePublicKey(p, q);
    d = generatePrivateKey(p, q, e);

    printf("p = %lld\n", p);
    printf("q = %lld\n", q);
    printf("n = %lld\n", n);
    printf("phi = %lld\n", phi);
    printf("e = %lld\n", e);
    printf("d = %lld\n", d);

    message = 123;
    printf("Message: %lld\n", message);

    encrypted = encrypt(message, e, n);
    printf("Encrypted: %lld\n", encrypted);

    decrypted = decrypt(encrypted, d, n);
    printf("Decrypted: %lld\n", decrypted);

    return 0;
}

该实现中包含以下函数：

- `gcd`：计算两个数的最大公约数。
- `modExp`：计算一个数的模幂运算。
- `isPrime`：判断一个数是否为质数。
- `generatePrime`：生成一个指定范围内的质数。
- `generatePublicKey`：生成公钥。
- `generatePrivateKey`：生成私钥。
- `encrypt`：加密。
- `decrypt`：解密。

主函数中首先生成两个随机质数p和q，然后计算n和phi，再生成公钥和私钥。接着，将一个简单的消息123加密和解密，最后输出加密和解密结果。