HƯỚNG DẪN DOWNLOAD TÀI LIỆU

Bước 1:Tại trang tài liệu slideshare.vn bạn muốn tải, click vào nút Download màu xanh lá cây ở phía trên.

Bước 2: Tại liên kết tải về, bạn chọn liên kết để tải File về máy tính. Tại đây sẽ có lựa chọn tải File được lưu trên slideshare.vn

Bước 3: Một thông báo xuất hiện ở phía cuối trình duyệt, hỏi bạn muốn lưu . - Nếu click vào Save, file sẽ được lưu về máy (Quá trình tải file nhanh hay chậm phụ thuộc vào đường truyền internet, dung lượng file bạn muốn tải)

Có nhiều phần mềm hỗ trợ việc download file về máy tính với tốc độ tải file nhanh như: Internet Download Manager (IDM), Free Download Manager, ... Tùy vào sở thích của từng người mà người dùng chọn lựa phần mềm hỗ trợ download cho máy tính của mình

International Journal of Computer Networks and Communications Security
VOL. 2, NO. 12, DECEMBER 2014, 462–471 Available online at: www.ijcncs.org
ISSN 2308-9830
Improved Arithmetic on Elliptic Curves over Prime Field
NAJLAE FALAH HAMEED AL SAFFAR1 AND MOHAMAD RUSHDAN MD SAID2
1 Institute for Mathematical Research, Universiti Putra Malaysia,Malaysia
2 Department of Mathematics, Faculty of Mathematics and Computer Science,Kufa University,Iraq 2 Institute for Mathematical Research, Universiti Putra Malaysia,Malaysia
E-mail: 1najlae_falah@yahoo.com, 2mrushdan@upm.edu.my
ABSTRACT
A fast point doubling and point addition operations on an elliptic curve over prime field are proposed. This occur when we use a special coordinates system (to represent any point on elliptic curve over prime field. Using this system improved the elliptic curve point arithmetic by reducing the computation cost for point doubling and point addition operation.
Keywords: Elliptic curve cryptosystem, point arithmetic of elliptic curve, affine coordinates, projective coordinates and Jacobian coordinates.
1 INTRODUCTION elliptic curve scalar multiplication, denoted by kP
Elliptic curves are used for several kinds of cryptosystems, even it involved in key exchange protocols and digital signature algorithms [11], since it independently presented by Miller [20] and Koblitz [15] in the 1980s. Elliptic curve cryptography ECC has attracted attention in recent years due to it’s dependence on the difficulty of the elliptic curve discrete logarithm problem ( ECDLP ). Since there are no known subexponential time algorithms to solve the ECDLP, ECC supplies the same level of security with a shorter key size comparing with the well known public key cryptosystems based on the discrete logarithm problem ( DLP) and the integer factoring problem ( IFP) over finite fields such as RSA [23], DSA [18] and ElGamal [9]. Because of this singularity (requires a shorter key sizes are translated to less power and storage requirements, and reduced computing time comparing with another public cryptosystems) using ECC is recommended in resource constrained environments, such as mobile phones, PDAs and smart cards [3] [12]. Towards this end, considerable research has been performed to accelerate and improve this system, by focusing on the most important part of ECC which is
where P is a point on an elliptic curve E and k considered as a secret scalar. This basically means adding a point P on elliptic curve E , k times. Reducing the total computation time for this operation was the main focus for many researchers such as [8] [21].
The structure of the elliptic curve scalar multiplication operation involves three computational levels: field arithmetic, point arithmetic and scalar arithmetic [10] [19]. In this work, we will focus on developments at the elliptic curve point arithmetic level to accelerate the elliptic curve scalar multiplication.
The computation of the elliptic curve point arithmetic involves the effective implementation of point doubling and point addition operations. An elliptic curve can be represented using several coordinates systems. For each such system, the speed of point doubling and point addition operations is different. This means a good choice of coordinates system is an important factor for speeding up the elliptic curve scalar multiplication.
Due to the expensive cost of the field multiplication inversion involves in both point doubling and point addition operation with the arithmetic of the affine coordinates (x, y) , the
463
N. F. H. Al Saffar and M. R. Md Said / International Journal of Computer Networks and Communications Security, 2 (12), December 2014
projective coordinates systems were proposed. This means projective coordinates system offer an alternative method for efficient performance of the arithmetic of elliptic curve [24].
In 1986, Chudnovsky and Chudnovsky [6] used the Jacobian coordinates system to represent an affine point (x, y) as the triplet (X,Y,Z) , where
x = Z2 and y = Y3 . In 1993 Agnew et al. [1] the homogeneous projective coordinates systems was introduced, where a projective point (X,Y,Z)
corresponds to the affine point (x = Z , y = Z ) , whereas at the end of nineties LD coordinates system [25] was proposed, which an affine point
(x = X ,y = Y ) is presented as (X,Y,Z) using Z
elliptic curve over binary field. Significant effort to optimize the LD coordinates system performance has been carried out since it was introduced such as [16] [2] [17].
In 2007, Kim et al. [13] introduced the 4− dimensional coordinates system, where the point
(X,Y,Z,T2) corresponds to the affine point
(x = Z , y = T ) , with T = Z , on an elliptic curve over finite fields of characteristic three. In the same year, the same technique introduced by Kim and Kim [14] but on an elliptic curves over binary fields.
In this work, we introduce a modification on Jacobian coordinates, which gives faster point doubling and point addition operation than affine, projective, and Jacobian coordinates. Each point is presented by the 4− dimensional coordinates
(X = xT,Y = yZ3,Z,T = Z2) corresponding to the
affine point on a curve y2 = x3 + ax +b over Fp . The
basic technique of this work is to rewrite the point doubling and point addition operation on the elliptic curve with less costly field multiplication inversion, multiplication and squaring operation. Due to the discussion on the computation time for the point doubling and point addition operation on an elliptic curve, we will neglect the point addition, subtraction and multiplication by small constant in the prime field Fp since they are much faster than
field multiplication inversion and field multiplication operation. Throughout this work, I , M and S in italics, denote field multiplication inversion, multiplication and squaring operation
respectively.
2 PRELIMINARIES
In this section, we will give a brief review of the materials which is used in the current work. The interested reader may find additional information in [3] [24]. Also, for background on finite field we refer [5].
An elliptic curve E over an arbitrary field F denoted by E(F) is given by the Weierstrass equation [24] [7] as follows:
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 (1)
where a ,a2,a3,a4,a6 ∈ F, and Δ 0, where Δ denoted to the discriminant of E .
The set of points on E that solved the equation (1), together with a special point named point at infinity (denoted by O ) which is the identity for the group law, form an abelian group. This abelian group is used for the implementation of ECC .
Elliptic curve can be defined over finite fields, such as binary field or prime field. Furthermore, we can define elliptic curve over field of real number but only for algebraic geometry manner.
Over the prime field Fp , the equation (1)
simplifies as follows:
y2 = x3 + ax +b (2)
where a,b∈Fp and Δ = 4a3 + 27b2 0 .
Over the binary field F2m , equation (1) can be simplified to:
y2 + xy = x3 + ax2 +b (3) where a,b∈ F2m and Δ = b 0 .
Over the field of real number R , the elliptic curve is defined on equation (2) but with a,b∈ R and
Δ = 4a3 + 27b2 0 .
Theorem 2.1 [24]
Let P,Q ∈ E , L the line connecting P and Q (tangent line to E if P = Q ), and M the third point of intersection L with E . Let L' be the line
connecting M and O . Then the point P + Q is the third point on E , such that L' intersects E at M ,
O and P + Q .
The set E(F) of rational points on an elliptic curve E defined over a field F forms an abelian additive group. The additive operation is defined by the tangent and secant law. Figure 1 illustrate this operation geometrically [7] on special elliptic curve
over the real field, as an example if the target is to
464
N. F. H. Al Saffar and M. R. Md Said / International Journal of Computer Networks and Communications Security, 2 (12), December 2014
compute P + Q for P and Q are points on E , then we have to draw a line though P and Q which
intersects with the E at the third point M on E , the intersection between the vertical line and the E is P + Q .
Theorem 2.2 [24]
If a line L intersects E at the points Q,P,M (not necessarily distinct), then Q + P + M = O .
This means, when we need to find Q + P we have
to find M and then apply the negation formula for M .
Theorem 2.4 2.4 is the formula for point doubling operation, while theorem 2.4 2.4 represented the formula for point addition operation. So, the computation time for the point doubling operation is 1I + 2M + 2S and 1I + 2M +1S for the point addition operation in affine coordinates system.
To achieve efficiency, field multiplication inversion in group operations should be avoided, projective coordinates systems have ensured this requirement. There are different types of projective coordinates systems having the advantages in efficiency, such as ordinary projective coordinates
system where (x, y) = ( X , Y ), Jacobian coordinates
system where (x, y) = ( X , Y ), LD projective Z Z
coordinates system where (x, y) = ( X , Y ) and 4− Z
dimensional coordinates system (X,Y,Z,T) where
(x, y) = ( X , Y ) and T = Z 2 . Z
In the next section, we will give a brief review of the formulas for point doubling and point addition operation on elliptic curve over prime field but with various coordinates systems.
3 COORDINATES SYSTEMS
Fig. 1. Elliptic Curve Point Addition
The focus of this work will be with elliptic curve E defined over field of prime number Fp which is
denoted by E(Fp) given by equation (2).
In the rest of this section, the formulas for the inverse point, point doubling and point addition in the affine coordinates system are presented.
To avoid the field multiplication inversion in point doubling and point addition operation in affine coordinates system which is one I =1, points on elliptic curve are usually substituted with projective coordinates system.
In homogeneous coordinates system, a projective point (X,Y,Z) with Z 0 , corresponds to affine
point ( Z , Z ) . In this case the equation of elliptic
Theorem 2.3 [24]
Let P = (x0, y0) be point in E(Fp) . Then
curve will be:
Y 2Z = X 3 + aXZ 2 +bZ 3 (4)
−P = (x0,−y0) .
Theorem 2.4 [24]
Let P = (x1, y1) and P = (x2, y2) be points in E(Fp) .
1. If x1 = x2 . Then P + P = O .
2. If x1 = x2 but P −P . Then P + P = (x', y') where x'= m2 − x − x2, y'= m(x1 − x') − y1 and
m = 3x2y+ a .
3. If x1 x2 . Then P + P = (x3, y3)
where x3 = m2 − x1 − x2 , y3 = m(x1 − x3)− y1) and
y2 − y1 x2 − x1
In Jacobian coordinates system, a point (x, y) in
affine coordinates system is recovered as ( X , Y ) Z Z
with Z 0 . In this case the equation of elliptic curve will be:
Y 2 = X 3 + aXZ 4 +bZ 6 (5)
That means, the projective coordinates system can be identified with all points (x, y) of the affine coordinates system plus point (point at infinity O ) for which Z = 0 . Putting Z = 0 in equation (4) or (5), the O is (0,1,0) or (1,1,0) respectively, there is only one projective points that
satisfy the equation (4) and (5) for which Z = 0 .
465
N. F. H. Al Saffar and M. R. Md Said / International Journal of Computer Networks and Communications Security, 2 (12), December 2014
We have earlier mentioned the formulas for point doubling and point addition in the affine coordinates system section 2. Point doubling and point addition formulas for projective coordinates and Jacobian coordinates will be mentioned in the following subsections.
1) 3.1 The Point Doubling and Point Addition Formulas in Projective Coordinates System
The computation time for the point doubling operation is 7M +5S while it is 12M + 2S operations for point addition, as in the following theorems:
Theorem 3.1 [8]
Let P = (X ,Y,Z) be a point in a non singular elliptic curve in projective coordinates on E(Fp) . Then the
formula for the point doubling operation 2P = (X',Y',Z') is as follows
X'= 2BD
Y'= A(4C − D)−8Y2B2
Z'= 8B3
with A = 3X 2 + aZ 2 , B = YZ , C = XYB and D = A2 −8C .
For efficiency purposes, the constant a in equation 5 has been recommended to a fix −3 [10] [11] [4]. Without loss of generality, if we consider this case a = −3 in equation 5, the computation cost for A in theorem 3.1 is reduced as follows:
A = 3(X − Z)(X + Z)
The computation cost for point doubling operation is reduced to 8M + 3S .
Theorem 3.2 [8]
Let P = (X1,Y ,Z1) and P = (X2,Y2,Z2) be points in a non singular elliptic curve in projective coordinates on E(Fp) with P P . Then the
formula for the point addition operation P + P = (X3,Y3,Z3) is as follows
X3 = FG
Y3 = E(X1Z2F2 −G)
Z3 = Z1Z2F
with E = Y2Z1 −Y Z2, F = X2Z1 − X1Z2 and G = E2Z1Z2 − F3 − 2FX1Z2 .
From theorems 3.1 and 3.2 we have confirmation that a point doubling operation requires 7M +5S , while a point addition operation requires 12M + 2S. Now, if we consider Z = Z1 =1, the computation cost reduces to 5M + 3S for point doubling and
9M + 2S for point addition, while when Z2 =1 then
the computation cost reduces to 8M + 2S for point addition. The case where one point in affine coordinates and the other one in projective coordinates is referred to as a mixed point addition operation. Furthermore, If Z1 = Z2 =1, the computation cost for point addition drops to
4M + 2S .
2) 3.2 The Point Doubling and Point Addition Formulas in Jacobian Coordinates System
The computation time for the point doubling operation is 5M + 4S while it is 12M + 4S operations for point addition, as in the following theorems:
Theorem 3.3 [19]
Let P = (X ,Y,Z) be a point in a non singular elliptic curve in Jacobian coordinates on E(Fp) . Then the
formula for the point doubling operation 2P = (X ',Y',Z') is as follows:
X'= B2 − 2A
Y'= B(A− X3) −8Y 4
Z'= 2YZ
with A = 4XY2 and B = 3X 2 + aZ 4 .
If we consider the efficient case (a = −3 in equation 5), then the computation cost for B in theorem 3.3 is reduced as follows:
B = 3(X − Z2)(X + Z2)
That means, the computation cost for point doubling operation is reduced to 5M + 3S .
Theorem 3.4 [19]
Let P = (X1,Y ,Z1) and P = (X2,Y2,Z2) be points in a non singular elliptic curve in Jacobian coordinates on E(Fp) with P P . Then the formula for the
point addition operation P + P = (X3,Y3,Z3) is as follows
X3 = D2 − E3 −2X1Z2E2
Y3 = D(3X1Z2E2 − D2 + E3)−Y Z3E3 Z3 = Z3Z3E3
with D = Y2Z1 −Y Z2 and E = X2Z1 − X1Z2 .
From theorems 3.3 and 3.4 we have confirmation that a point doubling operation requires 5M + 4S , while a point addition operation requires 12M + 4S . Now, if we consider Z = Z1 =1, the computation cost reduces to 3M + 3S for point doubling and 10M +3S for point addition. While when Z2 =1 the computation cost for point addition will be 8M + 3S . This case, where one point in affine coordinates and
466
N. F. H. Al Saffar and M. R. Md Said / International Journal of Computer Networks and Communications Security, 2 (12), December 2014
the other one in Jacobian coordinates also as in the previous subsection 3.2 is referred to as a mixed point addition operation. Furthermore, If Z1 = Z2 =1 , the computation cost for point addition drops to
3M + 2S .
Using Jacobian coordinates system offer a faster point doubling than projective coordinates system. On other hand, it offer a slower point addition than projective coordinates system, which is usually the most frequent operation in elliptic curve scalar multiplication [22]. In the following section we will introduce new formula using 4− dimensional coordinates system (X,Y,Z,T) with Z 0
X'= A2 − 2B
Y'= A(B − X')−8Y4
Z'= 2YZ
with A = 3X 2 + aT 2 and B = 4XY2 .
Proof
We will prove that these formulas will lead to the point on non singular in affine coordinates on
E(Fp) . Suppose that x = X , y = Y and T = Z2 . We
will prove that x'= X' and y'= Y' , where (x', y') Z '
corresponds to the affine point ( X , Y ) with Z
is the result for point doubling in affine coordinates system.
T = Z2 .
4 NEW DESIGN POINT DOUBLING AND POINT ADDITION IN DIMENSIONAL JACOBIAN COORDINATES SYSTEM
In this section, we investigate a new design for point doubling and point addition on elliptic curve over prime field, using 4− dimensional coordinates
system, where an affine ( X , Y ) with Z 0 and Z
T = Z2 is presented as (X,Y,Z,T) . Due to the first two coordinates is as recovered point using Jacobian coordinates, we call this the 4− dimensional Jacobian coordinates system ( denoted by 4 − DJC ).
In other words, In 4 − DJC system, a point
(X,Y,Z,T) with Z 0 and T = Z2 , is corresponds to
affine point ( X , Y ) . In that case the equation of Z
elliptic curve will be:
Y 2 = X 3 + aXT 2 + bT 3 (6)
The first use of this formula was in 2007, by Kim and Kim [7] [14], but in both they used elliptic curves over fields of characteristic three and over binary fields.
3) 4.1 The Point Doubling and Point Addition Formulas in 4 − DJC
The computation time for the point doubling operation is 4M +3S while it is 12M + 2S operations for point addition, as in the following theorems:
X' (A)2 −2B T' 2Z'2
(3X 2 + aT2)2 −2(4XY2) 4Y2Z2
= (3X 2 + aT2)2 −2 X 2YZ
= (3X 2 + aT 2) Z3 2 − 2x 2T
2 2 3 + a)
= Y −2x Z3
= 3x2 + a −2x
= m − 2x m refers to the slope = x'
Y' A(B − X') −8Y4 Z3' 8Y3Z3
(3X 2 + aT2)(4XY2 − X') −8Y 4 8Y3Z3
(3X 2 + aT2)(4XY2 − X') Y 8Y3Z3 Z3
= 3X 2 + aT2 4XY2 − X' − y 4Y Z
= m 4XY2 − X' − y, 4Y Z 4Y Z
= m T − T' − y m refers to the slope
= m(x − x') − y
Theorem 4.1
Let P = (X,Y,Z,T) be a point in a non singular
= y'.
If we consider the efficient case where a = −3 in
elliptic curve in 4 − DJC on E(Fp) . Then the formula for the point doubling operation
2P = (X ',Y',Z',T') is as follows
equation 6, without loss of generality the computation cost for A in theorem 4.1 is reduced as follows:
B = 3(X −T)(X +T)
467
N. F. H. Al Saffar and M. R. Md Said / International Journal of Computer Networks and Communications Security, 2 (12), December 2014
That means, the computation cost for point doubling operation is reduced to 5M + 2S .
Y3 D(X1T2C2 − X3)−Y Z2T2C3 Z3 Z3Z3C3
Theorem 4.2
Let P = (X1,Y ,Z1,T ) and P = (X2,Y2,Z2,T2) be points in a non singular elliptic curve in 4 − DJC on E(Fp) . Then the formula for the point addition
operation P + P = (X3,Y3,Z3,T3) is as follows X3 = D2 −C3 − 2X1T2C2
Y3 = D(X1T2C2 − X3) −Y Z2T2C3
Z3 = Z1Z2C
with C = X2T − X1T2 and B = Y2Z1T −Y Z2T2 .
Proof
We will prove that these formulas will lead to the point on non singular in affine coordinates on
E(Fp). Suppose that x1 = X1 , y1 = Y3 , T = Z2 , 1
x2 = X2 , y2 = Y2 and T2 = Z2 . We will prove that 2
x3 = T3 and y3 = Z3 , where (x3, y3) is the result
for point doubling in affine coordinates system.
(Y2Z T −Y Z2T2)(X T2(X2T − X1T2)2 − X3) −Y Z2T2(X2T − X1T2)3 Z3Z3(X2T − X T2)3
(Y2Z3 −Y Z3)(X T2(X2T − X T2)2 − X3) −Y Z2T2(X2T − X T2)3 Z3Z3(X2T − X T2)3
Y2Z1 −Y Z2 X1T2(X2T − X1T2)2 − X3 1 Z1Z2(X2T − X1T2) T T2(X2T − X1T2)2 Z1
= m X1 − X3 − y m refers to the slope 1 3
= m(x1 − x3)− y1
= y3.