第十三讲密码执行下.ppt

第十三讲 密码执行(下),本讲提要,模幂(续)指数译码 多模幂 中国剩余定理加速RSA Montgomery约减方法,2.2.2 k-ary方法,2.2.2 k-ary方法(续),2.2.2 k-ary方法(续),2.2.2 k-ary方法(续),2.2.2 k-ary方法(续),2.2.3 窗口方法,2.2.3 窗口方法(续),2.3 固定指数模幂算法 在许多情况下，我们需要计算指数为固定值的模幂。例子有RSA加密和解密，以及ElGamal解密。,2.3 固定指数模幂算法(续),2.3 固定指数模幂算法(续),2.3 固定指数模幂算法(续),2.4 固定底数模幂算法,2.4.1固定基窗口方法,2.4.1固定基窗口方法(续),2.4.1固定基窗口方法(续),2.4.2 固定基Euclidean方法,2.4.2 固定基Euclidean方法(续),2.4.2 固定基Euclidean方法(续),2.4.2 固定基Euclidean方法(续),3 指数译码,另一种减少基本二进制算法中乘法数量的方法就是将指数e的二进制表示用其它更少非零元的表示方法代替。由于二进制表示是唯一的，更少非零元的表示方法需要使用除0和1以外的数字。将指数从一种表示变成另一种表示称为指数译码。,3.1 符号数字表示,3.1 符号数字表示(续),3.1 符号数字表示(续),非邻接表指数译码的查表方法。,3.1 符号数字表示(续),3.2 使用 NAF表示 的二进制方法,4 多模幂,在一些情况下我们需要计算多个模幂的乘积，它们有不同的指数和底数，例子有ElGamal签名的认证。我们这里考虑如何同步计算，而不是分别计算它们，因为实际中我们并不需要这些模幂的中间值。,4.1 Shamir窍门,4.1 Shamir窍门(续),4.1 Shamir窍门(续),4.2 扩展Shamir窍门,5 中国剩余定理加速RSA,5 中国剩余定理加速RSA(续),5 中国剩余定理加速RSA(续),5 中国剩余定理加速RSA(续),6 Montgomery约减方法,6.1 Montgomery乘法,6.1 Montgomery乘法(续),6.1 Montgomery乘法(续),6.2 Montgomery模幂,6.2 Montgomery模幂(续),谢谢!,