Квантовый алгоритм Шора
На английском языке: Shor's algorithm
Коротко
- Квантовый алгоритм был разработан для решения задач факторизации целых чисел и дискретного логарифмирования в конечной группе. Опубликованный в 1994 году, этот алгоритм позволяет факторизовать число N за полиномиальное время (O(log3N)), используя O(log N) кубитов;
- На практике это может означать, что при наличии квантового компьютера из приблизительно 3000 кубитов криптографическая система RSA с ключом длиной 2048 битов может быть эффективно взломана за время, лишь ненамного превосходящее требующееся для зашифрования;
- Аналогично могут быть взломаны криптографические системы DSA, EdDSA, ГОСТ Р 34.10-2012 и ряд других асимметричных криптографических систем не обладающих свойством квантовой устойчивости. Отметим, что на стойкость симметричных шифров (AES, Кузнечик и другие) и хэш-функций (SHA, Стрибог и другие) алгоритм Шора не оказывает влияния, поскольку для их анализа применяются другие, не столь эффективные алгоритмы.
Подробно
Американский математик Питер Шор разработал квантовый алгоритм для целочисленной факторизации, позже названный в его честь, в 1994 году. Алгоритм использует метод определения периода функции и может быть настроен для решения задач вычисления дискретного логарифма в конечной группе или группе точек эллиптических
Работоспособность алгоритма Шора была показана в 2001 году на примере факторизации числа 15 на квантовом компьютере из 7 кубитов.
В случае создания квантового компьютера достаточной мощности алгоритм Шора позволит эффективно (за время, лишь ненамного превосходящее требующееся для зашифрования) взламывать большинство используемых сейчас асимметричных криптографических схем (RSA, DSA, EdDSA, ГОСТ Р 34.10-2012 и других).
Работоспособность алгоритма Шора была показана в 2001 году на примере факторизации числа 15 на квантовом компьютере из 7 кубитов.
В случае создания квантового компьютера достаточной мощности алгоритм Шора позволит эффективно (за время, лишь ненамного превосходящее требующееся для зашифрования) взламывать большинство используемых сейчас асимметричных криптографических схем (RSA, DSA, EdDSA, ГОСТ Р 34.10-2012 и других).
Питер Шор
Права на фотографию: BBVA FOUNDATION
В таблице ниже приведены актуальные на начало 2021 года рекорды по факторизации чисел, используемых в качестве открытого ключа в наиболее распространенной криптосистеме с открытым ключом RSA. Для сравнения также даны рекорды факторизации достигнутые на классических компьютерах.
На рисунке приведен график построенной по второй колонке этой таблицы экстраполирующей функции (по оси X — год, по оси Y — количество битов в числах RSA, факторизуемых квантовым вычислителем). Учитывая, что современные зарубежные рекомендации по защите информации предполагают использование в криптосистеме RSA чисел размера не менее 2048 битов (рекомендовано 3072), можно сделать вывод о том, что квантовые компьютеры, способные эффективно решать задачи криптоанализа используемых сейчас криптосистем, будут доступны в диапазоне 2028-2033 годов.
Рис. 1: экстраполяция возможностей квантовых вычислителей по факторизации чисел RSA.
Отметим также, что некоторые из указанных в таблице рекордов по факторизации чисел получены при помощи квантовых компьютеров, реализующих модели, которые ранее считались не вполне подходящими для решения задач криптоанализа, таких как модель квантового отжига, реализованного в квантовых вычислителях производства компании D-Wave.
На стойкость симметричных шифров (AES, Кузнечик и других) и хэш-функций (SHA, Стрибог и других) алгоритм Шора не оказывает влияния, поскольку для их анализа применяются другие, не столь эффективные алгоритмы (метод Гровера, Саймона, BHT и другие), для успешной защиты от которых достаточно увеличить размер параметров в 2-3 раза.
На стойкость симметричных шифров (AES, Кузнечик и других) и хэш-функций (SHA, Стрибог и других) алгоритм Шора не оказывает влияния, поскольку для их анализа применяются другие, не столь эффективные алгоритмы (метод Гровера, Саймона, BHT и другие), для успешной защиты от которых достаточно увеличить размер параметров в 2-3 раза.
Тем не менее, поскольку в современных телекоммуникационных сетях симметричные алгоритмы практически всегда используются в связке с асимметричными (как, например, в протоколе TLS), возможная реализация алгоритма Шора представляет реальную угрозу всему существующему криптографическому ландшафту. Злоумышленник может уже сегодня сохранять зашифрованные традиционными методами данные, а с появлением у него доступа к квантовому компьютеру дешифровать их.
Для противодействия квантовой угрозе усилиями мирового криптографического сообщества, в том числе и команды QApp, ведется деятельность по разработке и внедрению квантово-устойчивых криптографических алгоритмов.
Для противодействия квантовой угрозе усилиями мирового криптографического сообщества, в том числе и команды QApp, ведется деятельность по разработке и внедрению квантово-устойчивых криптографических алгоритмов.
Как уже сегодня использовать постквантовую криптографию для защиты данных вашего бизнеса?
- Получить больше информации о квантовых угрозах и методах защиты именно для своей индустрии;
- Провести аудит текущей инфраструктуры кибербезопасности вашей компании, подобрать оптимальные решения защиты от квантовых угроз и разработать стратегию защиты;
- Провести пилотирование квантово-устойчивых решений и масштабировать полученный опыт.