ЧАСТЬ 5. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ НАД КОНЕЧНЫМ ПОЛЕМ.
В данном пособии рассматриваются только задачи, решаемые в конечной аддитивной группе точек эллиптической кривой над простым конечным полем характеристики p>3. Конечной группой точек эллиптической кривой называют совокупность точек с целочисленными координатами удовлетворяющих короткой аффинной форме однородного уравнения Вейерштрасса над конечным полем характеристики p [3]: Кривая также характеризуется: дискриминантом и j-инвариантом . В данной аддитивной группе точек определены две операции – сложение и удвоение, которые выполняются в соответствии с групповым законом: Пусть P1(x1, y1), P2(x2, y2) и, если P3(x3, y3) = P1 + P2 ≠ O, то координаты x3, y3 вычисляются как: где при а при При создании криптосистем на основе эллиптических кривых важно знать порядок группы точек эллиптической кривой. Он характеризует стойкость системы и является одним из ее параметров. На практике порядок группы точек эллиптической кривой и ее циклической подгруппы находится при помощи алгоритма Шуфа [5], который в данном пособии не приводится. Определим порядок группы точек методом прямого перебора на примере кривой над полем характеристики , характеризуемой уравнением [11]: Ее дискриминант: , - кривая не аномальная и не суперсингулярная. Для каждого элемента поля Fp вычислим y2: При помощи вычисления символа Лежандра по упрощенной зависимости: определим возможность извлечения квадратного корня. В случае – на кривой нет целочисленных точек с таким x. В случае – мы нашли нулевую точку ( x, 0). В случае произведем извлечение квадратного корня по упрощенной методике и определим: Результаты вычислений сведены в таблицу 5. Таблица 5
Из таблицы видно, что количество точек с целочисленными координатами Q = 27. 27 – составное число, поэтому в группе существует несколько циклических подгрупп. Задача 5.1. Для заданной эллиптической кривой E над конечным полем и ее точек P1 и P2 , осуществить удвоение точки P1 и сложить результат с точкой P2. Проверить принадлежность результата к группе точек эллиптической кривой. Пример решения
;
Ниже приведены примеры реализации криптосистем на основе эллиптических кривых.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|