返回总目录,第7章 非对称密钥密码系统与离散对数,教学目的,了解非对称密匙密码系统 了解Pohlig-Hellman密码 了解Diffie-Hellman密钥交换 了解ElGamal密码 了解Pohlig-Hellman算法 了解Index Calculus 离散对数算法, Pohlig-Hellman密码与离散对数,本章内容, Diffie-Hellman密钥交换, ElGamal密码, Pohlig-Hellman算法, Index Calculus,Pohlig-Hellman密码与离散对数,7.1 Pohlig-Hellman密码与离散对数,定义 离散对数，Discrete Logarithm，Index,令n、为非零整数，满足,其中n不一定是质数）,原根定理,定理 原根,令n、为非零整数且 ， 为n的原根，当且唯当以下任一等价关系成立：,（1） 生成 ，即,（2） 的秩（Order）为,离散对数,定理,令r、s、n为非零整数，而r、s为n的原根，令x、y为与n互质的整数，则,（1）,（2）,（3）,（4）,离散对数,定理,令r为整数，p为奇质数，r为乘法群 的原根,证明：,其中对q为p-1的所有质因子均成立。,Diffie-Hellman密钥交换,7.2 Diffie-Hellman密钥交换,居中攻击,居中攻击，Man in the Middle Attack,Alice和Bob在极度不安全的通路共同约定私钥，当中第三者Eve分别假扮成Alice与Bob约定私钥，假扮成Bob与Alice约定私钥，而Alice与Bob浑然不知。Eve借助以下步骤与Alice、Bob约定私钥：,Eve选一数 ，计算值 与Alice约定出私钥 与Bob约定出私钥。,这样，Eve便可用私钥KAlice与Alice加密解密信息，而与Bob可用私钥KBob加密解密信息。,ElGamal密码,7.3 ElGamal密码,Pohlig-Hellman算法,7.4 Pohlig-Hellman算法,例：解离散对数问题,乘法群 的秩为,由于,且,故x0=1。而,又,故x1=0。再者,且,所以x2=1，故得,Pohlig-Hellman算法,q=5求x(mod 5)如下：,因此,由中国余式定理解联立同余式,得,其中,故得解x=13,Index Calculus,7.5 Index Calculus,求离散对数问题 ，其中p为大质数而为一原根。,选取因数基底S,建构同余方程组,计算x,