Как Шор и Гроуър променят криптографския риск: практическа квантова демонстрация

Квантовите изчисления често се обсъждат чрез бъдещи сценарии: какво може да се случи, когато достатъчно мощни квантови компютри станат реалност, кои алгоритми могат да се окажат уязвими и кога организациите трябва да започнат подготовка.

По-полезният начин да разберем риска е да погледнем механизмите зад него.

Два квантови алгоритъма са особено важни за киберсигурността: алгоритъмът на Шор и алгоритъмът на Гроувър. Те влияят на криптографията по съществено различен начин. Шор засяга математическите проблеми, върху които се основава широко използваната публично-ключова криптография, докато Гроувър ускорява търсенето в големи пространства от възможни стойности, включително криптографски ключове.

За да покаже тази разлика, CISO на DIAMATIX Красимир Коев, PhD, разработи програмни демонстрации с Python и Qiskit Software Development Kit. Примерите използват малки или силно опростени стойности. Те не представляват атаки срещу реални production RSA или AES системи. Целта им е да направят техническия принцип зад квантовия риск по-ясен и видим.

Това разграничение е важно. Квантовият риск не е едно събитие, което засяга всички криптографски механизми по един и същ начин.

Алгоритъмът на Шор: защо публично-ключовата криптография изисква внимание

RSA (Rivest-Shamir-Adleman) се основава на математическа асиметрия.

Умножаването на две големи прости числа е лесна задача. Ако разполагаме само с произведението им, намирането на първоначалните множители става изключително трудно при достатъчно големи числа.

Тази трудност е една от основите на сигурността на RSA.

Алгоритъмът на Шор променя модела, защото предлага квантов подход за решаване на факторизацията много по-ефективно от известните класически методи.

Вместо последователно да проверява възможни множители, квантовата част на алгоритъма превръща факторизацията в задача за намиране на период. Квантовата суперпозиция позволява да бъде обработена информация за множество възможни стойности, а QFT (Quantum Fourier Transform) помага да се извлече периодичната структура, необходима за възстановяване на множителите.

Затова достатъчно способен квантов компютър би създал фундаментално различен проблем за RSA. Не става дума просто за „по-бърз компютър“. Алгоритъмът атакува математическата трудност, върху която криптографският механизъм разчита.

Малък RSA пример

За да бъде механизмът видим, демонстрацията използва умишлено малък RSA-подобен пример:

N = 35 = 5 × 7

Публичната информация съдържа N. Нападателят първоначално не знае простите множители 5 и 7.

В демонстрацията алгоритъмът на Шор използва намиране на период за избрана стойност. След като бъде открит подходящ период, класически изчисления с най-голям общ делител позволяват двата множителя да бъдат възстановени.

В използвания пример:

• избира се стойност 4;

• откритият период е 6;

• половината от периода е 3;

• 4³ mod 35 дава 29;

• най-големият общ делител на 28 и 35, както и на 30 и 35, разкрива съответно 7 и 5.

Резултатът е факторизацията на N.

След като тези множители са известни, става възможно да бъде възстановена математическата информация, необходима за частния RSA ключ.

Този пример използва много малки числа, които могат лесно да бъдат факторизирани и по класически начин. Това е умишлено. Демонстрацията показва логиката на алгоритъма, а не реалния мащаб, необходим за атака срещу production RSA ключове.

Фигура 1. Демонстрационна квантова схема на алгоритъма на Шор, реализирана с Qiskit.

На пръв поглед схемата изглежда сложна, но може да бъде разгледана като няколко функционални етапа.

Броящите кубити се намират в горната част. H (Hadamard) операциите ги поставят в суперпозиция, така че по време на изчислението да може да бъде представена информация за множество възможни стойности.

Долният регистър съдържа целевите кубити, върху които контролираните унитарни операции изпълняват модулните изчисления, свързани с търсенето на периода.

Големият блок към края на схемата представлява обратното QFT (Quantum Fourier Transform). Неговата задача е да преобразува натрупаната квантова фазова информация във форма, от която може да бъде извлечен периодът.

Накрая броящите кубити се измерват, а резултатите се записват в класически битове. След това класическата обработка използва тези стойности, за да изчисли периода и в крайна сметка да възстанови множителите.

Най-важният извод за сигурността не е броят на операциите в схемата. Важен е изчислителният модел зад тях. Шор предоставя принципно различен начин за решаване на факторизационния проблем, върху който RSA разчита да бъде труден.

Какво показва демонстрацията на Шор и какво не показва

Демонстрацията не показва, че реални RSA системи могат днес да бъдат разбивани с обикновен лаптоп или с публично достъпните квантови устройства.

Тя показва защо RSA принадлежи към групата криптографски системи, за които трябва да има миграционен план преди появата на криптографски релевантни квантови компютри.

Подобен риск съществува и за други публично-ключови механизми, чиято сигурност зависи от математически задачи, за които са известни ефективни квантови алгоритми, включително криптографията върху елиптични криви.

Това има практическо значение за сигурността. Организациите трябва да знаят къде подобни механизми се използват в:

• сертификати;

• VPN връзки;

• системи за удостоверяване;

• цифрови подписи;

• приложения;

• устройства;

• услуги на външни доставчици.

Това е една от причините криптографският инвентар да се превръща във важна част от постквантовата готовност.

Алгоритъмът на Гроувър: различен тип квантово предимство

Grover решава различен тип проблем.

Представете си търсене в неподреден набор от възможни отговори. Класическият алгоритъм може да се наложи да провери до N възможности. Гроувър намалява сложността приблизително до √N квантови итерации.

Алгоритъмът започва, като поставя възможните състояния в суперпозиция.

След това оракул идентифицира търсеното състояние чрез промяна на фазата му.

Дифузионен оператор усилва вероятността на маркираното състояние и намалява вероятността на останалите.

След няколко повторения измерването на системата е много по-вероятно да върне правилния резултат.

За киберсигурността това е важно, защото търсенето на криптографски ключ е по същество задача за търсене.

Демонстрация на Гроувър с квантово състояние

Първата демонстрация използва три кубита, което създава осем възможни състояния.

Търсеното състояние е:

|101⟩

H (Hadamard) операциите първоначално поставят всичките осем състояния в суперпозиция.

Оракулът маркира |101⟩. Дифузионната операция след това увеличава вероятността именно това състояние да бъде измерено.

Повторението на този процес прави |101⟩ все по-вероятен резултат при измерване.

Фигура 2. Демонстрационна схема на алгоритъма на Grover с три кубита.

Трите хоризонтални квантови линии представляват кубитите, които изграждат пространството за търсене.

Началните H операции създават равномерна суперпозиция на възможните състояния.

Оракулът маркира търсеното решение чрез промяна на фазата му. Той не „показва“ директно правилния отговор, а го маркира по начин, който позволява на следващата част от алгоритъма да усили неговата вероятност.

Операциите след оракула формират дифузионния процес. Повтарянето на оракул и дифузия постепенно концентрира вероятността около търсеното състояние.

Символите за измерване в края преобразуват квантовото състояние в класически резултат.

Концептуално Гроувър не знае предварително правилния отговор. Той променя разпределението на вероятностите така, че правилният кандидат да стане значително по-вероятен при измерване.

Какво означава това за криптографските ключове

Втората демонстрация свързва същия принцип директно с криптографията.

Използва се силно опростен AES-подобен шифър с 5-битов ключ. Това означава само 32 възможни ключа, което прави примера достатъчно малък за ясна демонстрация.

В примера са известни:

• plaintext: 00000;

• ciphertext: 10110;

• неизвестен 5-битов ключ.

Всички възможни ключове се поставят в суперпозиция.

Оракулът проверява кой кандидат генерира очаквания ciphertext и маркира този ключ. Дифузионният процес след това увеличава вероятността му.

При пространство от 2⁵ възможности демонстрацията използва приблизително четири итерации на Grover, преди измерването да даде най-силния кандидат за ключ.

Това е учебен модел. Използваният шифър не е AES-128 и примерът не трябва да се интерпретира като практическо разбиване на AES.

Неговата стойност е в това, че показва как квантовото търсене променя изчислителната цена на brute-force атака.

Шор и Гроувър влияят на криптографията по различен начин

Това разграничение е едно от най-важните за организациите, които планират постквантова готовност.

Shor променя сигурностния модел зад важни публично-ключови системи.

При RSA и свързани механизми достатъчно мощното квантово изчисление може да компрометира математическата задача, върху която сигурността им се основава. Затова постквантовата миграция поставя силен акцент върху обмена на ключове, сертификатите, цифровите подписи и публично-ключовата инфраструктура.

Grover предоставя квадратично ускорение при задачи за търсене.

При симетричната криптография ефектът е различен. Пространството на ключовете не изчезва, но изчислителната цена на изчерпателното търсене намалява.

Затова публично-ключовата и симетричната криптография не трябва да бъдат третирани като един и същ тип квантов риск.

Това е и причината твърдения като „квантовите компютри ще разбият криптирането“ да са твърде общи, за да бъдат полезни за реално управление на сигурността.

Екипите трябва да знаят каква криптография използват, къде я използват, какво защитава тя и как конкретният квантов риск се отнася към съответния механизъм.

Защо тези малки демонстрации са важни за реалната сигурност

Нито една от двете демонстрации не представлява непосредствена атака срещу production среда.

Стойността им е архитектурна.

Те показват, че постквантовото планиране се основава на известни изчислителни свойства, а не на абстрактната идея, че квантовите компютри просто ще бъдат „много по-бързи“.

За организациите това води до няколко практически извода.

Публично-ключовите зависимости трябва да могат да бъдат открити

RSA и ECC (Elliptic Curve Cryptography) могат да присъстват в:

• TLS сертификати;

• виртуални частни мрежи;

• цифрови подписи;

• идентичност на устройства;

• системи за удостоверяване;

• подписване на софтуер и фърмуер;

• облачни услуги;

• продукти на трети страни.

Ако организацията не знае къде съществуват тези зависимости, планирането на тяхната подмяна става трудно.

Симетричната криптография изисква различна оценка

AES (Advanced Encryption Standard) и други симетрични механизми не се засягат по същия начин като RSA.

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

Замяната на всеки криптографски механизъм с едно и също решение би могла да създаде нови оперативни проблеми, вместо да реши съществуващите.

Миграцията изисква crypto-agility

Алгоритмите и стандартите ще продължат да се развиват.

Затова системите трябва да позволяват криптографските механизми да бъдат сменяни без цялостно препроектиране на приложението или инфраструктурата.

Crypto-agility, или криптографска гъвкавост, означава възможност за контролирана промяна на алгоритми, сертификати, ключове, библиотеки и политики с развитието на стандартите и поддръжката от доставчиците.

Целта не е да бъде предвидена точната дата на бъдещ квантов пробив. Целта е да се намали количеството инфраструктура, която би била трудно променима, когато миграцията стане необходима.

От демонстрацията към постквантова готовност

Техническият урок от Шор и Гроувър води до практически въпрос за сигурността:

Колко лесно организацията може да идентифицира и промени криптографията, от която зависи днес?

Практична начална рамка включва:

• идентифициране на публично-ключови и симетрични криптографски зависимости;

• картографиране на сертификати, VPN, ключове, цифрови подписи и криптографски библиотеки;

• откриване на системи, които защитават дългосрочно чувствителна информация;

• преглед на постквантовите планове на доставчиците;

• тестване на съвместимост и производителност преди миграция;

• проектиране на нови системи с crypto-agility.

Тук техническата демонстрация се превръща в реален въпрос за оперативната сигурност.

Самата квантова схема не казва на организацията какво трябва да мигрира първо. Разбирането как различните алгоритми влияят на различните криптографски механизми помага да бъдат определени зависимостите, които изискват най-голямо внимание.

DIAMATIX перспектива

Квантовите изчисления не създават един универсален криптографски риск.

Алгоритъмът на Шор показва защо широко използвани публично-ключови механизми изискват планиран преход. Гроувър показва защо симетричната криптография трябва да бъде оценявана по различен начин, според силата на ключовете, реализацията и оперативния контекст.

За DIAMATIX практическият въпрос не е дали организацията трябва незабавно да подмени цялата си криптография.

По-важните въпроси са:

• Къде се използва криптография?

• Каква функция изпълнява всеки механизъм?

• Кои системи защитават информация, която трябва да остане поверителна с години?

• Кои зависимости могат да бъдат сменени лесно и кои са вградени в инфраструктура с дълъг жизнен цикъл?

• Могат ли доставчиците да поддържат контролиран постквантов преход?

Техническите демонстрации помагат да се разбере рискът. Криптографската видимост и crypto-agility определят колко управляем ще бъде този риск на практика.

Постквантовата готовност започва с разбиране на текущата среда, преди да започне нейната промяна.

За по-широкия контекст на този преход прочетете първата ни статия „Постквантова криптография: защо подготовката започва още сега“, в която разглеждаме защо постквантовата готовност вече се превръща в оперативен въпрос, от криптографския инвентар и дългосрочно чувствителните данни до плановете на доставчиците и crypto-agility.

Заключение

Шор и Гроувър показват два различни начина, по които квантовите изчисления могат да повлияят на киберсигурността.

Шор засяга математически структури, използвани от важни публично-ключови криптографски системи. Гроувър променя изчислителната цена на изчерпателното търсене и затова влияе различно на симетричната криптография.

Малките демонстрации в този материал не представляват атаки срещу production RSA или AES реализации. Те правят основните принципи видими.

Точно това е практическата им стойност.

Организациите не трябва да реагират на квантовите технологии с незабавни мащабни подмени. Те трябва да знаят върху какви криптографски предположения разчитат системите им и дали тези системи могат да бъдат адаптирани, когато миграцията стане необходима.

Техническият проблем започва с алгоритмите. Оперативният проблем започва с видимостта.

Източници

• DIAMATIX technical demonstration by Krasimir Koev, PhD, Chief Information Security Officer, using Python and Qiskit.

• NIST. Post-Quantum Cryptography Standardization.

• NIST. FIPS 203, FIPS 204 and FIPS 205.

• IBM Qiskit documentation. Quantum algorithms and circuit implementation.