New embedded S

6.5.2Elliptic Curves

Following there is an example of an elliptic curve:

Let an elliptic curve on , and its point are:

There is a method for adding two points on an elliptic curve to produce a third: the addition rule requires some arithmetic operations of addition with the coordinates of points to be added. With this addition rule, the set of points of an elliptic curve make a group with the point at infinity which acts as identity: for this reason indicates the sum operation repeated d times of the point P to generate the point Q.

Let E be an elliptic curve defined over the field K. There is a chord-and-tangent rule for adding two points in E() to give a third point in E(); this rule is right only for real numbers. Together with this addition operation, the set of points E() forms an abelian group with serving as its identity. It is this group that is used in the construction of elliptic curve cryptographic systems.

The addition rule is best explained geometrically. Let P = (x1 ,y1) and Q = (x2, y2) be two distinct points on an elliptic curve E. Then the sum R, of P and Q, is defined as follows. First draw a line through P and Q; this line intersects the elliptic curve at a third point. Then R is the reflection of this point about the x-axis. This is represented in Figure .

The double R, of P, is defined as follows. First draw the tangent line to the elliptic curve at P. This line intersects the elliptic curve at a second point. Then R is the reflection of this point about the x-axis. Algebraic formulas for the group law can be derived from the geometric description. These formulas are presented next for elliptic curves E of the simplified Weierstrass form in affine coordinates when the characteristic of the underlying field is not 2 or 3.

• 
  Identity. P + ∞ = ∞ + P = P for all P ∈ E().
  
• 
  Negatives. If P = (x, y) ∈ E(), then (x, y) + (x,−y) = ∞. The point (x,−y) is denoted by −P and is called the negative of P; note that −P is indeed a point in E(). Also, − ∞ = ∞.
  

• 
  Point addition. Let P = (x1, y1) ∈ E() and Q = (x2, y2) ∈ E), where P = ±Q. Then P + Q = (x3, y3), where:
  

• 
  Point doubling. Let P = (x1, y1) ∈ E(), where P = −P. Then 2P = (,), where:
  

The interval [q + 1 - 2, q +1 +2] is called the Hasse interval. Since 2 is small relative to q, we have #E(Fq )≈ q.

Like any other type of curve also elliptic curves can make profitable use of changes of coordinates. Previously rules of addition and doubling in natural coordinates of elliptic curves were presented: these are called affine coordinates.

Let K be any field extended, binary or prime; it is possible define an equivalence relationship between non-zero triple on K, that is passes by the couple(x, y) to the triple (X, Y, Z). In particular, the map is the following:

If so . The point is indicated by and is called the negative of P.

• 
  Point addition. Let and ∈ E(), and let . So, where:
  

• 
  Point doubling . Let ∈ E() and let . So , where:
  

Figure - Example of an elliptic curve, scheme of point sum and point inversion.

From the computational point of view a superficial analysis would lead one to conclude that the Jacobian coordinates are inappropriate because the number of involved operations is higher. However in the Jacobian coordinates is not performed the operation of "division" that in a finite field is the operation of inversion that is known to be particularly expensive: It is made by the extended Euclidean algorithm, and if possible this type of operation should be avoided. Paying some extra multiplication (fast operation) avoids costly inversions: in the literature assumes that an inversion costs 80 multiplications. There are algorithms particularly efficient where it is known the structure of the elliptic curve and Jacobian coordinates are used: in general more are the parameters of the system that we fix and more we are able to build efficient algorithms for the price of a lower flexibility. There are other types of coordinates and the search is open on this front to get better and better representations that enable performance gains.

Table - Operations needed to perform point addiction and point doubling on an elliptic curve

Operations needed to perform point addiction and point doubling on an elliptic curve with equation , over different representations.

Point representation: A = affine, P = standard projective, J = Jacobian, C = Chudnovsky.

Operation over finite field: I = inversion, M = multiplication, S =squaring.

For example, there are special numeric representations to further improve performance (NAF Not Adjacent Form), special techniques of sliding window, the well-known product of Montgomery, interleaving, the use of the Frobenius map, the decomposition of the operands in multiplication, the halving and others. As a synthesis of these considerations, Table [hankerson] summarizes the computational costs of the most used coordinate systems for example for the case a = -3 and field prime.

To place elliptic curves in an application context should understand that there are domain parameters of a cryptosystem and how to represent a message through a point on the curve.

The basic operation to perform cryptography is the scalar multiplication of a point that is the operation of adding a point k times with itself.

A classical and efficient algorithm that is used is the algorithm of multiplication that a bit at a time of k, determines the operation to do. The algorithm consists in the following steps [hankerson].
INPUT: k = (), P Є E).

OUTPUT: kP.

1. 
   Q ← ∞
   
2. 
   For i from 0 to t – 1 do
   

1. 
   If = 1 then Q ← Q + P
   
2. 
   P ← 2P
   

3. 
   Return(Q)
   

To define a cryptosystem based on elliptic curves is appropriate to make a variety of parameters suitable to the definition of the domain in which we operate. The domain parameters are the following n-tuple of elements:

• 
  q represents the power of the prime number that describes the field in which it operates, which means that we are operating in
  
• 
  fr indicates the way in which we are representing the elements of . In the case the field is not an extension, or is simply prime, the representation coincides with the elements of the field: in case of extended fields must have recourse to a polynomial representation.
  
• 
  a, b are the coefficient of the curve
  
• 
  P is the base point that is the point from which we start to perform the operation kP
  
• 
  n indicates the order of P. Using an additive language, order means the value of n such that ∞ = nP
  
• 
  h is called cofactor and is defined
  

Suppose to operate in and that and . Defining with it should be noted that .

Defining with a, b coefficient of the curve: it is calculated the Legendre symbol and it is verified that it is a quadratic residue (that is 1): in this way we can see if the root could be extracted. If the answer is affirmative (ie is 1) for we have found an univocal correspondence with m.

One can better understand the hypothesis: in fact is known that if that congruence is valid the root can be found easily by calculating. If is not valid the root can be calculated, however, it must use a more sophisticated called Tonelli’s algorithm. In case of contrary response we will try for another so long as at least one allows the solution of the equation. It is known from considerations of number theory that the fields are rich in quadratic residues, and should not be a preoccupation the idea of finding a residue because you can always easily find it.

To have any guarantee of success that we have imposed that is we have the opportunity to make 100 attempts. It is known that the probability of finding a quadratic residue is 0.5, for this reason the probability of not finding 1 in 100 attempts is that is 0.

A message encoded in a point will also need to go back, the decoding operation is trivial and gives.