lect06DiscreteLogarithm

1、离散对数Discrete Logarithm非对称加密算法基于困难假设 大整数因式分解 RSA, Rabin 离散对数 El Gamal 椭圆曲线上的离散对数 椭圆曲线上的El GamalEl Gamal密码体制离散对数：实例：乘法群，一个 阶元素 和问题：找到一个唯一的整数 ， ，满足 ,GnGa10naaEl Gamal密码体制El Gamal密码体制基于离散对数问题。我们首先在有限乘法群中描述这个问题。对于一个 阶元素 ，定义容易看到，是 的一个子群， 是一个 阶循环群。经常使用的一个例子是，取 为 ( 为素数)上的乘法群， 为模 的生成元。这时有 ,GGn10:niiGnGpZp1pn

2、pEl Gamal密码体制我们将这个整数 记为 ，称为 的离散对数。在密码中主要应用离散对数问题的如下性质：求解离散对数(可能)是困难的，而其逆运算指数运算可以应用平方-乘方法有效地计算。换句话说，在适当的群 中，指数函数是单向函数。alogGEl Gamal密码体制 上的El Gamal密码体制设 是一个素数，使得 上的离散对数问题是难处理的，令 是一个生成元。令 ， 定义， 是公钥， 是私钥。对 ,以及一个(秘密)随机数 ，定义 ，其中且对，定义*pZpapKamod:,1pZkp ,*pZ*pZ*pZP*ppZZC,p, p a,apK21,yykxeKpykmod1pxykmod2*2

3、1,pZyy pyyyydaKmod,11221El Gamal密码体制在El Gamal密码体制中，加密运算是随机的，因为密文既依赖于明文又依赖于加密方选择的随机数 ，因此对于同一个明文会有许多( 个)可能的密文。例：设 ， 。 是模 的生成元。令所以 ，假设Alice现在想要传送消息 给Bob,如果她选择 作为随机数，那么她计算k23962579mod949*1299,4352579mod285328531yy21p2579pp765a9492579mod27651299x853kEl Gamal密码体制 Bob收到密文 后，他计算这正是Alice加密的明文。显然，如果其他人可以计算 ，那

4、么El Gamal密码体制就是不安全的。El Gamal密码体制安全的一个必要条件就是 上的离散对数问题是难处理的。为此 应该至少取300个十进制位， 应该具有一个较“大”的素数因子。12992579mod435*23961765x2396,435loga*pZp1pEl Gamal体制的安全性El Gamal是否正确？El Gamal是否高效？El Gamal是否安全？Diffie-Hellman问题Dis,n,logGGGa离散对数问题（crete Logarithm)：已知一个乘法群，一个 阶元素和元素计算。Diffie-HellmanCDH, Computational Diffie-

5、Hellman,n,logloglogGGGG 计算问题（)：已知一个乘法群，一个 阶元素两个元素计算满足。Diffie-HellmanDDH, Dicision Diffie-Hellman,n, ,logloglogGGG 判定问题（)：已知一个乘法群，一个 阶元素两个元素判定是否成立。El Gamal 安全性 如何证明？ ,xyxyxyzggggggEl Gamal安全性 解决DDH问题的概率？*01*,PubKey:,:,iiiixyxyxyrxyzxrxriiiyzbrxriiiggggggggggEncOracle mrgm gm mgm gEncOracle mrgm gb：Di

6、ffie-Hellman问题ElGamalCDH体制的解密等价于求解问题。CDH（1）解决了问题求出明文。12, yxy1已知计算 ，则DDH（2）区分出明文解决了问题1212( , , ),yyxy x 给定定义随机选择调用解密算法得到则El Gamal密码体制El Gamal密码体制可以在任何离散对数问题难处理的群中实现。除了乘法群 ，还有两类群也是合适的候选者。有限域 的乘法群；定义在有限域上的椭圆曲线的群。为此，下面介绍群、环、域的定义以及区别联系。*pZnpF群、环、域半群称代数系统为半群，如果*运算满足结合律。典型的半群如：，其中Z+代表正整数群、环、域群称代数结构为群（group

7、s）,如果 （1）为一半群（2）中有单位元e（3）中每一元素都有逆元其中，若 * 运算满足交换律，则称该群为交换群或阿贝尔群。典型的群如：，其中Q+代表正有理数群、环、域环称代数结构为环（ring），如果（1）是阿贝尔群。（2）是半群。 （3）乘运算对加运算可分配，即对任意元素a,b,c R，有 a（bc） ab+ac , （bc）a = ba+ca典型的环如： (Z为整数集，+,为数加与数乘运算) 群、环、域域称为域（fields），如果为环,且为阿贝尔群。典型的域如：，其中Q为有理数。但是不是域。为什么？因为在整数集中整数没有乘法逆元。 有限域当 是素数时， 是一个域。如果 ， 是素数，

8、是整数，就存在一个具有 个元素的域。这类域的构造方法如下：假定 是素数。定义是变元 的所有多项式的集合。按照通常多项式的乘法和加法定义（并且模 约化系数），我们构造一个环。对于 ，如果存在满足，则说 整除 ，记作 ,xZxgxfppZpnpqp1nqpxZpxp xZxqp xfxqxg xf xg xgxf|有限域对 ， 的次数定义为 的项中最高次数。假定，且。如果 则定义我们注意到，多项式同余与整数的同余有着非常相似之处。我们要定义一个“模 ”的多项式环，记作为此，基于模 同余的观点，从 构造 ，类似于由 构造f fdegxZp xfxhxgmod xhxgxf| xf ,xZxhxgxf

9、p xZxfpf 1degnf xfxZp/ xfZmZ xfxZp/有限域假定 ，用 去除 ，得到(唯一)商 和其中， ，并且这可以由多项式的长除法实现。因此 中任何多项式模 同余于唯一的次数至多 的多项式。定义 的元素是 中所有 个次数不超过 的多项式。加法和乘法与 中相同，并且模 约化。有了这两个运算， 是一个环。1n xrxfxqxg xf xgxZp nfdeg xq xr nrdeg xf xfxZp/1nxZpnpxZp xf xfxZp/有限域 是一个域当且仅当 是素数，乘法逆元可以通过欧几里得算法求得。对于 有类似的情形。多项式中类似于素性的概念是不可约性，定义如下所述。定义

10、6.2 一个多项式 称为不可约，如果不存在多项式 ，满足 ，其中 且 xZxfpmZ 0deg1fm xfxfxf21 xfxZp/ ,21xZxfxfp 0deg2f有限域一个重要的事实是， 是域当且仅当 是不可约的。中元素的乘法逆元可以直接通过改进的(扩展)欧几里得算法计算。例：我们构造一个具有八个元素的域。这可以通过在 中找一个次数为 的不可约多项式做到。因为任何和常数项为 的多项式都可以被 整除，因而是可约的，我们只需要考虑具有常数项为 的多项式。有 个这样的多项式。 xfxZp/ xf xfxZp/2Zx3014有限域 11112342333231xxxxfxxxfxxxfxxf 1

11、111112234231xxxxxxfxxxxxf有限域由于 和 都是不可约的，所以我们可以其构造域。这里使用 构造域 个域元素如下：由于任意两个域元素的乘积模约化后，余式的次数至多是 ，因此是域中的元素。例如，计算 中的1,1,1,1 ,02222xxxxxxxx8 xf2 xf3 xf21/32xxxZ13xx21/32xxxZ1122xxx有限域例如，计算 中的首先在中计算乘积，得到。随后用 去除，得到表达式：因此，在域 中有：1/32xxxZ1122xxx2xZ134xxx13xxxxxxxxxx23341111/32xxxZxxxxx22211有限域下面给出一个域中非零元素的乘法表，

12、将多项式简写为有序三元组0122axaxa012aaa001010011100101110111001001010011100101110111010010100110011001111101011011110101111100001010100100011111110010101001101101001100010111011110110110111001101011010100111111101010001110100011有限域通过直接应用扩展的欧几里得算法，可以计算域元素的逆元。最后域中非零多项式是一个7阶乘法群，由于7是素数，所以域中除0和1外，任何元素都是本原元。例如，计算 的幂可

13、以囊括域中的所有非零元素：x13221xxxxxx1117262524xxxxxxxxx有限域域的存在性和唯一性可以证明，在 中，对任意给定的次数 ，至少存在一个不可约多项式。因此，对所有的整数 以及所有的素数 存在具有 个元素的有限域。通常， 中有许多次数为 的不可约多项式，但是可以证明有任何两个不可约多项式构造的域是同构的。因此，存在唯一的 个元素的有限域，记为xZp1n1npnpxZpnnpnpF有限域当 时， 与 相同。最后可以证明，如果存在 个元素的有限域，那么一定存在某个素数 ，以及某个整数 ，使得注意到乘法群 是一个阶为 的循环群。事实上，任何有限域的乘法群都是循环群： 是一个阶

14、为 的循环群。pZr1np1npFnpr*pZ1p 0npF1np椭圆曲线实数上的椭圆曲线椭圆曲线被描述为一个二元方程解的集合模 定义的椭圆曲线在公钥密码学中非常重要定义6.3 设 是满足 的常实数方程 的所有解 连同一个无穷远点 组成的集合 ，称为一个非奇异椭圆曲线pR, ba027423babaxxy32RR,yxOE椭圆曲线实数上的椭圆曲线如果 是保证方程 有三个不同解（实数或复数）的充要条件。如果 ，则对应椭圆曲线为奇异椭圆曲线。假定 是一个非奇异椭圆曲线，在 上定义一个二元运算，使其成为一个阿贝尔群，这个二元运算常用加法表示。无穷远点 将是单位元。027423babaxxy32027

15、423baEEO椭圆曲线实数上的椭圆曲线因此，对于所有 有假设 ，其中我们分三种情况考虑：1.2.3. PPOOPEPEQP, 2211,yxQyxP21xx2121,yyxx2121,yyxx椭圆曲线1.定义 是通过 和 的直线。 交 于 和 ，容易看出， 还交 于第三点，记为 。对于 轴反射 ，得到一点 。定义这里首先给出计算 的代数公式。首先，直线 的方程为 ，其斜率是并且21xxLPQLPQELRExRRRQPRLxy1212xxyy2211xyxy椭圆曲线为了算出 中的点，将 代入到 的方程中得到等价于上式的三个根中， 和 是其中的两个点，所以 和 是方程的两个根。由于该方程是实数域

16、上的三次方程，所以第三个根应该也是实数根，记为 。三根之和是二次项系数 的相反数，所以LExyEbaxxx32022223bxaxxPQ1x2x3x22123xxx椭圆曲线设，则又由于 在直线上，所以即所以对于 ，可以导出 的一个计算公式其中),(33yxR),(33yxRR1213xxyy1313yxxy21xxQP332211,yxyxyx13132123yxxyxxx1212xxyy椭圆曲线2121yyxx2312xxx3131()yxxy椭圆曲线2.当 时，定义因此 与 是关于椭圆曲线加法运算互逆的。2121,yyxx2121,yyxxEyxOyxyx,yx,yx,椭圆曲线3.这就相当

17、于 与自己相加。可以假定 ，否则就是情形2。这里定义 是 在 点的切线。此时利用微积分知识计算 的斜率：替换 ，得到切线斜率为2121,yyxx11,yxP01yLPELyaxdxdyaxdxdyy23322211,yyxx12123yax椭圆曲线13131123yxxyxxx12123yax椭圆曲线到此为止，按照前述定义，加法运算具有下列性质：1.加法在集合 上是封闭的。2.加法是可交换的。3. 是加法的单位元。4. 上每个点有关于加法的逆元。EOE要证明是阿贝尔群，尚需证明加法是可结合的，但是方法比较繁杂，这里不做过多讨论。,E椭圆曲线模素数的椭圆曲线设 是素数。 上的同余方程的所有解 ，

18、连同无穷远点 ，共同构成 上的椭圆曲线 。其中 并且满足恒不等于 的常量。3ppZpbaxxymod32ppZZyx,OpZbaxxy32pZba,23274ba0椭圆曲线 上的加法运算定义如下(设所有的运算都在 中)：假设 是 上的点。如果 且 则 否则 其中且EpZ2211,yxQyxP21xxE12yyOQP33,yxQP23123131xxxyxxyQPyaxQPxxyy11211121223椭圆曲线最后，对于所有的 ，定义 上的椭圆曲线虽然不像实数域上的椭圆曲线那样具有直观的几何解释，然而同样的公式可以用来定义加法运算，仍然是一个阿贝尔群。例：设 是 上的椭圆曲线 。首先确定的点。这可以通过对每个，计算对于给定的 ，测试 是否二次剩余。EPPPOOPpZ,EE11Z632xxyE11Zx36 mod11xx。x63xxz椭圆曲线利用这个公式，二次剩余 的平方根是z11mod11mod34/111zz是二次剩余吗06182533485468