Хорст Файстель. Криптография и компьютерная безопасность. Перевод А.Винокурова. Часть 2.

Теперь мы можем усложнить шифр принципиально иным способом. Вместо того, чтобы пользоваться единственной таблицей подстановок, мы можем использовать несколько таблиц в хаотичном, но определенном заранее порядке. Порядок использования таблиц и образует ключ. Если мы используем только две таблицы, обозначенные 0 и 1, то типовой ключ может быть, например, таким: 1101101. Теперь мы имеем дело с многоалфавитной подстановкой. Относительно этого нового источника сложности в шифре возникает следующий вопрос: возможно ли упростить таблицы подстановок, сделав их меньше? Простейшая двоичная подстановка, которую только можно выполнить, это замена одной двоичной цифры на другую, и в этом случае существует всего две различные таблицы подстановок. Давайте рассмотрим эти две таблицы, каждая из них будет соответствовать одному из двух основных типов ключа, как показано на следующей ниже иллюстрации. Таблица, помеченная "Ключ 1" аменяет нули на единицы и наоборот, а таблица, помеченная "Ключ 0" оставляет цифры неизменными. Существуют только две указанные возможности. Но оказывается, что тот же самый эффект можно получить с помощью операции, известной как сложение по модулю 2: две одинаковые цифры в результате такой операции дают 0, две различные - 1. Поэтому в рассматриваемом случае шаблонный ключ можно назвать также аддитивным ключом.

a) Ключ 0 Откры- тый Шифр 0 0 1 1 Ключ 1 Откры- тый Шифр 0 1 1 0

б) Ключ Сообщение 0 1 0 0 1 1 1 0 в) Сообщ. Ключ Шифр 0  +  0  =  0 0  +  1  =  1 1  +  0  =  1 1  +  1  =  0

г) "F" = 00101 Ключ = 10110 Шифр = 10011   Шифр = 10011 Ключ = 10110 00101  =  "F"

Двоичная подстановка в своей простейшей форме позволяет только две возможности: (а) в одной таблице (Ключ 0) открытые цифры равны цифрам шифра, во второй (Ключ 1) цифры шифра противоположны открытым цифрам. В таком варианте двоичной подстановки две таблицы подстановки могут быть заменены единственной таблицей сложения по модулю 2 (б); в этом случае двоичные подстановки эквивалентны двоичному сложению (в). Ключ шифрования для двоичного сложения по модулю 2 может быть произвольной последовательностью единиц и нулей. Чтобы зашифровать двоичное представление буквы сообщения, прибавляют цифры ключа к каждой цифре сообщения. При расшифровании вычитают цифры (это то же самое, что и сложение по модулю 2).

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

Теперь мы готовы рассмотреть что получается когда мы шифруем последовательность двоичных цифр, скажем, 0001010, преобразуя ее в другую последовательность, используя два ключа, Ключ 1 и Ключ 0, в некотором произвольном порядке: 1101101. Принимая во внимание правило, что Ключ 1 заменяет нули на единицы и наоборот, а Ключ 0 оставляет цифры неизменными, мы получим следующее:

Сообщение:	0001010
Ключ:	+ 1101101
Шифр:	1100111

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

Шифр:	1100111
Ключ:	- 1101101
Сообщение:	0001010

Сразу возникает вопрос: имеет ли рассмотренный простой шифр какое-либо практическое значение? Поскольку этот шифр, в сущности, использует лишь две таблицы подстановки минимального размера, очевидно, что мы должны переключаться между ними часто, и делать это случайным образом, то есть прибавлять к данным случайную последовательность ключевых цифр. Предположим что мы делаем это. Тогда ответ на наш вопрос достаточно неожиданный: мы имеем потенциально нераскрываемый шифр. С точки зрения теории информации этот шифр делает следующее: к каждому биту информации сообщения прибавляется один бит информации (а точнее, дезинформации!) ключа. Этого достаточно, чтобы полностью разрушить любую структуру, которую исходное сообщение могло бы иметь, если только цифры ключа взяты в случайном, скажем, определяемом подбрасыванием монеты порядке, и ключевая последовательность имеет такую же длину, как и сообщение, и никогда не повторяется.

Почему эта система действительно невскрываемая? На самом деле, это даже вообще не "система". Рассмотренное криптографическое преобразование является не более чем случайным прибавлением одной цифры, и в такой же степени тривиально. Стойкость метода следует исключительно из того факта, что для каждой цифры сообщения мы полностью и случайным образом меняем ключ. Это единственный класс шифров, для которого можно доказать невскрываемость в абсолютном смысле этого слова.

Даже если оппонент осуществляет попытку вскрыть систему грубой силой, например, опробованием всех возможных прибавляемых ключей (2⁶ или 64, в случае нашего 6-битового сообщения), он получит все возможные открытые тексты, включая тот, который мы в действительности зашифровали. Так, если мы зашифровали имя "Том" (что потребовало бы, как минимум, пятнадцати двоичных цифр), аналитик нашел бы среди своих вариантов расшифрования все английские трехбуквенные имена, такие, как Джо (Joe), Джим (Jim), Джоб (Job), и так далее, включая Тома (Tom), но никаких намеков на то, какое имя является правильным. Даже сам бог или дьявол, который мог бы опробовать все возможные ключи в одно мгновение, не мог бы внести сюда никакой определенности. Эта система хорошо известна и используется на практике под разными именами, такими, как система Вернама или одноразовый блокнот, всеми крупными правительствами.

В реальных системах сначала подготавливают две идентичные ленты со случайными цифрами ключа, ленты могут быть любого типа - телетайпные, перфорированные, магнитные или какие-нибудь еще. Одна остается у отправителя, а другая передается "неперехватываемым" образом например, курьером с охраной, законному получателю. Когда отправитель хочет передать сообщение, он сначала преобразует его в двоичную форму и помещает в устройство, которое к каждой цифре сообщения прибавляет по модулю два цифры, считанные с ключевой ленты, как показано на следующем ниже рисунке. На принимающей стороне кодированное сообщение записывается и пропускается через машину, похожую на устройство, использованное для шифрования, которое к каждой двоичной цифре сообщения прибавляет (вычитает) по модулю два цифры, считанные с ключевой ленты, получая таким образом открытый текст. При этом, естественно, ключевая лента должна продвигаться абсолютно синхронно со своим дубликатом, используемым для зашифрования.

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

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

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

Один из основных методов построения подобных генераторов заключается в использовании двух или более битовых лент, считанные с которых данные побитно складываются для получения "смешанного" потока. Например, простая одноразовая лента может быть заменена двумя циклическими лентами, длины которых являются простыми или взаимно простыми числами. Так как в этом случае длины лент не имеют общих множителей, полученный из них поток имеет период повторения, равный произведению их длин: две ленты, имеющие длину 1000 и 1001 соответственно, дают в результате составной поток, который не повторяется на первых 10001001, или 1001000 цифрах. Ленты циркулируют через сумматор, который складывает по модулю два считанных с них цифры, как показано на следующем ниже рисунке. Выход сумматора служит ключом, используемым для зашифрования сообщения. Поэтому важно, чтобы составной поток превышал по длине все вместе взятые сообщения, которые могут быть переданы за разумный период времени.

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

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

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

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.