§3.2. История криптографии

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

Скитала и линейка Энея

Один из первых примеров устройств для шифрования в истории — это скитала. Её придумали в древней Спарте, и использовали в военных действиях. Скитала представляла собой стержень, на который плотно наматывалась лента из пергамента.

Оригинал: Eivind Lindbråten, CC-BY-SA 3.0

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

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

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

Чтобы зашифровать текст, нужно было завязать верёвку на начальной прорези и продеть её через отверстие, соответствующее нужной букве. Затем на верёвке завязывался узел, и нитка возвращалась в прорезь. Верёвку с завязанными узлами отправляли адресату с такой же линейкой. Тот завязывал её в начальную прорезь и, ориентируясь на расстояние между узлами, продевал верёвку в нужные отверстия снова, таким образом восстанавливая сообщение. Не имея копии линейки, восстановить сообщение было невозможно. По сути, такая линейка реализовывала шифр простой замены.

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

Шифры простой замены — это такие, где каждая буква в исходном сообщении заменялась на другую из заранее определённого алфавита. Например, вы договорились что буква А на самом деле означает букву Б во всём тексте, а буква Б — это буква Р. Не зная придуманного алфавита замены, не получится прочитать сообщение. В линейке Энея алфавиту замены соответствуют длины между узлами верёвки — каждая длина соответствует какой-либо букве.

Чтобы не передавать весь алфавит замены целиком, иногда выбирают какое-то правило, по которому он строится. Самым простым примером такого шифра является атбаш, когда алфавит «переставляется» задом наперёд (А превращается в Я, Б — в Ю и т.д.).

Другим известным ранним шифром простой замены является шифр Цезаря. в котором каждая буква алфавита сдвигается циклически на определённое число позиций. По легенде, шифр придумал Юлий Цезарь. Он пользовался сдвигом 3 вправо (например, заменял A на D). Для того времени шифр был достаточно стоек. Он применялся даже в 1915 году в российской армии, поскольку не удалось массово обучить войска более сложным шифрам. Сейчас этот шифр также называют ROT3, где 3 — размер сдвига вправо. Соответственно, другие шифры этого семейства называют ROT1, ROT13 и так далее.

Такие шифры были взломаны с открытием частотного анализа в IX веке нашей эры. Идея анализа в том, что в каждом языке существует известная вероятность использования определённых букв и их сочетаний. Например, отдельно стоящая буква Ч в предложении Ч РБМИЛЦ c большой вероятностью означает Я. Разбирая предложение таким образом, зная часто встречающиеся буквосочетания и пробуя их, сломать такой шифр просто — особенно когда примеров шифрованного текста много.

Для работы с такими шифрами можно использовать хороший сайт dcode.fr. На нём есть множество инструментов для работы с историческими шифрами. Например, на странице шифра Цезаря можно как просто шифровать и расшифровывать текст, так и подбирать нужный сдвиг автоматически методом перебора. Обратите внимание, что результат работы появляется в левой колонке сайта.

Полиалфавитные шрифты

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

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

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

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

Выводы

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

  2. Самый популярный пример шифра простой замены это шифр Цезаря, когда исходный алфавит в сообщении сдвигается. Традиционно используется сдвиг на 3 вправо. Обобщённо шифр называется ROTn, где n — размер сдвига алфавита.

  3. Для работы с простыми шифрами есть хороший сайт dcode.fr. Шифры простой замены легко поддаются частотному анализу.

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

  5. И главное: помните, что никогда нельзя полагаться на секретность вашего алгоритма шифрования. Секретным должен быть только ключ, но не алгоритм!

§3.3. Кодирование ⟶