алгоритмы Шора и Гровера |

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

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

Алгоритм Шора и асимметричное шифрование

Шора и Гровера - алгоритмы Шора и Гровера |
Квантовая подпрограмма алгоритма Шора.

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

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

Алгоритм разделён на две части:

  1. Преобразование задачи факторизации в задачу нахождения порядка (которая может быть выполнена на обычном современном компьютере).
  2. Квантовый алгоритм для решения задачи нахождения порядка (неэффективен сегодня из-за недостатка возможностей квантовых вычислений).

Используется самый обычный стандарт шифрования, в котором классический компьютер делает 2128 (340 282 366 920 938 463 463 374 607 431 768 211 456) базовых операций для нахождения приватного ключа, связанного с публичным ключом. Квантовому компьютеру потребуется 1283 (только 2 097 152) базовых операций для вычисления приватного ключа, связанного с публичным ключом).

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

Алгоритм Гровера и хеширование

1557390003 643 алгоритмы Шора и Гровера - алгоритмы Шора и Гровера |
Квантовая схема алгоритма Гровера

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

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

Алгоритм Гровера имеет свойство вероятности: он измеряет вероятность различных возможных состояний системы.

Вот как он работает.

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

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

На классическом компьютере для нахождения правильного хеша потребовалось бы 2256 (78-значное число) базовых операций. Алгоритм Гровера, запущенный на квантовом компьютере, использовал бы только 2128 базовых операций (39-значное число, разделённое в секции алгоритма Гровера) для нахождения правильного хеша.

Вывод

1557390003 435 алгоритмы Шора и Гровера - алгоритмы Шора и Гровера |

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

Источник

Источник

Зацените вот что

Криптовалютная биржа Coinbase ведет переговоры о покупке сервиса Xapo

Криптовалютная биржа Coinbase ведет переговоры о покупке сервиса Xapo |

Американская криптовалютная биржа Coinbase ведет переговоры о покупке кастодиального сервиса Xapo за $50 млн для …

Третья часть эмиссии Ethereum находится в руках 376 человек

Третья часть эмиссии Ethereum находится в руках 376 человек |

Специалисты Chainalysis собрали информацию о крупных держателях криптовалюты и проанализировали их влияние на цифровую индустрию. …

ЦБ Франции изучает выпуск стейблкойнов

ЦБ Франции изучает выпуск стейблкойнов |

Президент Банка Франции Франсуа Виллеруа де Гало (Francois Villeroy de Galhau) заявил, что видит будущее …