当前位置：网站首页>Elliptic curve encryption

（3） congruence 、 Complete residue system 、 Inverse element 、 Additive generator 、 Euler φ function 、 Square surplus 、 Euler Criterion 、 The law of quadratic reciprocity

（4） Egyptian multiplication 、 Discrete logarithm problem 、 Public key system

One , The ellipse

Elliptic equation ： $\left ( \frac{x}{a} \right )^2+\left ( \frac{y}{b} \right )^2=1$ , among a>b>0

Elliptical area ：S=PI * a * b

The circumference of the ellipse is complex , There is no elementary formula .

The circumference of an ellipse can be expressed by a complete elliptic integral , It will involve a form such as $\sqrt{t^3+...}$ The formula of .

Two , Elliptic curve

1, General elliptic curve

（1） equation

equation y^2+uxy+vy=ax^3+bx^2+cx+d The curve described , If everything is smooth （ No sharp points 、 acnode 、 Selfing ）, So it's an elliptic curve

（2） Non elliptic curve

2 A counterexample ： Cusps and selfing

Below Montgomery Curve chapter , There are isolated points .

（3） Reduced to a common elliptic curve

y^2+uxy+vy=ax^3+bx^2+cx+d Can become $(y+\frac{u}{2}x+\frac{v}{2})=ax^3+(b+\frac{u^2}{4})x^2+(c+\frac{uv}{2})x+d+\frac{v^2}{4}$

（4） Degenerate to conic

2, Commonly used elliptic curve

y^2=ax^3+bx^2+cx+d namely $y=\pm \sqrt{ax^3+bx^2+cx+d}$ , among a Not for 0

Nondegenerate elliptic curves can be reduced to this form .

because $\sqrt{ax^3+bx^2+cx+d}$ Is consistent with the formula in complete elliptic integral , So it is called elliptic curve , In fact, it doesn't have much to do with ellipses .

Later, we will only discuss the commonly used elliptic curves , The encryption algorithm should only cover this .

On the right is the cubic term ：

3,Weierstrass equation （ Weierstrass equation ）

Common elliptic curves can be reduced to the following simple forms ：

y^2=x^3+ax+b

This seems to be called Weierstrass normal form Well , Didn't look into it very carefully , Not sure .

actually , The most commonly used formula for finding roots of cubic equations , It is also stipulated in this form first , Then, according to Weida's theorem, we can deduce the formula for finding roots .

4, Discriminant of elliptic curve

With Weierstrass Take the equation as an example , By default, the following paragraphs discuss Weierstrass equation

The discriminant is $\Delta = 4a^3+27b^2$ , It is the same as the discriminant of cubic equation ：https://blog.csdn.net/nameofcsdn/article/details/105172343

It's actually quite understandable , The shape of the elliptic curve , It depends on its axis of symmetry and its intersection .

If the discriminant is 0, Then there are either triple roots （ Sharp point ）, Or there are two roots （ Selfing ）

If the discriminant is not 0, Then it must be smooth , That's the elliptic curve .

5, Addition on elliptic curve

With y^2=x^3+ax+b For example

Let's construct an addition operation , Let the addition conform to the rules of the group https://blog.csdn.net/nameofcsdn/article/details/110495499

Cross two points on the curve A、B Draw a straight line , Find the intersection of the line and the elliptic curve , The intersection is about x A point in an axisymmetric position , Defined as A+B, This is called addition .

Thanks to tuyuan https://www.jianshu.com/p/e41bc1eb1d81

Make a straight line about x Axis （ The axis of symmetry of an elliptic curve ） Symmetric line of

therefore A+B+B'=A

To make addition conform to group , We use the law of association , obtain B+B' Is the unit element 0

therefore , We put B The symmetry point of is defined as -B

If A、B coincidence , Then just a little A Make a tangent .

6, Additive group analysis

OK, With this basic operation , Let's make a comprehensive analysis , Can such addition form a group ？

（1） The intersection of a line and a curve

If the line is perpendicular to x The shaft , Then there is no other intersection between the line and the curve , There is no tangency property .

If the line is not perpendicular to x Axis , So there are equations

$\left\{\begin{matrix} y^2=ax^3+bx^2+cx+d\\ y=kx+t\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \end{matrix}\right.$

Since there are already 2 A point of intersection , There must be a third intersection , But there may be coincident solutions , That is, the tangent .

（2） Sealing property

If you want to add any two points, the sum is still in the set , We have all the points on the elliptic curve except , And add an infinity point

namely , Any perpendicular to x Axis line , The points of intersection with the curve are at infinity , So clearly , It is the unit element .

For in x Those points on the axis D（ At least 1 individual , There may be more than one ）, Over time D Make a tangent , It also intersects at infinity ,

in other words ,D=-D, Be careful , This does not lead to D=0,

Similar groups , A group formed by the rotation of a plane ： Group elements refer to the various ways in which the plane rotates around the origin , Group operation is the combination of two rotation modes , The unit element is rotation 0 degree ,D It's rotation 180 degree ,D+D It's rotation 0 degree

（3） Group operations and constants

Group operation is the above addition operation （A+A Is to make a tangent ）, The inverse operation is to take the symmetric point （x The point on the axis and the point of symmetry at infinity are themselves ）,

The only unit element is the infinity

（4） Axioms of groups

The unit element axiom and the elimination axiom are already obvious , Mainly the axiom of associativity .

A+B+C=A+(B+C)

Proof of associativity is difficult , I searched dozens of web pages in Chinese and couldn't find any content about how to prove it , Not even any blogger mentioned the idea , Even after copying around, many bloggers think this is obvious , In fact, this is not obvious .

7, Proof of the associativity of elliptic curve addition

We use Weierstrass normal form, The equations that it intersects with the line are

$\left\{\begin{matrix} y^2=x^3+ax+b\\ y=kx+b\: \: \: \: \: \: \: \! \: \end{matrix}\right.$

According to Weida's Theorem , The sum of the three roots is $-k^{2}$

thus , If you know the two points where the line and curve intersect , You can easily find the coordinates of the third point .

Although groups do not need commutativity , Only abelian groups need commutativity , But the commutativity of elliptic curve addition is too obvious , So you can use it directly .

The following proves the binding associativity：

among It's an addition operation on a curve .

set up P(x1,y1) Q(x2,y2) R(x3,y3)

set up P+Q The coordinates of are （s,t）, that

among Det It's a determinant determinant

set up P+Q+R The coordinates of are （CC,DD）, that

PS： To prove associativity , Just prove ,CC and DD about x1 y1、x2 y2、x3 y3 It's rotation symmetric .

set up Q+R The coordinates of are （u,v）, that

set up Q+R+P The coordinates of are （FF,GG）, that

thus , We've got （CC,DD） and （FF,GG）, They are rotating , Namely the x1 y1 and x3 y3 swap ,

To prove associativity , Just prove CC-FF=0,DD-GG=0

Just prove that the last line of this equation is 0 that will do , However, there are about 100000 cases of violence , Scary pig heart ！

Divide

utilize matlab The result of division is found to be divisible , And this formula is constant 0 Of ,PQ Not constant 0 Of , So it turns out that CC-FF=0, The same can be DD-GG=0

Code ：

syms a b c d e f
A=f*(b-a)+e*(c-a)+d*(b-c);
B=f*(b-a)-e*(c-a)+d*(b-c);
P=(d-e)^2-(a-b)^2*(a+b+c);
Q=(f-e)^2-(b-c)^2*(a+b+c);
S=((a-b)*A*Q)^2-((c-b)*B*P)^2+2*P*Q*((e-d)*A*Q-(e-f)*B*P)+(P*Q)^2*2*(a-c);
T=(b-c)*d^2+(c-a)*e^2+(a-b)*f^2+(a-b)*(b-c)*(c-a)*(a+b+c);
[r,q] = polynomialReduce(S,T)

function ：

r = 0
q =

- 2*a^6*b^3 + 6*a^6*b^2*c - 6*a^6*b*c^2 + 2*a^6*c^3 - 6*a^5*b^3*c + 18*a^5*b^2*c^2 - 18*a^5*b*c^3 + 3*a^5*b*e^2 - 6*a^5*b*e*f + 3*a^5*b*f^2 + 6*a^5*c^4 - 3*a^5*c*e^2 + 6*a^5*c*e*f - 3*a^5*c*f^2 + 6*a^4*b^5 - 12*a^4*b^4*c - 6*a^4*b^3*c^2 + 30*a^4*b^2*c^3 - 2*a^4*b^2*e^2 + 8*a^4*b^2*e*f - 6*a^4*b^2*f^2 - 24*a^4*b*c^4 + 4*a^4*b*c*e^2 - 16*a^4*b*c*e*f + 12*a^4*b*c*f^2 + 6*a^4*c^5 - 2*a^4*c^2*e^2 + 8*a^4*c^2*e*f - 6*a^4*c^2*f^2 + 12*a^3*b^5*c - 24*a^3*b^4*c^2 - 2*a^3*b^3*c^3 + 3*a^3*b^3*d^2 - 8*a^3*b^3*d*e + 6*a^3*b^3*d*f - 3*a^3*b^3*e^2 + 2*a^3*b^3*e*f + 30*a^3*b^2*c^4 - 9*a^3*b^2*c*d^2 + 18*a^3*b^2*c*d*e - 12*a^3*b^2*c*d*f - 4*a^3*b^2*c*e^2 + 22*a^3*b^2*c*e*f - 15*a^3*b^2*c*f^2 - 18*a^3*b*c^5 + 9*a^3*b*c^2*d^2 - 12*a^3*b*c^2*d*e + 6*a^3*b*c^2*d*f + 5*a^3*b*c^2*e^2 - 26*a^3*b*c^2*e*f + 18*a^3*b*c^2*f^2 + 2*a^3*c^6 - 3*a^3*c^3*d^2 + 2*a^3*c^3*d*e + 2*a^3*c^3*e^2 + 2*a^3*c^3*e*f - 3*a^3*c^3*f^2 + 2*a^3*d*e^3 - 6*a^3*d*e^2*f + 6*a^3*d*e*f^2 - 2*a^3*d*f^3 - 3*a^3*e^4 + 8*a^3*e^3*f - 6*a^3*e^2*f^2 + a^3*f^4 - 6*a^2*b^7 + 6*a^2*b^6*c + 18*a^2*b^5*c^2 - 24*a^2*b^4*c^3 + 2*a^2*b^4*d*e - 6*a^2*b^4*d*f + 4*a^2*b^4*e^2 - 6*a^2*b^4*e*f + 6*a^2*b^4*f^2 - 6*a^2*b^3*c^4 + 6*a^2*b^3*c*d^2 - 14*a^2*b^3*c*d*e + 18*a^2*b^3*c*d*f - a^2*b^3*c*e^2 - 12*a^2*b^3*c*e*f + 3*a^2*b^3*c*f^2 + 18*a^2*b^2*c^5 - 18*a^2*b^2*c^2*d^2 + 30*a^2*b^2*c^2*d*e - 18*a^2*b^2*c^2*d*f - 6*a^2*b^2*c^2*e^2 + 30*a^2*b^2*c^2*e*f - 18*a^2*b^2*c^2*f^2 - 6*a^2*b*c^6 + 18*a^2*b*c^3*d^2 - 26*a^2*b*c^3*d*e + 6*a^2*b*c^3*d*f + 5*a^2*b*c^3*e^2 - 12*a^2*b*c^3*e*f + 9*a^2*b*c^3*f^2 - 3*a^2*b*d^2*e^2 + 6*a^2*b*d^2*e*f - 3*a^2*b*d^2*f^2 + 4*a^2*b*d*e^3 - 8*a^2*b*d*e^2*f + 4*a^2*b*d*e*f^2 + 2*a^2*b*e^4 - 4*a^2*b*e^3*f - a^2*b*e^2*f^2 + 6*a^2*b*e*f^3 - 3*a^2*b*f^4 - 6*a^2*c^4*d^2 + 8*a^2*c^4*d*e - 2*a^2*c^4*e^2 + 3*a^2*c*d^2*e^2 - 6*a^2*c*d^2*e*f + 3*a^2*c*d^2*f^2 - 4*a^2*c*d*e^3 + 8*a^2*c*d*e^2*f - 4*a^2*c*d*e*f^2 + a^2*c*e^4 - 2*a^2*c*e^3*f + a^2*c*e^2*f^2 - 6*a*b^7*c + 6*a*b^6*c^2 + 12*a*b^5*c^3 - 3*a*b^5*d^2 + 8*a*b^5*d*e - 6*a*b^5*d*f + 4*a*b^5*e*f - 3*a*b^5*f^2 - 12*a*b^4*c^4 + 6*a*b^4*c*d^2 - 8*a*b^4*c*d*e + 4*a*b^4*c*e^2 - 8*a*b^4*c*e*f + 6*a*b^4*c*f^2 - 6*a*b^3*c^5 + 3*a*b^3*c^2*d^2 - 12*a*b^3*c^2*d*e + 18*a*b^3*c^2*d*f - a*b^3*c^2*e^2 - 14*a*b^3*c^2*e*f + 6*a*b^3*c^2*f^2 + 6*a*b^2*c^6 - 15*a*b^2*c^3*d^2 + 22*a*b^2*c^3*d*e - 12*a*b^2*c^3*d*f - 4*a*b^2*c^3*e^2 + 18*a*b^2*c^3*e*f - 9*a*b^2*c^3*f^2 + a*b^2*d^2*e^2 - 4*a*b^2*d^2*e*f + 3*a*b^2*d^2*f^2 - 4*a*b^2*d*e^3 + 18*a*b^2*d*e^2*f - 20*a*b^2*d*e*f^2 + 6*a*b^2*d*f^3 - 8*a*b^2*e^3*f + 17*a*b^2*e^2*f^2 - 12*a*b^2*e*f^3 + 3*a*b^2*f^4 + 12*a*b*c^4*d^2 - 16*a*b*c^4*d*e + 4*a*b*c^4*e^2 - 2*a*b*c*d^2*e^2 + 8*a*b*c*d^2*e*f - 6*a*b*c*d^2*f^2 - 8*a*b*c*d*e^2*f + 8*a*b*c*d*e*f^2 + 2*a*b*c*e^4 - 2*a*b*c*e^2*f^2 - 3*a*c^5*d^2 + 6*a*c^5*d*e - 3*a*c^5*e^2 + a*c^2*d^2*e^2 - 4*a*c^2*d^2*e*f + 3*a*c^2*d^2*f^2 - 2*a*c^2*d*e^3 + 8*a*c^2*d*e^2*f - 6*a*c^2*d*e*f^2 + a*c^2*e^4 - 4*a*c^2*e^3*f + 3*a*c^2*e^2*f^2 + 2*b^9 - 6*b^7*c^2 - 2*b^6*d*e + 6*b^6*d*f - 2*b^6*e^2 - 2*b^6*e*f + 6*b^5*c^4 - 3*b^5*c*d^2 + 4*b^5*c*d*e - 6*b^5*c*d*f + 8*b^5*c*e*f - 3*b^5*c*f^2 + 6*b^4*c^2*d^2 - 6*b^4*c^2*d*e - 6*b^4*c^2*d*f + 4*b^4*c^2*e^2 + 2*b^4*c^2*e*f - 2*b^3*c^6 + 2*b^3*c^3*d*e + 6*b^3*c^3*d*f - 3*b^3*c^3*e^2 - 8*b^3*c^3*e*f + 3*b^3*c^3*f^2 - b^3*d^4 + 6*b^3*d^3*e - 4*b^3*d^3*f - 10*b^3*d^2*e^2 + 10*b^3*d^2*e*f + 8*b^3*d*e^3 - 16*b^3*d*e^2*f + 10*b^3*d*e*f^2 - 4*b^3*d*f^3 - 2*b^3*e^4 + 8*b^3*e^3*f - 10*b^3*e^2*f^2 + 6*b^3*e*f^3 - b^3*f^4 - 6*b^2*c^4*d^2 + 8*b^2*c^4*d*e - 2*b^2*c^4*e^2 + 3*b^2*c*d^4 - 12*b^2*c*d^3*e + 6*b^2*c*d^3*f + 17*b^2*c*d^2*e^2 - 20*b^2*c*d^2*e*f + 3*b^2*c*d^2*f^2 - 8*b^2*c*d*e^3 + 18*b^2*c*d*e^2*f - 4*b^2*c*d*e*f^2 - 4*b^2*c*e^3*f + b^2*c*e^2*f^2 + 3*b*c^5*d^2 - 6*b*c^5*d*e + 3*b*c^5*e^2 - 3*b*c^2*d^4 + 6*b*c^2*d^3*e - b*c^2*d^2*e^2 + 4*b*c^2*d^2*e*f - 3*b*c^2*d^2*f^2 - 4*b*c^2*d*e^3 - 8*b*c^2*d*e^2*f + 6*b*c^2*d*e*f^2 + 2*b*c^2*e^4 + 4*b*c^2*e^3*f - 3*b*c^2*e^2*f^2 + c^3*d^4 - 2*c^3*d^3*f - 6*c^3*d^2*e^2 + 6*c^3*d^2*e*f + 8*c^3*d*e^3 - 6*c^3*d*e^2*f - 3*c^3*e^4 + 2*c^3*e^3*f - 2*d^3*e^3 + 6*d^3*e^2*f - 6*d^3*e*f^2 + 2*d^3*f^3 + 6*d^2*e^4 - 18*d^2*e^3*f + 18*d^2*e^2*f^2 - 6*d^2*e*f^3 - 6*d*e^5 + 18*d*e^4*f - 18*d*e^3*f^2 + 6*d*e^2*f^3 + 2*e^6 - 6*e^5*f + 6*e^4*f^2 - 2*e^3*f^3

8, Abelian group

After proving associativity , An addition on an elliptic curve is a group , Because of the inherent exchangeability , So that it is an Abelian group .

3、 ... and , Elliptic curves over prime fields

1, Finite field 、 Prime field

https://blog.csdn.net/nameofcsdn/article/details/105172684

Prime field Fp： from p Elements （ from 0 To p-1） And number theory plus, minus, multiplication and division

2, Elliptic curves over prime fields

Elliptic curve Ep(a,b), $y^2\equiv x^3+ax+b(modp)$ , x,y∈[0,p-1]

among p Prime number , Non-negative integer a、b Less than p And meet $4a^3+27b^2\neq 0(modp)$

Elliptic curves over prime fields , Except for all points satisfying the congruence equation , Also need to add an additional infinity point , Unit element O spot

Write a simple program , Let's feel the distribution of points on an elliptic curve .


#include<iostream>
#include<windows.h>
#include<map>
using namespace std;

#define CIN(x) while (!(cin >> x)) { \
        cin.clear();      \
        cin.ignore();     \
    }
#define CIN2(x, y) CIN(x)CIN(y)
#define CIN3(x, y, z) CIN(x)CIN(y)CIN(z)

const int M = 10000;

bool check(int p)
{
    if(p<3 || p>M)return false;
    if(p%2==0)return false;
    for(int i=3;i*i<=p;i+=2)if(p%i==0)return false;
    return true;
}

void play()
{
    cout<<"y^2=x^3+ax+b(mod p), Input p,a,b\n";
    int p,a,b;
    CIN3(p,a,b);
    if(!check(p))return;
    a=(a%p+p)%p,b=(b%p+p)%p;
    map<int,int>modSqrt;
    for(int i=0;i<=p/2;i++)modSqrt[i*i%p]=i+1;
    for(int i=0;i<p;i++){
        int x=(i*i*i+a*i+b)%p;
        if(modSqrt[x]==0)continue;
        if(modSqrt[x]==1)cout<<i<<" "<<0<<"    ";
        else cout<<i<<" "<<modSqrt[x]-1<<"    "<<i<<" "<<p-modSqrt[x]+1<<"    " ;
    }
}

int main() {
    for(int i=0;i<10;i++){
        play();
        sleep(5);
    }
    return 0;
}

Input 23 1 3, Output ：

0 7 0 16 2 6 2 17 4 5 4 18 5 8 5 15 6 8 6 15 7 10 7 13 10 1 10 22 12 8 12 15 14 1 14 22 15 9 15 14 19 2 19 21 21 4 21 19 22 1 22 22

Plus O spot , altogether 27 A little bit .

Change to visual version ：

void play()
{
    cout<<"y^2=x^3+ax+b(mod p), Input p,a,b\n";
    int p,a,b;
    CIN3(p,a,b);
    if(!check(p))return;
    a=(a%p+p)%p,b=(b%p+p)%p;
    map<int,int>modSqrt;
    for(int i=0;i<=p/2;i++)modSqrt[i*i%p]=i+1;
    if(p>30)return;
    int pla[30][30]={0};
    for(int i=0;i<p;i++){
        int x=(i*i*i+a*i+b)%p;
        if(modSqrt[x]==0)continue;
        pla[i][modSqrt[x]-1]=1,pla[i][p-modSqrt[x]+1]=1;
    }
    for(int j=p-1;j>=0;j--){
        for(int i=0;i<p;i++){
            if(pla[i][j])cout<<'*';
            else cout<<'.';
        }
        cout<<endl;
    }
}

Modify the screenshot of the output result to get ：

above 13 A dot and below 13 The points are symmetric ,O Points exist alone .

Accurately speaking , For this p That's ok p Columns of squares , above p-1 Rows are symmetrical up and down .

let me put it another way , If you put the （p-1）/ 2 Move the line loop down , You'll get y=0 This behavior is about the axis of symmetry , A symmetrical one p That's ok p The square of the column .

3, Addition of elliptic curves over prime fields

（1） Define intersections

Same as in real fields ,P and Q Connected lines and curves intersect at R,P(x1,y1), Q(x2,y2), R(x3,y3) All three points are in a straight line y=kx+b On ,

that x1+x2+x3=k^2, among k It's the slope .

（2） Define the inverse element

alike , Symmetrical to each other 2 A little bit A and A' Elements that are opposite to each other ,A+A'=O

（3） Define addition

if P(x1,y1), Q(x2,y2), R(x3,y3) Satisfy P+Q=R,

be $x_3=k^2-x_1-x_2,\, y_3=k(x_1-x_3)-y_1$ , among k It's a straight line PQ The slope of ,

（3.1） if $P\neq Q$ , be $k=\frac{y_2-y_1}{x_2-x_1}$

if x1=x2, be k Is infinity ,R It's infinity O

（3.2） if P=Q, be PQ It's a tangent line , $k=\frac{3x_1^2+a}{2y_1}$

if y1=0, be k Is infinity ,R It's infinity O

（4） Abelian group

Addition over prime fields , It is also the Abelian group , And it's a cyclic group .

（5）demo Program

#include<iostream>
#include<map>
using namespace std;

long long get_mi(long long n,int k,int p)
{
	if (k == 0)return 1;
	long long r = get_mi(n, k / 2,p) % p;
	r = (r*r) % p;
	if (k % 2)r = (r*n) % p;
	return r;
}

long long reverse(int a,int p)
{
    return get_mi(a,p-2,p);
}

#define CIN(x) while (!(cin >> x)) { \
        cin.clear();      \
        cin.ignore();     \
    }
#define CIN2(x, y) CIN(x)CIN(y)
#define CIN3(x, y, z) CIN(x)CIN(y)CIN(z)

const int M = 10000;

bool check(int p)
{
    if(p<3 || p>M)return false;
    if(p%2==0)return false;
    for(int i=3;i*i<=p;i+=2)if(p%i==0)return false;
    return true;
}

bool isO(int x,int y)
{
    return x==0 && y==0;
}

void setO(int &x,int &y)
{
    x=0,y=0;
}

int p,a,b;

void play()
{
    cout<<"y^2=x^3+ax+b(mod p),input p,a,b\n";

    CIN3(p,a,b);
    if(!check(p))return;
    a=(a%p+p)%p,b=(b%p+p)%p;
    map<int,int>modSqrt;
    for(int i=0;i<=p/2;i++)modSqrt[i*i%p]=i+1;
    for(int i=0;i<p;i++){
        int x=(i*i*i+a*i+b)%p;
        if(modSqrt[x]==0)continue;
        if(modSqrt[x]==1)cout<<i<<" "<<0<<"    ";
        else cout<<i<<" "<<modSqrt[x]-1<<"    "<<i<<" "<<p-modSqrt[x]+1<<"    " ;
    }
}

void add(int x1,int y1,int x2,int y2,int &x3,int &y3)
{
    int k;
    if(isO(x1,y1))x3=x2,y3=y2;
    else if(isO(x2,y2))x3=x1,y3=y1;
    else if(x1==x2&&y1==y2){
        if(y1==0)setO(x3,y3);
        else k=(x1*x1*3+a)%p*(p+1)/2*reverse(y1,p)%p,x3=((k*k-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }else{
        if(x1==x2)setO(x3,y3);
        else k=(y2-y1)*reverse(x2-x1,p)%p,x3=((k*k-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }
}

void play2(int n)
{
    int x1,y1,x2,y2,x3,y3,k;
    while(n--){
        cout<<"\n input x1,y1,x2,y2\n";
        CIN2(x1,y1);
        CIN2(x2,y2);
        add(x1,y1,x2,y2,x3,y3);
        cout<<x3<<" "<<y3;
    }
}

int main()
{
    play();
    play2(10);
	return 0;
}

function ：

among , Infinity can be represented in many ways , For convenience, any point not on the curve can be selected in the finite field , For example, when b Not for 0 when ,（0,0） It can be used to represent the point of infinity .

4, The number of points on the prime field ——Hasse Theorem

corollary 2 yes theorem 1 stay k=1 A corollary of the special case of time

5, Generating subgroups

The whole set formed by addition is a finite group , The number multiplication of a single element constitutes its subgroup .

According to Lagrange's Theorem https://blog.csdn.net/nameofcsdn/article/details/110495499

The order of a subgroup must be a divisor of the group order .

Or to E(23,1,3) For example , Let's look at the order of the generated subgroup of each element ：

#include<iostream>
#include<map>
#include<vector>
using namespace std;

long long get_mi(long long n,int k,int p)
{
	if (k == 0)return 1;
	long long r = get_mi(n, k / 2,p) % p;
	r = (r*r) % p;
	if (k % 2)r = (r*n) % p;
	return r;
}

long long reverse(int a,int p)
{
    return get_mi(a,p-2,p);
}

#define CIN(x) while (!(cin >> x)) { \
        cin.clear();      \
        cin.ignore();     \
    }
#define CIN2(x, y) CIN(x)CIN(y)
#define CIN3(x, y, z) CIN(x)CIN(y)CIN(z)

const int M = 10000;

bool check(int p)
{
    if(p<3 || p>M)return false;
    if(p%2==0)return false;
    for(int i=3;i*i<=p;i+=2)if(p%i==0)return false;
    return true;
}

bool isO(int x,int y)
{
    return x==0 && y==0;
}

void setO(int &x,int &y)
{
    x=0,y=0;
}

int p,a,b;
vector<int>vx;
vector<int>vy;


void play()
{
    cout<<"y^2=x^3+ax+b(mod p),input p,a,b\n";
    CIN3(p,a,b);
    if(!check(p))return;
    a=(a%p+p)%p,b=(b%p+p)%p;
    map<int,int>modSqrt;
    for(int i=0;i<=p/2;i++)modSqrt[i*i%p]=i+1;
    for(int i=0;i<p;i++){
        int x=(i*i*i+a*i+b)%p;
        if(modSqrt[x]==0)continue;
        if(modSqrt[x]==1)vx.push_back(i),vy.push_back(0);
        else vx.push_back(i),vx.push_back(i),vy.push_back(modSqrt[x]-1),vy.push_back(p-modSqrt[x]+1);
    }
    int x,y;
    setO(x,y);
    vx.push_back(x),vy.push_back(y);
}

void add(int x1,int y1,int x2,int y2,int &x3,int &y3)
{
    int k;
    if(isO(x1,y1))x3=x2,y3=y2;
    else if(isO(x2,y2))x3=x1,y3=y1;
    else if(x1==x2&&y1==y2){
        if(y1==0)setO(x3,y3);
        else k=(x1*x1*3+a)%p*(p+1)/2*reverse(y1,p)%p,x3=((k*k-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }else{
        if(x1==x2)setO(x3,y3);
        else k=(y2-y1)*reverse(x2-x1,p)%p,x3=((k*k-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }
}

void getJ()
{
    int x1,y1,x2,y2;
    for(int i=0;i<vx.size();i++) {
        x1=x2=vx[i],y1=y2=vy[i];
        int s=1;
        while(!isO(x1,y1)){
            s++;
            add(x1,y1,x2,y2,x1,y1);
        }
        cout<<x2<<" "<<y2<<"   "<<s<<"      ";
    }
}

int main()
{
    play();
    getJ();
	return 0;
}

Input 23 1 3 , Output ：

0 7 27 0 16 27 2 6 27 2 17 27 4 5 9 4 18 9 5 8 27 5 15 27 6 8 27
6 15 27 7 10 27 7 13 27 10 1 9 10 22 9 12 8 3 12 15 3 14 1 27
14 22 27 15 9 27 15 14 27 19 2 9 19 21 9 21 4 27 21 19 27 22 1 27
22 22 27 0 0 1

It's not hard to find the law , The orders of all elements are divisors of large group orders , We divide the divisor of the order of a large group by the order of the element, which is called the Cofactor co-factor

When encrypting , Generally, the element with the smallest cofactor is selected .

about E(23,1,3), For each divisor , The number of elements whose order is this divisor is an Euler function , That is to say φ(27) The order of the elements is 27

For other curves , Not necessarily a cyclic group .

PS： $\sum _{d|n}\varphi (d)=n$

Four ,ECC Elliptic curve encryption

1, Mathematical calculation

Because the addition over a finite field is an Abelian group , Therefore, Egyptian multiplication can be used to calculate the number multiplication https://blog.csdn.net/nameofcsdn/article/details/110448717

therefore , For any point P, Arbitrary positive integer k, Calculation Q=kP It's easy , According to the P and Q Calculation k It's hard , The best algorithm at present is O（sqrt(p)） Time complexity of ,BSGS Algorithm https://blog.csdn.net/nameofcsdn/article/details/116059802

2, Encryption scheme

P、Q Exposed as a public key ,k Keep as private key

The sender converts the information into a point on the curve A, And produce a random integer x, And calculate 2 A little bit ：xP and xQ

And then B=xP and C=A+xQ this 2 Points are sent to the receiver .

The receiver receives B and C after , according to C-kB=A+xQ-kxP=A You can work out A

3, The solution

（1） according to P and Q Calculate the private key k, All the information encrypted with the public key is cracked at one time

（2） according to B=xP Calculate the random encryption seed x, Can only be cracked with x Encrypted information , That is, only a single piece of information can be cracked .

Now it's normal p Take binary 200 position ,sqrt(p) Namely 100 position , namely 10^30

The computing power of today's supercomputers is probably 10^17, Cracking needs 30 In ten thousand,

4,constant-time Design

The receiver completes the calculation C-kB The time is only with k of ,

Accurately speaking , The time of fast power algorithm is only equal to k The number of digits is related to , Therefore, the cracker can narrow the scope according to the running time of the algorithm , To crack k, namely Time bypass attack

To avoid time bypass attacks , The number of cycles can be controlled manually , Namely the k Number of fixed length , Such as X25519 No matter what k What is the actual length of , It's all regarded as 256 position .

5、 ... and ,Montgomery curve 、X25519

1,Montgomery curve

（1） equation

Curve equation ：By^2=x(x^2+Ax+1), among B(A^2-4) Not for 0

Montgomery The curve has three forms ：

When A^2-4=0 when , The curve will have a solitary point （1,0） perhaps （-1,0）

Montgomery The curve should have no cusps or self intersecting shapes .

（2）Weierstrass and Montgomery Interturn

although x(x^2+Ax+1)=0 This cubic equation can be solved directly , There is no need to find the root formula ,

But we can still use the statute method of finding the root formula , Make x = u - A/3, Turn it into something about u A cubic polynomial without a quadratic term ,

Then make By^2=v^2, This way Montgomery Turned into Weierstrass, On the contrary, the same is true .

（3） Add

if P(x1,y1), Q(x2,y2), R(x3,y3) Satisfy P+Q=R,

be $x_3=Bk^2-A-x_1-x_2,\, y_3=k(x_1-x_3)-y_1$ , among k It's a straight line PQ The slope of ,

（3.1） if $P\neq Q$ , be $k=\frac{y_2-y_1}{x_2-x_1}$

if x1=x2, be k Is infinity ,R It's infinity O

（3.2） if P=Q, be PQ It's a tangent line , $k=\frac{3x_1^2+2Ax_1+1}{2By_1}$

if y1=0, be k Is infinity ,R It's infinity O

2, On Finite Fields Montgomery curve

（1） The only fixed point

（0,0） The only point on the curve that can be determined , And the order of this point is obviously 2

（2） rank

In any finite field, B(A+ 2), B(A−2), and A^2 −4 cannot all be nonsquares simultaneously

The paper ：https://eprint.iacr.org/2017/212.pdf

because B(A+ 2)*B(A−2)=B^2*（A^2 −4） therefore There are at least three 1 One is the square remainder

（2.1） If B(A+2) Is the square residue , Then there must be something on a finite field X The abscissa of is 1, And pass by X The tangent of just goes through （0,0）, therefore X The order is 4

（2.2） If B(A-2) Is the square residue , Then there must be something on a finite field X The abscissa of is -1, And pass by X The tangent of just goes through （0,0）, therefore X The order is 4

（2.3） If B(A+2) and B(A-2) Are not square residuals , be A^2 −4 Is the square residue , equation x^2+Ax+1 There is 2 Two different solutions , And not for 0, That is to say 3 The three different points satisfy the vertical coordinate of 0

So this 3 Points plus infinity can form a subgroup , The order of this subgroup is 4

So the large group order must be 4 Multiple , That is, the number of all points on the curve is 4 Multiple 0

My code ：

#include<iostream>
#include<map>
#include<vector>
using namespace std;

//  The omitted code is the same as above 

#define XOO -12345678
bool isO(int x,int y)
{
    return x==XOO && y==XOO;
}

void setO(int &x,int &y)
{
    x=XOO,y=XOO;
}

int p,a,b;
vector<int>vx;
vector<int>vy;


void play()
{
    cout<<"By^2=x^3+Ax^2+x(mod p),input p,A,B\n";
    CIN3(p,a,b);
    if(!check(p))return;
    a=(a%p+p)%p,b=(b%p+p)%p;
    map<int,int>modSqrt;
    for(int i=0;i<=p/2;i++)modSqrt[i*i%p]=i+1;
    for(int i=0;i<p;i++){
        int x=(i*i*i+a*i*i+i)%p;
        x=x*reverse(b,p)%p;
        if(modSqrt[x]==0)continue;
        if(modSqrt[x]==1)vx.push_back(i),vy.push_back(0);
        else vx.push_back(i),vx.push_back(i),vy.push_back(modSqrt[x]-1),vy.push_back(p-modSqrt[x]+1);
    }
    int x,y;
    setO(x,y);
    vx.push_back(x),vy.push_back(y);
}

void add(int x1,int y1,int x2,int y2,int &x3,int &y3)
{
    int k;
    if(isO(x1,y1))x3=x2,y3=y2;
    else if(isO(x2,y2))x3=x1,y3=y1;
    else if(x1==x2&&y1==y2){
        if(y1==0)setO(x3,y3);
        else k=(x1*x1*3+x1*a*2+1)%p*(p+1)/2*reverse(y1,p)%p*reverse(b,p)%p,x3=((k*k*b-a-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }else{
        if(x1==x2)setO(x3,y3);
        else k=(y2-y1)*reverse(x2-x1,p)%p,x3=((k*k*b-a-x1-x2)%p+p)%p,y3=((k*(x1-x3)-y1)%p+p)%p;
    }
}

void getJ()
{
    int x1,y1,x2,y2;
    cout<<vx.size()<<endl;
    for(int i=0;i<vx.size();i++) {
        x1=x2=vx[i],y1=y2=vy[i];
        int s=1;
        while(!isO(x1,y1)){
            s++;
            add(x1,y1,x2,y2,x1,y1);
        }
        cout<<x2<<" "<<y2<<"   "<<s<<"      ";
    }
}

void play2(int n)
{
    int x1,y1,x2,y2,x3,y3;
    while(n--){
        cout<<"\n input x1,y1,x2,y2\n";
        CIN2(x1,y1);
        CIN2(x2,y2);
        add(x1,y1,x2,y2,x3,y3);
        cout<<x3<<" "<<y3;
    }
}

int main()
{
    play();
    getJ();
    play2(40);
	return 0;
}

The code is basically the same as Weierstrass The code of the equation is the same , Just change the parameters , In addition, the infinity point should be expressed in another way .

function ：

By^2=x^3+Ax^2+x(mod p),input p,A,B
23 11 5
32
0 0   2      3 9   16      3 14   16      4 9   16      4 14   16      5 9   8      5 14   8      6 2   16      6 21   16
7 7   4      7 16   4      8 1   16      8 22   16      9 6   16      9 17   16      10 10   4      10 13   4
11 1   8      11 22   8      13 8   16      13 15   16      14 7   8      14 16   8      15 0   2      16 1   16
16 22   16      18 11   16      18 12   16      20 0   2      21 4   8      21 19   8      -12345678 -12345678   1

3,X25519（Curve25519）

（1） equation

X25519 The equation of ：y^2=x^3+486662x^2+x,p=2^255-19

rfc7748：https://tools.ietf.org/html/rfc7748

The following are macro and micro charts

486662 This value should be based on 2^255-19 Calculate the , The goal is not to be too big （ The algorithm should be fast ） And the order must have a large factor

Because the order J It must be 4 Multiple , So the factor of order is probably at most J/4, The second most likely is J/8, and J The size of can only fluctuate in a very limited range （Hasse Theorem ）

So the ideal solution is J=4p, among p Prime number ,p About equal to 2^253, perhaps J=8p, among p Prime number ,p About equal to 2^252

486662 Corresponding to the latter scheme .

（2） basic point

Base point x=9,y=14781619447589544791020593568409986887264606134616475288964881837755586237401

Order is 2^252+27742317777372353535851937790883648493（ prime number ）, Cofactor co-factor=8

It can be used python The command line verifies the coordinate value of the base point ：

6、 ... and ,Edwards curve 、ED25519

1,Edwards curve

（1） equation

au^2 + v^2 = 1 + du^2v^2

Can be reduced to u^2 + v^2 = 1 + du^2v^2 （ If a Is the square residue ）

or -u^2 + v^2 = 1 + du^2v^2 （ If -a Is the square residue ）

（2）Montgomery and Edwards Interturn

Can be reduced to u^2 + v^2 = 1 + du^2v^2,d=(A-2)/(A+2) （ If B(A+2) Is the square residue ）

or -u^2 + v^2 = 1 + du^2v^2,d=-(A-2)/(A+2) （ If -B(A+2) Is the square residue ）

2,ED25519

（1） equation

direct Montgomery The handlebar in X25519 Turn it into Edwards：

y^2=x^3+486662x^2+x,p=2^255-19 namely A=486662,B=1

therefore a=486664, d=486660

namely 486664u^2 + v^2 = 1 + 486660u^2v^2

Whether it can be regulated depends on 486664 Is it square remainder

$\left ( \frac{486664}{p} \right )=\left ( \frac{2}{p} \right )\left ( \frac{127}{p} \right )\left ( \frac{479}{p} \right )$

According to the law of quadratic reciprocity $\left(\frac{2}{{p}}\right)=(-1)^{\frac{p^{2}-1}{8}}$ , $\left(\frac{{p}}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\left(\frac{q}{p}\right)$

You can get $\left ( \frac{2}{p} \right )=-1, \left ( \frac{127}{p} \right )=\left ( \frac{p}{127} \right )=\left ( \frac{116}{127} \right ), \left ( \frac{479}{p} \right )=\left ( \frac{p}{479} \right )=\left ( \frac{373}{479} \right )$

therefore $\left ( \frac{486664}{p} \right )=-\left ( \frac{116}{127} \right )\left ( \frac{373}{479} \right )=-\left ( \frac{127}{29} \right )\left ( \frac{479}{373} \right )=-1*(-1)*1=1$

And according to Euler's rule , $\left ( \frac{-1}{p} \right )=1$

therefore , 486664u^2 + v^2 = 1 + 486660u^2v^2 It can be stipulated as u^2 + v^2 = 1 + du^2v^2,d=121665/121666

It can also be stipulated as -u^2 + v^2 = 1 + du^2v^2,d=-121665/121666

That's why you can always see it on the Internet 2 Versions ED25519

（2） basic point

-u^2 + v^2 = 1 + du^2v^2,d=-121665/121666

rfc7748 What is given in is 37095705934669439343138083508754565189542113879843219016388785533085940283555, and -121665/121666 It's the same number

basic point u=15112221349535400772501151409588531511454012693041857206046113283949847762202

v=46316835694926478169428394003475163141307993866256225615783033603165251855960

In fact, this basic point is X25519 The basis of x=9

verification d Value ：

Verify the coordinate value of the base point ：

Verify that the two base points are the same , namely v=(x-1)/(x+1)

PS： Out-of-service u=x/y To verify , Because at the time of the statute u The value of has changed

7、 ... and , Summary

All the data presented in this article , The following items are given in the standard but I have not verified them ：

（1）p=2^255-19 Prime number

（2） The order of the base point is equal to 2^252+27742317777372353535851937790883648493

（3） The order of the base point is prime

Prime number detection is troublesome , Order is relatively easy to verify , You only need to verify the 2^252+27742317777372353535851937790883648493 Times is the point at infinity ,

Based on the fact that this number is a prime number , Plus Lagrange's theorem , It can be proved that this number is the order of the base point .

原网站

版权声明
本文为[csuzhucong]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202280519061046.html