Elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...

is a popular form of

public key Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

encryption that is based on the mathematical theory of

elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...

s. Points on an elliptic curve can be added and form a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

under this addition operation. This article describes the computational costs for this group addition and certain related operations that are used in elliptic curve cryptography algorithms.

Abbreviations for the operations

The next section presents a table of all the time-costs of some of the possible operations in elliptic curves. The columns of the table are labelled by various computational operations. The rows of the table are for different models of elliptic curves. These are the operations considered : DBL - Doubling ADD - Addition mADD - Mixed addition: addition of an input that has been scaled to have ''Z''-coordinate 1. mDBL - Mixed doubling: doubling of an input that has been scaled to have ''Z'' coordinate 1. TPL - Tripling. DBL+ADD - Combined double and add step To see how adding (ADD) and doubling (DBL) points on elliptic curves are defined, see The group law. The importance of doubling to speed scaler multiplication is discussed after the table. For information about other possible operations on elliptic curves see http://hyperelliptic.org/EFD/g1p/index.html.

Tabulation

Under different assumptions on the multiplication, addition, inversion for the elements in some fixed

field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...

, the time-cost of these operations varies. In this table it is assumed that: : I = 100M, S = 1M, *param = 0M, add = 0M, *const = 0M This means that 100 multiplications (M) are required to invert (I) an element; one multiplication is required to compute the square (S) of an element; no multiplication is needed to multiply an element by a parameter (*param), by a constant (*const), or to add two elements. For more information about other results obtained with different assumptions, see http://hyperelliptic.org/EFD/g1p/index.html

Importance of doubling

In some applications of

elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...

and the elliptic curve method of factorization ( ECM) it is necessary to consider the scalar multiplication 'n'''P''. One way to do this is to compute successively: :

P,\quad =P+P,\quad = +P,  \dots  , = -1 +P

But it is faster to use double-and-add method, e.g. 'P'' = ) + ''P''. In general to compute 'k'''P'', write

k=\sum_k_i2^i

with ''k''_''i'' in and

l= og_2 k /math>, ''k''

_''l'' = 1, then:

....(+_)+_)+_)+ \dots ) \dots +_1)+_0 =^l +_2^+ \dots  +_12 +_0

. Note that, this simple algorithm takes at most ''2l'' steps and each step consists of a doubling and (if ''k''_''i'' ≠ 0) adding two points. So, this is one of the reasons why addition and doubling formulas are defined. Furthermore, this method is applicable to any group and if the group law is written multiplicatively, the double-and-add algorithm is instead called square-and-multiply algorithm.

References

*http://hyperelliptic.org/EFD/g1p/index.html {{DEFAULTSORT:Table Of Costs Of Operations In Elliptic Curves Elliptic curve cryptography Finite fields Computational number theory Cryptographic attacks Elliptic curves