首页
社区
课程
招聘
[原创][分享]我快算出 RSA-210 (696 bits) 的 Φ(n), 征求有心也有能力的参与者一起努力~
发表于: 2012-11-10 17:10 115372

[原创][分享]我快算出 RSA-210 (696 bits) 的 Φ(n), 征求有心也有能力的参与者一起努力~

2012-11-10 17:10
115372
我快算出 RSA-210 (696 bits) 的 Φ(n)~离世界记录一步之遥~
征求有心也有能力的参与者一起努力~

大家都知道, RSA-768 (232 decimal digits) 于 2009 年 12 月被破解;而 RSA-704 (212 decimal digits) 也于 2012 年 7月被破解。
我现在的工作是挑战 RSA-210 (210 decimal digits, 696 bits)。

RSA-210 的 n 公开如下:( http://en.wikipedia.org/wiki/RSA_numbers#RSA-210 )
245 246 644 900 278 211 976 517 663 573 088 018 467 026 787 678 332 759 743 414 451 715 061 600 830 038 587 216 952 208 399 332 071 549 103 626 827 191 679 864 079 776 723 243 005 600 592 035 631 246 561 218 465 817 904 100 131 859 299 619 933 817 012 149 335 034 875 870 551 067

现在的进展成果如下:
我已经能算出一个很接近 Φ(n) 的数,我暂时叫 Φ(r) =
245 246 644 900 278 211 976 517 663 573 088 018 467 026 787 678 332 759 743 414 451 715 061 600 830 038 587 216 952 208 399 332 071 549 101 645 931 859 158 619 687 407 034 196 610 149 258 087 804 828 145 967 612 829 306 952 905 666 775 862 044 218 476 082 199 931 053 394 866 952

但这个数,并不是真的 Φ(n),我判断真正的 Φ(n),应该比 Φ(r) 小一点点。

譬如往下减 4 =
245 246 644 900 278 211 976 517 663 573 088 018 467 026 787 678 332 759 743 414 451 715 061 600 830 038 587 216 952 208 399 332 071 549 101 645 931 859 158 619 687 407 034 196 610 149 258 087 804 828 145 967 612 829 306 952 905 666 775 862 044 218 476 082 199 931 053 394 866 948

或是 减 8 =
245 246 644 900 278 211 976 517 663 573 088 018 467 026 787 678 332 759 743 414 451 715 061 600 830 038 587 216 952 208 399 332 071 549 101 645 931 859 158 619 687 407 034 196 610 149 258 087 804 828 145 967 612 829 306 952 905 666 775 862 044 218 476 082 199 931 053 394 866  944

或是减 12 =
245 246 644 900 278 211 976 517 663 573 088 018 467 026 787 678 332 759 743 414 451 715 061 600 830 038 587 216 952 208 399 332 071 549 101 645 931 859 158 619 687 407 034 196 610 149 258 087 804 828 145 967 612 829 306 952 905 666 775 862 044 218 476 082 199 931 053 394 866  940

这样下去....应该不会差很多。

我已经设法去计算出很接近真正 Φ(n) 的数。

Φ(n) 就落在 Φ(r) 底下的几个小范围。 (等差为 4 的一个数列, 等差数列)
现在征求有心,也有兴趣的朋友,一同参与这个验证的工作。

若真的成功,成果将共同分享。
谢谢。

2012年11月17日02:29 分,第一次补充及修正。

好几天前,我就给出比较准确的 Φ(r)  值,之前公布的比较不准。
忙,没空来的及更新。

以下这个数,才是精准的估计:

245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549102636379525419241883591878719807874925061718037353593039323605526518763037740989017744115767482964632709008
请以这个 Φ(r) 为 Φ(n) 的上界值。

Φ(n) 的下界范围落在何处,我正在计算,数论的密码学大师裴教授的学生 "没有姓名",也正在参与计算跟验证的行列,如想参者,请配合《没有姓名》及《Cnbragon》等人的分配任务。
衷心的谢谢大家的努力参与及支持。

2012年11月17日03:43 分,第二次补充及修正。

我估算出 Φ(n) 的下界值 Φ(l) Low Bound 是
214590814287743435479452955626452016158648439218541164775487645250678900726283763814833182349415562605464806832084741836648142893879831890559429003282684393909408154835703917658023365390526101296547594053620382

Φ(r)-Φ(l)=
30655830612534776497064707946636002308378348459791594967926806464382700103754823402119026049916508943637829547440677405235448984839975984365632714754669199129915450690814845379717623627218014470935370579088626

2012年11月17日05:27分,第三次补充及修正。
我现计算出最...最...最...接近Φ(n)的下界值 Φ(l) 是

244767647546957356093751027511421830930958375983648516072040595364055621140917418101294098617302126096858295292846658657426787988331683250169348706869311886802918676609474781078682901148568834291374599467410748

2012年11月18日03:28分,第四次补充及修正。
我再一次的计算出更接近Φ(n)的下界值 Φ(l) 是
245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549102513756202968774385245001608969065264951055892857595639630663741661571312620636986683340694745368189992960

2012年11月21日04:04分,第五次补充及修正。
我再一次的估算出接近Φ(n)的下界值 Φ(l) 是
245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549102617986027051721017579734131535066633608723320135703257895405070218987602113186570983810232135299645833216

2012年12月12日补充
完整内容已于11月25日提交至世界密码学会官网的电子平台 ePrint. 
http://eprint.iacr.org/2012/666 处,供大家检验~
PDF 可以在 http://eprint.iacr.org/2012/666.pdf 下载
PS 可以在 http://eprint.iacr.org/2012/666.ps 下载

◎ RSA-210 被破解之前的留帖纪念。(比对 Φ(n) 到底差了多少)

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 0
支持
分享
最新回复 (107)
雪    币: 36
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
厉害!   支持
2012-11-10 17:47
0
雪    币: 59
活跃值: (1501)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
这个厉害。支持!
2012-11-10 18:05
0
雪    币: 1233
活跃值: (907)
能力值: ( LV12,RANK:750 )
在线值:
发帖
回帖
粉丝
4
我是来膜拜楼主和你的头像的,超喜感!!!I like
2012-11-10 18:17
0
雪    币: 1737
活跃值: (110)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
祝愿楼主早日成功撒~~~
2012-11-10 18:19
0
雪    币: 3688
活跃值: (4242)
能力值: (RANK:215 )
在线值:
发帖
回帖
粉丝
6
我不懂这个,但是等待LZ的好消息
2012-11-10 18:51
0
雪    币: 2015
活跃值: (902)
能力值: ( LV12,RANK:1000 )
在线值:
发帖
回帖
粉丝
7
“RSA-201 的 n 公开如下”,应该是“RSA-210 的 n 公开如下”。楼主的电脑一定是在狂奔,这个范围要要有个最小值就好了。
2012-11-10 19:01
0
雪    币: 27
活跃值: (127)
能力值: ( LV8,RANK:120 )
在线值:
发帖
回帖
粉丝
8
Φ(n)是这个意思吗?Φ(n)=(p-1)(q-1)
2012-11-10 19:16
0
雪    币: 190
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
9
好牛掰,膜拜个
2012-11-10 19:46
0
雪    币: 1015
活跃值: (235)
能力值: ( LV12,RANK:440 )
在线值:
发帖
回帖
粉丝
10
占楼,争取成为历史见证。
2012-11-10 19:49
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
11
对笔误~~ a typo.
2012-11-10 19:51
0
雪    币: 221
活跃值: (2311)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
12
占楼,争取成为历史见证。
2012-11-10 20:13
0
雪    币: 107
活跃值: (404)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
我晕死..强帖留名啊.....

密码学很深奥啊....有点意思
2012-11-10 20:18
0
雪    币: 1632
活跃值: (13)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
厉害!有时间的话帮我keygen一个
2012-11-10 20:58
0
雪    币: 15094
活跃值: (4130)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
牛啊,期待早日成功!
2012-11-10 21:30
0
雪    币: 435
活跃值: (1282)
能力值: ( LV13,RANK:388 )
在线值:
发帖
回帖
粉丝
16
等待LZ的好消息 加油
2012-11-10 23:00
0
雪    币: 1708
活跃值: (586)
能力值: ( LV15,RANK:670 )
在线值:
发帖
回帖
粉丝
17
只能膜拜。
2012-11-10 23:21
0
雪    币: 544
活跃值: (264)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
18
虽然看不懂,但是先膜拜了再说。。
2012-11-11 00:07
0
雪    币: 21
活跃值: (26)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
19
破解的思路呢?这块很值得大家来一起讨论的
2012-11-12 13:04
0
雪    币: 67
活跃值: (30)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
按照R大的想法,我写了个验证程序,但是目前看来计算量还是比较大的,我花了10个小时,大概验证了250亿个,现在把验证程序发上来,欢迎有空余计算器的朋友一起算一下。

附件下载回去解压,Factor.exe是验证程序,然后还有很多phiXX.txt的分段验证任务,每个任务的计算量就是10个小时左右。

用法:挑一个任务,将phiXX.txt重命名为phi.txt,然后启动factor.exe,当factor.exe结束时说明找到了分解的结果,否则会一直继续下去的。
期间会更新phi.txt,以确保中间断开了下次还能接着算,同时还会以append的模式将factor.exe输出的内容保存到result.txt中。任务有28个,这就是传说中的“分布式并行”计算么?

下面是我的代码,仅供参考:
int main()
{
        
    f1 = (n + 1) / 2;
    f2 = phi / 2;
    f3 = f1 - f2;
    while(1){
        v1 = f3 * f3 - n;        
        if(mpz::perfect_square(v1)) {
            v2 = mpz::square_root(v1);
            p = f3 + v2;
            q = f3 - v2;
            if(p * q == n) break;
        }
        f3 += 2;
    }

    Log("p:%s", p.ToString(str));
    Log("q:%s", q.ToString(str));
    Log("ok.");    
    
    return 0;
}
上传的附件:
2012-11-15 12:18
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
21
在此, 本人除了谢谢看雪论坛上的众版友之外~
也谢谢热心参与的 "Cnbragon"  及 "没有姓名" , 以及云南某师范大学的 "云云老师" 共同参与 【RSA-210 计划】~
感谢人数众多~族繁不及备载~
无法一一致谢~
等真的成功之后, 再共同发布新闻一一列名致谢。
2012-11-15 18:59
0
雪    币: 1689
活跃值: (379)
能力值: ( LV15,RANK:440 )
在线值:
发帖
回帖
粉丝
22
能放到科学院的超级计算机上跑吗?
2012-11-15 20:11
0
雪    币: 244
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
23
我目前对这个不懂,相信未来会懂,在此见证lz取得的巨大成就,膜拜之
2012-11-15 20:39
0
雪    币: 18
活跃值: (17)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
24
能否重新写成LINUX下可以用的(我还在学习中 我写出来的效率太低了) 我来挂到服务器上计算
2012-11-15 21:05
0
雪    币: 303
活跃值: (30)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
强帖留名...祝早日成功
2012-11-16 09:10
0
游客
登录 | 注册 方可回帖
返回
//