МИСЗКИ книга (1085503), страница 22
Текст из файла (страница 22)
Поэтому на практике ггремятся к тому, чтобы по своим вероятностным свойствам ~ «мма была близка к слу ейной равновероятной г«жледовательностн. 131 При использовании неравновероятиой гаммы появляется возможность восстановить ее вероятностные характеристики непосредственно по шнфротексту и применить эту информацию при криптоанализе шифра гаммирования. Рассмотрим криптоанализ шифра гаммировання на примере шифра Виженера. Как уже упоминалось, это шифр модульного гаммировання с уравнением Ь>=(а;+у) шо>1л, для которого гамма является периодической последовательностью знаков алфавита.
Такая гамма обычно получается периодическим повторением некоторого ключевого слова. Например, ключевое слово КЕУ дает гамму КВАСКЕ т"КЕУ.... Пусть,и — длина ключевого слова. Обычно криптоанализ шифра Внжснсра про~слито~ в два этапа. На первом этапе определяется число ф„на втором этапе — само ключевое слово. Для определения числа р применяется так называемый тест Казиски, названный в честь Ф. Казискн, прнменившего его в 1863 г.
Тест основан на простом наблюдении того, что два одинаковых отрезка открьпого текста, отстоящих друг от друга на расстоянии, кратном р, будут одинаково зашифрованы. В силу этого в шифротексте ищутся повторения символов длиной не меньшей трех знаков, и расстояния между ними. Длина в трн символа выбрана потому, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью. Пусть»>,»ь... — найденные расстояния между повторениями и >1 — наиболыпий общий делитель этих чисел. Тогда р должно делиться на А Чем болыпе повторений имеет текст, тем более вероятно, что ф совпадает с >1. Предположим, что на первом этапе мы нашли длину ключевого слова 1>. Рассмотрим теперь вопрос о нахождении самою ключевого слова. Можно конечно искать его прямым перебором, а можно для его нахождения использовать так называемый взаимный индекс совпадения. Подробно этот алгоритм изложен в [8).
Мы же ограничимся следующим: для каждого из языков можно составить таблицы взаимного индекса совпадения при сдвиге. Сравнение результатов взаимного индекса совпадения шифротекста с таблицей язы- 132 ха позволяет составить систему уравнений, которая позволяет <>олучить столько вариантов ключевых слов, сколько букв в алфавите. Иными словами, если прямой не~сбор комбинаций слова вз 3 букв английского алфавита это 26 =17 576 комбинаций, то взаимный индекс совпадения выдает нам 26 вариантов слов. Следует отметить, что этот метод будет эффективен для не очень больших значений и.
Это связанно с тем, что для хороших приближений индексов совпадений требуются тексты достаточно большой длины. 4. Одноразовые блюкноть>. Это последний алгоритм из шифров замены, который мы рассмотрим. В классическом виде одноразовый блокнот представляет собой очень длинную последовательность случайных букв, записанную на листах бумаги, которые скреплены между собой в блокнот. Отправитель использует каждую букву из блокнота, » обы зашифровать ровно одну букву открытого текста сообщения. Шифрование состоит в сложении буквы открытого текста и ьуквы из одноразового блокнота по модулю 1«1, где Х вЂ” количегво букв в алфавите.
После шифрования отправитель уничтоваст использованный одноразовый блокнот. Чтобы отправить шяюе сообщение, ему придется изготовить или найти новый од>юразовый блокнот. Получатель, владеющий копией одноразового блокнота, «пгорым воспользовался отправитель сообщения, получает от> рмтый текст путем сложения букв шифротексга и букв, нзвле«гнных из имеющейся у него копии одноразового блокнота. Эту «опию он затем уничтожает.
Если предположить, что у крнптоаналитика нет доступа к «норазовому блокноту, то данный алгоритм шифрования абсожотно ~аде~с~. Перехва~е~~о~у ~~фро~ан~о~у сообщению с ьт>инаковой вероятностью соответствует произвольный откры> мй текст той же длины, что и сообщение. Однако у алгоритма шифрования с помощью одноразового >«я>киота есть ~ее~ма существенный недосшток.
Последо~а~ел~- воегь букв, которая содержится в одноразовом блокноте, должна 133 быть по-настоящему случайной, а не просто псевдослучайной, поскольку любая криптоаналкгическая атака на него будет, в первую очередь, направлена против метода генерации содержимого этого блокнота. Другая важная особенность применения одноразового блокнота состоит в том, чтобы никогда не пользоваться им дважды, поскольку криптоаналнтик может отыскать участки сообщений, для шифрования которых был применен один и тот же одноразовый блокнот.
Делается это следующим образом. Нужно последовательно сдвигать одно сообщение относительно другого и подсчитывать количество совпадений. Как только зто количество резко увеличится, значит, случайная последовательность, использованная для шифрования двух различных отрезков сообщений, была одной и той же.
Дальнейший криптоанализ осуществляется достаточно просто. Одноразовые блокноты могут состоять не из байтов, а из битов. Тогда шифрование будет заключаться в выполнении сложения по модулю 2. Для получения открытого текста достаточно опять сложить по модулю 2 шнфротекст и содержимое однора зового блокнота. Надежность будет по-прежнему такой же, ка» при посимвольном модульном сложении. Еще один недостаток блокнотного способа шифрованит заключается в том, что случайная последовательность должн» быть той же длины, что и само сообщение.
Чтобы послать ко роткую шифровку, одноразовый блокнот еще сгодится, но ка~ быть с каналом связи, пропускная способность которого измеря ется десятками мегабит в секунду? Конечно, при необходимости можно для хранения случай ных последовательностей воспользоваться компакт-дисками < многократной перезаписью или цифровой магнитной лентой Однако это будет достаточно дорогостоящее решение проблемь1 Кроме того, необходимо будет обеспечить синхронную работ1 приемной и передающей аппаратуры, а также отсутствие иска жений при передаче. Ведь даже если несколько бит сообщенит пропущены при его передаче, получатель так и не сможет про честь открытый текст. Несмотря на все перечисленные выше недостатки, однорт зовые блокноты успешно используются для шифрования евер» 134 секретных сообщений.
Не имея в своем распоряжении соответствующего блокнота, эти сообщения невозможно прочитать вне ивисимости от того, насколько быстро работают суперкомпьюшры, которые используются в ходе криптоаналитической атаки. Еще одним преимуществом использования блокнотов является возможность создания «ложного» блокнота. На основе аифротекста и некоторого несекретного текста, например литературного произведения, создается ложный блокнот. В случае воздействия со стороны спецслужб или других лиц, можно предоставить им «ложный» блокнот и рассказпь историю о том, «ак вы практиковались в шифровании различных текстов. Можно использовать не литературное произведение, а похожую на правду дезинформацию. Шифры перестановки В исто сторическом обзоре упоминались некоторые типы гяифров перестановки — Сцнтала, атбаш.
Ключом шифра являгэся перестановка номеров букв открытого текста. Зависимость ь»юча от длины текста создает значительные неудобства в исглифров перестановок, которые можно применять для шифрова«н» текстов любой длины. 1. Мартпрутные перестановки. Широкое применение получили так называемые маршруглмс перестановки, основанные на некоторой геометрической фигуре. Отрезок открьпого текста записывается в такую фнтуру л некоторой траектории.
Шифрованным текстом является по»гловательиость, полученная прн выписывании текста по 1~0! ае . ™ачр " тр кторин. 1~" —.~имер, можно записывать сообщение в прятекста по друг«угольную таблицу, выбрав такой маршрут: будем двигаться вл горизоншлн, начнтлш с левого верхнего угла, поочередно ~ »сва направо и справа налево. Списывать же сообщение будем г«другому маршруту: по вертиьзлям, начиная с верхнего правот» гела и двигаясь поочередно сверху вниз и снизу вверх.
135 136 137 Пример: Зашифруем указанным выше способом фразу пример мари~рутной перестаиовки, используя прямоугольную таблицу размером 4х7: Обозначения: — Зались открытого текста -----+ Чтение шифротекста цфрованная фраза выглядит следующ™ о~разом' мастаеррешрноермиупвкйтрпнои Обращение описанных шагов при расшнфровании нг представляет тязш. Более сложные маршруппяе перестановки могуг исполь зовать другие геометрические фигуры и более «хитрые» мар шруты, как, например, при обходе шахматной доски «ходом ко ня», пути в некотором лабиринте и т.
п. Возможные варианть~ зависят от фантазии составителя системы и, конечно, естествен ного требования простоты ее использования. 2. Вертикальные перестановки. Разновидность шифров маршрутной перестановки, полу чившая широкое распространение. В шифрах вертикальной пс рестановки также используется прямоугольная таблица, в котс рую сообщение записывается обычным образом (по строка» слева направо). Выписывается жс сообщение по вертнкаля (сверху вниз), при этом столбцы выбираются в порядке, опредг ляемом числовым ключом. Пример: Залшфруем Фразу вот пример шифра вертииальпой перестановки, используя прямоугольник размером 6 х 7 и числовой ключ (5,1,4,7,2,6,3).
5 1 4 7 2 6 3 Теперь„выписывая буквы по столбцам в порядке, указанном числовым ключом, получим такую криптограмму: орсье крфийамааеотшрнси невлрвиркпнпнтот Особенно хотелось бы подчеркнуп, что нецелесообразно таполюпь последнюю строку прямоугольника «нерабочими» буквамн, так как это дало бы противнику, получившему в свое распоряжение данную криптограмму, сведения о длине числово~е ключа и позволило бы ему определить примерный порядок считывания столбцов. Для сравнения приведем резулътат «неправильной» крип|ограммы, заполнив пустые клетки точками. ореьекрфийа мааео тшрнсивевлрвиркпн.питот По даннои криптограмме можно установить высоту и колшество столбцов, а также определить какие столбцы должны изходятся в левой части таблицы, а какие — в правой.