Час панікувати? Як людство готується до квантового апокаліпсису, який може настати вже зовсім скоро

Вони зможуть проводити обчислення в мільйони разів швидше за звичайні комп’ютери. І це палиця з двома кінцями — з одного боку це допоможе нам зробити величезну кількість відкриттів у різних галузях науки; з іншого — це приведе нас до квантового апокаліпсису, коли всі досягнення криптографії, які зараз працюють, стануть марними.

Хакери вже можуть збирати зашифровані дані, які вони зможуть зламати за допомогою квантових технологій, як тільки ті з’являться на ринку. Потенційно це дасть зловмисникам відкритий доступ до всього, що відбувається в інтернеті, адже квантові комп’ютери зможуть підбирати ключі шифрування для сучасних криптографічних протоколів за лічені хвилини.

Зараз криптографічні алгоритми засновані на факторизації. І якщо традиційним комп’ютерам практично неможливо працювати з неймовірно великим списком ймовірних паролів, то його квантовий аналог, який використовує алгоритм Шора, впорається з таким завданням без особливих труднощів.

Саме тому інженери вже активно працюють над створенням та впровадженням постквантової криптографії. Журнал Nature докладно розповів, як зараз просувається робота в цьому напрямі.

У 1976 році троє американських учених-комп'ютерників — Вітфілд Діффі, Мартін Хеллман і Ральф Меркл створили концепцію шифрування з відкритим ключем, яка вперше дозволила людям обмінюватися інформацією без побоювання бути «підслуханими» в інтернеті.

Тут концепція максимально проста, адже вона використовує лише два числа: перше, тобто відкритий ключ, «шифрує» повідомлення; другий, тобто секретний ключ, «розшифровує» його. Зараз на неї покладається практично будь-який пристрій, підключений до Інтернету. Але, звичайно, з метою безпеки, з часів початку інтернету алгоритми ставали дедалі складнішими.

У 1990-х популярним став алгоритм RSA, який покладається на множення простих цілих чисел для створення відкритих і секретних ключів. Помножити два великі числа не так вже й складно, проте знайти невідомі прості множники певної кількості — завдання не з простих, хоч і реальне навіть для звичайних сучасних комп’ютерів методом перебору.

Через це у 2018 році Інженерна рада Інтернету (IETF) схвалила криптографію на основі еліптичних кривих, яка мала замінити застарілу технологію. Нова система заснована на обчисленні n-ого ступеня цілого числа, яке пов’язане з точкою на кривій. Число n, що є відкритим ключем, знає лише одна сторона, а вирахувати його набагато складніше, ніж підібрати прості множники числа, як у алгоритмі попереднього покоління.

Проте квантовий комп’ютер без проблем впорається із сучасними криптографічними підходами, що ґрунтуються на математиці простих чисел. Постквантова криптографія будується на алгоритмах, у яких застосовуються складніші завдання.

У 2015 році Агентство національної безпеки США заявило про вразливість існуючих криптографічних систем. Через рік NIST (Національний інститут стандартів та технологій у США) запропонував усім бажаючим інженерам представити потенційні постквантові алгоритми. 82 команди з різних країн світу представили свої алгоритми, з яких відібрали 65. Після початку «конкурсу», інженери почали зламувати алгоритми один одного, а згодом список скоротився до 15. Вже скоро NIST оголосить про результати дослідження і співтовариство отримає перші алгоритми, що пройшли перевірку.

Більшість алгоритмів, що потрапили до «півфіналу», прямо чи опосередковано спираються на криптографію на основі математики решіток. Вона використовує набори точок, які розміщуються на перетинах прямих ліній (решітки), які проходять через простір. Чим більше вимірів у решітці — тим більше часу займає її декодинг.

Найпопулярнішим підходом цього напряму є навчання з помилками (LWE — learning with errors). У своїй простій формі він спирається на арифметику.

Щоб створити відкритий ключ, людина має спочатку створити закритий ключ, вибравши велике секретне число. Потім вираховується кілька кратних цього числа, до яких додаються випадкові помилки, на основі чого формується відкритий ключ. Одержувач вираховує секретний ключ та отримує відправлене повідомлення.

Одед Регев, дослідник комп’ютерних наук із Нью-Йоркського університету та творець алгоритму, називає це «шкільним рівнем математики». Завдяки цьому подібний спосіб захисту легший, ніж алгоритми на основі математики решіток, оскільки він не має відношення до векторів, але при цьому залишається настільки ж захищеним.

Проблемою цього підходу є великий розмір відкритого ключа, який досягає розмірів мегабайта (це неймовірно «важко» для чисел). Для порівняння, відкритий ключ сучасної програми має розмір одного твіту. Удосконалені системи «структурованої решітки» допомагають зменшити розмір відкритого ключа, проте роблять їх більш уразливими перед атаками. Теоретично, найкращий алгоритм допоможе знайти баланс між розмірами ключа та ефективністю проти квантових атак — саме цей критерій є найважливішим у «конкурсі» від NIST, поряд з вимогою, щоб усі алгоритми, які «переможуть», були безкоштовними.

Вже цього року NIST обере два «алгоритми-фіналісти»: для одного з них інститут почне розробляти стандарти, поки другий буде резервним, якщо перший варіант виявиться недостатньо підходящим.

Однак це далеко не останній крок — навіть коли алгоритм буде визнаний і стандартизований, усій інтернет-спільноті доведеться домовитися про те, як інтегрувати його до наявних протоколів. Наприклад, сучасні браузери не адаптовані до використання більшості постквантових алгоритмів, тому багатьом розробникам доведеться істотно оновити свої продукти.

Тим не менш, браузери — далеко не головна проблема, адже адаптувати доведеться безліч «розумних» пристроїв — починаючи від автомобілів і закінчуючи холодильниками. Багато хто з них працює на алгоритмах безпеки, які вбудовані в заводські чипи, через що змінити їх буде неможливо.

Проблема з браузерами не є настільки серйозною, на відміну від роботи з безліччю сучасних підключених пристроїв, таких як автомобілі, камери відеоспостереження та «розумні будинки». Багато хто з них має функції безпеки, вбудовані в заводські чипи, а значить змінити їх неможливо. Через це частина пристроїв залишиться вразливою, навіть коли нові алгоритми будуть уже всюди.

Так чи інакше постквантові технології будуть використовуватися поверх наявних систем, щоб плавно інтегрувати нові алгоритми. За задумом, коли технології дістануться квантової ери, Інтернет вже буде під замком постквантової ери.

Дослідники впевнені, що розробка квантового інтернету (як би не збивало з пантелику, саме це йде «після» постквантового інтернету в цьому випадку) стане ще більш важливою частиною захисту від квантових хакерів, оскільки ця мережа використовуватиме принципи квантової фізики, а не математики. А квантова фізика, як ми знаємо, це мало не синонім слову «хаос».