Дело застенчивой скопы. Алгоритм RSA

    Я думаю эта история будет интересна многим, в том числе людям, не связанным с математикой.

    В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали свою статью «Новые направления в криптографии» с революционными идеями шифрования с использованием открытого ключа. А затем, три учёных Рональд Райвест, Ади Шамир и Леонард Адлеман в августе 1977 опубликовали в статью в журнале Scientific American, где они подробно описали свой алгоритм, использующий вычисления в кольце целых чисел. Как многим известно, идея алгоритма заключается в существовании условно-одностронней функции — обычного умножения на множестве простых чисел большой длины
    (f:PxP->P*P), обратить которую вычислительно сложно. Иными словами, зная n = p*q (где p и q — простые числа), узнать p и q (или факторизовать число n) при большом n представляется ресурсоёмкой задачей.
    В этом же номере, известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (n, e) — открытый ключ, где длина числа n составляла 129 десятичных знаков, а e было равным 1007, и само зашифрованное сообщение. Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков). Но ситуация изменилась…

    image

    Затем, в 1994 году молодой криптограф американской армии Арьен Ленстра разработал усовершенствование агоритма Квадратичного Решета, позволяющий за разумное время найти простые множители числа до 130 цифр. Асимптотика алгоритма составляла O(esqrt(log n * log log n)), где e — основание натурального логарифма. К слову, асимптотика тривиального алгоритма факторизации O(sqrt(n)), что, дольше для больших n. Сам Ленстра не обладал необходимыми вычислительными мощностями, и тогда он предложил через Интернет добровольцам выделить часть своего процессорного времени на благо математики. Это был один из первых в истории больших проектов, использующих распределённые вычисления. К решению задачи присоединилось 600 человек, предоставив 1600 компьютеров: кроме самых обычных компьютеров участие приняли 3 суперкомпьютера и, если верить русскоязычной Википедии, 2 факс-машины :-). В результате была сформирована итоговая матрица размера 20.000 на 20.000, заполненная единицами и нулями. Далее, в дело вступил метеорологический суперкомпьютер, выделенный самому Ленстре, который за 220 дней непрерывной работы разложил на множители 129 значное число n.
    Ответ оказалася таким:
    RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
    × 32769132993266709549961988190834461413177642967992942539798288533

    Длины чисел p и q оказались 64 и 65 знаков соответственно. Фраза, зашифрованная Мартином Гарднером, была такая: "The Magic Words are Squeamish Ossifrage", что переводится "Волшебные слова — это Застенчивая Скопа", или, по версии русской Википедии, "Волшебные слова — это брезгливый ягнятник". После этого, рекомендуемая длина ключа была увеличена до 140 знаков до тех пор, пока через 4 года не разложили контрольное число из 140 цифр. В 1998 году Билл Гейтс заявил, что предоставляет неограниченное финансирование и вычислительные ресурсы своей компании для разложения числа в 200 знаков. В данный момент, эта цель уже достигнута в 2005 году, задача RSA-200. Из $100, как не трудно посчитать, по процентам за 17 лет получилось примерно $140, которые и были переданы в фонд свободного программного обеспечения :-)
    Вся эта история была прекрасным пиар-ходом для авторов алгоритма и основателей компании, запатентовавшей RSA, и получивших в результате $900 млн прибыли.
    Вот что значит делать деньги с умом ;)

    Источник: профессор Салий Вячеслав Николаевич, СГУ.
    Заранее прошу прощения за неточности.
    Всем спасибо за исправления в комментах!
    Поделиться публикацией

    Комментарии 60

      +4
      Очень познавательно! Спасибо!
        +3
        пожалуйста :)
        +1
        Он таких историй знает… каждую будешь записывать? :)
          +3
          самые интересные :)
            +2
            Было бы здорово еще почитать!
            Спасибо!
          0
          Какой СГУ-то? :) Их много!
          Вдруг земляки?
            0
            Саратов :)
              –4
              Приятно встретить земляков :)
                –4
                Забавно :) где учился?
                  –4
                  Еще учусь. Просто Саратов люблю сильно, не смотря ни на что :)
                    –4
                    Ок, где? :)
                      –4
                      МФТИ :)
                      Но я учился в ФТЛ, у которой сильные связи с СГУ=))
                        –4
                        А, всё понятно )) ну и как в МФТИ учиться? )) в СГУ не напрягают вообще
                –4
                Горжусь что учился в СГУ, жаль только на КНиИТ не попал…
                  –4
                  Здорово :)
                  –1
                  Передавай привет от бывшего студента 522 группы (выпуск 2005) =)
                0
                очень интересная статья!
                  0
                  Почти под копирку из конспектов по предмету «Защита данных», который когда-то в институте писал
                    0
                    Вы что ТАКОЕ записывали в обязательном порядке?!
                      0
                      Зачем же всё?… Тезисно: часть в конспекте, часть в голове :) но на экзамене такие детали преподами всегда поощрялись
                        0
                        Забавно, а нас так спрашивают, что и вставить такие истории негде на экзаменах :)
                    0
                    Всё-таки, скопа и ягнятник — совсем-совсем разные птицы:) И ossifrage — это таки ягнятник, он же бородач.
                      0
                      O(e*sqrt(log n * log log n)) = O(sqrt(log n * log log n))
                        0
                        Вполне логично, что при временах работы, исчисляемые чуть ли не в годах, константы всё же следует оставить. Конечно, формально вы правы, не спорю…
                          +1
                          можно даже так вставить:

                        +1
                        Ассимптотика алгоритма составляла O(e*sqrt(log n * log log n))

                        Вообще-то O(esqrt(log n * log log n)) (и, к слову, аСимптотика).
                        То, что это значительно лучше, чем O(sqrt(n)), не так уж сразу очевидно, по крайней мере, неочевидно, начиная с каких n…
                          0
                          > аСимптотика
                          Спасибо, сейчас исправлю в тексте

                          > Вообще-то…
                          Да, вы правы. Мой косяк, не заметил, сейчас исправлю. Спасибо что сказали.
                          В таком случае конечно менее очевидно, но для n=10^129 кмк всё же интуитивно понятно, какая лучше.
                          0
                          Райвест, Шамир и Адлеман, являющиеся американскими учеными, судя по фамилии, являются не совсем американскими, именно это и заставило их запатентовать то, что до этого Эль-Гамаль запатентовать не додумался. Идеи сильно схожи ведь…

                          Идея RSA же хороша, но наш ГОСТ Р34.10 мне нравится больше. Хотя, наши ведь учились на американских ошибках.
                            0
                            По поводу первенства RSA напишу позже :) вроде народ за
                              0
                              Шамир — израильтянин, работает в институте Вайцмана в Нес-Ционе и ещё в нескольких часных фирмах и Израиле.
                                0
                                Вообще-то еврейские корни я и имел ввиду. Хотя, ничего против совсем не имею…
                              0
                              … использующий вычисления в кольце целых чисел.
                                0
                                исправил
                                0
                                Спасибо, познавательно.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    Только, увы, RSA сейчас уходит в сторонку.
                                      0
                                      хм, а можно поподробнее?
                                      и что приходит в свет?
                                        0
                                        DSA уже пришло, ECC ходит рядом но не везде принято.
                                        В тех же ГОСТах про RSA ни слуху, и используется DSA-подобный алгоритм.
                                          +1
                                          Сваливать в одну кучу алгоритмы шифрования и алгоритмы для цифровых подписей — это как сравнивать помидоры с бананами.
                                            –1
                                            Согласен, товарищ видимо не понимает что говорит…
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                Ошибаетесь. RSA сам по себе ничего автоматически не представляет тексту, кроме шифрования.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    +1
                                                    Какой уникальный ключ?

                                                    Если это имеется ввиду открытый ключ, то нельзя — он одинаков для любого зашифрованого текста.

                                                    Результат работы голого RSA можно, конечно, воспринимать как подпись. Только не стойкую и не обладающую необходимыми криптографическими свойствами. Именно поэтому в стандартах цифровых подписей есть методы дополнения подписываемого текста и хэширование.
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                        +1
                                                        Я, наверное, вас удивлю, но и закрытый ключ тоже одинаков для различных текстов :)

                                                        Цифровая подпись должна удостоверять как подписавшего, так и подписываемый текст. Факт владения закрытым ключом подписываемый текст не удостоверяет никак. Честно :)

                                                        Собственно, и открытый, и закрытый RSA ключи не являются подписями.
                                                –1
                                                Ну вы бы лучше больше читали, чем писали, например про применение этих алгоритмов в частности и асимметричной криптографии в целом.

                                                  0
                                                  Уважаемый ni4, это вы сейчас весьма нелепо попытались нахамить профессиональному криптографу.
                                                    0
                                                    Я ушел в ступор и дико сру кирпичами.
                                                      +1
                                                      Можно сраться кирпичами, можно пытаться хамить для показушной крутости, можно минусовать до полного посинения — ничего из этого не заменит и не прибавит ни реальных знаний, ни опыта.
                                                        –1
                                                        Уважаемый, ну достаточно уже, мне тяжело это все выдерживать :)
                                                        Как минимум нужно быть скромнее, может вы конечно и самый сильный криптограф у себя на районе, но не стоит экстраполировать это на весь мир.
                                                        Професионалом Вас назовут другие люди, может быть. Но не Вы сами.
                                                          +1
                                                          Я понимаю, что сложно, и что думать — это не кирпичами срать. Но вы всё же попробуйте сделать усилие. «Криптограф» — это название той профессии, которая много лет указана в моих трудовых контрактах. Ещё раз, медлено: название профессии. И ещё раз для тех, кто совсем в каске: не степень крутости, а специальность.

                                                          А теперь повторю: сваливать в кучу алгоритмы шифрования и алгоритмами цифровых подписей — нелепо. Удивлятся отсутствию в ГОСТах алогритмов вероятного противника тоже нелепо. Делающий это человек демонстрирует, в первую очередь, слабое понимание предмета. Если при этом он берётся поучать других, то ещё и недалёкость с ущербным ЧСЗ.
                                                            –1
                                                            Давайте оставим этот разговор. Очевидно, за воротами своего глубочайшего професионализма вы не в состоянии проанализировать что же хотел сказать я своими комментариями.
                                        0
                                        один знакомый доцент рассказывал что к ним на мехмат в лихие 90-тые приходили банкиры и просили продать им немного простых чисел. Интересно где вообще достают большие простые числа? Если в каком-то «справочнике» — то хакеру достаточно устроить простой перебор по числам из этого справочника.
                                          0
                                          Простые числа можно получить различным образом, потом прогнать их по тестам. Хотя самому интересно как получают числа в криптографических системах.

                                          Перебор чисел невозможен, из-за их огромного количества. Например между 10^200 и 10^250 примерно 10^247 простых чисел.
                                            0
                                            я к тому что все алгоритмы получения больших простых чисел и «кандидатов на простые числа» (типа 2^p-1) опубликованы. Какие-то алгоритмы дают результат быстрее с какими-то исходными данными. Что мешает накапливать базу простых чисел, начиная с тех которые можно получить «быстрее». Те кто будет шифровать, с большой вероятностью используют именно сравнительно «быстрое» простое число.
                                          +2
                                          для разложения числа в 200 знаков. В данный момент, эта цель ещё не достигнута, и наибольшим факторизованным числом является 192-значное число.

                                          Передайте уважаемому профессору Салий Вячеславу Николаевичу, что на дворе 2009 год и что 200-значное число разложили уже как 4 года тому назад. Покажите ему вот эту ссылку: en.wikipedia.org/wiki/RSA_numbers
                                            0
                                            Спасибо за информацию! А я не перепроверя про 200-значное число написал… да, передам обязательно :)
                                            Сейчас текст поправлю.

                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                          Самое читаемое