Пример, иллюстрирующий применение алгоритма RSA

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

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

2. Определим n =3*11=33. Найдем (p -1)(q -1)=20.

3. Выберем в качестве 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.

6. Расшифруем полученное зашифрованное сообщение (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.

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

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

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

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

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

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

Числа p и q должны быть одинаковой длины. Если n занимает 1024 бита, то длина p и q должна быть равна 512 битам. Различие между p и q должно быть большим.

p-1 должно иметь большой простой делитель (r);

p+1 должно иметь большой простой делитель;

r-1 должно иметь большой простой делитель.