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

141

Если бы текст был бы подлиннее и строк было бы побольше, то в каж­ дой строке и в каждом столбце осталось бы ровно по одной не зачеркнутой клеточке и перестановка была бы восстановлена.

В нашей таблице мы только можем утверждать, что 6-ой столбец сле­ дует за 3-им (обозначим это событие следующим образом 3 —>6), если 6-ой столбец не является последним. Для 6-го столбца может быть два варианта

продолжения

8

Т

3 —У6 —^ 5

Нам надо рассмотреть оба и постараться отсеять ложный. Если отсеять ложный не удастся, то надо продолжать оба варианта

8—>4 1

тт

3 —^ 6—> 5 —^ 2 —> 7

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

7

т

3 —^ 6	—^ 5 —^ 2		—^ 8 —^ 4 —^ 1 —^ 7
4'	4"	4"
8	4	1 —>7
4,	4,
4	1.—» 7

5

4

2 —>7

1 —>7 Каждой ветви дерева соответствует некоторая перестановка столбцов.

Далее проверяем каждый вариант на осмысленность и получаем пра­ вильный вариант.

3 —^ 6 —^ 5 —^ 2 —^ 8 —У4 —У1 —^ 7

Заметим, что не обязательно было строить дерево до Ъонца. Например, ветвь 3 —> 6 —> 8 —> 4 —>5 можно было отсеять сразу. Разве можно признать

осмысленным следующий фрагмент текста.

142

3	6	8	4	5
я		м		в
ш	У	е	г
ж	е	о	л
ч	т	я		о
г	У	Щ е		3
к	а	т	ь	е.
е	а	т		а

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

1.Предварительная работа. Анализируя достаточно представительный объем открытых текстов, построить множество запретных биграмм.

2. Предварительная работа. Составить словарь всевозможных у-грамм для

у=2,3,...,с1, которые могут встретиться в открытом тексте. Число 6. выбира­ ется, исходя из возможностей вычислительной техники.

Построить таблицу 8x8. При этом перебираются последовательно все за­

претные биграммы и для каждой опробуемой биграммы - последовательно все строки. Если хотя бы в одной строке первый символ биграммы встречает­ ся в 1-том столбце, а второй в - >ом, то клеточка 1 х | таблицы зачеркивается.

3.Выбрать некоторый столбец в качестве исходного.

4.Начать процедуру построения дерева путем пристраивания к исходному столбцу всех вариантов столбцов.

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

6. Для каждого из не отсеянных вариантов добавляем еще один столбец и

проводим отсев ложных вариантов по словарю разрешенных 4-грамм.

Если словарь был построен только для с!< 3 , то отсев проводится путем проверки на допустимость 3-грамм, встретившихся в последних 3-х столбцах каждой строки. Продолжаем этот процесс до получения полной перестановки. Ниже приведен восстановленный для нашего примера текст.

I

143

1

2

3

4

5

6

7

8

1	я		в	а
2	ш	У		ч
3	ж	е		б
4	ч	т	о
5	г	У	3	е
6	к	а		а
7	е	п	е	Р
8	3	н	а	ю
9	а	ш	е	й
10	е		м	е
11	Р	е	3	Р
12	м		н	а
13	т	ь		с
14	л	а		я
15	ч	а	Т	ь
16	е	л	а
17	Р	ь	т	е
18	г	о		с
19	в	ы		б
20	У	3	н	а
21	е	к	о	г
22	о	г	д	а
23	а	д	е	ж
24	и	м	е	л
25	т	ь	т	Р
26	X	О		ь
27	е	д'	е	л
28	3		в
29	в	н	е
30	й		в	и
31	в	а	с

м		п и
е	г	о
о	л	е

ям О

щ	е	с
т	ь	т .

ья

вв

	в	о	л
н	я		п
е	н	ь	е
к	а	3	а
н	.а	ч	а
	м	О	л
	X	О	т
п	О	в	е
т	м	О	е
	ы	д	а
	н	е
л	и		н
д	а		к
д	б		н
	У		я
а		X	о
е	д	к	о
	в		н
ю	е	р ,	а
д		р	е
н	а	ш	е
Д	е	т	ь

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

144

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

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

С другой стороны, при уменьшении материала задача дешифрования су­ щественно усложняется. Действительно, представьте себе, что Вам предложе­ но дешифровать зашифрованный с помощью простой замены шифртекст, со­ стоящий из одного первого слова нашего первого примера ДОЧАЛЬ. Для ка­ ждого слова из шести различных букв найдется простая замена, при примене­ нии которой мы получим данный шифртекст. Проблема заключается не в том, чтобы найти ключевую подстановку, а в том, как выбрать из обширного мно­ жества вариантов восстановленных открытых текстов именно тот, который был зашифрован. Таким образом, важной характеристикой-эффективности криптографической защиты является степень неоднозначности восстановле­ ния открытого текста по шифрованному. Эта характеристика шифра будет изучена в главе 4. Сейчас же мы дадим качественное определение этого поня­ тия. Под степенью неоднозначности г естественно понимать математическое ожидание числа вариантов открытых текстов, которые могут быть получены при применении алгоритма дешифрования. Если предположить, что при слу­ чайном выборе ложного ключа (ключа, не совпадающего с истинным клю­ чом, с применением которого был получен шифртекст, восстановленный при расшифровании) и расшифровании на этом случайном ложном ключе рас­ шифрованный текст не отличается от случайного текста, то вероятность того, что полученный текст длины N будет осмысленным (по классическому опре­ делению вероятностей) равна отношению числа благоприятных исходов — числа А (К) осмысленных открытых текстов длины N к общему числу текстов длины N. которое равно, очевидно, пн, где п - число букв в алфавите откры­ тых текстов. Для того чтобы получить степень неоднозначности, необходимо умножить полученное отношение на число К вариантов ключей. Откуда по­ лучаем формулу

г=г(М)=КА(]Ч)п'н (*)

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

му чрезвычайно велика.

145

Степень неоднозначности, как будет показано в главе 4, позволяет классифицировать шифры по степени их криптографичесой стойкости. Каче­ ственные соображения здесь таковы. Если неоднозначность дешифрования (возможное число получаемых открытых текстов) есть г(К), а цель дешифро­ вания определена получением открытого истиного текста, то вероятность по­ лучения именно его оценивается величиной 1/г(ТМ). Согласно /Про/, шифры для которых г(Ы)=А(И) называются абсолютно (теоретически) стойкими (для абсолютно стойкого шифра применение любого алгоритма дешифрования не дает никакой информации об открытом тексте). К формуле (*), ее выводу и ее тратовкам следует относиться весьма осторожно (см. параграф 4.3). Действи­ тельно, согласно /Про/, для получения абсолютной стойкости шифра доста­ точно иметь пм ключей.

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

Согласно /Про/, шифры, не относящиеся к классам теоретически стой­ ких или практически стойких шифров, называют шифрами временной стойко­ сти.

Число осмысленных открытых текстов длины N для больших значе­ ний N обычно считается равным 2™, где Н - энтропия (в битах) на знак от­ крытого текста (см. главу 4). Для русского литературного текста, как показы­ вают экспериментальные расчеты, величина Н близка к единице. Для более формализованных текстов (организационно-распорядительных писем, доку­ ментов и т. п.) величина Н заключена в пределах от 0.5 до 0.8.

Возвращаясь к анализу шифра простой замены, отметим, что степень неоднозначности восстановления открытого текста для этого шифра согласно /Про/ имеет вид

г(Ы)=п!2н% м,

где Н - энтропия на букву открытого текста.

Шифр простой замены является теоретически стойким при шифрова­ нии литературного русского текста (п=32) длины в одно-два слова и обеспе­ чивает только временную стойкость при большом объеме материала.

Эксперименты показывают, что практическое дешифрование шифра простой замены для русского литературного текста возможно в случае, если длина шифртекста в 2-3 раза превышает размер алфавита открытого текста, т. е. равна 60-100 буквам.

Дешифрование шифра гаммирования при некачественной гамме.

Пусть I некоторый алфавит, буквы которого упорядочены в естествен­ ном порядке. Запись 1+Г=Г' будем понимать как модульное сложение номе­

146

ров букв из {1,2,...,|1|-1,0}по модулю |1|. То есть, записывая уравнения, свя­ занные с гаммированием, мы отождествляем буквы с их номерами в алфавите. Предположим, что в качестве знаков гаммы в шифре гаммирования могут быть лишь знаки 1, Ге1, то есть уравнения образования шифртекста Ь|,Ьг,..

Ът имеют вид {1,2,...,14} (можно сказать, что в данном примере ис­ пользуют всего 1 бит гаммы).

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

Ъг 1	Ъ2	-1	Ьы -1
Ь| -1'	Ъ2- 1'		Ьн-Г

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

к	ш и П Ш О л	ш А Э	И	Ж
в	р А 3 т ж г	р Ш Ф	А	Я

Прочитали слово КРИПТОГРАФИЯ?

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

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

убыванием (точнее, не возрастанием) вероятностей

Р(^)-Р(а.ЬУр(Ь)- Р<ау - а>,^

.

2,р(а )я(Ь - а )

а' при известной фиксированной букде Ь. Здесь (р(а),ае1) - вероятностное рас­

пределение букв открытого текста, (я(с), с е 1) - вероятностное распределение

на знаках гаммы.

147

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

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

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

148

В связи с вышеизложенным, обязательная составная часть крипто­ графии - это исследование вероятностно-статистических свойств выходных и промежуточных гамм. Для этих целей можно использовать стандартные ста­ тистические критерии проверки качества псевдослучайных последовательно­ стей (см. Кнут, «Искусство программирования». Т. 2.) либо специально разра­ ботанные статистические процедуры.

Достаточно частой является ситуация, когда гаммы или открытый

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

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

1

149

где п - мощность алфавита открытого (шифрованного текста), Н - энтропия открытого текста на букву.

Таким образом, дешифрование принципиально возможно для литера­ турного открытого текста (Н=1), если шифрующая гамма принимает к< ^ возможных значений, т.е. к< 16 (положим п=32, Н=1, решая уравнение

Т 2Ш

1ст - ___ = 1

п N ’

получим к=16).

Реальное дешифрование обычно удавалось провести при к < 8 . Высо­ коклассные специалисты добивались дешифрования где-то при к=12 .

Для шифрования не равновероятной гаммой оценки приобретают вид

2 ^ 2 ын

где Н у - энтропия гаммы.

Дешифрование шифра гаммирования при перекрытиях.

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

Ь\=а1,+ ^ , и Ь2,=а2,+ у ,, *=1,М.

Обращаем внимание, что открытый текст и шифрованный текст здесь разные, агамма одинакова. Злоумышленнику нетрудно из шифрованных текстов по­ лучить разность двух открытых текстов.

а\ - а(2 = Ь | -Ъ2 = с,

ипопытаться восстановить оба открытых текста. Это просто сделать, если один из открытых текстов известен, в этом случае

а] =с(+а2

2 1 2

где с* и а / - известны, а а , - легко восстанавливается. Открытый текст а, -

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

150

Если шифруются обычные тексты и ни один из них не известен, то для дешифрования используют стандарты.

Опробуют елово открытого'текста и пытаются восстановить второй открытый текст Если вариант опробования-был выбран неправильно, то вто­ рой открытый текст будет бессмысленным, если правильно - то осмыслен­ ным, и так по частям мы восстановим оба открытых текста.

Например, предположим, что в один из текстов начинался со слова «СЕКРЕТНО». В этом случае, подставив его на нужное место, мы восстано­ вим фрагмент второго текста, например,

С Е К Р Е Т Н О В О Е Н Н О-М

Угадав продолжение фрагмента второго текста, мы получаем продолжение первого текста

С Е К Р Е Т Н О С О О Б Щ В О Е Н Н О-'М О Р С К О Й

Продолжая первый текст, получаем

С Е К Р Е Т Н О С О О Б Щ А Ю В О Е Н Н О-М О Р С К О Й Ф

Снова обращаемся ко второму тексту

С Е К Р Е Т Н О С О О Б Щ А Ю В А М В О Е Н Н О - М О Р С К О Й Ф Л О Т

Таким образом, дешифровальщик восстанавливает оба текста. Обращаем внимание на то, что наличие перекрытий шифра опасно и

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