Elliptic Curve Cryptography (ECC) is an algorithm for establishing public-key encryption, also known as asymmetric encryption. Similar to RSA, ElGamal algorithm and so on. ECC is recognized as the most secure encryption algorithm for a given key length. Both the public and private key generation and the signature algorithm ECDSA in Bitcoin are based on ECC. The following describes the principles of ECC and ECDSA.

Start with public-key encryption

Public key encryption, also known as asymmetric encryption. It is now the basis of modern Internet security or trust chains. The most important feature of public key encryption is that each communication party has a pair of public and private keys, which have numerous mathematical relations. Each person keeps his own private key and discloses his own public key. The advantage of this method is that the communication line is not afraid of being eavesdropped, because the attacker can not solve the ciphertext with the public key. There are two basic scenarios for using public and private keys:

Assume that the communication parties are Alice (public key A and private key A) and Bob (public key B and private key B).

  • The public key is encrypted and the private key is decrypted
  1. Alice wrote a letter that she didn’t want others to know. So it uses Bob’s public key B to encrypt the plaintext of the message, which is m. It was sent to Bob.
  2. Bob receives the ciphertext M, decrypts the ciphertext with his private key B, and correctly reads the contents of the letter.

In the whole process, even if the eavesdropper got the ciphertext M and the public keys A and B of the two people, they were useless and could not decrypt anything. In fact, only someone with private key B can decrypt this information. To put it another way, everyone can own Bob’s public key B, that is, everyone can create a piece of information that only Bob can use, or is only valid for Bob.

  • Encrypt the private key and decrypt the public key
  1. Alice wrote a public statement file, which she encrypted with her private key A to generate an encrypted file M and posted it on her website.
  2. Bob downloads the declaration file and decrypts it using Alice’s public key A to read the file correctly.

Alice’s public key A is available to everyone, so why encrypt it? Sure, anyone can decrypt a file, but the goal here is not to decrypt it, but to authenticate the source of the file, proving that it is definitely a claim made by Alice. Even if the file is maliciously tampered, decryption with public key A at this time will be invalid, which can prove that the information has been changed and is not Alice’s original file. Using public and private keys in this way proves the source of information and has undeniable properties. (that is, Alice cannot deny that the message was not sent by her, because only the private key A can produce the encrypted file M)

The above are the basic scenarios for using public key encryption algorithms. However, in fact, the above methods are far from enough for communication. For example, to improve the encryption speed, files need to be hash first. If you cannot defend against a man-in-the-middle attack, you may need to introduce a certificate (that is, the public key obtained may not be correct), but these are beyond the scope of this article. Let’s look at how ECC generates key pairs.

Elliptic curve

Let’s take a look at some math in this video.

In general, an elliptic curve can be expressed by the following equation, where a,b, C, and d are the coefficients (a≠0,No double root)


For example, when a=1,b=0,c=-2,d=4, the elliptic curve obtained is:


The elliptic curve is shown below.

The elliptic curve is not the shape of an ellipse that we learned in high school. It gets its name because the equation describing an elliptic curve is similar to the equation calculating the circumference of an ellipse. The definition of elliptic curves used here for encryption is a special case, see here for the full definition

With images, we can do some things 😈

Addition of elliptic curves

Here I will first introduce the concept of groups. A group is an algebraic structure consisting of a set and a binary operation. Given the set sum operation (G,*) if it is a group it must satisfy the following requirements

  • Closure: ∀ A, B ∈G, A * B ∈G

  • Binding: ∀ A, B, C ∈G, there is (A * b) * C = A * (b * C).

  • The identity element: ョ E ∈G, ∀ A ∈G, has E * A = A * E = a

  • The inverse element: ∀ A ∈G, ョb∈G makes A * B = B * A = E

In addition, there is a special group called the Abelian group which satisfies the commutative law axiom a * b = b * a in addition to the above properties

For example, an addition operation over integers is an Abelian group (Z, +).

  • Closure: IF a and B are integers, then a+b must be integers.

  • Associativity: a + b + c = a + b + c.

  • Identity element: 0 is the identity element, because for all integers A, a + 0 = 0 + a = a.

  • Inverse element: The inverse element of A is -a because a + (-a) = 0, the identity element.

So Z plus is an Abelian group.

Now, let’s define addition on an elliptic curve.

Now I have an elliptic curvePoints P and Q on the curve. Let’s draw a line through P and Q, the intersecting elliptic curve is R prime, and let’s draw a line perpendicular to the X-axis through R prime, the other intersecting curve is R, and let’s define P + Q = R. As shown in the figure below.

If P=Q, then the tangent line crossing P intersects the elliptic curve is R prime. As shown in the figure below.

In this case, R is equal to 2P. Similarly, 3P = P + P + P = P + 2P = P + R. In other words, when given a point P, it is not difficult to “calculate the point xG of the known number x”, because of the property of addition, the operation can be relatively fast. On the other hand, “the problem of finding x at a given point xG” is very difficult, because you can only do the operation through every x. This is the “discrete logarithm problem on an elliptic curve” used in elliptic curve cryptography.

For this operation to satisfy the property of an Abelian group, we also introduce an infinity point O, which can be thought of as the intersection of parallel lines (see the definition of infinity if this is difficult to understand), and we use this O point as the identity element. (Easy to understand, you can think of all lines parallel to the Y-axis that intersect at O).

With the above definition of infinity, it is not difficult to prove that the addition on an elliptic curve is an Abelian group.

Discrete logarithm problems on elliptic curves

Elliptic curve cryptography exploits the complexity of the “discrete logarithm problem on elliptic curves” of the above “operations”, just as RSA exploits the complexity of the “prime factorization of large numbers”, and the Diffie-Hellman key exchange of EIGamal cryptography exploits the complexity of the “discrete logarithm problem on finite fields”.

Discrete logarithm problem on elliptic curve:

  • known
    • Elliptic curve E
    • Point G on elliptic curve E
    • A point xG on the elliptic curve E.
  • To solve the
    • x

The difficulty of this problem guarantees the security of elliptic curve cryptography.

Elliptic curves over a finite field

So far, elliptic curves have been defined and operated on real numbers. In fact, elliptic curve cryptography uses operations in finite fieldsOn. Finite fieldFor a given prime number p, 0,1,2,….. ,p-1 the operation of addition, subtraction, multiplication and division defined in the set of integers consisting of P elements. This operation usesModular arithmetic.

Let’s look at a specific example:


When this elliptic curveWhen it is on the real number field R, the image is shown below, which is a smooth curve.

It’s the same curve when you’re in a finite domainAt the beginning, write:


That is, the remainder of the left and right results divided by 23 is equal, also known as the left and right numerical modulo 23 congruence. So the graph is not a curve, but a set of discrete points. The image is shown below.

If we take the point P = (3,10) on the elliptic curve as the basis and calculate 2P, 3P, 4P according to the rule of elliptic curve “addition” operation… The result is shown below.

We can see that the resulting points can be said to be irregular, such as point P = (3,10) and point 23P = (9,7). Solving the discrete logarithm problem here is equivalent to finding 23 given the points (3,10) and (9,7). In this case p=23, the problem is not difficult to solve, but it is very difficult to solve when p is very large.

Generate public and private keys

In elliptic curve encryption, given elliptic curve E, base point G and point xG, we call xG the public key and x value the private key. It can be seen from the properties of elliptic curve that it is easy to find public key with known public key, but almost impossible to find private key with known public key.

Application of elliptic curve cryptography

With a key pair, you can do many things with public key encryption, such as encrypting basic communications and verifying digital signatures. Only digital signatures are introduced here. The other principles are essentially the same.

Digital Signature: Elliptic curve DSA (ECDSA)

Again, suppose Alice wants to publish a public file and digitally sign the file. Bob needs to validate the signature. (The following parts involving calculation are modular operations)

Generating a digital signature

  • Alice based on random numbersAnd bpTake the point = (x,y)
  • Alice based on random numbers, message,The hash valueThe private key,To calculate
  • Finally, Alice sends the messageAnd point å’Œ Send it to Bob with the dot å’Œ That’s digital signatures

Verifying a digital signature

  • Bob receives the messageAnd point å’Œ
  • Bob based on the messageFind the hash value
  • Finally, Bob does the following calculation:

  • Finally, R and rG are compared. If they are equal, the signature is verified. Otherwise, it is an incorrect digital signature.

Verify the principle

The key point here is that Alice uses random numbers when she signs, and using the property of public key A=aG, only A can eliminate the factor of random variable R in the formula. The introduction of random numbers also improves security. Even for the same message, if the random number R is changed, the signature will be changed accordingly.

So far, we have a general understanding of the principle of ECC and ECDSA digital signature.

References:

ECC elliptic curve details

Graphic Cryptography third edition