Re discrete logs: This email describes the recent attack on the discrete log problem. Q: this descrete log solution uses a 'safe' prime; does a 'safe' prime make the DLP harder or easier ?? https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912 Subject: 795-bit factoring and discrete logarithms From: Emmanuel Thomé <[log in to unmask]> Date: Mon, 2 Dec 2019 13:53:58 +0100 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 (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 [1] https://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage [2] https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt [3] https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;a0c66b63.1606 [4] http://cado-nfs.gforge.inria.fr/ [5] https://www.grid5000.fr [6] http://explor.univ-lorraine.fr/ [7] http://www.prace-ri.eu/prace-in-a-few-words/ [8] https://caramba.inria.fr/dlp240-rsa240.txt