ElGamal加密与解密——gmp库c++实现

先讲一下ElGamal 密码体制：

公开全局量
q    素数
a    a<q且a是q的素根

Alice 生成的密钥
选择私钥XA    XA<q-1
计算YA        YA=a^XA mod q
公开密钥      {q，a，YA}

Box用Alice的公钥加密
明文          M
随机选择整数k   k<q
计算K     K=(YA)^k mod q
计算c1   c1=a^k mod q
计算c2   c2=KM mod q
密文     （c1，c2）

用Alice的私钥解密
密文     M
计算K   K=（c1）^XA mod q
明文    M=（c2*K^(-1)） mod q

思路根据以上，直接贴代码（有点长，不好的地方多多包涵和指出~）

#include<gmpxx.h>
#include<gmp.h>
#include<iostream>
#include<cmath>
#include<time.h>
using namespace std;

//快速幂取模运算。简单参考另一篇文章用大数实现RSA选择密文攻击（可以直接用gmp库的函数mpz_powm()）
mpz_class fun(const mpz_class exponent,const mpz_class base,const mpz_class n)//base^exponent%n
{  
     mpz_class e,b,temp=1,remainder=0;  
     e=exponent;b=base;
     while(e>=1)
      {
          if(e==1)//当指数为1时，得出结果
            { 
               remainder=(temp*b)%n;
               return remainder;//返回结果
            }
           else if(e%2==0)//如果指数为偶数，将底数平方取模，指数除2
             {
               e=e/2;
               b=(b*b)%n;
             }
           else if(e%2==1)//如果指数为奇数，先提取一个底数相乘并取模，指数减1
             {
               temp=(b*temp)%n;
               e=e-1;
             }
      }  
 }  

在素数域中求乘法逆元。

mpz_class exgcd(mpz_class x,mpz_class q)//拓展欧几里德算法(辗转相除法)在GF(q)中求乘法逆元x^(-1)
{
    mpz_class r,d,t1,t2;
    mpz_class a1=1,a2=0,a3=q;//GF(p)的加法和乘法单位元分别是0和1
    mpz_class b1=0,b2=1,b3=x;
    while(1)
     {
       if(b3==0)
          cout<<"error"<<endl;
       if(b3==1)
          break;
       d=a3/b3;
       r=a3-d*b3;
       t1=a1-d*b1;
       t2=a2-d*b2;
       a3=b3;
       b3=r;
       a1=b1;
       b1=t1;
       a2=b2;
       b2=t2;
     }
   return (b2+q)%q;
}

有限域生成元的寻找方法，思路写得较简单。在此附上别人的博客链接，希望可以帮助看懂。（http://guoreason.blog.163.com/blog/static/234587682007159432178/）

void Gfun(mpz_class q,mpz_class p)//好像q没有什么作用，应该可以去掉？懒得改了 
{
     mpz_class i,count=0;
     for(i=2;i<p-1;i++)
        if((i*i%p!=1)&&fun((p-1)/2,i,p)!=1)//a^2 mod p和a^(q-1)/2 mod p，如它们都不等于1，则a是生成元
           {
            cout<<i<<",";
            count=count+1;
            if(count==10)//在这里我只需输出10个生成元
                return;
            }
}

//随机素数的生成
mpz_class randbits(int bits)//base=2
{
    gmp_randclass a(gmp_randinit_default);
    a.seed(rand());
    mpz_class l(bits);
    return a.get_z_bits(l);
}
inline mpz_class randprime(int bits)
{
    mpz_class a=randbits(bits);
    mpz_class ret;
    mpz_nextprime(ret.get_mpz_t(),a.get_mpz_t());
    return ret;
}

int main()
{
   mpz_class q,a,XA,YA,M,k,K,c1,c2;
   int bits;
   cout<<"输入大数比特数:";
   cin>>bits;
   q=randprime(bits);
   cout<<"素数q:"<<q<<endl;
   cout<<"生成元:";
   Gfun((q-1)/2,q);
   cout<<"\n请输入q的素根a：";
   cin>>a;
   srand(time(0));
   XA=rand()%(q-2)+2;//随机产生一个2~q-1的数XA私钥
   YA=fun(XA,a,q);//YA=a^XA mod q  //公钥{q,a,YA}
   cout<<"请输入明文M(M<q)：";
   cin>>M;
   while(M>=q)
    {
       cout<<"error!\n请重新输入明文M:";
       cin>>M;
     }
   //加密算法
   k=rand()%(q-1)+1;//随机产生一个1~q-1的数k
   K=fun(k,YA,q);//K=YA^k mod q
   c1=fun(k,a,q);//c1=a^k mod q
   c2=(K*M)%q;//c2=K*M mod q
   cout<<"加密后的密文为:("<<c1<<" , "<<c2<<")"<<endl;
   //解密算法
   K=fun(XA,c1,q);//K=c1^XA mod q
   cout<<"解密后的明文为:"<<(c2*exgcd(K,q))%q<<endl;//M=(c2*K^(-1)) mod q
   return 0;
}

终端命令

g++ ElGamal.cpp -o ElGamal -lgmp -lgmpxx -lm 
./ElGamal

代码有些长（不是一般的长？），用mpz_t可能不会这么长（？），但是我习惯用mpz_class，因为容易理解，哈哈哈。写得不好或者有误欢迎指正，不过我可能会没听懂你的指正，菜鸟一枚~