Книга шифров. Тайная история шифров и их расшифровки



страница11/32
Дата24.08.2017
Размер4,62 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   32

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

Шифр из одноразового шифрблокнота свободен от всех вышеозначенных слабостей. Представим, что сообщение attack the valley at dawn было зашифровано, как показано на рисунке 30, передано по радио и перехвачено противником.

Криптоаналитик противника получает шифртекст и пытается дешифровать его. Первый камень преткновения: по определению в случайном ключе повторений нет, поэтому методом Бэббиджа и Касиски взломать криптографический ключ одноразового использования не удастся. Как вариант, криптоаналитик противника может попытаться подставлять слово the в различные места текста и определять соответствующий фрагмент ключа, как это делали мы, когда старались дешифровать предыдущее сообщение. Если криптоаналитик попробует поставить the в начале сообщения, что неверно, тогда соответствующий сегмент ключа будет иметь вид WXB, иначе говоря, он получит хаотичный набор букв. Если же криптоаналитик подставит the таким образом, что начало слова будет совпадать с седьмой буквой сообщения, то есть в нужное место, тогда соответствующий сегмент ключа будет иметь вид QKJ, что также является беспорядочным набором букв. Другими словами, криптоаналитик не сумеет определить, на своем месте стоит пробное слово или нет.

В отчаянии криптоаналитик мог бы даже подумывать о поиске методом полного перебора всех возможных ключей. Шифртекст состоит из 21 буквы, так что криптоаналитик знает, что и ключ также состоит из 21 буквы. Это означает, что следует проверить примерно 500 000 000 000 000 000 000 000 000 000 возможных ключей, что абсолютно неосуществимо ни для человека, ни для механического устройства. Однако даже если криптоаналитик смог бы проверить все эти ключи, то в этом случае возникнет еще более значительная сложность. Проверяя каждый возможный ключ, криптоаналитик, несомненно, обнаружит истинное сообщение, но будут также представлены и все ложные сообщения. Так, например, если применить к предыдущему шифртексту следующий ключ, то получится совершенно иное сообщение:

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

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

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

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

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

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

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

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

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

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

Усовершенствование шифровальных машин — от шифровальных дисков до «Энигмы»

Самым первым криптографическим устройством был шифровальный диск, придуманный в пятнадцатом веке итальянским архитектором Леоном Альберти, одним из отцов многоалфавитного шифра. Он взял два медных диска, один чуть шире другого, и нанес алфавит по краям обоих дисков. Поместив меньший диск сверху диска большего размера и скрепив их иглой, действующей как ось, он получил шифровальный диск, который показан на рисунке 31. Оба эти диска могут вращаться независимо друг от друга, так что оба алфавита могут занимать различное положение друг относительно друга и тем самым использоваться для зашифровывания сообщения с помощью простого шифра Цезаря. Например, чтобы зашифровать сообщение шифром Цезаря со сдвигом на одну позицию, установите А на наружном диске напротив В на внутреннем; наружный диск будет алфавитом открытого текста, а внутренний диск будет представлять шифралфавит. На наружном диске ищется буква из открытого текста сообщения, а соответствующая буква с внутреннего диска записывается как часть шифртекста. Чтобы зашифровать сообщение шифром Цезаря со сдвигом на пять позиций, просто поверните диски так, чтобы А на наружном диске стояла напротив Р на внутреннем, а затем пользуйтесь шифровальным диском в этом новом положении.

Рис. 31 Шифровальный диск, применявшийся конфедератами во время Гражданской войны в США.

Даже при том, что шифровальный диск был исключительно простым приспособлением, он существенно облегчил процесс шифрования и широко использовался целых пять столетий. На рисунке 31 приведен вариант конструкции шифровального диска, который применялся в Гражданской войне в США. На рисунке 32 показан кодограф — шифровальный диск капитана Миднайта, одноименного героя одной из первых американских радиопостановок. Слушатели программы могли получить собственный кодограф, написав организаторам программы — компании Ovaltine — и приложив этикетку от одной из упаковок. Время от времени программы заканчивались секретным сообщением от капитана Миднайта, которое могло быть расшифровано радиослушателями с помощью кодографа.

Рис. 32 Кодограф Капитана Миднайта, который зашифровывал каждую букву открытого текста (наружный диск) в виде числа (внутренний диск), а не буквы.

Шифровальный диск может рассматриваться как «скремблер», который берет каждую букву открытого текста и преобразует ее в некую другую букву. При том способе применения шифровального диска, который мы рассматривали до сих пор, взломать получающийся шифр довольно просто, однако существует возможность использования шифровального диска и более сложным образом. Его изобретатель, Альберти, предложил менять установку диска во время подготовки сообщения, что фактически означает применение многоалфавитного шифра вместо одноалфавитного. Так, чтобы зашифровать слово goodbye с помощью ключевого слова LEON, Альберти мог бы поступить следующим образом. Он бы начал с того, что установил диск по первой букве ключевого слова, совместив букву А на наружном диске с буквой L на внутреннем. Далее он бы зашифровал первую букву сообщения, g, отыскав ее на наружном диске и отметив соответствующую ей букву на внутреннем диске, R. Затем, чтобы зашифровать вторую букву сообщения, он бы установил диск по второй букве ключевого слова, совместив букву А на наружном диске с буквой Е на внутреннем. После чего зашифровал бы букву о, найдя ее на наружном диске и отметив соответствующую ей букву на внутреннем диске, S. Процесс шифрования продолжается: шифровальный диск последовательно устанавливается по буквам ключа — О, затем N, вслед за этим снова на L и так далее. Фактически Альберти зашифровал бы сообщение с помощью шифра Виженера, где в качестве ключевого слова использовалось его первое имя. Но если сравнивать с квадратом Виженера, то шифровальный диск ускоряет процесс зашифровывания и уменьшает количество ошибок.

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

В 1918 году немецкий изобретатель Артур Шербиус и его близкий друг Ричард Рйттер основали компанию Шербиус-энд-Риттер, конструкторскую фирму, которая занималась всем — от турбин до подушек с подогревом. Шербиус отвечал за проведение исследований и конструкторских работ и постоянно изыскивал новые возможности. Один из лелеемых им замыслов заключался в замене несовершенных систем криптографии, применявшихся в Первой мировой войне, когда обменивались шифрами, подготовленными вручную карандашом на бумаге, способом шифрования, в котором применялась бы технология двадцатого века. Изучив электротехнику в Ганновере и Мюнхене, он разработал криптографическое устройство, которое являлось по сути электрическим вариантом шифровального диска Альберти. Под названием «Энигма» изобретение Шербиуса станет самой грозной системой шифрования в истории.

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

Рис. 33 Упрощенный вариант «Энигмы» с алфавитом, состоящим всего из шести букв. Самым важным элементом машины является шифратор. При наборе на клавиатуре буквы b ток поступает в шифратор, проходит по проводам внутри него, а затем зажигает лампочку А. Короче говоря, b зашифровывается как А. Справа в прямоугольнике показано, как зашифровывается каждая из шести букв.

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

при наборе а будет высвечиваться буква В, которая означает, что а зашифрована как В,

при наборе b будет высвечиваться буква А, которая означает, что b зашифрована как А,

при наборе с будет высвечиваться буква D, которая означает, что с зашифрована как D,

при наборе d будет высвечиваться буква F, которая означает, что d зашифрована как F,

при наборе е будет высвечиваться буква Е, которая означает, что е зашифрована как Е,

при наборе f будет высвечиваться буква С, которая означает, что f зашифрована как С.

Сообщение cafe будет зашифровано как DBCE. По сути, при данной базовой схеме шифратор определяет шифралфавит, и в машине применяется простой одноалфавитный шифр замены.

Однако идея Шербиуса заключалась в том, чтобы после того, как очередная буква будет зашифрована, шифрующий диск автоматически поворачивался на 1/6 (или на 1/26, в случае, если используется алфавит из 26 букв). На рисунке 34 (а) показано то же самое устройство, что и на рисунке 33; и точно так же при наборе буквы b будет высвечиваться буква А. Однако на сей раз, сразу же после того, как будет набрана буква и загорится лампочка на панели, шифратор сделает 1/6 оборота и перейдет в положение, показанное на рисунке 34 (b). Здесь, если еще раз ввести букву b, загорится уже другая буква — С. Тотчас же шифратор повернется снова и окажется в положении, показанном на рисунке 34 (с). Теперь уже, если снова набрать букву b, высветится буква Е. Вводя букву b шесть раз подряд, мы получим шифртекст ACEBDC. Другими словами, шифралфавит меняется после каждого зашифровывания, и способ зашифровывания буквы b постоянно меняется. Вращающееся шифрующее устройство фактически задает шесть шифралфавитов, и в машине реализуется использование многоалфавитного шифра.

Рис. 34 Каждый раз после того, как на клавиатуре будет набрана и зашифрована буква, шифратор поворачивается на одну позицию, изменяя, тем самым способ, которым может быть зашифрована каждая буква. В (а) шифратор зашифровывает b как А, в (b) шифратор в новом положении зашифровывает b как С. В (с), после поворота на следующую позицию, шифратор зашифровывает b как Е. После того как будут зашифрованы еще четыре буквы и шифратор повернется еще на четыре позиции, он окажется в своем исходном положении.

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

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

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

Рис. 35 При добавлении второго шифратора комбинации зашифрованных символов не будут повторяться до тех пор, пока не будут зашифрованы все 36 букв, то есть пока оба шифратора не вернутся в исходное положение. Для простоты шифраторы представлены на диаграмме в двухмерном виде: здесь, вместо поворота на один шаг шифратора, на одну позицию вниз смещается распайка. Хотя создается впечатление, что провод (или провода) сверху или снизу шифратора обрывается, но на самом деле его продолжением служит соответствующий провод снизу или сверху этого шифратора. В (а) b зашифровывается как D. После зашифровывания первый шифратор поворачивается на одну позицию, заставляя при этом повернуться на одну позицию и второй шифратор; это происходит только раз за один полный оборот первого ротора. Это новое положение показано на (b), где b зашифровывается как F. После зашифровывания первый шифратор поворачивается на один шаг, но второй шифратор при этом остается неподвижным. Это новое положение показано на (с), где b зашифровывается как В.

Преимущество добавления второго шифратора заключается в том, что комбинации символов не будут повторяться до тех пор, пока второй шифратор не вернется в начальное положение, что потребует шести полных оборотов первого шифратора, то есть зашифровывания 6x6, или 36 букв. Другими словами, существует 36 различных положений шифратора, которые эквивалентны переходам между 36 шифралфавитами. Если же взять полный алфавит, состоящий из 26 букв, то шифровальная машина будет переключаться между 26 х 26, или 676 шифралфавитами. Поэтому объединяя несколько шифраторов (которые иногда называются роторами), можно создать шифровальную машину, которая будет постоянно выполнять переход между различными шифралфавитами.

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

Прежде чем приступить к подробному объяснению, как Шербиус предполагал применять свою шифровальную машину, необходимо рассказать еще о двух элементах «Энигмы», которые показаны на рисунке 36. Во-первых, в стандартной шифровальной машине Шербиуса в целях увеличения стойкости использовался третий шифратор; для полного алфавита из 26 букв эти три шифратора дают 26 х 26 х 26, или 17 576 различных положений шифраторов. Во вторых, Шербиус добавил отражатель. Отражатель, как и шифратор, также представляет собой резиновый диск с проводами внутри, но его отличие от шифратора состоит в том, что он не вращается, а провода входят с одной стороны и затем выходят с той же стороны. Когда отражатель установлен, оператор вводит букву, посылая электрический сигнал через три шифратора. Поступающий в отражатель сигнал отражается и идет обратно через те же три шифратора, но уже по другому пути. Например, для приведенной на рисунке 36 схемы, при вводе с клавиатуры буквы b сигнал пройдет через три шифратора, попадет в отражатель, отразится и вернется назад к букве D. На самом деле сигнал попадает не в клавиатуру, как это могло бы показаться из рисунка 36, а поступает на панель с лампочками.

Рис. 36 Конструкция «Энигмы» Шербиуса с третьим шифратором и отражателем, который направляет ток обратно через шифраторы. Для данного расположения ввод с клавиатуры буквы b приведет к загоранию D на панели с лампочками, которая показана рядом с клавиатурой.

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

Допустим, оператор хочет отправить криптограмму. Прежде чем приступить к шифрованию, оператор должен вначале повернуть шифраторы, установив их в определенное начальное положение. Существует 17 576 возможных расположений и, соответственно, 17 576 возможных начальных установок. Начальные положения шифраторов будут определять, каким образом зашифровывается сообщение. Мы можем рассматривать «Энигму» как обобщенную шифрсистему, в которой способ зашифровывания определяется начальными установками. Другими словами, начальные установки обуславливают ключ. Начальные установки обычно задаются в шифровальной книге, в которой указаны ключи на каждый день и которая имеется у всех в коммуникационной сети. Для распространения шифровальных книг требуется время и усилия, но поскольку в день нужен только один ключ, то можно, например, предусмотреть рассылку шифровальных книг, содержащих 28 ключей, только один раз в четыре недели. Для сравнения, если бы в войсках пришлось бы применять одноразовые шифрблокноты, то для каждого сообщения требовался бы новый ключ, и задача распределения ключей оказалась бы несоизмеримо сложнее. Как только шифраторы будут установлены в положения, задаваемые ключом текущего дня из шифровальной книги, отправитель может начинать зашифровывание. Он вводит с клавиатуры первую букву сообщения, смотрит, какая буква высвечивается на панели с лампочками, и записывает ее как первую букву шифртекста. Затем, как только первый шифратор автоматически повернется на одну позицию, отправитель вводит вторую букву сообщения и так далее. После того как шифртекст будет полностью подготовлен, он вручается радисту, который передает его получателю сообщения.



Поделитесь с Вашими друзьями:
1   ...   7   8   9   10   11   12   13   14   ...   32


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница