Квантовый компьютер может взломать схемы шифрования с открытым ключом, которые теперь поддерживают интернет-безопасность.
Полноценному квантовому компьютеру еще долгие годы, если не десятилетия. Но разработчики уже давно думают, что его убийственное приложение будет декодировать зашифрованные сообщения в Интернете и в других местах, будь то государственная тайна или личная информация. Эта перспектива оцинковала криптографов. На встрече на этой неделе в Санта-Барбаре, штат Калифорния, они обсудят почти две дюжины схем шифрования сообщений таким образом, что даже квантовые компьютеры не смогут взломать.
Семинар является частью усилий Национального института стандартов и технологий (NIST) по установлению стандартов для так называемой постквантовой криптографии. Многолетнее усилие может показаться преждевременным и немного параноидальным, поскольку такого квантового компьютера может никогда не существовать. Но криптографы говорят, что сейчас самое время подготовиться, особенно потому, что теперь любой может записать конфиденциальные сообщения и расшифровать их позже. «Если вы подождете, пока у нас будет квантовый компьютер, будет слишком поздно», - говорит Таня Ланге, криптограф из Эйндховенского технологического университета в Нидерландах. «Каждый день, когда у нас нет постквантовой криптографии, - это день утечки данных».
Электронная коммерция на сотни миллиардов долларов опирается на потенциально уязвимые схемы, называемые криптографией с открытым ключом. Они основаны на вычислениях «ловушек», так называемых, потому что их гораздо легче работать вперед, чем назад. Получатель Алиса предоставляет числовой открытый ключ и рецепт, который отправитель Боб использует для шифрования сообщения. Подслушивающая, Ева, не может легко отменить вычисления Боба, чтобы обнаружить сообщение. Однако Алиса также сгенерировала секретный закрытый ключ, математически связанный с открытым, который помогает ей расшифровать сообщение с помощью вычислений, подобных Бобу.
Например, в популярной схеме открытого ключа, называемой RSA, Боб шифрует числовое сообщение, умножая его на число раз, указанное Алисой. Он делит результат на открытый ключ, гигантское число, полученное умножением двух простых чисел, и отправляет Алисе остаток. Чтобы восстановить сообщение, Алиса умножает остаток на себя другое число раз - это число является ее личным ключом - и делится на открытый ключ. Вуаля! Оригинальное сообщение Боба выскакивает в остатке. Как будто Алиса говорит Бобу, как скрыть настройку замка, поворачивая диск вперед на много оборотов, зная, как повернуть диск дальше, чтобы восстановить исходную настройку. Ева может только изо всех сил пытаться понять, как далеко повернуть циферблат.
RSA также иллюстрирует угрозу, создаваемую квантовым компьютером. Если бы Ева могла включить открытый ключ в простые составляющие, она могла бы украсть закрытый ключ и взломать код. Фактор больших чисел сложен для классического компьютера, но для квантового компьютера будет проще, как показал математик Питер Шор из Массачусетского технологического института в Кембридже в 1994 году. Квантовый компьютер, работающий по алгоритму Шора, может также победить новый открытый ключ схемы, потому что он превосходен при поиске шаблонов в повторяющихся операциях «разделяй и забирай остаток».
Чтобы противостоять риску, криптографы разрабатывают менее уязвимые алгоритмы ловушек. Многие полагаются на геометрические конструкции, называемые решетками, массивами точек, которые напоминают повторяющиеся трехмерные структуры атомов в кристалле, за исключением того, что они имеют сотни или тысячи измерений. Решетка определяется набором стрелок или векторов, которые могут быть добавлены в различных комбинациях для создания шаблона. Для той же самой решетки основа может состоять из коротких, почти перпендикулярных векторов, с которыми легко работать, или длинных, почти параллельных, с которыми труднее работать.
В этих схемах закрытый ключ Алисы является простой решетчатой основой, а ее открытый ключ - беспорядочным, определяющим тот же шаблон. Чтобы передать каждый бит информации Алисе, Боб может отправить ей координаты точки в многомерном пространстве, которая либо близка к точке в решетке, чтобы обозначить ноль, либо дальше от точки решетки, чтобы обозначить единицу. С грязным открытым ключом даже квантовый компьютер не мог помочь Еве сказать, насколько близко точка находится к решетке. Алиса, однако, может легко сделать это, потому что она держит простой, закрытый ключ. «Решетчатая криптография - очень активная область, потому что она настолько универсальна, - говорит Нина Биндель, специалист по информатике в Техническом университете Дармштадта в Германии.
Некоторые исследователи отряхивают гораздо более старые алгоритмы. Предположим, вы хотите передать цепочку битов через Интернет, но опасаетесь, что несколько нулей и единиц могут случайно перевернуться. Вы можете избежать этого, создав длинную строку с избыточностями, которые можно использовать для исправления ошибок. Такой код с исправлением ошибок может быть представлен сеткой или матрицей нулей и единиц, и в 1970-х годах криптографы показали, что они могут шифровать сообщения.
В схеме такого типа закрытый ключ Алисы является матрицей, исправляющей ошибки, а ее открытый ключ является ее зашифрованной версией. Сообщение Боба - это строка битов, к которой он применяет открытую матрицу, чтобы получить другую строку. Он подбрасывает несколько случайных битов и отправляет результат Алисе. Даже зная грязную матрицу Боба, Ева не может отменить его ходы. Но с более чистым, разработанным для исправления этих перевернутых битов, Алиса может. Ланге говорит, что схемы с исправлением ошибок были проверены больше, чем решетки, и могут столкнуться с Евой лицом вниз, даже если у нее есть квантовый компьютер.
Большинство постквантовых алгоритмов требуют больших ключей или большего вычислительного времени, чем современные стандарты. Но Симона Самарджиска, криптограф из университета Radboud в Неймегене, Нидерланды, и ее коллеги разрабатывают гибкую схему с небольшими ключами, основанную на наборах квадратных уравнений, которая могла бы лучше подходить для цифровых подписей - быстрых рукопожатий, которые аутентифицируют веб-сайты - чем для отправки секретных сообщений.
Как и в случае любой системы с открытым ключом, нет никаких доказательств того, что схемы postquantum не взломаны, возможно, даже с обычным компьютером. Поэтому вместо замены существующих алгоритмов новые, скорее всего, будут работать вместе с ними, говорит Брайан Ламаккиа, криптограф из Microsoft в Редмонде, штат Вашингтон.
NIST может стандартизировать два или три алгоритма для шифрования и цифровых подписей каждый к 2022 году, говорит Дастин Муди, математик из NIST в Гейтерсберге, штат Мэриленд. Агентство хочет вариантов, говорит он. «Если будет обнаружена какая-то новая атака, которая сломает все решетки, у нас все равно будет к чему вернуться». NIST устанавливает стандарты для федерального правительства, говорит Муди, но «большая часть мира использует шифрование, которое стандартизирует NIST». Cloudflare Интернет-компания по безопасности и производительности в Сан-Франциско, штат Калифорния, которая обслуживает 20 миллионов предприятий и других клиентов, уже начала экспериментировать с некоторыми алгоритмами в веб-браузерах. Но полная миграция займет годы, предупреждает Ник Салливан, криптограф из Cloudflare.
LaMacchia говорит, что за последние 30 лет он видел четыре или пять основных изменений в криптографии, включая десятилетие назад, чтобы перейти от RSA к математически связанному, но более безопасному преемнику. «Этот качественно другой. Это намного сложнее ». Пользователи шифрования, то есть почти все, будут знать, что изменения прошли хорошо, если они никогда не заметят этого.
