Защита информации: квантовая криптография

Лилия Виноградова, Константин Виноградов, Комиздат

Введение в криптографию

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

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

Классический подход состоит в том, что ключ, использующийся как для шифровки, так и для расшифровки сообщения, должен быть известен только Алисе и Бобу. Такие системы называются криптосистемами с закрытым ключом. Надежность процедуры шифрования доказана только для метода «одноразовых блокнотов», предложенного в 1917 году Гильбертом Вернамом (Gilbert Vernam). Идея его состоит в том, что Алиса и Боб обмениваются набором общих секретных ключей, каждый из которых используется для шифрования только одного сообщения. Ключи генерируются случайно и никакой информации не несут. Процесс шифровки состоит в том, что каждый символ исходного сообщения «складывается» с соответствующим символом ключа (так что ключ должен быть достаточно длинным, а сообщение — достаточно коротким). В «докомпьютерное» время ключи хранили в блокнотах с отрывными листами (отсюда и название метода). Каждый лист блокнота уничтожался после использования.

В применении к системам телекоммуникаций возникает проблема обеспечения секретности во время обмена ключами («блокнотами»), поскольку ключ должен быть доставлен получателю сообщения заранее и с соблюдением строгой секретности. Иначе говоря, конфиденциально обменяться сообщениями позволяют ключи, но как обменяться самими ключами с обеспечением секретности? Сформулированную таким образом проблему называют проблемой распространения ключа.

Если используется постоянный закрытый ключ, то расшифровка сообщения зависит от вычислительной мощности системы и времени. В США, например, для шифрования используется стандарт DES (Data Encryption Standard), разработанный в 1977 году. Он основан на 56-битном ключе, при помощи которого можно закодировать 64 бит информации. На этом стандарте основывается защита банковских транзакций, паролей Unix-систем и других секретных данных. Поскольку длина ключа меньше, чем длина кодируемого сообщения, то механизм защиты не является абсолютно надежным. Если попытаться угадать ключ методом проб и ошибок, нужно перебрать 256 всевозможных значений. И хотя этот объем вычислений очень велик, в настоящее время уже имеются данные о возможности взлома подобных систем. Рекордное время составляет 22 часа 15 минут при распределенной обработке информации в компьютерной сети (www.rsasecurity.com/rsalabs/challenges/).

Теория шифрования с использованием открытого ключа была создана Уэтфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г. В этой системе Боб имеет общедоступный код для шифрования и закрытый код для расшифровки сообщений. Криптосистемы с открытым ключом основываются на так называемых односторонних функциях:
по некоторому x легко вычислить функцию f(x), но зная f(x) трудно вычислить х.

Первый алгоритм, основанный на теории Диффи-Хеллмана, был предложен Роном Райвестом (Ron Rivest), Эди Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman) в 1977 г (RSA-алгоритм). Он основан на разложении простого числа на множители. Известно, что вычислить произведение двух простых чисел легко. В то же время, обратная задача – разложение числа на простые множители, достаточно трудоемка, поскольку время вычислений экспоненциально возрастает при увеличении количества битов в исходном числе. Хотя в настоящее время не опубликованы быстрые алгоритмы решения задачи разложения числа на простые множители, нельзя утверждать, что они не существуют вовсе. Кроме того, вычислительная мощность компьютерных систем постоянно возрастает, поэтому сложность задачи не означает ее неразрешимость. Так, компания RSA, основанная вышеперечисленными авторами алгоритма, предлагает всем желающим разложить на простые множители представленные ею числа. Один из последних отчетов компании посвящен разложению числа, состоящего из 155 цифр. Эта задача требует 35,7 процессорных года, что примерно эквивалентно 8000 MIPS-лет3; в реальном времени потребовалось 3,7 месяца благодаря распределенной обработке информации в компьютерной сети.

Таким образом, на настоящий момент единственно надежным методом шифрования является метод «одноразового блокнота», поскольку доказана его безусловная секретность, то есть секретность по отношению к шпиону, который обладает неограниченными временем и вычислительной мощностью. На пути к достижению такого уровня секретности, стоит проблема распространения ключа: Алиса и Боб должны обменяться ключом, сохранив его в полном секрете. Одним из ее решений является разработанный Чарльзом Беннетом (Charles Bennett) и Джилом Брассардом (Gilles Brassard) протокол квантового распространения ключа (quantum key distribution).

Квантовое распространение ключа

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

Идея использовать квантовые объекты для защиты информации от подделки и несанкционированного доступа впервые была высказана Стефаном Вейснером (Stephen Weisner) в 1970 г. Спустя 10 лет Беннет и Брассард, которые были знакомы с работой Вейснера, предложили использовать квантовые объекты для передачи секретного ключа. В 1984 г. они опубликовали статью, в которой описывался протокол квантового распространения ключа ВВ84.

Носителями информации в протоколе ВВ84 являются фотоны, поляризованные под углами 0, 45, 90, 135 градусов. В соответствии с законами квантовой физики, с помощью измерения можно различить лишь два ортогональных состояния: если известно, что фотон поляризован либо вертикально, либо горизонтально, то путем измерения, можно установить — как именно; то же самое можно утверждать относительно поляризации под углами 45 и 135 градусв. Однако с достоверностью отличить вертикально поляризованный фотон от фотона, поляризованного под углом 45?, невозможно.

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

Алиса посылает Бобу фотон в одном из поляризованных состояний (0, 45, 90, 135 градусов) и записывает угол поляризации. Отсчет углов ведется от направления "вертикально вверх" по часовой стрелке. В реальных же системах перед процессом передачи ключа оборудование специально юстируется для обеспечения одинакового режима отсчета на приемнике и передатчике (причем эту юстировку приходится проводить периодически в процессе передачи), а "пространственное расположение" начала отсчета угла -- несущественно.

Боб располагает двумя анализаторами: один распознает вертикально-горизонтальную поляризацию, другой — диагональную. Для каждого фотона Боб случайно выбирает один из анализаторов и записывает тип анализатора и результат измерений.

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

Алиса по общедоступному каналу связи сообщает Бобу, какие анализаторы он выбрал правильно. Те фотоны, для которых Боб неверно выбрал анализатор, отбрасываются.

Протокол для обмена ключом может выглядеть, как показано на рис. 1.

Пример шифрования по протоколу ВВ84

Последовательность фотонов Алисы	|	/	/	—	\	|	|	—	—
Последовательность анализаторов Боба	+	x	+	+	x	x	x	+	x
Результаты измерений Боба	0	0	1	1	1	0	1	1	0
Анализаторы выбраны верно	+	+		+	+			+
Ключ	0	0		1	1			1

Рис. 1. Принцип действия протокола ВВ84.

Условные обозначения:

Поляризация фотонов: | - вертикальная, — - горизонтальная, / - под угром 45, \ - под углом 135.

Анализаторы: + - прямоугольный, х - диагональный

Значения разрядов ключа получаются следующим образом: в случае вертикально-горизонтальной ("прямоугольной") поляризации вертикально-поляризованный фотон означает 0, горизонтально-поляризованный — 1; в случае диагональной поляризации фотон, поляризованный под углом 45 градусов -- 0, 135 градусов -- 1.

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

При изучении рисунка, на первый взгляд странно выглядят результаты измерения Боба (например, в 3-м столбце). Но, если анализатор выбран Бобом неверно, то результаты являются случайными (50/50), поэтому там вполне мог бы быть и 0 — этот результат все равно будет отброшен при формировании ключа.

Чтобы было легче разобраться, проследим результаты во всех ячейках на рисунке:

1-й столбец — Алиса послала вертикально-поляризованный фотон, Боб выбрал "прямоугольный" анализатор и, следовательно, смог получить правильный результат — 0. Этот результат вошел в ключ.

2-й столбец — Алиса посылает фотон, поляризованный под углом 45 градусов, Боб выбирает диагональный анализатор и может получить верный результат — 0. Этот результат также входит в ключ.

3-й столбец — Алиса вновь посылает фотон, поляризованный под углом 45 градусов, но Боб выбирает неверный, прямоугольный анализатор, поэтому с равной вероятностью может получить как 0, так и 1. В случае, показанном на рисунке, его результат равен 1. После сверки анализаторов этот результат будет отброшен и в ключ не войдет.

4-й столбец — Алиса посылает горизонтально-поляризованный фотон, Боб выбирает верный анализатор и получает результат 1, который войдет в ключ.

5-й столбец — Алиса посылает фотон, поляризованный под углом 135 градусов, Боб выбирает правильный, диагональный анализатор и получает результат 1, который войдет в ключ.

6-й и 7-й столбцы — Алиса дважды подряд (это случайно!) посылает вертикально-поляризованный фотон, но Боб оба раза (это тоже случайно) выбирает неверный, диагональный анализатор, в результате чего результаты его измерений — случайны, что и представлено на рисунке: в 6-м столбце Боб получил 0, а в 7-м — 1. Оба эти результата при формировании ключа будут отброшены из-за того, что был выбран неверный анализатор.

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

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

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

Если Алиса и Боб не собираются использовать полученный ими ключ сразу, то перед ними возникает новая проблема, — как сохранить ключ в секрете? В 1991 г. Артур Экерт (Artur Ekert) предложил протокол, позволяющий решить обе эти проблемы — распространения и хранения ключа. Протокол Экерта основан на эффекте сцепления квантовых частиц. Сцепленные частицы ведут себя необычном образом: если произвести измерение одной из них, то другая (на каком бы расстоянии она ни находилась) обязательно «перейдет» в состояние, противоположное состоянию первой частицы. Парадокс заключается в том, что информация о состоянии частицы передается со скоростью, превышающей скорость света. Тем не менее, это явление демонстрируется физиками экспериментально и может быть использовано для шифрования информации.

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

Экспериментальная реализация

Не так давно метод квантового распространения ключа воспринимался как научная фантастика. Но в 1989 г. в Уотсоновском исследовательском центре IBM Чарльзом Беннетом, Джилом Брасардом и их студентами была построена первая система, реализующая протокол ВВ84. Она позволяла «Алисе» и «Бобу» обмениваться секретным ключом со скоростью 10 бит/с на расстоянии 30 см. Это был небольшой шаг для Алисы и Боба, но большой шаг в развитии квантовой криптографии!

Позже эту идею реализовала Национальная лаборатория в Лос-Аламосе в эксперименте по распространению ключа в оптоволоконном кабеле на расстояние 48 км. В качестве среды передачи сигнала использовался и открытый воздух, расстояние передачи, в котором составляло около 1 км. Разработан план эксперимента по передаче квантового сигнала на спутник. Если этот эксперимент увенчается успехом, можно надеяться, что технология вскоре станет широко доступной.

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

Сведения об авторах:

Виноградова Лилия Степановна, ассистент Украинского государственного химико-технологического университета

Виноградов Константин Георгиевич, ст. преподаватель