181
Федеральное агентство по образованию
Сибирский государственный аэрокосмический университет
имени академика М.Ф. Решетнева
О. Н. Жданов,
И. А. Куденкова
Криптоанализ классических шифров
Лабораторный практикум для студентов, обучающихся по специальностям «Комплексное обеспечение информационной безопасности автоматизированных систем» и «Информационная безопасность телекоммуникационных систем»
Красноярск 2008
Оглавление
Введение
I. Классические шифры
II. Советы по выполнению частотного анализа английских текстов
III. Задания на криптоанализ классических шифров
3.1 Шифр столбцовой перестановки
3.2 Шифр двойной перестановки
3.3 Шифр простой замены
3.4 Шифр Виженера
Библиографический список
Введение
Курс «Криптографические методы защиты информации» является базовым при подготовке специалистов по защите информации. На основе знаний криптографии выстраивается система подготовки специалистов. При этом изучение методов защиты неразрывно связано с изучением возможных атак на алгоритмы и на их реализации. Хорошо известно, что для усвоения материала необходима активная самостоятельная работа студентов. Поэтому представляется целесообразным проведение лабораторных работ по криптоанализу. Работы по анализу таких шифров, как DES, ГОСТ 28147-89, IDEA требуют большого ресурса и для начинающего являются чрезвычайно сложными. В то же время на примерах классических шифров можно проиллюстрировать некоторые важные приемы и методы криптоанализа. Как показывает практика работы, студенты после анализа шифров перестановки, простой замены и Виженера уверенно и достаточно быстро входят в круг идей современной криптографии. Таким образом, настоящее пособие выполняет пропедевтическую функцию. После анализа классических шифров учащиеся успешно изучают современные блочные алгоритмы шифрования, им становятся доступными идеи линейного и дифференциального криптоанализа.
Авторы сочли необходимым теоретические сведения дополнить подробно изложенными примерами выполнения заданий. После изучения теории и ознакомления с образцами решений заданий студент должен выполнить свой вариант лабораторной работы. Мы не приводим ответы к задачам, дабы не лишать обучающихся удовольствия от самостоятельного решения. Заинтересовавшиеся коллеги могут получить ответы по адресу: onzhdanov@mail.ru.
I. Классические шифры
Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются шифрами.
Шифрование (зашифрование) -- процесс применения шифра к защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, криптограмму) с помощью определенных правил, содержащихся в шифре.
Дешифрование -- процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре.
Криптография -- прикладная наука, она использует самые последние достижения фундаментальных наук и, в первую очередь, математики. С другой стороны, все конкретные задачи криптографии существенно зависят от уровня развития техники и технологии, от применяемых средств связи и способов передачи информации.
Современная криптография является областью знаний, связанной с решением таких проблем безопасности информации, как конфиденциальность, целостность, аутентификация и невозможность отказа сторон от авторства. Достижение этих требований безопасности информационного взаимодействия и составляет основные цели криптографии. Они определяются следующим образом.
Обеспечение конфиденциальности -- решение проблемы защиты информации от ознакомления с ее содержанием со стороны лиц, не имеющих права доступа к ней. В зависимости от контекста вместо термина "конфиденциальная" информация могут выступать термины "секретная", "частная", "ограниченного доступа" информация.
Обеспечение целостности -- гарантирование невозможности несанкционированного изменения информации. Для гарантии целостности необходим простой и надежный критерий обнаружения любых манипуляций с данными. Манипуляции с данными включают вставку, удаление и замену.
Обеспечение аутентификации -- разработка методов подтверждения подлинности сторон (идентификация) и самой информации в процессе информационного взаимодействия. Информация, передаваемая по каналу связи, должна быть аутентифицирована по источнику, времени создания, содержанию данных, времени пересылки и т. д.
Обеспечение невозможности отказа от авторства -- предотвращение возможности отказа субъектов от некоторых из совершенных ими действий. Рассмотрим средства для достижения этих целей более подробно.
Традиционной задачей криптографии является проблема обеспечения конфиденциальности информации при передаче сообщений по контролируемому противником каналу связи. В простейшем случае эта задача описывается взаимодействием трех субъектов (сторон). Владелец информации, называемый обычно отправителем, осуществляет преобразование исходной (открытой) информации (сам процесс преобразования называется шифрованием) в форму передаваемых получателюпо открытому каналу связи шифрованных сообщений с целью ее защиты от противника.
Под противником понимается любой субъект, не имеющий права ознакомления с содержанием передаваемой информации. В качестве противника может выступать криптоаналитик, владеющий методами раскрытия шифров. Законный получатель информации осуществляет расшифрование полученных сообщений. Противник пытается овладеть защищаемой информацией (его действия обычно называют атаками). При этом он может совершать как пассивные, так и активные действия. Пассивные атаки связаны с прослушиванием, анализом трафика, перехватом, записью передаваемых шифрованных сообщений, дешифрованием, то есть попытками "взломать" защиту с целью овладения информацией.
При проведении активных атак противник может прерывать процесс передачи сообщений, создавать поддельные (сфабрикованные) или модифицировать передаваемые шифрованные сообщения. Эти активные действия называют попытками имитации и подмены соответственно.
Под шифром обычно понимается семейство обратимых преобразований, каждое из которых определяется некоторым параметром, называемым ключом, а также порядком применения данного преобразования, называемым режимом шифрования.
Ключ -- это важнейший компонент шифра, отвечающий за выбор преобразования, применяемого для зашифрования конкретного сообщения. Обычно ключ представляет собой некоторую буквенную или числовую последовательность. Эта последовательность как бы "настраивает" алгоритм шифрования.
Каждое преобразование однозначно определяется ключом и описывается некоторым криптографическим алгоритмом. Один и тот же криптографический алгоритм может применяться для шифрования в различных режимах. Тем самым реализуются различные способы шифрования (простая замена, гаммирование и т. п.). Каждый режим шифрования имеет как свои преимущества, так и недостатки. Поэтому выбор режима зависит от конкретной ситуации. При расшифровании используется криптографический алгоритм, который в общем случае может отличаться от алгоритма, применяемого для зашифрования сообщения. Соответственно могут различаться ключи зашифрования и расшифрования. Пару алгоритмов зашифрования и расшифрования обычно называют криптосистемой (шифрсистемой), а реализующие их устройства -- шифртехникой.
Если обозначить через М открытое, а через С шифрованное сообщения, то процессы зашифрования и расшифрования можно записать в виде равенств
Ek1(M)=C
Dk2(C)=M
в которых алгоритмы зашифрования Е и расшифрования D должны удовлетворять равенству
Dk2(Ek1(M))=M
Наряду с конфиденциальностью не менее важной задачей является обеспечение целостности информации, другими словами, -- неизменности ее в процессе передачи или хранении. Решение этой задачи предполагает разработку средств, позволяющих обнаруживать не столько случайные искажения (для этой цели вполне подходят методы теории кодирования с обнаружением и исправлением ошибок), сколько целенаправленное навязывание противником ложной информации. Для этого в передаваемую информацию вносится избыточность. Как правило, это достигается добавлением к сообщению некоторой проверочной комбинации, вычисляемой с помощью специального алгоритма и играющей роль контрольной суммы для проверки целостности полученного сообщения. Главное отличие такого метода от методов теории кодирования состоит в том, что алгоритм выработки проверочной комбинации является "криптографическим", то есть зависящим от секретного ключа. Без знания секретного ключа вероятность успешного навязывания противником искаженной или ложной информации мала. Такая вероятность служит мерой имитостойкости шифра, то есть способности самого шифра противостоять активным атакам со стороны противника.
Итак, для проверки целостности к сообщению М добавляется проверочная комбинация S, называемая кодом аутентификации сообщения (сокращенно -- КАС) или имитовставкой. В этом случае по каналу связи передается пара С = (М, S). При получении сообщения М пользователь вычисляет значение проверочной комбинации и сравнивает его с полученным контрольным значением S Несовпадение говорит о том, что данные были изменены.
Как правило, код аутентификации является значением некоторой (зависящей от секретного ключа) криптографической хеш-функции от данного сообщения: hk(M) = S К кодам аутентификации предъявляются определенные требования. К ним относятся:
-- невозможность вычисления значения hk(M) = S для заданного сообщения М без знания ключа k,
-- невозможность подбора для заданного сообщения М с известным значением hk(M)=S другого сообщения М1 с известным значением hk (М1) = S1, без знания ключа k.
Первое требование направлено против создания поддельных (сфабрикованных) сообщений при атаках типа имитация; второе -- против модификации передаваемых сообщений при атаках типа подмена.
Аутентификация -- установление подлинности. В общем случае этот термин может относиться ко всем аспектам информационного взаимодействия: сеансу связи, сторонам, передаваемым сообщениям и т. д.
Установление подлинности (то есть проверка и подтверждение) всех аспектов информационного взаимодействия является важной составной частью проблемы обеспечения достоверности получаемой информации. Особенно остро эта проблема стоит в случае не доверяющих друг другу сторон, когда источником угроз может служить не только третья сторона (противник), но и сторона, с которой осуществляется взаимодействие.
Применительно к сеансу связи аутентификация означает проверку: целостности соединения, невозможности повторной передачи данных противником и своевременности передачи данных. Для этого, как правило, используют дополнительные параметры, позволяющие "сцепить" передаваемые данные в легко проверяемую последовательность. Это достигается, например, путем вставки в сообщения некоторых специальных чисел или меток времени. Они позволяют предотвратить попытки повторной передачи, изменения порядка следования или обратной отсылки части переданных сообщений. При этом такие вставки в передаваемом сообщении необходимо защищать (например, с помощью шифрования) от возможных подделок и искажений.
Применительно к сторонам взаимодействия аутентификация означает проверку одной из сторон того, что взаимодействующая с ней сторона -- именно та, за которую она себя выдает. Часто аутентификацию сторон называют также идентификацией.
Основным средством для проведения идентификации являются протоколы идентификации, позволяющие осуществлять идентификацию (и аутентификацию) каждой из участвующих во взаимодействии и не доверяющих друг другу сторон. Различают протоколы односторонней и взаимной идентификации.
Протокол -- это распределенный алгоритм, определяющий последовательность действий каждой из сторон. В процессе выполнения протокола идентификации каждая из сторон не передает никакой информации о своем секретном ключе, а хранит его у себя и использует для формирования ответных сообщений на запросы, поступающие при выполнении протокола.
Наконец, применительно к самой информации аутентификация означает проверку того, что информация, передаваемая по каналу, является подлинной по содержанию, источнику, времени создания, времени пересылки и т. д.
Проверка подлинности содержания информации сводится, по сути, к проверке ее неизменности (с момента создания) в процессе передачи или хранения, то есть проверке целостности.
Аутентификация источника данных означает подтверждение того, что исходный документ был создан именно заявленным источником.
Заметим, что если стороны доверяют друг другу и обладают общим секретным ключом, то аутентификацию сторон можно обеспечить применением кода аутентификации. Действительно, каждое успешно декодированное получателем сообщение может быть создано только отправителем, так как только он знает их общий секретный ключ. Для не доверяющих друг другу сторон решение подобных задач с использованием общего секретного ключа становится невозможным. Поэтому при аутентификации источника данных нужен механизм цифровой подписи, который будет рассмотрен ниже.
В целом, аутентификация источника данных выполняет ту же роль, что и протокол идентификации. Отличие заключается только в том, что в первом случае имеется некоторая передаваемая информация, авторство которой требуется установить, а во втором требуется просто установить сторону, с шторой осуществляется взаимодействие.
Математические модели открытого текста
Потребность в математических моделях открытого текста продиктована, прежде всего, следующими соображениями. Во-первых, даже при отсутствии ограничений на временные и материальные затраты по выявлению закономерностей, имеющих место в открытых текстах, нельзя гарантировать того, что такие свойства указаны с достаточной полнотой. Например, хорошо известно, что частотные свойства текстов в значительной степени зависят от их характера. Поэтому при математических исследованиях свойств шифров прибегают к упрощающему моделированию, в частности, реальный открытый текст заменяется его моделью, отражающей наиболее важные его свойства. Во-вторых, при автоматизации методов криптоанализа, связанных с перебором ключей, требуется "научить" ЭВМ отличать открытый текст от случайной последовательности знаков. Ясно, что соответствующий критерий может выявить лишь адекватность последовательности знаков некоторой модели открытого текста.
Один из естественных подходов к моделированию открытых текстов связан с учетом их частотных характеристик, приближения для которых можно вычислить с нужной точностью, исследуя тексты достаточной длины. Основанием для такого подхода является устойчивость частот к -грамм или целых словоформ реальных языков человеческого общения (то есть отдельных букв, слогов, слов и некоторых словосочетаний). Основанием для построения модели может служить также и теоретико-информационный подход, развитый в работах К. Шеннона.
Учет частот k-грамм приводит к следующей модели открытого текста. Пусть Р(k)(А) представляет собой массив, состоящий из приближений для вероятностей р(b1,b2,...,bk) появления k-грамм b1bг...bk в открытом тексте, kN,
А = (а1 ,...,ап) -- алфавит открытого текста, biA, i = 1,k.
Тогда источник "открытого текста" генерирует последовательность с1,с2,...,сk,сk+1,... знаков алфавита А, в которой k-грамма с1с2...сk появляется с вероятностью р(с1с2...сk) е Р(k)(А), следующая k-грамма с1с2...сk+1 появляется с вероятность р(с2с3...сk+1)Р(k)(А) и т. д. Назовем построенную модель открытого текста вероятностной моделью k-го приближения.
Таким образом, простейшая модель открытого текста -вероятностная модель первого приближения - представляет собой последовательность знаков с1,с2,..., в которой каждый знак ci, i = 1,2,..., появляется с вероятностью р(сi)P(1)(A), независимо от других знаков. Будем называть также эту модель позначной моделью открытого текста. В такой модели открытый текст с1с2...с1 имеет вероятность
.
В вероятностной модели второго приближения первый знак с1 имеет вероятность р(с1)P(1)(A), а каждый следующий знак сi зависит от предыдущего и появляется с вероятностью
,
где р(сi-1сi) Р(2)(А), р(сi-1)Р(1)(A), i = 2,3,.... Другими словами, модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст с1с2...сl имеет вероятность
.
Модели открытого текста более высоких приближений учитывают зависимость каждого знака от большего числа предыдущих знаков. Ясно, что чем выше степень приближения, тем более "читаемыми" являются соответствующие модели. Проводились эксперименты по моделированию открытых текстов с помощью ЭВМ.
Отметим, что с более общих позиций открытый текст может рассматриваться как реализация стационарного эргодического случайного процесса с дискретным временем и конечным числом состояний.
Критерии распознавания открытого текста
Заменив реальный открытый текст его моделью, мы можем теперь построить критерий распознавания открытого текста. При этом можно воспользоваться либо стандартными методами различения статистических гипотез, либо наличием в открытых текстах некоторых запретов, таких, например, как биграмма ЪЪ в русском тексте. Проиллюстрируем первый подход при распознавании позначной модели открытого текста.
Итак, согласно нашей договоренности, открытый текст представляет собой реализацию независимых испытаний случайной величины, значениями которой являются буквы алфавита А = {а1,...,ап}, появляющиеся в соответствии с распределением вероятностей Р(1)(А) = (р(а1),...,р(ап)). Требуется определить, является ли случайная последовательность с1с2...сl букв алфавита А открытым текстом или нет.
Пусть Н0 -- гипотеза, состоящая в том, что данная последовательность -- открытый текст, Н1 -- альтернативная гипотеза. В простейшем случае последовательность c1c2...cl можно рассматривать при гипотезе Н1 как случайную и равновероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается "бессмысленная" последовательность знаков. В более общем случае можно считать, что при гипотезе Н1 последовательность c1c2...cl представляет собой реализацию независимых испытаний некоторой случайной величины, значениями которой являются буквы алфавита А = {а1,...,ап}, появляющиеся в соответствии с распределением вероятностей Q(1)(A)= (q(al),...,q(an)). При таких договоренностях можно применить, например, наиболее мощный критерий различения двух простых гипотез, который дает лемма Неймана--Пирсона.
В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может принять открытый текст за случайный набор знаков. Такая ошибка обычно называется ошибкой первого рода, ее вероятность равна = p{H1/H0}. Аналогично вводится ошибка второго рода и ее вероятность = p{Н0/Н1} . Эти ошибки определяют качество работы критерия. В криптографических исследованиях естественно минимизировать вероятность ошибки первого рода, чтобы не "пропустить" открытый текст. Лемма Неймана--Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.
Критерии на открытый текст, использующие запретные сочетания знаков, например к -граммы подряд идущих букв, будем называть критериями запретных k-грамм. Они устроены чрезвычайно просто. Отбирается некоторое число s редких k-грамм, которые объявляются запретными. Теперь, просматривая последовательно k-грамму за k-граммой анализируемой последовательности c1c2...cl, мы объявляем ее случайной, как только в ней встретится одна из запретных k-грамм, и открытым текстом в противном случае. Такие критерии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных k-грамм являются весьма эффективными.
Классификация шифров
В качестве первичного признака, по которому производится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены. Если буквы открытого текста при шифровании лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки. С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра. Всевозможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами. Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки (рис. 1).
181
Рисунок 1. Классификация шифров
Шифры перестановки
Шифры перестановки, или транспозиции, изменяют только порядок следования символов или других элементов исходного текста. Классическим примером такого шифра является система, использующая карточку с отверстиями - решетку Кардано, которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. При зашифровке буквы сообщения вписываются в эти отверстия. При расшифровке сообщение вписывается в диаграмму нужных размеров, затем накладывается решетка, после чего на виду оказываются только буквы открытого текста.
Решетки можно использовать двумя различными способами. В первом случае зашифрованный текст состоит только из букв исходного сообщения. Решетка изготавливается таким образом, чтобы при ее последовательном использовании в различных положениях каждая клетка лежащего под ней листа бумаги оказалась занятой. Примером такой решетки является поворотная решетка, показанная на рис.1. Если такую решетку последовательно поворачивать на 90° после заполнения всех открытых при данном положении клеток, то при возврате решетки в исходное положение все клетки окажутся заполненными. Числа, стоящие в клетках, облегчают изготовление решетки. В каждом из концентрических окаймлений должна быть вырезана только одна клетка из тех, которые имеют одинаковый номер. Второй, стеганографический метод использования решетки позволяет скрыть факт передачи секретного сообщения. В этом случае заполняется только часть листа бумаги, лежащего под решеткой, после чего буквы или слова исходного текста окружаются ложным текстом.
|
1 |
2 |
3 |
4 |
5 |
1 |
|
|
5 |
1 |
2 |
3 |
1 |
2 |
|
|
4 |
3 |
1 |
1 |
2 |
3 |
|
|
3 |
2 |
1 |
1 |
3 |
4 |
|
|
2 |
1 |
3 |
2 |
1 |
5 |
|
|
1 |
5 |
4 |
3 |
2 |
1 |
|
Рисунок 2. Пример поворотной решетки
Рассмотрим усложненную перестановку по таблице. Пример таблицы для реализации этого метода шифрования показан на рис.3. Таблица представляет собой матрицу размерностью 6 х 6, в которую построчно вписывается искомое сообщение. При считывании информации по столбцам в соответствии с последовательностью чисел ключа получается шифротекст. Усложнение заключается в том, что некоторые ячейки таблицы не используются. При зашифровании сообщения
КОМАНДОВАТЬ ПАРАДОМ БУДУ Я
получим:
ОЬБНАОДКДМУМВ АУ ОТР ААПДЯ,
|
Ключ |
||||||
|
2 |
4 |
0 |
3 |
5 |
1 |
|
|
К |
О |
М |
А |
Н |
||
|
Д |
О |
В |
А |
|||
|
Т |
Ь |
П |
А |
|||
|
Р |
А |
Д |
О |
|||
|
М |
Б |
У |
Д |
|||
|
У |
Я |
|||||
Рисунок 3. Пример шифрования методом усложненной перестановки по таблице
При расшифровании буквы шифротекста записываются по столбцам в соответствии с последовательностью чисел ключа, после чего исходный текст считывается по строкам. Для удобства запоминания ключа применяют перестановку столбцов таблицы по ключевому слову или фразе, всем символам которых ставятся в соответствие номера, определяемые порядком соответствующих букв в алфавите. Например, при выборе в качестве ключа слова ИНГОДА последовательность использования столбцов будет иметь вид 462531.
Также возможны и другие варианты шифра перестановки, например, шифры столбцовой и двойной перестановки.
Шифры замены
Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона «Математическая теория связи» (см. приложение).
В своей работе «Теория связи в секретных системах» Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.
Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y - два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X --> Y -- взаимнооднозначное отображение Х в Y. Тогда шифр замены действует так: открытый текст х1х2...хп преобразуется в шифрованный текст g(x1)g(x2)... g(хп).
Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и у -- взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х1...хп преобразуется в отрезок шифрованного текста
Математическая модель шифра замены
Определим модель А =(X,K,Y,E,D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: XA*, YВ*, |А|=п, |В| = т . Здесь и далее С* обозначает множество слов конечной длины в алфавите С.
Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А * и В * соответственно.
Пусть U = {u1,..,иN} -- множество возможных шифрвеличин, V = {v1,...,vM} -- множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты хX, yY можно было представить словами из U*, V * соответственно. Требование однозначности расшифрования влечет неравенства Nп, Мт, МN. Для определения правила зашифрования Еk(х) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.
Поскольку МN, множество V можно представить в виде объединения непересекающихся непустых подмножеств V(i). Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V :
,
и соответствующее семейство биекций
для которых .
Рассмотрим также произвольное отображение где , такое, что для любых
Назовем последовательность (к,1) распределителем, отвечающим данным значениям кK, lN.
Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть
xX, x = x1...xl, xiU, i = 1,l; kK
и (к,I) = а1(k)...а1(k). Тогда Ек(х) = у, где у = у1...уl,
В качестве уj можно выбрать любой элемент множества т . Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как при ij.
Классификация шифров замены
Если ключ зашифрования совпадает с ключом расшифрования: k3 = kp, то такие шифры называют симметричными, если же k3kр -- асимметричными.
В связи с указанным различием в использовании ключей сделаем еще один шаг в классификации:
181
Отметим также, что в приведенном определении правило зашифрования Еk(х) является, вообще говоря, многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Еk(х) не слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров замены на однозначные и многозначные замены (называемых также в литературе омофонами).
Для однозначных шифров замены справедливо свойство:
для многозначных шифров замены:
181
Исторически известный шифр -- пропорциональной замены представляет собой пример шифра многозначной замены, шифр гаммирования - пример шифра однозначной замены. Далее мы будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. Итак, далее М = N и .
Заметим, что правило зашифрования Еk естественным образом индуцирует отображение , которое в свою очередь продолжается до отображения . Для упрощения записи будем использовать одно обозначение Еk для каждого из трех указанных отображений.
В силу инъективности (по k) отображения Еk и того, что |U| = |V|, введенные в общем случае отображения являются биекциями , определенными равенствами
.
Число таких биекций не превосходит N!.
Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле включение следует заменить равенством
Введем еще ряд определений.
Если для некоторого числа qN выполняются включения viВq, i=1,N, то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае -- шифром разнозначной замены:
181
В подавляющем большинстве случаев используются шифры замены, для которых UАр, для некоторого рN . При р = 1 говорят о поточных шифрах замены, при р > 1 -- о блочных шифрах замены:
181
Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае - многоалфавитным шифром замены:
181
Ограничиваясь наиболее важными классами шифров замены и исторически известными классами шифров перестановки, сведем результаты классификации в схему, изображенную на рисунке.
181
Следует подчеркнуть, что стрелки, выходящие из любого прямоугольника схемы, указывают лишь на наиболее значимые частные подклассы шифров. Пунктирные стрелки, ведущие из подклассов шифров перестановки, означают, что эти шифры можно рассматривать и как блочные шифры замены в соответствии с тем, что открытый текст делится при шифровании на блоки фиксированной длины, в каждом из которых производится некоторая перестановка букв. Одноалфавитные и многоалфавитные шифры могут быть как поточными, так и блочными. В то же время шифры гаммирования, образующие подкласс многоалфавитных шифров, относятся к поточным, а не к блочным шифрам. Кроме того, они являются симметричными, а не асимметричными шифрами.
Шифр Виженера
Наиболее известными являются шифры замены, или подстановки, особенностью которых является замена символов (или слов, или других частей сообщения) открытого текста соответствующими символами, принадлежащими алфавиту шифротекста. Различают одноалфавитную и многоалфавитную замену. Вскрытие одноалфавитных шифров основано на учете частоты появления отдельных букв или их сочетаний (биграмм, триграмм и т. п.) в данном языке. Классические примеры вскрытия таких шифров содержатся в рассказах Э. По "Золотой жук" и А.Конан Дойля "Пляшущие человечки".
Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью п X n, где п - число символов используемого алфавита. На рис.4 показана таблица Виженера для русского языка (алфавит Z32- 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на символ влево.
Рисунок 4. Таблица Виженера для алфавита Z32
Выбирается ключ или ключевая фраза. После чего процесс зашифрования осуществляется следующим образом. Под каждой буквой исходного сообщения последовательно записываются буквы ключа; если ключ оказался короче сообщения, его используют несколько раз. Каждая буква шифротекста находится на пересечении столбца таблицы, определяемого буквой открытого текста, и строки, определяемой буквой ключа. Пусть, например, требуется зашифровать сообщение:
ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ТЧК БРАТЬЯ КАРАМАЗОВЫ ТЧК
С помощью ключа ВЕНТИЛЬ запишем строку исходного текста с расположенной под ней строкой с циклически повторяемым ключом:
ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ТЧК БРАТЬЯ КАРАМАЗОВЫ ТЧК
ВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕ
В результате зашифрования, начальный этап которого показан на рисунке 5, получим шифротекст:
ЕХЩРЭАБЕЫЧУДККТИСЙЩРМЕЩЬЗЭРМДОБИЭУАДЧТШЛЕВМЪФГКЛЩП
Рисунок 5. Принцип шифрования по таблице Виженера
Расшифрование осуществляется следующим образом. Под буквами шифро-текста последовательно записываются буквы ключа; в строке таблицы, соответствующей очередной букве ключа, происходит поиск соответствующей буквы шифротекста. Находящаяся над ней в первой строке таблицы буква является соответствующей буквой исходного текста.
Для увеличения надежности шифра можно рекомендовать его использование после предварительной псевдослучайной перестановки букв в каждой строке таблицы. Возможны и другие модификации метода.
II. Советы по выполнению частотного анализа английских текстов
Начните с подсчета частоты появления каждой из букв шифр-текста. Примерно пять букв должны появляться с частотой менее 1 процента, и они вероятно, представляют собой j, k, q, х и z. Одна из букв должна появляться с частотой более 10 процентов, и она, по-видимому, представляет собой е. Если шифр-текст не подчиняется этому распределению частот, то, возможно, исходное сообщение написано не на английском языке. Вы можете определить, какой это язык, если проанализируете частотное распределение букв в шифр-тексте. К примеру, в итальянском языке обычно ecть, три буквы с частотностью более 10 процентов и 9 букв с частотностью менее 1 процента. В немецком языке буква е имеет чрезвычайно высокую частотность - 19 процентов, поэтому любой шифр-текст, в котором одни из букв встречается столь же часто, является, вполне возможно, немецким. После того как вы определили язык, для выполнения частотного анализа вам следует воспользоваться соответствующей таблицей частотности букв для данного языка. Если у вас есть нужная таблица частотности букв, то нередко удается дешифровать даже шифр-тексты на неизвестном языке.
Если установлена взаимосвязь с английским языком, но, как часто и происходит, сразу же открытый текст не появляется, тогда обратите внимание на пары повторяющихся букв. В английском языке чаще всего повторяющимися буквами будут ss, ее, tt, ff, 11, mm и оо. Если в шифр-тексте имеются какие-либо повторяющиеся символы, то вы можете считать, что они представляют собой одну из этих пар.
Если в шифр-тексте имеются пробелы между словами, то постарайтесь определить слова, состоящие из одной, двух или трех букв. Единственными словами в английском языке, состоящими из одной буквы, являются а и I. Чаще всего встречающимися двухбуквенными словами будут of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am. Наиболее часто появляющиеся трехбуквенные слова - the и and.
Если удастся, подготовьте таблицу частотности букв для сообщения, которое вы стараетесь дешифровать. Например, в военных донесениях стремятся опускать местоимения и артикли, и отсутствие таких слов, как I, he, а и the, будет снижать частотность некоторых из чаще всего встречающихся букв. Если вы знаете, что работаете с военным донесением, вам следует использовать таблицу частотности букв, созданную на основе других военных донесений.
(5) Одно из самых полезных для криптоаналитика умений - это способность благодаря собственному опыту или чисто интуитивно - распознавать слова или даже целые фразы. Аль-Халил, один из первых арабских криптоаналитиков, продемонстрировал свои способности, когда взломал греческий шифр-текст. Он предположил, что шифр-текст начинается с приветствия «Во имя бога». Установив, что эти буквы соответствуют определенному фрагменту шифр-текста, он смог использовать их в качестве лома и раскрыть остальной шифр-текст. Это получило название криб.
(6) В некоторых случаях наиболее часто встречающейся буквой в шифр-тексте может быть Е, следующей по частоте появления - Т и так далее. Другими словами, частотность букв в шифр-тексте уже совпадает с частотностью букв в таблице. По-видимому, буква Е в шифр-тексте является действительно е, и то же самое, похоже, справедливо и для других букв, и все же шифр-текст выглядит тарабарщиной. В этом случае вы столкнулись не с шифром замены, а с шифром перестановки. Все буквы остались теми же самыми, но находятся они не на своих местах.
III. Задания на криптоанализ классических шифров
3.1 Шифр столбцовой перестановки
При решении заданий на криптоанализ шифров перестановки необходимо восстановить начальный порядок следования букв текста. Для этого используется анализ совместимости символов, в чем может помочь таблица сочетаемости.
Таблица 1. Сочетаемость букв русского языка
|
Г |
С |
Слева |
Справа |
Г |
С |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
3 |
97 |
л, д, к, т, в, р, н |
А |
л, н, с, т, р, в, к, м |
12 |
88 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
80 |
20 |
я, е, у, и, а, о |
Б |
о, ы, е, а, р, у |
81 |
19 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
68 |
32 |
я, т, а, е, и, о |
В |
о, а, и, ы, с, н, л, р |
60 |
40 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
78 |
22 |
р, у, а, и, е, о |
Г< /b>
о, а, р, л, и, в
69
31
72
28
р, я, у, а, и, е, о
д
е, а, и, о, н, у, р, в
68
32
19
81
м, и, л, д, т, р, н
Е
н, т, р, с, л, в, м, и
12
88
83
17
р, е, и, а, у, о
Ж
е, и, д, а, н
71
29
89
11
о, е, а, и
3
а, н, в, о, м, д
51
49
27
73
р, т, м, и, о, л, н
и
с, н, в, и, е, м, к, з
25
75
55
45
ь, в, е, о, а, и, с
к
о, а, и, р, у, т, л, е
73
27
77
23
г, в, ы, и, е, о, а
л
и, е, о, а, ь, я, ю, у
75
25
80
20
я, ы, а, и, е, о
м
и, е, о, у, а, н, п, ы
73
27
55
45
д, ь, н, о, а, и, е
н
о, а, и, е, ы, н, у
80
20
11
89
р, п, к, в, т, н
о
в, с, т, р, и, д, н, м
15
85
65
35
в, с, у, а, и, е, о
п
о, р, е, а, у, и, л
68
32
55
45
и, к, т, а, п, о, е
р
а, е, о, и, у, я ,ы, н
80
20
69
31
с, т, в, а, е, и, о
с
т, к, о, я, е, ь, с, н
32
68
57
43
ч, у, и, а, е, о, с
т
о, а, е, и, ь, в, р, с
63
37
15
85
п, т, к, д, н, м, р
У
т, п, с, д, н, ю, ж
16
84
70
30
н, а, е, о, и
ф
и, е, о, а, е, о, а
81
19
90
10
у, е, о, а, ы, и
X
о, и, с, н, в, п, р
43
57
69
31
е, ю, н, а, и
ц
и, е, а, ы
93
7
82
18
е, а, у, и, о
ч
е, и, т, н
66
34
67
33
ь, у, ы, е, о, а, и, в
ш
е, и, н, а, о, л
68
32
84
16
е, б, а, я, ю
щ
е, и, а
97
3
0
100
м, р, т, с, б, в, н
ы
л, х, е, м, и, в, с, н
56
44
0
100
н, с, т, л
ь
н, к, в, п, с, е, о, и
24
76
14
86
с, ы, м, л, д, т, р, н
э
н, т, р, с, к
0
100
58
42
ь, о, а, и, л, у
ю
д, т, щ, ц, н, п
11
89
43
57
о, н, р, л, а, и, с
я
в, с, т, п, д, к, м, л
16
84
Таблица 2. Сочетаемость букв английского языка
При анализе сочетаемости букв друг с другом следует иметь в виду зависимость появления букв в открытом тексте от значительного числа предшествующих букв. Для анализа этих закономерностей используют понятие условной вероятности. Систематически вопрос о зависимости букв алфавита в открытом тексте от предыдущих букв исследовался известным русским математиком А.А.Марковым (1856 -- 1922). Он доказал, что появления букв в открытом тексте нельзя считать независимыми друг от друга. В связи с этим А. А. Марковым отмечена еще одна устойчивая закономерность открытых текстов, связанная с чередованием гласных и согласных букв. Им были подсчитаны частоты встречаемости биграмм вида гласная-гласная (г,г), гласная-согласная (г,с), согласная-гласная (с,г), согласная-согласная (с,с) в русском тексте длиной в 105 знаков. Результаты подсчета отражены в следующей таблице: Таблица 3. Чередование гласных и согласных
Пример решения: Дан шифр-текст: СВПООЗЛУЙЬСТЬ_ЕДПСОКОКАЙЗО Текст содержит 25 символов, что позволяет записать его в квадратную матрицу 5х5. Известно, что шифрование производилось по столбцам, следовательно, расшифрование следует проводить, меняя порядок столбцов.
Необходимо произвести анализ совместимости символов (Таблица сочетаемости букв русского и английского алфавита, а также таблицы частот биграмм представлена выше). В первом и третьем столбце сочетание СП является крайне маловероятным для русского языка, следовательно, такая последовательность столбцов быть не может. Рассмотрим другие запрещенные и маловероятные сочетания букв: ВП (2,3 столбцы), ПС (3,1 столбцы), ПВ (3,2 столбцы). Перебрав их все, получаем наиболее вероятные сочетания биграмм по столбцам:
Получаем осмысленный текст: ВОСПОЛЬЗУЙТЕСЬ_ПОДСКАЗКОЙ Задание: Расшифровать фразу, зашифрованную столбцовой перестановкой. 1. ОКЕСНВРП_ЫРЕАДЕЫН_В_РСИКО 2. ДСЛИЕЗТЕА_Ь_ЛЬЮВМИ_ _АОЧХК 3. НМВИАИ_НЕВЕ_СМСТУОРДИАНКМ 4. ЕДСЗЬНДЕ_МУБД_УЭ_КРЗЕМНАЫ 5. СОНРЧОУО_ХДТ_ИЕИ_ВЗКАТРРИ 6. _ОНКА_БНЫЕЦВЛЕ_К_ТГОАНЕИР 7. НЗМАЕЕАА_Г_НОТВОССОТЬЯАЛС 8. РППОЕААДТВЛ_ЕБЬЛНЫЕ_ПА_ВР 9. ОПЗДЕП_ИХРДОТ_И_ВРИТЧ_САА 10. ВКЫОСИРЙУ_ОЬВНЕ_СОАПНИОТС 11. ПКТИРАОЛНАОИЧ_З_ЕСЬНЕЛНЖО 12. ИПКСОЕ_ТСМНАЧИ_ОЕН_ГДЕЛА_ 13. АМВИННЬТЛЕАНЕ_ЙОВ_ОПХАРТО 14. АРЫКЗЫ_КЙТНЛ_ААЫ_ОЛБКЫТРТ 15. _ПАРИИВИАРЗ_БРА_ИСТЬЛТОЕК 16. П_ЛНАЭУВКАА_ЦИИВР_ОКЧЕДРО 17. ЖВНОАН_АТЗОЬСН_ЫО_ФВИИКИЗ 18. ОТВГОСЕЬЬТАДВ_С_ЬЗАТТЕЫАЧ 19. ЯАМРИТ_ДЖЕХ_СВЕД_ТСУВЕТНО 20. УЬБДТ_ОЕГТВ_ОЫКЭА_ВКАИУЦИ 21. ЛТБЕЧЛЖЫЕ_ _ОАПТЖРДУ_ЛМНОА 22. ИТПРКРФАГО_АВЯИА_ЯНЖУАКАН 23. ПКЕЕРРПО_ЙУСТ_ИТПСУТЛЯЕИН 24. ИЬЖЗНСД_ТДН_ЕТ_НУВЕУРЫГОЫ 25. ЕОУРВА_НЬРИАДИЦЕПИ_РНШВЫЕ 3.2 Шифр двойной перестановки Пример решения: Дан шифр-текст: ЫОЕЧТТОУ_СНСОРЧТРНАИДЬН_Е Текст содержит 25 символов, что позволяет записать его в квадратную матрицу 5х5. известно, что шифрование производилось сначала по столбцам, а затем по строкам, следовательно, расшифрование следует проводить тем же способом.
Производим анализ совместимости символов. Если в примере столбцовой перестановки можно было легко подобрать нужную комбинацию путем перебора, то здесь лучше воспользоваться таблицей частот букв русского языка (см. приложение). Для оптимизации скорости выполнения задания можно проверить все комбинации букв только в первой строке. Получаем ОЕ-15, ОЧ-12, ЕТ-33, ТЕ-31, ЧО-х, ЕО-7, ЧЫ-х, ОЫ-х, ТЫ-11, ТЧ-1, ЧЕ-23 (где х-запрещенная комбинация). Из полученных результатов можно предположить следующую комбинацию замены столбцов 2 4 3 5 1:
Теперь необходимо переставить строки в нужном порядке. 3 2 4 5 1:
Получаем осмысленный текст: СРОЧНО_УСТРАНИТЬ_НЕДОЧЕТЫ Задание: Расшифровать фразу, зашифрованную двойной перестановкой (сначала были переставлены столбцы, затем строки) 1. СЯСЕ_ _ЛУНЫИАККННОГЯДУЧАТН 2. МСЕЫ_ЛЫВЕНТОСАНТУЕИ_РЛПОБ 3. АМНРИД_УЕБСЫ_ЕЙРСООКОТНВ_ 4. ОПЧУЛС_БООНЕВ_ОЖАЕОНЕЩЕИН 5. ЕШИАНИРЛПГЕЧАВРВ_СЕЫНА_ЛО 6. АРАВНРСВЕЕОАВ_ЗАНЯА_КМРЕИ 7. А_ЛТАВЙООЛСО_ТВ_ШЕЕНЕСТ_Ь 8. ФИ_ЗИММУЫНУУБК_Е_ДЬШЫИВЧУ 9. ВР_ЕСДЕИ_ТПХРОИ_ЗБУАДНУА_ 10. ЦТААЙПЕЕ_ТБГУРРСВЬЕ_ОРЗВВ 11. АВАРНСЧАА_НЕДВЕДЕРПЕОЙ_ИС 12. ДОПК_СОПАЛЕЧНЛ_ГИНЙОИЖЕ_Т 13. ЛУАЗИЯНСА_ДТДЕАИ_ШРФЕОНГ_ 14. С_ОЯНВ_СЬСЛААВРЧЕАРТОГДЕС 15. ЗШАФИПРАЛОЕНЖ_ОЬН_ДАРВОНА 16. КЭЕ_ТДУМБ_ЬСЗЕДНЕЗМАОР_ТУ 17. _ЕАЛЯРАНВЯАЧДА_ЕРПЕСАНВ_Ч 18. _И_ЕНТРЗИ_ОКЕВНОДЛЕША_ИМП 19. РОБДОЕВПС_МСХЬА_ _ИВПСНИОТ 20. ЕСДНОГТЕАНН_НЕОВМР_ЕУНПТЕ 21. _ЙЕСТОВО_НИИНЛАЕТИЖДСОПВ_ 22. НДИАЕОЫЛПНЕ_ _НВЕАНГТ_ИЗЛА 23. П_БИРДЛЬНЕВ_ОП_ОПЗДЕВЫГЕА 24. МДООИТЕЬ_СМТ_НАДТЕСУБЕХНО 25. АИНАЛЖНОЛЕШФ_ЗИ_УАРОЬСНЕ_ 3.3 Шифр простой замены Криптоанализ шифра простой замены основан на использовании статистических закономерностей языка. Так, например, известно, что в русском языке частоты букв распределены следующим образом: Таблица 4. Частоты букв русского языка (в 32-буквенном алфавите со знаком пробела)
Рисунок 6. Диаграмма частот букв русского языка Для получения более точных сведений об открытых текстах можно строить и анализировать таблицы k-грамм при k>2, однако для учебных целей вполне достаточно ограничиться биграммами. Неравновероятность k -грамм (и даже слов) тесно связана с характерной особенностью открытого текста - наличием в нем большого числа повторений отдельных фрагментов текста: корней, окончаний, суффиксов, слов и фраз. Так, для русского языка такими привычными фрагментами являются наиболее частые биграммы и триграммы: СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА Полезной является информация о сочетаемости букв, то есть о предпочтительных связях букв друг с другом, которую легко извлечь из таблиц частот биграмм. Имеется в виду таблица, в которой слева и справа от каждой буквы расположены наиболее предпочтительные "соседи" (в порядке убывания частоты соответствующих биграмм). В таких таблицах обычно указывается также доля гласных и согласных букв (в процентах), предшествующих (или следующих за) данной букве. Таблица 5. Таблица частот биграмм русского языка ЧАСТЬ 1
ЧАСТЬ 2
ЧАСТЬ 3
|
| ! | Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать. |
| Конспект | Лекция43. Учет материально - производственных запасов |
| Конспект | Средства в сельском хозяйстве |
| Конспект | Развивающиеся страны Африки |
| Конспект | Лакокрасочные материалы |
| Конспект | Скелет и его возрастные особенности |