Шифровальная решётка

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

Решётка Кардано и её различные варианты

Решётка Кардано была изобретена как метод секретной переписки. Криптография стала привычным термином для секретных посланий с середины 17-го века, до этого времени обычно употреблялось понятие стеганография. Другим универсальным термином для секретной переписки было слово шифр, которое на английском языке имело два варианта написания: cypher и cipher. В настоящее время существует различие между понятиями криптография и стеганография. Сэр Фрэнсис Бэкон установил три основных условия для шифров:

метод шифрования не должен быть сложным в использовании;
для посторонних лиц не должно быть возможности восстановить зашифрованный текст («дешифровать шифр»);
по возможности не должно возникать подозрения о наличии скрытого сообщения.

Исполнение всех трех условий требует серьёзных усилий и большого труда. Условие 3, относящееся к стеганографии, подразумевает, что зашифрованное сообщение в идеале вообще не должно выглядеть таковым. Именно этому условию решётка, изобретенная Кардано, в свое время отвечала наилучшим образом. Однако различные первоначальные варианты решётки Кардано не были специально разработаны для выполнения условия 3 и, как правило, не вполне соответствовали условию 2, поскольку возможность дешифровки текста, замаскированного с помощью любой шифровальной решётки, зависит от способностей и навыков криптоаналитиков. Привлекательность шифровальной решётки Кардано заключалась, прежде всего, в простоте её использования для пользователей, то есть в соответствии условию 1.

Однобуквенные решётки

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

Картонная решётка с восемью однобуквенными прорезями-ячейками.

В этом примере решётка имеет восемь неправильно (в идеале — хаотично) расположенных прорезей-ячеек. Их число соответствует количеству букв в ключевом слове TANGIERS. Решётка размещается на листе с сеткой (специально разлинованном листе бумаги), а буквы пишутся сверху вниз.

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

После удаления решётки сетка заполняется случайными буквами и цифрами. Чтобы прочитать скрытые буквы (в других вариантах — цифры и прочие знаки), нужно обладать авторской шифровальной решёткой или её копией. Зашифрованные знаки могут быть ключом к многоалфавитному шифру, подобному тому, который в то же время был предложен Джамбаттиста делла Порта.

Решётка и сетка хранятся отдельно. При наличии только одной копии решётки и одной копии сетки потеря любой из них — это потеря обеих.

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

Использование шифровальной решётки получило свое дальнейшее развитие в методе генерации псевдослучайных последовательностей из ранее существовавшего текста в связи с Рукописью Войнича. Область криптографии, занимающуюся извлечением тайного смысла из текстов, Дэвид Кан назвал энигматологией. Например, к ней относятся работы Джона Ди и шифры, предположительно встроенные в произведения Шекспира, доказывающие, что их написал Фрэнсис Бэкон. Последняя версия была изучена и опровергнута Уильямом Фридманом.^[1]

Сеточные шифры

Министр Елизаветы I, член Тайного совета, начальник разведки и контрразведки Англии, сэр Фрэнсис Уолсингем (1530—1590 годы) использовал шифровальную решётку, чтобы скрыть буквы открытого текста при общении со своими агентами. Однако обычно он предпочитал комбинированный метод, известный как номенклатор^{[уточнить]}, который был самым передовым методом шифрования в то время. Визуально номенклатор представлял собой инструмент перестановки, который создавал нечто похожее на зигзаговый шифр^[англ.] и напоминал шахматную доску.

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

После заполнения 32 букв доска поворачивается на 90 градусов по вертикали или горизонтали (результат один и тот же), то есть в правильное расположение для игры в шахматы (в левом верхнем углу находится белый квадрат), и записываются ещё 32 буквы. Для сообщений длиной более 64 букв требуется ещё один поворот доски и ещё один лист бумаги. Более короткие сообщения заполняются нулевыми буквами (т. н. дополнение). В каждом дополнительном квадрате ставится нуль, то есть все незаполненное знаками пространство заполняется нулями.

J M T H H D L I S I Y P S L U I A O W A E T I E E N W A P D E N E N E L G O O N N A I T E E F N K E R L O O N D D N T T E N R X

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

33, 5, 41, 13, 49, 21, 57, 29, 1, 37, 9, 45, 17, 53, 25, 61, 34, 6, 42, 14, 50, 22, 58, 30, 2, 38, 10, 46, 18, 54, 26, 62, 35, 7, 43, 15, 51, 23, 59, 31, 3, 39, 11, 47, 19, 55, 27, 63, 36, 8, 44, 16, 52, 24, 60, 32, 4, 40, 12, 48, 20, 56, 28, 64

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

Вращающиеся решётки

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

Решётка Фляйснера размером 8x8 перед прорезыванием ячеек.

Барон Эдуард Фляйснер фон Востровиц^[англ.], полковник австрийской кавалерии в отставке, в 1880 году описал вариант шифра на основе шахматной доски, и его решётки были приняты немецкой армией во время Первой мировой войны. Эти решётки часто называют в честь Фляйснера, хотя он использовал материалы из немецкой работы, опубликованной в Тюбингене в 1809 году, написанной Клюбером (Klüber), который, как и Элен Гейнс^[англ.], приписывал эту форму решётки Кардано^[2].

Бауэр отмечает, что похожие решётки использовались уже в XVIII веке, например, в 1745 году при администрации Штатгальтера Нидерландов Вильгельма IV. Позже в 1796 году математик К. Ф. Гинденбург изучил вращающиеся решётки более системно: «[эти решётки] часто называют решётками Фляйснера из-за незнания их исторического происхождения».

Одна форма решётки Фляйснера содержит 16 перфораций в решётке 8×8 — 4 отверстия в каждом квадранте. Если квадраты в каждом квадранте пронумерованы от 1 до 16, все 16 чисел должны использоваться для шифра только один раз, что обеспечивает большое число вариантов размещения отверстий.

Решётка имеет четыре позиции — север, восток, юг, запад. Каждая позиция дает возможность использовать 16 из 64 квадратов. Шифровщик помещает решётку на лист и записывает первые 16 букв сообщения. Затем, поворачивая решётку на 90 градусов, пишет вторые 16 и так далее, пока сетка не заполнится.

В принципе, можно построить решётки разных размеров; однако, если число квадратов в одном квадранте нечетное, даже если сумма является четным числом, один квадрант или секция должны содержать дополнительную прорезь-ячейку. Для иллюстрации решётки Фляйснера в качестве примера часто берут размер 6x6 в целях пространственной простоты; число прорезей-ячеек в одном квадранте равно 9, поэтому три квадранта содержат 2 прорези-ячейки, а один квадрант должен иметь 3. Стандартного шаблона для прорезей-ячеек не существует; они создаются пользователем в соответствии с приведенным выше описанием с целью создания «надёжного беспорядка», то есть сложно дешифруемого шифра.

Этот метод получил широкое признание, когда Жюль Верн использовал вращающуюся решётку в качестве сюжетного приема в своем романе «Матиас Шандор», опубликованном в 1885 году. Верн натолкнулся на эту идею в трактате Фляйснера «Справочник по криптографии», выпущенном в 1881 году.

Одну из многих вариаций решётки Фляйснера можно вращать по часовой стрелке или против часовой стрелки.

Решётки Фляйснера создавались в различных размерах во время Первой мировой войны и использовались немецкой армией в конце 1916 года^[3]. Каждая решётка имела свое кодовое название согласно последовательности букв в алфавите A, B, C, D, E, F: 5×5 — ANNA; 6×6 — BERTA; 7×7 — CLARA; 8×8 — DORA; 9×9 — EMIL; 10×10 — FRANZ. Однако надёжность шифрования с помощью решёток оказалась недостаточной, и через четыре месяца от их использования отказались.

Более надёжный метод указания размера используемой решётки состоял во вставке кода ключа в начале зашифрованного текста: E = 5; F = 6 и т. д., в соответствии с порядковым номером буквы в алфавите. Более того, усложнение дешифрование обеспечивалось тем, что решётку можно было вращать в любом направлении, и начальное положение не обязательно должно было быть NORTH. Очевидно, что рабочий метод передачи посланий заключается по договоренности между отправителем и получателем и может работать в соответствии с определённым графиком.

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

ПО ЧАСОВОЙ СТРЕЛКЕ

ITIT ILOH GEHE TCDF LENS IIST FANB FSET EPES HENN URRE NEEN TRCG PR&I ODCT SLOE

ПРОТИВ ЧАСОВОЙ СТРЕЛКИ

LEIT CIAH GTHE TIDF LENB IIET FONS FSST URES NEDN EPRE HEEN TRTG PROI ONEC SL&C

В 1925 году Луиджи Сакко^[англ.], служивший в итальянском корпусе военной связи, приступил к написанию книги о шифрах «Криптографические понятия» (Nozzioni di crittografia), которая включала исследование кодов Первой мировой войны. Он отмечал, что метод Фляйснера может быть применен к шифрам перемещения или транспозиционным, таким, как шифр Деластеля^[англ.], Bifid^[англ.] или шифр четырёх квадратов, при этом значительно повышается безопасность и надёжность шифра.

Шифры-решётки также являются полезным методом для переноса китайских иероглифов; с их помощью можно избежать транскрипции слов в буквенные или слоговые символы, к которым могут применяться другие шифры (например, шифры подстановки).

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

Необычные возможности

Шифр Д’Агапеева

Нерасшифрованный шифр Д’Агапеева^[англ.], который был задан в качестве криптографической задачи в 1939 году, содержит 14×14 диномов и, возможно, основывается на идее Сакко о переносе транспозиционного зашифрованного текста с помощью решётки.

Решётка третьей стороны: кроссворд

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

Решётка на основе кроссворда из газеты 1941 года

CTATI ETTOL TTOEH RRHEI MUCKE SSEEL AUDUE RITSC VISCH NREHE LEERD DTOHS ESDNN LEWAC LEONT OIIEA RRSET LLPDR EIVYT ELTTD TOXEA E4TMI GIUOD PTRT1 ENCNE ABYMO NOEET EBCAL LUZIU TLEPT SIFNT ONUYK YOOOO

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

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

Оригинальная решётка Кардано была эпистолярным приемом^{[уточнить]} в личной переписке джентльменов^[кого?]. Любое подозрение в её использовании могло повлечь за собой поиски и попытки обнаружения скрытых сообщений, даже когда скрытых сообщений не существовало, и эта неопределенность сбивала с толку криптоаналитиков^{[уточнить]}. Поскольку буквы и цифры в произвольной сетке могут принимать форму без содержания^{[уточнить]}, то получение копии шифровальной решётки являлось главной целью заинтересованной в расшифровке стороны.

В более поздних вариантах решётки Кардано возникают проблемы, которые являются общими для всех транспозиционных шифров. Частотный анализ показывает нормальное распределение букв и предлагает язык, на котором был написан открытый текст^[4]. Задача, которую легко сформулировать, хотя и не так легко решить, состоит в том, чтобы идентифицировать шаблон перестановки и таким образом расшифровать зашифрованный текст. Наличие нескольких сообщений, написанных с использованием одной и той же решётки, значительно облегчает задачу.

Элен Гейнс в работе по ручным шифрам и их криптоанализу подробно проанализировала транспозиционные шифры и посвятила главу вращающейся решётке^[2].

Примечания

↑ Friedman, William F. The Shakespearean Ciphers Examined (неопр.). — Cambridge University Press, 1957.
↑ ¹ ² Fouché Gaines, Helen. Cryptanalysis - a study of ciphers and their solution (англ.). — Dover, 1956. — P. 26—35. — ISBN 0-486-20097-3.
↑ Kahn, David. The Codebreakers — The Comprehensive History of Secret Communication from Ancient Times to the Internet (англ.). — 1996. — P. 308—309. — ISBN 0-684-83130-9.
↑ Pommerening, Klaus Cryptology — Commentary on Verne's Mathias Sandorf (неопр.) (2000). Дата обращения: 15 ноября 2013. Архивировано 2 декабря 2013 года.

Литература

Richard Deacon, A History of the British Secret Service, Frederick Mũller, London, 1969
Luigi Sacco, Nozzioni di crittografia, privately printed, Rome, 1930; revised and reprinted twice as Manuale di crittografia
Friedrich L. Bauer Decrypted Secrets — Methods and Maxims of Cryptology, Springer-Verlag, Berlin Heidelberg, 1997, ISBN 3-540-60418-9
Schneider, Matthias The Turning Grille Toolset (неопр.) (30 марта 2004). Дата обращения: 30 мая 2006. Архивировано из оригинала 22 сентября 2005 года.
Savard, John J. G. Methods of Transposition (неопр.). A Cryptographic Compendium (1998). Дата обращения: 15 ноября 2013.

Ссылки

Grille (неопр.). Classic Cryptography. ThinkQuest. Дата обращения: 15 ноября 2013. Архивировано из оригинала 13 декабря 2012 года.
Matthews, Robert A. J Notes on the D'Agapeyeff Cipher (неопр.). Дата обращения: 15 ноября 2013. Архивировано из оригинала 31 октября 2013 года.

[1] Friedman, William F. The Shakespearean Ciphers Examined (неопр.). — Cambridge University Press, 1957.

[GAINES-2] ¹ ² Fouché Gaines, Helen. Cryptanalysis - a study of ciphers and their solution (англ.). — Dover, 1956. — P. 26—35. — ISBN 0-486-20097-3.

[3] Kahn, David. The Codebreakers — The Comprehensive History of Secret Communication from Ancient Times to the Internet (англ.). — 1996. — P. 308—309. — ISBN 0-684-83130-9.

[4] Pommerening, Klaus Cryptology — Commentary on Verne's Mathias Sandorf (неопр.) (2000). Дата обращения: 15 ноября 2013. Архивировано 2 декабря 2013 года.

[1]

[2]

[3]

[4]