RSA算法的加解密用C语来实现

RSA算法是一种非对称加密算法，需要生成一对公钥和私钥，其中公钥用于加密，私钥用于解密。下面是用C语言实现RSA算法的加解密过程：

1. 生成公钥和私钥

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define MAX_PRIME 1000

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

int is_prime(int n) {
    int i;
    if (n == 2) {
        return 1;
    }
    if (n % 2 == 0) {
        return 0;
    }
    for (i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int generate_prime() {
    int p;
    do {
        p = rand() % MAX_PRIME;
    } while (!is_prime(p));
    return p;
}

int generate_key(int *e, int *d, int *n) {
    int p, q, phi_n;
    srand(time(NULL));
    p = generate_prime();
    q = generate_prime();
    *n = p * q;
    phi_n = (p - 1) * (q - 1);
    do {
        *e = rand() % phi_n;
    } while (gcd(*e, phi_n) != 1);
    int k = 1;
    while (1) {
        if ((phi_n * k + 1) % *e == 0) {
            *d = (phi_n * k + 1) / *e;
            break;
        }
        k++;
    }
    return 0;
}

其中，generate_prime函数用于生成小于MAX_PRIME的素数，is_prime函数用于判断一个数是否为素数，gcd函数用于求两个数的最大公约数，generate_key函数用于生成公钥和私钥。该函数首先生成两个随机素数p和q，然后计算n=p*q和phi_n=(p-1)*(q-1)，随机选择一个整数e，使得gcd(e,phi_n)=1，然后在phi_n*k+1能够被e整除的情况下，计算d=(phi_n*k+1)/e，最后返回公钥e和私钥d以及n。

2. 加密和解密

int encrypt(int m, int e, int n) {
    int c = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            c = (c * m) % n;
        }
        m = (m * m) % n;
        e /= 2;
    }
    return c;
}

int decrypt(int c, int d, int n) {
    int m = 1;
    while (d > 0) {
        if (d % 2 == 1) {
            m = (m * c) % n;
        }
        c = (c * c) % n;
        d /= 2;
    }
    return m;
}

其中，encrypt函数用于加密明文m，返回密文c，解密函数decrypt用于解密密文c，返回明文m。这两个函数的实现原理都是使用快速幂算法，对于加密来说，计算c=(m^e) mod n，对于解密来说，计算m=(c^d) mod n。

下面是一个完整的RSA算法示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define MAX_PRIME 1000

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

int is_prime(int n) {
    int i;
    if (n == 2) {
        return 1;
    }
    if (n % 2 == 0) {
        return 0;
    }
    for (i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int generate_prime() {
    int p;
    do {
        p = rand() % MAX_PRIME;
    } while (!is_prime(p));
    return p;
}

int generate_key(int *e, int *d, int *n) {
    int p, q, phi_n;
    srand(time(NULL));
    p = generate_prime();
    q = generate_prime();
    *n = p * q;
    phi_n = (p - 1) * (q - 1);
    do {
        *e = rand() % phi_n;
    } while (gcd(*e, phi_n) != 1);
    int k = 1;
    while (1) {
        if ((phi_n * k + 1) % *e == 0) {
            *d = (phi_n * k + 1) / *e;
            break;
        }
        k++;
    }
    return 0;
}

int encrypt(int m, int e, int n) {
    int c = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            c = (c * m) % n;
        }
        m = (m * m) % n;
        e /= 2;
    }
    return c;
}

int decrypt(int c, int d, int n) {
    int m = 1;
    while (d > 0) {
        if (d % 2 == 1) {
            m = (m * c) % n;
        }
        c = (c * c) % n;
        d /= 2;
    }
    return m;
}

int main() {
    int e, d, n, m, c;
    generate_key(&e, &d, &n);
    printf("Public key: (%d,%d)\n", e, n);
    printf("Private key: (%d,%d)\n", d, n);
    printf("Enter a message: ");
    scanf("%d", &m);
    c = encrypt(m, e, n);
    printf("Encrypted message: %d\n", c);
    m = decrypt(c, d, n);
    printf("Decrypted message: %d\n", m);
    return 0;
}