Elliptic Curve Cryptography (ECC)

There are many available choices for asymmetric cryptography, such as RSA or DLP-based cryptosystems. However, ECC has an edge over others in that it requires a shorter length keys than other cryptosystems to provide a similar security level. For example, where RSA, DLP-based cryptosystems require a key of 1024-2048 bits, we will need a key length of only 160-256 bits for ECC. Being able to use shorter key lengths with ECC means we get shorter digital signatures.

For cryptography, an elliptic curve is a particular type of polynomial equation constructed over a finite field. Prime fields, denoted as GF(p)GF(p) (after the name of mathematician Galois), are the most popular choice of finite fields, where all arithmetic is performed over modulo prime pp.

The elliptic curve equation in a finite field is:

y2x3+ax+b mod p:p>3 and a,b are elements of Zpy^2≡x^3+ax+b \ mod \ p:p>3 \ and \ a,b \ are \ elements \ of \ Z_p

Special consideration to note:

aa, bb and pp are required to satisfy the condition 4a3+27b2 mod p04a^3+27b^2 \ mod \ p ≠0

We consider an imaginary point of infinity ΦΦ (this is simply an identity element)

To visualise the above equation and understand a few operations, we must make use of coordinate geometry.

Note - plotting the above graph defined with ZpZ_pdoes not give us a curve, but rather a set of discrete points instead.

Therefore to demonstrate some ideas in the following examples, we construct the graph over a set of real numbers which yields a complete curve.

Group Operations

We mentioned the identity element above, and now, below is a high-level overview of group operations.

Point Doubling

To add points PP and QQ, we do the following steps:

  1. Draw a line joining PP and QQ and extend it until it intersects the curve. This point of intersection will be the negative of the sum P+QP+Q

  2. Therefore the mirror image about the x-axis of the point of intersection on the curve gives us the value of P+QP+Q

Special Case I - When Q=PQ=P, then what is P+QP+Q, i.e., P+PP+P?

The way to visualise this is to keep moving QQ closer and closer to PP and observe that the line will become a tangent at point PP. Extend this line to intersect the curve. The mirror image about the x-axis is the value of P+PP+P, i.e., 2P2P. This first special case is referred to as Point Doubling.

Special Case II - When Q=PQ=-P in other words, QQ is inverse of PP, P+QP+Q​ is the identity element (imaginary point ΦΦ at infinity)

Special Case III - When P=(x,0)P=(x,0), then P+PP+P is equal to the identity element ΦΦ

Note:

i. The rationale to perform addition ensures that the set of points on the elliptic curve, satisfies the necessary condition for a group.

ii. Generalizing above, in real-world applications, point addition is achieved by finding the slope of the line and solving the cubic equation.

Inverse

Is considered as a mirror image of the point on the curve. Identity is already mentioned above.

Scalar Multiplication

Scalar Multiplication is defined as multiplying point PP with scalar nn is essentially 'adding a point to itself nn times.'

nP=P+P+..+P(n times)nP = P+P+ …..+P (n \ times)

Scalar Multiplication is achieved by using Point Addition and Point Doubling. The algorithm used for Scalar Multiplication is included below; however, it is an optional topic. The algorithm is used for computing public keys in ECDSA

Square-and-Multiply Algorithm

Scalar Multiplication makes use of the "square-and-multiply algorithm." The difference is square is replaced by Point Doubling and multiply by Point Addition.

Convert the scalar value into a binary representation. Start from (MSB - 1) position and iterate till LSB (MSB stands for "Most significant bit" and LSB stands for "Least significant bit").

If in the iteration a bit is 0, then perform Point Doubling; if the bit is 1, then perform Point Doubling and Point Addition. For MSB, we don't perform any operation and consider the value as-is.

Let's say we want to find a value of 11P11P. First we need to convert decimal into binary representation: 11P11P = (1011)2P=(d3d2d1d0)2P(1011)_2P=(d_3d_2d_1d_0)_2P

Scan the bits on MSB i.e., d3d_3 and go till LSB d0d_0

Iteration 0: P=12PP = 1_2 P initial setting, bit processed: d3=1d_3 = 1 ---------------------------- Iteration 1a: P+P=2P=102PP + P = 2P = 10_2 P point double, bit processed: d2=0d_2 = 0 Iteration 1b: no point addition, as d2=0d_2 = 0 ---------------------------- Iteration 2a: 2P+2P=4P=2(102P)=1002P2P + 2P = 4P = 2(10_2 P )= 100_2 P point double: d1=1d_1 =1 Iteration 2b: 4P+P=5P=1012P4P + P = 5P = 101_2 P point add, as d1=1d_1 = 1 --------------------------- Iteration 3a: 5P+5P=10P=2(1012P)=10102P5P + 5P = 10 P = 2(101_2 P ) = 1010_2 P point double: d0=1d_0 = 1 Iteration 3b: 10P+P=11P=10112P10P + P = 11P = 1011_2 P point add: d0=1d_0 = 1

When we define the elliptic curve as above, under certain conditions the set of points and the identity element form a cyclic group. Firstly, the formation of a cyclic group implies the set must have a generator, i.e., an element in the set, such that its powers generate the entire group. Secondly, it leads to the next and last topic of pre-requisites.

Last updated

Was this helpful?