Квантовый криптоанализ
Криптография с открытым ключом
Математики очень долго старались решить проблему передачи ключа (смотри введение в квантовую криптографию). В 1970-х годах придумали хитрую идею - системы с открытым ключом. В таких системах, пользователем не надо договариваться заранее о ключе перед тем, как послать сообщение. Они работают на принципе сейфа с двумя ключами: один общий ключ для того, чтобы закрыть его, а другой, частный, для того, чтобы открыть его. У всех есть ключ для того, чтобы закрыть сейф, так что любой человек может оставить в нём сообщение. но только у одного человека есть ключ, чтобы забрать это сообщение. На практике, два ключа - это два больших целых числа. Можно легко получить общий ключ из частного, но не наоборот. Система использует тот факт, что определённые математические операции легче производить в одном направлении, а не в противоположном. Криптосистемы с открытым ключом избегают проблем с передачей ключа, но, к несчастью, их безопасность зависит от недоказанных математических допущений, таких, как трудности факторизации (разложении на составляющие) больших чисел (RSA - самая популярная криптосистема с открытым ключом, сильно зависит от факторизации больших чисел). Враг, которому известен общий ключ, может, в принципе, вычислить частный ключ, потому что эти два ключа математически связаны, однако, сложность вычислений частного ключа из соответствующего общего ключа полностью зависит от факторизации больших чисел.
Трудность факторизации быстро возрастает с размером, то есть, количеством цифр числа, которые мы хотим разложить. Для того, чтобы увидеть это, возьмите число N, состоящее из L десятичных цифр (N ~ 10^L), и попробуйте разложить его путём деления на 2, 3, ..., Sqrt(N) и проверки остатка от деления. В худшем случае, вам понадобится приблизительно Sqrt(N) = 10^(L/2) делений для того, чтобы решить проблему - экспоненциальное увеличение функции L. Теперь представьте компьютер, способный производить 10^10 делений в секунду. Компьютер способен разложить любое число N, используя алгоритм последовательного перебора, примерно за Sqrt(N)/10^10 секунд. Возьмите число N, состоящее из 100 цифр, N = 10^100. Компьютер разложит это число примерно за 10^40 секунд, что гораздо больше, нежели 3.8 * 10^17 секунд (12 миллиардов лет) - примерный возраст вселенной!
Квантовая факторизация
Похоже, что разложение больших чисел лежит за пределами способностей любого реального компьютера и до тех пор, пока математики или компьютерные учёные не найдут эффективного алгоритма разложения, криптосистемы с открытым ключом останутся безопасными. Или нет? Как оказывается, нет; классическая, чисто математическая, теория вычислений является неполной просто потому, что она не описывает все физически возможные вычисления. В частности, она не описывает вычисления, которые могут быть произведены квантовыми устройствами. В самом деле, недавняя работа в области квантовых вычислений показывает, что квантовые компьютеры способны разложить число гораздо быстрей любого классического компьютера.
Квантовые компьютеры могут вычислять быстрей, потому что они принимают в качестве ввода не одно число, а когерентную суперпозицию множества различных чисел, после чего могут производить вычисления (последовательность единичных операций) на всех этих числах одновременно. Это можно представить как массивное параллельное вычисление, но вместо множества процессоров, работающих параллельно, мы имеем только один квантовый процессор, осуществляющий вычисление, которое воздействует на все числа в векторе. Для того, чтобы увидеть, как это работает, позвольте описать разложение Шора, использующее квантовый компьютер, составленных из двух квантовых регистров.
|
Математика разложения Квантовое разложение целого числа N основано на вычислении периодичности функции FN(x) = a^x mod N. Математическая спецификация этой функции означает: выберите произвольное число а между 0 и N, затем возведите его в степени x, разделите на N и запомните остаток от деления, который будет являться значением функции. Выясняется, что с увеличением степени числа a, остатки от деления формируют повторяющуюся последовательность с периодом, который мы обозначим r. Как только r найден, множители числа N могут быть получены вычислением наименьшего общего частного числа N и чисел a^(r/2) +/- 1. К счастью, простой и очень эффективный алгоритм для вычисления наименьшего общего частного был найден ещё в 300 году нашей эры. Алгоритм, описанный в *Элементах* Эвклида - наистарейшем греческом научном труде по математике - достиг нас в своём первоначальном состоянии (просмотрите ваши школьные учебники в качестве пособия). Допустим, мы хотим разложить число 15, используя этот метод. Пусть а=11. Для увеличивающегося x функция 11^x mod 15 формирует повторяющуюся последовательность 1, 11, 1, 11, 1, 11, ... Период r=2. Вычисляем промежуточные коэффициенты a^(r/2)+1=12, a^(r/2)-1=10. Теперь мы берём наименьшее общее частное чисел 10 и 15, и 12 и 15, что даёт нам соответственно 5 и 3 - два множителя числа 15. Классически, подсчёт r является таким же трудным, как и попытка разложить N, используя технику последовательного перебора делителей, то есть время выполнения вычислений возрастает экспоненциально при увеличении цифр в N. Квантовые компьютеры могут найти r в течении времени, которое растёт только как квадратичная функция от количества цифр в N. |
Представьте себе два квантовых регистра, каждый регистр состоит из определённого числа двухпозиционных квантовых систем, которые мы называем "кубитами" (квантовыми битами). Возьмём первый регистр и поместим его в суперпозицию всех возможных целочисленных значений, которые могут в нём находится. Это можно сделать, если первоначально установить все кубиты в состояние 0, а затем применить к каждому кубиту унитарное преобразование, которое создаёт суперпозицию состояний 0 и 1:
|0> ---> 1/\/2*(|0> + |1>)
Представьте двухкубитовый регистр, к примеру. После этой процедуры регистр будет находится в суперпозиции всех четырёх чисел, которые он может содержать,
1/\/2*(|0> + |1>) x 1/\/2*(|0> + |1>) = 1/2*(|00> + |01> + |10> + |11>)
где 00 - двоичный 0, 01 - двоичная 1, 10 - двоичная 2, и наконец, 11 - двоичная 3.
Затем мы производим арифметическую операцию, которая воспользуется преимуществом квантового параллелизма для вычисления функции FN(x) для каждого x в суперпозиции. Значения FN(x) заносятся во второй регистр, так что после вычисления два регистра оказываются переплетёнными:
Sumx(|x>|F(x))
(мы проигнорировали нормализационную константу). Теперь произведём измерение второго регистра. Измерение выдаёт случайно выбранное значение FN(k) для некоторого k. Состояние первого регистра сразу после измерения, вследствие периодичности FN(x), является когерентной суперпозицией всех состояний |x>, при которых x = k, k+r, k+2r, ..., то есть всех k, для которых FN(x) = FN(k). Значение k выбирается случайным образом, следовательно состояние первого регистра впоследствии трансформируется, посредством единичных операций, которые устанавливают любое k в 0 (то есть |k> становится равным |0> плюс фазовый фактор) и модифицируют период r до множества из 1/r. Эта операция известна как квантовое преобразование Фурье. Первый регистр после этого готов к последнему измерению, которые выдаст число, которое является наиболее лучше аппроксимацией множества из 1/r. Из этого результата можно вычислить r, после чего можно легко вычислить множители числа N. Время выполнения квантового алгоритма разложения предполагается, будет расти как квадратичная зависимость от L, и числа, состоящие из 100 цифр могут быть разложены за доли секунды!
Открытым вопросом остаётся, возможно ли практически построить когда-либо физическое устройство, способное выполнять подобные вычисления, или они навечно останутся лишь теоретическим любопытством. Квантовые компьютеры требует когерентность - управляемое развитие в течении периода времени, необходимого для окончания вычисления. Многие видят это требование как непреодолимую экспериментальную проблему, однако, мы полагаем, что технологический прогресс рано или поздно, сделает подобные устройства реальными. Как только первое устройство, способное осуществлять квантовое разложение, будет построено, безопасность криптосистем с общим ключом разрушится. Математическое решение распространения ключа разобьётся о мощь квантовых вычислений. Отставляет ли это нас безо всякой надежды защитить нашу конфиденциальность? К счастью, квантовая механика, после уничтожения классических шифров, спасёт нашу конфиденциальность, предложив своё собственное решение проблемы распространения ключа. Это называется "квантовой криптографией".
DrawFooter();
