src/group.h

   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_GROUP_H
   8 #define SECP256K1_GROUP_H
   9
  10 #include "num.h"
  11 #include "field.h"
  12
  13 /** A group element of the secp256k1 curve, in affine coordinates. */
  14 typedef struct {
  15     secp256k1_fe x;
  16     secp256k1_fe y;
  17     int infinity; /* whether this represents the point at infinity */
  18 } secp256k1_ge;
  19
  20 #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}
  21 #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}
  22
  23 /** A group element of the secp256k1 curve, in jacobian coordinates. */
  24 typedef struct {
  25     secp256k1_fe x; /* actual X: x/z^2 */
  26     secp256k1_fe y; /* actual Y: y/z^3 */
  27     secp256k1_fe z;
  28     int infinity; /* whether this represents the point at infinity */
  29 } secp256k1_gej;
  30
  31 #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}
  32 #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}
  33
  34 typedef struct {
  35     secp256k1_fe_storage x;
  36     secp256k1_fe_storage y;
  37 } secp256k1_ge_storage;
  38
  39 #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))}
  40
  41 #define SECP256K1_GE_STORAGE_CONST_GET(t) SECP256K1_FE_STORAGE_CONST_GET(t.x), SECP256K1_FE_STORAGE_CONST_GET(t.y)
  42
  43 /** Set a group element equal to the point with given X and Y coordinates */
  44 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y);
  45
  46 /** Set a group element (affine) equal to the point with the given X coordinate
  47  *  and a Y coordinate that is a quadratic residue modulo p. The return value
  48  *  is true iff a coordinate with the given X coordinate exists.
  49  */
  50 static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x);
  51
  52 /** Set a group element (affine) equal to the point with the given X coordinate, and given oddness
  53  *  for Y. Return value indicates whether the result is valid. */
  54 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd);
  55
  56 /** Check whether a group element is the point at infinity. */
  57 static int secp256k1_ge_is_infinity(const secp256k1_ge *a);
  58
  59 /** Check whether a group element is valid (i.e., on the curve). */
  60 static int secp256k1_ge_is_valid_var(const secp256k1_ge *a);
  61
  62 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */
  63 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a);
  64
  65 /** Set a group element equal to another which is given in jacobian coordinates */
  66 static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a);
  67
  68 /** Set a batch of group elements equal to the inputs given in jacobian coordinates */
  69 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len);
  70
  71 /** Bring a batch inputs given in jacobian coordinates (with known z-ratios) to
  72  *  the same global z "denominator". zr must contain the known z-ratios such
  73  *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored. The x and y
  74  *  coordinates of the result are stored in r, the common z coordinate is
  75  *  stored in globalz. */
  76 static void secp256k1_ge_globalz_set_table_gej(size_t len, secp256k1_ge *r, secp256k1_fe *globalz, const secp256k1_gej *a, const secp256k1_fe *zr);
  77
  78 /** Set a group element (affine) equal to the point at infinity. */
  79 static void secp256k1_ge_set_infinity(secp256k1_ge *r);
  80
  81 /** Set a group element (jacobian) equal to the point at infinity. */
  82 static void secp256k1_gej_set_infinity(secp256k1_gej *r);
  83
  84 /** Set a group element (jacobian) equal to another which is given in affine coordinates. */
  85 static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a);
  86
  87 /** Compare the X coordinate of a group element (jacobian). */
  88 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a);
  89
  90 /** Set r equal to the inverse of a (i.e., mirrored around the X axis) */
  91 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a);
  92
  93 /** Check whether a group element is the point at infinity. */
  94 static int secp256k1_gej_is_infinity(const secp256k1_gej *a);
  95
  96 /** Check whether a group element's y coordinate is a quadratic residue. */
  97 static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a);
  98
  99 /** Set r equal to the double of a. Constant time. */
 100 static void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a);
 101
 102 /** 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). */
 103 static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr);
 104
 105 /** 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). */
 106 static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr);
 107
 108 /** Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity). */
 109 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b);
 110
 111 /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient
 112     than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time
 113     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). */
 114 static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr);
 115
 116 /** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */
 117 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv);
 118
 119 #ifdef USE_ENDOMORPHISM
 120 /** Set r to be equal to lambda times a, where lambda is chosen in a way such that this is very fast. */
 121 static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a);
 122 #endif
 123
 124 /** Clear a secp256k1_gej to prevent leaking sensitive information. */
 125 static void secp256k1_gej_clear(secp256k1_gej *r);
 126
 127 /** Clear a secp256k1_ge to prevent leaking sensitive information. */
 128 static void secp256k1_ge_clear(secp256k1_ge *r);
 129
 130 /** Convert a group element to the storage type. */
 131 static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a);
 132
 133 /** Convert a group element back from the storage type. */
 134 static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a);
 135
 136 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 137 static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag);
 138
 139 /** Rescale a jacobian point by b which must be non-zero. Constant-time. */
 140 static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b);
 141
 142 #endif /* SECP256K1_GROUP_H */