lib/nettle/ecc_projective_dbl_point_3.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GNUTLS.
   5  *
   6  * The GNUTLS library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation; either version 3 of
   9  * the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18  *
  19  */
  20
  21 /* Based on public domain code of LibTomCrypt by Tom St Denis.
  22  * Adapted to gmp and nettle by Nikos Mavrogiannopoulos.
  23  */
  24
  25 #include "ecc.h"
  26
  27 /*
  28   @file ecc_projective_dbl_point.c
  29   ECC Crypto, Tom St Denis
  30 */
  31
  32 #ifdef ECC_SECP_CURVES_ONLY
  33
  34 /*
  35    Double an ECC point
  36    @param P         The point to double
  37    @param R   [out] The destination of the double
  38    @param a         Curve's a value
  39    @param modulus   The modulus of the field the ECC curve is in
  40    @return          GNUTLS_E_SUCCESS on success
  41 */
  42 int
  43 ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a,
  44                               mpz_t modulus)
  45 {
  46    /* Using "dbl-2004-hmv" algorithm.
  47     * It costs 4M + 4S + half. */
  48    mpz_t t1, t2;
  49    int err;
  50
  51    if (P == NULL || R == NULL || modulus == NULL)
  52      return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
  53
  54    if ( (err = ecc_projective_isneutral(P, modulus)) == 1 ) {
  55
  56      if ((err = mp_init_multi(&t1, &t2, NULL)) != 0) {
  57         return err;
  58      }
  59
  60      if (P != R) {
  61        mpz_set(R->x, P->x);
  62        mpz_set(R->y, P->y);
  63        mpz_set(R->z, P->z);
  64      }
  65
  66      if (mpz_cmp_ui (P->z, 1) != 0) {
  67          /* t1 = Z * Z */
  68          mpz_mul(t1, R->z, R->z);
  69          mpz_mod(t1, t1, modulus);
  70          /* Z = Y * Z */
  71          mpz_mul(R->z, R->y, R->z);
  72          mpz_mod(R->z, R->z, modulus);
  73          /* Z = 2Z */
  74          mpz_add(R->z, R->z, R->z);
  75          if (mpz_cmp(R->z, modulus) >= 0) {
  76             mpz_sub(R->z, R->z, modulus);
  77          }
  78      } else {
  79          /* t1 = 1 */
  80          mpz_set(t1, P->z);
  81          /* Z = 2Y */
  82          mpz_add(R->z, R->y, R->y);
  83          if (mpz_cmp(R->z, modulus) >= 0) {
  84             mpz_sub(R->z, R->z, modulus);
  85          }
  86      }
  87
  88      /* T2 = X - T1 */
  89      mpz_sub(t2, R->x, t1);
  90      if (mpz_cmp_ui(t2, 0) < 0) {
  91         mpz_add(t2, t2, modulus);
  92      }
  93      /* T1 = X + T1 */
  94      mpz_add(t1, t1, R->x);
  95      if (mpz_cmp(t1, modulus) >= 0) {
  96         mpz_sub(t1, t1, modulus);
  97      }
  98      /* T2 = T1 * T2 */
  99      mpz_mul(t2, t1, t2);
 100      mpz_mod(t2, t2, modulus);
 101      /* T1 = 2T2 */
 102      mpz_add(t1, t2, t2);
 103      if (mpz_cmp(t1, modulus) >= 0) {
 104         mpz_sub(t1, t1, modulus);
 105      }
 106      /* T1 = T1 + T2 */
 107      mpz_add(t1, t1, t2);
 108      if (mpz_cmp(t1, modulus) >= 0) {
 109         mpz_sub(t1, t1, modulus);
 110      }
 111
 112      /* Y = 2Y */
 113      mpz_add(R->y, R->y, R->y);
 114      if (mpz_cmp(R->y, modulus) >= 0) {
 115         mpz_sub(R->y, R->y, modulus);
 116      }
 117      /* Y = Y * Y */
 118      mpz_mul(R->y, R->y, R->y);
 119      mpz_mod(R->y, R->y, modulus);
 120      /* T2 = Y * Y */
 121      mpz_mul(t2, R->y, R->y);
 122      mpz_mod(t2, t2, modulus);
 123      /* T2 = T2/2 */
 124      if (mpz_odd_p(t2)) {
 125         mpz_add(t2, t2, modulus);
 126      }
 127      mpz_divexact_ui(t2, t2, 2);
 128      /* Y = Y * X */
 129      mpz_mul(R->y, R->y, R->x);
 130      mpz_mod(R->y, R->y, modulus);
 131
 132      /* X  = T1 * T1 */
 133      mpz_mul(R->x, t1, t1);
 134      mpz_mod(R->x, R->x, modulus);
 135      /* X = X - Y */
 136      mpz_sub(R->x, R->x, R->y);
 137      if (mpz_cmp_ui(R->x, 0) < 0) {
 138         mpz_add(R->x, R->x, modulus);
 139      }
 140      /* X = X - Y */
 141      mpz_sub(R->x, R->x, R->y);
 142      if (mpz_cmp_ui(R->x, 0) < 0) {
 143         mpz_add(R->x, R->x, modulus);
 144      }
 145
 146      /* Y = Y - X */
 147      mpz_sub(R->y, R->y, R->x);
 148      if (mpz_cmp_ui(R->y, 0) < 0) {
 149         mpz_add(R->y, R->y, modulus);
 150      }
 151      /* Y = Y * T1 */
 152      mpz_mul(R->y, R->y, t1);
 153      mpz_mod(R->y, R->y, modulus);
 154      /* Y = Y - T2 */
 155      mpz_sub(R->y, R->y, t2);
 156      if (mpz_cmp_ui(R->y, 0) < 0) {
 157         mpz_add( R->y, R->y, modulus);
 158      }
 159
 160      err = GNUTLS_E_SUCCESS;
 161
 162      mp_clear_multi(&t1, &t2, NULL);
 163      return err;
 164    } else if (err == 0) {
 165      /* 2*neutral = neutral */
 166      mpz_set_ui(R->x, 1);
 167      mpz_set_ui(R->y, 1);
 168      mpz_set_ui(R->z, 0);
 169
 170      return GNUTLS_E_SUCCESS;
 171    } else {
 172      return err;
 173    }
 174 }
 175 #endif
 176 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_projective_dbl_point.c,v $ */
 177 /* $Revision: 1.11 $ */
 178 /* $Date: 2007/05/12 14:32:35 $ */
 179