Алгоритм Шора против блокчейна

Питер Шор и его алгоритм

Ученые — удивительный народ, им только дайте что-нибудь изобрести или открыть. А потом всем миром приходится думать, что же с этим открытием делать. Например, атомная энергия — явление сколь полезное, столь же и опасное. И алгоритм Питера Шора — наглядный тому пример.

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

И вот в 1994 году американский ученый Питер Шор (Peter Shor) разработал эффективный полиномиальный алгоритм разложения больших чисел на множители для квантового компьютера. Звучит загадочно, но что в этом страшного? А вот что. Так, асимметричная криптография базируется на задаче факторизации произведения двух больших чисел. Суть задачи: есть произведение двух огромных чисел, нужно найти исходные множители. Однако классический компьютер не способен решить эту задачу за приемлемый срок. На это ушли бы миллионы лет. Именно на этом и базируется современное асимметричное шифрование — невозможно быстро решить задачу факторизации и вычислить приватный ключ.

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

Проверка алгоритма Шора

В 1994 году у Питера Шора не было возможности проверить разработанный алгоритм на практике. Ведь тогда квантового компьютера не было даже в проекте.Однако уже в 2001 году алгоритм Шора был протестирован группой специалистов из IBM на 7-кубитном квантовом компьютере. Так, число 15 было разложено на два простых множителя 3 и 5. Казалось бы, совсем простенькая задачка. И с ней справится любой школьник — не только без квантового компьютера, но даже без калькулятора.

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

Алгоритм Шора против блокчейна

Алгоритм Шора очень опасен для блокчейна. И вот почему. Дело в том, что криптография с открытым ключом (асимметричное шифрование) — это сердце блокчейна. И криптовалют. Например, в блокчейне Биткоина открытый ключ передается в сеть в незашифрованном виде при совершении каждой транзакции. И у потенциального злоумышленника есть целых 10 минут (время подтверждения блока в сети Биткоина), чтобы провести атаку на публичный ключ, вычислить приватный ключ и подменить адрес, на который отправлены монеты.

И не только против блокчейна

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

Поделиться в facebook
Поделиться в google
Поделиться в twitter
Поделиться в linkedin
Поделиться в telegram
Поделиться в vk
Поделиться в pocket
Поделиться в email