Brandenburg Technical University of Cottbus Computer Networking Group
A Tutorial on Elliptic Curve Cryptography (ECC) Fuwen Liu
[email protected]
A Tutorial on Elliptic Curve Cryptography
Contents I.
Introduction
II.
Elliptic Curves over Real Number
III. Elliptic Curves over Prime Field and Binary Field IV. Security Strength of ECC System V.
ECC Protocols
VI. Patents and Standards VII. Final Remarks
A Tutorial on Elliptic Curve Cryptography
2
Fuwen Liu
I. Introduction
A Tutorial on Elliptic Curve Cryptography
3
Fuwen Liu
Basic concept Cryptography is a mathematical based technology to ensure the information security over a public channel. There are two objectives: Privacy: No information is accessible to unauthorized parties Authentication: Information is not alerted in transition and the communication parties are legitimate. Cryptography systems can be distinguished in two categories[1]: Unconditionally secure system: It resist any cryptanalytic attack no matter how much computation is used. One-time pad system is a typical example Require the length of the key stream equivalent to that of plaintext Rarely deployed in practice
Conditionally secure system: It is computationally infeasible to be broken, but would succumb to an attack with unlimited computation. Basically modern cryptographic systems are constructed on the basis of the conditionally secure principle.
A Tutorial on Elliptic Curve Cryptography
4
Fuwen Liu
Motivation Public key cryptographic algorithms (asymmetric key algorithms) play an important role in providing security services: Key management User authentication Signature Certificate Public key cryptography systems are constructed by relying on the hardness of mathematical problems RSA: based on the integer factorization problem DH: based on the discrete logarithm problem The main problem of conventional public key cryptography systems is that the key size has to be sufficient large in order to meet the high-level security requirement. This results in lower speed and consumption of more bandwidth Solution: Elliptic Curve Cryptography system A Tutorial on Elliptic Curve Cryptography
5
Fuwen Liu
History of ECC In 1985, Neal Koblitz [2] and Victor Miller [3] independently proposed using elliptic curves to design public key cryptographic systems. In the late 1990`s, ECC was standardized by a number of organizations and it started receiving commercial acceptance. Nowadays, it is mainly used in the resource constrained environments, such as ad-hoc wireless networks and mobile networks. There is a tend that conventional public key cryptographic systems are gradually replaced with ECC systems. As computational power evolves, the key size of the conventional systems is required to be increased dramatically.
A Tutorial on Elliptic Curve Cryptography
6
Fuwen Liu
II. Elliptic Curves over Real Numbers
A Tutorial on Elliptic Curve Cryptography
7
Fuwen Liu
Overview Elliptic curves have been studied by mathematicians for over a hundred years. They have been deployed in diverse areas Number theory: proving Fermat`s Last Theorem in 1995 [4] The equation x n + y n = z n has no nonzero integer solutions for x,y,z when the integer n is grater than 2.
Modern physics: String theory The notion of a point-like particle is replaced by a curve-like string.
Elliptic Curve Cryptography
An efficient public key cryptographic system.
A Tutorial on Elliptic Curve Cryptography
8
Fuwen Liu
Definition An elliptic curve E over R (real numbers) is defined by a Weierstrass equation
E : y 2 + a1 xy + a3 y = x3 + a2 x 2 + a4 x + a6 where a1, a2, a3, a4,a5 ∈K and∆‡0. ∆ is the discriminant of E and is defined as follows: 2 3 2 ∆ = −d 2 d8 − 8d 4 − 27d 6 + 9d 2d 4d 6
d 2 = a12 + 4a2 d 4 = 2a4 + a1a3 d 6 = a32 + 4a6 d8 = a12a6 + 4a2a6 − a1a3a4 + a2a32 − a42
Points: If both the coordinates of the point P∈ ∈E or P=∞ ∞ (the point at infinity, or zero element ࣩ). The set of points on E is:
E ( L) = {( x, y) ∈ R × R : y 2 + a1xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0} ∪ {ο} A Tutorial on Elliptic Curve Cryptography
9
Fuwen Liu
Simplified Weierstrass Equations The Weierstrass equations can be simplified by performing the following change of variables:
and set
a1 = 0, a3 = 0
a2 a1 x + a3 ( x, y ) → ( x − , y − ) 3 2
a = 1 / 9a22 + a4 , b = 2 / 27a23 − 1 / 3a2a4a6
we get one of the simplified Weierstrass equations: y
2
= x 3 + ax + b
By performing the following change of variables:
a3 3 a12a4 + a32 ( x, y ) → (a x + , a1 y + ) 3 a1 a1 2 1
We get another important simplified Weiertstrass equations:
y 2 + xy = x 3 + ax 2 + b A Tutorial on Elliptic Curve Cryptography
10
Fuwen Liu
Example Curves of y 2 = x 3 + ax + b
A Tutorial on Elliptic Curve Cryptography
11
Fuwen Liu
Addition law Addition law of elliptic curve E has the following properties: Identity: Inverse:
P+ࣩ=ࣩ+P=P P+(-P)=ࣩ
Associative: P+(R+Q)=(P+R)+Q Commutative: P+Q=Q+R
∀ P∈ E ∀ P∈ E ∀ P,Q,R∈ E ∀ P, Q∈ E
The addition law makes the points of E into an abelian group.
A Tutorial on Elliptic Curve Cryptography
12
Fuwen Liu
Point addition Geometry approach: To add two distinct points P and Q on an elliptic curve, draw a straight line between them. The line will intersect the elliptic cure at exactly one more point –R. The reflection of the point –R with respect to x-axis gives the point R, which is the results of addition of points R and Q -R
A Tutorial on Elliptic Curve Cryptography
13
Fuwen Liu
Point doubling Geometry approach: To the point P on elliptic curve, draw the tangent line to the elliptic curve at P. The line intersects the elliptic cure at the point –R. The reflection of the point –R with respect to x-axis gives the point R, which is the results of doubling of point P. -R
P
R=2P
A Tutorial on Elliptic Curve Cryptography
14
Fuwen Liu
Algebraic Formulae of Point Addition For the curve E: y 2 = x 3 + ax + b . Let P=(xP,yP) and Q=(xQ,yQ) ∈ E with P≠Q, then R=P+Q=(xR,yR) is determined by the following formulae: x R = λ2 − x P − xQ yR = λ ( x p − xR ) − yP where : λ =
yQ − y P xQ − x p
In the same way, for the curve E: y + xy = x + ax + b. R=P+Q=(xR,yR) can be determined by the following formulae: 2
3
2
x R = λ 2 + λ + x P + xQ + a yR = λ ( x p + xR ) + xR + yP where : λ =
A Tutorial on Elliptic Curve Cryptography
yQ + y P xQ + x p
15
Fuwen Liu
Algebraic Formulae of Point Doubling For the curve E: y 2 = x 3 + ax + b . Let P=(xP,yP) ∈ E with P≠-P, then R=2P=(xR,yR) is determined by the following formulae: x R = λ2 − 2 x P yR = λ ( x p − xR ) − yP 3 x P2 + a where : λ = 2yp
In the same way, for the curve E: y + xy = x + ax + b. R=2P=(xR,yR) can be determined by the following formulae: 2
3
2
x R = λ2 + λ + a y R = x P2 + λ x R + x R where : λ = x P + y P / x P
A Tutorial on Elliptic Curve Cryptography
16
Fuwen Liu
Example of Point Addition
Point addition in the curve y 2 = x 3 − 7 x x R = λ 2 − x P − x Q = 1 . 1982
2
+ 2 . 35 + 0 . 1 = 3 . 89
y R = λ ( x p − x R ) − y P = 1 . 1982 ( − 2 . 35 − 3 . 89 ) + 1 . 86 = − 5 . 62 where : λ =
yQ − y P xQ − x p
=
0 . 836 + 1 . 86 = 1 . 1982 − 0 . 1 + 2 . 35
(From www.certicom.com)
A Tutorial on Elliptic Curve Cryptography
17
Fuwen Liu
Example of Point Doubling
Point doubling in the curve y 2 = x 3 − 3x + 5 x R = λ 2 − 2 x P = 1 . 698 2 − 2 ∗ 2 = − 1 . 11 y R = λ ( x p − x R ) − y P = 1 . 698 ( 2 + 1 . 11 ) − 2 . 65 = 2 . 64 3 x P2 + a 3 ∗ 2 2 + ( − 3) where : λ = = = 1 . 698 2 yp 2 ∗ 2 . 65
(From www.certicom.com)
A Tutorial on Elliptic Curve Cryptography
18
Fuwen Liu
III. Elliptic Curves over Prime Field and Binary Field
A Tutorial on Elliptic Curve Cryptography
19
Fuwen Liu
Motivation Elliptic curves over real numbers Calculations prove to be slow Inaccurate due to rounding error Infinite field Cryptographic schemes need fast and accurate arithmetic In the cryptographic schemes, elliptic curves over two finite fields are mostly used. Prime field Fp , where p is a prime. Binary field F2m, where m is a positive integer.
A Tutorial on Elliptic Curve Cryptography
20
Fuwen Liu
EC over Fp The equation of the elliptic curve over Fp is defined as: y 2 mod p = ( x 3 + ax + b ) mod p where : ( 4 a 3 + 27 b 2 ) mod p ≠ 0 x , y , a , b ∈ [0 , p − 1 ]
The points on E are denoted as: E(Fp )={(x,y):x,y∈Fp satisfy y2=x3+ax+b}∪{ࣩ} Example: Elliptic curve y 2 = x 3 + x over the Prime field F23. The points in the curve are the Following: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)
(From www.certicom.com) A Tutorial on Elliptic Curve Cryptography
21
Fuwen Liu
Point Addition and Doubling for EC over Fp
Point addition: x R = ( λ 2 − x P − x Q ) mod p y R = ( λ ( x p − x R ) − y P ) mod p where : λ =
yQ − y P xQ − x p
mod p
Point doubling: x R = ( λ 2 − 2 x P ) mod p y R = ( λ ( x p − x R ) − y P ) mod p 3 x P2 + a where : λ = mod p 2yp
A Tutorial on Elliptic Curve Cryptography
22
Fuwen Liu
Example for point addition and doubling Let P=(1,5) and Q=(9,18) in the curve y 2 = x 3 + x over the Prime field F23. Then the point R(xR,yR) can be calculated as 18 − 5 13 1 mod 23 = mod 23 = 13 mod 23 × mod 23 = 13 × 3 mod 23 = 16 9 −1 8 8 x R = (16 2 − 1 − 9 ) mod 23 = 246 mod 23 = 16
λ =
y R = (16 (1 − 16 ) − 5 ) mod 23 = − 245 mod 23 = − 15 mod 23 = 8 So the R=P+Q=(16,8) The doubling point of P can be computed as: 3 × 12 + 1 2 1 mod 23 = mod 23 = 2 mod 23 × mod 23 = 2 × 14 mod 23 = 5 λ = 2×5 5 5 x R = ( 5 2 − 1 − 1 ) mod 23 = 23 mod 23 = 0
y R = ( 5 (1 − 0 ) − 5 ) mod 23 = 0 mod 23 = 0
So the R=2P=(0,0) Point addition and doubling need to perform modular arithmetic (addition, subtraction, multiplication, inversion) A Tutorial on Elliptic Curve Cryptography
23
Fuwen Liu
EC over F2m A elliptic curve E over the finite field F2m is given through the following equation.
y 2 + xy = x 3 + ax
2
+b
Where x, y, a, b ∈ F2m The points on E are denoted as: E(F2m)={(x,y):x,y∈F2m satisfy y2+xy=x3+ax2+b}∪{O}
A Tutorial on Elliptic Curve Cryptography
24
Fuwen Liu
Example Elliptic Curve over F2m Assume the finite field F24 has irreducible polynomial f(x)=x4+x+1. The element g = (0010) is a generator for the field . The powers of g are: g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011) g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g9 = (1010) g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001) g15 = (0001)
Consider the elliptic curve y2 + xy = x3 + g4x2 + 1. The points on E are: (1, g13) (g3, g13) (g5, g11) (g6, g14) (g9, g13) (g10, g8) (g12, g12) (1, g6) (g3, g8) (g5, g3) (g6, g8) (g9, g10) (g10, g) (g12, 0) (0, 1)
(From www.certicom.com)
A Tutorial on Elliptic Curve Cryptography
25
Fuwen Liu
Point Addition and Doubling over F2m
Let P=(xP, yP), Q=(xQ,yQ) on the curve Then R=P+Q can be computed: x R = λ 2 + λ + x P + xQ + a
y 2 + xy = x 3 + ax
2
+b
yR = λ ( x p + xR ) + xR + yP where : λ =
yQ + y P xQ + x p
Let P=(xP, yP) on the curve curve Then R=2P can be computed:
y 2 + xy = x 3 + ax
2
+b
x R = λ2 + λ + a y R = x P2 + λ x R + x R where : λ = x P + y P / x P
Note that all calculations are performed using the rules of arithmetic in F2m
A Tutorial on Elliptic Curve Cryptography
26
Fuwen Liu
An Example of Point Addition and Doubling over F2m
Let P=(g5, g3), Q=(g9,g13) on the curve y 2 Then R(xR, yR)=P+Q can be computed: yQ + y P g 3 + g 13 g8 2 = 5 = = g λ = xQ + x p g + g9 g6
+ xy = x 3 + g 4 x 2 + 1
x R = λ 2 + λ + x P + xQ + a = ( g 2 ) 2 + g 2 + g 5 + g 9 + g 4 = g 3 y R = λ ( x p + x R ) + x R + y P = g 2 ( g 5 + g 3 ) + g 3 + g 3 = g 13
Let P=(xP, yP) on the curve curve y 2 + xy = x 3 Then R=2P can be computed: λ = x P + y P / x P = g 5 + g 3 / g 5 = g 5 + g 13 = g 7
+ ax + b
x R = λ2 + λ + a = ( g 7 )2 + g 7 + g 4 = 1 y R = x P2 + λ x R + x R = ( g 5 ) 2 + g 7 + 1 = g 13
Point addition and doubling need to perform the polynomial arithmetic ( addition, subtraction, multiplication, and division) A Tutorial on Elliptic Curve Cryptography
27
Fuwen Liu
Point Representation The normal (x, y) pairs are denoted as affine coordinates. It has disadvantages in performing point addition and doubling. Expensive inverse operations are involved. The normal (x, y) pairs can be represented by the triplet (X, Y, Z), which is called the projective coordinates. The relationship between (x, y) and (X, Y,Z) is: ( X ,Y , Z ) = (λc x , λd y , λ ) ( x, y ) = ( X / Z c ,Y / Z d ) where : λ ≠ 0
There are a number of types of coordinates when c, d are set different values, such as standard[5], Jacobian[5], Lopez-Dahab[6]. The use of projective coordinates can avoid the expensive inverse operations. But it requires more multiplications in the field operation. If the ratio of Inverse/Multiplication is big, the resulting computation cost of point addition is less than that using affine coordinates.
A Tutorial on Elliptic Curve Cryptography
28
Fuwen Liu
Usage of Elliptic Curves An elliptic curve over Fp is defined as prime curve. An elliptic curve over F2m is defined as binary curve. As pointed out in [7], prime curves are best for software applications. They do not need the extended bit-fiddling operations required by binary curves.
As shown in [7], binary curves are best for hardware applications. They can takes less logic gates to create a cryptosystem compared to prime curves.
A Tutorial on Elliptic Curve Cryptography
29
Fuwen Liu
Elliptic Curve Cryptography (ECC) Elliptic curves are used to construct the public key cryptography system The private key d is randomly selected from [1,n-1], where n is integer. Then the public key Q is computed by dP, where P,Q are points on the elliptic curve. Like the conventional cryptosystems, once the key pair (d, Q) is generated, a variety of cryptosystems such as signature, encryption/decryption, key management system can be set up. Computing dP is denoted as scalar multiplication. It is not only used for the computation of the public key but also for the signature, encryption, and key agreement in the ECC system.
A Tutorial on Elliptic Curve Cryptography
30
Fuwen Liu
Scalar Multiplication Intuitive approach: dP= P+P+…+P d times
It requires d-1 times point addition over the elliptic curve. Observation: To compute 17 P, we could start with 2P, double that, and that two more times, finally add P, i.e. 17P=2(2(2(2P)))+P. This needs only 4 point doublings and one point addition instead of 16 point additions in the intuitive approach. This is called Double-and-Add algorithm.
A Tutorial on Elliptic Curve Cryptography
31
Fuwen Liu
Double-and-Add algorithm Let d=(dt-1, dt-2,…d0) be the binary representation of d, then d =
t −1
∑d i=0
i
2i
t −1
dP = ( ∑ d i 2 i ) P = ( d t − 1 2 t − 1 P ) + ... + ( d 1 2 P ) + d 0 P i=0
= 2 ( 2 (... 2 ( 2 d t − 1 P ) + d t − 2 P ) + ...) + d 1 P ) + d 0 P
Double-and-Add algorithm: Input: d=(dt-1, dt-2,…d0) , P∊E. 1. Q←O 2. For i from 0 to t-1 do 2.1 If di=1 then Q←Q+P 2.2 P←2P Output: dP=Q
A Tutorial on Elliptic Curve Cryptography
32
Fuwen Liu
IV. Security Strength of ECC System
A Tutorial on Elliptic Curve Cryptography
33
Fuwen Liu
Complexity of an Algorithm Definition: Let A be an algorithm whose input has bit-length n A is a polynomial-time algorithm if its running time is O(nc) for some constant c>0, such as n10 1/3
A is a subexponential-time algorithm if its running time is O(eo(n)), such as en . A is an exponential-time algorithm if its running time is O(cn) or O(nf(n)) for c>1, 2 such as 1.1n and nn .
Fuwen Liu
Security of Public Key Cryptosystems A Public key cryptosystem is constructed on the basis of hardness of some mathematic problems. RSA depends on the intractability of factoring problem DH protocol relies on the hardness of discrete logarithm ECC is secure due to the elliptic curve discrete logarithm problem (ECDLP).
A public key cryptosystem consist of a private key that is kept secret, and a public key which is accessible to the public. The straightforward way to break the public key cryptosystem is to draw the private key from the public key. But the required computation cost is equivalent to solving these difficult mathematic problems.
Fuwen Liu
RSA RSA key pair generation. Randomly select two large primes p and q, and p≠q Compute n=pq and ø=(p-1)(q-1) Select an arbitrary integer e with 1
