1977 жылғы RSA шифрын бұзу: «Құлыққан сүйекұзар» кодының шешілуі

Кіріспе

"Сөздер сиқырлы - бұл кірпікшіл сүйек" 1977 жылы RSA шифрын ойлап тапқандардың шифрмәтінге қойған сынағының шешімі болды. Мәселе Мартин Гарднердің "Математикалық ойындар" бағанында 1977 жылғы Scientific American журналының тамыз айында жарияланды. Бұл мәселені 1993–94 жылдары Дерек Аткинс, Майкл Графф, Арьен Ленстра және Пол Лейланд басқарған үлкен бірлескен компьютерлік жоба шешті. 600-дан астам еріктілер шамамен 1600 машинадан (оның екеуі факс машиналары) алты ай бойы процессорлық уақытты үлестірді. Координация Интернет арқылы жасалды және бұл сияқты алғашқы жобалардың бірі болды. Ossifrage ("сүйек сындыратын", латын тілінен) – сақалды құрлықаяқтың ескі аты, ол жануарлардың сүйектерін және тірі тасбақаларды жартастардың үстіне тастап, оларды жарып алуымен әйгілі. 1993–94 жылдардағы күш-жігер криптоанализдік сынақтарда "кірпікшіл ossifrage" сөздерін пайдалану дәстүрін қалыптастырды. RSA шифрын бұзудың қиындығы – шифрмәтін мен ашық кілт берілгенде қарапайым мәтінді қалпына келтіру – үлкен сандарды факторлаудың қиындығымен байланысты. Екі мәселенің математикалық тұрғыдан эквивалентті екені белгісіз, бірақ факторлау қазіргі уақытта RSA-ны тікелей бұзудың жалғыз белгілі әдісі болып табылады. 1977 жылғы шифрмәтінді шифрлау үшін қарапайым мәтінді қалпына келтіру мақсатында 129 таңбалы (426 биттік) RSA 129 саны факторланды. Рон Ривест 1977 жылы 125 таңбалы жартылай жай санды факторлауға сол кездегі ең жақсы алгоритм мен ең жылдам компьютерлерді пайдалана отырып, 40 квадриллион жыл қажет болады деп есептеген. Олардың бастапқы мақаласында болашақ дамуларға қарсы қауіпсіздік маржасын қамтамасыз ету үшін 200 таңбалы (663 биттік) жай сандарды пайдалану ұсынылды, бірақ бұл шешімді кейінге қалдырған болуы мүмкін, өйткені 200 таңбалы жартылай жай сан 2005 жылы факторланды. Дегенмен, сол кезде тиімді факторлау алгоритмдері жеткілікті зерттелмеген, ал келесі онжылдықтарда көптеген жетістіктерге қол жеткізілді. Аткинс және т.б. 1981 жылы Карл Померанс ойлап тапқан квадраттық елеу алгоритмін қолданды. Асимптотикалық жағынан жылдам сандық өріс елеуі жаңа ғана ойлап табылған болса да, ол 129 таңбалы сандар үшін квадраттық елеуден жақсы болатыны сол кезде анық емес еді. Жаңа алгоритмнің жад талаптары да алаңдатушылық тудырды. Сынаққа 100 АҚШ доллары сыйлық қарастырылды, жеңімпаздар оны Free Software Foundation-ға сыйлады. 2015 жылы сол RSA 129 саны шамамен бір күнде, CADO NFS ашық бастапқы кодты сандық өріс елеуінің іске асырылуы арқылы, коммерциялық бұлтты есептеу қызметін пайдалана отырып, шамамен 30 долларға факторландырылды.

"The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American. It was solved in 1993–94 by a large, joint computer project co ordinated by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland. More than 600 volunteers contributed CPU time from about 1,600 machines (two of which were fax machines) over six months. The coordination was done via the Internet and was one of the first such projects. Ossifrage ('bone breaker', from Latin) is an older name for the bearded vulture, a scavenger famous for dropping animal bones and live tortoises on top of rocks to crack them open. The 1993–94 effort began the tradition of using the words "squeamish ossifrage" in cryptanalytic challenges. The difficulty of breaking the RSA cipher—recovering a plaintext message given a ciphertext and the public key—is connected to the difficulty of factoring large numbers. While it is not known whether the two problems are mathematically equivalent, factoring is currently the only publicly known method of directly breaking RSA. The decryption of the 1977 ciphertext involved the factoring of a 129 digit (426 bit) number, RSA 129, in order to recover the plaintext. Ron Rivest estimated in 1977 that factoring a 125 digit semiprime would require 40 quadrillion years, using the best algorithm known and the fastest computers of the day. In their original paper they recommended using 200 digit (663 bit) primes to provide a margin of safety against future developments, though it may have only delayed the solution as a 200 digit semiprime was factored in 2005. However, efficient factoring algorithms had not been studied much at the time, and a lot of progress was made in the following decades. Atkins et al. used the quadratic sieve algorithm invented by Carl Pomerance in 1981. While the asymptotically faster number field sieve had just been invented, it was not clear at the time that it would be better than the quadratic sieve for 129 digit numbers. The memory requirements of the newer algorithm were also a concern. There was a US$100 prize associated with the challenge, which the winners donated to the Free Software Foundation. In 2015, the same RSA 129 number was factored in about one day, with the CADO NFS open source implementation of number field sieve, using a commercial cloud computing service for about $30.