Elgamal

加密算法

在密码学中，ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法，它在1985年由塔希尔·盖莫尔提出。

算法定义

EIGam以公钥密码是一种国际公认的较理想公钥密码体制，是网络上进行保密通信和数字签名的较有效的安全算法。EIGam以公钥密码体制在网络安全加密技术中应用受到密码学界的广泛关注。

ElGamal算法，是一种较为常见的加密算法，它是基于1985年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，在密码中主要应用离散对数问题的几个性质：求解离散对数（可能）是困难的，而其逆运算指数运算可以应用平方-乘的方法有效地计算。也就是说，在适当的群G中，指数函数是单向函数。

加密算法

ElGamal加密算法由三部分组成：密钥生成、加密和解密。

密钥生成

密钥生成的步骤如下：

Alice利用生成元g产生一个q阶循环群G的有效描述。该循环群需要满足一定的安全性质。

Alice从中随机选择一个 x。

Alice计算。

Alice公开h以及G,q,g的描述作为其公钥，并保留x作为其私钥。私钥保密。

加密

使用Alice的公钥(G,q,g,h)向她加密一条消息m的加密算法工作方式如下：

Bob从随机选择一个y，然后计算。

Bob计算共享秘密。

Bob把他要发送的秘密消息m映射为G上的一个元素m'。

Bob计算。

Bob将密文发送给Alice。

值得注意的是，如果一个人知道了m'，那么它很容易就能知道的值。因此对每一条信息都产生一个新的y可以提高安全性。

解密

利用私钥x对密文进行解密的算法工作方式如下：

Alice计算共享秘密

然后计算，并将其映射回明文 m，其中是s在群G上的逆元。（例如：如果G是整数模n乘法群的一个子群，那么逆元就是模逆元）。

解密算法是能够正确解密出明文的，因为

实际使用

在使用EIGamal加密算法时，模运算是实现公钥密码加解密运算速度的关键，如何提出并实现一个有效的大整数幂模运算算法是实现公钥密码体制的关键，所有使用者可以选取使用同样的素数 p 和生成元，在这种情况下，p不必作为公钥的一部分而发布，这可使公钥的长度小一些。使用固定元素还有另外的优点：可以通过预计算来加快取幂运算，但使用共同系统参数一个潜在的缺点是必须保证模 p足够大。

EIGamal公钥密码是目前国际公认的较理想公钥密码体制，是目前网络上进行保密通信和数字签名的较为有效的算法。ElGamal公钥密码体制在网络安全加密技术中应用得到密码学界的广泛关注。

数字签名方案

在系统中有两个用户A和B，A要发送消息到B，并对发送的消息进行签名。B收到A发送的消息和签名后进行验证。

系统初始化

选取一个大的素数p，g是GF(p)的生成元。h：GF(p)→GF(p)，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。

数字签名

假定用户A要向B发送消息，并对消息m签名。

第一步：用户A选取一个作为秘密密钥，计算作为公钥。将公钥y存放于公用的文件中。

第二步：随机选取且.

第三步：计算，及.

第四步：A将发送到B。

签名验证

B接收到A发送的消息，从系统公开文件和A的公开文件中获得系统公用参数p，g，h和A的公钥y。

第一步：B计算.

第二步：B计算.

第三步：比较left和right，相等则通过验证。

算法分析

效率分析

ElGamal公钥密码算法的加密效率相对于其它公钥密码来说是比较慢的，下面对其进行分析。

(1)加密过程需要两次模指数运算，即和；通过选取具有某种附加结构的随机指数可加速指数运算，在计算过程中，可以使用一些幂算的乘方等一些算法，也可以对固定的代数结构，制定相应的幂运算表，使得计算起来比较简单，加密、解密的速度比较快，从而使信息传递的速度加快；

(2)ElGamal加密算法的一个缺点是传递密文的长度是明文长度的二倍，使得传递密文的过程中，通信的信息量增大。同时ElGamal加密算法一个最大的特点是在加密过程中进行随机方式的加密方法，这种方法有着很好的抗攻击性，可以用以下一个或多个方法随机增加加密过程的密码安全性。

1.增加明文消息空间的长度，即增加所选代数结构中的元素个数；

2.通过一个到多个的明文到密文的映射来减小选择明文攻击的有效性；

3.通过统计先验概率分布的方法来减小统计攻击的有效性。

安全分析

关于EIGamal加密的安全性分析，通常都从两个方面考虑加密体制的安全性，安全目标和攻击者的类型。

加密的安全目标一般看下面两个：不可区分性(IND)：敌手选择两个明文，加密者随机选取一个，返回其密文，则敌手不能以明显大于1/2的概率正确猜测选择的是哪一个明文。语义安全性(SEM)：敌手在知道密文的条件下能有效计算出的有关明文的信息量并不比他不知道密文时的多，除了明文的长度。

密码体制的安全性是主要是根据攻击来定义的，攻击可分为被动攻击和主动攻击，其中被动攻击，敌手只是监视通信信道，阻止信息传输在通信信道上传输，被攻击者只能威胁数据的机密性；主动攻击，敌方企图删除、增加或以其他方式改变信道上的传输内容，它会威胁数据的完整性、认证性及机密性，主动攻击的方法通常分为以下几种：

(1)选择明文攻击(CPA)：攻击者选择明文消息并得到加密的服务，产生相应的密文，攻击者的任务是利用所得到的明文．密文对来降低目标密码体制的安全性；

ElGamal加密体制具有选择明文攻击下的不可区分性(IND-CPA)，当且仅当计算Diffie-Hellman问题是困难的。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省