Board logo

标题: [讨论]探讨RSA密码体制中密钥固定部分比特的可行性 [打印本页]

作者: valen886    时间: 2008-7-22 09:41     标题: [讨论]探讨RSA密码体制中密钥固定部分比特的可行性

[讨论]探讨RSA密码体制中密钥固定部分比特的可行性
议题作者:tomzhi
信息来源:邪恶八进制信息安全团队(www.eviloctal.com

最近工作中在调研一个关于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)也就越难。不知道是否有有效的机制产生,谢谢。
作者: hansonlc    时间: 2008-7-22 09:41

根据n= p*q  p, q 为质数

n=2048 bits => p, q 分别为1024 bits 左右

本题可以转化成  在p,q 附近, s/2 bits范围内, 存在多少可用质数

我记得有一篇文章, 说的是质数的分布概率

http://www.channelwest.com/bbs/s ... 907&Forum_ID=19

根据给定范围, 计算出素数的可能存在数, 在进步平均分配, 可以估算出在给定的s/2 bits范围内, 存在多少可用组合

s越大, 范围自然越广.....

有效机制? 个人感觉在p, q 附近寻找新的素数算是比较好的吧自从做了俯卧撑,腰也不痛了,背也不酸了,打酱油也有劲了

帖子151 精华6 积分3794 阅读权限200 性别男 来自AUS 在线时间90 小时 注册时间2005-11-15 最后登录2008-7-17 查看个人网站
查看详细资料引用 报告 回复 TOP 少女暴富的隐秘(图)

tomzhi
晶莹剔透§烈日灼然
作者: 黑糊糊    时间: 2008-7-22 09:41

引用:
原帖由 fr.qaker 于 2008-6-5 13:11 发表
根据n= p*q  p, q 为质数

n=2048 bits => p, q 分别为1024 bits 左右

本题可以转化成  在p,q 附近, s/2 bits范围内, 存在多少可用质数

我记得有一篇文章, 说的是质数的分布概率

http://www.channelwest.com/bbs/ ...
由RSA算法由原理到实现(作者:张峰岭)中提到,如果p,q比较接近或任何一个比较小,n都能被快速分解,感觉p,q 均为1024 bits的方案不可取阿。不过还是很感谢。
帖子2 精华0 积分4 阅读权限40 在线时间1 小时 注册时间2007-3-8 最后登录2008-6-10 查看详细资料引用 报告 回复 TOP 爱要怎么说出口

fr.qaker
技术核心组





欢迎光临 【3.A.S.T】网络安全爱好者 (http://3ast.com/) Powered by Discuz! 7.2