«Такое не взломает даже квантовый компьютер»
Сенсация: в Бристольском университете якобы смогли прочесть самую таинственную рукопись мира — манускрипт Войнича. «Огонек» разобрался, как находят скрытое и расшифровывают тайное.
Выйти из полноэкранного режима
Развернуть на весь экран
Вот эта электромеханическая машина некогда помогла взломать немецкую «Энигму»
Сергей Владимиров, автор труда по защите информации, ученый (МФТИ)
Фото: Из личного архива
Британский лингвист Герард Чешир удивил мир: он утверждает, что смог прочесть легендарный манускрипт Войнича. Речь про иллюстрированный кодекс XV века, найденный книготорговцем Уилфридом Войничем и состоящий из 240 страниц загадочного текста с астрономическими знаками, растениями, сосудами и людьми. Правда, утверждается, что это вовсе не шифр, а текст на давно утраченном — протороманском — языке. Сам манускрипт представляет собой справочник по разным вопросам (в частности, по медицине и истории), составленный доминиканскими монахами для Марии Кастильской, королевы Арагона. Вся рукопись целиком пока не прочитана, но Герард обещает завершить начатое: еще в апреле он представил первые результаты на суд коллег и общественности в журнале Romance Studies. Остается дождаться реакции — такие сенсационные заявления звучат не в первый раз.
Выйти из полноэкранного режима
Развернуть на весь экран
Сергей Владимиров, автор труда по защите информации, ученый (МФТИ)
Впрочем, вне зависимости от того, чем закончится история с манускриптом Войнича, можно смело констатировать: криптография сегодня на пике моды. В информационном поле то и дело всплывают новости о расшифровке таинственных посланий, а с экранов не сходят сериалы о специалистах-шифровальщиках. Сразу два таких сериала (отечественный «Шифр» и британский «Код убийства») напомнили о военной (и послевоенной) истории криптографии. С одной из самых известных легенд того времени — взлома немецкой шифровальной машины «Энигмы» — мы и начали разговор с ученым (МФТИ), автором труда по защите информации Сергеем Владимировым .
— Вы наверняка знаете про то, как британцы взломали «Энигму», кинематографисты не устают снимать фильмы на эту тему. Достижение и правда столь выдающееся?
— Как вам сказать… Некоторые считают, что благодаря взлому «Энигмы» длительность Второй мировой войны сократилась на пару лет. Напомню, что немцы использовали эту роторную машину для шифрования и расшифровки секретных сообщений, причем такие аппараты существовали и у американцев, и у нас. Однако история, конечно, приобрела всемирную известность благодаря своим масштабам: количество шифровок «Энигмы» исчислялось тысячами.
Приоритет в ее расшифровке принадлежит полякам — трем специалистам из «Бюро Шифров» — подразделения польской военной разведки. Сама «Энигма», по сути, представляла собой плохой полиалфавитный шифр, плохой в том смысле, что ключи соседних букв были связаны по определенным правилам — в механическом устройстве невозможно по-другому. Но если поляки занимались в основном ручной расшифровкой, то британцы из Блетчли-парка создали электромеханические машины, помогавшие взломать немецкий код. В том числе для взлома шифров они собрали первый в мире компьютер, вот почему эту историю трудно переоценить. К сожалению, науки у нас развиваются в тени войн. Первая мировая война — это механическая криптография и криптоаналитика (взлом шифров.— «О» ), Вторая мировая — это Блетчли-парк и «Энигма».
А вот вам еще один парадокс: «Энигма» стала известна именно потому, что ее взломали. Это как с разведчиками — мир узнает о них только тогда, когда их раскрывают.
— С «Энигмой» понятно. А что бы вы назвали главным событием в истории криптографии?
— Пожалуй, создание криптографии на открытых ключах, которая используется до сих пор. Это произошло уже в 1970-х. Понимаете, классическая симметричная криптография имеет дело с одним ключом, или кусочком информации, нужным для шифрования и последующей расшифровки. Допустим, таким ключом может быть цифра (в случае сдвига шифра по алфавиту, как в шифре Цезаря) или целая книга. Этот принцип не менялся тысячелетиями и остается актуален до сих пор. Однако в криптографии на открытых ключах нашли новый подход: теперь для шифрования нужен один ключ, а для расшифровки другой. Для нас, криптографов, это, конечно, была настоящая революция.
Текст на затылке
— Давайте ненадолго вернемся в прошлое. Когда люди впервые начали шифроваться и главное — что пытались скрыть?
— Насколько мне известно, самый ранний пример шифров — это древнеиндийский аналог русского «Домостроя», с разделом о женском календаре. Календарь был зашифрован, чтобы его не могли прочесть мужчины. Так что история криптографии насчитывает уже несколько тысяч лет.
— Насколько сложны были шифры древности?
— Судите сами: в знаменитом шифре Цезаря, изобретенном им самим, буквы «сдвигались» на определенное число по алфавиту. Выбирался ключ (например, число 3), а дальше вместо А ставилась третья буква — В, вместо Б — Г и так далее. Когда варвары видели зашифрованный таким образом текст, они думали, что это просто неизвестный им язык. Но долго этот шифр не продержался: его быстро научились «взламывать».
Анализируй это
«Огонек» попросил Сергея Владимирова составить специально для нашего журнала несколько простых криптографических задач. Вот они — теперь каждый может примерить на себя роль дешифровщика
Интересно, что первые криптоаналитики появились еще раньше, одним из них был Аристотель. Он догадался, как взломать шифр, созданный с помощью скиталы. Напомню: скитала представляла собой палку, на которую тонкой лентой наматывался папирус. Далее вдоль палки на намотанную ленту писался текст, и когда папирус снимался — текст сразу становился не читаем. Просто набор букв. Это еще называется геометрическим шифром, когда мы меняем не сами буквы, а их положение в тексте. Так вот Аристотель взял конус, намотал на него ленту с шифром и просто стал сдвигать ее вдоль конуса, пока не получил читабельный текст.
— Остроумно. Похоже на соревнование брони и снаряда: чем лучше броня, тем бронебойнее снаряды…
— Совершенно верно! Например, довольно долго использовались моноалфавитные шифры (когда текст заменяется на другой согласно одному правилу, побуквенно), такой шифр применяла Мария Стюарт в своей секретной переписке. Правда, она использовала модернизированный вариант: шифровала одни и те же буквы разными символами… Однако ее переписку все равно смогли перехватить и расшифровать, а Мария поплатилась за это головой. Так что, когда моноалфавитные шифры стали совсем ненадежными, мир перешел на полиалфавитные (допустим, для четных букв используется одно правило шифрования, а для нечетных — другое). Но к началу XX века криптоаналитики научились взламывать большинство шифров. Главное, что нужно было угадать,— на сколько групп разбит нужный шифр, а затем «ломать» каждую из них. Наконец, настоящий прорыв случился в середине ХХ века — с появлением шифрования на открытых ключах. Если до этого криптография была своего рода искусством, то затем началась эра науки — математики.
— Надо было брать пример с Ленина, он, как известно, вообще писал молоком…
— А это уже стеганография, или искусство скрытого письма. Когда речь не столько про шифр, сколько про то, чтобы скрыть некий текст. Стеганографию тоже применяли в далекой древности, правда, необычно: на бритой голове раба писали сообщение, дожидались, пока волосы у него отрастут, и отправляли к адресату. Желательно, чтобы раб при этом еще был немым и не мог выдать своего секрета.
Самый надежный шифр
— Вернемся к шифрованию. Я навскидку назову так и не взломанные шифры: манускрипт Войнича, послания американского маньяка Зодиака… Почему их так и не смогли «расколоть»?
— А были ли связные тексты за этими шифрами? Например, в случае с манускриптом Войнича некоторые ученые уверены, что это просто случайный набор символов. Мистификация.
Как устроена квантовая криптография
Я не утверждаю, что это именно так. Но тут встают и чисто математические сложности. Например, для полноценной расшифровки нужен большой объем текста, если его не хватает, ничего не получится. Или еще одна интересная проблема — соотношение длины ключа и длины текста. Если в манускрипте Войнича один ключ на всю книгу, тогда расшифровка возможна. Если же на каждой странице использовался свой ключ — дело безнадежное. Наконец, помните, что это просто игра: никаких экономических или военных плюсов расшифровка этого манускрипта не принесет, а значит, вполне вероятно, что за него не брались всерьез.
— Выходит, шифр, который нельзя расшифровать, все же существует?
— Конечно! Например, шифроблокноты, их до сих пор используются дипломатами. Это такие блокноты, которые прошиты с четырех сторон особыми нитками. На каждой странице — цифры, они являются ключом. Когда нужно зашифровать текст, берутся цифры с первой страницы, текст с их помощью зашифровывается, а затем страница срывается и сжигается. После шифровка пересылается адресату. У адресата есть точно такой же шифроблокнот с таким же ключом на нужной странице. С его помощью он и расшифровывает сообщение. Все! Идея шифроблокнота в том, что длина ключа, с помощью которого зашифровано сообщение, равна длине текста. При этом если ключ выбран случайно, то текст невозможно взломать при условии, что каждая буква шифруется по отдельности и никакой ключ не используется два раза. Такое не взломает даже квантовый компьютер. Точнее, способ взлома все-таки есть — его еще называют «метод утюга и паяльника». Но это уже другая история.
Один из основателей современной криптографии, американский математик Клод Шеннон, некогда придумал способ измерить то, насколько шифр надежен, с помощью теории вероятности. Так вот Шеннон доказал, что шифроблокнот — абсолютно надежный шифр. Никакими математическими методами его не взломать.
Ключи эпохи интернета
— А насколько современная криптография приблизилась к таким вот идеальным шифрам?
— Можно сказать, подошла вплотную. Смотрите: сейчас криптография строится на двух китах — той самой симметричной криптографии и криптографии на открытых ключах. Ну, например, симметричная криптография — в основе современных госстандартов шифрования. Сам ключ сегодня представляет собой большую формулу (по сути, с десяток страниц текста, описывающего процесс шифрования). Но, конечно, криптографы думают над тем, как сделать этот ключ меньше и при этом столь же стойким к взлому. Это развитие идей американца Клода Шеннона: попытка придумать алгоритм, когда маленький ключ может так замешать и запутать текст, что его нельзя «прочитать».
— И где такое шифрование применяется?
— Да, в общем, везде, просто в разных видах. Ну, например, в сотовой связи, когда ваш телефон вырабатывает ключ для связи с сотовой вышкой. Или при подключении монитора к компьютеру — они общаются друг с другом по зашифрованному каналу (это было сделано для того, чтобы пираты не могли скопировать видеосигнал). Или автомобильный брелок…
— А шифрование на открытых ключах?
— Спектр его применения тоже широк, но среди основных сфер — IT. В шифровании на открытых ключах, напомню, совсем другая основа — математика. Ну, например, взяли два больших простых числа, перемножили их и получили еще большее число. Теперь математическая проблема: как из этого восстановить простые числа? Например, число 15 легко раскладывается на 5 и 3. Но, когда у нас числа имеют размер в тысячи десятичных знаков, проблема с практической точки зрения уже становится нерешаемой.
Почему Россия не выучила уроки компьютерной эпохи и как от этого страдает экономика
Давайте я коротко напомню, как работает такое шифрование: мы шифруем информацию открытым ключом, а расшифровываем закрытым. При этом открытый ключ не составляет никакой тайны: то есть зашифровать сообщение с его помощью может любой. Но вот расшифровать может только получатель, у которого есть второй, закрытый, ключ. Плюс этой технологии в том, что для нее можно использовать открытые каналы связи, например интернет или мессенджеры.
— Правильно ли я понимаю, что блокчейн основан на той же технологии?
— Да, там используется криптография открытого ключа и немного симметричного шифрования. Например, чтобы перевести деньги с кошелька на кошелек, вы должны создать транзакцию и подписать ее своим открытым ключом.
Но если мы вспомним алгоритм майнинга биткойнов, то он несколько другой. Майнинг состоит в том, что вы перебираете числа одно за другим, применяете к ним криптографическую функцию и смотрите, что получилось на выходе. Как только на выходе получается число с определенным количеством нулей — ура! Вы откопали «монетку». Для чего здесь нужна криптографическая функция? Очень просто: для того, чтобы процесс нельзя было «провернуть» назад, узнать исходное число и майнить столько, сколько хочешь. Так вот здесь уже используется симметричное шифрование.
— Все равно как-то не верится, что все это нельзя взломать…
— Почему же нельзя. Бывают так называемые бэкдоры — лазейки, которые оставляют разработчики тех или иных криптографических средств. Например, печально известна микросхема Clipper для шифрования, которую пытались навязать всем американским разработчикам средств связи и защиты информации еще в 1990-х. Быстро выяснилось, что там была такая лазейка. Американцы встроили бэкдор и в свой стандарт генерации случайных чисел для криптографии. Его потом обнаружили и исключили, но осадочек остался.
— А что именно хотели получить наши спецслужбы в рамках знаменитого «пакета Яровой»? Речь там тоже шла о криптографии…
— Речь шла не о дешифровке, а о самом процессе передачи зашифрованной информации. Возьмем интернет.
Во многих социальных сетях общение людей зашифровано только на уровне «клиент — сервер», то есть его невозможно прочитать, пока оно «идет», зато непосредственно на сервере — сколько угодно. Там оно хранится в расшифрованном виде.
А вот в некоторых мессенджерах шифруется канал общения от пользователя до пользователя, то есть, по сути, до конкретного устройства. И когда компетентные органы обращаются к владельцу сервиса, чтобы получить текст сообщения, тот лишь разводит руками: он тоже видит его лишь в зашифрованном виде. Проблема в том, что расшифровать это невозможно, сколько законов ни принимай.
Наше светлое криптобудущее
— Давайте перейдем к квантовым компьютерам. Говорят, они скоро смогут «расколоть» любой шифр. Не верите?
— Не в ближайшие лет пять точно. Чтобы квантовый компьютер смог расшифровать более или менее длинный код, зашифрованный открытым ключом, ему понадобится объем, скажем, в 2 тысячи кубитов (это элементы для хранения информации в квантовом компьютере.— «О» ). А сегодня успешно строят компьютеры примерно в 15 кубитов. Пока эта инженерная проблема не преодолена, квантовый компьютер неэффективен.
К тому же сейчас мир переходит на шифрование с помощью эллиптических кривых, они для квантового компьютера и вовсе крепкий орешек. Объясняю, как это работает: представьте, что мы можем складывать точки на параболе как числа или даже умножать их на целые числа. В таком случае можно узнать, какая точка была в начале, какую точку мы получили в конце. Но быстро понять, на какое число ее умножили, очень трудно. Эта чисто математическая проблема и лежит в основе эллиптической криптографии. Так вот квантовый компьютер сможет разве что сократить перебор вариантов на сколько-то порядков. Но если ключ сам по себе длинный, это бесполезно.
— Какие же тогда перспективы у криптографии? Как будем шифроваться в ближайшем будущем?
— В целом современная криптография переходит в прикладную область: создание не просто шифров, а правил их использования. Например, у вас есть сервер социальной сети, вы как пользователь пытаетесь к нему обратиться. Но где гарантия, что это не копия сервера, созданная злоумышленниками? Есть различные способы решения этой проблемы: допустим, организация доверенных серверов. Над этим и думаем.
Что же касается перспектив… К примеру, есть большой математический вызов: решение нелинейных уравнений в дискретном поле. Не буду сейчас вдаваться в подробности, но лишь отмечу, что, если их научатся быстро решать, симметричная криптография падет — такие шифры смогут легко взламывать.
Беседовал Кирилл Журенков
- Журнал «Огонёк» №19 от 20.05.2019, стр. 28
- Кирилл Журенков подписаться отписаться
Шифр Вернама (одноразовый блокнот)
Шифр Вернама (одноразовый блокнот) — единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым xor с одноразовым ключом, длина которого не меньше длины передаваемого сообщения.
[math]E_k(x_1) = x_1 \oplus k[/math]
[math]D_k(x_1 \oplus k \oplus k) = x_1[/math]
Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).
Легко заметить, что нельзя использовать один и тот же ключ несколько раз — при кодировании одинаковых сообщений с одинаковым ключом, полученные сообщения также будут одинаковыми, что позволит анализировать передаваемые сообщения.
Доказательство абсолютной секретности:
Пусть кодируемое слово — [math]x[/math] , ключ [math]k[/math] , результат кодирования [math] y = x \oplus k [/math] . Таким образом [math]P(y=y_0) = P(k = y_o \oplus x)[/math] . Заметим, что при фиксированном [math]x[/math] , каждому случайному [math]k[/math] соответствует ровно один [math]y[/math] , а значит и распределение [math]y[/math] будет совпадать с распределением ключа, из чего следует, что [math]\forall x_1 \neq x_2[/math] [math] f(y_1 \oplus k) = f(y_2 \oplus k)[/math] , что и требовалось доказать.
Шифр, который нельзя взломать
В современном цифровом мире защита информации от несанкционированного доступа стала постоянной проблемой почти для всех — и учреждений, и граждан, которые пользуются электронной почтой, мессенджерами, банковскими услугами, просто интернетом. В последние годы особенно актуальной стала квантовая криптография, обеспечивающая значительно более высокую степень защищенности по сравнению с другими способами криптографии. Квантовым коммуникациям была посвящена значительная часть недавно состоявшегося Форума будущих технологий , в котором принял участие президент России.
Мы обратились к одному из виднейших российских специалистов в области квантовых коммуникаций, автору ряда приоритетных работ в этой области, получивших международное признание, доктору физико-математических наук, ведущему научному сотруднику центра квантовых технологий физического факультета МГУ Сергею Молоткову с просьбой популярно объяснить суть квантовой криптографии для нашего читателя.
Сергей Молотков, доктор физико-математических наук, профессор кафедры суперкомпьютеров и квантовой информатики факультета ВМК МГУ, профессор кафедры квантовых технологий Института общей физики РАН, ведущий научный сотрудник центра квантовых технологий физического факультета МГУ
Фото предоставлено автором
Исторически термин «квантовые коммуникации» возник на втором этапе развития квантовых технологий. Исходная идея использовать законы квантовой механики для защиты информации называлась квантовой криптографией. Впервые эта идея была высказана в работе Стивена Визнера*.
Годом позднее Чарльз Беннет и Жиль Брассар предложили первый протокол квантовой криптографии**, который получил название BB84, по именам авторов.
Для того чтобы понять, в чем принципиальное отличие квантового протокола от классических криптографических протоколов, нужно кратко напомнить, что такое криптографические секретные ключи.
Фото предоставлено автором
Допустим, что два участника протокола (обычно их называют легитимными участниками), Алиса — передающая сторона и Боб — приемная сторона, хотят обменяться конфиденциальной информацией так, чтобы никто, кроме Боба, не смог прочитать сообщение Алисы.
На сегодняшний день существует два способа решения этой проблемы: первый реализуется при помощи симметричной криптографии, второй — с помощью асимметричной криптографии (другое название — криптография с открытыми ключами).
Сначала про симметричную криптографию. Развитие идей в любой научной области можно понять только в контексте логики исторических событий, поэтому для самодостаточности рассказа потребуется проследить историческую логику событий, которая привела к возникновению квантовой криптографии и, в более широком смысле, квантовых коммуникаций.
Для симметричной криптографии требуется, чтобы легитимные участники обмена информацией, Алиса и Боб, исходно имели общий секрет — секретный ключ. В современных условиях секретный ключ — это случайная битовая строка 0 и 1, которая известна только Алисе и Бобу.
Этот секретный ключ позволяет Алисе зашифровать свое сообщение, а Бобу — расшифровать передаваемое сообщение. Кстати о терминологии. Часто, особенно в разных блогах в интернете, говорят «дешифровать» вместо «расшифровать». Дешифрование — это нелигитимная процедура, которую осуществляет злоумышленник, который не знает секретного ключа. Грубо говоря, дешифрование — это взлом шифра. Легитимная процедура, которая требует знания секретного ключа, — расшифрование.
В этом месте возникает принципиальный вопрос о стойкости шифра. Пусть ключ секретен, но может ли злоумышленник, не имея секретного ключа, взломать шифр — прочитать сообщение?
Иначе говоря, существуют ли способы шифрования с секретным ключом, которые в принципе нельзя взломать?
Это принципиальный вопрос для криптографии, ответ на который совсем не очевиден.
* Stephen Wiesner, Conjugate Coding (manuscript circa 1970); sub-sequently published in SIGACT News15:1, 78–88; 1983.
** C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, In Proc. IEEE Int. Conf. on Comp., Sys. and Signal Process., pp, 175‒179, Bangalore, India (1984).
Иоганн Карл Фридрих Гаусс — немецкий математик, механик, физик, астроном и геодезист. Считается одним из величайших математиков всех времён, «королём математиков»
spacegid.com
От Гаусса до Шеннона
Даже великие математики ошибались в ответе на этот вопрос. Карл Фридрих Гаусс, например, считал, что шифр с омофонами взломать нельзя. Кратко расскажем, что это такое. Шифр замены состоит в том, что каждая буква открытого текста заменяется некоторым символом, неважно каким, хоть смайликом. Такой шифр является слабым, поскольку частота появления букв в тексте разная, соответственно частота символов замены сохраняется. Гаусс предлагал для выравнивания частот появления символов замены использовать не один, а несколько групп символов для часто встречающихся букв текста, символы из разных групп выбирались случайно.
Однако это не спасает ситуацию: шифр остается слабым. Ошибки гениев очень поучительны. Гаусс не сделал еще одного последнего шага: а может быть, надо заменять в каждом сообщении все буквы открытого текста каждый раз новыми случайными символами?
Потребовалось более ста лет, чтобы довести эту идею до логического завершения, и сделать финальный шаг.
Этот шаг был сделан в 1918 году американским инженером связистом Гилбертом Вернамом, который, кстати, работал на оборонное ведомство США (патент датируется 1918 годом).
Американский инженер связист Гилберт Вернам
cryptohistory.ru
В качестве догадки, но без доказательства в 1926 году была опубликована идея бегущих ключей (running keys), которая сводилась к тому, чтобы заменять каждый символ открытого текста в телеграфе, который представлялся 0 и 1, каждый раз новыми и случайными 0 и 1 — бегущими секретными ключами.
Следующий шаг с простым доказательством абсолютной стойкости такого способа шифрования с секретными ключами был независимо сделан нашим выдающимся соотечественником академиком АН СССР Владимиром Котельниковым 19 июня 1941 года. Закрытый отчет состоял из десяти страниц машинописного текста. Гриф секретности с данного отчета более двадцати лет назад был снят, но, насколько я знаю, отчет до сих пор неизвестен широкой общественности.
Академик АН СССР Владимир Котельников
Фото предоставлено автором
Важно, что наши криптографы независимо от своих западных коллег знали о таком способе шифрования.
Следующий шаг с полным математическим доказательством методами современной классической теории информации был приведен в работе Клода Шеннона Communication Theory of Secrecy Systems. Работа была выполнена в США в лаборатории Bell Labs в 1945 году и рассекречена в 1948-м (кстати, некоторые американские криптографы считают, что это было сделано ошибочно, по недосмотру).
После появления этой работы такой способ шифрования получил название «шифрование с одноразовыми ключами» — one time pad, «шифрование в режиме одноразового блокнота».
Клод Шеннон — американский инженер, криптоаналитик и математик. Считается «отцом информационного века». Является основателем теории информации, нашедшей применение в современных высокотехнологических системах связи
Резюмируем. Системы шифрования, которые невозможно взломать, даже теоретически существуют.
Что нужно для реализации таких систем?
1. Нужен общий секретный ключ — случайная битовая строка 0 и 1 у Алисы и Боба.
2. Длина ключа — число битовых позиций 0 и 1 должно быть не меньше длины отрытого сообщения — числа позиций текста в виде 0 и 1.
3. Ключ используется только один раз, на каждое новое сообщение нужен новый ключ.
4. Зашифрование происходит побитовым сложением по модулю 2 позиций текста с позициями ключа — возникает зашифрованный текст — битовая строка 0 и 1. Расшифрование производится аналогично побитовым сложением по модулю 2 позиций шифртекста с позициями ключа на приемной стороне. (сложение по модулю 2 — операция в булевой алгебре, результат которой равен 0, если оба слагаемых равны, и 1 в ином случае. — «Стимул»). Способ шифрования в режиме одноразового блокнота является абсолютно стойким — совершенным шифром. Шифр невозможно взломать даже теоретически. Данные утверждения строго доказаны математически. Это один из немногих фундаментальных результатов в криптографии, который строго доказан.
Интуитивно это тоже можно понять: каждый раз, не зная секретного ключа, злоумышленник видит в канале связи случайную битовую строку, которая никак не коррелирована — не связана с открытым текстом.
Казалось бы, проблема абсолютно защищенных коммуникаций решена.
Дело остается за малым. Нужно передавать (точнее, распределять) на каждое сообщение секретный ключ либо заранее иметь большой запас секретных ключей у Алисы и Боба на все последующие сообщения, которые также нужно как-то передать, а затем еще и хранить, чтобы до них не добрался злоумышленник.
Таким образом, распределение секретных ключей является центральной проблемой симметричной криптографии. Здесь мы сталкиваемся с проблемой «яйца и курицы» — кто вперед появился.
Для передачи секретных ключей нужен защищенный канал связи, который сам реализуется с помощью секретных ключей (канал связи с курьерами базируется на честности и надежности курьеров, что зиждется на человеческом факторе — иначе говоря, как в известном фильме «Бриллиантовая рука»: курьера можно подкупить, напоить, на худой конец получить ключ с бесчувственного тела (цитата приведена по памяти).
Переход в квантовый мир
В этом месте возникает переход в квантовый мир. Оказывается, что квантовая механика разрывает этот порочный круг — для передачи секретных ключей нужен защищенный (секретный) канал, для защищенного (секретного) канала нужен секретный ключ.
Следующий шаг с простым доказательством абсолютной стойкости такого способа шифрования с секретными ключами был независимо сделан нашим выдающимся соотечественником академиком АН СССР Владимиром Котельниковым 19 июня 1941 года
Теперь более подробно о том, в каком смысле и как квантовая природа микромира разрывает этот круг.
Чтобы не потерять общую логику событий, приведу утверждения, которые буду уточнять и детализировать далее.
1. Квантовая механика позволяет секретным образом распределять ключи через открытые и доступные для прослушивания и модификации квантовые каналы связи посредством передачи квантовых состояний, в которые кодируются биты будущего ключа. В качестве квантового канала связи используется стандартное оптическое волокно либо атмосферный канал связи, через которые передаются квантовые состояния света — в идеале однофотонные состояния либо когерентное сильно ослабленное до квазиоднофотонного уровня излучение стандартного телекоммуникационного лазера.
2. Кроме квантового канала связи требуется вспомогательный открытый и доступный для прослушивания аутентичный классический канал связи. В качестве такого канала связи также используется стандартное оптическое волокно либо атмосферный канал связи.
Таким образом, квантовая механика, используя передачу квантовых состояний через открытый квантовый канал связи и дополнительный открытый аутентичный классический канал связи, позволяет получить общий секретный ключ.
Выбор состояний и измерений
По сути, квантовая криптография — синоним квантового распределения ключей (КРК) — согласования независимых случайных последовательностей на стороне Алисы и на стороне Боба. Данные независимые случайные последовательности являются заготовками для будущего общего секретного ключа.
Действия Алисы и Боба происходят в соответствии с набором правил, которые и называются протоколом квантового распределения ключей — протоколом квантовой криптографии.
Случайные последовательности 0 и 1 получаются при помощи двух независимых генераторов случайных чисел.
Очевидно, что, поскольку случайные последовательности Алисы и Боба независимы, они совпадают примерно в половине позиций.
Каждый раз, не зная секретного ключа, злоумышленник видит в канале связи случайную битовую строку, которая никак не коррелирована — не связана с открытым текстом
Алиса в соответствии со своей случайной последовательностью готовит квантовые состояния — выбирает тип состояний и посылает их Бобу. Боб в соответствии со своей случайной последовательностью выбирает тип квантовых измерений.
В каждом типе измерений может быть квантовое состояние, отвечающее 0 или 1.
Посылается длинная серия квантовых состояний — посылок, обычно длина серии — несколько десятков миллионов, что занимает время порядка секунды.
Далее Боб или Алиса, в каждой зарегистрированной посылке сообщают через открытый аутентичный классический канал тип измерений, но не результат измерений 0 или 1 — это остается секретом.
Если типы измерений совпадают, то в отсутствие подслушивателя биты Алисы и Боба тоже будут совпадать. Посылки, где типы посылок и измерений не совпадают, отбрасываются. В оставшихся посылках (примерно в половине последовательности) типы посылок и измерений совпадают, и в них биты Алисы и Боба тоже совпадают. Так происходит синхронизация двух независимых случайных последовательностей.
Что будет, если нарушитель попытается узнать, какие квантовые состояния, соответственно какие биты 0 или 1, передает Алиса?
Здесь в игру вступает квантовая механика.
Фундаментальный запрет
Существует фундаментальный запрет природы, диктуемый квантовой механикой, на измерения квантовых состояний. Фактически этот запрет есть следствие фундаментальных соотношений неопределенностей Гейзенберга, о которых наверняка все слышали.
Применительно к квантовой криптографии запрет звучит так: невозможно получить информацию о неизвестном квантовом состоянии без его возмущения — данный запрет формализован в виде no cloning теоремы — запрет на точное копирование неизвестного состояния. Этот факт впервые был доказан Вутерсом и Зуреком***
Невозможно получить информацию о неизвестном квантовом состоянии без его возмущения — этот запрет формализован в виде no cloning теоремы — запрет на точное копирование неизвестного состояния
Классический носитель информации может быть достоверно скопирован без возмущения. Если можно создать одну копию, то можно создать сколь угодно много копий классического носителя информации. Можно скопировать без разрушения, например, электромагнитный сигнал передающий звук, изображение и т. д. Можно скопировать информацию на CD, при этом с исходной информацией ничего не происходит.
В классической области нет запретов «отщипнуть» от классического сигнала сколь угодно малую долю.
В квантовом мире — квантовые объекты, которые часто ведут себя контринтуитивно относительно нашей привычной классической интуиции.
*** W. K. Wootters, W. H. Zurek, A single quantum cannot be cloned, Nature, 299, 802 (1982).
Неделимый и некопируемый
При более тонком описании классических электромагнитных сигналов нужно вспомнить, что существует элементарный неделимый квант электромагнитного сигнала — фотон.
Заподозрить то, что может возникнуть что-то принципиально новое для защиты информации, мог бы, наверное, и старшеклассник, который слышал про неделимые элементарные кванты света.
Для интуиции приведем следующие рассуждения, за которыми скрывается суть квантовой криптографии. Наверное, мало кто задумывался над простым вопросом: почему миллионы людей могут слушать одну и ту же радиостанцию или смотреть одну и ту же программу телевидения, не мешая друг другу и не замечая того, что сосед включил телевизор и принимает ту же программу?
Что происходит по сути. Передающая станция излучает интенсивный электромагнитный сигнал, несущий информацию. Сигнал содержит огромное (правильно говорить макроскопически большое) число элементарных квантов, каждый приемник отводит часть сигнала — часть квантов. Однако поскольку квантов так много, то остается достаточно и всем остальным приемникам.
Мало кто задавал себе вопрос: а что будет, если понизить интенсивность сигнала до отдельного фотона?
Если наблюдаемая ошибка на приемной стороне меньше критической величины, то Алиса и Боб могут спокойно продолжать пить кофе, обмениваться общими секретными ключами и использовать их для защиты — шифрования своего трафика
Если задать такой вопрос, можно сразу усмотреть переход ситуации в принципиально новое качество.
От отдельного фотона нельзя отвести какую-то долю, поэтому если один приемник отвел сигнал себе, то остальным ничего не останется и данный факт можно обнаружить. И это хорошая новость для криптографии: нельзя незаметно подслушивать.
Если нельзя отвести часть фотона, может быть, можно сделать его копию, далее еще копию и тем самым усилить однофотонный сигнал? Но оказывается, что и это сделать нельзя: существует фундаментальный запрет на достоверное точное копирование неизвестного квантового состояния.
Если опустить формальные, хотя и важные детали, это означает, что поскольку нарушитель (обычно именуемый Евой, от английского eavesdropper — подслушиватель) не знает передаваемых состояний, то попытка узнать, какое состояние передается, неизбежно приведет к его возмущению (искажению) и, как результат, к ошибкам Боба при регистрации на приемной стороне.
Иначе говоря, любое вторжение в канал связи с целью получить информацию о передаваемом квантовом состоянии приведет к его возмущению и к ошибкам в переданной последовательности, где должно быть точное совпадение 0 и 1 у Алисы и Боба.
В идеале хотелось бы иметь возможность получать строго однофотонные сигналы, что существует пока в рамках экспериментальных работ. В реальных действующих системах КРК используются квазиоднофотонные состояния света — ослабленное до почти однофотонного уровня лазерное излучение. Это обстоятельство вкупе с собственными темновыми шумами однофотонных детекторов ограничивает дальность передачи ключей.
Как узнать, что было вторжение в квантовый канал связи?
Здесь еще раз используется открытый классический аутентичный канал связи. Алиса или Боб случайно выбирают позиции в оставшейся части последовательности и раскрывают их, сообщают, что в них было — 0 или 1. Зная число несовпадений, Алиса и Боб узнают вероятность ошибки на приемной стороне.
Раскрытая часть последовательности отбрасывается. При длинной исходной последовательности в оставшейся нераскрытой части такой же процент ошибок.
Зная процент ошибок, Алиса и Боб знают утечку информации к Еве.
Существует фундаментальная верхняя граница утечки информации при заданном наблюдаемом проценте ошибок на приемной стороне.
Неформально говоря, если Алиса и Боб знают процент ошибок, то они знают, сколько бит из оставшейся последовательности известно Еве — это фундаментальный закон природы, следствие фундаментальных соотношений неопределенностей.
Пока еще остаются ошибки у Боба. Как их исправить для полного совпадения всех позиций?
В этом случае используются классические коды коррекции ошибок. На сегодняшний день обычно используются, так называемые коды коррекции ошибок с низкой плотностью проверок на четность (LDPC-коды, Low Density Parity Check Codes). Коды были предложены Робертом Галлагером в 1963 году в его докторской (PhD) диссертации, но почти тридцать лет не были востребованы, поскольку требуют компьютерных вычислений.
Ситуация изменилась в 1990-е. На сегодняшний день LDPC-коды широко используются — от мобильной до дальней космической связи.
При коррекции ошибок, неформально говоря, Алиса должна передать Бобу через открытый аутентичный канал связи некоторое количество бит информации — 0 и 1. Еве данные биты также известны.
Дальность квантового распределения ключей в волоконных линиях связи ограничена как потерями в волокне, так и собственными темновыми шумами детекторов. Типичная длина линии составляет 100‒130 км
После исправления ошибок Алиса и Боб имеют общий и уже одинаковый ключ — очищенный ключ, о котором Ева имеет частичную информацию (опуская детали и неформально говоря, Ева знает часть позиций очищенного ключа.)
После исправления ошибок наступает третий финальный этап — этап получения финального общего секретного ключа –этот этап называется усилением секретности очищенного ключа, privacy amplification.
Данная процедура сводится к сжатию (хешированию) очищенного ключа при помощи специальных хеш-функций, причем важно, что процедура проводится в открытую через открытый канал связи — Ева знает используемые хеш-функции.
Из очищенного ключа получается финальный секретный ключ меньшей длины.
Насколько я знаю, исходно, термин «хеш» (hash) использовался в кулинарии, что означало — хорошо измельчить и перемешать (естественно, объем продукта при этом уменьшается, аналогично с криптографическим ключом — позиции исходного ключа исходно большой длины перемешиваются и сжимаются).
Теперь можно кратко суммировать, что принципиально нового дает квантовая криптография и системы КРК.
1. Возможно распределение секретных ключей через открытые и доступные для прослушивания каналы связи. Более того, нарушителю не запрещается даже модифицировать квантовый канал связи.
2. Системы КРК могут работать в полностью автоматизированном режиме. Человек не имеет доступа к секретным ключам — не требуется курьерская доставка ключей, исключается человеческий фактор.
3. Квантовое распределение ключей обеспечивает достаточно частую смену ключей, что в принципе позволяет приблизиться к идеальному совершенному шифрованию в режиме одноразового блокнота.
Что гарантируют системы КРК
Важно при этом отметить, что системы КРК гарантируют секретность ключей при условии, что наблюдаемый процент ошибок на приемной стороне не выше некоторой критической величины.
Иначе говоря, если ошибок слишком много (и аппаратура диагностирует свою работу как штатную), то это означает, что нарушитель очень грубо подслушивает — утечка информации к нему настолько велика, что невозможно распределить секретный ключ. В этом случае разбираться с нарушителем будут другими средствами.
Если наблюдаемая ошибка на приемной стороне меньше критической величины, то Алиса и Боб могут спокойно продолжать пить кофе, обмениваться общими секретными ключами и использовать их для защиты — шифрования своего трафика.
Принципиально важно, что КРК-системы гарантируют: никогда не возникнет ситуации, при которой Алиса и Боб думают, что обменялись секретным ключом, а ключ скомпрометирован — перестал быть секретным.
От точек к звездам
Базовой конфигурацией систем КРК является конфигурация «точка — точка — передатчик — приемник. В современных условиях требуется распределение секретных ключей в коммуникационных сетях, когда любая пара пользователей должна иметь общий секретный ключ. Возможны различные конфигурации сетей. Например, конфигурация «звезда» — общий квантовый сервер, который имеет соединение квантовым каналом с каждым пользователем сети. В этом случае на сервере есть ключи от всех пользователей, сгенерированных КРК. Согласование ключей у разных пользователей реализуется процедурой согласования через классический канал связи, при этом секретность ключей сохраняется.
Аналогично происходит в сетях с другой конфигурацией.
Открытие квантовой сети с шифрованием речевого трафика на квантовых ключах было продемонстрировано 16 декабря 2021 года. Данная сеть, названная квантовой телефонией (в разговорной речи — квантовый телефон) является совместной разработкой Центра квантовых технологий МГУ и российской IT-компании «ИнфоТекс» (компания — национальный чемпион. — «Стимул»). Более детальную информацию можно посмотреть на YouTube.
Дальность квантового распределения ключей в волоконных линиях связи ограничена как потерями в волокне, так и собственными темновыми шумами детекторов. Типичная длина линии составляет 100‒130 км. Хотя в Китае проведены эксперименты с использованием малошумящих сверхпроводящих детекторов и специального волокна с низкими потерями, в которых длина линии связи может достигать 500 км.
Как распределять ключи на любые расстояния
Существует несколько способов, которые отличаются сложностью реализации и ценой.
Первый, уже реализованный и используемый в сетях способ состоит в распределении ключей через доверенные узлы. Идея проста: по цепочке ключи распределяются по отдельным сегментам сети. Промежуточные доверенные узлы имеют в своем составе приемник и передатчик, которые соединены с соседними сегментами сети. На каждом доверенном узле возникают два ключа от соседних сегментов. Далее специальной процедурой через открытый классический канал связи ключи согласуются через каждый доверенный узел. В итоге возникает общий секретный ключ между крайними узлами.
Естественно, каждый узел должен иметь физическую защиту от нарушителя — быть доверенным. Нарушитель не должен знать результатов работы аппаратуры.
Такой способ распределения ключей используется в китайской сети Пекин — Шанхай общей длиной более 2000 км, длина каждого сегмента сети не превышает 100 км.
Второй способ увеличения дальности квантового распределения ключей состоит в комбинированной передаче ключей через низкоорбитальные спутники и волоконные линии связи. В КНР спутник квантовой связи был запущен в 2016 году. Было продемонстрировано квантовое распределение ключей между Пекином и Веной, ключи затем использовались для шифрования в режиме одноразового блокнота портретов Шредингера (одного из создателей квантовой механики) и китайского философа.
Третий способ увеличения дальности состоит в использовании недоверенных узлов. Этот способ находится пока в стадии интенсивных лабораторных экспериментов и включает в себя два идейно близких протокола квантового распределения ключей.
Под недоверенным узлом понимается такой промежуточный узел сети, к которому нарушитель может иметь прямой доступ. Точнее говоря, если доверенный узел требует полной физической защиты оборудования и нарушитель не должен знать результаты работы оборудования, то в недоверенном узле допускается, что нарушитель полностью знает результаты работы аппаратуры, тем не менее он не будет знать распределяемых ключей.
Идея крайне проста и была, по сути, высказана в России еще в 1997 году****, тогда такая система называлась квантовой криптографией на основе квантового компаратора. Идея была «переоткрыта» в 2018 году английскими учеными*****.
Пусть пара легитимных пользователей, Алиса и Боб, хотят распределить секретный ключ. Но расстояние между ними слишком большое и не позволяет распределять ключ напрямую и гарантировать его секретность.
В этом случае используется промежуточный недоверенный узел, на котором имеются два однофотонных детектора для регистрации состояний от Алисы и Боба.
Рисунок предоставлен автором
Алиса и Боб независимо друг от друга посылают квантовые состояния (сильно ослабленное излучение лазеров), которые отвечают 0 или 1. На недоверенном узле состояния Алисы и Боба «сбиваются» (интерферируют) на светоделителе и регистрируются одним из детекторов, L или R. Причем состояния устроены таким образом, что если Алиса и Боб послали одинаковые состояния 0 или 1, то сработает правый (R) детектор. Если Алиса и Боб послали разные состояния, Алиса —0, а Боб — 1 (и наоборот: Алиса — 1, Боб — 0), то сработает левый детектор (L).
Нарушитель знает (он имеет доступ к результатам работы аппаратуры на узле), какой детектор сработал, но не может знать бит ключа. Например, пусть сработал детектор R, это могло быть, если Алиса и Боб послали оба 0 или 1. Алиса и Боб, зная, какой детектор сработал, например R, знают, в отличие от нарушителя, что именно каждый из них посылал. В итоге получается общий секретный бит ключа. Аналогично, если сработал детектор L, в этом случае, например, Боб инвертирует свой бит — согласует с битом Алисы.
Как видно из описания и рисунка, такая система КРК позволяет увеличить дальность передачи только в два раза.
На сегодня данный метод КРК получил название Twin Field — сигналы-двойники. Нужно отметить, что эти системы крайне дороги и сложны в реализации, хотя сама по себе идея изящна.
Еще одним идейно близким протоколом КРК к протоколу Twin Field с недоверенным узлом является протокол КРК, называемый MDI (Measurement Device Independent). Он отличается от протокола Twin Filed только способом измерения на недоверенном узле. В этом протоколе используется четыре, а не два детектора.
MDI КРК, так же как и Twin Field КРК, позволяет увеличить дальность только в два раза. Система также довольно дорога и сложна в реализации, на сегодня существуют только лабораторные разработки. Наиболее активно такие системы исследуются в разных лабораториях в КНР.
Если квантовая криптография распределяет квантовые ключи, которые затем используются для шифрования в классическом режиме, то квантовое шифрование использует непосредственно сами квантовые состояния для передачи зашифрованной информации
Нужно упомянуть протокол релятивистской квантовой криптографии. Этот протокол, кроме фундаментальных ограничений квантовой механики, использует дополнительные фундаментальные ограничения, диктуемые специальной теорией относительности, на предельную скорость света — скорость распространения информации. Эти системы хорошо подходят для распределения ключей через открытое пространство между стационарными объектами, например релейными вышками. Такие системы КРК не требуют однофотонных или очень близких к однофотонным квантовых состояний.
Демонстратор такой системы был разработан в МГУ в рамках проекта Фонда перспективных исследований*****.
В системах КРК используются различные типы кодирования — сопоставление классическим битам информации 0 и 1 квантовых состояний. Поскольку стандартное одномодовое волокно не сохраняет состояние поляризации света, то для волоконных систем удобно так называемое фазовое кодирование, когда информация кодируется в относительную фазу квазиоднофотонных состояний. Для систем КРК в открытом пространстве чаще используют поляризационное кодирование, когда информация кодируется в состояние поляризации фотонов.
На сегодняшний день имеются эксперименты по прямому квантовому шифрованию. Если квантовая криптография распределяет квантовые ключи, которые затем используются для шифрования в классическом режиме, то квантовое шифрование использует непосредственно сами квантовые состояния для передачи зашифрованной информации. Хотя эти исследования находятся на лабораторной стадии.
Горячие головы теоретиков обсуждают возможность создания квантового интернета, что на сегодняшний день крайне далеко от практической реализации.
Вся область исследований, которая вкратце обсуждалась выше, получила название «квантовые коммуникации», но на сегодняшний день до практических работающих в реальных условиях устройств доведены только системы квантового распределения ключей — квантовая криптография.
**** С. Н. Молотков, Квантовая криптография на когерентных состояниях на основе квантового компаратора, Письма в Журнал экспериментальной и теоретической физики, 66, 736 (1997).
***** M. Lucamarini, Z. L.Yuan, J. F. Dynes, and A. J. Shields, Overcoming the rate-distance barrier of quantum key distribution without using quantum repeaters, Nature, 557, 400 (2018).
****** K. S. Kravtsov, I. V. Radchenko, S. P. Kulik, S. N. Molotkov, Relativistic quantum key distribution system with one-way quantum communication, Scientific Report, 8:6102 (2018).
Есть ли в перспективе шифр,который нельзя расшифровать?
ведь,даже мертвые языки расшифрованы. а комп может перебирать все варианты?или есть дешифровщики высшего пилотажа?
что скажет крипто-система в программировании,к примеру?
Лучший ответ
Шифр невозможно расшифровать, если длина случайного одноразового ключа равна длине сообщения. Это и шпионские криптоблокноты, и шифр Вернама.
лаура петровнаУченик (34) 1 год назад
а можно кратко о нем не программисту?
Андрей Высший разум (392638) лаура петровна, Так он появился задолго до программирования. На wiki нормальная статья.
Остальные ответы
маша корнееваУченик (100) 4 месяца назад
Вот ПРАВДА ЖИЗНИ. Смотрите и передавайте своим друзьям и знакомым : ВИДЕО 1: https://my.mail.ru/bk/pet.peskov/video/_myvideo/6.html ВИДЕО 2: https://my.mail.ru/bk/pet.peskov/video/_myvideo/3.html ВИДЕО 3: https://my.mail.ru/bk/pet.peskov/video/_myvideo/4.html ВИДЕО 4: https://my.mail.ru/bk/pet.peskov/video/_myvideo/5.html Только сначала скопируйте эти ссылки на свой компьютер, потому что местные модераторы-мошенники их удаляют.
Такой шифр был бы бесполезен, если можно восстановить из сообщения информацию, то можно и взломать, если нельзя, то и передача невозможна. Компы давно при расшифровке уже не перебирают все возможные варианты, ибо это крайне затратный и не эффективный метод, подбор простейшего ключа займёт тысячелетия тупо перебором.
Одноразовый блокнот
Шифры на основе одноразовых блокнотов, обобщенно упомянутые выше Андреем, взлому не поддаются принципиально при наличии надежного канала передачи этих самых блокнотов и надежного же механизма их случайного генерирования. Они были, есть и будут «в перспективе».