Внебрачная статья. Криптоанализ. Часть 1. Начало.

Добрый день/вечер/ночь. Мы поздравляем вас с наступившим 2021 годом(Это было почти месяц назад. Зачем их снова поздравлять.) и с прошедшим днём Мынки. Вы этого не просили, но Мынка нас уговорил. Сегодня будет весело и интересно. Советуем вам перед прочтением ознакомится с прошлыми статьями. Ну на этом мы можем начинать. Вперёд исследовать глубины криптоанализа(Ужасная фраза).

Шифр Виженера

Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе определяется длина ключевого слова, на втором этапе — само ключевое слово.

Обозначим µ - длина ключевого слова. Для определения числа µ применяется так называемый тест Казиски, названный в честь Ф. Казиски(или Касиски, кому как нравится(Мои скоби! не используй их)), применившего его в 1863 г. Тест основан на простом наблюдении о том, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном µ, будут одинаково зашифрованы. В силу этого в шифротексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Стоить отметить то, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью.

Пусть

— найденные расстояния между повторениями и d — наибольший общий делитель этих чисел. Тогда µ должно делить d. Чем больше повторений имеет текст, тем более вероятно, что µ совпадает с d. Для уточнения значения µ, можно использовать так называемый индекс совпадения, введенный в практику У. Фридманом в 1920 г.

Для строки

длины m, составленной из букв алфавита

, индексом совпадения в х, обозначаемым

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

Пусть

Будем отождествлять буквы алфавита с числами, так что

Фридман предложил следующую Теорему: Индекс совпадения в х вычисляется по формуле

где

— число вхождений буквы

Доказать данную теорему мы предлагаем вам самим. Ну а мы продолжим.

Пусть х — строка осмысленного текста (например, английского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями

независимо друг от друга, где

— вероятность появления буквы i в осмысленном тексте.

В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с i равна

следовательно,

Взяв за основу значения вероятностей

для открытых текстов на английском языке, получаем приближение

Тем самым для английских текстов х можно пользоваться следующим приближением для индекса совпадения:

Аналогичные приближения можно получить и для других языков, приведем значения индексов совпадения для ряда европейских языков:

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

переставляются местами, но сумма

остается неизменной.

Продолжим. Пусть

данный шифротекст. Выпишем его с периодом µ:

Если µ это истинная длина ключевого слова, то каждый столбец

представляет собой участок открытого текста, зашифрованный простой заменой, определяемой подстановкой

для некоторого

В силу сказанного выше, (для английского языка)

при любом i. С другой стороны, если µ отлично от длины ключевого слова, то столбцы

будут более "случайными", поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфавитным шифром. Тогда

будет ближе (для английского языка) к числу

Заметная разница значений

для осмысленных открытых текстов и случайных последовательностей букв (для английского языка — 0.066 и 0.038, для русского языка — 0.053 и 0.030) позволяет в большинстве случаев установить точное значение µ.

Предположим, что на первом этапе мы нашли длину ключевого слова µ. Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его нахождения можно использовать так называемый взаимный индекс совпадения.

Пусть

— две строки букв алфавита

А теперь любимая рубрика Определения: Взаимным индексом совпадения х и у, обозначаемым

, называется вероятность того, что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.

Пусть

— числа вхождений букв алфавита в х и у соответственно.

Теорема: Взаимный индекс совпадения в х и у вычисляется по формуле

Эта формула доказывается аналогично прошлой, поэтому мы верим что вы и эту формулу докажите.

Пусть

— истинное ключевое слово. Попытаемся оценить индексы

Для этого напомним, что

является результатом зашифрования фрагмента открытого текста простой заменой, определяемой подстановкой рассмотренной выше при некотором s. Вероятность того, что произвольная пара букв из

равна букве

, имеет вид

где вероятность появления буквы а в открытом тексте

Вероятность того, что обе буквы есть

, имеет вид

и так далее. На основании этого получаем:

Заметим, что сумма в правой части последнего равенства зависит только от разности

, которую назовем относительным сдвигом

Заметим также, что

поэтому

с относительными сдвигами s и n-s имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм для последней формулы для английского языка:

Обратим внимание на то, что ненулевые "сдвиги" дают взаимные индексы совпадения, изменяющиеся в пределах от 0.032 до 0.045, в то время как при нулевом сдвиге индекс

близок к 0.066. Это наблюдение позволяет определить величины относительных сдвигов

столбцов

Для этого заметим, что при некотором значении

столбец

полученный из

прибавлением к каждому его элементу числа s(i, j) (по модулю n), имеет нулевой относительный сдвиг с

Пусть

– результаты зашифрования

каждой из простых замен рассмотренных выше. Несложно вычислить взаимные индексы

(всего, таким образом, имеется

значений). Для этого воспользуемся формулой, полученной из формулы вычисления взаимного индекса совпадений.

Если s равно

- (относительному сдвигу

), то взаимный индекс впадения должен быть (для английского языка) близок к 0.066, так как относительный сдвиг

равен нулю. Если же s не равно

то взаимный индекс совпадения должен колебаться в пределах 0.032 - 0.045.

Используя изложенный метод, мы сможем связать системой уравнений относительные сдвиги различных пар столбцов

В результате останется 26 (для английского языка) вариантов для ключевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным(в том случае если тот, кто шифровал не читал нашу прошлую статью)). Следует отметить, что предложенный метод будет эффективным для не слишком больших значений µ. Это объясняется тем, что для хороших сближений индексов совпадения требуются тексты достаточно большой длины

На этом теория заканчивается и мы переходим к

Практике

Решим простую задачу: Задан некоторый текст зашифрованный шифром Виженера, требуется определить ключевое слово и прочитать открытый текст .

Шифрованный текст:

влцдутжбюцхъяррмшбрхцэооэцгбрьцмйфктъъюьмшэсяцпунуящэйтаьэдкцибр ьцгбрпачкъуцпъбьсэгкцъгуущарцёэвърюуоюэкааэбрняфукабъарпяъафкъиьжяффнйо яфывбнэнфуюгбрьсшьжэтбэёчюъюръегофкбьчябашвёэуъъюаднчжчужцёэвлрнчулб юпцуруньъшсэюъзкцхъяррнрювяспэмасчкпэужьжыатуфуярюравртубурьпэщлафоуф бюацмнубсюкйтаьэдйюнооэгюожбгкбрънцэпотчмёодзцвбцшщвщепчдчдръюьскасэг ъппэгюкдойрсрэвоопчщшоказръббнэугнялёкьсрбёуыэбдэулбюасшоуэтъшкрсдугэфл бубуъчнчтртпэгюкиугюэмэгюккъъпэгяапуфуэзьрадзьжчюрмфцхраююанчёчюъыхьъ цомэфъцпоирькнщпэтэузуябащущбаыэйчдфрпэцъьрьцъцпоилуфэдцойэдятррачкубу фнйтаьэдкцкрннцюабугюуубурьпйюэъжтгюркующоъуфъэгясуоичщщчдцсфырэдщэ ъуяфшёчцюйрщвяхвмкршрпгюопэуцчйтаьэдкцибрьцыяжтюрбуэтэбдуящэубъибрюв ъежагибрбагбрымпуноцшяжцечкфодщоъчжшйуъцхчщвуэбдлдъэгясуахзцэбдэулькнъ щбжяцэьрёдъьвювлрнуяфуоухфекьгцчччгэъжтанопчынажпачкъуъмэнкйрэфщэъьбуд эндадъярьеюэлэтчоубъцэфэвлнёэгфдсэвэёкбсчоукгаутэыпуббцчкпэгючсаъбэнэфърк ацхёваетуфяепьрювържадфёжбьфутощоявьъгупчршуитеачйчирамчюфчоуяюонкяжы кгсцбрясшчйотъъжрсщчл

Решение(Не смотри пока сам не решил или смотри, проверять не будем):

Используем тест Казиски. В данном тексте обнаружено четырехкратное повторение буквосочетания «брь». Выясним расстояние между ними и найдем наибольший общий делитель этих расстояний.

В результате получаем: 35, 85, 510
НОД = 5;

Следовательно, с определенной долей вероятности можно заключить, что длина кодового слова равна 5.

Запишем шифротекст в таблицу с 5 столбцами, предполагая, что длина ключевого слова равна 5. Это поможет нам убедится, что мы верно определили длину ключевого слова.

Вычислим взаимные индексы совпадения

букв в каждом из столбцов таблицы. Для этого посчитаем частоту повторения букв в каждом столбце.

Частота повторения букв в столбцах:

1 столбец (общее количество букв m=198)

2 столбец (общее количество букв m=198)

3 столбец (общее количество букв m=198)

4 столбец (общее количество букв m=198)

5 столбец (общее количество букв m=197)

По полученным индексам совпадения можно сказать, что длина ключевого слова выбрана верно и равна 5.

После того как мы нашли длину ключевого слова произведем поиск его истинного значения. Для этого воспользуемся взаимным индекс совпадений. Взаимный индекс совпадения значения ключевого слова для русского языка должен находиться в приделах 0.053 – 0.07. И для его вычисления предварительно необходимо определить относительный сдвиг всех столбцов относительно первого.

Сдвиг 2-го столбца на 6 позиций

Сдвиг 3-го столбца на 3 позиции

Сдвиг 4-го столбца на 16 позиций

Сдвиг 5-го столбца на 3 позиции

По взаимным индексам совпадения можно судить что сдвиги между столбцами выбраны верно.

Составим уравнения для определения ключевого слова:

Теперь только необходимо вычислить значение g[1]:

Найдено ключевое слово «СЛОВО». Убедимся в этом и расшифруем зашифрованный текст:

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

Ключевое слово верное, текст читается.

Итог

Как вы заметили данный метод эффективен только если у вас длинный текст. Если же у вас текст не достаточно длинный, то у вас не получится использовать данный метод дешифровки.
После прочтения статьи вы могли задаться вопросом, а что делать если тот кто шифровал читал нашу прошлую статью и знает что не надо использовать осмысленное слово для ключа? Всё просто, для этого используют магию перебора. На этом мы завершаем статью, но перед этим вот вам небольшое задание: Задан некоторый текст зашифрованный шифром Виженера, требуется определить ключевое слово и прочитать открытый текст. При этом ключевое слово осмысленное, радуйтесь.

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

Стоит отметить, что некоторые переходы на новую строку являются пробелами. Для решения используйте данную таблицу Виженера:

Решения может присылать в сообщения сообщества. Первый n+1 человек кто решит получит «Молодец» от Мынки.

Если у вас появились вопросы мы с радостью ответим на них в комментариях или сообщениях группы.