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 /** Field element module. 11 * 12 * Field elements can be represented in several ways, but code accessing 13 * it (and implementations) need to take certain properties into account: 14 * - Each field element can be normalized or not. 15 * - Each field element has a magnitude, which represents how far away 16 * its representation is away from normalization. Normalized elements 17 * always have a magnitude of 1, but a magnitude of 1 doesn't imply 18 * normality. 19 */ 20 21 #if defined HAVE_CONFIG_H 22 #include "libsecp256k1-config.h" 23 #endif 24 25 #include "util.h" 26 27 #if defined(SECP256K1_WIDEMUL_INT128) 28 #include "field_5x52.h" 29 #elif defined(SECP256K1_WIDEMUL_INT64) 30 #include "field_10x26.h" 31 #else 32 #error "Please select wide multiplication implementation" 33 #endif 34 35 /** Normalize a field element. This brings the field element to a canonical representation, reduces 36 * its magnitude to 1, and reduces it modulo field size `p`. 37 */ 38 static void rustsecp256k1_v0_4_1_fe_normalize(rustsecp256k1_v0_4_1_fe *r); 39 40 /** Weakly normalize a field element: reduce its magnitude to 1, but don't fully normalize. */ 41 static void rustsecp256k1_v0_4_1_fe_normalize_weak(rustsecp256k1_v0_4_1_fe *r); 42 43 /** Normalize a field element, without constant-time guarantee. */ 44 static void rustsecp256k1_v0_4_1_fe_normalize_var(rustsecp256k1_v0_4_1_fe *r); 45 46 /** Verify whether a field element represents zero i.e. would normalize to a zero value. */ 47 static int rustsecp256k1_v0_4_1_fe_normalizes_to_zero(const rustsecp256k1_v0_4_1_fe *r); 48 49 /** Verify whether a field element represents zero i.e. would normalize to a zero value, 50 * without constant-time guarantee. */ 51 static int rustsecp256k1_v0_4_1_fe_normalizes_to_zero_var(const rustsecp256k1_v0_4_1_fe *r); 52 53 /** Set a field element equal to a small integer. Resulting field element is normalized. */ 54 static void rustsecp256k1_v0_4_1_fe_set_int(rustsecp256k1_v0_4_1_fe *r, int a); 55 56 /** Sets a field element equal to zero, initializing all fields. */ 57 static void rustsecp256k1_v0_4_1_fe_clear(rustsecp256k1_v0_4_1_fe *a); 58 59 /** Verify whether a field element is zero. Requires the input to be normalized. */ 60 static int rustsecp256k1_v0_4_1_fe_is_zero(const rustsecp256k1_v0_4_1_fe *a); 61 62 /** Check the "oddness" of a field element. Requires the input to be normalized. */ 63 static int rustsecp256k1_v0_4_1_fe_is_odd(const rustsecp256k1_v0_4_1_fe *a); 64 65 /** Compare two field elements. Requires magnitude-1 inputs. */ 66 static int rustsecp256k1_v0_4_1_fe_equal(const rustsecp256k1_v0_4_1_fe *a, const rustsecp256k1_v0_4_1_fe *b); 67 68 /** Same as rustsecp256k1_v0_4_1_fe_equal, but may be variable time. */ 69 static int rustsecp256k1_v0_4_1_fe_equal_var(const rustsecp256k1_v0_4_1_fe *a, const rustsecp256k1_v0_4_1_fe *b); 70 71 /** Compare two field elements. Requires both inputs to be normalized */ 72 static int rustsecp256k1_v0_4_1_fe_cmp_var(const rustsecp256k1_v0_4_1_fe *a, const rustsecp256k1_v0_4_1_fe *b); 73 74 /** Set a field element equal to 32-byte big endian value. If successful, the resulting field element is normalized. */ 75 static int rustsecp256k1_v0_4_1_fe_set_b32(rustsecp256k1_v0_4_1_fe *r, const unsigned char *a); 76 77 /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */ 78 static void rustsecp256k1_v0_4_1_fe_get_b32(unsigned char *r, const rustsecp256k1_v0_4_1_fe *a); 79 80 /** Set a field element equal to the additive inverse of another. Takes a maximum magnitude of the input 81 * as an argument. The magnitude of the output is one higher. */ 82 static void rustsecp256k1_v0_4_1_fe_negate(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a, int m); 83 84 /** Multiplies the passed field element with a small integer constant. Multiplies the magnitude by that 85 * small integer. */ 86 static void rustsecp256k1_v0_4_1_fe_mul_int(rustsecp256k1_v0_4_1_fe *r, int a); 87 88 /** Adds a field element to another. The result has the sum of the inputs' magnitudes as magnitude. */ 89 static void rustsecp256k1_v0_4_1_fe_add(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a); 90 91 /** Sets a field element to be the product of two others. Requires the inputs' magnitudes to be at most 8. 92 * The output magnitude is 1 (but not guaranteed to be normalized). */ 93 static void rustsecp256k1_v0_4_1_fe_mul(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a, const rustsecp256k1_v0_4_1_fe * SECP256K1_RESTRICT b); 94 95 /** Sets a field element to be the square of another. Requires the input's magnitude to be at most 8. 96 * The output magnitude is 1 (but not guaranteed to be normalized). */ 97 static void rustsecp256k1_v0_4_1_fe_sqr(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a); 98 99 /** If a has a square root, it is computed in r and 1 is returned. If a does not 100 * have a square root, the root of its negation is computed and 0 is returned. 101 * The input's magnitude can be at most 8. The output magnitude is 1 (but not 102 * guaranteed to be normalized). The result in r will always be a square 103 * itself. */ 104 static int rustsecp256k1_v0_4_1_fe_sqrt(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a); 105 106 /** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be 107 * at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */ 108 static void rustsecp256k1_v0_4_1_fe_inv(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a); 109 110 /** Potentially faster version of rustsecp256k1_v0_4_1_fe_inv, without constant-time guarantee. */ 111 static void rustsecp256k1_v0_4_1_fe_inv_var(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a); 112 113 /** Convert a field element to the storage type. */ 114 static void rustsecp256k1_v0_4_1_fe_to_storage(rustsecp256k1_v0_4_1_fe_storage *r, const rustsecp256k1_v0_4_1_fe *a); 115 116 /** Convert a field element back from the storage type. */ 117 static void rustsecp256k1_v0_4_1_fe_from_storage(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe_storage *a); 118 119 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 120 static void rustsecp256k1_v0_4_1_fe_storage_cmov(rustsecp256k1_v0_4_1_fe_storage *r, const rustsecp256k1_v0_4_1_fe_storage *a, int flag); 121 122 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 123 static void rustsecp256k1_v0_4_1_fe_cmov(rustsecp256k1_v0_4_1_fe *r, const rustsecp256k1_v0_4_1_fe *a, int flag); 124 125 #endif /* SECP256K1_FIELD_H */ 126