УДК 004.27:004.056.55
П. Г. К л ю ч а р е в
КВАНТОВЫЙ КОМПЬЮТЕР И КРИПТОГРАФИ-
ЧЕСКАЯ СТОЙКОСТЬ СОВРЕМЕННЫХ СИСТЕМ
ШИФРОВАНИЯ
Рассмотрены квантовые алгоритмы, которые могут быть исполь-
зованы в задачах криптоанализа, и то влияние, которое могут ока-
зать квантовые компьютеры на информационную безопасность,
когда появятся их практические образцы.
Криптографические алгоритмы имеют большое значение в зада-
чах обеспечения информационной безопасности. Стойкость многих
современных криптоалгоритмов в настоящее время считается более
чем достаточной. Однако положение серьезнейшим образом изменит-
ся после разработки практических образцов квантовых компьютеров.
Современные криптоалгоритмы.
Современные алгоритмы ши-
фрования можно подразделить на симметричные и асимметричные
(алгоритмы с открытым ключом). Симметричный алгоритм шифрова-
ния (например, AES, RC6 и др.) считается достаточно стойким, если не
известны способы взлома этого криптоалгоритма, более быстрые, чем
полный перебор. Сложность полного перебора (для атаки с известным
шифротекстом) можно оценить как
O
(2
k
)
, где
k
— длина ключа в би-
тах. Учитывая, что в 2002 г. с помощью любительской сети распреде-
ленных вычислений distributed.net была продемонстрирована возмож-
ность взлома 64-битного ключа методом грубой силы, сейчас нормой
считается длина ключа 128 бит, а максимальная длина ключа, поддер-
живаемая большинством симметричных криптоалгоритмов, равна 256
битам.
Для асимметричных криптоалгоритмов известны способы крипто-
анализа, работающие значительно быстрее полного перебора. Из-за
этого асимметричные криптографические алгоритмы имеют длину
ключа, значительно б´ольшую, по сравнению с симметричными. Наи-
более часто применяются алгоритм RSA, основанный на вычисли-
тельной сложности задачи о факторизации целых чисел, и алгоритм
Эль-Гамаля, основанный на вычислительной сложности задачи дис-
кретного логарифмирования. Причем используются версии алгоритма
Эль-Гамаля для различных полей. В частности, большое значение име-
ет алгоритм Эль-Гамаля над группой точек эллиптической кривой [3]
(табл. 1).
Квантовые вычисления.
Квантовые компьютеры смогут решать
задачи криптоанализа значительно эффективнее по сравнению с клас-
сическими. Кратко рассмотрим основные положения теории кванто-
вых вычислений. Более обстоятельное введение можно найти, напри-
мер, в работе [1].
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 2
113
