Write it at the front

In the last section, we introduced The concept of group theory and the point coordinates of elliptic curve in real number field satisfy Abel The addition of groups , But the addition operation on the real number field can not meet the actual security needs , Because real numbers are continuous , If you know the result, you can use the inverse operation to solve it .

We may have known that the security of elliptic curve is based on the difficulty of solving discrete logarithm . This section will introduce how to discretize the coordinates of elliptic curve points .

Modular prime P operation

Modular arithmetic a mod p: Express a Divide p The remainder of .

Cryptography uses elliptic curves over finite fields , That is, the coefficients and variables of the elliptic equation are in a limited range , Use modulo primes 𝑝 The finite field of 𝑍p, Module operation is introduced into elliptic curve arithmetic , Variables and coefficients from the set [0,𝑝−1] Instead of taking values on real numbers . The equation in this field is modified as follows ：mod p =(+ax+b) mod p Discriminant (4+ 27) mpd p !=0 Satisfy all positive integer solutions and infinity points of the above equation O, The mathematical symbol is , It's a finite discrete （ Discontinuous ） Point set of . From this we can see that the points in the set are distributed in (0,0) To (𝑝−1,𝑝−1) In the quadrant of . actually , aggregate 𝐸𝑝(𝑎,𝑏) And mold 𝑝 A cyclic Abelian group is formed by the addition of . If the prime number p The choice is small , It can be solved by violence , Find all the points in . Illustrate with examples , about p=23, a=1,b=3, share 27 The first point is as follows ：(0,7) (6,15) (15,9) (0,16) (7,10) (15,14) (2,6) (7,13) (19,2) (2,17) (10,1) (19,21) (4,5) (10,22) (21,4) (4,18) (12,8) (21,19) (5,8) (12,15) (22,1) (5,15) (14,1) (22,22) (6,8) (14,22) O The last one is O spot . These points are a discrete set of points in the coordinate system , You can draw it yourself , Increase sensory knowledge . It can be verified that the equation is satisfied :mod 23 =(+x+3) mod 23

Addition on modular primes in discrete fields

𝐸𝑝(𝑎,𝑏) The rule of addition on is basically the same as that on real number field , But with more modular operations . model 𝑝 There is no intuitive geometric explanation for the addition of , Only algebraic description . solve (,) The algebraic expression of is ：=(−−) mod p=(−+𝑘(−)) mod p It can be seen that the solution process follows Previous section The solution on the real number field , It's just that in the end mod p. In the above formula :k=() mod p ( When p!=q)k=(() mod p ( When p==q)

for example 𝑎=1,𝑏=1,𝑝=23,𝑃(3,10),𝑄(13,16), seek 𝑅=𝑃+𝑄. here 𝑃≠𝑄, Calculation :k=() mod p=(16−10/13−3) mod 23=6× mod 23.

To calculate the above formula, we must first calculate mod 23.

Make 𝑥≡(mod23) [ notes ：≡ The symbol means that the module is equal to , Equivalent to 𝑥 mod 23=(mod23), The same below ], because 10≡10(mod23), therefore 10𝑥≡1(mod23), Using extensions Euclidean algorithm （ Refer to historical articles ） Get 𝑥=7.

k=6×7mod23=19 therefore =(−−) mod p = ( - 3−13) mod23 = 345 mod 23=0=(−+𝑘(−)) mod p = (19×(3−0)−10) mod 23=47 mod 23 = 1

therefore 𝑅=(0,1).

It can also be calculated according to the above rules 2𝑃,3𝑃 Wait a minute. Multiply .

The discrete logarithm problem in elliptic curves

With the above knowledge , Now we can get to the problem of discrete logarithm in elliptic curve . Constructing a mathematical problem to ensure the security of encryption is the main idea of encryption algorithm in cryptography . similar RSA Algorithm （ There will be a special article to describe ） The problem of factorization of large numbers is the same , Elliptic curves provide similar mathematical problems .

consider 𝑄=𝑘𝑃, among 𝑄,𝑃∈𝐸𝑝(𝑎,𝑏),𝑘<𝑝.

For a given 𝑘,𝑝 Calculation 𝑄 It's easy ; And vice versa 𝑄,𝑃, Calculation 𝑘 It's quite difficult , This is the discrete logarithm problem of elliptic curves （ The reason why it is called discrete logarithm problem is to keep consistent with other encryption algorithms , Easy to understand ）.

therefore , Can be 𝑄 As a public key , Go out in public ;𝑘 As the private key , Keep it secret , It's very difficult to crack the private key through the public key .

At present, the most effective algorithm for solving private key from elliptic curve public key is 𝑂(), among 𝑝 It's order 𝑛( Order in group theory refers to the number of elements in a group ) The largest prime factor of .

In this example , Selection of the p The relatively small , Actually p It's a very large integer , such as 256 Bit or more , It's not feasible to rely on violent operation for such a large number . Okay , Come here , Why elliptic curve encryption algorithm uses discrete domain , It's clear why modular operations are introduced and the principle of security . The next section describes the specific encryption process .

Welcome to continue to pay attention , If you have any questions, please leave a message ！