elliptic curve presntation computer security

elliptic curve computer security

1. Introduction

* Major issue with use of public key is the size of numbers used.

* ECC belongs to the category of Public-key Cryptography, performs the
computations using elliptic curve arithmetic instead of integer or
polynomial arithmetic.

* ECC provides equally good security compared to RSA, but uses smaller key
size,

* Notable Advantages of ECC
+ Uses smaller keys, ciphertexts and signatures.
* ECC supports, very fast key generation.
* ECC scores over RSA because of its moderately fast encryption and decryption.

* ECC computations are uses less memory and CPU cycles compared to RSA, hence
suited for securing Mobile Handheld devices.

2. Comparable Key Sizes for Equivalent Security

Symmetric scheme | ECC-based scheme RSA/DSA
(key size in bits) (size of nin bits) | (modulus size in bits)

112 224

William Stallings Table 10,3 - * Comparable Key Sizes in Terms of Computational Effort for Cryptanalysis"

3. Introduction

+ An elliptic curve is defined by an equation in two variables with
coefficients.

* Elliptic curves are not ellipses. Elliptic curves are described by cubic
equations similar to those used for calculating the circumference of
an ellipse

* Elliptic curve cryptography makes use of elliptic curves, in which the
variables and coefficients are all restricted to elements of a finite
field,

4. ECC over Real Numbers

* Elliptic curve over real numbers are nothing but set of points (x,y) which
satisfy an elliptic curve equation y2 = x3 + ax + b, where x, y, a and b are
real numbers,

* Supplying different set of values for a and b results in a different elliptic
curve,

+ For example a = -4 and b = 0.67 gives the elliptic curve with equation y2 =
x3 - 4x + 0,67

* If the cubic polynomial x3+ax+b has no repeated roots, we say the elliptic
curve is non-singular.

* Anecessary and sufficient condition for the cubic polynomial x3+ax+b to
have distinct roots is 4443 + 27 b*2 not equal to 0.

+ we'll always assume the elliptic curves are non-singular.

5. att tft x

Vv

y?=x5.4x + 0.67

6. Elliptic Curves Over Finite Fields

* Instead of choosing the field of real numbers, we can create elliptic curves over
other fields!

* Let a and b be elements of Z, for p prime, p>3. An elliptic curve E over Z, is the
set of points (x,y) with x and y in Z, that satisfy the equation

1? (mod p) = 2° + ar +b (mod p),

together with a single element ©, called the point at infinity.

+ Asin the real case, to get a non-singular elliptic curve, we'll require 4a? + 27 b?
(mod p) #0 (mod p).

* Elliptic curves over Z, will consist of a finite set of points

7. Elliptic Curves Over Finite Fields

* Just as in the real case, we can define addition of points on an elliptic
curve E over Zp, for prime p>3.

* This is done in the essentially the same way as the real case, with
appropriate modifications.

8. Elliptic Curve Cryptography Discrete
Logarithm Problem [ ECCDLP ]

* Addition is simple
P+P=2P

Multiplication is faster , it takes only 8 steps to compute 100P, using point doubling and add

1. P*2=2P

, P+2P=3P

. 3P*2=6P

. 6P*2=12P

. 12P*2=24P

. P+24P=25P

. 25P*2=50P

. 50P*2=100P

On nun 2 wn

9. Elliptic Curve Cryptography Discrete
Logarithm Problem [ ECCDLP ]

* Division is slow,
* In ECC Qis defined as product of n*P is another point on the curve
Q=nP
given initial point P and final point Q, it is hard to compute ‘n’
which serves as a secret key.

Brute force method, start with P, every step multiply P with
number 1, 2 and so on,

For each step compare result of P*x where x=1,2,3,... with Q
This problem is known as discrete log problem, difficult to beak

10. ECC Application

+ ECC is being used in many places such as
* PDAs
+ VOIP
+ Smart cards
* Mobile devices

11. Diffie-Hellman Key Exchange - ECC scenario

* Alice and Bob two parties need to exchange secret key

1,

a un S&S & NH

Both Alice and Bob agree upon starting point P point on elliptic
curve publicly defined y2 = x3 - 4x + 0.67

. Alice selects his private ‘a’ and computes aP shares this with bob
. Bob selects his private ‘B’ and computes BP shares with Alice

. Alice receives BP and computes BPa by multiplying with his private
. Bob receives aP and computes aPB by multiplying with his private
. Itis obvious BPa = aPB , hence both Alice and Bob have same key

which serves as private kev for further encrvotion and decrvotion

12. Security Aspect

+ Attacks on groups of elliptic curves are weaker than available factoring
algorithms attacks

+ Best known attacks on elliptic curves based on cryptographic criterions are
the Baby-Step Giant-Step and Pollard-Rho method

* Complexity of these methods are approximately v p.

* Anelliptic curve using a prime p with 160 bit ,roughly 2160 points, provides a
security of 2% steps on an average that is required by an attacker.

+ An elliptic curve using a prime p with 256 bit, roughly 2256 points, provides a
security of 21% steps on an average.