Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 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 | /* A 64-bit implementation of the NIST P-256 elliptic curve point |
| 16 | * multiplication |
| 17 | * |
| 18 | * OpenSSL integration was taken from Emilia Kasper's work in ecp_nistp224.c. |
| 19 | * Otherwise based on Emilia's P224 work, which was inspired by my curve25519 |
| 20 | * work which got its smarts from Daniel J. Bernstein's work on the same. */ |
| 21 | |
| 22 | #include <openssl/base.h> |
| 23 | |
| 24 | #if defined(OPENSSL_64_BIT) && !defined(OPENSSL_WINDOWS) |
| 25 | |
| 26 | #include <openssl/bn.h> |
| 27 | #include <openssl/ec.h> |
| 28 | #include <openssl/err.h> |
| 29 | #include <openssl/mem.h> |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 30 | |
| 31 | #include <string.h> |
| 32 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 33 | #include "../delocate.h" |
| 34 | #include "../../internal.h" |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 35 | #include "internal.h" |
| 36 | |
| 37 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 38 | /* The underlying field. P256 operates over GF(2^256-2^224+2^192+2^96-1). We |
| 39 | * can serialise an element of this field into 32 bytes. We call this an |
| 40 | * felem_bytearray. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 41 | typedef uint8_t felem_bytearray[32]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 42 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 43 | /* The representation of field elements. |
| 44 | * ------------------------------------ |
| 45 | * |
| 46 | * We represent field elements with either four 128-bit values, eight 128-bit |
| 47 | * values, or four 64-bit values. The field element represented is: |
| 48 | * v[0]*2^0 + v[1]*2^64 + v[2]*2^128 + v[3]*2^192 (mod p) |
| 49 | * or: |
| 50 | * v[0]*2^0 + v[1]*2^64 + v[2]*2^128 + ... + v[8]*2^512 (mod p) |
| 51 | * |
| 52 | * 128-bit values are called 'limbs'. Since the limbs are spaced only 64 bits |
| 53 | * apart, but are 128-bits wide, the most significant bits of each limb overlap |
| 54 | * with the least significant bits of the next. |
| 55 | * |
| 56 | * A field element with four limbs is an 'felem'. One with eight limbs is a |
| 57 | * 'longfelem' |
| 58 | * |
| 59 | * A field element with four, 64-bit values is called a 'smallfelem'. Small |
| 60 | * values are used as intermediate values before multiplication. */ |
| 61 | |
| 62 | #define NLIMBS 4 |
| 63 | |
| 64 | typedef uint128_t limb; |
| 65 | typedef limb felem[NLIMBS]; |
| 66 | typedef limb longfelem[NLIMBS * 2]; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 67 | typedef uint64_t smallfelem[NLIMBS]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 68 | |
| 69 | /* This is the value of the prime as four 64-bit words, little-endian. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 70 | static const uint64_t kPrime[4] = {0xfffffffffffffffful, 0xffffffff, 0, |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 71 | 0xffffffff00000001ul}; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 72 | static const uint64_t bottom63bits = 0x7ffffffffffffffful; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 73 | |
| 74 | /* bin32_to_felem takes a little-endian byte array and converts it into felem |
| 75 | * form. This assumes that the CPU is little-endian. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 76 | static void bin32_to_felem(felem out, const uint8_t in[32]) { |
| 77 | out[0] = *((const uint64_t *)&in[0]); |
| 78 | out[1] = *((const uint64_t *)&in[8]); |
| 79 | out[2] = *((const uint64_t *)&in[16]); |
| 80 | out[3] = *((const uint64_t *)&in[24]); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 81 | } |
| 82 | |
| 83 | /* smallfelem_to_bin32 takes a smallfelem and serialises into a little endian, |
| 84 | * 32 byte array. This assumes that the CPU is little-endian. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 85 | static void smallfelem_to_bin32(uint8_t out[32], const smallfelem in) { |
| 86 | *((uint64_t *)&out[0]) = in[0]; |
| 87 | *((uint64_t *)&out[8]) = in[1]; |
| 88 | *((uint64_t *)&out[16]) = in[2]; |
| 89 | *((uint64_t *)&out[24]) = in[3]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 90 | } |
| 91 | |
| 92 | /* To preserve endianness when using BN_bn2bin and BN_bin2bn. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 93 | static void flip_endian(uint8_t *out, const uint8_t *in, size_t len) { |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 94 | for (size_t i = 0; i < len; ++i) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 95 | out[i] = in[len - 1 - i]; |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | /* BN_to_felem converts an OpenSSL BIGNUM into an felem. */ |
| 100 | static int BN_to_felem(felem out, const BIGNUM *bn) { |
| 101 | if (BN_is_negative(bn)) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 102 | OPENSSL_PUT_ERROR(EC, EC_R_BIGNUM_OUT_OF_RANGE); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 103 | return 0; |
| 104 | } |
| 105 | |
| 106 | felem_bytearray b_out; |
| 107 | /* BN_bn2bin eats leading zeroes */ |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 108 | OPENSSL_memset(b_out, 0, sizeof(b_out)); |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 109 | size_t num_bytes = BN_num_bytes(bn); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 110 | if (num_bytes > sizeof(b_out)) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 111 | OPENSSL_PUT_ERROR(EC, EC_R_BIGNUM_OUT_OF_RANGE); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 112 | return 0; |
| 113 | } |
| 114 | |
| 115 | felem_bytearray b_in; |
| 116 | num_bytes = BN_bn2bin(bn, b_in); |
| 117 | flip_endian(b_out, b_in, num_bytes); |
| 118 | bin32_to_felem(out, b_out); |
| 119 | return 1; |
| 120 | } |
| 121 | |
| 122 | /* felem_to_BN converts an felem into an OpenSSL BIGNUM. */ |
| 123 | static BIGNUM *smallfelem_to_BN(BIGNUM *out, const smallfelem in) { |
| 124 | felem_bytearray b_in, b_out; |
| 125 | smallfelem_to_bin32(b_in, in); |
| 126 | flip_endian(b_out, b_in, sizeof(b_out)); |
| 127 | return BN_bin2bn(b_out, sizeof(b_out), out); |
| 128 | } |
| 129 | |
| 130 | /* Field operations. */ |
| 131 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 132 | static void felem_assign(felem out, const felem in) { |
| 133 | out[0] = in[0]; |
| 134 | out[1] = in[1]; |
| 135 | out[2] = in[2]; |
| 136 | out[3] = in[3]; |
| 137 | } |
| 138 | |
| 139 | /* felem_sum sets out = out + in. */ |
| 140 | static void felem_sum(felem out, const felem in) { |
| 141 | out[0] += in[0]; |
| 142 | out[1] += in[1]; |
| 143 | out[2] += in[2]; |
| 144 | out[3] += in[3]; |
| 145 | } |
| 146 | |
| 147 | /* felem_small_sum sets out = out + in. */ |
| 148 | static void felem_small_sum(felem out, const smallfelem in) { |
| 149 | out[0] += in[0]; |
| 150 | out[1] += in[1]; |
| 151 | out[2] += in[2]; |
| 152 | out[3] += in[3]; |
| 153 | } |
| 154 | |
| 155 | /* felem_scalar sets out = out * scalar */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 156 | static void felem_scalar(felem out, const uint64_t scalar) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 157 | out[0] *= scalar; |
| 158 | out[1] *= scalar; |
| 159 | out[2] *= scalar; |
| 160 | out[3] *= scalar; |
| 161 | } |
| 162 | |
| 163 | /* longfelem_scalar sets out = out * scalar */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 164 | static void longfelem_scalar(longfelem out, const uint64_t scalar) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 165 | out[0] *= scalar; |
| 166 | out[1] *= scalar; |
| 167 | out[2] *= scalar; |
| 168 | out[3] *= scalar; |
| 169 | out[4] *= scalar; |
| 170 | out[5] *= scalar; |
| 171 | out[6] *= scalar; |
| 172 | out[7] *= scalar; |
| 173 | } |
| 174 | |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 175 | #define two105m41m9 ((((limb)1) << 105) - (((limb)1) << 41) - (((limb)1) << 9)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 176 | #define two105 (((limb)1) << 105) |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 177 | #define two105m41p9 ((((limb)1) << 105) - (((limb)1) << 41) + (((limb)1) << 9)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 178 | |
| 179 | /* zero105 is 0 mod p */ |
| 180 | static const felem zero105 = {two105m41m9, two105, two105m41p9, two105m41p9}; |
| 181 | |
| 182 | /* smallfelem_neg sets |out| to |-small| |
| 183 | * On exit: |
| 184 | * out[i] < out[i] + 2^105 */ |
| 185 | static void smallfelem_neg(felem out, const smallfelem small) { |
| 186 | /* In order to prevent underflow, we subtract from 0 mod p. */ |
| 187 | out[0] = zero105[0] - small[0]; |
| 188 | out[1] = zero105[1] - small[1]; |
| 189 | out[2] = zero105[2] - small[2]; |
| 190 | out[3] = zero105[3] - small[3]; |
| 191 | } |
| 192 | |
| 193 | /* felem_diff subtracts |in| from |out| |
| 194 | * On entry: |
| 195 | * in[i] < 2^104 |
| 196 | * On exit: |
| 197 | * out[i] < out[i] + 2^105. */ |
| 198 | static void felem_diff(felem out, const felem in) { |
| 199 | /* In order to prevent underflow, we add 0 mod p before subtracting. */ |
| 200 | out[0] += zero105[0]; |
| 201 | out[1] += zero105[1]; |
| 202 | out[2] += zero105[2]; |
| 203 | out[3] += zero105[3]; |
| 204 | |
| 205 | out[0] -= in[0]; |
| 206 | out[1] -= in[1]; |
| 207 | out[2] -= in[2]; |
| 208 | out[3] -= in[3]; |
| 209 | } |
| 210 | |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 211 | #define two107m43m11 \ |
| 212 | ((((limb)1) << 107) - (((limb)1) << 43) - (((limb)1) << 11)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 213 | #define two107 (((limb)1) << 107) |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 214 | #define two107m43p11 \ |
| 215 | ((((limb)1) << 107) - (((limb)1) << 43) + (((limb)1) << 11)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 216 | |
| 217 | /* zero107 is 0 mod p */ |
| 218 | static const felem zero107 = {two107m43m11, two107, two107m43p11, two107m43p11}; |
| 219 | |
| 220 | /* An alternative felem_diff for larger inputs |in| |
| 221 | * felem_diff_zero107 subtracts |in| from |out| |
| 222 | * On entry: |
| 223 | * in[i] < 2^106 |
| 224 | * On exit: |
| 225 | * out[i] < out[i] + 2^107. */ |
| 226 | static void felem_diff_zero107(felem out, const felem in) { |
| 227 | /* In order to prevent underflow, we add 0 mod p before subtracting. */ |
| 228 | out[0] += zero107[0]; |
| 229 | out[1] += zero107[1]; |
| 230 | out[2] += zero107[2]; |
| 231 | out[3] += zero107[3]; |
| 232 | |
| 233 | out[0] -= in[0]; |
| 234 | out[1] -= in[1]; |
| 235 | out[2] -= in[2]; |
| 236 | out[3] -= in[3]; |
| 237 | } |
| 238 | |
| 239 | /* longfelem_diff subtracts |in| from |out| |
| 240 | * On entry: |
| 241 | * in[i] < 7*2^67 |
| 242 | * On exit: |
| 243 | * out[i] < out[i] + 2^70 + 2^40. */ |
| 244 | static void longfelem_diff(longfelem out, const longfelem in) { |
| 245 | static const limb two70m8p6 = |
| 246 | (((limb)1) << 70) - (((limb)1) << 8) + (((limb)1) << 6); |
| 247 | static const limb two70p40 = (((limb)1) << 70) + (((limb)1) << 40); |
| 248 | static const limb two70 = (((limb)1) << 70); |
| 249 | static const limb two70m40m38p6 = (((limb)1) << 70) - (((limb)1) << 40) - |
| 250 | (((limb)1) << 38) + (((limb)1) << 6); |
| 251 | static const limb two70m6 = (((limb)1) << 70) - (((limb)1) << 6); |
| 252 | |
| 253 | /* add 0 mod p to avoid underflow */ |
| 254 | out[0] += two70m8p6; |
| 255 | out[1] += two70p40; |
| 256 | out[2] += two70; |
| 257 | out[3] += two70m40m38p6; |
| 258 | out[4] += two70m6; |
| 259 | out[5] += two70m6; |
| 260 | out[6] += two70m6; |
| 261 | out[7] += two70m6; |
| 262 | |
| 263 | /* in[i] < 7*2^67 < 2^70 - 2^40 - 2^38 + 2^6 */ |
| 264 | out[0] -= in[0]; |
| 265 | out[1] -= in[1]; |
| 266 | out[2] -= in[2]; |
| 267 | out[3] -= in[3]; |
| 268 | out[4] -= in[4]; |
| 269 | out[5] -= in[5]; |
| 270 | out[6] -= in[6]; |
| 271 | out[7] -= in[7]; |
| 272 | } |
| 273 | |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 274 | #define two64m0 ((((limb)1) << 64) - 1) |
| 275 | #define two110p32m0 ((((limb)1) << 110) + (((limb)1) << 32) - 1) |
| 276 | #define two64m46 ((((limb)1) << 64) - (((limb)1) << 46)) |
| 277 | #define two64m32 ((((limb)1) << 64) - (((limb)1) << 32)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 278 | |
| 279 | /* zero110 is 0 mod p. */ |
| 280 | static const felem zero110 = {two64m0, two110p32m0, two64m46, two64m32}; |
| 281 | |
| 282 | /* felem_shrink converts an felem into a smallfelem. The result isn't quite |
| 283 | * minimal as the value may be greater than p. |
| 284 | * |
| 285 | * On entry: |
| 286 | * in[i] < 2^109 |
| 287 | * On exit: |
| 288 | * out[i] < 2^64. */ |
| 289 | static void felem_shrink(smallfelem out, const felem in) { |
| 290 | felem tmp; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 291 | uint64_t a, b, mask; |
| 292 | int64_t high, low; |
| 293 | static const uint64_t kPrime3Test = |
| 294 | 0x7fffffff00000001ul; /* 2^63 - 2^32 + 1 */ |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 295 | |
| 296 | /* Carry 2->3 */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 297 | tmp[3] = zero110[3] + in[3] + ((uint64_t)(in[2] >> 64)); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 298 | /* tmp[3] < 2^110 */ |
| 299 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 300 | tmp[2] = zero110[2] + (uint64_t)in[2]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 301 | tmp[0] = zero110[0] + in[0]; |
| 302 | tmp[1] = zero110[1] + in[1]; |
| 303 | /* tmp[0] < 2**110, tmp[1] < 2^111, tmp[2] < 2**65 */ |
| 304 | |
| 305 | /* We perform two partial reductions where we eliminate the high-word of |
| 306 | * tmp[3]. We don't update the other words till the end. */ |
| 307 | a = tmp[3] >> 64; /* a < 2^46 */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 308 | tmp[3] = (uint64_t)tmp[3]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 309 | tmp[3] -= a; |
| 310 | tmp[3] += ((limb)a) << 32; |
| 311 | /* tmp[3] < 2^79 */ |
| 312 | |
| 313 | b = a; |
| 314 | a = tmp[3] >> 64; /* a < 2^15 */ |
| 315 | b += a; /* b < 2^46 + 2^15 < 2^47 */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 316 | tmp[3] = (uint64_t)tmp[3]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 317 | tmp[3] -= a; |
| 318 | tmp[3] += ((limb)a) << 32; |
| 319 | /* tmp[3] < 2^64 + 2^47 */ |
| 320 | |
| 321 | /* This adjusts the other two words to complete the two partial |
| 322 | * reductions. */ |
| 323 | tmp[0] += b; |
| 324 | tmp[1] -= (((limb)b) << 32); |
| 325 | |
| 326 | /* In order to make space in tmp[3] for the carry from 2 -> 3, we |
| 327 | * conditionally subtract kPrime if tmp[3] is large enough. */ |
| 328 | high = tmp[3] >> 64; |
| 329 | /* As tmp[3] < 2^65, high is either 1 or 0 */ |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 330 | high = ~(high - 1); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 331 | /* high is: |
| 332 | * all ones if the high word of tmp[3] is 1 |
| 333 | * all zeros if the high word of tmp[3] if 0 */ |
| 334 | low = tmp[3]; |
| 335 | mask = low >> 63; |
| 336 | /* mask is: |
| 337 | * all ones if the MSB of low is 1 |
| 338 | * all zeros if the MSB of low if 0 */ |
| 339 | low &= bottom63bits; |
| 340 | low -= kPrime3Test; |
| 341 | /* if low was greater than kPrime3Test then the MSB is zero */ |
| 342 | low = ~low; |
| 343 | low >>= 63; |
| 344 | /* low is: |
| 345 | * all ones if low was > kPrime3Test |
| 346 | * all zeros if low was <= kPrime3Test */ |
| 347 | mask = (mask & low) | high; |
| 348 | tmp[0] -= mask & kPrime[0]; |
| 349 | tmp[1] -= mask & kPrime[1]; |
| 350 | /* kPrime[2] is zero, so omitted */ |
| 351 | tmp[3] -= mask & kPrime[3]; |
| 352 | /* tmp[3] < 2**64 - 2**32 + 1 */ |
| 353 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 354 | tmp[1] += ((uint64_t)(tmp[0] >> 64)); |
| 355 | tmp[0] = (uint64_t)tmp[0]; |
| 356 | tmp[2] += ((uint64_t)(tmp[1] >> 64)); |
| 357 | tmp[1] = (uint64_t)tmp[1]; |
| 358 | tmp[3] += ((uint64_t)(tmp[2] >> 64)); |
| 359 | tmp[2] = (uint64_t)tmp[2]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 360 | /* tmp[i] < 2^64 */ |
| 361 | |
| 362 | out[0] = tmp[0]; |
| 363 | out[1] = tmp[1]; |
| 364 | out[2] = tmp[2]; |
| 365 | out[3] = tmp[3]; |
| 366 | } |
| 367 | |
| 368 | /* smallfelem_expand converts a smallfelem to an felem */ |
| 369 | static void smallfelem_expand(felem out, const smallfelem in) { |
| 370 | out[0] = in[0]; |
| 371 | out[1] = in[1]; |
| 372 | out[2] = in[2]; |
| 373 | out[3] = in[3]; |
| 374 | } |
| 375 | |
| 376 | /* smallfelem_square sets |out| = |small|^2 |
| 377 | * On entry: |
| 378 | * small[i] < 2^64 |
| 379 | * On exit: |
| 380 | * out[i] < 7 * 2^64 < 2^67 */ |
| 381 | static void smallfelem_square(longfelem out, const smallfelem small) { |
| 382 | limb a; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 383 | uint64_t high, low; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 384 | |
| 385 | a = ((uint128_t)small[0]) * small[0]; |
| 386 | low = a; |
| 387 | high = a >> 64; |
| 388 | out[0] = low; |
| 389 | out[1] = high; |
| 390 | |
| 391 | a = ((uint128_t)small[0]) * small[1]; |
| 392 | low = a; |
| 393 | high = a >> 64; |
| 394 | out[1] += low; |
| 395 | out[1] += low; |
| 396 | out[2] = high; |
| 397 | |
| 398 | a = ((uint128_t)small[0]) * small[2]; |
| 399 | low = a; |
| 400 | high = a >> 64; |
| 401 | out[2] += low; |
| 402 | out[2] *= 2; |
| 403 | out[3] = high; |
| 404 | |
| 405 | a = ((uint128_t)small[0]) * small[3]; |
| 406 | low = a; |
| 407 | high = a >> 64; |
| 408 | out[3] += low; |
| 409 | out[4] = high; |
| 410 | |
| 411 | a = ((uint128_t)small[1]) * small[2]; |
| 412 | low = a; |
| 413 | high = a >> 64; |
| 414 | out[3] += low; |
| 415 | out[3] *= 2; |
| 416 | out[4] += high; |
| 417 | |
| 418 | a = ((uint128_t)small[1]) * small[1]; |
| 419 | low = a; |
| 420 | high = a >> 64; |
| 421 | out[2] += low; |
| 422 | out[3] += high; |
| 423 | |
| 424 | a = ((uint128_t)small[1]) * small[3]; |
| 425 | low = a; |
| 426 | high = a >> 64; |
| 427 | out[4] += low; |
| 428 | out[4] *= 2; |
| 429 | out[5] = high; |
| 430 | |
| 431 | a = ((uint128_t)small[2]) * small[3]; |
| 432 | low = a; |
| 433 | high = a >> 64; |
| 434 | out[5] += low; |
| 435 | out[5] *= 2; |
| 436 | out[6] = high; |
| 437 | out[6] += high; |
| 438 | |
| 439 | a = ((uint128_t)small[2]) * small[2]; |
| 440 | low = a; |
| 441 | high = a >> 64; |
| 442 | out[4] += low; |
| 443 | out[5] += high; |
| 444 | |
| 445 | a = ((uint128_t)small[3]) * small[3]; |
| 446 | low = a; |
| 447 | high = a >> 64; |
| 448 | out[6] += low; |
| 449 | out[7] = high; |
| 450 | } |
| 451 | |
| 452 | /*felem_square sets |out| = |in|^2 |
| 453 | * On entry: |
| 454 | * in[i] < 2^109 |
| 455 | * On exit: |
| 456 | * out[i] < 7 * 2^64 < 2^67. */ |
| 457 | static void felem_square(longfelem out, const felem in) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 458 | uint64_t small[4]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 459 | felem_shrink(small, in); |
| 460 | smallfelem_square(out, small); |
| 461 | } |
| 462 | |
| 463 | /* smallfelem_mul sets |out| = |small1| * |small2| |
| 464 | * On entry: |
| 465 | * small1[i] < 2^64 |
| 466 | * small2[i] < 2^64 |
| 467 | * On exit: |
| 468 | * out[i] < 7 * 2^64 < 2^67. */ |
| 469 | static void smallfelem_mul(longfelem out, const smallfelem small1, |
| 470 | const smallfelem small2) { |
| 471 | limb a; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 472 | uint64_t high, low; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 473 | |
| 474 | a = ((uint128_t)small1[0]) * small2[0]; |
| 475 | low = a; |
| 476 | high = a >> 64; |
| 477 | out[0] = low; |
| 478 | out[1] = high; |
| 479 | |
| 480 | a = ((uint128_t)small1[0]) * small2[1]; |
| 481 | low = a; |
| 482 | high = a >> 64; |
| 483 | out[1] += low; |
| 484 | out[2] = high; |
| 485 | |
| 486 | a = ((uint128_t)small1[1]) * small2[0]; |
| 487 | low = a; |
| 488 | high = a >> 64; |
| 489 | out[1] += low; |
| 490 | out[2] += high; |
| 491 | |
| 492 | a = ((uint128_t)small1[0]) * small2[2]; |
| 493 | low = a; |
| 494 | high = a >> 64; |
| 495 | out[2] += low; |
| 496 | out[3] = high; |
| 497 | |
| 498 | a = ((uint128_t)small1[1]) * small2[1]; |
| 499 | low = a; |
| 500 | high = a >> 64; |
| 501 | out[2] += low; |
| 502 | out[3] += high; |
| 503 | |
| 504 | a = ((uint128_t)small1[2]) * small2[0]; |
| 505 | low = a; |
| 506 | high = a >> 64; |
| 507 | out[2] += low; |
| 508 | out[3] += high; |
| 509 | |
| 510 | a = ((uint128_t)small1[0]) * small2[3]; |
| 511 | low = a; |
| 512 | high = a >> 64; |
| 513 | out[3] += low; |
| 514 | out[4] = high; |
| 515 | |
| 516 | a = ((uint128_t)small1[1]) * small2[2]; |
| 517 | low = a; |
| 518 | high = a >> 64; |
| 519 | out[3] += low; |
| 520 | out[4] += high; |
| 521 | |
| 522 | a = ((uint128_t)small1[2]) * small2[1]; |
| 523 | low = a; |
| 524 | high = a >> 64; |
| 525 | out[3] += low; |
| 526 | out[4] += high; |
| 527 | |
| 528 | a = ((uint128_t)small1[3]) * small2[0]; |
| 529 | low = a; |
| 530 | high = a >> 64; |
| 531 | out[3] += low; |
| 532 | out[4] += high; |
| 533 | |
| 534 | a = ((uint128_t)small1[1]) * small2[3]; |
| 535 | low = a; |
| 536 | high = a >> 64; |
| 537 | out[4] += low; |
| 538 | out[5] = high; |
| 539 | |
| 540 | a = ((uint128_t)small1[2]) * small2[2]; |
| 541 | low = a; |
| 542 | high = a >> 64; |
| 543 | out[4] += low; |
| 544 | out[5] += high; |
| 545 | |
| 546 | a = ((uint128_t)small1[3]) * small2[1]; |
| 547 | low = a; |
| 548 | high = a >> 64; |
| 549 | out[4] += low; |
| 550 | out[5] += high; |
| 551 | |
| 552 | a = ((uint128_t)small1[2]) * small2[3]; |
| 553 | low = a; |
| 554 | high = a >> 64; |
| 555 | out[5] += low; |
| 556 | out[6] = high; |
| 557 | |
| 558 | a = ((uint128_t)small1[3]) * small2[2]; |
| 559 | low = a; |
| 560 | high = a >> 64; |
| 561 | out[5] += low; |
| 562 | out[6] += high; |
| 563 | |
| 564 | a = ((uint128_t)small1[3]) * small2[3]; |
| 565 | low = a; |
| 566 | high = a >> 64; |
| 567 | out[6] += low; |
| 568 | out[7] = high; |
| 569 | } |
| 570 | |
| 571 | /* felem_mul sets |out| = |in1| * |in2| |
| 572 | * On entry: |
| 573 | * in1[i] < 2^109 |
| 574 | * in2[i] < 2^109 |
| 575 | * On exit: |
| 576 | * out[i] < 7 * 2^64 < 2^67 */ |
| 577 | static void felem_mul(longfelem out, const felem in1, const felem in2) { |
| 578 | smallfelem small1, small2; |
| 579 | felem_shrink(small1, in1); |
| 580 | felem_shrink(small2, in2); |
| 581 | smallfelem_mul(out, small1, small2); |
| 582 | } |
| 583 | |
| 584 | /* felem_small_mul sets |out| = |small1| * |in2| |
| 585 | * On entry: |
| 586 | * small1[i] < 2^64 |
| 587 | * in2[i] < 2^109 |
| 588 | * On exit: |
| 589 | * out[i] < 7 * 2^64 < 2^67 */ |
| 590 | static void felem_small_mul(longfelem out, const smallfelem small1, |
| 591 | const felem in2) { |
| 592 | smallfelem small2; |
| 593 | felem_shrink(small2, in2); |
| 594 | smallfelem_mul(out, small1, small2); |
| 595 | } |
| 596 | |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 597 | #define two100m36m4 ((((limb)1) << 100) - (((limb)1) << 36) - (((limb)1) << 4)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 598 | #define two100 (((limb)1) << 100) |
David Benjamin | 95add82 | 2016-10-19 01:09:12 -0400 | [diff] [blame] | 599 | #define two100m36p4 ((((limb)1) << 100) - (((limb)1) << 36) + (((limb)1) << 4)) |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 600 | |
| 601 | /* zero100 is 0 mod p */ |
| 602 | static const felem zero100 = {two100m36m4, two100, two100m36p4, two100m36p4}; |
| 603 | |
| 604 | /* Internal function for the different flavours of felem_reduce. |
| 605 | * felem_reduce_ reduces the higher coefficients in[4]-in[7]. |
| 606 | * On entry: |
| 607 | * out[0] >= in[6] + 2^32*in[6] + in[7] + 2^32*in[7] |
| 608 | * out[1] >= in[7] + 2^32*in[4] |
| 609 | * out[2] >= in[5] + 2^32*in[5] |
| 610 | * out[3] >= in[4] + 2^32*in[5] + 2^32*in[6] |
| 611 | * On exit: |
| 612 | * out[0] <= out[0] + in[4] + 2^32*in[5] |
| 613 | * out[1] <= out[1] + in[5] + 2^33*in[6] |
| 614 | * out[2] <= out[2] + in[7] + 2*in[6] + 2^33*in[7] |
| 615 | * out[3] <= out[3] + 2^32*in[4] + 3*in[7] */ |
| 616 | static void felem_reduce_(felem out, const longfelem in) { |
| 617 | int128_t c; |
| 618 | /* combine common terms from below */ |
| 619 | c = in[4] + (in[5] << 32); |
| 620 | out[0] += c; |
| 621 | out[3] -= c; |
| 622 | |
| 623 | c = in[5] - in[7]; |
| 624 | out[1] += c; |
| 625 | out[2] -= c; |
| 626 | |
| 627 | /* the remaining terms */ |
| 628 | /* 256: [(0,1),(96,-1),(192,-1),(224,1)] */ |
| 629 | out[1] -= (in[4] << 32); |
| 630 | out[3] += (in[4] << 32); |
| 631 | |
| 632 | /* 320: [(32,1),(64,1),(128,-1),(160,-1),(224,-1)] */ |
| 633 | out[2] -= (in[5] << 32); |
| 634 | |
| 635 | /* 384: [(0,-1),(32,-1),(96,2),(128,2),(224,-1)] */ |
| 636 | out[0] -= in[6]; |
| 637 | out[0] -= (in[6] << 32); |
| 638 | out[1] += (in[6] << 33); |
| 639 | out[2] += (in[6] * 2); |
| 640 | out[3] -= (in[6] << 32); |
| 641 | |
| 642 | /* 448: [(0,-1),(32,-1),(64,-1),(128,1),(160,2),(192,3)] */ |
| 643 | out[0] -= in[7]; |
| 644 | out[0] -= (in[7] << 32); |
| 645 | out[2] += (in[7] << 33); |
| 646 | out[3] += (in[7] * 3); |
| 647 | } |
| 648 | |
| 649 | /* felem_reduce converts a longfelem into an felem. |
| 650 | * To be called directly after felem_square or felem_mul. |
| 651 | * On entry: |
| 652 | * in[0] < 2^64, in[1] < 3*2^64, in[2] < 5*2^64, in[3] < 7*2^64 |
| 653 | * in[4] < 7*2^64, in[5] < 5*2^64, in[6] < 3*2^64, in[7] < 2*64 |
| 654 | * On exit: |
| 655 | * out[i] < 2^101 */ |
| 656 | static void felem_reduce(felem out, const longfelem in) { |
| 657 | out[0] = zero100[0] + in[0]; |
| 658 | out[1] = zero100[1] + in[1]; |
| 659 | out[2] = zero100[2] + in[2]; |
| 660 | out[3] = zero100[3] + in[3]; |
| 661 | |
| 662 | felem_reduce_(out, in); |
| 663 | |
| 664 | /* out[0] > 2^100 - 2^36 - 2^4 - 3*2^64 - 3*2^96 - 2^64 - 2^96 > 0 |
| 665 | * out[1] > 2^100 - 2^64 - 7*2^96 > 0 |
| 666 | * out[2] > 2^100 - 2^36 + 2^4 - 5*2^64 - 5*2^96 > 0 |
| 667 | * out[3] > 2^100 - 2^36 + 2^4 - 7*2^64 - 5*2^96 - 3*2^96 > 0 |
| 668 | * |
| 669 | * out[0] < 2^100 + 2^64 + 7*2^64 + 5*2^96 < 2^101 |
| 670 | * out[1] < 2^100 + 3*2^64 + 5*2^64 + 3*2^97 < 2^101 |
| 671 | * out[2] < 2^100 + 5*2^64 + 2^64 + 3*2^65 + 2^97 < 2^101 |
| 672 | * out[3] < 2^100 + 7*2^64 + 7*2^96 + 3*2^64 < 2^101 */ |
| 673 | } |
| 674 | |
| 675 | /* felem_reduce_zero105 converts a larger longfelem into an felem. |
| 676 | * On entry: |
| 677 | * in[0] < 2^71 |
| 678 | * On exit: |
| 679 | * out[i] < 2^106 */ |
| 680 | static void felem_reduce_zero105(felem out, const longfelem in) { |
| 681 | out[0] = zero105[0] + in[0]; |
| 682 | out[1] = zero105[1] + in[1]; |
| 683 | out[2] = zero105[2] + in[2]; |
| 684 | out[3] = zero105[3] + in[3]; |
| 685 | |
| 686 | felem_reduce_(out, in); |
| 687 | |
| 688 | /* out[0] > 2^105 - 2^41 - 2^9 - 2^71 - 2^103 - 2^71 - 2^103 > 0 |
| 689 | * out[1] > 2^105 - 2^71 - 2^103 > 0 |
| 690 | * out[2] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 > 0 |
| 691 | * out[3] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 - 2^103 > 0 |
| 692 | * |
| 693 | * out[0] < 2^105 + 2^71 + 2^71 + 2^103 < 2^106 |
| 694 | * out[1] < 2^105 + 2^71 + 2^71 + 2^103 < 2^106 |
| 695 | * out[2] < 2^105 + 2^71 + 2^71 + 2^71 + 2^103 < 2^106 |
| 696 | * out[3] < 2^105 + 2^71 + 2^103 + 2^71 < 2^106 */ |
| 697 | } |
| 698 | |
| 699 | /* subtract_u64 sets *result = *result - v and *carry to one if the |
| 700 | * subtraction underflowed. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 701 | static void subtract_u64(uint64_t *result, uint64_t *carry, uint64_t v) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 702 | uint128_t r = *result; |
| 703 | r -= v; |
| 704 | *carry = (r >> 64) & 1; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 705 | *result = (uint64_t)r; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 706 | } |
| 707 | |
| 708 | /* felem_contract converts |in| to its unique, minimal representation. On |
| 709 | * entry: in[i] < 2^109. */ |
| 710 | static void felem_contract(smallfelem out, const felem in) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 711 | uint64_t all_equal_so_far = 0, result = 0; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 712 | |
| 713 | felem_shrink(out, in); |
| 714 | /* small is minimal except that the value might be > p */ |
| 715 | |
| 716 | all_equal_so_far--; |
| 717 | /* We are doing a constant time test if out >= kPrime. We need to compare |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 718 | * each uint64_t, from most-significant to least significant. For each one, if |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 719 | * all words so far have been equal (m is all ones) then a non-equal |
| 720 | * result is the answer. Otherwise we continue. */ |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 721 | for (size_t i = 3; i < 4; i--) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 722 | uint64_t equal; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 723 | uint128_t a = ((uint128_t)kPrime[i]) - out[i]; |
| 724 | /* if out[i] > kPrime[i] then a will underflow and the high 64-bits |
| 725 | * will all be set. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 726 | result |= all_equal_so_far & ((uint64_t)(a >> 64)); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 727 | |
| 728 | /* if kPrime[i] == out[i] then |equal| will be all zeros and the |
| 729 | * decrement will make it all ones. */ |
| 730 | equal = kPrime[i] ^ out[i]; |
| 731 | equal--; |
| 732 | equal &= equal << 32; |
| 733 | equal &= equal << 16; |
| 734 | equal &= equal << 8; |
| 735 | equal &= equal << 4; |
| 736 | equal &= equal << 2; |
| 737 | equal &= equal << 1; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 738 | equal = ((int64_t)equal) >> 63; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 739 | |
| 740 | all_equal_so_far &= equal; |
| 741 | } |
| 742 | |
| 743 | /* if all_equal_so_far is still all ones then the two values are equal |
| 744 | * and so out >= kPrime is true. */ |
| 745 | result |= all_equal_so_far; |
| 746 | |
| 747 | /* if out >= kPrime then we subtract kPrime. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 748 | uint64_t carry; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 749 | subtract_u64(&out[0], &carry, result & kPrime[0]); |
| 750 | subtract_u64(&out[1], &carry, carry); |
| 751 | subtract_u64(&out[2], &carry, carry); |
| 752 | subtract_u64(&out[3], &carry, carry); |
| 753 | |
| 754 | subtract_u64(&out[1], &carry, result & kPrime[1]); |
| 755 | subtract_u64(&out[2], &carry, carry); |
| 756 | subtract_u64(&out[3], &carry, carry); |
| 757 | |
| 758 | subtract_u64(&out[2], &carry, result & kPrime[2]); |
| 759 | subtract_u64(&out[3], &carry, carry); |
| 760 | |
| 761 | subtract_u64(&out[3], &carry, result & kPrime[3]); |
| 762 | } |
| 763 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 764 | /* felem_is_zero returns a limb with all bits set if |in| == 0 (mod p) and 0 |
| 765 | * otherwise. |
| 766 | * On entry: |
| 767 | * small[i] < 2^64 */ |
| 768 | static limb smallfelem_is_zero(const smallfelem small) { |
| 769 | limb result; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 770 | uint64_t is_p; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 771 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 772 | uint64_t is_zero = small[0] | small[1] | small[2] | small[3]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 773 | is_zero--; |
| 774 | is_zero &= is_zero << 32; |
| 775 | is_zero &= is_zero << 16; |
| 776 | is_zero &= is_zero << 8; |
| 777 | is_zero &= is_zero << 4; |
| 778 | is_zero &= is_zero << 2; |
| 779 | is_zero &= is_zero << 1; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 780 | is_zero = ((int64_t)is_zero) >> 63; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 781 | |
| 782 | is_p = (small[0] ^ kPrime[0]) | (small[1] ^ kPrime[1]) | |
| 783 | (small[2] ^ kPrime[2]) | (small[3] ^ kPrime[3]); |
| 784 | is_p--; |
| 785 | is_p &= is_p << 32; |
| 786 | is_p &= is_p << 16; |
| 787 | is_p &= is_p << 8; |
| 788 | is_p &= is_p << 4; |
| 789 | is_p &= is_p << 2; |
| 790 | is_p &= is_p << 1; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 791 | is_p = ((int64_t)is_p) >> 63; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 792 | |
| 793 | is_zero |= is_p; |
| 794 | |
| 795 | result = is_zero; |
| 796 | result |= ((limb)is_zero) << 64; |
| 797 | return result; |
| 798 | } |
| 799 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 800 | /* felem_inv calculates |out| = |in|^{-1} |
| 801 | * |
| 802 | * Based on Fermat's Little Theorem: |
| 803 | * a^p = a (mod p) |
| 804 | * a^{p-1} = 1 (mod p) |
| 805 | * a^{p-2} = a^{-1} (mod p) */ |
| 806 | static void felem_inv(felem out, const felem in) { |
| 807 | felem ftmp, ftmp2; |
| 808 | /* each e_I will hold |in|^{2^I - 1} */ |
| 809 | felem e2, e4, e8, e16, e32, e64; |
| 810 | longfelem tmp; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 811 | |
| 812 | felem_square(tmp, in); |
| 813 | felem_reduce(ftmp, tmp); /* 2^1 */ |
| 814 | felem_mul(tmp, in, ftmp); |
| 815 | felem_reduce(ftmp, tmp); /* 2^2 - 2^0 */ |
| 816 | felem_assign(e2, ftmp); |
| 817 | felem_square(tmp, ftmp); |
| 818 | felem_reduce(ftmp, tmp); /* 2^3 - 2^1 */ |
| 819 | felem_square(tmp, ftmp); |
| 820 | felem_reduce(ftmp, tmp); /* 2^4 - 2^2 */ |
| 821 | felem_mul(tmp, ftmp, e2); |
| 822 | felem_reduce(ftmp, tmp); /* 2^4 - 2^0 */ |
| 823 | felem_assign(e4, ftmp); |
| 824 | felem_square(tmp, ftmp); |
| 825 | felem_reduce(ftmp, tmp); /* 2^5 - 2^1 */ |
| 826 | felem_square(tmp, ftmp); |
| 827 | felem_reduce(ftmp, tmp); /* 2^6 - 2^2 */ |
| 828 | felem_square(tmp, ftmp); |
| 829 | felem_reduce(ftmp, tmp); /* 2^7 - 2^3 */ |
| 830 | felem_square(tmp, ftmp); |
| 831 | felem_reduce(ftmp, tmp); /* 2^8 - 2^4 */ |
| 832 | felem_mul(tmp, ftmp, e4); |
| 833 | felem_reduce(ftmp, tmp); /* 2^8 - 2^0 */ |
| 834 | felem_assign(e8, ftmp); |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 835 | for (size_t i = 0; i < 8; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 836 | felem_square(tmp, ftmp); |
| 837 | felem_reduce(ftmp, tmp); |
| 838 | } /* 2^16 - 2^8 */ |
| 839 | felem_mul(tmp, ftmp, e8); |
| 840 | felem_reduce(ftmp, tmp); /* 2^16 - 2^0 */ |
| 841 | felem_assign(e16, ftmp); |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 842 | for (size_t i = 0; i < 16; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 843 | felem_square(tmp, ftmp); |
| 844 | felem_reduce(ftmp, tmp); |
| 845 | } /* 2^32 - 2^16 */ |
| 846 | felem_mul(tmp, ftmp, e16); |
| 847 | felem_reduce(ftmp, tmp); /* 2^32 - 2^0 */ |
| 848 | felem_assign(e32, ftmp); |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 849 | for (size_t i = 0; i < 32; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 850 | felem_square(tmp, ftmp); |
| 851 | felem_reduce(ftmp, tmp); |
| 852 | } /* 2^64 - 2^32 */ |
| 853 | felem_assign(e64, ftmp); |
| 854 | felem_mul(tmp, ftmp, in); |
| 855 | felem_reduce(ftmp, tmp); /* 2^64 - 2^32 + 2^0 */ |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 856 | for (size_t i = 0; i < 192; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 857 | felem_square(tmp, ftmp); |
| 858 | felem_reduce(ftmp, tmp); |
| 859 | } /* 2^256 - 2^224 + 2^192 */ |
| 860 | |
| 861 | felem_mul(tmp, e64, e32); |
| 862 | felem_reduce(ftmp2, tmp); /* 2^64 - 2^0 */ |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 863 | for (size_t i = 0; i < 16; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 864 | felem_square(tmp, ftmp2); |
| 865 | felem_reduce(ftmp2, tmp); |
| 866 | } /* 2^80 - 2^16 */ |
| 867 | felem_mul(tmp, ftmp2, e16); |
| 868 | felem_reduce(ftmp2, tmp); /* 2^80 - 2^0 */ |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 869 | for (size_t i = 0; i < 8; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 870 | felem_square(tmp, ftmp2); |
| 871 | felem_reduce(ftmp2, tmp); |
| 872 | } /* 2^88 - 2^8 */ |
| 873 | felem_mul(tmp, ftmp2, e8); |
| 874 | felem_reduce(ftmp2, tmp); /* 2^88 - 2^0 */ |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 875 | for (size_t i = 0; i < 4; i++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 876 | felem_square(tmp, ftmp2); |
| 877 | felem_reduce(ftmp2, tmp); |
| 878 | } /* 2^92 - 2^4 */ |
| 879 | felem_mul(tmp, ftmp2, e4); |
| 880 | felem_reduce(ftmp2, tmp); /* 2^92 - 2^0 */ |
| 881 | felem_square(tmp, ftmp2); |
| 882 | felem_reduce(ftmp2, tmp); /* 2^93 - 2^1 */ |
| 883 | felem_square(tmp, ftmp2); |
| 884 | felem_reduce(ftmp2, tmp); /* 2^94 - 2^2 */ |
| 885 | felem_mul(tmp, ftmp2, e2); |
| 886 | felem_reduce(ftmp2, tmp); /* 2^94 - 2^0 */ |
| 887 | felem_square(tmp, ftmp2); |
| 888 | felem_reduce(ftmp2, tmp); /* 2^95 - 2^1 */ |
| 889 | felem_square(tmp, ftmp2); |
| 890 | felem_reduce(ftmp2, tmp); /* 2^96 - 2^2 */ |
| 891 | felem_mul(tmp, ftmp2, in); |
| 892 | felem_reduce(ftmp2, tmp); /* 2^96 - 3 */ |
| 893 | |
| 894 | felem_mul(tmp, ftmp2, ftmp); |
| 895 | felem_reduce(out, tmp); /* 2^256 - 2^224 + 2^192 + 2^96 - 3 */ |
| 896 | } |
| 897 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 898 | /* Group operations |
| 899 | * ---------------- |
| 900 | * |
| 901 | * Building on top of the field operations we have the operations on the |
| 902 | * elliptic curve group itself. Points on the curve are represented in Jacobian |
| 903 | * coordinates. */ |
| 904 | |
| 905 | /* point_double calculates 2*(x_in, y_in, z_in) |
| 906 | * |
| 907 | * The method is taken from: |
| 908 | * http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b |
| 909 | * |
| 910 | * Outputs can equal corresponding inputs, i.e., x_out == x_in is allowed. |
| 911 | * while x_out == y_in is not (maybe this works, but it's not tested). */ |
| 912 | static void point_double(felem x_out, felem y_out, felem z_out, |
| 913 | const felem x_in, const felem y_in, const felem z_in) { |
| 914 | longfelem tmp, tmp2; |
| 915 | felem delta, gamma, beta, alpha, ftmp, ftmp2; |
| 916 | smallfelem small1, small2; |
| 917 | |
| 918 | felem_assign(ftmp, x_in); |
| 919 | /* ftmp[i] < 2^106 */ |
| 920 | felem_assign(ftmp2, x_in); |
| 921 | /* ftmp2[i] < 2^106 */ |
| 922 | |
| 923 | /* delta = z^2 */ |
| 924 | felem_square(tmp, z_in); |
| 925 | felem_reduce(delta, tmp); |
| 926 | /* delta[i] < 2^101 */ |
| 927 | |
| 928 | /* gamma = y^2 */ |
| 929 | felem_square(tmp, y_in); |
| 930 | felem_reduce(gamma, tmp); |
| 931 | /* gamma[i] < 2^101 */ |
| 932 | felem_shrink(small1, gamma); |
| 933 | |
| 934 | /* beta = x*gamma */ |
| 935 | felem_small_mul(tmp, small1, x_in); |
| 936 | felem_reduce(beta, tmp); |
| 937 | /* beta[i] < 2^101 */ |
| 938 | |
| 939 | /* alpha = 3*(x-delta)*(x+delta) */ |
| 940 | felem_diff(ftmp, delta); |
| 941 | /* ftmp[i] < 2^105 + 2^106 < 2^107 */ |
| 942 | felem_sum(ftmp2, delta); |
| 943 | /* ftmp2[i] < 2^105 + 2^106 < 2^107 */ |
| 944 | felem_scalar(ftmp2, 3); |
| 945 | /* ftmp2[i] < 3 * 2^107 < 2^109 */ |
| 946 | felem_mul(tmp, ftmp, ftmp2); |
| 947 | felem_reduce(alpha, tmp); |
| 948 | /* alpha[i] < 2^101 */ |
| 949 | felem_shrink(small2, alpha); |
| 950 | |
| 951 | /* x' = alpha^2 - 8*beta */ |
| 952 | smallfelem_square(tmp, small2); |
| 953 | felem_reduce(x_out, tmp); |
| 954 | felem_assign(ftmp, beta); |
| 955 | felem_scalar(ftmp, 8); |
| 956 | /* ftmp[i] < 8 * 2^101 = 2^104 */ |
| 957 | felem_diff(x_out, ftmp); |
| 958 | /* x_out[i] < 2^105 + 2^101 < 2^106 */ |
| 959 | |
| 960 | /* z' = (y + z)^2 - gamma - delta */ |
| 961 | felem_sum(delta, gamma); |
| 962 | /* delta[i] < 2^101 + 2^101 = 2^102 */ |
| 963 | felem_assign(ftmp, y_in); |
| 964 | felem_sum(ftmp, z_in); |
| 965 | /* ftmp[i] < 2^106 + 2^106 = 2^107 */ |
| 966 | felem_square(tmp, ftmp); |
| 967 | felem_reduce(z_out, tmp); |
| 968 | felem_diff(z_out, delta); |
| 969 | /* z_out[i] < 2^105 + 2^101 < 2^106 */ |
| 970 | |
| 971 | /* y' = alpha*(4*beta - x') - 8*gamma^2 */ |
| 972 | felem_scalar(beta, 4); |
| 973 | /* beta[i] < 4 * 2^101 = 2^103 */ |
| 974 | felem_diff_zero107(beta, x_out); |
| 975 | /* beta[i] < 2^107 + 2^103 < 2^108 */ |
| 976 | felem_small_mul(tmp, small2, beta); |
| 977 | /* tmp[i] < 7 * 2^64 < 2^67 */ |
| 978 | smallfelem_square(tmp2, small1); |
| 979 | /* tmp2[i] < 7 * 2^64 */ |
| 980 | longfelem_scalar(tmp2, 8); |
| 981 | /* tmp2[i] < 8 * 7 * 2^64 = 7 * 2^67 */ |
| 982 | longfelem_diff(tmp, tmp2); |
| 983 | /* tmp[i] < 2^67 + 2^70 + 2^40 < 2^71 */ |
| 984 | felem_reduce_zero105(y_out, tmp); |
| 985 | /* y_out[i] < 2^106 */ |
| 986 | } |
| 987 | |
| 988 | /* point_double_small is the same as point_double, except that it operates on |
| 989 | * smallfelems. */ |
| 990 | static void point_double_small(smallfelem x_out, smallfelem y_out, |
| 991 | smallfelem z_out, const smallfelem x_in, |
| 992 | const smallfelem y_in, const smallfelem z_in) { |
| 993 | felem felem_x_out, felem_y_out, felem_z_out; |
| 994 | felem felem_x_in, felem_y_in, felem_z_in; |
| 995 | |
| 996 | smallfelem_expand(felem_x_in, x_in); |
| 997 | smallfelem_expand(felem_y_in, y_in); |
| 998 | smallfelem_expand(felem_z_in, z_in); |
| 999 | point_double(felem_x_out, felem_y_out, felem_z_out, felem_x_in, felem_y_in, |
| 1000 | felem_z_in); |
| 1001 | felem_shrink(x_out, felem_x_out); |
| 1002 | felem_shrink(y_out, felem_y_out); |
| 1003 | felem_shrink(z_out, felem_z_out); |
| 1004 | } |
| 1005 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1006 | /* p256_copy_conditional copies in to out iff mask is all ones. */ |
| 1007 | static void p256_copy_conditional(felem out, const felem in, limb mask) { |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 1008 | for (size_t i = 0; i < NLIMBS; ++i) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1009 | const limb tmp = mask & (in[i] ^ out[i]); |
| 1010 | out[i] ^= tmp; |
| 1011 | } |
| 1012 | } |
| 1013 | |
| 1014 | /* copy_small_conditional copies in to out iff mask is all ones. */ |
| 1015 | static void copy_small_conditional(felem out, const smallfelem in, limb mask) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1016 | const uint64_t mask64 = mask; |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 1017 | for (size_t i = 0; i < NLIMBS; ++i) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1018 | out[i] = ((limb)(in[i] & mask64)) | (out[i] & ~mask); |
| 1019 | } |
| 1020 | } |
| 1021 | |
| 1022 | /* point_add calcuates (x1, y1, z1) + (x2, y2, z2) |
| 1023 | * |
| 1024 | * The method is taken from: |
| 1025 | * http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl, |
| 1026 | * adapted for mixed addition (z2 = 1, or z2 = 0 for the point at infinity). |
| 1027 | * |
| 1028 | * This function includes a branch for checking whether the two input points |
| 1029 | * are equal, (while not equal to the point at infinity). This case never |
| 1030 | * happens during single point multiplication, so there is no timing leak for |
| 1031 | * ECDH or ECDSA signing. */ |
| 1032 | static void point_add(felem x3, felem y3, felem z3, const felem x1, |
| 1033 | const felem y1, const felem z1, const int mixed, |
| 1034 | const smallfelem x2, const smallfelem y2, |
| 1035 | const smallfelem z2) { |
| 1036 | felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, ftmp6, x_out, y_out, z_out; |
| 1037 | longfelem tmp, tmp2; |
| 1038 | smallfelem small1, small2, small3, small4, small5; |
| 1039 | limb x_equal, y_equal, z1_is_zero, z2_is_zero; |
| 1040 | |
| 1041 | felem_shrink(small3, z1); |
| 1042 | |
| 1043 | z1_is_zero = smallfelem_is_zero(small3); |
| 1044 | z2_is_zero = smallfelem_is_zero(z2); |
| 1045 | |
| 1046 | /* ftmp = z1z1 = z1**2 */ |
| 1047 | smallfelem_square(tmp, small3); |
| 1048 | felem_reduce(ftmp, tmp); |
| 1049 | /* ftmp[i] < 2^101 */ |
| 1050 | felem_shrink(small1, ftmp); |
| 1051 | |
| 1052 | if (!mixed) { |
| 1053 | /* ftmp2 = z2z2 = z2**2 */ |
| 1054 | smallfelem_square(tmp, z2); |
| 1055 | felem_reduce(ftmp2, tmp); |
| 1056 | /* ftmp2[i] < 2^101 */ |
| 1057 | felem_shrink(small2, ftmp2); |
| 1058 | |
| 1059 | felem_shrink(small5, x1); |
| 1060 | |
| 1061 | /* u1 = ftmp3 = x1*z2z2 */ |
| 1062 | smallfelem_mul(tmp, small5, small2); |
| 1063 | felem_reduce(ftmp3, tmp); |
| 1064 | /* ftmp3[i] < 2^101 */ |
| 1065 | |
| 1066 | /* ftmp5 = z1 + z2 */ |
| 1067 | felem_assign(ftmp5, z1); |
| 1068 | felem_small_sum(ftmp5, z2); |
| 1069 | /* ftmp5[i] < 2^107 */ |
| 1070 | |
| 1071 | /* ftmp5 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2 */ |
| 1072 | felem_square(tmp, ftmp5); |
| 1073 | felem_reduce(ftmp5, tmp); |
| 1074 | /* ftmp2 = z2z2 + z1z1 */ |
| 1075 | felem_sum(ftmp2, ftmp); |
| 1076 | /* ftmp2[i] < 2^101 + 2^101 = 2^102 */ |
| 1077 | felem_diff(ftmp5, ftmp2); |
| 1078 | /* ftmp5[i] < 2^105 + 2^101 < 2^106 */ |
| 1079 | |
| 1080 | /* ftmp2 = z2 * z2z2 */ |
| 1081 | smallfelem_mul(tmp, small2, z2); |
| 1082 | felem_reduce(ftmp2, tmp); |
| 1083 | |
| 1084 | /* s1 = ftmp2 = y1 * z2**3 */ |
| 1085 | felem_mul(tmp, y1, ftmp2); |
| 1086 | felem_reduce(ftmp6, tmp); |
| 1087 | /* ftmp6[i] < 2^101 */ |
| 1088 | } else { |
| 1089 | /* We'll assume z2 = 1 (special case z2 = 0 is handled later). */ |
| 1090 | |
| 1091 | /* u1 = ftmp3 = x1*z2z2 */ |
| 1092 | felem_assign(ftmp3, x1); |
| 1093 | /* ftmp3[i] < 2^106 */ |
| 1094 | |
| 1095 | /* ftmp5 = 2z1z2 */ |
| 1096 | felem_assign(ftmp5, z1); |
| 1097 | felem_scalar(ftmp5, 2); |
| 1098 | /* ftmp5[i] < 2*2^106 = 2^107 */ |
| 1099 | |
| 1100 | /* s1 = ftmp2 = y1 * z2**3 */ |
| 1101 | felem_assign(ftmp6, y1); |
| 1102 | /* ftmp6[i] < 2^106 */ |
| 1103 | } |
| 1104 | |
| 1105 | /* u2 = x2*z1z1 */ |
| 1106 | smallfelem_mul(tmp, x2, small1); |
| 1107 | felem_reduce(ftmp4, tmp); |
| 1108 | |
| 1109 | /* h = ftmp4 = u2 - u1 */ |
| 1110 | felem_diff_zero107(ftmp4, ftmp3); |
| 1111 | /* ftmp4[i] < 2^107 + 2^101 < 2^108 */ |
| 1112 | felem_shrink(small4, ftmp4); |
| 1113 | |
| 1114 | x_equal = smallfelem_is_zero(small4); |
| 1115 | |
| 1116 | /* z_out = ftmp5 * h */ |
| 1117 | felem_small_mul(tmp, small4, ftmp5); |
| 1118 | felem_reduce(z_out, tmp); |
| 1119 | /* z_out[i] < 2^101 */ |
| 1120 | |
| 1121 | /* ftmp = z1 * z1z1 */ |
| 1122 | smallfelem_mul(tmp, small1, small3); |
| 1123 | felem_reduce(ftmp, tmp); |
| 1124 | |
| 1125 | /* s2 = tmp = y2 * z1**3 */ |
| 1126 | felem_small_mul(tmp, y2, ftmp); |
| 1127 | felem_reduce(ftmp5, tmp); |
| 1128 | |
| 1129 | /* r = ftmp5 = (s2 - s1)*2 */ |
| 1130 | felem_diff_zero107(ftmp5, ftmp6); |
| 1131 | /* ftmp5[i] < 2^107 + 2^107 = 2^108 */ |
| 1132 | felem_scalar(ftmp5, 2); |
| 1133 | /* ftmp5[i] < 2^109 */ |
| 1134 | felem_shrink(small1, ftmp5); |
| 1135 | y_equal = smallfelem_is_zero(small1); |
| 1136 | |
| 1137 | if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { |
| 1138 | point_double(x3, y3, z3, x1, y1, z1); |
| 1139 | return; |
| 1140 | } |
| 1141 | |
| 1142 | /* I = ftmp = (2h)**2 */ |
| 1143 | felem_assign(ftmp, ftmp4); |
| 1144 | felem_scalar(ftmp, 2); |
| 1145 | /* ftmp[i] < 2*2^108 = 2^109 */ |
| 1146 | felem_square(tmp, ftmp); |
| 1147 | felem_reduce(ftmp, tmp); |
| 1148 | |
| 1149 | /* J = ftmp2 = h * I */ |
| 1150 | felem_mul(tmp, ftmp4, ftmp); |
| 1151 | felem_reduce(ftmp2, tmp); |
| 1152 | |
| 1153 | /* V = ftmp4 = U1 * I */ |
| 1154 | felem_mul(tmp, ftmp3, ftmp); |
| 1155 | felem_reduce(ftmp4, tmp); |
| 1156 | |
| 1157 | /* x_out = r**2 - J - 2V */ |
| 1158 | smallfelem_square(tmp, small1); |
| 1159 | felem_reduce(x_out, tmp); |
| 1160 | felem_assign(ftmp3, ftmp4); |
| 1161 | felem_scalar(ftmp4, 2); |
| 1162 | felem_sum(ftmp4, ftmp2); |
| 1163 | /* ftmp4[i] < 2*2^101 + 2^101 < 2^103 */ |
| 1164 | felem_diff(x_out, ftmp4); |
| 1165 | /* x_out[i] < 2^105 + 2^101 */ |
| 1166 | |
| 1167 | /* y_out = r(V-x_out) - 2 * s1 * J */ |
| 1168 | felem_diff_zero107(ftmp3, x_out); |
| 1169 | /* ftmp3[i] < 2^107 + 2^101 < 2^108 */ |
| 1170 | felem_small_mul(tmp, small1, ftmp3); |
| 1171 | felem_mul(tmp2, ftmp6, ftmp2); |
| 1172 | longfelem_scalar(tmp2, 2); |
| 1173 | /* tmp2[i] < 2*2^67 = 2^68 */ |
| 1174 | longfelem_diff(tmp, tmp2); |
| 1175 | /* tmp[i] < 2^67 + 2^70 + 2^40 < 2^71 */ |
| 1176 | felem_reduce_zero105(y_out, tmp); |
| 1177 | /* y_out[i] < 2^106 */ |
| 1178 | |
| 1179 | copy_small_conditional(x_out, x2, z1_is_zero); |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1180 | p256_copy_conditional(x_out, x1, z2_is_zero); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1181 | copy_small_conditional(y_out, y2, z1_is_zero); |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1182 | p256_copy_conditional(y_out, y1, z2_is_zero); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1183 | copy_small_conditional(z_out, z2, z1_is_zero); |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1184 | p256_copy_conditional(z_out, z1, z2_is_zero); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1185 | felem_assign(x3, x_out); |
| 1186 | felem_assign(y3, y_out); |
| 1187 | felem_assign(z3, z_out); |
| 1188 | } |
| 1189 | |
| 1190 | /* point_add_small is the same as point_add, except that it operates on |
| 1191 | * smallfelems. */ |
| 1192 | static void point_add_small(smallfelem x3, smallfelem y3, smallfelem z3, |
| 1193 | smallfelem x1, smallfelem y1, smallfelem z1, |
| 1194 | smallfelem x2, smallfelem y2, smallfelem z2) { |
| 1195 | felem felem_x3, felem_y3, felem_z3; |
| 1196 | felem felem_x1, felem_y1, felem_z1; |
| 1197 | smallfelem_expand(felem_x1, x1); |
| 1198 | smallfelem_expand(felem_y1, y1); |
| 1199 | smallfelem_expand(felem_z1, z1); |
| 1200 | point_add(felem_x3, felem_y3, felem_z3, felem_x1, felem_y1, felem_z1, 0, x2, |
| 1201 | y2, z2); |
| 1202 | felem_shrink(x3, felem_x3); |
| 1203 | felem_shrink(y3, felem_y3); |
| 1204 | felem_shrink(z3, felem_z3); |
| 1205 | } |
| 1206 | |
| 1207 | /* Base point pre computation |
| 1208 | * -------------------------- |
| 1209 | * |
| 1210 | * Two different sorts of precomputed tables are used in the following code. |
| 1211 | * Each contain various points on the curve, where each point is three field |
| 1212 | * elements (x, y, z). |
| 1213 | * |
| 1214 | * For the base point table, z is usually 1 (0 for the point at infinity). |
| 1215 | * This table has 2 * 16 elements, starting with the following: |
| 1216 | * index | bits | point |
| 1217 | * ------+---------+------------------------------ |
| 1218 | * 0 | 0 0 0 0 | 0G |
| 1219 | * 1 | 0 0 0 1 | 1G |
| 1220 | * 2 | 0 0 1 0 | 2^64G |
| 1221 | * 3 | 0 0 1 1 | (2^64 + 1)G |
| 1222 | * 4 | 0 1 0 0 | 2^128G |
| 1223 | * 5 | 0 1 0 1 | (2^128 + 1)G |
| 1224 | * 6 | 0 1 1 0 | (2^128 + 2^64)G |
| 1225 | * 7 | 0 1 1 1 | (2^128 + 2^64 + 1)G |
| 1226 | * 8 | 1 0 0 0 | 2^192G |
| 1227 | * 9 | 1 0 0 1 | (2^192 + 1)G |
| 1228 | * 10 | 1 0 1 0 | (2^192 + 2^64)G |
| 1229 | * 11 | 1 0 1 1 | (2^192 + 2^64 + 1)G |
| 1230 | * 12 | 1 1 0 0 | (2^192 + 2^128)G |
| 1231 | * 13 | 1 1 0 1 | (2^192 + 2^128 + 1)G |
| 1232 | * 14 | 1 1 1 0 | (2^192 + 2^128 + 2^64)G |
| 1233 | * 15 | 1 1 1 1 | (2^192 + 2^128 + 2^64 + 1)G |
| 1234 | * followed by a copy of this with each element multiplied by 2^32. |
| 1235 | * |
| 1236 | * The reason for this is so that we can clock bits into four different |
| 1237 | * locations when doing simple scalar multiplies against the base point, |
| 1238 | * and then another four locations using the second 16 elements. |
| 1239 | * |
| 1240 | * Tables for other points have table[i] = iG for i in 0 .. 16. */ |
| 1241 | |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 1242 | /* g_pre_comp is the table of precomputed base points */ |
| 1243 | static const smallfelem g_pre_comp[2][16][3] = { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1244 | {{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}, |
| 1245 | {{0xf4a13945d898c296, 0x77037d812deb33a0, 0xf8bce6e563a440f2, |
| 1246 | 0x6b17d1f2e12c4247}, |
| 1247 | {0xcbb6406837bf51f5, 0x2bce33576b315ece, 0x8ee7eb4a7c0f9e16, |
| 1248 | 0x4fe342e2fe1a7f9b}, |
| 1249 | {1, 0, 0, 0}}, |
| 1250 | {{0x90e75cb48e14db63, 0x29493baaad651f7e, 0x8492592e326e25de, |
| 1251 | 0x0fa822bc2811aaa5}, |
| 1252 | {0xe41124545f462ee7, 0x34b1a65050fe82f5, 0x6f4ad4bcb3df188b, |
| 1253 | 0xbff44ae8f5dba80d}, |
| 1254 | {1, 0, 0, 0}}, |
| 1255 | {{0x93391ce2097992af, 0xe96c98fd0d35f1fa, 0xb257c0de95e02789, |
| 1256 | 0x300a4bbc89d6726f}, |
| 1257 | {0xaa54a291c08127a0, 0x5bb1eeada9d806a5, 0x7f1ddb25ff1e3c6f, |
| 1258 | 0x72aac7e0d09b4644}, |
| 1259 | {1, 0, 0, 0}}, |
| 1260 | {{0x57c84fc9d789bd85, 0xfc35ff7dc297eac3, 0xfb982fd588c6766e, |
| 1261 | 0x447d739beedb5e67}, |
| 1262 | {0x0c7e33c972e25b32, 0x3d349b95a7fae500, 0xe12e9d953a4aaff7, |
| 1263 | 0x2d4825ab834131ee}, |
| 1264 | {1, 0, 0, 0}}, |
| 1265 | {{0x13949c932a1d367f, 0xef7fbd2b1a0a11b7, 0xddc6068bb91dfc60, |
| 1266 | 0xef9519328a9c72ff}, |
| 1267 | {0x196035a77376d8a8, 0x23183b0895ca1740, 0xc1ee9807022c219c, |
| 1268 | 0x611e9fc37dbb2c9b}, |
| 1269 | {1, 0, 0, 0}}, |
| 1270 | {{0xcae2b1920b57f4bc, 0x2936df5ec6c9bc36, 0x7dea6482e11238bf, |
| 1271 | 0x550663797b51f5d8}, |
| 1272 | {0x44ffe216348a964c, 0x9fb3d576dbdefbe1, 0x0afa40018d9d50e5, |
| 1273 | 0x157164848aecb851}, |
| 1274 | {1, 0, 0, 0}}, |
| 1275 | {{0xe48ecafffc5cde01, 0x7ccd84e70d715f26, 0xa2e8f483f43e4391, |
| 1276 | 0xeb5d7745b21141ea}, |
| 1277 | {0xcac917e2731a3479, 0x85f22cfe2844b645, 0x0990e6a158006cee, |
| 1278 | 0xeafd72ebdbecc17b}, |
| 1279 | {1, 0, 0, 0}}, |
| 1280 | {{0x6cf20ffb313728be, 0x96439591a3c6b94a, 0x2736ff8344315fc5, |
| 1281 | 0xa6d39677a7849276}, |
| 1282 | {0xf2bab833c357f5f4, 0x824a920c2284059b, 0x66b8babd2d27ecdf, |
| 1283 | 0x674f84749b0b8816}, |
| 1284 | {1, 0, 0, 0}}, |
| 1285 | {{0x2df48c04677c8a3e, 0x74e02f080203a56b, 0x31855f7db8c7fedb, |
| 1286 | 0x4e769e7672c9ddad}, |
| 1287 | {0xa4c36165b824bbb0, 0xfb9ae16f3b9122a5, 0x1ec0057206947281, |
| 1288 | 0x42b99082de830663}, |
| 1289 | {1, 0, 0, 0}}, |
| 1290 | {{0x6ef95150dda868b9, 0xd1f89e799c0ce131, 0x7fdc1ca008a1c478, |
| 1291 | 0x78878ef61c6ce04d}, |
| 1292 | {0x9c62b9121fe0d976, 0x6ace570ebde08d4f, 0xde53142c12309def, |
| 1293 | 0xb6cb3f5d7b72c321}, |
| 1294 | {1, 0, 0, 0}}, |
| 1295 | {{0x7f991ed2c31a3573, 0x5b82dd5bd54fb496, 0x595c5220812ffcae, |
| 1296 | 0x0c88bc4d716b1287}, |
| 1297 | {0x3a57bf635f48aca8, 0x7c8181f4df2564f3, 0x18d1b5b39c04e6aa, |
| 1298 | 0xdd5ddea3f3901dc6}, |
| 1299 | {1, 0, 0, 0}}, |
| 1300 | {{0xe96a79fb3e72ad0c, 0x43a0a28c42ba792f, 0xefe0a423083e49f3, |
| 1301 | 0x68f344af6b317466}, |
| 1302 | {0xcdfe17db3fb24d4a, 0x668bfc2271f5c626, 0x604ed93c24d67ff3, |
| 1303 | 0x31b9c405f8540a20}, |
| 1304 | {1, 0, 0, 0}}, |
| 1305 | {{0xd36b4789a2582e7f, 0x0d1a10144ec39c28, 0x663c62c3edbad7a0, |
| 1306 | 0x4052bf4b6f461db9}, |
| 1307 | {0x235a27c3188d25eb, 0xe724f33999bfcc5b, 0x862be6bd71d70cc8, |
| 1308 | 0xfecf4d5190b0fc61}, |
| 1309 | {1, 0, 0, 0}}, |
| 1310 | {{0x74346c10a1d4cfac, 0xafdf5cc08526a7a4, 0x123202a8f62bff7a, |
| 1311 | 0x1eddbae2c802e41a}, |
| 1312 | {0x8fa0af2dd603f844, 0x36e06b7e4c701917, 0x0c45f45273db33a0, |
| 1313 | 0x43104d86560ebcfc}, |
| 1314 | {1, 0, 0, 0}}, |
| 1315 | {{0x9615b5110d1d78e5, 0x66b0de3225c4744b, 0x0a4a46fb6aaf363a, |
| 1316 | 0xb48e26b484f7a21c}, |
| 1317 | {0x06ebb0f621a01b2d, 0xc004e4048b7b0f98, 0x64131bcdfed6f668, |
| 1318 | 0xfac015404d4d3dab}, |
| 1319 | {1, 0, 0, 0}}}, |
| 1320 | {{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}, |
| 1321 | {{0x3a5a9e22185a5943, 0x1ab919365c65dfb6, 0x21656b32262c71da, |
| 1322 | 0x7fe36b40af22af89}, |
| 1323 | {0xd50d152c699ca101, 0x74b3d5867b8af212, 0x9f09f40407dca6f1, |
| 1324 | 0xe697d45825b63624}, |
| 1325 | {1, 0, 0, 0}}, |
| 1326 | {{0xa84aa9397512218e, 0xe9a521b074ca0141, 0x57880b3a18a2e902, |
| 1327 | 0x4a5b506612a677a6}, |
| 1328 | {0x0beada7a4c4f3840, 0x626db15419e26d9d, 0xc42604fbe1627d40, |
| 1329 | 0xeb13461ceac089f1}, |
| 1330 | {1, 0, 0, 0}}, |
| 1331 | {{0xf9faed0927a43281, 0x5e52c4144103ecbc, 0xc342967aa815c857, |
| 1332 | 0x0781b8291c6a220a}, |
| 1333 | {0x5a8343ceeac55f80, 0x88f80eeee54a05e3, 0x97b2a14f12916434, |
| 1334 | 0x690cde8df0151593}, |
| 1335 | {1, 0, 0, 0}}, |
| 1336 | {{0xaee9c75df7f82f2a, 0x9e4c35874afdf43a, 0xf5622df437371326, |
| 1337 | 0x8a535f566ec73617}, |
| 1338 | {0xc5f9a0ac223094b7, 0xcde533864c8c7669, 0x37e02819085a92bf, |
| 1339 | 0x0455c08468b08bd7}, |
| 1340 | {1, 0, 0, 0}}, |
| 1341 | {{0x0c0a6e2c9477b5d9, 0xf9a4bf62876dc444, 0x5050a949b6cdc279, |
| 1342 | 0x06bada7ab77f8276}, |
| 1343 | {0xc8b4aed1ea48dac9, 0xdebd8a4b7ea1070f, 0x427d49101366eb70, |
| 1344 | 0x5b476dfd0e6cb18a}, |
| 1345 | {1, 0, 0, 0}}, |
| 1346 | {{0x7c5c3e44278c340a, 0x4d54606812d66f3b, 0x29a751b1ae23c5d8, |
| 1347 | 0x3e29864e8a2ec908}, |
| 1348 | {0x142d2a6626dbb850, 0xad1744c4765bd780, 0x1f150e68e322d1ed, |
| 1349 | 0x239b90ea3dc31e7e}, |
| 1350 | {1, 0, 0, 0}}, |
| 1351 | {{0x78c416527a53322a, 0x305dde6709776f8e, 0xdbcab759f8862ed4, |
| 1352 | 0x820f4dd949f72ff7}, |
| 1353 | {0x6cc544a62b5debd4, 0x75be5d937b4e8cc4, 0x1b481b1b215c14d3, |
| 1354 | 0x140406ec783a05ec}, |
| 1355 | {1, 0, 0, 0}}, |
| 1356 | {{0x6a703f10e895df07, 0xfd75f3fa01876bd8, 0xeb5b06e70ce08ffe, |
| 1357 | 0x68f6b8542783dfee}, |
| 1358 | {0x90c76f8a78712655, 0xcf5293d2f310bf7f, 0xfbc8044dfda45028, |
| 1359 | 0xcbe1feba92e40ce6}, |
| 1360 | {1, 0, 0, 0}}, |
| 1361 | {{0xe998ceea4396e4c1, 0xfc82ef0b6acea274, 0x230f729f2250e927, |
| 1362 | 0xd0b2f94d2f420109}, |
| 1363 | {0x4305adddb38d4966, 0x10b838f8624c3b45, 0x7db2636658954e7a, |
| 1364 | 0x971459828b0719e5}, |
| 1365 | {1, 0, 0, 0}}, |
| 1366 | {{0x4bd6b72623369fc9, 0x57f2929e53d0b876, 0xc2d5cba4f2340687, |
| 1367 | 0x961610004a866aba}, |
| 1368 | {0x49997bcd2e407a5e, 0x69ab197d92ddcb24, 0x2cf1f2438fe5131c, |
| 1369 | 0x7acb9fadcee75e44}, |
| 1370 | {1, 0, 0, 0}}, |
| 1371 | {{0x254e839423d2d4c0, 0xf57f0c917aea685b, 0xa60d880f6f75aaea, |
| 1372 | 0x24eb9acca333bf5b}, |
| 1373 | {0xe3de4ccb1cda5dea, 0xfeef9341c51a6b4f, 0x743125f88bac4c4d, |
| 1374 | 0x69f891c5acd079cc}, |
| 1375 | {1, 0, 0, 0}}, |
| 1376 | {{0xeee44b35702476b5, 0x7ed031a0e45c2258, 0xb422d1e7bd6f8514, |
| 1377 | 0xe51f547c5972a107}, |
| 1378 | {0xa25bcd6fc9cf343d, 0x8ca922ee097c184e, 0xa62f98b3a9fe9a06, |
| 1379 | 0x1c309a2b25bb1387}, |
| 1380 | {1, 0, 0, 0}}, |
| 1381 | {{0x9295dbeb1967c459, 0xb00148833472c98e, 0xc504977708011828, |
| 1382 | 0x20b87b8aa2c4e503}, |
| 1383 | {0x3063175de057c277, 0x1bd539338fe582dd, 0x0d11adef5f69a044, |
| 1384 | 0xf5c6fa49919776be}, |
| 1385 | {1, 0, 0, 0}}, |
| 1386 | {{0x8c944e760fd59e11, 0x3876cba1102fad5f, 0xa454c3fad83faa56, |
| 1387 | 0x1ed7d1b9332010b9}, |
| 1388 | {0xa1011a270024b889, 0x05e4d0dcac0cd344, 0x52b520f0eb6a2a24, |
| 1389 | 0x3a2b03f03217257a}, |
| 1390 | {1, 0, 0, 0}}, |
| 1391 | {{0xf20fc2afdf1d043d, 0xf330240db58d5a62, 0xfc7d229ca0058c3b, |
| 1392 | 0x15fee545c78dd9f6}, |
| 1393 | {0x501e82885bc98cda, 0x41ef80e5d046ac04, 0x557d9f49461210fb, |
| 1394 | 0x4ab5b6b2b8753f81}, |
| 1395 | {1, 0, 0, 0}}}}; |
| 1396 | |
| 1397 | /* select_point selects the |idx|th point from a precomputation table and |
| 1398 | * copies it to out. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1399 | static void select_point(const uint64_t idx, size_t size, |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1400 | const smallfelem pre_comp[/*size*/][3], |
| 1401 | smallfelem out[3]) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1402 | uint64_t *outlimbs = &out[0][0]; |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1403 | OPENSSL_memset(outlimbs, 0, 3 * sizeof(smallfelem)); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1404 | |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 1405 | for (size_t i = 0; i < size; i++) { |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1406 | const uint64_t *inlimbs = (const uint64_t *)&pre_comp[i][0][0]; |
| 1407 | uint64_t mask = i ^ idx; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1408 | mask |= mask >> 4; |
| 1409 | mask |= mask >> 2; |
| 1410 | mask |= mask >> 1; |
| 1411 | mask &= 1; |
| 1412 | mask--; |
David Benjamin | 7c0d06c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 1413 | for (size_t j = 0; j < NLIMBS * 3; j++) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1414 | outlimbs[j] |= inlimbs[j] & mask; |
| 1415 | } |
| 1416 | } |
| 1417 | } |
| 1418 | |
| 1419 | /* get_bit returns the |i|th bit in |in| */ |
| 1420 | static char get_bit(const felem_bytearray in, int i) { |
| 1421 | if (i < 0 || i >= 256) { |
| 1422 | return 0; |
| 1423 | } |
| 1424 | return (in[i >> 3] >> (i & 7)) & 1; |
| 1425 | } |
| 1426 | |
| 1427 | /* Interleaved point multiplication using precomputed point multiples: The |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1428 | * small point multiples 0*P, 1*P, ..., 17*P are in p_pre_comp, the scalar |
| 1429 | * in p_scalar, if non-NULL. If g_scalar is non-NULL, we also add this multiple |
| 1430 | * of the generator, using certain (large) precomputed multiples in g_pre_comp. |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1431 | * Output point (X, Y, Z) is stored in x_out, y_out, z_out. */ |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1432 | static void batch_mul(felem x_out, felem y_out, felem z_out, |
| 1433 | const uint8_t *p_scalar, const uint8_t *g_scalar, |
| 1434 | const smallfelem p_pre_comp[17][3]) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1435 | felem nq[3], ftmp; |
| 1436 | smallfelem tmp[3]; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1437 | uint64_t bits; |
| 1438 | uint8_t sign, digit; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1439 | |
| 1440 | /* set nq to the point at infinity */ |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1441 | OPENSSL_memset(nq, 0, 3 * sizeof(felem)); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1442 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1443 | /* Loop over both scalars msb-to-lsb, interleaving additions of multiples |
| 1444 | * of the generator (two in each of the last 32 rounds) and additions of p |
| 1445 | * (every 5th round). */ |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1446 | |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1447 | int skip = 1; /* save two point operations in the first round */ |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1448 | size_t i = p_scalar != NULL ? 255 : 31; |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1449 | for (;;) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1450 | /* double */ |
| 1451 | if (!skip) { |
| 1452 | point_double(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2]); |
| 1453 | } |
| 1454 | |
| 1455 | /* add multiples of the generator */ |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1456 | if (g_scalar != NULL && i <= 31) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1457 | /* first, look 32 bits upwards */ |
| 1458 | bits = get_bit(g_scalar, i + 224) << 3; |
| 1459 | bits |= get_bit(g_scalar, i + 160) << 2; |
| 1460 | bits |= get_bit(g_scalar, i + 96) << 1; |
| 1461 | bits |= get_bit(g_scalar, i + 32); |
| 1462 | /* select the point to add, in constant time */ |
| 1463 | select_point(bits, 16, g_pre_comp[1], tmp); |
| 1464 | |
| 1465 | if (!skip) { |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1466 | point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1 /* mixed */, |
| 1467 | tmp[0], tmp[1], tmp[2]); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1468 | } else { |
| 1469 | smallfelem_expand(nq[0], tmp[0]); |
| 1470 | smallfelem_expand(nq[1], tmp[1]); |
| 1471 | smallfelem_expand(nq[2], tmp[2]); |
| 1472 | skip = 0; |
| 1473 | } |
| 1474 | |
| 1475 | /* second, look at the current position */ |
| 1476 | bits = get_bit(g_scalar, i + 192) << 3; |
| 1477 | bits |= get_bit(g_scalar, i + 128) << 2; |
| 1478 | bits |= get_bit(g_scalar, i + 64) << 1; |
| 1479 | bits |= get_bit(g_scalar, i); |
| 1480 | /* select the point to add, in constant time */ |
| 1481 | select_point(bits, 16, g_pre_comp[0], tmp); |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1482 | point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1 /* mixed */, tmp[0], |
| 1483 | tmp[1], tmp[2]); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1484 | } |
| 1485 | |
| 1486 | /* do other additions every 5 doublings */ |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1487 | if (p_scalar != NULL && i % 5 == 0) { |
| 1488 | bits = get_bit(p_scalar, i + 4) << 5; |
| 1489 | bits |= get_bit(p_scalar, i + 3) << 4; |
| 1490 | bits |= get_bit(p_scalar, i + 2) << 3; |
| 1491 | bits |= get_bit(p_scalar, i + 1) << 2; |
| 1492 | bits |= get_bit(p_scalar, i) << 1; |
| 1493 | bits |= get_bit(p_scalar, i - 1); |
| 1494 | ec_GFp_nistp_recode_scalar_bits(&sign, &digit, bits); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1495 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1496 | /* select the point to add or subtract, in constant time. */ |
| 1497 | select_point(digit, 17, p_pre_comp, tmp); |
| 1498 | smallfelem_neg(ftmp, tmp[1]); /* (X, -Y, Z) is the negative |
| 1499 | * point */ |
| 1500 | copy_small_conditional(ftmp, tmp[1], (((limb)sign) - 1)); |
| 1501 | felem_contract(tmp[1], ftmp); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1502 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1503 | if (!skip) { |
| 1504 | point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 0 /* mixed */, |
| 1505 | tmp[0], tmp[1], tmp[2]); |
| 1506 | } else { |
| 1507 | smallfelem_expand(nq[0], tmp[0]); |
| 1508 | smallfelem_expand(nq[1], tmp[1]); |
| 1509 | smallfelem_expand(nq[2], tmp[2]); |
| 1510 | skip = 0; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1511 | } |
| 1512 | } |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1513 | |
| 1514 | if (i == 0) { |
| 1515 | break; |
| 1516 | } |
| 1517 | --i; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1518 | } |
| 1519 | felem_assign(x_out, nq[0]); |
| 1520 | felem_assign(y_out, nq[1]); |
| 1521 | felem_assign(z_out, nq[2]); |
| 1522 | } |
| 1523 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1524 | /******************************************************************************/ |
| 1525 | /* |
| 1526 | * OPENSSL EC_METHOD FUNCTIONS |
| 1527 | */ |
| 1528 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1529 | /* Takes the Jacobian coordinates (X, Y, Z) of a point and returns (X', Y') = |
| 1530 | * (X/Z^2, Y/Z^3). */ |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1531 | static int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group, |
| 1532 | const EC_POINT *point, |
| 1533 | BIGNUM *x, BIGNUM *y, |
| 1534 | BN_CTX *ctx) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1535 | felem z1, z2, x_in, y_in; |
| 1536 | smallfelem x_out, y_out; |
| 1537 | longfelem tmp; |
| 1538 | |
| 1539 | if (EC_POINT_is_at_infinity(group, point)) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 1540 | OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1541 | return 0; |
| 1542 | } |
| 1543 | if (!BN_to_felem(x_in, &point->X) || |
| 1544 | !BN_to_felem(y_in, &point->Y) || |
| 1545 | !BN_to_felem(z1, &point->Z)) { |
| 1546 | return 0; |
| 1547 | } |
| 1548 | felem_inv(z2, z1); |
| 1549 | felem_square(tmp, z2); |
| 1550 | felem_reduce(z1, tmp); |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1551 | |
| 1552 | if (x != NULL) { |
| 1553 | felem_mul(tmp, x_in, z1); |
| 1554 | felem_reduce(x_in, tmp); |
| 1555 | felem_contract(x_out, x_in); |
| 1556 | if (!smallfelem_to_BN(x, x_out)) { |
| 1557 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
| 1558 | return 0; |
| 1559 | } |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1560 | } |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1561 | |
| 1562 | if (y != NULL) { |
| 1563 | felem_mul(tmp, z1, z2); |
| 1564 | felem_reduce(z1, tmp); |
| 1565 | felem_mul(tmp, y_in, z1); |
| 1566 | felem_reduce(y_in, tmp); |
| 1567 | felem_contract(y_out, y_in); |
| 1568 | if (!smallfelem_to_BN(y, y_out)) { |
| 1569 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
| 1570 | return 0; |
| 1571 | } |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1572 | } |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1573 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1574 | return 1; |
| 1575 | } |
| 1576 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1577 | static int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, |
| 1578 | const BIGNUM *g_scalar, const EC_POINT *p, |
| 1579 | const BIGNUM *p_scalar, BN_CTX *ctx) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1580 | int ret = 0; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1581 | BN_CTX *new_ctx = NULL; |
| 1582 | BIGNUM *x, *y, *z, *tmp_scalar; |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1583 | felem_bytearray g_secret, p_secret; |
| 1584 | smallfelem p_pre_comp[17][3]; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1585 | felem_bytearray tmp; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1586 | smallfelem x_in, y_in, z_in; |
| 1587 | felem x_out, y_out, z_out; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1588 | |
| 1589 | if (ctx == NULL) { |
| 1590 | ctx = new_ctx = BN_CTX_new(); |
| 1591 | if (ctx == NULL) { |
| 1592 | return 0; |
| 1593 | } |
| 1594 | } |
| 1595 | |
| 1596 | BN_CTX_start(ctx); |
| 1597 | if ((x = BN_CTX_get(ctx)) == NULL || |
| 1598 | (y = BN_CTX_get(ctx)) == NULL || |
| 1599 | (z = BN_CTX_get(ctx)) == NULL || |
| 1600 | (tmp_scalar = BN_CTX_get(ctx)) == NULL) { |
| 1601 | goto err; |
| 1602 | } |
| 1603 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1604 | if (p != NULL && p_scalar != NULL) { |
| 1605 | /* We treat NULL scalars as 0, and NULL points as points at infinity, i.e., |
| 1606 | * they contribute nothing to the linear combination. */ |
| 1607 | OPENSSL_memset(&p_secret, 0, sizeof(p_secret)); |
| 1608 | OPENSSL_memset(&p_pre_comp, 0, sizeof(p_pre_comp)); |
| 1609 | size_t num_bytes; |
| 1610 | /* Reduce g_scalar to 0 <= g_scalar < 2^256. */ |
| 1611 | if (BN_num_bits(p_scalar) > 256 || BN_is_negative(p_scalar)) { |
| 1612 | /* This is an unusual input, and we don't guarantee constant-timeness. */ |
| 1613 | if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) { |
| 1614 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
| 1615 | goto err; |
| 1616 | } |
| 1617 | num_bytes = BN_bn2bin(tmp_scalar, tmp); |
| 1618 | } else { |
| 1619 | num_bytes = BN_bn2bin(p_scalar, tmp); |
| 1620 | } |
| 1621 | flip_endian(p_secret, tmp, num_bytes); |
| 1622 | /* Precompute multiples. */ |
| 1623 | if (!BN_to_felem(x_out, &p->X) || |
| 1624 | !BN_to_felem(y_out, &p->Y) || |
| 1625 | !BN_to_felem(z_out, &p->Z)) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1626 | goto err; |
| 1627 | } |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1628 | felem_shrink(p_pre_comp[1][0], x_out); |
| 1629 | felem_shrink(p_pre_comp[1][1], y_out); |
| 1630 | felem_shrink(p_pre_comp[1][2], z_out); |
| 1631 | for (size_t j = 2; j <= 16; ++j) { |
| 1632 | if (j & 1) { |
| 1633 | point_add_small(p_pre_comp[j][0], p_pre_comp[j][1], |
| 1634 | p_pre_comp[j][2], p_pre_comp[1][0], |
| 1635 | p_pre_comp[1][1], p_pre_comp[1][2], |
| 1636 | p_pre_comp[j - 1][0], p_pre_comp[j - 1][1], |
| 1637 | p_pre_comp[j - 1][2]); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1638 | } else { |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1639 | point_double_small(p_pre_comp[j][0], p_pre_comp[j][1], |
| 1640 | p_pre_comp[j][2], p_pre_comp[j / 2][0], |
| 1641 | p_pre_comp[j / 2][1], p_pre_comp[j / 2][2]); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1642 | } |
| 1643 | } |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1644 | } |
| 1645 | |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 1646 | if (g_scalar != NULL) { |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 1647 | size_t num_bytes; |
| 1648 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1649 | OPENSSL_memset(g_secret, 0, sizeof(g_secret)); |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 1650 | /* reduce g_scalar to 0 <= g_scalar < 2^256 */ |
| 1651 | if (BN_num_bits(g_scalar) > 256 || BN_is_negative(g_scalar)) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1652 | /* this is an unusual input, and we don't guarantee |
| 1653 | * constant-timeness. */ |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 1654 | if (!BN_nnmod(tmp_scalar, g_scalar, &group->order, ctx)) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 1655 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1656 | goto err; |
| 1657 | } |
| 1658 | num_bytes = BN_bn2bin(tmp_scalar, tmp); |
| 1659 | } else { |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 1660 | num_bytes = BN_bn2bin(g_scalar, tmp); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1661 | } |
| 1662 | flip_endian(g_secret, tmp, num_bytes); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1663 | } |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 1664 | batch_mul(x_out, y_out, z_out, |
| 1665 | (p != NULL && p_scalar != NULL) ? p_secret : NULL, |
| 1666 | g_scalar != NULL ? g_secret : NULL, |
| 1667 | (const smallfelem(*)[3]) &p_pre_comp); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1668 | |
| 1669 | /* reduce the output to its unique minimal representation */ |
| 1670 | felem_contract(x_in, x_out); |
| 1671 | felem_contract(y_in, y_out); |
| 1672 | felem_contract(z_in, z_out); |
| 1673 | if (!smallfelem_to_BN(x, x_in) || |
| 1674 | !smallfelem_to_BN(y, y_in) || |
| 1675 | !smallfelem_to_BN(z, z_in)) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 1676 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1677 | goto err; |
| 1678 | } |
| 1679 | ret = ec_point_set_Jprojective_coordinates_GFp(group, r, x, y, z, ctx); |
| 1680 | |
| 1681 | err: |
| 1682 | BN_CTX_end(ctx); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1683 | BN_CTX_free(new_ctx); |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1684 | return ret; |
| 1685 | } |
| 1686 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 1687 | DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_nistp256_method) { |
| 1688 | out->group_init = ec_GFp_simple_group_init; |
| 1689 | out->group_finish = ec_GFp_simple_group_finish; |
| 1690 | out->group_copy = ec_GFp_simple_group_copy; |
| 1691 | out->group_set_curve = ec_GFp_simple_group_set_curve; |
| 1692 | out->point_get_affine_coordinates = |
| 1693 | ec_GFp_nistp256_point_get_affine_coordinates; |
| 1694 | out->mul = ec_GFp_nistp256_points_mul; |
| 1695 | out->field_mul = ec_GFp_simple_field_mul; |
| 1696 | out->field_sqr = ec_GFp_simple_field_sqr; |
| 1697 | out->field_encode = NULL; |
| 1698 | out->field_decode = NULL; |
David Benjamin | f0c4a6c | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 1699 | }; |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 1700 | |
| 1701 | #endif /* 64_BIT && !WINDOWS */ |