1 /********************************************************************** 2 * Copyright (c) 2013, 2014 Pieter Wuille * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.* 5 **********************************************************************/ 6 7 #ifndef _SECP256K1_FIELD_ 8 #define _SECP256K1_FIELD_ 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 #if defined(USE_FIELD_10X26) 26 #include "field_10x26.h" 27 #elif defined(USE_FIELD_5X52) 28 #include "field_5x52.h" 29 #else 30 #error "Please select field implementation" 31 #endif 32 33 #include "util.h" 34 35 /** Normalize a field element. */ 36 static void secp256k1_fe_normalize(secp256k1_fe *r); 37 38 /** Weakly normalize a field element: reduce it magnitude to 1, but don't fully normalize. */ 39 static void secp256k1_fe_normalize_weak(secp256k1_fe *r); 40 41 /** Normalize a field element, without constant-time guarantee. */ 42 static void secp256k1_fe_normalize_var(secp256k1_fe *r); 43 44 /** Verify whether a field element represents zero i.e. would normalize to a zero value. The field 45 * implementation may optionally normalize the input, but this should not be relied upon. */ 46 static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r); 47 48 /** Verify whether a field element represents zero i.e. would normalize to a zero value. The field 49 * implementation may optionally normalize the input, but this should not be relied upon. */ 50 static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r); 51 52 /** Set a field element equal to a small integer. Resulting field element is normalized. */ 53 static void secp256k1_fe_set_int(secp256k1_fe *r, int a); 54 55 /** Sets a field element equal to zero, initializing all fields. */ 56 static void secp256k1_fe_clear(secp256k1_fe *a); 57 58 /** Verify whether a field element is zero. Requires the input to be normalized. */ 59 static int secp256k1_fe_is_zero(const secp256k1_fe *a); 60 61 /** Check the "oddness" of a field element. Requires the input to be normalized. */ 62 static int secp256k1_fe_is_odd(const secp256k1_fe *a); 63 64 /** Compare two field elements. Requires magnitude-1 inputs. */ 65 static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b); 66 67 /** Same as secp256k1_fe_equal, but may be variable time. */ 68 static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b); 69 70 /** Compare two field elements. Requires both inputs to be normalized */ 71 static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b); 72 73 /** Set a field element equal to 32-byte big endian value. If successful, the resulting field element is normalized. */ 74 static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a); 75 76 /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */ 77 static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a); 78 79 /** Set a field element equal to the additive inverse of another. Takes a maximum magnitude of the input 80 * as an argument. The magnitude of the output is one higher. */ 81 static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m); 82 83 /** Multiplies the passed field element with a small integer constant. Multiplies the magnitude by that 84 * small integer. */ 85 static void secp256k1_fe_mul_int(secp256k1_fe *r, int a); 86 87 /** Adds a field element to another. The result has the sum of the inputs' magnitudes as magnitude. */ 88 static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a); 89 90 /** Sets a field element to be the product of two others. Requires the inputs' magnitudes to be at most 8. 91 * The output magnitude is 1 (but not guaranteed to be normalized). */ 92 static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b); 93 94 /** Sets a field element to be the square of another. Requires the input's magnitude to be at most 8. 95 * The output magnitude is 1 (but not guaranteed to be normalized). */ 96 static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a); 97 98 /** If a has a square root, it is computed in r and 1 is returned. If a does not 99 * have a square root, the root of its negation is computed and 0 is returned. 100 * The input's magnitude can be at most 8. The output magnitude is 1 (but not 101 * guaranteed to be normalized). The result in r will always be a square 102 * itself. */ 103 static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a); 104 105 /** Checks whether a field element is a quadratic residue. */ 106 // static int secp256k1_fe_is_quad_var(const secp256k1_fe *a); 107 108 /** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be 109 * at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */ 110 static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a); 111 112 /** Potentially faster version of secp256k1_fe_inv, without constant-time guarantee. */ 113 // static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a); 114 115 /** Calculate the (modular) inverses of a batch of field elements. Requires the inputs' magnitudes to be 116 * at most 8. The output magnitudes are 1 (but not guaranteed to be normalized). The inputs and 117 * outputs must not overlap in memory. */ 118 // static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len); 119 120 /** Convert a field element to the storage type. */ 121 static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a); 122 123 /** Convert a field element back from the storage type. */ 124 static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a); 125 126 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */ 127 static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag); 128 129 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */ 130 static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag); 131 132 #endif 133