Understanding the Mathematics of ECC | Java Security Solutions

The mathematics behind elliptic curves has been around for at least 150 years. This concept is not new, but using ECC for exchanging keys has only been around for the last 10 years . One of the most noteworthy mathematicians who developed elliptic curves was Karl Weierstrass, a 19 ^th century mathematician .

The ECC rests on solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). An elliptic curve consists of all real numbers for the points x , y , a , and b in the (x, y) coordinate plane. The E _p (a, b) curve plane satisfies the following equation:

y ² = x ³ + ax + b (mod p)

The prime number p sets the upper limits of the equation and is used for modulus arithmetic.

When using ECC, there are two types of arithmetic: the Cartesian coordinates for resolving the elliptic curve and modular arithmetic used for resolving the points along the coordinate system. For example, choosing p = 23 creates the elliptic curve y ² = x ³ + ax + b (mod 23) . Substituting a = 1 and b = 1 yields the following example equation #1:

y ² = x ³ + x + 1

The example equation #1 creation is denoted by an elliptic group E ₂₃ (1,1) , where p = 23 , a = 1 , and b = 1 . When a different a and b are chosen , the curve changes. The elliptic group in its raw form is denoted by E _p (a, b) .

The real number scale can now be solved for y by using all values of x that start with 0 and are less than p . The prime number p provides a limit of the points that can be found. So y can be solved for values 0 through 23. For instance, if x = 0 in y ² = 0 ³ + 0 + 1 = 1, then y = 1. The point is denoted as ( x , y ) or (0, 1). All other points for x and y can be calculated in the same manner.

To represent the numbers in a binary form, p can take on the form of 2 ^m , which makes E ₂ ^m (a, b) . Also, the negative of a point is reflective of the shape across the x-axis. That is, if a P = (0,1) , the negative is the point -P= (0, -1) . In addition, the modulus equation can be used to find more points. Since -1 mod 23 = 22 , the negative point -P of P = (0,1) can also be (0,22) . Listing 5-1 shows examples of the modulo operation.

Tip	Recall from basic mathematics that modulo is the remainder. That is, r = mod(x,p) if r is a number between 0 and p such that x = qp+r* with integer q and imaginary parts ignored if they exist. Also, the congruent modulo is defined as r x (mod p) if [(r - x)/(p)] is an integer.

Listing 5-1: Modulo examples

 Find r = mod(10,7): solve r=x - q*p so that r is between 0 and 7 so r = 3     Find r = mod(-10,7): solve r=x - q*p so that r is between 0 and 7 so r = 4      Find r = mod(10,-7): solve r=x - q*p so that r is between 0 and 7 so r = -4      Find 89   x mod 23:  89/23 roughly equals 3 so 3 * 23 = 69 and 89 - 69 = 20 so 89   20 mod 23.

Modular arithmetic can also be applied to the equation of the curve to check the validity of a given point. Consider the E ₂₃ (1, 0) , which generates the curve y ² = x ³ + x . To see if a point P (9,5) works on the curve, solve the " mod 23 " for both sides as follows :

First substitute the x and y parameters to have 5 ² = 9 ³ + 9.
The highest degree to the equation is cubic, so the 9 ³ is the greatest computation.
Apply " mod 23 " on both sides. That renders 25 mod 23 = 738 mod 23 .
Now 25/23 = 1, 1*23 = 23, and 25 - 23 = 2 for the y side.
Next solve the x side. 738/23 roughly equals 32. Multiplying 32 by 23 brings 736, and subtracting the closest difference is 738 - 736 = 2 for the x side.
Since the x and y side equal each other, the P (9,5) is a valid point on the curve.

Modular arithmetic is also used for adding points. When adding points, usually a difference is taken on the curve to find the combination of the two points. The difference is denoted by the symbol lambda as l. There are two possibilities:

The two points are different. That is P = (x _p , y _p ) , and Q = (x _q , y _q ) then P + Q = (x _r , y _r ) where (x _r , y _r ) is the resulting point R . The difference is calculated l = (y _q - y _p )/(x _q - x _q ) and the formulas for xr = ( l ² - x _p - x _q )(mod p) and the formula for y _r = ( l( x _p - x _q ) - y _p )(mod p) .
The two points are equal. That is, you are doubling a point or adding the same point to it. There is no difference between the two points. The l is calculated using l = 3x _p ² + a / 2y _p . After lambda is calculated, the point R representing (x _r , y _r ) is calculated as 2P instead of Q + P where (x _q , y _q ) and (x _p , y _p ) are now the same points. To calculate 3 times P , P can simply be added to itself 3 times using this equation.

Here is an example calculation, let P = (3, 10) , Q = (9, -7) and E23 (1, 1) . Using these values, P + Q = (x _r , y _r ) for (x _r , y _r ) and the curve y ² = x ³ + x + 1 .

First calculate lambda

l = y _q - y _p / x _q - x _{q =} 7 - 10 / 9 - 3 = -3 / 6 = -1 /2 11 mod 23.

Tip	You need to use the mod inverse of x to find 11. Here is a simple way of doing it: (-1/2) = -1 * (1/2) so evaluate (1/2) (mod 23) by trial and error get (122) 1 mod 23 from that (1/2) 12 mod 23 and therefore, -1 12 = -12 11 mod 23

Next calculate x _r

x _r = ( l ² - x _p - x _q )(mod p) = 11 ² - 3 - 9 = 109 17 mod 23 so x _r = 17.
Then calculate y _r

y _r = ( l( x _p - x _q ) - y _p )(mod p) = 11(3 - (-6)) - 10= 89 20 mod 23 so y _r = 20.
The final result R = (17,20) .

Note
Multiplicative inverses are two numbers that multiplied together equal 1, for instance 11 and 1/11. Multipling by a modular inverse pair is just like multiplying by 1.

Table of content

Java Security Solutions

ISBN: 0764549286
EAN: 2147483647

Year: 2001
Pages: 222

Authors: Rich Helton, Johennie Helton

BUY ON AMAZON

A+ Fast Pass

Developing Tablet PC Applications (Charles River Media Programming)

C & Data Structures (Charles River Media Computer Engineering)

Practical Intrusion Analysis: Prevention and Detection for the Twenty-First Century: Prevention and Detection for the Twenty-First Century

An Introduction to Design Patterns in C++ with Qt 4

VBScript in a Nutshell, 2nd Edition