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

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

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

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

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

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

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

• 768 бит - для частных лиц;

• 1024 бит - для коммерческой информации;

• 2048 бит - для особо секретной информации.

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

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

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

3.6Пример 1 rsa.

Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA. Зашифруем сообщение “САВ”. Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).

1. Выберем p=3 и q=11.

2. Определим n=3*11=33. Длина n тесно связана с размером алфавита. То есть в нашем алфавите может быть не более 33 символов.

3. Найдем (p-1)(q-1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, С3 (номера символов в алфавите). Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

1. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.