Jarno Lamsa | 18987a4 | 2019-04-24 15:40:43 +0300 | [diff] [blame] | 1 | /* ecc.c - TinyCrypt implementation of common ECC functions */ |
| 2 | |
| 3 | /* |
| 4 | * Copyright (c) 2014, Kenneth MacKay |
| 5 | * All rights reserved. |
| 6 | * |
| 7 | * Redistribution and use in source and binary forms, with or without |
| 8 | * modification, are permitted provided that the following conditions are met: |
| 9 | * * Redistributions of source code must retain the above copyright notice, |
| 10 | * this list of conditions and the following disclaimer. |
| 11 | * * Redistributions in binary form must reproduce the above copyright notice, |
| 12 | * this list of conditions and the following disclaimer in the documentation |
| 13 | * and/or other materials provided with the distribution. |
| 14 | * |
| 15 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
| 16 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| 17 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| 18 | * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR |
| 19 | * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 20 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 21 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON |
| 22 | * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 23 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 24 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 25 | * |
| 26 | * Copyright (C) 2017 by Intel Corporation, All Rights Reserved. |
| 27 | * |
| 28 | * Redistribution and use in source and binary forms, with or without |
| 29 | * modification, are permitted provided that the following conditions are met: |
| 30 | * |
| 31 | * - Redistributions of source code must retain the above copyright notice, |
| 32 | * this list of conditions and the following disclaimer. |
| 33 | * |
| 34 | * - Redistributions in binary form must reproduce the above copyright |
| 35 | * notice, this list of conditions and the following disclaimer in the |
| 36 | * documentation and/or other materials provided with the distribution. |
| 37 | * |
| 38 | * - Neither the name of Intel Corporation nor the names of its contributors |
| 39 | * may be used to endorse or promote products derived from this software |
| 40 | * without specific prior written permission. |
| 41 | * |
| 42 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| 43 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 44 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 45 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
| 46 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| 47 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| 48 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| 49 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| 50 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 51 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 52 | * POSSIBILITY OF SUCH DAMAGE. |
| 53 | */ |
| 54 | |
Jarno Lamsa | 5542796 | 2019-04-29 10:25:23 +0300 | [diff] [blame^] | 55 | #if defined(MBEDTLS_USE_UECC) |
Jarno Lamsa | 18987a4 | 2019-04-24 15:40:43 +0300 | [diff] [blame] | 56 | #include <tinycrypt/ecc.h> |
Jarno Lamsa | 18987a4 | 2019-04-24 15:40:43 +0300 | [diff] [blame] | 57 | #include <string.h> |
| 58 | |
| 59 | /* IMPORTANT: Make sure a cryptographically-secure PRNG is set and the platform |
| 60 | * has access to enough entropy in order to feed the PRNG regularly. */ |
| 61 | #if default_RNG_defined |
| 62 | static uECC_RNG_Function g_rng_function = &default_CSPRNG; |
| 63 | #else |
| 64 | static uECC_RNG_Function g_rng_function = 0; |
| 65 | #endif |
| 66 | |
| 67 | void uECC_set_rng(uECC_RNG_Function rng_function) |
| 68 | { |
| 69 | g_rng_function = rng_function; |
| 70 | } |
| 71 | |
| 72 | uECC_RNG_Function uECC_get_rng(void) |
| 73 | { |
| 74 | return g_rng_function; |
| 75 | } |
| 76 | |
| 77 | int uECC_curve_private_key_size(uECC_Curve curve) |
| 78 | { |
| 79 | return BITS_TO_BYTES(curve->num_n_bits); |
| 80 | } |
| 81 | |
| 82 | int uECC_curve_public_key_size(uECC_Curve curve) |
| 83 | { |
| 84 | return 2 * curve->num_bytes; |
| 85 | } |
| 86 | |
| 87 | void uECC_vli_clear(uECC_word_t *vli, wordcount_t num_words) |
| 88 | { |
| 89 | wordcount_t i; |
| 90 | for (i = 0; i < num_words; ++i) { |
| 91 | vli[i] = 0; |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | uECC_word_t uECC_vli_isZero(const uECC_word_t *vli, wordcount_t num_words) |
| 96 | { |
| 97 | uECC_word_t bits = 0; |
| 98 | wordcount_t i; |
| 99 | for (i = 0; i < num_words; ++i) { |
| 100 | bits |= vli[i]; |
| 101 | } |
| 102 | return (bits == 0); |
| 103 | } |
| 104 | |
| 105 | uECC_word_t uECC_vli_testBit(const uECC_word_t *vli, bitcount_t bit) |
| 106 | { |
| 107 | return (vli[bit >> uECC_WORD_BITS_SHIFT] & |
| 108 | ((uECC_word_t)1 << (bit & uECC_WORD_BITS_MASK))); |
| 109 | } |
| 110 | |
| 111 | /* Counts the number of words in vli. */ |
| 112 | static wordcount_t vli_numDigits(const uECC_word_t *vli, |
| 113 | const wordcount_t max_words) |
| 114 | { |
| 115 | |
| 116 | wordcount_t i; |
| 117 | /* Search from the end until we find a non-zero digit. We do it in reverse |
| 118 | * because we expect that most digits will be nonzero. */ |
| 119 | for (i = max_words - 1; i >= 0 && vli[i] == 0; --i) { |
| 120 | } |
| 121 | |
| 122 | return (i + 1); |
| 123 | } |
| 124 | |
| 125 | bitcount_t uECC_vli_numBits(const uECC_word_t *vli, |
| 126 | const wordcount_t max_words) |
| 127 | { |
| 128 | |
| 129 | uECC_word_t i; |
| 130 | uECC_word_t digit; |
| 131 | |
| 132 | wordcount_t num_digits = vli_numDigits(vli, max_words); |
| 133 | if (num_digits == 0) { |
| 134 | return 0; |
| 135 | } |
| 136 | |
| 137 | digit = vli[num_digits - 1]; |
| 138 | for (i = 0; digit; ++i) { |
| 139 | digit >>= 1; |
| 140 | } |
| 141 | |
| 142 | return (((bitcount_t)(num_digits - 1) << uECC_WORD_BITS_SHIFT) + i); |
| 143 | } |
| 144 | |
| 145 | void uECC_vli_set(uECC_word_t *dest, const uECC_word_t *src, |
| 146 | wordcount_t num_words) |
| 147 | { |
| 148 | wordcount_t i; |
| 149 | |
| 150 | for (i = 0; i < num_words; ++i) { |
| 151 | dest[i] = src[i]; |
| 152 | } |
| 153 | } |
| 154 | |
| 155 | cmpresult_t uECC_vli_cmp_unsafe(const uECC_word_t *left, |
| 156 | const uECC_word_t *right, |
| 157 | wordcount_t num_words) |
| 158 | { |
| 159 | wordcount_t i; |
| 160 | |
| 161 | for (i = num_words - 1; i >= 0; --i) { |
| 162 | if (left[i] > right[i]) { |
| 163 | return 1; |
| 164 | } else if (left[i] < right[i]) { |
| 165 | return -1; |
| 166 | } |
| 167 | } |
| 168 | return 0; |
| 169 | } |
| 170 | |
| 171 | uECC_word_t uECC_vli_equal(const uECC_word_t *left, const uECC_word_t *right, |
| 172 | wordcount_t num_words) |
| 173 | { |
| 174 | |
| 175 | uECC_word_t diff = 0; |
| 176 | wordcount_t i; |
| 177 | |
| 178 | for (i = num_words - 1; i >= 0; --i) { |
| 179 | diff |= (left[i] ^ right[i]); |
| 180 | } |
| 181 | return !(diff == 0); |
| 182 | } |
| 183 | |
| 184 | uECC_word_t cond_set(uECC_word_t p_true, uECC_word_t p_false, unsigned int cond) |
| 185 | { |
| 186 | return (p_true*(cond)) | (p_false*(!cond)); |
| 187 | } |
| 188 | |
| 189 | /* Computes result = left - right, returning borrow, in constant time. |
| 190 | * Can modify in place. */ |
| 191 | uECC_word_t uECC_vli_sub(uECC_word_t *result, const uECC_word_t *left, |
| 192 | const uECC_word_t *right, wordcount_t num_words) |
| 193 | { |
| 194 | uECC_word_t borrow = 0; |
| 195 | wordcount_t i; |
| 196 | for (i = 0; i < num_words; ++i) { |
| 197 | uECC_word_t diff = left[i] - right[i] - borrow; |
| 198 | uECC_word_t val = (diff > left[i]); |
| 199 | borrow = cond_set(val, borrow, (diff != left[i])); |
| 200 | |
| 201 | result[i] = diff; |
| 202 | } |
| 203 | return borrow; |
| 204 | } |
| 205 | |
| 206 | /* Computes result = left + right, returning carry, in constant time. |
| 207 | * Can modify in place. */ |
| 208 | static uECC_word_t uECC_vli_add(uECC_word_t *result, const uECC_word_t *left, |
| 209 | const uECC_word_t *right, wordcount_t num_words) |
| 210 | { |
| 211 | uECC_word_t carry = 0; |
| 212 | wordcount_t i; |
| 213 | for (i = 0; i < num_words; ++i) { |
| 214 | uECC_word_t sum = left[i] + right[i] + carry; |
| 215 | uECC_word_t val = (sum < left[i]); |
| 216 | carry = cond_set(val, carry, (sum != left[i])); |
| 217 | result[i] = sum; |
| 218 | } |
| 219 | return carry; |
| 220 | } |
| 221 | |
| 222 | cmpresult_t uECC_vli_cmp(const uECC_word_t *left, const uECC_word_t *right, |
| 223 | wordcount_t num_words) |
| 224 | { |
| 225 | uECC_word_t tmp[NUM_ECC_WORDS]; |
| 226 | uECC_word_t neg = !!uECC_vli_sub(tmp, left, right, num_words); |
| 227 | uECC_word_t equal = uECC_vli_isZero(tmp, num_words); |
| 228 | return (!equal - 2 * neg); |
| 229 | } |
| 230 | |
| 231 | /* Computes vli = vli >> 1. */ |
| 232 | static void uECC_vli_rshift1(uECC_word_t *vli, wordcount_t num_words) |
| 233 | { |
| 234 | uECC_word_t *end = vli; |
| 235 | uECC_word_t carry = 0; |
| 236 | |
| 237 | vli += num_words; |
| 238 | while (vli-- > end) { |
| 239 | uECC_word_t temp = *vli; |
| 240 | *vli = (temp >> 1) | carry; |
| 241 | carry = temp << (uECC_WORD_BITS - 1); |
| 242 | } |
| 243 | } |
| 244 | |
| 245 | static void muladd(uECC_word_t a, uECC_word_t b, uECC_word_t *r0, |
| 246 | uECC_word_t *r1, uECC_word_t *r2) |
| 247 | { |
| 248 | |
| 249 | uECC_dword_t p = (uECC_dword_t)a * b; |
| 250 | uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0; |
| 251 | r01 += p; |
| 252 | *r2 += (r01 < p); |
| 253 | *r1 = r01 >> uECC_WORD_BITS; |
| 254 | *r0 = (uECC_word_t)r01; |
| 255 | |
| 256 | } |
| 257 | |
| 258 | /* Computes result = left * right. Result must be 2 * num_words long. */ |
| 259 | static void uECC_vli_mult(uECC_word_t *result, const uECC_word_t *left, |
| 260 | const uECC_word_t *right, wordcount_t num_words) |
| 261 | { |
| 262 | |
| 263 | uECC_word_t r0 = 0; |
| 264 | uECC_word_t r1 = 0; |
| 265 | uECC_word_t r2 = 0; |
| 266 | wordcount_t i, k; |
| 267 | |
| 268 | /* Compute each digit of result in sequence, maintaining the carries. */ |
| 269 | for (k = 0; k < num_words; ++k) { |
| 270 | |
| 271 | for (i = 0; i <= k; ++i) { |
| 272 | muladd(left[i], right[k - i], &r0, &r1, &r2); |
| 273 | } |
| 274 | |
| 275 | result[k] = r0; |
| 276 | r0 = r1; |
| 277 | r1 = r2; |
| 278 | r2 = 0; |
| 279 | } |
| 280 | |
| 281 | for (k = num_words; k < num_words * 2 - 1; ++k) { |
| 282 | |
| 283 | for (i = (k + 1) - num_words; i < num_words; ++i) { |
| 284 | muladd(left[i], right[k - i], &r0, &r1, &r2); |
| 285 | } |
| 286 | result[k] = r0; |
| 287 | r0 = r1; |
| 288 | r1 = r2; |
| 289 | r2 = 0; |
| 290 | } |
| 291 | result[num_words * 2 - 1] = r0; |
| 292 | } |
| 293 | |
| 294 | void uECC_vli_modAdd(uECC_word_t *result, const uECC_word_t *left, |
| 295 | const uECC_word_t *right, const uECC_word_t *mod, |
| 296 | wordcount_t num_words) |
| 297 | { |
| 298 | uECC_word_t carry = uECC_vli_add(result, left, right, num_words); |
| 299 | if (carry || uECC_vli_cmp_unsafe(mod, result, num_words) != 1) { |
| 300 | /* result > mod (result = mod + remainder), so subtract mod to get |
| 301 | * remainder. */ |
| 302 | uECC_vli_sub(result, result, mod, num_words); |
| 303 | } |
| 304 | } |
| 305 | |
| 306 | void uECC_vli_modSub(uECC_word_t *result, const uECC_word_t *left, |
| 307 | const uECC_word_t *right, const uECC_word_t *mod, |
| 308 | wordcount_t num_words) |
| 309 | { |
| 310 | uECC_word_t l_borrow = uECC_vli_sub(result, left, right, num_words); |
| 311 | if (l_borrow) { |
| 312 | /* In this case, result == -diff == (max int) - diff. Since -x % d == d - x, |
| 313 | * we can get the correct result from result + mod (with overflow). */ |
| 314 | uECC_vli_add(result, result, mod, num_words); |
| 315 | } |
| 316 | } |
| 317 | |
| 318 | /* Computes result = product % mod, where product is 2N words long. */ |
| 319 | /* Currently only designed to work for curve_p or curve_n. */ |
| 320 | void uECC_vli_mmod(uECC_word_t *result, uECC_word_t *product, |
| 321 | const uECC_word_t *mod, wordcount_t num_words) |
| 322 | { |
| 323 | uECC_word_t mod_multiple[2 * NUM_ECC_WORDS]; |
| 324 | uECC_word_t tmp[2 * NUM_ECC_WORDS]; |
| 325 | uECC_word_t *v[2] = {tmp, product}; |
| 326 | uECC_word_t index; |
| 327 | |
| 328 | /* Shift mod so its highest set bit is at the maximum position. */ |
| 329 | bitcount_t shift = (num_words * 2 * uECC_WORD_BITS) - |
| 330 | uECC_vli_numBits(mod, num_words); |
| 331 | wordcount_t word_shift = shift / uECC_WORD_BITS; |
| 332 | wordcount_t bit_shift = shift % uECC_WORD_BITS; |
| 333 | uECC_word_t carry = 0; |
| 334 | uECC_vli_clear(mod_multiple, word_shift); |
| 335 | if (bit_shift > 0) { |
| 336 | for(index = 0; index < (uECC_word_t)num_words; ++index) { |
| 337 | mod_multiple[word_shift + index] = (mod[index] << bit_shift) | carry; |
| 338 | carry = mod[index] >> (uECC_WORD_BITS - bit_shift); |
| 339 | } |
| 340 | } else { |
| 341 | uECC_vli_set(mod_multiple + word_shift, mod, num_words); |
| 342 | } |
| 343 | |
| 344 | for (index = 1; shift >= 0; --shift) { |
| 345 | uECC_word_t borrow = 0; |
| 346 | wordcount_t i; |
| 347 | for (i = 0; i < num_words * 2; ++i) { |
| 348 | uECC_word_t diff = v[index][i] - mod_multiple[i] - borrow; |
| 349 | if (diff != v[index][i]) { |
| 350 | borrow = (diff > v[index][i]); |
| 351 | } |
| 352 | v[1 - index][i] = diff; |
| 353 | } |
| 354 | /* Swap the index if there was no borrow */ |
| 355 | index = !(index ^ borrow); |
| 356 | uECC_vli_rshift1(mod_multiple, num_words); |
| 357 | mod_multiple[num_words - 1] |= mod_multiple[num_words] << |
| 358 | (uECC_WORD_BITS - 1); |
| 359 | uECC_vli_rshift1(mod_multiple + num_words, num_words); |
| 360 | } |
| 361 | uECC_vli_set(result, v[index], num_words); |
| 362 | } |
| 363 | |
| 364 | void uECC_vli_modMult(uECC_word_t *result, const uECC_word_t *left, |
| 365 | const uECC_word_t *right, const uECC_word_t *mod, |
| 366 | wordcount_t num_words) |
| 367 | { |
| 368 | uECC_word_t product[2 * NUM_ECC_WORDS]; |
| 369 | uECC_vli_mult(product, left, right, num_words); |
| 370 | uECC_vli_mmod(result, product, mod, num_words); |
| 371 | } |
| 372 | |
| 373 | void uECC_vli_modMult_fast(uECC_word_t *result, const uECC_word_t *left, |
| 374 | const uECC_word_t *right, uECC_Curve curve) |
| 375 | { |
| 376 | uECC_word_t product[2 * NUM_ECC_WORDS]; |
| 377 | uECC_vli_mult(product, left, right, curve->num_words); |
| 378 | |
| 379 | curve->mmod_fast(result, product); |
| 380 | } |
| 381 | |
| 382 | static void uECC_vli_modSquare_fast(uECC_word_t *result, |
| 383 | const uECC_word_t *left, |
| 384 | uECC_Curve curve) |
| 385 | { |
| 386 | uECC_vli_modMult_fast(result, left, left, curve); |
| 387 | } |
| 388 | |
| 389 | |
| 390 | #define EVEN(vli) (!(vli[0] & 1)) |
| 391 | |
| 392 | static void vli_modInv_update(uECC_word_t *uv, |
| 393 | const uECC_word_t *mod, |
| 394 | wordcount_t num_words) |
| 395 | { |
| 396 | |
| 397 | uECC_word_t carry = 0; |
| 398 | |
| 399 | if (!EVEN(uv)) { |
| 400 | carry = uECC_vli_add(uv, uv, mod, num_words); |
| 401 | } |
| 402 | uECC_vli_rshift1(uv, num_words); |
| 403 | if (carry) { |
| 404 | uv[num_words - 1] |= HIGH_BIT_SET; |
| 405 | } |
| 406 | } |
| 407 | |
| 408 | void uECC_vli_modInv(uECC_word_t *result, const uECC_word_t *input, |
| 409 | const uECC_word_t *mod, wordcount_t num_words) |
| 410 | { |
| 411 | uECC_word_t a[NUM_ECC_WORDS], b[NUM_ECC_WORDS]; |
| 412 | uECC_word_t u[NUM_ECC_WORDS], v[NUM_ECC_WORDS]; |
| 413 | cmpresult_t cmpResult; |
| 414 | |
| 415 | if (uECC_vli_isZero(input, num_words)) { |
| 416 | uECC_vli_clear(result, num_words); |
| 417 | return; |
| 418 | } |
| 419 | |
| 420 | uECC_vli_set(a, input, num_words); |
| 421 | uECC_vli_set(b, mod, num_words); |
| 422 | uECC_vli_clear(u, num_words); |
| 423 | u[0] = 1; |
| 424 | uECC_vli_clear(v, num_words); |
| 425 | while ((cmpResult = uECC_vli_cmp_unsafe(a, b, num_words)) != 0) { |
| 426 | if (EVEN(a)) { |
| 427 | uECC_vli_rshift1(a, num_words); |
| 428 | vli_modInv_update(u, mod, num_words); |
| 429 | } else if (EVEN(b)) { |
| 430 | uECC_vli_rshift1(b, num_words); |
| 431 | vli_modInv_update(v, mod, num_words); |
| 432 | } else if (cmpResult > 0) { |
| 433 | uECC_vli_sub(a, a, b, num_words); |
| 434 | uECC_vli_rshift1(a, num_words); |
| 435 | if (uECC_vli_cmp_unsafe(u, v, num_words) < 0) { |
| 436 | uECC_vli_add(u, u, mod, num_words); |
| 437 | } |
| 438 | uECC_vli_sub(u, u, v, num_words); |
| 439 | vli_modInv_update(u, mod, num_words); |
| 440 | } else { |
| 441 | uECC_vli_sub(b, b, a, num_words); |
| 442 | uECC_vli_rshift1(b, num_words); |
| 443 | if (uECC_vli_cmp_unsafe(v, u, num_words) < 0) { |
| 444 | uECC_vli_add(v, v, mod, num_words); |
| 445 | } |
| 446 | uECC_vli_sub(v, v, u, num_words); |
| 447 | vli_modInv_update(v, mod, num_words); |
| 448 | } |
| 449 | } |
| 450 | uECC_vli_set(result, u, num_words); |
| 451 | } |
| 452 | |
| 453 | /* ------ Point operations ------ */ |
| 454 | |
| 455 | void double_jacobian_default(uECC_word_t * X1, uECC_word_t * Y1, |
| 456 | uECC_word_t * Z1, uECC_Curve curve) |
| 457 | { |
| 458 | /* t1 = X, t2 = Y, t3 = Z */ |
| 459 | uECC_word_t t4[NUM_ECC_WORDS]; |
| 460 | uECC_word_t t5[NUM_ECC_WORDS]; |
| 461 | wordcount_t num_words = curve->num_words; |
| 462 | |
| 463 | if (uECC_vli_isZero(Z1, num_words)) { |
| 464 | return; |
| 465 | } |
| 466 | |
| 467 | uECC_vli_modSquare_fast(t4, Y1, curve); /* t4 = y1^2 */ |
| 468 | uECC_vli_modMult_fast(t5, X1, t4, curve); /* t5 = x1*y1^2 = A */ |
| 469 | uECC_vli_modSquare_fast(t4, t4, curve); /* t4 = y1^4 */ |
| 470 | uECC_vli_modMult_fast(Y1, Y1, Z1, curve); /* t2 = y1*z1 = z3 */ |
| 471 | uECC_vli_modSquare_fast(Z1, Z1, curve); /* t3 = z1^2 */ |
| 472 | |
| 473 | uECC_vli_modAdd(X1, X1, Z1, curve->p, num_words); /* t1 = x1 + z1^2 */ |
| 474 | uECC_vli_modAdd(Z1, Z1, Z1, curve->p, num_words); /* t3 = 2*z1^2 */ |
| 475 | uECC_vli_modSub(Z1, X1, Z1, curve->p, num_words); /* t3 = x1 - z1^2 */ |
| 476 | uECC_vli_modMult_fast(X1, X1, Z1, curve); /* t1 = x1^2 - z1^4 */ |
| 477 | |
| 478 | uECC_vli_modAdd(Z1, X1, X1, curve->p, num_words); /* t3 = 2*(x1^2 - z1^4) */ |
| 479 | uECC_vli_modAdd(X1, X1, Z1, curve->p, num_words); /* t1 = 3*(x1^2 - z1^4) */ |
| 480 | if (uECC_vli_testBit(X1, 0)) { |
| 481 | uECC_word_t l_carry = uECC_vli_add(X1, X1, curve->p, num_words); |
| 482 | uECC_vli_rshift1(X1, num_words); |
| 483 | X1[num_words - 1] |= l_carry << (uECC_WORD_BITS - 1); |
| 484 | } else { |
| 485 | uECC_vli_rshift1(X1, num_words); |
| 486 | } |
| 487 | |
| 488 | /* t1 = 3/2*(x1^2 - z1^4) = B */ |
| 489 | uECC_vli_modSquare_fast(Z1, X1, curve); /* t3 = B^2 */ |
| 490 | uECC_vli_modSub(Z1, Z1, t5, curve->p, num_words); /* t3 = B^2 - A */ |
| 491 | uECC_vli_modSub(Z1, Z1, t5, curve->p, num_words); /* t3 = B^2 - 2A = x3 */ |
| 492 | uECC_vli_modSub(t5, t5, Z1, curve->p, num_words); /* t5 = A - x3 */ |
| 493 | uECC_vli_modMult_fast(X1, X1, t5, curve); /* t1 = B * (A - x3) */ |
| 494 | /* t4 = B * (A - x3) - y1^4 = y3: */ |
| 495 | uECC_vli_modSub(t4, X1, t4, curve->p, num_words); |
| 496 | |
| 497 | uECC_vli_set(X1, Z1, num_words); |
| 498 | uECC_vli_set(Z1, Y1, num_words); |
| 499 | uECC_vli_set(Y1, t4, num_words); |
| 500 | } |
| 501 | |
| 502 | void x_side_default(uECC_word_t *result, |
| 503 | const uECC_word_t *x, |
| 504 | uECC_Curve curve) |
| 505 | { |
| 506 | uECC_word_t _3[NUM_ECC_WORDS] = {3}; /* -a = 3 */ |
| 507 | wordcount_t num_words = curve->num_words; |
| 508 | |
| 509 | uECC_vli_modSquare_fast(result, x, curve); /* r = x^2 */ |
| 510 | uECC_vli_modSub(result, result, _3, curve->p, num_words); /* r = x^2 - 3 */ |
| 511 | uECC_vli_modMult_fast(result, result, x, curve); /* r = x^3 - 3x */ |
| 512 | /* r = x^3 - 3x + b: */ |
| 513 | uECC_vli_modAdd(result, result, curve->b, curve->p, num_words); |
| 514 | } |
| 515 | |
| 516 | uECC_Curve uECC_secp256r1(void) |
| 517 | { |
| 518 | return &curve_secp256r1; |
| 519 | } |
| 520 | |
| 521 | void vli_mmod_fast_secp256r1(unsigned int *result, unsigned int*product) |
| 522 | { |
| 523 | unsigned int tmp[NUM_ECC_WORDS]; |
| 524 | int carry; |
| 525 | |
| 526 | /* t */ |
| 527 | uECC_vli_set(result, product, NUM_ECC_WORDS); |
| 528 | |
| 529 | /* s1 */ |
| 530 | tmp[0] = tmp[1] = tmp[2] = 0; |
| 531 | tmp[3] = product[11]; |
| 532 | tmp[4] = product[12]; |
| 533 | tmp[5] = product[13]; |
| 534 | tmp[6] = product[14]; |
| 535 | tmp[7] = product[15]; |
| 536 | carry = uECC_vli_add(tmp, tmp, tmp, NUM_ECC_WORDS); |
| 537 | carry += uECC_vli_add(result, result, tmp, NUM_ECC_WORDS); |
| 538 | |
| 539 | /* s2 */ |
| 540 | tmp[3] = product[12]; |
| 541 | tmp[4] = product[13]; |
| 542 | tmp[5] = product[14]; |
| 543 | tmp[6] = product[15]; |
| 544 | tmp[7] = 0; |
| 545 | carry += uECC_vli_add(tmp, tmp, tmp, NUM_ECC_WORDS); |
| 546 | carry += uECC_vli_add(result, result, tmp, NUM_ECC_WORDS); |
| 547 | |
| 548 | /* s3 */ |
| 549 | tmp[0] = product[8]; |
| 550 | tmp[1] = product[9]; |
| 551 | tmp[2] = product[10]; |
| 552 | tmp[3] = tmp[4] = tmp[5] = 0; |
| 553 | tmp[6] = product[14]; |
| 554 | tmp[7] = product[15]; |
| 555 | carry += uECC_vli_add(result, result, tmp, NUM_ECC_WORDS); |
| 556 | |
| 557 | /* s4 */ |
| 558 | tmp[0] = product[9]; |
| 559 | tmp[1] = product[10]; |
| 560 | tmp[2] = product[11]; |
| 561 | tmp[3] = product[13]; |
| 562 | tmp[4] = product[14]; |
| 563 | tmp[5] = product[15]; |
| 564 | tmp[6] = product[13]; |
| 565 | tmp[7] = product[8]; |
| 566 | carry += uECC_vli_add(result, result, tmp, NUM_ECC_WORDS); |
| 567 | |
| 568 | /* d1 */ |
| 569 | tmp[0] = product[11]; |
| 570 | tmp[1] = product[12]; |
| 571 | tmp[2] = product[13]; |
| 572 | tmp[3] = tmp[4] = tmp[5] = 0; |
| 573 | tmp[6] = product[8]; |
| 574 | tmp[7] = product[10]; |
| 575 | carry -= uECC_vli_sub(result, result, tmp, NUM_ECC_WORDS); |
| 576 | |
| 577 | /* d2 */ |
| 578 | tmp[0] = product[12]; |
| 579 | tmp[1] = product[13]; |
| 580 | tmp[2] = product[14]; |
| 581 | tmp[3] = product[15]; |
| 582 | tmp[4] = tmp[5] = 0; |
| 583 | tmp[6] = product[9]; |
| 584 | tmp[7] = product[11]; |
| 585 | carry -= uECC_vli_sub(result, result, tmp, NUM_ECC_WORDS); |
| 586 | |
| 587 | /* d3 */ |
| 588 | tmp[0] = product[13]; |
| 589 | tmp[1] = product[14]; |
| 590 | tmp[2] = product[15]; |
| 591 | tmp[3] = product[8]; |
| 592 | tmp[4] = product[9]; |
| 593 | tmp[5] = product[10]; |
| 594 | tmp[6] = 0; |
| 595 | tmp[7] = product[12]; |
| 596 | carry -= uECC_vli_sub(result, result, tmp, NUM_ECC_WORDS); |
| 597 | |
| 598 | /* d4 */ |
| 599 | tmp[0] = product[14]; |
| 600 | tmp[1] = product[15]; |
| 601 | tmp[2] = 0; |
| 602 | tmp[3] = product[9]; |
| 603 | tmp[4] = product[10]; |
| 604 | tmp[5] = product[11]; |
| 605 | tmp[6] = 0; |
| 606 | tmp[7] = product[13]; |
| 607 | carry -= uECC_vli_sub(result, result, tmp, NUM_ECC_WORDS); |
| 608 | |
| 609 | if (carry < 0) { |
| 610 | do { |
| 611 | carry += uECC_vli_add(result, result, curve_secp256r1.p, NUM_ECC_WORDS); |
| 612 | } |
| 613 | while (carry < 0); |
| 614 | } else { |
| 615 | while (carry || |
| 616 | uECC_vli_cmp_unsafe(curve_secp256r1.p, result, NUM_ECC_WORDS) != 1) { |
| 617 | carry -= uECC_vli_sub(result, result, curve_secp256r1.p, NUM_ECC_WORDS); |
| 618 | } |
| 619 | } |
| 620 | } |
| 621 | |
| 622 | uECC_word_t EccPoint_isZero(const uECC_word_t *point, uECC_Curve curve) |
| 623 | { |
| 624 | return uECC_vli_isZero(point, curve->num_words * 2); |
| 625 | } |
| 626 | |
| 627 | void apply_z(uECC_word_t * X1, uECC_word_t * Y1, const uECC_word_t * const Z, |
| 628 | uECC_Curve curve) |
| 629 | { |
| 630 | uECC_word_t t1[NUM_ECC_WORDS]; |
| 631 | |
| 632 | uECC_vli_modSquare_fast(t1, Z, curve); /* z^2 */ |
| 633 | uECC_vli_modMult_fast(X1, X1, t1, curve); /* x1 * z^2 */ |
| 634 | uECC_vli_modMult_fast(t1, t1, Z, curve); /* z^3 */ |
| 635 | uECC_vli_modMult_fast(Y1, Y1, t1, curve); /* y1 * z^3 */ |
| 636 | } |
| 637 | |
| 638 | /* P = (x1, y1) => 2P, (x2, y2) => P' */ |
| 639 | static void XYcZ_initial_double(uECC_word_t * X1, uECC_word_t * Y1, |
| 640 | uECC_word_t * X2, uECC_word_t * Y2, |
| 641 | const uECC_word_t * const initial_Z, |
| 642 | uECC_Curve curve) |
| 643 | { |
| 644 | uECC_word_t z[NUM_ECC_WORDS]; |
| 645 | wordcount_t num_words = curve->num_words; |
| 646 | if (initial_Z) { |
| 647 | uECC_vli_set(z, initial_Z, num_words); |
| 648 | } else { |
| 649 | uECC_vli_clear(z, num_words); |
| 650 | z[0] = 1; |
| 651 | } |
| 652 | |
| 653 | uECC_vli_set(X2, X1, num_words); |
| 654 | uECC_vli_set(Y2, Y1, num_words); |
| 655 | |
| 656 | apply_z(X1, Y1, z, curve); |
| 657 | curve->double_jacobian(X1, Y1, z, curve); |
| 658 | apply_z(X2, Y2, z, curve); |
| 659 | } |
| 660 | |
| 661 | void XYcZ_add(uECC_word_t * X1, uECC_word_t * Y1, |
| 662 | uECC_word_t * X2, uECC_word_t * Y2, |
| 663 | uECC_Curve curve) |
| 664 | { |
| 665 | /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ |
| 666 | uECC_word_t t5[NUM_ECC_WORDS]; |
| 667 | wordcount_t num_words = curve->num_words; |
| 668 | |
| 669 | uECC_vli_modSub(t5, X2, X1, curve->p, num_words); /* t5 = x2 - x1 */ |
| 670 | uECC_vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ |
| 671 | uECC_vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ |
| 672 | uECC_vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ |
| 673 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y2 - y1 */ |
| 674 | uECC_vli_modSquare_fast(t5, Y2, curve); /* t5 = (y2 - y1)^2 = D */ |
| 675 | |
| 676 | uECC_vli_modSub(t5, t5, X1, curve->p, num_words); /* t5 = D - B */ |
| 677 | uECC_vli_modSub(t5, t5, X2, curve->p, num_words); /* t5 = D - B - C = x3 */ |
| 678 | uECC_vli_modSub(X2, X2, X1, curve->p, num_words); /* t3 = C - B */ |
| 679 | uECC_vli_modMult_fast(Y1, Y1, X2, curve); /* t2 = y1*(C - B) */ |
| 680 | uECC_vli_modSub(X2, X1, t5, curve->p, num_words); /* t3 = B - x3 */ |
| 681 | uECC_vli_modMult_fast(Y2, Y2, X2, curve); /* t4 = (y2 - y1)*(B - x3) */ |
| 682 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y3 */ |
| 683 | |
| 684 | uECC_vli_set(X2, t5, num_words); |
| 685 | } |
| 686 | |
| 687 | /* Input P = (x1, y1, Z), Q = (x2, y2, Z) |
| 688 | Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) |
| 689 | or P => P - Q, Q => P + Q |
| 690 | */ |
| 691 | static void XYcZ_addC(uECC_word_t * X1, uECC_word_t * Y1, |
| 692 | uECC_word_t * X2, uECC_word_t * Y2, |
| 693 | uECC_Curve curve) |
| 694 | { |
| 695 | /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ |
| 696 | uECC_word_t t5[NUM_ECC_WORDS]; |
| 697 | uECC_word_t t6[NUM_ECC_WORDS]; |
| 698 | uECC_word_t t7[NUM_ECC_WORDS]; |
| 699 | wordcount_t num_words = curve->num_words; |
| 700 | |
| 701 | uECC_vli_modSub(t5, X2, X1, curve->p, num_words); /* t5 = x2 - x1 */ |
| 702 | uECC_vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ |
| 703 | uECC_vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ |
| 704 | uECC_vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ |
| 705 | uECC_vli_modAdd(t5, Y2, Y1, curve->p, num_words); /* t5 = y2 + y1 */ |
| 706 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y2 - y1 */ |
| 707 | |
| 708 | uECC_vli_modSub(t6, X2, X1, curve->p, num_words); /* t6 = C - B */ |
| 709 | uECC_vli_modMult_fast(Y1, Y1, t6, curve); /* t2 = y1 * (C - B) = E */ |
| 710 | uECC_vli_modAdd(t6, X1, X2, curve->p, num_words); /* t6 = B + C */ |
| 711 | uECC_vli_modSquare_fast(X2, Y2, curve); /* t3 = (y2 - y1)^2 = D */ |
| 712 | uECC_vli_modSub(X2, X2, t6, curve->p, num_words); /* t3 = D - (B + C) = x3 */ |
| 713 | |
| 714 | uECC_vli_modSub(t7, X1, X2, curve->p, num_words); /* t7 = B - x3 */ |
| 715 | uECC_vli_modMult_fast(Y2, Y2, t7, curve); /* t4 = (y2 - y1)*(B - x3) */ |
| 716 | /* t4 = (y2 - y1)*(B - x3) - E = y3: */ |
| 717 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); |
| 718 | |
| 719 | uECC_vli_modSquare_fast(t7, t5, curve); /* t7 = (y2 + y1)^2 = F */ |
| 720 | uECC_vli_modSub(t7, t7, t6, curve->p, num_words); /* t7 = F - (B + C) = x3' */ |
| 721 | uECC_vli_modSub(t6, t7, X1, curve->p, num_words); /* t6 = x3' - B */ |
| 722 | uECC_vli_modMult_fast(t6, t6, t5, curve); /* t6 = (y2+y1)*(x3' - B) */ |
| 723 | /* t2 = (y2+y1)*(x3' - B) - E = y3': */ |
| 724 | uECC_vli_modSub(Y1, t6, Y1, curve->p, num_words); |
| 725 | |
| 726 | uECC_vli_set(X1, t7, num_words); |
| 727 | } |
| 728 | |
| 729 | void EccPoint_mult(uECC_word_t * result, const uECC_word_t * point, |
| 730 | const uECC_word_t * scalar, |
| 731 | const uECC_word_t * initial_Z, |
| 732 | bitcount_t num_bits, uECC_Curve curve) |
| 733 | { |
| 734 | /* R0 and R1 */ |
| 735 | uECC_word_t Rx[2][NUM_ECC_WORDS]; |
| 736 | uECC_word_t Ry[2][NUM_ECC_WORDS]; |
| 737 | uECC_word_t z[NUM_ECC_WORDS]; |
| 738 | bitcount_t i; |
| 739 | uECC_word_t nb; |
| 740 | wordcount_t num_words = curve->num_words; |
| 741 | |
| 742 | uECC_vli_set(Rx[1], point, num_words); |
| 743 | uECC_vli_set(Ry[1], point + num_words, num_words); |
| 744 | |
| 745 | XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], initial_Z, curve); |
| 746 | |
| 747 | for (i = num_bits - 2; i > 0; --i) { |
| 748 | nb = !uECC_vli_testBit(scalar, i); |
| 749 | XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve); |
| 750 | XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve); |
| 751 | } |
| 752 | |
| 753 | nb = !uECC_vli_testBit(scalar, 0); |
| 754 | XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve); |
| 755 | |
| 756 | /* Find final 1/Z value. */ |
| 757 | uECC_vli_modSub(z, Rx[1], Rx[0], curve->p, num_words); /* X1 - X0 */ |
| 758 | uECC_vli_modMult_fast(z, z, Ry[1 - nb], curve); /* Yb * (X1 - X0) */ |
| 759 | uECC_vli_modMult_fast(z, z, point, curve); /* xP * Yb * (X1 - X0) */ |
| 760 | uECC_vli_modInv(z, z, curve->p, num_words); /* 1 / (xP * Yb * (X1 - X0))*/ |
| 761 | /* yP / (xP * Yb * (X1 - X0)) */ |
| 762 | uECC_vli_modMult_fast(z, z, point + num_words, curve); |
| 763 | /* Xb * yP / (xP * Yb * (X1 - X0)) */ |
| 764 | uECC_vli_modMult_fast(z, z, Rx[1 - nb], curve); |
| 765 | /* End 1/Z calculation */ |
| 766 | |
| 767 | XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve); |
| 768 | apply_z(Rx[0], Ry[0], z, curve); |
| 769 | |
| 770 | uECC_vli_set(result, Rx[0], num_words); |
| 771 | uECC_vli_set(result + num_words, Ry[0], num_words); |
| 772 | } |
| 773 | |
| 774 | uECC_word_t regularize_k(const uECC_word_t * const k, uECC_word_t *k0, |
| 775 | uECC_word_t *k1, uECC_Curve curve) |
| 776 | { |
| 777 | |
| 778 | wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
| 779 | |
| 780 | bitcount_t num_n_bits = curve->num_n_bits; |
| 781 | |
| 782 | uECC_word_t carry = uECC_vli_add(k0, k, curve->n, num_n_words) || |
| 783 | (num_n_bits < ((bitcount_t)num_n_words * uECC_WORD_SIZE * 8) && |
| 784 | uECC_vli_testBit(k0, num_n_bits)); |
| 785 | |
| 786 | uECC_vli_add(k1, k0, curve->n, num_n_words); |
| 787 | |
| 788 | return carry; |
| 789 | } |
| 790 | |
| 791 | uECC_word_t EccPoint_compute_public_key(uECC_word_t *result, |
| 792 | uECC_word_t *private_key, |
| 793 | uECC_Curve curve) |
| 794 | { |
| 795 | |
| 796 | uECC_word_t tmp1[NUM_ECC_WORDS]; |
| 797 | uECC_word_t tmp2[NUM_ECC_WORDS]; |
| 798 | uECC_word_t *p2[2] = {tmp1, tmp2}; |
| 799 | uECC_word_t carry; |
| 800 | |
| 801 | /* Regularize the bitcount for the private key so that attackers cannot |
| 802 | * use a side channel attack to learn the number of leading zeros. */ |
| 803 | carry = regularize_k(private_key, tmp1, tmp2, curve); |
| 804 | |
| 805 | EccPoint_mult(result, curve->G, p2[!carry], 0, curve->num_n_bits + 1, curve); |
| 806 | |
| 807 | if (EccPoint_isZero(result, curve)) { |
| 808 | return 0; |
| 809 | } |
| 810 | return 1; |
| 811 | } |
| 812 | |
| 813 | /* Converts an integer in uECC native format to big-endian bytes. */ |
| 814 | void uECC_vli_nativeToBytes(uint8_t *bytes, int num_bytes, |
| 815 | const unsigned int *native) |
| 816 | { |
| 817 | wordcount_t i; |
| 818 | for (i = 0; i < num_bytes; ++i) { |
| 819 | unsigned b = num_bytes - 1 - i; |
| 820 | bytes[i] = native[b / uECC_WORD_SIZE] >> (8 * (b % uECC_WORD_SIZE)); |
| 821 | } |
| 822 | } |
| 823 | |
| 824 | /* Converts big-endian bytes to an integer in uECC native format. */ |
| 825 | void uECC_vli_bytesToNative(unsigned int *native, const uint8_t *bytes, |
| 826 | int num_bytes) |
| 827 | { |
| 828 | wordcount_t i; |
| 829 | uECC_vli_clear(native, (num_bytes + (uECC_WORD_SIZE - 1)) / uECC_WORD_SIZE); |
| 830 | for (i = 0; i < num_bytes; ++i) { |
| 831 | unsigned b = num_bytes - 1 - i; |
| 832 | native[b / uECC_WORD_SIZE] |= |
| 833 | (uECC_word_t)bytes[i] << (8 * (b % uECC_WORD_SIZE)); |
| 834 | } |
| 835 | } |
| 836 | |
| 837 | int uECC_generate_random_int(uECC_word_t *random, const uECC_word_t *top, |
| 838 | wordcount_t num_words) |
| 839 | { |
| 840 | uECC_word_t mask = (uECC_word_t)-1; |
| 841 | uECC_word_t tries; |
| 842 | bitcount_t num_bits = uECC_vli_numBits(top, num_words); |
| 843 | |
| 844 | if (!g_rng_function) { |
| 845 | return 0; |
| 846 | } |
| 847 | |
| 848 | for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { |
| 849 | if (!g_rng_function((uint8_t *)random, num_words * uECC_WORD_SIZE)) { |
| 850 | return 0; |
| 851 | } |
| 852 | random[num_words - 1] &= |
| 853 | mask >> ((bitcount_t)(num_words * uECC_WORD_SIZE * 8 - num_bits)); |
| 854 | if (!uECC_vli_isZero(random, num_words) && |
| 855 | uECC_vli_cmp(top, random, num_words) == 1) { |
| 856 | return 1; |
| 857 | } |
| 858 | } |
| 859 | return 0; |
| 860 | } |
| 861 | |
| 862 | |
| 863 | int uECC_valid_point(const uECC_word_t *point, uECC_Curve curve) |
| 864 | { |
| 865 | uECC_word_t tmp1[NUM_ECC_WORDS]; |
| 866 | uECC_word_t tmp2[NUM_ECC_WORDS]; |
| 867 | wordcount_t num_words = curve->num_words; |
| 868 | |
| 869 | /* The point at infinity is invalid. */ |
| 870 | if (EccPoint_isZero(point, curve)) { |
| 871 | return -1; |
| 872 | } |
| 873 | |
| 874 | /* x and y must be smaller than p. */ |
| 875 | if (uECC_vli_cmp_unsafe(curve->p, point, num_words) != 1 || |
| 876 | uECC_vli_cmp_unsafe(curve->p, point + num_words, num_words) != 1) { |
| 877 | return -2; |
| 878 | } |
| 879 | |
| 880 | uECC_vli_modSquare_fast(tmp1, point + num_words, curve); |
| 881 | curve->x_side(tmp2, point, curve); /* tmp2 = x^3 + ax + b */ |
| 882 | |
| 883 | /* Make sure that y^2 == x^3 + ax + b */ |
| 884 | if (uECC_vli_equal(tmp1, tmp2, num_words) != 0) |
| 885 | return -3; |
| 886 | |
| 887 | return 0; |
| 888 | } |
| 889 | |
| 890 | int uECC_valid_public_key(const uint8_t *public_key, uECC_Curve curve) |
| 891 | { |
| 892 | |
| 893 | uECC_word_t _public[NUM_ECC_WORDS * 2]; |
| 894 | |
| 895 | uECC_vli_bytesToNative(_public, public_key, curve->num_bytes); |
| 896 | uECC_vli_bytesToNative( |
| 897 | _public + curve->num_words, |
| 898 | public_key + curve->num_bytes, |
| 899 | curve->num_bytes); |
| 900 | |
| 901 | if (uECC_vli_cmp_unsafe(_public, curve->G, NUM_ECC_WORDS * 2) == 0) { |
| 902 | return -4; |
| 903 | } |
| 904 | |
| 905 | return uECC_valid_point(_public, curve); |
| 906 | } |
| 907 | |
| 908 | int uECC_compute_public_key(const uint8_t *private_key, uint8_t *public_key, |
| 909 | uECC_Curve curve) |
| 910 | { |
| 911 | |
| 912 | uECC_word_t _private[NUM_ECC_WORDS]; |
| 913 | uECC_word_t _public[NUM_ECC_WORDS * 2]; |
| 914 | |
| 915 | uECC_vli_bytesToNative( |
| 916 | _private, |
| 917 | private_key, |
| 918 | BITS_TO_BYTES(curve->num_n_bits)); |
| 919 | |
| 920 | /* Make sure the private key is in the range [1, n-1]. */ |
| 921 | if (uECC_vli_isZero(_private, BITS_TO_WORDS(curve->num_n_bits))) { |
| 922 | return 0; |
| 923 | } |
| 924 | |
| 925 | if (uECC_vli_cmp(curve->n, _private, BITS_TO_WORDS(curve->num_n_bits)) != 1) { |
| 926 | return 0; |
| 927 | } |
| 928 | |
| 929 | /* Compute public key. */ |
| 930 | if (!EccPoint_compute_public_key(_public, _private, curve)) { |
| 931 | return 0; |
| 932 | } |
| 933 | |
| 934 | uECC_vli_nativeToBytes(public_key, curve->num_bytes, _public); |
| 935 | uECC_vli_nativeToBytes( |
| 936 | public_key + |
| 937 | curve->num_bytes, curve->num_bytes, _public + curve->num_words); |
| 938 | return 1; |
| 939 | } |
| 940 | |
Jarno Lamsa | 5542796 | 2019-04-29 10:25:23 +0300 | [diff] [blame^] | 941 | #endif /* MBEDTLS_USE_UECC */ |
Jarno Lamsa | 18987a4 | 2019-04-24 15:40:43 +0300 | [diff] [blame] | 942 | |