[讨论]探讨RSA密码体制中密钥固定部分比特的可行性
议题作者：tomzhi信息来源：邪恶八进制信息安全团队（[url]www.eviloctal.com[/url]）
最近工作中在调研一个关于RSA的问题，现已知RSA算法中公布的公钥为(e,n)（即加密数据用的加密密钥），私钥为(d,n)。
Boss给我提了这样一个想法，问我实现的可能性。即如果n为2048 bits,并且已知有1920位数字取值固定，仅余128 bits可配置，这样能否得到不止一组满足条件的n，并且对应的e也是已知有某些位固定，仅余128 bits可配置。
我的初步想法是，两端两端极限思维告诉我128bits可配置未必可行，但是如果把128这个数字改得大一些或许可行。因为假设已知n的2048 bits 中有某一位数字取值固定（比如是最末位，毕竟大质数相乘必然是奇数，则末位为1），对应的e也是某一个固定位（比如也是末位，末位为1），其余2047位可配置，则显然应该能找到两组不同的(e1,n1),(e2,n2)作为公钥。
上述是极限思维的一端。
另一端就是当2047位固定，1位可配置，显然就无解。
那么在这两个极限中间，必然存在一个s位固定，其余（2048-s）位可配置的方案，且该方案对于n于e均可行。这样只要准备几套密钥对，固定位写入ROM，可配置位在硬件具体运行时配置，这样数据带宽会小一些，所以自然希望这个s尽可能大，则(2048-s)就会比较小。
个人感觉就算找到了这样的s，如果s越大，则2048-s越小，也就意味着条件越苛刻，要找到满足条件的(e1,n1),(e2,n2)也就越难。不知道是否有有效的机制产生，谢谢。 根据n= p*q p, q 为质数
n=2048 bits => p, q 分别为1024 bits 左右
本题可以转化成 在p,q 附近, s/2 bits范围内, 存在多少可用质数
我记得有一篇文章, 说的是质数的分布概率
[url]http://www.channelwest.com/bbs/showtopic.asp?TOPIC_ID=5907&Forum_ID=19[/url]
根据给定范围, 计算出素数的可能存在数, 在进步平均分配, 可以估算出在给定的s/2 bits范围内, 存在多少可用组合
s越大, 范围自然越广.....
有效机制? 个人感觉在p, q 附近寻找新的素数算是比较好的吧 [quote]原帖由 [i]fr.qaker[/i] 于 2008-6-5 13:11 发表 [url=https://forum.eviloctal.com/redirect.php?goto=findpost&pid=143890&ptid=33264][img]images/common/back.gif[/img][/url]
根据n= p*q p, q 为质数
n=2048 bits => p, q 分别为1024 bits 左右
本题可以转化成 在p,q 附近, s/2 bits范围内, 存在多少可用质数
我记得有一篇文章, 说的是质数的分布概率
[url]http://www.channelwest.com/bbs/[/url] ... [/quote]
由RSA算法由原理到实现（作者：张峰岭）中提到，如果p,q比较接近或任何一个比较小，n都能被快速分解，感觉p,q 均为1024 bits的方案不可取阿。不过还是很感谢。 1024bit + 1024 bit 只是一个example, 你固定了一个长度, 其他的也是p q 周围, 这样的N其实也很容易被分解的
页:
[1]