Module 3- Elliptic curves

MODULE- 3

ELLIPTIC CURVES, KEY MANAGEMENT AND DISTRIBUTION

Elliptic Curve :

Elliptic-curve cryptography (ECC) is an approach to public-key

cryptography based on the algebraic structure of elliptic curves over finite fields.
 Elliptic curves are applicable for key agreement, digital signatures, pseudo-
random generators and other tasks. Indirectly, they can be used
for encryption by combining the key agreement with a symmetric
encryption scheme.
 Elliptic curves are also used in several integer factorization algorithms based
on elliptic curves that have applications in cryptography, such as Lenstra
elliptic-curve factorization.
 The use of elliptic curves in cryptography was suggested independently
by Neal Koblitz and Victor S. Miller in 1985. Elliptic curve cryptography
algorithms entered wide use in 2004 to 2005.

Elliptic Curve Architecture:

Majority of public-key cryptography encryption algorithms like RSA, DH use

either integer or polynomial arithmetic with very large numbers/polynomials
Imposes a significant load in storing and processing keys and messages
An alternative is to use Elliptic Curve Cryptography (ECC)
Offers same security with smaller key size, thereby reducing the processing
overhead.
To know in detail about ECC, first we have to know about the following:
o Abelian groups

o Elliptic curves over real numbers

Availaible at VTU HUB (Android App)

Prof. Syed Matheen Pasha. Dept of CSE, SVIT Page 1
 Module 3- Elliptic curves
o Elliptic curves over finite fields
o Elliptic curves ciphers
Abelian groups:
 An abelian group G, denoted by {G, . }, is a set of elements with a binary
operation, denoted by .
(A1) Closure: If a and b belong to G, then a . b is also in G
(A2) Associative: a . (b . c) = (a . b) . C for all a, b, c in G
(A3) Identity element: There is an element e in G such that a . e = e . a = a
for all a in G
(A4) Inverse element: For each a in G there is an element a’ in G such that
a . a‘ = a’ . a =e
(A5) Commutative: a . b = b . a for all a, b in G
 For elliptic curve cryptography, an operation over elliptic curves, called
addition is used.
 Multiplication is defined by repeated addition.

Elliptic curves over real numbers:

 Elliptic curves are not ellipses
 Described by cubic equations, similar to those used for calculating the
circumference of an ellipse.
y2 + ax + by = x3 + cx2 + dx + e
 It is sufficient to limit this equation of the form
y2 = x3 + ax+ b
Where a,b are all real numbers and x, y take on values in the real numbers.
 An elliptic curve is defined by an equation in two variables x & y, with
coefficients.
 Cubic equation or of degree 3, coz the highest exponent they contain is 3.
 Elliptic curve is a single element denoted O, called the point at infinity or
the zero point.

Availaible at VTU HUB (Android App)

Prof. Syed Matheen Pasha. Dept of CSE, SVIT Page 2
 Module 3- Elliptic curves
Geometric description of addition:
 If 3 points on an elliptic curve lie on a straight line, their sum is O.

Rules of addition over elliptic curve:

1. O serves as an additive element. Thus O = - O, and for any point P on the
curve, P + O = P
2. If P = (x , y) and –P = (x, -y), then P + (- P) = O
3. To add two points P and Q with different coordinates, draw a straight line
between them and find the third point of intersection R.
4. P + Q = - R, thus P + Q is the mirror image of the third point of intersection.
5. To double a point Q, draw the tangent line and find the other point of
intersection S
Q + Q = 2Q = S

Algebraic description of addition:

1. If P = (xp, yp) and Q = (xq, yq), then R = P + Q = (xr, yr)
xr = ∆2 – xp – xq
yr = -yp + ∆ (xp – xr)
where ∆ = (yq - yp ) / (Xq - Xp )

Elliptic curves over finite fields:

 Elliptic curve cryptography uses curves whose variables & coefficients are
finite
 Have two families of elliptic curves:
 Prime curves Ep(a,b) defined over Zp
o Use integers modulo a prime p
o Best in software
 Binary curves E2m(a,b) defined over GF(2m)
o Use polynomials with binary coefficients
o Best in hardware

Elliptic curves defined over Zp :

 For elliptic curves over Zp, a cubic equation in which the variables and
coefficients all take on the values in the set of integers from 0 through p-1.
 Equation for elliptic curves over Zp is denoted by
y2 mod p = (x3 + ax + b) mod p
Rules of addition over an elliptic curve:
1. P + O = P
2. If P = (xp , yp), then P + (xp, -yp) = O
3. If P = (xp , yp) and Q = (xq , yq) with P ≠ Q, then R = P + Q = (xr, yr)
xr = λ2 –xp – xq) mod p
yr = (λ (xp- xr) – yp) mod p

Availaible at VTU HUB (Android App)

Prof. Syed Matheen Pasha. Dept of CSE, SVIT Page 3
 Module 3- Elliptic curves
where λ = [(yq – yp)/ (xq- xp) ] mod p if P ≠ Q
λ = [(3xp2 + a)/ (2yp) ] mod p if P = Q
4. Multiplication is defined as repeated addition: 4Q = Q + Q + Q + Q

Elliptic curves defined over GF(2m):

 Equation for elliptic curves over GF(2m) is denoted by
y2 + xy = x3 + ax2 + b
Rules for addition over an elliptic curve:
1. P + O = P
2. If P = (xp , yp), then P + (xp, xp+yp) = O. The point (xp, xp+yp) is the negative
of , i.e, -P
3. If P = (xp , yp) and Q = (xq , yq) with P ≠ - Q and P ≠ Q, then R = P + Q = (xr,
yr)
xr = λ2 + λ +xp + xq + a
yr = (λ (xp+ xr) + xr + yp
where λ = [(yq + yp)/ (xq +xp) ]
4. If P = (xp , yp) and R = P + P = P = (xr , yr), then
x r = λ2 + λ + a
yr = (xp2+ λ + 1) xr
Where
λ = xp + (yp /xp)

Elliptic curve cryptography:

 ECC addition is analog of modular multiplication in RSA
 ECC repeated addition is analog of modular exponentiation
 Need “hard” problem equivalent to discrete log
 Q=kP, where Q, P belong to a prime curve
o Is “easy” to compute Q given k, P
o But “hard” to find k given Q, P
o Known as the discrete logarithm problem of elliptic curve.

ECC Diffie-Hellman:
 Can do key exchange using ECC that is analogous to D – H
 Select global parameters:
o Eq(a, b)  elliptic curve with parameters a, b and q, where q is a
prime number
o G (x1,y1) (base point)  point on elliptic curve whose order is large
value n
 User A key generation:
o Select private key nA  nA<n
o Calculate public key PA=nA G
 User B key generation:

Availaible at VTU HUB (Android App)

Prof. Syed Matheen Pasha. Dept of CSE, SVIT Page 4
 Module 3- Elliptic curves
o Select private key nB  nB<n
o Calculate public key PB=nB G
 Generation of secret keys:
o KA=nA PB
o KB=nB PA

ECC Encryption/Decryption:
 First task in this system is to encode the plaintext message M as a point (x-y
coordinates) on elliptic curve Pm
 Then this Pm will be encrypted as a ciphertext and it will be decrypted.
 Each user chooses private key nA<n & computes public key PA=nA G
 To encrypt Pm : Cm={k G, Pm + kPb}, k random
 To decrypt Cm compute:
 Pm =Cm+ kPb –nB (k G)
= Cm+k(nBG)–nB(k G)

ECC Security:
 Relies on elliptic curve logarithm problem
 Fastest method to take the elliptic curve logarithm is “pollard rho method”
 Factoring a number into two primes using the general field sieve.

Advantages:
 Smaller key size can be used for ECC compared to RSA
 For equivalent key lengths, the computational effort required for ECC and
RSA is comparable.
 Computational advantage of ECC is the usage of much smaller key size.

Availaible at VTU HUB (Android App)

Prof. Syed Matheen Pasha. Dept of CSE, SVIT Page 5