简述ElGamal加密算法

简述ElGamal加密算法

ElGamal加密算法是由塔希尔·盖莫尔（Tather ElGamal）在1985年提出的一个基于迪菲-赫尔曼密钥（D-H）交换的非对称加密算法。它是一种基于离散对数难题的加密体系，与RSA算法一样，都能用于数据加密和数据签名。

什么是ElGamal加密算法？

ElGamal加密算法是由塔希尔·盖莫尔（Tather ElGamal）在1985年提出的一个基于迪菲-赫尔曼密钥（D-H）交换的非对称加密算法。它是一种基于离散对数难题的加密体系，与RSA算法一样，都能用于数据加密和数据签名。但是两者的原理不一样，ElGamal算法基于离散对数问题，而RSA算法基于大素数分解困难问题。

与RSA算法相比，ElGamal算法的特点就是，哪怕是使用相同的私钥，对相同的明文进行加密，每次加密后得到的签名也各不相同，有效的防止了网络中可能出现的重放攻击。

ElGamal加密算法的原理

ElGamal密钥生成

1. 随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。
2. 随机选择一个整数d作为密钥，2≤d≤p-2 。
3. 计算y=α^d mod p，取y为公钥。

ElGamal加密

1. 对于明文M加密，随机地选取一个整数k，2≤k≤p-2
2. C1＝α^k mod p
3. C2＝MY^k mod p
4. 密文为（C1,C2）

ElGamal解密

由密文可得明文M，M=C2/C1^d mod p

ElGamal加密算法的使用

1985年，塔希尔·盖莫尔（Tather ElGamal）利用ElGamal算法设计出ElGamal数字签名方案，该数字签名是经典数字签名方案之一，具有高度的安全性与实用性。后来，ElGamal数字签名体制的变体被使用于数字签名标准DSS（数字签名标准）中。直到今天，很多新的数字签名方案仍然属于ElGamal数字签名体制的变体或扩展。GnuPG和PGP等很多密码学系统中也都应用到了ElGamal算法。

ElGamal加密算法的安全性

现代密码学一般是基于因数分解、或者离散对数等数学难题，ElGamal算法就是基于离散对数问题，其安全性依赖于计算有限域上离散对数这一难题，目前求解离散对数仍然是很困难的，因此它的安全性有一定保障。

ElGamal加密算法的缺点

ELGamal算法的安全密钥长度和其他一些加密算法相比还是较长，因此它的运算速度有待提高，而且由于ElGamal密码系统加密和解密的数学算法完全不同，造成签名和验证的时间消耗不同，以及加密和解密的花费的时间也不同。

本文原文来自jiamisoft.com