Основы современной криптографии


Криптосистема, основанная на эллиптических кривых


Рассмотренная выше криптосистема Эль-Гамаля основана на том, что проблема логарифмирования в конечном простом поле является сложной с вычислительной точки зрения. Однако, конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 1985 году Коблиц и Миллер независимо друг от друга предложили использовать для построения криптосистем алгебраические структуры, определенные на множестве точек на эллиптических кривых. Мы рассмотрим случаи определения эллиптических кривых над простыми конечными полями произвольной характеристики и над полями Галуа характеристики 2.

Определение 3.1. Пусть p > 3 – простое число. Пусть a, b О GF(p) такие, что 4a2 + 27b2 № 0. Эллиптической кривой E над полем GF(p) называется множество решений (x, y) уравнения

y2 = x3 + ax + b                                                      (3.1)

над полем GF(p) вместе с дополнительной точкой Ґ, называемой точкой в бесконечности.

Представление эллиптической кривой в виде уравнения (3.1) носит название эллиптической кривой в форме Вейерштрасса.

Обозначим количество точек на эллиптической кривой E

через #E. Верхняя и нижняя границы для #E определяются теоремой Хассе:

.

Зададим бинарную операцию на E (в аддитивной записи) следующими правилами:

(i) Ґ + Ґ = Ґ;

(ii)                           " (x, y) О E, (x, y) + Ґ = (x, y);

(iii)                         " (x, y) О E, (x, y) + (x,

y) = Ґ;

(iv)                         " (x1,

y1) О E, (x2,

y2) О E, x1

x2, (x1,

y1) + (x2, y2) = (x3,




- Начало -  - Назад -  - Вперед -