Какой будет постквантовая криптография?

Автор оригинала: Martin Giles
  • Перевод

Идёт гонка за создание новых способов защиты данных и коммуникаций от угроз, исходящих от сверхмощных квантовых компьютеров




Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах каждый раз, когда мы заходим на сайт интернет-магазина, отправляем и получаем емейлы, проверяем наш банковский счёт или кредитную карту. Однако он сигнализирует о том, что онлайн-сервисы используют HTTPS, веб-протокол, шифрующий данные, которые мы отправляем по интернету, и те ответы, что мы получаем. Эта и другие формы шифрования защищают различные электронные коммуникации, а также такие вещи, как пароли, цифровые подписи и истории болезней.

Квантовые компьютеры могут подорвать эту криптографическую защиту. Сегодня эти машины пока недостаточно мощны, но они быстро эволюционируют. Возможно, что не позднее, чем через десять лет – а возможно, и раньше – эти машины смогут стать угрозой для широко используемых методов криптографии. Именно поэтому исследователи и компании, занимающиеся безопасностью, наперегонки разрабатывают новые подходы к криптографии, которые смогут выдержать будущие квантовые атаки хакеров.

Как работает цифровое шифрование?




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

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

Цель – не дать хакерам при помощи значительных вычислительных мощностей попытаться угадать используемые ключи. Для этого популярные криптографические методы, включая RSA и шифрование с помощью эллиптических кривых, обычно используют т.н. односторонние функции с потайным входом – математические конструкции, которые относительно легко вычислять в одну сторону для получения ключей, но очень сложно для злоумышленника подвергнуть обратному инжинирингу.

Хакеры могут попытаться взломать код, подбирая все возможные варианты ключа. Но защищающиеся стороны очень усложняют им эту задачу, используя пары очень длинных ключей – как в 2048-битной RSA, использующей ключи длиной в 617 десятичных чисел. Перебор всех возможных вариантов приватных ключей займёт тысячи – если не миллионы – лет у обычных компьютеров.

Почему квантовые компьютеры несут угрозу шифрованию?




Поскольку они могут помочь хакерам гораздо быстрее пробираться через алгоритмические потайные ходы. В отличие от классических компьютеров, использующих биты, способные принимать лишь значения 1 или 0, квантовые машины используют кубиты, способные одновременно представлять различные возможные состояния, промежуточные между 0 и 1 – это явление называется суперпозицией. Они также могут влиять друг на друга на расстоянии благодаря такому явлению, как запутанность.

Благодаря этому явлению добавление нескольких дополнительных кубитов может привести к экспоненциальным скачкам вычислительной мощности. Квантовая машина с 300 кубитами способна представлять больше значений, чем количество атомов в наблюдаемой Вселенной. Предполагая, что квантовые компьютеры смогут преодолеть некоторые присущие им ограничения, касающиеся быстродействия, когда-нибудь их можно будет использовать для проверки всех возможных вариантов криптографического ключа за относительно недолгое время.

Хакеры также, скорее всего, попытаются использовать во вред алгоритмы оптимизации определенных задач. Один из таких алгоритмов, опубликованный Ловом Гровером из AT&T Bell Labs, помогает квантовым компьютерам гораздо быстрее искать варианты. Другой алгоритм, опубликованный в 1994 году Питером Шором, тогда также работавшим в Bell Labs, а теперь профессором в MIT, помогает квантовым компьютерам невероятно быстро находить простые множители целых чисел.

Алгоритм Шора угрожает таким системам с публичным ключом, как RSA, чья математическая защита в частности зависит от того, насколько сложно провести обратный инжиниринг результата перемножения очень больших простых чисел (разложение на множители). В отчёте по квантовым вычислениям, опубликованном в прошлом году национальной академией наук, инженерного дела и медицины США, предсказывается, что мощный квантовый компьютер, на котором работает алгоритм Шора, сможет взламывать 1024-битные варианты RSA менее, чем за день.

Смогут ли квантовые компьютеры взламывать криптографическую защиту в ближайшее время?




Маловероятно. Исследование национальных академий утверждает, что для того, чтобы представлять реальную угрозу, квантовым компьютерам понадобится гораздо больше вычислительной мощности, чем имеется у наилучших из них на сегодня.

Однако, год, в котором квантовый взлом кодов станет серьёзной головной болью – который некоторые исследователи безопасности окрестили Y2Q – может подобраться неожиданно быстро. В 2015 году исследователи заключили, что для достаточно быстрого взлома 2048-битного RSA шифрования квантовому компьютеру понадобится миллиард кубитов. В более современной работе указывается, что компьютер с 20 млн кубитов сможет справиться с этой задачей всего за 8 часов.

Это находится далеко за пределами возможностей самых мощных из сегодняшних компьютеров, обладающих всего 128 кубитами. Но прогресс квантовых вычислений непредсказуем. Без криптографической защиты, учитывающей квантовые вычисления, всякие сервисы – от робомобилей до военного оборудования, финансовых транзакций и коммуникаций – подвержены угрозе атаки со стороны хакеров, получивших доступ к квантовым компьютерам.

Любое предприятие или правительство, рассчитывающее хранить данные несколько десятилетий, должно уже сейчас задуматься над тем, какие риски несёт в себе новая технология, поскольку используемое ими сегодня шифрование может быть взломано в будущем. На перекодирование огромных объёмов исторических данных в более надёжный вид могут уйти года, поэтому лучше будет применять надёжное кодирование сегодня. Отсюда проистекает запрос на постквантовую криптографию.

Какой будет постквантовая криптография?




Это разработка новых видов криптографических методов, которые можно применять с использованием сегодняшних классических компьютеров, но которые при этом будут неуязвимы перед завтрашними квантовыми.

Одна из линий обороны – увеличение размеров цифровых ключей для значительного увеличения количества вариантов, в которых нужно будет вести поиск перебором. К примеру, простое удвоение размера ключа с 128 до 256 бит учетверяет количество возможных вариантов, которые придётся перебрать квантовой машине, использующей алгоритм Гровера.

Ещё один подход включает использование более сложных функций с потайным входом, таких, чтобы с ними тяжело было справиться даже мощному квантовому компьютеру, исполняющему алгоритм Шора. Исследователи работают над широким спектром подходов, включая такие экзотические, как криптография на решётках и протокол обмена ключами с использованием суперсингулярных изогений.

Цель исследований – выбрать один или несколько методов, которые затем можно будет широко применять. Национальный институт стандартов и технологий США запустил в 2016 году разработку стандартов постквантового шифрования для правительственного использования. Он уже сузил изначальный набор заявок с 69 до 26, но говорит, что первые черновики стандартов, скорее всего, появятся не ранее 2022 года.

Критическая важность этой задачи связана с тем, что технологии шифрования глубоко внедрены во множество различных систем, поэтому на их переделку и внедрение новых алгоритмов потребуется очень много времени. В исследовании национальных академий от прошлого года отмечено, что на полное избавление от одного широко использовавшегося криптографического алгоритма, оказавшегося уязвимым, ушло более 10 лет. Учитывая скорость развития квантовых компьютеров, возможно, у мира осталось не так уж много времени, чтобы разобраться с этой новой проблемой безопасности.
Поддержать автора
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 21

    0
    Квантовые компьютеры могут подорвать эту криптографическую защиту. Сегодня эти машины пока недостаточно мощны, но они быстро эволюционируют. Возможно, что не позднее, чем через десять лет – а возможно, и раньше – эти машины смогут стать угрозой для широко используемых методов криптографии. Именно поэтому исследователи и компании, занимающиеся безопасностью, наперегонки разрабатывают новые подходы к криптографии, которые смогут выдержать будущие квантовые атаки хакеров.

    Если убрать из контекста слово "квантовые", а где-то заменить просто на "компьютерные", то это изречение можно было читать или слышать и в 60-х и в 70-х и так до нащих дней.
    А компьютерная защита жива, здравствует и развивается. Так что можно уверенно сказать, что все будет Хорошо!

      –1
      На перекодирование огромных объёмов исторических данных в более надёжный вид могут уйти года, поэтому лучше будет применять надёжное кодирование сегодня.

      Да и когда доживем до этих «домашних» квантовых компьютеров — ими же и перекодировать сможем.
        +2
        Да и когда доживем до этих «домашних» квантовых компьютеров

        Не доживем. Там есть принципиальные физические ограничения.
          0
          Жидкого гелия на всех не хватит.
          0
          этот призыв надо адресовать не криптографам, а производителям железа. Какая там квантовая криптография, когда они выпускают сотни подключенных к интернету устройств логином и паролем админ: админ?
            0
            Меняйте пароль на роутере, если пихаете его в инет.
            P.S. Хотя я себе не менял, только на Wi-Fi.
              0
              увы, кроме роутеров это еще и вебкамеры и не только…
                0

                Так особо выдающиеся производители умудряются логин/пароль рута захардкодить.

                  0
                  Печально.
                  P.S. А где-то на роутере можно логины менять? Как-то даже не знал, на каких-то TP-Link действительно можно.
                    0

                    Да полно где можно. Но это не гарантирует от того, что в коде может быть зашит какой-нибудь root с паролем Qwe123.

                0
                Как раз «соседний» пост на тему камер в де-факто открытом доступе в IoT.
                Тут уже, увы, не все знают азы безопасности и забывают, что у того, чему не нужен доступ к инету, этого доступа быть и не должно.

                В принципе, проэксплойтить уязвимость можно даже с самым сложным логином и паролем, другая проблема в том, что у большинства IoT-устройств лог/пасс admin:admin и стандартные порты. Хотя, конечно, там и Ханипотов — море…
                +2
                Национальный институт стандартов и технологий США запустил в 2016 году разработку стандартов постквантового шифрования для правительственного использования.

                Не разработку, а конкурс. Это очень важная разница в данном случае. Куча специалистов по шифрованию со всего мира представили варианты алгоритмов на конкурс. Там никто не пилит свой закрытый алгоритм, а всё идёт в открытую, анализом и взломом занимаются, опять же, специалисты по шифрованию и математике со всего мира.
                  0
                  Ага, в открытую, особенно вчера отожгли на конкурсе по низкоресурсным алгоритмам: «вы знаете, вы нам до фига алгоритмов на сабмитили, поэтому мы решили некоторые выкинуть из дальнейшего рассмотрения»
                  0
                  Если будет найден способ скейлинга кубитов, то в том же кубическом миллиметре вещества можно будет иметь ~10^18 кубит. Это уже настолько много, что нужно придумывать какие-то алгоритмы, где расшифровка невозможна простыми методами перебора.
                    0
                    На сколько помню матчасть кубитов, там есть ограничение на расстояние между кубитами. В том плане, что слишком близко их не посадишь, иначе они будут влиять друг на друга. Вроде бы ещё не решили эту проблему
                    0
                    ключи длиной в 617 десятичных чисел

                    Со временем взлома порядка (10^617 секунд/«кол-во ядер*частоту»)? Я в курсе, что там все же не так сложно, но все равно взлом кажется слишком долгим.
                      +3
                      ключи длиной в 617 десятичных чисел

                      В очередной раз путают числа и цифры...

                        +4
                        Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах

                        Да, конечно. Понятия не имеем что это.
                          +3
                          Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах каждый раз, когда мы заходим на сайт интернет-магазина, отправляем и получаем емейлы, проверяем наш банковский счёт или кредитную карту.

                          Хм…
                            +1
                            Это находится далеко за пределами возможностей самых мощных из сегодняшних компьютеров, обладающих всего 128 кубитами


                            Со 128-ми кубитами- это явный загон. Ригетти только анонсировали 128 кубит, а не сделали его, так что пока рекорд 72

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


                            Когда это решетки стали экзотическими? NTRU известна с 90-х, кроме того, это стандарт X9.

                            И правильно говорить на изогениях суперсигулярных эллиптических кривых

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое