Применение алгоритма RSA для шифрования потоков данных — страница 5

Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при помощи ЭВМ, а способы, которыми выполняются эти операции, как неко­торые функции, определённые на множестве целых чисел. Всё это делает естественным появление в криптографии методов теории чисел. Кроме того, стойкость ряда современных криптосистем обосновывается только сложностью некоторых теоретико-числовых задач. Но

возможности ЭВМ имеют определённые границы. Приходится раз­бивать длинную цифровую последовательность на блоки ограниченной длины и шифровать каждый такой блок отдельно. Мы будем считать в дальнейшем, что все шифруемые целые числа неотрицательны и по вели­чине меньше некоторого заданного (скажем, техническими ограничени­ями) числа m. Таким же условиям будут удовлетворять и числа, получае­мые в процессе шифрования. Это

позволяет считать и те, и другие числа элементами кольца вычетов а число представляет собой сообщение в зашифрованном виде. Простейший шифр такого рода - шифр замены, соответству­ет отображению при некотором фиксированном целом k. Подобный шифр использовал еще Юлий Цезарь. Конечно, не каждое отображение подходит для целей надежного сокрытия инфор­мации. В 1978 г. американцы Р. Ривест, А. Шамир и Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman)

предложили пример функции RSA. Эта функция такова, что 1) существует достаточно быстрый алгоритм вычисления значений 2) существует достаточно быстрый алгоритм вычисления значений об­ратной функции 3) функция обладает некоторым «секретом», знание которого позво­ляет быстро вычислять значения становится трудно разрешимой в вычислительном отношении задачей, требующей для своего решения столь много времени, что по его прошествии

зашифрованная информация перестает представлять инте­рес для лиц, использующих отображение в качестве шифра. Еще до выхода из печати статьи копия доклада в Массачусетском Технологическом институте, посвящённого системе RSA. была послана известному популяризатору математики М. Гарднеру, который в 1977 г. в журнале Scientific American опубликовал статью посвящённую этой системе шифрования. В русском переводе заглавие статьи Гарднера

зву­чит так: Новый вид шифра, на расшифровку которого потребуются мил­лионы лет. Именно эта статья сыграла важнейшую роль в распростране­нии информации об RSA, привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области, произошедшему в последовавшие 20 лет. 2.1. система шифрования RSA Пусть и натуральные числа. Функция реализующая схему RSA, устроена следующим образом