Как показал Л. Гровер в работе [2], это преобразование может быть
эффективно реализовано на квантовом компьютере, а сложность всего
алгоритма оценивается как
O
2
n/
2
.
Таким образом, появление квантовых компьютеров приведет к сни-
жению эффективной длины ключа в два раза. Это говорит о том,
что уже сейчас следует использовать симметричные шифры с длиной
ключа не менее 256 битов.
Кроме того, аналогичный алгоритм может быть использован для
взлома хэш-функций, в связи с чем следует использовать хэш-функции
с длиной блока не менее 256 битов.
Криптостойкость системы RSA.
Стойкость системы асимметрич-
ного шифрования RSA основывается на сверхполиномиальной вычи-
слительной сложности факторизации натуральных чисел. Однако су-
ществует квантовый алгоритм, сложность которого полиномиальна.
Поставим задачу следующим образом: по натуральному числу
N
,
имеющему ровно два простых делителя, найти эти делители. Заме-
тим, что для некоторого числа
a
его порядок по модулю
N
(т.е. мини-
мальное число
r
такое, что
a
r
= 1
(mod
N
)
) четен. Тогда мы можем
выражение
a
r
= 1
(mod
N
)
записать в виде
a
r
2
−
1
a
r
2
+ 1 = 0 (mod
N
)
.
То есть, зная
r
, мы можем эффективно найти делители числа
N
.
Заметим, что порядок
r
фактически является периодом функции
a
x
(
mod
N
)
.
Для нахождения периода функции существует следующий кванто-
вый алгоритм.
Пусть у нас есть периодическая функция
f
(
x
)
. Область опреде-
ления и область значений этой функции — множество целых чисел,
причем
0
6
x
6
2
n
−
1
и
0
6
f
(
x
)
6
2
m
−
1
. Для того, чтобы найти
период этой функции, нам нужен квантовый регистр, состоящий из
n
+
m
квантовых битов. Приведем его в состояние
1
√
2
n
2
n
−
1
X
x
=0
|
x,
0
i
.
Теперь вычислим от него функцию
f
, так чтобы у нас получилось
состояние
1
√
2
n
2
n
−
1
X
x
=0
|
x, f
(
x
)
i
.
Затем проведем измерение последних
m
квантовых битов (т.е.
квантовых битов, относящихся к
f
(
x
))
. После него наш квантовый
регистр перейдет в состояние
X
x
:
f
(
x
)=
u
|
x, u
i
.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 2
117
