Monday , October 19 2020
Breaking News

# The Factorization of RSA-240, Hacker News

`Dear number theorists,    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 ( (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)  [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    [1]https://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage[2]https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa 768 .txt[3]https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;a0c  (b) . 1606[4]http://cado-nfs.gforge.inria.fr/[5]https: //www.grid 5000 .FR[6]http://explor.univ-lorraine.fr/[7]http://www.prace-ri.eu/prace-in-a-few- words /[8]https://caramba.inria.fr/dlp  (-rsa)  .txt`