ECC elliptic curve encryption

This article written by Li Jianying explains the ECC eclliptic curve encryption in a simple way.

Regarding RSA’s idea of ​public-private key encryption, I thought I knew it well and I was skillful of it.

Of course, RSA is not used much now, but the most famous crypto that’s based on the ECC curve for signature verification is Bitcoin.

But the other day when I talked to others about the code, I was asked why ECC can be used for the signature verification, I found that I can’t give a clear explanation of it.

So I did some homework to make this issue clear.

First of all, we skip the topic of what ECC curve is.

because I feel that it is not very helpful to understand its logic. It is better to black box it.

Because we are coders, there are “types” that are very clear, and you don’t have to be afraid at all.

Just say the principle, non-pseudo code, for example, I will not say the curve degree as skipping it does not affect understanding the principle.

The core principle of ECC curve encryption

As we discuss in the article, we assume all points are on the same curve, on which the points support a multiplication operation.

Let Q be a point on the curve

If the point R = Q * Q, it can also be recorded as R = 2.Q

If the point R = Q * Q * Q, it can be recorded as R = 3.Q

If the point R = Q * Q * … * Q, a total of n Q, it can be recorded as R = n. Q

Then here comes the principle.

It is easy to find R if n and Q are given. If R and Qare given, it is very difficult to find n.

On this principle, then everything else is proved.

Public and private keys

Let’s review the principle first

Let Q be a point on the curve and k be an integer

Let point K = k.Q, if k and Q are given, it is easy to find K

If K and Q are given, it is difficult to find k

Let me show you in another way.

Let G be a point on the curve and k be the private key.

Let the public key K=k.G, if the private key and G are given, it is easy to find the public key.

If a public key and G are given, it is difficult to find the private key.

Is it a bit interesting? From here we can also see that the private key of ECC is an integer, a very large integer, not to mention Int64. In the commonly used ECC algorithm, the private key is a 256-bit integer.

The ECC public key is a point, although they are usually seen as either strings or bytearray, but the private key is an integer and the public key is a point (two-dimensional coordinate).

There are many applications for the ECC curve. The most common ones are encryption and decryption as well as signature verification.

Encryption principle

Encryption steps

First set K=k.G, (public key = agreed point G to the power of private key).

1. To pass the data m, first encode it as a coordinate point M (how to encode it is your thing, such as a string, you bytes it first, then turn into a large integer, and make it as the x in the coordinate. It’s purely an example.

2. The entire random integer r

3. Calculate the point C1 = M+r.K It must be a little confusing here. There is a dot addition, and r.K, r.K is r Ks multiplied, and K is the public key. That is, point C1 is equal to r public keys multiplicated plus coordinate point M

4. Calculate the point C2 = r.G G is the agreed point on the curve, that is k=k.G (public key = agreed point G to the power of factorial private key), r is the previous random integer

After the encryption is completed, it can be seen that the encryption requires a public key, and the encryption encrypts the coordinate point M into two coordinate points of C1 C2.

The encryptor only needs to send C1 C2 to the other party.

Decryption steps

1. From C1=M+r.K, we can know M = C1-r.K

2. Substituting K into the above formula by K=k.G (public key = private key) M=C1-r.k.G

3. Bring C2=r.G into the above equation, you can get M=C1-k.(r.G)=C1-k.C2

4. According to the conclusions derived above, M=C1-k.C2, the decrypter can calculate the encrypted coordinate point M according to the received C1, C2 and its own private key.

Principle of signature verification

Signature step

First set K=k.G, (public key = agreed-point G to the power of factorial private key), set the signature data to m, and use the private key for signature.

1. Process the data that are to be signed: e=hash(m), e is a huge integer. The Hash algorithm does not need to be explained. m is mandatory. The ECSDA implementation also puts a coordinate into the hash to calculate the principle. I will not substitute for them, just say e

2. The entire random integer r

3. Calculate s=r-e*k. This expression is purely an integer operation. The result s is of course an integer. The s= random number minus the hash* private key.

Signature completed

Usually, signature (signdata) refers to two integers, s and r.

The signer sends s, r, and public key K. If you want to sign the data m, anyone can check it.

Verification steps, public key is used for signature verification

1. Process the data that are to be signed e=hash(m)

2. Calculate the point V1=r.G (that is, the point of the public key, the G to the power of factorial random number r)

3. Calculate the point V2=s.G+e.K (point G to the power of factorial signature data s plus factorial public key)

4. If V1=V2, the verification is successful, then prove

5. If the data is correct, then s = r-e*k is established.

6. Now set s=r-e*k, V2=s.G+e.K to expand s to V2=(r-e*k).G+e.K

7. V2 = r.G-e.k.G+e.K

8. Since K=k.G, substituting the above formula, you can get V2 = r.G — e.(k.G)+e.K = r.G -e.K+e.K

9. The above formula cancels e.K and gets V2=r.G. It can be seen that when s=r-e*k, V2=r.G=V1

10. Conversely, when V1=V2, s=r-e*k is true then the data is correct.