Как квантовый компьютер может сломать 2048-битное шифрование RSA за 8 часов
Новое исследование показывает, что квантовая технология догонит современные стандарты шифрования намного раньше, чем ожидалось. Это должно волновать любого, кому необходимо безопасно хранить данные в течение 25 лет или около того.
Многие люди беспокоятся, что квантовые компьютеры смогут взломать определенные коды, используемые для отправки защищенных сообщений. Рассматриваемые коды шифруют данные, используя математические функции «люка», которые легко работают в одном направлении, но не в другом. Это делает шифрование данных простым, но расшифровывает его без особого ключа.
Эти системы шифрования никогда не были взломаны. Вместо этого их безопасность основана на огромном количестве времени, которое потребуется классическому компьютеру для выполнения этой работы. Современные методы шифрования специально разработаны таким образом, чтобы их декодирование занимало так много времени, что они практически не ломаются.
Но квантовые компьютеры меняют это мышление. Эти машины гораздо более мощные, чем классические компьютеры, и должны легко взламывать эти коды.
Возникает важный вопрос: когда квантовые компьютеры станут достаточно мощными, чтобы сделать это? После этой даты любая информация, защищенная этой формой шифрования, становится небезопасной.
Поэтому ученые-компьютерщики попытались рассчитать ресурсы, которые могут понадобиться квантовому компьютеру, а затем выяснить, сколько времени понадобится, пока такая машина не будет построена. И ответом всегда были десятилетия.
Сегодня это мышление необходимо пересмотреть благодаря работе Крэйга Гидни в Google в Санта-Барбаре и Мартина Экера в Королевском технологическом институте KTH в Стокгольме, Швеция. Эти ребята нашли более эффективный способ для квантовых компьютеров выполнять вычисления с нарушением кода, сокращая ресурсы, которые им требуются на порядок.
Следовательно, эти машины значительно ближе к реальности, чем кто-либо подозревал. Результатом будет неудобное чтение для правительств, военных и охранных организаций, банков и всех, кому необходимо защищать данные в течение 25 лет или дольше.
Сначала немного предыстории. Еще в 1994 году американский математик Питер Шор открыл квантовый алгоритм, который превзошел его классический эквивалент. Алгоритм Шора учитывает большие числа и является ключевым элементом в процессе взлома кодов, основанных на лазейке.
Функции люка основаны на процессе умножения, которое легко выполнить в одном направлении, но намного сложнее сделать в обратном. Например, тривиально умножить два числа вместе: 593 умножить на 829 - это 491 597. Но трудно начать с числа 491 597 и определить, какие два простых числа нужно умножить, чтобы получить его.
И это становится все труднее, поскольку цифры становятся больше. Действительно, компьютерные ученые считают, что для классического компьютера практически невозможно вычислить числа, длина которых превышает 2048 бит, что является основой наиболее часто используемой формы шифрования RSA.
Шор показал, что достаточно мощный квантовый компьютер может с легкостью сделать это, и это вызвало шок в индустрии безопасности.
И с тех пор у квантовых компьютеров растет мощность. В 2012 году физики использовали квантовый компьютер с четырьмя кубитами для вычисления коэффициента 143. Затем в 2014 году они использовали аналогичное устройство с коэффициентом 56,153.
Легко представить, что при таких темпах прогресса квантовые компьютеры скоро смогут превзойти лучшие классические компьютеры.
Не так. Оказывается, на практике квантовый факторинг гораздо сложнее, чем можно было бы ожидать. Причина в том, что шум становится серьезной проблемой для больших квантовых компьютеров. И лучший способ в настоящее время бороться с шумом - это использовать коды с исправлением ошибок, которые сами требуют значительных дополнительных кубитов.
Принимая это во внимание, резко увеличивается количество ресурсов, необходимых для учета 2048-битных чисел. В 2015 году, по оценкам исследователей, квантовому компьютеру потребовался бы миллиард кубитов для надежного выполнения работы. Это значительно больше, чем 70 кубитов в современных квантовых компьютерах .
Исходя из этого, эксперты по безопасности вполне могли бы обосновать идею о том, что пройдет много десятилетий, прежде чем сообщения с 2048-битным шифрованием RSA могут быть повреждены квантовым компьютером.
Теперь Гидни и Экеро показали, как квантовый компьютер может выполнять вычисления всего с 20 миллионами кубитов. Действительно, они показывают, что такое устройство займет всего восемь часов, чтобы завершить расчет. «[В результате] наихудшая оценка того, сколько кубитов потребуется для вычисления 2048-битных целых чисел RSA, упала почти на два порядка», - говорят они.
Их метод ориентирован на более эффективный способ выполнения математического процесса, называемого модульным возведением в степень. Это процесс поиска остатка, когда число увеличивается до определенной степени, а затем делится на другое число.
Этот процесс является самой дорогой вычислительной операцией в алгоритме Шора. Но Гидни и Экера нашли различные способы его оптимизации, значительно сократив ресурсы, необходимые для запуска алгоритма.
Это интересная работа, которая должна иметь важные последствия для любого, кто хранит информацию для будущего. Сегодня квантовый компьютер с 20-миллионным кубитом, безусловно, кажется далекой мечтой. Но вопрос, который эти эксперты должны задать себе, заключается в том, возможно ли такое устройство в течение 25 лет, которые они хотят защитить информацию. Если они думают, что это так, то им нужна новая форма шифрования.
Действительно, эксперты по безопасности разработали постквантовые коды, которые даже квантовый компьютер не сможет взломать . Таким образом, уже сегодня можно защитить данные от будущей атаки со стороны квантовых компьютеров. Но эти коды еще не используются в качестве стандарта.
Для обычных людей существует небольшой риск. Большинство людей используют 2048-битное шифрование или что-то подобное для таких задач, как отправка данных кредитной карты через Интернет. Если эти транзакции будут зарегистрированы сегодня и сорваны через 25 лет, мало что будет потеряно.
Но для правительств на карту поставлено больше. Сообщения, которые они посылают сегодня - например, между посольствами или военными - могут быть значительными через 20 лет, и поэтому их стоит хранить в секрете. Если такие сообщения по-прежнему отправляются с использованием 2048-битного шифрования RSA или чего-то подобного, то этим организациям следует начать беспокоиться - быстро.
Ссылка: arxiv.org/abs/1905.09749 : Как рассчитать 2048-битные целочисленные значения RSA за 8 часов с использованием 20 миллионов шумовых кубитов