首页
社区
课程
招聘
[求助]RSA算法求私钥d。
发表于: 2011-8-26 11:06 12531

[求助]RSA算法求私钥d。

2011-8-26 11:06
12531
我知道RSA中由公钥e求私钥d是要满足e*d(mod n)=1.此处n大家都知道是(p-1)(q-1)。用辗转相除法可以求得。但是问题在于如果n是一个大数,有512bit。这么大的数我怎么用辗转相除法啊?如果e选择3,那d肯定也很大,怎么求?。。。求高手解答······

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 0
支持
分享
最新回复 (7)
雪    币: 952
活跃值: (1821)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
能求出来现在的密码体系就崩溃了。。银行的钱随便取
2011-8-26 12:01
0
雪    币: 68
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
是我自己做题目,因此p,q,n等参数都知道。当然能求···
2011-8-26 14:59
0
雪    币: 8209
活跃值: (4518)
能力值: ( LV15,RANK:2473 )
在线值:
发帖
回帖
粉丝
4
看来算法是知道的,问题在于大数运算,用大数库就行了
2011-8-26 15:26
0
雪    币: 210
活跃值: (221)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
5
1997年后开发的系统,用户应使用1024位密钥,证书认证机构应用2048位或以上。

[编辑] 已公开的或已知的攻击方法针对RSA最流行的攻击一般是基于大数因数分解。1999年,RSA-155(512 bits)被成功分解,花了五个月时间(约8000 MIPS 年)和224 CPU hours 在一台有3.2G中央内存的Cray C916计算机上完成 。

2002年,RSA-158也被成功因数分解。

RSA-158表示如下:

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139
2009年12月12日,编号为 RSA-768 (768 bits, 232 digits)数也被成功分解[1]。这一事件威胁了现通行的1024-bit密钥的安全性,普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下:

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917
2011-8-29 14:03
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
6
在已知 e, n 求 d 的情况下, 这只是解一个一元一次同余方程而已, 即使 n 是一个512 bits 或更大(当然不要说是 102400000 bits)的数, 所用的时间只是O(1)级的.
另外, 按 RSA 文档, 不建议 e 选 3, 常用的是 65537.
2011-8-29 20:40
0
雪    币: 2307
活跃值: (1013)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
7
楼上的哥哥所言极是,不懂你是想用n求p,q还是做什么,e与d只是对于φn的乘法逆元,简单的说~~
2011-8-29 22:20
0
雪    币: 35
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
他的难解也就基于大数分解问题啊,这个在任何公共基础教材上都会说明。要是轻易就解了岂不是没有任何安全性可言了啊。
2011-9-2 00:11
0
游客
登录 | 注册 方可回帖
返回
//