Описание объекта исследования

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

Открытый текст: 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
ИССЛЕДОВАНИЕ ШИФРА ПЕРЕСТАНОВКИ (ШИФР КАРДАНО)

Цель работы: Исследовать шифр Кардана. Разработать алгоритмы
шифрования и дешифрования.