在灌水版建立一个博弈版块如何？

gxqcn

原帖由 mathe 于 2008-5-6 14:56 发表
gxqcn的HugeCalc里面有RSATool,可以用一用看。不过据medie2005说比较难看懂该怎么用(可能界面上提示比较少）

很简单的。
如：x^877=1347602418762670020207110630011012391306796656138569913597146753558169
(mod 3114737665614036551724192975736494577899839808364045105215740888438567)
并已知：p=24571843890568162730310908961971921 q=126760436843309930202877195135812727

[img=http://www.emath.ac.cn/image/ui_RSATool.gif]最直观的 RSA 算法教程（含源代码及程序）[/img]

• 启动上述程序 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的大概时间是多少秒？
=======================================
这里似乎存在一个临界点
超越临界点会存在时间的大幅度增加

shshsh_0510

原帖由 无心人 于 2008-5-6 15:41 发表
也可手工解
$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$怎么求呀？

无心人

我晕
手工的意思是写代码用程序做
有现成算法啊

shshsh_0510

呵呵，就俺实在
不过就是不知道用什么算法。那个方幂很大呀，请各位赐教

mathe

给个大概估计，不过估计也不怎么准
100 18300000
110 6*10^12
120 3.8*10^25
130 5.4*10^59

mathe

原帖由 shshsh_0510 于 2008-5-6 17:12 发表
呵呵，就俺实在
不过就是不知道用什么算法。那个方幂很大呀，请各位赐教

a^b (mod p)
可以使用下面伪码的方法

1. r=1;
   
2. m=a;
   
3. while(b){
   
4.   if(b&1){
   
5.      r=(r*m)%p;
   
6.   }
   
7.   m=(m*m)%p;
   
8.   b>>=1;
   
9. }

复制代码

shshsh_0510

thank you。
看来只用计算器是算不出来了