Криптосистема, основанная на эллиптических кривых
Рассмотренная выше криптосистема Эль-Гамаля основана на том, что проблема логарифмирования в конечном простом поле является сложной с вычислительной точки зрения. Однако, конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 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,
y3), где
x3 = l2
– x1 – x2,
y3 = l(x1
– x3) – y1, и
(v) " (x1,
y1) О E, y1
№ 0, (x1, y1) + (x1, y1) = (x2, y2), где
x2 = l2
– 2x1,
y2 = l(x1
– x3) – y1 и
Множество точек эллиптической кривой E с заданной таким образом операцией образует абелеву группу.
Если #E = p + 1, то кривая E называется суперсингулярной.
Эллиптическая не являющаяся суперсингулярной кривая E
над полем GF(2m) характеристики 2 задается следующим образом.
Определение 3.2. Пусть m > 3 – целое число. Пусть a, b О GF(2m), b № 0. Эллиптической кривой E над полем GF(2m) называется множество решений (x, y) уравнения
y2 + xy = x3 + ax + b
(3.2)
над полем GF(2m) вместе с дополнительной точкой Ґ, называемой точкой в бесконечности.
Количество точек на кривой E также определяется теоремой Хассе:
где q = 2m. Более того, #E четно.
Операция сложения на E в этом случае задается следующими правилами:
(i) Ґ + Ґ = Ґ;
(ii) " (x, y) О E, (x, y) + Ґ = (x, y);
(iii) " (x, y) О E, (x, y) + (x,
x + y) = Ґ;
(iv) " (x1,
y1) О E, (x2,
y2) О E, x1
№ x2, (x1,
y1) + (x2, y2) = (x3,
y3), где
x3 = l2
+ l + x1 + x2 + a,
y3 = l(x1
+ x3) + x3 + y1, и
(v) " (x1,
y1) О E, x1
№ 0, (x1, y1) + (x1, y1) = (x2, y2), где
x2 = l2
+ l +a,
В этом случае множество точек эллиптической кривой E
с заданной таким образом операцией также образует абелеву группу.
Пользуясь операцией сложения точек на кривой, можно естественным образом определить операцию умножения точки P О E на произвольное целое число n:
nP = P + P + … + P,
где операция сложения выполняется n раз.
Теперь построим одностороннюю функцию, на основе которой можно будет создать криптографическую систему.
Пусть E – эллиптическая кривая, P О E – точка на этой кривой. Выберем целое число n < #E. Тогда в качестве прямой функции выберем произведение nP. Для его вычисления по оптимальному алгоритму потребуется не более 2Чlog2n операций сложения. Обратную задачу сформулируем следующим образом: по заданным эллиптической кривой E, точке P О E и произведению nP найти n. В настоящее время все известные алгоритмы решения этой задачи требуют экспоненциального времени.
Теперь мы можем описать криптографический протокол, аналогичный известному протоколу Диффи-Хеллмана. Для установления защищенной связи два пользователя A и B совместно выбирают эллиптическую кривую E и точку P на ней. Затем каждый из пользователей выбирает свое секретное целое число, соответственно a и b. Пользователь A
вычисляет произведение aP, а пользователь B – bP. Далее они обмениваются вычисленными значениями. При этом параметры самой кривой, координаты точки на ней и значения произведений являются открытыми и могут передаваться по незащищенным каналам связи. Затем пользователь A умножает полученное значение на a, а пользователь B умножает полученное им значение на b. В силу свойств операции умножения на число aЧbP = = bЧaP. Таким образом, оба пользователя получат общее секретное значение (координаты точки abP), которое они могут использовать для получения ключа шифрования. Отметим, что злоумышленнику для восстановления ключа потребуется решить сложную с вычислительной точки зрения задачу определения a и b по известным E, P, aP
и bP.
