rsa加密算法c++简单实现

以下是一个简单的RSA加密算法C实现：

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

#define MAX 1000

// 求最大公约数
int gcd(int a, int b) {
    int temp;
    while (1) {
        temp = a % b;
        if (temp == 0)
            return b;
        a = b;
        b = temp;
    }
}

// 判断两个数是否互质
int isCoPrime(int a, int b) {
    if (gcd(a, b) == 1)
        return 1;
    return 0;
}

// 求模反元素
int getModInverse(int a, int m) {
    int i;
    for (i = 1; i < m; i++) {
        if ((a * i) % m == 1)
            return i;
    }
    return -1;
}

// 加密函数
int encrypt(int msg, int e, int n) {
    int c = 1;
    int i;
    for (i = 0; i < e; i++) {
        c = (c * msg) % n;
    }
    return c;
}

// 解密函数
int decrypt(int msg, int d, int n) {
    int m = 1;
    int i;
    for (i = 0; i < d; i++) {
        m = (m * msg) % n;
    }
    return m;
}

int main() {
    int p, q, n, phi, e, d, i;
    char msg[MAX];
    int encrypted[MAX], decrypted[MAX];

    printf("Enter a message to encrypt: ");
    fgets(msg, MAX, stdin);
    msg[strcspn(msg, "\n")] = 0;

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

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

    // 选择e
    for (i = 2; i < phi; i++) {
        if (isCoPrime(i, phi) && isCoPrime(i, n)) {
            e = i;
            break;
        }
    }

    // 求模反元素d
    d = getModInverse(e, phi);

    // 加密
    for (i = 0; i < strlen(msg); i++) {
        encrypted[i] = encrypt(msg[i], e, n);
    }

    // 解密
    for (i = 0; i < strlen(msg); i++) {
        decrypted[i] = decrypt(encrypted[i], d, n);
    }

    printf("Original message: %s\n", msg);
    printf("Encrypted message: ");
    for (i = 0; i < strlen(msg); i++) {
        printf("%d ", encrypted[i]);
    }
    printf("\n");

    printf("Decrypted message: ");
    for (i = 0; i < strlen(msg); i++) {
        printf("%c", decrypted[i]);
    }
    printf("\n");

    return 0;
}

注意，这只是一个简单的实现，不适用于真实场景。在实际应用中，需要考虑更多的安全问题，例如如何选择p和q、如何保护私钥等等。