Книга шифров

Еще одна проблема была вызвана тем, что ученые не знали, как запрограммировать квантовый компьютер, и поэтому не были уверены, какого рода вычисления он способен производить. Однако в 1994 году Питеру Шору из AT&T Bell Laboratories штата Нью-Джерси удалось составить пригодный для квантового компьютера алгоритм. Замечательной новостью для криптоаналитиков было то, что алгоритм Шора описывал ряд шагов, которые могли бы быть использованы квантовым компьютером для разложения на множители гигантского числа, то есть как раз то, что требовалось для взлома шифра RSA. Когда Мартин Гарднер опубликовал задачу по RSA в «Сайентифик Америкен», потребовалась работа шести сотен компьютеров в течение нескольких месяцев, чтобы разложить на множители число, состоящее из 129 цифр. Для сравнения, с помощью алгоритма Шора можно было разложить на множители число, в миллион раз большее, за время, в миллион раз меньшее. К сожалению, он не мог продемонстрировать свой алгоритм для разложения на множители, поскольку по-прежнему не было такого инструмента, как квантовый компьютер.

В 1996 году Лов Гровер, также из Bell Laboratories, разработал еще один мощный алгоритм. Алгоритм Гровера — это способ осуществления поиска в списке[35] с невероятно высокой скоростью, что может казаться не особенно интересным, пока вы не поймете, что это именно то, что требуется для взлома шифра DES. Чтобы взломать шифр DES, необходимо выполнить поиск списка всех возможных ключей, чтобы найти правильный. Если обычный компьютер может проверять миллион ключей в секунду, то для раскрытия шифра DES ему потребуется свыше тысячи лет, в то время как квантовый компьютер с помощью алгоритма Гровера смог бы найти ключ менее, чем за четыре минуты.

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