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


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


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, а пользователь BbP. Далее они обмениваются вычисленными значениями. При этом параметры самой кривой, координаты точки на ней и значения произведений являются открытыми и могут передаваться по незащищенным каналам связи. Затем пользователь A умножает полученное значение на a, а пользователь B умножает полученное им значение на b. В силу свойств операции умножения на число aЧbP = = bЧaP. Таким образом, оба пользователя получат общее секретное значение (координаты точки abP), которое они могут использовать для получения ключа шифрования. Отметим, что злоумышленнику для восстановления ключа потребуется решить сложную с вычислительной точки зрения задачу определения a и b по известным E, P, aP

и bP.




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