blocksight 2021-04-23 20:25:10 阅读数:548
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 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
𝐸𝑝(𝑎,𝑏) 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 .
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 !
版权声明:本文为[blocksight]所创,转载请带上原文链接,感谢。 https://netfreeman.com/2021/04/20210423201642224C.html