Кривая дорожка к прямому доверию

Зачем электронной подписи нужна эллиптическая кривая

В нашей мини-игре шайба летит по прямой, отскакивает от бортов и снова летит по прямой. Всё честно и предсказуемо: зная направление и скорость, можно примерно понять, где она окажется дальше.

Но электронная подпись защищена не прямой, а эллиптической кривой.

Звучит так, будто где-то внутри токена спрятан маленький овал, по которому бегают числа. На деле всё интереснее: эллиптическая кривая — это математическая конструкция, на точках которой можно выполнять специальные операции.

Именно эти операции позволяют:

• создать открытый ключ из закрытого;

• легко проверить математическую связь между ключами;

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

Кривая здесь нужна не ради красоты. Она создаёт математическую «местность», где идти вперёд легко, а вернуться по следам чрезвычайно трудно.

Зачем вообще нужна односторонняя задача

В электронной подписи есть два ключа:

• закрытый ключ хранится только у владельца и используется при подписании;

• открытый ключ можно передавать всем, кому нужно проверять подпись.

Между ними должна существовать математическая связь.

Из закрытого ключа нужно легко получить открытый:

Закрытый ключ
      ↓
Математическая операция
      ↓
Открытый ключ

Но в обратную сторону схема должна быть практически невычислимой:

Закрытый ключ  ─────────→  Открытый ключ
                    легко


Закрытый ключ  ← - - - -  Открытый ключ
         вычислительно неосуществимо

Иначе любой человек скачал бы открытый ключ из сертификата, восстановил закрытый и начал подписывать документы от имени владельца.

Нужна операция с выраженной асимметрией:

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

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

Название длинное. Задача ещё длиннее.

Эллиптическая, но не эллипс. Математики умеют давать названия

Первое, что обычно удивляет:

Все знают, как выглядит эллипс, но стоит напомнить, что одна из распространённых форм записи эллиптической кривой выглядит так (у математиков):

y² = x³ + a·x + b например: y² = x³ - x + 1

Если нарисовать такую кривую над обычными действительными числами, можно получить линию с плавными изгибами:

Конкретная форма зависит от коэффициентов a и b.

Название появилось исторически: такие уравнения связаны с задачами вычисления длины дуги эллипса и эллиптическими интегралами. Сам график при этом не обязан быть похожим на эллипс.

Так что претензии к названию можно отправить математикам прошлых веков. Современная электронная подпись просто работает с тем, что досталось.

Кривая должна быть без особых «заломов»

Не любое уравнение вида:

y² = x³ + a·x + b

подходит для криптографии.

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

Для кривой над полем с характеристикой, отличной от 2 и 3, это условие обычно записывают так:

4a³ + 27b² ≠ 0

В конечном поле сравнение выполняется по модулю используемого простого числа.

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

Главное понять идею:

В реальной криптографии гладкой линии нет

Красивый график с плавными ветвями полезен для объяснения, но электронная подпись работает не прямо на нём.

В криптографии кривую рассматривают над конечным полем.

Это означает, что координаты точек берутся не из бесконечного множества обычных чисел, а из ограниченного набора значений.

Можно представить арифметику по модулю как часы.

На обычной числовой прямой:

10 + 5 = 15

На часах с 12 делениями:

10 + 5 = 3

Потому что после 12 счёт начинается заново.

В криптографии используется похожая идея, только модуль огромен.

Например, в небольшом учебном мире по модулю 17 доступны значения:

0, 1, 2, 3, ... 16

После 16 снова идёт 0.

Если подставлять такие значения в уравнение кривой и оставлять только подходящие пары координат, получится не непрерывная линия, а набор отдельных точек:

·       ·       ·

    ·       ·

·           ·       ·

        ·

  ·             ·

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

И здесь слово «дискретный» пригодится ещё раз.

Точки, точки, запятая — вышла криптография кривая

Точки эллиптической кривой можно складывать. Это звучит странно. Как сложить две точки? Для обычного графика над действительными числами используется красивое геометрическое объяснение. Пусть есть две точки P и Q, проводим через них прямую, которая пересекает кривую ещё в одной точке. Затем отражаем эту точку относительно горизонтальной оси (ну замутили, без поллитра не разберешь!). Получаем результат:

P + Q = R

Схематично:

Q ●
           / \
          /   \
---------/-----\---------
        /       ●
     P ●        │
                │ отражение
                ▼
                ● R

Реальный рисунок зависит от формы кривой, но правило можно запомнить так:

1. провести прямую;

2. найти третье пересечение;

3. отразить его;

4. получить сумму точек.

Если нужно сложить точку саму с собой:

P + P = 2P

вместо прямой через две разные точки проводят касательную к кривой в точке P.

Получается операция удвоения точки.

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

Геометрия помогает понять идею, а компьютер выполняет вычисления.

Ещё одна точка, которой как будто нет

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

Её часто обозначают:

O

Она играет роль нуля.

Для обычных чисел:

5 + 0 = 5

Для точек:

P + O = P

Кроме того, у каждой точки есть противоположная.

Если:

P = (x, y)

то противоположная точка имеет тот же x, но противоположную координату y с учётом арифметики поля.

Их сумма даёт точку на бесконечности:

P + (−P) = O

В повседневной работе с электронной подписью пользователь эту точку не видит. Но без неё правила сложения были бы неполными.

Даже в криптографии иногда нужен свой ноль. Просто он живёт очень далеко.

От сложения к умножению

Если точку можно складывать, её можно несколько раз сложить саму с собой.

Например:

2G = G + G

3G = G + G + G

4G = G + G + G + G

Вместо длинной записи используют умножение точки на число:

Q = d × G

Здесь:

• G — заранее выбранная базовая точка;

• d — большое целое число;

• Q — результат умножения.

Важно: это не обычное умножение координат.

Запись:

d × G

означает многократное сложение точки G по правилам эллиптической кривой.

Например:

7 × G =
G + G + G + G + G + G + G

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

Используются быстрые алгоритмы, основанные на удвоениях и сложениях.

Например, вместо восьми сложений:

8G = G + G + G + G + G + G + G + G

можно выполнить:

G
↓ удвоение
2G
↓ удвоение
4G
↓ удвоение
8G

Количество операций растёт намного медленнее самого числа d.

Поэтому вычислить:

Q = d × G

можно быстро даже при огромном d.

Туда легко, обратно — билет не продаётся

Теперь мы подошли к главной идее.

Пусть известны:

G — базовая точка

d — большое секретное число

Вычисляем:

Q = d × G

Получаем точку Q.

Если известны d и G, найти Q сравнительно легко.

Но теперь представим обратную задачу.

Известны:

G

Q

Нужно найти число:

d

то есть определить, сколько условных «шагов» от G привело к Q.

Эта задача называется задачей дискретного логарифмирования на эллиптической кривой.

Упрощённо:

d + G
  ↓
Q

Вперёд — быстро


G + Q
  ↓
d

Назад — вычислительно чрезвычайно трудно

Слово «логарифмирование» здесь не означает, что можно открыть калькулятор и нажать кнопку log.

Это отдельная задача в конечной группе точек.

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

Именно на этой асимметрии строится ключевая пара.

Где здесь закрытый и открытый ключи

Теперь формула становится понятнее:

Q = d × G

В электронной подписи:

• d — закрытый ключ;

• G — известная базовая точка;

• Q — открытый ключ.

Схема выглядит так:

Случайное секретное число d
            ↓
        d × G
            ↓
Открытая точка Q

Закрытый ключ:

d

нужно хранить в секрете.

Открытый ключ:

Q = (x, y)

можно включить в сертификат и передавать проверяющим.

Публикация Q не должна раскрывать d.

Именно поэтому открытый ключ действительно может быть открытым.

Почему нельзя просто использовать обычную прямую

Вернёмся к шайбе.

На обычной прямой движение слишком предсказуемо.

Если известно:

Начальная точка

Направление

Размер шага

Конечная точка

обычно легко посчитать количество шагов.

Например:

Старт: 5

Каждый шаг: +3

Финиш: 35

Количество шагов находится обычным уравнением:

5 + 3d = 35

d = 10

Секрет спрятать не получилось.

Эллиптическая кривая над конечным полем создаёт намного более сложную структуру.

Точки «перепрыгивают» по конечному множеству по специальным правилам. У результата нет простого расстояния вдоль линии, которое можно измерить линейкой.

Вперёд вычисления ускоряются благодаря известному числу d.

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

Так что прямая хороша для шайбы.

Для закрытого ключа лучше немного покривляться.

Почему маленькие примеры нельзя считать защищёнными

Для объяснения часто используют маленькое поле:

по модулю 17

или:

по модулю 23

На таком примере можно вручную выписать все точки и перебрать возможные значения.

Это учебная модель.

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

Нельзя сделать вывод:

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

Принцип похож, масштаб — совершенно другой.

Почему важен не только размер ключа

Иногда безопасность пытаются оценить одной цифрой:

Но длина сама по себе не описывает всю стойкость.

Важны:

• конкретная математическая задача;

• параметры поля;

• форма кривой;

• порядок группы или подгруппы;

• базовая точка;

• отсутствие известных слабостей;

• корректная реализация;

• качество генерации закрытого ключа.

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

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

Например, фраза:

неверна без указания алгоритмов.

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

Как кривая участвует в электронной подписи

При создании подписи используется не только постоянный закрытый ключ d, но и новое одноразовое число k.

Сначала вычисляется точка:

C = k × G

Одна из координат этой точки участвует в формировании первой части подписи.

Затем вместе используются:

• хеш документа;

• закрытый ключ d;

• одноразовое число k;

• параметры группы точек.

В результате получается электронная подпись, состоящая из двух чисел:

r и s

При проверке программа использует:

• документ;

• его хеш;

• подпись r, s;

• открытый ключ Q;

• параметры эллиптической кривой.

Проверяющая сторона не знает ни закрытый ключ d, ни одноразовое число k.

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

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

Полный процесс создания и проверки мы разберём в следующей статье.

Можно ли увидеть эллиптическую кривую внутри подписи

Нет.

В готовом файле подписи вы не увидите нарисованный график.

Кривая проявляется через параметры и результаты вычислений:

• координаты открытого ключа;

• идентификаторы набора параметров;

• числа r и s;

• криптографические операции при создании и проверке.

Сама картинка нужна только человеку для понимания.

Компьютеру достаточно чисел.

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

ГОСТ Р 34.10-2012 и эллиптические кривые

ГОСТ Р 34.10-2012 описывает процессы формирования и проверки электронной подписи, основанные на операциях в группе точек эллиптической кривой над конечным простым полем.

Стойкость схемы связана с двумя основными компонентами:

• сложностью задачи дискретного логарифмирования в группе точек эллиптической кривой;

• стойкостью используемой криптографической хеш-функции.

В стандарте предусмотрены варианты с параметрами порядка 256 и 512 бит.

В реальных системах используется не произвольная кривая, которую разработчик нарисовал утром на салфетке, а определённые наборы параметров.

Выбор параметров — отдельная сложная криптографическая задача.

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

Что кривая защищает, а что — нет

Эллиптическая кривая защищает математическую связь между закрытым и открытым ключами.

Она помогает сделать практически неосуществимым восстановление закрытого ключа по открытому.

Но кривая не защищает от всех угроз.

Она не поможет, если:

• закрытый ключ скопировали;

• злоумышленник получил токен и PIN-код;

• компьютер подписанта заражён;

• пользователь сам подтвердил подписание подменённого документа;

• криптографическая реализация содержит критическую ошибку;

• используется слабый генератор случайных чисел.

Надёжность электронной подписи складывается из нескольких элементов:

Стойкая математическая задача
              +
Качественная случайность
              +
Надёжная хеш-функция
              +
Корректная реализация
              +
Защищённое хранение ключа
              +
Безопасная работа пользователя

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

Главное

Эллиптическая кривая нужна электронной подписи как математическая среда, в которой можно построить асимметричную ключевую пару.

Закрытый ключ — большое случайное число:

d

Открытый ключ — точка, полученная умножением базовой точки:

Q = d × G

Вычислить Q по известному d легко.

Восстановить d по известным G и Q при правильно выбранных параметрах считается вычислительно неосуществимым.

На этой разнице строится главное свойство:

Случайность создаёт секрет.

Хеш связывает подпись с документом.

Эллиптическая кривая превращает секрет в открытую проверяемую конструкцию.

Теперь все основные детали лежат на столе. Пора собрать механизм целиком и посмотреть, что именно происходит с момента нажатия кнопки «Подписать» до сообщения «Подпись действительна».

В следующей статье: «Как создаётся и проверяется электронная подпись: весь процесс по шагам».