Содержание к диссертации
Введение
1 Квантовое распределение ключей на двух неортогональных состояниях (протокол В92) 14
1.1 Информационные состояния и измерения 14
1.2 Стратегии подслушивания 15
2 Длина секретного ключа в шенноновском пределе 19
2.1 Индивидуальная атака 20
2.2 Коллективная атака 22
3 Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc 11% 26
3.1 Общие сведения о протоколе ВВ84 26
3.2 Атака подслушивателя на ключ 27
3.3 Измерения на приемной стороне 28
3.4 Коррекция ошибок легитимными пользователями 29
3.5 Индивидуальные измерения подслушивателя 29
3.6 Коллективные измерения подслушивателя 31
3.7 Область критических ошибок 11% < Qc< 15% 35
3.8 Выводы 36
4 Усиление секретности 37
4.1 Теорема об усилении секретности 37
4.2 Длина финального секретного ключа 40
4.3 Выводы 42
5 Практические методы коррекции ошибок 43
5.1 Требования к процедурам коррекции ошибок в квантовой криптографии . 43
5.2 "Чистка" первичного ключа при помощи БЧХ кодов (Bose-Chaudhuri-Hocquenghem) 44
5.2.1 Вычисление ошибки подслушивателя после "чистки" ключа БЧХ кодами 51
5.3 "Чистка" первичного ключа при помощи кодов Хэмминга (Hamming) 55
5.4 Протокол Cascade 58
5.4.1 Исходные данные 58
5.4.2 Результат 59
5.4.3 Алгоритм 59
5.4.4 Статистика 62
5.5 Удаление битов четности 63
5.5.1 Исходные данные 64
5.5.2 Результат 64
5.5.3 Алгоритм 64
5.5.4 Пример удаления битов четности пересекающихся подмножеств (сохранение конфиденциальности) 65
5.6 Выводы 68
6 Система квантовой криптографии 71
6.1 Оптоволоконная реализация протокола В92 71
6.1.1 Информационные однофотонные состояния 71
6.1.2 Преобразование состояний на передающей станции 73
6.1.3 Преобразование состояний па приемной станции 74
6.1.4 Измерения на приемной стороне 75
6.2 Открытый классический канал связи 75
6.3 Передача сообщений 76
6.4 Генерация сырого ключа 80
6.5 Обработка ключа 80
6.5.1 Описание 80
6.5.2 Сетевое взаимодействие 81
6.5.3 Случайные числа 81
6.5.4 Раскрытые биты четности 82
6.5.5 Параметры "чистки" 82
6.5.6 Определение начальной стадии процесса 82
6.5.7 Синхронизация 83
6.5.8 Перестановка битов 83
6.5.9 Каскадная процедура коррекции ошибок в первичных ключах 83
6.5.10 Сравнение ключей 89
6.5.11 Выбрасывание раскрытых битов 90
6.5.12 Хэширование "очищенных" ключей 91
6.5.13 Возврат ключа 93
Заключение 94
Литература 123
- Информационные состояния и измерения
- Индивидуальные измерения подслушивателя
- "Чистка" первичного ключа при помощи БЧХ кодов (Bose-Chaudhuri-Hocquenghem)
- Пример удаления битов четности пересекающихся подмножеств (сохранение конфиденциальности)
Введение к работе
Объект исследования и актуальность темы.
Квантовая криптография [1, 2], или распространение секретных ключей, в принципе позволяет реализовать абсолютно стойкие (не дешифруемые подслушивателем далее теоретически) системы шифрования с одноразовыми ключами [3, 4]. Секретность ключей в квантовой криптографии основана на фундаментальных запретах квантовой механики [5], а именно, на том обстоятельстве, что пара наблюдаемых, которым отвечают некоммутирую-щие операторы, не может быть достоверно одновременно различима, что является следствием соотношений неопределенности Гейзенберга. В квантовой криптографии в качестве таких наблюдаемых выступают матрицы плотности информационных состояний, соответствующих классическим битам 0 и 1. Для чистых состояний одновременная ненаблюдаемость (достоверная неразличимость) матриц плотности эквивалентна неортогональности информационных квантовых состояний [6]. Сказанное означает, что не существует измерений, которые с вероятностью единица позволяют различать одно из пары пеортогональных состояний и так, чтобы после измерения система оказалась в исходном состоянии, в котором она была до измерения. Таким образом, любое измерение, если оно дает информацию о передаваемых состояниях, неизбежно приводит к их возмущению, что позволяет детектировать любые попытки подслушивания в канале связи. Другими словами, подслушивание (соответственно возмущение состояний) передаваемых состояний должно неизбежно приводить к изменению статистики результатов измерений на приемном конце по сравнению со статистикой результатов измерений на невозмущенных состояниях. Искажение квантовых состояний возникает в неидеальном квантовом канале, что также приводит к изменению статистики результатов измерений. В квантовой криптографии принципиально невозможно отличить изменение статистики результатов по сравнению с идеальным случаем, возникающих за счет шума в канале или от действий подслушивателя, поэтому любые изменения статистики приходится относить на действия подслушивателя.
Если бы законы квантовой механики позволяли обнаруживать только сам факт возмущения передаваемых состояний, то это было бы бесполезно для целей криптографии, точнее передачи ключей. Квантовая механика позволяет не только обнаруживать возмущение состояний, но и связать изменение статистики результатов измерений с количеством информации,
которое может быть получено подслушивателем при наблюдаемом изменении статистики отсчетов по сравнению с идеальным случаем.
В квантовой криптографии кроме квантового канала связи (в реальных условиях это либо оптоволокно, либо открытое пространство), по которому передаются квантовые состояния, необходим также открытый классический канал связи. Классический открытый канал связи необходим для выяснения легитимными пользователями изменений статистики отсчетов и коррекции ошибок в первичном ключе, переданном по квантовому каналу связи. Единственное требование, которое предъявляется к классическому каналу связи состоит в том, что передаваемая открыто и доступная всем, включая подслушивателя, классическая информация не могла быть изменена подслушивателем - сохраняла целостность (так называемый unjammable channel). Такой открытый классический канал является математической идеализацией, поскольку подобных каналов в природе не существует. Для сохранения целостности открыто передаваемых классических данных в реальных условиях необходимо использовать процедуры аутентификации и контроля целостности данных. Для подобных процедур в свою очередь требуется секретный ключ.
Если в качестве открытого классического канала используется, например, интернет, то для целей ауіентификации возможна генерация ключей по схеме Хеллмана-Диффи [7]. Если же для открытого классического канала используется та же самая оптоволоконная линия, что и для квантового канала связи, то генерация ключей для аутентификации по схеме Хеллмана-Диффи оказывается принципиально неприемлемой из-за очевидной, так называемой атаки "man in the middle". В такой ситуации требуется небольшой стартовый ключ один раз при первом сеансе. При последующих сеансах этот ключ выбрасывается, и для аутентификации и сохранения целостности данных, передаваемых по классическому каналу, используется часть ключа, сгенерированного но квантовому каналу в предыдущем сеансе обмена. Оставшаяся большая часть ключа, используется собственно для шифрования данных. Если для аутентификации и сохранения целостности данных используются процедуры на основе ГОСТа, то длина стартового ключа составляет 256 бит. При этом в результате работы протокола передачи ключа обмена может быть получен новый секретный ключ по квантовому каналу гораздо более длинный, чем исходный.
Разумеется, что стартовый ключ мог бы быть использован для шифрования этим ключом нового ключа и передачи его второму легитимному пользователю. Однако при этом абсолютная секретность нового ключа гарантируется лишь, если его длина не более длины ключа, на котором он шифруется. Т.е. более длинного ключа получить нельзя. В квантовой криптографии стартовый ключ не используется напрямую для передачи нового ключа,
который генерируется по квантовому каналу связи. Как будет видно ниже, число бит открытой информации, переданной по открытому классическому каналу на один бит нового секретного ключа меньше единицы, поэтому возможно расширение ключа.
Подход с небольшим стартовым ключом является более предпочтительным, поскольку при этом возможно свести к минимуму число раундов обмена по открытому каналу связи в процессе "чистки" и усиления секретности ключа (privacy amplification).
Основная задача теории сводится к выяснению длины секретного ключа, который может быть получен при наблюдаемых изменениях статистики результатов измерений на приемном конце по сравнению со статистикой на невозмущенных состояниях. Как правило величиной, которая характеризует отклонение статистики измерений от идеальной, является величина вероятности ошибки. Точнее, вероятности того, что переданный бит был 0, а зарегистрирован как 1, и наоборот. Хотя возможны и другие критерии для обнаружения изменения статистики.
Первым этапом любого квантового протокола распределения ключей является передача и детектирование квантовых состояний. После передачи квантовых состояний легитимные пользователи оценивают вероятность ошибки (отклонение статистики отсчетов от идеальной).
Оценка вероятности ошибки получается путем сравнения через открытый канал части переданной последовательности по квантовому каналу, в дальнейшем раскрытая часть отбрасывается.
Следующий этап состоит в коррекции ошибок в нераскрытой части последовательности у легитимных пользователей посредством обмена информацией через открытый канал связи. Обычно легитимных пользователей называют Алиса и Боб, а подслушивателя - Ева (от английского Eavesdropper). В результате коррекции ошибок остается последовательность бит меньшей длины и одинаковая у Алисы и Боба. "Одинаковая" в данном контексте означает, что их последовательности совпадают с вероятностью, сколь угодно близкой к единице (например, 1 — 2~т ~ 1-Ю-70 при та = 200, величина параметра га выбирается легитимными пользователями). Напомним, что число атомов в видимой части Вселенной оценивается как 1077).
После "чистки" первичного ключа у подслушивателя имеется строка бит или регистр квантовой памяти с состояниями, или и то и другое вместе. Последний шаг при получении финального секретного ключа состоит в сжатии (фактически в применении случайной функции хэшировании) уже к одинаковой последовательности у Алисы и Боба. Сжатая последовательность бит является общим секретным ключом для легитимных пользователей,
про который гарантируется, что подслушиватель имеет о ключе экспоненциально малую информацию по некоторому, заданному Алисой и Бобом, параметру секретности.
Естественным требованием к процедурам коррекции ошибок и усиления секретности ключа является сохранение как можно большего числа бит в финальном ключе. Еще одно требование состоит в минимизации числа обменов по открытому каналу связи в пересчете на один бит в финальном секретном ключе.
При коррекции ошибок в первичном ключе задача легитимных пользователей состоит не только в исправлении ошибок, но также в оценке верхней границы информации, которую может получить об оставшемся ключе подслушиватель из обменов по открытому каналу связи. Для коррекции ошибок возможно использование различных процедур, включая хорошо разработанные классические коды, исправляющие ошибки, либо специальные итерационные процедуры, используюшие двусторонние обмены вспомогательной информацией между Алисой и Бобом через открытый канал связи. Причем заранее отнюдь не очевидно, какой из методов окажется более эффективным по упомянутым выше критериям.
Целью диссертационной работы является :
Исследование криптографической стойкости двух основных протоколов квантового распределения ключей В92 и ВВ84 с учетом коллективной атаки подслушивателя на передаваемые квантовые состояния;
Определение величины критической ошибки Qc в первичных ключах на приемной стороне, до которой возможно получение общего секретного ключа легитимными пользователями;
Оценка длины финального секретного ключа, который можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах;
Исследование различных процедур распределенной коррекции ошибок в первичных ключах, включая процедуры с двухсторонним обменом вспомогательной информацией через открытый канал связи, а также сравнение их эффективности;
Разработка компьютерных алгоритмов и программ для распределенной коррекции ошибок.
Краткое содержание диссертации.
В первой главе приведено описание квантового криптографического протокола В92 и различных стратегий подслушивания.
Во второй главе для протокола В92 определена критическая ошибка, до которой возможно распределение ключей для индивидуальной и коллективной атаках, получена также оценка длины секретного финального ключа в зависимости от наблюдаемой ошибки, если последняя меньше критической.
В третьей главе исследуется криптографическая стойкость основного квантового протокола распределения ключей - ВВ84. Для данного протокола ранее была найдена (Mayers, Shor, Preskill [26],[28]) точная величина критической ошибки [26],[28]. Однако доказательства [26],[28] являются фактически теоремами существования, констатирующими, что при Q > Qc ~ 11% J Алиса и Боб не могут получить общий секретный ключ. При этом явная стратегия Евы, которая приводит к данной ошибке, неизвестна. Точнее говоря, неизвестна оптимальная стратегия подслушивания, которая дает Еве максимум информации о ключе при минимально возможной производимой ей ошибкой у Боба.
Более менее ясно, что при такой стратегии Ева должна использовать квантовую память и коллективные измерения над всей последовательностью квантовых состояний. Это убеждение возникает из того обстоятельства, что для случая индивидуальных измерений над передаваемыми состояниями, оптимальная стратегия известна и построена явно. Но при такой стратегии Евы критическая ошибка оказывается Qc ру 15%, что выше точной границы.
Кроме того, оставался открытым вопрос о том, что происходит в области ошибок 11% < Qc < 15%. Или иначе говоря, какие стратегии Евы будут приводит к критической ошибке в "диапазоне" стратегий (коллективная атака - индивидуальная атака).
В третьей главе стратегия, на которой достигается теоретический предел критической ошибки Qc « 11%, построена явно. Кроме того, прояснен вопрос, что происходит в области ошибок 11% < Q < 15%. Показано, что существует бесконечный набор стратегий подслушивания Евы, который приводит к ошибкам в интервале 11% < Q < 15%. Установлена связь бесконечного набора стратегий с бесконечным набором классических пропускных способностей квантового канала связи. Данное явление не имеет классического аналога. Причем оказывается, что различные атаки внутри бесконечного набора отличаются только на стадии измерений. Если Ева может проводить коллективные измерения сразу над всей последовательностью квантовых состояний, то реализуется оптимальная стратегия, приводящая к критической ошибке в 11%. Если Ева может производить только индивидуальные измерния, то достигается ошибка в 15%. Если Ева может делать измерения не более, чем над к состояниями сразу (1 < к < оо), то критическая ошибка Qc(ll%) < Qc < Qc(15%).
Критическая ошибка зависит от способа исправления ошибок. Упомянутые критиче-
^нак » используется для краткости, поскольку значение Qc определяется как корень некоторого трансцендентного уравнения.
ские ошибки достигаются, если легитимные пользователи используют случайные шенноновские коды для исправления ошибок. Однако такая процедура является хоть и конструктивной, но практически нереализуема, поскольку требует экспоненциально большой по длине битовой последовательности таблицы кодовых слов. Шенноновские случайные коды обладают минимальной избыточностью. Поэтому количество вспомогательной классической информации, передаваемой через через канал связи, и которая доступна подслушивателю, является минимально возможным по сравнению с другими процедурами исправления ошибок.
Используемые на практике процедуры исправления ошибок имеют большую избыточность, чем процедуры, основанные на случайных кодах. Поэтому Еве оказывается доступно большее количество информации, что приводит к меньшей допустимой критической ошибке, до которой возможно получение общего секретного ключа для Алимы м Боба.
Одной и важных задач является поиск эффективных процедур распределенной коррекции ошибок.
После исправления ошибок Алисой и Бобом у них возникают одинаковые битовые строки ("очищенный" ключ). Однако информация Евы об "очищенном" клююче все еще1 является конечной, и заведомо не экспоненциально малой по параметру секретности. Для получения финального секретного ключа необходимо сжатие (хеширование) очищенного ключа при помощи универсальных функций хеширования второго рода [20] (Wegman, Carter), которые сами являются случайными величинами. Причем степень сжатия определяется как величиной ошибки в первичном ключе, так и используемой процедурой коррекции ошибок. Исследованию этих вопросов посвящена четвертая глава.
В пятой главе рассмотрена эффективность различных методов коррекции ошибок применительно к задачам квантовой криптографии, основанных на процедуре бисектив-ного поиска, комбинированном каскадном методе, а также на классических кодах Боуза-Чоудхури-Хоквингема и Хэмминга.
Наиболее простая итерационная процедура коррекции ошибок - это бисективный поиск ошибок, который сводится к разбиению первичного ключа на случайные непересекающиеся блоки и вычислению четностей этих блоков. Четности множеств сравниваются, как на приемном, так и на передающем конце через открытый канал. После раскрытия четности какого-либо множества, один из случайно выбранных битов, отбрасывается. При несовпадении четностей размер блока уменьшается вдвое, и процесс повторяется. Поскольку блоки не пересекаются, то выбрасывание битов не представляет труда. Такая процедура сохраняет конфиденциальность - подслушиватель не получает дополнительной информации при "чистке" первичного ключа. Однако, такая процедура крайне неэффективна, поскольку остается
достаточно мало битов в "очищенном" ключе (например, при вероятности ошибки в 10% в первичном ключе в "очищенном" ключе остается не более 10% от исходной длины).
Наиболее эффективным, в смысле длины "очищенного" ключа, на сегодняшний день, по-видимому, является каскадный метод коррекции ошибок, впервые предложенный в [22]. В исходном варианте каскадного метода биты четности отдельных, и, в общем случае, пересекающихся подмножеств запоминаются и используются на следующих проходах. В процессе работы метода никакие биты не выбрасываются, поэтому метод не сохраняет конфиденциальность. Оценить информацию, которую получает подслушиватель, когда раскрываются биты четности набора пересекающихся множеств, возникающие на разных проходах, достаточно сложно. До сих пор, насколько нам известно, полный анализ не был выполнен.
Сохранить конфиденциальность и эффективность метода можно, если в конце "чистки" первичного ключа отбрасывать некоторое количество битов. Поскольку, возникающие на каждом проходе множества битов пересекаются, то процедура выбрасывания не является тривиальной.
В данной главе предложен простой регулярный способ сохранения конфиденциальности (отбрасывания раскрытых при "чистке" битов четности пересекающихся множеств).
В шестой главе на основе результатов, полученных в предыдущих главах, приводится описание разработанного программного комплекса и алгоритмов обработки ключей, используемых в экспериментальном образце оптоволоконной системы квантовой криптографии.
Защищаемые положения.
Построена явная атака на передаваемый при помощи квантовых состояний ключ для протокола ВВ84, достигающая теоретического предела ошибки Qc т 11%, до которой возможно распределение ключей;
Дана оценка длины секретного ключа, которую можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах, для двух основных квантовых протоколов распределения ключей ВВ84 и В92;
Предложен метод сохранения конфиденциальности для каскадного метода коррекции ошибок в первичных ключах;
Разработаны алгоритмы и комрыотерные программы для распределенной коррекции ошибок.
Научная новизна и практическая значимость.
В диссертационной работе впервые построена явная атака на ключ в квантовой криптографии (протокол ВВ84), на которой достигается теоретический предел по критической ошибке. Данная атака является наилучшей для подслушивателя в том смысле, что подслу-шиватель получает максимум информации о ключе, производя при этом минимально возможную ошибку на приемной стороне. Впервые также выяснено, что происходит в области ошибок 11% < Qc < 15%. Показано, что существует бесконечный набор атак подслушивателя, которые приводят к ошибкам в данном диапазоне. Атаки отличаются друг от друга только на стадии измерений, которые производит подслушиватель. Выяснена связь получаемой подслушивателем информации о ключе при таких измерениях с набором классических пропускных способностей квантового канала связи. Показано, что для достижения теоретического предела по ошибке подслушивателю необходима квантовая память.
Получены оценки длины ключа для двух основных квантовых протоколов распределения ключей В92 и ВВ84.
Проведено сравнение эффективности различных методов распределенной коррекции ошибок в первичных ключах в квантовой криптографии. Показано, что наиболее эффективным методом является каскадный метод. Предложен метод исключения контрольных битов четности перекрывающихся множеств, которые возникают при коррекции ошибок. Это позволяет устранить информацию выдаваемую подслушивателю легитимными пользователями через открытый канал при коррекции ошибок. Использование данной процедуры позволяет гарантировать, что информация о ключе, которую имел подслушиватель до коррекции ошибок, не увеличится после их исправлении легитимными пользователя.
На основе теоретических исследований разработаны алгоритмы и компьтерные программы, которые использованы при разработке экспериментального образца оптоволоконной системы квантовой криптографии.
Апробация работы и публикации.
Результаты работы докладывались и обсуждались на следующих конференциях:
Международная конференция "Quantum Informatics - QI-2007", Москва, Россия, 2007 г.;
10 Научно-техническая конференция по криптографии, посвященная 85-летию образования Криптографической Службы России, Москва 2006 г., Академия Криптографии Российской Федерации, Секция 13.
Международная конференция "Quantum Informatics - QI-2005", Москва, Россия, 2005 г.;
Основные результаты диссертации опубликованы в работах:
С.Н.Молотков, А.В.Тимофеев, Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc « 11%, Письма в Журнал экспериментальной и теоретичесой физики, т.85, вып. 10, 634 (2007).
А.В.Тимофеев, С.Н.Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в Журнал экспериментальной и теоретичесой физики, т.82, вып. 12, 868 (2005).
А.В.Тимофеев, Д.И.Помозов, А.П.Маккавеев, С.Н.Молотков, О структуре открытого классического канала связи в квантовой криптографии: коррекция ошибок, целостность и аутентичность, Журнал экспериментальной и теоретической физики, т.131, вып.5, 771 (2007).
А.П.Маккавеев, С.Н.Молотков, Д.И.Помозов, А.В.Тимофеев, О практических методах "чистки" ключей в квантовой криптографии, Журнал экспериментальной и теоретической физики, т.128, вып.2, 263 (2005).
Информационные состояния и измерения
Используемые на практике процедуры исправления ошибок имеют большую избыточность, чем процедуры, основанные на случайных кодах. Поэтому Еве оказывается доступно большее количество информации, что приводит к меньшей допустимой критической ошибке, до которой возможно получение общего секретного ключа для Алимы м Боба.
Одной и важных задач является поиск эффективных процедур распределенной коррекции ошибок. После исправления ошибок Алисой и Бобом у них возникают одинаковые битовые строки ("очищенный" ключ). Однако информация Евы об "очищенном" клююче все еще1 является конечной, и заведомо не экспоненциально малой по параметру секретности. Для получения финального секретного ключа необходимо сжатие (хеширование) очищенного ключа при помощи универсальных функций хеширования второго рода [20] (Wegman, Carter), которые сами являются случайными величинами. Причем степень сжатия определяется как величиной ошибки в первичном ключе, так и используемой процедурой коррекции ошибок. Исследованию этих вопросов посвящена четвертая глава.
В пятой главе рассмотрена эффективность различных методов коррекции ошибок применительно к задачам квантовой криптографии, основанных на процедуре бисектив-ного поиска, комбинированном каскадном методе, а также на классических кодах Боуза-Чоудхури-Хоквингема и Хэмминга.
Наиболее простая итерационная процедура коррекции ошибок - это бисективный поиск ошибок, который сводится к разбиению первичного ключа на случайные непересекающиеся блоки и вычислению четностей этих блоков. Четности множеств сравниваются, как на приемном, так и на передающем конце через открытый канал. После раскрытия четности какого-либо множества, один из случайно выбранных битов, отбрасывается. При несовпадении четностей размер блока уменьшается вдвое, и процесс повторяется. Поскольку блоки не пересекаются, то выбрасывание битов не представляет труда. Такая процедура сохраняет конфиденциальность - подслушиватель не получает дополнительной информации при "чистке" первичного ключа. Однако, такая процедура крайне неэффективна, поскольку остается достаточно мало битов в "очищенном" ключе (например, при вероятности ошибки в 10% в первичном ключе в "очищенном" ключе остается не более 10% от исходной длины).
Наиболее эффективным, в смысле длины "очищенного" ключа, на сегодняшний день, по-видимому, является каскадный метод коррекции ошибок, впервые предложенный в [22]. В исходном варианте каскадного метода биты четности отдельных, и, в общем случае, пересекающихся подмножеств запоминаются и используются на следующих проходах. В процессе работы метода никакие биты не выбрасываются, поэтому метод не сохраняет конфиденциальность. Оценить информацию, которую получает подслушиватель, когда раскрываются биты четности набора пересекающихся множеств, возникающие на разных проходах, достаточно сложно. До сих пор, насколько нам известно, полный анализ не был выполнен.
Сохранить конфиденциальность и эффективность метода можно, если в конце "чистки" первичного ключа отбрасывать некоторое количество битов. Поскольку, возникающие на каждом проходе множества битов пересекаются, то процедура выбрасывания не является тривиальной. В данной главе предложен простой регулярный способ сохранения конфиденциальности (отбрасывания раскрытых при "чистке" битов четности пересекающихся множеств). В шестой главе на основе результатов, полученных в предыдущих главах, приводится описание разработанного программного комплекса и алгоритмов обработки ключей, используемых в экспериментальном образце оптоволоконной системы квантовой криптографии. Защищаемые положения. 1. Построена явная атака на передаваемый при помощи квантовых состояний ключ для протокола ВВ84, достигающая теоретического предела ошибки Qc т 11%, до которой возможно распределение ключей; 2. Дана оценка длины секретного ключа, которую можно получить при наблюдаемой вероятности ошибки Q Qc в первичных ключах, для двух основных квантовых протоколов распределения ключей ВВ84 и В92; 3. Предложен метод сохранения конфиденциальности для каскадного метода коррекции ошибок в первичных ключах; 4. Разработаны алгоритмы и комрыотерные программы для распределенной коррекции ошибок. Научная новизна и практическая значимость.
В диссертационной работе впервые построена явная атака на ключ в квантовой криптографии (протокол ВВ84), на которой достигается теоретический предел по критической ошибке. Данная атака является наилучшей для подслушивателя в том смысле, что подслу-шиватель получает максимум информации о ключе, производя при этом минимально возможную ошибку на приемной стороне. Впервые также выяснено, что происходит в области ошибок 11% Qc 15%. Показано, что существует бесконечный набор атак подслушивателя, которые приводят к ошибкам в данном диапазоне. Атаки отличаются друг от друга только на стадии измерений, которые производит подслушиватель. Выяснена связь получаемой подслушивателем информации о ключе при таких измерениях с набором классических пропускных способностей квантового канала связи. Показано, что для достижения теоретического предела по ошибке подслушивателю необходима квантовая память.
Проведено сравнение эффективности различных методов распределенной коррекции ошибок в первичных ключах в квантовой криптографии. Показано, что наиболее эффективным методом является каскадный метод. Предложен метод исключения контрольных битов четности перекрывающихся множеств, которые возникают при коррекции ошибок. Это позволяет устранить информацию выдаваемую подслушивателю легитимными пользователями через открытый канал при коррекции ошибок. Использование данной процедуры позволяет гарантировать, что информация о ключе, которую имел подслушиватель до коррекции ошибок, не увеличится после их исправлении легитимными пользователя.
На основе теоретических исследований разработаны алгоритмы и компьтерные программы, которые использованы при разработке экспериментального образца оптоволоконной системы квантовой криптографии.
Индивидуальные измерения подслушивателя
При этом в пределе больших п Боб сможет исправить все ошибки в своей строке с вероятностью единица. Ошибка Ева при этом будет стремится к единице (т.е. имеет место сильное обращение прямой теоремы кодирования). Алиса и Боб могут использовать всю строку длины п как секретный ключ.
Если же Ева имеет возможность делать коллективные квантово-механические измерения (2.15,2.16), она сможет различить с вероятностью единица правильную строку, если выбранное число кодовых слов легитимными пользователями М 2П СТАЕ 6 . Поэтому заведомо с момента, когда передача секретного ключа невозможна, если Ева может выполнять коллективные измерения.
В том случае, когда выбранное Алисой число кодовых слов М 2ПСТАЕ, ТО даже с использованием коллективных измерений Ева не сможет декодировать свою строку в правильное кодовое слово, в отличие от Бобы, который при числе кодовых слов М 2П САВ 6 сможет исправить с вероятностью единица все ошибки в своей строке длины п. Ошибка Евы при декодировании в среднем по всем кодовым словам при этом не менее
Т.е. имеет место, так называемое слабое обращение прямой теоремы кодирования. Ошибка отлична от нуля, но стремится к единице, но в отличие от классического случая или индивидуальных измерений Евы не экспоненциально по параметру U[CAB{Q) CAE{E(Q))\, а существенно медленнее.
В случае коллективных измерений (истинно квантовый случай) вероятность ошибки Евы в среднем при различении кодового слова не лучше, чем CAB{Q) — СтАЕі соответственно вероятность правильной интерпретации не более, чем 1 — [CAB(Q) СтАЕ\- При консервативной оценке, возможно завышенной в пользу Евы, Ева из всего числа кодовых слов М знает 2ПСТАВ. Поскольку при М 2ПСАВ Боб исправляет все ошибки в своей строке длины п, то завышая оценку по числу кодовых слов до полной размерности пространства 2", можно считать, что Ева знает долю бит из всего пространства равную 2ПСТАЕ/2П. Поскольку кодовые слова выбираются случайно и равномерно, то доля бит в каждой конкретной строке, которые Ева знает, не более пСтАЕ. Число бит в каждой строке, равное п[1 — СтАЕ], могут считаться легитимными пользователями секретными.
Ниже речь пойдет о протоколе ВВ84 [2], который был первым квантовым криптографическим протоколом, и который является основным и наиболее исследованным. Для данного протокола известна точная величина критической ошибки Qc « 11% [26, 27, 28]1. Строгие доказательства о критической величине Qc скорее являются теоремами существования и не предъявляют явную оптимальную стратегию подслушивателя, при которой достигается теоретически минимально возможное значение Qc. Точнее говоря, оптимальную стратегию в том смысле, что Ева извлекает максимум информации о ключе при данной наблюдаемой ошибке. При Q Qc взаимная информация между легитимными пользователями Алисой и Бобом о ключе, и Алисой и Евой IAB{Q) IAE{Q), что позволяет, согласно теореме [29], извлечь секретный ключ. При Q = Qc IAB{Q) — IAE{Q), получить секретный ключ нельзя. Формально длина секретного ключа при Q = Qc обращается в нуль.
Существует множество работ, в которых рассматриваютя частичные стратегии Евы. В частности была построена оптимальная стратегия Евы для индивидуальных измерений (см. [30]), которая на словах сводится к следующему. Ева в каждой посылке использует свое квантовое вспомогательное состояние \А) (ancilla), которое унитарно взаимодействует с передаваемым состоянием. В результате передаваемое состояние и \А) оказываются в запутанном состоянии. Состояние \А) изменяется в зависимости от передаваемого состояния. Изменяется также передаваемое состояние. Затем измененное состояние Алисы направляется к Бобу, а свое состояние Ева сохраняет у себя в квантовой памяти до стадии раскрытия базисов. После того, как Боб произвел измерения, происходит согласование базисов. То есть посылки, где Боб производил измерения в не согласованным с Алисой базисе отбрасываются. Далее Ева производит индивидуальные измерения над каждым своим состоянием с целью извлечения классической информации о передаваемом бите Алисы. Для такой стратегии найдена критическая величина ошибки, до которой возможно распределение секретных ключей. Кри 3нак w употребляется для краткости, точное значение Qc определяется как корень некоторого трансцендентного уравнения [28]. Ошибка оказывается равной Qc и 15%, что выше теоретического значения в 11%. Т.е. подобная стратегия Евы не является оптимальной в упомянутом выше смысле. На сегодняшний день никаких других явных стратегий Евы, при которых получается меньший вносимый процент ошибок не было предъявлено.
Будет показано, что если Ева использует на последнем шаге не индивидуальные измерения над каждым своим состоянием, а коллективные сразу над всеми состояниями, то в этом случае достигается минимальная предельно допустимая ошибка в 11%.
"Чистка" первичного ключа при помощи БЧХ кодов (Bose-Chaudhuri-Hocquenghem)
Таким образом, описана явная атака на ключ, при которой достигается максимум информации Евы при минимуме наблюдаемой ошибки на приемном конце. Данная атака сводится к реализации совместной эволюции в каждой посылке состояния, передаваемого-Алисой со вспомогательным состоянием Евы. Унитарный оператор U (3.1,3.2), описывающий совместную эволюцию состояния Алисы и Евы, строится явно (3.3-3.7). По нему можно предъявить квантовую схему, которая реализует такой оператор [34]. Далее Ева сохраняет состояния в квантовой памяти до раскрытия базисов Алисой и Бобом, и только затем производит коллективные измерения сразу над всеми состояниями.
Если Ева на конечном этапе, производит индивидуальные измерения, то это соответствует достижению пропускной способности квантового канала между Алисой и Евой за один шаг С\ (one shot). Критическая величина ошибки при этом Qc « 15%. При коллективных измерениях Евы достигается классичекая пропускная способность квантового канала связи С. Критическая ошибка при этом Qc 11%.
Данная область имела до сих пор некоторый налет мистики. До построения явной атаки нижняя граница (Qc « 11%) представляла собой точку, и было неясно при помощи какой атаки Ева может достичь эту границу. Правая граница (Qc 15%) достигается на оптимальной атаке с индивидуальными измерениями, такая атака была построена многими авторами (например, [30]).
Ответ на этот вопрос оказывается удивительно простым и укладывается в общую схему, изложенную выше. Любая атака Евы может быть разделена на две часть. Первую часть условно можно назвать унитарной. На этой стадии Ева готовит свое вспомогательное квантовое состояние (ancilla), которое некоторое время взаимодействует с передаваемым Алисой состоянием. Такое взаимодействие описывается унитарным оператором, который Ева может выбирать по своему усмотрению. После такого взаимодействия оба состояния изменяются и находятся, вообще говоря, в запутанном состоянии (entangled state). Возмущенное состояние Алисы Ева направляет к Бобу, а свое вспомогательное (также возмущенное) оставляет у себя.
Вторая часть атаки - измерение. Измеряя свое возмущенное состояние Ева пытается узнать, какое состояние передавала Алиса. Удивительным фактом является то, что бесконечный набор атак Евы, которые дают критические ошибки в интервале 11% Qc 15%, отличаются только на стадии измерений. Унитарная часть для всех атак является универсальной (одинаковой).
Как было отмечено в работе [35] для квантового канала связи (точнее c-q - classical-quantum, канала, в котором классическая информация передается при помощи квантовых состояний) существует бесконечный набор классических пропускных способностей квантового канала связи. А именно, если длина кодового слова равна 1 (квантовые состояния измеряются индивидуально в каждой посылке), то максимально достижимое количество классической информации, которое можно передать при помощи квантовых состояний, не превосходит Сі (в обозначениях [35] Сі,і). Если длина кодового слова равна всей длине последовательности п — со (что отвечает коллективным измерениям над всей последовательностью), то классическая информация, извлекаемая из квантовых состояний, ограничена С (в обозначениях [35] Сі)00)- Длина кодового слова к может быть любой от к — 1 до к = со, соответственно доступное количество классической информации не превосходит C\,k- Если длина кодового слова к, то это означает, что в переданной последовательности длины п возможны коллективные измерения над блоками состояний, содержащими не более, чем к квантовых состояний сразу. При этом Сід C\tk Ci)0O критическая ошибка определяется из условия что дает ответ на вопрос о том, что происходит в области критической ошибки между 11% и 15%.
Получены явные выражения лишь для Схд и Сі)00, для других к, сожалению, явное аналитическое выражение для Сі, неизвестно, но в принципе может быть получено численно. Для этого необходимо построить квантово-механическое измерение минимизирующее ошибку различения трех квантовых состояний.
До тех пор, пока не создано квантовой памяти можно исходить из критической ошибки в 15%. Даже если такая квантовая память и будет создана, это еще не решает проблему коллективного измерения для Евы. Заметим, что на сегодняшний день реализованы лишь измерения для двухфотонных состояний (измерения в белловском базисе), причем такие измерения при экспериментальной реализации требуют использования нелинейных оптических элементов (кристаллов с нелинейной восприимчивостью второго порядка х 2\ которая крайне мала и имеет порядок величины Ю-6.) Это означает, что эффективность такого измерительного устройства также крайне мала и пропорциональна х Измерения же п-фотонных состояний, если использовать те же оптические элементы (других пока не предложено), будут иметь эффективность (х )п- В связи с этим атака с коллективными измерениями на сегодняшний день находится далеко за пределами технологических возможностей, поэтому, даже если исходить из критической ошибки в 15% квантовая криптография имеет очень большой запас прочности.
Пример удаления битов четности пересекающихся подмножеств (сохранение конфиденциальности)
Как было показано в предыдущей главе, после работы квантовой части протокола Боба получает строку битов, которая в общем случае может отличаться от строки, переданной Алисой. Ева к этому моменту уже может получить некоторую информацию о ключе в результате подслушивания. Итак, для того, чтобы получить секретный ключ из этой строки нам необходимо исправить в ней все ошибки, и удалить информацию, раскрытую на предыдущем шаге. Коррекция ошибок происходит посредством обмена классической информацией по открытому каналу связи. Вся переданная на этом шаге информация считается известной Еве и должна быть удалена из ключа.
Перед коррекцией ошибок проверим, что строки у Алисы и Боба имеют одинаковую длину. Если это не так, то строки отбрасываются, и необходимо сгенерировать новые. На практике, различная длина строк означает потерю синхроимпульса на предыдущем этапе. Эта вероятность настолько мала, что не имеет смысл пытаться корректировать такие ошибки.
Далее рассматривается несколько методов коррекции ошибок в первичном ключе, и оценивается их эффективность. При рассмотрении конкретных алгоритмов "чистки" будем руководствоваться следующими критериями эффективности: Все ошибки в ключе должны быть исправлены с вероятностью, достаточно близкой к единице. Если после "чистки" в ключе остаются ошибки, этот ключ придется отбросить, и начать процесс заново. Алгоритм должен выдавать подслушивателю как можно меньше информации о ключе. В нашей системе в среднем на каждый бит ключа приходится порядка 103 посланных состояний, так что каждый бит дорог. Необходимо минимизировать сетевой трафик. Поскольку идеальных открытых каналов не существует, все посланные по сети биты должны шифроваться и подписываться, иначе подслушиватель сможет вмешаться в коррекцию ошибок. Шифрование осуществляется с помощью ключа, полученного на предыдущем шаге, так что каждый посланный по сети пакет уменьшает ресурс ключа Существует два основных класса алгоритмов для распределенной коррекции ошибок. Алгоритмы, основанные на кодах коррекции ошибок, и алгоритмы, основанные на проверках четности. Коды коррекции ошибок дают меньшее время выполнения и меньший трафик (по крайней мере, по числу посланных по сети пакетов). Проверки четности выдают меньше информации, но посылают большое количество пакетов маленького размера (несколько битов) по сети, и, соостветственно, работают дольше. Ниже приводятся описание и сравнительные характеристики различных алгоритмов "чистки". Один из естественных способов "чистки" первичного ключа состоит в использовании классических кодов исправляющих ошибки. Сразу и еще раз отметим, что эффективность кода не может быть установлена в отрыве от квантово-механической части протокола. Эффективность классического кода самого по себе еще не означает его эффективности применительно к задачам квантовой криптографии, поскольку эффективность кода определяется не только тем, сколь хорошо он исправляет, но и тем сколь сильно он изменяет исходные условные вероятности относительно первичного ключа у Евы. Ниже будет рассмотрена "чистка" первичного ключа при помощи БЧХ кодов [23, 24], которые представляют собой широкий класс достаточно хороших кодов, которые позволяют исправлять по несколько ошибок в блоке (кодовом слове), что позволяет в зависимости от оценки вероятности ошибки Q выбирать код динамически. Сначала введем минимально необходимые определения для БЧХ кодов, исправляющих t ошибок. Поле Галуа GF(2n) — векторное пространство двоичных слов длины гг, где все арифметические действия происходят по модулю 2. Линейный код 8 образует линейное подпространство в GF(2n). Код называется циклическим, если с = (с0, сх, ...сп-х) (с, = 0,1) является кодовым словом, то с = (сь ...cn_i, со) также есть кодовое слово. Удобно представлять векторы из GF(2n) многочленами от х степени не выше п— 1, коэффициентами которых являются координаты векторов Циклический код задается своим порождающим многочленом д(х) степени п — к (к - число информационных символов, п - длина кодового слова). Порождающий многочлен д(х) является делителем многочлена хп 1 — 1. Для любого циклического кода выполнено равенство хп 1 — 1 = g(x)h(x), h(x) - проверочный многочлен. Код БЧХ, исправляющий t ошибок, строится следующим образом. Выбирается примитивный элемент а расширенного поля GF(2n) (любой элемент поля получается как некоторая степень примитивного элемента, кроме того имеет место в GF(2) а = а2). Определяется множество элементов По этим элементам строится порождающий многочлен д(х), корнями которого является множество (5.2). Считается, что t задано, затем берется некоторое т, которое определяет длину кодового слова п = 2т — 1. Далее находятся минимальные многочлены fj(x) (многочлены минимальной степени), корнями которых являются степени примитивного элемента а? (j = 1,2, ...2t) в расширении поля GF{2) - GF(2n). Порождающий многочлен д(х) кода с длиной п находится как наименьшее общее кратное При декодировании был использован метод Питерсона-Горенштейпа-Цирлера [23, 24]. Пусть было передано кодовое слово с = (с0, С\, ....cn_i), которое на приемном конце содержит ошибку где е = (eh, ...Єг„) (аналогично в виде многочлена е(х) = е х4 + ...е х1", eix = 0,1)- вектор ошибок, и - число ошибок, которое, вообще говоря, неизвестно. Декодирование с исправлением ошибок осуществляется в три этапа. Во-первых, вычисление синдрома ошибок. Во-вторых, определение многочлена локаторов ошибок S(x). И в третьих, вычисление корней многочлена локаторов ошибок S(x), исправление ошибок. Т.е. определение ej и исправление.
