1 /*********************************************************************** 2 * Copyright (c) 2014 Pieter Wuille * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 5 ***********************************************************************/ 6 7 #ifndef SECP256K1_SCALAR_H 8 #define SECP256K1_SCALAR_H 9 10 #include "util.h" 11 12 #if defined HAVE_CONFIG_H 13 #include "libsecp256k1-config.h" 14 #endif 15 16 #if defined(EXHAUSTIVE_TEST_ORDER) 17 #include "scalar_low.h" 18 #elif defined(SECP256K1_WIDEMUL_INT128) 19 #include "scalar_4x64.h" 20 #elif defined(SECP256K1_WIDEMUL_INT64) 21 #include "scalar_8x32.h" 22 #else 23 #error "Please select wide multiplication implementation" 24 #endif 25 26 /** Clear a scalar to prevent the leak of sensitive data. */ 27 static void secp256k1_scalar_clear(secp256k1_scalar *r); 28 29 /** Access bits from a scalar. All requested bits must belong to the same 32-bit limb. */ 30 static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count); 31 32 /** Access bits from a scalar. Not constant time. */ 33 static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count); 34 35 /** Set a scalar from a big endian byte array. The scalar will be reduced modulo group order `n`. 36 * In: bin: pointer to a 32-byte array. 37 * Out: r: scalar to be set. 38 * overflow: non-zero if the scalar was bigger or equal to `n` before reduction, zero otherwise (can be NULL). 39 */ 40 static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow); 41 42 /** Set a scalar from a big endian byte array and returns 1 if it is a valid 43 * seckey and 0 otherwise. */ 44 static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin); 45 46 /** Set a scalar to an unsigned integer. */ 47 static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v); 48 49 /** Convert a scalar to a byte array. */ 50 static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a); 51 52 /** Add two scalars together (modulo the group order). Returns whether it overflowed. */ 53 static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b); 54 55 /** Conditionally add a power of two to a scalar. The result is not allowed to overflow. */ 56 static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag); 57 58 /** Multiply two scalars (modulo the group order). */ 59 static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b); 60 61 /** Shift a scalar right by some amount strictly between 0 and 16, returning 62 * the low bits that were shifted off */ 63 static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n); 64 65 /** Compute the inverse of a scalar (modulo the group order). */ 66 static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *a); 67 68 /** Compute the inverse of a scalar (modulo the group order), without constant-time guarantee. */ 69 static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *a); 70 71 /** Compute the complement of a scalar (modulo the group order). */ 72 static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a); 73 74 /** Check whether a scalar equals zero. */ 75 static int secp256k1_scalar_is_zero(const secp256k1_scalar *a); 76 77 /** Check whether a scalar equals one. */ 78 static int secp256k1_scalar_is_one(const secp256k1_scalar *a); 79 80 /** Check whether a scalar, considered as an nonnegative integer, is even. */ 81 static int secp256k1_scalar_is_even(const secp256k1_scalar *a); 82 83 /** Check whether a scalar is higher than the group order divided by 2. */ 84 static int secp256k1_scalar_is_high(const secp256k1_scalar *a); 85 86 /** Conditionally negate a number, in constant time. 87 * Returns -1 if the number was negated, 1 otherwise */ 88 static int secp256k1_scalar_cond_negate(secp256k1_scalar *a, int flag); 89 90 /** Compare two scalars. */ 91 static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b); 92 93 /** Find r1 and r2 such that r1+r2*2^128 = k. */ 94 static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k); 95 /** Find r1 and r2 such that r1+r2*lambda = k, 96 * where r1 and r2 or their negations are maximum 128 bits long (see secp256k1_ge_mul_lambda). */ 97 static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k); 98 99 /** Multiply a and b (without taking the modulus!), divide by 2**shift, and round to the nearest integer. Shift must be at least 256. */ 100 static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift); 101 102 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 103 static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag); 104 105 #endif /* SECP256K1_SCALAR_H */ 106