# New embedded S

 Page 20/31 Date conversion 17.10.2016 Size 1.14 Mb.

### 6.5.2Elliptic Curves

Given a prime number different from 2 and 3, and the respective field: an elliptic curve E on is denoted with E() and it is defined by the equation:

where satisfy 4 + 27 ≠ 0mod p (like asking that the polynomial in x don’t have multiple roots). A couple (x, y) where is defined a point of the curve if satisfy the previous equation on . It is postulated the point at infinity, and it is denoted by . Other three equations are valid for fields different from 2 and 3: this is due to the fact that the equation presented here is a simplified form of the general equation valid for any field, the Weierstrass equation.

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.

The group law for an elliptic curve with p ≠2,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:

= - and =

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

= - and = () -
An important theorem about the number of points of an elliptic curve is the Hasse’s theorem: let E be an elliptic curve defined over . The number of points in E(), denoted #E(), is called the order of E over . Since the Weierstrass equation has at most two solutions for each x , we know that #E() ∈ [1,2q +1]. This theorem provides tighter bounds for #E() that is:
q + 1 - 2 ≤ #E() ≤ q +1 +2

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:

x = X / , y = Y / for some values of c and d
In this new reference can be shown that the point at infinity becomes the point for which Z = 0 is: to be precise it is not a point but a line in the new coordinates so generally it is called line at infinity. This new type of coordinates is called projective coordinates. It is evident that according to the choice of parameters can have different coordinate systems. A particularly good choice is c = 2 and d = 3, in which case we speak of Jacobian coordinates. The usual characteristic curve defined for fields with> 3 becomes:

in this system the point to infinity becomes (1 : 1 : 0) and the negative of (X : Y : Z) is (X : -Y : Z). In this new reference the couple (x, y), matches more than one of a point (X : Y : Z) because there is an added degree of freedom Z. For this reason the writing (X : Y : Z) indicates the equivalence class that corresponds to (x, y) and not the point (X : Y : Z) representative of that class. Following it is showed the new mode in which adding and doubling points:

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.

It is important to note that when the final result is found it must return to affine coordinates because in Jacobian coordinates the result will be ambiguous.

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 doubling Point multiplication Mixed coordinates 2A → A 1I, 2M, 2S A + A → A 1I, 2M, 1S J + A → J 8M, 3S 2P → P 7M, 3S P + P → P 12M, 2S J + C → J 11M, 3S 2J → J 4M, 4S J + J → J 12M, 4S C + A → C 8M, 3S 2C → C 5M, 4S C + C → C 11M, 3S

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

1. 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

A very simple way to represent a message was created by Koblitz, one of the two fathers of the elliptic curve cryptography this method is called encapsulation or embedding.

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.