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

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

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

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

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

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

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

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

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

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

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

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