Moment For Technology

SM2 cryptography/elliptic curve cryptography MATHEMATICAL principles of ECC

Posted on Nov. 24, 2023, 11:33 p.m. by Rebecca O'Brien
Category: reading Tag: mathematics

The foreword 0.

Recently, I joined a company in the field of security, and came into contact with some cryptography, especially the state secret algorithm. There may be few companies in this field in China, and I found that the introduction of state secret algorithm in China is very superficial, let alone the introduction of mathematics and cryptography behind it. I've been doing some research on this recently. Keep a journal and hope it will help you. This paper mainly introduces the mathematical basis of ECC, and does not involve SM2 algorithm itself.

1. Introduction to SM2 algorithm

The full name of SM2 algorithm is SM2 elliptic curve public key cryptography algorithm (SM is the pinyin abbreviation of commercial cryptography, which fully reflects the autonomy and controllability of this series of algorithms), is a cryptography based on "elliptic curve". In 2016, SM2 became China's national cryptographic standard. In commercial cryptography, SM2 is mainly used to replace THE RSA encryption algorithm. Since SM2 is intended to replace RSA, it is necessary to introduce RSA, a well-known asymmetric encryption algorithm whose security is based on the integer factorization problem (IFP). Even if you haven't heard of RSA, you've probably heard of the integer factorization problem, and your gut instinct is, well, it's really hard. There are many reasons why SM2 is needed since RSA is such a mature algorithm. But one thing that cannot be ignored is that SM2 is a kind of Elliptic Curve Cryptography (ECC) based on ECC, which has its natural advantages. It is possible to obtain the same security strength as RSA with a smaller key length. The following are the recommended key lengths from NIST, the National Institute of Standards and Technology. The peers in the table represent the same security strength, i.e. the calculation time required to crack is the same.

RSA key size (bits) ECC key size (bits)
1024 160
2048 224
3072 256
7680 384
15360 521

It can be seen that under the same security intensity, the length of ECC key is much smaller than that of RSA key. In addition, as the RSA key is doubled, ECC key does not need to be doubled to obtain the same security intensity. This is useful for mobile devices, embedded devices, and other power-constrained, computationally constrained scenarios.

RSA is famous, and integer factorization problems we feel we can "understand", but personally feel that the mathematical principle of RSA is more difficult than ECC, because the mathematical principle of RSA involves many concepts of "number theory", number theory is not only abstract, but also not easy to understand; The mathematic principle of ECC is just another orientation, mathematic principle of ECC of math concepts involved in 9 years of compulsory education is not only a + not involved in the high school, even the most professional college will not come into contact with, this makes the understanding of the ECC is endowed with a high threshold, but in fact these mathematical concepts is not so difficult, In addition, ECC only uses the basic part of these mathematical concepts and does not involve very deep fields. Personally, I feel that these concepts are easier to understand than number theory. In addition, elliptic curves have images, images can greatly help our understanding, so understanding ECC is really not that difficult, you have to have confidence in yourself.

2. ElGamal public key cryptosystem

Mentioned above, SM2 is a kind of public key cryptography algorithm, public key cryptographic algorithms are built on a one-way function, the main reason why the function is one-way, because its the inverse function is calculated, that is to say, have so a kind of function, it is calculated easily and reverse calculation is very difficult to (imagine if really is such a function of all living things equality, Others difficult reverse calculation, it means that the decrypting party - happy Bob, decryption is hard, it's not what we want, of course), unless you know some other people don't know the information, with that information, you can easily reverse calculation, also means that the decryption only feasible to have these information, the "information" is what we call the private key. We call this function one-way trap door function, RSA one-way trap door function construction is based on the above IFP. SM2, as a kind of public key cryptographic algorithms, nature also need to construct such a one-way trapdoor function, the good news is that we don't need to start from scratch to "feeling" out of such a function, there is a ready and mature system of public key cryptography -- ElGamal public key cryptography system, this system is based on certain mathematical concepts constructed a universal one-way trapdoor function, The elliptic curve cryptography based on SM2 is the application of ElGamal public key cryptography in elliptic curve. The ElGamal system is built on cyclic subgroups of finite fields, and SM2 is based on these mathematical concepts, which are described below. These mathematical concepts are somewhat abstract and difficult to understand, but they are essential for understanding SM2 and ECC. And when you get confused, remember, it's not that we're trying to copy abstractions, it's that there are public key systems built on top of these abstractions, and we're just trying to apply elliptic curves to them.

3. What is an elliptical curve

The ellipse, as you all know, looks like this:

x 2 a 2 + y 2 b 2 = 1 \frac{x^2}{a^2}+\frac{y^2}{b^2}=1

It doesn't matter if it brings up some bad memories from high school, it's just getting started, and the following will make it even worse. So what is an elliptic curve? Y2 =x3+ax+b(4a3+27b2≠0)y^2 =x ^3 +ax+b(4a ^3 +27b ^2 \ne 0)y2=x3+ax+b(4a3+27b2=0) For different values of a and B, the graph looks something like this:

We can see from the graph, from the equation, that the elliptic curve is symmetric with respect to the x axis. And you might be thinking, well, this elliptic curve doesn't have anything to do with an ellipse, congratulations, that's right, the relationship between an ellipse and an elliptic curve, just like the relationship between Java and JavaScript, is called an elliptic curve because part of the integral for calculating the circumference of an ellipse is similar to the equation of an elliptic curve, So there is a good reason why the curve represented by this equation is called an elliptic curve. It is not far-fetched.

A little knowledge of group theory

With elliptic curves out of the way, we're going to introduce an important concept, groups. 12. A group is composed of a set and a binary operation (denoted by ⋅\cdot⋅) defined on that set, in compliance with the group axiom:

  1. 12. Closure: A ⋅ba\cdot ba\ b belongs to G\mathbb{G}G if AAA and BBB are members of the set G\mathbb{G}G
  2. Associative law: (1) a ⋅ b) c = a ⋅ ⋅ ⋅ c (b) (a \ cdot b) \ cdot c = a \ cdot \ cdot c (b) (a ⋅ b) c = a ⋅ ⋅ ⋅ c (b)
  3. ⋅e=a⋅e=aa\cdot e=a\cdot e=a⋅e=a carrier =a
  4. 12. Inverse: Any member a of the set G\mathbb{G}G, where B exists, so that a⋅b= EA \cdot b=ea =e, a, and b are inverse elements.

In popular culture, group is a collection of an operation, and then defined above set elements involved in the operation is not from this collection, and have a bit of a special element called collection unit, unit element and other elements in collection of doing the or the elements, and the collection each element has an element of contrary, Both of them, when you do that, you get the identity element that you just defined. Obviously, all integers and ordinary addition form a group, and the identity element is 0. All integers and ordinary multiplication cannot form a group, the first three are satisfied, and the identity element is 1, but there is no inverse element of other elements except 1. For example, the inverse element of 2 should be 1/2, but 1/2 is not in the integer range. Although the group axiom seems obvious, these conditions are not so easy to satisfy. And the other thing is, the identity element is special, we'll say it's 0, we'll say it's 1, but for certain operations, you can think of the identity element as a 0 for normal addition and a 1 for normal multiplication, so the inverse is just the negative for normal addition, the reciprocal for normal multiplication. We learned in elementary school that addition satisfies associative and commutative laws, but the commutative law is not included in the group axioms, and that's because these four axioms alone are enough to give us a lot of useful theorems, and there's no need to add another one that makes the group less applicable. However, it is better if the binary operation satisfies the commutative law, and more theorems can be derived. Such "enhanced groups" which satisfy the commutative law are called Abelian groups or Abelian groups. For example, in linear algebra, we have learned, there is not necessarily a n order the phalanx of inverse matrix, only to meet certain conditions have inverse matrix, n order "reversible" phalanx constitute a group under the matrix multiplication, the unit is a unit matrix, the inverse certainly exist, because our definition is "reversible" phalanx of order n, ⋅B≠B⋅AA\cdot B\ne B\cdot AA =B⋅A. So the commutative law is not something to be taken for granted, depending on how this binary operation is defined.

5. Elliptic curve group

We know what an elliptic curve is, what a group is, and what we really want to do is construct a group on an elliptic curve. Why such a strange idea? ECC is an application of elliptic curves in the ElGamal system, which is defined on groups. Ok, so how do you define binary operations on elliptic curves? Like I wait for wooden fish certainly can't think of, fortunately mathematician has helped you think well. Before introducing binary operations on elliptic curves (hereafter referred to as addition on elliptic curves), we need to make a small addition. A group is defined on a set, and the set of elliptic curves is, of course, all the points on an elliptic curve, but there's a little bit of trouble here, because defining a group requires a special element of the set, which is the identity element, and what point on an elliptic curve is special? In fact, no, every point on an elliptic curve has the same position. Therefore, in order to construct a group on an elliptic curve, it is necessary to first extend the set of elliptic curves by introducing a "special" point, which is called "infinity point" and denoted as 0:

{ ( x . y ) R 2     y 2 = x 3 + a x + b .   4 a 3 + 27 b 2 indicates 0 }     { 0 } \left\{ (x, y) \in \mathbb{R}^2\ |\ y^2 = x^3 + ax + b,\ 4 a^3 + 27 b^2 \ne 0 \right\}\ \cup\ \left\{ 0 \right\}

So this point at infinity is our identity element, and why do we say that, in combination with the following elliptic curve addition. So, where is infinity? Nonsense, of course at infinity, as if I asked you where do parallel lines intersect? You'd say parallel lines don't intersect. In fact, you could also say that parallel lines intersect at infinity, right, that's the point, if you get a sense of it.

With an extension to the set of elliptic curves, we can define the addition of elliptic curves:

  1. Identity element: point 0 at infinity
  2. The sum of three points P,Q, and R is the identity element: P+Q+R=0
  3. The two points that are symmetric about the x axis are inverses of each other.

This is the definition of addition that mathematicians have come up with for an elliptic curve that satisfies the group axiom. We can verify this:

  1. The closure, of course, satisfies that point plus point plus point must still be on the elliptic curve, or at infinity.
  2. The associative law satisfies, there is no order for three collinear points, so (P+Q)+R=0=P+(Q+R)
  3. The identity element, which is 0 at infinity, each point plus infinity is equal to this point
  4. The inverses, there must be inverses at every point, because the elliptic curve is symmetric about the x axis, but why do the inverses add up to zero at infinity? That's not obvious, but we can look at it another way.

I want to define elliptic curve addition, but this definition is just adding three points, so let's take a more straightforward definition, P+Q= -r, where the addition of two points on an elliptic curve is equal to the point of symmetry of the line crossing the elliptic curve with respect to the X-axis. Except in some special cases, a line that crosses two points on an elliptic curve must have one and only one intersection with the elliptic curve, that is, by definition of addition, the result must exist.

Special circumstances are:

  1. If you add two points of symmetry, if you only have two or one intersection of the vertical line and the elliptic curve, then the sum of those two points is equal to infinity 0, and as we said before, there is no third intersection, but you could say that the intersection is at infinity. So it makes sense that the sum of inverses is equal to infinity at 0.
  2. The sum of the same points, which is P plus P, is essentially taking the limit, the tangent point of the elliptic curve at P.
  3. P is the tangent point, P+Q= -p, also take the limit, as shown in the figure.

In fact, by definition, addition on an elliptic curve is commutative, so obviously P+Q=Q+P, so it's not just a group, it's an commutative group.

You have to ask yourself, why do you define it that way? What's the point? In fact, it doesn't make any sense, but the point of this definition is to define a binary operation that satisfies the group axiom, and we've already seen that it satisfies the group axiom. You think the addition of ordinary real numbers "makes sense" because you can find the corresponding in real life, such an abstract operation, do not need to have the "reason" you think, only need to meet the "condition" (namely the group axiom), and "consistent", that is, the operation rule itself can "justify". If it's going to be used in cryptography, it needs to be computationally easy. That's how it's defined.

5.1 Scalar Multiplication

If we define the addition of an elliptic curve, we can then define its scalar multiplication, which means adding the same point n times:

n P = P + P + ... + P n  times nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}

We could have done it step by step, and we could have done it n times and we would have gotten nP, but we didn't have to do that, but we could have done it faster, so let's say that n=151, 151 in binary is 10010111, which is to say

151 = 2 7 + 2 4 + 2 2 + 2 1 + 2 0 151 = 2^7 + 2^4 + 2^2 + 2^1 + 2^0

So what we can do is we can compute 2P, then we can compute 4P, 8P, 16P, 32P, 64P, 128P, and then

151 P = 2 7 P + 2 4 P + 2 2 P + 2 1 P + 2 0 P = 128 P + 16 P + 4 P + 2 P + P 151P = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P=128P+16P+4P+2P+P

The simple way to do it is to multiply it every time, and then you can quickly calculate nP. The above example shows that scalar multiplication on an elliptic curve can be computed quickly.

There's a website where you can visually see the addition on an elliptic curve.

More information about the elliptic curve addition is based on the geometric image, geometry image for people is more intuitive, facilitate us to understand, must also is in the form of algebraic computation, can apparently simultaneous equations of elliptic curve and linear, calculate the intersection point, intersection point of symmetry is as a result, the specific calculation formula given, You just have to remember that the calculation works and that the formula exists.

6. Limited domain

Let's put aside elliptic curves and groups and look at another mathematical concept called a finite field. A domain is a reinforced group, the definition of which is not given. Let's just look at the most common and understandable finite field Fp\mathbb{F}_{p}Fp, the integer field of modular p, where P is a prime number, and the elements of this field are p integers from 0 to p-1. The operation on the field is also very simple, just a normal operation and then modulo p, this should be familiar to programmers, take F23\mathbb{F}_{23}F23 as an example:

( 18 + 9 ) ( m o d 23 ) = 4 ( 7 - 14 ) ( m o d 23 ) = 16 4 x 7 ( m o d 23 ) = 5 (18+9) \pmod{23} = 4 \\ (7-14) \pmod{23} = 16 \\ 4\times 7 \pmod{23} = 5 \\

It's all simple. The key is "division" :

1 9 ( m o d 23 ) = 9 - 1 ( m o d 23 ) \frac{1}{9}\pmod{23} = 9^{-1} \pmod{23}

What is the multiplicative inverse of 9 on F23\mathbb{F}_{23}F23? It's basically asking:

9 x ? ( m o d 23 ) = 1 ( 1 Is the identity element of multiplication ) 9\times ? \pmod{23}=1(1 is the unit of multiplication)

Try 9×18(mod23)=19\times 18 \pmod{23}=19×18(mod23)=1, so the multiplicative inverse of 9 on F23\mathbb{F}_{23}F23 is 18, so

1 9 ( m o d 23 ) = 9 - 1 ( m o d 23 ) = 18 \frac{1}{9}\pmod{23} = 9^{-1} \pmod{23}=18

The reason p must be a prime is that only if p is a prime can we guarantee that every element from 1 to p-1 has a multiplicative inverse (obviously 0 has no multiplicative inverse). In fact, p is short for prime. And there is a way to quickly find the multiplicative inverse of each element, known as the extended Euclidean algorithm.

7. Elliptic curves over finite fields

We introduced the notion of a finite field in order to define an elliptic curve over a finite field, and let's not ask why we did that, we'll explain that later, but let's just accept that, and let's see what an elliptic curve over a finite field looks like.

{ ( x . y ) ( F p ) 2 y 2 x 3 + a x + b ( m o d p ) . 4 a 3 + 27 b 2 0 ( m o d p ) }     { 0 } \begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. \left. | \right. \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array}

The equation is the same as before, except that there is a finite field constraint on all the parameters x and y including a and b, which means that x,y,a, and b can only be integers from 0 to p minus 1. The three lines are congruence, which means that the magnitude of the left-hand side of the equation with respect to P is equal to the magnitude of the right-hand side with respect to P. So what does an elliptic curve look like with this constraint? Look at the picture.

Above is the image of y2≡x3−7x+10(modp)y^2 \equiv x^ 3-7x +10 \pmod{p}y2≡x3−7x+10(modp) when p is 19,97,127,487. Let's look at a couple of examples, let's look at the picture in the upper left, p=19, for the point (2,2), 22≡23−7×2+10≡4(mod19)2^2 \equiv 2^ 3-7 \times 2+10 \equiv 4 \pmod{19}22≡23−7×2+10 (mod19) for point (16,17), 172≡163−7×16+10≡4(mod19)17^2 \equiv 16^ 3-7 \times 16+10 \equiv 4 \pmod{19}172≡163−7×16+10≡4(mod19) It's just that every point in the graph you plug into the equation is equal to the magnitude of p. Notice that the graph is symmetric with respect to y equals p over 2.

The next question is, what should be the addition of an elliptic curve over a finite field? As we just saw the real number of domain of additive on the elliptic curve is the same, but because of the elliptic curve over finite field into discrete points, to say what two attachment for intersection becomes no longer image, but stressed before, image just to see, we calculated by means of simultaneous equations of point addition formula, The elliptic curve on a finite field is still valid, but the operation in the formula is also limited by the finite field, that is, the calculation result needs to be modulo p, and the "division" in the calculation process needs to be converted to multiply the multiplicative inverse element. The elliptic curves over a finite field and their point addition still constitute Abelian groups, although the finite field restriction is imposed on them.

7.1 group of order

The order of the group is just the number of elements in the group, and elliptic curves in the real field don't have this problem, because of course the order of the group in the real field is infinite, but in a finite field you can ask the question, what is the order of the group in a finite field? Obviously you could step x from 0 to p minus 1, and then figure out all the points, but in reality p would be a very large prime number, and that wouldn't work. Fortunately, mathematicians have solved this problem and Schoof's algorithm can quickly find the order of elliptic curve groups over finite fields.

7.2 Cyclic subgroups

Another useful result of an elliptic curve over a finite field is that any point P on it, after a number of scalar multiplies, returns to infinity at 0, which means that there is always n such that nP is equal to 0. For a specific example, y2≡x3+2x+3(mod97)y^2 \equiv x^3 +2x+3 \pmod{97}y2≡x3+2x+3(mod97) P(3,6)P(3,6)P(3,6

5P=05P=05P=0, and you can continue to verify that 6P=P,7P=2P... P6P mod 5 kP = (k) = P and 7 P = 2 P \ dots kP = (k \ bmod {5}) P6P = P and 7 P = 2 P... KP = P (kmod5). These five points form a closed set, and when you do dot plus in this set, the result is still in this set, let's call this set a cyclic subgroup of the group. For the example above, the order of the cyclic subgroup is 5. All other points in the cyclic subgroup are obtained from point P, which we call the base point or generator of the cyclic subgroup.

Cyclic subgroups are important and are the basis of elliptic curve cryptography and many other cryptographic systems.

Here, again, is the conclusion from group theory that the order of a subgroup must be a factor of the order of the parent group. Assuming that the order of the parent group is N and the order of the subgroup is N, then h=N/ N must be an integer, and h is called the cofactor of the subgroup. For the example above, Schoof's algorithm can calculate that the order of the parent group is 100, and the order of the cyclic subgroup based on P is 5, so the cofactor h=20. At this point, you might wonder, how do we determine the order of a base point and its corresponding cyclic subgroup in an elliptic curve over a finite field? This problem very important, but in fact you don't need to care about, because Alice and Bob to use ECC communication must be on the same curve calculation, the curve will often choose standard curve, standard curve is standard, is this curve parameters are determined, on the basis points and cyclic subgroup also determine the order of nature, and tell you, You just need to know that there is a way to determine the order of base points and cyclic subgroups, which you can ignore.

8. Elliptic curve discrete logarithm problem

So much talk, so much foreshadowing, it's finally coming to a climax. All these mathematical concepts are introduced in order to construct a mathematical problem: given two points P and Q on a cyclic subgroup of an elliptic curve over a finite field, what is the value of k, Q=kP? When the order of the cyclic subgroup is small, then the problem is easy, we can try each value of k, but when the order of the subgroup is large, this problem is difficult, there is no polynomial time algorithm on classical computers to solve. And this problem is more difficult than integer factor decomposition, so ECC can use smaller keys to obtain the same security strength as RSA.

Subjectively speaking, the point of the elliptic curve over finite field addition, even when you know the addition rule, also hard to find its rule, the result is like from one point to another point, based on the rules we can quickly find out from a point of "jump" after n steps by which point, but tell you if there are two points, ask the contact between them, The question of how many steps it took to "jump" to "finish" is difficult to answer.

Embed Equation. Dsmt4 (Elliptic Curve discrete Logarithm Problem). The security of ECC is based on the ELLIPtic Curve discrete logarithm Problem (ECDLP). It's that it's really hard (come on, trust me) -- and that's not a far-fetched reason at all. The point is, we don't have a good algorithm to solve this problem, but anyway, you know it's a problem.

9. Elliptic curve cryptography ECC

With the above mathematical problems, we can construct a public key encryption system on its basis, which generally includes three aspects:

  1. Elliptic Curve Diffie-Hellman (ECDH) : key exchange
  2. Elliptic Curve Digital Signature Algorithm (ECDSA) : Digital Signature
  3. Asymmetric encryption

Let's take a look at how ECDLP can be applied to each of these areas one by one.

9.1 Key Exchange

To put it simply, key exchange means that Alice and Bob can negotiate a secret key known only to them by exchanging some information publicly, while other people can solve the secret key through public information, which is computationally infeasible. The resulting key is particularly suitable for use as a symmetric encryption key. The basic principles of ECDH are as follows:

  • An elliptic curve over a finite field is based on GGG
  • Alice's private key is dAd_AdA, and the public key is HA=dAGH_A=d_AGHA=dAG
  • Bob's private key is dBd_BdB, and the public key is HB=dBGH_B=d_BGHB=dBG
  • Alice and Bob exchange public keys with each other, and they can solve for the same key S

S = d A H B = d A ( d B G ) = d B ( d A G ) = d B H A S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A

It is generally believed that the difficulty of solving SSS from HAH_AHA and HBH_BHB is the same as that of ECDLP. Obviously, this problem is not more difficult than ECDLP, because solving ECDLP can definitely solve SSS.

9.2 Digital Signature

To put it simply, digital signature means that Alice "signs" a certain information through its private key, and other people including Bob can verify that the information is indeed signed by Alice through Alice's public key, because this information can only be signed out through Alice's private key, and no one else can sign out. The basic principles of ECDSA are as follows:

  • The information m to be signed is converted to a hash value Z using a password-secure hash function
  • In the {1,... ,n−1}\{1, \dots, n-1 \}{1,... ,n−1} generates a random number k, where n is the order of the cyclic subgroup
  • Calculate P=kGP =kGP =kG
  • r = x P m o d n   ( x P is P The abscissa ) R = x_P \bmod{n}\ (x_P is the x-coordinate of P)
  • s = k - 1 ( z + r d A ) m o d n s = k^{-1} (z + rd_A) \bmod{n}
  • R,s is the signature information

Anyone can verify whether the digital signature (R, S) of information M comes from Alice through Alice's public key. The specific verification steps are not given any more. Generally speaking, R hides the information of random number K, while S mixes Alice's private key with the information to be signed. With these information, we can verify from another direction that the information is from Alice. Here's a graphic illustration of this:

S is designed that way so that rP plus zG is equal to sR. Note that calculating S requires the multiplicative inverse of k-modulo n. As mentioned earlier, the multiplicative inverse of K is guaranteed to exist only if n is prime, and n is the order of the cyclic subgroup of elliptic curves, which is why almost all standard curves have n as prime.

9.3 Asymmetric Encryption

Asymmetric encryption requires no further explanation, public key encryption, only the private key can be decrypted. In ECC, the basic principle of asymmetric encryption is:

  • Alice's private key is dAd_AdA, and the public key is HA=dAGH_A=d_AGHA=dAG
  • The message M Bob will send is encoded as a point M on an elliptic curve and generates a random number R
  • Bob sends C1=M+rHA C2=rGC_1=M+rH_A \ \ C_2=rGC1=M+rHA C2=rG to Alice
  • Alice decryption C1 - dAC2 = M + rHA - dArG = M + rdAG - dArG = MC_1 - d_AC_2 = M + rH_A - d_ArG = M + rd_AG - d_ArG = MC1 - dAC2 = M + rHA - dArG = M + rdAG - dArG = M

In layman's terms, Bob's information is in C1C_1C1, but only Alice can subtract the excess from C1C_1C1.

9.4 One Point

This section explains how to implement key exchange, digital signature and asymmetric encryption based on elliptic curve discrete logarithm problem. However, these are only principles and do not represent a concrete implementation of the algorithm. The actual algorithm design may be more complex than these principles, have achieved better security, or more clever design to make the computation faster.

10. Standard curve

The field parameters of secP256K1 standard curve are as follows:

a = 0
b = 7
xG = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
yG = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
h = 1
Copy the code

The finite field is roughly 2 to the power of 256, and the cofactor h=1, indicating that the order of the group is the same as that of the cyclic subgroup, both n, and it can be verified that n is a prime number, which is also roughly 2 to the power of 256. In general, the cofactors h are numbers like 1, 2, and 4, so there are more points in the cyclic subgroup, and it's harder to crack. This curve is famous because it is used as a digital signature for Bitcoin. In addition to this standard curve, there are many other standard curves, and their names are not arbitrary. They contain information about elliptic curves, and more specifically, see a tour of elliptic curves to find their roots.

SM2 standard elliptic curve is called SM2P256V1, and the specific field parameters are as follows:

b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
xG = 0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
yG = 0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0
h = 1
Copy the code

Similar to secP256k1, the order of finite fields and groups is close to 2 to the power of 256.

11. What is SM2 designed for

In fact, the theory of elliptic curve cryptography has been very mature, and there are many common elliptic curve cryptography algorithms in the world, so what is SM2 designed? In fact, there are two main points:

  1. Choose the right domain parameters to avoid "weak curves" against known attacks.
  2. Design specific key exchange, digital signature, asymmetric encryption standard algorithm, not only to ensure security, but also to ensure computational efficiency.

Problem of 12.

  1. Paradox: standard ellipse curve whether to hide the back door, elliptic curve discrete logarithm problem is not in any conditions is difficult, in particular on the elliptic curve is relatively simple, so if the elliptic curve is not guarantee standard "design", and then the designers know some closed crack means? This is a paradox, and it's a question of whatever the parameters of the standard elliptic curve are. RSA, on the other hand, has no such problem, because there is no need for such a thing as standard prime numbers. However, I don't think this is a problem. Trying to "hide" through "public" is not feasible in itself.
  2. How information is encoded to a point, and how information is extrapolated from a point, that's not covered, because I don't know.
  3. There are many kinds of elliptic curves. The one mentioned in this article is Weierstrass, which is the most commonly used elliptic curve. Of course, there are other forms of elliptic curve.
  4. F2m\mathbb{F}_{2^m}F2m \mathbb{F}_{2^m}F2m \mathbb{F}_{2^m}F2m \mathbb{F}_{2^m}F2m \mathbb{F}_{2^m} Of course, there are also standard curves defined over the finite field F2m\mathbb{F}_{2^m}F2m.

13. To summarize

Loosely speaking, the construction of groups on elliptic curves is the basis for elliptic curves to be used in cryptosystems, while the introduction of finite fields makes the discrete logarithm problem of elliptic curves difficult.

14. The reference

The best and most popular introduction to ECC should be this foreign article: Elliptic Curve Cryptography: A gentle Introduction this is a series of articles, including four. Many of the graphs and examples are from this article. An introduction to elliptic curve cryptography

How Schnorr Signatures may improve Bitcoin, this article describes the details of Bitcoin signatures, and the images featured in this ECDSA article are from this article.

Elliptic curve cryptography is a systematic and professional field. For more professional information, please refer to the book introduction to Elliptic Curve Cryptography.

About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.