Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

181

Ф+1 1(Ьц-1), СГц-2 ( ^ 1+2 )? • * • > СГц-с ^Ьц-с) ~~ а 1+1, 3 1+2»• • • > ^ 1+с.

Если текст а' ьа'2,.• -,а'ь а\+1, а\+2,- • •» а\+с «нечитаемый» (он может быть таким за счет его окончания а\+1, а\+2,..., а \+с.), то продолжение Ын9">А+<1 +с отбрасывается. Если же текст а'ьа'2,...,а'ь а\+1, а\+2,..., а\+с

«читаемый», то ищут его возможные продолжения и т. д. Очевидно, поиск продолжений заканчивается по прочтению первых с! букв открытого текста. Так как в этом случае найден отрезок ключа на с! первых знаков и, следова­ тельно, определен весь ключ. Оставшаяся часть не найденного открытого тек­ ста читается расшифрованием на найденном ключе.

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

Метод чтения по колонкам. Пусть Ъ1,Ъ2,...,Ъы - известный шифр-

текст, й - период ключевой последовательности. Рассмотрим две его подпос­ ледовательности.

Для изложения «метода чтения по колонкам» введем предварительно необходимые обозначения. Будем предполагать, что открытыми текстами, подлежащими шифрованию, являются содержательные тексты с вероятностя­ ми Р1,Р2,..*,Р|1| букв алфавита I, Р,- вероятность буквы с номером] в содержа­ тельных текстах. Пусть на множестве ключей К14задано равномерное распре­

деление (ключом является реализация выборки объема N из равномерного распределения на К). Тогда вероятность Р(а3=1, а^а=17о](аД=Ъ^ а/а^ ^ -к ,)) того, что>тая и з+<1-тая буквы открытого текста были равны, соответственно, 1и Г при условии, что )-тая и ]’+с1-тая буквы шифрованного текста равны Ь, и

Ь|н| выражается формулой

Р(^=1,^+а=17^(д)=^,^(а]+<1)=Ь]+а)=

_ Р(а} = 1,а ка =Г;<гу (ау) = Ъ} , а ] (а ) = Ь]+, )

Р(сгу (ау ) = Ър су ] {а]+а ) = Ь]+, )

/

Л82

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

Для рассматриваемых букв шифрованного текста Ь(и Ъ)+аупорядочим

в соответствии с невозрастанием полученных значений условных вероятно­

стей и запишем в вертикальную колонку пары букв открытого текста , при

Г

этом верхние пары будут иметь большую условную вероятность, чем нижние. Построив такие колонки для каждого^е {1,...,Ы} и расположив их по порядку слева направо, можно утверждать, что пары

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

Метод дешифрования с использованием взаимного индекса сов­ падения.

Пусть 3 =11,12,...Ды; 3 '=Г ],Г2,• • •Л'ы' - последовательности длины, соот­

ветственно, N и букв алфавита I.

ОПРЕДЕЛЕНИЕ. Взаимным индексом совпадения последовательно­ стей 3, 3' называется величина

183

Т . г , г ,

М1с(3 ’ 3 ')‘ ' !Ж _ ’ гдеР; (Р'0 - частота встречаемости буквы 1 в последовательности 3 (3').

Данная величина совпадает с вероятностью совпадения букв в последователь­ ностях 3, 3' при случайном независимом и равновероятном выборе позиций этих букв последовательностях 3, 3'.

Пусть 3 - случайная выборка объема N из некоторого распределения

М1С( Р ,Р ') = ^ Р ' . /б/

совпадает с вероятностью Р(^=Г^) события (^=Гу) при случайном и равнове­ роятном выборе выборе] и]' в случайных последовательностях 3, 3'.

Очевидно, для реализаций выборок 3, 3' длины N=14' из распределе­ ний Р , Р' справедлив предельный переход по вероятности

Х ^ ' > М1С(3, 3')= —-------- ж .в.->У/>Р',. = М1с(Р,Р')

а’ Ж '

приИ—> со. Поэтому при достаточно большом N пользуются с некоторой на­ дежностью приближением

Пусть, как и ранее, Р=(Р1,Р2,---,Р|1|) вероятностное распределение букв содер­ жательных текстов, а Р'=(Р' 1,Р'2, ,Р'щ) - неизвестное распределение на I, принадлежащее множеству Р(0€к) распределений вида: -

?(а ‘)=(Ро'1(1),Ро'1(2),-•

где а принадлежит множеству К подстановок на I (Ро 'о)_ вероятность .ртой буквы, для ее расчета исходя из набора (РьР2,...,Р|1|) необходимо найти сГ’О) -

образ буквы ] при подстановке а Предположим, что множество К подстановок таково, что при любых

различных ст,а',а*€К величины М1с(Р(ст"|),Р(ст'"|) ) = ^ Р г_|(.)Р г_|<.| и

184

различаются так, что различаются и взаимные индексы совпадения М1с(3(сг), 3(сг')), М1с(3(ст),3(ст*)) для выборок 3(а), 3(ст'),3(ст*) из распределений Р(а '), Р(а ■), Р(а*-‘).

Приведенное выше приближенное равенство (,) является основным средством решения следующей задачи. При известных значениях М1с(Р(ст '), Р(ст' ‘)), М1с(Р(а |),Р(ст*1)) и известной подстановке а найти ст' и а* по реали­ зациям выборок: 3(<т), З(а'), 3(ст*) из распределений

Р(а”'), Р(а '), Р(а*-‘).

Для решения этой задачи подсчитывают взаимные индексы совпаде­ ния М1с(3(а),3(а')), М1с(3(ст),3(а*)) выборок 3(а), З(ст') и 3(а), 3(ст*) и. определяют по ним приближенные значения величин МЦРСа'^РСа'1)) и М1с(Р(ст‘|),Р(а*1)), Откуда узнают и неизвестные а' и а*.

Метод Симпсона.

Перейдем теперь к изложению метода дешифрования шифра последо­ вательной замены при известном периоде ключевой последовательности.

Пусть ЬьЬ2,...,Ьы - известный шифртекст, б - период ключевой после­ довательности.

Для всех возможных пар (а,ст') из КхК подсчитывается значение веро­ ятности М1с(Р(а''), Р(а'-')). Проводится разбиение множества К на классы ксК эквивалентности так, что пары из одного класса имеют одинаковое зна­ чение вероятности, а из разных классов к, к' - разное значение вероятности.

Выписывают шифртекст в следующем виде:

Пусть <51,02,...,<5(1- начальный отрезок неизвестной ключевой после­

довательности. Тогда первая строка букв - последовательность 3(1) результат шифрования букв открытого текста по простой замене Ст|, вторая - 3 (2) - по <т2, ...<1-тая - по <5(1. Далее предполагают, что каждая последовательность 3(]’)

является реализацией выборки из неизвестного вероятностного распределения Р(о-:‘). Подсчитываются значения взаимных индексов совпадения

М1с(3(1),3(0),)е{1,...,<1}. Опробуют в качестве неизвестной подстановки 01

все подстановки а из К. Для опробуемого варианта ст при каждом фиксиро­ ванном )€ ( 1 ,...,6} проводят сравнение значения взаимного индекса совпаде­ ния М1с(3(1),3(])) с вероятностями: М1с(Р(ст1),Р(ст'1)), а'еК . Для каждого

{1,...,<!} находят наиболее близкое значение М1,с(Р(ст'1),Р(ст''1)). Этому зна­

187

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

Читателю, интересующемуся цифровой обработкой сигналов, реко­ мендуем прочесть ПРИЛОЖЕНИЕ 1 и книги: А.В. Оппенгейм, Р.В. Шафер «Цифровая обработка сигналов», М., Связь, 1979,416 с.; Л.М. Рольденберг, Б.А. Матюшкин, М.Н. Поляк «Цифровая обработка сигналов», М., Связь, 1990.

Параграф 3.2 Открытые сообщения и их характеристики (/Фом/)

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

В данном параграфе под открытым текстом, как правило, мы понима­ ем содержательный читаемый текст на каком либо языке.

Модели шифров, криптосхем, шифраторов, модели ключевых систем шифров строятся с использованием моделей открытого текста (или моделей источника открытых сообщений). Все модели, в том числе и модели открытых сообщений, обычно делятся на два класса: детерминированные и вероятно­ стные.

Детерминированный источник сообщений.

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

Число символов в алфавите математики называют мощностью алфа­ вита. Например, алфавит А(1)={А,В,С,Б,...,Х,У,2} - прописные буквы анг­ лийского языка. Мощность алфавита 26 (иногда вместо пробела используют

188

букву 2). Алфавит А(2)= {А,В,С,Б,... ,Х,У,2, а,Ъ,с,..., х,у,2, 0,1,2,... ,9, □ , .

« » ? !}- мощность алфавита 70. Алфавит А(3)={0,1} - мощность 2. Часто используются алфавиты, представляющие собой двоичные наборы длины п (как правило 5<п<8) или двоичные коды, например, международный теле­ графный код (МТК-2). Полный русский алфавит состоит из 33 букв:

А Б И Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я , пробела, точки,запятой.

Отождествляют: в ряде случаев Е и Ё, иногда И и И, а иногда Е и Э, часто отождествляют Ь и Ъ. Добавляя пробел, говорят, что алфавит состоит из 34 букв, а с некоторыми отождествлениями букв алфавит содержит от 28 до 33 букв.

Пусть I - некоторый алфавит, мощности |1|. Текст, записанный в алфа­ вите I, имеет длину - число символов в соответствующей последовательно­ сти. Последовательность к символов называют к-граммой в алфавите I. Мате­ матики, как правило, под последовательностью обычно понимают бесконеч­ ную последовательность символов алфавита I, конечную же последователь­ ность называют словом в алфавите I. Двоякое использование терминов мы, по возможности, будем отмечать и далее во всей книге.

Собственно источниками открытого текста является отдельный чело­ век или группа людей, радиопередающие станции, пункты телеграфной и те­ лефонной сети и т. д. Каждый источник открытого текста (сообщений) харак­ теризуется своими особенностями: используемым алфавитом, например, рус­ ским алфавитом; определенной структурой тематики сообщений, например, о погоде, о политике; математический текст, физический и т. д.; частотными характеристиками сообщений и другими особенностями, например, так назы­ ваемыми вероятными словами: «Сообщаю Вам», «Докладываю», «На Ваш номер «...» сообщаю», «старший оперуполномоченный провинции Логар майор Тарасов», и т. д. Сообщения на английском язык,е передаваемые по телетайпу, скорее всего используют алфавит А(2). Частный корреспондент, намеревающийся шифровать свои сообщения, во многих случаях предпочтет использовать алфавит А(1). Данные, передаваемые при межмашинном обме­ не, удобнее отображать с использованием алфавита А(3) (см. В.М. Фомичев, «Симметричные криптосхемы», М., 1995).

Каждый источник сообщений порождает тексты в соответствии с пра­ вилами грамматики, что находит отражение и в других характеристиках со­ общений. Например, в содержательных текстах на английском языке за бук­ вой «ц» всегда следует буква «и», в русских текстах буквы «ь» и «ъ» никогда не располагаются рядом и не следуют за гласными буквами. Всякий источник сообщений можно моделировать списком допустимых (т.е. встречающихся в

189

'каких-либо текстах) к-грамм при к=1,2,3,... Если к-грамма не является допус­ тимой, то ее называют запретной или запрещенной.

Разделение множества к-грамм на допустимые и запретные опре­ деляет детерминированную модель источника открытых сообщений. В

такой модели открытый текст рассматривается как последовательность сим­ волов некоторого алфавита, не содержащую запретных к-грамм.

Построение детерминированной модели исследуемого источника от­ крытых сообщений можно реализовать в результате статистической обработ­ ки генерируемых им текстов. Для этого следует «просмотреть» достаточно большое количество текстов, сгенерированного данным источником, и все не встретившиеся к-граммы отнести к множеству запретных к-грамм источника. Естественно, чем большее количество материала отработано, тем эффектив­ нее применение прстроенной модели сообщений на практике для решения , различных криптографических задач.

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

Источник передачи данных.

Появление систем телеобработки привело к появлению нового вида электрической связи, так называемого «передача данных». Целью передачи данных является передача информации для обработки ее вычислительным машинам или же выдача ее этими машинами. Принципиальная новизна вида связи - передачи данных - состоит в том, что эта связь осуществляет обмен информацией между ЭВМ, а так же между ЭВМ и человеком. Данные, пред­ назначенные для машин, называют «формализованным языком», языком ма­ шин. Этим подчеркивается, что они не предназначены непосредственно для восприятия человеком. Эти данные передаются в цифровом виде (часто в виде двоичной последовательности). Осмысливание их человеком может происхо­ дить только после их представления в соответствующей форме. В криптогра­ фических терминах понятия формализованного языка представляют собой словарные величины, а их условные формы - кодобозначения, последние изо­ бражаются в виде буквенных, цифровых и смешанных групп различной дли­ ны (разрядности). Формализованный документ оформляется в виде так назы­ ваемого «формата», т. е. формы, в которой размещение данных осуществляет­ сяпо некоторым жестким правилам на местах, определяемых для данного формата шаблоном. Таким образом, для чтения таких документов необходи­ мо знать формальный язык и форматы документов. Можно сказать, что фак­ тически открытое сообщение в формализованном языке представляет собой кодограмму, а перевод открытого сообщения в формализованный язык есть позиционное кодирование смысловых сообщений нескольких языков, каждый

190

из которых кодируется своим кодом и располагается на определенном месте формата сообщения. Таким образом, для формализованных сообщений исче­ зает понятие открытого текста в общепринятом его понимании «читаемого» текста.

Признаками «открытого текста» текста формализованного являются не его читаемость, а различные его детерминированные и статистические при­ знаки, связанные с применяемыми способами сжатия и кодирования в систе­ мах дискретного фототелеграфа, телевидения, ЭВМ.

Вероятностные источники сообщений.

В этих моделях источник открытого текста рассматривается как ис­ точник случайных последовательностей. Считается, что источник генерирует конечную или бесконечную последовательность случайных символов х(1),х(2),...,х(п) из алфавитаI. Вероятность случайного сообщения

«1(1),1(2),..., 1(п)» определяется как вероятность совместного события Р(1(1),1(2),..., 1(п ) ) = Р (х (1 )= 1 (1 ),х (2 )= 1 (2 )„ .,,х(п)=1(п))).

При этом, естественно, требуют выполнения условий:

1) для любого случайного сообщения «1(1 )Д 2),..., 1(п)»

Р(1(1),1(2),...,1(п))>0;

2)

1(1),1(2),..'.,1(п)

3) для любого случайного сообщения «1(1),1(2),..., 1(п)»

Смысл последнего условия состоит в том, что вероятность всякого случайного сообщения длины п есть сумма вероятностей всех «продолжений» этого сообщения до длины 8>п (некоторый вариант аксиомы Колмогорова).

Текст, порождаемый таким источником, является вероятностным ана­ логом языка. Он обладает одинаковыми с языком частотными характеристи­ ками к-грамм. Задавая конкретное вероятностное распределение на множестве открытых текстов, мы задаем соответствующую модель источника сообще­ ний. Рассмотрим некоторые частные случаи этой общей модели.

Стационарный источник независимых символов алфавита.

/В этой модели предполагается, что вероятности сообщений полностью определяются вероятностями отдельных символов алфавита: