«Такое не взломает даже квантовый компьютер»
Как находят скрытое и расшифровывают тайное
Сенсация: в Бристольском университете якобы смогли прочесть самую таинственную рукопись мира — манускрипт Войнича. «Огонек» разобрался, как находят скрытое и расшифровывают тайное.
Фото: Reuters
Фото: Из личного архива
Сергей Владимиров, автор труда по защите информации, ученый (МФТИ)
Сергей Владимиров, автор труда по защите информации, ученый (МФТИ)
Впрочем, вне зависимости от того, чем закончится история с манускриптом Войнича, можно смело констатировать: криптография сегодня на пике моды. В информационном поле то и дело всплывают новости о расшифровке таинственных посланий, а с экранов не сходят сериалы о специалистах-шифровальщиках. Сразу два таких сериала (отечественный «Шифр» и британский «Код убийства») напомнили о военной (и послевоенной) истории криптографии. С одной из самых известных легенд того времени — взлома немецкой шифровальной машины «Энигмы» — мы и начали разговор с ученым (МФТИ), автором труда по защите информации Сергеем Владимировым.
— Вы наверняка знаете про то, как британцы взломали «Энигму», кинематографисты не устают снимать фильмы на эту тему. Достижение и правда столь выдающееся?
— Как вам сказать… Некоторые считают, что благодаря взлому «Энигмы» длительность Второй мировой войны сократилась на пару лет. Напомню, что немцы использовали эту роторную машину для шифрования и расшифровки секретных сообщений, причем такие аппараты существовали и у американцев, и у нас. Однако история, конечно, приобрела всемирную известность благодаря своим масштабам: количество шифровок «Энигмы» исчислялось тысячами.
Приоритет в ее расшифровке принадлежит полякам — трем специалистам из «Бюро Шифров» — подразделения польской военной разведки. Сама «Энигма», по сути, представляла собой плохой полиалфавитный шифр, плохой в том смысле, что ключи соседних букв были связаны по определенным правилам — в механическом устройстве невозможно по-другому. Но если поляки занимались в основном ручной расшифровкой, то британцы из Блетчли-парка создали электромеханические машины, помогавшие взломать немецкий код. В том числе для взлома шифров они собрали первый в мире компьютер, вот почему эту историю трудно переоценить. К сожалению, науки у нас развиваются в тени войн. Первая мировая война — это механическая криптография и криптоаналитика (взлом шифров.— «О»), Вторая мировая — это Блетчли-парк и «Энигма»...
А вот вам еще один парадокс: «Энигма» стала известна именно потому, что ее взломали. Это как с разведчиками — мир узнает о них только тогда, когда их раскрывают.
— С «Энигмой» понятно. А что бы вы назвали главным событием в истории криптографии?
— Пожалуй, создание криптографии на открытых ключах, которая используется до сих пор. Это произошло уже в 1970-х. Понимаете, классическая симметричная криптография имеет дело с одним ключом, или кусочком информации, нужным для шифрования и последующей расшифровки. Допустим, таким ключом может быть цифра (в случае сдвига шифра по алфавиту, как в шифре Цезаря) или целая книга. Этот принцип не менялся тысячелетиями и остается актуален до сих пор. Однако в криптографии на открытых ключах нашли новый подход: теперь для шифрования нужен один ключ, а для расшифровки другой. Для нас, криптографов, это, конечно, была настоящая революция.
Текст на затылке
Манускрипт Войнича — один из самых загадочных текстов в истории. Многие исследователи считают, что он зашифрован
Фото: AFP
— Давайте ненадолго вернемся в прошлое. Когда люди впервые начали шифроваться и главное — что пытались скрыть?
— Насколько мне известно, самый ранний пример шифров — это древнеиндийский аналог русского «Домостроя», с разделом о женском календаре. Календарь был зашифрован, чтобы его не могли прочесть мужчины. Так что история криптографии насчитывает уже несколько тысяч лет.
— Насколько сложны были шифры древности?
— Судите сами: в знаменитом шифре Цезаря, изобретенном им самим, буквы «сдвигались» на определенное число по алфавиту. Выбирался ключ (например, число 3), а дальше вместо А ставилась третья буква — В, вместо Б — Г и так далее. Когда варвары видели зашифрованный таким образом текст, они думали, что это просто неизвестный им язык. Но долго этот шифр не продержался: его быстро научились «взламывать».
Анализируй это
«Огонек» попросил Сергея Владимирова составить специально для нашего журнала несколько простых криптографических задач. Вот они — теперь каждый может примерить на себя роль дешифровщика
Интересно, что первые криптоаналитики появились еще раньше, одним из них был Аристотель. Он догадался, как взломать шифр, созданный с помощью скиталы. Напомню: скитала представляла собой палку, на которую тонкой лентой наматывался папирус. Далее вдоль палки на намотанную ленту писался текст, и когда папирус снимался — текст сразу становился не читаем. Просто набор букв. Это еще называется геометрическим шифром, когда мы меняем не сами буквы, а их положение в тексте. Так вот Аристотель взял конус, намотал на него ленту с шифром и просто стал сдвигать ее вдоль конуса, пока не получил читабельный текст.
— Остроумно. Похоже на соревнование брони и снаряда: чем лучше броня, тем бронебойнее снаряды…
— Совершенно верно! Например, довольно долго использовались моноалфавитные шифры (когда текст заменяется на другой согласно одному правилу, побуквенно), такой шифр применяла Мария Стюарт в своей секретной переписке. Правда, она использовала модернизированный вариант: шифровала одни и те же буквы разными символами… Однако ее переписку все равно смогли перехватить и расшифровать, а Мария поплатилась за это головой. Так что, когда моноалфавитные шифры стали совсем ненадежными, мир перешел на полиалфавитные (допустим, для четных букв используется одно правило шифрования, а для нечетных — другое). Но к началу XX века криптоаналитики научились взламывать большинство шифров. Главное, что нужно было угадать,— на сколько групп разбит нужный шифр, а затем «ломать» каждую из них. Наконец, настоящий прорыв случился в середине ХХ века — с появлением шифрования на открытых ключах. Если до этого криптография была своего рода искусством, то затем началась эра науки — математики.
— Надо было брать пример с Ленина, он, как известно, вообще писал молоком…
— А это уже стеганография, или искусство скрытого письма. Когда речь не столько про шифр, сколько про то, чтобы скрыть некий текст. Стеганографию тоже применяли в далекой древности, правда, необычно: на бритой голове раба писали сообщение, дожидались, пока волосы у него отрастут, и отправляли к адресату. Желательно, чтобы раб при этом еще был немым и не мог выдать своего секрета.
Самый надежный шифр
— Вернемся к шифрованию. Я навскидку назову так и не взломанные шифры: манускрипт Войнича, послания американского маньяка Зодиака… Почему их так и не смогли «расколоть»?
— А были ли связные тексты за этими шифрами? Например, в случае с манускриптом Войнича некоторые ученые уверены, что это просто случайный набор символов. Мистификация.
Я не утверждаю, что это именно так. Но тут встают и чисто математические сложности. Например, для полноценной расшифровки нужен большой объем текста, если его не хватает, ничего не получится. Или еще одна интересная проблема — соотношение длины ключа и длины текста. Если в манускрипте Войнича один ключ на всю книгу, тогда расшифровка возможна. Если же на каждой странице использовался свой ключ — дело безнадежное. Наконец, помните, что это просто игра: никаких экономических или военных плюсов расшифровка этого манускрипта не принесет, а значит, вполне вероятно, что за него не брались всерьез.
— Выходит, шифр, который нельзя расшифровать, все же существует?
— Конечно! Например, шифроблокноты, их до сих пор используются дипломатами. Это такие блокноты, которые прошиты с четырех сторон особыми нитками. На каждой странице — цифры, они являются ключом. Когда нужно зашифровать текст, берутся цифры с первой страницы, текст с их помощью зашифровывается, а затем страница срывается и сжигается. После шифровка пересылается адресату. У адресата есть точно такой же шифроблокнот с таким же ключом на нужной странице. С его помощью он и расшифровывает сообщение. Все! Идея шифроблокнота в том, что длина ключа, с помощью которого зашифровано сообщение, равна длине текста. При этом если ключ выбран случайно, то текст невозможно взломать при условии, что каждая буква шифруется по отдельности и никакой ключ не используется два раза. Такое не взломает даже квантовый компьютер. Точнее, способ взлома все-таки есть — его еще называют «метод утюга и паяльника». Но это уже другая история.
Один из основателей современной криптографии, американский математик Клод Шеннон, некогда придумал способ измерить то, насколько шифр надежен, с помощью теории вероятности. Так вот Шеннон доказал, что шифроблокнот — абсолютно надежный шифр. Никакими математическими методами его не взломать.
Ключи эпохи интернета
— А насколько современная криптография приблизилась к таким вот идеальным шифрам?
— Можно сказать, подошла вплотную. Смотрите: сейчас криптография строится на двух китах — той самой симметричной криптографии и криптографии на открытых ключах. Ну, например, симметричная криптография — в основе современных госстандартов шифрования. Сам ключ сегодня представляет собой большую формулу (по сути, с десяток страниц текста, описывающего процесс шифрования). Но, конечно, криптографы думают над тем, как сделать этот ключ меньше и при этом столь же стойким к взлому. Это развитие идей американца Клода Шеннона: попытка придумать алгоритм, когда маленький ключ может так замешать и запутать текст, что его нельзя «прочитать».
— И где такое шифрование применяется?
— Да, в общем, везде, просто в разных видах. Ну, например, в сотовой связи, когда ваш телефон вырабатывает ключ для связи с сотовой вышкой. Или при подключении монитора к компьютеру — они общаются друг с другом по зашифрованному каналу (это было сделано для того, чтобы пираты не могли скопировать видеосигнал). Или автомобильный брелок…
— А шифрование на открытых ключах?
— Спектр его применения тоже широк, но среди основных сфер — IT. В шифровании на открытых ключах, напомню, совсем другая основа — математика. Ну, например, взяли два больших простых числа, перемножили их и получили еще большее число. Теперь математическая проблема: как из этого восстановить простые числа? Например, число 15 легко раскладывается на 5 и 3. Но, когда у нас числа имеют размер в тысячи десятичных знаков, проблема с практической точки зрения уже становится нерешаемой.
Давайте я коротко напомню, как работает такое шифрование: мы шифруем информацию открытым ключом, а расшифровываем закрытым. При этом открытый ключ не составляет никакой тайны: то есть зашифровать сообщение с его помощью может любой. Но вот расшифровать может только получатель, у которого есть второй, закрытый, ключ. Плюс этой технологии в том, что для нее можно использовать открытые каналы связи, например интернет или мессенджеры.
— Правильно ли я понимаю, что блокчейн основан на той же технологии?
— Да, там используется криптография открытого ключа и немного симметричного шифрования. Например, чтобы перевести деньги с кошелька на кошелек, вы должны создать транзакцию и подписать ее своим открытым ключом.
Но если мы вспомним алгоритм майнинга биткойнов, то он несколько другой. Майнинг состоит в том, что вы перебираете числа одно за другим, применяете к ним криптографическую функцию и смотрите, что получилось на выходе. Как только на выходе получается число с определенным количеством нулей — ура! Вы откопали «монетку». Для чего здесь нужна криптографическая функция? Очень просто: для того, чтобы процесс нельзя было «провернуть» назад, узнать исходное число и майнить столько, сколько хочешь. Так вот здесь уже используется симметричное шифрование.
— Все равно как-то не верится, что все это нельзя взломать…
— Почему же нельзя. Бывают так называемые бэкдоры — лазейки, которые оставляют разработчики тех или иных криптографических средств. Например, печально известна микросхема Clipper для шифрования, которую пытались навязать всем американским разработчикам средств связи и защиты информации еще в 1990-х. Быстро выяснилось, что там была такая лазейка. Американцы встроили бэкдор и в свой стандарт генерации случайных чисел для криптографии. Его потом обнаружили и исключили, но осадочек остался.
— А что именно хотели получить наши спецслужбы в рамках знаменитого «пакета Яровой»? Речь там тоже шла о криптографии…
— Речь шла не о дешифровке, а о самом процессе передачи зашифрованной информации. Возьмем интернет.
Во многих социальных сетях общение людей зашифровано только на уровне «клиент — сервер», то есть его невозможно прочитать, пока оно «идет», зато непосредственно на сервере — сколько угодно. Там оно хранится в расшифрованном виде.
А вот в некоторых мессенджерах шифруется канал общения от пользователя до пользователя, то есть, по сути, до конкретного устройства. И когда компетентные органы обращаются к владельцу сервиса, чтобы получить текст сообщения, тот лишь разводит руками: он тоже видит его лишь в зашифрованном виде. Проблема в том, что расшифровать это невозможно, сколько законов ни принимай.
Наше светлое криптобудущее
Квантовая криптография — перспективное направление, но с ней связано еще много нерешенных инженерных проблем
Фото: Shutterstock / REX / Fotodom
— Давайте перейдем к квантовым компьютерам. Говорят, они скоро смогут «расколоть» любой шифр. Не верите?
— Не в ближайшие лет пять точно. Чтобы квантовый компьютер смог расшифровать более или менее длинный код, зашифрованный открытым ключом, ему понадобится объем, скажем, в 2 тысячи кубитов (это элементы для хранения информации в квантовом компьютере.— «О»). А сегодня успешно строят компьютеры примерно в 15 кубитов. Пока эта инженерная проблема не преодолена, квантовый компьютер неэффективен.
К тому же сейчас мир переходит на шифрование с помощью эллиптических кривых, они для квантового компьютера и вовсе крепкий орешек. Объясняю, как это работает: представьте, что мы можем складывать точки на параболе как числа или даже умножать их на целые числа. В таком случае можно узнать, какая точка была в начале, какую точку мы получили в конце. Но быстро понять, на какое число ее умножили, очень трудно. Эта чисто математическая проблема и лежит в основе эллиптической криптографии. Так вот квантовый компьютер сможет разве что сократить перебор вариантов на сколько-то порядков. Но если ключ сам по себе длинный, это бесполезно.
— Какие же тогда перспективы у криптографии? Как будем шифроваться в ближайшем будущем?
— В целом современная криптография переходит в прикладную область: создание не просто шифров, а правил их использования. Например, у вас есть сервер социальной сети, вы как пользователь пытаетесь к нему обратиться. Но где гарантия, что это не копия сервера, созданная злоумышленниками? Есть различные способы решения этой проблемы: допустим, организация доверенных серверов. Над этим и думаем.
Что же касается перспектив… К примеру, есть большой математический вызов: решение нелинейных уравнений в дискретном поле. Не буду сейчас вдаваться в подробности, но лишь отмечу, что, если их научатся быстро решать, симметричная криптография падет — такие шифры смогут легко взламывать.