Математические основы криптографии на эллиптических кривых

Использование эллиптических кривых для криптографии было независимо предложено Нилом Коблицем (Neal Koblitz) и Виктором Миллером (Victor Miller) в середине 80-х годов прошлого века [Kob87, Mil85].

На сегодняшний день это одно из самых перспективных направлений развития криптографии с открытыми ключами. Эллиптической кривой E , определенной в конечном поле Fp , где p > 3, называется множество точек с координатами (x, y) , удовлетворяющих уравнению: y 2 = x3 + ax + b , где a, b ? Fp и 4a3 + 27b2 ? 0 вместе со специальной точкой O , называемой точкой бесконечности или, как еще иногда говорят, нулевой точкой [Коб2001]. В группе точек на эллиптической кривой точка бесконечности O нужна для обеспечения существования обратного элемента в группе и необходимых свойств операций.

Рассмотрим основные операции над точками и их геометрическую интерпретацию на примере обычных плоских эллиптических кривых, т.е. кривых определенных над полем вещественных чисел. Полученные в результате аналитические формулы для рассматриваемых операций являются действительными для эллиптических кривых (5.1), определенных над любым полем.

Точкой, обратной к данной точке P(x, y) , называется точка с координатами (x,? y) и обозначается как (?P) , т.е. точка, зеркально отраженная от оси абсцисс. Геометрический смысл операции сложения двух точек P,Q ? E на эллиптической кривой (рис.NN) заключается в том, что через них проводится секущая, пересекающая кривую в третьей точке. Обратная точка для точки пересечения дает результат операции сложения.