Описание объекта исследования
Самым древним и самым простым из известных подстановочных шифров является шифр, использовавшийся Юлием Цезарем. В шифре Цезаря каждая буква алфавита заменяется буквой, которая находится на три позиции дальше в этом же алфавите. Проще всего это увидеть на примере.
Открытый текст: meet me after the toga party
Шифрованный текст: PHHW PH DIWHU WKH WRJD SDUMB
Алфавит считается «циклическим» поэтому после Z идет А. Определить преобразование, можно перечислив все варианты, как показано ниже.
Открытый текст: abcdefghijklmnopqrstuvwxyz
Шифрованный текст: DEFGHIJKLMNOPQRSTUVWXYZABC
Если каждой букве назначить числовой эквивалент (а=1, b=2, с=3 и т.д.), то алгоритм можно выразить следующими формулами. Каждая буква
открытого текста р заменяется буквой шифрованного текста С:
C = E(p) = (p+3)mod(26).
В общем случае сдвиг может быть любым, поэтому обобщенный
алгоритм Цезаря записывается формулой
С = Е(р) = (р +k) mod (26),
где k принимает значение в диапазоне от 1 до 25. Алгоритм дешифрования
также прост:
р = D(C) = (С-k)mod (26).
Если известно, что определенный текст был шифрован с помощью шифра Цезаря, то с помощью простого перебора всех вариантов раскрыть шифр очень просто - для этого достаточно перебрать 25 возможных вариантов ключей. На рисунке 4 показаны результаты применения этой стратегии к указанному выше сообщению. В данном случае открытый текст распознается в третьей строке.
Применение метода последовательного перебора всех возможных вариантов оправдано, если выполняются три важные характеристики данного шифра:
- известны алгоритмы шифрования и дешифрования;
- необходимо перебрать небольшое количество вариантов;
- язык открытого текста известен и легко узнаваем.
Алгоритм, для которого требуется перебрать слишком много ключей,
делает криптоанализ на основе метода последовательного перебора.
практически бесполезным. Например, алгоритм DES, использующий 56-
битовые ключи, требует при последовательном переборе рассмотреть
пространство из 256, или более чем 7x1016 ключей.
PHHW PH DIWHU WKH WRJD SDUMB
KEY
| oggv | og | chvgt | vjg | vqic | rctva | |
| nffu | nf | bgufs | uif | uphb | qbsuz | |
| meet | me | after | the | toga | party | |
| ldds | ld | zesdq | sgd | snfz | ozqsx | |
| kccr | kc | ydrcp | rfc | rmey | nyprw | |
| jbbq | jb | xcqbo | qeb | qldx | mxoqv | |
| iaap | ia | wbpan | pda | pkcw | lwnpu | |
| hzzo | hz | vaozm | ocz | ojbv | kvmot | |
| gyyn | gy | uznyl | nby | niau | julns | |
| fxxm | fx | tymxk | max | mhzt | itkmr | |
| ewwl | ew | sxlwj | lzw | lgys | hsjlq | |
| dvvk | dv | rwkvi | kyv | kfxr | grikp | |
| cuuj | cu | gvjuh | jxu | jewq | fqhjo | |
| btti | bt | puitg | iwt | idvp | epgin | |
| assh | as | othsf | hvs | hcuo | dofhm | |
| zrrg | zr | nsgre | gur | gbtn | cnegl | |
| yggf | yg | mrfqd | ftq | fasm | bmdfk | |
| xppe | xp | lqepc | esp | ezrl | alcej | |
| wood | wo | kpdob | dro | dyqk | zkbdi | |
| vnnc | vn | jocna | cqn | cxpj | yjach | |
| ummb | um | inbmz | bpm | bwoi | xizbg | |
| tlla | tl | hmaly | aol | avnh | whyaf | |
| skkz | sk | glzkx | znk | zumg | vgxze | |
| rjjy | rj | fkyjm | ymj | ytlf | ufwyd | |
| qiix | qi | ejxiv | xli | xske | tevxc |
Рисунок 4 - Криптоанализ шифра простой замены (шифра Цезаря) методом перебора всех вариантов ключей
В этом случае для криптоаналитика существует другая линия атаки. Если криптоаналитик имеет представление о природе открытого текста (например, о том, что это несжатый текст на английском языке), можно использовать известную информацию о характерных признаках, присущих текстам на соответствующих языке. Чтобы показать, как этот подход используется на практике, рассмотрим небольшой пример. Допустим, необходимо расшифровать следующий шифрованный текст.
На первом этапе можно определить относительную частоту появления в тексте различных букв и сравнит их со среднестатистическими данными для букв соответствующего языка, представленными в таблице 1 для русского языка и в таблице 2 для английского языка.
Таблица 1 - Вероятности p(С) появления символов в среднестатистическом тексте для русского языка
| Буква | p(C) | Буква | p(C) | Буква | p(C) |
| О | 0,090 | М | 0,026 | Й | 0,010 |
| Е | 0,072 | Д | 0,025 | Х | 0,009 |
| Ф | 0,062 | П | 0,023 | Ж | 0,007 |
| И | 0,062 | У | 0,021 | Ш | 0,006 |
| Н | 0,053 | Я | 0,018 | Ю | 0,006 |
| Т | 0,053 | З | 0,016 | Ц | 0,004 |
| С | 0,045 | Ы | 0,016 | Щ | 0,003 |
| Р | 0,040 | Б | 0,014 | Э | 0,003 |
| В | 0,038 | Ь,Ъ | 0,014 | Ф | 0,002 |
| Л | 0,035 | Г | 0,013 | ||
| К | 0,028 | Ч | 0,012 |
Таблица 2 - Вероятности р(С)появления символов в среднестатистическом тексте для английского языка
| Буква | p(C) | Буква | p(C) | Буква | p(C) |
| E | 0,131 | N | 0,071 | H | 0,053 |
| T | 0,104 | R | 0,068 | D | 0,038 |
| A | 0,082 | I | 0,063 | L | 0,034 |
| O | 0,080 | S | 0,061 | F | 0,029 |
| C | 0,028 | P | 0,020 | X | 0,002 |
| M | 0,025 | W | 0,015 | J | 0,001 |
| U | 0,024 | B | 0,014 | Q | 0,001 |
| G | 0,020 | V | 0,009 | Z | 0,001 |
| Y | 0,020 | K | 0,004 |
Если сообщение достаточно длинное, этой методики уже может быть достаточно для распознавания текста. Выяснив значения всего лишь 3-4 букв можно расшифровать уже значительную часть сообщения. Продолжая анализ частоты появления букв, а также применяя метод проб и ошибок, необходимо воспользоваться особенностями языка. Например, для русского языка это удвоение букв, окончания слов, короткие слова типа «как», «или», союзы и т.п.
Порядок выполнения работы
1. Использовать результаты сравнения статистических характеристик
символов шифртекста и русского языка для определения предварительных
значений нескольких символов в шифртексте.
1.1. Выполнить частотный анализ символов зашифрованного текста.
1.2. Выписать символы из шифртекста с частотой большей 0,04 и
произвести ранжирование их в порядке убывания частоты.
1.3. Сравнить ранги символов шифртекста с рангами символов в
русском языке.
1.4. Выбрать 3-4 наиболее частых символа в шифртексте и русском языке с одинаковыми рангами.
1.5. Заменить три или четыре символа в шифртексте на символы
русского языка с теми же рангами. Проверить совпадение рангов замененных символов в шифртексте и соответствующих символов в русском языке. Например, буква «о» самая частая буква в русском языке - она же должна оказаться самой частой буквой в шифртексте.
2. Использовать результаты грамматического анализа шифртекста и на этой основе произвести полное дешифрование текста.
2.1. Выполнить предварительный анализ и расшифровку коротких
слов (предлогов, местоимений, союзов междометий и т.п.) с использованием результатов, полученных в п. 1.5.
2.2. Для идентификации остальных символов шифртекста
воспользоваться особенностями русского языка (удвоения букв, окончания
слов и т.п.).
Содержание отчета
- Титульный лист
- Результаты частотного анализа шифрованного текста для первых символов, имеющих частоту большую 0,04
- Ранжирование наиболее часто встречающихся символов в порядке убывания.
- Таблица замены наиболее часто встречающихся символов шифртекста на соответствующие им по рангу символы в русском языке.
- Примеры особенностей русского языка, использованных при
дешифровании.
- Таблица ранжирования символов, имеющих в расшифрованном тексте частоту большую 0,04, и сравнения с ранжированием наиболее частых символов русского языка.
- Ответы на контрольные вопросы.
- Выводы.
Варианты заданий
Варианты для выполнения лабораторной работы представлены в таблице 3
Таблица 3
| № варианта | Шифртекст |
| СЛБПЗНЮЛЦХБО КИЮНЯВО МУИ АИЭЦО НЗЛЦКЭЫ ЕВЦВББ ЕЦЦФЦЗРФЦЫЦЦО НЮЛНТВРИ ЛЦЕЯИЭР ЯЛМЮБД ВЦМС АИЭЫЬ СНЗНЛНБ ОФЭОИЗКО БЕМЧИВБИ Б КНЕЯЦВБИ СЛБПЗНЮЛЦХБЧИКСБД ПЛИНГЛЦЕНФЦВББ Б ЦЭЮНЛБЗТНФ | |
| ФЕЫМК ЖПВ ЗЫВЮЫЦТТНР СВЯ ФНИЯЬШННРЕ Ф ЗЫВЮЫЦТТМ Е ФНИЯЫОЬЩЕЕ КФВЕ СВЗЕЕ Ф ЯЫМЮЕИ ЗЫВЮЫЦТТР ЗВТЕТВ ХМНСАЕЕ ЫЦКЗЫВКПЫЦНИНЕО ФЕЫМК ФРЗВЭНОИП НИУИЭЦПИЭЧНМЬ ХМНСАЕЬ ЯЭО КЕКПИТР | |
| ЛПВ ОФЯОИПКО ЦЕЮФТВЭ ЭЕИИЭ БЮЩЭПР ВПЫЮСИТЭИ АЕЮЫЮ ЛПВ ОФЯОИПКО ШЮЫЮУПИЫТВЭ ВКВГИТТВКПЗЬ БЮЩЭПР ЧВКПВОТТВИ ВСЭЕЮТЭИ АЕЮЫЮ ЭКУАК КПФВ ФИЕИТЭО ФВЭТР | |
| ЧПДШЭЗ ЖЮШ ГЮДШИП ГЯНФШЭШФ ЯГЧШЭЗБАУНПО ЕЭО ПАЮУТЮЯЫЯИПМЯЯ ШКЗУИЮП БПЕПТЯУ ЧШДШЭО Я ГФОБПТТШЦШ Г ТЯН ЯЕУТЮЯЫЯИПЮШДП ЧШЭЗБШФПЮУЭО ДПГГНПЮДЯФПУЮГО ИПИ ЕШИШБПЮУЭЗГЮФШ ЧДПФП ТП ЯГЧШЭЗБШФПТЯУ ФШБНШСТШГЮУЯ ГФОБПТТРВ Г ЕПТТРН ЯЕУТЮЯЫЯИПЮШДШН ЧШЭЗБШФПЮУЭО | |
| ЮДБОТУИАА ИБТЗ ИБЕЧЗЬЮГДТПО ЧДБСДПЕЕП У ИПЦЯЩАЕАУО АЭА НГАУЮФАЮГЭЗТБ ЧБЭГШТРЕА ЫЯТИМАОЕА УБНГДЦПЩПО НБЧБЭТАЮГЭЗТРГ УИДРЮРГ ЫЯТИМАА ЮПАИБЕ АУЧБЭЗШЯЬЩАГ ШПИБТТРГ ЧДПФП ФРЧБЭТОЫЦАГ ГГ ЧДБМГУУП ФБ ФДГН ШПЩАЮГ | |
| ЕИХЭДЫВФЮТЭИ ЖПВ ЧИЫИФВЕ ХЭДЫВФЮТТВЦВ ПИУКПЮ ЭЯЭ ЕЮТТРШ Ф ВЫЭЦЭТЮЯЗТРЭ ПИУКП ЭЯЭ ЕЮТТРИ ТЮБРФЮИНРИ ВПУЫРПРН ПИУКПВН ПВ СИ ЛПВ Э ЫЮКХЭДЫВФЮТЭИ | |
| ГУИДУЮТРЯ ИЭЬЛ ЖЮШ ИЭЬЛ ЧДЯНУТОУНРЯ Ф ГЯГЮУНУ ГЯННУЮДЯЛТШЦШ ХЯЫДШФПТЯО ШКУ АЛПГЮФАЬЩЯУ Ф ШКНУТУ ЕПТТРНЯ ГЮШДШТР ЕШЭСТР ГШФНУГЮТШ ЯГЧШЭЗБШФПЮЗ ШЕЯТ Я ЮШЮ СУ ИЭЬЛ ИШЮШДРЯ ЕШЭСУТ ШГЮПФПЮЗГО ГУИДУЮТРН ЛЮШКР ГФОБЗ ШГЮПФПЭПГЗ ГУИДУЮТШЯ | |
| ИКЯЭ КИУЫИПТРИ КФИЕИТЭО ВУЮБРФЮЬПКО ЫЮКУЫРПРНЭ УИН ПВ ЫЮТЗХИ ФЫИНИТЭ ПВ ИЦВ КЯИЕАИП АГЭПЗ ЫЮФТВ УЮУ Э ПВЦВ УВНА ВТ ЖПЭ КФИЕИТЭО ВПУЫРЯ ФВИТТВИ ЭКУАККПФВ | |
| ЦНЦЭЕБ Е НЦГЭЬЯИНЕИ ПИВЫЕО Е ВЗРП НЕСВЮЯЦ НИ ЯВЭУНР ЕКСЭЬЛЦПЧ ЯЫМЮ ЯЫМЮЦ ЕЭЕ ВПНВКЕПЧКО ЯЫМЮ С ЯЫМЮМ К ЗЫИНИГЫИУИНЕИТ НЦЗЫВПЕФ ВНЕ ЯВЭУНР ЯВЗВЭНОПЧ ЯЫМЮ ЯЫМЮЦ |
Контрольные вопросы
1. Что такое энтропия языка?
2. Что понимается под избыточностью сообщения?
3. Что такое шифр простой замены?
4. Объясните принцип дешифрования шифра простой замены.
5. Объяснить, почему при вскрытии шифра простой замены используется не полная ранжировка по частоте всех символов русского языка, а лишь 3-4 наиболее частых символов, как в п. 1.4?
6. Какие основные разновидности шифров простой замены применялись в прошлом?
7. Правила шифрования/дешифрования шифра Цезаря.
Литература
1. Бабаш А.В., Шанкин Г.П. История криптографии. Учебное пособие. -М.»Гелиос АРВ», 2001 г.
2. Столингс В. Криптография и защита сетей. Принципы и практика. 2-е изд. - М.: Вильямс, 2001.
Лабораторная работа №2
ИССЛЕДОВАНИЕ ШИФРА ПЕРЕСТАНОВКИ (ШИФР КАРДАНО)
Цель работы: Исследовать шифр Кардана. Разработать алгоритмы
шифрования и дешифрования.