group.h
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 secp256k1_fe x; 18 secp256k1_fe y; 19 int infinity; /* whether this represents the point at infinity */ 20 } secp256k1_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 secp256k1_fe x; /* actual X: x/z^2 */ 30 secp256k1_fe y; /* actual Y: y/z^3 */ 31 secp256k1_fe z; 32 int infinity; /* whether this represents the point at infinity */ 33 } secp256k1_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 secp256k1_fe_storage x; 40 secp256k1_fe_storage y; 41 } secp256k1_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 secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_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 secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd); 61 62 /** Determine whether x is a valid X coordinate on the curve. */ 63 static int secp256k1_ge_x_on_curve_var(const secp256k1_fe *x); 64 65 /** Determine whether fraction xn/xd is a valid X coordinate on the curve (xd != 0). */ 66 static int secp256k1_ge_x_frac_on_curve_var(const secp256k1_fe *xn, const secp256k1_fe *xd); 67 68 /** Check whether a group element is the point at infinity. */ 69 static int secp256k1_ge_is_infinity(const secp256k1_ge *a); 70 71 /** Check whether a group element is valid (i.e., on the curve). */ 72 static int secp256k1_ge_is_valid_var(const secp256k1_ge *a); 73 74 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */ 75 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a); 76 77 /** Set a group element equal to another which is given in jacobian coordinates. Constant time. */ 78 static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a); 79 80 /** Set a group element equal to another which is given in jacobian coordinates. */ 81 static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a); 82 83 /** Set group elements r[0:len] (affine) equal to group elements a[0:len] (jacobian). 84 * None of the group elements in a[0:len] may be infinity. Constant time. */ 85 static void secp256k1_ge_set_all_gej(secp256k1_ge *r, const secp256k1_gej *a, size_t len); 86 87 /** Set group elements r[0:len] (affine) equal to group elements a[0:len] (jacobian). */ 88 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len); 89 90 /** Bring a batch of inputs to the same global z "denominator", based on ratios between 91 * (omitted) z coordinates of adjacent elements. 92 * 93 * Although the elements a[i] are _ge rather than _gej, they actually represent elements 94 * in Jacobian coordinates with their z coordinates omitted. 95 * 96 * Using the notation z(b) to represent the omitted z coordinate of b, the array zr of 97 * z coordinate ratios must satisfy zr[i] == z(a[i]) / z(a[i-1]) for 0 < 'i' < len. 98 * The zr[0] value is unused. 99 * 100 * This function adjusts the coordinates of 'a' in place so that for all 'i', z(a[i]) == z(a[len-1]). 101 * In other words, the initial value of z(a[len-1]) becomes the global z "denominator". Only the 102 * a[i].x and a[i].y coordinates are explicitly modified; the adjustment of the omitted z coordinate is 103 * implicit. 104 * 105 * The coordinates of the final element a[len-1] are not changed. 106 */ 107 static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr); 108 109 /** Check two group elements (affine) for equality in variable time. */ 110 static int secp256k1_ge_eq_var(const secp256k1_ge *a, const secp256k1_ge *b); 111 112 /** Set a group element (affine) equal to the point at infinity. */ 113 static void secp256k1_ge_set_infinity(secp256k1_ge *r); 114 115 /** Set a group element (jacobian) equal to the point at infinity. */ 116 static void secp256k1_gej_set_infinity(secp256k1_gej *r); 117 118 /** Set a group element (jacobian) equal to another which is given in affine coordinates. */ 119 static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a); 120 121 /** Check two group elements (jacobian) for equality in variable time. */ 122 static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b); 123 124 /** Check two group elements (jacobian and affine) for equality in variable time. */ 125 static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b); 126 127 /** Compare the X coordinate of a group element (jacobian). 128 * The magnitude of the group element's X coordinate must not exceed 31. */ 129 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a); 130 131 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */ 132 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a); 133 134 /** Check whether a group element is the point at infinity. */ 135 static int secp256k1_gej_is_infinity(const secp256k1_gej *a); 136 137 /** Set r equal to the double of a. Constant time. */ 138 static void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a); 139 140 /** 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). */ 141 static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr); 142 143 /** 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). */ 144 static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr); 145 146 /** Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity). */ 147 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b); 148 149 /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient 150 than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time 151 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). */ 152 static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr); 153 154 /** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */ 155 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv); 156 157 /** Set r to be equal to lambda times a, where lambda is chosen in a way such that this is very fast. */ 158 static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a); 159 160 /** Clear a secp256k1_gej to prevent leaking sensitive information. */ 161 static void secp256k1_gej_clear(secp256k1_gej *r); 162 163 /** Clear a secp256k1_ge to prevent leaking sensitive information. */ 164 static void secp256k1_ge_clear(secp256k1_ge *r); 165 166 /** Convert a group element to the storage type. */ 167 static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a); 168 169 /** Convert a group element back from the storage type. */ 170 static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a); 171 172 /** If flag is 1, set *r equal to *a; if flag is 0, leave it. Constant-time. 173 * Both *r and *a must be initialized. Flag must be 0 or 1. */ 174 static void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag); 175 176 /** If flag is 1, set *r equal to *a; if flag is 0, leave it. Constant-time. 177 * Both *r and *a must be initialized. Flag must be 0 or 1. */ 178 static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag); 179 180 /** Rescale a jacobian point by b which must be non-zero. Constant-time. */ 181 static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b); 182 183 /** Convert a group element that is not infinity to a 64-byte array. The output 184 * array is platform-dependent. */ 185 static void secp256k1_ge_to_bytes(unsigned char *buf, const secp256k1_ge *a); 186 187 /** Convert a 64-byte array into group element. This function assumes that the 188 * provided buffer correctly encodes a group element. */ 189 static void secp256k1_ge_from_bytes(secp256k1_ge *r, const unsigned char *buf); 190 191 /** Convert a group element (that is allowed to be infinity) to a 64-byte 192 * array. The output array is platform-dependent. */ 193 static void secp256k1_ge_to_bytes_ext(unsigned char *data, const secp256k1_ge *ge); 194 195 /** Convert a 64-byte array into a group element. This function assumes that the 196 * provided buffer is the output of secp256k1_ge_to_bytes_ext. */ 197 static void secp256k1_ge_from_bytes_ext(secp256k1_ge *ge, const unsigned char *data); 198 199 /** Determine if a point (which is assumed to be on the curve) is in the correct (sub)group of the curve. 200 * 201 * In normal mode, the used group is secp256k1, which has cofactor=1 meaning that every point on the curve is in the 202 * group, and this function returns always true. 203 * 204 * When compiling in exhaustive test mode, a slightly different curve equation is used, leading to a group with a 205 * (very) small subgroup, and that subgroup is what is used for all cryptographic operations. In that mode, this 206 * function checks whether a point that is on the curve is in fact also in that subgroup. 207 */ 208 static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge* ge); 209 210 /** Check invariants on an affine group element (no-op unless VERIFY is enabled). */ 211 static void secp256k1_ge_verify(const secp256k1_ge *a); 212 #define SECP256K1_GE_VERIFY(a) secp256k1_ge_verify(a) 213 214 /** Check invariants on a Jacobian group element (no-op unless VERIFY is enabled). */ 215 static void secp256k1_gej_verify(const secp256k1_gej *a); 216 #define SECP256K1_GEJ_VERIFY(a) secp256k1_gej_verify(a) 217 218 #endif /* SECP256K1_GROUP_H */