Книга Джордж и код, который не взломать - Люси Хокинг

10 – так в шестнадцатеричной системе записывается число 16;

11 – это 17;

1F – это 31 (то есть 1 x 16 плюс F × 1 (15));

20 – это 32 (2 × 16);

F7 – это 247 (F × 16 (15 × 16 = 240) плюс 7 × 1);

100 – это 256.

Взлом кода

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

В докомпьютерную эру

До появления цифровых компьютеров шифровальщики работали с буквами или же с цифрами, заменявшими буквы. Например, можно было заменить каждую букву в сообщении другой буквой. В простом коде буква А заменялась на Д, Б заменялась на Е и так далее. Или же расположение букв в алфавите изменялось определённым образом.

При расшифровке такого сообщения имело смысл подсчитать, сколько раз та или иная буква появляется в зашифрованном тексте (это называется частотный анализ), а затем угадать какие-то из замен. Например, мы знаем, что буква «о» встречается в очень многих словах, так что если в зашифрованном тексте часто попадается буква «ч», то можно предположить, что она заменяет букву «о». А учитывая, что в сообщении всегда присутствует смысл, одной верной догадки может оказаться достаточно, чтобы правильно определить остальные замены.

В более сложных шифрах для каждой буквы сообщения могут применяться комбинации букв алфавита, и возможности для шифрования очень широки: так, если в алфавите 33 буквы, то для шифрования первой буквы комбинации могут составляться из 33 букв, для второй – из 32 букв, для третьей – из 31 и так далее.

Современная дешифрация сообщений

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

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

ВЗЛОМ КОДА (+ 1 БУКВА) ГИМПН ЛПЕБ

ДЖОРДЖ (+ 3 БУКВЫ) ЖЙСУЖЙ

АННИ (− 1 БУКВА) ЯММЗ

– Вот это да! – воскликнула Анни, отрывая взгляд от телефона. – Значит, вы могли читать тайные послания, а те, кто их писал, понятия не имели, что вы в курсе их планов? Это как если бы кто-то сейчас прочитал все мои мейлы… Хотя, конечно, я ни с кем не воюю, – добавила она. – Разве что с Карлой Кусзанос, которая надо мной издевалась, когда я неправильно написала что-то на доске…

– Именно, – кивнула Берил. – Мы перехватывали их послания, расшифровывали и таким образом узнавали их планы. И это давало нам огромное преимущество.

– Круто! – восхитилась Анни. – Уважуха, Берил! – И она снова принялась печатать на телефоне.

– Это что, настоящая «Энигма»? – Джордж пожирал машину глазами. В доме Беллисов появилось очередное умопомрачительное устройство! Он в миллионный раз пожалел, что родился у своих мамы с папой, а не у Беллисов.

– Да, – сказала Берил, улыбаясь ему. – И я дарю её Эрику.

Энигма

Военные тайны

Во время Второй мировой (1939–1945) воюющие страны для шифрования важных сообщений использовали машины. В Германии это была машина «Энигма», в Британии – «Тайпекс».

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

Три ротора

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

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

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

Универсальная машина тьюринга

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

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

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

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