先講一下ElGamal 密碼體制：
公開全局量
q 素?cái)?shù)
a a<q且a是q的素根
Alice 生成的密鑰
選擇私鑰XA XA<q-1
計(jì)算YA YA=a^XA mod q
公開密鑰 {q，a，YA}
Box用Alice的公鑰加密
明文 M
隨機(jī)選擇整數(shù)k k<q
計(jì)算K K=(YA)^k mod q
計(jì)算c1 c1=a^k mod q
計(jì)算c2 c2=KM mod q
密文 （c1，c2）
用Alice的私鑰解密
密文 M
計(jì)算K K=（c1）^XA mod q
明文 M=（c2*K^(-1)） mod q
思路根據(jù)以上，直接貼代碼（有點(diǎn)長，不好的地方多多包涵和指出~）
#include<gmpxx.h>
#include<gmp.h>
#include<iostream>
#include<cmath>
#include<time.h>
using namespace std;
//快速冪取模運(yùn)算。簡單參考另一篇文章用大數(shù)實(shí)現(xiàn)RSA選擇密文攻擊（可以直接用gmp庫的函數(shù)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)//當(dāng)指數(shù)為1時(shí)，得出結(jié)果
{
remainder=(temp*b)%n;
return remainder;//返回結(jié)果
}
else if(e%2==0)//如果指數(shù)為偶數(shù)，將底數(shù)平方取模，指數(shù)除2
{
e=e/2;
b=(b*b)%n;
}
else if(e%2==1)//如果指數(shù)為奇數(shù)，先提取一個(gè)底數(shù)相乘并取模，指數(shù)減1
{
temp=(b*temp)%n;
e=e-1;
}
}
}
在素?cái)?shù)域中求乘法逆元。
mpz_class exgcd(mpz_class x,mpz_class q)//拓展歐幾里德算法(輾轉(zhuǎn)相除法)在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沒有什么作用，應(yīng)該可以去掉？懶得改了
{
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個(gè)生成元
return;
}
}
//隨機(jī)素?cái)?shù)的生成
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<<"輸入大數(shù)比特?cái)?shù):";
cin>>bits;
q=randprime(bits);
cout<<"素?cái)?shù)q:"<<q<<endl;
cout<<"生成元:";
Gfun((q-1)/2,q);
cout<<"\n請輸入q的素根a：";
cin>>a;
srand(time(0));
XA=rand()%(q-2)+2;//隨機(jī)產(chǎn)生一個(gè)2~q-1的數(shù)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;//隨機(jī)產(chǎn)生一個(gè)1~q-1的數(shù)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可能不會這么長（？），但是我習(xí)慣用mpz_class，因?yàn)槿菀桌斫猓?。寫得不好或者有誤歡迎指正，不過我可能會沒聽懂你的指正，菜鳥一枚~
