tinc-vpn.org Git - tinc/blob - src/ed25519/ge.c

   1 #include "ge.h"
   2 #include "precomp_data.h"
   3
   4
   5 /*
   6 r = p + q
   7 */
   8
   9 void ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
  10         fe t0;
  11         fe_add(r->X, p->Y, p->X);
  12         fe_sub(r->Y, p->Y, p->X);
  13         fe_mul(r->Z, r->X, q->YplusX);
  14         fe_mul(r->Y, r->Y, q->YminusX);
  15         fe_mul(r->T, q->T2d, p->T);
  16         fe_mul(r->X, p->Z, q->Z);
  17         fe_add(t0, r->X, r->X);
  18         fe_sub(r->X, r->Z, r->Y);
  19         fe_add(r->Y, r->Z, r->Y);
  20         fe_add(r->Z, t0, r->T);
  21         fe_sub(r->T, t0, r->T);
  22 }
  23
  24
  25 static void slide(signed char *r, const unsigned char *a) {
  26         int i;
  27         int b;
  28         int k;
  29
  30         for(i = 0; i < 256; ++i) {
  31                 r[i] = 1 & (a[i >> 3] >> (i & 7));
  32         }
  33
  34         for(i = 0; i < 256; ++i)
  35                 if(r[i]) {
  36                         for(b = 1; b <= 6 && i + b < 256; ++b) {
  37                                 if(r[i + b]) {
  38                                         if(r[i] + (r[i + b] << b) <= 15) {
  39                                                 r[i] += r[i + b] << b;
  40                                                 r[i + b] = 0;
  41                                         } else if(r[i] - (r[i + b] << b) >= -15) {
  42                                                 r[i] -= r[i + b] << b;
  43
  44                                                 for(k = i + b; k < 256; ++k) {
  45                                                         if(!r[k]) {
  46                                                                 r[k] = 1;
  47                                                                 break;
  48                                                         }
  49
  50                                                         r[k] = 0;
  51                                                 }
  52                                         } else {
  53                                                 break;
  54                                         }
  55                                 }
  56                         }
  57                 }
  58 }
  59
  60 /*
  61 r = a * A + b * B
  62 where a = a[0]+256*a[1]+...+256^31 a[31].
  63 and b = b[0]+256*b[1]+...+256^31 b[31].
  64 B is the Ed25519 base point (x,4/5) with x positive.
  65 */
  66
  67 void ge_double_scalarmult_vartime(ge_p2 *r, const unsigned char *a, const ge_p3 *A, const unsigned char *b) {
  68         signed char aslide[256];
  69         signed char bslide[256];
  70         ge_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */
  71         ge_p1p1 t;
  72         ge_p3 u;
  73         ge_p3 A2;
  74         int i;
  75         slide(aslide, a);
  76         slide(bslide, b);
  77         ge_p3_to_cached(&Ai[0], A);
  78         ge_p3_dbl(&t, A);
  79         ge_p1p1_to_p3(&A2, &t);
  80         ge_add(&t, &A2, &Ai[0]);
  81         ge_p1p1_to_p3(&u, &t);
  82         ge_p3_to_cached(&Ai[1], &u);
  83         ge_add(&t, &A2, &Ai[1]);
  84         ge_p1p1_to_p3(&u, &t);
  85         ge_p3_to_cached(&Ai[2], &u);
  86         ge_add(&t, &A2, &Ai[2]);
  87         ge_p1p1_to_p3(&u, &t);
  88         ge_p3_to_cached(&Ai[3], &u);
  89         ge_add(&t, &A2, &Ai[3]);
  90         ge_p1p1_to_p3(&u, &t);
  91         ge_p3_to_cached(&Ai[4], &u);
  92         ge_add(&t, &A2, &Ai[4]);
  93         ge_p1p1_to_p3(&u, &t);
  94         ge_p3_to_cached(&Ai[5], &u);
  95         ge_add(&t, &A2, &Ai[5]);
  96         ge_p1p1_to_p3(&u, &t);
  97         ge_p3_to_cached(&Ai[6], &u);
  98         ge_add(&t, &A2, &Ai[6]);
  99         ge_p1p1_to_p3(&u, &t);
 100         ge_p3_to_cached(&Ai[7], &u);
 101         ge_p2_0(r);
 102
 103         for(i = 255; i >= 0; --i) {
 104                 if(aslide[i] || bslide[i]) {
 105                         break;
 106                 }
 107         }
 108
 109         for(; i >= 0; --i) {
 110                 ge_p2_dbl(&t, r);
 111
 112                 if(aslide[i] > 0) {
 113                         ge_p1p1_to_p3(&u, &t);
 114                         ge_add(&t, &u, &Ai[aslide[i] / 2]);
 115                 } else if(aslide[i] < 0) {
 116                         ge_p1p1_to_p3(&u, &t);
 117                         ge_sub(&t, &u, &Ai[(-aslide[i]) / 2]);
 118                 }
 119
 120                 if(bslide[i] > 0) {
 121                         ge_p1p1_to_p3(&u, &t);
 122                         ge_madd(&t, &u, &Bi[bslide[i] / 2]);
 123                 } else if(bslide[i] < 0) {
 124                         ge_p1p1_to_p3(&u, &t);
 125                         ge_msub(&t, &u, &Bi[(-bslide[i]) / 2]);
 126                 }
 127
 128                 ge_p1p1_to_p2(r, &t);
 129         }
 130 }
 131
 132
 133 static const fe d = {
 134         -10913610, 13857413, -15372611, 6949391, 114729, -8787816, -6275908, -3247719, -18696448, -12055116
 135         };
 136
 137 static const fe sqrtm1 = {
 138         -32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482
 139         };
 140
 141 int ge_frombytes_negate_vartime(ge_p3 *h, const unsigned char *s) {
 142         fe u;
 143         fe v;
 144         fe v3;
 145         fe vxx;
 146         fe check;
 147         fe_frombytes(h->Y, s);
 148         fe_1(h->Z);
 149         fe_sq(u, h->Y);
 150         fe_mul(v, u, d);
 151         fe_sub(u, u, h->Z);     /* u = y^2-1 */
 152         fe_add(v, v, h->Z);     /* v = dy^2+1 */
 153         fe_sq(v3, v);
 154         fe_mul(v3, v3, v);      /* v3 = v^3 */
 155         fe_sq(h->X, v3);
 156         fe_mul(h->X, h->X, v);
 157         fe_mul(h->X, h->X, u);  /* x = uv^7 */
 158         fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */
 159         fe_mul(h->X, h->X, v3);
 160         fe_mul(h->X, h->X, u);  /* x = uv^3(uv^7)^((q-5)/8) */
 161         fe_sq(vxx, h->X);
 162         fe_mul(vxx, vxx, v);
 163         fe_sub(check, vxx, u);  /* vx^2-u */
 164
 165         if(fe_isnonzero(check)) {
 166                 fe_add(check, vxx, u); /* vx^2+u */
 167
 168                 if(fe_isnonzero(check)) {
 169                         return -1;
 170                 }
 171
 172                 fe_mul(h->X, h->X, sqrtm1);
 173         }
 174
 175         if(fe_isnegative(h->X) == (s[31] >> 7)) {
 176                 fe_neg(h->X, h->X);
 177         }
 178
 179         fe_mul(h->T, h->X, h->Y);
 180         return 0;
 181 }
 182
 183
 184 /*
 185 r = p + q
 186 */
 187
 188 void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
 189         fe t0;
 190         fe_add(r->X, p->Y, p->X);
 191         fe_sub(r->Y, p->Y, p->X);
 192         fe_mul(r->Z, r->X, q->yplusx);
 193         fe_mul(r->Y, r->Y, q->yminusx);
 194         fe_mul(r->T, q->xy2d, p->T);
 195         fe_add(t0, p->Z, p->Z);
 196         fe_sub(r->X, r->Z, r->Y);
 197         fe_add(r->Y, r->Z, r->Y);
 198         fe_add(r->Z, t0, r->T);
 199         fe_sub(r->T, t0, r->T);
 200 }
 201
 202
 203 /*
 204 r = p - q
 205 */
 206
 207 void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
 208         fe t0;
 209
 210         fe_add(r->X, p->Y, p->X);
 211         fe_sub(r->Y, p->Y, p->X);
 212         fe_mul(r->Z, r->X, q->yminusx);
 213         fe_mul(r->Y, r->Y, q->yplusx);
 214         fe_mul(r->T, q->xy2d, p->T);
 215         fe_add(t0, p->Z, p->Z);
 216         fe_sub(r->X, r->Z, r->Y);
 217         fe_add(r->Y, r->Z, r->Y);
 218         fe_sub(r->Z, t0, r->T);
 219         fe_add(r->T, t0, r->T);
 220 }
 221
 222
 223 /*
 224 r = p
 225 */
 226
 227 void ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {
 228         fe_mul(r->X, p->X, p->T);
 229         fe_mul(r->Y, p->Y, p->Z);
 230         fe_mul(r->Z, p->Z, p->T);
 231 }
 232
 233
 234
 235 /*
 236 r = p
 237 */
 238
 239 void ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {
 240         fe_mul(r->X, p->X, p->T);
 241         fe_mul(r->Y, p->Y, p->Z);
 242         fe_mul(r->Z, p->Z, p->T);
 243         fe_mul(r->T, p->X, p->Y);
 244 }
 245
 246
 247 void ge_p2_0(ge_p2 *h) {
 248         fe_0(h->X);
 249         fe_1(h->Y);
 250         fe_1(h->Z);
 251 }
 252
 253
 254
 255 /*
 256 r = 2 * p
 257 */
 258
 259 void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {
 260         fe t0;
 261
 262         fe_sq(r->X, p->X);
 263         fe_sq(r->Z, p->Y);
 264         fe_sq2(r->T, p->Z);
 265         fe_add(r->Y, p->X, p->Y);
 266         fe_sq(t0, r->Y);
 267         fe_add(r->Y, r->Z, r->X);
 268         fe_sub(r->Z, r->Z, r->X);
 269         fe_sub(r->X, t0, r->Y);
 270         fe_sub(r->T, r->T, r->Z);
 271 }
 272
 273
 274 void ge_p3_0(ge_p3 *h) {
 275         fe_0(h->X);
 276         fe_1(h->Y);
 277         fe_1(h->Z);
 278         fe_0(h->T);
 279 }
 280
 281
 282 /*
 283 r = 2 * p
 284 */
 285
 286 void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {
 287         ge_p2 q;
 288         ge_p3_to_p2(&q, p);
 289         ge_p2_dbl(r, &q);
 290 }
 291
 292
 293
 294 /*
 295 r = p
 296 */
 297
 298 static const fe d2 = {
 299         -21827239, -5839606, -30745221, 13898782, 229458, 15978800, -12551817, -6495438, 29715968, 9444199
 300         };
 301
 302 void ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {
 303         fe_add(r->YplusX, p->Y, p->X);
 304         fe_sub(r->YminusX, p->Y, p->X);
 305         fe_copy(r->Z, p->Z);
 306         fe_mul(r->T2d, p->T, d2);
 307 }
 308
 309
 310 /*
 311 r = p
 312 */
 313
 314 void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {
 315         fe_copy(r->X, p->X);
 316         fe_copy(r->Y, p->Y);
 317         fe_copy(r->Z, p->Z);
 318 }
 319
 320
 321 void ge_p3_tobytes(unsigned char *s, const ge_p3 *h) {
 322         fe recip;
 323         fe x;
 324         fe y;
 325         fe_invert(recip, h->Z);
 326         fe_mul(x, h->X, recip);
 327         fe_mul(y, h->Y, recip);
 328         fe_tobytes(s, y);
 329         s[31] ^= fe_isnegative(x) << 7;
 330 }
 331
 332
 333 static unsigned char equal(signed char b, signed char c) {
 334         unsigned char ub = b;
 335         unsigned char uc = c;
 336         unsigned char x = ub ^ uc; /* 0: yes; 1..255: no */
 337         uint64_t y = x; /* 0: yes; 1..255: no */
 338         y -= 1; /* large: yes; 0..254: no */
 339         y >>= 63; /* 1: yes; 0: no */
 340         return (unsigned char) y;
 341 }
 342
 343 static unsigned char negative(signed char b) {
 344         uint64_t x = b; /* 18446744073709551361..18446744073709551615: yes; 0..255: no */
 345         x >>= 63; /* 1: yes; 0: no */
 346         return (unsigned char) x;
 347 }
 348
 349 static void cmov(ge_precomp *t, ge_precomp *u, unsigned char b) {
 350         fe_cmov(t->yplusx, u->yplusx, b);
 351         fe_cmov(t->yminusx, u->yminusx, b);
 352         fe_cmov(t->xy2d, u->xy2d, b);
 353 }
 354
 355
 356 static void select(ge_precomp *t, int pos, signed char b) {
 357         ge_precomp minust;
 358         unsigned char bnegative = negative(b);
 359         unsigned char babs = b - shlu8(((-bnegative) & b), 1);
 360         fe_1(t->yplusx);
 361         fe_1(t->yminusx);
 362         fe_0(t->xy2d);
 363         cmov(t, &base[pos][0], equal(babs, 1));
 364         cmov(t, &base[pos][1], equal(babs, 2));
 365         cmov(t, &base[pos][2], equal(babs, 3));
 366         cmov(t, &base[pos][3], equal(babs, 4));
 367         cmov(t, &base[pos][4], equal(babs, 5));
 368         cmov(t, &base[pos][5], equal(babs, 6));
 369         cmov(t, &base[pos][6], equal(babs, 7));
 370         cmov(t, &base[pos][7], equal(babs, 8));
 371         fe_copy(minust.yplusx, t->yminusx);
 372         fe_copy(minust.yminusx, t->yplusx);
 373         fe_neg(minust.xy2d, t->xy2d);
 374         cmov(t, &minust, bnegative);
 375 }
 376
 377 /*
 378 h = a * B
 379 where a = a[0]+256*a[1]+...+256^31 a[31]
 380 B is the Ed25519 base point (x,4/5) with x positive.
 381
 382 Preconditions:
 383   a[31] <= 127
 384 */
 385
 386 void ge_scalarmult_base(ge_p3 *h, const unsigned char *a) {
 387         signed char e[64];
 388         signed char carry;
 389         ge_p1p1 r;
 390         ge_p2 s;
 391         ge_precomp t;
 392         int i;
 393
 394         for(i = 0; i < 32; ++i) {
 395                 e[2 * i + 0] = (a[i] >> 0) & 15;
 396                 e[2 * i + 1] = (a[i] >> 4) & 15;
 397         }
 398
 399         /* each e[i] is between 0 and 15 */
 400         /* e[63] is between 0 and 7 */
 401         carry = 0;
 402
 403         for(i = 0; i < 63; ++i) {
 404                 e[i] += carry;
 405                 carry = e[i] + 8;
 406                 carry >>= 4;
 407                 e[i] -= shl32(carry, 4);
 408         }
 409
 410         e[63] += carry;
 411         /* each e[i] is between -8 and 8 */
 412         ge_p3_0(h);
 413
 414         for(i = 1; i < 64; i += 2) {
 415                 select(&t, i / 2, e[i]);
 416                 ge_madd(&r, h, &t);
 417                 ge_p1p1_to_p3(h, &r);
 418         }
 419
 420         ge_p3_dbl(&r, h);
 421         ge_p1p1_to_p2(&s, &r);
 422         ge_p2_dbl(&r, &s);
 423         ge_p1p1_to_p2(&s, &r);
 424         ge_p2_dbl(&r, &s);
 425         ge_p1p1_to_p2(&s, &r);
 426         ge_p2_dbl(&r, &s);
 427         ge_p1p1_to_p3(h, &r);
 428
 429         for(i = 0; i < 64; i += 2) {
 430                 select(&t, i / 2, e[i]);
 431                 ge_madd(&r, h, &t);
 432                 ge_p1p1_to_p3(h, &r);
 433         }
 434 }
 435
 436
 437 /*
 438 r = p - q
 439 */
 440
 441 void ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
 442         fe t0;
 443
 444         fe_add(r->X, p->Y, p->X);
 445         fe_sub(r->Y, p->Y, p->X);
 446         fe_mul(r->Z, r->X, q->YminusX);
 447         fe_mul(r->Y, r->Y, q->YplusX);
 448         fe_mul(r->T, q->T2d, p->T);
 449         fe_mul(r->X, p->Z, q->Z);
 450         fe_add(t0, r->X, r->X);
 451         fe_sub(r->X, r->Z, r->Y);
 452         fe_add(r->Y, r->Z, r->Y);
 453         fe_sub(r->Z, t0, r->T);
 454         fe_add(r->T, t0, r->T);
 455 }
 456
 457
 458 void ge_tobytes(unsigned char *s, const ge_p2 *h) {
 459         fe recip;
 460         fe x;
 461         fe y;
 462         fe_invert(recip, h->Z);
 463         fe_mul(x, h->X, recip);
 464         fe_mul(y, h->Y, recip);
 465         fe_tobytes(s, y);
 466         s[31] ^= fe_isnegative(x) << 7;
 467 }