logo
Лекции_Информационная безопасность

3.5Практическая реализация rsa

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

Важная проблема практической реализации - генерация больших простых чисел. Решение задачи «в лоб» состоит в генерации случайного нечетного большого числа n (нечетного) и проверка его делимости на множители от 3 вплоть до n0.5. В случае неуспеха следует взять n+2 и так далее. В теории чисел показано, что вероятность того, что число порядка n будет простым составляет 1/ln n.

В принципе в качестве p и q можно использовать «почти» простые числа, то есть числа для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать «почти» простые числа с уровнем доверия 2100.

Другая проблема - ключи какой длины следует использовать?

Для практической реализации алгоритмов RSA полезно знать оценки трудоемкости разложения простых чисел различной длины. В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.

Авторы RSA рекомендуют использовать следующие размеры n:

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

Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Pentium-90 осуществляет шифрование со скоростью 21.6 Кбит/c для 512-битного ключа и со скоростью 7.4 Кбит/c для 1024 битного. Самая «быстрая» аппаратная реализация обеспечивает скорости в 60 раз больше.

По сравнению с тем же алгоритмом DES, RSA требует в тысячи и сотни тысяч раз большее время.