RSA-шифрование. Описание и реализация алгоритма RSA

RSA-шифрование представляет собой одну из первых практических криптосистем с открытым ключом, которая широко используется для безопасной передачи данных. Ее основное отличие от подобных сервисов в том, что ключ шифрования является открытым и отличается от ключа дешифрования, который держится в секрете. В технологии RSA эта асимметрия основана на практической сложности факторингового воспроизведения двух больших простых чисел (проблема факторинга).

Видео: Алгоритм шифрования RSA

История создания

Название RSA состоит из начальных букв фамилий Ривест, Шамир и Адлеман, - ученых, которые впервые публично описали подобные алгоритмы шифрования в 1977 году. Клиффорд Кокс, английский математик, работавший на спецслужбы Великобритании, впервые разработал эквивалентную систему в 1973 году, но она не была рассекречена до 1997 г.

Пользователь RSA создает и затем публикует открытый ключ, основанный на двух больших простых числах вместе со вспомогательным значением. Простые числа должны храниться в тайне. Любой человек может использовать открытый ключ для шифрования сообщения, но если он достаточно большой, то только кто-либо со знанием простых чисел может декодировать сообщение. Раскрытие RSA шифрования известно как основная проблема: сегодня остается открытой дискуссия о том, насколько это надежный механизм.

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

Когда появилась криптосистема в современном виде?

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

Ривест, Ади Шамир и Адлеман в Массачусетском технологическом институте предприняли несколько попыток в течение года, чтобы создать однонаправленную функцию, которую трудно раскодировать. Ривест и Шамир (как компьютерные ученые) предложили множество потенциальных функций, в то время как Адлеманом (как математиком) осуществлялся поиск «слабых мест» алгоритма. Они использовали много подходов и в конечном итоге в апреле 1977 года разработали окончательно систему, сегодня известную как RSA.

ЭЦП и открытый ключ

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

Данная криптосистема (RSA-шифрование) предлагает открытый ключ, чем отличается от симметричных. Принцип ее функционирования в том, что применяют два разных ключа – закрытый (зашифрованный), а также открытый. Первый применяют для того, чтобы сгенерировать ЭЦП и впоследствии получить возможность расшифровки текста. Второй – для собственно шифрования и проверки ЭЦП.

Использование подписи позволяет лучше понять шифрование RSA, пример которого можно привести как обычный засекреченный «закрытый от посторонних глаз» документ.

Видео: Алгоритм шифрования RSA: шаг второй

В чем суть алгоритма?

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

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

Открытый ключ состоит из модуля и публичной экспоненты. Закрытый состоит из модуля и приватного показателя, который должен храниться в тайне.

Шифрование файлов RSA и слабые места

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

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

Видео: How the RSA algorithm works, including how to select d, e, n, p, q, and (phi)

Дополнительные алгоритмы шифрования и защиты

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

Безопасность криптосистемы RSA и шифрование информации основаны на двух математических задачах: проблемы разложения на множители больших чисел и собственно проблемы RSA. Полное раскрытие шифротекста и ЭЦП в RSA считается недопустимым на том предположении, что обе эти проблемы невозможно разрешить в совокупности.

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

Автоматизация

Инструмент, называемый Yafu, может быть использован для оптимизации этого процесса. Автоматизация в YAFU представляет собой современную функцию, сочетающую алгоритмы факторизации в интеллектуальной и адаптивной методологии, которая сводит к минимуму время, чтобы найти факторы произвольных входных чисел. Большинство реализаций алгоритма многопоточные, что позволяет Yafu в полной мере использовать мульти- или много многоядерные процессоры (в том числе SNFS, SIQS и ECM). Прежде всего, это управляемый инструмент командной строки. Время, затраченное на поиск фактора шифрования с использованием Yafu на обычном компьютере, может быть уменьшено до 103.1746 секунд. Инструмент производит обработку бинарных файлов емкостью 320 бит или больше. Это очень сложное программное обеспечение, которое требует определенного количества технических навыков для установки и настройки. Таким образом, RSA-шифрование C может оказаться уязвимым.

Попытки взлома в новейшее время

В 2009 году Бенджамин Муди с помощью битового ключа RSA-512 работал над расшифровкой криптотекста в течение 73 дней, используя только общеизвестное программное обеспечение (GGNFS) и среднестатистический настольный компьютер (двухъядерный Athlon64 при 1900 МГц). Как показал данный опыт, потребовалось чуть менее 5 гигабайт диска и около 2,5 гигабайт оперативной памяти для процесса «просеивания».

По состоянию на 2010 год, самый большой факторизованный номер RSA был 768 бит длиной (232 десятичные цифры, или RSA-768). Его раскрытие длилось два года на нескольких сотнях компьютеров одновременно.

На практике же ключи RSA имеют большую длину - как правило, от 1024 до 4096 бит. Некоторые эксперты считают, что 1024-битные ключи могут стать ненадежными в ближайшем будущем или даже уже могут быть взломаны достаточно хорошо финансируемым атакующим. Однако, мало кто станет утверждать, что 4096-битные ключи могут быть также раскрыты в обозримом будущем.

Перспективы

Поэтому, как правило, предполагается, что RSA является безопасным, если числа достаточно велики. Если же основное число 300 бит или короче, шифротекст и ЭЦП может быть разложен в течение нескольких часов на персональном компьютере с использованием программного обеспечения, имеющегося уже в свободном доступе. Ключи длиной 512 бит, как было доказано, могли быть вскрыты уже в 1999 году с использованием нескольких сотен компьютеров. В наши дни это возможно в течение нескольких недель с использованием общедоступного аппаратного обеспечения. Таким образом, вполне возможно, что в будущембудет легко раскрываться RSA-шифрование на пальцах, и система станет безнадежно устаревшей.

Официально в 2003 году была поставлена под сомнение безопасность 1024-битных ключей. В настоящее время рекомендуется иметь длину не менее 2048 бит.