ELGamal算法课件.pptx

EIGamal算法; EIGamal公钥密码体制是1984年斯坦福大学的Tather EIGamal 提出的一种基于离散对数问题困难性的公钥体制。1985年，Tather EIGamal 利用EIGamal 公钥密码体制设计出EIGamal数字签名方案，该数字签名方案是经典数字签名方案之一，具有高度的安全性与实用性。后来，EIGamal数字签名体制的变体被使用于数字签名标准DSS中，直到今天，很多新的数字签名方案仍然属于EIGamal数字签名体制的变体或扩展。; ? 群是一个集合G，连同一个运算 ·，它结合任何两个元素 a 和 b 而形成另一个元素，记为 a · b。符号 · 是对具体给出的运算，比如加法的一般的占位符。要具备成为群的资格，这个集合和运算 (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 也是整数。换句话说，在任何时候，把两个整数相加都能得出整数的结果。这个性质叫做在加法下封闭。 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, 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,1594323, 4782969, 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用于加密;EIGamal用于加密;EIGamal用于加密;EIGamal用于数字签名;EIGamal用于数字签名;EIGamal用于数字签名; EIGamal算法的安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，在密码中主要应用离散对数问题的几个性质:求解离散对数(可能)是困难的，而其逆运算指数运算可以应用平方-乘的方法有效地计算。 ElGamal签名的安全性主要依赖于p和a，若选取不当则签名容易伪造，应保证a对于p-1的大素数因子不可约。为抵抗Pohlig Hellman算法的攻击，M一般都应采用被签信息的HASH值。; 该方案在技术上存在一些限制，从而可能导致一定的安全隐患， 如 ： 会话密钥