Распознавание одноключевых сообщений

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

Если индикаторы являются скрытыми , то внешних признаков того, что сообщения действительно являются одноключевыми, может и не быть. Как в таком случае криптоаналитик может установить этот факт? Предполагая, что в данной системе шифрование выполняется побуквенно, надо сначала подписать сообщения одно под другим, выровняв их по началам шифрованных текстов, и применить простой статистический тест. Если два шифрованных сообщения не являются одноключевыми, то вероятность того, что буква одного шифрованного текста совпадет с соответствующей буквой другого текста (то есть с той, которая стоит под ней), составляет 1 шанс из 26. Если сообщения являются одноключевыми, то вероятность того, что эти буквы шифрованных текстов совпадают, равна вероятности того, что совпадают соответствующие буквы открытых текстов. А эта вероятность, в свою очередь, примерно вдвое превосходит вероятность случайного совпадения, то есть составляет примерно 1 шанс из 13 как для английского языка, так и для большинства языков, использующих латинский алфавит. Это частный случай более общего наблюдения, которое мы рассмотрим в главе 7; подробное математическое доказательство содержится в приложении M6. Отсюда следует, что если подписать одно сообщение под другим, то для пары неодноключевых сообщений на 100 знаков шифрованного текста должно встретиться примерно четыре пары одинаковых букв, а для одноключевых сообщений таких пар одинаковых букв должно быть примерно семь или восемь на сотню. Чем длиннее сообщения, тем более вескими оказываются аргументы за или против наличия общего ключа. Доводы в пользу наличия общего ключа становятся намного более вескими, если обнаружены совпадающие полиграфы, например, двух или трехбуквенные, поскольку их появление в неодноключевых сообщениях весьма маловероятно. Разумеется, и такой тест не является абсолютно надежным, так как в парах шифрованных текстов могут встречаться и случайные совпадения полиграфов. Джек Гуд (см. [3.1]) пишет, что однажды он обнаружил в паре сообщений военного времени абсолютно ложное повторение октографа. Вероятность подобного восьмизначного совпадения меньше, чем 1 шанс из 20 000 000 000. Это удивительно, даже если учесть, что были просмотрены все шифрованные сообщения военного времени. С другой стороны, Джек Гуд пишет также (см. [3.1]), что он обнаружил 22-буквенное повторение, и оно было истинным!

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

Пример 3.2

Три сообщения зашифрованы с помощью системы, в которой буквы шифруются последовательно одна за другой. Самое короткое сообщение состоит из 500 знаков. Число совпадений знаков шифрованного текста внутри каждой пары сообщений следующее:

Сообщение 1 и сообщение 2 : 37.

Сообщение 1 и сообщение 3 : 27.

Сообщение 2 и сообщение 3 : 16.

Возможно ли, что какая-нибудь пара из этих трех сообщений имеет один и тот же ключ?

Решение

Если общая часть имеет длину 500 знаков, то ожидаемое число совпадений в паре шифрованных текстов для одноключевых сообщений будет около 38, а для неодноключевых сообщений - всего лишь около 19. Следовательно, на основании приведенных данных можно с уверенностью сказать, что первое и второе сообщения - одноключевые, а второе и третье - неодноключевые. Статистические данные для пары сообщений 1 и 3 являются аномальными, и, опираясь только на них, к определенному заключению прийти нельзя, поскольку вероятность появления 27 совпадений при ожидаемых 38 примерно такая же, как и вероятность появления 27 совпадений при ожидаемых 19. (Математические основы этой теории подробно описаны в литературе - см., например, [2.4]). Однако, поскольку мы почти уверены в том, что первое и второе сообщения - одноключевые, а второе и третье сообщения - неодноключевые, то логично сделать вывод, что первое и третье сообщения также неодноключевые.

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

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

Задача 3.1

Резидент-меломан послал трем своим агентам однотекстовые сообщения, зашифровав их шифром Вижанэра со следующими ключевыми словами:

(1) RHAPSODY, (2) SYMPHONY и (3) SCHUBERT.

Что обнаружит криптоаналитик, проанализировав пары, составленные из этих шифрованных текстов? Проверьте ваши выводы, зашифровав сообщение

NOW IS THE TIME FOR AL GOOD MEN TO COME TO THE AID OF THE PARTY

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

Заканчивая описание шифра Вижанэра, предлагаем решить следующую задачу.

Задача 3.2

Сообщение длиной 249 знаков зашифровано с помощью шифра Вижанэра (пробелы в открытом тексте заменены на букву Z). Шифрованный тест имеет вид:

GLEKR DAKRD SHZIZ MUIOK RQSSJ MTAME ZIESO

YMAHB PLZBF DSHMW HHEXZ TAHZX YIGTA XZMUE

TSVXZ LRIML MYNEV OEELD TANXZ TMFEM GIRSB

RESJM LEMIV XEDBX MJONA HZLHG HSVWZ MUIZV

NWESJ MTAMI UVYMD LMTRH BJZMU ETSGL EKRDA

KRDAG MMNYV RIMRD NNZFE KMSFS CVIFR WZMUM

SSCVO HSDIL MMNSG LESNT PXAHI QMMNS GLILM

FOHX.

Требуется найти ключ и дешифровать сообщение.