 |
|
АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
А ЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕР
Б УШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗ
В ШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУ
Г ВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШ
Д ЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВ
Е ЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬ
Ж ЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯ
З ЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖ
И КГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩ
Й ГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩК
К ЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГ
Л ФМДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛ
М МДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФ
Н ДПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМ
О ПЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМД
П ЪЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДП
Р ЫНЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪ
С НЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫ
Т ЮОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫН
У ОСИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮ
Ф СИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮО
Х ИЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОС
Ц ЙТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИ
Ч ТЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙ
Ш ЧБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТ
ЩБАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧ
ЪАЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБ
ЫЭХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБА
ЬХЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭ
ЭЦЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХ
ЮЕРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦ
ЯРЗУШВЬЯЖЩКГЛФМДПЪЫНЮОСИЙТЧБАЭХЦЕ
Применение квадрата Виженера весьма удобно для шифрования/ расшифрования "вручную", т.к. при этом не требуется выполнения арифметических операций над числовыми эквивалентами букв алфавита, как это было показано в лаборатрной работе № 2.
Для шифрования текста с использованием "квадрата" ключевое слово (ключ) многократно подписывается под шифруемым текстом. Каждая буква текста шифруется с помощью смешанного алфавита, соответствующего той букве ключа, которая стоит под данной буквой текста.
Теперь понятно, почему полученные таким способом криптограммы уже не поддаются раскрытию с помощью частотного метода, так как каждая буква текста шифруется по-разному в зависимости от выпавшей на нее буквы ключа.
Упражнение 2. Самостоятельно опробуйте описанный метод, используя как пример шифровку текста
"Попробуйте прочитать криптограмму точка"
с ключом ЛИСП на основе приведенного выше квадрата:
ПОПРОБУЙТЕ ПРОЧИТАТЬ КРИПТОГРАММУ ТОЧКА
ЛИСПЛИСПЛИ СПЛИСПЛИС ПЛИСПЛИСПЛИС ПЛИСП
——————————————————————————————————————-
АЙЗРБГЬЧЦД ЗРБРБУФАД БЭЫЗУБФУЪТСЬ УБРЭЪ
Теперь предположим, что перехвачена следующая криптограмма (сочетание букв ЦМ выделено специально - для наглядности последующих пояснений):
ЖНФЖП ЕЕЫШВ ЛПЖАТ ГФБЦМ КЖЬЗА ЮЪИВУ ЩЖРСЮ БЬЬКЬ ЫЕСУУ ЦТЮБШ УНЖЦМ
ЭЭШЮЗ УЬЕКН АУЕЫЩ ШЖРЬЙ ЛЮПКН ДЙЯГЭ ЪЖЫГЖ ОУШИШ УФГВР ШМАГВ ВУВОС
ЗХЧИУ ГНЛАЯ ЬЬКИЯ РЦЖРЫ АХЪВИ ЖГЭЯЦ СЪУЫФ ЯРМЗФ ЧФЬЩС ЬФШВЕ ОМКТИ
МБЭВЪ КФХЙЦ ХНЬЮЬ МФЛБИ МРУЛМ ЯЗФЧЪ ЪЧЗНК ЗНИВЛ НЩГЛЩ ИЛЗНФ ФУЖКН
ДЙЯГЭ ЕУЮЛЛ ЮЖНЯИ ЕМДЙШ ГЯУГВ ЦФЩВЮ МФАГЯ ВХМЭВ ВФПГФ ФЖККГ ЦМЛЫБ
ШМПУЕ ШЖЛЯЮ ЯРЧВЪ ЖУПВМ КЛЫЭС ЭЧИРЫ ГЫЩЗЗ ЗКЖЛЕ ШВРЪЧ ЪААЖЗ ДХЪДС
БРНМЪ КЫБЪФ УНЦЮБ ТЖУНЯ ЕШИМУ КФВГВ ГЧМЭВ ЗРВМЪ ЪЕЕТО ЯЦБЖГ ВИЖМД
КЗЗПА ФЯВНР ЫГЮЩЭ ЯЫЦШЪ ЧНГВЫ АХЪВЛ НШАПВ ЧОЬОЙ КЮАШО КЗЛЩУ ШЯРНЗ
ГХЛТЮ ЖЫШШГ ППЬЫШ АЬФМА ФЕЙЗА ЙПЛУЭ ЖЛЗИЗ НЖККР ЦЯДЧК НДЙЯГ ЭБФЬА
ВБЭКЗ ФКЫТВ ЛЕЪЭЯ ЛЭЩЗН ФХГЧК ТКЫЮЗ ЗЪУЖА ПВЧОЬ ОЙКЕС ЛЗАЮЪ ИВУНЫ
ПКЗВЯ ЪГОСЩ ЛБЬГМ ЯВЗГЬ КШЪГЙ ЕНПСМ ЭВГОГ ЧСОРГ ЩОЦМВ ДГЩКЧ ЮЗВЗК
ЦЧЯРЧ ВЪЖФЫ ЕЛЖАЪ УССХР УОЬЫЕ ЙГЫОТ УЕАГЖ ГЫСЩИ ЯРВТЮ ДЖНЛГ ЦМЗЬЪ
ЯИЦТР ЕМИКЦ ЩВЦОР ЛХМХЖ ВРЬПУ ГВЯРЬ ПМЯЖЖ РЧПШЪ ЧУВГЧ СЕЕГЦ ЪПЗДМ
ОЬОЧЗ КВУФЯ УПОХЪ ГЪЭЯЖ ВЖФ
В исходном тексте и криптограмме использован русский язык. Последовательность букв криптограммы разбита на группы по 5 букв (за исключением только последней группы из 3-х букв).
Очевидно, что перегруппировка букв сделана криптографом для скрытия структуры исходного текста - разбивки слов пробелами с целью повышения криптостойкости сообщения. Это мотивировано тем, что вследствие информационной избыточности реальных языков длина слова являются весьма ценной подсказкой и может облегчить работу криптоаналитика.
Предположим, что криптограмма получена при помощи квадрата Внженера. Если предположение неверно, приведенные ниже методы позволят это обнаружить.
Если же предположение верно, то необходимо определить не только смешанный алфавит, но и ключевое слово, поскольку каждый из этих элементов искажен другим.
Расшифровку следует начинать с нахождения длины ключевого слова (ключа).
Для пояснения идеи определения длины ключа вернемся к упражнению 2.
Обратите внимание, что в криптограмме 1-я, 5-я, 9-я и т.д. буквы исходного текста шифровались при помощи одного и того же смешанного алфавита « Л » (отмечены красным цветом и подчеркнуты).
Таким образом, если рассматривать лишь каждую четвертую букву шифрованного текста начиная с 1-й, то получим распределение частот, подобное распределению частот букв русского алфавита, поскольку буквы в этих позициях зашифрованы при помощи одного и того же смешанного алфавита, т. е. при помощи простой подстановки.
Аналогично если взять каждую четвертую букву шифрованного текста, начиная со 2-й, 3-й или 4-й позиции, то снова получим распределение частот как для букв русского алфавита.
 |
Существует способ оценить, насколько измеренное по криптограмме распределение частот букв соответствует типичному распределению букв алфавита можно, используя т.н. индекс совпадения (ИС), который вычисляется по формуле /включите режим разметки/:
где fi— количество появлений i-й буквы, а N — общее число рассматриваемых букв.
Если все буквы рассматриваемого подмножества текста зашифрованы при помощи одного алфавита, то этот индекс совпадения должен иметь значение больше 0.045 и, возможно, меньше 0.065(теоретическое значение равно 0.055).
Таким образом, рекомендуется следующий алгоритм определения длины ключа.
Шаг 1. Для i от 1 до 20 предположить, что длина ключевого слова равна i, и выполнить шаги 2, 3. Верхняя граница выбрана = 20 лишь в учебных целях (реальный ключ может быть значительно длиннее).
Шаг 2. Для j от 1 до i выполнить шаг 3. На этом шаге должны быть вычислены i различных значений ИС.
Шаг 3. Построить распределение числа появления букв в каждой i-й позиции, начиная с j -й позиции т.е. в позицнях
j, i + j, 2i + j, ...
и вычислить ИС для полученного распределения.
Внимание! В качестве N при вычислениях нужно использовать число букв в данном подмножестве текста, а не длину всего текста.
Если все вычисленные при этом значения ИС больше 0.045, то, вероятно, i кратно длине ключа. Если только один из ИС меньше 0.045, то i также может быть кратно длине ключа.
Проверить длину ключевого слова можно и другим способом.
Для этого следует найти два места в криптограмме, где две одинаковых буквы идут в том же порядке, например ЦМ в позициях 19,20 и 54,55.
Такое повторение могло произойти по двум причинам:
- в соответствующих местах исходного текста были разные сочетания букв, которым отвечали разные части ключа, и они случайно отобразились в одинаковые сочетания букв;
- в исходном тексте были повторения, которые попали на одинаковые части ключевого слова, и, таким образом, оказались зашифрованными дважды одним и тем же перемешанным алфавитом.
Во втором случае расстояние между началами повторяющихся сочетаний букв должно быть кратно длине ключевого слова.
Однако невозможно определить, по какой из двух причин произошло повторение данного сочетания букв, т.к. случайное повторение 2-х букв в криптограмме довольно частое явление.
Но если в криптограмме повторяются сочетания из 3-х или более букв, то вероятность того, что это повторение произошло случайно, а не в результате повторения ключа, очень мала (для сочетаний из 4-х и более букв она практически нулевая).
Таким образом, другой способ выявления длины ключевого слова — отыскать в шифрованном тексте все пары повторяющихся групп 3-х и более букв и измерить расстояния между ними.
Число, которое делит нацело 90% или более из этих расстояний, — наиболее вероятное значение длины ключа.
Проверка указанным способом в совокупности с вычислением значений ИС однозначно определяет длину ключа.
ПРАКТИЧЕСКАЯ ЧАСТЬ
1. Написать вспомогательную программу определения статистики алфавита русского/английского языка (подсчета вероятностей букв в осмысленных текстах).
Примечание: Выбор языка шифрованных текстов и, соответственно, криптограмм - по усмотрению исполнителя.
Вход.
Текстовый файл. Размер файла - чем больше, тем лучше. Ограничение на длину - только лишь разумное время обработки.
Выход.
Таблица статистики (вывести на экран и в файл), аналогичная любой из табл. 1-4.
Примечание. Пробелы и пунктуация должны убираться из текста автоматически, поскольку и при шифровании текста они не должны учитываться (только в учебных целях, разумеется).
Задание. С помощью программы определения статистики исследовать зависимость статистики от размера выборки (файла).
Результат исследования в отчете представить в виде таблиц (или одной сводной таблицы)и диаграммы для 5-6 возрастающих по размеру файлов (или связных фрагментов одного файла). По оси "Y" - вероятности букв; по оси "Х" - последовательность букв от первой до последней в алфавите.
Сравнить результаты с данными табл. 1-4. Сделать выводы. Создать рабочий файл статистики для использования в дальнейшем.
2. Написать программу расшифровки криптограмм, созданных методом простой подстановки.
Вход.
2.1. Выходной текстовый файл программы шифровки методом простой подстановки или текстовый файл, представляющий собой криптограмму и созданный "вручную" с помощью какого-либо текстового редактора. В первом (предпочтительном!) случае целесообразно использовать программы, разработанные в Лаб. работе № 2.
2.2. Таблица статистики, полученная с помощью программы определения статистики алфавита (п. 1. ПРАКТИЧЕСКОЙ ЧАСТИ) и одна из таблиц 1 - 4.
Длина криптограммы - не менее 30-40 букв.
Выход. расшифрованный текст (вывести на экран).
ПРИМЕЧАНИЕ. Криптограмму получить по произвольно выбранному фрагменту того же файла, который использовался как входной для программы п. 1. ПРАКТИЧЕСКОЙ ЧАСТИ.
Задание. С помощью данной программы попробовать "расшифровать" несколько криптограмм. Сравнить результаты расшифровки с помощью самостоятельно созданной таблицы статистики и с помощью выбранной таблицы из приведенных в тексте теоретической части. Какая из таблиц "лучше"?
3. Написать программу шифровки текста с использованием квадрата Виженера.
Вход.
3.1. Текстовый файл.
3.2. Начальный перемешанный алфавит.
3.3. Ключ (длина порядка 10 букв).
Выход.
Криптограмма (вывести в файл и на экран).
Примечания.
Программа должна автоматически формировать квадрат Виженера по введенному любым способом начальному перемешанному алфавиту. Иными словами, и начальный перемешанный алфавит, и ключ являются параметрами, позволяющими варьировать условия шифровки/расшифровки, исследовать и повторно проверять отдельные особенности программы расшифровки.
Криптограмму на экран желательно выводить группами букв для удобства визуального исследования (см. криптограмму, используемую в качестве примера в теоретической части).
Пробелы и знаки пунктуации игнорировать.
Задание. Зашифровать фрагмент того же файла, по которому определялась статистика. Размер шифруемого текста и соответственно, криптограммы, должен быть порядка 800-1000 букв.
4. Написать программу для определения длины ключа криптограммы.
Вход.
Криптограмма (выходной файл программы п.3 ПРАКТИЧЕСКОЙ ЧАСТИ).
Выход.
Предполагаемая длина ключа (вывести на экран). Дополнительная информация (вывод на экран):
- значение индексов совпадения;
- пары повторяющихся групп 3-х и более букв с указанием их позиций в криптограмме;
- другая информация по усмотрению исполнителя.
Примечание. Использовать оба метода оценки длины ключа (по индексу совпадения и по отысканию в криптограмме всех пар повторяющихся групп 3-х и более букв.
Задание. Определить длину ключа криптограммы, полученной при выполнении задания к п.3 ПРАКТИЧЕСКОЙ ЧАСТИ. Сопоставить с известным значением. Сделать выводы.
ОБЩИЕ ЗАМЕЧАНИЯ (Прочтите обязательно!)
Криптоанализ - в общем случае очень сложная задача, в успешном решении которой немалую роль играет интуиция криптоаналитика, т.е. в определенном смысле процесс ее решения носит эвристический характер. То, что выполняется в лабораторной работе - лишь имитация реальности, поскольку и щифруемый текст, и ключ и др. известны "криптоаналитику" абсолютно точно и всегда есть возможность проконтролировать процесс и проверить результат расшифровки.
Следует иметь в виду, что в реальных ситуациях предложенное машиной решение может оказаться не совсем точным.
Четкость оформления выводных данных программ имеет большое значение: бестолковый вывод лишь затруднит работу интуиции криптоаналитика в реальных условиях.
Описанные здесь алгоритмы достаточно легко реализуются, но имеют один недостаток — они не дают однозначного результата.
Длина ключевого слова, например, будет лишь вероятной, так что необходимо еще сделать обоснованный выбор одной из возможных длин.
Кроме этого, алгоритмическое определение исходных эквивалентов для редко встречающихся букв криптограммы следует проверить, убедившись, что при расшифровке получаются правильные русские/английские слова.
Увеличивая статистическую информацию, доступную программе, можно получить более надежное основание для алгоритмических решений, но все равно эти решения должен проверить криптоаналитик.
В идеале помимо указанных алгоритмов в программах должны быть реализованы средства, позволяющие подтвердить обоснованность выводов, которые делает программа. Хороший способ обеспечить возможность такой оценки — написать программу, работающую в интерактивном режиме так, чтобы программа и пользователь смогли "совместно обсудить" качество каждого решения до того, как оно будет окончательно принято. «Обсуждение» обычно состоит в том, что программа сообщает криптоаналитику факты, говорящие в пользу того или иного возможного решения, а он либо принимает его, либо отвергает, после чего вычисление может быть продолжено.
ОТЧЕТНОСТЬ
Тексты программ, таблицы, диаграмма статистик, шифруемые (открытые) тексты и их криптограммы, "взломанные криптограммы", числовые результаты работы программ. Выводы.