Саймон Сингх - Книга шифров .Тайная история шифров и их расшифровки
Математические таблицы рассчитывались вручную, а потому ошибки в них были просто результатом ошибок вычислений, выполняемых человеком. Это вынудило Бэббиджа воскликнуть: «Как бы мне хотелось, чтобы эти вычисления выполнялись паром!» Тем самым было положено начало попыткам построить машину, способную безошибочно вычислять таблицы с высокой степенью точности. В 1823 году Бэббидж разработал «разностную машину № 1» — великолепный вычислитель, состоящий из 25 000 точно подогнанных деталей, который предполагалось создать с помощью финансирования за счет государственных средств. Бэббидж был блестящим изобретателем, но никак не великим конструктором. После десяти лет тяжелого труда он отказался от «разностной машины № 1», придумал абсолютно новую конструкцию и принялся за создание «разностной машины № 2».
Когда Бэббидж отказался от своей первой машины, правительство потеряло в него веру и решило списать убытки, отказавшись от участия в проекте — оно уже и так потратило 17 470 фунтов, — достаточно, чтобы построить пару линкоров. Возможно, что именно этот отказ в поддержке побудил Бэббиджа позднее посетовать: «Предложите англичанину какую-нибудь идею или какой-нибудь инструмент, и, как бы она ни была превосходна, Вы увидите, что все усилия английского ума будут направлены на поиск в ней недостатков, изъянов или ее неосуществимости. Если Вы обсуждаете с ним машину для очистки картофеля, он заявит, что создать ее невозможно; если Вы очистите ею картофель перед его глазами, он объявит ее бесполезной, потому что она не режет ананас ломтиками».
Рис. 12 Чарльз Бэббидж
Отсутствие финансовой поддержки со стороны правительства означало, что Бэббидж никогда не сможет закончить «разностную машину № 2». Трагедия заключалась в том, что машина Бэббиджа являлась как бы ступенькой на пути создания аналитической машины.
Аналитическая машина могла не просто рассчитывать определенный набор таблиц, а решать различные математические задачи в зависимости от задаваемых ей инструкций. Фактически аналитическая машина являлась прототипом современных компьютеров. В ее конструкцию входили «хранилище» (память) и «мельница» (процессор), благодаря которым она могла принимать решения и повторять выполнение команд, что эквивалентно командам «If… then…» и «цикл» в современном программировании.
Столетием позже, во время Второй мировой войны, первые электронные воплощения машины Бэббиджа оказали значительное влияние на криптоанализ, однако и при жизни Бэббидж внес существенный вклад в этом направлении: ему удалось взломать шифр Виженера, и это стало величайшим достижением в криптоанализе с тех пор, как арабские ученые в девятом веке взломали одноалфавитный шифр, изобретя частотный анализ. Для этого Бэббиджу не потребовалось проводить никаких вычислений или сложных выкладок. Единственное, что оказалось необходимым, это сообразительность.
Бэббидж заинтересовался шифрами в очень юном возрасте. Позднее он вспоминал, как его детское увлечение временами доставляло ему неприятности: «Старшие ребята придумывали шифры, но если мне попадалось хотя бы несколько слов, то я, как правило, находил ключ. Последствия этого бывали подчас болезненны: владельцы раскрытых шифров иногда задавали мне трепку, хотя виной всему была их собственная глупость». Эти колотушки не обескураживали Бэббиджа; криптоанализ по-прежнему пленял его. В своей автобиографии он писал: «…дешифрование, на мой взгляд, является одним из самых захватывающих искусств».
Очень скоро он приобрел известность в лондонском обществе как дешифровальщик, готовый взяться за любое зашифрованное сообщение, и к нему стали обращаться со всевозможными задачами. Так, Бэббидж помог отчаявшемуся биографу, пытающемуся дешифровать стенографические записи Джона Флемстида, первого королевского астронома Англии. Он также пришел на помощь историку, разгадывающему шифр Генриетты-Марии, жены Карла I. В 1854 году Бэббидж сотрудничал с адвокатом и использовал криптоанализ, чтобы представить в судебном разбирательстве решающее доказательство. За эти годы он собрал значительную картотеку зашифрованных сообщений, которые он собирался использовать в качестве основы для авторитетной книги по криптоанализу под названием «Основные принципы дешифрования». В книге были бы даны по два примера каждого вида шифра; на одном из примеров было бы показано, как взломать шифр, а второй предназначался бы в качестве упражнения для читателя. К сожалению, как это случилось и со множеством других его грандиозных замыслов, книга не была закончена.
Несмотря на то что большинство криптоаналитиков уже оставили всякую надежду когда-либо взломать шифр Виженера, Бэббиджа побудил попытаться дешифровать его обмен письмами с Джоном Холом Бруком Твэйтсом, дантистом из Бристоля, имевшим довольно наивное представление о шифрах. В 1854 году Твэйтс заявил, что он придумал новый шифр, который по сути был аналогичен шифру Виженера. Он написал в «Джорнел оф зе Сэсайети оф Артс» с намерением запатентовать свою идею, явно не осознавая, что опоздал на несколько столетий. Бэббидж написал в журнал, указав, что «данный шифр… известен уже очень давно и его можно найти во многих книгах». Твэйтс был непримирим и потребовал от Бэббиджа, чтобы тот раскрыл его шифр. Можно ли было взломать этот шифр или нет, никак не зависело от того, был ли он старым или новым, но любопытство Бэббиджа было достаточно разбужено, чтобы попробовать найти слабое место в шифре Виженера.
Взламывание сложного шифра напоминает восхождение по обрывистой отвесной скале. Криптоаналитик стремится отыскать любую трещинку или выступ, которые могли бы дать хоть сколь-нибудь мельчайшую зацепку. В одноалфавитном шифре криптоаналитик будет отталкиваться от частотности появления букв, потому что чаще всего встречающиеся буквы, как, например, е, t и а, будут просто бросаться в глаза, независимо от того, как они были замаскированы. В многоалфавитном же шифре Виженера буквы появляются более равномерно, поскольку для перехода от одного шифралфавита к другому применяется ключевое слово. Поэтому на первый взгляд поверхность скалы кажется совершенно ровной.
Вспомните, что исключительная стойкость шифра Виженера обеспечивается тем, что одна и та же буква будет зашифрована различными способами. Например, если ключевым будет слово KING, тогда каждая буква в открытом тексте может быть зашифрована четырьмя различными способами, потому что в ключевом слове содержится четыре буквы. Как показано в таблице 7, каждая буква ключевого слова задает различные шифралфавиты в квадрате Виженера. Здесь в квадрате выделен столбец е, чтобы показать, почему зашифровывание, в зависимости от того, какой буквой ключевого слова задается шифрование, происходит различным образом:
Если для зашифровывания буквы е используется К из слова KING, то в шифртексте будет стоять буква О.
Если для зашифровывания буквы е используется I из слова KING, то в шифртексте будет стоять буква М.
Если для зашифровывания буквы е используется N из слова KING, то в шифртексте будет стоять буква R.
Если для зашифровывания буквы е используется G из слова KING, то в шифртексте будет стоять буква К.
Точно так же различными способами будут зашифрованы и цельте слова: слово the, например, в зависимости от его положения относительно ключевого слова, может быть зашифровано как DPR, BUK, CNO или ZRM. Хотя это и усложняет проведение криптоанализа, но он все же возможен. Следует отметить следующий важный, момент: если существует всего лишь четыре способа зашифровывания слова the, и если в исходном тексте это слово появляется несколько раз, то некоторые из этих четырех возможных зашифрованных слов почти наверняка встретятся в шифртексте. Это показано в следующем примере, где строка The Sun and the Man in the Moon была зашифрована с помощью шифра Виженера и ключевого слова KING.
Слово the зашифровывается как DPR в первом случае и как BUK во втором и третьем случаях. Причина повторного появления BUK заключается в том, что второе the отстоит от третьего the на восемь букв, а восемь кратно длине ключевого слова, которое состоит из четырех букв. Другими словами, второе the было зашифровано в соответствии с тем, как оно располагается относительно ключевого слова (the находится прямо под ING), и к тому моменту, как мы дойдем до третьего the, ключевое слово повторится точно два раза.
Таблица 7 Квадрат Виженера, применяемый совместно с ключевым словом KING. Ключевое слово задает четыре различных шифралфавита, так что буква е может быть зашифрована как О, М, R или К.
