Elliptic Curve Cryptography

Outline
• Introduction to Elliptic Curves

• Elliptic Curve Cryptosystems (ECC)

Introduction to Elliptic Curves
 Graphical Representation

Y axis

X axis

Curves of this nature

are called ELLIPTIC
CURVES
 Elliptic curves in Cryptography
• Elliptic Curve (EC) systems as applied to
cryptography were first proposed in 1985
independently by Neal Koblitz and Victor Miller.

• The discrete logarithm problem on elliptic curve

groups is believed to be more difficult than the
corresponding problem in (the multiplicative
group of nonzero elements of) the underlying
finite field.
 Discrete Logarithms
in Finite Fields
F={1,2,3,…,p-1}
Pick secret, random
Pick secret, random Y from F
X from F
gx mod p
gy mod p
Alice Bob
Compute k=(gy)x=gxy mod p
Compute k=(gx)y=gxy mod p
Eve has to compute gxy from gx and gy without knowing x and y…
She faces the Discrete Logarithm Problem in finite fields
Elliptic Curve on a finite set of
Integers
• Consider y2 = x3 + 2x + 3 (mod 5)
x = 0 ⇒ y2 = 3 ⇒ no solution (mod 5)
x = 1 ⇒ y2 = 6 = 1 ⇒ y = 1 (mod 5)
x = 2 ⇒ y2 = 15 = 0 ⇒ y = 0 (mod 5)
x = 3 ⇒ y2 = 36 = 1 ⇒ y = 1 (mod 5)
x = 4 ⇒ y2 = 75 = 0 ⇒ y = 0 (mod 5)
• Then points on the elliptic curve are
(1,1) (2,0) (3,1) (4,0) and the point
at infinity: ∞
 Definition of Elliptic curves
• An elliptic curve over a field K is a nonsingular
cubic curve in two variables, f(x,y) =0 with a
rational point (which may be a point at infinity).

• The field K is usually taken to be the complex

numbers, reals, rationals, algebraic extensions
of rationals, p-adic numbers, or a finite field.

• Elliptic curves groups for cryptography are

examined with the underlying fields of Fp (where
p>3 is a prime) and F2m (a binary representation
with 2m elements).
 General form of a EC
• An elliptic curve is a plane curve defined by an
equation of the form

y = x + ax + b
2 3

Examples
Points on the Elliptic Curve (EC)
• Elliptic Curve over field L
E ( L) = {∞} ∪ {( x, y ) ∈ L × L | y 2 + ... = x3 + ...}

• It is useful to add the point at infinity

• The point is sitting at the top of the y-axis
and any line is said to pass through the
point when it is vertical
• It is both the top and at the bottom of the
y-axis
 The Abelian Group
Given two points P,Q in E(Fp), there is a third
point, denoted by P+Q on E(Fp), and the
following relations hold for all P,Q,R in E(Fp)

• P + Q = Q + P (commutativity)

• (P + Q) + R = P + (Q + R) (associativity)

• P + O = O + P = P (existence of an identity element)

• there exists ( − P) such that − P + P = P + ( − P)

= O (existence of inverses)
 Elliptic Curve Picture

y
• Consider elliptic curve
E: y2 = x3 - x + 1
P2 • If P1 and P2 are on E, we
P1
can define
x
P3 = P1 + P2
P3 as shown in picture
• Addition is all we need
 Addition in Affine Co-ordinates
y=m(x-x1)+y1 P = ( x1 , y1 ), Q = ( x2 , y2 )
R = ( P + Q) = ( x3 , y3 )
y

Let, P≠Q,

y2 − y1
m= ;
x2 − x1
To find the intersection with E. we get
(m( x − x1 ) + y1 ) 2 = x 3 + Ax + B
x or , 0 = x 3 − m 2 x 2 + ...
So, x3 = m 2 − x1 − x2
y2=x3+Ax+B ⇒ y3 = m( x1 − x2 ) − y1
 Doubling of a point
• Let, P=Q
dy
2y = 3x 2 + A
dx
dy 3 x12 + A
⇒m= =
dx 2 y1
If , y1 ≠ 0 (since then P1 +P2 =∞):
∴ 0 = x3 − m 2 x 2 + ...
⇒ x3 = m 2 − 2 x1 , y3 = m( x1 − x3 ) − y1

• What happens when P2=∞?

Why do we need the reflection?

y P2=O=∞

P1=P1+ O=P1

P1
 Sum of two points
Define for two points P (x1,y1) and
Q (x2,y2) in the Elliptic curve

 y 2 − y1
 x − x for _ x1 ≠ x 2
λ =  22 1
 3 x1 + a for _ x1 = x 2
 2 y 1

Then P+Q is given by R(x3,y3) :

x3 = λ − x1 − x2
y3 = λ ( x3 − x1 ) + y1
 Point at infinity O

P+P = 2P

As a result of the above case P=O+P

O is called the additive identity of
the elliptic curve group.
Hence all elliptic curves have an
additive identity O.
 Projective Co-ordinates
• Two-dimensional projective space PK2 over K
is given by the equivalence classes of triples
(x,y,z) with x,y z in K and at least one of x, y,
z nonzero.
• Two triples (x1,y1,z1) and (x2,y2,z2) are said to
be equivalent if there exists a non-zero
element λ in K, st:
– (x1,y1,z1) = (λx2, λy2, λz2)
– The equivalence class depends only the ratios
and hence is denoted by (x:y:z)
 Outline
• Introduction to Elliptic Curves

• Elliptic Curve Cryptosystems

Elliptic Curve Cryptosystems
(ECC)
 What Is Elliptic Curve
Cryptography (ECC)?
• Elliptic curve cryptography [ECC] is a public-
key cryptosystem just like RSA, Rabin, and El
Gamal.
• Every user has a public and a private key.
– Public key is used for encryption/signature
verification.
– Private key is used for decryption/signature
generation.
• Elliptic curves are used as an extension to other
current cryptosystems.
– Elliptic Curve Diffie-Hellman Key Exchange
– Elliptic Curve Digital Signature Algorithm
 Using Elliptic Curves In
Cryptography
• The central part of any cryptosystem involving
elliptic curves is the elliptic group.
• All public-key cryptosystems have some
underlying mathematical operation.
– RSA has exponentiation (raising the message or
ciphertext to the public or private values)
– ECC has point multiplication (repeated addition of two
points).
 Generic Procedures of ECC
• Both parties agree to some publicly-known data items
– The elliptic curve equation
• values of a and b
• prime, p
– The elliptic group computed from the elliptic curve equation
– A base point, B, taken from the elliptic group
• Similar to the generator used in current cryptosystems
• Each user generates their public/private key pair
– Private Key = an integer, x, selected from the interval [1, p-1]
– Public Key = product, Q, of private key and base point
• (Q = x*B)
 Example – Elliptic Curve
Cryptosystem Analog to El Gamal
• Suppose Alice wants to send to Bob an
encrypted message.
– Both agree on a base point, B.
– Alice and Bob create public/private keys.
• Alice
– Private Key = a
– Public Key = PA = a * B
• Bob
– Private Key = b
– Public Key = PB = b * B
– Alice takes plaintext message, M, and encodes it onto
a point, PM, from the elliptic group
 Example – Elliptic Curve
Cryptosystem
– Alice chooses another random integer, k from the
interval [1, p-1]
– The ciphertext is a pair of points
• PC = [ (kB), (PM + kPB) ]

– To decrypt, Bob computes the product of the first

point from PC and his private key, b
• b * (kB)
– Bob then takes this product and subtracts it from the
second point from PC
• (PM + kPB) – [b(kB)] = PM + k(bB) – b(kB) = PM
– Bob then decodes PM to get the message, M.
Example – Compare to El Gamal
– The ciphertext is a pair of points
• PC = [ (kB), (PM + kPB) ]
– The ciphertext in El Gamal is also a pair.
• C = (gk mod p, mPBk mod p)
--------------------------------------------------------------------------
– Bob then takes this product and subtracts it from the
second point from PC
• (PM + kPB) – [b(kB)] = PM + k(bB) – b(kB) = PM
– In El Gamal, Bob takes the quotient of the second
value and the first value raised to Bob’s private value
• m = mPBk / (gk)b = mgk*b / gk*b = m
Diffie-Hellman (DH) Key Exchange
 ECC Diffie-Hellman
• Public: Elliptic curve and point B=(x,y) on curve
• Secret: Alice’s a and Bob’s b

a(x,y)
b(x,y)

Alice, A Bob, B

• Alice computes a(b(x,y))

• Bob computes b(a(x,y))
• These are the same since ab = ba
 Example – Elliptic Curve
Diffie-Hellman Exchange
• Alice and Bob want to agree on a shared key.
– Alice and Bob compute their public and private keys.
• Alice
» Private Key = a
» Public Key = PA = a * B
• Bob
» Private Key = b
» Public Key = PB = b * B
– Alice and Bob send each other their public keys.
– Both take the product of their private key and the other user’s
public key.
• Alice
KAB = a(bB)
• Bob
KAB = b(aB)
• Shared Secret Key = KAB = abB
 Why use ECC?
• How do we analyze Cryptosystems?
– How difficult is the underlying problem that it
is based upon
• RSA – Integer Factorization
• DH – Discrete Logarithms
• ECC - Elliptic Curve Discrete Logarithm problem
– How do we measure difficulty?
• We examine the algorithms used to solve these
problems
 Security of ECC
• To protect a 128 bit
AES key it would take
a:
– RSA Key Size: 3072
bits
– ECC Key Size: 256
bits
• How do we
strengthen RSA?
– Increase the key
length
• Impractical?
 Applications of ECC
• Many devices are small and have limited
storage and computational power
• Where can we apply ECC?
– Wireless communication devices
– Smart cards
– Web servers that need to handle many encryption
sessions
– Any application where security is needed but
lacks the power, storage and computational
power that is necessary for our current
cryptosystems
 Benefits of ECC
• Same benefits of the other cryptosystems:
confidentiality, integrity, authentication and
non-repudiation but…
• Shorter key lengths
– Encryption, Decryption and Signature
Verification speed up
– Storage and bandwidth savings
 Summary of ECC
• “Hard problem” analogous to discrete log
– Q=kP, where Q,P belong to a prime curve
given k,P
“easy” to compute Q
given Q,P
“hard” to find k
– known as the elliptic curve logarithm problem
• k must be large enough

• ECC security relies on elliptic curve

logarithm problem
– compared to factoring, can use much smaller key sizes than with RSA
etc
 for similar security ECC offers significant
computational advantages
Thank You