Джордж и код, который не взломать
Шрифт:
Десятичная
Система, которой мы обычно пользуемся при счёте – десятичная система, – имеет основание 10, по числу цифр от 0 до 9.
Мы считаем от 1 до 9 и переходим к следующему разряду – десяткам. Например:
36 = 3 x 10 плюс 6 x 1;
48 = 4 x 10 плюс 8 x 1;
148 = 1 x 100 плюс 4 x 10 плюс 8 x 1
и так далее.
Двоичная
В первых компьютерах применялась двоичная система счисления. Она названа так потому, что её основание – число 2: это значит, что в ней есть только две цифры – 0 и 1.
10 = 1 x 2 плюс 0 x 1 – то есть число 2 в десятичной системе;
11 = 1 x 2 плюс 1 x 1 – то есть число 3;
111 = 1 x 4 плюс 1 x 2 плюс 1 x 1 – то есть число 7.
В микросхемах первых компьютеров было всего два положения: «выключено» и «включено»; поэтому двоичный код – код, основанный на двоичной системе, – хорошо подходил для вычислений: ноль в ней соответствовал положению «выключено», а единица – «включено».
Шестнадцатеричная
Современные компьютеры намного сложнее, и код часто пишут в шестнадцатеричной системе счисления с основанием 16. Счет идёт от 0 до 9, а дальше 10 обозначается буквой A, 11 – буквой B и так далее до буквы F (то есть до 15).
Следовательно, C обозначает 12 из десятичной системы.
10 – так в шестнадцатеричной системе записывается число 16;
11 –
1F – это 31 (то есть 1 x 16 плюс F x 1 (15));
20 – это 32 (2 x 16);
F7 – это 247 (F x 16 (15 x 16 = 240) плюс 7 x 1);
100 – это 256.
Взломом обычно называют расшифровку сообщений, когда у расшифровщика нет доступа к секретному ключу, которым пользовался отправитель. Другое название этого процесса – криптоанализ.
В докомпьютерную эру
До появления цифровых компьютеров шифровальщики работали с буквами или же с цифрами, заменявшими буквы. Например, можно было заменить каждую букву в сообщении другой буквой. В простом коде буква А заменялась на Д, Б заменялась на Е и так далее. Или же расположение букв в алфавите изменялось определённым образом.
При расшифровке такого сообщения имело смысл подсчитать, сколько раз та или иная буква появляется в зашифрованном тексте (это называется частотный анализ), а затем угадать какие-то из замен. Например, мы знаем, что буква «о» встречается в очень многих словах, так что если в зашифрованном тексте часто попадается буква «ч», то можно предположить, что она заменяет букву «о». А учитывая, что в сообщении всегда присутствует смысл, одной верной догадки может оказаться достаточно, чтобы правильно определить остальные замены.
В более сложных шифрах для каждой буквы сообщения могут применяться комбинации букв алфавита, и возможности для шифрования очень широки: так, если в алфавите 33 буквы, то для шифрования первой буквы комбинации могут составляться из 33 букв, для второй – из 32 букв, для третьей – из 31 и так далее.
Современная дешифрация сообщений
Современные методы применимы не только к буквам, но и к битам (единицам и нолям). При зашифровке и дешифровке используется секретный ключ, который представляет собой длинную последовательность битов (единиц и нолей).
256-битный ключ считается в наши дни вполне достаточным для того, чтобы помешать взломщику кода, сидящему за суперкомпьютером, найти ключ «лобовым методом» – полным перебором возможных вариантов.
ВЗЛОМ КОДА (+ 1 БУКВА) ГИМПН ЛПЕБ
ДЖОРДЖ (+ 3 БУКВЫ) ЖЙСУЖЙ
АННИ (- 1 БУКВА) ЯММЗ
– Вот это да! – воскликнула Анни, отрывая взгляд от телефона. – Значит, вы могли читать тайные послания, а те, кто их писал, понятия не имели, что вы в курсе их планов? Это как если бы кто-то сейчас прочитал все мои мейлы… Хотя, конечно, я ни с кем не воюю, – добавила она. – Разве что с Карлой Кусзанос, которая надо мной издевалась, когда я неправильно написала что-то на доске…
– Именно, – кивнула Берил. – Мы перехватывали их послания, расшифровывали и таким образом узнавали их планы. И это давало нам огромное преимущество.
– Круто! – восхитилась Анни. – Уважуха, Берил! – И она снова принялась печатать на телефоне.
– Это что, настоящая «Энигма»? – Джордж пожирал машину глазами. В доме Беллисов появилось очередное умопомрачительное устройство! Он в миллионный раз пожалел, что родился у своих мамы с папой, а не у Беллисов.
– Да, – сказала Берил, улыбаясь ему. – И я дарю её Эрику.
Военные тайны
Во время Второй мировой (1939–1945) воюющие страны для шифрования важных сообщений использовали машины. В Германии это была машина «Энигма», в Британии – «Тайпекс».
Оператор «Энигмы» печатал послание на клавиатуре, расположенной в передней части машины, а машина выдавала зашифрованный текст, указывая на каждую закодированную букву вспыхиванием маленькой электрической лампочки. Зашифрованное сообщение записывали от руки, переводили в азбуку Морзе и затем передавали по радио.
Три ротора
У «Энигмы» было три ротора – три колеса, начинённые сложными электросхемами. Роторы можно было вынимать из машины и вращать таким образом, чтобы каждый из трёх можно было поставить в любую из 26 возможных позиций (26 – число букв английского алфавита). Таким образом, имелось шесть (3 x 2 x 1) способов взаимного расположения роторов и 26 x 26 x 26 позиций для каждой буквы. Чтобы ещё усложнить эту систему, можно было подключить к передней панели до десяти коротких проводков, и каждый из способов подключения создавал полностью новую систему из 26 x 26 x 26 шифров для сообщения. У получателя сообщения была своя «Энигма», настроенная точно таким же способом, и он вводил в неё зашифрованное сообщение. Записывая, какие лампочки загорались, можно было прочесть исходный текст. Каждый оператор «Энигмы» ежедневно узнавал, куда и в какое положение нужно поставить какой ротор и какие провода подключать к передней панели.
Взлом «Энигмы»
Шифровальная система была основана на секретной информации, известной отправителю и получателю. В случае «Энигмы» это были ежедневные инструкции по настройке и использованию машины, и задача заключалась в том, чтобы надёжно передать их большому числу людей. Ошибка любого из них привела бы к утечке важной информации. Инструкции в печатном виде тоже были уязвимы – их могли похитить или захватить в бою. Благодаря нескольким ошибкам немцев, достижениям математики и творческому мышлению, взломщики кода – сначала в Польше, а позже в Блетчли-Парке в Англии – сумели распознать настройки машин «Энигма» и получили возможность расшифровывать немецкие сообщения. Важнейшим элементом этого метода была особая машина, которую сконструировал гений математики Алан Тьюринг; эту машину называли «бомбой Тьюринга». В Блетчли-Парке также был разработан «Колосс» – первая программируемая вычислительная машина на электронных лампах; с помощью «Колосса» взломали код другой немецкой шифровальной машины, которая называлась «Лоренц».
Воображаемое устройство
В 1936 году «компьютером», то есть «вычислителем», называли не машину, а человека, который что-то вычисляет. Машина Тьюринга, придуманная гениальным математиком Аланом Тьюрингом, – воображаемое устройство, способное воспроизводить всё, что делает в хо де расчётов человек-компьютер. То есть машина Тьюринга – не реальный прибор, а математическое устройство, позволяющее понять, что такое вычисление и чего можно достичь путем вычислений. В реальности такой машины быть не может: например, у неё должны быть и бесконечная «память», и неограниченное время работы, а ни то, ни другое невозможно.
Цепочка нулей
Действие, выполняемое машиной, описывается конечным списком зашифрованных инструкций. Представим себе очень длинную ленту, на которой написана очень длинная цепочка нулей (такая же длинная, как сама лента). Эта лента, которая тянется бесконечно в обоих направлениях (предположим, что она бесконечно длинная), – «память» вычислительной машины. Между нулями вкраплено конечное число единиц – они представляют введённые в машину «данные». На ленте установлено управляющее устройство (процессор). Процессор может читать ровно один символ, проходящий через него в данный момент, и может либо ничего с ним не делать, либо заменить на 0 или 1.
Процессор также включает в себя часовой механизм, который ритмично тикает, и с каждым тиканьем процессор читает символ, который видит в данный момент. Затем он может сделать одно из двух – в зависимости от того, что он прочёл, и от своего текущего состояния. Он может:
• изменить прочитанный символ на 0 или 1; сдвинуться по ленте на одну позицию
• сделать всё то же, после чего остановиться (отключиться).
Что именно сделает процессор, зависит от правил («программы»), которые мы зададим, и от того, что он прочтёт на ленте. Предположим, что машина начинает работу в состоянии 0, с длинной цепочкой нулей на ленте, и где-то справа несколько нулей заменены единицами – эти единицы образуют в двоичной системе число, которое мы даём машине в качестве входных данных.
Тогда правило для начала работы выглядит так: если в состоянии 0 мы читаем 0 – перейти в состояние 0, написать 0 и перейти вправо.
Это означает, что если вначале машина видит 0 (находясь в состоянии 0), она остаётся в состоянии 0, не изменяет запись 0 на ленте и переходит на шаг вправо. Если следующий знак – опять 0, повторяется то же самое: машина остаётся в состоянии 0, не делает отметок на ленте и передвигается ещё на шаг вправо.
Всё это повторяется с каждым тиканьем часов, пока наконец машина не достигнет первой единицы на ленте. Теперь требуется правило, объясняющее, что делать, когда процессор читает 1 в состоянии 0. Простейшим правилом будет: оставаться в состоянии 0, записать 1, перейти на шаг вправо и остановиться. Теперь слева от машины будет записана единица, и это будет результат вычисления.
Этот алгоритм можно описать как «печатать 1, если входные данные корректны», где «корректны» означает «содержат по меньшей мере одну единицу». Если бы на момент начала работы справа от управляющего устройства не было ни одной единицы, она бы никогда не остановилась, а продолжала бы движение в вечном и бесплодном поиске единицы. Такое может произойти и с настоящим компьютером: программа может «зациклиться», и в конце концов компьютер сломается.
К сожалению, такая возможность – неотъемлемое свойство и машины Тьюринга, и реальных компьютеров. Однако этого легко избежать, если изначально указать, что среди «корректных» входных данных должна быть по меньшей мере одна единица, так, чтобы первое правило не могло применяться до бесконечности.
Тьюринг также математически показал, что даже машина Тьюринга не может решить все задачи! Иными словами, некоторые задачи в математике не решаются с помощью вычислительной техники – то есть математиков пока нельзя заменить машинами.
Любое возможное вычисление
Если есть достаточно времени и есть возможность записать на ленте ввода нужное число единиц, то выполнимо любое механическое действие с целыми числами, какое только можно придумать. Для этого требуется дать машине Тьюринга входное число справа от машины, запустить часы, дождаться остановки – и прочесть ответ слева от машины. К таким действиям относится любой арифметический расчёт, какой может произвести человек с помощью ручки и бумаги. Алан Тьюринг предложил такое определение вычислимого: вычислимо то, что может вычислить машина Тьюринга. Удивительно, но спустя примерно 80 лет это определение по-прежнему считается верным: все известные компьютеры могут выполнять вычисления только в пределах возможностей машины Тьюринга.
Эрик ахнул. Она явно не предупредила его о своих намерениях.
– Нет, вы не можете… – начал он.
– Очень даже могу, – твёрдо сказала Берил. – Я дарю её вашему математическому факультету. Вы, с вашими работами по квантовым компьютерам, – самый подходящий человек для такого подарка. Так что лучшее место для неё и придумать трудно.
– Что такое квантовый компьютер? – насторожился Джордж. Для него это была новость. Он давно обратил внимание на то, что Эрик в последнее время стал очень скрытен. На вопросы о том, над чем он сейчас работает, выдающийся учёный отвечал туманно и уклончиво.
Однако сегодня Эрик оказался существенно говорливее, чем обычно.
– Это очередной прорыв, – ответил он Джорджу. – Уже произошла цифровая революция в мире информации, а теперь мы стоим на пороге квантовой революции. Если мы сумеем создать квантовый компьютер – и не только создать, но и управлять им, что в данный момент кажется чрезвычайно сложным, – то сможем делать многое из того, что при нынешнем уровне компьютерных технологий выглядит совершенно непредставимым.
– Например? – спросил Джордж.
– С помощью квантового компьютера можно взломать любой код – на Земле не существует системы ограничения доступа, которая могла бы его остановить! – сказал Эрик, сияя. – И тогда мы сможем делать просто невероятные вещи в области обработки данных, в медицине, физике, машиностроении, математике. Это будет очередной гигантский прорыв в науке.
– Но при чём тут «Энигма»? – спросил Джордж.
– При том, – ответила Берил, – что «Энигма» – предшественница множества поразительных технологий. И важно, что «Энигма» на самом деле существует и доказала свою действенность. А квантовый компьютер на данный момент ещё не действует, поскольку не существует.
– Да! – Эрик рассмеялся. – Моя нынешняя работа по большей части состоит в исправлении ошибок в квантовых вычислениях…
– Кстати, – Берил указала на Эрика, – перед вами единственный, наверное, человек на Земле, способный управлять квантовым компьютером – если бы, конечно, такой компьютер существовал.
Эрик расплылся в довольной улыбке.
– Выявлять ошибки в квантовых вычислениях, – сказал он, – по сути означает убедиться в том, что, получив функционирующий квантовый компьютер, мы будем способны держать его под контролем. Пока что это выглядит маловероятным! С «Энигмой» такой проблемы не было.
Код как тайнопись
Люди с давних времён научились кодировать – шифровать – сообщения так, чтобы тем, кто не знает шифра, эти сообщения казались абракадаброй. Это позволяло посылать союзникам тайные послания, которые не сможет прочесть враг.
В наши дни всякий, кто что-то покупает в интернете – например, музыку, книги или подарок, – тоже вынужден зашифровывать номер своей банковской карты, чтобы никто не украл его деньги. Современные компьютеры не только обеспечивают шифрование сообщений, но и дают возможность убедиться, что сообщение не подделано и что отправитель – не подставное лицо.
Шифрование в компьютере происходит очень быстро, ведь шифруются биты, а не буквы; а вот взломать такой шифр, если нет секретного ключа, чрезвычайно трудно. Однако взломщиков это не останавливает, они придумывают всё новые и новые методы, и вполне возможно, что рано или поздно все существующие шифры будут взломаны. Что ж, тогда придётся изобретать новые!
Языки программирования
С точки зрения математики кодирование – это превращение одного набора символов в другой по определённым правилам.
Если правильно «закодировать» (ещё говорят – «запрограммировать») команды и данные в виде ноликов и единичек, то компьютер их поймёт. Как именно это сделать? По специальным правилам, которые у каждого процессора свои. Получившиеся нолики и единички, которые «понимает» процессор, называются машинным кодом. Каждый набор правил – это особый алгоритм. Запасшись терпением, программу из ноликов и единичек можно составить самому и записать ручкой в тетради. Но у компьютера это получится гораздо быстрее.
Люди пишут программы на легко читаемых языках программирования, таких как С или FORTRAN; оба эти языка состоят из обычных английских слов, так что нет нужды возиться с ноликами и единичками. Существует много разных языков программирования, на которых мы можем «говорить» с ком пью те ром. Под «компьютерным кодом» мы обычно подразумеваем программу, написанную на одном из таких языков.
Компиляторы – это специальные программы, которые преобразуют программы на высокоуровневых языках программирования в понятный процессору машинный код. Машинный код обычно записывают в шестнадцатеричной системе счисления.
Взломать компьютерный код – значит добиться сбоя в программе или сделать нечто совершенно непредвиденное. Так, злоумышленники в интернете из хулиганских или преступных побуждений пытаются получить несанкционированный доступ к компьютеру жертвы (например, чтобы завладеть данными кредитной карты и украсть с неё деньги).