Шор как угроза современной криптографии +22



Привет, Хабр!

В настоящее время, как в известной басне, ведется опасное соревнование «черепахи и зайца» между квантовыми вычислениями и классической криптографией. Последняя же защищает Интернет, регистры блокчейнов, средства коммуникации и многое другое. Не похоже, что медленно развивающиеся сегодня квантовые вычисления скоро поймают классическую криптографию, но предупреждение в басне всё равно уместно.

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

Проблема Y2Q

Исследователи придумали термин, обозначающий момент, когда "черепаха" будет проходить мимо "зайца". Это год Y2Q, когда возможности квантового взлома кода станут угрозой существованию классической криптографии. Когда это произойдет, остается только догадываться, но вопрос о том, произойдет ли это, для многих уже решен. В 2018 году в отчете Национальной академии наук, инженерии и медицины США (NASEM) было предсказано, что мощный квантовый компьютер, использующий алгоритм Шора, сможет взломать 1024-битную реализацию шифрования RSA менее чем за 24 часа.

Математик Питер Шор, ответственный за один из алгоритмов, в конце 2020 года добавил свое собственное предупреждение: «Я думаю, что единственным препятствием для замены RSA [криптосистемы с открытым ключом] на безопасную постквантовую криптосистему будет сила воли и время программирования... Если мы будем ждать слишком долго, будет слишком поздно».

В конце 2018 года редакторы журнала Nature объяснили риск, связанный с продуктами блокчейн. Так, безопасность блокчейна основана на односторонних математических функциях. Их легко запустить на обычном компьютере и трудно рассчитать в обратном порядке. Например, умножить два больших простых числа легко, но найти простые множители данного произведения сложно — обычному компьютеру может потребоваться много лет, чтобы решить.

Но алгоритм Шора разработан для работы на квантовом компьютере, который может принимать число и выводить его множители за короткий промежуток времени. С математической точки зрения, это потребует логарифмического (log(N)),а не экспоненциального (exp(N))количества времени. Алгоритм Гровера также является квантовым алгоритмом, предназначенным для ускорения поиска в несортированных базах данных.

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

Алгоритм Шора

Питер Шор
Питер Шор

В этом параграфе кратко рассмотрим сам алгоритм Шора. Цель алгоритма: для нечетного составного числаNнужно найти целое числоd(строго от 1 доN),на которое делитсяN.

Алгоритм Шора состоит из следующих частей:

  • Преобразование проблемы факторизации в задачу нахождения периода. Эта часть может быть реализована классическими средствами.

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

Факторизация числа
Факторизация числа

Общая последовательность действий:

INPUT (N) \rightarrow \text{Алгоритм Шора} \rightarrow OUTPUT(\text{Нетривиальный множитель } N)

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

  1. Выбираем любое случайное число r < Nтакое, что rи N— взаимно простые числа.

  2. Квантовый компьютер используется для определения неизвестного периода pфункции f_{r, N} (x) = r^x \text{ mod }N.

  3. Если p— нечетное целое число, возвращаемся к шагу 1. В противном случае переходим к следующему шагу.

  4. Поскольку p— четное целое число, то (r^{p/2}-1)(r^{p/2} +1) = 0 \text{ mod } N.

  5. Теперь, если значение r^{p/2} + 1 = 0 \text{ mod } N,то возвращаемся к шагу 1.

  6. Если значение r^{p/2} +1 \neq 0 \text{ mod }N,переходим к следующему шагу.

  7. Вычисляем d= gcd(r^{p/2} - 1, N).

  8. Получаем требуемое значение d.

Существующие атаки

Для примера, рассмотрим атаку, которая нацелена именно на алгоритм RSA. Суть этой атаки заключается в поиске ключа путем факторизации большого числа (алгоритм Шора для этого как раз заточен!). Если мы сможем вычислить простые числа, которые использовались для генерации конкретного ключа, то фактически получим значение этого ключа.

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

По существующим оценкам учёных, при наличии квантовых компьютеров нам потребуется около 20 миллионов физических кубитов для ключа размером 2048 бит. Вы удивитесь, но даже и при таком огромном количестве кубитов нам нужно будет ждать 8 часов.

Если у нас в распоряжении не такие мощные квантовые компьютеры, то оценки показывают, что с 13436 квантовыми единицами информации мы должны будем потратить 177 дней. Сегодня мы не располагаем такой возможностью. Хорошо это или плохо? Поговорим в следующем разделе.

Перспективы развития

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

Можно выделить несколько перспективных методов, на которых основана постквантовая криптография:

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


Стоит отметить, что проблема массового исчезновения информационной безопасности не нова. Шифрование, созданное немецкими военными машинами Enigma во время Второй мировой войны, в конечном итоге было взломано союзниками, но на этом криптография не закончилась. А в 1977 году в ходе публичного конкурса был нарушен современный стандарт шифрования данных (DES).

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

Не все предсказывают, что гонка завершится через несколько лет. Например, Роджер Граймс, специалист по обеспечению безопасности KnowBe4, объявил, что 2021, вероятно, станет первым публичным признанием квантового криптографического взлома, когда квантовые компьютеры будут способны взламывать традиционные криптографические ключи с открытым ключом. Как мы можем наблюдать, этого пока не случилось.

Заключение

Итак, в нашей статье мы рассмотрели опасность квантового вычисления для классического шифрования Y2Q, представили краткое описание алгоритма Шора и поговорили о перспективах развития криптографии.

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

Спасибо за внимание!




Комментарии (59):

  1. johnfound
    /#23766281 / +9

    Учёные предсказывают, что в течение десяти лет квантовые компьютеры...

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

    • Wesha
      /#23766519 / +16

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

      Я это предсказание читал в 1990 году, и с тех пор каждые 5 лет.

    • LevPos
      /#23766695 / +3

      Статья 2018 года:

      Квантовые компьютеры поставят под угрозу безопасность блокчейна (часть 1)

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

      Год неизвестен:

      Немного о квантовых компьютерах

      Таким образом, исследования активно ведутся и можно предположить, что в самом недалеком будущем — лет через десять — эффективный квантовый компьютер будет создан.

      • Carburn
        /#23766877

        Очень даже известен год - 2004. Так создали же квантовый компьютер

        • netch80
          /#23766947 / +1

          А эффективный квантовый компьютер? ;)

    • IkaR49
      /#23766913 / +7

      Управляемый термояд существует. Но пока что выход энергии меньше, чем необходимо для его работы :)

    • imater
      /#23767479

      Тогда ходила байка что плейстейшены запретили, так как они слишком мощные и могут помогать делать расчеты для ядерной программы

      • Kazehay
        /#23772061

        Запретить не запрещали, но активная скупка могла создать некий дефицит))

        Например Пентагон так развлекался 11 лет назад.

  2. Stas911
    /#23766485

    Вот еще видео на тему: https://www.youtube.com/watch?v=_GSDUXPpSgc

  3. Alcpp
    /#23766559 / +4

    Так сколько же кубитов нужно, чтобы взломать RSA?

    • SemyonSinchenko
      /#23766677 / +14

      20 миллионов "физических" (то есть таких, которые есть сегодня - коррекция ошибок уже учтена) кубитов: https://arxiv.org/abs/1905.09749, взлом займет 8 часов, оценка для 2048 битного ключа. Есть еще вариант взломать используя всего ~15000 кубитов: https://arxiv.org/abs/2103.06159, но тогда нужно иметь миллионы единиц квантовой памяти (qRAM), а ее сегодня еще вообще нет.

      • pfg21
        /#23767379 / +3

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

      • tbp2k5
        /#23767881 / +2

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

        • Tarakanator
          /#23768975 / +1

          Подозреваю что десятки-сотни кубитов — и есть тот порог за которым поведение системы больше нельзя рассматривать как квантовое.

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

          • tbp2k5
            /#23769267

            Видимо не точно выразился: теоретически возможно, но практически не реализуем — проблема масштабирования. С одной стороны у вас «облако кубитов», а другой «инфраструктура» для поддержки/работы с ними. С определенного масштаба будет невозможно «аннулировать» влияние второй на первую. Как-то так…

            • Tarakanator
              /#23771443

              Ну да есть такие опасения, но смотрю я на развитие хайтека и думаю что прогресс не остановить.

            • Kazehay
              /#23772819

              Проблема масштабов уже есть, т.н. квантовые шумы. Поиск решений, на сколько мне известно, идёт сейчас в нескольких направлениях:

              • Снижение шумов температурой и, соответственно, миниатюризация систем охлаждения

              • Компенсация шумов за счёт дублирования кубитов (логические кубиты

              • Переход на более крупные объекты, вплоть до молекул.

              Вообще не специалист, просто слежу за новостями.

      • Alcpp
        /#23769307

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

        • SemyonSinchenko
          /#23769567

          Верно. Сегодня опасения вызывает не количество кубитов, а то, что компания IBM и другие лидеры области пока выполняют свои планы, которые они озвучивали в 18-19 годах. В этом году IBM (пусть и под самый конец кода) представили 127-и кубитный чип, в след году обещают 430 кубитов, в 23-м году уже более 1000. К 2030-му году основные сегодняшние игроки планируют иметь уже миллион кубит. Просто и переход на постквантовую криптографию это тоже дело не быстрое...

      • arpoyda
        /#23778485

        Спасибо за количественные оценки, действительно выглядит нагляднее!

    • nckma
      /#23769441

      Меня очень удивляет, когда рассматривают только количество кубитов и таким образом оценивают возможности квантового компьютера. А кроме кубитов нужны еще квантовые вентиля. А сколько их? А какие есть в наличии? Например, в квантовом компьютере IBM физически есть только три вида вентилей, остальные эмулируются в пользовательском интерфейсе. А какие кубиты физически можно соединять, а какие нет в физическом квантовом компьютере? Зависит от схемы соединений по реализуемому алгоритму. В общем там очень много факторов.

  4. MAXH0
    /#23766579 / +2

    Есть у меня одна паранойя. С учетом того что Энигмой торговали, когда она уже была надежно взломана, то какие шансы что RSA так же взломана без всяких квантовых компьютеров. Все миллиарды лет, которые требуются для подбора ключа, они сформулированны для обычных компьютеров и алгоритмов. Возможно ли, что был сделан аналоговый проц, который сильно облегчает подбор ключа и засекречен?

    • zorn-v
      /#23766623 / +5

      Математики всего мира не разделяют вашу паранойю...

      Конечно если "догадавшегося" тут же не увозят на ч0рных вертолётах :D

      • MAXH0
        /#23766691 / +1

        А разве все доказательства не основаны на определенной архитектуре компьютера, заданной априори?

      • vanxant
        /#23766861 / +2

        Математики всего мира не разделяют вашу паранойю...

        Ну есть некая разница между задачей факторизации и стойким алгоритмом шифрования на её основе. См. историю любви АНБ и DES, например.

        • paluke
          /#23767023 / +11

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

        • 2ANikulin
          /#23771349

          Что там за история любви АНБ и DES?

          Можете ссылкой поделиться?

          • LevPos
            /#23771737

            DES

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

      • novoselov
        /#23766885

        Оставайтесь на месте, за вами уже вылетели ...

    • vsb
      /#23766707 / +4

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

      Но в рамках паранойи - сейчас очень активно проталкивается идея перехода на алгоритмы на эллиптических кривых, несмотря на то, что RSA хоть и имеет ряд объективных недостатков, но по сути при правильном использовании вполне себе стойкий алгоритм. Меня лично это вот так слегка напрягает и удивляет. Но, повторюсь, исключительно в рамках бессознательной паранойи, не воспринимайте это, как осмысленный аргумент.

      • MAXH0
        /#23766749 / +1

        По поводу эллиптических согласен...

      • netch80
        /#23766943

        > Но в рамках паранойи — сейчас очень активно проталкивается идея перехода на алгоритмы на эллиптических кривых

        Пишут, что ECC алгоритмы точно так же пострадают от квантовых компьютеров. Переход RSA->ECC идеологически обосновывался лет 20 назад.

        • plus79501445397
          /#23769177

          Пишут, что ECC алгоритмы точно так же пострадают от квантовых компьютеров.
          Скорее они даже больше/раньше пострадают в случае развития квантовых компьютеров (КК) до соотв. уровня. Из практических соображений стандартные ключи подписей на основе EC как правило короче, чем у RSA, ElGаmal или старого ГОСТа ЭЦП (без EC). По всей видимости в этом не было бы потенциальной проблемы в плане криптосткойкости, если бы не приближающаяся угроза со стороны КК. По вашей же ссылке пишут, что приведенные оценки (для EC с 256-битными модулями и RSA c 2048-битными ключами) позволяют предположить, что ECС является более легкой целью для КК чем RSA: «ECC is an easier target for quantum computers than RSA».

      • emaxx
        /#23771089

        Паранойя паранойей, но эллиптические кривые гораздо быстрее же.

  5. zorn-v
    /#23766599 / +4

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

    Людикони. Хеш функция необратима по определению (нельзя из хеша файла востановаить файл, если так понятнее). А перемножение больших простых чисел - это про ассиметричное шифрование (RSA).

    • paluke
      /#23766977 / +3

      Так и не надо ее обращать, обычно достаточно найти коллизию — два файла с одинаковым хешем.

      • zorn-v
        /#23767863

        Прочитайте что написано в цитированном тексте.

        И при чем тут коллизии вообще ? Как они помогут взломать блокчейн ?

        • unsignedchar
          /#23767953 / +1

          И при чем тут коллизии вообще? Как они помогут взломать блокчейн ?

          Ну вот окажутся в блокчейне 2 записи, подписанные одной подписью, согласно 1 — в вашем кошельке 0.00001BTC, согласно 2 — 999999BTC. Обе записи верные.

          • zorn-v
            /#23768249

            Вы чем вообще ? А если ОДНОМОМЕНТНО хеш блока найдут 2-10 разных людей без всяких коллизий ?

            Даю намек - консенсус.

            согласно 1 — в вашем кошельке 0.00001BTC, согласно 2 — 999999BTC

            Нет никакого "моего кошелька". Есть транзакции которые приносят на адреса "моего кошелька" BTC. Транзакции переписать нельзя.

            Ну да ладно.

        • dmitrysvd
          /#23768407 / +1

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

  6. frkbvfnjh
    /#23766669 / +1

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

    А откуда такое утверждение? Вы реально думаете, что если сделают квантовый криптографический взлом, вам по телевизиру скажут что ли? Я вот только сегодня узнал, что эти самые телики каждую секунду на сервера снимки экрана шлют и то, об этом не распространяются. И все уже прекрасно знают, что взламываются буквально все устройства и айфончики и дроиды и все что угодно и вообще ваше шифрование это защита корпораций и власти от дурачков - не более. Дяди сверку могут получить любую информацию о вас. Может ее и можно было бы скрыть от них, только вот во всех источниках информации есть лазейки для тех кому нужно. Так что вам простым смертным, что есть эта криптография что ее нет. В полне возможно что любую криптографию уже давно ломают, только вот вам все забывают об этом сказать.

    • LevPos
      /#23766757 / +1

      Само предсказание отсюда:

      6 experts share quantum computing predictions for 2021

      "I predict that someone will publicly announce that they have used a quantum computer to break a traditional asymmetric key cipher. It's been the Holy Grail since 1994 and I predict it happens next year."

    • dimskiy
      /#23766767

      как минимум, ваша теория не предполагает доступ к зашифрованным данным широких масс. Что позволяет вашим токенам от интернет-банка оставаться вашими :)

    • dem0crypt
      /#23768333

      Шапочку из фольги в ванной хоть снимаете?

  7. vsb
    /#23766715

    А сколько битов может факторизовать современный квантовый компьютер? Если судить по новостям, то вроде в районе 100-150 кубитов последние достижения. Но я много раз читал, что это "не настоящие" кубиты, они не связаны между собой как положено, т.е. даже 30 битов (из расчёта 4N кубитов) ими не факторизовать.

    • paluke
      /#23767129 / +1

      А несколько лет назад последним достижением было порядка десятка кубитов…

    • zorn-v
      /#23768329 / -2

      Когда вы натягиваете носок на левую ногу, второй автоматически становится правым вне зависимости от расстояния между ними.

      В этом есть суть квантовой запутанности )

  8. aml
    /#23767057 / +2

    Очевидно, что когда-то всё учёное сообщество верило в абсолютную стойкость классических криптографических систем.

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

    • lealxe
      /#23767269

      Люди, не имеющие отношения к "ученому сообществу", почему-то постоянно приписывают оному скопом слепую веру во что-то (я тоже этого отношения не имею, просто кринж), которую говорящий, конечно, не разделяет.

      А человек, который это написал, видимо, не в курсе, что сегодня уже никто не пользуется RC4, Blowfish, DES, для хэшей родными MD4 и MD5 , что вроде вполне обывательские ойтишные знания.

      • ksbes
        /#23767435

        Ну 3DES до сих пор много где используют, особенно в банках, как ни странно. Старичёк ещё тянет! Надеюсь с него не будут переходить на 5DES или что-то такое. А то могут :) (чипов с хардварной реализацией-то дофига уже сделанно - не выбрасывать же?)

        • zorn-v
          /#23767945

          на 5DES или что-то такое. А то могут :)

          Лишь бы ляпнуть ? 3DES это просто "шифруем три раза, потому что ничего лучше нет". Сейчас есть AES.

          5DES в стандарте нет. А это сложнее утрясти чем слабую/медленную криптографию.

          • Tarakanator
            /#23769041 / +1

            Угу, вот выйдет ГОСТ на шифрование переписки, что можно только 3DES и 5DES и посмотрим как вы AES сделаете.

            *Если считаете заявление слишком бредовым, то замените 5des на любой проприетарный алгоритм.

            • zorn-v
              /#23769249

              *Если считаете заявление слишком бредовым, то замените 5des на любой проприетарный алгоритм.

              Гы. Вы реально думаете что "там" тупые сидят, чтобы использовать алго от "васи пупкина" (а "5DES" таким и является) ?

              Вы несете какую то дичь, извините.

              ЗЫ. Мне кажется что вы намекаете про "крипто про". Но DES/AES тут вообще никаким боком.

              • Tarakanator
                /#23771433

                Я не намекаю на криптопро.

                Я думаю там не такие тупые, а такие наглые, что могут заставить использовать криптоалгориомы с бэкдором.

      • pfg21
        /#23767447 / +2

        люди, не имеющие к "ученому сообществу", не понимают онное "ученое сообщество" от слова них...я :) по вполне понятным причинам - спробуйте бухгалтерше объяснить стройную систему программирования на языке 1с :)

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

        "потому и не кусают" (с) реклама.

  9. johnfound
    /#23767701 / +5

    Пока ученые публикуются на эти темы, то все нормально, нечего бояться.


    А вот, когда однажды все публикации приостановятся, тогда и надо начинать беспокоится.

  10. zorn-v
    /#23768381 / +1

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