diff options
Diffstat (limited to 'libmincrypt/p256.c')
| -rw-r--r-- | libmincrypt/p256.c | 373 |
1 files changed, 373 insertions, 0 deletions
diff --git a/libmincrypt/p256.c b/libmincrypt/p256.c new file mode 100644 index 000000000..555a07a80 --- /dev/null +++ b/libmincrypt/p256.c @@ -0,0 +1,373 @@ +/* + * Copyright 2013 The Android Open Source Project + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Google Inc. nor the names of its contributors may + * be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + * EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// This is an implementation of the P256 elliptic curve group. It's written to +// be portable 32-bit, although it's still constant-time. +// +// WARNING: Implementing these functions in a constant-time manner is far from +// obvious. Be careful when touching this code. +// +// See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background. + +#include <assert.h> +#include <stdint.h> +#include <string.h> +#include <stdio.h> + +#include "mincrypt/p256.h" + +const p256_int SECP256r1_n = // curve order + {{0xfc632551, 0xf3b9cac2, 0xa7179e84, 0xbce6faad, -1, -1, 0, -1}}; + +const p256_int SECP256r1_p = // curve field size + {{-1, -1, -1, 0, 0, 0, 1, -1 }}; + +const p256_int SECP256r1_b = // curve b + {{0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0, + 0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8}}; + +void p256_init(p256_int* a) { + memset(a, 0, sizeof(*a)); +} + +void p256_clear(p256_int* a) { p256_init(a); } + +int p256_get_bit(const p256_int* scalar, int bit) { + return (P256_DIGIT(scalar, bit / P256_BITSPERDIGIT) + >> (bit & (P256_BITSPERDIGIT - 1))) & 1; +} + +int p256_is_zero(const p256_int* a) { + int i, result = 0; + for (i = 0; i < P256_NDIGITS; ++i) result |= P256_DIGIT(a, i); + return !result; +} + +// top, c[] += a[] * b +// Returns new top +static p256_digit mulAdd(const p256_int* a, + p256_digit b, + p256_digit top, + p256_digit* c) { + int i; + p256_ddigit carry = 0; + + for (i = 0; i < P256_NDIGITS; ++i) { + carry += *c; + carry += (p256_ddigit)P256_DIGIT(a, i) * b; + *c++ = (p256_digit)carry; + carry >>= P256_BITSPERDIGIT; + } + return top + (p256_digit)carry; +} + +// top, c[] -= top_a, a[] +static p256_digit subTop(p256_digit top_a, + const p256_digit* a, + p256_digit top_c, + p256_digit* c) { + int i; + p256_sddigit borrow = 0; + + for (i = 0; i < P256_NDIGITS; ++i) { + borrow += *c; + borrow -= *a++; + *c++ = (p256_digit)borrow; + borrow >>= P256_BITSPERDIGIT; + } + borrow += top_c; + borrow -= top_a; + top_c = (p256_digit)borrow; + assert((borrow >> P256_BITSPERDIGIT) == 0); + return top_c; +} + +// top, c[] -= MOD[] & mask (0 or -1) +// returns new top. +static p256_digit subM(const p256_int* MOD, + p256_digit top, + p256_digit* c, + p256_digit mask) { + int i; + p256_sddigit borrow = 0; + for (i = 0; i < P256_NDIGITS; ++i) { + borrow += *c; + borrow -= P256_DIGIT(MOD, i) & mask; + *c++ = (p256_digit)borrow; + borrow >>= P256_BITSPERDIGIT; + } + return top + (p256_digit)borrow; +} + +// top, c[] += MOD[] & mask (0 or -1) +// returns new top. +static p256_digit addM(const p256_int* MOD, + p256_digit top, + p256_digit* c, + p256_digit mask) { + int i; + p256_ddigit carry = 0; + for (i = 0; i < P256_NDIGITS; ++i) { + carry += *c; + carry += P256_DIGIT(MOD, i) & mask; + *c++ = (p256_digit)carry; + carry >>= P256_BITSPERDIGIT; + } + return top + (p256_digit)carry; +} + +// c = a * b mod MOD. c can be a and/or b. +void p256_modmul(const p256_int* MOD, + const p256_int* a, + const p256_digit top_b, + const p256_int* b, + p256_int* c) { + p256_digit tmp[P256_NDIGITS * 2 + 1] = { 0 }; + p256_digit top = 0; + int i; + + // Multiply/add into tmp. + for (i = 0; i < P256_NDIGITS; ++i) { + if (i) tmp[i + P256_NDIGITS - 1] = top; + top = mulAdd(a, P256_DIGIT(b, i), 0, tmp + i); + } + + // Multiply/add top digit + tmp[i + P256_NDIGITS - 1] = top; + top = mulAdd(a, top_b, 0, tmp + i); + + // Reduce tmp, digit by digit. + for (; i >= 0; --i) { + p256_digit reducer[P256_NDIGITS] = { 0 }; + p256_digit top_reducer; + + // top can be any value at this point. + // Guestimate reducer as top * MOD, since msw of MOD is -1. + top_reducer = mulAdd(MOD, top, 0, reducer); + + // Subtract reducer from top | tmp. + top = subTop(top_reducer, reducer, top, tmp + i); + + // top is now either 0 or 1. Make it 0, fixed-timing. + assert(top <= 1); + + top = subM(MOD, top, tmp + i, ~(top - 1)); + + assert(top == 0); + + // We have now reduced the top digit off tmp. Fetch new top digit. + top = tmp[i + P256_NDIGITS - 1]; + } + + // tmp might still be larger than MOD, yet same bit length. + // Make sure it is less, fixed-timing. + addM(MOD, 0, tmp, subM(MOD, 0, tmp, -1)); + + memcpy(c, tmp, P256_NBYTES); +} +int p256_is_odd(const p256_int* a) { return P256_DIGIT(a, 0) & 1; } +int p256_is_even(const p256_int* a) { return !(P256_DIGIT(a, 0) & 1); } + +p256_digit p256_shl(const p256_int* a, int n, p256_int* b) { + int i; + p256_digit top = P256_DIGIT(a, P256_NDIGITS - 1); + + n %= P256_BITSPERDIGIT; + for (i = P256_NDIGITS - 1; i > 0; --i) { + p256_digit accu = (P256_DIGIT(a, i) << n); + accu |= (P256_DIGIT(a, i - 1) >> (P256_BITSPERDIGIT - n)); + P256_DIGIT(b, i) = accu; + } + P256_DIGIT(b, i) = (P256_DIGIT(a, i) << n); + + top = (p256_digit)((((p256_ddigit)top) << n) >> P256_BITSPERDIGIT); + + return top; +} + +void p256_shr(const p256_int* a, int n, p256_int* b) { + int i; + + n %= P256_BITSPERDIGIT; + for (i = 0; i < P256_NDIGITS - 1; ++i) { + p256_digit accu = (P256_DIGIT(a, i) >> n); + accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - n)); + P256_DIGIT(b, i) = accu; + } + P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> n); +} + +static void p256_shr1(const p256_int* a, int highbit, p256_int* b) { + int i; + + for (i = 0; i < P256_NDIGITS - 1; ++i) { + p256_digit accu = (P256_DIGIT(a, i) >> 1); + accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - 1)); + P256_DIGIT(b, i) = accu; + } + P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> 1) | + (highbit << (P256_BITSPERDIGIT - 1)); +} + +// Return -1, 0, 1 for a < b, a == b or a > b respectively. +int p256_cmp(const p256_int* a, const p256_int* b) { + int i; + p256_sddigit borrow = 0; + p256_digit notzero = 0; + + for (i = 0; i < P256_NDIGITS; ++i) { + borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i); + // Track whether any result digit is ever not zero. + // Relies on !!(non-zero) evaluating to 1, e.g., !!(-1) evaluating to 1. + notzero |= !!((p256_digit)borrow); + borrow >>= P256_BITSPERDIGIT; + } + return (int)borrow | notzero; +} + +// c = a - b. Returns borrow: 0 or -1. +int p256_sub(const p256_int* a, const p256_int* b, p256_int* c) { + int i; + p256_sddigit borrow = 0; + + for (i = 0; i < P256_NDIGITS; ++i) { + borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i); + if (c) P256_DIGIT(c, i) = (p256_digit)borrow; + borrow >>= P256_BITSPERDIGIT; + } + return (int)borrow; +} + +// c = a + b. Returns carry: 0 or 1. +int p256_add(const p256_int* a, const p256_int* b, p256_int* c) { + int i; + p256_ddigit carry = 0; + + for (i = 0; i < P256_NDIGITS; ++i) { + carry += (p256_ddigit)P256_DIGIT(a, i) + P256_DIGIT(b, i); + if (c) P256_DIGIT(c, i) = (p256_digit)carry; + carry >>= P256_BITSPERDIGIT; + } + return (int)carry; +} + +// b = a + d. Returns carry, 0 or 1. +int p256_add_d(const p256_int* a, p256_digit d, p256_int* b) { + int i; + p256_ddigit carry = d; + + for (i = 0; i < P256_NDIGITS; ++i) { + carry += (p256_ddigit)P256_DIGIT(a, i); + if (b) P256_DIGIT(b, i) = (p256_digit)carry; + carry >>= P256_BITSPERDIGIT; + } + return (int)carry; +} + +// b = 1/a mod MOD, binary euclid. +void p256_modinv_vartime(const p256_int* MOD, + const p256_int* a, + p256_int* b) { + p256_int R = P256_ZERO; + p256_int S = P256_ONE; + p256_int U = *MOD; + p256_int V = *a; + + for (;;) { + if (p256_is_even(&U)) { + p256_shr1(&U, 0, &U); + if (p256_is_even(&R)) { + p256_shr1(&R, 0, &R); + } else { + // R = (R+MOD)/2 + p256_shr1(&R, p256_add(&R, MOD, &R), &R); + } + } else if (p256_is_even(&V)) { + p256_shr1(&V, 0, &V); + if (p256_is_even(&S)) { + p256_shr1(&S, 0, &S); + } else { + // S = (S+MOD)/2 + p256_shr1(&S, p256_add(&S, MOD, &S) , &S); + } + } else { // U,V both odd. + if (!p256_sub(&V, &U, NULL)) { + p256_sub(&V, &U, &V); + if (p256_sub(&S, &R, &S)) p256_add(&S, MOD, &S); + if (p256_is_zero(&V)) break; // done. + } else { + p256_sub(&U, &V, &U); + if (p256_sub(&R, &S, &R)) p256_add(&R, MOD, &R); + } + } + } + + p256_mod(MOD, &R, b); +} + +void p256_mod(const p256_int* MOD, + const p256_int* in, + p256_int* out) { + if (out != in) *out = *in; + addM(MOD, 0, P256_DIGITS(out), subM(MOD, 0, P256_DIGITS(out), -1)); +} + +// Verify y^2 == x^3 - 3x + b mod p +// and 0 < x < p and 0 < y < p +int p256_is_valid_point(const p256_int* x, const p256_int* y) { + p256_int y2, x3; + + if (p256_cmp(&SECP256r1_p, x) <= 0 || + p256_cmp(&SECP256r1_p, y) <= 0 || + p256_is_zero(x) || + p256_is_zero(y)) return 0; + + p256_modmul(&SECP256r1_p, y, 0, y, &y2); // y^2 + + p256_modmul(&SECP256r1_p, x, 0, x, &x3); // x^2 + p256_modmul(&SECP256r1_p, x, 0, &x3, &x3); // x^3 + if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - x + if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - 2x + if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - 3x + if (p256_add(&x3, &SECP256r1_b, &x3)) // x^3 - 3x + b + p256_sub(&x3, &SECP256r1_p, &x3); + + return p256_cmp(&y2, &x3) == 0; +} + +void p256_from_bin(const uint8_t src[P256_NBYTES], p256_int* dst) { + int i; + const uint8_t* p = &src[0]; + + for (i = P256_NDIGITS - 1; i >= 0; --i) { + P256_DIGIT(dst, i) = + (p[0] << 24) | + (p[1] << 16) | + (p[2] << 8) | + p[3]; + p += 4; + } +} |