Квантовый алгоритм Шора
На английском языке: Shor's algorithm
Коротко

  • Квантовый алгоритм был разработан для решения задач факторизации целых чисел и дискретного логарифмирования в конечной группе. Опубликованный в 1994 году, этот алгоритм позволяет факторизовать число N за полиномиальное время (O(log3N)), используя O(log N) кубитов.
  • На практике это может означать, что при наличии квантового компьютера из приблизительно 3000 кубитов криптографическая система RSA с ключом длиной 2048 битов может быть эффективно взломана за время, лишь ненамного превосходящее требующееся для зашифрования.
  • Аналогично, могут быть взломаны криптографические системы DSA, EdDSA, ГОСТ Р 34.10-2012 и ряд других асимметричных криптографических систем, не обладающих свойством квантовой устойчивости. Отметим, что на стойкость симметричных шифров (AES, Кузнечик и другие) и хэш-функций (SHA, Стрибог и другие) алгоритм Шора не оказывает влияния, поскольку для их анализа применяются другие, не столь эффективные алгоритмы.
Подробно

Американский исследователь Питер Шор опубликовал квантовый алгоритм для факторизации целых чисел, получивший впоследствии его имя, в 1994 году. Этот алгоритм использует метод поиска периода функции и может быть адаптирован к решению задачи дискретного логарифмирования в конечной группе или в группе точек эллиптических кривых.
    Американский исследователь Питер Шор опубликовал квантовый алгоритм для факторизации целых чисел, получивший впоследствии его имя, в 1994 году. Этот алгоритм использует метод поиска периода функции и может быть адаптирован к решению задачи дискретного логарифмирования в конечной группе или в группе точек эллиптических кривых.

    Работоспособность алгоритма Шора была показана в 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 раза.
    Тем не менее, поскольку в современных телекоммуникационных сетях симметричные алгоритмы практически всегда используются в связке с асимметричными (как, например, в протоколе TLS), возможная реализация алгоритма Шора представляет реальную угрозу всему существующему криптографическому ландшафту. Злоумышленник может уже сегодня сохранять зашифрованные традиционными методами данные, а с появлением у него доступа к квантовому компьютеру дешифровать их.

    Для противодействия квантовой угрозе усилиями мирового криптографического сообщества, в том числе и команды QApp, ведется деятельность по разработке и внедрению квантово-устойчивых криптографических алгоритмов.

    Как уже сегодня использовать постквантовую криптографию для защиты данных вашего бизнеса

    1. Получить больше информации о квантовых угрозах и методах защиты именно для своей индустрии.
    2. Провести аудит текущей инфраструктуры кибербезопасности вашей компании, подобрать оптимальные решения защиты от квантовых угроз и разработать стратегию защиты.
    3. Провести пилотирование квантово-устойчивых решений и масштабировать полученный опыт.