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 } 321
This page was automatically generated by LXR 0.3.1. • OpenWrt