Квантовое превосходство уже тут (но это не точно)

26 сентября 2019

На днях пришли новости, что квантовый компьютер Google решил криптографическую задачу на несколько порядков быстрее, чем самый производительный суперкомпьютер в мире. Однако наделавшую столько шума публикацию вскоре отозвали.

Исчезновение с сайта NASA отчета, который обнаружила и сделала достоянием общественности Financial Times, только добавило неопределенности всей этой истории. Так, например, не до конца понятно, какую конкретно задачу якобы решил квантовый компьютер. Также неизвестно, сколько кубитов было задействовано — 53 или 72. Тем не менее, весьма вероятно, что эра квантового превосходства все-таки наступила. По крайней мере, стоит исходить из этого постулата, и я объясню почему.

Правда ли, что квантовый компьютер Google только что взломал алгоритм RSA 512?

Квантовое превосходство (вероятно) достигнуто

В прошлом году, находясь под впечатлением от числа докладов и круглых столов по квантово-устойчивой криптографии на RSA Conference 2018, мы решили примерно оценить, когда наступит квантовое превосходство. По нашим прикидкам, оно должно было подоспеть как раз к концу 2019 года.

Мы также оценили, сколько времени потребуется квантовому компьютеру и суперкомпьютеру, чтобы разложить на простые сомножители ключевое число 512-значного алгоритма шифрования RSA. Эти оценки очень близки к тому, о чем сообщала Financial Times со ссылкой на удаленную публикацию: 3 минуты 20 секунд и около 10 000 лет соответственно. Выходит, мы оказались правы?

Вполне вероятно, что да, однако с практической точки зрения это не самое главное. Для нас, профессионалов информационной безопасности, гораздо важнее другой вопрос: если традиционной криптографии приходит конец, то что с этим делать?

Обычного шифрования становится недостаточно. Что делать?

Кто-то считает Эдварда Сноудена героем, кто-то предателем, кто-то и тем, и другим, а иные ни тем, ни другим. Его противоречивая репутация напоминает мне запутанные состояния квантовых систем. Но упоминаю я его тут не просто так: в своей новой книге «Личное дело», также вышедшей на днях, Сноуден дает хороший практический совет по шифрованию, который особенно актуален в условиях возможного пришествия квантового превосходства: использовать последовательно несколько способов. И он прав. Когда нельзя быть уверенным, что используемый метод шифрования выдержит попытки взлома, лучшая стратегия — зашифровать данные несколько раз с помощью разных алгоритмов.

В ситуации, когда квантовое превосходство уже совершенно неопределенно где-то рядом, стоит позаботиться, чтобы хотя бы один из применяемых алгоритмов был квантово-устойчивым. Например, их можно выбрать из 17 финалистов, прошедших во второй раунд отбора NIST. Алгоритмы из этого списка пока вызывают большее доверие, чем эллиптические кривые, устойчивость которых уже подвергли сомнению.

Однако пока NIST не подвел окончательные итоги, для рабочих целей вполне разумно использовать доступное уже сейчас шифрование на основе эллиптических кривых поверх AES с достаточной длиной ключа или SHA3, в зависимости от того, какие задачи вы решаете. Не стоит забывать и о своего рода криптографическом «техобслуживании» — перешифровке особо ценных данных, поскольку даже самым продвинутым алгоритмам свойственно устаревать со временем.