Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2012 Werner Dittmann |
| 3 | * All rights reserved. For licensing and other legal details, see the file legal.c. |
| 4 | * |
| 5 | * @author Werner Dittmann <Werner.Dittmann@t-online.de> |
| 6 | * |
| 7 | */ |
| 8 | #ifndef _EC_H_ |
| 9 | #define _EC_H_ |
| 10 | |
| 11 | #include <bn.h> |
| 12 | |
| 13 | /** |
| 14 | * @file ec.h |
| 15 | * @brief Elliptic curve functions for bnlib |
| 16 | * @defgroup BNLIB_EC Elliptic curve functions |
| 17 | * @{ |
| 18 | */ |
| 19 | |
| 20 | #ifdef __cplusplus |
| 21 | extern "C" |
| 22 | { |
| 23 | #endif |
| 24 | |
| 25 | typedef struct BigNum BigNum; |
| 26 | |
| 27 | typedef enum { |
| 28 | NIST192P = 1, |
| 29 | NIST224P = 2, |
| 30 | NIST256P = 3, |
| 31 | NIST384P = 4, |
| 32 | NIST521P = 5, |
| 33 | Curve25519 = 10, |
| 34 | Curve3617 = 11 |
| 35 | } Curves; |
| 36 | |
| 37 | /** |
| 38 | * \brief This structure contains the x, y affine coordinates and the z value if we |
| 39 | * use projective coordinates during EC point arithmetic. |
| 40 | */ |
| 41 | typedef struct _EcPoint { |
| 42 | BigNum *x, *y, *z; |
| 43 | BigNum tx, ty, tz; |
| 44 | } EcPoint; |
| 45 | |
| 46 | /** |
| 47 | * @brief This structure contains the value of EC curves over Prime Fields. |
| 48 | * |
| 49 | * The for NIST curves the field names correspond to the variable names defined in |
| 50 | * NIST FIPS 186-3, E.1.2. The <b>a</b> curve parameter is the constant -3 and is |
| 51 | * computed during initialization of the curve structure. |
| 52 | * |
| 53 | * For other curves, for example curve3917 we have less parameters to fill in, mostly |
| 54 | * the prime number, the base point, etc. Refer to the curve's initialization function |
| 55 | * about the use of the fileds. |
| 56 | */ |
| 57 | struct EcCurve; |
| 58 | struct EcCurve { |
| 59 | Curves id; |
| 60 | BigNum _p; |
| 61 | BigNum _n; |
| 62 | BigNum _SEED; |
| 63 | BigNum _c; |
| 64 | BigNum _a; |
| 65 | BigNum _b; |
| 66 | BigNum _Gx; |
| 67 | BigNum _Gy; |
| 68 | /* Pointers to the BigNum structures, for better readability mainly */ |
| 69 | BigNum *p; |
| 70 | BigNum *n; |
| 71 | BigNum *SEED; |
| 72 | BigNum *c; |
| 73 | BigNum *a; |
| 74 | BigNum *b; |
| 75 | BigNum *Gx; |
| 76 | BigNum *Gy; |
| 77 | /* some scratch pad variables, the EC algorithms use them to |
| 78 | avoid to much memory allocation/deallocatio0n overhead */ |
| 79 | BigNum _S1, _U1, _H, _R, _t0, _t1, _t2, _t3; |
| 80 | BigNum *S1, *U1, *H, *R, *t0, *t1, *t2, *t3; |
| 81 | int (*affineOp)(const struct EcCurve *curve, EcPoint *R, const EcPoint *P); |
| 82 | int (*doubleOp)(const struct EcCurve *curve, EcPoint *R, const EcPoint *P); |
| 83 | int (*addOp)(const struct EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q); |
| 84 | int (*modOp)(BigNum *, const BigNum *, const BigNum *); |
| 85 | int (*checkPubOp)(const struct EcCurve *curve, const EcPoint *pub); |
| 86 | int (*randomOp)(const struct EcCurve *curve, BigNum *d); |
| 87 | int (*mulScalar)(const struct EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar); |
| 88 | |
| 89 | }; |
| 90 | |
| 91 | typedef struct EcCurve EcCurve; |
| 92 | typedef EcCurve NistECpCurve; |
| 93 | |
| 94 | /** |
| 95 | * \brief Marco to initialize a EC point structure. |
| 96 | * |
| 97 | * \param P Address of the EC point structure |
| 98 | */ |
| 99 | #define INIT_EC_POINT(P) {EcPoint *e = P; e->x = &e->tx; e->y = &e->ty; e->z = &e->tz; bnBegin(e->x); bnBegin(e->y); bnBegin(e->z);} |
| 100 | |
| 101 | /** |
| 102 | * \brief Marco to free a EC point structure. |
| 103 | * |
| 104 | * \param P Address of the EC point structure |
| 105 | */ |
| 106 | #define FREE_EC_POINT(P) {EcPoint *e = P; bnEnd(e->x); bnEnd(e->y); bnEnd(e->z);} |
| 107 | |
| 108 | /** |
| 109 | * \brief Marco to set a EC point structure to the curve's base point. |
| 110 | * |
| 111 | * \param C Address of the NistECpCurve structure. |
| 112 | * |
| 113 | * \param P Address of the EC point structure. |
| 114 | */ |
| 115 | #define SET_EC_BASE_POINT(C, P) {EcPoint *e = P; const EcCurve *c = C; bnCopy(e->x, c->Gx); bnCopy(e->y, c->Gy); bnSetQ(e->z, 1);} |
| 116 | |
| 117 | /* |
| 118 | * EC point helper functions |
| 119 | */ |
| 120 | extern void ecInitPoint(EcPoint *P); |
| 121 | |
| 122 | extern void ecFreePoint(EcPoint *P); |
| 123 | |
| 124 | extern void ecSetBasePoint(EcCurve *C, EcPoint *P); |
| 125 | |
| 126 | /** |
| 127 | * \brief Get NIST EC curve parameters. |
| 128 | * |
| 129 | * Before reusing a EC curve structure make sure to call ecFreeCurveNistECp |
| 130 | * to return memory. |
| 131 | * |
| 132 | * \param curveId Which curve to initialize |
| 133 | * |
| 134 | * \param curve Pointer to a EcCurve structure |
| 135 | * |
| 136 | * \return 0 if successful |
| 137 | * |
| 138 | * \note Call ecFreeCurveNistECp to return allocated memory. |
| 139 | */ |
| 140 | int ecGetCurveNistECp(Curves curveId, NistECpCurve *curve); |
| 141 | |
| 142 | |
| 143 | /** |
| 144 | * \brief Free EC curve parameters. |
| 145 | * |
| 146 | * \param curve Pointer to a EcCurve structure |
| 147 | * |
| 148 | * \note Curve parameters must be initialized calling ecGetCurveNistECp. |
| 149 | */ |
| 150 | void ecFreeCurveNistECp(EcCurve *curve); |
| 151 | |
| 152 | /** |
| 153 | * \brief Double an EC point. |
| 154 | * |
| 155 | * This function uses affine coordinates to perform the computations. For |
| 156 | * further reference see RFC 6090 or the standard work <i>Guide to Elliptic |
| 157 | * Curve Cryptography</i>. |
| 158 | * |
| 159 | * \param curve Address of EC curve structure |
| 160 | * \param R Address of resulting EC point structure |
| 161 | * \param P Address of the EC point structure |
| 162 | * |
| 163 | * \return 0 if successful |
| 164 | */ |
| 165 | int ecDoublePoint(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| 166 | |
| 167 | /** |
| 168 | * \brief Add two EC points. |
| 169 | * |
| 170 | * This function uses affine coordinates to perform the computations. For |
| 171 | * further reference see RFC 6090 or the standard work <i>Guide to Elliptic |
| 172 | * Curve Cryptography</i>. |
| 173 | * |
| 174 | * \param curve Address of EC curve structure |
| 175 | * \param R Address of resulting EC point structure |
| 176 | * \param P Address of the first EC point structure |
| 177 | * \param Q Address of the second EC point structure |
| 178 | * |
| 179 | * \return 0 if successful |
| 180 | */ |
| 181 | int ecAddPoint(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q); |
| 182 | |
| 183 | /** |
| 184 | * \brief Mulitply an EC point with a scalar value. |
| 185 | * |
| 186 | * \param curve Address of EC curve structure |
| 187 | * \param R Address of resulting EC point structure |
| 188 | * \param P Address of the EC point structure |
| 189 | * \param scalar Address of the scalar multi-precision integer value |
| 190 | * |
| 191 | * \return 0 if successful |
| 192 | */ |
| 193 | int ecMulPointScalar(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar); |
| 194 | |
| 195 | /** |
| 196 | * \brief Convert an EC point from Jacobian projective coordinates to normal affine x/y coordinates. |
| 197 | * |
| 198 | * \param curve Address of EC curve structure |
| 199 | * \param R Address of EC point structure that receives the x/y coordinates |
| 200 | * \param P Address of the EC point structure that contains the jacobian x/y/z coordinates. |
| 201 | * |
| 202 | * \return 0 if successful |
| 203 | */ |
| 204 | int ecGetAffine(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| 205 | |
| 206 | /** |
| 207 | * @brief Generate a random number. |
| 208 | * |
| 209 | * The method generates a random number and checks if it matches the curve restricitions. |
| 210 | * Use this number as ECDH private key. |
| 211 | * |
| 212 | * @param curve the NIST curve to use. |
| 213 | * |
| 214 | * @param d receives the generated random number. |
| 215 | */ |
| 216 | int ecGenerateRandomNumber(const NistECpCurve *curve, BigNum *d); |
| 217 | |
| 218 | /** |
| 219 | * @brief Check a public key. |
| 220 | * |
| 221 | * The method checks if a public key is valid. For NIST curves it uses the |
| 222 | * ECC Partial Validation, NIST SP800-56A section 5.6.2.6 |
| 223 | * |
| 224 | * For other curves it computes the equation and compares the left hand and |
| 225 | * the right handresults. If they are equal the point is on the curve. |
| 226 | * |
| 227 | * @param curve the curve to use. |
| 228 | * |
| 229 | * @param pub the public key to check. |
| 230 | * |
| 231 | * @returns true (!0) if the check was ok, false (0) otherwise. |
| 232 | * |
| 233 | * @note The function uses some scratch pad variable of the NistECpCurve structure. |
| 234 | */ |
| 235 | int ecCheckPubKey(const EcCurve *curve, const EcPoint *pub); |
| 236 | |
| 237 | int ecGetCurvesCurve(Curves curveId, EcCurve *curve); |
| 238 | |
| 239 | void ecFreeCurvesCurve(EcCurve *curve); |
| 240 | |
| 241 | /** |
| 242 | * This is a special function for DJB's curve 25519. Actually it's the scalar multiplication |
| 243 | * mypublic = basepoint * secret |
| 244 | */ |
| 245 | int curve25519_donna(unsigned char *mypublic, const unsigned char *secret, const unsigned char *basepoint); |
| 246 | |
| 247 | /* |
| 248 | * Some additional functions that are not available in bnlib |
| 249 | */ |
| 250 | int bnAddMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod); |
| 251 | |
| 252 | int bnAddQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod); |
| 253 | |
| 254 | int bnSubMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod); |
| 255 | |
| 256 | int bnSubQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod); |
| 257 | |
| 258 | int bnMulMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *n2, struct BigNum *mod, const EcCurve *curve); |
| 259 | |
| 260 | int bnMulQMod_ (struct BigNum *rslt, struct BigNum *n1, unsigned n2, struct BigNum *mod, const EcCurve *curve); |
| 261 | |
| 262 | int bnSquareMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod, const EcCurve *curve); |
| 263 | |
| 264 | #ifdef __cplusplus |
| 265 | } |
| 266 | #endif |
| 267 | |
| 268 | /** |
| 269 | * @} |
| 270 | */ |
| 271 | |
| 272 | #endif |