Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Заметим, что вместо 5-мерных можно было рассматривать и «-мерные векторы, п > 5. Предложенный метод работает и в этом, более общем случае.
§ 6.4. Повторное использование гаммы
Как и раньше, мы предполагаем, что алфавит А открытых текстов, гаммы и шифртекстов представляет собой множество чисел Zn = {0,1,..., Tl — 1} .
Пусть в распоряжении криптоаналитика оказались две криптограммы, полученные наложением одной и той же гаммы на два разных открытых текста:
Рассмотрим возможности криптоаналитика по восстановлению исходных открытых текстов.
S{ =T1 + /"(mod я), S2 = T2 + /"(mod л),
где
Ілава 6
Прежде всего можно найти позначную разность S = S1 -S2 = T1 -T72Cmodw).
Пусть S = 2,... • Тогда поставленная задача сводит-
ся к попытке подобрать пару открытых текстов, разность которых совпадает с известной последовательностью S. Будем в связи с этим говорить о разложении S на два составляющих открытых текста. В случае когда данные тексты являются нормативными текстами, например, на русском, английском или другом языке, для решения последней задачи используется ряд подходов. Интуитивно понятно, что при достаточной длине текстов маловероятна возможность множественного представления данной последовательности S в виде разности T1-T2. Как правило, такое разложение бывает единственным. Здесь имеет место приблизительно такая же ситуация, как и при рассмотрении вопроса о расстоянии единственности (см. гл. 7).
Один из таких подходов (хорошо известных из истории криптографии) связан с использованием некоторого запаса слов или словоформ, часто встречающихся в открытых текстах. Это могут быть, например, стандарты переписки, частые ^-граммы и т. п.
Предположим сначала, что одно из вероятных слов встретилось в начале первого сообщения:
В таком случае можно вычислить начало второго сообщения:
вероятное слово
T2 — ^2 ^2 ***^/ •** *
140
Шифры гаммирования
Если / > 4, легко определить, является ли начало T2 “чи-таемым” или нет. В первом случае нужно попытаться продлить начало T2 по смыслу. Во втором случае нужно сдвинуть начало вероятного слова в T1 и проделать то же самое. Если удалось развить T2 до т знаков (т> I):
»1 H H
T2 = /у2 tт ¦¦¦, то можно вычислить и соответствующие т-1 знаки
Ti =/,...// tM +sl+l...tm +sm,
и попытаться, в свою очередь, развить по смыслу Г,.
Продолжая этот процесс далее, мы частично или полностью восстановим оба текста или убедимся в том, что опробуемого вероятного слова данные тексты не содержат. В последнем случае следует попытаться ту же процедуру проделать для следующего вероятного слова.
Может оказаться так, что при опробовании некоторого слова удается восстановить лишь часть каждого из текстов, а дальнейшее развитие их по смыслу бесперспективно. В таком случае следует продолжить работу с другим вероятным словом.
Конечно, данный метод далеко не всегда приводит к успеху. Ho нельзя пренебрегать шансом, который он дает.
Пример
Возьмем два текста на английском языке, содержащих наиболее часто встречающуюся триграмму THE:
T1 = THE APPLE, T2 = TELL THEM,
и зашифруем их одной и той же гаммой Г = ONETWOTHRE. При этом будем пользоваться числовыми значениями букв согласно следующей таблице:
141
і лава 6
00 01 02 03 04 05 06 07 08 09 10 11 12
А в С D E F G H I J К L M
13 14 15 16 17 18 19 20 21 22 23 24 25
N О P Q R S T U V W X Y Z
В результате зашифрования получаем:
Ti 19 07 04 00 15 15 И 04
T2 19 04 11 11 19 07 04 12
Г 14 13 04 19 22 14 19 07
S1 07 20 08 19 11 03 04 11
S2 07 17 15 04 15 21 23 19
S 00 03 19 15 22 08 07 18
Предположим теперь, что триграмма THE находится в начале Tx, тогда можно вычислить начало T2:
T1 = T2 + S = T H E А
19 07 04 00
T2=T1-S = T E L L
19 04 11 11
Дальнейшие попытки продолжить по смыслу T1 или T2 к успеху не приводят. Поэтому предположим, что T2 также содержит THE. С учетом полученного результата, мы получаем два варианта расположения триграммы THE в тексте T2. В первом из них триграмма THE расположена, начиная с пятой позиции, во втором — начиная с шестой позиции.
142
Шифры гаммирования
Рассмотрим первый вариант:
T2 19 04 11 И 19 07 04
T E L L T H E
T2 19 07 04 00 15 15 11
T H E А P P L
Теперь ясно, что T2 = THE APPLE, откуда получаем Т\ = TELL THEM.
Идея другого способа разложения разности открытых текстов состоит в упорядочении возможных вариантов пар букв (J1J1) по убыванию апостериорных вероятностей
p(tt =Vjl =V-Ufsl = и) , u,veA, 7 = 1,2,... ,
построении для каждого / упорядоченных колонок, состоящих из таких пар, и попытке чтения (аналогичной изложенной выше) в колонках сразу двух открытых текстов. При этом (как и ранее) используются позначные модели рассматриваемых последовательностей и аналог формулы (9).
§ 6.5. Криптоанализ шифра Виженера
Рассмотрим шифр модульного гаммирования с уравнением (1), для которого гамма является периодической последовательностью знаков алфавита. Как указывалось в историческом экскурсе, такая гамма обычно получалась периодическим повторением некоторого ключевого слова. Например, ключевое слово KEY дает гамму KEYKEYKEY... . Рассмотрим задачу вскрытия такого шифра по тексту одной криптограммы достаточной длины.
