OpenSSL入门-椭圆曲线

数学基础

例如求椭圆曲线$y^2=x^3-x$在有限域$\operatorname{GF}(89)$上所有点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#define MAX 100
typedef struct point {
    int point_x;
    int point_y;
}Point;
typedef struct ecc {
    struct point p[MAX];
    int len;
}ECCPoint;
typedef struct generator {
    Point p;
    int p_class;
}GENE_SET;
char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
ECCPoint eccPoint;
GENE_SET geneSet[MAX];
int geneLen;
char plain[] = "yes";
int m[MAX];
int cipher[MAX];
int nB;//私钥
Point P1, P2, Pt, G, PB;
Point Pm;
int C[MAX];
//取模函数
int mod_p(int s) {
    int i;	//保存s/p的倍数
    int result;	//模运算的结果
    i = s / p;
    result = s - i * p;
    if (result >= 0)
        return result;
    else
        return result + p;
}
//判断平方根是否为整数 
int int_sqrt(int s) {
    int temp;
    temp = (int)sqrt(s);//转为整型 
    if (temp * temp == s)
        return temp;
    else
        return -1;
}
//打印点集 
void print() {
    int i;
    int len = eccPoint.len;
    printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
    for (i = 0; i < len; i++) {
        if (i % 8 == 0)
            printf("\n");
        printf("(%2d,%2d)\t", eccPoint.p[i].point_x, eccPoint.p[i].point_y);
    }
    printf("\n");
}
void get_all_points() {
    int i = 0;
    int j = 0;
    int s, y = 0;
    int n = 0, q = 0;
    int modsqrt = 0;
    int flag = 0;
    if (4 * a * a * a + 27 * b * b != 0) {
        for (i = 0; i <= p - 1; i++) {
            flag = 0;
            n = 1;
            y = 0;
            s = i * i * i + a * i + b;
            while (s < 0)
                s += p;
            s = mod_p(s);
            modsqrt = int_sqrt(s);
            if (modsqrt != -1) {
                flag = 1;
                y = modsqrt;
            }
            else
                while (n <= p - 1) {
                    q = s + n * p;
                    modsqrt = int_sqrt(q);
                    if (modsqrt != -1) {
                        y = modsqrt;
                        flag = 1;
                        break;
                    }
                    flag = 0;
                    n++;
                }
            if (flag == 1) {
                eccPoint.p[j].point_x = i;
                eccPoint.p[j].point_y = y;
                j++;
                if (y != 0) {
                    eccPoint.p[j].point_x = i;
                    eccPoint.p[j].point_y = (p - y) % p;  //注意：P(x,y)的负元是 (x,p-y)
                    j++;
                }
            }
        }
        eccPoint.len = j;//点集个数 
        print(); //打印点集 
    }
}
int main() {
    get_all_points();
}

例如实现点加和倍点算法，其中点加运算公式为：

设$P(x_1,y_1),Q(x_2,y_2)$，得$P+Q=R(x_3,y_3)$，有：
$$
\begin{cases}
x_3=\left(\dfrac{y_2-y_1}{x_2-x_1}\right)^2-x_1-x_2,\
y_3=-\left(\dfrac{y_2-y_1}{x_2-x_1}\right)x_3+\left(\dfrac{y_2-y_1}{x_2-x_1}\right)x_1+y_1
\end{cases}
$$
对于倍点运算，$P+Q=2P=R$，有：
$$
\begin{cases}
x_3=\left(\dfrac{3x_1^2+a}{2y_1}\right)^2-2x_1,\
y_3=-\left(\dfrac{3x_1^2+a}{2y_1}\right)x_3+\left(\dfrac{3x_1^2+a}{2y_1}\right)x_1-y_1
\end{cases}
$$
实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#define MAX 100
typedef struct point {
    int point_x;
    int point_y;
}Point;
int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
//求b关于n的逆元 
int inverse(int n, int b) {
    int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
    while (r2 > 0) {
        q = r1 / r2;
        r = r1 % r2;
        r1 = r2;
        r2 = r;
        t = t1 - q * t2;
        t1 = t2;
        t2 = t;
    }
    if (t1 >= 0)
        return t1 % n;
    else {
        while ((t1 + i * n) < 0)
            i++;
        return t1 + i * n;
    }
}
//两点的加法运算 
Point add_two_points(Point p1, Point p2) {
    long t;
    int x1 = p1.point_x;
    int y1 = p1.point_y;
    int x2 = p2.point_x;
    int y2 = p2.point_y;
    int tx, ty;
    int x3, y3;
    int flag = 0;
    //求 
    if ((x2 == x1) && (y2 == y1)) {
        //相同点相加 
        if (y1 == 0)
            flag = 1;
        else
            t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
        //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
    }
    else {
        //不同点相加
        ty = y2 - y1;
        tx = x2 - x1;
        while (ty < 0)
            ty += p;
        while (tx < 0)
            tx += p;
        if (tx == 0 && ty != 0)
            flag = 1;
        else
            t = ty * inverse(p, tx) % p;
    }
    if (flag == 1) {
        p2.point_x = -1;
        p2.point_y = -1;
    }
    else {
        x3 = (t * t - x1 - x2) % p;
        y3 = (t * (x1 - x3) - y1) % p;
        //使结果在有限域GF(P)上 
        while (x3 < 0)
            x3 += p;
        while (y3 < 0)
            y3 += p;
        p2.point_x = x3;
        p2.point_y = y3;
    }
    return p2;
}
int main() {
    Point p1, p2, p3;
    p1.point_x = 6; p1.point_y = 78;
    p2.point_x = 7; p2.point_y = 43;
    p3 = add_two_points(p1, p2);
    printf("p3=(%d,%d)\n", p3.point_x, p3.point_y);
}

标量乘运算时，一旦相加得两个点相同就是倍点运算，不同就是点加运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#define MAX 100
typedef struct point {
    int point_x;
    int point_y;
}Point;
typedef struct ecc {
    struct point p[MAX];
    int len;
}ECCPoint;
int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
//求b关于n的逆元 
int inverse(int n, int b) {
    int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
    while (r2 > 0) {
        q = r1 / r2;
        r = r1 % r2;
        r1 = r2;
        r2 = r;
        t = t1 - q * t2;
        t1 = t2;
        t2 = t;
    }
    if (t1 >= 0)
        return t1 % n;
    else {
        while ((t1 + i * n) < 0)
            i++;
        return t1 + i * n;
    }
}
Point add_two_points(Point p1, Point p2) {
    long t;
    int x1 = p1.point_x;
    int y1 = p1.point_y;
    int x2 = p2.point_x;
    int y2 = p2.point_y;
    int tx, ty;
    int x3, y3;
    int flag = 0;
    //求 
    if ((x2 == x1) && (y2 == y1)) {
        //相同点相加 
        if (y1 == 0)
            flag = 1;
        else
            t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
        //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
    }
    else {
        //不同点相加
        ty = y2 - y1;
        tx = x2 - x1;
        while (ty < 0)
            ty += p;
        while (tx < 0)
            tx += p;
        if (tx == 0 && ty != 0)
            flag = 1;
        else
            t = ty * inverse(p, tx) % p;
    }
    if (flag == 1) {
        p2.point_x = -1;
        p2.point_y = -1;
    }
    else {
        x3 = (t * t - x1 - x2) % p;
        y3 = (t * (x1 - x3) - y1) % p;
        //使结果在有限域GF(P)上 
        while (x3 < 0)
            x3 += p;
        while (y3 < 0)
            y3 += p;
        p2.point_x = x3;
        p2.point_y = y3;
    }
    return p2;
}
Point timesPiont(int k, Point p0) {
    if (k == 1)
        return p0;
    else if (k == 2)
        return add_two_points(p0, p0);
    else
        return add_two_points(p0, timesPiont(k - 1, p0));
}
int main() {
    Point pt;
    pt.point_x = 6; pt.point_y = 78;
    Point p = timesPiont(5, pt);
    printf("p=(%d,%d)\n", p.point_x, p.point_y);
}

若椭圆曲线上一点$P$存在最小正整数$n$使得数乘$nP=O\infin$，则称$n$为$P$的阶。这时对点$P$不停点乘运算，当某次点上横坐标等于$P$的横坐标时，次数$n+1$则为阶。例如计算$y^2=x^3-x$的所有阶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <iostream>
#define MAX 100
typedef struct point {
    int point_x;
    int point_y;
}Point;
typedef struct ecc {
    struct point p[MAX];
    int len;
}ECCPoint;
typedef struct generator {
    Point p;
    int p_class;
}GENE_SET;
ECCPoint eccPoint;
GENE_SET geneSet[MAX];
int geneLen;
int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
//打印点集 
void print() {
    int i;
    int len = eccPoint.len;
    printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
    for (i = 0; i < len; i++) {
        if (i % 8 == 0)
            printf("\n");
        printf("(%2d,%2d)\t", eccPoint.p[i].point_x, eccPoint.p[i].point_y);
    }
    printf("\n");
}
//取模函数
int mod_p(int s) {
    int i;	//保存s/p的倍数
    int result;	//模运算的结果
    i = s / p;
    result = s - i * p;
    if (result >= 0)
        return result;
    else
        return result + p;
}
//判断平方根是否为整数 
int int_sqrt(int s) {
    int temp;
    temp = (int)sqrt(s);//转为整型 
    if (temp * temp == s)
        return temp;
    else
        return -1;
}
//求b关于n的逆元 
int inverse(int n, int b) {
    int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
    while (r2 > 0) {
        q = r1 / r2;
        r = r1 % r2;
        r1 = r2;
        r2 = r;
        t = t1 - q * t2;
        t1 = t2;
        t2 = t;
    }
    if (t1 >= 0)
        return t1 % n;
    else {
        while ((t1 + i * n) < 0)
            i++;
        return t1 + i * n;
    }
}
//task1:求出椭圆曲线上所有点 
void get_all_points() {
    int i = 0;
    int j = 0;
    int s, y = 0;
    int n = 0, q = 0;
    int modsqrt = 0;
    int flag = 0;
    if (4 * a * a * a + 27 * b * b != 0) {
        for (i = 0; i <= p - 1; i++) {
            flag = 0;
            n = 1;
            y = 0;
            s = i * i * i + a * i + b;
            while (s < 0)
                s += p;
            s = mod_p(s);
            modsqrt = int_sqrt(s);
            if (modsqrt != -1) {
                flag = 1;
                y = modsqrt;
            }
            else
                while (n <= p - 1) {
                    q = s + n * p;
                    modsqrt = int_sqrt(q);
                    if (modsqrt != -1) {
                        y = modsqrt;
                        flag = 1;
                        break;
                    }
                    flag = 0;
                    n++;
                }
            if (flag == 1) {
                eccPoint.p[j].point_x = i;
                eccPoint.p[j].point_y = y;
                j++;
                if (y != 0) {
                    eccPoint.p[j].point_x = i;
                    eccPoint.p[j].point_y = (p - y) % p;
                    j++;
                }
            }
        }
        eccPoint.len = j;//点集个数 
        print(); //打印点集 
    }
}
//两点的加法运算 
Point add_two_points(Point p1, Point p2) {
    long t;
    int x1 = p1.point_x;
    int y1 = p1.point_y;
    int x2 = p2.point_x;
    int y2 = p2.point_y;
    int tx, ty;
    int x3, y3;
    int flag = 0;
    //求 
    if ((x2 == x1) && (y2 == y1)) {
        //相同点相加 
        if (y1 == 0)
            flag = 1;
        else
            t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
        //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
    }
    else {
        //不同点相加
        ty = y2 - y1;
        tx = x2 - x1;
        while (ty < 0)
            ty += p;
        while (tx < 0)
            tx += p;
        if (tx == 0 && ty != 0)
            flag = 1;
        else
            t = ty * inverse(p, tx) % p;
    }
    if (flag == 1) {
        p2.point_x = -1;
        p2.point_y = -1;
    }
    else {
        x3 = (t * t - x1 - x2) % p;
        y3 = (t * (x1 - x3) - y1) % p;
        //使结果在有限域GF(P)上 
        while (x3 < 0)
            x3 += p;
        while (y3 < 0)
            y3 += p;
        p2.point_x = x3;
        p2.point_y = y3;
    }
    return p2;
}
//求点的阶
void get_generetor_class() {
    int i, j = 0;
    int count = 1;
    Point p1, p2;
    get_all_points();
    printf("\n*************输出所有点的阶：*******************\n");
    for (i = 0; i < eccPoint.len; i++) {
        count = 1;
        p1.point_x = p2.point_x = eccPoint.p[i].point_x;
        p1.point_y = p2.point_y = eccPoint.p[i].point_y;
        while (1) {
            p2 = add_two_points(p1, p2);
            if (p2.point_x == -1 && p2.point_y == -1)
                break;
            count++;
            if (p2.point_x == p1.point_x)
                break;
        }
        count++;
        if (count <= eccPoint.len + 1) {
            geneSet[j].p.point_x = p1.point_x;
            geneSet[j].p.point_y = p1.point_y;
            geneSet[j].p_class = count;
            printf("点(%d,%d)的阶：%d\t", geneSet[j].p.point_x, geneSet[j].p.point_y, geneSet[j].p_class);
            j++;
            if (j % 3 == 0)
                printf("\n");
        }
        geneLen = j;
    }
}
int main() {
    get_generetor_class();
    return 0;
}

ECC

考虑$K=kG$，$K,G$为$E_p(a,b)$上的点，$nG=O\infin,n\in\mathbb P$，$k<n,k\in\mathbb Z$。其中$G$称为基点或生成元，$k$为私钥，$K$为公钥。加解密通信过程如下：

  • A选定一条$E_p(a,b)$，并取一基点$G$。
  • A选一个私钥$k$，生成公钥$K=kG$。
  • A将$E_p(a,b)$和点$K,G$传给B。
  • B将待传输的明文编码到$E_p(a,b)$上一点$M$，产生一个随机整数$r$，计算点$C_1=M+r,C_2=rG$，将$C_1,C_2$传给A。
  • A计算$C_1-kC_2$，结果为点$M$。

中间人通过$K,G$求$k$或通过$C_2,G$求$r$都困难。

描述一条$F_p$上椭圆曲线用$T=(p,a,b,G,n,h)$。$G$为基点，$n$为基点的阶，$m$为曲线所有点个数，$h=\left\lfloor\dfrac{m}{n}\right\rfloor$，一般要求条件如下：

  • $p$越大越好，一般200位左右。
  • $p\neq nh$。
  • $p^t\not\equiv1\pmod n,1\leqslant t<20$。
  • $4a^3+27b^2\not\equiv0\pmod p$。
  • $h\leqslant4$。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include <iostream>
#include<math.h>
#include<time.h>
#define MAX 100
typedef struct point {
    int point_x;
    int point_y;
}Point;
typedef struct ecc {
    struct point p[MAX];
    int len;
}ECCPoint;
typedef struct generator {
    Point p;
    int p_class;
}GENE_SET;
char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
ECCPoint eccPoint;
GENE_SET geneSet[MAX];
int geneLen;
char plain[] = "yes";
int m[MAX];
int cipher[MAX];
int nB;//私钥 
Point P1, P2, Pt, G, PB;
Point Pm;
int C[MAX];
//打印点集 
void print(){
    int i;
    int len = eccPoint.len;
    printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
    for (i = 0; i < len; i++){
        if (i % 8 == 0)
            printf("\n");
        printf("(%2d,%2d)\t", eccPoint.p[i].point_x, eccPoint.p[i].point_y);
    }
    printf("\n");
}
//取模函数
int mod_p(int s){
    int i;	//保存s/p的倍数
    int result;	//模运算的结果
    i = s / p;
    result = s - i * p;
    if (result >= 0)
        return result;
    else
        return result + p;
}
//判断平方根是否为整数 
int int_sqrt(int s){
    int temp;
    temp = (int)sqrt(s);//转为整型 
    if (temp * temp == s)
        return temp;
    else
        return -1;
}
//求b关于n的逆元 
int inverse(int n, int b){
    int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
    while (r2 > 0){
        q = r1 / r2;
        r = r1 % r2;
        r1 = r2;
        r2 = r;
        t = t1 - q * t2;
        t1 = t2;
        t2 = t;
    }
    if (t1 >= 0)
        return t1 % n;
    else {
        while ((t1 + i * n) < 0)
            i++;
        return t1 + i * n;
    }
}
//task1:求出椭圆曲线上所有点 
void get_all_points(){
    int i = 0;
    int j = 0;
    int s, y = 0;
    int n = 0, q = 0;
    int modsqrt = 0;
    int flag = 0;
    if (4 * a * a * a + 27 * b * b != 0){
        for (i = 0; i <= p - 1; i++){
            flag = 0;
            n = 1;
            y = 0;
            s = i * i * i + a * i + b;
            while (s < 0)
                s += p;
            s = mod_p(s);
            modsqrt = int_sqrt(s);
            if (modsqrt != -1){
                flag = 1;
                y = modsqrt;
            }
            else
                while (n <= p - 1){
                    q = s + n * p;
                    modsqrt = int_sqrt(q);
                    if (modsqrt != -1){
                        y = modsqrt;
                        flag = 1;
                        break;
                    }
                    flag = 0;
                    n++;
                }
            if (flag == 1){
                eccPoint.p[j].point_x = i;
                eccPoint.p[j].point_y = y;
                j++;
                if (y != 0){
                    eccPoint.p[j].point_x = i;
                    eccPoint.p[j].point_y = (p - y) % p;
                    j++;
                }
            }
        }
        eccPoint.len = j;//点集个数 
        print(); //打印点集 
    }
}
//两点的加法运算 
Point add_two_points(Point p1, Point p2){
    long t;
    int x1 = p1.point_x;
    int y1 = p1.point_y;
    int x2 = p2.point_x;
    int y2 = p2.point_y;
    int tx, ty;
    int x3, y3;
    int flag = 0;
    //求 
    if ((x2 == x1) && (y2 == y1)){
        //相同点相加 
        if (y1 == 0)
            flag = 1;
        else
            t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
        //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
    }
    else {
        //不同点相加
        ty = y2 - y1;
        tx = x2 - x1;
        while (ty < 0)
            ty += p;
        while (tx < 0)
            tx += p;
        if (tx == 0 && ty != 0)
            flag = 1;
        else
            t = ty * inverse(p, tx) % p;
    }
    if (flag == 1){
        p2.point_x = -1;
        p2.point_y = -1;
    }
    else {
        x3 = (t * t - x1 - x2) % p;
        y3 = (t * (x1 - x3) - y1) % p;
        //使结果在有限域GF(P)上 
        while (x3 < 0)
            x3 += p;
        while (y3 < 0)
            y3 += p;
        p2.point_x = x3;
        p2.point_y = y3;
    }
    return p2;
}
//求点的阶
void get_generetor_class(){
    int i, j = 0;
    int count = 1;
    Point p1, p2;
    get_all_points();
    printf("\n*************输出所有点的阶：*******************\n");
    for (i = 0; i < eccPoint.len; i++){
        count = 1;
        p1.point_x = p2.point_x = eccPoint.p[i].point_x;
        p1.point_y = p2.point_y = eccPoint.p[i].point_y;
        while (1){
            p2 = add_two_points(p1, p2);
            if (p2.point_x == -1 && p2.point_y == -1)
                break;
            count++;
            if (p2.point_x == p1.point_x)
                break;
        }
        count++;
        if (count <= eccPoint.len + 1){
            geneSet[j].p.point_x = p1.point_x;
            geneSet[j].p.point_y = p1.point_y;
            geneSet[j].p_class = count;
            printf("点(%d,%d)的阶：%d\t", geneSet[j].p.point_x, geneSet[j].p.point_y, geneSet[j].p_class);
            j++;
            if (j % 3 == 0)
                printf("\n");
        }
        geneLen = j;
    }
}
Point timesPiont(int k, Point p0){
    if (k == 1)
        return p0;
    else if (k == 2)
        return add_two_points(p0, p0);
    else
        return add_two_points(p0, timesPiont(k - 1, p0));
}
//判断是否为素数 
int isPrime(int n){
    int i, k;
    k = sqrt(n);
    for (i = 2; i <= k; i++)
        if (n % i == 0)
            break;
    if (i <= k)
        return -1;
    else
        return 0;
}
//加密 
void encrypt_ecc(){
    int num, i, j;
    int gene_class;
    int num_t;
    int k;
    printf("\n\n明文数据：%s\n", plain);
    srand(time(NULL));
    //明文转换过程
    for (i = 0; i < strlen(plain); i++)
        for (j = 0; j < 26; j++) //for(j=0;j<26;j++) 
            if (plain[i] == alphabet[j])
                m[i] = j;//将字符串明文换成数字，并存到整型数组m里面
    //选择生成元
    num = rand() % geneLen;
    gene_class = geneSet[num].p_class;
    while (isPrime(gene_class) == -1) {//不是素数 
        num = rand() % (geneLen - 3) + 3;
        gene_class = geneSet[num].p_class;
    }
    //printf("gene_class=%d\n", gene_class);
    //printf("gene_class=%d\n",gene_class);
    G = geneSet[num].p;
    //printf("G:(%d,%d)\n",geneSet[num].p.point_x,geneSet[num].p.point_y);
    nB = rand() % (gene_class - 1) + 1;//选择私钥 
    PB = timesPiont(nB, G);//PB是公钥 
    printf("\n公钥：\n");
    printf("{y^2=x^3%d*x+%d,%d,(%d,%d),(%d,%d)}\n", a, b, gene_class, G.point_x, G.point_y, PB.point_x, PB.point_y);
    printf("私钥：\n");
    printf("nB=%d\n", nB);
    //加密 
    k = rand() % (gene_class - 2) + 1;
    P1 = timesPiont(k, G);
    num_t = rand() % eccPoint.len; //选择映射点
    Pt = eccPoint.p[num_t];
    //printf("Pt:(%d,%d)\n",Pt.point_x,Pt.point_y);
    P2 = timesPiont(k, PB);
    Pm = add_two_points(Pt, P2);
    printf("加密数据：\n");
    printf("kG=(%d,%d),Pt+kPB=(%d,%d),C={", P1.point_x, P1.point_y, Pm.point_x, Pm.point_y);
    for (i = 0; i < strlen(plain); i++){
        C[i] = m[i] * Pt.point_x + Pt.point_y;
        printf("{%d}", C[i]);
    }
    printf("}\n");
}
//解密 
void decrypt_ecc(){
    Point temp, temp1;
    int m, i;
    temp = timesPiont(nB, P1);
    temp.point_y = 0 - temp.point_y;
    temp1 = add_two_points(Pm, temp);//求解Pt 
    //	printf("(%d,%d)\n",temp.point_x,temp.point_y);
    //	printf("(%d,%d)\n",temp1.point_x,temp1.point_y);
    printf("\n解密结果:");
    for (i = 0; i < strlen(plain); i++){
        m = (C[i] - temp1.point_y) / temp1.point_x;
        printf("%c", alphabet[m]);//输出密文 
    }
    printf("\n");
}
int main(){
    get_generetor_class();
    encrypt_ecc();
    decrypt_ecc();
    return 0;
}