Квантовые компьютеры стимулируют развитие новых алгоритмов цифрового шифрования
На протяжении большей части последнего десятилетия эксперты по кибербезопасности предупреждали о надвигающейся угрозе: появлении квантовых компьютеров.
Это машины, которые используют принципы квантовой физики для обработки информации, однажды станут достаточно мощными, чтобы взломать наиболее широко используемые системы шифрования, сделав почти все цифровые коммуникации уязвимыми.
Всегда стоял вопрос, когда именно наступит этот день. Самый распространенный метод цифрового шифрования, RSA, который был изобретен в 1977 году, основан на умножении двух больших простых чисел. Один из способов взломать его - выяснить, что это были за два больших простых числа. В 1994 году математик Питер Шор изобрел алгоритм, который при запуске на достаточно мощном квантовом компьютере легко находил эти два простых числа. Но в то время квантовые компьютеры были чисто теоретическими машинами.
Первые работающие квантовые компьютеры были построены более десяти лет назад. Но большинство из них либо не были спроектированы таким образом, чтобы позволить им запускать алгоритм Шора. Другие просто были недостаточно мощными, чтобы справиться с очень большим простым кратным числом. Момент, когда экспертам по кибербезопасности придется беспокоиться о хакерах, оснащенных квантовыми компьютерами, казался далеким - по некоторым оценкам, по крайней мере, четверть века назад никто не рассматривал это как серьезную угрозу.
Но не более. В прошлом году Google заявила, что достиг порога, известного как "квантовое превосходство", создав квантовый компьютер, способный выполнять вычисления, которые невозможно было бы сделать на обычном компьютере за разумный промежуток времени.
Машина Google все еще не может взломать RSA. Но быстрый прогресс в создании квантового оборудования наряду с некоторыми умными достижениями в алгоритмах означает, что сроки для алгоритма Шора, выводящего RSA из сферы применения, были значительно сдвинуты. Если повезет, у нас может остаться более десяти лет защиты конфиденциальности данных, говорят эксперты. Но некоторые думают, что у нас есть в лучшем случае пять лет, а может быть, и меньше.
В 2016 году Агентство национальной безопасности США выступило с резким предупреждением о том, что правительственные агентства и компании "должны действовать сейчас", чтобы начать переход на новый стандарт шифрования, который защищен от атак с использованием квантовых компьютеров. Единственная проблема - никто не был уверен, каким должен быть этот стандарт шифрования.
Вот почему Национальный институт стандартов и технологий (NIST), агентство при Министерстве торговли США, которое отвечает за рекомендации стандартов, часто утверждаемые как правительством, так и бизнесом, почти три года назад объявило конкурс на выбор новых методов шифрования, которые будут устойчивы к атакам со стороны квантовых компьютеров.
Эти новые методы "постквантового" шифрования и цифровой подписи, вероятно, станут обязательными для всех правительственных ведомств США и для многих компаний, которые ведут дела с правительством, особенно в сфере обороны и разведки. Из-за размера рынка США они также могут стать новым мировым стандартом безопасности. В настоящее время NIST находится на пороге выбора лучших алгоритмов шифрования и открывает новую эру в сфере кибербезопасности.
В июле агентство стандартизации объявило, что отсеяло первоначальную группу из 82 кандидатов до длинного списка из 15, включая четырех основных финалистов по шифрованию и трех по цифровой подписи, которые используют криптографию для проверки подлинности электронных сообщений и документов. NIST заявил, что объявит о своем окончательном одобрении нового стандарта шифрования в течение следующих 18 месяцев.
Итак, что длинный список NIST говорит нам о будущем кибербезопасности? Что ж, есть большая вероятность, что это будет связано с так называемой криптографией на основе решеток. Трое из четырех финалистов по шифрованию принадлежат к этому семейству алгоритмов.
Криптография на основе решеток основана на уникальных математических свойствах сеток из равномерно расположенных точек или решеток. Поскольку точки расположены равномерно, оказывается, что всего по двум координатам сетки можно вычислить все точки внутри одной и той же решетки. Но выяснить, находится ли какая-либо данная точка в решетке, может быть трудно, если решетка имеет многие тысячи измерений и если углы между точками в решетке далеки от перпендикулярных. Было создано несколько схем шифрования, которые используют эти свойства для создания открытого и закрытого ключей, которые работают вместе - потому что они вычисляются из одной и той же решетки, - но в которых чрезвычайно сложно получить закрытый ключ из открытого ключа отдельно друг от друга.
Однако, некоторые эксперты по кибербезопасности удивлены, что NIST так сильно склонна к внедрению подобного вида постквантового шифрования. Это связано с тем, что, хотя задачи на основе решеток математически сложны и, в отличие от RSA, не подвержены воздействию алгоритма Шора, математически не доказано, что они невосприимчивы к атакам на основе квантового компьютера. "Мы говорим, что квантовые алгоритмы не могут сломать их пока", - говорит Делари Каробай, профессор кибербезопасности в Университете Йорка, из Англии. "Но завтра кто-то предложит другой квантовый алгоритм, который может их взломать".
Каробай говорит, что разочарована тем, что кандидаты из других семейств потенциальных постквантовых алгоритмов не попали в окончательный список. Это включает многомерную криптографию, которая основана на сложности решения полиномиальных уравнений и групповую криптографию, над которой работает сама Каробай. Алгоритм основан на еще одной области математики, включающей преобразование набора чисел путем комбинирования элементов, часто в соответствии со сложными геометрическими узорами, такими как косы.
Единственный кандидат на постквантовое шифрование без решетки среди финалистов NIST - из семейства криптографических, известен как алгоритмы на основе кода. Все они включают в себя добавление какой-то ошибки к данным - например, классический код, в котором вы сдвигаете алфавит на две буквы, так что A кодируется как C, а B как D, и так далее. Затем эту ошибку исправляют, чтобы расшифровать сообщение. Постквантовый алгоритм, выбранный NIST, называется Классическим Мак-Элисом, в честь алгоритма кода с исправлением ошибок, изобретенного математиком Робертом Мак-Элисом в конце 1970-х. Он применяет разные случайные ошибки к каждой кодируемой информации, что теоретически делает невозможным взлом, не зная ключа.
"Система МакЭлиса существует уже 41 год и все это время подвергалась атакам со стороны криптосообщества, не обнаружив уязвимости", - сказал Андерсен Ченг, соучредитель и главный исполнительный директор Post-Quantum Group, лондонской компании, занимающейся кибербезопасностью, который объединил усилия с другой командой, возглавляемой Дэниелом Бернстайном, известным криптографом из Университета Иллинойса в Чикаго, для работы над классическим заявлением Мак-Элиса, которое вошло в длинный список финалистов NIST.
В 2019 году Федеральное управление по информационной безопасности Германии (BSI), обеспокоенное тем, что процесс NIST затягивается, рекомендовало Classic McEliece в качестве одного из двух рекомендованных стандартов постквантового шифрования. Ченг подозревает, что NIST, как и правительство Германии, в конечном итоге поддержит два стандарта - классический метод Мак-Элиса и один из решеточных методов.
Единственный недостаток алгоритма Мак-Элиса, по словам Ченг, заключается в том, что относительно длинные ключи, которые использует метод, и вычислительная сложность алгоритма означают, что компьютеру требуется больше времени для шифрования и дешифрования информации, чем у его конкурентов на основе решеток. "Он медленнее на несколько миллисекунд, - говорит Ченг. Но для обмена общедоступными ключами шифрования - для чего в основном и будет использоваться алгоритм - этот метод все же на самом деле быстрее, чем RSA."
Хотя есть исследователи из известных технологических компаний, таких как IBM, Intel, а также производителя микросхем ARM, участвующего в гонке за поиском алгоритмов квантово-безопасного шифрования, примечательно то, что в конкурсе NIST претендует относительно мало известных фирм, занимающихся кибербезопасностью.
Каробай говорит, что она ожидает появления множества новых компаний, которые помогут коммерциализировать постквантовое шифрование, так же как RSA Security - компания, основанная в 1982 году для коммерциализации алгоритма RSA - стала доминирующим игроком в сфере кибербезопасности в течение последних тридцати лет.
Intel Германия Правительство Университеты
