field.h (17389B)
1 /*********************************************************************** 2 * Copyright (c) 2013, 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_FIELD_H 8 #define SECP256K1_FIELD_H 9 10 #include "util.h" 11 12 /* This file defines the generic interface for working with haskellsecp256k1_v0_1_0_fe 13 * objects, which represent field elements (integers modulo 2^256 - 2^32 - 977). 14 * 15 * The actual definition of the haskellsecp256k1_v0_1_0_fe type depends on the chosen field 16 * implementation; see the field_5x52.h and field_10x26.h files for details. 17 * 18 * All haskellsecp256k1_v0_1_0_fe objects have implicit properties that determine what 19 * operations are permitted on it. These are purely a function of what 20 * haskellsecp256k1_v0_1_0_fe_ operations are applied on it, generally (implicitly) fixed at 21 * compile time, and do not depend on the chosen field implementation. Despite 22 * that, what these properties actually entail for the field representation 23 * values depends on the chosen field implementation. These properties are: 24 * - magnitude: an integer in [0,32] 25 * - normalized: 0 or 1; normalized=1 implies magnitude <= 1. 26 * 27 * In VERIFY mode, they are materialized explicitly as fields in the struct, 28 * allowing run-time verification of these properties. In that case, the field 29 * implementation also provides a haskellsecp256k1_v0_1_0_fe_verify routine to verify that 30 * these fields match the run-time value and perform internal consistency 31 * checks. */ 32 #ifdef VERIFY 33 # define SECP256K1_FE_VERIFY_FIELDS \ 34 int magnitude; \ 35 int normalized; 36 #else 37 # define SECP256K1_FE_VERIFY_FIELDS 38 #endif 39 40 #if defined(SECP256K1_WIDEMUL_INT128) 41 #include "field_5x52.h" 42 #elif defined(SECP256K1_WIDEMUL_INT64) 43 #include "field_10x26.h" 44 #else 45 #error "Please select wide multiplication implementation" 46 #endif 47 48 #ifdef VERIFY 49 /* Magnitude and normalized value for constants. */ 50 #define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0) \ 51 /* Magnitude is 0 for constant 0; 1 otherwise. */ \ 52 , (((d7) | (d6) | (d5) | (d4) | (d3) | (d2) | (d1) | (d0)) != 0) \ 53 /* Normalized is 1 unless sum(d_i<<(32*i) for i=0..7) exceeds field modulus. */ \ 54 , (!(((d7) & (d6) & (d5) & (d4) & (d3) & (d2)) == 0xfffffffful && ((d1) == 0xfffffffful || ((d1) == 0xfffffffe && (d0 >= 0xfffffc2f))))) 55 #else 56 #define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0) 57 #endif 58 59 /** This expands to an initializer for a haskellsecp256k1_v0_1_0_fe valued sum((i*32) * d_i, i=0..7) mod p. 60 * 61 * It has magnitude 1, unless d_i are all 0, in which case the magnitude is 0. 62 * It is normalized, unless sum(2^(i*32) * d_i, i=0..7) >= p. 63 * 64 * SECP256K1_FE_CONST_INNER is provided by the implementation. 65 */ 66 #define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) SECP256K1_FE_VERIFY_CONST((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) } 67 68 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1); 69 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_const_beta = SECP256K1_FE_CONST( 70 0x7ae96a2bul, 0x657c0710ul, 0x6e64479eul, 0xac3434e9ul, 71 0x9cf04975ul, 0x12f58995ul, 0xc1396c28ul, 0x719501eeul 72 ); 73 74 #ifndef VERIFY 75 /* In non-VERIFY mode, we #define the fe operations to be identical to their 76 * internal field implementation, to avoid the potential overhead of a 77 * function call (even though presumably inlinable). */ 78 # define haskellsecp256k1_v0_1_0_fe_normalize haskellsecp256k1_v0_1_0_fe_impl_normalize 79 # define haskellsecp256k1_v0_1_0_fe_normalize_weak haskellsecp256k1_v0_1_0_fe_impl_normalize_weak 80 # define haskellsecp256k1_v0_1_0_fe_normalize_var haskellsecp256k1_v0_1_0_fe_impl_normalize_var 81 # define haskellsecp256k1_v0_1_0_fe_normalizes_to_zero haskellsecp256k1_v0_1_0_fe_impl_normalizes_to_zero 82 # define haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var haskellsecp256k1_v0_1_0_fe_impl_normalizes_to_zero_var 83 # define haskellsecp256k1_v0_1_0_fe_set_int haskellsecp256k1_v0_1_0_fe_impl_set_int 84 # define haskellsecp256k1_v0_1_0_fe_clear haskellsecp256k1_v0_1_0_fe_impl_clear 85 # define haskellsecp256k1_v0_1_0_fe_is_zero haskellsecp256k1_v0_1_0_fe_impl_is_zero 86 # define haskellsecp256k1_v0_1_0_fe_is_odd haskellsecp256k1_v0_1_0_fe_impl_is_odd 87 # define haskellsecp256k1_v0_1_0_fe_cmp_var haskellsecp256k1_v0_1_0_fe_impl_cmp_var 88 # define haskellsecp256k1_v0_1_0_fe_set_b32_mod haskellsecp256k1_v0_1_0_fe_impl_set_b32_mod 89 # define haskellsecp256k1_v0_1_0_fe_set_b32_limit haskellsecp256k1_v0_1_0_fe_impl_set_b32_limit 90 # define haskellsecp256k1_v0_1_0_fe_get_b32 haskellsecp256k1_v0_1_0_fe_impl_get_b32 91 # define haskellsecp256k1_v0_1_0_fe_negate_unchecked haskellsecp256k1_v0_1_0_fe_impl_negate_unchecked 92 # define haskellsecp256k1_v0_1_0_fe_mul_int_unchecked haskellsecp256k1_v0_1_0_fe_impl_mul_int_unchecked 93 # define haskellsecp256k1_v0_1_0_fe_add haskellsecp256k1_v0_1_0_fe_impl_add 94 # define haskellsecp256k1_v0_1_0_fe_mul haskellsecp256k1_v0_1_0_fe_impl_mul 95 # define haskellsecp256k1_v0_1_0_fe_sqr haskellsecp256k1_v0_1_0_fe_impl_sqr 96 # define haskellsecp256k1_v0_1_0_fe_cmov haskellsecp256k1_v0_1_0_fe_impl_cmov 97 # define haskellsecp256k1_v0_1_0_fe_to_storage haskellsecp256k1_v0_1_0_fe_impl_to_storage 98 # define haskellsecp256k1_v0_1_0_fe_from_storage haskellsecp256k1_v0_1_0_fe_impl_from_storage 99 # define haskellsecp256k1_v0_1_0_fe_inv haskellsecp256k1_v0_1_0_fe_impl_inv 100 # define haskellsecp256k1_v0_1_0_fe_inv_var haskellsecp256k1_v0_1_0_fe_impl_inv_var 101 # define haskellsecp256k1_v0_1_0_fe_get_bounds haskellsecp256k1_v0_1_0_fe_impl_get_bounds 102 # define haskellsecp256k1_v0_1_0_fe_half haskellsecp256k1_v0_1_0_fe_impl_half 103 # define haskellsecp256k1_v0_1_0_fe_add_int haskellsecp256k1_v0_1_0_fe_impl_add_int 104 # define haskellsecp256k1_v0_1_0_fe_is_square_var haskellsecp256k1_v0_1_0_fe_impl_is_square_var 105 #endif /* !defined(VERIFY) */ 106 107 /** Normalize a field element. 108 * 109 * On input, r must be a valid field element. 110 * On output, r represents the same value but has normalized=1 and magnitude=1. 111 */ 112 static void haskellsecp256k1_v0_1_0_fe_normalize(haskellsecp256k1_v0_1_0_fe *r); 113 114 /** Give a field element magnitude 1. 115 * 116 * On input, r must be a valid field element. 117 * On output, r represents the same value but has magnitude=1. Normalized is unchanged. 118 */ 119 static void haskellsecp256k1_v0_1_0_fe_normalize_weak(haskellsecp256k1_v0_1_0_fe *r); 120 121 /** Normalize a field element, without constant-time guarantee. 122 * 123 * Identical in behavior to haskellsecp256k1_v0_1_0_fe_normalize, but not constant time in r. 124 */ 125 static void haskellsecp256k1_v0_1_0_fe_normalize_var(haskellsecp256k1_v0_1_0_fe *r); 126 127 /** Determine whether r represents field element 0. 128 * 129 * On input, r must be a valid field element. 130 * Returns whether r = 0 (mod p). 131 */ 132 static int haskellsecp256k1_v0_1_0_fe_normalizes_to_zero(const haskellsecp256k1_v0_1_0_fe *r); 133 134 /** Determine whether r represents field element 0, without constant-time guarantee. 135 * 136 * Identical in behavior to haskellsecp256k1_v0_1_0_normalizes_to_zero, but not constant time in r. 137 */ 138 static int haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(const haskellsecp256k1_v0_1_0_fe *r); 139 140 /** Set a field element to an integer in range [0,0x7FFF]. 141 * 142 * On input, r does not need to be initialized, a must be in [0,0x7FFF]. 143 * On output, r represents value a, is normalized and has magnitude (a!=0). 144 */ 145 static void haskellsecp256k1_v0_1_0_fe_set_int(haskellsecp256k1_v0_1_0_fe *r, int a); 146 147 /** Set a field element to 0. 148 * 149 * On input, a does not need to be initialized. 150 * On output, a represents 0, is normalized and has magnitude 0. 151 */ 152 static void haskellsecp256k1_v0_1_0_fe_clear(haskellsecp256k1_v0_1_0_fe *a); 153 154 /** Determine whether a represents field element 0. 155 * 156 * On input, a must be a valid normalized field element. 157 * Returns whether a = 0 (mod p). 158 * 159 * This behaves identical to haskellsecp256k1_v0_1_0_normalizes_to_zero{,_var}, but requires 160 * normalized input (and is much faster). 161 */ 162 static int haskellsecp256k1_v0_1_0_fe_is_zero(const haskellsecp256k1_v0_1_0_fe *a); 163 164 /** Determine whether a (mod p) is odd. 165 * 166 * On input, a must be a valid normalized field element. 167 * Returns (int(a) mod p) & 1. 168 */ 169 static int haskellsecp256k1_v0_1_0_fe_is_odd(const haskellsecp256k1_v0_1_0_fe *a); 170 171 /** Determine whether two field elements are equal. 172 * 173 * On input, a and b must be valid field elements with magnitudes not exceeding 174 * 1 and 31, respectively. 175 * Returns a = b (mod p). 176 */ 177 static int haskellsecp256k1_v0_1_0_fe_equal(const haskellsecp256k1_v0_1_0_fe *a, const haskellsecp256k1_v0_1_0_fe *b); 178 179 /** Compare the values represented by 2 field elements, without constant-time guarantee. 180 * 181 * On input, a and b must be valid normalized field elements. 182 * Returns 1 if a > b, -1 if a < b, and 0 if a = b (comparisons are done as integers 183 * in range 0..p-1). 184 */ 185 static int haskellsecp256k1_v0_1_0_fe_cmp_var(const haskellsecp256k1_v0_1_0_fe *a, const haskellsecp256k1_v0_1_0_fe *b); 186 187 /** Set a field element equal to the element represented by a provided 32-byte big endian value 188 * interpreted modulo p. 189 * 190 * On input, r does not need to be initialized. a must be a pointer to an initialized 32-byte array. 191 * On output, r = a (mod p). It will have magnitude 1, and not be normalized. 192 */ 193 static void haskellsecp256k1_v0_1_0_fe_set_b32_mod(haskellsecp256k1_v0_1_0_fe *r, const unsigned char *a); 194 195 /** Set a field element equal to a provided 32-byte big endian value, checking for overflow. 196 * 197 * On input, r does not need to be initialized. a must be a pointer to an initialized 32-byte array. 198 * On output, r = a if (a < p), it will be normalized with magnitude 1, and 1 is returned. 199 * If a >= p, 0 is returned, and r will be made invalid (and must not be used without overwriting). 200 */ 201 static int haskellsecp256k1_v0_1_0_fe_set_b32_limit(haskellsecp256k1_v0_1_0_fe *r, const unsigned char *a); 202 203 /** Convert a field element to 32-byte big endian byte array. 204 * On input, a must be a valid normalized field element, and r a pointer to a 32-byte array. 205 * On output, r = a (mod p). 206 */ 207 static void haskellsecp256k1_v0_1_0_fe_get_b32(unsigned char *r, const haskellsecp256k1_v0_1_0_fe *a); 208 209 /** Negate a field element. 210 * 211 * On input, r does not need to be initialized. a must be a valid field element with 212 * magnitude not exceeding m. m must be an integer constant expression in [0,31]. 213 * Performs {r = -a}. 214 * On output, r will not be normalized, and will have magnitude m+1. 215 */ 216 #define haskellsecp256k1_v0_1_0_fe_negate(r, a, m) ASSERT_INT_CONST_AND_DO(m, haskellsecp256k1_v0_1_0_fe_negate_unchecked(r, a, m)) 217 218 /** Like haskellsecp256k1_v0_1_0_fe_negate_unchecked but m is not checked to be an integer constant expression. 219 * 220 * Should not be called directly outside of tests. 221 */ 222 static void haskellsecp256k1_v0_1_0_fe_negate_unchecked(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a, int m); 223 224 /** Add a small integer to a field element. 225 * 226 * Performs {r += a}. The magnitude of r increases by 1, and normalized is cleared. 227 * a must be in range [0,0x7FFF]. 228 */ 229 static void haskellsecp256k1_v0_1_0_fe_add_int(haskellsecp256k1_v0_1_0_fe *r, int a); 230 231 /** Multiply a field element with a small integer. 232 * 233 * On input, r must be a valid field element. a must be an integer constant expression in [0,32]. 234 * The magnitude of r times a must not exceed 32. 235 * Performs {r *= a}. 236 * On output, r's magnitude is multiplied by a, and r will not be normalized. 237 */ 238 #define haskellsecp256k1_v0_1_0_fe_mul_int(r, a) ASSERT_INT_CONST_AND_DO(a, haskellsecp256k1_v0_1_0_fe_mul_int_unchecked(r, a)) 239 240 /** Like haskellsecp256k1_v0_1_0_fe_mul_int but a is not checked to be an integer constant expression. 241 * 242 * Should not be called directly outside of tests. 243 */ 244 static void haskellsecp256k1_v0_1_0_fe_mul_int_unchecked(haskellsecp256k1_v0_1_0_fe *r, int a); 245 246 /** Increment a field element by another. 247 * 248 * On input, r and a must be valid field elements, not necessarily normalized. 249 * The sum of their magnitudes must not exceed 32. 250 * Performs {r += a}. 251 * On output, r will not be normalized, and will have magnitude incremented by a's. 252 */ 253 static void haskellsecp256k1_v0_1_0_fe_add(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a); 254 255 /** Multiply two field elements. 256 * 257 * On input, a and b must be valid field elements; r does not need to be initialized. 258 * r and a may point to the same object, but neither can be equal to b. The magnitudes 259 * of a and b must not exceed 8. 260 * Performs {r = a * b} 261 * On output, r will have magnitude 1, but won't be normalized. 262 */ 263 static void haskellsecp256k1_v0_1_0_fe_mul(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a, const haskellsecp256k1_v0_1_0_fe * SECP256K1_RESTRICT b); 264 265 /** Square a field element. 266 * 267 * On input, a must be a valid field element; r does not need to be initialized. The magnitude 268 * of a must not exceed 8. 269 * Performs {r = a**2} 270 * On output, r will have magnitude 1, but won't be normalized. 271 */ 272 static void haskellsecp256k1_v0_1_0_fe_sqr(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a); 273 274 /** Compute a square root of a field element. 275 * 276 * On input, a must be a valid field element with magnitude<=8; r need not be initialized. 277 * If sqrt(a) exists, performs {r = sqrt(a)} and returns 1. 278 * Otherwise, sqrt(-a) exists. The function performs {r = sqrt(-a)} and returns 0. 279 * The resulting value represented by r will be a square itself. 280 * Variables r and a must not point to the same object. 281 * On output, r will have magnitude 1 but will not be normalized. 282 */ 283 static int haskellsecp256k1_v0_1_0_fe_sqrt(haskellsecp256k1_v0_1_0_fe * SECP256K1_RESTRICT r, const haskellsecp256k1_v0_1_0_fe * SECP256K1_RESTRICT a); 284 285 /** Compute the modular inverse of a field element. 286 * 287 * On input, a must be a valid field element; r need not be initialized. 288 * Performs {r = a**(p-2)} (which maps 0 to 0, and every other element to its 289 * inverse). 290 * On output, r will have magnitude (a.magnitude != 0) and be normalized. 291 */ 292 static void haskellsecp256k1_v0_1_0_fe_inv(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a); 293 294 /** Compute the modular inverse of a field element, without constant-time guarantee. 295 * 296 * Behaves identically to haskellsecp256k1_v0_1_0_fe_inv, but is not constant-time in a. 297 */ 298 static void haskellsecp256k1_v0_1_0_fe_inv_var(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a); 299 300 /** Convert a field element to haskellsecp256k1_v0_1_0_fe_storage. 301 * 302 * On input, a must be a valid normalized field element. 303 * Performs {r = a}. 304 */ 305 static void haskellsecp256k1_v0_1_0_fe_to_storage(haskellsecp256k1_v0_1_0_fe_storage *r, const haskellsecp256k1_v0_1_0_fe *a); 306 307 /** Convert a field element back from haskellsecp256k1_v0_1_0_fe_storage. 308 * 309 * On input, r need not be initialized. 310 * Performs {r = a}. 311 * On output, r will be normalized and will have magnitude 1. 312 */ 313 static void haskellsecp256k1_v0_1_0_fe_from_storage(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe_storage *a); 314 315 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 316 static void haskellsecp256k1_v0_1_0_fe_storage_cmov(haskellsecp256k1_v0_1_0_fe_storage *r, const haskellsecp256k1_v0_1_0_fe_storage *a, int flag); 317 318 /** Conditionally move a field element in constant time. 319 * 320 * On input, both r and a must be valid field elements. Flag must be 0 or 1. 321 * Performs {r = flag ? a : r}. 322 * 323 * On output, r's magnitude will be the maximum of both input magnitudes. 324 * It will be normalized if and only if both inputs were normalized. 325 */ 326 static void haskellsecp256k1_v0_1_0_fe_cmov(haskellsecp256k1_v0_1_0_fe *r, const haskellsecp256k1_v0_1_0_fe *a, int flag); 327 328 /** Halve the value of a field element modulo the field prime in constant-time. 329 * 330 * On input, r must be a valid field element. 331 * On output, r will be normalized and have magnitude floor(m/2) + 1 where m is 332 * the magnitude of r on input. 333 */ 334 static void haskellsecp256k1_v0_1_0_fe_half(haskellsecp256k1_v0_1_0_fe *r); 335 336 /** Sets r to a field element with magnitude m, normalized if (and only if) m==0. 337 * The value is chosen so that it is likely to trigger edge cases related to 338 * internal overflows. */ 339 static void haskellsecp256k1_v0_1_0_fe_get_bounds(haskellsecp256k1_v0_1_0_fe *r, int m); 340 341 /** Determine whether a is a square (modulo p). 342 * 343 * On input, a must be a valid field element. 344 */ 345 static int haskellsecp256k1_v0_1_0_fe_is_square_var(const haskellsecp256k1_v0_1_0_fe *a); 346 347 /** Check invariants on a field element (no-op unless VERIFY is enabled). */ 348 static void haskellsecp256k1_v0_1_0_fe_verify(const haskellsecp256k1_v0_1_0_fe *a); 349 #define SECP256K1_FE_VERIFY(a) haskellsecp256k1_v0_1_0_fe_verify(a) 350 351 /** Check that magnitude of a is at most m (no-op unless VERIFY is enabled). */ 352 static void haskellsecp256k1_v0_1_0_fe_verify_magnitude(const haskellsecp256k1_v0_1_0_fe *a, int m); 353 #define SECP256K1_FE_VERIFY_MAGNITUDE(a, m) haskellsecp256k1_v0_1_0_fe_verify_magnitude(a, m) 354 355 #endif /* SECP256K1_FIELD_H */