Google начал эксперимент по использованию постквантовой криптографии в браузерах Chrome. Согласно заявлению компании, часть информации, обмениваемой браузером и серверами Google, будет шифроваться новыми алгоритмами, которые устойчивы по отношению ко взлому квантовыми компьютерами. Эксперимент запущен на браузерах Chrome Canary — версии Chrome для разработчиков. Анонс опубликован в блоге Google.
Как объясняет блог, потребность в постквантовой криптографии возникла из-за возможности создания квантовых компьютеров в обозримом будущем. Благодаря фундаментальным отличиям между квантовыми и классическими вычислителями современные протоколы шифрования могут оказаться неустойчивыми к дешифровке квантовыми компьютерами. Это означает, что в теории злоумышленники могут сегодня записать зашифрованную информацию в хранилище и получить из нее ценные сведения с появлением квантовых компьютеров.
В основе современных протоколов шифрования с открытым ключом (например, в TLS, основе HTTPS) лежат вычислительно сложные математические задачи, такие как разложение больших чисел на простые множители или вычисление дискретных логарифмов. Современные классические алгоритмы и устройства, к примеру, могут в лучшем случае разложить за разумное время на множители число, являющееся произведением двух 384-битных (около 80 цифр) простых чисел. Ключи в шифровании RSA состоят из, по меньшей мере, 1024 бит.
Сложность разложения числа на простые множители быстро растет с длиной самого числа. В большинстве классических алгоритмов время, затрачиваемое на разложение, растет по экспоненте. Однако для квантовых компьютеров существует алгоритм Шора, требующий лишь полиномиального времени на решение этой задачи. Это означает, что даже увеличение длины ключей не даст серьезного прироста в стойкости шифрования.
Новый алгоритм обмена ключами шифрования, используемый Google, получил название New Hope («Новая надежда»). Подробное его описание можно прочитать здесь. Этот алгоритм основан на обучении с ошибкам и устойчив по отношению к квантовым алгоритмам. Компания отмечает, что в случае, если New Hope окажется взламываем классическими алгоритмами, безопасность пользователей не пострадает: новый алгоритм будет применяться «поверх» традиционных протоколов.
Обучение с ошибками — алгоритм, в котором открытый ключ является системой линейных уравнений, в которых могут быть небольшие ошибки. Например, равенство 3x+5y = 5 может быть верным с точностью ±1. New Hope — его усовершенствованная версия. В его основе лежат длинные многочлены, коэффициенты в которых выбираются из ограниченного набора (конечного поля).
Эксперимент продлится два года, после чего будет остановлен. Google не рассматривает New Hope в качестве будущего стандарта шифрования — эта область активно развивается и, возможно, в будущем появятся более быстрые и эффективные протоколы. Основная задача сейчас, как отмечает блог компании, протестировать системы, необходимые для реального применения новых методов шифрования.
Квантовые компьютеры — вычислительные устройства, работающие на квантовых битах или кубитах. В отличие от классических бит, хранящих в себе либо «0», либо «1», кубит находится в суперпозиции этих состояний, принимая то или иное значение с некоторой вероятностью. Подробнее о них можно прочитать в нашем материале.
Сейчас такие компьютеры работают на небольшом количестве кубитов. К примеру, физики из Мэрилендского университета недавно продемонстрировали полноценное пятикубитное устройство. Разработками квантовых вычислителей занимаются и в IBM, а также Google, Microsoft и Intel. Важным применением квантовых компьютеров является моделирование различных физических явлений. К примеру, недавно с помощью такого устройства физики изучали рождение электрон-позитронных пар из-за флуктуаций вакуума. Для классических компьютеров подобные задачи очень сложны.
Владимир Королёв