[讨论]探讨RSA密码体制中密钥固定部分比特的可行性
[讨论]探讨RSA密码体制中密钥固定部分比特的可行性议题作者：tomzhi
信息来源：邪恶八进制信息安全团队（[url=http://www.eviloctal.com/]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]http://www.channelwest.com/bbs/s ... 907&Forum_ID=19[/url]
根据给定范围, 计算出素数的可能存在数, 在进步平均分配, 可以估算出在给定的s/2 bits范围内, 存在多少可用组合
s越大, 范围自然越广.....
有效机制? 个人感觉在p, q 附近寻找新的素数算是比较好的吧自从做了俯卧撑，腰也不痛了，背也不酸了，打酱油也有劲了
[url=http://wpa.qq.com/msgrd?V=1&Uin=167110&Site=邪恶八进制信息安全团队技术讨论组&Menu=yes][img]http://forum.eviloctal.com/images/default/qq.gif[/img][/url]
帖子151 精华[url=http://forum.eviloctal.com/digest.php?authorid=18708]6[/url] 积分3794 阅读权限200 性别男 来自AUS 在线时间90 小时 注册时间2005-11-15 最后登录2008-7-17 [url=http://blog.n-ku.com/blog.asp?name=bigboyq]查看个人网站[/url]
[url=http://forum.eviloctal.com/space.php?action=viewpro&uid=18708]查看详细资料[/url][url=http://forum.eviloctal.com/post.php?action=reply&fid=9&tid=33264&repquote=143890&extra=page%3D4&page=1]引用[/url] [url=http://forum.eviloctal.com/misc.php?action=report&fid=9&tid=33264&pid=143890&page=1]报告[/url] [url=http://forum.eviloctal.com/###]回复[/url] TOP [url=http://www.google.cn/search?q=干洗店加盟&client=pub-0204114945524753&forid=1&prog=aff&ie=UTF-8&oe=UTF-8&cof=GALT%3A#008000;GL%3A1;DIV%3A336699;VLC%3A663399;AH%3Acenter;BGC%3AFFFFFF;LBGC%3A336699;ALC%3A0000FF;LC%3A0000FF;T%3A000000;GFNT%3A0000FF;GIMP%3A0000FF;FORID%3A1&hl=zh-CN]少女暴富的隐秘（图）[/url]
[url=http://forum.eviloctal.com/space-uid-88447.html]tomzhi[/url] [img]http://forum.eviloctal.com/images/avatars/noavatar.gif[/img]
晶莹剔透§烈日灼然 引用:
原帖由 fr.qaker 于 2008-6-5 13:11 发表 [url=https://forum.eviloctal.com/redirect.php?goto=findpost&pid=143890&ptid=33264][img]http://forum.eviloctal.com/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/]http://www.channelwest.com/bbs/[/url] ...
由RSA算法由原理到实现（作者：张峰岭）中提到，如果p,q比较接近或任何一个比较小，n都能被快速分解，感觉p,q 均为1024 bits的方案不可取阿。不过还是很感谢。
帖子2 精华[url=http://forum.eviloctal.com/digest.php?authorid=88447]0[/url] 积分4 阅读权限40 在线时间1 小时 注册时间2007-3-8 最后登录2008-6-10 [url=http://forum.eviloctal.com/space.php?action=viewpro&uid=88447]查看详细资料[/url][url=http://forum.eviloctal.com/post.php?action=reply&fid=9&tid=33264&repquote=143906&extra=page%3D4&page=1]引用[/url] [url=http://forum.eviloctal.com/misc.php?action=report&fid=9&tid=33264&pid=143906&page=1]报告[/url] [url=http://forum.eviloctal.com/###]回复[/url] TOP [url=http://www.google.cn/search?q=鲜花预定&client=pub-0204114945524753&forid=1&prog=aff&ie=UTF-8&oe=UTF-8&cof=GALT%3A#008000;GL%3A1;DIV%3A336699;VLC%3A663399;AH%3Acenter;BGC%3AFFFFFF;LBGC%3A336699;ALC%3A0000FF;LC%3A0000FF;T%3A000000;GFNT%3A0000FF;GIMP%3A0000FF;FORID%3A1&hl=zh-CN]爱要怎么说出口[/url]
[url=http://forum.eviloctal.com/space-uid-18708.html]fr.qaker[/url] [img]http://forum.eviloctal.com/images/avatars/pw/eviloctal2.gif[/img]
技术核心组
[img]http://forum.eviloctal.com/images/default/star_level2.gif[/img][img]http://forum.eviloctal.com/images/default/star_level2.gif[/img]
页:
[1]