lib/nettle/ecc_projective_add_point.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_add_point.c
  29   ECC Crypto, Tom St Denis
  30 */
  31
  32 /*
  33    Add two ECC points
  34    @param P        The point to add
  35    @param Q        The point to add
  36    @param R        [out] The destination of the double
  37    @param a        Curve's a value
  38    @param modulus  The modulus of the field the ECC curve is in
  39    @return 0 on success
  40 */
  41 int
  42 ecc_projective_add_point (ecc_point * P, ecc_point * Q, ecc_point * R,
  43                               mpz_t a, mpz_t modulus)
  44 {
  45   mpz_t t1, t2, x, y, z;
  46   int err;
  47
  48   if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
  49     return -1;
  50
  51   if ((err = mp_init_multi (&t1, &t2, &x, &y, &z, NULL)) != 0)
  52     {
  53       return err;
  54     }
  55
  56   /* Check if P == Q and do doubling in that case
  57    * If Q == -P then P+Q=point at infinity
  58    */
  59   if ((mpz_cmp (P->x, Q->x) == 0) &&
  60       (mpz_cmp (P->z, Q->z) == 0))
  61     {
  62       /* x and z coordinates match. Check if P->y = Q->y, or P->y = -Q->y
  63        */
  64       if (mpz_cmp (P->y, Q->y) == 0)
  65         {
  66           mp_clear_multi (&t1, &t2, &x, &y, &z, NULL);
  67           return ecc_projective_dbl_point (P, R, a, modulus);
  68         }
  69
  70       mpz_sub (t1, modulus, Q->y);
  71       if (mpz_cmp (P->y, t1) == 0)
  72         {
  73           mp_clear_multi (&t1, &t2, &x, &y, &z, NULL);
  74           mpz_set_ui(R->x, 1);
  75           mpz_set_ui(R->y, 1);
  76           mpz_set_ui(R->z, 0);
  77           return 0;
  78         }
  79     }
  80
  81
  82   mpz_set (x, P->x);
  83   mpz_set (y, P->y);
  84   mpz_set (z, P->z);
  85
  86   /* if Z is one then these are no-operations */
  87   if (mpz_cmp_ui (Q->z, 1) != 0)
  88     {
  89       /* T1 = Z' * Z' */
  90       mpz_mul (t1, Q->z, Q->z);
  91       mpz_mod (t1, t1, modulus);
  92       /* X = X * T1 */
  93       mpz_mul (x, x, t1);
  94       mpz_mod (x, x, modulus);
  95       /* T1 = Z' * T1 */
  96       mpz_mul (t1, t1, Q->z);
  97       mpz_mod (t1, t1, modulus);
  98       /* Y = Y * T1 */
  99       mpz_mul (y, y, t1);
 100       mpz_mod (y, y, modulus);
 101     }
 102
 103   /* T1 = Z*Z */
 104   mpz_mul (t1, z, z);
 105   mpz_mod (t1, t1, modulus);
 106   /* T2 = X' * T1 */
 107   mpz_mul (t2, t1, Q->x);
 108   mpz_mod (t2, t2, modulus);
 109   /* T1 = Z * T1 */
 110   mpz_mul (t1, t1, z);
 111   mpz_mod (t1, t1, modulus);
 112   /* T1 = Y' * T1 */
 113   mpz_mul (t1, t1, Q->y);
 114   mpz_mod (t1, t1, modulus);
 115
 116   /* Y = Y - T1 */
 117   mpz_sub (y, y, t1);
 118   if (mpz_cmp_ui (y, 0) < 0)
 119     {
 120       mpz_add (y, y, modulus);
 121     }
 122   /* T1 = 2T1 */
 123   mpz_add (t1, t1, t1);
 124   if (mpz_cmp (t1, modulus) >= 0)
 125     {
 126       mpz_sub (t1, t1, modulus);
 127     }
 128   /* T1 = Y + T1 */
 129   mpz_add (t1, t1, y);
 130   if (mpz_cmp (t1, modulus) >= 0)
 131     {
 132       mpz_sub (t1, t1, modulus);
 133     }
 134   /* X = X - T2 */
 135   mpz_sub (x, x, t2);
 136   if (mpz_cmp_ui (x, 0) < 0)
 137     {
 138       mpz_add (x, x, modulus);
 139     }
 140   /* T2 = 2T2 */
 141   mpz_add (t2, t2, t2);
 142   if (mpz_cmp (t2, modulus) >= 0)
 143     {
 144       mpz_sub (t2, t2, modulus);
 145     }
 146   /* T2 = X + T2 */
 147   mpz_add (t2, t2, x);
 148   if (mpz_cmp (t2, modulus) >= 0)
 149     {
 150       mpz_sub (t2, t2, modulus);
 151     }
 152
 153   /* if Z' != 1 */
 154   if (mpz_cmp_ui (Q->z, 1) != 0)
 155     {
 156       /* Z = Z * Z' */
 157       mpz_mul (z, z, Q->z);
 158       mpz_mod (z, z, modulus);
 159     }
 160
 161   /* Z = Z * X */
 162   mpz_mul (z, z, x);
 163   mpz_mod (z, z, modulus);
 164
 165   /* T1 = T1 * X  */
 166   mpz_mul (t1, t1, x);
 167   mpz_mod (t1, t1, modulus);
 168   /* X = X * X */
 169   mpz_mul (x, x, x);
 170   mpz_mod (x, x, modulus);
 171   /* T2 = T2 * x */
 172   mpz_mul (t2, t2, x);
 173   mpz_mod (t2, t2, modulus);
 174   /* T1 = T1 * X  */
 175   mpz_mul (t1, t1, x);
 176   mpz_mod (t1, t1, modulus);
 177
 178   /* X = Y*Y */
 179   mpz_mul (x, y, y);
 180   mpz_mod (x, x, modulus);
 181   /* X = X - T2 */
 182   mpz_sub (x, x, t2);
 183   if (mpz_cmp_ui (x, 0) < 0)
 184     {
 185       mpz_add (x, x, modulus);
 186     }
 187
 188   /* T2 = T2 - X */
 189   mpz_sub (t2, t2, x);
 190   if (mpz_cmp_ui (t2, 0) < 0)
 191     {
 192       mpz_add (t2, t2, modulus);
 193     }
 194   /* T2 = T2 - X */
 195   mpz_sub (t2, t2, x);
 196   if (mpz_cmp_ui (t2, 0) < 0)
 197     {
 198       mpz_add (t2, t2, modulus);
 199     }
 200   /* T2 = T2 * Y */
 201   mpz_mul (t2, t2, y);
 202   mpz_mod (t2, t2, modulus);
 203   /* Y = T2 - T1 */
 204   mpz_sub (y, t2, t1);
 205   if (mpz_cmp_ui (y, 0) < 0)
 206     {
 207       mpz_add (y, y, modulus);
 208     }
 209   /* Y = Y/2 */
 210   if (mpz_odd_p (y))
 211     {
 212       mpz_add (y, y, modulus);
 213     }
 214   mpz_divexact_ui (y, y, 2);
 215
 216   mpz_set (R->x, x);
 217   mpz_set (R->y, y);
 218   mpz_set (R->z, z);
 219
 220   err = 0;
 221
 222   mp_clear_multi (&t1, &t2, &x, &y, &z, NULL);
 223   return err;
 224 }
 225
 226 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_projective_add_point.c,v $ */
 227 /* $Revision: 1.16 $ */
 228 /* $Date: 2007/05/12 14:32:35 $ */