Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 1 | /* |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 2 | * Copyright (C) 2012 Werner Dittmann |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 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 | #include <stdio.h> |
| 9 | #include <stdlib.h> |
| 10 | #include <stdint.h> |
| 11 | |
| 12 | #include <bn.h> |
| 13 | #include <bnprint.h> |
| 14 | |
| 15 | #include <ec/ec.h> |
| 16 | |
| 17 | static BigNum _mpiZero; |
| 18 | static BigNum _mpiOne; |
| 19 | static BigNum _mpiTwo; |
| 20 | static BigNum _mpiThree; |
| 21 | static BigNum _mpiFour; |
| 22 | static BigNum _mpiEight; |
| 23 | |
| 24 | static BigNum* mpiZero = &_mpiZero; |
| 25 | static BigNum* mpiOne = &_mpiOne; |
| 26 | static BigNum* mpiTwo = &_mpiTwo; |
| 27 | static BigNum* mpiThree = &_mpiThree; |
| 28 | static BigNum* mpiFour = &_mpiFour; |
| 29 | static BigNum* mpiEight = &_mpiEight; |
| 30 | static int initialized = 0; |
| 31 | |
| 32 | |
| 33 | /* The following parameters are given: |
| 34 | - The prime modulus p |
| 35 | - The order n |
| 36 | - The 160-bit input seed SEED to the SHA-1 based algorithm (i.e., the domain parameter seed) |
| 37 | - The output c of the SHA-1 based algorithm |
| 38 | - The coefficient b (satisfying b2 c ≡ –27 (mod p)) |
| 39 | - The base point x coordinate Gx |
| 40 | - The base point y coordinate Gy |
| 41 | */ |
| 42 | |
| 43 | typedef struct _curveData { |
| 44 | char *p; |
| 45 | char *n; |
| 46 | char *SEED; |
| 47 | char *c; |
| 48 | char *b; |
| 49 | char *Gx; |
| 50 | char *Gy; |
| 51 | } curveData; |
| 52 | |
| 53 | static curveData nist192 = { |
| 54 | "6277101735386680763835789423207666416083908700390324961279", |
| 55 | "6277101735386680763835789423176059013767194773182842284081", |
| 56 | "3045ae6fc8422f64ed579528d38120eae12196d5", |
| 57 | "3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65", |
| 58 | "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", |
| 59 | "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", |
| 60 | "07192b95ffc8da78631011ed6b24cdd573f977a11e794811", |
| 61 | }; |
| 62 | |
| 63 | static curveData nist224 = { |
| 64 | "26959946667150639794667015087019630673557916260026308143510066298881", |
| 65 | "26959946667150639794667015087019625940457807714424391721682722368061", |
| 66 | "bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5", |
| 67 | "5b056c7e11dd68f40469ee7f3c7a7d74f7d121116506d031218291fb", |
| 68 | "b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", |
| 69 | "b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", |
| 70 | "bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", |
| 71 | }; |
| 72 | |
| 73 | static curveData nist256 = { |
| 74 | "115792089210356248762697446949407573530086143415290314195533631308867097853951", |
| 75 | "115792089210356248762697446949407573529996955224135760342422259061068512044369", |
| 76 | "c49d360886e704936a6678e1139d26b7819f7e90", |
| 77 | "7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0d", |
| 78 | "5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", |
| 79 | "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", |
| 80 | "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", |
| 81 | }; |
| 82 | |
| 83 | static curveData nist384 = { |
| 84 | "39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", |
| 85 | "39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", |
| 86 | "a335926aa319a27a1d00896a6773a4827acdac73", |
| 87 | "79d1e655f868f02fff48dcdee14151ddb80643c1406d0ca10dfe6fc52009540a495e8042ea5f744f6e184667cc722483", |
| 88 | "b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", |
| 89 | "aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", |
| 90 | "3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", |
| 91 | }; |
| 92 | |
| 93 | static curveData nist521 = { |
| 94 | "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", |
| 95 | "6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", |
| 96 | "d09e8800291cb85396cc6717393284aaa0da64ba", |
| 97 | "0b48bfa5f420a34949539d2bdfc264eeeeb077688e44fbf0ad8f6d0edb37bd6b533281000518e19f1b9ffbe0fe9ed8a3c2200b8f875e523868c70c1e5bf55bad637", |
| 98 | "051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", |
| 99 | "c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", |
| 100 | "11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", |
| 101 | }; |
| 102 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 103 | /*============================================================================*/ |
| 104 | /* Bignum Shorthand Functions */ |
| 105 | /*============================================================================*/ |
| 106 | |
| 107 | int bnAddMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod) |
| 108 | { |
| 109 | bnAdd (rslt, n1); |
| 110 | if (bnCmp (rslt, mod) >= 0) { |
| 111 | bnSub (rslt, mod); |
| 112 | } |
| 113 | return 0; |
| 114 | } |
| 115 | |
| 116 | int bnAddQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod) |
| 117 | { |
| 118 | bnAddQ (rslt, n1); |
| 119 | if (bnCmp (rslt, mod) >= 0) { |
| 120 | bnSub (rslt, mod); |
| 121 | } |
| 122 | return 0; |
| 123 | } |
| 124 | |
| 125 | int bnSubMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod) |
| 126 | { |
| 127 | if (bnCmp (rslt, n1) < 0) { |
| 128 | bnAdd (rslt, mod); |
| 129 | } |
| 130 | bnSub (rslt, n1); |
| 131 | return 0; |
| 132 | } |
| 133 | |
| 134 | int bnSubQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod) |
| 135 | { |
| 136 | if (bnCmpQ (rslt, n1) < 0) { |
| 137 | bnAdd (rslt, mod); |
| 138 | } |
| 139 | bnSubQ (rslt, n1); |
| 140 | return 0; |
| 141 | } |
| 142 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 143 | int bnMulMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *n2, struct BigNum *mod) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 144 | { |
| 145 | bnMul (rslt, n1, n2); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 146 | bnMod (rslt, rslt, mod); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 147 | return 0; |
| 148 | } |
| 149 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 150 | int bnMulQMod_ (struct BigNum *rslt, struct BigNum *n1, unsigned n2, struct BigNum *mod) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 151 | { |
| 152 | bnMulQ (rslt, n1, n2); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 153 | bnMod (rslt, rslt, mod); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 154 | return 0; |
| 155 | } |
| 156 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 157 | int bnSquareMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 158 | { |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 159 | bnSquare (rslt, n1); |
| 160 | bnMod (rslt, rslt, mod); |
| 161 | return 0; |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 162 | } |
| 163 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 164 | int ecGetCurveNistECp(NistCurves curveId, NistECpCurve *curve) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 165 | { |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 166 | size_t maxBits; |
| 167 | curveData *cd; |
| 168 | |
| 169 | if (!initialized) { |
| 170 | bnBegin(mpiZero); bnSetQ(mpiZero, 0); |
| 171 | bnBegin(mpiOne); bnSetQ(mpiOne, 1); |
| 172 | bnBegin(mpiTwo); bnSetQ(mpiTwo, 2); |
| 173 | bnBegin(mpiThree); bnSetQ(mpiThree, 3); |
| 174 | bnBegin(mpiFour); bnSetQ(mpiFour, 4); |
| 175 | bnBegin(mpiEight); bnSetQ(mpiEight, 8); |
| 176 | initialized = 1; |
| 177 | } |
| 178 | if (curve == NULL) |
| 179 | return -2; |
| 180 | |
| 181 | bnBegin(&curve->_p); curve->p = &curve->_p; |
| 182 | bnBegin(&curve->_n); curve->n = &curve->_n; |
| 183 | bnBegin(&curve->_SEED); curve->SEED = &curve->_SEED; |
| 184 | bnBegin(&curve->_c); curve->c = &curve->_c; |
| 185 | bnBegin(&curve->_a); curve->a = &curve->_a; |
| 186 | bnBegin(&curve->_b); curve->b = &curve->_b; |
| 187 | bnBegin(&curve->_Gx); curve->Gx = &curve->_Gx; |
| 188 | bnBegin(&curve->_Gy); curve->Gy = &curve->_Gy; |
| 189 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 190 | /* Initialize scratchpad variables and their pointers */ |
| 191 | bnBegin(&curve->_S1); curve->S1 = &curve->_S1; |
| 192 | bnBegin(&curve->_U1); curve->U1 = &curve->_U1; |
| 193 | bnBegin(&curve->_H); curve->H = &curve->_H; |
| 194 | bnBegin(&curve->_R); curve->R = &curve->_R; |
| 195 | bnBegin(&curve->_t0); curve->t0 = &curve->_t0; |
| 196 | bnBegin(&curve->_t1); curve->t1 = &curve->_t1; |
| 197 | bnBegin(&curve->_t2); curve->t2 = &curve->_t2; |
| 198 | bnBegin(&curve->_t3); curve->t3 = &curve->_t3; |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 199 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 200 | switch (curveId) { |
| 201 | case NIST192P: |
| 202 | cd = &nist192; |
| 203 | break; |
| 204 | |
| 205 | case NIST224P: |
| 206 | cd = &nist224; |
| 207 | break; |
| 208 | |
| 209 | case NIST256P: |
| 210 | cd = &nist256; |
| 211 | break; |
| 212 | |
| 213 | case NIST384P: |
| 214 | cd = &nist384; |
| 215 | break; |
| 216 | |
| 217 | case NIST521P: |
| 218 | cd = &nist521; |
| 219 | break; |
| 220 | |
| 221 | default: |
| 222 | return -2; |
| 223 | } |
| 224 | |
| 225 | bnReadAscii(curve->p, cd->p, 10); |
| 226 | bnReadAscii(curve->n, cd->n, 10); |
| 227 | bnReadAscii(curve->SEED, cd->SEED, 16); |
| 228 | bnReadAscii(curve->c, cd->c, 16); |
| 229 | bnCopy(curve->a, curve->p); |
| 230 | bnSub(curve->a, mpiThree); |
| 231 | bnReadAscii(curve->b, cd->b, 16); |
| 232 | bnReadAscii(curve->Gx, cd->Gx, 16); |
| 233 | bnReadAscii(curve->Gy, cd->Gy, 16); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 234 | |
| 235 | /* variables must be able to hold p^2, plus one nimb (min. 15 bits) for overflow */ |
| 236 | maxBits = bnBits(curve->p) * 2 + 15; |
| 237 | |
| 238 | /* The set_bit allocates enough memory to hold maximum values */ |
| 239 | /* Initialize scratchpad variables before use */ |
| 240 | bnPrealloc(curve->S1, maxBits); |
| 241 | bnPrealloc(curve->U1, maxBits); |
| 242 | bnPrealloc(curve->H, maxBits); |
| 243 | bnPrealloc(curve->R, maxBits); |
| 244 | bnPrealloc(curve->S1, maxBits); |
| 245 | bnPrealloc(curve->t1, maxBits); |
| 246 | bnPrealloc(curve->t2, maxBits); |
| 247 | bnPrealloc(curve->t3, maxBits); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 248 | |
| 249 | return 0; |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 250 | |
| 251 | /* ecFreeCurveNistECp(curve); |
| 252 | return ret; |
| 253 | */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 254 | } |
| 255 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 256 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 257 | void ecFreeCurveNistECp(NistECpCurve *curve) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 258 | { |
| 259 | if (curve == NULL) |
| 260 | return; |
| 261 | |
| 262 | bnEnd(curve->p); |
| 263 | bnEnd(curve->n); |
| 264 | bnEnd(curve->SEED); |
| 265 | bnEnd(curve->c); |
| 266 | bnEnd(curve->b); |
| 267 | bnEnd(curve->Gx); |
| 268 | bnEnd(curve->Gy); |
| 269 | |
| 270 | bnEnd(curve->S1); |
| 271 | bnEnd(curve->U1); |
| 272 | bnEnd(curve->H); |
| 273 | bnEnd(curve->R); |
| 274 | bnEnd(curve->t0); |
| 275 | bnEnd(curve->t1); |
| 276 | bnEnd(curve->t2); |
| 277 | bnEnd(curve->t3); |
| 278 | } |
| 279 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 280 | |
| 281 | /*============================================================================*/ |
| 282 | /* Elliptic Curve arithmetic */ |
| 283 | /*============================================================================*/ |
| 284 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 285 | int ecGetAffine(const NistECpCurve *curve, EcPoint *R, const EcPoint *P) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 286 | { |
| 287 | int ret = 0; |
| 288 | |
| 289 | struct BigNum z_1, z_2; |
| 290 | |
| 291 | bnBegin(&z_1); |
| 292 | bnBegin(&z_2); |
| 293 | |
| 294 | /* affine x = X / Z^2 */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 295 | bnInv (&z_1, P->z, curve->p); /* z_1 = Z^(-1) */ |
| 296 | bnMulMod_(&z_2, &z_1, &z_1, curve->p); /* z_2 = Z^(-2) */ |
| 297 | bnMulMod_(R->x, P->x, &z_2, curve->p); |
| 298 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 299 | /* affine y = Y / Z^3 */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 300 | bnMulMod_(&z_2, &z_2, &z_1, curve->p); /* z_2 = Z^(-3) */ |
| 301 | bnMulMod_(R->y, P->y, &z_2, curve->p); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 302 | |
| 303 | bnSetQ(R->z, 1); |
| 304 | |
| 305 | bnEnd(&z_1); |
| 306 | bnEnd(&z_2); |
| 307 | return ret; |
| 308 | } |
| 309 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 310 | int ecDoublePoint(const NistECpCurve *curve, EcPoint *R, const EcPoint *P) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 311 | { |
| 312 | int ret = 0; |
| 313 | |
| 314 | EcPoint tP; |
| 315 | const EcPoint *ptP = 0; |
| 316 | |
| 317 | if (!bnCmp(P->y, mpiZero) || !bnCmp(P->z, mpiZero)) { |
| 318 | bnSetQ(R->x, 1); |
| 319 | bnSetQ(R->y, 1); |
| 320 | bnSetQ(R->z, 0); |
| 321 | return 0; |
| 322 | } |
| 323 | |
| 324 | /* Check for overlapping arguments, copy if necessary and set pointer */ |
| 325 | if (P == R) { |
| 326 | INIT_EC_POINT(&tP); |
| 327 | ptP = &tP; |
| 328 | bnCopy(tP.x, P->x); |
| 329 | bnCopy(tP.y, P->y); |
| 330 | bnCopy(tP.z, P->z); |
| 331 | } |
| 332 | else |
| 333 | ptP = P; |
| 334 | |
| 335 | /* S = 4*X*Y^2, save Y^2 in t1 for later use */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 336 | bnMulMod_(curve->t1, ptP->y, ptP->y, curve->p); /* t1 = Y^2 */ |
| 337 | bnMulMod_(curve->t0, ptP->x, mpiFour, curve->p); /* t0 = 4 * X */ |
| 338 | bnMulMod_(curve->S1, curve->t0, curve->t1, curve->p); /* S1 = t0 * t1 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 339 | |
| 340 | /* M = 3*(X + Z^2)*(X - Z^2), use scratch variable U1 to store M value */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 341 | bnMulMod_(curve->t2, ptP->z, ptP->z, curve->p); /* t2 = Z^2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 342 | bnCopy(curve->t0, ptP->x); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 343 | bnAddMod_(curve->t0, curve->t2, curve->p); /* t0 = X + t2 */ |
| 344 | bnMulMod_(curve->t3, curve->t0, mpiThree, curve->p); /* t3 = 3 * t0 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 345 | bnCopy(curve->t0, ptP->x); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 346 | bnSubMod_(curve->t0, curve->t2, curve->p); /* t0 = X - t2 */ |
| 347 | bnMulMod_(curve->U1, curve->t3, curve->t0, curve->p); /* M = t3 * t0 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 348 | |
| 349 | /* X' = M^2 - 2*S */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 350 | bnMulMod_(curve->t2, curve->U1, curve->U1, curve->p); /* t2 = M^2 */ |
| 351 | bnMulMod_(curve->t0, curve->S1, mpiTwo, curve->p); /* t0 = S * 2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 352 | bnCopy(R->x, curve->t2); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 353 | bnSubMod_(R->x, curve->t0, curve->p); /* X' = t2 - t0 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 354 | |
| 355 | /* Y' = M*(S - X') - 8*Y^4 */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 356 | bnMulMod_(curve->t3, curve->t1, curve->t1, curve->p); /* t3 = Y^4 (t1 saved above) */ |
| 357 | bnMulMod_(curve->t2, curve->t3, mpiEight, curve->p); /* t2 = t3 * 8 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 358 | bnCopy(curve->t3, curve->S1); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 359 | bnSubMod_(curve->t3, R->x, curve->p); /* t3 = S - X' */ |
| 360 | bnMulMod_(curve->t0, curve->U1, curve->t3, curve->p); /* t0 = M * t3 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 361 | bnCopy(R->y, curve->t0); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 362 | bnSubMod_(R->y, curve->t2, curve->p); /* Y' = t0 - t2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 363 | |
| 364 | /* Z' = 2*Y*Z */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 365 | bnMulMod_(curve->t0, ptP->y, mpiTwo, curve->p); /* t0 = 2 * Y */ |
| 366 | bnMulMod_(R->z, curve->t0, ptP->z, curve->p); /* Z' = to * Z */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 367 | |
| 368 | if (P == R) |
| 369 | FREE_EC_POINT(&tP); |
| 370 | |
| 371 | return ret; |
| 372 | } |
| 373 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 374 | /* Add two elliptic curve points. Any of them may be the same object. */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 375 | int ecAddPoint(const NistECpCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 376 | { |
| 377 | int ret = 0; |
| 378 | |
| 379 | EcPoint tP, tQ; |
| 380 | const EcPoint *ptP = 0; |
| 381 | const EcPoint *ptQ = 0; |
| 382 | |
| 383 | |
| 384 | /* Fast check if application called add(R, P, P) */ |
| 385 | if (!bnCmp(P->x, Q->x) && !bnCmp(P->y, Q->y) && !bnCmp(P->z, Q->z)) { |
| 386 | return ecDoublePoint(curve, R, P); |
| 387 | } |
| 388 | |
| 389 | /* if P is (@,@), R = Q */ |
| 390 | if (!bnCmp(P->z, mpiZero)) { |
| 391 | bnCopy(R->x, Q->x); |
| 392 | bnCopy(R->y, Q->y); |
| 393 | bnCopy(R->z, Q->z); |
| 394 | return 0; |
| 395 | } |
| 396 | |
| 397 | /* if Q is (@,@), R = P */ |
| 398 | if (!bnCmp(Q->z, mpiZero)) { |
| 399 | bnCopy(R->x, P->x); |
| 400 | bnCopy(R->y, P->y); |
| 401 | bnCopy(R->z, P->z); |
| 402 | return 0; |
| 403 | } |
| 404 | |
| 405 | /* Check for overlapping arguments, copy if necessary and set pointers */ |
| 406 | if (P == R) { |
| 407 | INIT_EC_POINT(&tP); |
| 408 | ptP = &tP; |
| 409 | bnCopy(tP.x, P->x); |
| 410 | bnCopy(tP.y, P->y); |
| 411 | bnCopy(tP.z, P->z); |
| 412 | } |
| 413 | else |
| 414 | ptP = P; |
| 415 | |
| 416 | if (Q == R) { |
| 417 | INIT_EC_POINT(&tQ); |
| 418 | ptQ = &tQ; |
| 419 | bnCopy(tQ.x, Q->x); |
| 420 | bnCopy(tQ.y, Q->y); |
| 421 | bnCopy(tQ.z, Q->z); |
| 422 | } |
| 423 | else |
| 424 | ptQ = Q; |
| 425 | |
| 426 | /* U1 = X1*Z2^2, where X1: P->x, Z2: Q->z */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 427 | bnMulMod_(curve->t1, ptQ->z, ptQ->z, curve->p); /* t1 = Z2^2 */ |
| 428 | bnMulMod_(curve->U1, ptP->x, curve->t1, curve->p); /* U1 = X1 * z_2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 429 | |
| 430 | /* S1 = Y1*Z2^3, where Y1: P->y */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 431 | bnMulMod_(curve->t1, curve->t1, ptQ->z, curve->p); /* t1 = Z2^3 */ |
| 432 | bnMulMod_(curve->S1, ptP->y, curve->t1, curve->p); /* S1 = Y1 * z_2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 433 | |
| 434 | /* U2 = X2*Z1^2, where X2: Q->x, Z1: P->z */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 435 | bnMulMod_(curve->t1, ptP->z, ptP->z, curve->p); /* t1 = Z1^2 */ |
| 436 | bnMulMod_(curve->H, ptQ->x, curve->t1, curve->p); /* H = X2 * t1 (store U2 in H) */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 437 | |
| 438 | /* H = U2 - U1 */ |
| 439 | bnSubMod_(curve->H, curve->U1, curve->p); |
| 440 | |
| 441 | /* S2 = Y2*Z1^3, where Y2: Q->y */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 442 | bnMulMod_(curve->t1, curve->t1, ptP->z, curve->p); /* t1 = Z1^3 */ |
| 443 | bnMulMod_(curve->R, ptQ->y, curve->t1, curve->p); /* R = Y2 * t1 (store S2 in R) */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 444 | |
| 445 | /* R = S2 - S1 */ |
| 446 | bnSubMod_(curve->R, curve->S1, curve->p); |
| 447 | |
| 448 | /* if (U1 == U2), i.e H is zero */ |
| 449 | if (!bnCmp(curve->H, mpiZero)) { |
| 450 | |
| 451 | /* if (S1 != S2), i.e. R is _not_ zero: return infinity*/ |
| 452 | if (bnCmp(curve->R, mpiZero)) { |
| 453 | bnSetQ(R->x, 1); |
| 454 | bnSetQ(R->y, 1); |
| 455 | bnSetQ(R->z, 0); |
| 456 | return 0; |
| 457 | } |
| 458 | return ecDoublePoint(curve, R, P); |
| 459 | } |
| 460 | /* X3 = R^2 - H^3 - 2*U1*H^2, where X3: R->x */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 461 | bnMulMod_(curve->t0, curve->H, curve->H, curve->p); /* t0 = H^2 */ |
| 462 | bnMulMod_(curve->t1, curve->U1, curve->t0, curve->p); /* t1 = U1 * t0, (hold t1) */ |
| 463 | bnMulMod_(curve->t0, curve->t0, curve->H, curve->p); /* t0 = H^3, (hold t0) */ |
| 464 | bnMulMod_(curve->t2, curve->R, curve->R, curve->p); /* t2 = R^2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 465 | bnCopy(curve->t3, curve->t2); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 466 | bnSubMod_(curve->t3, curve->t0, curve->p); /* t3 = t2 - t0, (-H^3)*/ |
| 467 | bnMulMod_(curve->t2, mpiTwo, curve->t1, curve->p); /* t2 = 2 * t1 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 468 | bnCopy(R->x, curve->t3); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 469 | bnSubMod_(R->x, curve->t2, curve->p); /* X3 = t3 - t2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 470 | |
| 471 | /* Y3 = R*(U1*H^2 - X3) - S1*H^3, where Y3: R->y */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 472 | bnSubMod_(curve->t1, R->x, curve->p); /* t1 = t1 - X3, overwrites t1 now */ |
| 473 | bnMulMod_(curve->t2, curve->R, curve->t1, curve->p); /* t2 = R * z_2 */ |
| 474 | bnMulMod_(curve->S1, curve->S1, curve->t0, curve->p); /* S1 = S1 * t0, (t0 has H^3) */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 475 | bnCopy(R->y, curve->t2); |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 476 | bnSubMod_(R->y, curve->S1, curve->p); /* Y3 = t2 - S1 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 477 | |
| 478 | /* Z3 = H*Z1*Z2, where Z1: P->z, Z2: Q->z, Z3: R->z */ |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 479 | bnMulMod_(curve->t2, curve->H, P->z, curve->p); /* t2 = H * Z1 */ |
| 480 | bnMulMod_(R->z, curve->t2, Q->z, curve->p); /* Z3 = t2 * Z2 */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 481 | |
| 482 | if (P == R) |
| 483 | FREE_EC_POINT(&tP); |
| 484 | if (Q == R) |
| 485 | FREE_EC_POINT(&tQ); |
| 486 | return ret; |
| 487 | } |
| 488 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 489 | int ecMulPointScalar(const NistECpCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 490 | { |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 491 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 492 | /* MPI_CHK below macro requires a 'ret' variable and a cleanup label */ |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 493 | int ret = 0; |
| 494 | int i; |
| 495 | int bits = bnBits(scalar); |
| 496 | EcPoint n; |
| 497 | |
| 498 | INIT_EC_POINT(&n); |
| 499 | bnCopy(n.x, P->x); |
| 500 | bnCopy(n.y, P->y); |
| 501 | bnCopy(n.z, P->z); |
| 502 | |
| 503 | bnSetQ(R->x, 0); |
| 504 | bnSetQ(R->y, 0); |
| 505 | bnSetQ(R->z, 0); |
| 506 | |
| 507 | for (i = 0; i < bits; i++) { |
| 508 | if (bnReadBit(scalar, i)) |
| 509 | ecAddPoint(curve, R, R, &n); |
| 510 | |
| 511 | /* ecAddPoint(curve, &n, &n, &n); */ |
| 512 | ecDoublePoint(curve, &n, &n); |
| 513 | } |
| 514 | FREE_EC_POINT(&n); |
| 515 | return ret; |
| 516 | } |
| 517 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 518 | #ifdef WEAKRANDOM |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 519 | /* |
| 520 | * A standard random number generator that uses the portable random() system function. |
| 521 | * |
| 522 | * This should be enhanced to use a better random generator |
| 523 | */ |
| 524 | static int _random(unsigned char *output, size_t len) |
| 525 | { |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 526 | size_t i; |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 527 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 528 | for(i = 0; i < len; ++i ) |
| 529 | output[i] = random(); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 530 | |
| 531 | return( 0 ); |
| 532 | } |
| 533 | #else |
| 534 | #include <cryptcommon/ZrtpRandom.h> |
| 535 | static int _random(unsigned char *output, size_t len) |
| 536 | { |
| 537 | return zrtp_getRandomData(output, len); |
| 538 | } |
| 539 | #endif |
| 540 | |
Alexandre Lision | ddd731e | 2014-01-31 11:50:08 -0500 | [diff] [blame^] | 541 | int ecGenerateRandomNumber(const NistECpCurve *curve, BigNum *d) |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 542 | { |
| 543 | BigNum c, nMinusOne; |
| 544 | |
| 545 | size_t randomBytes = ((bnBits(curve->n) + 64) + 7) / 8; |
| 546 | |
| 547 | uint8_t *ran = malloc(randomBytes); |
| 548 | |
| 549 | bnBegin(&c); |
| 550 | bnBegin(&nMinusOne); |
| 551 | |
| 552 | bnCopy(&nMinusOne, curve->n); |
| 553 | bnSubMod_(&nMinusOne, mpiOne, curve->p); |
| 554 | |
| 555 | bnSetQ(d, 0); |
| 556 | |
| 557 | while (!bnCmpQ(d, 0)) { |
| 558 | /* use _random function */ |
| 559 | _random(ran, randomBytes); |
| 560 | bnInsertBigBytes(&c, ran, 0, randomBytes); |
| 561 | bnMod(d, &c, &nMinusOne); |
| 562 | bnAddMod_(d, mpiOne, curve->p); |
| 563 | } |
| 564 | |
| 565 | bnEnd(&c); |
| 566 | bnEnd(&nMinusOne); |
| 567 | free(ran); |
| 568 | |
| 569 | return 0; |
| 570 | } |