RSA算法c语言实现

RSA算法是一种非对称加密算法，它可以用来加密和解密数据，也可以用来生成数字签名。它的安全性基于一个数学难题：大质数分解。RSA算法的实现包括以下几个步骤：

1. 选择两个大质数p和q，并计算它们的乘积n=p*q。
2. 计算欧拉函数phi(n)=(p-1)*(q-1)。
3. 选择一个小于phi(n)且与phi(n)互质的整数e，作为加密指数。
4. 计算d，使得d*e mod phi(n)=1，d称为解密指数。
5. 将n和e公开，作为公钥；将n和d保密，作为私钥。
6. 加密时，将明文m转化为整数M，计算C=M^e mod n，C即为密文。
7. 解密时，将密文C计算出明文m=M^d mod n。

以下是一个简单的RSA算法C语言实现示例：

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

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

int main() {
    int p, q, n, phi_n, e, d, i, flag;
    char message[100];
    int ascii_message[100];
    int encrypted_message[100], decrypted_message[100];

    printf("Enter two prime numbers: ");
    scanf("%d %d", &p, &q);

    n = p * q;
    phi_n = (p - 1) * (q - 1);

    printf("Enter a number e such that 1<e<phi(n) and gcd(e,phi(n))=1: ");
    scanf("%d", &e);

    for (i = 2; i < phi_n; i++) {
        if (gcd(i, phi_n) == 1) {
            flag = 1;
            break;
        }
    }

    if (flag == 0) {
        printf("No valid value of e\n");
        exit(0);
    }

    d = (int)fmod(pow(e, -1), phi_n);

    printf("Public key (n,e): (%d,%d)\n", n, e);
    printf("Private key (n,d): (%d,%d)\n", n, d);

    printf("Enter message: ");
    scanf("%s", message);

    for (i = 0; message[i] != '\0'; i++) {
        ascii_message[i] = (int)message[i];
        encrypted_message[i] = (int)fmod(pow(ascii_message[i], e), n);
    }

    printf("Encrypted message: ");
    for (i = 0; message[i] != '\0'; i++) {
        printf("%d ", encrypted_message[i]);
    }

    for (i = 0; message[i] != '\0'; i++) {
        decrypted_message[i] = (int)fmod(pow(encrypted_message[i], d), n);
    }

    printf("\nDecrypted message: ");
    for (i = 0; message[i] != '\0'; i++) {
        printf("%c", decrypted_message[i]);
    }

    return 0;
}