Записки программиста

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

Вы читаете гостевой пост Романа Душкина (Blogspot, ЖЖ, Twitter). Также вас могут заинтересовать другие заметки за авторством Романа:

Если вы интересуетесь криптографией, попробуйте еще обратить внимание на заметки Эллиптическая криптография на практике и Памятка по созданию безопасного канала связи моего авторства.

Вся история криптографии основывается на постоянном противоборстве криптографов м криптоаналитиков. Первые придумывают методы сокрытия информации, а вторые тут же находят методы взлома. Тем не менее, теоретически показано, что победа в такой гонке вооружений всегда останется на стороне криптографов, поскольку имеется абсолютно невзламываемый шифр — одноразовый блокнот. Так же есть некоторые очень сложно взламываемые шифры, для получения скрытой информации без пароля из которых у криптоаналитика практически нет шансов. К таким шифрам относятся перестановочные шифры посредством решеток Кардано, шифрование при помощи редких текстов в виде ключей и некоторые другие.

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

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

Однако, в конце концов, был разработан протокол обмена ключами, который позволил сохранять секрет при передаче ключа по открытому каналу (протокол Диффи-Хеллмана). Это был прорыв в классической криптографии, и по сей день этот протокол с модификациями, защищающими от атак класса MITM, используется для симметричного шифрования. Сам протокол основан на гипотезе о том, что обратная задача для вычисления дискретного логарифма является очень сложной. Другими словами, этот стойкость этого протокола зиждется только на том, что на сегодняшний день не существует вычислительных мощностей или эффективных алгоритмов для дискретного логарифмирования.

Проблемы начнутся тогда, когда будет реализован квантовый компьютер достаточной мощности. Дело в том, что Питер Шор разработал квантовый алгоритм, который решает не только задачу факторизации, но и задачу поиска дискретного логарифма. Для этого квантовая схема незначительно изменяется, а принцип работы остается тем же. Так что хитроумный изобретатель одним ударом убил двух криптографических зайцев — асимметричную криптографию RSA и симметричную криптографию Диффи-Хеллмана. Все пойдет прахом, как только на свет появится он, универсальный квантовый компьютер (не факт, что его еще нет; просто мы можем об этом даже и не знать).

Но модель квантовых вычислений как повергла криптографов в шок и трепет, так и дала им новую надежду. Именно квантовая криптография позволила придумать новый метод распределения ключей, в котором отсутствуют многие проблемы схемы Диффи-Хеллмана (например, простая атака MITM абсолютно не поможет в силу чисто физических ограничений квантовой механики). Более того, квантовая криптография устойчива и к квантовым алгоритмам поиска ключей, так как основана на совершенно ином аспекте квантовой механики. Так что сейчас мы изучим квантовый метод секретного обмена ключами по открытому каналу.

Первый квантовый протокол BB84 для секретного распределения ключей был разработан корифеями квантовых вычислений Чарльзом Беннетом и Жилем Брассардом в 1984 году. Для его описания как обычно воспользуемся ролевой моделью, в которой представлены Алиса и Боб, обменивающиеся информацией, а также зловредная Ева, которая хочет эту информацию перехватить и использовать в своих целях.

Как обычно, Алиса хочет отправить Бобу послание (она всегда хочет это сделать). Однако она боится пересылать свое сообщение без зашифровки, но ничего кроме одноразового блокнота не приемлет. Но возможности встретиться лично для обмена ключами у Алисы и Боба не было, поскольку они живут в разных галактиках. К счастью, у них есть квантовый канал передачи информации, которым и решает воспользоваться Алиса для генерации ключа, при помощи которого затем будет зашифровано сообщение.

Алиса может последовательно посылать Бобу фотоны (кванты света), каждый из которых имеет одну из четырех поляризаций: вертикальную, горизонтальную, диагональную слева-направо и диагональную справа-налево, то есть −, |, / и \. В какой именно поляризации послать очередной фотон выбирается на основании случайного выбора. Конечно же, это должен быть истинно случайный процесс, но за неимением его можно воспользоваться и генератором псевдослучайной последовательности, но как это обычно бывает в этом случае есть небольшой риск успешного подбора злоумышленником этой псевдослучайной последовательности.

Надо отметить, что фотоны − и / обозначают бит 0, а фотоны | и \ обозначают, соответственно, бит 1. Другими словами, Алиса посылает Бобу последовательность битов, при этом каждый бит может быть представлен двумя различными символами.

При приеме набора поляризованных фотонов Боб имеет возможность измерять каждый из них посредством двух различно ориентированных приборов: + или ×. Каждый способ измерения обладает интересной особенностью. Прибор + измеряет биты − и | с абсолютной точностью, а вот биты / и \ не даются ему, а при попадании в него фотона / или \ этот прибор дает с вероятностью ½ результат −, а с вероятностью ½ результат |. То же самое можно сказать и про прибор ×, только он с абсолютной точностью измеряет биты / и \, а вот для фотонов − и | он опять же с вероятностями ½ и ½ дает значения / или \.

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

Поскольку передачу Алисой Бобу фотонов можно сделать сколь угодно длительной, на выходе можно получить последовательность битов любой требуемой длины. В среднем будет выходить, что ровно половину полученных и измеренных фотонов надо будет отсеять, поскольку Боб выбрал неправильный прибор. Вот этот ключевой момент надо запомнить: в среднем половина фотонов будет измерена неправильно и должна быть вычеркнута.

Давайте посмотрим, как это может быть. Пусть Алиса послала Бобу вот такую последовательность поляризованных фотонов:

Боб произвел их измерения, используя такие приборы (первая строка таблицы показывает тип использованного прибора; вторая строка таблицы показывает результат, полученный Бобом):

Боб и Алиса созваниваются, и Алиса сообщает Бобу, какие измерения он произвел правильным типом прибора, а какие неправильным. Боб вычеркивает неправильные измерения, и в итоге получается двоичный ключ:

Действительно, в 8/16 случаев (50 %) Боб воспользовался неправильным прибором, так что из 16 переданных Алисой фотонов пришлой убрать половину. Остался ключ 00110101. Этот ключ секретный, и его знают только Алиса и Боб.

Как же Алиса и Боб могут удостовериться, что Ева не занималась перехватом, и передача действительно была секретной?

Пусть Алиса пересылает Бобу те же самые фотоны. Но на этот раз между ними находится Ева и фотоны перехватывает. Поскольку Ева не знает, какая именно поляризация у фотонов Алисы, ей также приходится использовать случайное применение двух разных типов приборов для измерения поляризации. Пусть это сделано так:

Ева, как человек посередине, очень хочет остаться незасеченной, поэтому она должна переслать эту последовательность Бобу. Ведь Боб должен что-то получить от Алисы. Фишка в том, что как только Ева измерила фотоны, полученные от Алисы, она схлопнула их волновые функции, и теперь даже если она пересылает именно их Бобу, последовательность уже совсем не та, которую посылала Алиса, а именно та, которую получила Ева в процессе своих измерений.

Боб опять измеряет полученные им фотоны, случайным образом применяя свои приборы:

После этого он созванивается с Алисой, с которой они сверяют использованные приборы. Как и в случае без Евы посередине Боб вычеркивает те биты, для получения которых он использовал неправильный прибор:

Итого у Боба получилась строка 10110111, в то время как у Алисы осталась строка 00110101. Как видно, 2 бита различаются у Алисы и Боба, и это именно то, что обусловлено действиями Евы по перехвату. Своими измерениями Ева схлопывает волновые функции фотонов, и они уже несут иную информацию в отличие от той, которую передавала Алиса.

Как же Алиса и Боб могут проверить наличие Евы между ними?

Все достаточно просто. Они должны выбрать в своих строках некоторое количество битов (допустим, k) и сравнить их по открытому каналу. Если все биты совпали, то с вероятностью 1-2^-k канал не прослушивается. Увеличивая k, можно получить достаточный уровень доверия. Само собой разумеется, что выбранные для сравнения биты должны быть вычеркнуты после проверки, поскольку они сравнивались по открытому каналу.

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

Напоследок я хотел бы пригласить всех заинтересованных читателей поучаствовать в моей новой краудфандинговой кампании по сбору народных средств на издание набора книг для обучения детей криптографии. На текущий момент написано три книги (из которых одна в двух вариантах: для мальчиков и для девочек). Первая книга художественная и рассказывает про приключения десятилетнего мальчика в заброшенной деревне, в которой он находит зашифрованные записки своего отца и начинает распутывать клубок загадок. Вторая книга представляет собой методические рекомендации для родителей, которые хотели бы заняться со своими детьми изучением криптографии, математики и немного информатики. Наконец, третья книга является учебников для ребенка, в котором самым простым образом объясняются двенадцать тем по криптографии и стеганографии от шифра одноалфавитной подстановки до одноразового блокнота.

Поучаствовать в кампании можно здесь: Занимательная криптография для детей.

Метки: Алгоритмы, Криптография.