Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Теперь мы смотрим на эллиптические кривые – уравнения – через призму конечных колец и полей. Геометрический образ кривой здесь, по существу, неприменим, поскольку имеется всего лишь конечное множество точек, но нам удобно пользоваться прежним названием. На рисунке показана типичная фигура и ее дополнительное свойство, известное еще Ферма и Эйлеру и интриговавшее математиков в начале XX века. Имея два решения, можно «сложить» их, чтобы получить еще одно решение, как показано на рисунке. Если решения – рациональные числа, то рациональным числом будет и их сумма. Это не просто «купи два, получи третье бесплатно», а «купи два, получи бесплатно уйму всего», потому что операцию и построение можно повторить. Иногда это вновь приводит нас в одну из начальных точек, но в основном подобные действия генерируют бесконечно много различных решений. Мало того, эти решения имеют красивую алгебраическую структуру: они образуют группу Морделла – Вейля эллиптической кривой. Луис Морделл доказал ее основные свойства, а Андре Вейль обобщил их. Слово «группа» здесь означает, что дополнение подчиняется короткому списку простых правил. Эта группа коммутативна, то есть P + Q = Q + P, что очевидно из рисунка, поскольку прямая, проведенная через P и Q, совпадает с прямой, проведенной через Q и P. Существование такой групповой структуры – явление необычное, и большинство диофантовых уравнений не может этим похвастаться. Многие из них вовсе не имеют решений, некоторые имеют всего по несколько, и трудно предсказать, какое именно уравнение находится перед вами. В настоящее время эллиптические кривые находятся в центре интенсивных исследований – по этой и другим причинам. Доказывая Великую теорему Ферма, Эндрю Уайлс доказал глубокую гипотезу об эллиптических кривых, которая стала одним из ключевых этапов доказательства.
* * *
Групповая структура эллиптической кривой интересует и криптографов. Обычно она рассматривается как форма «дополнения» к решениям, хотя формула там намного сложнее, потому что она коммутативна, и символ + стал традиционным в теории коммутативных групп. В частности, если есть решение (x, y), которое можно рассматривать как точку на плоскости, то мы можем генерировать решения 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. Квантовая система не такова. Квантовый объект – это волна, а волны могут накладываться одна на другую, что на формальном языке называется суперпозицией. Состояние суперпозиции – это смесь состояний компонентов. Знаменитый (мало того, печально знаменитый) кот Шрёдингера может служить
