-密码执行(下)课件

第十二讲 密码执行(下)本讲提要 q 模幂(续)q 指数译码q 多模幂q 中国剩余定理加速RSAq 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 中国剩余定理加速RSA5 中国剩余定理加速RSA(续)5 中国剩余定理加速RSA(续)5 中国剩余定理加速RSA(续)6 Montgomery约减方法6.1 Montgomery乘法6.1 Montgomery乘法(续)6.1 Montgomery乘法(续)6.2 Montgomery模幂6.2 Montgomery模幂(续)谢谢!