Національний інститут стандартів і технологій США (NIST) з 2016 року просуває розробку криптографічних алгоритмів, стійких до квантових комп’ютерів. Проте Пітер Гутманн, професор комп’ютерних наук з Університету Окленда (Нова Зеландія), вважає це нісенітницею для читачів — і прямо про це заявив у своїй презентації під назвою «Чому квантовий криптоаналіз — це маячня».
Очікується, що потужний квантовий комп’ютер зможе зламати основу лснов сучасного світу – криптографію. Цей день уже називають катастрофою Q-Day. Багато публічних криптосистем, які використовуються сьогодні, постраждають – йдеться в огляді NIST з Постквантової криптографії (PQC).
Аргумент Гутманна проти такої паніки простий: досі квантові комп’ютери, які він вважає радше «фізичними експериментами», ніж перспективними продуктами, не змогли без шахрайства розкласти на множники жодного числа, більшого за 21.
Квантові обчислення та PQC — надзвичайно складні. Але сам процес злому RSA-шифрування — досить прямолінійний. Маючи модуль n з відкритого ключа, потрібно знайти два простих числа p і q, такі що n = p ? q.
Якщо n = 21, то p = 3, q = 7 — простенька 5-бітна реалізація RSA. Але якщо n має 1024 або 2048 біт, пошук p і q потребує колосальних обчислювальних ресурсів. Саме ця потреба в колосальних обчислювальних ресурсах робить злом криптографії фактично неможливим на кремнієвих процесорах – вони не надають потрібної обчислювальної потужності.
Занепокоєння NIST — і не тільки — полягає в тому, що колись квантовий комп’ютер зможе запускати алгоритм Шора, який суттєво пришвидшує розкладання великих чисел на прості множники. У такому разі дані, захищені занадто простими ключами, опиняться під загрозою. Щоб уникнути цього гіпотетичного ризику, NIST координує розробку «квантостійких» алгоритмів: HQC, CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, FALCON — замість RSA.
NIST зазначає, що деякі інженери припускають появу таких методів злому протягом 20 років. Оскільки саме стільки часу пішло на впровадження інфраструктури відкритих ключів, NIST вважає, що час готуватись.
Однак, якщо дивитися на сучасний стан квантових обчислень, потреба в нових алгоритмах виглядає не такою вже й нагальною. У статті Гутманн і співавтор Штефан Нойгаус, викладач інформатики з Німеччини, стверджують, що можливості сучасних квантових комп’ютерів можна відтворити за допомогою домашнього 8-бітного комп’ютера VIC-20 (1981 року), абакуса і собаки.
«PQC — це не математика і не інженерія, це ворожіння: “Прийде велика машина, і вона знищить всю існуючу криптографію. Буде Голод, Чума, Війна і довгий неврожай”»
У статті згадується, що IBM ще у 2001 році реалізувала алгоритм Шора на 7-кубітному квантовому комп’ютері, розклавши число 15. Через 10 років вдалося розкласти 21. У 2019 році IBM намагалась розкласти 35, але результат був вдалим лише у 14% випадків через численні помилки кубітів.
Дослідники з Шанхайського університету заявили, що використали квантовий комп’ютер D-Wave для розкладання 2048-бітного RSA-числа.
Але, за словами Гутманна й Нойгауса, вибрані прості числа були надто близькі одне до одного, що значно спрощує задачу.
Як у фокусника, що підготував колоду заздалегідь, автори пояснюють: «Факторизація у “квантовому стилі” — це фокуси з числами, підібраними так, щоб їх легко було розкласти експериментом з фізики або VIC-20, абакусом і собакою».
«Оскільки n = p ? q, квадратний корінь із n дає значення p і q з точністю до одного-двох бітів, якщо p і q близькі. Саме тому стандарти RSA, як FIPS 186, вимагають, щоб p і q відрізнялись щонайменше на 100 бітів (тобто на 2^100 або 1,3 ? 10^30, що називається “нонілліон”) — щоб не можна було приблизно вгадати їх через корінь», — пояснює Гутманн.
Аналогія зі світом ШІ: вихвалятися високими результатами в бенчмарках, використовуючи ШІ, який тренувався саме на цих тестах.
Тревор Лантінг, технічний директор D-Wave, прокоментував: «Це дослідження не є проривом. Це дослідження попередніх спроб використання квантового відпалу (annealing) для розкладання малих чисел. Щоб зламати сучасне шифрування, потрібні квантові процесори на багато порядків масштабніші. Загрози для криптографії не буде ще багато років. До того ж уже існують квантостійкі алгоритми. D-Wave не спеціалізується на криптографії, але нашу технологію використовують для виявлення загроз та атак».
Попри гучні заяви про «квантову перевагу» від Google, сумнівний прорив Microsoft із ферміонами Майорани, аргументи професора Даніеля Бернштайна з Університету Іллінойсу, що квантові комп’ютери не слід списувати з рахунків, і думку Скотта Ааронсона з Техаського університету, що квантові обчислення «майже готові до прориву», Гутманн залишається скептиком: ніхто найближчим часом не буде зламувати коди за допомогою «експериментів з фізики».
Гутманн уточнює, коли саме він зрозумів, що квантовий криптоаналіз — це міф.
«Якоїсь конкретної миті не було, — відповів він, — але з часом стало все очевидніше: жодного реального (не шахрайського) прориву не з’явилося. Це так само реально, як електроенергія з термоядерного синтезу, яка буде настільки дешевою, що її не доведеться рахувати».
«Я емпіричний гностик. Зі звичайною криптографією все чітко: є математика, інженерія, обчислювальні ресурси — і можна провести лінію на графіку: ось коли буде небезпечно. А PQC — це не наука. Це ворожіння».
«У презентації ми провели лінію через дві наявні точки PQC — і отримали, що рівень криптоаналізу, як у сучасних комп’ютерів, квантові досягнуть десь через 2000 років. І навіть ці точки — це фокуси, а не реальні результати алгоритму Шора для знаходження невідомих p і q. Тому ми в статті пропонуємо критерії оцінки таких заяв, які мають захищати від шахрайства».
«Насправді у нас нуль достовірних точок даних. Це доволі вагомий доказ, що криптоаналіз на базі фізичних експериментів нікуди не веде».
Гутманн додає: ми маємо стільки ж даних і щодо подорожей швидше за світло, і щодо телепортації, як у Star Trek, і щодо інших мрій техноутопістів.
На запитання, чи його скептицизм щодо PQC поширюється і на квантові комп’ютери загалом, Гутманн відповів, що найкраще це сформулував Австралійський інститут стратегічної політики (ASPI).
Коли його запитали, що варто робити фахівцям з кібербезпеки у зв’язку з переходом до PQC, він відповів:
«Нічого. Насправді ми більше втрачаємо. Сьогодні існує багатомільярдна індустрія кіберзлочинності, яка побудована на тому, що шифрування не виконує свою захисну функцію. І замість того, щоб виправити це, ми витрачаємо колосальні ресурси на впровадження нових алгоритмів, які не кращі, лише незручніші. Недарма їх ігнорували десятиліттями — вони не практичні. Перехід до PQC — це просто відволікання від реального, складного завдання».
За матеріалами: The Register
