精华内容
参与话题
问答
  • ElGamal算法

    2014-10-29 17:16:17
    ElGamal算法既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法。首先选择一个素数p,两个随机数, g 和x,g, x , 计算 y = g^x ( mod p ),则其公钥为 y, g 和p。私钥...
    ElGamal算法既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法。首先选择一个素数p,两个随机数, g 和x,g, x < p, 计算 y = g^x ( mod p ),则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M,首先选择一个随机数k,
     k与 p - 1互质,计算 

    a = g^k ( mod p ) 
    再用扩展 Euclidean 算法对下面方程求解b: 

    M = xa + kb ( mod p - 1 ) 

    签名就是( a, b )。随机数k须丢弃。验证时要验证下式: 

    y^a * a^b ( mod p ) = g^M ( mod p ) 

    同时一定要检验是否满足1<= a < p。否则签名容易伪造。ElGamal用于加密。被加密信息为M,首先选择一个随机数k,k与 p - 1互质,计算 

    a = g^k ( mod p ),b = y^k M ( mod p ) 


    ( a, b )为密文,是明文的两倍长。解密时计算 

    M = b / a^x ( mod p ) 

    ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大,且p-1至少包含一个大素数。因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g,若选取不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张
    展开全文
  • ElGamal公钥密码算法及ElGamal数字签名方案实现

    万次阅读 热门讨论 2018-03-30 15:41:58
    ElGamal公钥密码算法是在密码协议中有着重要应用的一...一、ElGamal公钥密码算法描述 1.选取一个大素数p,使离散对数问题在有限域GF(p)上是难解的,选取g∈Z是一个本原元。 2.随机选取整数x,1≤x≤p-2,计算y=g^x...

    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 <iostream>
    #include <string>
    #include <cstdlib>
    #include <algorithm>//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返回负数,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<<s.values<<endl;
                        temp = s.values;
                        quotient = quotient + c;
                        break;
                    }
                }
            }
        }
        //去除前导零
        quotient.erase(0, quotient.find_first_not_of('0'));
        ret.values = temp;
        ret.flag = true;
        return ret;
    }
    /*
    一个大整数和一个小整数的取余
    
    int divMod(string ch,int num)
    {
        int s=0;
        for(int i=0;ch[i]!='\0';i++)
        s=(s*10+ch[i]-'0')%num;
        return s;
    }*/
    
    /*
    欧几里德求GCD
    */
    BigInt gcd(BigInt a,BigInt b)
    {
        BigInt stemp;
        //cout<<a<<endl;
        //cout<<b<<endl;
        if((a-b).flag==false)//判断大小
        {
            stemp.values=a.values;
            a.values=b.values;
            b.values=stemp.values;
        }
        if(b.values=="0") return a;
        else return gcd(b,a%b);
    }
    /*
    快速幂
    */
    BigInt fast(BigInt a,BigInt b)
    {
        BigInt aa=a,t("1"),k("2");
     //   int b2=atoi(b1[lsize-1].c_str());
        while(b.values!="0")
        {
            if((b%k).values!="0")
            {
                t=t*aa;
            }
            aa=aa*aa;
            b=b/k;
        }
        return t;
    }
    /*
    快速幂模
    */
    BigInt mod_fast(BigInt a,BigInt b,BigInt p)
    {
        BigInt aa=a,t("1"),k("2");
     //   int b2=atoi(b1[lsize-1].c_str());
        while(b.values!="0")
        {
            if((b%k).values!="0")
            {
                t=(t%p)*(aa%p)%p;
            }
            aa=(aa%p)*(aa%p)%p;
            b=b/k;
        }
        return t%p;
    }
    
    /*
    扩展欧几里德实现乘法逆
    */
    BigInt extgcd(BigInt a, BigInt b, BigInt& x, BigInt& y)
    {
        BigInt d(a.values);
    
        if(b.values != "0"){
            d = extgcd(b, a % b, y, x);
            y = y-(a / b) * x;
     //   cout<<"a:"<<a<<endl;
      //  cout<<"b:"<<b<<endl;
      //  cout<<"x:"<<x<<endl;
      //  cout<<"y:"<<y<<endl<<endl<<endl;
        }else {
            x.values = "1";
            y.values = "0";
        }
        return d;
    }
    BigInt mod_inverse(BigInt a, BigInt m)
    {
        BigInt x, y;
        extgcd(a, m, x, y);
        if(x.flag==false)
        {
            x.flag=true;
            x=m-x;
        }
        return (m + x % m) % m;
    }
    
    
    #endif // BIGINT_H_INCLUDED

     

    Main.cpp

     

    #include <iostream>
    #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:"<<endl;
        cin>>m;
        r=mod_fast(g,k,p);
        k1=mod_inverse(k,p-a);
        s=((m-x*r)*k1)%(p-a);
        cout<<"r:"<<r<<endl;
        cout << "s:"<<s << endl;
        cout<<"接下来验证签名------->"<<endl;
        t1=fast(y,r);
        t2=fast(r,s);
        cout << "t1:"<<t1<< endl;
        cout << "t2:"<<t2<< endl;
        if(((t1*t2)%p).values==mod_fast(g,m,p).values)
        {
            cout<<"签名成功!"<<endl;
        }else{
            cout<<"签名失败!"<<endl;
        }
        return 0;
    }

     

     

     

    四、运行结果

     

    展开全文
  • ElGamal加密体制

    千次阅读 2019-03-26 19:56:30
    ElGamal加密体制的公私密钥生成过程如下。 (1)随机选择一个满足安全要求的大素数p,并生成有限域。的一个生成元; (2)选一个随机数x(1<r<p-1),计算,则公钥为(y,g,p),私钥为x。 1.加密过程 与...

    ElGamal加密体制的公私密钥生成过程如下。
    (1)随机选择一个满足安全要求的大素数p,并生成有限域Z_{p}。的一个生成元g\in Z_{p}^{*}
    (2)选一个随机数x(1<r<p-1),计算y\equiv g^{x}(mod\quad p),则公钥为(y,g,p),私钥为x。

    1.加密过程

    与RSA密码体制相同,加密时首先将明文比特串分组,使得每个分组对应的十进制数小于p,即分组长度小于log_{2}p,然后对每个明文分组分别加密。具体过程分为如下几步:
    (1)得到接收方的公钥(y,g,p);
    (2)把消息m分组为长度为L(L<log_{2}p)的消息分组m=m_{1}m_{2}...m_{t}
    (3)对第i块消息(1≤i≤t)随机选择整数r_{i},1<r_{i}<p-1;
    (4)计算c_{i}\equiv g^{r_{i}}(mod \quad p),c_{i}^{'}\equiv m_{i}y^{r_{i}}(mod \quad p)(1\leq i\leq t)
    (5)将密文C=(c_{1},c_{1}^{'})(c_{2},c_{2}^{'})...(c_{t},c_{t}^{'})发送给接收方。

    2.解密过程

    (1)接收方收到的密文C=(c_{1},c_{1}^{'})(c_{2},c_{2}^{'})...(c_{t},c_{t}^{'})
    (2)使用私钥x和解密算法m_{i}\equiv (c_{i}^{'}/c_{i}^{x})(mod \quad p) \quad (1\leq i\leq t)进行计算;
    (3)得到明文m=m_{1}m_{2}...m_{t}

    3.正确性

    下面证明若严格按步骤执行算法,则接收者可以使用私钥和解密算法恢复明文。
    因为
    y\equiv g^{x}(mod\quad p)c_{i}\equiv g^{r_{i}}(mod \quad p),c_{i}^{'}\equiv m_{i}y^{r_{i}}(mod \quad p)

    所以
    (c_{i}^{'}/c_{i}^{x})\equiv (m_{i}y^{r_{i}}/g^{xr_{i}})\equiv (m_{i}g^{xr_{i}}/g^{xr_{i}})\equiv m_{i}(mod \quad p)
    又因为m_{i}< p,故
    (c_{i}^{'}/c_{i}^{x})mod \quad p=m_{i}

    得证。

    ElGamal加密过程需要两次模指数运算和一次模乘积运算,解密过程需要模指数运算,求逆运算和模乘积运算各一次。每次加密运算需要选择一个随机数,所以密文既依赖于明文,又依赖于选择的随机数,故对于同一个明文,不同的时刻生成的密文不同。另外,El-Gamal加密使得消息扩展了两倍,即密文的长度是对应明文长度的两倍。

    展开全文
  • ElGamal加密原理和代码实例

    千次阅读 2019-03-26 21:27:17
    具体原理和证明过程参见ElGamal加密体制,看个例子: 假设发送方为A,接收方为B,B选择素数p=13171,生成元g=2,私钥x=23。A欲用EIGamal算法将消息m=nupt加密为密文C后传送给B。消息m按英文字母表a=00,b=01,…,z...

    具体原理和证明过程参见ElGamal加密体制,看个例子:

    假设发送方为A,接收方为B,B选择素数p=13171,生成元g=2,私钥x=23。A欲用EIGamal算法将消息m=nupt加密为密文C后传送给B。消息m按英文字母表a=00,b=01,…,z=25编码,求加解密过程。

    原题是bupt,我的代码中用的是nuptlovebupt(南邮)。

    #include<bits/stdc++.h>
    #include<time.h>
    using namespace std;
    string e_to_binary(int e)//模指数转二进制数
    {
        string str="";
        int tail=0;
        for(int i=0;i<32;i++)
        {
            int t=(e&1);
            e=e>>1;
            if(t==1)
                str+='1';
            else
                str+='0';
        }
        for(int i=str.size()-1;i>=0;i--)
        {
            if(str[i]!='0')
            {
                tail=i;
                break;
            }
        }
        for(int i=0;i<(1+tail/2);i++)
        {
            char ch=str[i];
            str[i]=str[tail-i];
            str[tail-i]=ch;
        }
        return str.substr(0,tail+1);
    }
    int computation(string e_binary,int m,int n)//加密解密的数学运算
    {
        int c=1;
        for(int i=0;i<e_binary.size();i++)
       {
           c=(c*c)%n;
           if(e_binary[i]=='1')
           {
               c=(c*m)%n;
           }
       }
       return c;
    }
    vector<string> encrypt_message(string message,int g,int y,int p)
    {
        unordered_map<char,string> mapp;
        vector<string> en_message;
        for(char ch='a';ch<='z';ch++)
        {
            mapp[ch]=to_string(ch-'a');
            if(mapp[ch].size()<2)
                mapp[ch]='0'+mapp[ch];
        }
        srand((int)time(NULL));
        for(int i=0;i<message.size();i+=2)
        {
            int r= rand()%(p-1);
            string tmp_str=e_to_binary(r);
            int tmp_num=computation(tmp_str,g,p);
            string tmp_str2=to_string(tmp_num);
            while(tmp_str2.size()<4)
                tmp_str2='0'+tmp_str2;
            en_message.emplace_back(tmp_str2);//en_message+=tmp_str2;
            string tmp_str_m=mapp[message[i]]+mapp[message[i+1]];
            int tmp_num_m=stoi(tmp_str_m);
            tmp_num_m=(tmp_num_m*computation(tmp_str,y,p))%p;
            tmp_str_m=to_string(tmp_num_m);
            while(tmp_str_m.size()<4)
                tmp_str_m='0'+tmp_str_m;
            en_message.emplace_back(tmp_str_m);//en_message+=tmp_str_m;
        }
        return en_message;
    }
    string decrypt_message(vector<string> en_message,int private_key,int p)
    {
        unordered_map<char,string> mapp;
        unordered_map<string,char> mp;
        string de_message="";
        for(char ch='a';ch<='z';ch++)
        {
            mapp[ch]=to_string(ch-'a');
            if(mapp[ch].size()<2)
                mapp[ch]='0'+mapp[ch];
            mp[mapp[ch]]=ch;
        }
        string e_binary=e_to_binary(private_key);
        for(int i=0;i<en_message.size();i+=2)
        {
            string str_c1=en_message[i],str_c2=en_message[i+1];
            int num_c1=stoi(str_c1),num_c2=stoi(str_c2);
            int tmp_num=num_c2%p;
            int tmp_num2=computation(e_binary,num_c1,p);
            for(int i=1;;i++)
            {
                if(i*tmp_num2%p==1)
                {
                    tmp_num2=i;
                    break;
                }
            }
            tmp_num=tmp_num*tmp_num2%p;
            string tmp_str=to_string(tmp_num);
            while(tmp_str.size()<4)
                tmp_str='0'+tmp_str;
            de_message+=mp[tmp_str.substr(0,2)];
            de_message+=mp[tmp_str.substr(2,2)];
        }
        return de_message;
    }
    
    int main()
    {
        int p=13171,g=2,private_key=23;
        string e_binary=e_to_binary(private_key);
        int y=computation(e_binary,g,p);
        string message="nuptlovebupt";
        cout<<"message:"<<message<<endl;
        vector<string> en_message=encrypt_message(message,g,y,p);
        cout<<"en_message:";
        for(int i=0;i<en_message.size();i+=2)
            cout<<"("<<en_message[i]<<","<<en_message[i+1]<<")";
        cout<<endl;
        string de_message=decrypt_message(en_message,private_key,p);
        cout<<"de_message:"<<de_message<<endl;
       return 0;
    }
    

     

    展开全文
  • ElGamal加密算法的理解

    2020-05-08 10:48:12
    原理:求解离散对数是困难的,而其逆运算可以应用平方乘的方法有效的计算出来。...ElGamal加密算法三部分: 密钥生成、加密、解密 密钥生成 利用生成元g产生一个q阶循环群G 从{1,…q-1}中随机选择一个x h=gx ...
  • ElGamal实现加密算法

    千次阅读 2017-10-04 19:38:43
    1.新建一个java项目,里面新建一个java类,加入要...2.ElGamal.java里面的代码如下所示: import java.security.AlgorithmParameterGenerator; import java.security.AlgorithmParameters; import java.security.KeyPa
  • ElGamal加密算法基础到实现详解

    万次阅读 多人点赞 2011-11-26 14:23:08
    先从数学基础开始 ... 群   群是一个集合G,连同一个运算 "·",它结合任何两个元素 a 和 b 而形成另一个元素,记为 a · b。符号 "·" 是对具体给出的运算,比如加法的一般的占位符。要具备成为群的资格,这个...
  • ElGamal

    2010-10-06 17:44:00
    ElGamal算法既能用于数据加密也能用于数字签名,其安全性依赖于计算有限域上离散对数这一难题。  密钥对产生办法。首先选择一个素数p,两个随机数, g 和x,g, x
  • ElGamal签名 加密

    2013-01-06 17:51:54
    ElGamal签名 加密C语言实现
  • 基本思想 ...使用公钥密码的每一个用户都分别拥有两个密钥:加密密钥与解密密钥,它们两者并不相同,并且由加密密钥得到解密密钥在计算上是不可行的。每一个用户的加密密钥都是公开的。 ...两个密钥中的任何一个都可...
  • Elgamal算法的java实现

    千次阅读 2014-04-16 14:32:47
    曾经有位故人请在下帮助做此程序,虽然故人已消失多年,QQ也被其列入黑名单,今天在电脑里偶然发现这个程序代码,分享于大家;望对学习有所帮助!,当初为使故人能够更容易的阅读代码,程序中则以static function的方式进行...
  • ElGamal算法1. 算法概述模型分析 1. 算法概述 ElGamal算法和ECC算法基于离散对数问题建立。与典型非对称加密算法RSA算法相比,ElGamal算法则被称为常用非对称加密算法。 ElGamal既可用于加密,又可用于数字签名,是...
  • 密码学——ELGamal算法

    千次阅读 2019-05-10 19:06:05
    1985年,Tather ElGamal利用ElGamal公钥密码体制设计出ElGamal数字签名方案,该数字签名是经典数字签名方案之一,具有高度的安全性与实用性。后来,ElGamal数字签名体制的变体被使用于数字签名标准DSS中。直到今天,...
  • ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。这篇文章通过示例代码给大家介绍Python实现ElGamal加密算法的相关知识,感兴趣的朋友一起看看吧
  • ELGamal数字签名方案的实现

    千次阅读 2019-03-04 16:08:24
    ELGamal数字签名方案的实现@TOC 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。...
  • ElGamal密码及其安全性证明

    千次阅读 2020-06-05 20:38:26
    ElGamal 在 DDH下的 IND-CPA 安全性 刘宇轩 07111806 1120181352 计算机学院 有关DDH和ElGamal Diffie-Hellman Protocol 有限循环群 G\mathbb{G}G (e.gG=(Zp)∗)\left(e.g\quad G=\left(Z_{p}\right)^{*}\right)(e....
  • Elgamal算法的实现

    2020-06-13 16:43:10
    elgamal算法详解: 选择一个大素数p,取一个p的本原元g,选取私钥x,计算y=g^x(mod p),则公钥为(y,g,p)。采用(B/S来解释) 客户端B过程:客户端B想要和S服务的通讯,于是访问S,得到公钥。 首先需要将消息m进行...
  • ElGamal 算法思考

    2019-09-17 23:09:28
    前驱知识: 离散对数问题 离散对数 百度百科介绍: 在整数中,离散对数(英语:Discrete logarithm)是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 logba是指对于给定的a和b,有一个数x,使得...
  • 使用Elgamal公钥密码系统实现数字签名的程序,程序很小巧。可以自动生成大素数,经测试无误。
  • ElGamal Encryption

    千次阅读 2018-09-28 16:17:10
    T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT–31(4):469– 472, July ...ElGamal Encryption is IND-CPA secure...

空空如也

1 2 3 4 5 ... 20
收藏数 3,391
精华内容 1,356
关键字:

elgamal