Непростая загогулина. Краткий путеводитель по эллиптическим кривым

Источник: t.me/USBKiller

Содержание статьи

• Криптография с открытым ключом: как все начиналось
• Алгоритм RSA в миниатюре
• Не такой уж тайный ход
• Эллиптические кривые: где найти надежный потайной ход?
• Странная симметрия
• Все страньше и страньше
• Что все это значит?
• Эллиптические кривые в действии
• Оборотная сторона
• Заглядывая вперед

Криптография с открытым ключом: как все начиналось

Историю криптографии можно разделить на два периода: классический и современный. Водоразделом здесь служит 1977 год, когда одновременно были представлены алгоритм RSA и протокол Диффи — Хеллмана. Случилась настоящая революция: это были первые криптографические системы, где безопасность строилась на теории чисел. Стала возможной безопасная коммуникация без известного обеим сторонам — то есть симметричного — шифра. До этого криптография бесконечно занималась вопросом, как безопасно переслать секретные шифры. Теперь же она могла обеспечить доказательно безопасную коммуникацию между двумя сторонами — без заботы о том, не перехватит ли кто обмен ключами.

Современная криптография стоит на том, что ключ для шифрования данных может быть открытым, а вот ключ для дешифровки лучше оставить в секрете. Такие системы называют криптографическими системами с открытым ключом (public key cryptographic systems). Первая — и все еще самая распространенная из них — RSA. Она названа инициалами тех, кто впервые описал ее алгоритм (Ron Rivest, Adi Shamir, Leonard Adleman).

Хорошей криптографической системе с открытым ключом нужен набор алгоритмов, которые легко пройти в одном направлении и трудно в обратном. В случае с RSA «легкий» алгоритм умножает два простых числа. Его «трудной» парой будет факторизация — разложение получившегося результата на изначальные множители. Алгоритмы с такой характеристикой — «просто в одну сторону, трудно в обратную» — называют односторонней функцией с потайным входом (trapdoor function, TDF). Найти хорошую TDF критично важно для создания безопасной криптографической системы с открытым ключом.

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

Алгоритм RSA в миниатюре

RSA — самая популярная и наиболее понятная из систем с открытым ключом. Ее безопасность опирается на то, что умножение — это быстро, а разложение на множители — медленно. Коротко рассмотрим, как выглядит и работает маленькая RSA-система.

Системы с открытым ключом обычно имеют два компонента: открытый ключ и секретный ключ. Шифрование работает так: берешь сообщение, применяешь к нему математическую операцию — и получаешь число, которое выглядит случайным. При дешифровке берешь это «случайное» число и применяешь другую операцию, чтобы получить исходное сообщение. Зашифрованное с помощью открытого ключа можно расшифровать, только применив секретный ключ.

Компьютеры не очень хорошо справляются с произвольно большими числами. Эту проблему можно решить, если выбрать максимальное значение и иметь дело только с числами, которые меньше максимума. Работает это как в часах с циферблатом и стрелками. Как перевести их, например, на 37 часов? Очевидно, разделить 37 на максимум — то есть 12 — и докрутить остаток. Так и здесь: любые вычисления, дающие результат больше максимума, мы «докручиваем» до числа в допустимом диапазоне.

В RSA максимальное значение (обозначим его max) получают умножением двух случайных простых чисел. Открытый и секретный ключи — это два специально выбранных числа больше нуля, но меньше максимального значения, обозначим их pub и priv. Чтобы зашифровать число, мы перемножаем его pub раз — и всякий раз «докручиваем», когда превышаем максимум. Чтобы расшифровать сообщение, перемножаем его priv раз по тому же правилу — и получаем исходное число. Звучит удивительно, но правда работает. Когда обнаружили эту особенность, она стала большим прорывом.

Чтобы создать пару ключей для RSA, сначала берешь два простых числа, чтобы получить максимум (max). Затем выбираешь число для открытого ключа (pub). До тех пор пока ты знаешь два изначальных простых числа, ты можешь вычислить секретный ключ priv через открытый. Это то, как факторизация соотносится со взломом RSA: разложение максимального значения на исходные множители позволяет вычислить чей-то секретный ключ по открытому и дешифровать личные сообщения.

Рассмотрим все это на конкретном примере. Возьмем простые числа 13 и 7, перемножим и получим максимальное значение 91. В качестве открытого ключа возьмем число 5. А затем, зная изначальные множители и максимум, применим расширенный алгоритм Евклида и получим секретный ключ — 29.

Эти параметры (max = 91, pub = 5, priv = 29) определяют полностью функциональную RSA-систему. Мы можем взять число и перемножить его пять раз для зашифровки, а затем взять получившийся результат, перемножить его 29 раз и получить изначальное число.

Используем эти значения, чтобы зашифровать слово CLOUD.

Чтобы представить сообщение математически, нужно превратить буквы в числа. Для представления латинского алфавита отлично подходит кодировка UTF-8. Каждому символу соответствует свой номер.

В этой кодировке CLOUD выглядит как 67, 76, 79, 85, 68. Все эти числа меньше нашего максимума, поэтому мы можем зашифровать их по отдельности.

67 × 67 = 4489 = 30

4489 = 91 × 49 + 30
30 × 67 = 2010 = 8
8 × 67 = 536 = 81
81 × 67 = 5427 = 58

58 и будет зашифрованной версией 67.

Повторив этот процесс для каждой из букв, мы получим зашифрованное сообщение CLOUD в виде

58, 20, 53, 50, 87

Чтобы расшифровать это запутанное сообщение, берем каждое из получившихся чисел — и точно так же перемножаем 29 раз.

58 × 58 = 3364 = 88 (помни, что мы «докручиваем» число, если оно превышает максимум)
88 × 58 = 5104 = 8
…
9 × 58 = 522 = 67

Вуаля, мы вернулись к 67. Провернув то же самое с остальными числами, мы получим исходное сообщение.

Вывод: ты можешь взять число, перемножить его сколько-то (pub) раз и получить случайно выглядящий результат, а потом перемножить его другое количество (priv) раз и вернуться к изначальному числу.

Не такой уж тайный ход

RSA и протокол Диффи — Хеллмана были столь мощны, потому что имели строгие обоснования безопасности. Их авторы доказали, что взлом системы равен решению математической проблемы, которую, как считается, сложно решить. Факторизация — хорошо известная проблема, ее изучают с античности (см. решето Эратосфена). Любые прорывы в этой области стали бы громкой новостью и озолотили изобретателя.

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

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

Все это значит, что RSA далеко не идеальная система для криптографии будущего. В идеальной TDF операции «туда» и «обратно» усложняются в одинаковом темпе — пропорционально растущему размеру чисел. Нам нужен потайной ход понадежней.

Эллиптические кривые: где найти надежный потайной ход?

С появлением RSA и протокола Диффи — Хеллмана начался активный поиск других математически обоснованных решений для криптографии, которые могли бы послужить хорошей TDF. И вот в 1985 году были предложены алгоритмы, основанные на таинственном математическом направлении — эллиптических кривых.

Но что же такое эллиптическая кривая — и как работает основанная на ней TDF? К сожалению, в отличие от факторизации — штуки, с которой мы неизбежно сталкиваемся в школе, — эллиптические кривые большинству людей не близки. Понять и объяснить их не так-то просто — впрочем, я все равно попытаюсь. (Если глаза уже начали стекленеть, можешь скипнуть до раздела «Что все это значит?».)

Эллиптическая кривая — это множество точек, удовлетворяющих конкретному математическому уравнению. Выглядит оно так:

y² = x³ + ax + b

Его график отдаленно напоминает упавшую набок греческую букву Ω (омега).

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

Странная симметрия

Еще раз взглянем на нашу эллиптическую кривую — и найдем те самые особенности.

Одна из них — горизонтальная симметрия. Каждую точку на кривой можно зеркально отразить по оси x — и окажешься на все той же кривой. Еще интересней то, что любая не строго вертикальная прямая пересекает эллиптическую кривую не более чем в трех местах.

Представим, что это такой странный бильярд. Если соединить две точки на кривой, проходящая через них прямая пересечет ее еще ровно в одном месте. Поставим воображаемый бильярдный шарик в точку A и толкнем его в сторону точки B. Достигнув третьей, последней точки на кривой, шар отскочит либо прямо вверх (если он находится ниже оси x), либо прямо вниз (если он выше оси x) — на другую сторону кривой.

Мы можем соединить любые две точки на кривой и получить новую — например, соединив A и B, мы получили С.

А еще мы можем связывать эти «ходы», чтобы раз за разом соединять изначальную точку с получившимся результатом. Так, соединив точку A с самой собой, мы получим точку B; из исходной точки A и получившейся B выйдет C; А и С, в свою очередь, дадут D — и так далее.

Оказывается, если мы имеем две точки — изначальную, «помноженную» на себя n раз, и конечную — выяснить, чему равно n, довольно сложно. Чтобы развить метафору со странным бильярдом, представь себе человека, который сколько-то времени играет в такой бильярд — сам с самой и в закрытой комнате. Ему будет довольно просто толкать шарик снова и снова по описанным выше правилам. Но если кто-нибудь войдет в эту комнату и увидит, где остановился шарик, то, даже зная правила игры и изначальную точку, определить количество ударов о бортики он все равно не сможет — пока не повторит все ходы от стартовой точки до финальной. «Легко туда, трудно обратно» — это, как помнишь, основа для хорошей TDF.

Все страньше и страньше

Упрощенная кривая из предыдущего раздела прекрасно выглядит и объясняет общую концепцию эллиптических кривых, но не показывает, как выглядят эллиптические кривые в криптографии.

Здесь, как и в RSA, нам приходится ограничивать себя числами в фиксированном диапазоне. Более того, нас в этом диапазоне интересуют целые числа — а кривая состоит не только из них. При решении уравнения эллиптической кривой (y² = x³ + ax + b) мы используем тот же самый трюк с «докручиванием» чисел, превышающих максимум. Если за максимум взять простое число, такая эллиптическая кривая называется простой — и обладает превосходными криптографическими свойствами.

Вот пример кривой (y² = x³ − x + 1), построенной для всех значений.

А вот та же кривая, но построенная только для целых значений с максимумом 97.

Совсем не похоже на кривую в традиционном понимании — но это она. Выглядит так, как будто ставшую вдруг невидимой кривую прикололи кнопками в точках, где она выдает целые значения. И заметь, горизонтальная симметрия сохранилась.

На самом деле мы все еще можем играть на этой кривой в бильярд и соединять точки. И любая прямая по-прежнему может собрать на себе не более трех точек. Вычислить эти точки довольно легко. Представь себе, что линия, соединяющая две точки, — это нитка, которая обматывается вокруг кривой, пока не попадет на третью. Это как если бы в нашем странном бильярде шар, ударившись о бортик (максимум), волшебным образом перемещался на противоположную сторону стола и продолжал свое движение до тех пор, пока не ударится о точку, — как в игре «Астероиды».

С помощью такого представления кривой уже реально зашифровывать сообщения. Можно представить исходное число сообщения как x, получить из уравнения y — и, соответственно, точку на кривой. На практике все чуть сложнее, но общая идея такова.

Для слова FLARE получим точки с координатами (70,6), (76,48), -, (82,6), (69,22).

(На этой кривой нет точки при x = 65, но в реальном мире есть способы обойти эту проблему.)

Эллиптическую криптосистему определяют: взятое за максимум простое число, уравнение кривой и открытая (стартовая) точка на кривой. Секретным ключом будет число priv, а открытым ключом — стартовая точка, соединенная сама с собой priv раз. Вычисление секретного ключа по открытому в такой криптосистеме называется функцией дискретного логарифма эллиптической кривой. Кажется, это и есть та TDF, которую мы искали.

Что все это значит?

Вычислить дискретный логарифм эллиптической кривой трудно — на чем и строится эллиптическая криптография. Спустя несколько десятилетий математики так и не нашли алгоритм, который решал бы эту проблему лучше простого перебора. Другими словами, в отличие от факторизации с ее понятными математическими основаниями, у этой проблемы, кажется, нет короткого решения, которое сократило бы разрыв в TDF. При работе с числами одной величины решить дискретный логарифм эллиптической кривой гораздо труднее, чем разложить число на множители. А значит, эллиптические криптосистемы крепче RSA и протокола Диффи — Хеллмана.

Чтобы иллюстрировать, насколько крепче, Арьен Ленстра несколько лет назад представил концепцию «Универсальной безопасности» (PDF). Суть в том, чтобы вычислить, сколько энергии тратится на взлом криптографического алгоритма, и сравнить с тем, сколько воды можно вскипятить той же энергией. Эдакий криптографический углеродный след. По его расчетам, на взлом 228-битного RSA-ключа требуется меньше энергии, чем на кипячение одной чайной ложки воды. Для сравнения: энергией, потраченной на взлом 228-битного ECC-ключа, можно вскипятить всю воду на планете. Чтобы добиться того же уровня безопасности c RSA, нужен ключ в 2380 бит.

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

Эллиптические кривые в действии

Эллиптические кривые медленно запрягали, но теперь стремительно набирают популярность — и очень быстро распространяются. Эллиптическую криптографию сейчас можно найти в самых разных приложениях: правительство США использует ее для защиты внутренних коммуникаций, проект Tor — чтобы обеспечить анонимность; этот же механизм работает, если нужно подтвердить право собственности на биткойны, отправить сообщение в iMessage и зашифровать данные DNS с помощью DNSCurve; также это предпочтительный метод аутентификации для безопасного серфа через SSL/TLS. Cloudflare пользуется ECC, чтобы обеспечить совершенную прямую секретность (PFS), которая необходима, чтобы сохранить приватность в сети.

Криптографические алгоритмы первого поколения вроде RSA и Диффи — Хеллмана все еще подойдут для большинства сфер, но ECC быстро набирает популярность — как решение для конфиденциальности и безопасности в интернете.

Если ты откроешь HTTPS-версию блога Cloudflare через свежий Chrome или Firefox, то твой браузер будет использовать эллиптическую криптографию. Можешь убедиться в этом сам — нажми на замок слева от адресной строки и выбери вкладку «Соединение».

На этой картинке нас в первую очередь интересует текст ECDHE_RSA. ECDHE расшифровывается как Elliptic Curve Diffie Hellman Ephemeral — это механизм обмена ключами, построенный на эллиптических кривых. В Cloudflare он обеспечивает совершенную прямую секретность на SSL. А с помощью RSA здесь идентифицируется сервер.

Мы используем RSA, потому что SSL-сертификат Cloudflare привязан к паре RSA-ключей. Но современные браузеры поддерживают и сертификаты на эллиптических кривых. Если бы Cloudflare использовал такой сертификат, его обозначение выглядело бы ECDHE_ECDSA. Идентификация сервера в таком случае выполнялась бы с помощью эллиптического алгоритма электронной подписи (Elliptic Curve Digital Signature Algorithm).

Уравнение эллиптической кривой для ECDHE, которую использует Cloudflare (и Google.com, кстати):

max: 115792089210356248762697446949407573530086143415290314195533631308867097853951  
curve: y² = x³ + ax + b  
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948  
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

Уровень производительности ECDSA по сравнению с RSA впечатляет. Даже со старыми версиями OpenSSL, которые не заточены под код эллиптических кривых, ECDSA-подпись с 256-битным ключом более чем в 20 раз быстрее RSA-подписи с 2048-битным ключом.

На MacBook Pro с OpenSSL 0.9.8 тест скорости выдает:

Doing 256 bit sign ecdsa's for 10s: 42874 256 bit ECDSA signs in 9.99s
Doing 2048 bit private rsa's for 10s: 1864 2048 bit private RSA's in 9.99s

То есть с ECDSA за то же время можно получить в 23 раза больше подписей, чем с RSA.

Cloudflare постоянно ищет способы поднять производительность SSL. Например, мы начали использовать оптимизированную версию ECC, которая увеличивает скорость ECDHE более чем в два раза. Эллиптическая криптография экономит время, мощность и вычислительные ресурсы — как для сервера, так и для браузера — и помогает нам сделать сеть одновременно быстрее и безопаснее.

Оборотная сторона

Но не все так радужно в мире эллиптических кривых — есть и тонкие места, которые мешают им полностью охватить отрасль.

Одно из них — недавно мелькавший в новостях Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator). Это генератор случайных чисел, стандартизированный Национальным институтом стандартов и технологий США (NIST), который продвигало их же Агентство национальной безопасности.

Dual_EC_DRBG генерирует псевдослучайные числа, используя принцип эллиптических кривых. Его алгоритм берет точки на кривой и многократно выполняет операцию по соединению этих точек — чтобы получить новые. После его публикации сообщалось (PDF), что в генератор, возможно, встроен бэкдор — а значит, последовательность полученных чисел можно полностью предсказать, если есть правильный секретный ключ.

Недавно компания RSA отозвала несколько своих продуктов, потому что Dual_EC_DRBG был установлен как дефолтный генератор псевдослучайных чисел в их линейке продуктов безопасности. Был генератор случайных чисел написан с бэкдором или нет, силу самой технологии эллиптических кривых это не отменяет — но зато поднимает вопрос о стандартизации. Как мы уже писали ранее, нужно следить, чтобы ваша система использовала адекватно случайные числа.

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

Есть, конечно, кое-какой прогресс в разработке кривых с эффективной арифметикой за пределами NIST, включая кривую 25519, созданную Дэниелом Бернштейном (djb), и недавно вычисленные кривые Пауло Баретто со товарищи, — но до их широкого распространения еще жить и жить. Пока эти «нетрадиционные» кривые не встроят в браузеры, их нельзя будет использовать для обеспечения безопасности передаваемых по сети данных.

Другое тонкое место ECC связано с патентами. Более 130 патентов, касающихся конкретного использования эллиптических кривых, принадлежат BlackBerry — ведь в 2009 году они приобрели Certicom. Многие из тех патентов лицензированы для эксклюзивного использования частными компаниями — и даже АНБ. Некоторые разработчики из-за этого взяли паузу — чтобы оценить, не нарушает ли их работа с ECC эти патенты. В 2007 году Certicom подала иск против Sony — из-за нескольких видов использования эллиптических кривых, — однако в 2009 году иск был отклонен. Сейчас уже есть куча разных реализаций криптографии с эллиптическими кривыми, которые, как считается, не нарушают эти патенты — а потому широко используются.

У цифровой подписи ECDSA есть серьезный недостаток по сравнению с RSA: она требует хорошего источника энтропии. Без достаточной случайности чисел секретный ключ могут раскрыть. В 2013 году слабый генератор случайных чисел в Android позволил хакерам найти секретный ключ ECDSA и взломать несколько биткойн-кошельков. У Sony PlayStation была похожая уязвимость. Для электронных подписей нужен хороший генератор случайных чисел. Dual_EC_DRBG уж точно не подойдет.

Заглядывая вперед

Впрочем, недостатки есть у всякой технологии, а вот достоинства ECC по сравнению с традиционной RSA неоспоримы — и уже широко признаны. Многие эксперты беспокоятся, что математические алгоритмы RSA и Диффи — Хеллмана могут быть успешно взломаны в течение ближайших лет — и тогда ECC останется единственной разумной альтернативой.

ПОДПИСАТЬСЯ - USBKiller