ElGamal公钥密码算法及ElGamal数字签名方案实现

ElGamal公钥密码算法是在密码协议中有着重要应用的一类公钥密码算法，其安全性是基于有限域上离散对数学问题的难解性。它至今仍是一个安全性良好的公钥密码算法。它既可用于加密又可用于数字签名的公钥密码体制。

一、ElGamal公钥密码算法描述

1. 选取一个大素数p，使离散对数问题在有限域GF(p)上是难解的，选取g∈Z是一个本原元。

2. 随机选取整数x，1≤x≤p-2,计算y=g^x(mod p); y是公开的加密密钥，而x是保密的脱密密钥。

3. 明文空间为Z，密文空间为Z×Z。

4. 加密变换：对任意明文m∈Z，秘密地随机选取一个整数k，1≤k≤p-2，于是可得密文为：

c=(c1,c2)

其中

c1=g^k(mod p) , c2=my^k(mod p)

5. 脱密变换：对任意密文c=(c1,c2)∈Z×Z，明文为：

m=c2×(c1^x)^-1(mod p)

证明：

c2×(c1^x)^-1(mod p)=my^k(g^(kx))^-1 (mod p)

=mg^kx × g^(-kx) (mod p)=m (mod p)

二、ElGamal数字签名方案

1. 生成乘法群Z中的一个生成元g，p,g公开。

2. 随机选取整数x，1≤x≤p-2,计算y=g^x(mod p)，y是公开密钥，而x是保密密钥。

3. 签名算法：设m∈Z是待签名的消息，秘密随机选取一个整数k，1≤k≤p-2，且(k,p-1)=1，计算

r=g^k(mod p)

s=k^-1(m-rx)(mod p-1)

则(m,r,s)为对消息m的数字签名。

4. 验证算法：对方收到对消息m的数字签名(m,r,s)后，利用签名者的公开密钥y,g,p可对签名进行以下验证：

(y^r)(r^s)=g^m(mod p)

如果上式成立，则接受该签名，否则拒绝该签名。

对m正确签名，那么有：

(y^r)(r^s)(mod p)=g^(rx+sk)(mod p)

=g^(rx+m-rx)(mod p)

=g^m (mod p)

三、ElGamal数字签名方案实现

为简化问题，我们取p=19,g=2,私钥x=9,则公钥y=29 mod 19=18。C++代码实现如下：

BigInt.h

#ifndef BIGINT_H_INCLUDED #define BIGINT_H_INCLUDED #include 
  
    #include 
   
     #include 
    
      #include 
     
       //reverse函数所需添加的头文件 using namespace std; /* 大整数类 */ class BigInt { private: inline int compare(string s1, string s2) { if(s1.size() < s2.size()) return -1; else if(s1.size() > s2.size()) return 1; else return s1.compare(s2); } public: bool flag;//true表示正数，false表示负数，0默认为正数 string values;//保存所有位上的数字 BigInt():values("0"),flag(true){};//构造函数 BigInt(string str)//类型转换构造函数(默认为正整数) { values = str; flag = true; } public: friend ostream& operator << (ostream& os, const BigInt& bigInt);//重载输出操作符 friend istream& operator>>(istream& is, BigInt& bigInt);//输入操作符重载 BigInt operator+(const BigInt& rhs);//加法操作重载 BigInt operator-(const BigInt& rhs);//减法操作重载 BigInt operator*(const BigInt& rhs);//乘法操作重载 BigInt operator/(const BigInt& rhs);//除法操作重载 BigInt operator%(const BigInt& rhs);//求余操作重载 }; /* 重载流提取运算符'>>'，输出一个整数 */ ostream& operator << (ostream& os, const BigInt& bigInt) { if (!bigInt.flag) { os << '-'; } os << bigInt.values; return os; } /* 重载流插入运算符'>>'，输入一个正整数 */ istream& operator >> (istream& is, BigInt& bigInt) { string str; is >> str; bigInt.values = str; bigInt.flag = true; return is; } /* 两个正整数相加 */ BigInt BigInt::operator+(const BigInt& rhs) { BigInt ret; ret.flag = true;//正整数相加恒为正数 string lvalues(values), rvalues(rhs.values); //处理特殊情况 if (lvalues == "0") { ret.values = rvalues; return ret; } if (rvalues == "0") { ret.values = lvalues; return ret; } //调整s1与s2的长度 unsigned int i, lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); if (lsize < rsize) { for (i = 0; i < rsize - lsize; i++)//在lvalues左边补零 { lvalues = "0" + lvalues; } } else { for (i = 0; i < lsize - rsize; i++)//在rvalues左边补零 { rvalues = "0" + rvalues; } } //处理本质情况 int n1, n2; n2 = 0; lsize = lvalues.size(); string res = ""; reverse(lvalues.begin(), lvalues.end());//颠倒字符串，以方便从低位算起计算 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < lsize; i++) { n1 = (lvalues[i] - '0' + rvalues[i] - '0' + n2) % 10;//n1代表当前位的值 n2 = (lvalues[i] - '0' + rvalues[i] - '0' + n2) / 10;//n2代表进位 res = res + char(n1 + '0'); } if (n2 == 1) { res = res + "1"; } reverse(res.begin(), res.end()); ret.values = res; return ret; } /* 两个正整数相减 */ BigInt BigInt::operator-(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); //负数减负数 if(flag==false&&rhs.flag==false) { string tmp = lvalues; lvalues = rvalues; rvalues = tmp; } //负数减正数 if(flag==false&&rhs.flag==true) { BigInt res(lvalues); ret=res+rhs; ret.flag = false; return ret; } if(flag==true&&rhs.flag==false) { BigInt rel(lvalues),res(rhs.values); ret=rel+res; ret.flag = true; return ret; } //处理特殊情况 if (rvalues == "0") { ret.values = lvalues; ret.flag = true; return ret; } if (lvalues == "0") { ret.values = rvalues; ret.flag = false; return ret; } //调整s1与s2的长度 unsigned int i, lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); if (lsize < rsize) { for (i = 0; i < rsize - lsize; i++)//在lvalues左边补零 { lvalues = "0" + lvalues; } } else { for (i = 0; i < lsize - rsize; i++)//在rvalues左边补零 { rvalues = "0" + rvalues; } } //调整使‘-’号前边的数大于后边的数 int t = lvalues.compare(rvalues);//相等返回0，str1 
      
        str2返回正数 if (t < 0) { ret.flag = false; string tmp = lvalues; lvalues = rvalues; rvalues = tmp; } else if (t == 0) { ret.values = "0"; ret.flag = true; return ret; } else { ret.flag = true; } //处理本质情况 unsigned int j; lsize = lvalues.size(); string res = ""; reverse(lvalues.begin(), lvalues.end());//颠倒字符串，以方便从低位算起计算 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < lsize; i++) { if (lvalues[i] < rvalues[i])//不足，向前借一维 { j = 1; while(lvalues[i+j] == '0') { lvalues[i+j] = '9'; j++; } lvalues[i+j] -= 1; res = res + char(lvalues[i] + ':' - rvalues[i]); } else { res = res + char(lvalues[i] - rvalues[i] + '0'); } } reverse(res.begin(), res.end()); res.erase(0, res.find_first_not_of('0'));//去掉前导零 ret.values = res; return ret; } /* 两个正整数相乘 */ BigInt BigInt::operator*(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); //处理0或结果正负 if (lvalues == "0" || rvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(flag==false||rhs.flag==false) { ret.flag=false; } //处理特殊情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); string temp; BigInt res, itemp; //让lvalues的长度最长 if (lvalues < rvalues) { temp = lvalues; lvalues = rvalues; rvalues = temp; lsize = lvalues.size(); rsize = rvalues.size(); } //处理本质情况 int i, j, n1, n2, n3, t; reverse(lvalues.begin(), lvalues.end());//颠倒字符串 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < rsize; i++) { temp = ""; n1 = n2 = n3 = 0; for (j = 0; j < i; j++) { temp = temp + "0"; } n3 = rvalues[i] - '0'; for (j = 0; j < lsize; j++) { t = (n3*(lvalues[j] - '0') + n2); n1 = t % 10;//n1记录当前位置的值 n2 = t / 10;//n2记录进位的值 temp = temp + char(n1 + '0'); } if (n2) { temp = temp + char(n2 + '0'); } reverse(temp.begin(), temp.end()); itemp.values = temp; res = res + itemp; } ret.values = res.values; return ret; } /* 两个正整数相除 */ BigInt BigInt::operator/(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); string quotient; string temp; //处理特殊情况 if(rvalues == "0") { ret.values = "error";//输出错误 ret.flag = true; return ret; } if(lvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(compare(lvalues, rvalues) < 0) { ret.values = "0"; ret.flag = true; return ret; } else if(compare(lvalues, rvalues) == 0) { ret.values = "1"; ret.flag = true; return ret; } else { //处理本质情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); int i; if(rsize > 1) temp.append(lvalues, 0, rsize-1); for(i = rsize - 1; i < lsize; i++) { temp = temp + lvalues[i]; //试商 for(char c = '9'; c >= '0'; c--) { BigInt t = (BigInt)rvalues * (BigInt)string(1, c); BigInt s = (BigInt)temp - t; if(s.flag == true) { temp = s.values; quotient = quotient + c; break; } } } } //去除前导零 quotient.erase(0, quotient.find_first_not_of('0')); ret.values = quotient; ret.flag = true; return ret; } /* 两个正整数取余 */ BigInt BigInt::operator%(const BigInt& rhs) { BigInt ret,kj(values),ki(rhs.values); string lvalues(values), rvalues(rhs.values); string quotient; string temp; //处理特殊情况 if(rvalues == "0") { ret.values = "error";//输出错误 ret.flag = true; return ret; } if(lvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(compare(lvalues, rvalues) < 0) { if(flag==false) { ret.values=(ki-kj).values; ret.flag = true; return ret; }else{ ret.values = lvalues; ret.flag = true; return ret; } } else if(compare(lvalues, rvalues) == 0) { ret.values = "0"; ret.flag = true; return ret; } else { //处理本质情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); int i; if(rsize > 1) temp.append(lvalues, 0, rsize-1); for(i = rsize - 1; i < lsize; i++) { if(temp=="0"){ temp=lvalues[i]; }else{ temp = temp + lvalues[i]; } //试商 for(char c = '9'; c >= '0'; c--) { BigInt t = (BigInt)rvalues * (BigInt)string(1, c); BigInt s = (BigInt)temp - t; if(s.flag == true) { //cout< 
        
       
      
     
    
  

Main.cpp

#include 
  
    #include"BigInt.h" using namespace std; int main() { /* 公开密钥y,g,p */ BigInt p("19"),g("2"),x("9"),y("18"),a("1"); BigInt k("5"),s,r,m,k1; BigInt t1,t2; cout<<"请输入m："< 
   
     >m; r=mod_fast(g,k,p); k1=mod_inverse(k,p-a); s=((m-x*r)*k1)%(p-a); cout<<"r:"< 
    
      "< 
      
     
    
  

四、运行结果