给出RSA的完整c语言程序
时间: 2024-06-19 15:04:25 浏览: 34
RSA是一种非对称加密算法,它的加密和解密使用不同的密钥,其中一个称为公钥,另一个称为私钥。下面是一个简单的C语言程序实现RSA加密和解密:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
// 求最大公约数
int gcd(int a, int b) {
if (a % b == 0) {
return b;
} else {
return gcd(b, a % b);
}
}
// 扩展欧几里得算法
int ex_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
} else {
int r = ex_gcd(b, a % b, y, x);
*y -= a / b * (*x);
return r;
}
}
// 求逆元
int mod_reverse(int a, int n) {
int x, y;
ex_gcd(a, n, &x, &y);
return (x % n + n) % n;
}
// 判断是否为素数
int is_prime(int n) {
if (n <= 1) {
return 0;
}
int sqr = sqrt(n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
// 生成公钥和私钥
void gen_key(int p, int q, int *n, int *e, int *d) {
// 计算n
*n = p * q;
// 计算欧拉函数
int phi = (p - 1) * (q - 1);
// 选择e
for (int i = 2; i < phi; i++) {
if (gcd(i, phi) == 1) {
*e = i;
break;
}
}
// 计算d
*d = mod_reverse(*e, phi);
}
// 加密
int encrypt(int m, int e, int n) {
return (int)fmod(pow(m, e), n);
}
// 解密
int decrypt(int c, int d, int n) {
return (int)fmod(pow(c, d), n);
}
int main() {
int p = 61;
int q = 53;
int n, e, d;
gen_key(p, q, &n, &e, &d);
printf("公钥:(%d, %d)\n", n, e);
printf("私钥:(%d, %d)\n", n, d);
char plaintext[100] = "Hello RSA!";
printf("明文:%s\n", plaintext);
int len = strlen(plaintext);
int m[len];
for (int i = 0; i < len; i++) {
m[i] = plaintext[i];
printf("%d ", m[i]);
}
printf("\n");
int c[len];
for (int i = 0; i < len; i++) {
c[i] = encrypt(m[i], e, n);
printf("%d ", c[i]);
}
printf("\n");
char ciphertext[100] = "";
for (int i = 0; i < len; i++) {
ciphertext[i] = c[i];
}
printf("密文:%s\n", ciphertext);
for (int i = 0; i < len; i++) {
m[i] = decrypt(c[i], d, n);
printf("%d ", m[i]);
}
printf("\n");
char decryptedtext[100] = "";
for (int i = 0; i < len; i++) {
decryptedtext[i] = m[i];
}
printf("解密后明文:%s\n", decryptedtext);
return 0;
}
```
注意,这只是一个简单的示例程序,实际使用时需要考虑到更多的安全问题,如选择更大的素数、选择更复杂的加密算法等。