Стивен Хокинг: Джордж и код, который не взломать

Три ротора

У «Энигмы» было три ротора – три колеса, начинённые сложными электросхемами. Роторы можно было вынимать из машины и вращать таким образом, чтобы каждый из трёх можно было поставить в любую из 26 возможных позиций (26 – число букв английского алфавита). Таким образом, имелось шесть (3 × 2 × 1) способов взаимного расположения роторов и 26 × 26 × 26 позиций для каждой буквы. Чтобы ещё усложнить эту систему, можно было подключить к передней панели до десяти коротких проводков, и каждый из способов подключения создавал полностью новую систему из 26 × 26 × 26 шифров для сообщения. У получателя сообщения была своя «Энигма», настроенная точно таким же способом, и он вводил в неё зашифрованное сообщение. Записывая, какие лампочки загорались, можно было прочесть исходный текст. Каждый оператор «Энигмы» ежедневно узнавал, куда и в какое положение нужно поставить какой ротор и какие провода подключать к передней панели.

Взлом «Энигмы»

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

Воображаемое устройство

В 1936 году «компьютером», то есть «вычислителем», называли не машину, а человека, который что-то вычисляет. Машина Тьюринга, придуманная гениальным математиком Аланом Тьюрингом, – воображаемое устройство, способное воспроизводить всё, что делает в хо де расчётов человек-компьютер. То есть машина Тьюринга – не реальный прибор, а математическое устройство, позволяющее понять, что такое вычисление и чего можно достичь путем вычислений. В реальности такой машины быть не может: например, у неё должны быть и бесконечная «память», и неограниченное время работы, а ни то, ни другое невозможно.

Цепочка нулей

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

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

• изменить прочитанный символ на 0 или 1; сдвинуться по ленте на одну позицию влево или вправо; возможно, перейти в другое состояние; ждать следующего тиканья;

• сделать всё то же, после чего остановиться (отключиться).

Что именно сделает процессор, зависит от правил («программы»), которые мы зададим, и от того, что он прочтёт на ленте. Предположим, что машина начинает работу в состоянии 0, с длинной цепочкой нулей на ленте, и где-то справа несколько нулей заменены единицами – эти единицы образуют в двоичной системе число, которое мы даём машине в качестве входных данных.

Тогда правило для начала работы выглядит так: если в состоянии 0 мы читаем 0 – перейти в состояние 0, написать 0 и перейти вправо.

Это означает, что если вначале машина видит 0 (находясь в состоянии 0), она остаётся в состоянии 0, не изменяет запись 0 на ленте и переходит на шаг вправо. Если следующий знак – опять 0, повторяется то же самое: машина остаётся в состоянии 0, не делает отметок на ленте и передвигается ещё на шаг вправо.