知识卡片

普通读书笔记卡 · 7174.e.1.q · 生成模型:未记录

取模之前的乘积必须先装得下

理解等级:中级

若a和y已化为0到n−1,a²和ya都小于n²,直接乘法实现往往要为约两倍模数位宽的中间积留空间,然后再取模。若机器无符号乘法先回绕,后续%n不能一般地恢复本来正确的模积。

Huge只是unsigned long时,能够表示的模数必须满足中间乘积边界;“通常10位”“最多5位”是特定位宽背景的粗略描述,不能替代对ULONG_MAX及数值上界的检查。输入a若起初不在模数内,第一次乘法的界还可能更大。

把Huge改为大整数类型仍需把乘法、取模、位操作和比较等改成对应库操作并处理失败/资源责任;单改typedef不会把内置C运算符自动变成大数算法。当前源码没有提供大数库或安全规模保证。

287称两个200位十进制整数a、b的a^b有40000位,是把指数数值与指数位数混淆。幂的十进制位数在a>0时由floor(b×log10 a)+1决定,可远大于40000;平方乘的重要性正是避免构造该完整幂,而不是其位数恰等两者位数之积。每步先取模仍不能消除取模前机器乘法溢出。

290再次强调大数表示重要;“至少200位/400位”沿用书的历史规模举例,不作为当前安全参数标准。实现须满足实际模数与乘积范围,并使用适当的完整加密编码,而不只增加数字宽度。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      密钥位数的2倍。(我们一会儿将在模幂计算中看到这个需求)。因此,如果密钥是个200位的整数,就需要一种抽象数据类型来支持至少400位的整数。 由于本书并没有提供有关大数运算的相关章节,因此这里给出的RSA实现必须依赖其他的函数库。已经有一些可用的函数库,因此本书不提供具体的实现。示例15-1定了数据

    • · 查看原书依据

      40 000位的整数对200位的整数取模!因为最终得到的结果就是一个200位的整数,那么这里的目的就是要避免出现40 000位整数的中间值。 用二进制平方-乘算法计算abmod n,主要是多个开平方运算的结果(见图15-4)。首先将b表示为二进制形式,然后从最右边的位开始处理。对于b中的每个位,求出

    • · 查看原书依据

      大数运算 这是RSA算法安全实现中的一个重要部分。在RSA算法中,考虑到当前计算整数素数因子的水平,为了安全起见,所选择的整数必须至少有200位的数字组成。这意味着所有参与运算的整数必须至少为400位数。 欧几里得最大公约数算法 一种用来计算最大公约数的方法,是已知的最古老的算法之一。该算法同RSA

    参考来源

    - 位置:《算法精解:C语言描述》第15章《RSA算法的实现与分析》(spine1405;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1371.html;u286-ch15-018)。 - 结论依据:286全文与03070/03071 a*a、y*a及原生Huge实际表示完整实读。 - 原始内容:密钥位数的2倍。(我们一会儿将在模幂计算中看到这个需求)。因此,如果密钥是个200位的整数,就需要一种抽象数据类型来支持至少400位的整数。 由于本书并没有提供有关大数运算的相关章节,因此这里给出的RSA实现必须依赖其他的函数库。已经有一些可用的函数库,因此本书不提供具体的实现。示例15-1定了数据 - 位置:《算法精解:C语言描述》第15章《rsa_encipher》(spine1405;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1371.html;u287-ch15-018)。 - 结论依据:287称两个200位十进制整数a、b的a^b有40000位,是把指数数值与指数位数混淆。幂的十进制位数在a>0时由floor(b×log10 a)+1决定,可远大于40000;平方乘的重要性正是避免构造该完整幂,而不是其位数恰等两者位数之积。每步先取模仍不能消除取模前机器乘法溢出。 - 原始内容:40 000位的整数对200位的整数取模!因为最终得到的结果就是一个200位的整数,那么这里的目的就是要避免出现40 000位整数的中间值。 用二进制平方-乘算法计算abmod n,主要是多个开平方运算的结果(见图15-4)。首先将b表示为二进制形式,然后从最右边的位开始处理。对于b中的每个位,求出 - 位置:《算法精解:C语言描述》第15章《相关主题》(spine1408;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1374.html;u290-ch15-018)。 - 结论依据:290再次强调大数表示重要;“至少200位/400位”沿用书的历史规模举例,不作为当前安全参数标准。实现须满足实际模数与乘积范围,并使用适当的完整加密编码,而不只增加数字宽度。 - 原始内容:大数运算 这是RSA算法安全实现中的一个重要部分。在RSA算法中,考虑到当前计算整数素数因子的水平,为了安全起见,所选择的整数必须至少有200位的数字组成。这意味着所有参与运算的整数必须至少为400位数。 欧几里得最大公约数算法 一种用来计算最大公约数的方法,是已知的最古老的算法之一。该算法同RSA