信息安全数学基础第5章原根和阶

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信息安全数学基础,第,5,章,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,5,章 原根和,阶,引子,在密码学中,有很多基于离散对数问题的密码算法和协议,比方ElGamal公钥密码算法,Diffie-Hellman密钥协商算法,美国的数字签名算法DSA等等.学习原根的知识有助于理解离散对数问题.,进一步地，理解离散对数问题也是理解椭圆曲线密码学的根底。,5.1,原根和,阶,原根和,阶,-,定义,原根和,阶,-,方法？,原根和,阶,-,例题,原根和,阶,-,例题,原根和,阶,-,例题,原根和,阶,-,性质,原根和,阶,-,性质,原根和,阶,-,性质,原根和,阶,-,例题,原根和,阶,-,例题,原根和,阶,-,性质,【例】整数5模17的阶为ord17(5)=16.因为7-15(mod 17),那么由【性质】,整数7模17的阶为16.,原根和,阶,-,例题,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,5,8,6,13,14,2,10,16,12,9,11,4,3,15,7,原根和,阶,-,举例,0,1,2,3,4,5,1,5,7,17,13,11,原根和,阶,-,性质,原根和,阶,-,举例,原根和,阶,-,性质,原根和,阶,-,性质,【例】由,ord,17,(5),16,可知,5,是模,17,的原根,由原根,5,就可以求出,17,的所有原根,.,解,:,模,17,的所有原根为,5,1,5,3,5,5,5,7,5,9,5,11,5,13,5,15,.,即,5,1,5(mod 17),5,3,6(mod 17),5,5,14(mod 17),5,7,10(mod 17),5,9,12(mod 17),5,11,11(mod 17),5,13,13(mod 17),5,15,6(mod 17).,原根存在的充分必要条件,5.1.3,素数的原根,5.2,离散对数,离散对数,-,定义,离散对数,-,例题,【例】5是模17的原根.求10对模17的离散对数.,解:先构造以5为底的阶函数表.再构造离散对数表.可得,10对模17的离散对数为7.,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,5,8,6,13,14,2,10,16,12,9,11,4,3,15,7,1,a,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,16,6,13,12,1,3,15,2,10,7,11,9,4,5,14,8,离散对数,-,性质,离散对数,-,举例,离散对数,-,举例,5.3,离散对数在密码学中的应用,离散对数问题在密码学中的应用,主要包括了,ElGamal,密码算法、,Diffie-Hellman,密钥协商算法、数字签名标准,(DSS),等,.,这里我们介绍,ElGamal,密码算法,以及,DSS,参数选取时用到的本章的相关知识,.,5.3.1 ELGamal,密码算法,ELGamal密码算法是一个非对称加密算法,由ELGamal在1985提出.既可以用于加密,也可以用于签名,其平安性依赖于离散对数问题.ELGamal数字签名算法的一个变体就是数字签名标准DSS.下面给出ELGamal算法的描述.,5.3.2,数字签名标准的参数选取,1991年8月,NIST颁发了一个通告,提出将数字签名算法DSA用于数字签名标准DSS中.1994年,在考虑了公众的建议后,该标准最终公布.,数字签名算法(DSA)的平安性是基于求解离散对数困难性的根底之上的,它是Schnorr和ElGamal签名算法的变体.,作业,