| 1 |
/* Copyright (c) 2015, Google Inc. |
| 2 |
* |
| 3 |
* Permission to use, copy, modify, and/or distribute this software for any |
| 4 |
* purpose with or without fee is hereby granted, provided that the above |
| 5 |
* copyright notice and this permission notice appear in all copies. |
| 6 |
* |
| 7 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 8 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 9 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
| 10 |
* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 11 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
| 12 |
* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
| 13 |
* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ |
| 14 |
|
| 15 |
/* This code is mostly taken from the ref10 version of Ed25519 in SUPERCOP |
| 16 |
* 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as |
| 17 |
* public domain but this file has the ISC license just to keep licencing |
| 18 |
* simple. |
| 19 |
* |
| 20 |
* The field functions are shared by Ed25519 and X25519 where possible. */ |
| 21 |
|
| 22 |
#include <openssl/curve25519.h> |
| 23 |
|
| 24 |
#include <string.h> |
| 25 |
|
| 26 |
#include "internal.h" |
| 27 |
|
| 28 |
|
| 29 |
#if defined(BORINGSSL_X25519_X86_64) |
| 30 |
|
| 31 |
typedef struct { uint64_t v[5]; } fe25519; |
| 32 |
|
| 33 |
/* These functions are defined in asm/x25519-x86_64.S */ |
| 34 |
void x25519_x86_64_work_cswap(fe25519 *, uint64_t); |
| 35 |
void x25519_x86_64_mul(fe25519 *out, const fe25519 *a, const fe25519 *b); |
| 36 |
void x25519_x86_64_square(fe25519 *out, const fe25519 *a); |
| 37 |
void x25519_x86_64_freeze(fe25519 *); |
| 38 |
void x25519_x86_64_ladderstep(fe25519 *work); |
| 39 |
|
| 40 |
static void fe25519_setint(fe25519 *r, unsigned v) { |
| 41 |
r->v[0] = v; |
| 42 |
r->v[1] = 0; |
| 43 |
r->v[2] = 0; |
| 44 |
r->v[3] = 0; |
| 45 |
r->v[4] = 0; |
| 46 |
} |
| 47 |
|
| 48 |
/* Assumes input x being reduced below 2^255 */ |
| 49 |
static void fe25519_pack(unsigned char r[32], const fe25519 *x) { |
| 50 |
fe25519 t; |
| 51 |
t = *x; |
| 52 |
x25519_x86_64_freeze(&t); |
| 53 |
|
| 54 |
r[0] = (uint8_t)(t.v[0] & 0xff); |
| 55 |
r[1] = (uint8_t)((t.v[0] >> 8) & 0xff); |
| 56 |
r[2] = (uint8_t)((t.v[0] >> 16) & 0xff); |
| 57 |
r[3] = (uint8_t)((t.v[0] >> 24) & 0xff); |
| 58 |
r[4] = (uint8_t)((t.v[0] >> 32) & 0xff); |
| 59 |
r[5] = (uint8_t)((t.v[0] >> 40) & 0xff); |
| 60 |
r[6] = (uint8_t)((t.v[0] >> 48)); |
| 61 |
|
| 62 |
r[6] ^= (uint8_t)((t.v[1] << 3) & 0xf8); |
| 63 |
r[7] = (uint8_t)((t.v[1] >> 5) & 0xff); |
| 64 |
r[8] = (uint8_t)((t.v[1] >> 13) & 0xff); |
| 65 |
r[9] = (uint8_t)((t.v[1] >> 21) & 0xff); |
| 66 |
r[10] = (uint8_t)((t.v[1] >> 29) & 0xff); |
| 67 |
r[11] = (uint8_t)((t.v[1] >> 37) & 0xff); |
| 68 |
r[12] = (uint8_t)((t.v[1] >> 45)); |
| 69 |
|
| 70 |
r[12] ^= (uint8_t)((t.v[2] << 6) & 0xc0); |
| 71 |
r[13] = (uint8_t)((t.v[2] >> 2) & 0xff); |
| 72 |
r[14] = (uint8_t)((t.v[2] >> 10) & 0xff); |
| 73 |
r[15] = (uint8_t)((t.v[2] >> 18) & 0xff); |
| 74 |
r[16] = (uint8_t)((t.v[2] >> 26) & 0xff); |
| 75 |
r[17] = (uint8_t)((t.v[2] >> 34) & 0xff); |
| 76 |
r[18] = (uint8_t)((t.v[2] >> 42) & 0xff); |
| 77 |
r[19] = (uint8_t)((t.v[2] >> 50)); |
| 78 |
|
| 79 |
r[19] ^= (uint8_t)((t.v[3] << 1) & 0xfe); |
| 80 |
r[20] = (uint8_t)((t.v[3] >> 7) & 0xff); |
| 81 |
r[21] = (uint8_t)((t.v[3] >> 15) & 0xff); |
| 82 |
r[22] = (uint8_t)((t.v[3] >> 23) & 0xff); |
| 83 |
r[23] = (uint8_t)((t.v[3] >> 31) & 0xff); |
| 84 |
r[24] = (uint8_t)((t.v[3] >> 39) & 0xff); |
| 85 |
r[25] = (uint8_t)((t.v[3] >> 47)); |
| 86 |
|
| 87 |
r[25] ^= (uint8_t)((t.v[4] << 4) & 0xf0); |
| 88 |
r[26] = (uint8_t)((t.v[4] >> 4) & 0xff); |
| 89 |
r[27] = (uint8_t)((t.v[4] >> 12) & 0xff); |
| 90 |
r[28] = (uint8_t)((t.v[4] >> 20) & 0xff); |
| 91 |
r[29] = (uint8_t)((t.v[4] >> 28) & 0xff); |
| 92 |
r[30] = (uint8_t)((t.v[4] >> 36) & 0xff); |
| 93 |
r[31] = (uint8_t)((t.v[4] >> 44)); |
| 94 |
} |
| 95 |
|
| 96 |
static void fe25519_unpack(fe25519 *r, const uint8_t x[32]) { |
| 97 |
r->v[0] = x[0]; |
| 98 |
r->v[0] += (uint64_t)x[1] << 8; |
| 99 |
r->v[0] += (uint64_t)x[2] << 16; |
| 100 |
r->v[0] += (uint64_t)x[3] << 24; |
| 101 |
r->v[0] += (uint64_t)x[4] << 32; |
| 102 |
r->v[0] += (uint64_t)x[5] << 40; |
| 103 |
r->v[0] += ((uint64_t)x[6] & 7) << 48; |
| 104 |
|
| 105 |
r->v[1] = x[6] >> 3; |
| 106 |
r->v[1] += (uint64_t)x[7] << 5; |
| 107 |
r->v[1] += (uint64_t)x[8] << 13; |
| 108 |
r->v[1] += (uint64_t)x[9] << 21; |
| 109 |
r->v[1] += (uint64_t)x[10] << 29; |
| 110 |
r->v[1] += (uint64_t)x[11] << 37; |
| 111 |
r->v[1] += ((uint64_t)x[12] & 63) << 45; |
| 112 |
|
| 113 |
r->v[2] = x[12] >> 6; |
| 114 |
r->v[2] += (uint64_t)x[13] << 2; |
| 115 |
r->v[2] += (uint64_t)x[14] << 10; |
| 116 |
r->v[2] += (uint64_t)x[15] << 18; |
| 117 |
r->v[2] += (uint64_t)x[16] << 26; |
| 118 |
r->v[2] += (uint64_t)x[17] << 34; |
| 119 |
r->v[2] += (uint64_t)x[18] << 42; |
| 120 |
r->v[2] += ((uint64_t)x[19] & 1) << 50; |
| 121 |
|
| 122 |
r->v[3] = x[19] >> 1; |
| 123 |
r->v[3] += (uint64_t)x[20] << 7; |
| 124 |
r->v[3] += (uint64_t)x[21] << 15; |
| 125 |
r->v[3] += (uint64_t)x[22] << 23; |
| 126 |
r->v[3] += (uint64_t)x[23] << 31; |
| 127 |
r->v[3] += (uint64_t)x[24] << 39; |
| 128 |
r->v[3] += ((uint64_t)x[25] & 15) << 47; |
| 129 |
|
| 130 |
r->v[4] = x[25] >> 4; |
| 131 |
r->v[4] += (uint64_t)x[26] << 4; |
| 132 |
r->v[4] += (uint64_t)x[27] << 12; |
| 133 |
r->v[4] += (uint64_t)x[28] << 20; |
| 134 |
r->v[4] += (uint64_t)x[29] << 28; |
| 135 |
r->v[4] += (uint64_t)x[30] << 36; |
| 136 |
r->v[4] += ((uint64_t)x[31] & 127) << 44; |
| 137 |
} |
| 138 |
|
| 139 |
static void fe25519_invert(fe25519 *r, const fe25519 *x) { |
| 140 |
fe25519 z2; |
| 141 |
fe25519 z9; |
| 142 |
fe25519 z11; |
| 143 |
fe25519 z2_5_0; |
| 144 |
fe25519 z2_10_0; |
| 145 |
fe25519 z2_20_0; |
| 146 |
fe25519 z2_50_0; |
| 147 |
fe25519 z2_100_0; |
| 148 |
fe25519 t; |
| 149 |
int i; |
| 150 |
|
| 151 |
/* 2 */ x25519_x86_64_square(&z2, x); |
| 152 |
/* 4 */ x25519_x86_64_square(&t, &z2); |
| 153 |
/* 8 */ x25519_x86_64_square(&t, &t); |
| 154 |
/* 9 */ x25519_x86_64_mul(&z9, &t, x); |
| 155 |
/* 11 */ x25519_x86_64_mul(&z11, &z9, &z2); |
| 156 |
/* 22 */ x25519_x86_64_square(&t, &z11); |
| 157 |
/* 2^5 - 2^0 = 31 */ x25519_x86_64_mul(&z2_5_0, &t, &z9); |
| 158 |
|
| 159 |
/* 2^6 - 2^1 */ x25519_x86_64_square(&t, &z2_5_0); |
| 160 |
/* 2^20 - 2^10 */ for (i = 1; i < 5; i++) { x25519_x86_64_square(&t, &t); } |
| 161 |
/* 2^10 - 2^0 */ x25519_x86_64_mul(&z2_10_0, &t, &z2_5_0); |
| 162 |
|
| 163 |
/* 2^11 - 2^1 */ x25519_x86_64_square(&t, &z2_10_0); |
| 164 |
/* 2^20 - 2^10 */ for (i = 1; i < 10; i++) { x25519_x86_64_square(&t, &t); } |
| 165 |
/* 2^20 - 2^0 */ x25519_x86_64_mul(&z2_20_0, &t, &z2_10_0); |
| 166 |
|
| 167 |
/* 2^21 - 2^1 */ x25519_x86_64_square(&t, &z2_20_0); |
| 168 |
/* 2^40 - 2^20 */ for (i = 1; i < 20; i++) { x25519_x86_64_square(&t, &t); } |
| 169 |
/* 2^40 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_20_0); |
| 170 |
|
| 171 |
/* 2^41 - 2^1 */ x25519_x86_64_square(&t, &t); |
| 172 |
/* 2^50 - 2^10 */ for (i = 1; i < 10; i++) { x25519_x86_64_square(&t, &t); } |
| 173 |
/* 2^50 - 2^0 */ x25519_x86_64_mul(&z2_50_0, &t, &z2_10_0); |
| 174 |
|
| 175 |
/* 2^51 - 2^1 */ x25519_x86_64_square(&t, &z2_50_0); |
| 176 |
/* 2^100 - 2^50 */ for (i = 1; i < 50; i++) { x25519_x86_64_square(&t, &t); } |
| 177 |
/* 2^100 - 2^0 */ x25519_x86_64_mul(&z2_100_0, &t, &z2_50_0); |
| 178 |
|
| 179 |
/* 2^101 - 2^1 */ x25519_x86_64_square(&t, &z2_100_0); |
| 180 |
/* 2^200 - 2^100 */ for (i = 1; i < 100; i++) { |
| 181 |
x25519_x86_64_square(&t, &t); |
| 182 |
} |
| 183 |
/* 2^200 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_100_0); |
| 184 |
|
| 185 |
/* 2^201 - 2^1 */ x25519_x86_64_square(&t, &t); |
| 186 |
/* 2^250 - 2^50 */ for (i = 1; i < 50; i++) { x25519_x86_64_square(&t, &t); } |
| 187 |
/* 2^250 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_50_0); |
| 188 |
|
| 189 |
/* 2^251 - 2^1 */ x25519_x86_64_square(&t, &t); |
| 190 |
/* 2^252 - 2^2 */ x25519_x86_64_square(&t, &t); |
| 191 |
/* 2^253 - 2^3 */ x25519_x86_64_square(&t, &t); |
| 192 |
|
| 193 |
/* 2^254 - 2^4 */ x25519_x86_64_square(&t, &t); |
| 194 |
|
| 195 |
/* 2^255 - 2^5 */ x25519_x86_64_square(&t, &t); |
| 196 |
/* 2^255 - 21 */ x25519_x86_64_mul(r, &t, &z11); |
| 197 |
} |
| 198 |
|
| 199 |
static void mladder(fe25519 *xr, fe25519 *zr, const uint8_t s[32]) { |
| 200 |
fe25519 work[5]; |
| 201 |
|
| 202 |
work[0] = *xr; |
| 203 |
fe25519_setint(work + 1, 1); |
| 204 |
fe25519_setint(work + 2, 0); |
| 205 |
work[3] = *xr; |
| 206 |
fe25519_setint(work + 4, 1); |
| 207 |
|
| 208 |
int i, j; |
| 209 |
uint8_t prevbit = 0; |
| 210 |
|
| 211 |
j = 6; |
| 212 |
for (i = 31; i >= 0; i--) { |
| 213 |
while (j >= 0) { |
| 214 |
const uint8_t bit = 1 & (s[i] >> j); |
| 215 |
const uint64_t swap = bit ^ prevbit; |
| 216 |
prevbit = bit; |
| 217 |
x25519_x86_64_work_cswap(work + 1, swap); |
| 218 |
x25519_x86_64_ladderstep(work); |
| 219 |
j -= 1; |
| 220 |
} |
| 221 |
j = 7; |
| 222 |
} |
| 223 |
|
| 224 |
*xr = work[1]; |
| 225 |
*zr = work[2]; |
| 226 |
} |
| 227 |
|
| 228 |
void x25519_x86_64(uint8_t out[32], const uint8_t scalar[32], |
| 229 |
const uint8_t point[32]) { |
| 230 |
uint8_t e[32]; |
| 231 |
memcpy(e, scalar, sizeof(e)); |
| 232 |
|
| 233 |
e[0] &= 248; |
| 234 |
e[31] &= 127; |
| 235 |
e[31] |= 64; |
| 236 |
|
| 237 |
fe25519 t; |
| 238 |
fe25519 z; |
| 239 |
fe25519_unpack(&t, point); |
| 240 |
mladder(&t, &z, e); |
| 241 |
fe25519_invert(&z, &z); |
| 242 |
x25519_x86_64_mul(&t, &t, &z); |
| 243 |
fe25519_pack(out, &t); |
| 244 |
} |
| 245 |
|
| 246 |
#endif /* BORINGSSL_X25519_X86_64 */ |