Національний інститут стандартів та технологій США (NIST) оголосив переможців конкурсу криптоалгоритмів, стійких до підбору на квантовому комп'ютері. Конкурс був організований шість років тому і націлений на вибір алгоритмів постквантової криптографії, придатних для висування як стандарти. У процесі проведення конкурсу запропоновані міжнародними командами дослідників алгоритми були вивчені незалежними експертами щодо можливих уразливостей та слабких місць.
Переможцем серед універсальних алгоритмів, які можна використовувати для захисту передачі інформації в комп'ютерних мережах, вибрано CRYSTALS-Kyber, сильними сторонами якого є невеликий розмір ключів і висока швидкість роботи. CRYSTALS-Kyber рекомендований для перекладу стандартів. Крім CRYSTALS-Kyber виділено ще чотири алгоритми загального призначення — BIKE, Classic McEliece, HQC та SIKE, які потребують доопрацювання. Авторам даних алгоритмів надано можливість до 1 жовтня оновити специфікації та усунути недоліки в реалізаціях, після чого вони також можуть бути включені до фіналістів.
З алгоритмів, націлених працювати з цифровими підписами, виділено CRYSTALS-Dilithium, FALCON і SPHINCS+. Алгоритми CRYSTALS-Dilithium та FALCON відрізняються високою ефективністю. Як первинний алгоритм для цифрових підписів рекомендований CRYSTALS-Dilithium, а FALCON орієнтований на рішення, які потребують мінімальний розмір підпису. SPHINCS+ відстає від перших двох алгоритмів за розміром підписів та швидкості роботи, але він залишений серед фіналістів як запасний варіант, оскільки базується на принципово інших математичних принципах.
Зокрема, в алгоритмах CRYSTALS-Kyber, CRYSTALS-Dilithium і FALCON використовуються методи криптографії, засновані на вирішенні завдань теорії ґрат, час вирішення яких не відрізняється на звичайних та квантових комп'ютерах. Алгоритм SPHINCS+ застосовує методи криптографії на основі хеш-функцій.
Залишені для доопрацювання універсальні алгоритми також ґрунтуються на інших принципах — у BIKE та HQC використовуються елементи теорії кодування алгебри та лінійні коди, які також застосовуються в схемах корекції помилок. NIST має намір додатково стандартизувати один із цих алгоритмів для залишення альтернативи вже обраному алгоритму CRYSTALS-Kyber, заснованому на теорії ґрат. Алгоритм SIKE базується на використанні суперсингулярної ізогенії (кружіння в суперсингулярному ізогенному графі) і також розглядається як кандидат на стандартизацію, оскільки відрізняється найменшим розміром ключа. Алгоритм Classic McEliece включений до фіналістів, але поки не буде стандартизований через дуже великий розмір відкритого ключа.
Необхідність розробки та стандартизації нових криптоалгоритмів обумовлена тим, що квантові комп'ютери, що активно розвиваються останнім часом, кардинально швидше вирішують завдання розкладання натурального числа на прості множники (RSA, DSA) і дискретного логарифмування точок еліптичної кривої (ECDSA), які лежать в основі сучасних. відкритим ключам та ефективно не вирішуються на класичних процесорах. На поточному етапі розвитку можливостей квантових комп'ютерів поки що недостатньо для злому актуальних класичних алгоритмів шифрування та цифрових підписів на базі відкритих ключів, таких як ECDSA, але передбачається, що ситуація може змінитися протягом 10 років і необхідно підготувати базу перекладу криптосистем на нові стандарти.
Джерело: opennet.ru