1  /***********************************************************************
  2   * Copyright (c) 2015 Andrew Poelstra                                  *
  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_REPR_IMPL_H
  8  #define SECP256K1_SCALAR_REPR_IMPL_H
  9  
 10  #include "checkmem.h"
 11  #include "scalar.h"
 12  #include "util.h"
 13  
 14  #include <string.h>
 15  
 16  SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) {
 17      SECP256K1_SCALAR_VERIFY(a);
 18  
 19      return !(*a & 1);
 20  }
 21  
 22  SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) {
 23      *r = v % EXHAUSTIVE_TEST_ORDER;
 24  
 25      SECP256K1_SCALAR_VERIFY(r);
 26  }
 27  
 28  SECP256K1_INLINE static uint32_t secp256k1_scalar_get_bits_limb32(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
 29      SECP256K1_SCALAR_VERIFY(a);
 30  
 31      VERIFY_CHECK(count > 0 && count <= 32);
 32      if (offset < 32) {
 33          return (*a >> offset) & (0xFFFFFFFF >> (32 - count));
 34      } else {
 35          return 0;
 36      }
 37  }
 38  
 39  SECP256K1_INLINE static uint32_t secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
 40      SECP256K1_SCALAR_VERIFY(a);
 41  
 42      return secp256k1_scalar_get_bits_limb32(a, offset, count);
 43  }
 44  
 45  SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) { return *a >= EXHAUSTIVE_TEST_ORDER; }
 46  
 47  static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
 48      SECP256K1_SCALAR_VERIFY(a);
 49      SECP256K1_SCALAR_VERIFY(b);
 50  
 51      *r = (*a + *b) % EXHAUSTIVE_TEST_ORDER;
 52  
 53      SECP256K1_SCALAR_VERIFY(r);
 54      return *r < *b;
 55  }
 56  
 57  static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) {
 58      SECP256K1_SCALAR_VERIFY(r);
 59      VERIFY_CHECK(flag == 0 || flag == 1);
 60  
 61      if (flag && bit < 32)
 62          *r += ((uint32_t)1 << bit);
 63  
 64      SECP256K1_SCALAR_VERIFY(r);
 65      VERIFY_CHECK(bit < 32);
 66      /* Verify that adding (1 << bit) will not overflow any in-range scalar *r by overflowing the underlying uint32_t. */
 67      VERIFY_CHECK(((uint32_t)1 << bit) - 1 <= UINT32_MAX - EXHAUSTIVE_TEST_ORDER);
 68  }
 69  
 70  static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow) {
 71      int i;
 72      int over = 0;
 73      *r = 0;
 74      for (i = 0; i < 32; i++) {
 75          *r = (*r * 0x100) + b32[i];
 76          if (*r >= EXHAUSTIVE_TEST_ORDER) {
 77              over = 1;
 78              *r %= EXHAUSTIVE_TEST_ORDER;
 79          }
 80      }
 81      if (overflow) *overflow = over;
 82  
 83      SECP256K1_SCALAR_VERIFY(r);
 84  }
 85  
 86  static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) {
 87      SECP256K1_SCALAR_VERIFY(a);
 88  
 89      memset(bin, 0, 32);
 90      bin[28] = *a >> 24; bin[29] = *a >> 16; bin[30] = *a >> 8; bin[31] = *a;
 91  }
 92  
 93  SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) {
 94      SECP256K1_SCALAR_VERIFY(a);
 95  
 96      return *a == 0;
 97  }
 98  
 99  static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) {
100      SECP256K1_SCALAR_VERIFY(a);
101  
102      if (*a == 0) {
103          *r = 0;
104      } else {
105          *r = EXHAUSTIVE_TEST_ORDER - *a;
106      }
107  
108      SECP256K1_SCALAR_VERIFY(r);
109  }
110  
111  SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) {
112      SECP256K1_SCALAR_VERIFY(a);
113  
114      return *a == 1;
115  }
116  
117  static int secp256k1_scalar_is_high(const secp256k1_scalar *a) {
118      SECP256K1_SCALAR_VERIFY(a);
119  
120      return *a > EXHAUSTIVE_TEST_ORDER / 2;
121  }
122  
123  static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) {
124      SECP256K1_SCALAR_VERIFY(r);
125      VERIFY_CHECK(flag == 0 || flag == 1);
126  
127      if (flag) secp256k1_scalar_negate(r, r);
128  
129      SECP256K1_SCALAR_VERIFY(r);
130      return flag ? -1 : 1;
131  }
132  
133  static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
134      SECP256K1_SCALAR_VERIFY(a);
135      SECP256K1_SCALAR_VERIFY(b);
136  
137      *r = (*a * *b) % EXHAUSTIVE_TEST_ORDER;
138  
139      SECP256K1_SCALAR_VERIFY(r);
140  }
141  
142  static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) {
143      SECP256K1_SCALAR_VERIFY(a);
144  
145      *r1 = *a;
146      *r2 = 0;
147  
148      SECP256K1_SCALAR_VERIFY(r1);
149      SECP256K1_SCALAR_VERIFY(r2);
150  }
151  
152  SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) {
153      SECP256K1_SCALAR_VERIFY(a);
154      SECP256K1_SCALAR_VERIFY(b);
155  
156      return *a == *b;
157  }
158  
159  static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
160      uint32_t mask0, mask1;
161      volatile int vflag = flag;
162      VERIFY_CHECK(flag == 0 || flag == 1);
163      SECP256K1_SCALAR_VERIFY(a);
164      SECP256K1_CHECKMEM_CHECK_VERIFY(r, sizeof(*r));
165  
166      mask0 = vflag + ~((uint32_t)0);
167      mask1 = ~mask0;
168      *r = (*r & mask0) | (*a & mask1);
169  
170      SECP256K1_SCALAR_VERIFY(r);
171  }
172  
173  static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) {
174      int i;
175      uint32_t res = 0;
176      SECP256K1_SCALAR_VERIFY(x);
177  
178      for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
179          if ((i * *x) % EXHAUSTIVE_TEST_ORDER == 1) {
180              res = i;
181              break;
182          }
183      }
184  
185      /* If this VERIFY_CHECK triggers we were given a noninvertible scalar (and thus
186       * have a composite group order; fix it in exhaustive_tests.c). */
187      VERIFY_CHECK(res != 0);
188      *r = res;
189  
190      SECP256K1_SCALAR_VERIFY(r);
191  }
192  
193  static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) {
194      SECP256K1_SCALAR_VERIFY(x);
195  
196      secp256k1_scalar_inverse(r, x);
197  
198      SECP256K1_SCALAR_VERIFY(r);
199  }
200  
201  static void secp256k1_scalar_half(secp256k1_scalar *r, const secp256k1_scalar *a) {
202      SECP256K1_SCALAR_VERIFY(a);
203  
204      *r = (*a + ((-(uint32_t)(*a & 1)) & EXHAUSTIVE_TEST_ORDER)) >> 1;
205  
206      SECP256K1_SCALAR_VERIFY(r);
207  }
208  
209  #endif /* SECP256K1_SCALAR_REPR_IMPL_H */