Discrete logarithm problem in ECC

The discrete logarithm problem in ECC is based on the idea that, under certain conditions, all points on an elliptic curve form a cyclic group.

On an elliptic curve, the public key is a random multiple of the generator point, whereas the private key is a randomly chosen integer used to generate the multiple. In other words, a private key is a randomly selected integer, whereas the public key is a point on the curve. The discrete logarithm problem is used to find the private key (an integer) where that integer falls within all points on the elliptic curve. The following equation shows this concept more precisely.

Consider an elliptic curve E, with two elements P and T. The discrete logarithmic problem is to find the integer d, where 1 <= d <= #E, such that:

Here, T is the public key (a point on the curve), and d is the private key. In other words, the public key is a random multiple of the generator, whereas the private key is the integer that is used to generate the multiple. #E represents the order of the elliptic curve, which means the number of points that are present in the cyclic group of the elliptic curve. A cyclic group is formed by a combination of points on the elliptic curve and point of infinity.

A key pair is linked with the specific domain parameters of an elliptic curve. Domain parameters include field size, field representation, two elements from the field a and b, two field elements Xg and Yg, order n of point G that is calculated as G = (Xg, Yg), and the cofactor h = #E(Fq)/n. A practical example using OpenSSL will be described later in this section.

Various parameters are recommended and standardized to use as curves with ECC. An example of secp256k1 specifications is shown here. This is the specification that is used in Bitcoin:

An explanation of all of these values in the sextuple is as follows:

• P is the prime p that specifies the size of the finite field.
• a and b are the coefficients of the elliptic curve equation.
• G is the base point that generates the required subgroup, also known as the generator. The base point can be represented in either compressed or uncompressed form. There is no need to store all points on the curve in a practical implementation. The compressed generator works because the points on the curve can be identified using only the x coordinate and the least significant bit of the y coordinate.
• n is the order of the subgroup.
• h is the cofactor of the subgroup.

In the following section, two examples of using OpenSSL are shown to help you understand the practical aspects of RSA and ECC cryptography.