原帖由 mathe 于 2008-5-6 14:56 发表 http://images.5d6d.net/dz60/common/back.gif
gxqcn的HugeCalc里面有RSATool,可以用一用看。不过据medie2005说比较难看懂该怎么用(可能界面上提示比较少）
很简单的。
如：x^877=1347602418762670020207110630011012391306796656138569913597146753558169
(mod 3114737665614036551724192975736494577899839808364045105215740888438567)
并已知：p=24571843890568162730310908961971921 q=126760436843309930202877195135812727
最直观的 RSA 算法教程（含源代码及程序）
[*]启动上述程序 RSATool
[*]切换输出模式到 Dec(10)
[*]粘贴 877 进 Public Exponent [ E ] 窗口
[*]粘贴 p=24571843890568162730310908961971921 进 1st Prime [ P ] 窗口
[*]粘贴 q=126760436843309930202877195135812727 进 2st Prime [ Q ] 窗口
[*]随后依次点击 Set&Check - P 按钮、Set&Check - Q 按钮，通过测试后，N、D 均会同步更新，请检查 N==3114737665614036551724192975736494577899839808364045105215740888438567 ? （千万别点进去那个 Public Key - Modulus [ N = P * Q ] 窗口，否则程序认为你只知道“Public Key”）
[*]清空下面的 Original Message(text) [ OM < N ] 窗口中的文本
[*]粘贴 1347602418762670020207110630011012391306796656138569913597146753558169 进 Encrypt Message [ EM = OM^E mod N ] 窗口
[*]解密好的明码请见 Decrypt Message [ DM = EM^D mod N ] 窗口
也可手工解
$n = p * q$
$(e, p-1) = (e, q - 1) = 1$
求出d
$ed = 1 mod (p-1)*(q-1)$
则加密是
$em=om^e mod n$
解密是
$om=em^d mod n$
由目前的分解测试看出来
90位并不是一个安全的位数
如果有双核的高频Core2机器
不排除在2小时内分解掉的可能
所以120甚至150位才是比较合适的
我倾向于512二进制位，大概150左右
n t lgn lgt
59 68 4.077537444 4.219507705
65 109 4.17438727 4.691347882
70 256 4.248495242 5.545177444
75 525 4.317488114 6.263398263
80 2714 4.382026635 7.90617884
90 599001 4.49980967 13.30301855
100 4.605170186
110 4.700480366
120 4.787491743
130 4.86753445
140 4.941642423
150 5.010635294
帮我分析下100-150的大概时间是多少秒？
=======================================
这里似乎存在一个临界点
超越临界点会存在时间的大幅度增加
原帖由 无心人 于 2008-5-6 15:41 发表 http://images.5d6d.net/dz60/common/back.gif
也可手工解
$n = p * q$
$(e, p-1) = (e, q - 1) = 1$
求出d
$ed = 1 mod (p-1)*(q-1)$
则加密是
$em=om^e mod n$
解密是
$om=em^d mod n$
我就手工解，求D就累得半死了。
那个$om=em^d mod n$怎么求呀？
:)
我晕
手工的意思是写代码用程序做
有现成算法啊
呵呵，就俺实在
不过就是不知道用什么算法。那个方幂很大呀，请各位赐教
给个大概估计，不过估计也不怎么准
100 18300000
110 6*10^12
120 3.8*10^25
130 5.4*10^59
原帖由 shshsh_0510 于 2008-5-6 17:12 发表 http://images.5d6d.net/dz60/common/back.gif
呵呵，就俺实在
不过就是不知道用什么算法。那个方幂很大呀，请各位赐教
a^b (mod p)
可以使用下面伪码的方法r=1;
m=a;
while(b){
if(b&1){
r=(r*m)%p;
}
m=(m*m)%p;
b>>=1;
}
thank you。
看来只用计算器是算不出来了