用C++实现RSA公钥密码算法

RSA公钥密码算法是一种非对称加密算法，其中包括两个密钥，一个公钥和一个私钥。它利用大质数的难以分解性质实现了安全性。

在C语言中实现RSA公钥密码算法，可以按照以下步骤：

1.选择两个大质数 p,q，计算 𝜑(n) = (p-1)(q-1)。
2.选择一个整数 e，使得 e 与 𝜑(n) 互质。
3.计算 d = e^-1(mod 𝜑(n))。其中，e^-1 表示 e 的乘法逆元。
4.将 p、q、e 公开作为公钥，n=pq，d 作为私钥。
5.将明文 M 转化为数字 m。
6.公钥加密：C = m^e(mod n)。其中，C 是密文。
7.私钥解密：m = C^d(mod n)。

以下是C语言代码实现：

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

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

int inverse(int a, int b) {
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1)
return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0)
x1 += b0;
return x1;
}

int fast_pow(int base, int power, int mod) {
int result = 1;
base = base % mod;
while (power > 0) {
if (power & 1) {
result = (result * base) % mod;
}
power = power >> 1;
base = (base * base) % mod;
}
return result;
}

int main() {
int p = 61, q = 53;
int n = p * q;
int phi = (p - 1) * (q - 1);
int e = 17;
while (gcd(e, phi) != 1) {
e += 2;
}
int d = inverse(e, phi);
int m = 1234;
int C = fast_pow(m, e, n);
printf("Ciphertext: %d\n", C);
int decrypted_m = fast_pow(C, d, n);
printf("Decrypted plaintext: %d\n", decrypted_m);
return 0;
}

需要注意的是，在实际应用中，选择的大质数 p,q 应该足够大，以保证算法的安全性。此外，由于 C 和 m 的值可能非常大，因此需要使用快速幂算法来计算幂的结果。