数学研发论坛

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

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

[复制链接]
发表于 2008-5-6 10:39:55 | 显示全部楼层
85位的不对
还不如80的长

评分

参与人数 1贡献 +1 收起 理由
mathe + 1 已修改,发现CHugeIntX::GeneratePrime(140 ...

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 14:14:43 | 显示全部楼层
signature^697=44583379684764213868431721926136605529750126332148393391083714467200675872771867145040612
(mod 195829895438658706737622283850473406883420690004301400096152802481984054576589511059194683)


RSA 不是很懂,问一下,44583379684764213868431721926136605529750126332148393391083714467200675872771867145040612 可是密文,
697 和  195829895438658706737622283850473406883420690004301400096152802481984054576589511059194683 可是公钥 E 和 P。

另外,可否推荐一块RSA 工具,可将密文用公钥解密。

网上说,129位(10进制)是一个临界值,n >129位,很难在合理的时间内分解,不知各位老大怎么看?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 14:38:30 | 显示全部楼层
RSA解密很难,主要就是要对公钥进行因子分解。
无心人在BBS上已经提供了好几个因子分解的库文件(和源代码等),使用他们应该很不错。
而因子分解的时间复杂度是指数递增的,在n比较大的时候就很难成功了。这个无心人应该比较熟悉。比如他上面能够估计出分解那个90位整数大概需要1天时间。而他分解那个60位左右的数只用了数秒。从这些数据我们也可以猜测n稍微大一些分解已经很难了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 14:40:51 | 显示全部楼层
我们这种平凡人,对于RSA破解,能做的也只是搜一些大牛开发的大数分解工具,借助这些工具来破解.
其实,也没什么意义了,都是别人嚼了又嚼的东西了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 14:45:16 | 显示全部楼层
我说的解密不是破解。解密是指 下文中的解密:
    比如数字签名,信息发布者用私钥加密数据,信息阅读方用 信息发布者 提供的公钥解密数据
    或者在通信中,发送方用接受方提供的公钥加密数据,接受方用用自己的私钥来解密数据
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 14:50:06 | 显示全部楼层
Tue May 06 10:56:05 2008  
Tue May 06 10:56:05 2008  
Tue May 06 10:56:05 2008  Msieve v. 0.88
Tue May 06 10:56:05 2008  random seeds: 49525ad0 79e91a8e
Tue May 06 10:56:05 2008  factoring 23062496730092690709353215131843843057725682565268421456019 (59 digits)
Tue May 06 10:56:05 2008  using multiplier of 19
Tue May 06 10:56:05 2008  using sieve block of 65536
Tue May 06 10:56:05 2008  using a sieve bound of 51941 (2647 primes)
Tue May 06 10:56:05 2008  using large prime bound of 2389286
Tue May 06 10:57:12 2008  found 2752 relations (1457 full + 1295 partial), need 2743
Tue May 06 10:57:12 2008  begin with 11347 relations
Tue May 06 10:57:12 2008  reduce to 2411 relations in 2 passes
Tue May 06 10:57:12 2008  attempting to read 1457 full and 2411 partial relations
Tue May 06 10:57:12 2008  recovered 1457 full and 2411 partial relations
Tue May 06 10:57:12 2008  recovered 2886 polynomials
Tue May 06 10:57:12 2008  attempting to build 1295 cycles
Tue May 06 10:57:12 2008  found 1295 cycles in 1 passes
Tue May 06 10:57:12 2008  distribution of cycle lengths:
Tue May 06 10:57:12 2008     length 2 : 1295
Tue May 06 10:57:12 2008  largest cycle: 2 relations
Tue May 06 10:57:12 2008  2647 x 2711 system, weight 66861 (avg 24.66/col)
Tue May 06 10:57:12 2008  reduce to 2489 x 2553 in 3 passes
Tue May 06 10:57:12 2008  lanczos halted after 41 iterations
Tue May 06 10:57:12 2008  recovered 61 nontrivial dependencies
Tue May 06 10:57:13 2008  prp29 factor: 78845314666500290207081997553
Tue May 06 10:57:13 2008  prp30 factor: 292503071712534603216698269123
Tue May 06 10:57:13 2008  elapsed time 00:01:08
Tue May 06 11:01:43 2008  
Tue May 06 11:01:43 2008  
Tue May 06 11:01:43 2008  Msieve v. 0.88
Tue May 06 11:01:43 2008  random seeds: 4493e188 546d9f56
Tue May 06 11:01:43 2008  factoring 19568751779704846894153757735636728037621270144025906037913319859 (65 digits)
Tue May 06 11:01:43 2008  using multiplier of 31
Tue May 06 11:01:43 2008  using sieve block of 65536
Tue May 06 11:01:43 2008  using a sieve bound of 126551 (5933 primes)
Tue May 06 11:01:43 2008  using large prime bound of 12401998
Tue May 06 11:03:29 2008  found 6485 relations (3130 full + 3355 partial), need 6029
Tue May 06 11:03:29 2008  begin with 34843 relations
Tue May 06 11:03:29 2008  reduce to 6259 relations in 2 passes
Tue May 06 11:03:29 2008  attempting to read 3130 full and 6259 partial relations
Tue May 06 11:03:29 2008  recovered 3130 full and 6259 partial relations
Tue May 06 11:03:29 2008  recovered 7883 polynomials
Tue May 06 11:03:29 2008  attempting to build 3355 cycles
Tue May 06 11:03:29 2008  found 3355 cycles in 1 passes
Tue May 06 11:03:29 2008  distribution of cycle lengths:
Tue May 06 11:03:29 2008     length 2 : 3355
Tue May 06 11:03:29 2008  largest cycle: 2 relations
Tue May 06 11:03:29 2008  5933 x 5997 system, weight 158827 (avg 26.48/col)
Tue May 06 11:03:29 2008  reduce to 5543 x 5607 in 3 passes
Tue May 06 11:03:30 2008  lanczos halted after 89 iterations
Tue May 06 11:03:30 2008  recovered 63 nontrivial dependencies
Tue May 06 11:03:32 2008  prp32 factor: 67148917862769937322043077366873
Tue May 06 11:03:32 2008  prp33 factor: 291423188973750394352320153627883
Tue May 06 11:03:32 2008  elapsed time 00:01:49
Tue May 06 11:47:27 2008  
Tue May 06 11:47:27 2008  
Tue May 06 11:47:27 2008  Msieve v. 0.88
Tue May 06 11:47:27 2008  random seeds: 88881100 7e8768c6
Tue May 06 11:47:27 2008  factoring 3114737665614036551724192975736494577899839808364045105215740888438567 (70 digits)
Tue May 06 11:47:27 2008  using multiplier of 35
Tue May 06 11:47:27 2008  using sieve block of 65536
Tue May 06 11:47:27 2008  using a sieve bound of 233881 (10467 primes)
Tue May 06 11:47:27 2008  using large prime bound of 19178242
Tue May 06 11:51:36 2008  found 10753 relations (5598 full + 5155 partial), need 10563
Tue May 06 11:51:36 2008  begin with 51974 relations
Tue May 06 11:51:36 2008  reduce to 9645 relations in 2 passes
Tue May 06 11:51:36 2008  attempting to read 5598 full and 9645 partial relations
Tue May 06 11:51:36 2008  recovered 5598 full and 9645 partial relations
Tue May 06 11:51:36 2008  recovered 13216 polynomials
Tue May 06 11:51:36 2008  attempting to build 5155 cycles
Tue May 06 11:51:36 2008  found 5155 cycles in 1 passes
Tue May 06 11:51:36 2008  distribution of cycle lengths:
Tue May 06 11:51:36 2008     length 2 : 5155
Tue May 06 11:51:36 2008  largest cycle: 2 relations
Tue May 06 11:51:36 2008  10467 x 10531 system, weight 299853 (avg 28.47/col)
Tue May 06 11:51:37 2008  reduce to 9468 x 9532 in 3 passes
Tue May 06 11:51:39 2008  lanczos halted after 151 iterations
Tue May 06 11:51:39 2008  recovered 62 nontrivial dependencies
Tue May 06 11:51:43 2008  prp35 factor: 24571843890568162730310908961971921
Tue May 06 11:51:43 2008  prp36 factor: 126760436843309930202877195135812727
Tue May 06 11:51:43 2008  elapsed time 00:04:16
Tue May 06 11:56:40 2008  
Tue May 06 11:56:40 2008  
Tue May 06 11:56:40 2008  Msieve v. 0.88
Tue May 06 11:56:40 2008  random seeds: 354216f0 8baf5ebe
Tue May 06 11:56:40 2008  factoring 269239885904399464077666682592356844323423389153434388696172765128368027801 (75 digits)
Tue May 06 11:56:41 2008  using multiplier of 1
Tue May 06 11:56:41 2008  using sieve block of 65536
Tue May 06 11:56:41 2008  using a sieve bound of 715679 (28599 primes)
Tue May 06 11:56:41 2008  using large prime bound of 70852221
Tue May 06 12:04:54 2008  found 28715 relations (16018 full + 12697 partial), need 28695
Tue May 06 12:04:54 2008  begin with 143302 relations
Tue May 06 12:04:54 2008  reduce to 23781 relations in 2 passes
Tue May 06 12:04:54 2008  attempting to read 16018 full and 23781 partial relations
Tue May 06 12:04:55 2008  recovered 16018 full and 23781 partial relations
Tue May 06 12:04:55 2008  recovered 29559 polynomials
Tue May 06 12:04:55 2008  attempting to build 12697 cycles
Tue May 06 12:04:55 2008  found 12697 cycles in 1 passes
Tue May 06 12:04:55 2008  distribution of cycle lengths:
Tue May 06 12:04:55 2008     length 2 : 12697
Tue May 06 12:04:55 2008  largest cycle: 2 relations
Tue May 06 12:04:55 2008  28599 x 28663 system, weight 793333 (avg 27.68/col)
Tue May 06 12:04:56 2008  reduce to 24062 x 24126 in 4 passes
Tue May 06 12:05:15 2008  lanczos halted after 382 iterations
Tue May 06 12:05:16 2008  recovered 60 nontrivial dependencies
Tue May 06 12:05:24 2008  prp37 factor: 8183269180297971111478441181493536633
Tue May 06 12:05:24 2008  prp38 factor: 32901262316119465396381940043223396897
Tue May 06 12:05:25 2008  elapsed time 00:08:45
Tue May 06 14:56:05 2008  
Tue May 06 14:56:05 2008  Msieve v. 0.88
Tue May 06 14:56:05 2008  random seeds: 80a24078 e8556c46
Tue May 06 14:56:05 2008  factoring 24754629007703530595783597953118663273500649152609142573755968421157144229186131 (80 digits)
Tue May 06 14:56:08 2008  using multiplier of 11
Tue May 06 14:56:08 2008  using sieve block of 65536
Tue May 06 14:56:08 2008  using a sieve bound of 1234969 (47647 primes)
Tue May 06 14:56:08 2008  using large prime bound of 123496900
Tue May 06 15:38:29 2008  found 47885 relations (26202 full + 21683 partial), need 47743
Tue May 06 15:38:30 2008  begin with 245412 relations
Tue May 06 15:38:30 2008  reduce to 40683 relations in 2 passes
Tue May 06 15:38:30 2008  attempting to read 26202 full and 40683 partial relations
Tue May 06 15:38:32 2008  recovered 26202 full and 40683 partial relations
Tue May 06 15:38:32 2008  recovered 57409 polynomials
Tue May 06 15:38:32 2008  attempting to build 21683 cycles
Tue May 06 15:38:32 2008  found 21683 cycles in 1 passes
Tue May 06 15:38:32 2008  distribution of cycle lengths:
Tue May 06 15:38:32 2008     length 2 : 21683
Tue May 06 15:38:32 2008  largest cycle: 2 relations
Tue May 06 15:38:33 2008  47647 x 47711 system, weight 1417651 (avg 29.71/col)
Tue May 06 15:38:33 2008  reduce to 40343 x 40407 in 4 passes
Tue May 06 15:40:44 2008  lanczos halted after 640 iterations
Tue May 06 15:40:45 2008  recovered 60 nontrivial dependencies
Tue May 06 15:41:19 2008  prp40 factor: 2698729977431574411732833294724178719161
Tue May 06 15:41:19 2008  prp40 factor: 9172695754935407463828342942914640433771
Tue May 06 15:41:19 2008  elapsed time 00:45:14


这是原始的二次筛运算记录Tue May 06 14:56:05 2008  
59   1:08
65   1:49
70   4:16
75   8:45
80  45:14
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 14:56:50 | 显示全部楼层
原帖由 liangbch 于 2008-5-6 14:45 发表
我说的解密不是破解。解密是指 下文中的解密:
    比如数字签名,信息发布者用私钥加密数据,信息阅读方用 信息发布者 提供的公钥解密数据
    或者在通信中,发送方用接受方提供的公钥加密数据,接受方用用自己的 ...

gxqcn的HugeCalc里面有RSATool,可以用一用看。不过据medie2005说比较难看懂该怎么用(可能界面上提示比较少)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 14:57:25 | 显示全部楼层
我说的破解就是你说的解密.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 15:04:22 | 显示全部楼层
Tue May 06 09:26:00 2008  
Tue May 06 09:26:00 2008  
Tue May 06 09:26:00 2008  Msieve v. 0.88
Tue May 06 09:26:00 2008  random seeds: 8b6f3420 bd53e1d8
Tue May 06 09:26:00 2008  factoring 195829895438658706737622283850473406883420690004301400096152802481984054576589511059194683 (90 digits)
Tue May 06 09:26:04 2008  using multiplier of 7
Tue May 06 09:26:04 2008  using sieve block of 65536
Tue May 06 09:26:04 2008  using a sieve bound of 1572433 (59667 primes)
Tue May 06 09:26:04 2008  using large prime bound of 125794640
Tue May 06 09:26:04 2008  using double large prime bound of 379657280734080
Tue May 06 14:44:36 2008  found 59796 relations (15600 full + 44196 partial), need 59763
Tue May 06 14:44:42 2008  begin with 634005 relations
Tue May 06 14:44:43 2008  reduce to 130582 relations in 9 passes
Tue May 06 14:44:43 2008  attempting to read 15600 full and 130582 partial relations
Tue May 06 14:44:48 2008  recovered 15600 full and 130582 partial relations
Tue May 06 14:44:48 2008  recovered 140385 polynomials
Tue May 06 14:44:49 2008  attempting to build 44196 cycles
Tue May 06 14:44:49 2008  found 44196 cycles in 6 passes
Tue May 06 14:44:49 2008  distribution of cycle lengths:
Tue May 06 14:44:49 2008     length 2 : 11437
Tue May 06 14:44:49 2008     length 3 : 10642
Tue May 06 14:44:49 2008     length 4 : 8117
Tue May 06 14:44:49 2008     length 5 : 5742
Tue May 06 14:44:49 2008     length 6 : 3668
Tue May 06 14:44:49 2008     length 7 : 2094
Tue May 06 14:44:49 2008     length 8 : 1187
Tue May 06 14:44:49 2008     length 9+: 1309
Tue May 06 14:44:49 2008  largest cycle: 20 relations
Tue May 06 14:44:50 2008  59667 x 59731 system, weight 3451894 (avg 57.79/col)
Tue May 06 14:44:50 2008  reduce to 58340 x 58404 in 3 passes
Tue May 06 14:47:52 2008  lanczos halted after 924 iterations
Tue May 06 14:47:53 2008  recovered 62 nontrivial dependencies
Tue May 06 14:49:00 2008  prp45 factor: 193586843950321608506064410069661525156328021
Tue May 06 14:49:00 2008  prp46 factor: 1011586797132312935871084948418941679079526223
Tue May 06 14:49:00 2008  elapsed time 05:23:00
Tue May 06 15:00:31 2008  
Tue May 06 15:00:31 2008  
Tue May 06 15:00:31 2008  Msieve v. 0.88
Tue May 06 15:00:31 2008  random seeds: 79f173e0 94207b2c
Tue May 06 15:00:31 2008  factoring 23062496730092690709353215131843843057725682565268421456019 (59 digits)
Tue May 06 15:00:31 2008  using multiplier of 19
Tue May 06 15:00:31 2008  using sieve block of 65536
Tue May 06 15:00:31 2008  using a sieve bound of 51941 (2647 primes)
Tue May 06 15:00:31 2008  using large prime bound of 2389286
Tue May 06 15:00:51 2008  found 3283 relations (1663 full + 1620 partial), need 2743
Tue May 06 15:00:51 2008  begin with 12784 relations
Tue May 06 15:00:51 2008  reduce to 3001 relations in 2 passes
Tue May 06 15:00:51 2008  attempting to read 1663 full and 3001 partial relations
Tue May 06 15:00:51 2008  recovered 1663 full and 3001 partial relations
Tue May 06 15:00:51 2008  recovered 3409 polynomials
Tue May 06 15:00:51 2008  attempting to build 1620 cycles
Tue May 06 15:00:51 2008  found 1620 cycles in 1 passes
Tue May 06 15:00:51 2008  distribution of cycle lengths:
Tue May 06 15:00:51 2008     length 2 : 1620
Tue May 06 15:00:51 2008  largest cycle: 2 relations
Tue May 06 15:00:52 2008  2647 x 2711 system, weight 64391 (avg 23.75/col)
Tue May 06 15:00:52 2008  reduce to 2453 x 2517 in 3 passes
Tue May 06 15:00:52 2008  lanczos halted after 40 iterations
Tue May 06 15:00:52 2008  recovered 64 nontrivial dependencies
Tue May 06 15:00:53 2008  prp29 factor: 78845314666500290207081997553
Tue May 06 15:00:53 2008  prp30 factor: 292503071712534603216698269123
Tue May 06 15:00:53 2008  elapsed time 00:00:22

另外一台机器上的90位的结果,比预期的少很多
顺便测试了那个59位的做参考
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 15:04:59 | 显示全部楼层
原帖由 medie2005 于 2008-5-6 14:40 发表
我们这种平凡人,对于RSA破解,能做的也只是搜一些大牛开发的大数分解工具,借助这些工具来破解.
其实,也没什么意义了,都是别人嚼了又嚼的东西了

是的,其实对我们就是一种游戏而已
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-4-20 18:04 , Processed in 0.175950 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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