Improved arithmetic on elliptic curves over prime field

Đăng ngày 4/2/2019 4:00:52 PM | Thể loại: | Lần tải: 0 | Lần xem: 6 | Page: 10 | FileSize: 0.29 M | File type: PDF
Improved arithmetic on elliptic curves over prime field. 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.
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
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
same
level
of
security
with
a
shorter
key
size
curve point arithmetic level to accelerate the elliptic
comparing
with
the
well
known
public
key
curve scalar multiplication.
cryptosystems
based
on
the
discrete
logarithm
The
computation
of
the
elliptic
curve
point
problem ( DLP) and the integer factoring problem (
arithmetic involves the effective implementation of
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
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
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
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
2
3
X Y
2
Z
X Y
1
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
2
PRELIMINARIES
means
projective
coordinates
system
offer
an
alternative method for efficient performance of the
In this section, we will give a brief review of the
arithmetic of elliptic curve [24].
materials which is used in the current work. The
In 1986, Chudnovsky and Chudnovsky [6] used
interested reader may find additional information in
the Jacobian coordinates system to represent an
[3] [24]. Also, for background on finite field we
affine point
(x, y)
as the triplet
(X,Y,Z) , where
refer [5].
x = X and y = Y . In 1993 Agnew et al. [1] the
Z Z
homogeneous projective coordinates systems was
introduced, where a projective point (X,Y,Z)
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)
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
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)
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
where a,bFp and Δ = 4a3 + 27b2 0 .
Over the binary field F2m , equation (1) can be
simplified to:
on Jacobian coordinates, which gives faster point
doubling and point addition operation than affine,
projective, and Jacobian coordinates. Each point is
presented by the 4dimensional coordinates
(X = xT,Y = yZ3,Z,T = Z2) corresponding to the
affine point on a curve y2 = x3 + ax +b over Fp . The
y2 + xy = x3 + ax2 +b (3)
where a,bF2m and Δ = b 0 .
Over the field of real number R , the elliptic curve
is defined on equation (2) but with a,bR and
Δ = 4a3 + 27b2 0 .
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.
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
X Y
2 3
2
Z
3
T
X Y
0
0
1 2
1 2
1 2 1 2
1
2 3
2
2
1
1 2
.
m =
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
Theorem 2.4 2.4 is the formula for point doubling
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 .
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.
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 .
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) = ( Z , Z ), Jacobian coordinates
system
where
(x, y) = ( X , Y ), LD
Z Z
projective
coordinates system where
(x, y) = ( X , Y ) and
Z
4
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
To
avoid
the
field
multiplication
inversion
in
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.
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) .
In Jacobian coordinates system, a point (x, y) in
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
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)
m = 3x1y+ a .
3. If x1 x2 . Then P + P = (x3, y3)
where x3 = m2 x1 x2 , y3 = m(x1 x3)y1)
y2 y1
x2 x1
and
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 .
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  
6 lần xem

Improved arithmetic on elliptic curves over prime field. 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..

Nội dung

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.