ed25519.c

   1 /* Edwards curve operations
   2  * Daniel Beer <dlbeer@gmail.com>, 9 Jan 2014
   3  *
   4  * This file is in the public domain.
   5  */
   6
   7 #include "ed25519.h"
   8
   9 /* Base point is (numbers wrapped):
  10  *
  11  *     x = 151122213495354007725011514095885315114
  12  *         54012693041857206046113283949847762202
  13  *     y = 463168356949264781694283940034751631413
  14  *         07993866256225615783033603165251855960
  15  *
  16  * y is derived by transforming the original Montgomery base (u=9). x
  17  * is the corresponding positive coordinate for the new curve equation.
  18  * t is x*y.
  19  */
  20 const struct ed25519_pt ed25519_base = {
  21         .x = {
  22                 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9,
  23                 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
  24                 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
  25                 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21
  26         },
  27         .y = {
  28                 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
  29                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
  30                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
  31                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66
  32         },
  33         .t = {
  34                 0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d,
  35                 0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20,
  36                 0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66,
  37                 0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67
  38         },
  39         .z = {1, 0}
  40 };
  41
  42 static const struct ed25519_pt ed25519_neutral = {
  43         .x = {0},
  44         .y = {1, 0},
  45         .t = {0},
  46         .z = {1, 0}
  47 };
  48
  49 /* Conversion to and from projective coordinates */
  50 void ed25519_project(struct ed25519_pt *p,
  51                      const uint8_t *x, const uint8_t *y)
  52 {
  53         f25519_copy(p->x, x);
  54         f25519_copy(p->y, y);
  55         f25519_load(p->z, 1);
  56         f25519_mul__distinct(p->t, x, y);
  57 }
  58
  59 void ed25519_unproject(uint8_t *x, uint8_t *y,
  60                        const struct ed25519_pt *p)
  61 {
  62         uint8_t z1[F25519_SIZE];
  63
  64         f25519_inv__distinct(z1, p->z);
  65         f25519_mul__distinct(x, p->x, z1);
  66         f25519_mul__distinct(y, p->y, z1);
  67
  68         f25519_normalize(x);
  69         f25519_normalize(y);
  70 }
  71
  72 /* Compress/uncompress points. We compress points by storing the x
  73  * coordinate and the parity of the y coordinate.
  74  *
  75  * Rearranging the curve equation, we obtain explicit formulae for the
  76  * coordinates:
  77  *
  78  *     x = sqrt((y^2-1) / (1+dy^2))
  79  *     y = sqrt((x^2+1) / (1-dx^2))
  80  *
  81  * Where d = (-121665/121666), or:
  82  *
  83  *     d = 370957059346694393431380835087545651895
  84  *         42113879843219016388785533085940283555
  85  */
  86
  87 static const uint8_t ed25519_d[F25519_SIZE] = {
  88         0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
  89         0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
  90         0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
  91         0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
  92 };
  93
  94 void ed25519_pack(uint8_t *c, const uint8_t *x, const uint8_t *y)
  95 {
  96         uint8_t tmp[F25519_SIZE];
  97         uint8_t parity;
  98
  99         f25519_copy(tmp, x);
 100         f25519_normalize(tmp);
 101         parity = (tmp[0] & 1) << 7;
 102
 103         f25519_copy(c, y);
 104         f25519_normalize(c);
 105         c[31] |= parity;
 106 }
 107
 108 uint8_t ed25519_try_unpack(uint8_t *x, uint8_t *y, const uint8_t *comp)
 109 {
 110         const int parity = comp[31] >> 7;
 111         uint8_t a[F25519_SIZE];
 112         uint8_t b[F25519_SIZE];
 113         uint8_t c[F25519_SIZE];
 114
 115         /* Unpack y */
 116         f25519_copy(y, comp);
 117         y[31] &= 127;
 118
 119         /* Compute c = y^2 */
 120         f25519_mul__distinct(c, y, y);
 121
 122         /* Compute b = (1+dy^2)^-1 */
 123         f25519_mul__distinct(b, c, ed25519_d);
 124         f25519_add(a, b, f25519_one);
 125         f25519_inv__distinct(b, a);
 126
 127         /* Compute a = y^2-1 */
 128         f25519_sub(a, c, f25519_one);
 129
 130         /* Compute c = a*b = (y^2-1)/(1-dy^2) */
 131         f25519_mul__distinct(c, a, b);
 132
 133         /* Compute a, b = +/-sqrt(c), if c is square */
 134         f25519_sqrt(a, c);
 135         f25519_neg(b, a);
 136
 137         /* Select one of them, based on the compressed parity bit */
 138         f25519_select(x, a, b, (a[0] ^ parity) & 1);
 139
 140         /* Verify that x^2 = c */
 141         f25519_mul__distinct(a, x, x);
 142         f25519_normalize(a);
 143         f25519_normalize(c);
 144
 145         return f25519_eq(a, c);
 146 }
 147
 148 /* k = 2d */
 149 static const uint8_t ed25519_k[F25519_SIZE] = {
 150         0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb,
 151         0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00,
 152         0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19,
 153         0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24
 154 };
 155
 156 void ed25519_add(struct ed25519_pt *r,
 157                  const struct ed25519_pt *p1, const struct ed25519_pt *p2)
 158 {
 159         /* Explicit formulas database: add-2008-hwcd-3
 160          *
 161          * source 2008 Hisil--Wong--Carter--Dawson,
 162          *     http://eprint.iacr.org/2008/522, Section 3.1
 163          * appliesto extended-1
 164          * parameter k
 165          * assume k = 2 d
 166          * compute A = (Y1-X1)(Y2-X2)
 167          * compute B = (Y1+X1)(Y2+X2)
 168          * compute C = T1 k T2
 169          * compute D = Z1 2 Z2
 170          * compute E = B - A
 171          * compute F = D - C
 172          * compute G = D + C
 173          * compute H = B + A
 174          * compute X3 = E F
 175          * compute Y3 = G H
 176          * compute T3 = E H
 177          * compute Z3 = F G
 178          */
 179         uint8_t a[F25519_SIZE];
 180         uint8_t b[F25519_SIZE];
 181         uint8_t c[F25519_SIZE];
 182         uint8_t d[F25519_SIZE];
 183         uint8_t e[F25519_SIZE];
 184         uint8_t f[F25519_SIZE];
 185         uint8_t g[F25519_SIZE];
 186         uint8_t h[F25519_SIZE];
 187
 188         /* A = (Y1-X1)(Y2-X2) */
 189         f25519_sub(c, p1->y, p1->x);
 190         f25519_sub(d, p2->y, p2->x);
 191         f25519_mul__distinct(a, c, d);
 192
 193         /* B = (Y1+X1)(Y2+X2) */
 194         f25519_add(c, p1->y, p1->x);
 195         f25519_add(d, p2->y, p2->x);
 196         f25519_mul__distinct(b, c, d);
 197
 198         /* C = T1 k T2 */
 199         f25519_mul__distinct(d, p1->t, p2->t);
 200         f25519_mul__distinct(c, d, ed25519_k);
 201
 202         /* D = Z1 2 Z2 */
 203         f25519_mul__distinct(d, p1->z, p2->z);
 204         f25519_add(d, d, d);
 205
 206         /* E = B - A */
 207         f25519_sub(e, b, a);
 208
 209         /* F = D - C */
 210         f25519_sub(f, d, c);
 211
 212         /* G = D + C */
 213         f25519_add(g, d, c);
 214
 215         /* H = B + A */
 216         f25519_add(h, b, a);
 217
 218         /* X3 = E F */
 219         f25519_mul__distinct(r->x, e, f);
 220
 221         /* Y3 = G H */
 222         f25519_mul__distinct(r->y, g, h);
 223
 224         /* T3 = E H */
 225         f25519_mul__distinct(r->t, e, h);
 226
 227         /* Z3 = F G */
 228         f25519_mul__distinct(r->z, f, g);
 229 }
 230
 231 static void ed25519_double(struct ed25519_pt *r, const struct ed25519_pt *p)
 232 {
 233         /* Explicit formulas database: dbl-2008-hwcd
 234          *
 235          * source 2008 Hisil--Wong--Carter--Dawson,
 236          *     http://eprint.iacr.org/2008/522, Section 3.3
 237          * compute A = X1^2
 238          * compute B = Y1^2
 239          * compute C = 2 Z1^2
 240          * compute D = a A
 241          * compute E = (X1+Y1)^2-A-B
 242          * compute G = D + B
 243          * compute F = G - C
 244          * compute H = D - B
 245          * compute X3 = E F
 246          * compute Y3 = G H
 247          * compute T3 = E H
 248          * compute Z3 = F G
 249          */
 250         uint8_t a[F25519_SIZE];
 251         uint8_t b[F25519_SIZE];
 252         uint8_t c[F25519_SIZE];
 253         uint8_t e[F25519_SIZE];
 254         uint8_t f[F25519_SIZE];
 255         uint8_t g[F25519_SIZE];
 256         uint8_t h[F25519_SIZE];
 257
 258         /* A = X1^2 */
 259         f25519_mul__distinct(a, p->x, p->x);
 260
 261         /* B = Y1^2 */
 262         f25519_mul__distinct(b, p->y, p->y);
 263
 264         /* C = 2 Z1^2 */
 265         f25519_mul__distinct(c, p->z, p->z);
 266         f25519_add(c, c, c);
 267
 268         /* D = a A (alter sign) */
 269         /* E = (X1+Y1)^2-A-B */
 270         f25519_add(f, p->x, p->y);
 271         f25519_mul__distinct(e, f, f);
 272         f25519_sub(e, e, a);
 273         f25519_sub(e, e, b);
 274
 275         /* G = D + B */
 276         f25519_sub(g, b, a);
 277
 278         /* F = G - C */
 279         f25519_sub(f, g, c);
 280
 281         /* H = D - B */
 282         f25519_neg(h, b);
 283         f25519_sub(h, h, a);
 284
 285         /* X3 = E F */
 286         f25519_mul__distinct(r->x, e, f);
 287
 288         /* Y3 = G H */
 289         f25519_mul__distinct(r->y, g, h);
 290
 291         /* T3 = E H */
 292         f25519_mul__distinct(r->t, e, h);
 293
 294         /* Z3 = F G */
 295         f25519_mul__distinct(r->z, f, g);
 296 }
 297
 298 void ed25519_smult(struct ed25519_pt *r_out, const struct ed25519_pt *p,
 299                    const uint8_t *e)
 300 {
 301         struct ed25519_pt r;
 302         int i;
 303
 304         ed25519_copy(&r, &ed25519_neutral);
 305
 306         for (i = 255; i >= 0; i--) {
 307                 const uint8_t bit = (e[i >> 3] >> (i & 7)) & 1;
 308                 struct ed25519_pt s;
 309
 310                 ed25519_double(&r, &r);
 311                 ed25519_add(&s, &r, p);
 312
 313                 f25519_select(r.x, r.x, s.x, bit);
 314                 f25519_select(r.y, r.y, s.y, bit);
 315                 f25519_select(r.z, r.z, s.z, bit);
 316                 f25519_select(r.t, r.t, s.t, bit);
 317         }
 318
 319         ed25519_copy(r_out, &r);
 320 }