rsa加密算法c++语言实现

RSA加密算法的C语言实现，主要包括以下步骤：

1、选取两个大质数p、q，并计算它们的乘积n=p*q。

2、计算欧拉函数φ(n)=(p-1)*(q-1)。

3、选取一个小于φ(n)且与φ(n)互质的整数e，作为公钥（e，n）。

4、计算e在模φ(n)意义下的逆元d，作为私钥（d，n）。

5、明文M经过公钥（e，n）加密后，得到密文C=(M^e)modn。

6、密文C经过私钥（d，n）解密后，得到明文M'=(C^d)modn。

实现RSA加密算法的C语言代码如下：

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

// 计算a和b的最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 判断一个数是否为质数
int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 6 != 1 && n % 6 != 5) return 0;
    int sq = sqrt(n);
    for (int i = 5; i <= sq; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return 0;
        }
    }
    return 1;
}

// 获取一个随机的素数
int get_prime() {
    int prime;
    do {
        prime = rand() % 10000 + 10000;
    } while (!is_prime(prime));
    return prime;
}

// 计算x的y次方取模z的结果
long long power_mode(long long x, long long y, long long z) {
    long long result = 1;
    x = x % z;
    while (y > 0) {
        if (y % 2 == 1) {
            result = (result * x) % z;
        }
        y = y / 2;
        x = (x * x) % z;
    }
    return result;
}

// 获取与n互质的数
int get_coprime(int n) {
    int e;
    do {
        e = rand() % (n - 2) + 2;
    } while (gcd(e, n) != 1);
    return e;
}

// 计算模反元素
long long mod_inverse(long long a, long long m) {
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}

// 使用公钥加密
long long rsa_encrypt(long long m, long long e, long long n) {
    return power_mode(m, e, n);
}

// 使用私钥解密
long long rsa_decrypt(long long c, long long d, long long n) {
    return power_mode(c, d, n);
}

int main() {
    srand(time(NULL));
    // 选取两个随机素数
    int p = get_prime();
    int q = get_prime();
    // 计算n和phi(n)
    long long n = p * q;
    long long phi_n = (p - 1) * (q - 1);
    // 选取与phi(n)互质的随机数e作为公钥
    long long e = get_coprime(phi_n);
    // 计算e在模phi(n)下的逆元素d作为私钥
    long long d = mod_inverse(e, phi_n);
    // 要加密的明文
    long long m = 123456789;
    // 加密
    long long c = rsa_encrypt(m, e, n);
    // 解密
    long long m2 = rsa_decrypt(c, d, n);
    // 输出结果
    printf("p = %d, q = %d\n", p, q);
    printf("n = %lld, phi(n) = %lld\n", n, phi_n);
    printf("Public key: (e=%lld, n=%lld)\n", e, n);
    printf("Private key: (d=%lld, n=%lld)\n", d, n);
    printf("Original message: %lld\n", m);
    printf("Encrypted message: %lld\n", c);
    printf("Decrypted message: %lld\n", m2);

    return 0;
}