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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信息安全数学基础,第,5,章,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,5,章 原根和,阶,引子,在密码学中,有很多基于离散对数问题的密码算法和协议,比如,ElGamal,公钥密码算法,Diffie-Hellman,密钥协商算法,美国的数字签名算法,DSA,等等,.,学习原根的知识有助于理解离散对数问题,.,进一步地，理解离散对数问题也是理解椭圆曲线密码学的基础。,5.1,原根和,阶,原根和,阶,-,定义,原根和,阶,-,例题,原根和,阶,-,例题,原根和,阶,-,例题,原根和,阶,-,性质,原根和,阶,-,性质,原根和,阶,-,例题,【例,5.1.6,】已知整数,5,模,17,的阶为,ord,17,(5)=16.,因为,7,-1,5(mod 17),则由【性质,5.1.1,】,整数,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,原根和,阶,-,性质,原根和,阶,-,举例,原根和,阶,-,性质,【例,5.1.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.2.1,】已知,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,签名算法的变体,.,作业,