Автор работы: Пользователь скрыл имя, 07 Декабря 2013 в 21:19, доклад
Описание RSA было опубликовано в августе 1977 года в журнале Scientific American. Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда — например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках.
Введение
1 История
2 Описание алгоритма
2.1 Введение
2.2 Алгоритм создания открытого и секретного ключей
2.3 Шифрование и расшифрование
2.3.1 Схема RSA
2.3.2 Корректность схемы RSA
2.4 Пример
2.5 Цифровая подпись
2.6 Скорость работы алгоритма RSA
3 Криптоанализ RSA
4 Применение RSA
Примечания
Литература
Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма).
По эвристическим оценкам длина секретной экспоненты d, нетривиальным образом зависящей от открытой экспоненты e и модуля n, с большой вероятностью близка к длине n. Поэтому расшифрование данных идёт медленнее чем шифрование, а проверка подписи быстрее чем подписание.
Алгоритм RSA намного медленнее чем DES и другие алгоритмы блочного шифрования.
На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера в 1024 бита.
Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.
Как следует из описания работы, вычисление значений ключа осуществлялось общим методом решета числового поля.
На первый шаг (выбор пары полиномов степени 6 и 1) было потрачено около полугода вычислений на 80 процессорах, что составило около 3 % времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течение почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.
Решение ОСЛУ проводилось с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (то есть в среднем 144 ненулевых элементов на строку). Для хранения матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.
В итоге группе удалось вычислить 232-цифровой ключ, открывающий доступ к зашифрованным данным.
Исследователи уверены, что с использованием их метода факторизации взломать 1024-битный RSA-ключ будет возможно в течение следующего десятилетия.
Зная разложение модуля на произведение двух простых чисел, противник может легко найти секретную экспоненту и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа составляет
для некоторого ,
не позволяет разложить большое целое за приемлемое время.
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи.
Также
она используется в открытой системе
шифрования PGP и иных системах шифрования
(к примеру, DarkCryptTC и формат xdc) в
сочетании с симметричными
Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).
Список использованной литературы: