Шифр простой замены примеры

Шифр простой замены примеры

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

Примеры шифров простой замены

Шифр Атбаш

Шифр простой замены, использованный для еврейского алфавита и получивший оттуда свое название. Шифрование происходит заменой первой буквы алфавита на последнюю, второй на предпоследнюю (алеф (первая буква) заменяется на тав (последнюю), бет (вторая) заменяется на шин (предпоследняя); из этих сочетаний шифр и получил свое название). Шифр Атбаш для английского алфавита:

Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Алфавит замены: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Шифр с использованием кодового слова

Шифр с использованием кодового слова является одним из самых простых как в реализации так и в расшифровывании. Идея заключается в том что выбирается кодовое слово, которое пишется впереди, затем выписываются остальные буквы алфавита в своем порядке. Шифр с использованием кодового слова WORD.

Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Алфавит замены: W O R D A B C E F G H I J K L M N P Q S T U V X Y Z

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

К шифрам замены тоже можно отнести всем известные шифры, используемые авторами многих известных книг. Таких как «Пляшущие человечки» А. Конан Дойла, или «Золотой Жук» Э. По, так же шифр из романа Ж. Верна «Путешествие к центру земли».

Безопасность шифров простой замены

Главный недостаток этого метода шифрования это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищенный способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это не часто делается. Несмотря на то, что число возможных ключей является очень большим (26! = 2^88.4), этот вид шифра может быть легко взломанным. Согласно расстоянию уникальности английского языка, 27.6 букв от зашифрованного текста должно быть достаточно чтобы взломать шифр простой замены. На практике, обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте может потребоваться куда более длинные шифротексты для взлома.

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

Омофоническая замена

Ранние попытки увеличивать трудность дешифровки частотным анализом шифров замены состояла в том, чтобы замаскировать реальные частоты появления символов обычного текста с помощью омофонии. В этих шифрах, буквы исходного алфавита соответствуют больше чем одному символу из алфавита замены. Обычно, символам исходного текста наивысшей частотой дают большее количество эквивалентов чем более редким символам. Таким образом, распределение частоты становится более равномерным, сильно затрудняя частотный анализ. С тех пор как для алфавита замены стало требоваться больше чем 26 символов появилась необходимость в расширенных алфавитах. Одним из самых простых решений является это замена алфавита на цифры. Другой метод состоит из простых изменений существующего алфавите: прописные буквы, строчные буквы, перевернутые символы и т. д. Более художественными, хотя не обязательно более надежными, будут омофонические шифры, которые используют полностью изобретенные (вымышленные) алфавиты. (например «Пляшущие человечки» А. Конан Дойла, или «Золотой Жук» Э. По. или «Рукопись Войнича»).

Примеры омофонических шифров

Номенклатор

Шифр, изданный средневековым чиновником, представляющий собой маленькую книгу с большими омофоническими таблицами замены. Первоначально шифр был ограничен названиям важных людей того времени, отсюда и последовало название шифра; в более поздних изданиях это шифр дополнился большим количеством распространенных слов и географических названий. На основе этого «номенклатора» был составлен Великий Шифр Россиньеля, используемый королем Франции Луи XIV. И действительно после того как этот шифр перестал использоваться французские архивы были закрытыми ещё в течение нескольких сотен лет. «Номенклаторы» были стандартом для дипломатической корреспонденции, шпионских сообщений, и являлись основыним средством антиполитической конспирации с начала пятнадцатого столетия до конца восемнадцатого столетия. Хотя правительственные криптоаналитики систематически взламывали «номенклаторы» к середине шестнадцатого столетия. Обычный выходом из этой ситуации было увеличение объемов таблиц. Но к концу восемнадцатого столетия, когда система начинала вымирать, некоторые «номенклаторы» имели до 50 000 символов. Однако, не все «номенклаторы» были сломаны.

Великий Шифр Россиньеля

Антони Россиньель и его сын Бонавентур Россиньель изобрели шифр, который использовал 587 различных числа. Шифр был настолько силен, что в течение многих столетий никто не мог взломать его, пока это не сделал Командир Птинье Базарье в 1893 году, который понял, что каждое число замещало французский слог, а не одну букву, как до этого считали. Он предположил, что специфическая последовательность повторных чисел, 124-22-125-46-345, кодирует слово «les ennemis» (враги) и отталкиваясь от этой информации он смог распутать весь шифр.

Книжный шифр

Книжный шифр — шифр, в котором ключом является книга или небольшая часть текста. Основным требованием будет, чтобы оба корреспондента не только имели одну и ту же самую книгу, но и тот же самое издание и выпуск. Традиционно книжные шифры работают заменяя слова в исходном тексте на местоположение этих же слов в книге. Это будет работать до тех пор пока не встретится слово, которого не будет в книге, тогда сообщение не может быть закодировано. Альтернативный подход, который обходит эту проблему, состоит в том, чтобы заменять отдельные символы, а не слова. Однако, такой способ имеет побочный эффект: зашифрованный текст становится очень большого размера. (обычно используется от 4 до 6 цифр для шифрования каждого символа или слога).

Именно это способ показан в начале фильма Семнадцать мгновений весны.

Криптоанализ

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

Однозвучные шифры сложнее для вскрытия, хотя они и не скрывают всех статистических свойств текста.

Многоалфавитные шифры шифруют каждый символ с помощью некоторого одноалфавитного шифра. Стойкость такого шифра сильно зависит от количества используемых шифров простой замены. Но при использовании компьютера криптоаналитик не испытает трудностей при вскрытии.

Шифр табличной замены. Шифр простой замены — один из древнейших. Прежде всего, выбирается нормативный алфавиту т.е. набор символов, которые будут использоваться для составления сообщений. В качестве нормативного алфавита может применяться, например, русский алфавит, исключая буквы «ъ» и «ё», дополненный символом пробела. Выбранный нормативный алфавит состоит из 32 символов.

Читайте также:  Как настроить вай фай на ноутбуке белтелеком

Затем выбирается алфавит шифрования <шифр-алфавит)укоторый может состоять из произвольных символов (цифр, букв, графических знаков), в том числе и из букв нормативного алфавита. Между нормативным алфавитом и алфавитом шифрования устанавливается взаимно-однозначное соответствие. Такое соответствие обычно задается таблицей и определяет секретный ключ шифра простой замены.

Шифрование заключается в замене каждого символа открытого текста на соответствующие символы шифр-алфавита.

В шифре простой замены каждый символ исходного текста заменяется символами шифр-алфавита одинаково на всем протяжении текста.

Пусть соответствие между нормативным и шифрующим алфавитом задано табл. 1.1 — это секретный ключ шифра. Требуется зашифровать слово «ЗВЕЗДА».

Пример табличной замены

Используя таблицу замены 1.1, можно получить криптограмму: Исходное сообщение: ЗВЕЗДА

Криптограмма: П С У П И Ф

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

8,6-10 36 — для русского, и выяснить ключ простым перебором становится практически невозможно. Вариантом такого шифра является замена букв на числа или некоторые символы (как, например, в рассказе А. Конан-Дойля «Пляшущие человечки»).

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

Рис. 1.12. Код «Квадрат Полибия» для греческого языка

Известно, что греки и римляне использовали для связи друг с другом семафорную систему, сообщения в которой кодировались но таблице Полибия, заполненной буквами по алфавиту.

При этом кодируемые символы заменяются соответствующими индексами строки и столбца. В исходном виде шифрование с помощью квадрата Полибия является нестойким. Однако если буквы алфавита занести в таблицу п X т в произвольном порядке (рис. 1.13), может быть получено (пт) возможных расположений букв (

2,6 • 10 32 для русского алфавита), что практически исключает возможность подбора ключа вручную.

Рис. 1.13. Варианты таблиц шифра «Квадрат Полибия»:

а — для английского языка; б — для русского языка

Например, слово «безопасность», зашифрованное вариантом шифра «Квадрат Полибия», изображенным на рис. 1.13, б, примет вид 31, 24, 44, 23, 33, 21,25, 13,23,35,53.

Квадрат Полибия использовался достаточно долгое время, чему способствовала его большая стойкость (при произвольном расположении букв в таблице).

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

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

Шифр индийских женщин. Одно из первых описаний шифров простой замены дано в «Камасутре». Согласно этому трактату, написанному в IV в. н.э., но базирующемуся на манускриптах IV в. до н.э., женщина должна овладеть 64 искусствами, среди которых — искусство тайнописи, предназначенное для того, чтобы помочь женщине скрыть подробности своих любовных связей. Один из рекомендуемых способов таков: следует случайным образом расположить попарно буквы алфавита, а потом заменять буквы исходного текста их парами. Пример одной из возможных таблиц подстановок для латинского алфавита, описывающей этот шифр, приведен на рис. 1.14.

Рис. 1.14. Шифр индийских женщин

Тогда вместо фразы «meet at midnight» («встретимся в полночь») отправитель напишет «cuuz vz cgxsgibz». Получатель сообщения должен иметь такую же таблицу подстановок и сделать обратное преобразование по таблице.

Шифрующая система Цезаря. Первое документально подтвержденное использование шифра замены в военных целях появилось в «Галльских войнах» Юлия Цезаря. Римский император Юлий Цезарь использовал этот шифр при переписке с Цицероном.

Шифр Цезаря (I в. н.э.) также является шифром простой замены, использующим следующее правило. Буква шифр-алфавита определялась путем смещения но нормативному алфавиту от исходной буквы на S позиций. При достижении конца алфавита выполнялся циклический переход к его началу. Таким образом, шифр-алфавит циклически сдвинут влево на S позиций относительно нормативного алфавита.

Цезарь использовал этот шифр замены при смещении .9 = 3. Такой шифр можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифротекста (рис. 1.15).

Рис. 1.15. Шифр Цезаря

Например, фраза «veni vidi vichi» («пришел увидел победил») будет записано с помощью этого шифра так: «yhgl ylgl ylfl». Расшифрование следует провести обратным смещением букв. Ключом шифрования в этом случае является постоянное значение смещения.

При использовании шифра Цезаря для латинского алфавита сдвиг S, являющийся ключом шифра, может принимать всего 25 различных значений (от 1 до 25). Значения сдвига 0 (или 26) не изменяет исходный алфавит.

С математической точки зрения шифрование сообщения с помощью шифра Цезаря, задающего фиксированный сдвиг исходного алфавита, записывается как

При этом <&„>— последовательность символов исходного текста в числовой кодировке, 0 1 буква «z» — наиболее часто встречающаяся наряду с «а» (16,7%), тогда как стандартная вероятность появления «z» в английском языке составляет всего 0,1% (0,001).

В длинных текстах (более 120 символов) частота появления букв будет приближаться к стандартной, хотя это происходит не всегда.

Поскольку частотное распределение конкретного текста может точно не совпадать с распределениями, указанными в частотной таблице, обычно приходится проверять несколько гипотез о соответствии букв шифротекс- та и букв открытого текста (например, «d» — «е», «I» или «а»; «Ь» — «е», «I» или «а»; « г » — «е», «I» или «а»?).

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

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

Пусть имеется криптограмма, полученная шифром табличной замены (рис. 1.17). Символы шифр-алфавита — двухзначные числа. В тексте криптограммы для простоты сохранены знаки препинания и пробелы между словами. Требуется определить исходный текст и ключ шифра (таблицу замен).

Подсчитаем частоты появления символов криптограммы (табл. 1.3).

Наиболее часто встречающиеся символы — эго 11, 16 и 14. Сопоставив их с частотами букв русского языка (рис. 1.16, б), можно сделать вывод, что, скорее

Частоты появления символов криптограммы, %

На протяжении многих веков люди придумывали хитроумные способы сокрытия информации — шифры, в то время как другие люди придумывали еще более хитроумные способы вскрытия информации — методы взлома.

Читайте также:  Расчет длины нихромовой проволоки на 220в

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

Шифр Цезаря

Самый легкий и один из самых известных классических шифров — шифр Цезаря отлично подойдет на роль аперитива.
Шифр Цезаря относится к группе так называемых одноалфавитных шифров подстановки. При использовании шифров этой группы «каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита» wiki.

Способы выбора ключей могут быть различны. В шифре Цезаря ключом служит произвольное число k, выбранное в интервале от 1 до 25. Каждая буква открытого текста заменяется буквой, стоящей на k знаков дальше нее в алфавите. К примеру, пусть ключом будет число 3. Тогда буква A английского алфавита будет заменена буквой D, буква B — буквой E и так далее.

Для наглядности зашифруем слово HABRAHABR шифром Цезаря с ключом k=7. Построим таблицу подстановок:

a b c d e f g h i j k l m n o p q r s t u v w x y z
h i j k l m n o p q r s t u v w x y z a b c d e f g

И заменив каждую букву в тексте получим: C(‘HABRAHABR’, 7) = ‘OHIYHOHIY’.

При расшифровке каждая буква заменяется буквой, стоящей в алфавите на k знаков раньше: D(‘OHIYHOHIY’, 7) = ‘HABRAHABR’.

Криптоанализ шифра Цезаря

Малое пространство ключей (всего 25 вариантов) делает брут-форс самым эффективным и простым вариантом атаки.
Для вскрытия необходимо каждую букву шифртекста заменить буквой, стоящей на один знак левее в алфавите. Если в результате этого не удалось получить читаемое сообщение, то необходимо повторить действие, но уже сместив буквы на два знака левее. И так далее, пока в результате не получится читаемый текст.

Аффиный шифр

Рассмотрим немного более интересный одноалфавитный шифр подстановки под названием аффиный шифр. Он тоже реализует простую подстановку, но обеспечивает немного большее пространство ключей по сравнению с шифром Цезаря. В аффинном шифре каждой букве алфавита размера m ставится в соответствие число из диапазона 0… m-1. Затем при помощи специальной формулы, вычисляется новое число, которое заменит старое в шифртексте.

Процесс шифрования можно описать следующей формулой:

,

где x — номер шифруемой буквы в алфавите; m — размер алфавита; a, b — ключ шифрования.

Для расшифровки вычисляется другая функция:

,

где a -1 — число обратное a по модулю m. Это значит, что для корректной расшифровки число a должно быть взаимно простым с m.

С учетом этого ограничения вычислим пространство ключей аффиного шифра на примере английского алфавита. Так как английский алфавит содержит 26 букв, то в качестве a может быть выбрано только взаимно простое с 26 число. Таких чисел всего двенадцать: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Число b в свою очередь может принимать любое значение в интервале от 0 до 25, что в итоге дает нам 12*26 = 312 вариантов возможных ключей.

Криптоанализ аффиного шифра

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

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

Т.е. в английском тексте наиболее встречающимися буквами будут E, T, A. В то время как самыми редкими буквами являются J, Q, Z. Следовательно, посчитав частоту появления каждой буквы в тексте мы можем определить насколько частотная характеристика текста соответствует английскому языку.

Для этого необходимо вычислить значение:

,

где ni — частота i-й буквы алфавита в естественном языке. И fi — частота i-й буквы в шифртексте.

Чем больше значение χ, тем больше вероятность того, что текст написан на естественном языке.

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

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

Шифр простой замены

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

При шифровании каждая буква в тексте заменяется по следующему правилу. Первая буква алфавита замещается первой буквой ключа, вторая буква алфавита — второй буквой ключа и так далее. В нашем примере буква A будет заменена на X, буква B на F.

При расшифровке буква сперва ищется в ключе и затем заменяется буквой стоящей в алфавите на той же позиции.

Криптоанализ шифра простой замены

Пространство ключей шифра простой замены огромно и равно количеству перестановок используемого алфавита. Так для английского языка это число составляет 26! = 2 88 . Разумеется наивный перебор всех возможных ключей дело безнадежное и для взлома потребуется более утонченная техника, такая как поиск восхождением к вершине:

  1. Выбирается случайная последовательность букв — основной ключ. Шифртекст расшифровывается с помощью основного ключа. Для получившегося текста вычисляется коэффициент, характеризующий вероятность принадлежности к естественному языку.
  2. Основной ключ подвергается небольшим изменениям (перестановка двух произвольно выбранных букв). Производится расшифровка и вычисляется коэффициент полученного текста.
  3. Если коэффициент выше сохраненного значения, то основной ключ заменяется на модифицированный вариант.
  4. Шаги 2-3 повторяются пока коэффициент не станет постоянным.

Для вычисления коэффициента используется еще одна характеристика естественного языка — частота встречаемости триграмм.
Чем ближе текст к английскому языку тем чаще в нем будут встречаться такие триграммы как THE, AND, ING. Суммируя частоты появления в естественном языке всех триграмм, встреченных в тексте получим коэффициент, который с большой долей вероятности определит текст, написанный на естественном языке.

Шифр Полибия

Еще один шифр подстановки. Ключом шифра является квадрат размером 5*5 (для английского языка), содержащий все буквы алфавита, кроме J.

При шифровании каждая буква исходного текста замещается парой символов, представляющих номер строки и номер столбца, в которых расположена замещаемая буква. Буква a будет замещена в шифртексте парой BB, буква b — парой EB и так далее. Так как ключ не содержит букву J, перед шифрованием в исходном тексте J следует заменить на I.

Например, зашифруем слово HABRAHABR. C(‘HABRAHABR’) = ‘AB BB EB DA BB AB BB EB DA’.

Криптоанализ шифра Полибия

Шифр имеет большое пространство ключей (25! = 2 83 для английского языка). Однако единственное отличие квадрата Полибия от предыдущего шифра заключается в том, что буква исходного текста замещается двумя символами.

Читайте также:  Трафарет буквы красивым шрифтом

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

Перестановочный шифр

Помимо шифров подстановки, широкое распространение также получили перестановочные шифры. В качестве примера опишем Шифр вертикальной перестановки.

В процессе шифрования сообщение записывается в виде таблицы. Количество колонок таблицы определяется размером ключа. Например, зашифруем сообщение WE ARE DISCOVERED. FLEE AT ONCE с помощью ключа 632415.

Так как ключ содержит 6 цифр дополним сообщение до длины кратной 6 произвольно выбранными буквами QKJEU и запишем сообщение в таблицу, содержащую 6 колонок, слева направо:

Для получения шифртекста выпишем каждую колонку из таблицы в порядке, определяемом ключом: EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE.

При расшифровке текст записывается в таблицу по колонкам сверху вниз в порядке, определяемом ключом.

Криптоанализ перестановочного шифра

Лучшим способом атаки шифра вертикальной перестановки будет полный перебор всех возможных ключей малой длины (до 9 включительно — около 400 000 вариантов). В случае, если перебор не дал желаемых результатов, можно воспользоваться поиском восхождением к вершине.

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

Шифр Плейфера

Шифр Плейфера — подстановочный шифр, реализующий замену биграмм. Для шифрования необходим ключ, представляющий собой таблицу букв размером 5*5 (без буквы J).

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

Зашифруем пару ‘WN’. Буква W расположена в первой строке и первой колонке. А буква N находится во второй строке и третьей колонке. Эти буквы образуют прямоугольник с углами W-E-S-N. Следовательно, при шифровании биграмма WN преобразовывается в биграмму ES.
В случае, если буквы расположены в одной строке или колонке, результатом шифрования является биграмма расположенная на одну позицию правее/ниже. Например, биграмма NG преобразовывается в биграмму GP.

Криптоанализ шифра Плейфера

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

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

Суть алгоритма сводится к следующим действиям:

  1. Выбирается случайная последовательность букв — основной-ключ. Шифртекст расшифровывается с помощью основного ключа. Для получившегося текста вычисляется коэффициент, характеризующий вероятность принадлежности к естественному языку.
  2. Основной ключ подвергается небольшим изменениям (перестановка двух произвольно выбранных букв, перестановка столбцов или строк). Производится расшифровка и вычисляется коэффициент полученного текста.
  3. Если коэффициент выше сохраненного значения, то основной ключ заменяется на модифицированный вариант.
  4. В противном случае замена основного ключа на модифицированный происходит с вероятностью, напрямую зависящей от разницы коэффициентов основного и модифицированного ключей.
  5. Шаги 2-4 повторяются около 50 000 раз.

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

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

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

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

Шифр Виженера представляет собой последовательность нескольких шифров Цезаря с различными ключами.

Продемонстрируем, в качестве примера, шифрование слова HABRAHABR с помощью ключа 123. Запишем ключ под исходным текстом, повторив его требуемое количество раз:

Цифры ключа определяют на сколько позиций необходимо сдвинуть букву в алфавите для получения шифртекста. Букву H необходимо сместить на одну позицию — в результате получается буква I, букву A на 2 позиции — буква C, и так далее. Осуществив все подстановки, получим в результате шифртекст: ICESCKBDU.

Криптоанализ шифра Виженера

Первая задача, стоящая при криптоанализе шифра Виженера заключается в нахождении длины, использованного при шифровании, ключа.

Для этого можно воспользоваться индексом совпадений.

Индекс совпадений — число, характеризующее вероятность того, что две произвольно выбранные из текста буквы окажутся одинаковы.
Для любого текста индекс совпадений вычисляется по формуле:

,

где fi — количество появлений i-й буквы алфавита в тексте, а n — количество букв в тексте.

Для английского языка индекс совпадений имеет значение 0.0667, в то время как для случайного набора букв этот показатель равен 0.038.
Более того, для текста зашифрованного с помощью одноалфавитной подстановки, индекс совпадений также равен 0.0667. Это объясняется тем, что количество различных букв в тексте остается неизменным.

Это свойство используется для нахождения длины ключа шифра Виженера. Из шифртекста по очереди выбираются каждая вторая буквы и для полученного текста считается индекс совпадений. Если результат примерно соответствует индексу совпадений естественного языка, значит длина ключа равна двум. В противном случае из шифртекста выбирается каждая третья буква и опять считается индекс совпадений. Процесс повторяется пока высокое значение индекса совпадений не укажет на длину ключа.

Успешность метода объясняется тем, что если длина ключа угадана верно, то выбранные буквы образуют шифртекст, зашифрованный простым шифром Цезаря. И индекс совпадений должен быть приблизительно соответствовать индексу совпадений естественного языка.
После того как длина ключа будет найдена взлом сводится к вскрытию нескольких шифров Цезаря. Для этого можно использовать способ, описанный в первом разделе данного топика.

Исходники всех вышеописанных шифров и атак на них можно посмотреть на GitHub.

Ссылка на основную публикацию
Что можно делать с айфоном
Не отвлекать оповещениями, когда вы смотрите кино или отдыхаете. Не беспокоить. Вы можете включить режим «Не беспокоить» одним касанием. И...
Хрипит динамик на телефоне при прослушивании
Одной из самых распространенных поломок мобильных аппаратов является выход из строя динамика. Любой пользователь мобильных телефонов знает, что сейчас производители...
Хэнкок из какой вселенной комиксов
Хэнкок Общая информацияЖанр Научная фантастика Драма Комедия Страна производстваСШАКиностудия Columbia Pictures РежиссёрПитер БергАвтор сценария Винс Джиллиган Винсент Нго Когда вышел2008...
Что можно сделать из перебойника от компьютера
Всем привет! В общем валялся у меня в гараже ненужный компьютерный безперебойник, сначала хотел его выбросит. но потом разобрав я...
Adblock detector