Цилиндр Джефферсона (Enlnu;j :'yssyjvkug)

Цилиндр Джефферсона — шифратор, придуманный Томасом Джефферсоном, состоящий из 36 дисков, на каждый из которых нанесен алфавит из 26 букв (не по порядку), диски надеты на одну ось и могут вращаться вокруг неё.

История создания

Цилиндр Джефферсона — один из первых современных шифраторов, созданный Джефферсоном между 1790 г. и 1800 г. Джефферсон назвал свою систему шифрования «дисковым шифром». Сам он не был уверен в надежности своего изобретения, поэтому относился к нему с осторожностью и, будучи президентом США, не использовал его, а продолжил применять традиционные коды и шифры. Он поддерживал связь с математиком Р. Паттерсеном, для того, чтобы тот проанализировал это изобретение^[1]. Так как Джефферсон не навязывал своё изобретение к использованию, довольно скоро оно попало в архив. В XX веке, когда изобретение нашли и вновь о нём вспомнили, оно было признано как очень стойкое к криптоанализу шифровальное устройство, а самого Джефферсона назвали «отцом американского шифровального дела».

Принцип работы

Конструкция шифратора такова: деревянный цилиндр надет на ось и разрезан на 36 дисков, на каждый из этих дисков нанесен английский алфавит в произвольном порядке, диски могут вращаться независимо друг от друга. Над поверхностью цилиндра выделяется линия, под которой будет собираться открытый текст. Текст, который необходимо зашифровать разбивается на блоки по 36 символов. Первая буква блока находится на первом диске и фиксируется под выделенной линией, вторая — на следующем диске и т. д. Зашифрованный текст считывается с любой другой строки, кроме строки открытого текста. Расшифрование осуществляется на таком же шифраторе: шифротекст составляется под выделенной линией, открытый текст ищется среди параллельных линий, путём отыскания осмысленного сообщения. Теоретически возможно отыскание осмысленного текста в нескольких строчках, на практике же, такой текст находился только в одной строке; а даже если осмысленный текст можно было найти в нескольких строках, то на следующем шаге (на следующем блоке из 36 букв), строка, по которой нужно читать открытый текст, определяется однозначно. Ключом является порядок расположения букв на каждом из дисков и порядок дисков на оси^[1]. Количество ключей очень велико: $(25!)^{36}\cdot (36!)$ . Даже если допустить, что сам цилиндр мог попасть в руки к злоумышленнику, то количество ключей по-прежнему остается очень большим: $(36!)=371.993.326.789.901.217.467.999.448.150.835.200.000.000.$ Порядок цилиндров периодически менялся: один порядок мог использоваться для одного или нескольких сообщений, или не меняться в течение дня.

Пример шифра

В книге Secret History: The Story of Cryptology (2013), Craig P. Bauer, приведен данный шифр:

Этот шифр создан в 1915 году криптографом армии США, и, на данный момент, он до сих пор не расшифрован. Бауэром была выдвинута гипотеза, что этот шифр был создан с помощью шифратора Джефферсона, поэтому его так и не смогли расшифровать.^[2].

Аналоги

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

Цилиндр Базери

В конце XIX века изобретение повторил Этьен Базери. Его цилиндр состоял из 20 дисков, на каждый из которых были нанесены 25 символов английского алфавита. Его изобретение отказались использовать, назвав слишком сложным и в применении, и в изготовлении. Базери упростил своё изобретение, объявив порядок букв не секретным, и для простоты запоминания этот порядок легко образовывался из фраз-лозунгов. Это упрощение сильно ослабило шифр, он стал не надежным, что показал маркиз де Виари, вскрыв его. Шифр Базери так и не был принят^[1].

Шифратор Хитта

В начале XX века идея была повторена Паркером Хиттом со ссылкой на Базери, здесь вместо цилиндров использовались полоски^[1].

М-94

В 20-х годах XX века идею вновь повторили в США, признали её стойкой, приняли на вооружение и создали машину М-94. Машина состояла из 25 тонких дисков с алфавитом, вращающихся на оси длиной 110 мм. Она использовалась в американской армии с 1922 г. по 1943 г.^[3]

Прибор Вави

В 1916 году изобретение было повторено в России. Изготовил его подпоручик Попазов, позднее оно было названо «Прибор Вави». Строение устройства было аналогично устройству цилиндра Джефферсона, но вместо дисков использовались 20 колец, надетых вплотную друг к другу на цилиндр. На 18 колец наносился перемешанный алфавит из 30 букв, а на первое и последнее кольца — числа от 1 до 30. Ключом для данного прибора являлся набор: цифра, буква и «ключ шага» (две буквы). Для шифрования сообщение разбивалось на блоки по 17 символов, каждый блок зашифровывался отдельно. Сначала отыскивалось число, определяемое ключом, напротив него выставлялась буква, также являвшаяся ключом, напротив них в строку выстраивался блок открытого сообщения. Затем сообщение зашифровывалось: под ключевой буквой отыскивались две буквы «ключа шага», далее нечетные символы заменялись символами из строки, соответствующей первой букве «ключа шага», чётные — второй, то есть символы брались поочередно из разных строк. Данный шифратор имел одно значительное отличие от цилиндра Джефферсона — шифртекст выбирался единственным образом. Изобретение не имело широкого применения^[1].

Атака де Виари

В 1893 г. де Виари провел успешную атаку на цилиндр Базери. Атака строится на предположении, что злоумышленнику доступно устройство шифрования, то есть известен порядок букв на каждом диске. Также для атаки потребуется вероятное слово (то есть слово, которое с большой вероятностью встретится в открытом тексте), это слово не должно быть слишком длинным, чтобы не быть оборванным периодической сменой строк шифрования. Де Виари продемонстрировал свою атаку для цилиндра Базери и шифртекста Живержа (известно, что сообщение имеет военную тематику):

Пусть вероятным словом является «division». Множество встречающихся криптосимволов читаются вертикально под символами открытого текста. Так как расположение букв на дисках известно, то соответственно известно и на какую букву заменится буква открытого текста при сдвиге на определённое количество символов по диску. На рисунке приведены все возможные зашифрования каждого символа открытого текста, при сдвиге на 1 символ (слева), при сдвиге на 4 символа (справа).

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

Таким образом, зная этот порядок, можно расшифровать слова или их фрагменты в других строках шифртекста на тех же позициях. Например, в третьей строке расшифровывается слово «departas».

Следующее попадание (расшифрование ещё одной части шифртекста)

Для каждой строки могут быть разные сдвиги (для третьей строки сдвиг — 22). Зная французский, слово «departas» можно продолжить двумя способами «departasixheures» и «departaseptheures». Предполагаем, что 6 часов — это довольно рано и начинаем дальнейшую расшифровку с помощью слова «departaseptheures». Испытываем его обрывок «ptheures» в четвёртой строке.

Испытание предполагаемого окончания слова.

Это определяет положение ещё пяти дисков однозначно и трёх дисков неоднозначно (по два варианта).

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

Конец сообщения заполнен пустышками. Атака работает и при отсутствии вероятного слова, используя, например, стандартное для английского и французского языка окончания «ation»^[4].

Примечания

↑ ¹ ² ³ ⁴ ⁵ А. В. Бабаш, д.ф.-м.н., профессор, Ю. И. Гольев, Д. А. Ларин, к.т.н., Г. П. Шанкин, д.т.н., профессор Криптографические идеи XIX века — Журнал «Конфидент»
↑ Craig P. Bauer Secret History: The Story of Cryptology
↑ Ф. Бауэр. Методы и принципы криптологии — Мир, 2006 г. — С. 147—149
↑ Ф. Бауэр. Методы и принципы криптологии — Мир, 2006 г. — С. 306—311

См. также

Литература

Ф. Бауэр. Методы и принципы криптологии. — Мир, 2006. — 568 с.
Craig P. Bauer. Secret History: The Story of Cryptology. — Chapman and Hall/CRC, 2013. — 620 с.
David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Scribner, 1996. — 1200 с.
А. В. Бабаш, Ю. И. Гольцев, Д. А. Ларин, Г. П. Шанкин. Криптографические идеи XIX века // Конфидент : журнал. — 2004. — № 1. — С. 88—95. Архивировано 8 декабря 2014 года.

[Бабаш-1] ¹ ² ³ ⁴ ⁵ А. В. Бабаш, д.ф.-м.н., профессор, Ю. И. Гольев, Д. А. Ларин, к.т.н., Г. П. Шанкин, д.т.н., профессор Криптографические идеи XIX века — Журнал «Конфидент»

[2] Craig P. Bauer Secret History: The Story of Cryptology

[3] Ф. Бауэр. Методы и принципы криптологии — Мир, 2006 г. — С. 147—149

[bauer-4] Ф. Бауэр. Методы и принципы криптологии — Мир, 2006 г. — С. 306—311

[1]

[2]

[3]

[4]