Пример2

Этап	Описание операции	Результат операции
Генерация ключей	Выбрать два простых числа
Вычислить модуль
Вычислить функцию Эйлера
Выбрать открытую экспоненту
Вычислить секретную экспоненту
Опубликовать открытый ключ
Сохранить секретный ключ
Шифрование	Выбрать текст для зашифровки
Вычислить шифротекст
Расшифрование	Вычислить исходное сообщение

Алгоритм RSA намного медленнее чем DES и другие алгоритмы блочного шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1000 до 10 000 - в аппаратной реализации.

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера в 1024 бита.

Удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Причём от шифрования ключом длиной в 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-битного целого числа составляет

для некоторого ,

не позволяет разложить большое целое за приемлемое время.

Дата добавления: 2014-01-20