知识卡片
平方乘按指数位累积模幂
令y=1,从指数b的最低位开始:当前位为1时先令y=(y×a) mod n,再令a=(a×a) mod n并右移b。循环结束时y是原始a^b mod n;这里是平方和乘法,不是开平方。位为1时使用平方前的当前a,不能按正文简述把顺序反过来。
03069以5^11 mod53为例,b从1011依次右移,a依次5、25、42、15,y在有效位更新为5、19、20,最终20。这个表用于说明位分解,不是程序运行记录。
若b>0循环次数为其二进制位数,按大数参数分析需O(log b)次平方/条件乘法,单次大数操作成本另计。书中O(1)只固定了机器位宽,不应外推为密钥任意增大仍常时。当前按指数位分支也没有提供恒定时间安全保证。
288再次给固定分组O(1)说明,与源码while(b!=0)并不矛盾:固定机器位宽有固定迭代上限,变化的密钥位数则须保留log b及大数运算成本。没有运行原rsa.c或作密码性能测试。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
二进制平方-乘的算法来计算模幂。 二进制平方-乘算法避免了当a和b都很大时计算ab时会出现的超大中间值。比如,假设当a、b和n都是包含200位数字的超大整数,计算abmod n,其结果是一个40 000位的整数对200位的整数取模!因为最终得到的结果就是一个200位的整数,那么这里的目的就是要避免出
- · 查看原书依据
恒定的时间内完成。由于分组大小是恒定的,因此modexp中的循环执行时间也是恒定的。 示例15-4:RSA算法的实现
参考来源
- 位置:《算法精解:C语言描述》第15章《rsa_encipher》(spine1405;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1371.html;u287-ch15-019)。
- 结论依据:287全文与03069完整表、03070–03071完整modexp实读。
- 原始内容:二进制平方-乘的算法来计算模幂。 二进制平方-乘算法避免了当a和b都很大时计算ab时会出现的超大中间值。比如,假设当a、b和n都是包含200位数字的超大整数,计算abmod n,其结果是一个40 000位的整数对200位的整数取模!因为最终得到的结果就是一个200位的整数,那么这里的目的就是要避免出
- 位置:《算法精解:C语言描述》第15章《rsa_decipher》(spine1406;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1372.html;u288-ch15-019)。
- 结论依据:288再次给固定分组O(1)说明,与源码while(b!=0)并不矛盾:固定机器位宽有固定迭代上限,变化的密钥位数则须保留log b及大数运算成本。没有运行原rsa.c或作密码性能测试。
- 原始内容:恒定的时间内完成。由于分组大小是恒定的,因此modexp中的循环执行时间也是恒定的。 示例15-4:RSA算法的实现