数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

[建议] 在灌水版建立一个博弈版块如何?

[复制链接]
发表于 2008-5-6 15:34:46 | 显示全部楼层
原帖由 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 ] 窗口
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 15:41:43 | 显示全部楼层
也可手工解
$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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 16:01:11 | 显示全部楼层
由目前的分解测试看出来
90位并不是一个安全的位数
如果有双核的高频Core2机器
不排除在2小时内分解掉的可能
所以120甚至150位才是比较合适的

我倾向于512二进制位,大概150左右
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 16:13:25 | 显示全部楼层
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 17:09:04 | 显示全部楼层
原帖由 无心人 于 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$怎么求呀?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 17:10:53 | 显示全部楼层


我晕
手工的意思是写代码用程序做
有现成算法啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 17:12:41 | 显示全部楼层
呵呵,就俺实在
不过就是不知道用什么算法。那个方幂很大呀,请各位赐教
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 17:14:00 | 显示全部楼层
给个大概估计,不过估计也不怎么准
100 18300000
110 6*10^12
120 3.8*10^25
130 5.4*10^59
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 17:16:29 | 显示全部楼层
原帖由 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. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 17:18:44 | 显示全部楼层
thank you。
看来只用计算器是算不出来了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-11-29 21:36 , Processed in 0.100122 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表