В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях.
Важная проблема практической реализации — генерация больших простых чисел. Решение задачи «в лоб» — генерация случайного большого числа n (нечетного) и проверка его делимости на множители от 3 вплоть до n0.5. В случае неуспеха следует взять n+2 и так далее.
В принципе в качестве p и q можно использовать «почти» простые числа, то есть числа, для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать «почти» простые числа с уровнем доверия 2−100.
Другая проблема — ключи, какой длины следует использовать?
Для практической реализации алгоритмов RSA полезно знать оценки трудоемкости разложения простых чисел различной длины, сделанные Шроппелем.
|
log10 n. | Число операций. | Примечания. |
| 1.4 *1010. | Раскрываем на суперкомпьютерах. |
| 2.3 *1015. | На пределе современных технологий. |
| 1.2 *1023. | За пределами современных технологий. |
| 2.7 *1034. | Требует существенных изменений в технологии. |
| 1.3 *1051. | Не раскрываем. |
В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.
Сами авторы RSA рекомендуют использовать следующие размеры модуля n:
- · 768 бит — для частных лиц;
- · 1024 бит — для коммерческой информации;
- · 2048 бит — для особо секретной информации.
Третий немаловажный аспект реализации RSA — вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О (k2) операций, по закрытому ключу — О (k3) операций, а для генерации новых ключей требуется О (k4) операций.
Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Pentium-90 осуществляет шифрование со скоростью 21.6 Кбит/c для 512-битного ключа и со скоростью 7.4 Кбит/c для 1024 битного. Самая «быстрая» аппаратная реализация обеспечивает скорости в 60 раз больше.
По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время.
