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 #include <string.h>
   6 #include <stdio.h>
   7
   8 #include "tools.h"
   9
  10 struct point {
  11         u8 x[20];
  12         u8 y[20];
  13 };
  14
  15 static u8 ec_p[20];
  16 static u8 ec_a[20];     // mon
  17 static u8 ec_b[20];     // mon
  18 static u8 ec_N[21];
  19 static struct point ec_G;       // mon
  20 static struct point ec_Q;       // mon
  21 static u8 ec_k[21];
  22
  23 static void elt_copy(u8 *d, u8 *a)
  24 {
  25         memcpy(d, a, 20);
  26 }
  27
  28 static void elt_zero(u8 *d)
  29 {
  30         memset(d, 0, 20);
  31 }
  32
  33 static int elt_is_zero(u8 *d)
  34 {
  35         u32 i;
  36
  37         for (i = 0; i < 20; i++)
  38                 if (d[i] != 0)
  39                         return 0;
  40
  41         return 1;
  42 }
  43
  44 static void elt_add(u8 *d, u8 *a, u8 *b)
  45 {
  46         bn_add(d, a, b, ec_p, 20);
  47 }
  48
  49 static void elt_sub(u8 *d, u8 *a, u8 *b)
  50 {
  51         bn_sub(d, a, b, ec_p, 20);
  52 }
  53
  54 static void elt_mul(u8 *d, u8 *a, u8 *b)
  55 {
  56         bn_mon_mul(d, a, b, ec_p, 20);
  57 }
  58
  59 static void elt_square(u8 *d, u8 *a)
  60 {
  61         elt_mul(d, a, a);
  62 }
  63
  64 static void elt_inv(u8 *d, u8 *a)
  65 {
  66         u8 s[20];
  67         elt_copy(s, a);
  68         bn_mon_inv(d, s, ec_p, 20);
  69 }
  70
  71 static void point_to_mon(struct point *p)
  72 {
  73         bn_to_mon(p->x, ec_p, 20);
  74         bn_to_mon(p->y, ec_p, 20);
  75 }
  76
  77 static void point_from_mon(struct point *p)
  78 {
  79         bn_from_mon(p->x, ec_p, 20);
  80         bn_from_mon(p->y, ec_p, 20);
  81 }
  82
  83 #if 0
  84 static int point_is_on_curve(u8 *p)
  85 {
  86         u8 s[20], t[20];
  87         u8 *x, *y;
  88
  89         x = p;
  90         y = p + 20;
  91
  92         elt_square(t, x);
  93         elt_mul(s, t, x);
  94
  95         elt_mul(t, x, ec_a);
  96         elt_add(s, s, t);
  97
  98         elt_add(s, s, ec_b);
  99
 100         elt_square(t, y);
 101         elt_sub(s, s, t);
 102
 103         return elt_is_zero(s);
 104 }
 105 #endif
 106
 107 static void point_zero(struct point *p)
 108 {
 109         elt_zero(p->x);
 110         elt_zero(p->y);
 111 }
 112
 113 static int point_is_zero(struct point *p)
 114 {
 115         return elt_is_zero(p->x) && elt_is_zero(p->y);
 116 }
 117
 118 static void point_double(struct point *r, struct point *p)
 119 {
 120         u8 s[20], t[20];
 121         struct point pp;
 122         u8 *px, *py, *rx, *ry;
 123
 124         pp = *p;
 125
 126         px = pp.x;
 127         py = pp.y;
 128         rx = r->x;
 129         ry = r->y;
 130
 131         if (elt_is_zero(py)) {
 132                 point_zero(r);
 133                 return;
 134         }
 135
 136         elt_square(t, px);      // t = px*px
 137         elt_add(s, t, t);       // s = 2*px*px
 138         elt_add(s, s, t);       // s = 3*px*px
 139         elt_add(s, s, ec_a);    // s = 3*px*px + a
 140         elt_add(t, py, py);     // t = 2*py
 141         elt_inv(t, t);          // t = 1/(2*py)
 142         elt_mul(s, s, t);       // s = (3*px*px+a)/(2*py)
 143
 144         elt_square(rx, s);      // rx = s*s
 145         elt_add(t, px, px);     // t = 2*px
 146         elt_sub(rx, rx, t);     // rx = s*s - 2*px
 147
 148         elt_sub(t, px, rx);     // t = -(rx-px)
 149         elt_mul(ry, s, t);      // ry = -s*(rx-px)
 150         elt_sub(ry, ry, py);    // ry = -s*(rx-px) - py
 151 }
 152
 153 static void point_add(struct point *r, struct point *p, struct point *q)
 154 {
 155         u8 s[20], t[20], u[20];
 156         u8 *px, *py, *qx, *qy, *rx, *ry;
 157         struct point pp, qq;
 158
 159         pp = *p;
 160         qq = *q;
 161
 162         px = pp.x;
 163         py = pp.y;
 164         qx = qq.x;
 165         qy = qq.y;
 166         rx = r->x;
 167         ry = r->y;
 168
 169         if (point_is_zero(&pp)) {
 170                 elt_copy(rx, qx);
 171                 elt_copy(ry, qy);
 172                 return;
 173         }
 174
 175         if (point_is_zero(&qq)) {
 176                 elt_copy(rx, px);
 177                 elt_copy(ry, py);
 178                 return;
 179         }
 180
 181         elt_sub(u, qx, px);
 182
 183         if (elt_is_zero(u)) {
 184                 elt_sub(u, qy, py);
 185                 if (elt_is_zero(u))
 186                         point_double(r, &pp);
 187                 else
 188                         point_zero(r);
 189
 190                 return;
 191         }
 192
 193         elt_inv(t, u);          // t = 1/(qx-px)
 194         elt_sub(u, qy, py);     // u = qy-py
 195         elt_mul(s, t, u);       // s = (qy-py)/(qx-px)
 196
 197         elt_square(rx, s);      // rx = s*s
 198         elt_add(t, px, qx);     // t = px+qx
 199         elt_sub(rx, rx, t);     // rx = s*s - (px+qx)
 200
 201         elt_sub(t, px, rx);     // t = -(rx-px)
 202         elt_mul(ry, s, t);      // ry = -s*(rx-px)
 203         elt_sub(ry, ry, py);    // ry = -s*(rx-px) - py
 204 }
 205
 206 static void point_mul(struct point *d, u8 *a, struct point *b)  // a is bignum
 207 {
 208         u32 i;
 209         u8 mask;
 210
 211         point_zero(d);
 212
 213         for (i = 0; i < 21; i++)
 214                 for (mask = 0x80; mask != 0; mask >>= 1) {
 215                         point_double(d, d);
 216                         if ((a[i] & mask) != 0)
 217                                 point_add(d, d, b);
 218                 }
 219 }
 220
 221 static void generate_ecdsa(u8 *R, u8 *S, u8 *k, u8 *hash)
 222 {
 223         u8 e[21];
 224         u8 kk[21];
 225         u8 m[21];
 226         u8 minv[21];
 227         struct point mG;
 228
 229         e[0] = 0;
 230         memcpy(e + 1, hash, 20);
 231         bn_reduce(e, ec_N, 21);
 232
 233 try_again:
 234
 235         get_rand(m, sizeof m);
 236         m[0] = 0;
 237         if (bn_compare(m, ec_N, 21) >= 0)
 238                 goto try_again;
 239
 240         //      R = (mG).x
 241
 242         point_mul(&mG, m, &ec_G);
 243         point_from_mon(&mG);
 244         R[0] = 0;
 245         elt_copy(R+1, mG.x);
 246
 247         //      S = m**-1*(e + Rk) (mod N)
 248
 249         bn_copy(kk, k, 21);
 250         bn_reduce(kk, ec_N, 21);
 251         bn_to_mon(m, ec_N, 21);
 252         bn_to_mon(e, ec_N, 21);
 253         bn_to_mon(R, ec_N, 21);
 254         bn_to_mon(kk, ec_N, 21);
 255
 256         bn_mon_mul(S, R, kk, ec_N, 21);
 257         bn_add(kk, S, e, ec_N, 21);
 258         bn_mon_inv(minv, m, ec_N, 21);
 259         bn_mon_mul(S, minv, kk, ec_N, 21);
 260
 261         bn_from_mon(R, ec_N, 21);
 262         bn_from_mon(S, ec_N, 21);
 263 }
 264
 265 static int check_ecdsa(struct point *Q, u8 *R, u8 *S, u8 *hash)
 266 {
 267         u8 Sinv[21];
 268         u8 e[21];
 269         u8 w1[21], w2[21];
 270         struct point r1, r2;
 271         u8 rr[21];
 272
 273         e[0] = 0;
 274         memcpy(e + 1, hash, 20);
 275         bn_reduce(e, ec_N, 21);
 276
 277         bn_to_mon(R, ec_N, 21);
 278         bn_to_mon(S, ec_N, 21);
 279         bn_to_mon(e, ec_N, 21);
 280
 281         bn_mon_inv(Sinv, S, ec_N, 21);
 282
 283         bn_mon_mul(w1, e, Sinv, ec_N, 21);
 284         bn_mon_mul(w2, R, Sinv, ec_N, 21);
 285
 286         bn_from_mon(w1, ec_N, 21);
 287         bn_from_mon(w2, ec_N, 21);
 288
 289         point_mul(&r1, w1, &ec_G);
 290         point_mul(&r2, w2, Q);
 291
 292         point_add(&r1, &r1, &r2);
 293
 294         point_from_mon(&r1);
 295
 296         rr[0] = 0;
 297         memcpy(rr + 1, r1.x, 20);
 298         bn_reduce(rr, ec_N, 21);
 299
 300         bn_from_mon(R, ec_N, 21);
 301         bn_from_mon(S, ec_N, 21);
 302
 303         return (bn_compare(rr, R, 21) == 0);
 304 }
 305
 306 #if 0
 307 static void ec_priv_to_pub(u8 *k, u8 *Q)
 308 {
 309         point_mul(Q, k, ec_G);
 310 }
 311 #endif
 312
 313 int ecdsa_set_curve(u32 type)
 314 {
 315         if (ecdsa_get_params(type, ec_p, ec_a, ec_b, ec_N, ec_G.x, ec_G.y) < 0)
 316                 return -1;
 317
 318         bn_to_mon(ec_a, ec_p, 20);
 319         bn_to_mon(ec_b, ec_p, 20);
 320
 321         point_to_mon(&ec_G);
 322
 323         return 0;
 324 }
 325
 326 void ecdsa_set_pub(u8 *Q)
 327 {
 328         memcpy(ec_Q.x, Q, 20);
 329         memcpy(ec_Q.y, Q+20, 20);
 330         point_to_mon(&ec_Q);
 331 }
 332
 333 void ecdsa_set_priv(u8 *k)
 334 {
 335         memcpy(ec_k, k, sizeof ec_k);
 336 }
 337
 338 int ecdsa_verify(u8 *hash, u8 *R, u8 *S)
 339 {
 340         return check_ecdsa(&ec_Q, R, S, hash);
 341 }
 342
 343 void ecdsa_sign(u8 *hash, u8 *R, u8 *S)
 344 {
 345         generate_ecdsa(R, S, ec_k, hash);
 346 }