| /* |
| * Copyright (C) 2012-2013 Werner Dittmann |
| * All rights reserved. For licensing and other legal details, see the file legal.c. |
| * |
| * @author Werner Dittmann <Werner.Dittmann@t-online.de> |
| * |
| */ |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <stdint.h> |
| |
| #include <bn.h> |
| #include <bnprint.h> |
| |
| #include <ec/ec.h> |
| |
| static BigNum _mpiZero; |
| static BigNum _mpiOne; |
| static BigNum _mpiTwo; |
| static BigNum _mpiThree; |
| static BigNum _mpiFour; |
| static BigNum _mpiEight; |
| |
| static BigNum* mpiZero = &_mpiZero; |
| static BigNum* mpiOne = &_mpiOne; |
| static BigNum* mpiTwo = &_mpiTwo; |
| static BigNum* mpiThree = &_mpiThree; |
| static BigNum* mpiFour = &_mpiFour; |
| static BigNum* mpiEight = &_mpiEight; |
| static int initialized = 0; |
| |
| |
| /* The following parameters are given: |
| - The prime modulus p |
| - The order n |
| - The 160-bit input seed SEED to the SHA-1 based algorithm (i.e., the domain parameter seed) |
| - The output c of the SHA-1 based algorithm |
| - The coefficient b (satisfying b2 c ≡ –27 (mod p)) |
| - The base point x coordinate Gx |
| - The base point y coordinate Gy |
| */ |
| |
| typedef struct _curveData { |
| char *p; |
| char *n; |
| char *SEED; |
| char *c; |
| char *b; |
| char *Gx; |
| char *Gy; |
| } curveData; |
| |
| static curveData nist192 = { |
| "6277101735386680763835789423207666416083908700390324961279", |
| "6277101735386680763835789423176059013767194773182842284081", |
| "3045ae6fc8422f64ed579528d38120eae12196d5", |
| "3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65", |
| "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", |
| "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", |
| "07192b95ffc8da78631011ed6b24cdd573f977a11e794811", |
| }; |
| |
| static curveData nist224 = { |
| "26959946667150639794667015087019630673557916260026308143510066298881", |
| "26959946667150639794667015087019625940457807714424391721682722368061", |
| "bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5", |
| "5b056c7e11dd68f40469ee7f3c7a7d74f7d121116506d031218291fb", |
| "b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", |
| "b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", |
| "bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", |
| }; |
| |
| static curveData nist256 = { |
| "115792089210356248762697446949407573530086143415290314195533631308867097853951", |
| "115792089210356248762697446949407573529996955224135760342422259061068512044369", |
| "c49d360886e704936a6678e1139d26b7819f7e90", |
| "7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0d", |
| "5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", |
| "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", |
| "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", |
| }; |
| |
| static curveData nist384 = { |
| "39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", |
| "39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", |
| "a335926aa319a27a1d00896a6773a4827acdac73", |
| "79d1e655f868f02fff48dcdee14151ddb80643c1406d0ca10dfe6fc52009540a495e8042ea5f744f6e184667cc722483", |
| "b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", |
| "aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", |
| "3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", |
| }; |
| |
| static curveData nist521 = { |
| "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", |
| "6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", |
| "d09e8800291cb85396cc6717393284aaa0da64ba", |
| "0b48bfa5f420a34949539d2bdfc264eeeeb077688e44fbf0ad8f6d0edb37bd6b533281000518e19f1b9ffbe0fe9ed8a3c2200b8f875e523868c70c1e5bf55bad637", |
| "051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", |
| "c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", |
| "11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", |
| }; |
| |
| |
| /* |
| * The data for curve3617 copied from: |
| * http://safecurves.cr.yp.to/field.html |
| * http://safecurves.cr.yp.to/base.html |
| */ |
| static curveData curve3617 = { |
| "3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef", /* Prime */ |
| "7ffffffffffffffffffffffffffffffffffffffffffffffffffeb3cc92414cf706022b36f1c0338ad63cf181b0e71a5e106af79", /* order */ |
| "", /* SEED */ |
| "", /* c */ |
| "", /* b */ |
| "1a334905141443300218c0631c326e5fcd46369f44c03ec7f57ff35498a4ab4d6d6ba111301a73faa8537c64c4fd3812f3cbc595", /* Gx*/ |
| "22", /* Gy (radix 16) */ |
| }; |
| |
| /* |
| * The data for curve25519 copied from: |
| * http://safecurves.cr.yp.to/field.html |
| * http://safecurves.cr.yp.to/base.html |
| * |
| * Note: |
| * The data for Curve25519 is here for the sake of completeness and to have the same |
| * set of initialization. One exception if the base point X coordinate (Gx) that we use to |
| * compute the DH public value, refer to function ecdhGeneratePublic(...) in ecdh.c. |
| * |
| * Otherwise the functions use EcCurve structure only to get the pointers to the Curve25519 |
| * wrapper functions. |
| * |
| */ |
| static curveData curve25519 = { |
| "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", /* Prime */ |
| "1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed", /* order */ |
| "", /* SEED */ |
| "", /* c */ |
| "", /* b */ |
| "9", /* Gx */ |
| "20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9", /* Gy */ |
| }; |
| |
| /*============================================================================*/ |
| /* Bignum Shorthand Functions */ |
| /*============================================================================*/ |
| |
| int bnAddMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod) |
| { |
| bnAdd (rslt, n1); |
| if (bnCmp (rslt, mod) >= 0) { |
| bnSub (rslt, mod); |
| } |
| return 0; |
| } |
| |
| int bnAddQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod) |
| { |
| bnAddQ (rslt, n1); |
| if (bnCmp (rslt, mod) >= 0) { |
| bnSub (rslt, mod); |
| } |
| return 0; |
| } |
| |
| int bnSubMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod) |
| { |
| if (bnCmp (rslt, n1) < 0) { |
| bnAdd (rslt, mod); |
| } |
| bnSub (rslt, n1); |
| return 0; |
| } |
| |
| int bnSubQMod_ (struct BigNum *rslt, unsigned n1, struct BigNum *mod) |
| { |
| if (bnCmpQ (rslt, n1) < 0) { |
| bnAdd (rslt, mod); |
| } |
| bnSubQ (rslt, n1); |
| return 0; |
| } |
| |
| int bnMulMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *n2, struct BigNum *mod, const EcCurve *curve) |
| { |
| bnMul (rslt, n1, n2); |
| if (curve) |
| curve->modOp(rslt, rslt, mod); |
| else |
| bnMod(rslt, rslt, mod); |
| return 0; |
| } |
| |
| int bnMulQMod_ (struct BigNum *rslt, struct BigNum *n1, unsigned n2, struct BigNum *mod, const EcCurve *curve) |
| { |
| bnMulQ (rslt, n1, n2); |
| if (curve) |
| curve->modOp(rslt, rslt, mod); |
| else |
| bnMod(rslt, rslt, mod); |
| return 0; |
| } |
| |
| int bnSquareMod_ (struct BigNum *rslt, struct BigNum *n1, struct BigNum *mod, const EcCurve *curve) |
| { |
| bnSquare (rslt, n1); |
| if (curve) |
| curve->modOp(rslt, rslt, mod); |
| else |
| bnMod(rslt, rslt, mod); |
| return 0; |
| } |
| |
| /* |
| * Note on the Curve25519 functions and usage of BigNumber: |
| * In most cases the functions to compute Curve25519 data are small wrapper functions |
| * that implement the same API as for the other curve functions. The wrapper functions |
| * then call the very specific, high-efficient function in curve25519-donna.c . |
| * |
| * For Curve25519 we don't have a real implementation for point add, point doubling, modulo |
| * and check public key. Please refer to the actual implementations below. |
| */ |
| |
| static int ecGetAffineNist(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| static int ecGetAffineEd(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| static int ecGetAffine25519(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| |
| static int ecDoublePointNist(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| static int ecDoublePointEd(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| static int ecDoublePoint25519(const EcCurve *curve, EcPoint *R, const EcPoint *P); |
| |
| static int ecAddPointNist(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q); |
| static int ecAddPointEd(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q); |
| static int ecAddPoint25519(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q); |
| |
| static int ecCheckPubKeyNist(const EcCurve *curve, const EcPoint *pub); |
| static int ecCheckPubKey3617(const EcCurve *curve, const EcPoint *pub); |
| static int ecCheckPubKey25519(const EcCurve *curve, const EcPoint *pub); |
| |
| static int ecGenerateRandomNumberNist(const EcCurve *curve, BigNum *d); |
| static int ecGenerateRandomNumber3617(const EcCurve *curve, BigNum *d); |
| static int ecGenerateRandomNumber25519(const EcCurve *curve, BigNum *d); |
| |
| static int ecMulPointScalarNormal(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar); |
| static int ecMulPointScalar25519(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar); |
| |
| /* Forward declaration of new modulo functions for the EC curves */ |
| static int newMod192(BigNum *r, const BigNum *a, const BigNum *modulo); |
| static int newMod256(BigNum *r, const BigNum *a, const BigNum *modulo); |
| static int newMod384(BigNum *r, const BigNum *a, const BigNum *modulo); |
| static int newMod521(BigNum *r, const BigNum *a, const BigNum *modulo); |
| |
| static int mod3617(BigNum *r, const BigNum *a, const BigNum *modulo); |
| static int mod25519(BigNum *r, const BigNum *a, const BigNum *modulo); |
| |
| static void commonInit() |
| { |
| bnBegin(mpiZero); bnSetQ(mpiZero, 0); |
| bnBegin(mpiOne); bnSetQ(mpiOne, 1); |
| bnBegin(mpiTwo); bnSetQ(mpiTwo, 2); |
| bnBegin(mpiThree); bnSetQ(mpiThree, 3); |
| bnBegin(mpiFour); bnSetQ(mpiFour, 4); |
| bnBegin(mpiEight); bnSetQ(mpiEight, 8); |
| } |
| |
| static void curveCommonInit(EcCurve *curve) |
| { |
| /* Initialize scratchpad variables and their pointers */ |
| bnBegin(&curve->_S1); curve->S1 = &curve->_S1; |
| bnBegin(&curve->_U1); curve->U1 = &curve->_U1; |
| bnBegin(&curve->_H); curve->H = &curve->_H; |
| bnBegin(&curve->_R); curve->R = &curve->_R; |
| bnBegin(&curve->_t0); curve->t0 = &curve->_t0; |
| bnBegin(&curve->_t1); curve->t1 = &curve->_t1; |
| bnBegin(&curve->_t2); curve->t2 = &curve->_t2; |
| bnBegin(&curve->_t3); curve->t3 = &curve->_t3; |
| } |
| |
| static void curveCommonPrealloc(EcCurve *curve) |
| { |
| size_t maxBits; |
| |
| /* variables must be able to hold p^2, plus one nimb (min. 15 bits) for overflow */ |
| maxBits = bnBits(curve->p) * 2 + 15; |
| |
| /* The set_bit allocates enough memory to hold maximum values */ |
| /* Initialize scratchpad variables before use */ |
| bnPrealloc(curve->S1, maxBits); |
| bnPrealloc(curve->U1, maxBits); |
| bnPrealloc(curve->H, maxBits); |
| bnPrealloc(curve->R, maxBits); |
| bnPrealloc(curve->S1, maxBits); |
| bnPrealloc(curve->t1, maxBits); |
| bnPrealloc(curve->t2, maxBits); |
| bnPrealloc(curve->t3, maxBits); |
| } |
| |
| int ecGetCurveNistECp(Curves curveId, EcCurve *curve) |
| { |
| curveData *cd; |
| |
| if (curveId >= Curve25519 && curveId <= Curve3617) |
| return ecGetCurvesCurve(curveId, curve); |
| |
| if (!initialized) { |
| commonInit(); |
| initialized = 1; |
| } |
| if (curve == NULL) |
| return -2; |
| |
| bnBegin(&curve->_p); curve->p = &curve->_p; |
| bnBegin(&curve->_n); curve->n = &curve->_n; |
| bnBegin(&curve->_SEED); curve->SEED = &curve->_SEED; |
| bnBegin(&curve->_c); curve->c = &curve->_c; |
| bnBegin(&curve->_a); curve->a = &curve->_a; |
| bnBegin(&curve->_b); curve->b = &curve->_b; |
| bnBegin(&curve->_Gx); curve->Gx = &curve->_Gx; |
| bnBegin(&curve->_Gy); curve->Gy = &curve->_Gy; |
| |
| curveCommonInit(curve); |
| |
| switch (curveId) { |
| case NIST192P: |
| cd = &nist192; |
| curve->modOp = newMod192; |
| break; |
| |
| case NIST224P: |
| cd = &nist224; |
| curve->modOp = bnMod; |
| break; |
| |
| case NIST256P: |
| cd = &nist256; |
| curve->modOp = bnMod; |
| break; |
| |
| case NIST384P: |
| cd = &nist384; |
| curve->modOp = newMod384; |
| break; |
| |
| case NIST521P: |
| cd = &nist521; |
| curve->modOp = newMod521; |
| break; |
| |
| default: |
| return -2; |
| } |
| |
| curve->affineOp = ecGetAffineNist; |
| curve->doubleOp = ecDoublePointNist; |
| curve->addOp = ecAddPointNist; |
| curve->checkPubOp = ecCheckPubKeyNist; |
| curve->randomOp = ecGenerateRandomNumberNist; |
| curve->mulScalar = ecMulPointScalarNormal; |
| |
| bnReadAscii(curve->p, cd->p, 10); |
| bnReadAscii(curve->n, cd->n, 10); |
| bnReadAscii(curve->SEED, cd->SEED, 16); |
| bnReadAscii(curve->c, cd->c, 16); |
| bnCopy(curve->a, curve->p); |
| bnSub(curve->a, mpiThree); |
| bnReadAscii(curve->b, cd->b, 16); |
| bnReadAscii(curve->Gx, cd->Gx, 16); |
| bnReadAscii(curve->Gy, cd->Gy, 16); |
| |
| curveCommonPrealloc(curve); |
| curve->id = curveId; |
| |
| return 0; |
| } |
| |
| int ecGetCurvesCurve(Curves curveId, EcCurve *curve) |
| { |
| curveData *cd; |
| |
| if (!initialized) { |
| commonInit(); |
| initialized = 1; |
| } |
| if (curve == NULL) |
| return -2; |
| |
| /* set-up all bignum structures, simplifies "free" handling */ |
| bnBegin(&curve->_p); curve->p = &curve->_p; |
| bnBegin(&curve->_n); curve->n = &curve->_n; |
| bnBegin(&curve->_SEED); curve->SEED = &curve->_SEED; |
| bnBegin(&curve->_c); curve->c = &curve->_c; |
| bnBegin(&curve->_a); curve->a = &curve->_a; |
| bnBegin(&curve->_b); curve->b = &curve->_b; |
| bnBegin(&curve->_Gx); curve->Gx = &curve->_Gx; |
| bnBegin(&curve->_Gy); curve->Gy = &curve->_Gy; |
| |
| curveCommonInit(curve); |
| |
| switch (curveId) { |
| case Curve3617: |
| cd = &curve3617; |
| curve->modOp = mod3617; |
| curve->affineOp = ecGetAffineEd; |
| curve->doubleOp = ecDoublePointEd; |
| curve->addOp = ecAddPointEd; |
| curve->checkPubOp = ecCheckPubKey3617; |
| curve->randomOp = ecGenerateRandomNumber3617; |
| curve->mulScalar = ecMulPointScalarNormal; |
| |
| bnReadAscii(curve->a, "3617", 10); |
| break; |
| |
| case Curve25519: |
| cd = &curve25519; |
| curve->modOp = mod25519; |
| curve->affineOp = ecGetAffine25519; |
| curve->doubleOp = ecDoublePoint25519; |
| curve->addOp = ecAddPoint25519; |
| curve->checkPubOp = ecCheckPubKey25519; |
| curve->randomOp = ecGenerateRandomNumber25519; |
| curve->mulScalar = ecMulPointScalar25519; |
| |
| bnReadAscii(curve->a, "486662", 10); |
| break; |
| |
| default: |
| return -2; |
| } |
| bnReadAscii(curve->p, cd->p, 16); |
| bnReadAscii(curve->n, cd->n, 16); |
| |
| bnReadAscii(curve->Gx, cd->Gx, 16); |
| bnReadAscii(curve->Gy, cd->Gy, 16); |
| |
| curveCommonPrealloc(curve); |
| curve->id = curveId; |
| return 0; |
| } |
| |
| void ecFreeCurveNistECp(EcCurve *curve) |
| { |
| if (curve == NULL) |
| return; |
| |
| bnEnd(curve->p); |
| bnEnd(curve->n); |
| bnEnd(curve->SEED); |
| bnEnd(curve->c); |
| bnEnd(curve->b); |
| bnEnd(curve->Gx); |
| bnEnd(curve->Gy); |
| |
| bnEnd(curve->S1); |
| bnEnd(curve->U1); |
| bnEnd(curve->H); |
| bnEnd(curve->R); |
| bnEnd(curve->t0); |
| bnEnd(curve->t1); |
| bnEnd(curve->t2); |
| bnEnd(curve->t3); |
| } |
| |
| /* |
| * EC point helper functions |
| */ |
| |
| void ecInitPoint(EcPoint *P) |
| { |
| INIT_EC_POINT(P); |
| } |
| |
| void ecFreePoint(EcPoint *P) |
| { |
| FREE_EC_POINT(P); |
| } |
| |
| void ecSetBasePoint(EcCurve *C, EcPoint *P) |
| { |
| SET_EC_BASE_POINT(C, P); |
| } |
| |
| void ecFreeCurvesCurve(EcCurve *curve) |
| { |
| ecFreeCurveNistECp(curve); |
| } |
| |
| /*============================================================================*/ |
| /* Elliptic Curve arithmetic */ |
| /*============================================================================*/ |
| |
| int ecGetAffine(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| return curve->affineOp(curve, R, P); |
| } |
| |
| static int ecGetAffineNist(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| int ret = 0; |
| |
| struct BigNum z_1, z_2; |
| |
| bnBegin(&z_1); |
| bnBegin(&z_2); |
| |
| /* affine x = X / Z^2 */ |
| bnInv (&z_1, P->z, curve->p); /* z_1 = Z^(-1) */ |
| bnMulMod_(&z_2, &z_1, &z_1, curve->p, curve); /* z_2 = Z^(-2) */ |
| bnMulMod_(R->x, P->x, &z_2, curve->p, curve); |
| |
| /* affine y = Y / Z^3 */ |
| bnMulMod_(&z_2, &z_2, &z_1, curve->p, curve); /* z_2 = Z^(-3) */ |
| bnMulMod_(R->y, P->y, &z_2, curve->p, curve); |
| |
| bnSetQ(R->z, 1); |
| |
| bnEnd(&z_1); |
| bnEnd(&z_2); |
| return ret; |
| } |
| |
| static int ecGetAffineEd(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| int ret = 0; |
| |
| struct BigNum z_1; |
| |
| bnBegin(&z_1); |
| |
| /* affine x = X / Z */ |
| bnInv (&z_1, P->z, curve->p); /* z_1 = Z^(-1) */ |
| bnMulMod_(R->x, P->x, &z_1, curve->p, curve); |
| |
| /* affine y = Y / Z */ |
| bnMulMod_(R->y, P->y, &z_1, curve->p, curve); |
| |
| bnSetQ(R->z, 1); |
| |
| bnEnd(&z_1); |
| return ret; |
| |
| } |
| |
| /* |
| * If the arguments do not point to the same EcPoint then copy P to result. |
| * Curve25519 has no specific GetAffine function, it's all inside curve25519-donna |
| */ |
| static int ecGetAffine25519(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| if (R != P) { |
| bnCopy(R->x, P->x); |
| bnCopy(R->y, P->y); |
| bnCopy(R->z, P->z); |
| } |
| return 0; |
| } |
| |
| int ecDoublePoint(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| return curve->doubleOp(curve, R, P); |
| } |
| |
| static int ecDoublePointNist(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| int ret = 0; |
| |
| EcPoint tP; |
| const EcPoint *ptP = 0; |
| |
| if (!bnCmp(P->y, mpiZero) || !bnCmp(P->z, mpiZero)) { |
| bnSetQ(R->x, 1); |
| bnSetQ(R->y, 1); |
| bnSetQ(R->z, 0); |
| return 0; |
| } |
| |
| /* Check for overlapping arguments, copy if necessary and set pointer */ |
| if (P == R) { |
| INIT_EC_POINT(&tP); |
| ptP = &tP; |
| bnCopy(tP.x, P->x); |
| bnCopy(tP.y, P->y); |
| bnCopy(tP.z, P->z); |
| } |
| else |
| ptP = P; |
| |
| /* S = 4*X*Y^2, save Y^2 in t1 for later use */ |
| bnMulMod_(curve->t1, ptP->y, ptP->y, curve->p, curve); /* t1 = Y^2 */ |
| bnMulMod_(curve->t0, ptP->x, mpiFour, curve->p, curve); /* t0 = 4 * X */ |
| bnMulMod_(curve->S1, curve->t0, curve->t1, curve->p, curve); /* S1 = t0 * t1 */ |
| |
| /* M = 3*(X + Z^2)*(X - Z^2), use scratch variable U1 to store M value */ |
| bnMulMod_(curve->t2, ptP->z, ptP->z, curve->p, curve); /* t2 = Z^2 */ |
| bnCopy(curve->t0, ptP->x); |
| bnAddMod_(curve->t0, curve->t2, curve->p); /* t0 = X + t2 */ |
| bnMulMod_(curve->t3, curve->t0, mpiThree, curve->p, curve); /* t3 = 3 * t0 */ |
| bnCopy(curve->t0, ptP->x); |
| bnSubMod_(curve->t0, curve->t2, curve->p); /* t0 = X - t2 */ |
| bnMulMod_(curve->U1, curve->t3, curve->t0, curve->p, curve); /* M = t3 * t0 */ |
| |
| /* X' = M^2 - 2*S */ |
| bnMulMod_(curve->t2, curve->U1, curve->U1, curve->p, curve); /* t2 = M^2 */ |
| bnMulMod_(curve->t0, curve->S1, mpiTwo, curve->p, curve); /* t0 = S * 2 */ |
| bnCopy(R->x, curve->t2); |
| bnSubMod_(R->x, curve->t0, curve->p); /* X' = t2 - t0 */ |
| |
| /* Y' = M*(S - X') - 8*Y^4 */ |
| bnMulMod_(curve->t3, curve->t1, curve->t1, curve->p, curve); /* t3 = Y^4 (t1 saved above) */ |
| bnMulMod_(curve->t2, curve->t3, mpiEight, curve->p, curve); /* t2 = t3 * 8 */ |
| bnCopy(curve->t3, curve->S1); |
| bnSubMod_(curve->t3, R->x, curve->p); /* t3 = S - X' */ |
| bnMulMod_(curve->t0, curve->U1, curve->t3, curve->p, curve); /* t0 = M * t3 */ |
| bnCopy(R->y, curve->t0); |
| bnSubMod_(R->y, curve->t2, curve->p); /* Y' = t0 - t2 */ |
| |
| /* Z' = 2*Y*Z */ |
| bnMulMod_(curve->t0, ptP->y, mpiTwo, curve->p, curve); /* t0 = 2 * Y */ |
| bnMulMod_(R->z, curve->t0, ptP->z, curve->p, curve); /* Z' = to * Z */ |
| |
| if (P == R) |
| FREE_EC_POINT(&tP); |
| |
| return ret; |
| } |
| |
| static int ecDoublePointEd(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| EcPoint tP; |
| const EcPoint *ptP = 0; |
| |
| /* Check for overlapping arguments, copy if necessary and set pointer */ |
| if (P == R) { |
| INIT_EC_POINT(&tP); |
| ptP = &tP; |
| bnCopy(tP.x, P->x); |
| bnCopy(tP.y, P->y); |
| bnCopy(tP.z, P->z); |
| } |
| else |
| ptP = P; |
| |
| /* Compute B, C, D, H, E */ |
| bnCopy(curve->t1, ptP->x); |
| bnAddMod_(curve->t1, ptP->y, curve->p); |
| bnSquareMod_(curve->t0, curve->t1, curve->p, curve); /* t0 -> B */ |
| |
| bnSquareMod_(R->x, ptP->x, curve->p, curve); /* Rx -> C */ |
| |
| bnSquareMod_(R->y, ptP->y, curve->p, curve); /* Ry -> D */ |
| |
| bnSquareMod_(R->z, ptP->z, curve->p, curve); /* Rz -> H */ |
| bnAddMod_(R->z, R->z, curve->p); /* Rz -> 2H */ |
| |
| bnCopy(curve->t1, R->x); |
| bnAddMod_(curve->t1, R->y, curve->p); /* t1 -> E */ |
| |
| /* Compute Ry */ |
| bnCopy(curve->t2, R->x); |
| bnSubMod_(curve->t2, R->y, curve->p); /* C - D */ |
| bnMulMod_(R->y, curve->t1, curve->t2, curve->p, curve); /* E * t3; Ry */ |
| |
| /* Compute Rx */ |
| bnSubMod_(curve->t0, curve->t1, curve->p); /* B - E; sub result */ |
| bnCopy(curve->t2, curve->t1); |
| bnSubMod_(curve->t2, R->z, curve->p); /* t2 -> J; (E - 2H) */ |
| bnMulMod_(R->x, curve->t2, curve->t0, curve->p, curve); /* J * t0 */ |
| |
| /* Compute Rz */ |
| bnMulMod_(R->z, curve->t2, curve->t1, curve->p, curve); /* J * E */ |
| |
| if (P == R) |
| FREE_EC_POINT(&tP); |
| |
| return 0; |
| } |
| |
| /* |
| * Curve25519 has no specific Double Point function, all inside curve25519-donna |
| */ |
| static int ecDoublePoint25519(const EcCurve *curve, EcPoint *R, const EcPoint *P) |
| { |
| return -2; |
| } |
| |
| /* Add two elliptic curve points. Any of them may be the same object. */ |
| int ecAddPoint(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q) |
| { |
| return curve->addOp(curve, R, P, Q); |
| } |
| |
| static int ecAddPointNist(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q) |
| { |
| int ret = 0; |
| |
| EcPoint tP, tQ; |
| const EcPoint *ptP = 0; |
| const EcPoint *ptQ = 0; |
| |
| |
| /* Fast check if application called add(R, P, P) */ |
| if (!bnCmp(P->x, Q->x) && !bnCmp(P->y, Q->y) && !bnCmp(P->z, Q->z)) { |
| return ecDoublePoint(curve, R, P); |
| } |
| |
| /* if P is (@,@), R = Q */ |
| if (!bnCmp(P->z, mpiZero)) { |
| bnCopy(R->x, Q->x); |
| bnCopy(R->y, Q->y); |
| bnCopy(R->z, Q->z); |
| return 0; |
| } |
| |
| /* if Q is (@,@), R = P */ |
| if (!bnCmp(Q->z, mpiZero)) { |
| bnCopy(R->x, P->x); |
| bnCopy(R->y, P->y); |
| bnCopy(R->z, P->z); |
| return 0; |
| } |
| |
| /* Check for overlapping arguments, copy if necessary and set pointers */ |
| if (P == R) { |
| INIT_EC_POINT(&tP); |
| ptP = &tP; |
| bnCopy(tP.x, P->x); |
| bnCopy(tP.y, P->y); |
| bnCopy(tP.z, P->z); |
| } |
| else |
| ptP = P; |
| |
| if (Q == R) { |
| INIT_EC_POINT(&tQ); |
| ptQ = &tQ; |
| bnCopy(tQ.x, Q->x); |
| bnCopy(tQ.y, Q->y); |
| bnCopy(tQ.z, Q->z); |
| } |
| else |
| ptQ = Q; |
| |
| /* U1 = X1*Z2^2, where X1: P->x, Z2: Q->z */ |
| bnMulMod_(curve->t1, ptQ->z, ptQ->z, curve->p, curve); /* t1 = Z2^2 */ |
| bnMulMod_(curve->U1, ptP->x, curve->t1, curve->p, curve); /* U1 = X1 * z_2 */ |
| |
| /* S1 = Y1*Z2^3, where Y1: P->y */ |
| bnMulMod_(curve->t1, curve->t1, ptQ->z, curve->p, curve); /* t1 = Z2^3 */ |
| bnMulMod_(curve->S1, ptP->y, curve->t1, curve->p, curve); /* S1 = Y1 * z_2 */ |
| |
| /* U2 = X2*Z1^2, where X2: Q->x, Z1: P->z */ |
| bnMulMod_(curve->t1, ptP->z, ptP->z, curve->p, curve); /* t1 = Z1^2 */ |
| bnMulMod_(curve->H, ptQ->x, curve->t1, curve->p, curve); /* H = X2 * t1 (store U2 in H) */ |
| |
| /* H = U2 - U1 */ |
| bnSubMod_(curve->H, curve->U1, curve->p); |
| |
| /* S2 = Y2*Z1^3, where Y2: Q->y */ |
| bnMulMod_(curve->t1, curve->t1, ptP->z, curve->p, curve); /* t1 = Z1^3 */ |
| bnMulMod_(curve->R, ptQ->y, curve->t1, curve->p, curve); /* R = Y2 * t1 (store S2 in R) */ |
| |
| /* R = S2 - S1 */ |
| bnSubMod_(curve->R, curve->S1, curve->p); |
| |
| /* if (U1 == U2), i.e H is zero */ |
| if (!bnCmp(curve->H, mpiZero)) { |
| |
| /* if (S1 != S2), i.e. R is _not_ zero: return infinity*/ |
| if (bnCmp(curve->R, mpiZero)) { |
| bnSetQ(R->x, 1); |
| bnSetQ(R->y, 1); |
| bnSetQ(R->z, 0); |
| return 0; |
| } |
| return ecDoublePoint(curve, R, P); |
| } |
| /* X3 = R^2 - H^3 - 2*U1*H^2, where X3: R->x */ |
| bnMulMod_(curve->t0, curve->H, curve->H, curve->p, curve); /* t0 = H^2 */ |
| bnMulMod_(curve->t1, curve->U1, curve->t0, curve->p, curve); /* t1 = U1 * t0, (hold t1) */ |
| bnMulMod_(curve->t0, curve->t0, curve->H, curve->p, curve); /* t0 = H^3, (hold t0) */ |
| bnMulMod_(curve->t2, curve->R, curve->R, curve->p, curve); /* t2 = R^2 */ |
| bnCopy(curve->t3, curve->t2); |
| bnSubMod_(curve->t3, curve->t0, curve->p); /* t3 = t2 - t0, (-H^3)*/ |
| bnMulMod_(curve->t2, mpiTwo, curve->t1, curve->p, curve); /* t2 = 2 * t1 */ |
| bnCopy(R->x, curve->t3); |
| bnSubMod_(R->x, curve->t2, curve->p); /* X3 = t3 - t2 */ |
| |
| /* Y3 = R*(U1*H^2 - X3) - S1*H^3, where Y3: R->y */ |
| bnSubMod_(curve->t1, R->x, curve->p); /* t1 = t1 - X3, overwrites t1 now */ |
| bnMulMod_(curve->t2, curve->R, curve->t1, curve->p, curve); /* t2 = R * z_2 */ |
| bnMulMod_(curve->S1, curve->S1, curve->t0, curve->p, curve); /* S1 = S1 * t0, (t0 has H^3) */ |
| bnCopy(R->y, curve->t2); |
| bnSubMod_(R->y, curve->S1, curve->p); /* Y3 = t2 - S1 */ |
| |
| /* Z3 = H*Z1*Z2, where Z1: P->z, Z2: Q->z, Z3: R->z */ |
| bnMulMod_(curve->t2, curve->H, P->z, curve->p, curve); /* t2 = H * Z1 */ |
| bnMulMod_(R->z, curve->t2, Q->z, curve->p, curve); /* Z3 = t2 * Z2 */ |
| |
| if (P == R) |
| FREE_EC_POINT(&tP); |
| if (Q == R) |
| FREE_EC_POINT(&tQ); |
| return ret; |
| } |
| |
| /* |
| * Refer to the document: Faster addition and doubling on elliptic curves; Daniel J. Bernstein and Tanja Lange |
| * section 4. |
| * |
| * This function is a variant of the 'addition'. The function returns the result in an own curve point |
| * and does not overwrite its input parameters. |
| */ |
| static int ecAddPointEd(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q) |
| { |
| EcPoint tP, tQ; |
| const EcPoint *ptP = 0; |
| const EcPoint *ptQ = 0; |
| |
| /* if P is (@,@), R = Q */ |
| if (!bnCmp(P->z, mpiZero)) { |
| bnCopy(R->x, Q->x); |
| bnCopy(R->y, Q->y); |
| bnCopy(R->z, Q->z); |
| return 0; |
| } |
| |
| /* if Q is (@,@), R = P */ |
| if (!bnCmp(Q->z, mpiZero)) { |
| bnCopy(R->x, P->x); |
| bnCopy(R->y, P->y); |
| bnCopy(R->z, P->z); |
| return 0; |
| } |
| |
| /* Check for overlapping arguments, copy if necessary and set pointers */ |
| if (P == R) { |
| INIT_EC_POINT(&tP); |
| ptP = &tP; |
| bnCopy(tP.x, P->x); |
| bnCopy(tP.y, P->y); |
| bnCopy(tP.z, P->z); |
| } |
| else |
| ptP = P; |
| |
| if (Q == R) { |
| INIT_EC_POINT(&tQ); |
| ptQ = &tQ; |
| bnCopy(tQ.x, Q->x); |
| bnCopy(tQ.y, Q->y); |
| bnCopy(tQ.z, Q->z); |
| } |
| else |
| ptQ = Q; |
| |
| /* Compute A, C, D first */ |
| bnMulMod_(R->z, ptP->z, ptQ->z, curve->p, curve); /* Rz -> A; (Z1 * z2); Rz becomes R3 */ |
| bnMulMod_(R->x, ptP->x, ptQ->x, curve->p, curve); /* Rx -> C; (X1 * X2); Rx becomes R1 */ |
| bnMulMod_(R->y, ptP->y, ptQ->y, curve->p, curve); /* Ry -> D; (Y1 * Y2); Ry becomes R2 */ |
| |
| /* Compute large parts of X3 equation, sub result in t0 */ |
| bnCopy(curve->t0, ptP->x); |
| bnAddMod_(curve->t0, ptP->y, curve->p); /* t0 -> X1 + Y1 */ |
| bnCopy(curve->t1, ptQ->x); |
| bnAddMod_(curve->t1, ptQ->y, curve->p); /* t1 -> X2 + Y2 */ |
| bnMulMod_(curve->t2, curve->t0, curve->t1, curve->p, curve); /* t2 = t0 * t1 */ |
| bnSubMod_(curve->t2, R->x, curve->p); /* t2 - C */ |
| bnSubMod_(curve->t2, R->y, curve->p); /* t2 - D */ |
| bnMulMod_(curve->t0, curve->t2, R->z, curve->p, curve); /* t0 -> R7; (t2 * A); sub result */ |
| |
| /* Compute E */ |
| bnMulMod_(curve->t2, R->x, R->y, curve->p, curve); /* t2 = C * D */ |
| bnMulMod_(curve->t1, curve->t2, curve->a, curve->p, curve); /* t1 -> E; t1 new R8 */ |
| |
| /* Compute part of Y3 equation, sub result in t2 */ |
| bnSubMod_(R->y, R->x, curve->p); /* Ry = D - C; sub result */ |
| bnMulMod_(curve->t2, R->y, R->z, curve->p, curve); /* t2 = Ry * A; sub result */ |
| |
| /* Compute B */ |
| bnSquareMod_(R->z, R->z, curve->p, curve); /* Rz -> B; (A^2) */ |
| |
| /* Compute F */ |
| bnCopy(curve->t3, R->z); |
| bnSubMod_(curve->t3, curve->t1, curve->p); /* t3 -> F; (B - E) */ |
| |
| /* Compute G */ |
| bnAddMod_(R->z, curve->t1, curve->p); /* Rz -> G; (B + E) */ |
| |
| /* Compute, X, Y, Z results */ |
| bnMulMod_(R->x, curve->t3, curve->t0, curve->p, curve); /* Rx = F * t0 */ |
| bnMulMod_(R->y, curve->t2, R->z, curve->p, curve); /* Ry = t2 * G */ |
| bnMulMod_(R->z, curve->t3, R->z, curve->p, curve); /* Rz = F * G */ |
| |
| if (P == R) |
| FREE_EC_POINT(&tP); |
| if (Q == R) |
| FREE_EC_POINT(&tQ); |
| |
| return 0; |
| } |
| |
| /* |
| * Curve25519 has no specific Add Point function, all inside curve25519-donna |
| */ |
| static int ecAddPoint25519(const EcCurve *curve, EcPoint *R, const EcPoint *P, const EcPoint *Q) |
| { |
| return -2; |
| } |
| |
| int ecMulPointScalar(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar) |
| { |
| return curve->mulScalar(curve, R, P, scalar); |
| } |
| |
| static int ecMulPointScalarNormal(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar) |
| { |
| int ret = 0; |
| int i; |
| int bits = bnBits(scalar); |
| EcPoint n; |
| |
| INIT_EC_POINT(&n); |
| bnCopy(n.x, P->x); |
| bnCopy(n.y, P->y); |
| bnCopy(n.z, P->z); |
| |
| bnSetQ(R->x, 0); |
| bnSetQ(R->y, 0); |
| bnSetQ(R->z, 0); |
| |
| for (i = 0; i < bits; i++) { |
| if (bnReadBit(scalar, i)) |
| ecAddPoint(curve, R, R, &n); |
| |
| /* ecAddPoint(curve, &n, &n, &n); */ |
| ecDoublePoint(curve, &n, &n); |
| } |
| FREE_EC_POINT(&n); |
| return ret; |
| } |
| |
| /* |
| * This function uses BigNumber only as containers to transport the 32 byte data. |
| * This makes it compliant to the other functions and thus higher-level API does not change. |
| * |
| * curve25519_donna function uses data in little endian format. |
| */ |
| static int ecMulPointScalar25519(const EcCurve *curve, EcPoint *R, const EcPoint *P, const BigNum *scalar) |
| { |
| uint8_t basepoint[32], secret[32], result[32]; |
| |
| bnExtractLittleBytes(P->x, basepoint, 0, 32); /* 25519 function requires the X coordinate only (compressed) */ |
| bnExtractLittleBytes(scalar, secret, 0, 32); |
| curve25519_donna(result, secret, basepoint); |
| bnInsertLittleBytes(R->x, result, 0, 32); |
| return 0; |
| } |
| |
| #ifdef WEAKRANDOM |
| #include <fcntl.h> |
| |
| /* |
| * A standard random number generator that uses the portable random() system function. |
| * |
| * This should be enhanced to use a better random generator |
| */ |
| static int _random(unsigned char *output, size_t len) |
| { |
| size_t num = 0; |
| |
| int rnd = open("/dev/urandom", O_RDONLY); |
| if (rnd >= 0) { |
| num = read(rnd, output, len); |
| close(rnd); |
| } |
| else |
| return num; |
| |
| return( 0 ); |
| } |
| #else |
| #include <cryptcommon/ZrtpRandom.h> |
| static int _random(unsigned char *output, size_t len) |
| { |
| return zrtp_getRandomData(output, len); |
| } |
| #endif |
| |
| int ecGenerateRandomNumber(const EcCurve *curve, BigNum *d) |
| { |
| return curve->randomOp(curve, d); |
| } |
| |
| static int ecGenerateRandomNumberNist(const EcCurve *curve, BigNum *d) |
| { |
| BigNum c, nMinusOne; |
| |
| size_t randomBytes = ((bnBits(curve->n) + 64) + 7) / 8; |
| |
| uint8_t *ran = malloc(randomBytes); |
| |
| bnBegin(&c); |
| bnBegin(&nMinusOne); |
| |
| bnCopy(&nMinusOne, curve->n); |
| bnSubMod_(&nMinusOne, mpiOne, curve->p); |
| |
| bnSetQ(d, 0); |
| |
| while (!bnCmpQ(d, 0)) { |
| /* use _random function */ |
| _random(ran, randomBytes); |
| bnInsertBigBytes(&c, ran, 0, randomBytes); |
| bnMod(d, &c, &nMinusOne); |
| bnAddMod_(d, mpiOne, curve->p); |
| } |
| |
| bnEnd(&c); |
| bnEnd(&nMinusOne); |
| free(ran); |
| |
| return 0; |
| } |
| |
| static int ecGenerateRandomNumber3617(const EcCurve *curve, BigNum *d) |
| { |
| unsigned char random[52]; |
| _random(random, 52); |
| |
| /* prepare the secret random data: clear bottom 3 bits. Clearing top 2 bits |
| * makes is a 414 bit value |
| */ |
| random[51] &= ~0x7; |
| random[0] &= 0x3f; |
| /* convert the random data into big numbers */ |
| bnInsertBigBytes(d, random, 0, 52); |
| return 0; |
| } |
| |
| static int ecGenerateRandomNumber25519(const EcCurve *curve, BigNum *d) |
| { |
| unsigned char random[32]; |
| _random(random, 32); |
| |
| /* No specific preparation. The curve25519_donna functions prepares the data. |
| * |
| * convert the random data into big numbers. the bigNumber is a container only. |
| * we don not use the big number for any arithmetic |
| */ |
| bnInsertLittleBytes(d, random, 0, 32); |
| return 0; |
| |
| } |
| |
| int ecCheckPubKey(const EcCurve *curve, const EcPoint *pub) |
| { |
| return curve->checkPubOp(curve, pub); |
| } |
| |
| static int ecCheckPubKeyNist(const NistECpCurve *curve, const EcPoint *pub) |
| { |
| /* Represent point at infinity by (0, 0), make sure it's not that */ |
| if (bnCmpQ(pub->x, 0) == 0 && bnCmpQ(pub->y, 0) == 0) { |
| return 0; |
| } |
| /* Check that coordinates are within range */ |
| if (bnCmpQ(pub->x, 0) < 0 || bnCmp(pub->x, curve->p) >= 0) { |
| return 0; |
| } |
| if (bnCmpQ(pub->y, 0) < 0 || bnCmp(pub->y, curve->p) >= 0) { |
| return 0; |
| } |
| /* Check that point satisfies EC equation y^2 = x^3 - 3x + b, mod P */ |
| bnSquareMod_(curve->t1, pub->y, curve->p, curve); |
| bnSquareMod_(curve->t2, pub->x, curve->p, curve); |
| bnSubQMod_(curve->t2, 3, curve->p); |
| bnMulMod_(curve->t2, curve->t2, pub->x, curve->p, curve); |
| bnAddMod_(curve->t2, curve->b, curve->p); |
| if (bnCmp (curve->t1, curve->t2) != 0) { |
| return 0; |
| } |
| return 1; |
| |
| } |
| |
| static int ecCheckPubKey3617(const EcCurve *curve, const EcPoint *pub) |
| { |
| /* Represent point at infinity by (0, 0), make sure it's not that */ |
| if (bnCmpQ(pub->x, 0) == 0 && bnCmpQ(pub->y, 0) == 0) { |
| return 0; |
| } |
| /* Check that coordinates are within range */ |
| if (bnCmpQ(pub->x, 0) < 0 || bnCmp(pub->x, curve->p) >= 0) { |
| return 0; |
| } |
| if (bnCmpQ(pub->y, 0) < 0 || bnCmp(pub->y, curve->p) >= 0) { |
| return 0; |
| } |
| /* Check that point satisfies EC equation x^2+y^2 = 1+3617x^2y^2, mod P */ |
| bnSquareMod_(curve->t1, pub->y, curve->p, curve); |
| bnSquareMod_(curve->t2, pub->x, curve->p, curve); |
| bnCopy(curve->t3, curve->t1); /* Load t3 */ |
| bnAddMod_(curve->t3, curve->t2, curve->p); /* t3 = t1 + t2, (x^2+y^2)*/ |
| |
| bnMulMod_(curve->t0, curve->a, curve->t1, curve->p, curve); /* t0 = a * t1, (3617 * x^2) */ |
| bnMulMod_(curve->t0, curve->t0, curve->t2, curve->p, curve); /* t0 = t0 * t1, (3617 * x^2 * y^2) */ |
| bnAddMod_(curve->t0, mpiOne, curve->p); /* t0 = t0 + 1, (3617 * x^2 * y^2 + 1) */ |
| |
| if (bnCmp (curve->t0, curve->t3) != 0) { |
| return 0; |
| } |
| return 1; |
| } |
| |
| /** |
| * According to http://cr.yp.to/ecdh.html#validate no validation is required if used for Diffie-Hellman |
| * thus always return success. |
| */ |
| static int ecCheckPubKey25519(const EcCurve *curve, const EcPoint *pub) |
| { |
| return 1; |
| } |
| |
| static int mod3617(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| unsigned char buffer[52] = {0}; |
| int cmp; |
| BigNum tmp; |
| |
| bnBegin(&tmp); |
| cmp = bnCmp(modulo, a); |
| if (cmp == 0) { /* a is equal modulo, set resul to zero */ |
| bnSetQ(r, 0); |
| return 0; |
| } |
| if (cmp > 0) { /* modulo is greater than a - copy a to r and return it */ |
| bnCopy(r, a); |
| return 0; |
| } |
| bnExtractLittleBytes(a, buffer, 0, 52); |
| buffer[51] &= 0x3f; |
| |
| bnCopy(&tmp, a); |
| bnRShift(&tmp, 414); |
| bnCopy(r, &tmp); |
| bnLShift(r, 4); |
| bnAdd(r, &tmp); |
| |
| bnInsertLittleBytes(&tmp, buffer, 0, 52); |
| |
| bnAdd(r, &tmp); |
| while (bnCmp(r, modulo) >= 0) { |
| bnSub(r, modulo); |
| } |
| bnEnd(&tmp); |
| return 0; |
| } |
| |
| /* |
| * Curve25519 has no specific modulo function, all inside curve25519-donna |
| */ |
| static int mod25519(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| return -2; |
| } |
| |
| /* |
| * Beware: Here are the dragons. |
| * |
| * The modulo implementations for the NIST curves. For more detailled information see |
| * FIPS 186-3, chapter D.2 and other papers about Generailzed Mersenne numbers. |
| * |
| * I use byte operations to perfom the additions with carry. On a little endian machine |
| * this saves conversion from/to big endian format if I would use integers for example. Also |
| * using byte addition into a short carry accumulator works on every word size and avoids |
| * complex testing and handling of wordsizes and big/little endian stuff. |
| * |
| */ |
| |
| /* new modulo for 192bit curve */ |
| static int newMod192(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| unsigned char buffer[200] = {0}; |
| unsigned char *pt; |
| unsigned char *ps1; |
| unsigned char *ps2; |
| unsigned char *ps3; |
| short ac; |
| int cmp; |
| |
| /* Binary big number representation in PolarSSL is always big endian |
| * |
| * the least significant 64bit large word starts at byte offset 40, |
| * the least significant 32bit word starts at byte offset 44 |
| * the least significant byte starts at byte offset 47 |
| * |
| * S3 S2 S1 T |
| * /-----^------\ |
| * A5 A4 A3 A2 A1 A0 |
| * 64bit 0 1 2 3 4 5 |
| * |--+--|--+--|--+--|--+--|--+--|--+--| |
| * 32bit 0 1 2 3 4 5 6 7 8 9 10 11 |
| * |
| * perform T + S1 + S2 + S3 mod p |
| |
| * where T = (A2 || A1 || A0) |
| * + S1 = ( 0 || A3 || A3) |
| * + S2 = (A4 || A4 || 0) |
| * + S3 = (A5 || A5 || A5) |
| * |
| * TODO: error check if input variable is > modulo^2 (do normal mpi_mod_mpi), |
| */ |
| |
| /* TODO: check if a is > modulo^2 */ |
| cmp = bnCmp(modulo, a); |
| if (cmp == 0) { /* a is equal modulo, set resul to zero */ |
| bnSetQ(r, 0); |
| return 0; |
| } |
| if (cmp > 0) { /* modulo is greater than a - copy a to r and return it */ |
| bnCopy(r, a); |
| return 0; |
| } |
| bnExtractBigBytes(a, buffer, 0, bnBytes(modulo)*2); |
| |
| /* 6 'A' words, each word is 8 byte. Compute offset to least significant byte of word X */ |
| #define A(X) buffer + (((6-X)*8)-1) |
| |
| ac = 0; |
| |
| pt = A(0); /* pt points to least significant byte of A0 */ |
| |
| /* Add up first 8 byte word, no need to add ps2 */ |
| ps1 = A(3); /* ps1 points to least significant byte of S1 (A3) */ |
| ps3 = A(5); /* ps3 points to least significant byte of S3 (A5)*/ |
| |
| /* Each block processes one 32 bit word, big endian, using byte operations */ |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| /* Add up second 8 byte word, all three S words are used here */ |
| ps1 = A(3); ps2 = A(4); ps3 = A(5); |
| |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1--; ac += *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| /* Add up third 8 byte word, no need to add S1 word */ |
| ps2 = A(4); ps3 = A(5); |
| |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; *pt-- = ac; ac >>= 8; |
| |
| /* In this function we cannot have a negative carry and at most a carry of 2 |
| * thus just subtract the modulo until we are less than modulo |
| */ |
| bnSetQ(r, 0); |
| |
| *(A(3)) = ac; /* Store the carry */ |
| bnInsertBigBytes(r, A(3), 0, 25); /* 25: 3 * 8 byte words + 1 carry byte */ |
| while (bnCmp(r, modulo) >= 0) { |
| bnSub(r, modulo); |
| } |
| return 0; |
| } |
| #undef A |
| |
| /* new modulo for 256bit curve */ |
| static int newMod256(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| unsigned char buffer[200] = {0}; |
| unsigned char *pt; |
| unsigned char *ps1; |
| unsigned char *ps2; |
| unsigned char *ps3; |
| unsigned char *ps4; |
| |
| unsigned char *pd1; |
| unsigned char *pd2; |
| unsigned char *pd3; |
| unsigned char *pd4; |
| short ac; |
| int cmp; |
| |
| /* Binary big number representation in PolarSSL is always big endian |
| * |
| * the least significant byte starts at byte offset 63 |
| * |
| * T |
| * /-----------------^------------------\ |
| * A15 A14 A13 A12 A11 A10 A9 A8 A7 A6 A5 A4 A3 A2 A1 A0 |
| * |----+----|----+----|----+----|----+----|----+----|----+----|----+----|----+----| |
| * offset 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 |
| * |
| * T = ( A7 || A6 || A5 || A4 || A3 || A2 || A1 || A0 ) |
| * |
| * S1 = ( A15 || A14 || A13 || A12 || A11 || 00 || 00 || 00 ) |
| * S2 = ( 00 || A15 || A14 || A13 || A12 || 00 || 00 || 00 ) |
| * S3 = ( A15 || A14 || 00 || 00 || 00 || A10 || A9 || A8 ) |
| * S4 = ( A8 || A13 || A15 || A14 || A13 || A11 || A10 || A9 ) |
| * D1 = ( A10 || A8 || 00 || 00 || 00 || A13 || A12 || A11 ) |
| * D2 = ( A11 || A9 || 00 || 00 || A15 || A14 || A13 || A12 ) |
| * D3 = ( A12 || 00 || A10 || A9 || A8 || A15 || A14 || A13 ) |
| * D4 = ( A13 || 00 || A11 || A10 || A9 || 00 || A15 || A14 ) |
| * |
| * perform B = T + 2*S1 + 2*S2 + S3 + S4 - D1 - D2 - D3 - D4 mod p |
| * |
| * TODO: error check if input variable is > modulo^2 (do normal mpi_mod_mpi), |
| */ |
| |
| cmp = bnCmp(modulo, a); |
| if (cmp == 0) { /* a is equal modulo, set resul to zero */ |
| bnSetQ(r, 0); |
| return 0; |
| } |
| if (cmp > 0) { /* modulo is greater than a - copya to r and return it */ |
| bnCopy(r, a); |
| return 0; |
| } |
| bnExtractBigBytes(a, buffer, 0, bnBytes(modulo)*2); |
| |
| /* 16 'A' words, each word is 4 byte. Compute offset to least significant byte of word X */ |
| #define A(X) buffer + (((16-X)*4)-1) |
| |
| ac = 0; |
| |
| pt = A(0); /* pt points to least significant byte of A0 */ |
| |
| /* Set up to add up data that goes into A0 (right-most column abover); S1, S2 not used */ |
| ps3 = A(8); /* ps3 points to least significant byte of S3 */ |
| ps4 = A(9); /* ps4 points to least significant byte of S4 */ |
| pd1 = A(11); /* pd1 points to least significant byte of D1 */ |
| pd2 = A(12); /* pd2 points to least significant byte of D2 */ |
| pd3 = A(13); /* pd3 points to least significant byte of D3 */ |
| pd4 = A(14); /* pd4 points to least significant byte of D4 */ |
| |
| /* Each block processes one 32 bit word, big endian, using byte operations */ |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A1; S1, S2 not used */ |
| ps3 = A(9); ps4 = A(10); pd1 = A(12); pd2 = A(13); pd3 = A(14); pd4 = A(15); |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A2; S1, S2, D4 not used */ |
| ps3 = A(10); ps4 = A(11); pd1 = A(13); pd2 = A(14); pd3 = A(15); |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A3; S3, D1 not used */ |
| ps1 = A(11); ps2 = A(12); ps4 = A(13); pd2 = A(15); pd3 = A(8); pd4 = A(9); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A4; S3, D1, D2 not used */ |
| ps1 = A(12); ps2 = A(13); ps4 = A(14); pd3 = A(9); pd4 = A(10); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A5; S3, D1, D2 not used */ |
| ps1 = A(13); ps2 = A(14); ps4 = A(15); pd3 = A(10); pd4 = A(11); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps4--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A6; D3, D4 not used */ |
| ps1 = A(14); ps2 = A(15); ps3 = A(14); ps4 = A(13); pd1 = A(8); pd2 = A(9); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2;ac += *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add up data that goes into A7; S2 not used */ |
| ps1 = A(15); ps3 = A(15); ps4 = A(8); pd1 = A(10); pd2 = A(11); pd3 = A(12); pd4 = A(13); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; ac -= *pd4--; *pt-- = ac; ac >>= 8; |
| |
| bnSetQ(r, 0); |
| if (ac > 0) { |
| *(A(8)) = ac; /* Store the carry */ |
| bnInsertBigBytes(r, A(8), 0, 33); /* 33: 8 * 4 byte words + 1 carry byte */ |
| } |
| /* Negative carry requires that we add the modulo (carry * -1) times to make |
| * the result positive. Then get the result mod(256). |
| */ |
| else if (ac < 0) { |
| int msb, maxMsb; |
| |
| *(A(8)) = 0; |
| bnInsertBigBytes(r, A(8), 0, 33); /* 33: 8 * 4 byte words + 1 carry byte */ |
| ac *= -1; |
| while (ac--) { |
| bnAdd(r, modulo); |
| } |
| maxMsb = bnBits(modulo); |
| msb = bnBits(r) - maxMsb; |
| /* clear all bits above bit length of modulo. This length is 256 here, thus |
| * we effectiviely doing a mod(256) |
| */ |
| if (msb > 0) { |
| BigNum tmp; |
| bnBegin(&tmp); |
| bnSetQ (&tmp, 1); |
| bnLShift (&tmp, maxMsb); |
| bnMod(r, r, &tmp); |
| bnEnd(&tmp); |
| } |
| } |
| else { |
| *(A(8)) = 0; |
| bnInsertBigBytes(r, A(8), 0, 33); /* 33: 8 * 4 byte words + 1 carry byte */ |
| } |
| while (bnCmp(r, modulo) >= 0) { |
| bnSub(r, modulo); |
| } |
| return 0; |
| } |
| #undef A |
| |
| |
| /* new modulo for 384bit curve */ |
| static int newMod384(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| unsigned char buffer[200] = {0}; |
| unsigned char *pt; |
| unsigned char *ps1; |
| unsigned char *ps2; |
| unsigned char *ps3; |
| unsigned char *ps4; |
| unsigned char *ps5; |
| unsigned char *ps6; |
| |
| unsigned char *pd1; |
| unsigned char *pd2; |
| unsigned char *pd3; |
| short ac; |
| int cmp; |
| |
| /* |
| * |
| * the least significant byte starts at byte offset 97 |
| * |
| * T |
| * /---------------------------^----------------------------\ |
| * A23 ......... A15 A14 A13 A12 A11 A10 A9 A8 A7 A6 A5 A4 A3 A2 A1 A0 |
| * |----+ ...... |----+----|----+----|----+----|----+----|----+----|----+----|----+----|----+----| |
| * |
| * T = (A11 || A10 || A9 || A8 || A7 || A6 || A5 || A4 || A3 || A2 || A1 || A0) |
| |
| * S1 = ( 00 || 00 || 00 || 00 || 00 || A23 || A22 || A21 || 00 || 00 || 00 || 00) |
| * S2 = (A23 || A22 || A21 || A20 || A19 || A18 || A17 || A16 || A15 || A14 || A13 || A12) |
| * S3 = (A20 || A19 || A18 || A17 || A16 || A15 || A14 || A13 || A12 || A23 || A22 || A21) |
| * S4 = (A19 || A18 || A17 || A16 || A15 || A14 || A13 || A12 || A20 || 00 || A23 || 00) |
| * S5 = ( 00 || 00 || 00 || 00 || A23 || A22 || A21 || A20 || 00 || 00 || 00 || 00) |
| * S6 = ( 00 || 00 || 00 || 00 || 00 || 00 || A23 || A22 || A21 || 00 || 00 || A20) |
| * D1 = (A22 || A21 || A20 || A19 || A18 || A17 || A16 || A15 || A14 || A13 || A12 || A23) |
| * D2 = ( 00 || 00 || 00 || 00 || 00 || 00 || 00 || A23 || A22 || A21 || A20 || 00) |
| * D3 = ( 00 || 00 || 00 || 00 || 00 || 00 || 00 || A23 || A23 || 00 || 00 || 00) |
| * |
| * perform B = T + 2S1 + S2 + S3 + S4 + S5 + S6 – D1 – D2 – D3 mod p |
| * |
| * TODO: error check if input variable is > modulo^2 (do normal mpi_mod_mpi), |
| * optimize if input is already < modulo (just copy over in this case). |
| */ |
| |
| cmp = bnCmp(modulo, a); |
| if (cmp == 0) { /* a is equal modulo, set resul to zero */ |
| bnSetQ(r, 0); |
| return 0; |
| } |
| if (cmp > 0) { /* modulo is greater than a - copy a to r and return it */ |
| bnCopy(r, a); |
| return 0; |
| } |
| |
| bnExtractBigBytes(a, buffer, 0, bnBytes(modulo)*2); |
| |
| /* 24 'A' words, each word is 4 byte. Compute offset to least significant byte of word X */ |
| #define A(X) buffer + (((24-X)*4)-1) |
| |
| ac = 0; |
| |
| pt = A(0); /* pt points to least significant byte of A0 */ |
| |
| /* Set up to add data that goes into A0; S1, S4, S5, D2, D3 not used */ |
| ps2 = A(12); ps3 = A(21); ps6 = A(20); pd1 = A(23); |
| |
| /* Each block processes one 32 bit word, big endian, using byte operations */ |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A1; S1, S5, S6, D3 not used */ |
| ps2 = A(13); ps3 = A(22); ps4 = A(23); pd1= A(12); pd2 = A(20); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A2; S1, S4, S5, S6, D3 not used */ |
| ps2 = A(14); ps3 = A(23); pd1 = A(13); pd2 = A(21); |
| ac += *pt + *ps2--; ac += *ps3--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac -= *pd1--; ac -= *pd2--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A3; S1, S5, S6 not used */ |
| ps2 = A(15); ps3 = A(12); ps4 = A(20); ps6 = A(21); pd1 = A(14); pd2 = A(22); pd3 = A(23); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A4 */ |
| ps1 = A(21); ps2 = A(16); ps3 = A(13); ps4 = A(12); ps5 = A(20); ps6 = A(22); pd1 = A(15); pd2 = A(23), pd3 = A(23); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; ac -= *pd2--; ac -= *pd3--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A5; D2, D3 not used */ |
| ps1 = A(22); ps2 = A(17); ps3 = A(14); ps4 = A(13); ps5 = A(21); ps6 = A(23); pd1 = A(16); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac += *ps6--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A6; S6, D2, D3 not used */ |
| ps1 = A(23); ps2 = A(18); ps3 = A(15); ps4 = A(14); ps5 = A(22); pd1 = A(17); |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps1;ac += *ps1--; ac += *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A7; S1, S6, D2, D3 not used */ |
| ps2 = A(19); ps3 = A(16); ps4 = A(15); ps5 = A(23); pd1 = A(18); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac += *ps5--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A8; S1, S5, S6, D2, D3 not used */ |
| ps2 = A(20); ps3 = A(17); ps4 = A(16); pd1 = A(19); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A9; S1, S5, S6, D2, D3 not used */ |
| ps2 = A(21); ps3 = A(18); ps4 = A(17); pd1 = A(20); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A10; S1, S5, S6, D2, D3 not used */ |
| ps2 = A(22); ps3 = A(19); ps4 = A(18); pd1 = A(21); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| /* Set up to add data that goes into A10; S1, S5, S6, D2, D3 not used */ |
| ps2 = A(23); ps3 = A(20); ps4 = A(19); pd1 = A(22); |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| ac += *pt + *ps2--; ac += *ps3--; ac += *ps4--; ac -= *pd1--; *pt-- = ac; ac >>= 8; |
| |
| bnSetQ(r, 0); |
| if (ac > 0) { |
| *(A(12)) = ac; /* Store the carry */ |
| bnInsertBigBytes(r, A(12), 0, 49); /* 49: 12 * 4 byte words + 1 carry byte */ |
| } |
| /* Negative carry requires that we add the modulo (carry * -1) times to make |
| * the result positive. Then get the result mod(256). |
| */ |
| else if (ac < 0) { |
| int msb, maxMsb; |
| |
| *(A(12)) = 0; |
| bnInsertBigBytes(r, A(12), 0, 49); /* 49: 12 * 4 byte words + 1 carry byte */ |
| ac *= -1; |
| while (ac--) { |
| bnAdd(r, modulo); |
| } |
| maxMsb = bnBits(modulo); |
| msb = bnBits(r) - maxMsb; |
| /* clear all bits above bit length of modulo. This length is 384 here, thus |
| * we effectiviely doing a mod(384) |
| */ |
| if (msb > 0) { |
| BigNum tmp; |
| bnBegin(&tmp); |
| bnSetQ (&tmp, 1); |
| bnLShift (&tmp, maxMsb); |
| bnMod(r, r, &tmp); |
| bnEnd(&tmp); |
| } |
| } |
| else { |
| *(A(12)) = 0; |
| bnInsertBigBytes(r, A(12), 0, 49); /* 49: 12 * 4 byte words + 1 carry byte */ |
| } |
| while (bnCmp(r, modulo) >= 0) { |
| bnSub(r, modulo); |
| } |
| return 0; |
| } |
| #undef A |
| |
| |
| /* new modulo for 521bit curve, much easier because the prime for 521 is a real Mersenne prime */ |
| static int newMod521(BigNum *r, const BigNum *a, const BigNum *modulo) |
| { |
| unsigned char buf1[200] = {0}; |
| unsigned char buf2[200] = {0}; |
| unsigned char *p1; |
| unsigned char *p2; |
| size_t modSize; |
| short ac = 0; |
| unsigned int i; |
| int cmp; |
| |
| /* TODO: check if a is > modulo^2 */ |
| #if 0 |
| if (a->s < 0) /* is it a negative value? */ |
| return bnMod(r, a, modulo); |
| #endif |
| cmp = bnCmp(modulo, a); |
| if (cmp == 0) { /* a is equal modulo, set resul to zero */ |
| bnSetQ(r, 0); |
| return 0; |
| } |
| bnCopy(r, a); |
| if (cmp > 0) { /* modulo is greater than a - return the prepared r */ |
| return 0; |
| } |
| modSize = bnBytes(modulo); |
| |
| bnExtractBigBytes(a, buf1, 0, modSize*2); /* a must be less modulo^2 */ |
| buf1[modSize] &= 1; /* clear all bits except least significat */ |
| |
| bnRShift(r, 521); |
| bnExtractBigBytes(r, buf2, 0, modSize*2); |
| buf2[modSize] &= 1; |
| |
| p1 = &buf2[131]; /* p1 is pointer to A0 */ |
| p2 = &buf1[131]; /* p2 is pointer to A1 */ |
| |
| for (i = 0; i < modSize; i++) { |
| ac += *p1 + *p2--; *p1-- = ac; ac >>= 8; |
| } |
| bnSetQ(r, 0); |
| bnInsertBigBytes(r, p1+1, 0, modSize); |
| |
| while (bnCmp(r, modulo) >= 0) { |
| bnSub(r, modulo); |
| } |
| return 0; |
| } |
| |