gazya.ru страница 1
скачать файл

Полиалфавитные шифры и их криптоанализ
Шифрование. Исходный открытый текст разбивается на последовательные группы длины , где -- период, выбираемый криптографом и держащийся в секрете. Для удобства объяснений сообщение переписывается в виде матрицы, строками которой являются последовательные группы. Например, пусть открытый текст будет "Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении" и пусть период будет равен 4. Представим открытый текст как матрицу размера 17х4:


и

г

р

ы

р

а

з

л

и

ч

а

ю

т

с

я

п

о

м

у

к

а

к

о

е

м

е

с

т

о

о

н

и

з

а

н

и

м

а

ю

т

в

ж

и

з

н

и

д

е

т

е

й

и

х

в

о

с

п

и

т

а

н

и

и

и

е

н

и

и

Далее криптограф выбирает 4 различных моноалфавитных шифра. Первый столбец (буквы и р и т о ....е) шифруются первым шифром; второй столбец (буквы г а ч с м ...н) -- вторым шифром, и т.д.



Пример (Вариант 51 из файла Rus_poly)
Исходный текст:

Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении Каждый отдельный вид игры имеет многочисленные варианты Дети очень изобретательны Они усложняют и упрощают известные игры придумывают новые правила и детали Например сюжетно ролевые игры создаются самими детьми но при некотором руководстве воспитателя Их основой является самодеятельность Такие игры иногда называют творческими сюжетно ролевыми играми Разновидностью сюжетно ролевой игры являются строительные игры и игры драматизации В практике воспитания нашли свое место и игры с правилами которые создаются для детей взрослыми К ним относятся дидактические подвижные и игры забавы В основе их лежит четко определенное программное содержание дидактические задачи и целенаправленное обучение. Для хорошо организованной жизни детей в детском саду необходимо разнообразие игр так как только при этих условиях будет обеспечена детям возможность интересной и содержательной деятельности Многообразие типов видов форм игр неизбежно как неизбежно многообразие жизни которую они отражают как неизбежно многообразие несмотря на внешнюю схожесть игр одного типа модели


Период: 4

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ - чистый алфавит

ЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЖЗИ - 1-ый алфавит

ГАЭЪЧФСОЛИЕВЯЬЩЦУРНКЗДБЮЫШХТПМЙЖ - 2-ый алфавит

БФЗЪНАУЖЩМЯТЕШЛЮСДЧКЭРГЦЙЬПВХИЫО - 3-ый алфавит

ПЪЕРЫЖСЬЗТЭИУЮЙФЯКХАЛЦБМЧВНШГОЩД - 4-ый алфавит



Задание:
Расшифруйте сообщение, полагая, что был использован полиалфавитный шифр
СЪСШ ЩГЖИСЮБЩЫРО ФЧ РЛЫОУУПЦЛЫ ЦЙУБЭЫФСЮДЯ ЛКЧААЮЦЩДХИЯ Б ХЙЕУЖ ШЩ ЧЙХК ЯПУЩА УОРЧЙ ЧЬЩ ЬЙЬЩУЙЙЧ Е ПЛЖЮС ЧАХОИ ЩЦ ЛЩДФСНБЮСЛ Щ ЙККЦЖЦЛЩ ЭЙСНШТ ЩЧЫОВХЮДИ ЗЗН ЛЪЯД ЛЕЖОН ЕЮЧЪЛМСРТЖЦЬВЖ ЛГСЗЙЬЧШ НФЧЗ ЧЮАЮЕ ЛЖЙКУАХЙНАИЕЬВ ЙЦЛ ККФЩУЮИЙЧ З ЬЦСЙВГЫХ СОЗЖЪНШШО ЛЪЯД ЦСЗНКЕШЛГЫХ ЦЩЗШО ЦСПЛЛТП С ЧАХЙВЩ ЮЙЦСЗХФС КЗСАХЦЩ СЙФФЗШО ЛЪЯД РЛЬНГЫХЪЖ ДПХЛЕЗ НФЧГХЛ ШЙ ШУЩ ЮОЕЛХЧУЛУ ЩКЯЙЛЩНКЫЭА ЕЧРЮЗЫГЧЖФЖ ЩЦ ЧРШЙЛЩМ ДЛВОЖЫРО КЙЯЛЫОЖЧЖФПШЙЪНХ ХЙЕЩЖ СЪСШ СЬЛРНГ ШПРТЗПЗН ЧЕЧУЦЖЪЕЩУС РЫСОНШЙ ЩЩТЖЛТЕЗ СЪСПХЛ СПРЬЛЕСЧШЙЪНХЩ ЪЙУЖЫЬЛ ЯЧВАЕЧИ ЩРЩТ ОЕФЖЫХЪЖ ДХЩЩЩХОВХЮДФ ЩРЩТ Щ ЗМУВ ЫЩГЕПЫЛЖПЯЛЩ Е ШУБЭЫЛЯЖ ЛЩДФСНБЮСЖ ШПБВЩ КЛЩА УОРЧЙ С ЛЪЯД Р ЮЯЙЭЩИЙЯЩ ЭЧНЛЯДФ ДЙРЧБЩЫРО ЫФЖ НЖЫФМ ЕРУЛКФТЕЗ У ЬЩУ ЧНШЙЪЖЧКИ ЧЩЫЙЕЧЗАФДЭСФ ЮЙНЭЩСЦТА З СЪСШ РГФПЛТ З ЙЪЬЛЕО ЛР ИОСЩХ АФЧЭЧ ЩЮЯОЧАИОЬШЙО ЦСЙМУБУХЬЛЖ ЪЩНЖЩСБЮСФ НЗНГЯХСЮАКУЛА ЬЙЧБМС Л ГЖФФШПШУБЕФФШЮЧФ ЛЪЬЮАЮСФ НИИ ДЛЯЧЫЛ ЙЩЪБЮСОЛЕЙЬШЙТ СЩЬЦЛ НЖЫФМ Е НФЧКУЩЕ КЙЧК ЮОЩФЦЧЧЩУЧ УБЬЦЩЛЪЩГЖЗО ЛЪЯ ЫГЯ ЭЙЕ ЧЙФПЯЙ ШУЩ ОЫЛР АЪВЛЕСЖР ЪЬЧАХ ЧААКШФЦЖЦГ НЖЫЖЕ ЕЧОЕЙПЬЛКЫП ЩЮЫФСЖЪЬЛТ С РЛЫОУУПЫФТГЦЩМ ЫОЖЧЖФПШЙЪНЩ УЦЩЪЙЧАСПРЛА ХСЦЛЕ ЛЛНЙЛ ЗЛЯХ ЛЪЯ ЦФЩЬКФУЮЧ ЕБЭ ЦФЩЬКФУЮЧ ЯШЙМЩЛЪЩГЖЗО СЩЬЦЛ ЯЙЫЩСАЗ ЩШЗ ЧНСППГЫХ УГЯ ЮОЛЖЪОСШЙ ХЬЛРЧЩФЯЙОЩЖ ЦФДУЧНСД ЦГ ЗЮОЫШЩЗ РРЙПФДХЕ ЛЪЯ ЧЧШЙМЩ ЧЗШГ ЕЙНФТЗ

Частотный анализ:
Встречаемость букв в тексте

Всего букв 1036

А -- 26

Б -- 15


В -- 11

Г -- 21


Д -- 20

Е -- 36


Ж -- 42

З -- 31


И -- 13

Й -- 56


К -- 23

Л -- 70


М -- 10

Н -- 33


О -- 36

П -- 25


Р -- 28

С -- 54


Т -- 15

У -- 36


Ф -- 45

Х -- 32


Ц -- 31

Ч -- 57


Ш -- 35

Щ -- 72


Ъ -- 32

Ы -- 35


Ь -- 27

Э -- 11


Ю -- 30

Я -- 28


Расшифрование. Легальный получатель знает период, располагает принятую шифрограмму в матрицу, применяет к каждому столбцу соответствующий ключ и расшифровывает сообщение.
Дешифрование. Криптоаналитик должен сначала определить период, преобразовать шифрограмму в матрицу для предполагаемого периода и использовать для каждого столбца методы криптоанализа моноалфавитных шифров. При неудаче следует изменить предполагаемый период.

Для нахождения периода чаще всего используются Метод Касиски, Автокорреляционный метод и Метод индекса совпадений. Для данного шифротекста надо использовать все методы, а затем переходить к дешифрованию, начиная с наиболее правдоподобного периода.


Метод Касиски состоит в том, что в шифртексте находятся одинаковые сегменты длин не меньше 3 и вычисляются расстояния между началами последовательных сегментов. Далее находится наибольший общий делитель этих расстояний. Предполагаемый период является кратным этого делителя.
В рассматриваемом примере:
Группа СЪС встречается в позициях 1, 373, 417, 196. Соответствующие расстояния равны 372=(4)(3)(31), 44 = (4)(11) и 196 = (4)(49). Наибольший общий делитель равен 4. Делаем вывод, что период кратен 4.
Группа ЩГЖ встречается в позициях 5, 781, 941. Соответствующие расстояния равны 776=(8)(97) и 160 = (32)(5). Делаем вывод, что период кратен 8, что не противоречит выводу для предыдущей группы (кратен 4).
Группа ЫРО встречается в позициях 13, 349, 557. Соответствующие расстояния равны 336=(16)(3)(7) и (4)(53). Делаем вывод, что период кратен 4.

Правдоподобным является предположение, что период равен 4.
Автокорреляционный метод состоит в том, что исходный шифртекст выписывается в строку, а под ней выписываются строки, полученные сдвигом вправо на t =1, 2, 3, ... позиций. Для каждого t подсчитывается число индексов таких, что . Вычисляются автокорреляционные коэффициенты . Для чисел t, кратных периоду, коэффициенты должны быть заметно больше, чем для сдвигов, не кратных периоду.

Пример. Для рассматриваемой криптограммы выделим те значения t, для которых . Получим ряд чисел


[].

Все эти числа делятся на 4.



Правдоподобно, что период равен 4.
Метод индекса совпадений. Для последовательности из букв алфавита из A букв индексом совпадения называется вероятность того, что два случайных элемента этой последовательности совпадают. Экспериментально индекс совпадений приближенной равен

где число появлений буквы i в последовательности x.

Период можно определить по формуле

где -- частота появления буквы I в естественном языке.



Пример. В рассматриваемой криптограмме для облегчения приведены числа . Для русского языка A=32, Проведя вычисления, получаем



Правдоподобно, что период равен 4.
Далее проводим 4 раза анализ моноалфавитных шифров (здесь этот этап опускается). В Примере на этом все заканчивается. В других случаях может быть, что период все же определен неверно. Тогда следует испытать значения периода на 1 меньше или на 1 больше.
скачать файл



Смотрите также:
Исходный открытый текст разбивается на последовательные группы длины, где период, выбираемый криптографом и держащийся в секрете
90.18kb.
Алгоритм преобразования Фурье длины 50 разобьем как представлено на ри
123.28kb.
Определение длины световой волны при помощи интерференционных колец
47.17kb.
Отчет о выполненной работе Постоянной рабочей группы по реализации демографической политики в Республике Коми за период апрель – сентябрь 2013 года
77.38kb.
в этом уроке говорится о пророчестве, описывающем период времени, в котором будут править искупленные вместе со Христом
46.83kb.
Бразилия 167 Где наибольшее количество итальянских и немецких поселений было в период эмиграции
56.51kb.
Роман Глушков
4909.77kb.
Текст подготовлен к посвященному проблеме миграции заседанию Рабочей группы «Гражданское общество» в рамках Российско-Американской президентской комиссии по развитию сотрудничества 27 мая 2010 г
157.2kb.
Реферат История Узбекистана
199.37kb.
Решение Исследуем на абсолютную сходимость
18.44kb.
Методические материалы Текст. Основные категории и свойства текста
166.2kb.
Меры длины, площади, массы, объема, применяемые в различных странах
339.37kb.