Автор: Пользователь скрыл имя, 11 Ноября 2011 в 00:57, курсовая работа
Теория эллиптических кривых является одним из важнейших разделов алгебраической геометрии, точнее, её раздела. изучающего плоские алгебраических кривые Она тесно связана также с комплексным анализом и с теорией чисел до сих пор интенсивно развивается и чрезвычайно обширна и сложна. В ее создании принимали участие многие крупнейшие математики прошлого. а начинается она (в определенном смысле) с последнего из великих древнегреческих математиков – Диофанта.
ВВЕДЕНИЕ
Теория эллиптических кривых является одним из важнейших разделов алгебраической геометрии, точнее, её раздела. изучающего плоские алгебраических кривые Она тесно связана также с комплексным анализом и с теорией чисел до сих пор интенсивно развивается и чрезвычайно обширна и сложна. В ее создании принимали участие многие крупнейшие математики прошлого. а начинается она (в определенном смысле) с последнего из великих древнегреческих математиков – Диофанта. Структуру группы на эллиптических кривых определил знаменитый французский математик Анри Пуанкаре. Долгое время теория эллиптических кривых являлась чистешей областью математики, не имеющей за ее пределами никаких приложений. Представление об этой теории и ее взаимосвязях с другими разделами математики можно получить, заглянув, например в книги.
В восьмидесятые годы прошлого века теория эллиптических кривых получила приложения в области построения алгоритмов факторизации больших чисел и через эти приложения вошла в криптографию (как в ее области, связанные с построением криптосистем с открытым ключом, протоколов распределения ключей, и протоколов цифровой подписи, а также и области классической криптографии, связанные с генерацией псевдослучайных последовательностей).
В криптографии с открытым ключом эллиптические кривые являются основой ряда алгоритмов 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, что, конечно, меньше
На ЭК Е над полем определено отображение Фробениуса:
Оно сопоставляет точке кривой Е точку на той же кривой, вне зависимости от поля, над которым эта точка определена. Кроме того, отображение Фробениуса сохраняет групповую операцию, т. е.
Другими словами, — эндоморфизм группы Е над алгебраическим замыканием который обычно называют эндоморфизмом Фробениуса.
Информация о работе Понятие и использованиепреобразований в эллиптических кривых