Elliptic Curve Cryptography – Generation of Domain Parameters

“The transistor density of integrated circuits doubles every 2 years” – Gordon Moore

Let’s contemplate upon what Moore said. We live in a world where new advancements happen every fraction of second. Given the increase in processing power of the modern day computers and their successors, even unnerving problems can be solved in a matter of minutes. But on the other hand the same processing power has left many cryptographic algorithms – OBSOLETE.

Recently I came across the need of securing data in transit and storage by employing such a cryptographic algorithm which has no freely floating hacks. Since brute forcing is an answer to solve all kinds of cryptographic problems, the sole hope rests on making it computationally infeasible (in cryptographic terms). After breaking our heads on it for 2 days we came across Elliptic Curve Cryptography. The algorithm being relatively newer isn’t much in practice nor has any known mathematical attack (as of my writing Certicom has come out with one [1]). Further a key length of 160-bit in ECC is considered equivalent to 1024-bit in RSA.

I found an open source Java implementation of the algorithm on Sourceforge [2]. Free lunch! But alas it generated only static keys. So, I had to go through the entire process of generating the ‘Domain Parameters’ of ECC thereby causing a new key to be generated each time a new communication is initiated. Now there’s a whole lot of math involved (obviously) in ECC so I’ll discuss just a few major conditions which must be met while implementation. I worked only on the domain parameters for Prime Field as it was alone enough to overwhelm me. 😀

Let’s start off with the equation for prime field and its variables:

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

• a, b are such that 4a³ + 27b² mod p ≠ 0 and p is a huge prime number.

For generating p one can either use the premade function getFieldSize( ) or use the Big Integer class to generate very large primes.

Now the values of a & b should be chosen so that the expression doesn’t result in 0 after the entire calculation is done. These values can also be made to generate automatically with any custom built algorithm. For eg. a can be 1/kth part of p while b can be 1/lth part of p, where k and l are so chosen that 4a³>0 and 27b² > p.

• Order of the ellipse is represented by n.

• G is the generator point (x_G, y_G) on the elliptic curve chosen for cryptographic purposes.

• The cofactor, h = E(F_p)/n, where E(F_p) is the number of points on the elliptical curve.

Now what about h? How do we go on calculating the number of point on the curve? There are quite a number of algorithms for that too. But talking of open source and simplicity these two can be used [3]:

1. Naive approach
2. Baby step giant step method

Once h is calculated check whether it satisfies the criterion: h <= 4 & h = [(√p + 1)²/n]

There are a lot more conditions to be satisfied, but they are already being taken care by the open source implementation. Once the domain parameters are generated dynamically the entire process of generation of keys becomes automatic. In ECC:

• Private key = any random number
• Public key = Private key X (Generator point, G)

The generator point can be any point lying on the curve. Since, we’ve already found out which all points lie on the curve using the naïve approach, we can select one of them for our purpose

Okay, I hear people heaving a sigh of relief there. I agree it’s seemingly complex but that’s the beauty of cryptography, isn’t it? 🙂

REFERENCES:

[1] http://sourceforge.net/projects/jecc/

[2] https://www.certicom.com/index.php?action=company,press_archive&view=307

[3] http://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves