|
[转帖][Cado-nfs-discuss] 795-bit factoring and discrete logarithms (RSA-240 于2019年12月2日被破解)
这一次, cado-nfs 实现了2个重量级的计算: 1. 分解了 795 bits 的RSA -Number; 2. 计算了 795 bits的离散对数。 795 bits 模P的 离散对数, NFS的矩阵量级 和RSA 795 bits 数量级一样。计算量大概2-3倍。 RSA-240 sieving: 800 physical core-years RSA-240 matrix: 100 physical core-years DLP-240 sieving: 2400 physical core-years DLP-240 matrix: 700 physical core-years DLog描述如下: G^X = Y mod P Y是hex("The magic words are still Squeamish Ossifrage") G = 5; Y = 774356626343973985966622216006087686926705588649958206166317147722421706101723470351970238538755049093424997 P-795 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029285303 用数域筛法,指数积分 求解离散对数: dlog X = 92603135928144195363094955331732855502961099191437611616729420475898744562365366788100548099072093487548258752802923326447367244150096121629264809207598195062213366889859186681126928982506005127728321426751244111412371767375547225045851716 X 是一个 794 bits的大整数。 Dear cado-nfs-discuss subscribers, We are pleased to announce the factorization of RSA-240, from RSA's challenge list, and the computation of a discrete logarithm of the same size (795 bits): RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 Let p = RSA-240 + 49204 be the first safe prime above RSA-240. We chose as a target the encoding of the sentence "The magic words are still Squeamish Ossifrage" (in reference to the factorization of RSA-129 [1]): target_str="The magic words are still Squeamish Ossifrage" target_hex=`echo -n $target_str | xxd -p -c 256` target_hex=${target_hex^^} target=`echo "ibase=16; $target_hex" | BC_LINE_LENGTH=0 bc` target = 774356626343973985966622216006087686926705588649958206166317147722421706101723470351970238538755049093424997 we have with generator g = 5: log(target) = 92603135928144195363094955331732855502961099191437611616729420475898744562365366788100548099072093487548258752802923326447367244150096121629264809207598195062213366889859186681126928982506005127728321426751244111412371767375547225045851716 which can be checked with 5^926...716 = target mod p. The previous records were RSA-768 (768 bits) in December 2009 [2], and a 768-bit prime discrete logarithm in June 2016 [3]. It is the first time that two records for integer factorization and discrete logarithm are broken together, moreover with the same hardware and software. Both computations were performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software [4]. The sum of the computation time for both records is roughly 4000 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz). A rough breakdown of the time spent in the main computation steps is as follows. RSA-240 sieving: 800 physical core-years RSA-240 matrix: 100 physical core-years DLP-240 sieving: 2400 physical core-years DLP-240 matrix: 700 physical core-years The computation times above are well below the time that was spent with the previous 768-bit records. To measure how much of this can be attributed to Moore's law, we ran our software on machines that are identical to those cited in the 768-bit DLP computation [3], and reach the conclusion that sieving for our new record size on these old machines would have taken 25% less time than the reported sieving time of the 768-bit DLP computation. Another estimation can be made with the rough complexity ratio given by the L_N(1/3,(64/9)^(1/3)) formula that, up to (1+o(1)) factors in the exponent, is customarily taken as an estimation of the expected hardness increase from one computation to the next. This would suggest that 795-bit computations should be 2.25 times harder than 768-bit computations. Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records. The acceleration can be attributed to various algorithmic improvements that were implemented for these computations. The CADO-NFS implementation was also vastly improved. We used computer resources of the Grid'5000 experimental testbed in France (INRIA, CNRS, and partner institutions) [5], of the EXPLOR computing center at Université de Lorraine, Nancy, France [6], an allocation of computing hours on the PRACE research infrastructure using resources at the Juelich supercomputing center in Germany [7], as well as computer equipment gifted by Cisco Systems, Inc. to the University of Pennsylvania. More details will be given in a forthcoming scientific publication. Fabrice Boudot, Éducation Nationale and Université de Limoges, France Pierrick Gaudry, CNRS, Nancy, France Aurore Guillevic, INRIA, Nancy, France Nadia Heninger, University of Pennsylvania and University of California, San Diego, United States Emmanuel Thomé, INRIA, Nancy, France Paul Zimmermann, INRIA, Nancy, France
最后于 2019-12-13 17:11
被readyu编辑
,原因:
|
|
[转帖]How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
20 million 个量子比特(2000万个量子比特), 对现在是天文数字。 目前只能实现100个左右的量子比特。
最后于 2019-12-13 17:13
被readyu编辑
,原因:
|
|
|
|
|
|
|
|
[2019中秋礼物]《看雪论坛精华15》发布!(礼物1:踩楼中奖;礼物2:论坛取消了回帖扣雪币功能)
中秋快乐!祝看雪越来越好 |
操作理由
RANk
{{ user_info.golds == '' ? 0 : user_info.golds }}
雪币
{{ experience }}
课程经验
{{ score }}
学习收益
{{study_duration_fmt}}
学习时长
基本信息
荣誉称号:
{{ honorary_title }}
能力排名:
No.{{ rank_num }}
等 级:
LV{{ rank_lv-100 }}
活跃值:
在线值:
浏览人数:{{ visits }}
最近活跃:{{ last_active_time }}
注册时间:{{ user_info.create_date_jsonfmt }}
勋章
兑换勋章
证书
证书查询 >
能力值