ec.c

   1 // Copyright 2007,2008  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 // y**2 + x*y = x**3 + x + b
  11 static u8 ec_b[30] =
  12         "\x00\x66\x64\x7e\xde\x6c\x33\x2c\x7f\x8c\x09\x23\xbb\x58\x21"
  13         "\x3b\x33\x3b\x20\xe9\xce\x42\x81\xfe\x11\x5f\x7d\x8f\x90\xad";
  14
  15 // order of the addition group of points
  16 static u8 ec_N[30] =
  17         "\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
  18         "\x13\xe9\x74\xe7\x2f\x8a\x69\x22\x03\x1d\x26\x03\xcf\xe0\xd7";
  19
  20 // base point
  21 static u8 ec_G[60] =
  22         "\x00\xfa\xc9\xdf\xcb\xac\x83\x13\xbb\x21\x39\xf1\xbb\x75\x5f"
  23         "\xef\x65\xbc\x39\x1f\x8b\x36\xf8\xf8\xeb\x73\x71\xfd\x55\x8b"
  24         "\x01\x00\x6a\x08\xa4\x19\x03\x35\x06\x78\xe5\x85\x28\xbe\xbf"
  25         "\x8a\x0b\xef\xf8\x67\xa7\xca\x36\x71\x6f\x7e\x01\xf8\x10\x52";
  26
  27 static void elt_print(char *name, u8 *a)
  28 {
  29         u32 i;
  30
  31         printf("%s = ", name);
  32
  33         for (i = 0; i < 30; i++)
  34                 printf("%02x", a[i]);
  35
  36         printf("\n");
  37 }
  38
  39 static void elt_copy(u8 *d, u8 *a)
  40 {
  41         memcpy(d, a, 30);
  42 }
  43
  44 static void elt_zero(u8 *d)
  45 {
  46         memset(d, 0, 30);
  47 }
  48
  49 static int elt_is_zero(u8 *d)
  50 {
  51         u32 i;
  52
  53         for (i = 0; i < 30; i++)
  54                 if (d[i] != 0)
  55                         return 0;
  56
  57         return 1;
  58 }
  59
  60 static void elt_add(u8 *d, u8 *a, u8 *b)
  61 {
  62         u32 i;
  63
  64         for (i = 0; i < 30; i++)
  65                 d[i] = a[i] ^ b[i];
  66 }
  67
  68 static void elt_mul_x(u8 *d, u8 *a)
  69 {
  70         u8 carry, x, y;
  71         u32 i;
  72
  73         carry = a[0] & 1;
  74
  75         x = 0;
  76         for (i = 0; i < 29; i++) {
  77                 y = a[i + 1];
  78                 d[i] = x ^ (y >> 7);
  79                 x = y << 1;
  80         }
  81         d[29] = x ^ carry;
  82
  83         d[20] ^= carry << 2;
  84 }
  85
  86 static void elt_mul(u8 *d, u8 *a, u8 *b)
  87 {
  88         u32 i, n;
  89         u8 mask;
  90
  91         elt_zero(d);
  92
  93         i = 0;
  94         mask = 1;
  95         for (n = 0; n < 233; n++) {
  96                 elt_mul_x(d, d);
  97
  98                 if ((a[i] & mask) != 0)
  99                         elt_add(d, d, b);
 100
 101                 mask >>= 1;
 102                 if (mask == 0) {
 103                         mask = 0x80;
 104                         i++;
 105                 }
 106         }
 107 }
 108
 109 static const u8 square[16] =
 110         "\x00\x01\x04\x05\x10\x11\x14\x15\x40\x41\x44\x45\x50\x51\x54\x55";
 111
 112 static void elt_square_to_wide(u8 *d, u8 *a)
 113 {
 114         u32 i;
 115
 116         for (i = 0; i < 30; i++) {
 117                 d[2*i] = square[a[i] >> 4];
 118                 d[2*i + 1] = square[a[i] & 15];
 119         }
 120 }
 121
 122 static void wide_reduce(u8 *d)
 123 {
 124         u32 i;
 125         u8 x;
 126
 127         for (i = 0; i < 30; i++) {
 128                 x = d[i];
 129
 130                 d[i + 19] ^= x >> 7;
 131                 d[i + 20] ^= x << 1;
 132
 133                 d[i + 29] ^= x >> 1;
 134                 d[i + 30] ^= x << 7;
 135         }
 136
 137         x = d[30] & ~1;
 138
 139         d[49] ^= x >> 7;
 140         d[50] ^= x << 1;
 141
 142         d[59] ^= x >> 1;
 143
 144         d[30] &= 1;
 145 }
 146
 147 static void elt_square(u8 *d, u8 *a)
 148 {
 149         u8 wide[60];
 150
 151         elt_square_to_wide(wide, a);
 152         wide_reduce(wide);
 153
 154         elt_copy(d, wide + 30);
 155 }
 156
 157 static void itoh_tsujii(u8 *d, u8 *a, u8 *b, u32 j)
 158 {
 159         u8 t[30];
 160
 161         elt_copy(t, a);
 162         while (j--) {
 163                 elt_square(d, t);
 164                 elt_copy(t, d);
 165         }
 166
 167         elt_mul(d, t, b);
 168 }
 169
 170 static void elt_inv(u8 *d, u8 *a)
 171 {
 172         u8 t[30];
 173         u8 s[30];
 174
 175         itoh_tsujii(t, a, a, 1);
 176         itoh_tsujii(s, t, a, 1);
 177         itoh_tsujii(t, s, s, 3);
 178         itoh_tsujii(s, t, a, 1);
 179         itoh_tsujii(t, s, s, 7);
 180         itoh_tsujii(s, t, t, 14);
 181         itoh_tsujii(t, s, a, 1);
 182         itoh_tsujii(s, t, t, 29);
 183         itoh_tsujii(t, s, s, 58);
 184         itoh_tsujii(s, t, t, 116);
 185         elt_square(d, s);
 186 }
 187
 188 static int point_is_on_curve(u8 *p)
 189 {
 190         u8 s[30], t[30];
 191         u8 *x, *y;
 192
 193         x = p;
 194         y = p + 30;
 195
 196         elt_square(t, x);
 197         elt_mul(s, t, x);
 198
 199         elt_add(s, s, t);
 200
 201         elt_square(t, y);
 202         elt_add(s, s, t);
 203
 204         elt_mul(t, x, y);
 205         elt_add(s, s, t);
 206
 207         elt_add(s, s, ec_b);
 208
 209         return elt_is_zero(s);
 210 }
 211
 212 static int point_is_zero(u8 *p)
 213 {
 214         return elt_is_zero(p) && elt_is_zero(p + 30);
 215 }
 216
 217 static void point_double(u8 *r, u8 *p)
 218 {
 219         u8 s[30], t[30];
 220         u8 *px, *py, *rx, *ry;
 221
 222         px = p;
 223         py = p + 30;
 224         rx = r;
 225         ry = r + 30;
 226
 227         if (elt_is_zero(px)) {
 228                 elt_zero(rx);
 229                 elt_zero(ry);
 230
 231                 return;
 232         }
 233
 234         elt_inv(t, px);
 235         elt_mul(s, py, t);
 236         elt_add(s, s, px);
 237
 238         elt_square(t, px);
 239
 240         elt_square(rx, s);
 241         elt_add(rx, rx, s);
 242         rx[29] ^= 1;
 243
 244         elt_mul(ry, s, rx);
 245         elt_add(ry, ry, rx);
 246         elt_add(ry, ry, t);
 247 }
 248
 249 static void point_add(u8 *r, u8 *p, u8 *q)
 250 {
 251         u8 s[30], t[30], u[30];
 252         u8 *px, *py, *qx, *qy, *rx, *ry;
 253
 254         px = p;
 255         py = p + 30;
 256         qx = q;
 257         qy = q + 30;
 258         rx = r;
 259         ry = r + 30;
 260
 261         if (point_is_zero(p)) {
 262                 elt_copy(rx, qx);
 263                 elt_copy(ry, qy);
 264                 return;
 265         }
 266
 267         if (point_is_zero(q)) {
 268                 elt_copy(rx, px);
 269                 elt_copy(ry, py);
 270                 return;
 271         }
 272
 273         elt_add(u, px, qx);
 274
 275         if (elt_is_zero(u)) {
 276                 elt_add(u, py, qy);
 277                 if (elt_is_zero(u))
 278                         point_double(r, p);
 279                 else {
 280                         elt_zero(rx);
 281                         elt_zero(ry);
 282                 }
 283
 284                 return;
 285         }
 286
 287         elt_inv(t, u);
 288         elt_add(u, py, qy);
 289         elt_mul(s, t, u);
 290
 291         elt_square(t, s);
 292         elt_add(t, t, s);
 293         elt_add(t, t, qx);
 294         t[29] ^= 1;
 295
 296         elt_mul(u, s, t);
 297         elt_add(s, u, py);
 298         elt_add(rx, t, px);
 299         elt_add(ry, s, rx);
 300 }
 301
 302 static void point_mul(u8 *d, u8 *a, u8 *b)      // a is bignum
 303 {
 304         u32 i;
 305         u8 mask;
 306
 307         elt_zero(d);
 308         elt_zero(d + 30);
 309
 310         for (i = 0; i < 30; i++)
 311                 for (mask = 0x80; mask != 0; mask >>= 1) {
 312                         point_double(d, d);
 313                         if ((a[i] & mask) != 0)
 314                                 point_add(d, d, b);
 315                 }
 316 }
 317
 318 void generate_ecdsa(u8 *R, u8 *S, u8 *k, u8 *hash)
 319 {
 320         u8 e[30];
 321         u8 kk[30];
 322         u8 m[30];
 323         u8 minv[30];
 324         u8 mG[60];
 325         FILE *fp;
 326
 327         elt_zero(e);
 328         memcpy(e + 10, hash, 20);
 329
 330         fp = fopen("/dev/random", "rb");
 331         if (fread(m, sizeof m, 1, fp) != 1)
 332                 fatal("reading random");
 333         fclose(fp);
 334         m[0] = 0;
 335
 336         //      R = (mG).x
 337
 338         point_mul(mG, m, ec_G);
 339         elt_copy(R, mG);
 340         if (bn_compare(R, ec_N, 30) >= 0)
 341                 bn_sub_modulus(R, ec_N, 30);
 342
 343         //      S = m**-1*(e + Rk) (mod N)
 344
 345         elt_copy(kk, k);
 346         if (bn_compare(kk, ec_N, 30) >= 0)
 347                 bn_sub_modulus(kk, ec_N, 30);
 348         bn_mul(S, R, kk, ec_N, 30);
 349         bn_add(kk, S, e, ec_N, 30);
 350         bn_inv(minv, m, ec_N, 30);
 351         bn_mul(S, minv, kk, ec_N, 30);
 352 }
 353
 354 int check_ecdsa(u8 *Q, u8 *R, u8 *S, u8 *hash)
 355 {
 356         u8 Sinv[30];
 357         u8 e[30];
 358         u8 w1[30], w2[30];
 359         u8 r1[60], r2[60];
 360
 361         bn_inv(Sinv, S, ec_N, 30);
 362
 363         elt_zero(e);
 364         memcpy(e + 10, hash, 20);
 365
 366         bn_mul(w1, e, Sinv, ec_N, 30);
 367         bn_mul(w2, R, Sinv, ec_N, 30);
 368
 369         point_mul(r1, w1, ec_G);
 370         point_mul(r2, w2, Q);
 371
 372         point_add(r1, r1, r2);
 373
 374         if (bn_compare(r1, ec_N, 30) >= 0)
 375                 bn_sub_modulus(r1, ec_N, 30);
 376
 377         return (bn_compare(r1, R, 30) == 0);
 378 }
 379
 380 void ec_priv_to_pub(u8 *k, u8 *Q)
 381 {
 382         point_mul(Q, k, ec_G);
 383 }