Современные шифры (RSA, ECC) держатся на том, что разложить большое число на простые множители или решить задачу дискретного логарифмирования для обычных компьютеров слишком трудно. Но квантовый алгоритм Шора способен делать это моментально. Как только появятся достаточно мощные квантовые машины, все, что мы сегодня защищаем, станет открытым текстом. Уже сегодня специалисты по кибербезопасности ищут способы защиты от потенциального краха.

Система Classic McEliece, разработанная в 1978 году Робертом Макэлисом, была в то время первой, основана на сложности декодированых полных линейных кодов. За долгие годы он выдержал многочисленные проверки, хотя и не получил широкого распространения в классической криптографии.

Вместо того чтобы использовать операции с большими простыми числами, система Макэлиса использует корректирующие коды — те же самые, которые исправляют ошибки при передаче данных по сотовой связи или в глубоком космосе. Зашифрованное сообщение представляет собой искаженный кодовый вектор, и только обладатель специальной секретной матрицы может восстановить исходный текст. Все остальные видят лишь хаотичный набор битов, который невозможно прочитать без знания ключа. Криптоанализ этой системы требует решения задачи декодирования общего линейного кода, которая считается NP-полной и устойчивой к квантовым вычислениям.

Однако алгоритм Макэлиса требовал огромных ключей и долгое время считался непрактичным.

Благодаря оптимизациям и росту вычислительных мощностей, в 2020-х годах ситуация изменилась, пишет Quantum Zeitgeist. Немецкое Федеральное ведомство по информационной безопасности уже одобрило его для защиты сверхсекретных данных, а Национальный институт стандартов и технологий США (NIST) рассматривает такую возможность. И вот теперь ISO официально включила Classic McEliece в свой стандарт. Это означает, что систему вскоре внедрят банки и государственные инфраструктуру. А шведский VPN-провайдер Mullvad уже интегрировал Classic McEliece в свои сервисы.

Не все, впрочем, согласны с тем, что квантовые компьютеры представляют реальную угрозу современным видам шифрования. Профессор Оксфордского университета Тим Палмер выступил с теорией, согласно которой фундаментальные физические ограничения связанные с гравитацией, а не только инженерные проблемы, не позволят квантовым компьютерам превысить порог в 1000 полезных кубитов. Этого количества недостаточно для взлома 2048-битного RSA-шифрования с помощью алгоритма Шора.