C语言实现rsa加密

0x00 RSA简介

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

0x01 RSA原理

原文连接

这次轮到RSA加密算法了。RSA加密过程相对DES和MD5要简单很多，但作为现在还在使用的加密算法之一，它还是有需要认真思索的地方哒~

首先是密钥对的生成：

（1）选取两个大素数p和q（目前两个数的长度都接近512bit是安全的）

（2）计算乘积n=p*q，Φ(n)=(p-1)(q-1)，其中Φ(n)为n的欧拉函数（因为两素数乘积的欧拉函数等于两数分别减一后的乘积）

（3）随机选取整数e（1<e<Φ(n)）作为公钥d，要求满足e与Φ(n)的最大公约数为1，即两者互素

（4）用Euclid扩展算法计算私钥d，已满足d * e ≡ 1 (mod Φ(n))，即d ≡ e^(-1) (mod
Φ(n))。则e与n是公钥，d是私钥

注意：e与n应公开，两个素数p和q不再需要，可销毁，但绝不可泄露。

加密过程：

将接收到的明文转换成特定的编码方式。如p=43，q=59，e=13，明文为cybergreatwall，按照英文字母表的顺序a=00，b=01，… ，z=25进行编码后为022401041706001922001111。
现在可以加密了~~ ci ≡ mi^e (mod n)

0x02 中国剩余定理（CRT）

(abc)%n = ((a%n)(b%n)(c%n))%n
使用该定理可有效避免数值溢出。

0x03 C语言代码实现

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

//最大公约数。 
int gcd(int x,int y){
	
	if(y)
		return gcd(y, x%y);
	else
		return x;
}

//求e关于(p-1)(q-1)的逆元d：私钥 
int extend(int e, int fhla){
	for(int d=2; d<fhla; d++){ // 1<d<fhla
		if(e*d%fhla==1){
			return d;
		}
	}
} 

//加密
int c[100]; //用于存储密文 
int len;
void encrypt(int e, int n){
	char plaintext[100];
	printf("请输入明文：");
	scanf("%s", plaintext);
	
	len = strlen(plaintext);//获取输入的明文长度。 
	int ascll[len]; //ascll用于存储明文的ascll转换码
	//将字母转换成ascll编码 
	for(int i=0; i<len; i++) {
		ascll[i] = plaintext[i]; //将字母转换成数字 
	}
	printf("\n") ;
	printf("开始加密--------------------------------------\n");
	int temp = 1;
	for(int i=0; i<len; i++){
		for(int j=0;j<e;j++){
			temp = temp * ascll[i] %n;  //  根据剩余定理 (a*b)%n = ((a%n)*(b%n))%n
		}
		c[i] = temp;
		temp = 1;
	}
	printf("加密的密文为：");
	for(int i=0;i<len;i++){
		printf("%d",c[i]);
	}
	printf("\n加密结束--------------------------------------\n");
}

//解密函数
void decrypto(int d, int n) {
	int de_plaintext[len];
	int temp = 1;
	char de_ascll[len];
	for(int i=0; i<len; i++){
		for(int j=0;j<d;j++){
			temp = temp*c[i]%n;
		}
		de_plaintext[i] = temp;
		temp = 1;
	}
	
	printf("解密开始--------------------------------------\n");
	printf("解密后的符号明文为：");
	for(int i=0;i<len;i++){
		de_ascll[i] = de_plaintext[i];
		printf("%c", de_ascll[i]);
	}
	printf("\n解密结束--------------------------------------\n");			
}

int main(){
	int p,q,e,d,n,flha;
	p = 149;
	q = 211;
	n = p*q;
	flha = (p-1)*(q-1);
	if (gcd(p,q) == 1){
		printf("p,q互质\n"); 
		e = 12493;
		if (gcd(e,flha) == 1){
			printf("e 的选择符合要求\n");
			d = extend(e,flha);
			printf("公钥为：(e,n) = (%d,%d),请公开！\n",e,n);
			printf("密钥为：(d,n) = (%d,%d),不能公开！\n",d,n);
			printf("\n\n--------------------------------------\n");
			encrypt(e,n);
			printf("\n请输入正确的密钥，密钥正确将解密上面的密文:");scanf("%d",&d);
			decrypto(d,n);
		}else
			printf("e 的选择不符合要求\n");
		
	}else
		printf("p,q不是质数！");
		return 0;
}