知识卡片
取模之前的乘积必须先装得下
若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 条
还没有人提交反馈。
在整书笔记中的位置
- · 取模之前的乘积必须先装得下
- · rsa_encipher
- · 相关主题
原书出处 · 3 处
- · 查看原书依据
密钥位数的2倍。(我们一会儿将在模幂计算中看到这个需求)。因此,如果密钥是个200位的整数,就需要一种抽象数据类型来支持至少400位的整数。 由于本书并没有提供有关大数运算的相关章节,因此这里给出的RSA实现必须依赖其他的函数库。已经有一些可用的函数库,因此本书不提供具体的实现。示例15-1定了数据
- · 查看原书依据
40 000位的整数对200位的整数取模!因为最终得到的结果就是一个200位的整数,那么这里的目的就是要避免出现40 000位整数的中间值。 用二进制平方-乘算法计算abmod n,主要是多个开平方运算的结果(见图15-4)。首先将b表示为二进制形式,然后从最右边的位开始处理。对于b中的每个位,求出
- · 查看原书依据
大数运算 这是RSA算法安全实现中的一个重要部分。在RSA算法中,考虑到当前计算整数素数因子的水平,为了安全起见,所选择的整数必须至少有200位的数字组成。这意味着所有参与运算的整数必须至少为400位数。 欧几里得最大公约数算法 一种用来计算最大公约数的方法,是已知的最古老的算法之一。该算法同RSA