ELGamal算法.ppt

《ELGamal算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、EIGamal算法王亚星叶达成张常文EIGamal公钥密码体制是1984年斯坦福大学的TatherEIGamal提出的一种基于离散对数问题困难性的公钥体制。1985年，TatherEIGamal利用EIGamal公钥密码体制设计出EIGamal数字签名方案，该数字签名方案是经典数字签名方案之一，具有高度的安全性与实用性。后来，EIGamal数字签名体制的变体被使用于数字签名标准DSS中，直到今天，很多新的数字签名方案仍然属于EIGamal数字签名体制的变体或扩展。历史背景群是一个集合G，连同一个运算"·"，它结合任何两个元素a和b而形成另一个元素，记为a·b。符号

2、"·"是对具体给出的运算，比如加法的一般的占位符。要具备成为群的资格，这个集合和运算(G,·)必须满足叫做群公理的四个要求：1.封闭性。对于所有G中a,b，运算a·b的结果也在G中。2.结合性。对于所有G中的a,b和c，等式(a·b)·c=a·(b·c)成立。3.单位元。存在G中的一个元素e，使得对于所有G中的元素a，等式e·a=a·e=a成立。4.反元素。对于每个G中的a，存在G中的一个元素b使得a·b=b·a=e，这里的e是单位元。群例如整数集合和加法运算，具有以下性质1.对于任何两个整数a和b，它们的和a+b也是整数。换句话说，在任何时候，把两个整数相加都能

3、得出整数的结果。这个性质叫做在加法下封闭。2.对于任何整数a,b和c，(a+b)+c=a+(b+c)。用话语来表达，先把a加到b，然后把它们的和加到c，所得到的结果与把a加到b与c的和是相等的。这个性质叫做结合律。3.如果a是任何整数，那么0+a=a+0=a。零叫做加法的单位元，因为把它加到任何整数都得到相同的整数。对于任何整数a，存在另一个整数b使得a+b=b+a=0。整数b叫做整数a的逆元，记为−a。群一个群被称为有限群，如果它有有限个元素。元素的数阶叫做群G的阶例如，模19下7的阶为3，[1,7,49,343,2401,16807,117649,823543

4、,5764801...]={1,7,11,1,7,11,1,7,11...}这里的1,7,11循环，实际只有3个元素群循环群是其所有元素都是特定元素a的幂的群(在群运算被写为加法的时候使用术语倍数)。在乘法符号下，群的元素是:...,a−3,a−2,a−1,a0=e,a,a2,a3,...,这个元素a叫做这个群的生成元或本原元。循环群模n下a的阶m=φ(n)，m就是n的本原元，如3是19的本原元19为质数，因此φ(19)=18,模19下3的群为[1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,159

5、4323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401L,10460353203L,31381059609L,94143178827L...]用模19来表示[1,3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,1,3,9L,8L,5L,15L]循环为1,3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,因此该循环群阶为18本原元EIGamal用于加密密钥对的生成：随机选择一个大素数p，要求p-1有大素

6、数因子。再选择一个模p的本原元a。将p和a公开。随机选择一个整数d作为私钥，2≤d≤p-2。计算y=a^dmodp，取y为公钥。实例解析：p=97；a=5,d=58，a,d均小于97，符合条件；y=5^58（mod97)=44公钥：y=44私钥：d=58EIGamal用于加密加密过程：被加密信息为m；随机选择一个整数k，2≤k≤p-2；计算c1=a^k(modp)c2=y^k*m(modp)(c1,c2)为密文，是明文的两倍长。实例解析：m=3；k=36，满足k<97-1计算c1=5^36mod97=50c2=44^36*3mod97=31所以密文为（50,31）

7、EIGamal用于加密解密过程：计算m=c2*(c1^d)^-1modp,即得出明文实例解析：m=31*（50^58)^-1mod97=31*(97-75)mod97=31*22mod97=3mod97即明文m=3EIGamal用于数字签名密钥对的生成：随机选择一个大素数p，要求p-1有大素数因子。再选择一个模p的本原元a。将p和a公开。随机选择一个整数d作为私钥，2≤d≤p-2。计算y=a^dmodp，取y为公钥。实例解析：p=19；a=13,d=10,a与d均小于p,符合条件；y=13^10(mod19)=6;公钥：y=6a=13p=19私钥：d=10EIGa

8、mal用于