使用c语言实现rsa算法

RSA算法是一种非对称加密算法，实现过程相对复杂，需要涉及大数运算和模运算等数学知识。以下是一个简单的C语言实现RSA算法的示例代码：

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

#define MAX_LEN 1000

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

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

//求模幂运算 a^b % c
int modPow(int a, int b, int c) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    return res;
}

//生成公钥和私钥
void generateKeys(int *p, int *q, int *n, int *e, int *d) {
    //1.选择两个大质数p和q
    srand((unsigned)time(NULL)); //设置随机数种子
    do {
        *p = rand() % MAX_LEN + 100; //生成100~MAX_LEN之间的随机数
    } while (!isPrime(*p));
    do {
        *q = rand() % MAX_LEN + 100;
    } while (!isPrime(*q) || *q == *p);
    //2.计算n和欧拉函数phi(n)
    *n = *p * *q;
    int phi = (*p - 1) * (*q - 1);
    //3.选择一个与phi(n)互质的整数e作为公钥
    do {
        *e = rand() % (phi - 2) + 2; //e取值范围为[2, phi(n)-1]
    } while (gcd(*e, phi) != 1);
    //4.计算d作为私钥，满足 e*d = 1 (mod phi(n))
    int k = 1;
    while (1) {
        if ((k * phi + 1) % *e == 0) {
            *d = (k * phi + 1) / *e;
            break;
        }
        k++;
    }
}

//加密
void encrypt(char *plainText, char *cipherText, int n, int e) {
    int len = strlen(plainText);
    for (int i = 0; i < len; i++) {
        int c = (int)plainText[i];
        int res = modPow(c, e, n);
        cipherText[i] = (char)res;
    }
    cipherText[len] = '\0';
}

//解密
void decrypt(char *cipherText, char *plainText, int n, int d) {
    int len = strlen(cipherText);
    for (int i = 0; i < len; i++) {
        int c = (int)cipherText[i];
        int res = modPow(c, d, n);
        plainText[i] = (char)res;
    }
    plainText[len] = '\0';
}

int main() {
    int p, q, n, e, d;
    char plainText[MAX_LEN], cipherText[MAX_LEN], decryptedText[MAX_LEN];

    //生成公钥和私钥
    generateKeys(&p, &q, &n, &e, &d);
    printf("p = %d, q = %d, n = %d, e = %d, d = %d\n", p, q, n, e, d);

    //输入明文
    printf("Enter plain text: ");
    gets(plainText);

    //加密
    encrypt(plainText, cipherText, n, e);
    printf("Encrypted text: %s\n", cipherText);

    //解密
    decrypt(cipherText, decryptedText, n, d);
    printf("Decrypted text: %s\n", decryptedText);

    return 0;
}

在这个代码中，我们先定义了一些常量和函数。其中：

- `isPrime(num)`：判断一个数是否为质数；
- `gcd(a, b)`：求两个数的最大公约数；
- `modPow(a, b, c)`：求模幂运算 a^b % c。

然后，我们实现了生成公钥和私钥的函数 `generateKeys()`，其中：

- 选择两个大质数p和q；
- 计算n和欧拉函数phi(n)；
- 选择一个与phi(n)互质的整数e作为公钥；
- 计算d作为私钥，满足 e*d = 1 (mod phi(n))。

接着，我们实现了加密函数 `encrypt()` 和解密函数 `decrypt()`。其中，加密使用公钥 (n, e)，解密使用私钥 (n, d)。

最后，在 `main()` 函数中，我们使用以上函数实现了一个RSA加密解密的示例程序。