RSA加密算法实现

使用了GMP库、

GMP中文手册笔记，大数高精度计算库gmp简介

带你彻底理解RSA算法原理，用gmp库实现rsa加密算法_，一文搞懂RSA算法

RSA加密算法加密整数。对于中文或者字符的话要进行转化，要根据unicode和ASCII编码转化成整数才能够加密。

一些使用的GMP的API函数、

mpz_t
整数（integer）是指高精度整数（multiple precision integer），数据类型mpz_t，是一个动态的类型。还有什么高精度浮点型，高精度有理数型......


void mpz_init (mpz_t x);
对mpz_t类型的变量x初始化值为0（每定义一个mpz_t都需要初始化变量）


void mpz_set (mpz_t rop, const mpz_t op);
用已经初始化的mpz_t变量op给另一个变量rop赋值


int mpz_set_str (mpz_t rop, const char *str, int base);
用一个base进制的字符串给rop变量赋值，base是进制数


void mpz_sub (mpz_t rop, const mpz_t op1, const mpz_t op2);
rop = op1 - op2


void mpz_sub_ui (mpz_t rop, const mpz_t op1, unsigned long op2);
rop = op1 - op2，这个版本多了个ui后缀，表示第二个参数不同，但效果是相同的，下面的函数也是这样。


void mpz_add (mpz_t rop, const mpz_t op1, const mpz_t op2);
rop = op1 + op2


void mpz_mod (mpz_t r, const mpz_t n, const mpz_t d);
r = n % d


void mpz_mul(mpz_t rop, const mpz_t op1, const mpz_t op2);
rop = op1 * op2


void mpz_div (mpz_t rop, const mpz_t op1, const mpz_t op2);
rop = op1 / op2


void mpz_gcd (mpz_t rop, const mpz_t op1, const mpz_t op2);
rop = gcd(op1 , op2)，gcd表示求最大公约数，这里是求op1和op2的最大公约数。可以根据最大公约数求最小公倍数。op1 * op2 = 最大公约数 * 最小公倍数


void mpz_clear (mpz_t x);
释放之前定义的x变量


int mpz_probab_prime_p (const mpz_t n, int reps);
判断n是不是素数，
如果确定是就返回2 ，
如果可能是素数就返回1，
如果不是素数就返回0，
判断误差取决于reps的值，理想的reps值在15-50之间


int mpz_cmp (const mpz_t op1, const mpz_t op2);
判断op1和op2的大小
op1 > op2 : 返回正值
op1 = op2 : 返回0
op1 < op2 : 返回负值


void gmp_randinit_default (gmp_randstate_t state);
在随机生成一个数之前，需要定义一个gmp_randstate_t类型的状态变量，这个函数是对状态变量进行初始化的函数。


void gmp_randseed_ui (gmp_randstate_t state, unsigned long int seed);
初始化状态之后，要给状态变量state设置种子seed


void mpz_urandomb (mpz_t rop, gmp_randstate_t state, mp_bitcnt_t n);
在0~2^n范围内随机生成一个数

void mpz_nextprime (mpz_t rop, const mpz_t op);
生成一个比op大的素数rop。


mpz_invert(op1,op2,op3);
求逆元函数，即数论倒数 op1*op2 mod op3=1；


mpz_powm(op1,op2,op3,op4);
求幂模函数,即op1=op2^op3  mod op4;

RSA算法步骤、

注意：下面的 ^ 代表幂运算，也就是多少次方。

（1）随机找两个质数 P 和 Q ,P 与 Q 越大，越安全。实际使用中的算法是往往是 1024 位（128字节） 或 2048（256字节） 位，位数越长，算法越难被破解。由于c/c++语言内置的数据结构没有这么大位数的整数，所以使用GMP库。目前被破解的最长 RSA 密钥就是 768 位。实际应用中 RSA 的密钥长度为 1024 位，重要场合 2048 位，未来半个世纪不可能破解。

（2）计算 N = P * Q

（3）计算N的欧拉函数，F = (P - 1) * (Q - 1)

（4）随便找一个质数E，条件是 1< E < F，且 E 与 F 互质（公约数只有 1 的两个整数，叫做互质整数）。两个不同的质数一定是互质数，通常选择 3、17、65537作为E的值，用这些值不会对RSA的安全性造成影响，因为解密需要私钥。

（5）计算D的值，E*D=1 mod N。使用逆元运算，即 D = E^-1 mod N。

（6）公钥 = （E，N），私钥 = （D，N）。P，Q，D不能够公开，公钥可以公开。

（7）加密，密文 = 明文^E mod N

（8）解密，明文 = 密文^D mod N

实现、

#include<gmp.h>
using namespace std;
#include<iostream>
#include<unistd.h>

int main(int args,char* argv[],char* envp[])
{

	if(args >= 2 && argv[1]){}
	else
	{
		exit(0);
	}

	FILE* file = fopen(argv[1],"r");
	if(file == nullptr)
	{
		exit(0);
	}


	//设置默认随机状态为跟着时间改变,也就是引入时间随机数种子
	gmp_randstate_t state;
	gmp_randinit_default(state);
	gmp_randseed_ui(state,time(0));

	//创建p，q，并且初始化
	mpz_t key_p,key_q;
	mpz_init(key_p);
	mpz_init(key_q);

	//随机生成1024位的随机数,128字节
	mpz_urandomb(key_p,state,1024);
	mpz_urandomb(key_q,state,1024);


	//获取两个不相同质数p，q
	mpz_nextprime(key_p,key_p);
	mpz_nextprime(key_q,key_q);
	if(mpz_cmp(key_q,key_p) == 0)
	{
		exit(0);
	}


	//计算 n = p*q
	mpz_t key_n;
	mpz_init(key_n);
	mpz_mul(key_n,key_p,key_q);


	//计算 f = (p-1)*(q-1)
	mpz_t key_f;
	mpz_init(key_f);
	mpz_sub_ui(key_p,key_p,1);
	mpz_sub_ui(key_q,key_q,1);
	mpz_mul(key_f,key_p,key_q);


	//计算e,选择65537作为e的值
	mpz_t key_e;
	mpz_init_set_ui(key_e,65537);



	//求d, d = (e^-1) mod ((p-1)*(q-1)),逆元运算
	mpz_t key_d;
	mpz_init(key_d);
	mpz_invert(key_d,key_e,key_f);

        //将公钥，私钥写入到文件里
	FILE* pub = fopen("./public_key","w+");
	if(pub == nullptr)
	{
		exit(0);
	}

	mpz_out_str(pub,10,key_e);
	fwrite("\n",1,1,pub);
	mpz_out_str(pub,10,key_n);

        //将公钥，私钥写入到文件里
	FILE* pri = fopen("./private_key","w+");
	if(pri == nullptr)
	{
		exit(0);
	}

        //参数10是表示十进制写入，也可以使用16进制写入
	mpz_out_str(pri,10,key_d);
	fwrite("\n",1,1,pri);     //写入一个换行符比较容易看懂......
	mpz_out_str(pri,10,key_n);

	fclose(pri);
	fclose(pub);

        //从文件中读取整数数据
	mpz_t text;
	mpz_init(text);
	if(mpz_inp_str(text,file,10)  <= 0)
	{
		exit(0);
	}
        fclose(file);

        //使用专门的输出函数来输出公钥和私钥
	gmp_printf("public key = ( %Zd , %Zd )\n\n",key_e,key_n);
	gmp_printf("private key = ( %Zd , %Zd )\n\n",key_d,key_n);


	gmp_printf("被加密的内容为：%Zd\n\n",text);

	//加密,text = (text^key_e) mod key_n
	mpz_powm(text,text,key_e,key_n);
	gmp_printf("加密成功：%Zd\n\n",text);


	//解密,text = (text^key_d) mod key_n
	mpz_powm(text,text,key_d,key_n);
	gmp_printf("解密成功：%Zd\n\n",text);



        //清理资源
	mpz_clear(text);
	mpz_clear(key_p);
	mpz_clear(key_q);
	mpz_clear(key_n);
	mpz_clear(key_e);
	mpz_clear(key_d);
	mpz_clear(key_f);


	return 0;
}