C/C++使用GMP库实现Paillier加密和解密，中国剩余定理(CRT)加速解密过程对比。＜三＞_使用中国剩余定理优化paillier

1、如何实现C语言使用GMP库实现Paillier加密，详看本篇文章，链接如下：

C/C++语言使用GMP大数运算库实现Paillier算法_Paidx.的博客-CSDN博客_c++ gmp

2、中国剩余定理在Paillier中的作用。

        想要使用中国剩余定理，则需要提前知道p,q的值，如果不知道p,q的值则不能够使用中国剩余定理进行加速解密的过程。大数的模幂运算在计算机中是耗时的，如果使用硬算的方法则会消耗大量时间，如果使用中国剩余定理进行优化则会提高解密效率。

        按照Paillier算法的要求进行加密，得到密文c，需要进行下面的数学原理进行划分：

 上述中的CRT(m_p,m_q) mod pq如何进行计算呢，请看下述讲解。

3、计算CRT(m_p,m_q) mod pq

 对于第二步中计算的m_q,m_p直接带入第三步最后一步的推到即可，即带入如下方程：

 4、可能会遇到的计算问题。

        （1）求乘法逆元

                调用GMP库中的gmp_invert()函数能够直接求出来。

                想要理解乘法逆元的概念，要先想想倒数的概念，3 * =1。举个例子：

                求3 *  mod 5 的结果？？？

                此时显然是不能直接求得，需要先mod 5的乘法逆元，设乘法逆元为x，通过倒数的理解我们知道x 和在mod 5 的情况下同于于1。此时你直接看成 2 是一样的。计算x * 2 mod 5 =1，就可以知道x是多少了，显然x取3。这个是咱们手算，使用gmp_invert()方法咋求呢，该方法一共三个参数展示如下gmp_invert(result，2，5)，第一个坑位放求得的逆元值，第二个坑是你求谁的逆元，第三个是mod谁。

        （2）第二步的L_p是一个函数。

                这个地方直接把数带进去计算就可以了，可以直接算乘法，应为是能够整除的。 

                但是h_p那个地方那个-1操作不能直接除法做，要求逆元，因为后面是mod一个数，可以直接求出一个逆元，不能看做是除法。就是如下展示的地方，不能看做除法，要用gmp_invert()来求逆元。

 5、使用常规方法（硬算）进行解密得到的时间：65ms

 6、使用中国剩余定理解密得到的时间：20ms

 7、常规解密的代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<gmpxx.h>
#include<gmp.h>
#include<iostream>
#include<time.h>
 
int main(){
	 //设置随机数种子
	 clock_t time=clock();
	 gmp_randstate_t grt;
	 gmp_randinit_default(grt); 
	 gmp_randseed_ui(grt, time); 
	 
	 //p、q初始化
	 mpz_t p,q,p1,q1;
 
	 mpz_init(p); 
	 mpz_init(q);
	 mpz_init(p1); 
	 mpz_init(q1);
	 
	 //p、q的的范围在0~2^128-1
	 mpz_urandomb(p, grt, 128);
	 mpz_urandomb(q, grt, 128);
 
	  //生成p,q大素数
	 mpz_nextprime(p, p); 
	 mpz_nextprime(q, q);
	 
	 //判断生成的是否是素数得到的结果为2则确定为大素数
	 int su1,su2;//如果为1则在判断次数内大概率确定是大素数，为0则不是
	 su1=mpz_probab_prime_p(p,10);
	 su2=mpz_probab_prime_p(q,10);
	 //printf("判断生成的是否是素数 :p=%d   q=%d\n",su1,su2);
	 //求p，q的乘积 n,以及n的平方n2
	 mpz_t n,n2;
 
	 mpz_init(n);
	 mpz_init(n2);
	 mpz_mul(n,p,q); 
	 mpz_mul(n2,n,n); 
	 
	 //设置g,取值g=n+1
	 mpz_t g,j;
 
	 mpz_init(g);
	 mpz_init_set_ui(j,1);
	 //mpz_urandomb(g, grt, 128);
	 mpz_add(g,n,j);
 
	 //设置明文m
	 mpz_t m;
	 mpz_init_set_str(m,"123456",10);
	 mpz_t r;//设置r,r为随机数
	 mpz_urandomb(r, grt, 128);
 
	 //设置密文c
	 mpz_t c;
 
	 mpz_init(c);
	 //设置密文c
 
	 mpz_powm(c,g,m,n2);
	 mpz_powm(r,r,n,n2);
	 mpz_mul(c,c,r);
	 mpz_mod(c,c,n2);
 
	 //解密过程
	 //先求λ，是p、q的最小公倍数,y3代表λ
	 mpz_t y1,y2,y3;
 
	 mpz_init(y1);
	 mpz_init(y2);
	 mpz_init(y3);
	 
	 mpz_sub(p1,p,j);
	 mpz_sub(q1,q,j);
	 mpz_lcm(y3,p1,q1);//y3代表λ
	 
	 //输出明文m,g
	 //十进制输出是%Zd,十六进制输出是%ZX,folat使用&Ff
	 gmp_printf("明文m = %Zd\n\n", m);
	 //gmp_printf("p = %Zd\n\n", p);
	 //gmp_printf("q = %Zd\n\n", q);
	 //gmp_printf("r = %Zd\n\n", r);
	 //gmp_printf("g = %Zd\n\n", g);
	 //gmp_printf("λ = %Zd\n\n", y3);
	 //输出密文
	 gmp_printf("密文c = %Zd\n\n",c);
	 
	 clock_t start, finish;
	 start = clock();
	 //y1代表c的λ次方摸n平方
	 mpz_powm(y1,c,y3,n2);
	 mpz_sub(y1,y1,j);
	 mpz_div(y1,y1,n);
	 
	 //y2代表g的λ次方摸n平方
	 mpz_powm(y2,g,y3,n2);
	 mpz_sub(y2,y2,j);
	 mpz_div(y2,y2,n);
	 
	 mpz_t x_y;
	 mpz_init(x_y);
	 mpz_invert(x_y,y2,n);//至关重要的一步，取逆
	 
	 mpz_mul(x_y,x_y,y1);
	 mpz_mod(x_y,x_y,n);
	 
	 finish = clock();
	 printf("time is :%fms\n",(double)(finish - start));
	 //输出明文
	 gmp_printf("解密得到明文m = %Zd\n\n",x_y);
	 mpz_clear(p);
	 mpz_clear(q);
	 mpz_clear(n);
	 mpz_clear(n2);
	 mpz_clear(p1);
	 mpz_clear(q1);
	 mpz_clear(c);
	 mpz_clear(g);
	 mpz_clear(j);
	 mpz_clear(r);
	 mpz_clear(m);
	 mpz_clear(y2);
	 mpz_clear(y1);
	 mpz_clear(y3);
	 mpz_clear(x_y);
	 
	 return 0;
}

8、使用中国剩余定理解密的代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<gmpxx.h>
#include<gmp.h>
#include<iostream>
#include<time.h>
 
//g++ test_1.c -o test1 -lgmp -lm
//./test1
 
int main(){
	 //设置随机数种子
	 clock_t time=clock();
	 gmp_randstate_t grt;
	 gmp_randinit_default(grt); 
	 gmp_randseed_ui(grt, time); 
	 
	 //p、q初始化
	 mpz_t p,q,p1,q1;
 
	 mpz_init(p); 
	 mpz_init(q);
	 mpz_init(p1); 
	 mpz_init(q1);
	 
	 //p、q的的范围在0~2^128-1
	 mpz_urandomb(p, grt, 128);
	 mpz_urandomb(q, grt, 128);
 
	  //生成p,q大素数
	 mpz_nextprime(p, p); 
	 mpz_nextprime(q, q);
	 
	 //求p，q的乘积 n,以及n的平方n2
	 mpz_t n,n2;
 
	 mpz_init(n);
	 mpz_init(n2);
	 mpz_mul(n,p,q); 
	 mpz_mul(n2,n,n); 
	 
	 //设置g,取值g=n+1
	 mpz_t g,j;
 
	 mpz_init(g);
	 mpz_init_set_ui(j,1);
	 mpz_add(g,n,j);
 
	 //设置明文m
	 mpz_t m;
	 mpz_init_set_str(m,"123456",10);
	 mpz_t r;//设置r,r为随机数
	 mpz_urandomb(r, grt, 128);
 
	 //设置密文c,c1,需要对这两个密文做同态加法
	 mpz_t c;
 
	 mpz_init(c);
	 //设置密文c
 
	 mpz_powm(c,g,m,n2);
	 mpz_powm(r,r,n,n2);
	 mpz_mul(c,c,r);
	 mpz_mod(c,c,n2);	 
	 //输出密文
	 gmp_printf("明文m = %Zd\n\n", m);
	 gmp_printf("密文c = %Zd\n\n",c);	 
	 
	 //中国剩余定理做paillier
	 mpz_sub(p1,p,j);
	 mpz_sub(q1,q,j);
	 mpz_t m_p,m_q,p_2,q_2,mp_y1,mp_y2,mq_y1,mq_y2,p_ni,q_ni,q_p;
	 mpz_init(m_p);
	 mpz_init(q_p);
	 mpz_init(p_ni);
	 mpz_init(q_ni);
	 mpz_init(m_q);
	 mpz_init(p_2);
	 mpz_init(q_2);
	 mpz_init(mp_y1);
	 mpz_init(mp_y2);
	 mpz_init(mq_y1);
	 mpz_init(mq_y2);
	 
	 mpz_mul(p_2,p,p);
	 mpz_mul(q_2,q,q);
	 mpz_invert(p_ni,p,p);
	 mpz_invert(q_ni,q,q);
	 
	 //count time 
	 clock_t start, finish;
	 start = clock();
	 //m_p
	 mpz_powm(mp_y1,c,p1,p_2);
	 mpz_sub(mp_y1,mp_y1,j);
	 mpz_div(mp_y1,mp_y1,p);
	 
	 mpz_powm(mp_y2,g,p1,p_2);
	 mpz_sub(mp_y2,mp_y2,j);
	 mpz_div(mp_y2,mp_y2,p);
	 mpz_invert(mp_y2,mp_y2,p);
	 mpz_mod(mp_y2,mp_y2,p);
	 mpz_mul(mp_y1,mp_y1,mp_y2);
	 mpz_mod(m_p,mp_y1,p);
	 
	 //m_q
	 mpz_powm(mq_y1,c,q1,q_2);
	 mpz_sub(mq_y1,mq_y1,j);
	 mpz_div(mq_y1,mq_y1,q);
	 
	 mpz_powm(mq_y2,g,q1,q_2);
	 mpz_sub(mq_y2,mq_y2,j);
	 mpz_div(mq_y2,mq_y2,q);
	 mpz_invert(mq_y2,mq_y2,q);
	 mpz_mod(mq_y2,mq_y2,q);
	 mpz_mul(mq_y1,mq_y1,mq_y2);
	 mpz_mod(m_q,mq_y1,q);
	 
	 //CRT
	 mpz_t p_q,result;
	 mpz_init(p_q);
	 mpz_init(result);
	 
	 mpz_sub(p_q,m_q,m_p);
	 mpz_mul(p_q,p_q,p_ni);
	 mpz_mod(p_q,p_q,q);
	 mpz_mul(p_q,p_q,p);
	 mpz_add(result,m_p,p_q);
	  
	 finish = clock();
	 printf("time is :%fms\n",(double)(finish - start));
	 gmp_printf("解密得到明文m = %Zd\n\n",result);
	 
	 return 0;
}