P + P, P + P + P и т. д. Естественно называть такие решения 2P, 3P и т. д.
В 1985 году Нил Коблиц и Виктор Миллер независимо друг от друга поняли, что можно применить этот групповой закон к эллиптической кривой, чтобы получить шифр. Идея в том, чтобы работать в конечном поле с большим числом элементов. Чтобы зашифровать P, мы получаем kP для очень большого целого числа k, что несложно сделать при помощи компьютера, и называем результат Q. Чтобы обратить этот процесс, мы должны начать с Q и найти P – по существу, разделить Q на k. Из-за сложности групповой формулы обратный расчет очень труден, так что мы придумали новый тип «односторонней» функции с потайным входом, а следовательно, новую криптосистему с открытым ключом. Этот подход известен как шифрование на основе эллиптических кривых, или ECC (Elliptic Curve Cryptography). Точно так же, как RSA может применяться с использованием множества разных простых чисел, ECC может применяться с использованием множества разных эллиптических кривых над множеством разных конечных полей, с разным выбором P и множителя k. Здесь опять же имеется секретный ключ, который позволяет выполнить быструю расшифровку.
Преимущество этой системы в том, что относительно небольшая группа дает шифр, соответствующий по надежности шифру RSA, основанному на значительно больших простых числах. Так что шифр на основе эллиптических кривых более эффективен. Шифровать сообщение и расшифровывать его – при условии, что вам известен секретный ключ, – тоже оказывается быстрее и проще. Взломать шифр, если ключ вам неизвестен, трудно. В 2005 году Агентство национальной безопасности США рекомендовало перенести исследования по криптографии с открытыми ключами в новую область эллиптических кривых.
Как и в случае RSA, не существует строгого доказательства надежности системы ECC. Диапазон возможных атак аналогичен диапазону атак, осуществляемых в отношении RSA.
В настоящее время наблюдается серьезный интерес к криптовалютам, которые представляют собой финансовые системы, не контролируемые традиционными банками, хотя банки тоже начинают интересоваться ими. Банки – они такие: всегда начеку, всегда в поисках новых способов делать деньги. Самая известная криптовалюта – биткоин. Надежность биткоинов обеспечивается таким методом, как блокчейн, который представляет собой шифрованную запись всех транзакций с участием конкретной «монеты» (coin). Новые биткоины появляются в результате майнинга, который, по существу, означает выполнение громадного количества бессмысленных в остальном вычислений. Майнинг биткоинов потребляет значительное количество электроэнергии без какой бы то ни было полезной цели, за исключением обогащения нескольких индивидов. В Исландии, где электричество очень дешево благодаря геотермальным электростанциям, на майнинг биткоинов уходит больше электричества, чем используют все домохозяйства страны, вместе взятые. Вряд ли эта деятельность помогает бороться с глобальным потеплением и климатическим кризисом, но дело обстоит именно так.
Биткоин и многие другие криптовалюты используют одну и ту же эллиптическую кривую под заковыристым названием secp256k1. Ее уравнение, y2 = x3 + 7, запоминается гораздо легче, и это кажется главной причиной ее выбора. Шифрование через secp256k1 основано на одной из точек на этой кривой, заданной координатами
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240;
y = 326705100207588169780830851305070431844712733806592439243275938904335757337482424.
Это наглядно показывает, какие гигантские целые числа задействованы в практических реализациях ECC.
Я уже несколько раз говорил, что надежность системы RSA зиждется на недоказанном предположении о трудоемкости разложения числа на простые множители. Даже если это предположение верно, – а очень похоже, что это действительно так, – не исключено существование и других способов дискредитации надежности шифра (то же самое можно сказать обо всех классических схемах шифрования с открытым ключом). В их числе – появление компьютера, работающего намного быстрее нынешних. Сегодня эта новая угроза безопасности связи уже маячит на горизонте: речь идет о квантовом компьютере.
Классическая физическая система имеет конкретное состояние. Монета на столе может лежать орлом или решкой кверху. Выключатель либо включен, либо выключен. Двоичная цифра (или бит) в памяти компьютера равна либо 0, либо 1. Квантовая система не такова. Квантовый объект – это волна, а волны могут накладываться одна на другую, что на формальном языке называется суперпозицией. Состояние суперпозиции – это смесь состояний компонентов. Знаменитый (мало того, печально знаменитый) кот Шрёдингера может служить ярким примером: при помощи хитроумного устройства с радиоактивным атомом и ампулой ядовитого газа в сочетании с котом в непроницаемом ящике можно добиться того, что квантовое состояние несчастного животного будет суперпозицией состояний «жив» и «мертв». Классический кот должен находиться в одном из этих состояний, а квантовый может находиться в обоих одновременно.
Пока вы не откроете ящик.
Тогда волновая функция кота схлопывается, или коллапсирует, в одно из классических состояний. Кот либо жив, либо мертв. Любопытство (вы же открыли ящик) губит кота. Или не губит.
Я не хочу углубляться в неоднозначные и часто весьма жаркие споры о том, действительно ли квантовые состояния сработали бы подобным образом в случае представителя кошачьего племени{43}. Для нас важно лишь, что математическая физика прекрасно работает для более простых объектов, которые уже используются для создания рудиментарных квантовых компьютеров. Вместо бита, который может быть равен 0 или 1, там мы имеем кубит, который равен 0 и 1 одновременно. Классический компьютер, который может стоять у вас или у меня на столе, лежать в сумке или в кармане, работает с информацией, представленной в виде последовательности нулей и единиц. Он даже использует для этого квантовые эффекты – настолько мал масштаб электронных схем в сегодняшних компьютерах, но суть в том, что все вычисления соответствуют классической физике. При конструировании классических компьютеров инженеры очень стараются сделать так, чтобы нуль всегда оставался нулем, а единица – единицей и чтобы они никогда не встречались. Классический кот может быть либо жив, либо мертв. Так что регистр из (скажем) восьми бит может хранить в себе единственную последовательность вида 01101101 или 10000110.
В квантовом компьютере происходит в точности противоположное. Регистр из восьми кубитов может хранить оба эти варианта одновременно, наряду с остальными 254 возможными 8-битовыми последовательностями. Более того, он может производить арифметические действия со всеми 256 возможными вариантами одновременно. Это как если бы у вас было 256 компьютеров вместо одного. Чем длиннее последовательности, тем сильнее растет число возможностей: 100-битный регистр может содержать единственную последовательность из 100 бит, а 100-кубитный регистр может хранить все 1030 возможных 100-битных последовательностей и при этом манипулировать ими. Это и есть «параллельная обработка данных» в крупном масштабе, и именно это так волнует и восхищает многих в квантовых компьютерах. Вместо того чтобы производить 1030 операций по очереди, одну за другой, вы производите их все разом.
В принципе.
В 1980-е годы Пол Бениофф предложил квантовую модель машины Тьюринга – теоретической основы классических вычислений. Вскоре после этого физик Ричард Фейнман и математик Юрий Манин указали, что квантовый компьютер будет способен производить громадное количество вычислений параллельно. Серьезный прорыв в теории квантового компьютера произошел в 1994 году, когда Питер Шор придумал очень быстрый квантовый алгоритм для разложения больших чисел на простые множители. Из этого следует, что криптосистема RSA потенциально уязвима для атак противника, использующего квантовый компьютер, но, что еще важнее, квантовый алгоритм может серьезно превзойти алгоритм классический в решении осмысленной, неискусственной задачи.
На практике на пути к созданию квантового компьютера нас ждут просто громадные препятствия. Крохотные возмущения от внешних источников или даже просто тепловые колебания молекул вызывают декогеренцию, то есть разрушение состояния суперпозиции, причем очень быстрое. Для смягчения этой проблемы машину в настоящее время приходится охлаждать до температуры, очень близкой к абсолютному нулю (–273 ℃), что требует использования гелия-3 – редкого побочного продукта ядерных реакций. Но даже это не может предотвратить декогеренцию, а лишь замедляет ее. Так что каждое вычисление приходится дополнять системой коррекции ошибок, которая замечает нарушения, вызванные помехами от внешних источников, и возвращает кубиты в то состояние, в котором они должны находиться. Квантовая пороговая теорема утверждает, что такой метод работает при условии, что система способна исправлять ошибки быстрее, чем декогеренция их вызывает. По приблизительной оценке, вероятность ошибки для каждого логического ключа не должна превышать одну тысячную.
Коррекция ошибок имеет свою цену: она требует больше кубитов. Например, чтобы разложить на простые множители число, которое может храниться в n кубитах с использованием алгоритма Шора, на процесс вычисления требуется время, примерно пропорциональное чему-то промежуточному между n и n2. С учетом коррекции ошибок, совершенно необходимой на практике, время становится более похожим на n3. Для 1000-кубитного числа коррекция ошибок увеличивает время расчета в тысячу раз.
До последнего времени никому не удавалось построить квантовый компьютер больше чем с несколькими кубитами. В 1998 году Джонатан Джонс и Мишель Моска использовали 2-кубитное устройство для решения задачи Дойча, которая сформулирована в работе Дэвида Дойча и Ричарда Джоза 1992 года. Это квантовый алгоритм, работающий экспоненциально быстрее любого традиционного алгоритма, он всегда дает ответ, и этот ответ всегда верен. Решает он следующую задачу. Нам дано гипотетическое устройство (