← Back to branch summary

~ppsspp/ppsspp/ppsspp_1.3.0

« back to all changes in this revision

Viewing changes to ext/libkirk/ec.c

  • Committer: Sérgio Benjamim
  • Date: 2017-01-02 00:12:05 UTC
  • Revision ID: sergio_br2@yahoo.com.br-20170102001205-cxbta9za203nmjwm
1.3.0 source (from ppsspp_1.3.0-r160.p5.l1762.a165.t83~56~ubuntu16.04.1.tar.xz).

Show diffs side-by-side

added added

removed removed

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