Elliptic Curve Cryptography

Elliptic Curve Cryptography

An Intro:~

Hello Readers, in this my article I am going to tell you about the algorithm that has become very important in cryptography is the elliptic curve. The elliptic curve is used for finding points on an ellipse and is used for Elliptic Curve Cryptography (ECC). The benefit of the ECC is that performance is faster, and it gives the same strength as RSA with a smaller key size. According to RSA Laboratory's findings , the ECC key length of 192 bits has the same strength of the RSA key length of 1020 bits. Cracking a key that size with a brute force attack would take 114 computers with a total of 170 GB of memory and 3 million years. The principal attraction of ECC is the smaller bit size for the same strength as a larger RSA key bit size.

The ECC uses keys in the discrete range, meaning that only positive integers are used. All numbers must be finite and have a range of 0 to an agreed-upon number. The exponential curve is somewhat straight after it reaches a certain point on the graph. The benefit of the elliptic curve is that various curves follow a curve formula with a discrete set of points, and finding a specific point on a curved line is more difficult.

The range of the elliptic curve could be from 0 to 23, a very low number, but the complexity of the curve, or the curviness, could generate many points on the curve. The complexity of the formula of the curve makes it difficult to guess at its sequence. The straighter the curve, the easier it is to guess at its sequence. Figures 1 and 2 illustrate the difference between some curves

Figure 1: Curvier

Figure 2: Less curvy

The elliptic curve uses points on the x,y coordinate system. For example, a point labeled P3 is described as (-1, -2). The x-coordinate is -1 units and the y-coordinate is -2 units. The coordinate is based on where the two lines intersect to form a point.

The special thing about elliptic curves is the unique characteristics that make up the points on the coordinate system. Unlike some other shapes, adding a point on an elliptic curve to another point on the curve results in a point on the curve that does not have any obvious pattern.

Another special property of elliptic curves is the scalar multiplication. For instance, multiplying a point times a number is called scalar multiplication and can only be performed one way, meaning that the original point cannot be derived from the result. For example, if the original point is P0, then P1=2*P0 is the same as P1=P0+P0 and P2=3*P0 equals P2=P0+P0+P0; each of these points is different, and P0 cannot be derived from either P1 or P2.

Getting The Mathematics of ECC

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 19th 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 Ep (a, b) curve plane satisfies the following equation:

y2 = x3 + 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 y2 = x3 + ax + b (mod 23). Substituting a = 1 and b = 1 yields the following example equation #1:

y2 = x3 + x + 1

The example equation #1 creation is denoted by an elliptic group E23 (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 Ep (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 y2 = 03 + 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 2m, which makes E2m (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.

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 = q*p+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 l1: 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 E23 (1, 0), which generates the curve y2 = x3 + 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 52 = 93 + 9.
• The highest degree to the equation is cubic, so the 93 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.

One of the most common ways of passing ECC keys is to use a modified Diffie-Hellman using ECC (ECCDH) version. The idea is to pass a public key and then generate a shared secret key to use for a new public key. Just as in Diffie-Hellman, the key is produced from multiplication.

Getting the ECC key exchange

The ECCDH public key algorithm depends on the calculation of an agreed-upon elliptic curve, the point on the curve as a starting point, deriving a random number for a private key, and sending other users the product of all these values. The receiving user, knowing the curve and starting point, can use the sender's product and derive a common product for both users to share as a key. The key agreement for ECCDH follows this sequence:

• First User A and User B select the elliptic curve by choosing prime numbers p, a, and b that satisfy the elliptic curve group Ep(a,b). The elliptic curve equation is y2 = x3 + ax + b (mod p).

• For example, p = 211, a = 0, and b = -4 create the elliptic curve group E211 (0, -4) and the elliptic curve y2 = x3 - 4.

• User A and User B select a common (x,y) coordinate point P on the elliptic curve y2 = x3 - 4 that is less than p.

• For example, using x = 2 will generate y = 2, so P(2,2). The P point in this example is known as the generator or G in the Diffie-Hellman algorithm.

• User A selects a random number, d, less than p, that will be multiplied by the point P to retrieve a multiple point Q on the curve, Q = dP.

• For the example d = 203, Q = (203)(2,2) = (130,203).
• User A sends the public key Q to User B.

• User B selects a random number, d, less than p that will be multiplied by the point P to retrieve a multiple of point Q on the curve, Q = dP.

• For the example d = 121, Q = (121)(2,2) = (115,48).

• User B sends the public key Q to User A.

• User A can calculate a shared key by computing S = dQ with Q received from B.

• For the example d = 203, S = (203)(115,48) = (161,169).

• User B can calculate a shared key by computing S = dQ with Q received from A.

• For the example d = 121, S = (121)(130,203) = (161,169).

• Both users now contain share and public keys.

Understanding the Service Provider Interface (SPI)

There are two main layers that a developer using the JDK 1.4 must completely understand: the Application Layer Interface (API) and the Service Provider Interface (SPI). The API is the interface that the developer uses to load up algorithms and protocols. The SPI layer loads up the appropriate algorithms and protocols based on the parameters passed in through the API. The service providers maintain information in properties files. If the properties files are not defined correctly, the appropriate service may not be loaded, or worse, it may be loaded with a corrupted service. A simple issue can be that the classpath is not set correctly to the appropriate providers.

Implementing the ECC key exchange as an SPI

To build a service provider module, there are exact classes, interfaces, and entries into the properties files that must be accomplished. Building an SPI interface is a very structured interface for the JDK 1.4.

The interface that most developers will actually have to understand is the java.security.Provider class. To implement an asymmetric key interface, the java.security.KeyFactory and java.security.KeyPairGenerator must be implemented and an association must be provided in the Provider class implementation. Listing l2.

Listing l2: The ECCProvider class: The Provider class

package com.richware.chap05;
import java.security.AccessController;
import java.security.PrivilegedAction;  
/**
 * Class ECCProvider
 * Description: This is a example of a
 * simple ECC Provider
 *
 * Copyright:    Copyright (c) 2002 Wiley Publishing, Inc.
 * @author Rich Helton 
 * @version 1.0
 * DISCLAIMER: Please refer to the disclaimer at the beginning of this book.
 */
public final class ECCProvider extends java.security.Provider
{
 private static final String INFO = "Rich's provider for ECC";
 
 public ECCProvider()
 {
 super("RichECC", 1.0, INFO);
 AccessController.doPrivileged(new PrivilegedAction() {
 public Object run()
 {
 put("KeyFactory.ECC", "com.richware.chap05.ECCKeyFactory");
 put("KeyPairGenerator.ECC", "com.richware.chap05.ECCKeyPairGenerator");
 return null;
 }
 });
 }
}

Listl2 associates the com.richware.chap05.ECCKeyFactory and the com.richware.chap05.ECCKeyPairGenerator. It returns these instances when the "ECC" is passed in as the type for the KeyFactory's and KeyPairGenerator's getInstance methods. The name of the service provider is "RichECC", which is passed in the super class if a lookup is done by the service provider's name. The provider interface is supplied, but it will not be called unless the entry is added to the $JRE\lib\security\java.security file.

Listing l3 displays the added entry.

Listing l3: Adding the ECCProvider class

security.provider.1=sun.security.provider.Sun
security.provider.2=com.sun.net.ssl.internal.ssl.Provider
security.provider.3=com.sun.rsajca.Provider
security.provider.4=com.sun.crypto.provider.SunJCE
security.provider.5=sun.security.jgss.SunProvider
security.provider.6=com.richware.chap05.ECCProvider

Listings l2 and l3 give an example of configuring a provider. The developer should be familiar with this exercise. The developer should also be familiar with the API for calling the classes and methods to generate the keys. Listing l4 gives an example implementation of interfacing with the KeyFactory and KeyPairGenerator.

Listing 4: The ECCSimpleApp class: The sample application:

package com.richware.chap05;
import java.util.*;
import java.math.*;
import java.security.*;
import javax.crypto.spec.*;   
/**
 * Class ECCSimpleApp
 * Description: This is a example of a
 * simple ECC
 *
 * Copyright:    Copyright (c) 2002 Wiley Publishing, Inc.
 * @author Rich Helton 
 * @version 1.0  
* DISCLAIMER: Please refer to the disclaimer at the beginning of this book.
 */
public class ECCSimpleApp
 {
 /**
 * Method main
 * Description: The Main test driver
 * @param args none
 *
 */
 public static void main(String[] args)
 {
 try
 {
 System.out.println();
 System.out.println(
 "ECC letting the algorithm choose randoms**************");
 KeyPairGenerator kpg =
 KeyPairGenerator.getInstance("ECC");
 
 /*
 * A strong key uses 512 to 2048 bits
 * the bits must be multiples of 64
 */
 System.out.println("Provider =" + kpg.getProvider());
 kpg.initialize(512);
 KeyPair kp = kpg.generateKeyPair();
 
 /*
 * Read the keys
 * produced by the algorithm
 */
 System.out.println("Public Key ="
 + kp.getPublic().getEncoded());
 System.out.println("Public Key Algorithm ="
 + kp.getPublic().getAlgorithm());
 System.out.println("Public Key Format ="
 + kp.getPublic().getFormat());
 System.out.println("Private Key ="
 + kp.getPrivate().getEncoded());
 System.out.println("Private Key Algorithm ="
 + kp.getPrivate().getAlgorithm());
 System.out.println("Private Key Format ="
 + kp.getPrivate().getFormat());
 
 /*
 * Initialize the KeyFactory for DSA
 */
 KeyFactory kfactory = KeyFactory.getInstance("ECC");
 
 /*
 * Create the DH public key spec
 */
 ECCPublicKeySpec kspec =
 (ECCPublicKeySpec) kfactory
 .getKeySpec(kp.getPublic(), ECCPublicKeySpec.class);
 
 /*
 * Print out public Public Q point public values
 * to be sent to the other user
 */
 System.out.println("Public Key QY =" + kspec.getQY());
 System.out.println("Public Key QX =" + kspec.getQX());
 }
 
 /*
 * Catches
 */
 catch (java.security.NoSuchAlgorithmException ex)
 {
 ex.printStackTrace();
 }
 catch (Exception ex)
 {
 ex.printStackTrace();
 }
 }
}

Listing l4 demonstrates initializing the ECC algorithm. The ECC algorithm needs to know the key size, and optionally the random generator. Like most algorithms, if the key size is not specified, it will default to 512-bit key size. The KeyFactory, ECCPublicKeySpec, and ECCPrivateKeySpec are used to pass key-specific parameters for initiation. The private key spec will be the d parameter, and the public key specifications will require the point for Q for x and y.

The public key spec is needed to return the values of point Q in order to pass these values to the other user. Most implementations save the public key values to a file or a socket to pass them to the receiving user for developing a shared key. The key spec values are also useful for initializing the keys. The key spec values are extended for the java.security.spec.KeySpec interface.

The key specs are used to pass values to the actual keys, ECCPublicKey for an implementation of the public key and ECCPrivateKey for the private key. The public key is extended from the java.security.PublicKey interface. The private key is extended from the java.security.PrivateKey interface. The public key and private key interfaces mark the classes as serializable for saving key information and are used to identify in which class the key information is kept.

Other specifications in this implementation are the ECCParameterSpec and the ECCGenParameterSpec. Both of these spec classes are extended from the java.security.spec.AlgorithmParameterSpec interface. The ECCParameterSpec is used for passing cryptographic information between the keys in the generators and factories. The ECCGenParameterSpec is specific cryptographic information for generating the key pair. The ECCGenParameterSpec in the Listing l4 implementation contains the prime size p.
There are many benefits to using the API and SPI interfaces supplied by Java. By looking at the key and parameter spec, the parameters and high-level details of the algorithm can be understood without going into the minor details of the mathematics.
This article discussed the benefits of and how to implement the ECC algorithm as a service provider. The mathematics were introduced into this article as simply as possible. For a more complex understanding of the modular arithmetic, there are many advanced mathematics books. In addition, this article discussed how to implement a key exchange and ECC using Java's Service Provider Interface (SPI).

As presented in this article, the mathematics of curves and modular arithmetic for ECC require only a handful of algorithms and functions to implement a key exchange. The ECCDH only requires a handful of steps to implement. ECCDH has a lot of promise, and I am surprised that DH and RSA are shipped with JDK 1.4, but not ECC. There are a few companies that are working to provide ECC such as www.cryptix.com. ECC is a hard-to-break algorithm and is lightning fast, so I would think that there would be more products using ECC.