Understanding the elliptic curve cryptography (Part 2) by Manuel Pérez

ECC & INTRODUCTION TO ECDH AND ECDSA

In the last post, we introduced the ECC through Clock Cryptography, which also served as a first contact with this type of cryptography. We also saw the first examples of elliptical curves, the curves of Edward, Montgomery and Weierstrass. Now, we will focus our attention on the latter, because they may be the ones that are most present in the technology and, throughout this post, we will discover why.

1. THE WEIERSTRASS’ CURVES

As we saw in the last article, these are curves of the form y²=x³+ax+b, where 4a³+27b²≠0 (so, the discriminant¹ of the cubic equation is not 0). As an interesting note, Ethereum and Bitcoin use the curve y²=x³+7, called sepc256k1.

Some examples of graphs playing with a and b:

ADDITION LAW

In this section, we will see, geometrically, how the sum of points of the curve works.

Notice that we haven’t changed the sign of y3. This is interesting because making the reflection along the X-axis, we take the negative Y.
The equation to find x3, appears from intersecting the line with the curve. We leave to you, as an exercise, to verify that the result is

SCALAR PRODUCT.

The case P=Q introduce to us to the notion of multiply by a scalar. But:

ELLYPTIC CURVES OVER FINITE FIELDS

The curve y²≡x³−7x+10(modp) with p=19 ,97, 127, 487. Note that, for every x, there are at most two points. Also note the symmetry about y=p/2.

The operations act exactly the same.
Example:

ii) y²=x³+2x+3, p=97

-Observation: If we calculate more iterations:

We won’t entered in specifications, as the demonstration escapes the levels of this article.

SUBGROUP ORDER.

Is the smallest integer n such that nP=0 (we say that P is the generator of the subgroup). By Lagrange’s theorem, we know that this integer n divides the group order.

An example: suppose that we have y2=x3−x+3 over F37. In this case, the order of E(37) is N=42. Thus, a subgroup inside this group can have order n={1,2,3,6,7,14,21,42}. Let’s take P=(2,3). The subgroup order generate by P is 7.

So, is true that N=h⋅n, for a certain integer h, where N is the order of E(p) and n is the subgroup order. The integer h=N/n is denominate the cofactor of the subgroup. Be P the generator of the cyclic group of order n ⇒ NP = n (hP) = 0. Observe that hP is the generator of a cyclic subgroup of order n.

At the practice, we take n a prime (we will see the importance of that). Define G=h⋅P, that we just see that generates a cyclic subgroup of order n.

Algorithm

1. Calculate N
2. Choose a prime divisor of N, n
3. Calculate h=N/n.
4. Choose a random P.
5. Compute G=h⋅P.
6. If G=0, return to step 4.

The necessary parameters to generate a ellyptic curve in Fp (the called domain parameters) are (a,b,p,n,G,h). This values make that the curve is vulnerable to Smart’s attacks. How we can make a safety curve? A possibility is adding a new parameter: the seed.

The seed is a random value used to generate a,b or the base point G. The procedure is the following:

As we can see, the implementation of a hash function give us the fiability that we can’t recover the basic information to generate this parameters. We say that the curve is veriafibly random, and uses a principle knowing as nothing up my sleeve, because use numbers outside of suspicion by the construction. This gives to us the security that the curve is not design to be attacked or to expose the vulnerabilities, knew by the author, i. e., if I gave you a curve generated by a seed, it means that I can’t choose freely a or b. So, I can’t attack the curve that I gave you.

2. ELLYPTIC CURVE CRYPTOGRTAPHY

Now we can lay the foundations of the ECC.

1. Choose our domain parameters.
2. Our private key is d∈{1,2,3,…,n−1}.
3. Our public key is H=d⋅G.

Next we will introduce an encryption method based on ECC and Diffie-Hellman: ECDH.

3. INTRODUCTION TO ECDH

This is a method that defines how the clues should be generated and exchanged.
Suppose that Alice and Bob want to exchange information.

Now Alice and Bob can exchange information by symmetric encryption.

4. INTRODUCTION TO ECDSA

Let’s put ourselves in the following case: Alice want to sign a document with her private key dA, and Bob will validate it with Alice’s public key, HA. Only Alice can make valid signs, and anyone can validate it.

The algorithm is based in DSA, Digital Signature Algorithm, and consists of the following steps:

Remember that n has to be a prime number to avoid problems with the calculus of k⁻¹. If n is not prime, we can’t usae ECDSA.

How can Bob validate the sign? We present the algorithm:

¿Why?

We have:

¹ The discriminant of a third grade equation (ax³+bx²+cx+dax³+bx²+cx+d) it’s defined like Δ=18abcd−4b3d+b2c2−4ac3−27a2d2Δ=18abcd−4b3d+b2c2−4ac3−27a2d2.

Sorry for the format design, but Medium stories doesn’t allow me to write formulas correctly, or I don’t discover how yet.

Follow Manuel
Twitter: @Manupp94