Глава 13. Шифрование и Интернет Обобщение шифра простой замены

В шифре простой замены буквы заменяются согласно некоторой перестановке алфавита. Мы ранее уже убедились в том, что при наличии всего 200 знаков шифрованного текста этот шифр легко вскрывается подсчетом частот знаков с использованием знаний о языке. Для шифрования таким способом требуется таблица длины 26 с переставленными буквами алфавита. И если, например, A заменяется на R, N на C, а T на H, то AN переходит в шифрованном тексте в RC, а AT ‑ в RH. При этом знак R, образ буквы A, встречается в обоих случаях.

Поскольку в шифре простой замены отдельные буквы каждый раз заменяются на одни и те же, независимо от того, какая буква им предшествует и какая следует за ними, то метод подсчета частот в конце концов обязательно сработает. Противостоять этому могла бы система, в которой шифрование знака зависело бы от значения некоторых букв с какой-нибудь стороны от него: например, AN могло бы при шифровании перейти в RC, а AT - в KW. В таком случае метод подсчета частот монографов не годится. В основе подобной системы может лежать таблица замены, в которой перечислены все 676 (=2626) диграфов и их шифрованные эквиваленты. Фактически, мы получаем двухчастевую кодовую книгу: в первой части слева в алфавитном порядке перечислены все 676 диграфов открытого текста, а справа напротив них - их шифрованные эквиваленты. Во второй части слева в алфавитном порядке перечислены все 676 диграфов шифрованного текста, а их открытые эквиваленты - справа от них. Эта система, которую можно назвать шифром замены диграфов, является более стойкой, нежели простая замена, но пользоваться ею довольно утомительно. К тому же шифровальщику, если только он не обладает феноменальной памятью, необходимо постоянно иметь обе таблицы.

Если криптограф готов пойти на то, чтобы держать под рукой две таблицы, в которых перечисляются 17576 (=262626) триграфов открытого и шифрованного текстов, то можно было бы использовать еще более стойкую систему - шифр замены триграфов.

Очевидно, таким образом можно строить все более и более стойкие системы, но на практике таблицы будут громоздкими, и даже система, основанная на замене строк из 4-х букв (т.е. тетраграфов), вряд ли практически осуществима.

Допустим, однако, что можно построить систему, работающую со строками фиксированной длины, которые каким-то образом автоматически преобразуются в другие строки; причем гарантируется, что изменение любой буквы исходной строки даст нам в результате совершенно иную строку. Такая система уже не требует распечаток таблиц и может и в самом деле оказаться весьма стойкой - это зависит от метода преобразования строк и от числа букв в строке. Нижняя граница шкалы стойкости таких систем задана методом Юлия Цезаря: преобразование осуществляется с помощью сдвига каждой буквы на три позиции вперед в алфавите, а фиксированная длина строки равна единице. Верхнюю строчку шкалы занимает метод RSA, названный по первым буквам фамилий его авторов - Райвеста, Шамира и Эйдельмана (Rivest, Shamir, Adelman) - предложивших данный метод в 1978 году (см. [13.1]). Данный метод может быть использован для шифрования очень длинных строк (например, в 100 знаков) и обеспечивает весьма высокую степень стойкости. Это само по себе уже может показаться удивительным, но еще более удивителен тот факт, что RSA является системой с открытым ключом, что означает (как уже было разъяснено в главе 12), что детали способа зашифрования сообщений являются общедоступными, но только "хозяину" открытого ключа известно, как расшифровать адресованные ему сообщения. Однако, хозяин ключа может отвечать своим корреспондентам, шифруя свои сообщения таким образом, чтобы они могли расшифровать их.

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