rsa加密算法c语言实现

RSA加密算法是非常常用的公钥加密算法，C语言实现起来也比较简单。下面是一个简单的RSA加密算法的C语言实现：

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

#define MAX_CHAR 1000
#define PUBLIC_EXPONENT 65537

typedef struct {
    int n;
    int e;
} PublicKey;

typedef struct {
    int n;
    int d;
} PrivateKey;

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

int isPrime(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 generatePrime() {
    int p = rand() % 100 + 1;
    while (!isPrime(p)) {
        p = rand() % 100 + 1;
    }
    return p;
}

int generatePublicKey(int p, int q) {
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int e = PUBLIC_EXPONENT;
    while (e < phi) {
        if (gcd(e, phi) == 1)
            break;
        else
            e++;
    }
    PublicKey publicKey = {n, e};
    return publicKey;
}

int generatePrivateKey(int p, int q, int e) {
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int k = 1;
    while ((k * phi + 1) % e != 0) {
        k++;
    }
    int d = (k * phi + 1) / e;
    PrivateKey privateKey = {n, d};
    return privateKey;
}

int modularExponentiation(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent = exponent / 2;
    }
    return result;
}

void encrypt(char* message, PublicKey publicKey) {
    int i, len;
    len = strlen(message);
    int* cipher = (int*)malloc(sizeof(int) * len);
    for (i = 0; i < len; i++) {
        int m = message[i];
        int c = modularExponentiation(m, publicKey.e, publicKey.n);
        cipher[i] = c;
    }
    printf("Encrypted message: ");
    for (i = 0; i < len; i++) {
        printf("%d ", cipher[i]);
    }
    printf("\n");
    free(cipher);
}

void decrypt(int* cipher, int len, PrivateKey privateKey) {
    int i;
    char* message = (char*)malloc(sizeof(char) * len);
    for (i = 0; i < len; i++) {
        int c = cipher[i];
        int m = modularExponentiation(c, privateKey.d, privateKey.n);
        message[i] = m;
    }
    printf("Decrypted message: %s\n", message);
    free(message);
}

int main() {
    int p = generatePrime();
    int q = generatePrime();
    printf("p = %d, q = %d\n", p, q);
    PublicKey publicKey = generatePublicKey(p, q);
    PrivateKey privateKey = generatePrivateKey(p, q, publicKey.e);
    printf("Public key: n = %d, e = %d\n", publicKey.n, publicKey.e);
    printf("Private key: n = %d, d = %d\n", privateKey.n, privateKey.d);
    char message[MAX_CHAR];
    printf("Enter message to encrypt: ");
    fgets(message, MAX_CHAR, stdin);
    encrypt(message, publicKey);
    printf("Enter cipher to decrypt: ");
    char* input = (char*)malloc(sizeof(char) * MAX_CHAR);
    fgets(input, MAX_CHAR, stdin);
    char* token = strtok(input, " ");
    int len = 0;
    int* cipher = (int*)malloc(sizeof(int) * MAX_CHAR);
    while (token != NULL) {
        cipher[len++] = atoi(token);
        token = strtok(NULL, " ");
    }
    decrypt(cipher, len, privateKey);
    free(input);
    free(cipher);
    return 0;
}

在这个实现中，首先我们定义了PublicKey和PrivateKey两个结构体，分别用来存储公钥和私钥。接着，我们实现了gcd函数和isPrime函数，用来判断一个数是否是质数。然后，我们实现了generatePrime函数，用来生成一个不大于100的质数。接着，我们实现了generatePublicKey函数和generatePrivateKey函数，用来生成公钥和私钥。在这里，我们使用了欧拉函数来计算φ(n)，并且使用扩展欧几里得算法来计算d。接着，我们实现了modularExponentiation函数，用来计算快速模幂。最后，我们实现了encrypt函数和decrypt函数，用来加密和解密消息。在这里，我们将消息转换为ASCII码，并使用公钥进行加密，再使用私钥进行解密。

在main函数中，我们首先生成两个质数p和q，然后使用这两个质数来生成公钥和私钥。接着，我们从标准输入中读取一个消息，并使用公钥进行加密。然后，我们从标准输入中读取一个密文，并使用私钥进行解密。

注意：这个实现只是一个简单的示例，实际上RSA加密算法的实现还有很多细节需要注意，比如如何处理大数、如何选择合适的公钥和私钥等等。