Криптосистема RSA.

В июне 2003 года в Сан-Диего, Калифорния, состоялось очередное вручение Тьюринговской премии, учрежденной Ассоциацией вычислительной техники (Association for Computing Machinery). Эта премия названа именем Алана Тьюринга (1912-1954), английского математика, заложившего основы компьютерных наук и внесшего решающий вклад в раскрытие германского шифра «Энигма» в годы Второй мировой войны. Она присуждается с 1966 года специалистам в области компьютерных наук, создавшим теоретические и технические предпосылки для новых, этапных, достижений в области информационных технологий. Лауреатами 2002 года стали Рональд Ривест, Ади Шамир и Леонард Адлмен. В 1977-78 годах, работая в Массачусетском технологическом институте, они создали шифр, названный RSA (по первым буквам фамилий), который произвел переворот в криптографии и открыл новый период в сфере защиты информации.

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

Существующие алгоритмы позволяют персональному компьютеру за несколько секунд проверить, является ли простым предъявленное число, имеющее порядка 180 цифр (уровень современной практической криптографии). В то же время задача разложения на множители столь же больших составных чисел лежит далеко за пределами современных технологических возможностей.

Теперь о шифре. Пусть имеется компьютерная сеть, абоненты которой хотят обмениваться информацией, не предназначенной для непредусмотренных пользователей. Абонент A выбирает два больших (примерно по 100 цифр) простых числа %%p%% и %%q%%, находит их произведение %%n=pq%% и подбирает целое число %%e%% в интервале от 2 до %%(p-1)(q-1)%%, взаимно простое с %%p-1%% и с %%q-1%%. Затем он опубликовывает пару %%(n,e)%%, это его открытый ключ, он применяется для шифрования сообщений.

Предположим, что другой абонент B желает отправить для A секретное сообщение. Он переводит открытый текст в числовую форму %%m%% (например, заменяя a на 01, b – на 02, ... , z – на 26, а пробел между словами – на 00). Если полученное число %%m%% превышает %%n%%, его можно разбить на последовательные части, каждая меньше %%n%%, так что для простоты пусть %%m < n%%. Далее B вычисляет: $$c=(m^e)mod\,n$$

Это криптограмма, которую он и посылает абоненту A. Для того чтобы ее прочитать, A уже заготовил свой закрытый ключ – число %%d%%, удовлетворяющее двум требованиям: %%1< d < n%% и %%ed≡1 (mod (p-1)(q-1))%%.

Из теории известно, что такое число существует и притом только одно. Теперь A вычисляет %%(c^d)mod\, n%% и получает %%m%%.

Возьмем для примера %%p=3%%, %%q=11%%. Тогда $$n=pq=3·11=33$$ $$(p-1)(q- 1)=2·10=20$$

Выберем %%e=7%%. Открытым ключом является пара чисел %%(33,7)%%. Теперь нужно «изготовить» закрытый ключ (ключ расшифрования), т.е. найти число %%d%% такое, что %%ed≡1 (mod\, 20)%%. Очевидно, что %%d=3%%, так как %%7·3=21\,mod\, 20 =1%%.

Предположим, что %%m=2%%. Тогда

%%c=(m^e)mod\, n= 2^7mod33=128\,mod\,33=29.%%

Итак, криптограммой сообщения %%m=2%% является %%c=29%%.

Дешифрование:

$$(c^d)mod\, n=(29^3)mod \,33=(-4)^3mod\, 33 =\\ (-64)mod\, 33=(-31)mod \,33=2=m$$

Стойкость шифра RSA обосновывается следующими соображениями. Для того чтобы прочитать криптограмму %%c%%, нужно знать закрытый ключ %%d%%. Поскольку числа %%e%% и %%n=pq%% известны, для нахождения %%d%% достаточно найти произведение %%(p-1)(q-1)%%, так как %%ed≡1 (mod (p-1)(q-1))%%, Таким образом, все сводится к определению множителей %%p%% и %%q%% числа %%n%%. Как уже было отмечено выше, задача разложения на множители для больших составных чисел в настоящее время вычислительно не разрешима.

Все шифры, которые рассматривались до настоящего раздела, обладают тем свойством, что для шифрования и дешифрования в них применяется один и тот же секретный ключ. Поэтому такие шифры называют симметричными. Шифр RSA этим свойством не обладает, процедуры шифрование и дешифрование в нем осуществляются на разных ключах. Подобные шифры называются асимметричными.

Для коротких сообщений шифр RSA почти идеален, но при передаче информации большого объема он сильно уступает по скорости симметричным алгоритмам шифрования. Так, самые быстрые микросхемы для RSA имеют пропускную способность около 65 Кбит/с, в то время, как скорость реализации, например AES, достигает 70 Мбит/с. Поэтому в коммуникационных сетях с большой нагрузкой рекомендуется применять RSA вместе с AES (по протоколу «цифровой конверт»): абонент A, желая установить защищенную связь с абонентом B, посылает ему по открытому каналу секретный AES-ключ %%K%%, зашифрованный по методу RSA; абонент B расшифровывает полученную криптограмму, используя свой закрытый RSA- ключ, и теперь может приступить к скоростному обмену информацией с A, применяя шифрование по методу AES на ключе %%K%%.