No Image

Шифрование на эллиптических кривых

СОДЕРЖАНИЕ
0 просмотров
22 января 2020
Автор: Холодилов Сергей Александрович
Опубликовано: 08/08/2012
Исправлено: 10.12.2016
Версия текста: 1.1

Реализация ГОСТ Р 34.10 – 2001

Недавно мне случайно понадобилось разобраться в том, как работает ECDSA (Elliptic Curve Digital Signature Algorithm; цифровая подпись на эллиптических кривых) вообще и его реализация в OpenSSL в частности. В процессе написалась эта статья.

ПРИМЕЧАНИЕ

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

Были использованы следующие источники (помимо википедии):

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

ПРИМЕЧАНИЕ

Наш ГОСТ Р 34.10 – 2001 достаточно близок, об отличиях я напишу.

Пользуясь случаем, посылаю луч распознавания текста милым людям, выкладывающим pdf с ГОСТом в виде набора картинок. Особенно это актуально для приложения Б, содержащего контрольный пример с большим количеством 256-битных чисел. К счастью, вот здесь есть несколько неуклюжая, но всё же текстовая версия. Огромное спасибо сайту http://www.bestpravo.ru.

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

Схема Эль-Гамаля

Сначала нужно поговорить про схему Эль-Гамаля, так как с кривыми будет то же самое, только сложнее. Почему-то мне раза три в разных местах рассказывали про RSA, а про Эль-Гамаля ни разу, и боюсь, что не только мне.

И то и другое – системы шифрования с открытыми ключами. RSA основана на сложности задачи разложения числа на множители, а схема Эль-Гамаля – на задаче дискретного логарифма. Оказывается, зная (p, g, y), очень сложно найти такой x, что

Исходные данные

    p – большое простое число;

g – такое число, что g

mod p != 1 для любых 0 p-1

mod p == 1 для любых q, вопрос в том, чтобы нигде раньше 1 не встретилась.

ПРИМЕЧАНИЕ

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

d – случайное число, меньшее p-1

Открытый ключ – это тройка (p, g, y), секретный ключ –

Шифрование

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

  • m – сообщение – число меньше p
  • k – случайное число меньше p-1. Его знает только шифрующий, никому не отдаёт и уничтожает сразу после использования.

Пара (a, b) – это зашифрованное сообщение. Расшифровка:

почему это работает:

Подпись

Постановка задачи: подтвердить, что сообщение отправлено владельцем секретного ключа.

  • m = hash(сообщение) mod p, где hash – хеш-функция.
  • k – случайное число меньше p-1, взаимно простое с p-1. Его знает только подписывающий, никому не отдаёт и уничтожает сразу после использования.
ПРИМЕЧАНИЕ

Искать s, конечно, расширенным алгоритмом Евклида. Взаимная простота k и p-1 нужна для гарантии существования такого s.

пара (r, s) – это подпись сообщения. Проверка подписи:

Почему это работает:

Обобщим

Это всё мило, но несколько прямолинейно. Добавим немного алгебры.

Для начала нужно отовсюду убрать "mod p" и сказать вместо этого, что дело происходит в конечном поле. От этого вообще ничего не изменится.

Потом можно заметить, что нам тут не нужно поле, достаточно циклической группы порядка q и любой биекции из неё в <1, 2, … q>. (биекция понадобится, чтобы преобразовать сообщение m [число] в некоторый элемент группы и обратно, и ещё в паре мест). Назовём биекцию буквой f и попробуем кратко воспроизвести всё написанное выше.

  • q – порядок группы;
  • g – образующий элемент группы;
  • d – число меньше q, показатель степени;
  • y – элемент группы, g d ;
  • m – сообщение – число меньше q;
  • k – случайное число (для подписи – взаимно простое с q, для шифрования просто меньше q).

Итого, m = f(a (q – d) b), как ожидалось.

Работает. Теперь можно двигаться дальше.

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

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

  • p – простое, F = <0, 1, … p-1>– конечное поле характеристики p, отождествляем его элементы с числами.
  • a, b принадлежат F

Множество E(F) = <(x,y) из F 2 | y 2 = x 3 + ax + b>+ – эллиптическая кривая. Т.е. множество пар, компоненты которых удовлетворяют приведённому уравнению над F, и ещё один элемент – O. Элементы кривой называются точками, O – "точка на бесконечности".

Поскольку пары должны удовлетворять уравнению, понятно, что:

  • если есть точка (x, y), есть и точка (x, -y) (y – это элемент поля F, а там, конечно, определена операция "-");
  • других точек с таким же x нет.

На точках E(F) вводится операция сложения:

  • O + O = O
  • (x, y) + O = O + (x, y) = (x, y)
  • (x, y) + (x, -y) = O
  • (x, y) + (x, y) = . не важно .
  • (x 1 , y 1 ) + (x 2 , y 2 ) = . не важно, но коммутативно, хотя это вроде тоже не важно .

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

  • G = (x G , y G ) – выбранная точка E(F);
  • n – простое число, порядок G в группе E(F);
  • h – |E(F)| / n – "кофактор" G, небольшое число, рекомендуют не больше чем 4.

Параметры (p, a, b, G, n, h) вместе задают конкретную эллиптическую кривую с точки зрения криптографии.

  • d – случайное целое число из <1, 2, … n-1>– секретный ключ
  • Q = dG – точка кривой – открытый ключ

Подпись

Несложно заметить, что у нас получилось не совсем то, что нужно.

Во-первых, G – не образующая.

Во-вторых, у нас нет биекции из E(F) в <1, 2, … |E(F)|>.

Но для подписи хватит и того, что есть. Итак:

  • m = hash(сообщение) mod n, где hash – хеш-функция.
  • k – случайное число, взаимно простое с n

пара (R, s) — подпись. Проверяем:

Ура, товарищи! Вот она какая, криптография на эллиптических кривых.

ПРИМЕЧАНИЕ

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

Второй тип кривых

Описанные выше кривые, задающиеся шестёркой (p, a, b, G, n, h), называются кривыми над простым полем, они же GFp-кривые.

Во втором случае кривая задается семёркой (m, f(x), a, b, G, n, h). Здесь поле задают два первых параметра, уравнение – третий и четвёртый (хотя это немного другое уравнение и немного другие a и b), а три последних параметра точно те же, что и в первом случае. И точки тоже просто пары элементов поля. Это кривые над полем характеристики 2 m , они же GF2m-кривые.

Читайте также:  Что характерно для мониторных наушников

У GF2m-кривых отличаются правила сложения точек, но в результате всё равно имеем абелеву группу и ту же самую идею.

ПРИМЕЧАНИЕ

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

OpenSSL

Текст чуть меньше чем наполовину скопирован из заголовочных файлов OpenSSL, но важно же расположить их в нужной последовательности и верно поставить акценты! 🙂

Выбор кривой

К счастью, нам не нужно выбирать параметры кривой, искать точку G, определять n и h. Это давно сделано за нас людьми, которые понимают в этом гораздо больше (кстати, параноику на заметку). Есть стандарты с рекомендациями и вариантами, из них можно выбрать, а в конкретных системах нужно использовать конкретные кривые, которые полюбились авторам.

Желающие могут, конечно, придумать свою кривую (и для этого тоже есть развернутые рекомендации), но проще вызывать кривые как демонов, по имени.

Примеры имён можно увидеть в файле include/openssl/obj_mac.h:

ПРИМЕЧАНИЕ

Для файлов, присутствующих в стандартной установке, даётся стандартный путь, для файлов из исходников – путь в исходниках. Ссылки даю на последнюю (на данный момент) версию из CVS:

Кривые с названиями такого вида взяты из документа SEC 2: Recommended Elliptic Curve Domain Parameters.

Число в середине означает длину порядка группы в битах, это же оценка сложности вскрытия. Подразумевается, что злоумышленнику понадобится около 2 t/2 операций (есть более точные оценки, но приблизительно так).

sec p . – GFp-кривая

sec t . – GF2m-кривая (возможно, "t" от слова two)

Суффикс маркирует разное происхождение рекомендуемых параметров кривой: "k" в честь Neal Koblitz (их как-то по-умному считают), "r" от слова random (один раз запустили генератор, записали на бумажку и теперь рекомендуют использовать). И есть ещё какие-то типы кривых для X9.62, у них другие имена, но этого я уже совсем не знаю. Соответствующие именам параметры можно посмотреть в файле openssl/crypto/ec/ec_curve.c.

ПРИМЕЧАНИЕ

ГОСТ Р 34.10-2001 описывает только GFp-кривые с 256-битным порядком группы. Конкретные параметры кривой там не приводятся, только ограничения на них. Насколько я понял, кривая secp256k1 не подойдёт (так как у неё a == 0, это нарушает ограничение на инвариант кривой), а secp256r1 использовать можно.

Базовые функции

Кривой соответствует тип данных EC_GROUP*, точке EC_POINT* (это "непрозрачные" указатели, если не залезать в исходники, нам не известно, на что они указывают; в этот раз в исходники не полезем). Вот несколько функций из файла include/openssl/ec.h (там ещё много, и документированы они только там, я постарался выбрать наиболее полезные).

Создать новую точку, освободить, вычисление выражения nG + m 1 P 1 + m 2 P 2 + .

Последнюю функцию можно вызывать так:

Получается просто nG, как раз то, что нужно для получения открытого ключа из секретного. Точку r нужно инициализировать с помощью EC_POINT_new до вызова EC_POINTs_mul.

Ключи

Более высокий уровень абстракции – ключ. Открытый и секретный ключи на уровне интерфейса не отличают, есть всего один EC_KEY*, в котором можно установить отдельно открытую и секретную части. А можно сгенерировать новый полноценный.

Из того же файла include/openssl/ec.h (я убрал стандартные комментарии, т.к. там всё тривиально, и добавил свои на всякий случай и потому что люблю зелёный цвет):

Можно порадоваться, что я не наврал: открытый ключ – это действительно точка, а секретный – это действительно число. Вот она, польза теории.

Сериализация

Точка – это пара элементов поля (можно считать пара чисел), удовлетворяющих уравнению кривой. Если подставить в уравнение конкретный x, останется квадратное уравнение относительно y (для GFp-кривых просто y 2 = c) и, если уметь решать такие уравнения над конечным полем, получаем всего два подходящих y. Значит, чтобы идентифицировать точку, достаточно указать x и как-то обозначить, какой из двух y выбрать. Такое представление точки называется компактным (compressed). Развёрнутое представление – это просто x и y. В бинарном виде первый байт указывает вид представления и, если оно компактное, то ещё и указывает, который y выбрать.

ПРИМЕЧАНИЕ

Есть ещё третий вариант, гибридный он сочетает в себе недостатки обоих: первый байт как у компактного, но передаются и x, и у. Не знаю, кому это понадобилось.

ПРЕДУПРЕЖДЕНИЕ

На моей домашней убунту 10.4 попытки использовать компактные представления для точек GF2m-кривых заканчиваются с ошибкой "called a function that was disabled at compile-time", версия openssl 0.9.8, старенькая, но именно её предлагает стандартный репозиторий. Для GFp-кривых всё работает нормально, остальные функции для GF2m тоже работают нормально, то есть их поддержка не отключена полностью.

На убунте 11.10 с openssl 1.0.0e работает всё, что я проверял.

Кроме того, зная тип кривой, точки можно разными способами разобрать/собрать по координатам функциями типа EC_POINT_set_affine_coordinates_GFp и т.п. Координаты же это просто BIGNUM, для них есть много вариантов.

Для ключей идеологически правильно (но не обязательно) использовать высокоуровневые функции (файл всё тот же):

Но просто так их использовать не получится. За ними стоят следующие нетривиальные мысли:

  • d2i_ECPrivateKey / i2d_ECPrivateKey кодируют ключ в виде ASN.1 DER, это такой стандарт, позволяющий описывать иерархические бинарные структуры, типа xml или json, но бинарный. Соответственно, это нечто большее, чем "сохранить/прочитать одно число" (а секретный ключ это именно одно длинное число).
  • И действительно, в зависимости от установленных флагов ключа (см. ниже), i2d_ECPrivateKey может кроме самого секретного ключа сохранить параметры кривой и открытый ключ.
  • При чтении ключа, сохранённого с параметрами, функция d2i_ECPrivateKey автоматически проассоциирует ключ с правильной кривой. Если параметры не сохранены, кривую нужно знать заранее и передавать функции уже инициализированный ключ.
  • Если out == NULL, функции действительно возвращают необходимый размер буфера. А вот если out != NULL, а *out == NULL, они сами выделяют буфер вызовом OPENSSL_malloc. Соответственно, потом его следует освободить OPENSSL_free.
  • i2o_ECPublicKey и i2d_ECPrivateKey не возвращают 1 при успехе, это неправда. Они всегда возвращают 0 или размер буфера.
  • Крайне неочевидное поведение с буферами. Вы заметили, что все функции принимают буферы в виде ** ? Как in, так и out. Это потому что они модифицируют * первого уровня: прибавляют к нему размер прочитанного/записанного. Видимо, какой-то отраслевой стандарт с идеей типа "выделить один большой буфер и залить туда кучу структур, и каждая автоматически передвигает указатель, чтобы следующая начиналась с нужного места". А потом так же читать. Я очень удивился, когда увидел, весьма спорное решение, на мой взгляд.
  • Функции i2o_ECPublicKey / o2i_ECPublicKey только притворяются умными, на самом деле это просто обёртка над EP_POINT_pont2oct / EP_POINT_oct2pont (выделяющая буферы и портящая указатели). Никаких параметров кривой там нет, соответственно, при чтении публичного ключа кривую ему нужно установить заранее.
Читайте также:  Собираем системный блок для игр

А вот обещанные флаги:

По умолчанию они сброшены, соответственно, по умолчанию все сохраняется.

Подпись своими руками

Внезапно, ещё немного математики 🙂 В примечании в разделе "Теория" я писал, что, на самом деле, подпись вычисляется не совсем так. Пора узнать, как это происходит. Напомню обозначения:

  • G – точка-генератор кривой;
  • n – порядок генератора;
  • d – секретный ключ;
  • Q = dG – открытый ключ;
  • m = hash(сообщение) mod n, hash — хеш-функция;
  • k – случайное число, взаимно простое с n.

иксации отличий сравним два варианта: описанный выше как продолжение схемы Эль-Гамаля и принятый стандартом ECDSA. Вычисление подписи;:

То есть изменился знак в условии для s, после чего равносильными преобразованиями оно приводится к виду из SEC1. Как это влияет на проверку:

Вычитать точки не сложнее чем складывать.

Но это ещё не всё.

Чтобы такую подпись проверить, нужно восстановить точку R по r. Есть два варианта: простой и умный.

Простой: мы вообще-то умеем восстанавливать точку по одной координате и одному биту от второй. В данном случае мы не знаем ничего про вторую координату (даже одного бита), и мы взяли x R mod n. Но, поскольку в требованиях к кривой указано, что кофактор h не больше 4, а количество точек кривой не сильно отличается от количества точек поля (есть такая теорема), вопрос решается перебором не более чем восьми вариантов. Если хоть один из них подойдёт, значит это она.

И в этом случае проверка заключается в том, что x-координата полученной точки R совпадает с переданным r по модулю n. Для вычисления обратного по модулю предназначена функция BN_mod_inverse.

Несложно реализовать это самостоятельно и сравнить с результатами ECDSA_do_sign, до которого мы, наконец, добрались (очевидно, что совпадения не будет, так как в создании подписи участвует случайное число k, но можно проверить их подпись вручную или наоборот).

ПРИМЕЧАНИЕ

ГОСТ Р 34.10-2001 описывает другой способ вычисления s и, соответственно, другой алгоритм проверки.

Вычисление: s = rd + km mod n

z 1 = sm -1 mod n

z 2 = -rm -1 mod n

z 1 G + z 2 Q = sm -1 G – rm -1 Q = (rd + km)m -1 G – rm -1 dG = (rdm -1 + k)G – rm -1 dG = kG = R

Собственно проверка, как и в «умном» способе из SEC1, заключается в сравнении первой координаты полученной точки с r.

Стандартный OpenSSL не содержит готовых функций, реализующих этот алгоритм, но его несложно написать самостоятельно на базе низкоуровневых функций. А можно даже не писать: вроде как вот здесь предлагают модифицированный OpenSSL с поддержкой ГОСТа, но я не смотрел их код и даже не скачивал. Зато написал свой, см. последний раздел статьи.

Подпись

Наконец, использование всего этого и другой заголовочный файл: include/openssl/ecdsa.h (DSA — digital signature algorithm). Тут есть два подхода. Во-первых, можно использовать ECDSA_SIG* (который, кстати, вполне прозрачный), это выглядит примерно так:

Или можно сразу получать бинарную строку с закодированной в DER подписью.

Результаты одинаковые: подпись, полученную от ECDSA_sign можно прочитать d2i_ECDSA_SIG, и наоборот, i2d_ECDSA_SIG даёт подпись, подходящую для проверки ECDSA_verify.

Самопроверяющаяся подпись

Немного особенной эллиптической магии. При некотором везении, имея только сообщение, подпись и параметры кривой, можно подобрать по этим данным публичный ключ, для которого всё будет сходиться. И даже несколько таких ключей! Это, конечно, так себе проверка 🙂 В этом случае собственно проверка переносится на следующий этап: полученный таким образом ключ каким-то образом сверяется с настоящим. Например, если известен хеш настоящего ключа, этого оказывается достаточно, так как можно сравнить хеши и быть полностью уверенным в результате.

Здесь уже даже SEC1 предлагает перебор по возможным R. После попадания в похожую на правду точку R предлагается следующее:

То есть при правильных исходных данных получатся правильные результаты. Но при любых исходных данных получатся какие-то результаты, т.е. какая-то точка Q. При этом, если точка R похожа на правду, то -R тоже похожа на правду (как минимум для GFp-кривых это очевидно), и её тоже можно подставить и получить в результате ключ Q’. А значит алгоритм, завершающийся после первого же правдоподобного результата, без проверки, будет ошибаться как минимум в половине случаев.

Где здесь нужно везение: число r -1 mod n должно существовать, для этого r должно быть взаимно просто с n. Этого можно добиться, выбирая случайные k, пока не попадётся нужное r.

ПРИМЕЧАНИЕ

Почему-то в SEC1 об этом моменте нет ни слова, странно.

Реализация ГОСТ Р 34.10 – 2001

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

Математические понятия

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

В общем случае уравнение эллиптической кривой Е имеет вид:

y 2 + axy + by = x 3 + cx 2 + dx + e

В качестве примера рассмотрим эллиптическую кривую Е , уравнение которой имеет вид:

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки

А (0, 0), В (1, -1), С (1, 0) и D (0, -1)

Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:

  • На плоскости существует бесконечно удаленная точка , в которой сходятся все вертикальные прямые.
  • Будем считать, что касательная к кривой пересекает точку касания два раза.
  • Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть 0 .

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

  • Точка 0 выступает в роли нулевого элемента . Так, 0 = -0 и для любой точки Р на эллиптической кривой Р + 0 = Р .
  • Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х – скажем, S = (x, y) и T = (x, -y) . Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р1 + Р2 + 0 = 0 и Р1 = -Р2 .
  • Чтобы сложить две точки P и Q (см. рисунок 11.2) с разными координатами х , следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой . Если прямая не является касательной к кривой в точках P или Q , то существует только одна такая точка, обозначим ее S . Согласно нашему предположению

Если прямая является касательной к кривой в какой-либо из точек P или Q , то в этом случае следует положить S = P или S = Q соответственно.

  • Чтобы удвоить точку Q , следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой . Тогда Q + Q = 2 x Q = -S .

Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р .

Читайте также:  Снос пароля windows 7

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

Такую кривую будем обозначать Ep (a,b) . При этом числа а и b должны быть меньше р и должны удовлетворять условию . Множество точек на эллиптической кривой вычисляется следующим образом.

  1. Для каждого такого значения х , что 0 , вычисляется x 3 + ax + b (mod p) .
  2. Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р . Если нет, то в Ep (a,b) нет точек с этим значением х . Если корень существует, имеется два значения y , соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0 ). Эти значения (x,y) и будут точками Ep (a,b) .

Множество точек Ep (a,b) обладает следующими свойствами:

  1. Р + 0 = Р
  2. Если Р = (x,y) , то Р + (x,-y) = 0 . Точка (x,-y) является отрицательным значением точки Р и обозначается -Р . Заметим, что (x,-y) лежит на эллиптической кривой и принадлежит Ep (a,b) .
  3. Если Р = (x1,y1) и Q = (x2,y2) , где , то P + Q = (x3,y3) определяется по следующим формулам:

Число есть угловой коэффициент секущей, проведенной через точки P = (x1, y1) и Q = (x2, y2) . При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления

Задача, которую должен решить в этом случае атакующий, есть своего рода задача "дискретного логарифмирования на эллиптической кривой" , и формулируется она следующим образом. Даны точки P и Q на эллиптической кривой Ep (a,b) . Необходимо найти коэффициент k такой, что

Относительно легко вычислить P по данным k и Q , но довольно трудно вычислить k , зная P и Q .

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

Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (Neal Koblitz) и Виктором Миллером (Victor Miller) в 1985 г. При использовании алгоритмов на эллиптических кривых полагается, что не существует быстрых алгоритмов для решения задачи дискретного логарифмирования в группах их точек. В настоящий момент известны лишь экспоненциальные алгоритмы вычисления обратных функций для эллиптических кривых. По сравнению с субэкспоненциальными алгоритмами разложения числа на простые сомножители (см. криптосистему RSA), это позволяет при одинаковом уровне стойкости уменьшить размерность ключа в несколько раз, а, следовательно, упростить программную и аппаратную реализацию криптосистем.

Эллиптической кривой E называется множество точек (x, y), удовлетворяющих однородному уравнению Вейерштрасса:

где ai – коэффициенты уравнения.

а) y 2 = x 3 – x б) y 2 = x 3 – 3x + 2

в) y 2 = x 3 – x + 1

Рис. 6. Примеры эллиптических кривых

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (, где n > 3 – простое число) и полями характеристики 2 (GF(2 m )).

Эллиптические кривые над полями нечётной характеристики можно привести к виду, называемому эллиптической кривой в короткой форме Вейерштрасса:

y 2 = x 3 + Ax + B (mod n), (12)

где A, B – коэффициенты эллиптической кривой, удовлетворяющие 4 A 3 + 27 B 2 ? 0 (mod n).

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

x 3 + Ax + B = 0. (13)

Это можно сделать с помощью известных формул Кардано. Дискриминант этого уравнения

Если ? > 0, то уравнение имеет три различных действительных корня (см. рис. 9.1а – x1, x2 и x3). Если ? = 0, то уравнение имеет три действительных корня, по крайней мере, два из которых равны (см. рис. 9.1б – x1 и x2). Если ? = 0, то уравнение имеет один действительный корень (см. рис. 9.1в – x1) и два комплексно сопряженных.

Используемые в криптографии кривые не должны иметь особых точек. Геометрически это значит, что график не должен иметь точек возврата и самопересечений (см. рис. 6б). Если кривая не имеет особых точек, то её график имеет две части при положительном дискриминанте (см. рис. 6а), и одну – при отрицательном (см. рис. 6в). Например, для графиков выше в первом случае дискриминант равен 64, а в третьем он равен -368.

Следует отметить, что в у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида P = (x, y) и -P = (x, -y). Например, эллиптическая кривая y 2 = x 3 + 3x + 2 при x = 1 и n = 5 имеет две точки в качестве решения: P = (1, 1) и -P = (1, -1), т.к. 1 2 ? 1 3 + 3 * 1 + 2 (mod 5) и (-1) 2 ? 1 3 + 3 * 1 + 2 (mod 5).

Введем две операции, которые можно выполнять над точками кривой.

а) y 2 = x 3 – x б) y 2 = x 3 – x + 1

Рис. 7. Сложение точек

В формулах 15 и 16 л – угловой коэффициент прямой, проходящей через точки P1 и P2. Если P1 = P2, то л равен значению производной в точке P1.

Умножение точки на число Pk(xk, yk) = k * P(x, y).

а) y 2 = x 3 – x б) y 2 = x 3 – x + 1

Рис. 8. Удвоение точки

А) вариант 1 – выполнить сложение точки P k раз

B) вариант 2 – с использование двоичного представления числа k = (bL, …, b2, b1) и операции удвоения точки. Например, k = 110 = (1101110)2, тогда Pk = 64P + 32P + 8P + 4P + 2P.

Алгоритм, вычисления Pk может выглядеть следующим образом.

then if Pk = null

Q = 2 * Q (? Q = Q + Q)

Для k = 110 вместо 109 сложений будет 1 присваивание, 4 сложения и 7 удвоений (сложений).

Рассмотрим процедуру создания ключей.

Таблица 11. Процедура создания ключей

Прямой способ вычисления порядка группы точек эллиптической кривой q.

1) Рассчитываются координаты первой точки из выражения

y 2 = x 3 + Ax + B (mod n) > y 2 = x 3 + 3x + 7 (mod 41).

Примем x1 = 7, тогда y1 2 mod 41 = (7 3 + 3 * 7 + 7) mod 41 = 2, откуда y1 = 17.

2) Находим координаты второй точки. Для этого вначале вычисляется коэффициент л

Решая последнее уравнение, получаем л = 2 (34 * 2 mod 41 = 27).

Координаты второй точки получаем путем удваивания первой из выражений

x2 = (л 2 – 2x1) mod n = (2 2 – 2 * 7) mod 41 = -10 mod 41 = 31,

y2 = (л(x1 – x2) – y1) mod n = (2 (7 – 31) – 17) mod 41 = -65 mod 41 = 17.

3) Каждую следующую точку рассчитываем по формулам, пока в знаменателе первой формулы не будет получен 0:

К полученному числу точек добавляем точку О, в результате чего q = 46 + 1 = 47. Эта точка есть результат сложения любых двух точек P(xi, yi) и -P(xi, -yi) и представляет собой бесконечно удаленную точку, в которой гипотетически сходятся все вертикальные кривые.

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

Таблица 12. Процедура шифрования отдельного блока (буквы)

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

Таблица 13. Процедура расшифрования отдельного блока (буквы)

Приведенный выше способ шифрования является вариацией шифрования Эль-Гамаля. Если стойкость алгоритма шифрования Эль-Гамаля базируется на сложности решения задачи дискретного логарифмирования, то стойкость шифрования с помощью эллиптических кривых базируется на сложности нахождения множителя k точки P по их произведению. Т.е. если Q = k P, то зная P и k довольно легко вычислить Q. Эффективное решение обратной задачи (найти k при известных P и Q) на текущий момент пока не опубликовано.

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector