ecc.h

   1 /* ecc.h */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #ifndef NETTLE_ECC_H_INCLUDED
  26 #define NETTLE_ECC_H_INCLUDED
  27
  28 #include <gmp.h>
  29
  30 #include "nettle-types.h"
  31
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif
  35
  36 /* Name mangling */
  37 #define ecc_point_init nettle_ecc_point_init
  38 #define ecc_point_clear nettle_ecc_point_clear
  39 #define ecc_point_set nettle_ecc_point_set
  40 #define ecc_point_get nettle_ecc_point_get
  41 #define ecc_point_mul nettle_ecc_point_mul
  42 #define ecc_point_mul_g nettle_ecc_point_mul_g
  43 #define ecc_scalar_init nettle_ecc_scalar_init
  44 #define ecc_scalar_clear nettle_ecc_scalar_clear
  45 #define ecc_scalar_set nettle_ecc_scalar_set
  46 #define ecc_scalar_get nettle_ecc_scalar_get
  47 #define ecc_scalar_random nettle_ecc_scalar_random
  48 #define ecc_point_mul nettle_ecc_point_mul
  49 #define ecc_size nettle_ecc_size
  50 #define ecc_size_a nettle_ecc_size_a
  51 #define ecc_size_j nettle_ecc_size_j
  52 #define ecc_a_to_a_itch nettle_ecc_a_to_a_itch
  53 #define ecc_a_to_a nettle_ecc_a_to_a
  54 #define ecc_a_to_j nettle_ecc_a_to_j
  55 #define ecc_j_to_a_itch nettle_ecc_j_to_a_itch
  56 #define ecc_j_to_a nettle_ecc_j_to_a
  57 #define ecc_dup_ja_itch nettle_ecc_dup_ja_itch
  58 #define ecc_dup_ja nettle_ecc_dup_ja
  59 #define ecc_dup_jj_itch nettle_ecc_dup_jj_itch
  60 #define ecc_dup_jj nettle_ecc_dup_jj
  61 #define ecc_add_jja_itch nettle_ecc_add_jja_itch
  62 #define ecc_add_jja nettle_ecc_add_jja
  63 #define ecc_add_jjj_itch nettle_ecc_add_jjj_itch
  64 #define ecc_add_jjj nettle_ecc_add_jjj
  65 #define ecc_mul_g_itch nettle_ecc_mul_g_itch
  66 #define ecc_mul_g nettle_ecc_mul_g
  67 #define ecc_mul_a_itch nettle_ecc_mul_a_itch
  68 #define ecc_mul_a nettle_ecc_mul_a
  69
  70 struct ecc_curve;
  71
  72 /* High level interface, for ECDSA, DH, etc */
  73
  74 /* Represents a point on the ECC curve */
  75 struct ecc_point
  76 {
  77   const struct ecc_curve *ecc;
  78   /* Allocated using the same allocation function as GMP. */
  79   mp_limb_t *p;
  80 };
  81
  82 /* Represents a non-zero scalar, an element of Z_q^*, where q is the
  83    group order of the curve. */
  84 struct ecc_scalar
  85 {
  86   const struct ecc_curve *ecc;
  87   /* Allocated using the same allocation function as GMP. */
  88   mp_limb_t *p;
  89 };
  90
  91 void
  92 ecc_point_init (struct ecc_point *p, const struct ecc_curve *ecc);
  93 void
  94 ecc_point_clear (struct ecc_point *p);
  95
  96 /* Fails and returns zero if the point is not on the curve. */
  97 int
  98 ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y);
  99 void
 100 ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y);
 101
 102 void
 103 ecc_scalar_init (struct ecc_scalar *s, const struct ecc_curve *ecc);
 104 void
 105 ecc_scalar_clear (struct ecc_scalar *s);
 106
 107 /* Fails and returns zero if the scalar is not in the proper range. */
 108 int
 109 ecc_scalar_set (struct ecc_scalar *s, const mpz_t z);
 110 void
 111 ecc_scalar_get (const struct ecc_scalar *s, mpz_t z);
 112 /* Generates a random scalar, suitable as an ECDSA private key or a
 113    ECDH exponent. */
 114 void
 115 ecc_scalar_random (struct ecc_scalar *s,
 116                    void *random_ctx, nettle_random_func *random);
 117
 118 /* Computes r = n p */
 119 void
 120 ecc_point_mul (struct ecc_point *r, const struct ecc_scalar *n,
 121                const struct ecc_point *p);
 122
 123 /* Computes r = n g */
 124 void
 125 ecc_point_mul_g (struct ecc_point *r, const struct ecc_scalar *n);
 126
 127 \f
 128 /* Low-level interface */
 129
 130 /* Points on a curve are represented as arrays of mp_limb_t. For some
 131    curves, point coordinates are represented in montgomery form. We
 132    use either affine coordinates x,y, or Jacobian coordinates X, Y, Z,
 133    where x = X/Z^2 and y = X/Z^2.
 134
 135    Since we use additive notation for the groups, the infinity point
 136    on the curve is denoted 0. The infinity point can be represented
 137    with x = y = 0 in affine coordinates, and Z = 0 in Jacobian
 138    coordinates. However, note that most of the ECC functions do *not*
 139    support infinity as an input or output.
 140 */
 141
 142 /* FIXME: Also provided some compile time constants? */
 143
 144 /* Returns the size of a single coordinate. */
 145 mp_size_t
 146 ecc_size (const struct ecc_curve *ecc);
 147
 148 /* Size of a point, using affine coordinates x, y. */
 149 mp_size_t
 150 ecc_size_a (const struct ecc_curve *ecc);
 151
 152 /* Size of a point, using jacobian coordinates X, Y and Z. */
 153 mp_size_t
 154 ecc_size_j (const struct ecc_curve *ecc);
 155
 156 /* FIXME: Rename the low-level (and side-channel silent) functions to
 157    _ecc_*, and provide public ecc_* functions which handle the
 158    infinity points properly? */
 159
 160 /* Converts the affine coordinates of a point into montgomery form, if
 161    used for this curve. */
 162 mp_size_t
 163 ecc_a_to_a_itch (const struct ecc_curve *ecc);
 164 void
 165 ecc_a_to_a (const struct ecc_curve *ecc,
 166             mp_limb_t *r, const mp_limb_t *p,
 167             mp_limb_t *scratch);
 168
 169 /* Converts a point P in affine coordinates into a point R in jacobian
 170    coordinates. If INITIAL is non-zero, and the curve uses montgomery
 171    coordinates, also convert coordinates to montgomery form. */
 172 void
 173 ecc_a_to_j (const struct ecc_curve *ecc,
 174             int initial,
 175             mp_limb_t *r, const mp_limb_t *p);
 176
 177 /* Converts a point P in jacobian coordinates into a point R in affine
 178    coordinates. If FLAGS has bit 0 set, and the curve uses montgomery
 179    coordinates, also undo the montgomery conversion. If flags has bit
 180    1 set, produce x coordinate only. */
 181 mp_size_t
 182 ecc_j_to_a_itch (const struct ecc_curve *ecc);
 183 void
 184 ecc_j_to_a (const struct ecc_curve *ecc,
 185             int flags,
 186             mp_limb_t *r, const mp_limb_t *p,
 187             mp_limb_t *scratch);
 188
 189 /* Group operations */
 190
 191
 192 /* Point doubling, with jacobian output and affine input. Corner
 193    cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
 194 mp_size_t
 195 ecc_dup_ja_itch (const struct ecc_curve *ecc);
 196 void
 197 ecc_dup_ja (const struct ecc_curve *ecc,
 198             mp_limb_t *r, const mp_limb_t *p,
 199             mp_limb_t *scratch);
 200
 201 /* Point doubling, with jacobian input and output. Corner cases:
 202    Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
 203 mp_size_t
 204 ecc_dup_jj_itch (const struct ecc_curve *ecc);
 205 void
 206 ecc_dup_jj (const struct ecc_curve *ecc,
 207             mp_limb_t *r, const mp_limb_t *p,
 208             mp_limb_t *scratch);
 209
 210
 211 /* Point addition, with jacobian output, one jacobian input and one
 212    affine input. Corner cases: Fails for the cases
 213
 214      P = Q != 0                       Duplication of non-zero point
 215      P = 0, Q != 0 or P != 0, Q = 0   One input zero
 216
 217      Correctly gives R = 0 if P = Q = 0 or P = -Q. */
 218 mp_size_t
 219 ecc_add_jja_itch (const struct ecc_curve *ecc);
 220 void
 221 ecc_add_jja (const struct ecc_curve *ecc,
 222              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 223              mp_limb_t *scratch);
 224
 225 /* Point addition with Jacobian input and output. */
 226 mp_size_t
 227 ecc_add_jjj_itch (const struct ecc_curve *ecc);
 228 void
 229 ecc_add_jjj (const struct ecc_curve *ecc,
 230              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 231              mp_limb_t *scratch);
 232
 233
 234 /* Computes N * the group generator. N is an array of ecc_size()
 235    limbs. It must be in the range 0 < N < group order, then R != 0,
 236    and the algorithm can work without any intermediate values getting
 237    to zero. */
 238 mp_size_t
 239 ecc_mul_g_itch (const struct ecc_curve *ecc);
 240 void
 241 ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r,
 242            const mp_limb_t *np, mp_limb_t *scratch);
 243
 244 /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a
 245    non-zero point on the curve, in affine coordinates. Pass a non-zero
 246    INITIAL if the point coordinates have not previously been converted
 247    to Montgomery representation. Output R is a non-zero point, in
 248    Jacobian coordinates. */
 249 mp_size_t
 250 ecc_mul_a_itch (const struct ecc_curve *ecc);
 251 void
 252 ecc_mul_a (const struct ecc_curve *ecc,
 253            int initial, mp_limb_t *r,
 254            const mp_limb_t *np, const mp_limb_t *p,
 255            mp_limb_t *scratch);
 256
 257 #ifdef __cplusplus
 258 }
 259 #endif
 260
 261 #endif /* NETTLE_ECC_H_INCLUDED */