Эллиптические кривые по ГОСТу

(Введение)

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

Что это за кривая?

Это множество точек (x, y), удовлетворяющих уравнению y? + axy + by = x? + cx? + dx + e. Откуда брать коэффициенты? — Вопрос важный, так как каждое поле (обычно ?, ?, ? или F?) порождает целую отдельную науку. Мы же начнем для наглядности с вещественного случая, а потом сосредоточимся на конечных полях.

Замечания:

1. Заменой переменных уравнение эллиптической кривой всегда можно привести к форме Вейерштрасса: y? = x? + Ax + B, если характеристика рассматриваемого поля не равна 2 или 3.

2. В вещественном случае на эллиптическую кривую накладывается условие гладкости, т. е. не должно быть самопересечений и особых точек, как, например, точка (0, 0) для полукубической параболы y? = x? (постройте график). Для гладкости достаточно того, чтобы число ? = 4A? + 27B?, называемое дискриминантом, не обнулялось. По знаку ? еще можно определить число компонент связности эллиптической кривой (одна либо две).

Введем операцию сложения точек на эллиптической кривой (это нам понадобится).

Как сложить точки P и Q, лежащие на кривой:

1. Проводим прямую через P и Q;

2. Эта прямая обязательно пересечет кривую в третьей точке, которую мы назовем R' (с вертикальными прямыми разберемся ниже);

3. R — результат отражения R' относительно оси X — назовем суммой точек P и Q.

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

Если же нужно сложить точку саму с собой, то проводим касательную к кривой в этой точке и переходим к шагам 2 и 3 (можно вспомнить, что при устремлении Q к P секущие стремятся к касательной в P). При многократном прибавлении точки самой к себе получаем своего рода умножение на натуральный скаляр: Q := kP := P + P + ... + P (k раз).

Все эти операции обладают важными свойствами: они коммутативны (P + Q = Q + P) и ассоциативны ((P + Q) + R = P + (Q + R)). Последнее свойство неочевидно и доказывается с некоторым усилием (сейчас доказывать теорему о 9 точках не буду). Всё это позволяет нам складывать точки в любом порядке и получать один и тот же результат.

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

Из бесконечного в конечное.

В реальной криптографии мы не работаем с бесконечными полями, а переходим в конечные — перенесем нашу кривую в поле F?, где p — очень большое простое число. Удобно представлять F? как множество остатков при делении на p.

Теперь в качестве коэффициентов и переменных уравнения y? = x? + Ax + B можно брать только числа от 0 до p-1, используя арифметику остатков.

После этого наш бесконечный график эллиптической кривой превращается в сетку, где все числа "заворачиваются" по модулю p. Например, если p = 23, то 24 переходит 1, а -1 — в 22.

На такой сетке кривая выглядят не как плавная линия, а как хаотично разбросанное конечное множество точек, расположенных симметрично относительно уровня p/2 (см. рис. 4). Именно в этом "хаосе" и кроется вся криптографическая мощь: операции сложения и умножения становятся непредсказуемыми для стороннего наблюдателя, что делает взлом невероятно сложным. Для нахождения количества точек кривой (т. е. порядок группы) используют алгоритм Шуфа, а теорема Хассе утверждает, что это число отличается от p не более чем на 1+2?p.

Зачем это всё?

Безопасность ECC (elliptic-curve cryptography) основана на проблеме дискретного логарифмирования на эллиптической кривой (ECDLP):

1. Прямая задача: зная точку P и число k (ваш секретный ключ), легко вычислить точку Q = kP (публичный ключ). Это делается быстро, если использовать ускоренное сложение (в силу ассоциативности), т. е. учитывать промежуточные результаты сложения.

2. Обратная задача: зная точки P и Q, найти число k (секретный ключ). Если параметры кривой достаточно большие, то для самых мощных компьютеров в мире эта задача занимает миллионы-миллиарды лет. Судите сами: если выбрать p порядка 10??? (такие обычно и используются), то для ?-алгоритма Полларда (со сложностью порядка ?(?p/2)) — лучшего алгоритма — задача становится невозможной.

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

ECC в действии.

Самый распространенный пример использования ECC — это обмен ключами Диффи-Хеллмана на эллиптических кривых (ECDH), который используется для установления защищенного соединения:

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

1. Алиса выбирает секретное целое число k? и сложением вычисляет публичную точку Q? = k?P;

2. Боб выбирает секретное целое число k? и вычисляет публичную точку Q? = k?P;

3. Алиса и Боб обмениваются точками Q? и Q?;

4. Алиса вычисляет секретный ключ: S = k?Q?;

5. Боб вычисляет секретный ключ: S' = k?Q?.

Благодаря ассоциативности сложения, оба получают одну и ту же точку S=S', которая становится их общим секретным ключом. При этом подслушивающий, видя только публичные точки Q? и Q?, не может вычислить секретные числа k? и k?.

Что там про ГОСТ?

В России криптография на эллиптических кривых закреплена в национальных стандартах. Например, ГОСТ Р 34.10-2012 описывает схему электронной цифровой подписи (ЭЦП) и предусматривает использование эллиптических кривых с двумя уровнями стойкости: 256 бит и 512 бит. Для каждого уровня определены наборы параметров, которые должны использоваться для обеспечения криптографической защиты. Все они являются публичными и стандартизироваными. Можно сказать, этот ГОСТ представляет собой брошюру об эллиптических кривых и их использовании в шифровании. Прикольно, правда? И самое главное — этот стандарт действительно находит применение.

Об этом и об использовании ECC в ЭЦП поговорим подробнее в следующий раз.

На сегодня всё.

Источник: vk.com

Комментарии: