Elliptic Curve Cryptography

an elliptic curve will simply be the set of

CURVES?

points described by the equation:

y = x

2 3 + ax + b

where

4 a +27 b

3 2 ≠0

GROUPS

have defined a binary operation that we call "addition" and indicate with the symbol +.

In order for the set GG to be a group, addition must defined so that it respects the following four properties:

GROUP PROPERTIES

a + b is a member of G; associativity: (a + b )+ c = a +(b + c ); there exists an identity element 0 such that a +0=0+ = ;

a a

every element has an inverse, that is: for every

a there exists such that + =0.

b

a b

If we add a fifth requirement:

commutativity: + = +

a b b a,

then the group is called abelian group.

We can define a group over elliptic curves.

Specifically:

CURVES

the elements of the group are the points of an elliptic curve; the identity element is the point at infinity 0; the inverse of a point

P is the one symmetric

about the x-axis; addition is given by the following rule:

given three aligned, non-zero points P,

Q and R,

their sum is + +

P Q R =0

FINITE FIELDS

number of elements.

An example of finite field is the set of

p, where is a prime

p

integers modulo number.

Z/ p GF (p) ) or

It is generally denoted as, F We will use the latter notation.

p

FINITE FIELDS

operations: addition (+) and multiplication (·).

Both are closed, associative and commutative.

For both operations, there exist a unique identity element, and for every element there's a unique inverse element.

Finally, multiplication is distributive over the addition:

x (y + z )= x y + x z.

⋅

⋅ ⋅

Multiplication over points for elliptic curves

POINTS IN ELLIPTIC

in F has an interesting property.

p

CURVES

Take the curve

y x +2 x +3(mod97)and the point

≡ 3 2

P =(3,6).

Now calculate the multiples of P

A "subgroup" is a group which is a

BASE POINTS

subset of another group.

A "cyclic subgroup" is a subgroup which elements are repeating cyclically,

P is called generator or

The point base point of the cyclic subgroup.

ORDER

equivalent definition:

the order of P is the smallest positive integer

n such that =0.

nP

In fact, if you look at the previous example, our subgroup contained five points, and we had 5

P =0.

The order of a subgroup is a divisor of the order of the parent group.

In other words, if an elliptic curve contains N points and one of its subgroups contains

n

points, then n is a divisor of N.

FINDING THE BASE POINT

algorithm:

Calculate the order N of the elliptic curve.

Choose the order n of the subgroup. For the algorithm to work, this number must be prime and must be a divisor of

N.

Compute the cofactor = /

h N n.

Choose a random point P on the curve.

Compute =

G hP.

If G is 0, then go back to step 4. Otherwise we have found a generator of a subgroup with order

n and cofactor.

h

Note that this algorithm only works if n is a prime. If n wasn't a prime, then the order of G G could be one of the divisors of n.

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.

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 F (where p>3 is a prime) and F

m (a binary representation with 2

m

p

2

elements ).

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

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).

Both parties agree to some publicly-known data items  The elliptic curve equation

 values of a and b  p

prime,

 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)

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 = P = a * B

A

 Bob

 Private Key = b  Public Key = P = b * B

B

 Alice takes plaintext message, M, and encodes it onto a point, P, from the

M

elliptic group

 The ciphertext is a pair of points

 P = [ (kB), (P + kP) ]

C

M B

 The ciphertext in El Gamal is also a pair.

 C = (g k mod p, mP k mod p)

B

--------------------------------------------------------------------------  Bob then takes this product and subtracts it from the second point from P

C

 (P + kP) – [b(kB)] = P + k(bB) – b(kB) = P

M B

M

M

 In El Gamal, Bob takes the quotient of the second value and the first value

raised to Bob’s private value  m = mP k / (g k) b = mg k*b / g k*b = m

B

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 = P = a * B

A

 Bob

 Private Key = b  Public Key = P = b * 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 → K = a(bB)

AB

 Bob → K = b(aB)

AB

 Shared Secret Key = K = abB

AB

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

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

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

“ Hard problem ” analogous to discrete log  , where

Q=kP 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