Понятие и использованиепреобразований в эллиптических кривых
ВВЕДЕНИЕ
Теория эллиптических кривых является одним из важнейших разделов алгебраической геометрии, точнее, её раздела. изучающего плоские алгебраических кривые Она тесно связана также с комплексным анализом и с теорией чисел до сих пор интенсивно развивается и чрезвычайно обширна и сложна. В ее создании принимали участие многие крупнейшие математики прошлого. а начинается она (в определенном смысле) с последнего из великих древнегреческих математиков – Диофанта. Структуру группы на эллиптических кривых определил знаменитый французский математик Анри Пуанкаре. Долгое время теория эллиптических кривых являлась чистешей областью математики, не имеющей за ее пределами никаких приложений. Представление об этой теории и ее взаимосвязях с другими разделами математики можно получить, заглянув, например в книги.
В восьмидесятые годы прошлого века теория эллиптических кривых получила приложения в области построения алгоритмов факторизации больших чисел и через эти приложения вошла в криптографию (как в ее области, связанные с построением криптосистем с открытым ключом, протоколов распределения ключей, и протоколов цифровой подписи, а также и области классической криптографии, связанные с генерацией псевдослучайных последовательностей).
В криптографии с открытым ключом эллиптические кривые являются основой ряда алгоритмов ECC — криптографии на эллиптических кривых. Далее мы для краткости будем иногда называть не просто эллиптической криптографией. Идея создания эллиптической криптографии была выдвинута в 1985 году независимо в работах В. Миллера и Н. Коблица. Интерес в криптографии к эллиптическим кривым обусловлен, с одной стороны, тем, что они являются богатым источником конечных абелевых групп, обладающих полезными структурными свойствами, так и тем, что на их основе обеспечивается те же криптографический свойства которыми обладают числовые или полиноминальные криптосистемы, но при существенно меньшем размере ключа
Далее мы даем краткое и ориентированное только на последующие приложения
введение в теорию эллиптических кривых.
Алгебраической кривой порядка n над полем точек называется множеством точек удовлетворяющих уравнению , где многочлен степени n с коэффипиентами из . Уточним, что под под спенью одночлена понимается сумма степеней входящих в него переменных, а под степенью многочлена — максимальная степень составляющих его одночленов.
1 ПОНЯТИЕ
И ИСПОЛЬЗОВАНИЕ ПРЕОБРАЗОВАНИЙ В ЭЛЛИПТИЧЕСКИХ
КРИВЫХ
- Ввод в понятия о эллиптических кривых
Эта часть работы посвящена введению в теорию эллиптических кривых над конечными полями. Некоторые из наиболее современных криптографических систем с открытым ключом основаны на использовании эллиптических кривых (позже будем их сокращать как ЭК), в результате чего они обеспечивают высокую эффективность и большую пропускную способность. Эту часть работу можно пропустить, поскольку многое из данной работы можно читать, понимая лишь, что ЭК над конечным полем — конечная абелева группа, в которой можно ставить задачу о вычислении дискретных логарифмов.
Проективная плоскость над полем определяется как
множество троек не равных одновременно нулю элементов на котором введено отношение эквивалентности:
для любых
Так, например, две точки (4,1,1) и (5,3,3) эквивалентны в .
Класс
эквивалентности троек
ЭК называется множество точек проективной
плоскости, удовлетворяющих однородному уравнению Вейерштрасса.
где Это уравнение также называют длинной формой Вейерштрасса.
Кривая должна быть не особой в том смысле, что частные производные
не должны обращаться в нуль одновременно ни в одной ее точке.
Множество -рациональных точек кривой , т. е. точек из ,
удовлетворяющих уравнению кривой, обозначается через . Отметим,
что кривая
имеет ровно одну точку, чья координата
равна нулю, а именно (0,1,0). Ее принято называть
бесконечно удаленной точкой
(или просто точкой
на бесконечности)
и обозначать символом
.
1.2
Групповой закон
Допустим, что 3 и рассмотрим замену переменных
переводящую кривую, заданную длинной формой Вейерштрасса,
в изоморфную ей кривую, определяемую короткой формой Вейерштрасса
при некоторых На таких представителях классов изоморфных
эллиптических кривых можно наглядно ввести ГК
методом хорд и касательных.
Сложение точек определяется с помощью хорд (Рисунок 1.1). Пусть
Р и Q — две точки кривой. Соединим их прямой линией. Она обязательно
пересечет кривую в какой-то третьей точке R, поскольку мы пересекаем кубическую кривую прямой. Точка R будет определена над тем же полем, что сама кривая и исходные точки Р и Q. Отразим затем точку R относительно горизонтальной оси координат и получим точку, определенную над основным полем. Последняя точка и будет суммой Р + Q.
Рисунок
1.1 – Сложение точек на ЭК
Касательные служат для удвоения точек (используя хорду, нельзя
сложить точку с собой). Пусть Р — произвольная точка эллиптической
кривой (Рисунок 1.2). Проведем касательную к кривой в точке Р.
Она пересечет кривую еще в какой-то одной точке R (кубическая кривая пересекается с прямой по трем точкам с учетом кратности пересечения). Отразив R относительно горизонтальной оси, мы получим точку [2]Р = Р + Р. Вертикальная касательная в точке Р «пересекает» кривую в бесконечно удаленной точке. В этой ситуации Р + Р = и говорят,
что Р — точка порядка 2.
Можно показать, что метод хорд и касательных наделяет эллиптическую
кривую структурой абелевой группы с бесконечно удаленной точкой в качестве единичного элемента, т. е. нуля.
Определение операций можно легко перенести на случай общей ЭК, заданной длинной формой Вейерштрасса (в частности, характеристика поля может быть любой). Необходимо только заменить отражение относительно оси абсцисс на симметрию относительно прямой
Рисунок
1.2 – Удвоение точек на ЭК
В дополнение к сказанному приведем алгебраические формулы, реализующие сложение точек по методу хорд и касательных. Это необходимо сделать, поскольку вычерчивание диаграмм в поле конечной характеристики — дело безнадежное.
Пусть Е — ЭК, определяемая уравнением
на которой выбраны точки Точка — имеет координаты
Введем коэффициенты
при и
Если но Если
,
то вычисляются по формулам :
Описанный ранее изоморфизм эллиптических кривых сохраняет структуру группы. Так что на изоморфных кривых указанные формулы определяют структуры изоморфных абелевых групп. Фиксируем натуральное число т и обозначим через отображение кривой на себя, сопоставляющее каждой точке Р ее кратное Р, т. е.
Это отображение — основа криптографических систем, опирающихся на эллиптическую кривую, поскольку его можно легко вычислить, но крайне сложно обратить, т. е. по данным координатам найти очень трудно. Конечно, наше высказывание о сложности обращения предполагает специальный выбор ЭК и соблюдение нескольких других условий, к чему мы еще вернемся.
Закончим этот параграф иллюстрацией группового закона на ЭК. Вновь рассмотрим кривую Е над полем , заданную уравнением (2.2). Оказывается, на этой кривой всего лишь шесть точек, одна из которых — , а координаты других представлены списком:
(4,1), (6,6), (5,0), (6,1), (4,6).
Результаты сложения
несложно получить по формулам леммы 2.2.
Сведем их в таблицу 1.1. Найдем координаты
образов точки Р(4,1) при отображении
для различных
.
.
Из вычислений видно, что в нашем примере E( ) — конечная циклическая группа порядка 6, а точка Р(4,1) — ее образующая. Эллиптическая
кривая
над любым конечным полем будет
конечной абелевой группой, и, что очень
удачно, циклической (или близкой к циклической).
Таблица 1.1 – Сложение точек на кривой над полем
1.3 Эллиптические
кривые над конечными полями
Как мы уже отмечали, количество -рациональных точек эллиптической кривой конечно. Обозначим его символом . Ожидаемое число точек кривой близко и можно положить
где «дефект» называется следом отображения Фробениуса в q, В хорошо известной теореме Хассе дана оценка порядка группы След отображения Фробениуса удовлетворяет неравенству
В примере кривая над полем имеет 6 точек. Так что след отображения Фробениуса здесь равен 2, что, конечно, меньше
На ЭК Е над полем определено отображение Фробениуса:
Оно сопоставляет точке кривой Е точку на той же кривой, вне зависимости от поля, над которым эта точка определена. Кроме того, отображение Фробениуса сохраняет групповую операцию, т. е.
Другими словами, — эндоморфизм группы Е над алгебраическим замыканием который обычно называют эндоморфизмом Фробениуса.
Сед отображения Фробениуса и эндоморфизм Фробениуса связаны
уравнением:
т. е. для произвольной точки кривой выполнено соотношение
В котором сложение и вычитание — суть групповые операции на ЭК. Есть два частных случая криптографически непригодных эллиптических кривых:
Кривая называется аномальной, если ее след Фробениуса
равен 1, т.е. . Эта кривая особенно неудобна, когда q — простое число.
Кривая называется суперсингулярной, если характеристика
р поля делит след отображения Фробениуса . Таких кривых также стараются избегать в криптографии. При q = р ССК насчитывает р + 1 точку, поскольку t = 0 в этом случае. Если же то у суперсингулярных кривых может принимать значения
при нечетном
при четном если и если
Выбирая кривую для шифрования, нужно стремиться к тому, чтобы число ее точек делилось на достаточно большое простое число. В связи с этим необходимо научиться вычислять порядок группы
Известно, что порядок произвольной группы над любым полем вычисляется за полиномиальное время. Это делается с помощью сложного алгоритма, который мы не можем объяснить в этой книге. Достаточно запомнить, что вычисление порядка группы возможно как в теоретическом, так и в практических планах. В следующих главах, рассматривая алгоритмы решения задачи о дискретных логарифмах, мы увидим, что информация о порядке группы очень существенна для оценки стойкости протокола, основанного на соответствующей кривой.
Одним из достоинств эллиптических кривых является то, что они доставляют большое число возможных групп. Можно менять как основное поле, так и коэффициенты уравнения кривой. Наконец, отыскать эллиптическую кривую с хорошими криптографическими свойствами для создания безопасного протокола, относительно легко.
Как было отмечено ранее, случаи требуют дополнительных
усилий.
Реализация криптографических систем,
основанных на ЭК, базируется на поле
, чья характеристика равна 2, или на
поле
с большим простым числом р.
Поэтому в конце текущей главы мы сконцентрируем
внимание на полях характеристики 2 и
, опустив случай
. Большинство общих рассуждений
с некоторой модификацией переносится
на случай характеристики три, что хорошо
освещено в специальной литературе.
1.3.1
Кривые над полем
Пусть основное поле с , где р > 3 — простое число И Как уже отмечалось, уравнение кривой над таким полем можно представить в виде короткой формы Вейерштрасса
Ее дискриминант равен а ί-инвариант Формулы из леммы 2.2, описывающие ГК, также упрощаются: и если то координаты вычисляются так:
где при
а при
1.3.2 Кривые над полем характеристики 2
Здесь мы ограничимся конечными полями с при . В этом случае ί-инвариант кривой Е вычисляется по формуле Условие т.е. в характеристике 2 равносильно суперсингулярности кривой Е. Мы уже отмечали, что суперсингулярные кривые — очень специфический случай, который не используется в криптографии. Поэтому будем предполагать, что
В этих предположениях представитель любого класса изоморфизма эллиптических кривых над записывается уравнением
где и Здесь — фиксированный элемент поля , удовлетворяющий соотношению: , где — абсолютный след, вычисляющийся по формуле
Когда характеристика поля равна 2, формула для противоположного элемента ЭК из леммы 2.2 преобразуется к виду и, если , то
где при
а если то
1.4
Большая характеристика
Формулы сложения точек ЭК, заданной уравнением
над полем большой характеристики выглядят теперь как
где тройка координат вычисляется последовательно по правилу:
Обратите внимание, что здесь нет ни одной операции деления, кроме деления на 2, которая легко заменяется умножением на заранее вычисленное число
Удвоение точек упрощается с помощью формул
1.4.1
Четная характеристика
Уравнение ЭК над полем четной характеристики
записывается в виде
Сложение точек
В этом случае осуществляется по рецепту:
И, наконец, координаты удвоенной точки определяются по правилу:
Итак, в
обоих интересных случаях — при большой
и четной характеристиках поля — мы исключили
дорогостоящую операцию деления.
1.5
Сжатие точек
Во многих криптографических протоколах возникает необходимость хранить в памяти или передавать по сети отдельные точки ЭК.
В аффинных координатах это можно сделать с помощью двух элементов поля: координат х и у. Однако экономнее применять так называемую технику сжатия точек.
Метод
сжатия точек работает благодаря
тому, что уравнение кривой в аффинных
координатах при фиксированном значении
х превращается в квадратное уравнение
относительно координаты
у. Поэтому каждому возможному значению
координаты х точки кривой соответствует
не более двух значений координаты у.
Значит, вместо двух координат для идентификации
точки кривой можно хранить в памяти компьютера
только координату х
и еще некий двоичный параметре 6, сообщающий
о том, какое именно значение координаты
у нужно брать. Остается только решить,
как вычислять параметр b
и как по нему и данному х
восстановить у-координату нужной
точки.
1.5.1. Случай
большой характеристики поля
Заметим, что если р > 2, то квадратные корни из элемента представляются натуральными числами разной четности из промежутка
1, . . . , р — 1, поскольку
Таким образом, в качестве параметра b можно выбрать четность у-координаты соответствующей точки. Покажем теперь, как восстановить полную информацию о координатах точки по паре (x, b). Сначала вычисляется
а затем переменной у присваивают значение , если четность совпадает
с четностью b, и р — , когда четности разные. Если же оказалось, что = 0, то, не обращая внимания на параметр b, можно положить у = 0.
В качестве примера рассмотрим кривую
над полем . Для представления каждой из ее точек (4,1) и (4,6) в
двоичной
системе счисления нам
(0b 100, 0b 001) и (0b100, 0b 110),
в то время как при использовании метода сжатия точек всего четыре:
(0b 100, 0b1) и (0b 100, 0b0).
В реальных криптографических протоколах получается более существенная экономия компьютерной памяти. Рассмотрим, например,ту же кривую, но над полем с
На ней есть точка с координатами
для записи которой нам потребовалось 102 разряда. При сжатии информации эту точку можно представить в виде
(1125 899 906 842 675,1),
где использовано
только 52 разряда.
1.5.2.
Четная характеристика
В случае четной характеристики необходимо проявить больше изобретательности. Предположим, что нам дана точка Р(x, у) на эллиптической
кривой
Если у = 0, то можно положить b = 0. в противном случае вычисляют z = у/х и присваивают переменной b самый младший двоичный разряд числа z.
Для восстановления у по данной паре (x, b) в случае вычисляют
и обозначают через одно из решений уравнения
Если наименьший двоичный разряд числа совпадает с 6, то у = x/ .
В противоположной ситуации у = х( +1). Для объяснения того, почему этот метод правильно восстанавливает y-координату точки, напомним, что координаты (x, у) точки Р — решение уравнения (2.5). Поэтому пары (х, у/х) и (х, 1+у/х) удовлетворяют соотношению
