第九讲-离散对数课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,在RSA密码算法中，我们看到如何利用分解的困难性产生有用的密码系统。另一个数论问题，称为离散对数问题，也有相似的应用。Diffie认为离散对数问题来源于Gill的提示。离散对数问题是公钥密码学的又一个重要公开困难问题。,在RSA密码算法中，我们看到如何利用分解的困难性产生有,1,本讲提要,离散对数,计算离散对数,ElGamal公钥加密算法,比特承诺,本讲提要 离散对数,2,1 离散对数,1 离散对数,3,第九讲-离散对数课件,4,第九讲-离散对数课件,5,2 计算离散对数,2.1 穷举搜索,2 计算离散对数2.1 穷举搜索,6,2.2 小步大步算法,2.2 小步大步算法,7,2.2 小步大步算法(续),2.2 小步大步算法(续),8,2.2 小步大步算法(续),2.2 小步大步算法(续),9,2.2 小步大步算法(续),2.2 小步大步算法(续),10,2.3 Pollard的Rho算法,2.3 Pollard的Rho算法,11,2.3 Pollard的Rho算法 (续),2.3 Pollard的Rho算法 (续),12,2.3 Pollard的Rho算法(续),2.3 Pollard的Rho算法(续),13,2.3 Pollard的Rho算法(续),2.3 Pollard的Rho算法(续),14,2.3 Pollard的Rho算法(续),2.3 Pollard的Rho算法(续),15,2.3 Pollard的Rho算法(续),2.3 Pollard的Rho算法(续),16,2.4 Pohlig-Hellman算法,2.4 Pohlig-Hellman算法,17,2.4 Pohlig-Hellman算法(续),2.4 Pohlig-Hellman算法(续),18,2.4 Pohlig-Hellman算法(续),2.4 Pohlig-Hellman算法(续),19,2.4 Pohlig-Hellman算法(续),2.4 Pohlig-Hellman算法(续),20,2.4 Pohlig-Hellman算法(续),2.4 Pohlig-Hellman算法(续),21,2.5 指数积分算法,2.5 指数积分算法,22,2.5 指数积分算法(续),2.5 指数积分算法(续),23,2.5 指数积分算法(续),2.5 指数积分算法(续),24,2.5 指数积分算法(续),2.5 指数积分算法(续),25,2.5 指数积分算法(续),2.5 指数积分算法(续),26,2.5 指数积分算法(续),2.5 指数积分算法(续),27,3 ElGamal公钥加密算法,ElGamal公钥加密方案依赖于离散对数问题和Diffie-Hellman问题的困难性。基本的ElGamal公钥加密方案是ElGamal于1985年提出。,3 ElGamal公钥加密算法 ElGamal公钥加密方,28,3.1 算法描述,3.1 算法描述,29,3.1 算法描述(续),3.1 算法描述(续),30,3.1 算法描述(续),3.1 算法描述(续),31,3.2 例子,3.2 例子,32,3.3 ElGamal加密算法效率,3.3 ElGamal加密算法效率,33,3.4 ElGamal加密算法安全,3.4 ElGamal加密算法安全,34,3.4 ElGamal加密算法安全(续),3.4 ElGamal加密算法安全(续),35,4 比特承诺,4.1 背景,(1) Alice声称发现了一种方法可以成功预测球赛的结果。她想把这种方法买给Bob。Bob要求她把周末的球赛结果预测一下以证明方法有效。Alice说 “没门，你可能利用我的预测结果去买彩票牟利，并且不与我分成。为什么不让我给你预测上周比赛的结果呢？”,4 比特承诺 4.1 背景,36,4.2 比特承诺的要求,Alice能发送一个比特,b,给Bob，这个比特可以是0或1。并需要满足,(1) Bob在没有Alice的帮助下不能决定这一个比特的取值。,(2) Alice一旦发送了这个比特，就不能改变取值情况。这样，对每场球赛，Alice可以发送,b,=1，表示她预测的队获胜；发送,b,=0，表示她预测的队失败。在比赛结束以后，Alice向Bob揭示这一比特的取值，证明自己的预测。,4.2 比特承诺的要求,37,4.3 计算模4的离散对数,4.3 计算模4的离散对数,38,4.3 计算模4的离散对数(续),4.3 计算模4的离散对数(续),39,4.3 计算模4的离散对数(续),4.3 计算模4的离散对数(续),40,4.4 比特承诺方案,4.4 比特承诺方案,41,精品课件,！,精品课件！,42,精品课件,！,精品课件！,43,谢谢!,谢谢!,44,