|
|
|
|
|
|
|
|
|
|
Несмотря на то, что задача вскрытия шифров в этой книге не ставилась, но без описаний общих подходов к этой проблеме нельзя ни понять эволюцию криптографии, ни дать понятия устойчивости шифров. Поэтому хотя бы кратко изложим подходы к раскалыванию ряда простых шифров, что даст общую картину приемов, используемых в этой области. Существует пропасть между ручными и машинными способами шифровки. Ручные шифры весьма разнообразны и могут быть самыми неожиданными. Кроме того, закрываемые ими сообщения предельно кратки. По этой причине их вскрытие гораздо более эффективно выполняется людьми. Машинные шифры более стереотипны, вычислительно предельно сложны и предназначены для закрытия сообщений очень большой длины. Естественно, что вручную их расколоть даже и не надо пытаться. Однако и здесь криптоаналитики играют главную роль, выступая в роли полководцев криптографической атаки, хотя само сражение ведут лишь технические и программные средства. Недооценка этой особенности обусловила поражение шифров криптографической машины Энигмы во время Второй мировой войны.
Всегда считаются известными тип шифра и язык сообщения. Их могут подсказать алфавит и статистические свойства шифровки. Однако обычно информация о языке и типе шифра становится известной из агентурных источников. Положение несколько напоминает взлом сейфа: если "медвежатник" и не знает заранее конструкции вскрываемого сейфа, что представляется маловероятным, то он быстро определит ее по внешнему виду, фирменному знаку. Поэтому неизвестным является только ключ, который предстоит вскрыть. Трудность заключается в том, что точно так же, как и не все болезни лечатся одним и тем же лекарством, а для каждой имеются свои специфические средства, так отдельные виды шифров вскрываются только своими приемами.
При традиционном криптоанализе систем шифрования возможность их раскрытия зависит, в значительной мере, от квалификации взломщика. Криптоаналитик должен хорошо владеть методами дискретной математики, теории чисел, теории сложности, абстрактной алгебры, статистики, алгоритмического анализа и прочих родственных криптографии математических дисциплин, а также иметь развитую интуицию, чтобы найти метод, ведущий к вскрытию шифра, предполагая, что он существует. Процесс криптоанализа всякий раз начинается с самого начала при подходе к новой системе и опыт, полученный при раскрытии одной системы шифрования, редко когда может быть применен для раскрытия другой. Успех криптоанализа определяется алгоритмом шифрования - сложность вскрытия шифра зависит лишь от его конструкции. Это значит, что существует очень мало общих принципов криптоанализа, которые можно было бы практически использовать для раскрытия любых шифров и автоматический криптоанализ эффективен применительно к очень ограниченному классу алгоритмов.
Поэтому практически стойкость шифров к взлому принимается за меру криптографической стойкости их алгоритмов. Чем продолжительнее шифр не поддается раскрытию, тем больше причин считать его стойким. Однако стойкость шифра необязательно значит, что он является безопасным. Это означает лишь, что метод его взлома еще не найден любителями или не опубликован профессионалами. Как пример можно привести шифры, где кроме ключа шифрования имеется еще главный ключ, который называют ключом от черного входа. Такие шифры могут быть стойкими, но они не безопасны, так как обладатель главного ключа может читать любые шифровки. Следовательно, процесс криптоанализа может быть очень длительным по причине того, что криптоаналитику мало помогает успешное раскрытие других систем шифрования и ему неизвестна другая мера криптографической стойкости шифра, кроме продолжительности его сопротивления к взлому. Даже если взломщик не может прочесть сообщение, все равно нужно быть осторожным. В этом случае он может получить много информации, зная отправителя, получателя, время и длину сообщения.
Сообщения, как бы сложны они не были, можно представить себе
в виде последовательности знаков. Эти знаки берутся из заранее
фиксированного набора, например, русского алфавита или палитры
цветов (красный, желтый, зеленый). Разные знаки могут встречаются
в сообщениях с разной частотой. Поэтому количество информации,
передаваемой разными знаками может быть разным. В том смысле,
который предложил Шеннон, количество информации определяется
средним числом возможных вопросов с ответами ДА и НЕТ для того,
чтобы угадать следующий символ сообщения. Если буквы в тексте
следуют независимо друг от друга, то среднее количество
информации в сообщении приходящееся на один знак, равно:
В каких единицах выражается значение количества информации по Шеннону? Точнее всего ответ на этот вопрос дает теорема кодирования, утверждающая, что любое сообщение можно закодировать символами 0 и 1 так, что полученная длина сообщения будет сколь угодно близка сверху к Н. Эта теорема позволяет назвать и единицу информации - бит.
Каждый, кто использовал, работая на персональном компьютере, архиваторы, знает, как лихо они ужимают текстовые файлы, ничего при этом не теряя. Их работа лучшим образом демонстрирует теорему кодирования в действии. Так как для русского текста, переданного лишь прописными буквами, Н=4.43, то это означает, что в принципе в русском алфавите можно было бы обойтись лишь 22 буквами или на 45% сократить длину файлов в формате ASCII. Таким образом, сообщения языка занимают места больше, чем это необходимо. Это явление называют избыточностью языка. Благодаря ему искажения отдельных символов сообщения зачастую не разрушают содержания, что случилось бы при отсутствии избыточности. Заметьте, у компьютера наиболее часто встречаемые символы ETOANIRSHDLU (даны в порядке убывания частот в английском языке) вынесены в центр клавиатуры, чтобы при наборе текстов движение пальцев было бы минимальным. Это расположение клавиш было предложено изобретателем линотипа Оттомаром Мергенталером, который использовал избыточность языка для облегчения работы. Утверждение, что вероятность появления символа в связном тексте не зависит от его предыстории, неверно и статистически, и лингвистически. Уже давно литераторы заметили, что обычно за согласной буквой следует гласная, а за гласной согласная. Поэтому в конце XIX века петербургский математик Марков предложил текст рассматривать как цепочку символов, где вероятность появления буквы зависит от предыдущей и только от нее. Таким образом, он стал рассматривать не вероятности Pj появления в сообщении знака i, а вероятности Pij появления знака j при условии, что перед ним стоит знак i. Теория марковских цепей оказалась чрезвычайно продуктивной для криптографии, и к отдельным ее применениям мы будем возвращаться позже. Пока же достаточно отметить, что первое свое опробование она имела при анализе текстов "Евгения Онегина" самим Андреем Андреевичем Марковым. Объем информации в одном символе марковской цепи определяется следующей формулой:
В этом случае нет противоречия с требованием независимости знаков, так как знаком здесь считается не отдельный символ, а биграмма. В приложении приведена таблица вероятности встречи биграмм в русском техническом тексте по программированию. Вероятности их представлены десятью классами от 0 до 9 в порядке возрастания и образуют по средним значениям геометрическую прогрессию. Справа в этой таблице даны вероятности встречи отдельных символов. Так, из нее следует, что биграмма АЙ встречается довольно часто (класс 7), а биграмма ЙА почти совсем не попадается (класс 0). Среднее количество информации, приходящееся на один символ, определяемое по этой таблице равно 3.5 бит, что эквивалентно примерно II буквам в русском алфавите или возможности сжатия текстов примерно на 57% при их оптимальном кодировании.
Описанное свойство зависимости буквы в тексте от предыдущей называется марковостью первого порядка, а независимость букв друг от друга марковостью нулевого порядка. Естественно, что можно рассматривать также и марковости высших порядков, например второго, когда буква зависит от двух предыдущих. Для того, чтобы оценить порядок марковости в связном тексте, проведем случайное моделирование, используя сначала вероятности отдельных букв, потом биграмм, триграмм и так далее. Примеры марковского синтеза текстов разных порядков марковости от 0 до 4 приведены в следующей таблице:
0 ПАВЛНТ И ОАБУТ ЕИИЕТК ЖМЕ КСВИДАИВ 1 МОЙ ОГЛЬ ТАМАНУ ЧТЕТОГАНЕ СТА СЛИНА 2 КРУЖБЫ И ОТЧАЕТОНЕИСТАК ПЕХ ЭТОГО 3 3 В ДЕПАРЫ ЧТО НАСТЯМИ РАСПРОИСХОДИН 4 ПОНЯЛ О ГЛУБОКОЙ СИСТЕМ И ДЕЛЕ ВОДЫ
Из нее видно, что увеличение порядка марковости повышает схожесть отрывка случайного текста с естественным. Повышение порядка марковости позволяет доуточнить объем информации в сообщениях, но это очень скользкая тема есть масса разных точек зрения на нее. Действительно, вводя понятие шенноновской информации, мы похоронили понятие смысла, который связывает символы в слога, слога в слова, слова в предложения, а предложения в сообщение. Практически нет разницы, как сказать ребенку: "Нужно есть кашу!" или "Надо есть кашу!", а вот шенноновский подход эти сообщения считает различными. Поэтому оценка объема информации, содержащейся в сообщении и полученной по приведенным формулам, явно завышена. А ведь в жизни нередко бывает, что за целый день так и не узнаешь ничего нового!
Теперь рассмотрим одно приложение знаний свойств естественного текста сообщения для нужд криптографии. Требуется по отрезку текста решить, что он из себя представляет, осмысленное сообщение или последовательность случайных символов. Ряд шифров приходится на ЭВМ вскрывать перебором ключей, а вручную просмотреть свыше тысячи фрагментов вдень просто не под силу, да и скорость мала. Поэтому нужно эту задачу реализовать на ЭВМ. Пусть предстоит перебрать примерно миллиард ключей на машине со скоростью тысяча ключей в секунду, на что уйдет около 10 дней. В этом случае мы рискуем впасть в две крайности. Если будем чрезмерно осторожны в оценках, то часть несмысловых текстов будет воспринята как сообщения и передана человеку. Эта ошибка обычно называется "ложная тревога" или ошибка первого рода. При количестве таких ошибок свыше 1000 в день человек устанет и может начать проверять тексты невнимательно. Значит, допускается не более одной ошибки такого рода на сто тысяч проверок. Далее, если подойти к проверке поверхностно, то можно пропустить смысловой текст и по окончании полного перебора его опять придется повторить. Чтобы не рисковать необходимостью повторения всей работы, ошибки второго рода или "пропуски сообщения" допустимы лишь одном случае из ста или тысячи.
Самый простой критерий, который приходит в голову, связан с использованием алфавита сообщения. Если учитывать, что в нем могут встретиться лишь знаки препинания, цифры, заглавные и малые русские буквы, то в тексте сообщения встретится не больше половины набора кодовой таблицы ASCII. Следовательно, встретив в тексте недопустимый символ можно уверенно говорить о том, что он несмысловой - ошибки второго рода почти исключены при нормально работающем канале связи. Для того, чтобы снизить вероятность "ложных тревог" до принятой выше величины, требуется, чтобы текст состоял не менее чем из двадцати трех символов. Дело усложняется, если используемый код букв не избыточен, как представление в ASCII русского текста, а содержит ровно столько символов, сколько их в алфавите. Тогда приходится вести оценку по вероятностям встречи символов. Чтобы обеспечить принятые вероятности ошибок первого и второго рода при оценке максимального правдоподобия, необходимо анализировать уже около сотни символов, а анализ вероятностей биграмм лишь несколько снижает эту величину. Таким образом, короткие сообщения при большой длине ключа вообще невозможно расшифровать однозначно, так как появляющиеся случайные тексты могут совпадать с осмысленными фразами. Аналогичную задачу приходится решать и при контроле качества шифрования. В этом случае, правда, вероятность ложной тревоги можно повысить, приняв ее не свыше одной тысячной, при той же самой вероятности пропуска сообщения. А это позволит ограничиться для проверки лишь 20-30 символами.
Начинают взлом шифров обыкновенно со статистических испытаний текста шифровки, что дает общие данные об их стойкости на начальном этапе анализа. Так как цель криптографии состоит в том, чтобы преобразовать открытый текст в шифровку, смысл которой недоступен незаконному получателю информации, то можно в идеале представить шифровальную систему, как "черный ящик", вход и выход которого взаимонезависимы, так как для установления ключа, согласующего входной текст с шифром, потребуется перебор всех допустимых вариантов. Если пространство поиска ключа очень велико и невозможно с помощью имеющихся вычислительных средств проверить каждый ключ за ограниченное разумное время, то шифр является вычислительно безопасным. Надлежит сделать следующие важные замечания.
Важное значение для статистических испытаний имеет случайность текста шифровки конечной длины. Практическую меру случайности такой последовательности ввели Лемпел и Зив, авторы общеупотребимого алгоритма сжатия данных, применяемого во всех архиваторах IBM PC. Она указывает, на сколько можно сжать последовательность при использовании алгоритма Лемпела-Зива. Практически, если текст шифровки сжимается одним из архиваторов больше, чем на 10%, то шифровальная система очевидно не состоятельна. Если сжатие шифра оказалось меньше этой величины, то... все может быть. Отметим, что алгоритмам архивирования удается сжимать даже случайные последовательности символов, хотя сжатие в этом случае не превышает единиц процентов. Столь пространное описание статистического подхода к криптоанализу дано потому, что в этой главе ему будет уделено мало внимания, а вскрытие шифров будет показано лишь с точки зрения аналитического подхода. Итак, рассмотрим наиболее употребительные виды атак на некоторые известные уже шифры.
Сначала возьмем тот пример шифровки двойной перестановки, что изложен выше. Пусть имеется шифровка АЗЮЖЕ СШГГООИПЕР, которая так укладывается в таблицу 4 х 4:
1 2 3 4
1 A З Ю Ж
2 E С Ш
3 Г T О О
4 И П E P
Рассматривая маловероятные сочетания букв, легко найти истинную последовательность столбцов. Так, сочетание ГТ в 3 строке шифровки указывает на то, что после 1 столбца вряд ли следует 2 столбец. Рассчитаем статистически, какой столбец скорее всего следует за 1. Для этого воспользуемся таблицей логарифмов вероятностей биграмм русского текста, приведенной в приложении. Вероятность следования одного столбца за другим равна произведению вероятностей биграмм в строках этих столбцов. Поскольку в таблице даны логарифмы биграмм, то их достаточно суммировать, а потом выбрать сочетание столбцов с максимальной вероятностью. Для вероятностей следования за первым столбцом 2, 3 и 4 имеем выражения:
р (1-2) =р(A3) р(Е ) р(ГТ) р(ИП)=7+9+0+5=21 р (1-3) =р(АЮ) р(ЕС) р(ГО) р(ИЕ)=6+8+8+8=30 р (1-4 )=р(АЖ) р(ЕШ) р(ГО) р(ЯР)=7+5+8+7=27
В нашем случае наиболее вероятно, что после столбца 1 следует столбец 3. Для такой небольшой таблицы шифрования, которую имеем, можно перебрать все варианты перестановок - их всего лишь 24. В случае большого числа столбцов целесообразно оценить вероятности пар сочетаний разных столбцов и решить оптимизационную задачу, которая укажет перестановку столбцов, дающую фрагменты естественного текста с большей вероятностью. В нашем случае наилучший результат достигается при расстановке столбцов (2413), что примерно вдвое по вероятностной оценке достовернее ближайшей к ней по вероятности расстановки (4132). После того, как столбцы шифровки расставлены, не составит труда правильно расставить и ее строки по смыслу фрагментов текста:
2 4 1 3
1 З Ж A Ю
2 Ш E С
3 T О Г О
4 П P И E
Текст в ней уже читается и, расставив строки в порядке (4123), получим расшифровку ПРИЕЗЖАЮ ШЕСТОГО.
Теперь обратимся к приведенному выше примеру шифра решетки:
3 Т П О Ж Ш Р Е И Г А Е С Ю О
Неужели его так трудно взломать, как это утверждают некоторые авторы математических изданий? В этой шифровке видимо содержится 2 слова, если учитывать, что она длиной 16 букв, а одно слово русского языка содержит в среднем 7 букв и имеется пробел. Расшифровку проще начать с биграммы СТ.
Предположение 1.
Предположим, что наиболее частая биграмма в русском языке СТ входит в одно из слов текста. Так как Т расположена в решетке выше С, это значит, что между ними произошел поворот решетки таким образом:
**** *Т**
**** ****
**** ****
*С** ****
0' 90'
С учетом того, что эти буквы принадлежат различным прорезям решетки, получаем такой вид разгаданных частей таблиц:
**?? *Т** **П* ??** **??
**?? О*** ***Р ??** **??
Е*** **?? ??** ***А ***
*С** **?? ??** **Ю* * **
0' 90' 180' 270'
Проверим правильность этого предположения чтением, заменяя еще не ясные буквы точками: ..ЕСТО..ПР....АЮ. Это очень похожена фрагменты текста. Пометив в решетке клетку буквы С цифрой 1, обозначим с учетом поворота клетку буквы Т цифрой 2.
Предположение 2.
При составлении решеток прорези обычно размещают так, чтобы их было по одной в каждой колонке и каждом столбце, что гарантирует хаотичное и равномерное заполнение квадрата буквами. В этом случае имеется всего два варианта: 1234 и 123'4', изображенных на следующем макете решетки:
* * 3' 4
* * 3 4'
2 * * *
* 1 * *
Второй вариант 123'4' не подходит, так как не покрывает весь квадрат при поворотах, и остается 1234, что дает ШЕСТОГОПРИЕЗЖАЮ. Сообщение уже ясно, хотя расшифровка начата с неправильного поворота решетки. С учетом этого замечания получим сообщение: ПРИЕЗЖАЮ ШЕСТОГО.
Реальные шифры этого типа вскрываются еще проще. При поворотах происходят заметные смещения решетки по месту, которые весьма помогают при анализе выделить буквы, относящиеся к одному повороту. Выделив буквы, смещенные в одном направлении, получают прорезанные клетки трафарета. Если же текст сообщения имеет достаточно большую длину, то задача вскрытия шифра решетки резко упрощается из-за этой особенности. Использование ЭВМ для реконструкции решетки по вероятностям чередования букв в тексте позволяет полностью автоматизировать этот увлекательный процесс логического анализа. Однако наилучшая атака на этот шифр получается, если отгадывать вероятное слово текста, как ПРИБУДУ, ПРИЕДУ, ПРИБЫВАЮ, ПРИЛЕТАЮ, ПРИЛЕЧУ и тому подобное, так как обычно лексика сообщения примерно известна.
Разберем пример В. Никонова, опубликованный в журнале 9 "Наука и жизнь" за 1981 год, заменив использованные автором графические символы шифровки на привычные русские буквы. Итак, на доске объявлений некого учреждения, название которого популярный журнал не сообщил, появилась следующая надпись:
ТБПО ЩИЧЧЖ ЛНИЬЕЭФЭЕЭВЬ ЭКМНИО ИЩЩСКИЬОЭ СФБИТЬЛИЬШ ТБПОЧЩЬП ЛНОЭЧЖ Ь ЧЛЭПЛКПЕПООЭ ЛЭНЛКИВИЫП ФЭБСТПООЖП ЬН ЩИЧЧЖ ЧЧСУЖ
Несомненно, что это шифр. Каков же его тип? Это не может быть шифр перестановки, так как в шифровке четко проглядываются слова с регулярными окончаниями чж, иыи, оэ. Частоты встречи различных знаков шифровки явно неодинаковы. Знаки ч, и, э встречаются раз по десять, тогда как У, Ю и М лишь по одному разу, что не бывает в многоалфавитных шифрах, имеющих близкие вероятности знаков. Естественно предположить, что применен шифр простой замены. Читатели помнят, как герой рассказа Эдгара По "Золотой жук" Легран, анализируя записку о кладе, оставленном пиратами, обнаружил, что в ней наиболее часто, 7 раз, встречалось сочетание трех символов. Для английского языка это мог быть лишь определенный артикль THE (Хемингуэй иногда не реже, чем THE, использовал союз AND, что отвечало литературной задаче описать монотонность будней). У Лермонтова же наиболее часто используемое слово очень коротко - Я. С чего следует начать расшифровывание? Несомненно, с установления отправителя и получателя сообщения. Вспомним рассуждения Холмса из "Пляшущих человечков", который сразу же отождествил смешную надпись с шифровкой. Что в этой надписи могло напугать героиню, угроза? Представим, что она прочла текст: "Готовься к смерти". Не правда ли, такое неприятное сообщение слишком абстрактно, чтобы заставить ужаснуться спокойного волевого человека: кто должен готовиться и к чьей смерти? Поэтому решил Холмс, героиню напугало собственное имя и начал расшифровку отождествлением слова "Илей" с первыми четырьмя человечками. Зачастую, кроме имени получателя сообщения содержат еще и имя отправителя, как это принято в телеграммах: "Приезжаю шестого. Мама." У нашей шифровки была приписка: "Граждане, ознакомившиеся, запомнившие и исполнившие, принимаются ежедневно и без ограничений. Местком." Из нее ясен отправитель - местком. Поэтому шифрованный текст может не содержать его названия. Получатель все же должен быть доуточнен, как обращение: "всем садоводам..." или "члены кружка...". Однако это - слишком легкий путь. и предположим, что не удалось конкретизировать получателя, чтобы, используя его имя, вскрыть шифр.
Предположение 1.
Внимательно просматривая шифровку, можно обнаружить интересное удвоение знака Ч в конце последнего слова и начале последнего: щиччх ЧЧСУХ. Кажется, что этот знак весьма похож на употребление буквы С в русском тексте, как МАССА ССЫЛОК или ЛАССО ССУЧИЛ. Например, для буквы В не удается подобрать хороший пример, чтобы она удваивалась в конце слов, а для буквы Н - в начале. Отметим, что удвоение С в конце характерно для заимствованных существительных, где перед ним стоит чаще всего буква А. Значит, буква шифровки Ч соответствует в тексте С, а И соответствует русской букве А.Предположение 2.
Другое удвоение, знака о, встречается только в конце слов и типично для русской буквы Н. Поэтому сочетания знаков на концах слов шифровки ОЭ и ооэ, скорее всего отвечают русским окончаниям в сообщении НО и ННО. Если это так, то последнее слово шифровки ЧЧСУЖ, начинающееся с СС и состоящее из пяти букв может быть лишь одним из двух слов - ССУДЕ или ССУДЫ, что легко проверить по словарю. Другие варианты прочтения ССУДА, ССОРА и тому подобные отпадают, так как буквы А иО уже разгаданы.Предположение 3.
Знак шифровки ж, стоящий в конце слова ЧЧСУЖ встречается довольно редко, если учесть, что слово щиччж повторяется, а одинаковое окончание последнего и предпоследнего слов представляет собой обычное согласование слов в предложении. Это означает, что знаку ж скорее отвечает буква Ы, чем более часто встречаемая в русских текстах Е, а последнее слово - ССУДЫ. Окончание сообщения ?АССЫ ССУДЫ теперь нетрудно отгадать как КАССЫ ССУДЫ, что весьма близко к осмысленному тексту. Из отгаданных букв пятое слово шифровки складывается как АККУ?А?НО, что несомненно означает АККУРАТНО, а седьмое слово ??НОСЫ из контекста можно понять как ВЗНОСЫ. Итак, отгадывание идет вроде бы успешно, что подтверждается частичной расшифровкой:???Н КАССЫ ВЗА??0?0?0?? 0??ЗАН АККУРАТ- НО У??А??ВАТ? ???НСК?? ВЗНОСЫ ? СВО?ВР???ННО ВОЗВРА?АТ? ?0?У??ННЫ? ?3 КАССЫ ССУДЫ
Теперь дальнейшая расшифровка не представляет особого труда и выполняется быстро, угадыванием отдельных слов и подстановкой выясненных букв в шифровку. В итоге получаем сообщение:
ЧЛЕН КАССЫ ВЗАИМОПОМОЩИ ОБЯЗАН АККУРАТНО УПЛАЧИВАТЬ ЧЛЕНСКИЕ ВЗНОСЫ И СВОЕВРЕМЕННО ВОЗВРАЩАТЬ ПОЛУЧЕННЫЕ ИЗ КАССЫ ССУДЫ
Приведенный пример расшифровки не претендует на изящество, поскольку представляет собой реальный протокол рассуждений криптоаналитика без тупиковых вариантов, и показывает изнутри процесс вскрытия шифра простой замены. Возникает вопрос: насколько можно доверять правильности вскрытия этого шифра простой замены?
Лучше всего на него ответить словами Архимеда из послания к Эратосфену: "Хотя это всем вышеприведенным рассуждением и не доказано, но все же производит впечатление, что окончательный вывод верен". По ряду свидетельств, опытные криптоаналитики читают такие шифровки "с листа", потратив на это минуту-другую, что свидетельствует о профессиональном видении структуры текста в кажущейся мешанине букв. В этом они сильно превосходят ЭВМ, которая удовлетворительно читает шифр простой замены лишь при достаточно большой длине сообщения больше сотни символов. Однако и здесь ЭВМ может серьезно помочь в раскалывании шифра, например, разделив буквы на гласные и согласные. Так как гласные и согласные имеют тенденцию чередоваться, то можно по матрице чередований символов разделить их на эти классы (для этого на ЭВМ криптоаналитики традиционно используют так называемое сингулярное разложение матрицы переходных вероятностей.) . Кроме того, можно программно оценить вероятности принадлежности символов шифра разным буквам выписать их столбцами по убыванию вероятности, что даст другую технику вскрытия этого шифра. Применение распознавания, основанного на оценке лишь вероятностей отдельных символов в тексте и биграмм, за 10 этапов обучения дало по приведенной шифровке следующий текст:
ЧРЕН КАССЫ ВЗАИМОПОМОБИ ОДЯЭАН АККУЛАТНО УПРАЧИВАТЬ ЧРЕНСКИЕ ВЫНОСЫ И СВОЕВЛЕМЕННО ВОЗВЛАБАТЬ ПОРУЧЕННЫЕ ИЗ КАССЫ ССУШ
Получился довольно хорошо читаемый текст, хотя и за время, превысившее ручную расшифровку (эксперимент производился в 1991 году на машине IBM PC XT 6 MHz - как это было давно!)
После корректировки написания по словарю русского языка в Word 6.0 он приобрел такой вид:
ЧЛЕН КАССЫ ВЗАИМОПОМОЩИ ОБЯЗАН АККУРАТНО УПРОЧИВАТЬ ЧЛЕНСКИЕ ВЫНОСЫ И СВОЕВРЕМЕННО ВОЗВРАЩАТЬ ПОРУЧЕННЫЕ ИЗ КАССЫ ССУДЫ
Машинное вскрытие шифров простой замены вряд ли в близком будущем потеряет свою актуальность. Криптоаналитики широко им пользуются, поскольку атаки на сложные шифры заканчиваются обычно вскрытием шцфра простой замены.
Шифр Гронсфельда вскрывается довольно легко, если учесть следующее обстоятельство: так как цифр всего 10, то имеется лишь 10 вариантов прочтения каждой буквы. Выпишем их столбцами так, что одной строке соответствуют буквы одного значения ключа. Номер варианта будет определяться цифрой ключа от 0 до 9. При этом получим таблицу, правильно выбрав по одной букве из каждой колонки которой можно получить исходный текст:
ключ ??????????????????? вариант 0 ФПЖИСЬИОССАХИЛФИУСС вариант 1 УОЕЗРЫЗНРР ФЗКУЗТРР вариант 2 ТНДЖПЪЖМППЯУЖЙТЖСПП вариант 3 СМГЕОЩЕЛООЮТЕИСЕРОО вариант 4 РЛВДНШДКННЭСДЗРДПНН вариант 5 ПКБГМЧГЙММЬРГЖПГОММ вариант 6 ОЙАВЛЦВИЛЛЫПВЕОВНЛЛ вариант 7 НИ БКХБЗККЪОБДНБМКК вариант 8 МЗЯАЙФАЖЙЙЩНАГМАЛЙЙ вариант 9 ЛЖЮ ИУ ЕИИШМ ВЛ КИИ сообщение ???????????????????
Предположение 1.
Если прочесть исходный текст напрямую не удалось, то попробуем немного порассуждать. Самый частый символ текста - пробел, а разбиение фразы на слова порой может оказать большую помощь в расшифровке, как это уже было в случае вскрытия шифра решетки. Так как длина шифровки равна 19 символам, то она состоит из двух или трех слов, разделенных пробелами. Хорошее положение для пробела дает лишь вариант 1, а другие варианты, 7 и 9 или их сочетания маловероятны. Поэтому будем считать, что текст шифровки разбивается на два слова: ФПХИСЫЮСС ХИЛФИУСС. Из этого следует, что в 11 позиции текста стоит пробел и в той же позиции ключа находится цифра 1.Предположение 2.
У выделенных слов шифровки одинаковое окончание ее, и, весьма вероятно, что период ключа делит 9 - длину второго слова вместе с пробелом. Будем считать, что в этом случае одинаковые окончания слов (Одинаковые окончания часто появляются из-за согласования слов в предложениях на русском языке. Это хорошо видно в поговорках: одИН в поле не воИН, наняЛСЯ - продаЛСЯ.) текста попали на одинаковые участки ключа и дали одинаковые символы шифровки. На первый взгляд может показаться, что это слишком маловероятно, чтобы встречаться в практике. Однако таких находок, помогающих расшифровке, всегда бывает предостаточно в сообщениях большой длины и, порой, приходится жалеть скорее об их обилии, чем отсутствии. Если нет никаких идей о длине ключа, не беда - ее можно подобрать вслепую. Итак, есть два выбора для периода ключа: 3 и 9. Попробуем период длины 3:ключ ?1??1??1??1??1??1?? вариант 0 Ф ЖИ ЬИ СС ХИ ФИ СС вариант 1 УОЕЗРЫЗНРР ФЗКУЗТРР вариант 2 Т ДЖ ЪЖ ПП УЖ ТЖ ПП вариант 3 С ГЕ ЩЕ ОО ТЕ СЕ ОО вариант 4 Р БД ШД НН СД РД НН вариант 5 П БГ ЧГ ММ РГ ПГ ММ вариант 6 О АВ ЦБ ЛЛ ПВ ОВ ЛЛ вариант 7 Н Б ХБ КК ОБ НБ КК вариант 8 М ЯА ФА ЙЙ НА МА ЙЙ вариант 9 Л Ю У ИИ МЛ ИИ сообщение ?о??р??н?? ??к??т??
Таблица существенно поредела, но остается все-таки сложной для непосредственного прочтения (Криптоаналитики вряд ли сочтут прямое чтение ее сложным, так как достаточно перебрать лишь 100 вариантов для двух оставшихся цифр ключа вручную за несколько минут.). Поэтому попробуем подобрать символ ключа, стоящий в первой позиции, перебрав 10 вариантов. Так как ключ длиной 3 циклически повторяется, то этот же символ стоит в 4, 7, 10, 13, 16 и 19 позициях ключа. Вероятность варианта для первой цифры ключа равна произведению вероятностей биграмм, состоящих из символа по этому варианту расшифровки и следующего за ним, уже известного символа. Если Li - буква текста, стоящая на месте i, то вероятность одного из 10 вариантов:
р (L1L2) p(L4L5) р(L7L8) p(L10L11) p(L13L14) p(L16L17)
Для вычисления вероятности биграмм воспользуемся таблицей из приложения. Поскольку в ней даны логарифмы вероятностей биграмм, то их достаточно суммировать. В результате для вариантов от 0 до 3 имеем такие численные значения вероятностей:
р(0)=р(ФО)р(ИР)р(ИН)р(С )р(ИК)р(ИТ)=43 р(1)=р(УО)р(ЗР)р(ЗН)р(Р )р(ЗК)р(ЗТ)=23 р(2)=р(ТО)р(ЖР)р(ЖН)р(П )р(ЖК)р(ЖТ)=27 р(3)=р(СО)р(ЕР)р(ЕН)р(О )р(ЕК)р(ЕТ)=50
В результате для первой цифры ключа получается наиболее вероятным 3 вариант расшифровки. Это дает следующую таблицу:
ключ 31?31?31?31?31?31?3 вариант 0 Ж Ь С Х Ф С вариант 1 ОЕ РЫ HP Ф КУ ТР вариант 2 Д Ъ П У Т П вариант 3 С ГЕ ЩЕ ОО ТЕ С ОО вариант 4 в т н с р н вариант 5 Б Ч М Р П М вариант 6 А Ц Л П О Л вариант 7 Х К О Н К вариант 8 Я Ф Й Н М Й вариант 9 Ю У И М Л И сообщение СО?ЕР?ЕН?0 ?ЕК?РТ?0Теперь сообщение читается совсем просто. Достаточно выбрать одну из 10 строк с вариантом для 3 цифры ключа. В результате получим ключ и текст сообщения:
сообщение: СОВЕРШЕННО СЕКРЕТНО ключ: 3143143143143143143
В принципе есть возможность чтения шифра Гронсфельда напрямую, анализом таблицы возможных замен, даже если ключ длинный. При достаточно большой длине текста в таблице будут несложно прочитываемые участки. Использование ЭВМ для подключения к криптографической атаке на этот шифр априорных знаний о чередовании русских букв в тексте обычно позволяет без труда читать подобные шифровки.
При многоалфавитной замене с длинным ключом использованный для взлома шифра Гронсфельда прием уже не подходит. Однако известно, что шифры русских революционеров цифирная палата легко читала. Как же это удавалось сделать - черная магия? Все гораздо проще. Приведем короткий пример: перехвачена шифровка, вероятным автором которой является Троцкий. Известно также, что аналогичные шифровки делались методом сложной замены и в качестве ключа использовались тексты революционных песен, а иногда стихотворения Пушкина, Лермонтова и Некрасова. Так как отправитель Троцкий, то естественно предположить, что сообщение оканчивается подписью ТРОЦКИЙ с предыдущим пробелом. Подставив ее в шифровку вместо ключа, получим кусок настоящего ключа.
Шифровка ДДЯ Л ЫСЫ ШНМРКЮЮЩДБЬИЬМЫМТАНЭХЦК Сообщение ????????????????????????? ТРОЦКИЙ Ключ ?????????????????????????НАС ЗЛОБ
Не напоминает ли фрагмент НАС ЗЛОБ какойто известный текст? Не правда ли, очень похоже на слова, переведенной Кржижановским песни польского восстания 1863 года, называемой "Варшавянкой"? Теперь, подставив разгаданный ключ в виде текста песни: ВИХРИ ВРАЖДЕБНЫЕ ВЕЮТ НАД НАМИ ТЕМНЫЕ СИЛЫ НАС ЗЛОБ, можно вскpыть само сообщение:
ОБЫВАТЕЛИ СПАЛИ НЕ ЗНАЯ ЧТО МЕНЯЕТСЯ
ВЛАСТЬ ТРОЦКИЙ
Такая расшифровка вряд ли заняла бы вместе с составлением сопроводительной записки более часа времени. Ну, а предположим, что отправитель неизвестен? И это не беда, хотя потребует больше времени. Несложно перебрать несколько возможных имен, а в случае неудачи придется подставлять в разные места часто употребляемые слова текста и ключа - ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно из двух - текст или ключ, сразу получим второе. Вот как немцы описали вскрытие ручных шифров советской группы шпионов "Красная Капелла", полностью уничтожить которую Мюллер, Канарис и Шелленберг не смогли, несмотря на многие аресты ее участников с начала и до конца войны: "Тем временем математический отдел разведки и служба расшифровки Главного командования вермахта лихорадочно работала над найденным в особняке наполовину обуглившимся обрывком зашифрованного текста радиопередачи. Они пришли к выводу, что ключ к шифру находится в тексте какой-то французской книги (Язык сообщения и тип шифра стали известны после того, как арестованная бельгийская консьержка на допросах сообщила о пристрастии агентов "Красной Капеллы" к чтению французских романов, часть названий которых она вспомнила.). Из крошечного обрывка сожженного листка бумаги специалисты после кропотливых исследований сумели реконструировать слово ПРОКТОР. Теперь, следовало выяснить, в каких книгах встречается это ключевое слово. Через три месяца мы разыскали эту книгу. Тогда специалисты отдела расшифровки Главного командования вермахта принялись за работу, чтобы раскусить шифр. Они смогли расшифровать обнаруженные в Брюсселе и перехваченные заново радиопередачи."
Еще один короткий пример вскрытия многоалфавитного шифра замены приведем из-за его занимательной истории. Писатель Эдгар По считал себя непревзойденным криптоаналитиком. Ему принадлежит дерзкое высказывание: ".можно смело утверждать, что человеческий гений не в силах составить шифр, раскрыть который оказалось бы не под силу человеческому гению". Поэтому в 1839 году он бросил вызов читателям Журнала "Alexander's Weekly Messenger", утверждая, что расколет любой их шифр замены. Некто Калп в 1840 году прислал ему такой текст шифровки:
GE JEASGDXV, ZIJ GL MW, LAAM, XZY. . .
Эдгар По, предполагавший, что будет предложен шифр простой замены, счел пример Калпа "мешаниной случайных букв". Однако в 1975 году слушатели лекций по криптологии Винкель и Листер расшифровали его, предположив многоалфавитную замену вместо простой. Скорее всего они начали с первых двух слов, увидев в них искаженное имя получателя ALEXANDER как ALXANDER:
Шифpовка GE JEASGDXV Сообщение MR ALXANDER Ключ UN JTDSTATE
Полученная частная расшифровка была очень похожа на фразу UNITED STATES и, повторяя ее циклически, они вскрыли весь текст шифровки. Стало ясно, что даже если бы дилетант По и знал о многоалфавитных шифрах, то взламывание текста-шифровки Калпа представляло собой серьезную задачу: одна буква в шифровке была пропущена, а 15 искажены скорее всего по вине наборщика. Этот пример показывает, что ошибки в шифровании способны озадачить не только криптоаналитика, но и легального получателя сообщения, обладающего ключом. Ведь из-за пропущенной пятой буквы текста шифровки весь ее остаток был нечитаемым!
Машинные шифры в принципе много сложнее ручных и их раскалывание скорее напоминает не подбор отмычки к сейфу, а высверливание его механизма. Тем не менее, если силу прикладывать неразумно, то вряд ли можно будет добиться успеха. Рассмотрим лишь простенький древний машинный шифр. Одна из первых систем шифрования опробовалась в начале XX века на телеграфе. Она основывалась на том, что каждый символ кодировался 5 импульсами тока, а это вполне соответствует пяти битам представления этого кода в ЭВМ. Смысл шифра состоял в перестановке этих импульсов или, соответственно, бит по сложному закону с большим периодом. В частности от двоичного счетчика с n разрядами поступало n сигналов на релейные схемы, меняющие местами 2 бита. Так как n было велико, то такие перестановки пар бит, называемые математиками транспозициями, могли в принципе дать любую перестановку бит внутри кода символа. Однако если все биты равны нулю или единице, то, как их не переставляй, их совокупность не изменится. Если не все биты равны между собой, то может произойти замена символа. Число вариантов замены зависит от числа нулевых бит в коде символа:
число нулевых бит 0 1 2 3 4 5 число единичных бит 5 4 3 2 1 0 число вариантов 1 5 10 10 5 1
Предположим, что буква А кодируется 00000, Б как 00001 и так далее до Я - 11111. В этом случае букве А при любых перестановках бит будет соответствовать только она сама. Букве Б могут соответствовать уже 5 вариантов: Б(00001), В(00010), Д(00100), И(01000), Р(10000). Поэтому, написав под каждой буквой шифровки все буквы сообщения, которые возможно ей соответствуют, получим таблицу, содержащую все варианты прочтения шифровки. Для того, чтобы облегчить чтение, варианты расшифровки каждой буквы в таблице расположены сверху вниз в порядке убывания их вероятности, что выполнено на ЭВМ с учетом априорной информации о чередовании букв в тексте на естественном языке. В верхней строке таблицы дан исходный текст сообщения, а во второй - шифровка, полученная случайной перестановкой бит у каждой буквы. Далее приведены альтернативные варианты прочтения букв. Причем, чем ниже приведен вариант, тем менее он правдоподобен, а варианты с вероятностью прочтения ниже 0.05 отброшены. Программа на ЭВМ попыталась найти и наиболее вероятное прочтение шифровки используя для этого данные о вероятностях биграмм текста на русском языке. Предложенный ей вариант прочтения букв выделен жирными символами:
ЖИЛИ БЫЛИ СТАРИК СО СТАРУХОЙ текст МДЩВ БЮХД ЕСАВРЖ ЕЛ ЕКАДЦНЬТ шифр СИНИ ВЫхИ СТАВИЕ Сл СТАВОЛьг 1 мров бчЛв мк брм мО мк блзОИ 2 ...дальше нет вариантов... СИНИ ВЫЛИ СТАВИЕ СО СТАВОЛОЙ прочтение
Несмотря на немного смешной вид полученного текста, он довольно-таки близок к оригиналу: отгадано 19 букв из 28! Некоторое улучшение отгадывания может быть достигнуто переходом к оценке вероятностей не по биграммам, а по триграммам - трехбуквенным сочетаниям и даже полному словарю слов. Применение в программе полного словаря дало вариант расшифровки: ЖИЛИ БЫЛИ СТАРИК СО СТАРУХОЙ. Однако вряд ли кто лучше человека сможет выбрать окончательный вариант прочтения. Из этого примера следует важный вывод, что избыточность языка позволяет читать сообщение даже при большой неоднозначности прочтения каждой отдельно взятой буквы. В приведенном примере на одну букву в среднем приходится 7 вариантов ее прочтения. Практически, если число вариантов прочтения каждой буквы не больше 7, то текст обычно прочесть удается.
Попробуем теперь сделать выводы из рассмотренных примеров: что помогает и что мешает раскалыванию шифров. Помогает криптографической атаке на шифр в основном то обстоятельство, что буквы и слова в тексте взаимосвязаны. Так, например, было несложно отгадать слово АККУ?А?НО и даже по фрагменту НАС ЗЛОБ определить песню, откуда он взят. Такая внутренняя зависимость участков текста друг от друга - свойство естественного языка и от него никуда не денешься. Хотя были и есть языки с гораздо меньшей зависимостью, чем у русского языка, но не заставишь же их использовать для того, чтобы решить проблемы шифрования. Другой помощник криптоаналитика - малое число вариантов соответствия текста шифровке при незнании ключа. Так в шифре Гронсфельда букве шифровки могут соответствовать лишь 10 букв из текста, а в шифре перестановки бит и того меньше, в среднем 7. Способствует вскрытию шифра и малая длина ключа - вряд ли так легко мы разделались бы с шифром Гронсфельда, если длина ключа превышала длину сообщения. И, в конце концов, почему же так просто был вскрыт многоалфавитный шифр замены? Ведь у него и число вариантов для отгадывания было велико, и ключ длинный. Причина успеха его взлома заключается в сильной зависимости ключа, текста и шифровки меж собой. Шифровка известна всегда. Поэтому сначала, мы угадали кусок текста и сразу же за это в награду получили кусок ключа. По этому куску ключа удалось восстановить весь ключ целиком.
Итак, во-первых, если кусок-ключа можно было получить, отгадав лишь очень большую часть текста или перебрав множество вариантов, то этот номер не прошел бы. Во-вторых, это не дело, когда по малому участку ключа удается угадать весь ключ. Будь ключ представлен не осмысленным текстом, а случайным, то этого не удалось бы. Во всех современных системах шифрования открытый текст обязательно сжимается перед шифрованием. Сжимать шифрованный текст слишком поздно, так как шифровки почти несжимаемы. Кроме экономии места под хранение и времени передачи, сжатие еще и повышает стойкость шифра. Многие атаки на шифр осуществляются поиском фрагмента открытого текста в шифровке. Если отрытый текст перед шифрованием был сжат, то эти атаки затруднены и потери времени на сжатие окупаются. Теперь давайте пофантазируем, как составить нераскрываемый шифр. Если мы возьмем за основу многоалфавитный шифр замены, то это будет неплохой выбор, он многовариантен и к нему так просто не подступишься. Однако ключ для шифровки должен быть очень хорош: бесконечной длины и, конечно же, несмысловой. Можно схитрить и составить ключ из текста, беря из него лишь каждую третью букву, ведь по фрагменту ДНВТДМИН никогда не скажешь, что он взят из той же "Варшавянки". Еще лучше, если сообщение зашифровано дважды разными ключами и шифрами разных типов. Далее, скверно, когда символы всегда находятся в том же месте в шифровке, что и в сообщении - на подпись, заголовок или другой известный фрагмент текста может начаться атака. Поэтому вместе с заменой применим простой шифр двойной перестановки - пусть взломщики поищут, где теперь находится подпись. Таким способом, комбинируя шифр перестановки с многоалфавигным шифром замены при хорошем ключе, можно получить вполне приемлемый ручной шифр, вскрыть который будет очень непросто или вообще невозможно.
Но сменим галоп нашего рассуждения на шаг, чтобы предостеречь читателя от одной широко распространенной ошибки. Насколько осложнится вскрытие сообщения, если его зашифровать несколько раз одним ключом? Ответ естественный, хотя для многих и неожиданный, взломка сложнее вряд ли станет. Во времена Второй мировой войны английским криптографам не давал покоя простой, но заковыристый немецкий полицейский шифр. Из-за краткости сообщений его чтение удавалось далеко не всегда и, как правило, с большими трудностями. Немецкие криптографы об этом не знали, решив улучшить шифр, как бы удвоив примененный ключ. Так вот, после такого "усложнения" вскрытие шифровок стало легким и приятным. В известном автору аналогичном случае, имевшем место некогда в известной фирме, текст был зашифрован дважды. Шифровка криптоаналитиком была восстановлена из свободных кластеров на рабочей дискете, а в директории остались следы от двойного шифрования и длины двух файлов типа ВАК того же сообщения. Из этих следов и сопоставления длин шифровки с длинами файлов стало ясно, что текст зашифрован дважды. По заголовку файла была определена программа шифрования. Так как во второй раз был зашифрован и текст сообщения, и заголовок файла шифровки, содержание которого отчасти известно, то найти второй ключ удалось просто подбором, потому что он был всего из 5 букв по имени владельца. Первый ключ был угадан после этого сразу же, так как стало ясно пристрастие автора файла к собственному имени. Вследствие этого, примите за правило никогда не шифровать одно сообщение дважды одним и тем же ключом, чтобы не усложнять себе жизнь лишней работой. Применение нескольких разных ключей порой оправдано, если не из-за увеличения стойкости шифра, то хотя бы как свидетельство о согласии нескольких отправителей шифровки или одновременном присутствии нужных получателей сообщения.
Лучшие известные криптографические системы, преимущественно принадлежащие правительствам, практически невозможно вскрыть. Однако все государства теми или иными путями пытаются сдержать и даже запретить свободное использование криптографии, как вызывающее головную боль у их секретных служб. В то время, как ЦРУ в США призывает фирмы шире использовать шифрование, то АНБ пытается ограничить длину ключа 40 битами. В последнем случае возможен даже прямой перебор ключей, если использовать достаточно мощную ЭВМ. По оценкам специалистов, раскалывание шифра алгоритма RC-4 с ключом из 40 бит, широко используемого в сети Internet, потребует около 100 MIPS (MIPS - million instructions per second - миллион операций в секунду.) лет. Раньше считалось, что меньше, чем за 6 месяцев работы суперкомпьютера, такой шифр вскрыт не будет. Эта оценка была проверена практически и оказалось, что 120 рабочих станций с двумя суперкомпьютерами параллельного действия взломали ключ за, 8 дней. Цена такого раскалывания достаточно высока и превышает $10000, что впрочем сильно зависит от эффективности алгоритма атаки. Поэтому проблемы криптоанализа еще долгое время будут весьма актуальны.
