Оценка эффективности дифференциального сложения точек кривых в обобщенной форме Эдвардса

A survey of the main properties of three classes of curves in the generalized Edwards form is given: complete, quadratic and twisted Edwards curves. The analysis of the Montgomery algorithm for differential addition of points for the Montgomery curve is carried out. An estimation of the record low cost of computing the scalar product kP of a point P is given, which is equal to 5M+4S+1U on one step of the iterative cycle (M is the cost of finite field multiplication, S is the cost of squaring, U is the cost of field multiplication by a known constant). A detailed derivation of the formulas for addition-subtraction and doubling points for the curve in the generalized Edwards form in projective coordinates of Farashahi-Hosseini is carried out. Moving from three-dimensional projective coordinates (X:Y:Z) to two-dimensional coordinates (W: Z) allows achieving the same minimum computational cost for the Edwards curves as for the Montgomery curve. Aspects of the choice of an Edwards-form curve acceptable for cryptography and its parameters optimization in the problem of differential addition of points are discussed. Twisted Edwards curves with the order of NE=4n (n is prime) at p≡5mod8 are recommended, minimizing the parameters a and d allows achieving the minimum cost estimation 5M+4S for one step of computing the point product. It is shown that the transition from the Weierstrass curves (the form used in modern cryptographic standards) to the Edwards curves makes it possible to obtain a potential gain in the speed of computing the scalar product of the point by a factor of 3.09.
Дан обзор основных свойств трех классов кривых в обобщенной форме Эдвардса: полных, квадратичных и скрученных кривых Эдвардса. Проведен анализ алгоритма Монтгомери дифференциального сложения точек для кривой в форме Монтгомери. Приведена оценка рекордно малой стоимости вычисления скалярного произведения kP точки P, равная 5M+4S+1U на одном шаге итеративного цикла (M – стоимость вычисления умножения в конечном поле, S- стоимость возведения в квадрат, U – стоимость умножения на известную константу). Приведен подробный вывод формул сложения-вычитания и удвоения точек для кривой в обобщенной форме Эдвардса в проективных координатах Фарашахи – Хоссейни. Переход от трехмерных проективных координат X:Y:Z) к двухмерным координатам (W: Z) позволяет для кривых Эдвардса достичь той же минимальной стоимости вычислений 5M+4S+1U, что и для кривой в форме Монтгомери. Обсуждаются аспекты выбора приемлемой для криптографии кривой в форме Эдвардса и оптимизации ее параметров в задаче дифференциального сложения точек. Рекомендуются скрученные кривые Эдвардса с порядком NE=4n (n - простoе) при p≡5mod8, минимизация параметров a и d которых позволяет достичь минимальной оценки стоимости 5M+4S одного шага вычисления скалярного произведения точки. Показано, что переход от используемых в современных стандартах кривых в форме Вейерштрасса к кривым в форме Эдвардса позволяет получить потенциальный выигрыш в скорости вычисления скалярного произведения точки в 3,09 раза.
Дано огляд основних властивостей трьох класів кривих в узагальненій формі Едвардса: повних, квадратичних і скручених кривих Едвардса. Проведено аналіз алгоритму Монтгомері диференціального додавання точок для кривої в формі Монтгомері. Наведено оцінку рекордно малої вартості обчислення скалярного добутку точки P, яка дорівнює 5M+4S+1U на одному кроці ітеративного циклу (M– вартість операції обчислення добутку в скінченному полі, S – вартість піднесення до квадрату, U – вартість множення на відому константу). Дано ретельний вивід формул додавання-віднімання і подвоєння точок для кривої в узагальненій формі Едвардса в проективних координатах Фарашахи – Хоссейни. Перехід від тривимірних проективних координат (X:Y:Z) до двовимірних координат (W: Z) дозволяє для кривих Едвардса досягти тієї ж самої мінімальної вартості обчислень 5M+4S+1U, що і для кривої в формі Монтгомері. Обговорюються аспекти вибору придатної для криптографії кривої в формі Едвардса і оптимізації її параметрів в задачі диференціального додавання точок. Рекомендуються скручені криві Едвардса порядку NE=4n (n - просте) при p≡5mod8, для яких мінімізація параметрів a та d дозволяє досягнути мінімальної оцінки вартості 5M+4S для одного кроку обчислення скалярного добутку точки. Показано, що перехід від кривих в формі Вейерштраса, які використовуються в сучасних криптографічних стандартах, до кривих в формі Едвардса, дозволяє отримати потенціальний виграш в швидкості обчислення скалярного добутку точки в 3,09 рази.