АЛГОРИТМ RSA


RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) – криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений.

Историческая справка. В 1977 г. трое ученых Рональд Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского Технологического Института (MIT) опубликовали в журнале Scientific American новый алгоритм шифрования, основанный на идее двухключевого шифрования, названный по первым буквам фамилий авторов методом RSA.

В этом методе известным параметром служит некоторое целое число n большой длины (обычно 1024 или 2048 бита), являющееся произведением двух простых чисел p и q. Эти числа p и q являлись секретными параметрами метода, и для взлома системы RSA было достаточно найти множители, т.е выполнить разложение числа n на простые сомножители.

На момент опубликования алгоритма RSA было известны лишь небольшое количество алгоритмов факторизации, самым известным из которых являлся метод Ферма. Эти методы позволяли на тот день факторизовать числа, состоящие не более чем из 25 – 30 цифр. Поэтому использование в качестве n натурального числа, имеющего более 100 десятичных знаков, гарантированно обеспечивало безопасность шифрования этим методом.

Сами создатели метода предложили всей математической общественности для тестового взлома 129-значное десятичное число, пообещав за его разложение условное вознаграждение в $100. Масла в огонь подлила также опубликованная в 1977 г. в журнале Sci. Amer. статья известного математика и популяризатора Мартина Гарднера "A new kind of cipher that would take millions of years to break" (Новый алгоритм шифрования, для взлома которого потребуется миллионы лет).


Стеганография. Стратегия сокрытия изображений в изображении обычных объектов называется стеганографией. Преимущество этого способа передачи информации заключается в том, что и отправитель, и получатель защищены от раскрытия самого факта передачи. История имеет множество примеров применения подобной техники, от написания сообщений невидимыми чернилами, до шаблонов с микроотверстиями, позволяющими закрывать определенные части обычного текста.

Современный цифровой мир открыл перед стеганографией новые горизонты: теперь сообщение может быть встроено в образ за счет замены некоторых единиц и нулей в двоичном коде, задающих цвета пикселей. Человеческий глаз не способен распознать подобные незначительные изменения, но специальные программы анализа способны зафиксировать отклонение в обычном статистическом распределении оттенков.

Криптография. Не скрывает факта передачи сообщения. С элементарной криптографией мы знакомимся уже тогда, когда сообщение шифруется сдвигом букв алфавита, вместо A пишется Б и т.п. Уже в этом правиле фигурирует ключ K – величина сдвига. В общем, это может быть не только сдвиг, но и иная математическая операция.

Открытый и закрытый ключи. Существует двухтактная схема передачи информации, когда знание единого ключа обоими сторонами несущественно. Первый абонент защищает сообщение и отсылает его второму, скажем, сдвигом вправо на 2. Второй абонент защищает полученное сообщение (сдвигом влево на 3), и отсылает его обратно. Схема работоспособна, если вторая защита не мешает снять первую на передающей стороне (сдвигом влево на 2). Сообщение посылается снова второму абоненту, защищенное теперь уже только его ключом, поэтому (зная свой ключ) он расшифровывает его инверсным сдвигом (вправо на 3).

Таким образом можно посылать сообщение при незнании сторонами ключей друг друга или формировать некоторый удобный для менее интенсивного обмена информацией (двухтактная схема затратна по времени) ключ. Еще пример, когда в схеме передачи сообщений задействован открытый ключ 2. Первая сторона возводит 2 в квадрат и передает второй 4. Вторая сторона возведет 2 в куб и передает первой 8. Теперь каждая сторона повторит свою операцию с присланной информацией и каждый получит, в итоге, общий закрытый ключ: K=82=43=64, которым шифруется сообщение.

Заметим, что для вычисления закрытого ключа К по информации в канале при знании открытого ключа в виде основания 2 некоторой третьей стороне надо уметь вычислять показатель степени (логарифм), что несложно. Однако при вычислениях по модулю такая обратная операция, напротив, намного сложнее прямой, так как она связана с перебором и проверкой крайне большого числа вариантов. Различие в трудоемкости используется в схемах с открытым ключом. Ключ открыт лишь в том смысле, что им можно воспользоваться теоретически, но практически для этого потребуется такое время, что это сделает бессмысленным дешифрацию устаревшего сообщения.

Криптосистема RSA. RSA (Rivest, Shamir, Adleman) опирается на то, что произведение двух даже очень больших простых чисел n=pq вычислить нетрудно, тогда как обратная операция (разложения на множители) существенно сложна, поэтому n можно передавать открыто по каналу. Абоненты пользуются прямой операцией, а противная сторона имеет дело с обратной. Детали, как именно реализуется шифрование, что именно фигурирует в качестве ключей, не важны для понимания принципа сложности этой криптосистемы.

Тест авторов криптосистемы был расшифрован через 15 лет. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (две из которых были факс-машинами). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу "THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE" (Волшебные слова – это брезгливый ягнятник). В 2010 году группе ученых из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля. С 31 декабря 2013 года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит.

ВИКИ | ИШМУХМЕТОВ Ш.Т.


Rambler's Top100