1 // Copyright 2007,2008,2010 Segher Boessenkool <segher@kernel.crashing.org>
2 // Licensed under the terms of the GNU GPL, version 2
3 // http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt
4
5 #include <string.h>
6 #include <stdio.h>
7
8 #include "kirk_engine.h"
9
10 struct point {
11 u8 x[20];
12 u8 y[20];
13 };
14
15 u8 ec_p[20];
16 u8 ec_a[20];
17 u8 ec_b[20];
18 u8 ec_N[21];
19 struct point ec_G; // mon
20 struct point ec_Q; // mon
21 u8 ec_k[21];
22
hex_dump(char * str,u8 * buf,int size)23 void hex_dump(char *str, u8 *buf, int size)
24 {
25 int i;
26
27 if(str)
28 printf("%s:", str);
29
30 for(i=0; i<size; i++){
31 if((i%32)==0){
32 printf("\n%4X:", i);
33 }
34 printf(" %02X", buf[i]);
35 }
36 printf("\n\n");
37 }
38
elt_copy(u8 * d,u8 * a)39 static void elt_copy(u8 *d, u8 *a)
40 {
41 memcpy(d, a, 20);
42 }
43
elt_zero(u8 * d)44 static void elt_zero(u8 *d)
45 {
46 memset(d, 0, 20);
47 }
48
elt_is_zero(u8 * d)49 static int elt_is_zero(u8 *d)
50 {
51 u32 i;
52
53 for (i = 0; i < 20; i++)
54 if (d[i] != 0)
55 return 0;
56
57 return 1;
58 }
59
elt_add(u8 * d,u8 * a,u8 * b)60 static void elt_add(u8 *d, u8 *a, u8 *b)
61 {
62 bn_add(d, a, b, ec_p, 20);
63 }
64
elt_sub(u8 * d,u8 * a,u8 * b)65 static void elt_sub(u8 *d, u8 *a, u8 *b)
66 {
67 bn_sub(d, a, b, ec_p, 20);
68 }
69
elt_mul(u8 * d,u8 * a,u8 * b)70 static void elt_mul(u8 *d, u8 *a, u8 *b)
71 {
72 bn_mon_mul(d, a, b, ec_p, 20);
73 }
74
elt_square(u8 * d,u8 * a)75 static void elt_square(u8 *d, u8 *a)
76 {
77 elt_mul(d, a, a);
78 }
79
elt_inv(u8 * d,u8 * a)80 static void elt_inv(u8 *d, u8 *a)
81 {
82 u8 s[20];
83 elt_copy(s, a);
84 bn_mon_inv(d, s, ec_p, 20);
85 }
86
point_to_mon(struct point * p)87 static void point_to_mon(struct point *p)
88 {
89 bn_to_mon(p->x, ec_p, 20);
90 bn_to_mon(p->y, ec_p, 20);
91 }
92
point_from_mon(struct point * p)93 static void point_from_mon(struct point *p)
94 {
95 bn_from_mon(p->x, ec_p, 20);
96 bn_from_mon(p->y, ec_p, 20);
97 }
98
99 #if 0
100 static int point_is_on_curve(u8 *p)
101 {
102 u8 s[20], t[20];
103 u8 *x, *y;
104
105 x = p;
106 y = p + 20;
107
108 elt_square(t, x);
109 elt_mul(s, t, x);
110
111 elt_mul(t, x, ec_a);
112 elt_add(s, s, t);
113
114 elt_add(s, s, ec_b);
115
116 elt_square(t, y);
117 elt_sub(s, s, t);
118
119 return elt_is_zero(s);
120 }
121 #endif
122
point_zero(struct point * p)123 static void point_zero(struct point *p)
124 {
125 elt_zero(p->x);
126 elt_zero(p->y);
127 }
128
point_is_zero(struct point * p)129 static int point_is_zero(struct point *p)
130 {
131 return elt_is_zero(p->x) && elt_is_zero(p->y);
132 }
133
point_double(struct point * r,struct point * p)134 static void point_double(struct point *r, struct point *p)
135 {
136 u8 s[20], t[20];
137 struct point pp;
138 u8 *px, *py, *rx, *ry;
139
140 pp = *p;
141
142 px = pp.x;
143 py = pp.y;
144 rx = r->x;
145 ry = r->y;
146
147 if (elt_is_zero(py)) {
148 point_zero(r);
149 return;
150 }
151
152 elt_square(t, px); // t = px*px
153 elt_add(s, t, t); // s = 2*px*px
154 elt_add(s, s, t); // s = 3*px*px
155 elt_add(s, s, ec_a); // s = 3*px*px + a
156 elt_add(t, py, py); // t = 2*py
157 elt_inv(t, t); // t = 1/(2*py)
158 elt_mul(s, s, t); // s = (3*px*px+a)/(2*py)
159
160 elt_square(rx, s); // rx = s*s
161 elt_add(t, px, px); // t = 2*px
162 elt_sub(rx, rx, t); // rx = s*s - 2*px
163
164 elt_sub(t, px, rx); // t = -(rx-px)
165 elt_mul(ry, s, t); // ry = -s*(rx-px)
166 elt_sub(ry, ry, py); // ry = -s*(rx-px) - py
167 }
168
point_add(struct point * r,struct point * p,struct point * q)169 static void point_add(struct point *r, struct point *p, struct point *q)
170 {
171 u8 s[20], t[20], u[20];
172 u8 *px, *py, *qx, *qy, *rx, *ry;
173 struct point pp, qq;
174
175 pp = *p;
176 qq = *q;
177
178 px = pp.x;
179 py = pp.y;
180 qx = qq.x;
181 qy = qq.y;
182 rx = r->x;
183 ry = r->y;
184
185 if (point_is_zero(&pp)) {
186 elt_copy(rx, qx);
187 elt_copy(ry, qy);
188 return;
189 }
190
191 if (point_is_zero(&qq)) {
192 elt_copy(rx, px);
193 elt_copy(ry, py);
194 return;
195 }
196
197 elt_sub(u, qx, px);
198
199 if (elt_is_zero(u)) {
200 elt_sub(u, qy, py);
201 if (elt_is_zero(u))
202 point_double(r, &pp);
203 else
204 point_zero(r);
205
206 return;
207 }
208
209 elt_inv(t, u); // t = 1/(qx-px)
210 elt_sub(u, qy, py); // u = qy-py
211 elt_mul(s, t, u); // s = (qy-py)/(qx-px)
212
213 elt_square(rx, s); // rx = s*s
214 elt_add(t, px, qx); // t = px+qx
215 elt_sub(rx, rx, t); // rx = s*s - (px+qx)
216
217 elt_sub(t, px, rx); // t = -(rx-px)
218 elt_mul(ry, s, t); // ry = -s*(rx-px)
219 elt_sub(ry, ry, py); // ry = -s*(rx-px) - py
220 }
221
point_mul(struct point * d,u8 * a,struct point * b)222 static void point_mul(struct point *d, u8 *a, struct point *b)
223 {
224 u32 i;
225 u8 mask;
226
227 point_zero(d);
228
229 for (i = 0; i < 21; i++)
230 for (mask = 0x80; mask != 0; mask >>= 1) {
231 point_double(d, d);
232 if ((a[i] & mask) != 0)
233 point_add(d, d, b);
234 }
235 }
236
generate_ecdsa(u8 * outR,u8 * outS,u8 * k,u8 * hash)237 static void generate_ecdsa(u8 *outR, u8 *outS, u8 *k, u8 *hash)
238 {
239 u8 e[21];
240 u8 kk[21];
241 u8 m[21];
242 u8 R[21];
243 u8 S[21];
244 u8 minv[21];
245 struct point mG;
246
247 e[0] = 0;R[0] = 0;S[0] = 0;
248 memcpy(e + 1, hash, 20);
249 bn_reduce(e, ec_N, 21);
250
251 kirk_CMD14(m+1, 20);
252 m[0] = 0;
253
254 point_mul(&mG, m, &ec_G);
255 point_from_mon(&mG);
256 R[0] = 0;
257 elt_copy(R+1, mG.x);
258
259 bn_copy(kk, k, 21);
260 bn_reduce(kk, ec_N, 21);
261 bn_to_mon(m, ec_N, 21);
262 bn_to_mon(e, ec_N, 21);
263 bn_to_mon(R, ec_N, 21);
264 bn_to_mon(kk, ec_N, 21);
265
266 bn_mon_mul(S, R, kk, ec_N, 21);
267 bn_add(kk, S, e, ec_N, 21);
268 bn_mon_inv(minv, m, ec_N, 21);
269 bn_mon_mul(S, minv, kk, ec_N, 21);
270
271 bn_from_mon(R, ec_N, 21);
272 bn_from_mon(S, ec_N, 21);
273 memcpy(outR,R+1,0x20);
274 memcpy(outS,S+1,0x20);
275 }
276
check_ecdsa(struct point * Q,u8 * inR,u8 * inS,u8 * hash)277 static int check_ecdsa(struct point *Q, u8 *inR, u8 *inS, u8 *hash)
278 {
279 u8 Sinv[21];
280 u8 e[21], R[21], S[21];
281 u8 w1[21], w2[21];
282 struct point r1, r2;
283 u8 rr[21];
284
285 e[0] = 0;
286 memcpy(e + 1, hash, 20);
287 bn_reduce(e, ec_N, 21);
288 R[0] = 0;
289 memcpy(R + 1, inR, 20);
290 bn_reduce(R, ec_N, 21);
291 S[0] = 0;
292 memcpy(S + 1, inS, 20);
293 bn_reduce(S, ec_N, 21);
294
295 bn_to_mon(R, ec_N, 21);
296 bn_to_mon(S, ec_N, 21);
297 bn_to_mon(e, ec_N, 21);
298 // make Sinv = 1/S
299 bn_mon_inv(Sinv, S, ec_N, 21);
300 // w1 = m * Sinv
301 bn_mon_mul(w1, e, Sinv, ec_N, 21);
302 // w2 = r * Sinv
303 bn_mon_mul(w2, R, Sinv, ec_N, 21);
304
305 // mod N both
306 bn_from_mon(w1, ec_N, 21);
307 bn_from_mon(w2, ec_N, 21);
308
309 // r1 = m/s * G
310 point_mul(&r1, w1, &ec_G);
311 // r2 = r/s * P
312 point_mul(&r2, w2, Q);
313
314 //r1 = r1 + r2
315 point_add(&r1, &r1, &r2);
316
317 point_from_mon(&r1);
318
319 rr[0] = 0;
320 memcpy(rr + 1, r1.x, 20);
321 bn_reduce(rr, ec_N, 21);
322
323 bn_from_mon(R, ec_N, 21);
324 bn_from_mon(S, ec_N, 21);
325
326 return (bn_compare(rr, R, 21) == 0);
327 }
328
ec_priv_to_pub(u8 * k,u8 * Q)329 void ec_priv_to_pub(u8 *k, u8 *Q)
330 {
331 struct point ec_temp;
332 bn_to_mon(k, ec_N, 21);
333 point_mul(&ec_temp, k, &ec_G);
334 point_from_mon(&ec_temp);
335 memcpy(Q,ec_temp.x,20);
336 memcpy(Q+20,ec_temp.y,20);
337 }
338
ec_pub_mult(u8 * k,u8 * Q)339 void ec_pub_mult(u8 *k, u8 *Q)
340 {
341 struct point ec_temp;
342 point_mul(&ec_temp, k, &ec_Q);
343 point_from_mon(&ec_temp);
344 memcpy(Q,ec_temp.x,20);
345 memcpy(Q+20,ec_temp.y,20);
346 }
347
ecdsa_set_curve(u8 * p,u8 * a,u8 * b,u8 * N,u8 * Gx,u8 * Gy)348 int ecdsa_set_curve(u8* p,u8* a,u8* b,u8* N,u8* Gx,u8* Gy)
349 {
350 memcpy(ec_p,p,20);
351 memcpy(ec_a,a,20);
352 memcpy(ec_b,b,20);
353 memcpy(ec_N,N,21);
354
355 bn_to_mon(ec_a, ec_p, 20);
356 bn_to_mon(ec_b, ec_p, 20);
357
358 memcpy(ec_G.x, Gx, 20);
359 memcpy(ec_G.y, Gy, 20);
360 point_to_mon(&ec_G);
361
362 return 0;
363 }
364
ecdsa_set_pub(u8 * Q)365 void ecdsa_set_pub(u8 *Q)
366 {
367 memcpy(ec_Q.x, Q, 20);
368 memcpy(ec_Q.y, Q+20, 20);
369 point_to_mon(&ec_Q);
370 }
371
ecdsa_set_priv(u8 * ink)372 void ecdsa_set_priv(u8 *ink)
373 {
374 u8 k[21];
375 k[0]=0;
376 memcpy(k+1,ink,20);
377 bn_reduce(k, ec_N, 21);
378
379 memcpy(ec_k, k, sizeof ec_k);
380 }
381
ecdsa_verify(u8 * hash,u8 * R,u8 * S)382 int ecdsa_verify(u8 *hash, u8 *R, u8 *S)
383 {
384 return check_ecdsa(&ec_Q, R, S, hash);
385 }
386
ecdsa_sign(u8 * hash,u8 * R,u8 * S)387 void ecdsa_sign(u8 *hash, u8 *R, u8 *S)
388 {
389 generate_ecdsa(R, S, ec_k, hash);
390 }
391
point_is_on_curve(u8 * p)392 int point_is_on_curve(u8 *p)
393 {
394 u8 s[20], t[20];
395 u8 *x, *y;
396
397 x = p;
398 y = p + 20;
399
400 elt_square(t, x);
401 elt_mul(s, t, x);// s = x^3
402
403 elt_mul(t, x, ec_a);
404 elt_add(s, s, t); //s = x^3 + a *x
405
406 elt_add(s, s, ec_b);//s = x^3 + a *x + b
407
408 elt_square(t, y); //t = y^2
409 elt_sub(s, s, t); // is s - t = 0?
410 hex_dump("S", s, 20);
411 hex_dump("T", t,20);
412 return elt_is_zero(s);
413 }
414
dump_ecc(void)415 void dump_ecc(void)
416 {
417 hex_dump("P", ec_p, 20);
418 hex_dump("a", ec_a, 20);
419 hex_dump("b", ec_b, 20);
420 hex_dump("N", ec_N, 21);
421 hex_dump("Gx", ec_G.x, 20);
422 hex_dump("Gy", ec_G.y, 20);
423 }
424