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