group.h (12380B)
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_GROUP_H 8 #define SECP256K1_GROUP_H 9 10 #include "field.h" 11 12 /** A group element in affine coordinates on the secp256k1 curve, 13 * or occasionally on an isomorphic curve of the form y^2 = x^3 + 7*t^6. 14 * Note: For exhaustive test mode, secp256k1 is replaced by a small subgroup of a different curve. 15 */ 16 typedef struct { 17 haskellsecp256k1_v0_1_0_fe x; 18 haskellsecp256k1_v0_1_0_fe y; 19 int infinity; /* whether this represents the point at infinity */ 20 } haskellsecp256k1_v0_1_0_ge; 21 22 #define SECP256K1_GE_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) {SECP256K1_FE_CONST((a),(b),(c),(d),(e),(f),(g),(h)), SECP256K1_FE_CONST((i),(j),(k),(l),(m),(n),(o),(p)), 0} 23 #define SECP256K1_GE_CONST_INFINITY {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), 1} 24 25 /** A group element of the secp256k1 curve, in jacobian coordinates. 26 * Note: For exhastive test mode, secp256k1 is replaced by a small subgroup of a different curve. 27 */ 28 typedef struct { 29 haskellsecp256k1_v0_1_0_fe x; /* actual X: x/z^2 */ 30 haskellsecp256k1_v0_1_0_fe y; /* actual Y: y/z^3 */ 31 haskellsecp256k1_v0_1_0_fe z; 32 int infinity; /* whether this represents the point at infinity */ 33 } haskellsecp256k1_v0_1_0_gej; 34 35 #define SECP256K1_GEJ_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) {SECP256K1_FE_CONST((a),(b),(c),(d),(e),(f),(g),(h)), SECP256K1_FE_CONST((i),(j),(k),(l),(m),(n),(o),(p)), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1), 0} 36 #define SECP256K1_GEJ_CONST_INFINITY {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), 1} 37 38 typedef struct { 39 haskellsecp256k1_v0_1_0_fe_storage x; 40 haskellsecp256k1_v0_1_0_fe_storage y; 41 } haskellsecp256k1_v0_1_0_ge_storage; 42 43 #define SECP256K1_GE_STORAGE_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) {SECP256K1_FE_STORAGE_CONST((a),(b),(c),(d),(e),(f),(g),(h)), SECP256K1_FE_STORAGE_CONST((i),(j),(k),(l),(m),(n),(o),(p))} 44 45 #define SECP256K1_GE_STORAGE_CONST_GET(t) SECP256K1_FE_STORAGE_CONST_GET(t.x), SECP256K1_FE_STORAGE_CONST_GET(t.y) 46 47 /** Maximum allowed magnitudes for group element coordinates 48 * in affine (x, y) and jacobian (x, y, z) representation. */ 49 #define SECP256K1_GE_X_MAGNITUDE_MAX 4 50 #define SECP256K1_GE_Y_MAGNITUDE_MAX 3 51 #define SECP256K1_GEJ_X_MAGNITUDE_MAX 4 52 #define SECP256K1_GEJ_Y_MAGNITUDE_MAX 4 53 #define SECP256K1_GEJ_Z_MAGNITUDE_MAX 1 54 55 /** Set a group element equal to the point with given X and Y coordinates */ 56 static void haskellsecp256k1_v0_1_0_ge_set_xy(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_fe *y); 57 58 /** Set a group element (affine) equal to the point with the given X coordinate, and given oddness 59 * for Y. Return value indicates whether the result is valid. */ 60 static int haskellsecp256k1_v0_1_0_ge_set_xo_var(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_fe *x, int odd); 61 62 /** Determine whether x is a valid X coordinate on the curve. */ 63 static int haskellsecp256k1_v0_1_0_ge_x_on_curve_var(const haskellsecp256k1_v0_1_0_fe *x); 64 65 /** Determine whether fraction xn/xd is a valid X coordinate on the curve (xd != 0). */ 66 static int haskellsecp256k1_v0_1_0_ge_x_frac_on_curve_var(const haskellsecp256k1_v0_1_0_fe *xn, const haskellsecp256k1_v0_1_0_fe *xd); 67 68 /** Check whether a group element is the point at infinity. */ 69 static int haskellsecp256k1_v0_1_0_ge_is_infinity(const haskellsecp256k1_v0_1_0_ge *a); 70 71 /** Check whether a group element is valid (i.e., on the curve). */ 72 static int haskellsecp256k1_v0_1_0_ge_is_valid_var(const haskellsecp256k1_v0_1_0_ge *a); 73 74 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */ 75 static void haskellsecp256k1_v0_1_0_ge_neg(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge *a); 76 77 /** Set a group element equal to another which is given in jacobian coordinates. Constant time. */ 78 static void haskellsecp256k1_v0_1_0_ge_set_gej(haskellsecp256k1_v0_1_0_ge *r, haskellsecp256k1_v0_1_0_gej *a); 79 80 /** Set a group element equal to another which is given in jacobian coordinates. */ 81 static void haskellsecp256k1_v0_1_0_ge_set_gej_var(haskellsecp256k1_v0_1_0_ge *r, haskellsecp256k1_v0_1_0_gej *a); 82 83 /** Set a batch of group elements equal to the inputs given in jacobian coordinates */ 84 static void haskellsecp256k1_v0_1_0_ge_set_all_gej_var(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_gej *a, size_t len); 85 86 /** Bring a batch of inputs to the same global z "denominator", based on ratios between 87 * (omitted) z coordinates of adjacent elements. 88 * 89 * Although the elements a[i] are _ge rather than _gej, they actually represent elements 90 * in Jacobian coordinates with their z coordinates omitted. 91 * 92 * Using the notation z(b) to represent the omitted z coordinate of b, the array zr of 93 * z coordinate ratios must satisfy zr[i] == z(a[i]) / z(a[i-1]) for 0 < 'i' < len. 94 * The zr[0] value is unused. 95 * 96 * This function adjusts the coordinates of 'a' in place so that for all 'i', z(a[i]) == z(a[len-1]). 97 * In other words, the initial value of z(a[len-1]) becomes the global z "denominator". Only the 98 * a[i].x and a[i].y coordinates are explicitly modified; the adjustment of the omitted z coordinate is 99 * implicit. 100 * 101 * The coordinates of the final element a[len-1] are not changed. 102 */ 103 static void haskellsecp256k1_v0_1_0_ge_table_set_globalz(size_t len, haskellsecp256k1_v0_1_0_ge *a, const haskellsecp256k1_v0_1_0_fe *zr); 104 105 /** Check two group elements (affine) for equality in variable time. */ 106 static int haskellsecp256k1_v0_1_0_ge_eq_var(const haskellsecp256k1_v0_1_0_ge *a, const haskellsecp256k1_v0_1_0_ge *b); 107 108 /** Set a group element (affine) equal to the point at infinity. */ 109 static void haskellsecp256k1_v0_1_0_ge_set_infinity(haskellsecp256k1_v0_1_0_ge *r); 110 111 /** Set a group element (jacobian) equal to the point at infinity. */ 112 static void haskellsecp256k1_v0_1_0_gej_set_infinity(haskellsecp256k1_v0_1_0_gej *r); 113 114 /** Set a group element (jacobian) equal to another which is given in affine coordinates. */ 115 static void haskellsecp256k1_v0_1_0_gej_set_ge(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_ge *a); 116 117 /** Check two group elements (jacobian) for equality in variable time. */ 118 static int haskellsecp256k1_v0_1_0_gej_eq_var(const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_gej *b); 119 120 /** Check two group elements (jacobian and affine) for equality in variable time. */ 121 static int haskellsecp256k1_v0_1_0_gej_eq_ge_var(const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b); 122 123 /** Compare the X coordinate of a group element (jacobian). 124 * The magnitude of the group element's X coordinate must not exceed 31. */ 125 static int haskellsecp256k1_v0_1_0_gej_eq_x_var(const haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_gej *a); 126 127 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */ 128 static void haskellsecp256k1_v0_1_0_gej_neg(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a); 129 130 /** Check whether a group element is the point at infinity. */ 131 static int haskellsecp256k1_v0_1_0_gej_is_infinity(const haskellsecp256k1_v0_1_0_gej *a); 132 133 /** Set r equal to the double of a. Constant time. */ 134 static void haskellsecp256k1_v0_1_0_gej_double(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a); 135 136 /** Set r equal to the double of a. If rzr is not-NULL this sets *rzr such that r->z == a->z * *rzr (where infinity means an implicit z = 0). */ 137 static void haskellsecp256k1_v0_1_0_gej_double_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, haskellsecp256k1_v0_1_0_fe *rzr); 138 139 /** Set r equal to the sum of a and b. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ 140 static void haskellsecp256k1_v0_1_0_gej_add_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_gej *b, haskellsecp256k1_v0_1_0_fe *rzr); 141 142 /** Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity). */ 143 static void haskellsecp256k1_v0_1_0_gej_add_ge(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b); 144 145 /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient 146 than haskellsecp256k1_v0_1_0_gej_add_var. It is identical to haskellsecp256k1_v0_1_0_gej_add_ge but without constant-time 147 guarantee, and b is allowed to be infinity. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ 148 static void haskellsecp256k1_v0_1_0_gej_add_ge_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b, haskellsecp256k1_v0_1_0_fe *rzr); 149 150 /** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */ 151 static void haskellsecp256k1_v0_1_0_gej_add_zinv_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b, const haskellsecp256k1_v0_1_0_fe *bzinv); 152 153 /** Set r to be equal to lambda times a, where lambda is chosen in a way such that this is very fast. */ 154 static void haskellsecp256k1_v0_1_0_ge_mul_lambda(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge *a); 155 156 /** Clear a haskellsecp256k1_v0_1_0_gej to prevent leaking sensitive information. */ 157 static void haskellsecp256k1_v0_1_0_gej_clear(haskellsecp256k1_v0_1_0_gej *r); 158 159 /** Clear a haskellsecp256k1_v0_1_0_ge to prevent leaking sensitive information. */ 160 static void haskellsecp256k1_v0_1_0_ge_clear(haskellsecp256k1_v0_1_0_ge *r); 161 162 /** Convert a group element to the storage type. */ 163 static void haskellsecp256k1_v0_1_0_ge_to_storage(haskellsecp256k1_v0_1_0_ge_storage *r, const haskellsecp256k1_v0_1_0_ge *a); 164 165 /** Convert a group element back from the storage type. */ 166 static void haskellsecp256k1_v0_1_0_ge_from_storage(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge_storage *a); 167 168 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 169 static void haskellsecp256k1_v0_1_0_gej_cmov(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, int flag); 170 171 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ 172 static void haskellsecp256k1_v0_1_0_ge_storage_cmov(haskellsecp256k1_v0_1_0_ge_storage *r, const haskellsecp256k1_v0_1_0_ge_storage *a, int flag); 173 174 /** Rescale a jacobian point by b which must be non-zero. Constant-time. */ 175 static void haskellsecp256k1_v0_1_0_gej_rescale(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_fe *b); 176 177 /** Determine if a point (which is assumed to be on the curve) is in the correct (sub)group of the curve. 178 * 179 * In normal mode, the used group is secp256k1, which has cofactor=1 meaning that every point on the curve is in the 180 * group, and this function returns always true. 181 * 182 * When compiling in exhaustive test mode, a slightly different curve equation is used, leading to a group with a 183 * (very) small subgroup, and that subgroup is what is used for all cryptographic operations. In that mode, this 184 * function checks whether a point that is on the curve is in fact also in that subgroup. 185 */ 186 static int haskellsecp256k1_v0_1_0_ge_is_in_correct_subgroup(const haskellsecp256k1_v0_1_0_ge* ge); 187 188 /** Check invariants on an affine group element (no-op unless VERIFY is enabled). */ 189 static void haskellsecp256k1_v0_1_0_ge_verify(const haskellsecp256k1_v0_1_0_ge *a); 190 #define SECP256K1_GE_VERIFY(a) haskellsecp256k1_v0_1_0_ge_verify(a) 191 192 /** Check invariants on a Jacobian group element (no-op unless VERIFY is enabled). */ 193 static void haskellsecp256k1_v0_1_0_gej_verify(const haskellsecp256k1_v0_1_0_gej *a); 194 #define SECP256K1_GEJ_VERIFY(a) haskellsecp256k1_v0_1_0_gej_verify(a) 195 196 #endif /* SECP256K1_GROUP_H */