Список криптограмм/игры

История

Основная статья: История криптографии

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

Леон Баттиста Альберти

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

С началом использования частотного анализа для вскрытия моноалфавитных шифров в IX веке, появилась необходимость в изменении частоты появления символов обычного текста. С этой целью стал применяться однозвучный шифр подстановки, сутью которого было сопоставление нескольких заменяющих символов одной букве пропорционально частоте появление этой буквы в различных текстах. Секретарь антипапы Клемёнтия VII Габриель де Лавинда в XV веке впервые использует омофоны для обеспечения равномерной частоты гласных букв. Спустя 65 лет Леон Баттиста Альберти подробно описывает однозвучный шифр подстановки в своей книге «Трактат о шифрах». Основной проблемой распространения омофонической замены была необходимость использования расширенного алфавита для зашифровки сообщений.

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

В 1854 году английским физиком Чарльзом Уитстоном публикуется полиграммный шифр, впоследствии названный именем лорда Лайона Плейфера. Данный шифр осуществляет замену пар букв (биграмм) на одиночные символы, что значительно увеличивает его криптостойкость к частотному анализу.

С появлением ЭВМ полиалфавитные и полиграммные шифры отошли на второй план, а на смену им пришли новые более надежные блочные шифры.

Многоалфавитные замены[править | править код]

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

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

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

Многоалфавитная замена

a b c z

является ключом шифра замены .

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

А Б В Г Д Е Ж З И Й К М Н О П Р
21 37 14 22 01 24 62 73 46 23 12 08 27 53 35 04
40 26 63 47 31 83 88 30 02 91 72 32 77 68 60 44
10 03 71 82 15 70 11 55 90 69 38 61 54 09 84 45
С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я
20 13 59 25 75 43 19 29 06 65 74 48 36 28 16
52 39 07 49 33 85 58 80 50 34 17 56 78 64 41
89 67 93 76 18 51 87 66 81 92 42 79 86 05 57

то сообщение «я знаком с шифрами замены» может быть зашифровано, например, любым из следующих трех способов:

16 55 54 10 69 09 61 89 29 90 49 44 10 08 02 73 21 32 83 54 74
41 55 77 10 23 68 08 20 66 90 76 44 21 61 90 55 51 61 83 84 42
57 30 27 10 91 68 32 20 80 02 49 45 40 32 46 55 40 08 83 27 42

Такой вид кодирования, называется шифрование методом «`многоалфавитной«` подстановки.

Литература

Книги и монографии
  • Саймон Сингх. Книга шифров. Тайная история шифров и их расшифровки. — АСТ, 2007. — ISBN 978-5-17-038477-8.
  • Брюс Шнайер. Секреты и ложь. Безопасность данных в цифровом мире. — Издательский дом «Питер», 2003. — 368 с. — ISBN 5-318-00193-9.
  • В. В. Ященко. Введение в криптографию. — МЦНМО, 2012. — 348 с. — ISBN 978-5-4439-0026-1.
  • А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. Основы криптографии: Учебное пособие. — Гелиос АРВ, 2002. — 480 с. — ISBN 5-85438-025-0.
  • А.В. Бабаш, Г.П. Шанкин. Криптография. — Солон-пресс, 2007. — 512 с. — ISBN 5-93455-135-3.
  • Брюс Шнайер. Прикладная криптография = Applied Cryptography / Перевод с английского Дубнова Н.. — 2-ое. — Диалектика, 2003. — 610 с. — ISBN 5-89392-055-4.
  • Reinhard Wobst. Cryptology Unlocked. — Wiley, 2001. — ISBN 978-0470060643.
  • А.В. Бабаш, Г.П. Шанкин. История криптографии. Часть I. — Гелиос АРВ, 2002. — 240 с. — ISBN 5-85438-043-9..
  • Дэвид Кан. Взломщики кодов = The Codebreakers – The Story of Secret Writing / Перевод с английского А. Ключевский. — 2-ое. — М.: Центрполиграф, 2000. — 473 с. — ISBN 5-227-00678-4.
  • В.А. Долгов, В.В. Анисимов. Криптографические методы защиты информации. — ДВГУПС, 2008. — 155 с.
  • Т.А. Соболева. История шифровального дела в России.. — ОЛМА-ПРЕСС Образование, 2002. — 511 с. — ISBN 5-224-03634-8.
  • Н. Смарт. Криптография = Cryptography / Перевод с английского С.А. Кулешова. — Техносфера, 2005. — 528 с. — ISBN 5-94836-043-1.
  • Э.М. Габидулин, А.С. Кшевецкий, А.И. Колыбельников. Защита информации: учебное пособие. — МФТИ, 2011. — 255 с. — ISBN 5-7417-0377-9.
Отдельные статьи и главы
  • Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 19—22. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

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

Основная статья: Криптоанализ

Известный американский криптограф Брюс Шнайер выделяет четыре 4 основных метода криптоанализа:

  1. Атака на основе шифротекста
  2. Атака на основе открытых текстов
  3. Атака на основе подобранного открытого текста
  4. Атака на основе адаптивно подобранного открытого текста

Опишем криптостойкость шифров подстановки относительно данных методов.

Атаки на основе шифротекста

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

Криптоанализ однозвучных шифров подстановки осуществляется подсчетом частот появления пар и троек символов.

Для дешифровки полиалфавитных шифров применяется метод Касиски.

Полиграммный шифр Хилла может быть взломан при вычислении частот последовательностей символов.

Атаки на основе открытых текстов

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

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

Атаки на основе подобранного открытого текста

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

Стандартный шифр Хилла, составленный из n линейных уравнений, может быть взломан по выбранному открытому тексту при перехвате криптоаналитиком n² пар символов сообщения и шифротекста.

Практика: Задание 1

Метод 2: SubstitutionCipherDecryption

Автором данной статьи на просторах интернета была найдена интересная и удобная(на взгляд автора) программа SubstitutionCipherDecryption.exe

Загружаем текст в программу

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

При нажатии «AutoAssign» программа автоматически подставит ОЧЕВИДНЫЕ совпадения. Остальное легче сделать руками. Мы легко можем догадаться, что, допустим, THE — самое частое слово из 3 букв. Т.е. выбрав статистику слов из 3 букв мы сразу увидим очевидную замену

Метод 3 (От Создателя таска):

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

(т.е. левый столб = частоты нашего сообщения, правый = стандартные частоты)

«Энигма»

Всем известно, что «Энигма» — это главная шифровальная машина нацистов во время II мировой войны. Строение «Энигмы» включает комбинацию электрических и механических схем. То, каким получится шифр, зависит от начальной конфигурации «Энигмы». В то же время «Энигма» автоматически меняет свою конфигурацию во время работы, шифруя одно сообщение несколькими способами на всем его протяжении.

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

Взломать «Энигму» активно пытались в течение всей военной кампании Гитлера. В Англии в 1936 г. для этого построили один из первых вычислительных аппаратов (машина Тьюринга), ставший прообразом компьютеров в будущем. Его задачей было моделирование работы нескольких десятков «Энигм» одновременно и прогон через них перехваченных сообщений нацистов. Но даже машине Тьюринга лишь иногда удавалось взламывать сообщение.

Азбука Морзе

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

Телеграф и азбука Морзе… Морзе был тем, кто первый запатентовал «свое» изобретение в 1840 году, хотя до него и в России, и в Англии были изобретены подобные аппараты. Но кого это теперь интересует… Телеграф и азбука Морзе оказали очень большое влияние на мир, позволив почти мгновенно передавать сообщения на континентальные расстояния.

Транспозиционные или перестановочные шифры

Данные виды шифра простой перестановки более серьезны и активно применялись не так давно. В Гражданскую войну в США и в Первую мировую его использовали для передачи сообщений. Его алгоритм заключается в перестановке букв местами — записать сообщение в обратном порядке или попарно переставить буквы. Например, зашифруем фразу «азбука Морзе — тоже шифр» -> «акубза езроМ — ежот рфиш».

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

Зачем изучать старые шифры?

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

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

Зачем же нам знакомиться с такими древними и нестойкими шифрами, если можно сразу прочитать про DES и RSA — и вуаля, почти специалист? Изучение первых шифров поможет лучше понять, зачем нужна та или иная операция в современном алгоритме шифрования. Например, шифр перестановки, один из первых примитивных алгоритмов, не был забыт, и перестановка — одна из часто встречающихся операций в современном шифровании. Таким образом, чтобы лучше осознать, откуда на самом деле растут ноги у современных алгоритмов, нужно оглянуться на несколько тысяч лет назад.

Применение в наше время

Несмотря на вытеснение шифров подстановки блочными шифрами, одноразовые блокноты по-прежнему применяются на государственном уровне в наше время. Они используются для обеспечения сверхсекретных каналов связи. По слухам, телефонная линия между главами СССР и США шифровалась с помощью одноразового блокнота и вполне возможно существует до сих пор

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector