lib/nettle/ecc_projective_add_point_ng.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * Author: Ilya Tumaykin
   5  *
   6  * This file is part of GNUTLS.
   7  *
   8  * The GNUTLS library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation; either version 3 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  20  *
  21  */
  22
  23 #include "ecc.h"
  24
  25 /* We use two algorithms for different cases.
  26  * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html
  27  *
  28  * The algorithm used for general case is "add-1998-cmo-2"
  29  * It costs 12M + 4S.
  30  *
  31  * If Z2 = 1 we use "madd". It costs 8M + 3S.
  32  *
  33  * The original versions use a lot of vars:
  34  * Z1Z1, Z2Z2, U1, U2, S1, S2, H, I, HHH, r, V, etc.
  35  * We use only the needed minimum:
  36  * S1, H, HHH(J), r, V.
  37  * The rest of the vars are not needed for final
  38  * computation, so we calculate them, but don't store.
  39  * Follow the comments.
  40  */
  41
  42
  43 #define __WITH_EXTENDED_CHECKS
  44 /* Check if H == 0
  45  * In this case P + Q = neutral element.
  46  *
  47  * In all of the cases below when H == 0 then Z == 0
  48  * and the resulting point lies at infinity.
  49  *
  50  * And the only point on the curve with Z == 0 MUST be
  51  * the neutral point.
  52  *
  53  * Of course, if there wasn't a mistake somewhere before.
  54  * We will be gullible and won't do any checks and simply
  55  * return neutral point in that case.
  56  */
  57
  58
  59 /*
  60    Add two ECC points
  61    @param P        The point to add
  62    @param Q        The point to add
  63    @param R        [out] The destination of the double
  64    @param a        Curve's a value
  65    @param modulus  The modulus of the field the ECC curve is in
  66    @return         GNUTLS_E_SUCCESS on success
  67
  68    Note: this function WILL work when a != -3.
  69    It will work in general case without a change.
  70 */
  71 int
  72 ecc_projective_add_point (ecc_point * P, ecc_point * Q, ecc_point * R,
  73                              mpz_t a, mpz_t modulus)
  74 {
  75   mpz_t t0, t1, S1, H, HHH, r, V;
  76   int err;
  77
  78   if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
  79     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
  80
  81   /* check all special cases first */
  82
  83   /* check for neutral points */
  84   if ((err = ecc_projective_isneutral (Q, modulus)) == 0)
  85     {
  86       /* P + Q = P + neutral = P */
  87
  88       mpz_set (R->x, P->x);
  89       mpz_set (R->y, P->y);
  90       mpz_set (R->z, P->z);
  91
  92       return GNUTLS_E_SUCCESS;
  93     }
  94   else if (err < 0)
  95     {
  96       return err;
  97     }
  98
  99   if ((err = ecc_projective_isneutral (P, modulus)) == 0)
 100     {
 101       /* P + Q = neutral + Q = Q */
 102
 103       mpz_set (R->x, Q->x);
 104       mpz_set (R->y, Q->y);
 105       mpz_set (R->z, Q->z);
 106
 107       return GNUTLS_E_SUCCESS;
 108     }
 109   else if (err < 0)
 110     {
 111       return err;
 112     }
 113
 114   if ((err = mp_init_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL)) != 0)
 115     return err;
 116
 117   /* Check if P == Q and do doubling in that case
 118    * If Q == -P then P + Q = neutral element */
 119   if ((mpz_cmp (P->x, Q->x) == 0) && (mpz_cmp (P->z, Q->z) == 0))
 120     {
 121
 122       /* x and z coordinates match.
 123        * Check if P->y = Q->y, or P->y = -Q->y */
 124
 125       if (mpz_cmp (P->y, Q->y) == 0)
 126         {
 127           mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
 128           return ecc_projective_dbl_point (P, R, a, modulus);
 129         }
 130
 131       mpz_sub (t1, modulus, Q->y);
 132       if (mpz_cmp (P->y, t1) == 0)
 133         {
 134           mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
 135           mpz_set_ui (R->x, 1);
 136           mpz_set_ui (R->y, 1);
 137           mpz_set_ui (R->z, 0);
 138           return GNUTLS_E_SUCCESS;
 139         }
 140     }
 141
 142
 143   /* check if Z2 == 1 and do "madd" in that case */
 144   if ((mpz_cmp_ui (Q->z, 1) == 0))
 145     {
 146       mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
 147       return ecc_projective_madd (P, Q, R, a, modulus);
 148     }
 149
 150   /* no special cases occured
 151    * do general routine */
 152
 153   /* t1 = Z1 * Z1 */
 154   /* it is the original Z1Z1 */
 155   mpz_mul (t1, P->z, P->z);
 156   mpz_mod (t1, t1, modulus);
 157
 158   /* t0 = Z1 * Z1Z1 */
 159   mpz_mul (t0, t1, P->z);
 160   mpz_mod (t0, t0, modulus);
 161
 162   /* H = X2 * Z1Z1 */
 163   /* it is the original U2 */
 164   mpz_mul (H, t1, Q->x);
 165   mpz_mod (H, H, modulus);
 166
 167   /* r = Y2 * Z1 * Z1Z1 */
 168   /* it is the original S2 */
 169   mpz_mul (r, t0, Q->y);
 170   mpz_mod (r, r, modulus);
 171
 172   /* S1 = Z2 * Z2 */
 173   /* it is the original Z2Z2 */
 174   mpz_mul (S1, Q->z, Q->z);
 175   mpz_mod (S1, S1, modulus);
 176
 177   /* t0 = X1 * Z2Z2 */
 178   /* it is the original U1 */
 179   mpz_mul (t0, S1, P->x);
 180   mpz_mod (t0, t0, modulus);
 181
 182   /* H = U2 - U1 = H - t0 */
 183   mpz_sub (H, H, t0);
 184 #ifdef __WITH_EXTENDED_CHECKS
 185   err = mpz_cmp_ui (H, 0);
 186   if (err < 0)
 187     {
 188       mpz_add (H, H, modulus);
 189     }
 190   else if (!err)
 191     {
 192       mpz_set_ui (R->x, 1);
 193       mpz_set_ui (R->y, 1);
 194       mpz_set_ui (R->z, 0);
 195       mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
 196
 197       return GNUTLS_E_SUCCESS;
 198     }
 199 #else
 200   if (mpz_cmp_ui (H, 0) < 0)
 201     mpz_add (H, H, modulus);
 202 #endif
 203   /* t1 = H^2 */
 204   /* it is the original HH */
 205   mpz_mul (t1, H, H);
 206   mpz_mod (t1, t1, modulus);
 207   /* HHH = H * HH */
 208   mpz_mul (HHH, t1, H);
 209   mpz_mod (HHH, HHH, modulus);
 210
 211   /* V = U1 * HH = t0 * t1 */
 212   mpz_mul (V, t1, t0);
 213   mpz_mod (V, V, modulus);
 214
 215   /* t0 = Z2 * Z2Z2 */
 216   mpz_mul (t0, S1, Q->z);
 217   mpz_mod (t0, t0, modulus);
 218   /* S1 = Y1 * Z2 * Z2Z2 */
 219   mpz_mul (S1, t0, P->y);
 220   mpz_mod (S1, S1, modulus);
 221
 222   /* r = S2 - S1 = r - S1 */
 223   mpz_sub (r, r, S1);
 224   if (mpz_cmp_ui (r, 0) < 0)
 225     mpz_add (r, r, modulus);
 226
 227   /* we've calculated all needed vars:
 228    * S1, H, HHH, r, V
 229    * now, we will calculate the coordinates */
 230
 231   /* t0 = (r)^2 */
 232   mpz_mul (t0, r, r);
 233   mpz_mod (t0, t0, modulus);
 234   /* t0 = t0 - HHH */
 235   mpz_sub (t0, t0, HHH);
 236   if (mpz_cmp_ui (t0, 0) < 0)
 237     mpz_add (t0, t0, modulus);
 238   /* t1 = 2V */
 239   mpz_add (t1, V, V);
 240   if (mpz_cmp (t1, modulus) >= 0)
 241     mpz_sub (t1, t1, modulus);
 242   /* X = r^2 - HHH - 2V = t0 - t1 */
 243   mpz_sub (R->x, t0, t1);
 244   if (mpz_cmp_ui (R->x, 0) < 0)
 245     mpz_add (R->x, R->x, modulus);
 246
 247
 248   /* t1 = V - X */
 249   mpz_sub (t1, V, R->x);
 250   if (mpz_cmp_ui (t1, 0) < 0)
 251     mpz_add (t1, t1, modulus);
 252   /* t0 = r * t1 */
 253   mpz_mul (t0, r, t1);
 254   mpz_mod (t0, t0, modulus);
 255   /* t1 = S1 * HHH */
 256   mpz_mul (t1, S1, HHH);
 257   mpz_mod (t1, t1, modulus);
 258   /* Y = r*(V - X) - S1*HHH = t0 - t1 */
 259   mpz_sub (R->y, t0, t1);
 260   if (mpz_cmp_ui (R->y, 0) < 0)
 261     mpz_add (R->y, R->y, modulus);
 262
 263
 264   /* t1 = Z1 * Z2 */
 265   mpz_mul (t1, P->z, Q->z);
 266   mpz_mod (t1, t1, modulus);
 267   /* Z = Z1 * Z2 * H = t1 * H */
 268   mpz_mul (R->z, t1, H);
 269   mpz_mod (R->z, R->z, modulus);
 270
 271   mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
 272
 273   return GNUTLS_E_SUCCESS;
 274 }
 275
 276 /*
 277    Add two ECC points, when it is known that Z2 == 1
 278    @param P        The point to add
 279    @param Q        The point with Z == 1 to add
 280    @param R        [out] The destination of the double
 281    @param a        Curve's a value
 282    @param modulus  The modulus of the field the ECC curve is in
 283    @return         GNUTLS_E_SUCCESS on success
 284
 285    Note: this function will work when a != -3.
 286    It will work in general case without a change.
 287 */
 288 int
 289 ecc_projective_madd (ecc_point * P, ecc_point * Q, ecc_point * R,
 290                      mpz_t a, mpz_t modulus)
 291 {
 292   mpz_t t0, t1, H, J, r, V;
 293   int err;
 294
 295   if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
 296     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 297
 298   /* check all special cases first */
 299
 300   /* check for neutral points */
 301   /* Q is guaranteed not to be neutral since it has Z == 1 */
 302   if ((err = ecc_projective_isneutral (P, modulus)) == 0)
 303     {
 304       /* P + Q = neutral + Q = Q */
 305
 306       mpz_set (R->x, Q->x);
 307       mpz_set (R->y, Q->y);
 308       mpz_set (R->z, Q->z);
 309
 310       return GNUTLS_E_SUCCESS;
 311     }
 312   else if (err < 0)
 313     {
 314       return err;
 315     }
 316
 317   if ((err = mp_init_multi (&H, &J, &r, &V, &t0, &t1, NULL)) != 0)
 318     return err;
 319
 320   /* Check if P == Q and do doubling in that case
 321    * If Q == -P then P + Q = neutral element */
 322   if ((mpz_cmp (P->x, Q->x) == 0) && (mpz_cmp (P->z, Q->z) == 0))
 323     {
 324
 325       /* x and z coordinates match.
 326        * Check if P->y = Q->y, or P->y = -Q->y */
 327
 328       if (mpz_cmp (P->y, Q->y) == 0)
 329         {
 330           mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
 331           return ecc_projective_dbl_point (P, R, a, modulus);
 332         }
 333
 334       mpz_sub (t1, modulus, Q->y);
 335       if (mpz_cmp (P->y, t1) == 0)
 336         {
 337           mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
 338           mpz_set_ui (R->x, 1);
 339           mpz_set_ui (R->y, 1);
 340           mpz_set_ui (R->z, 0);
 341           return GNUTLS_E_SUCCESS;
 342         }
 343     }
 344
 345   /* no special cases occured
 346    * do madd */
 347
 348   /* t1 = Z1 * Z1 */
 349   /* it is the original Z1Z1 */
 350   mpz_mul (t1, P->z, P->z);
 351   mpz_mod (t1, t1, modulus);
 352
 353   /* t0 = Z1 * Z1Z1 */
 354   mpz_mul (t0, t1, P->z);
 355   mpz_mod (t0, t0, modulus);
 356
 357   /* r = Y2 * Z1 * Z1Z1 */
 358   /* it is the original S2 */
 359   mpz_mul (r, t0, Q->y);
 360   mpz_mod (r, r, modulus);
 361   /* r = S2 - Y1 = r - Y1 */
 362   mpz_sub (r, r, P->y);
 363   if (mpz_cmp_ui (r, 0) < 0)
 364     mpz_add (r, r, modulus);
 365   /* r = 2 * (S2 - Y1) */
 366   mpz_add (r, r, r);
 367   if (mpz_cmp (r, modulus) >= 0)
 368     mpz_sub (r, r, modulus);
 369
 370   /* H = X2 * Z1Z1 */
 371   /* it is the original U2 */
 372   mpz_mul (H, t1, Q->x);
 373   mpz_mod (H, H, modulus);
 374   /* H = U2 - X1  = H - X1 */
 375   mpz_sub (H, H, P->x);
 376 #ifdef __WITH_EXTENDED_CHECKS
 377   err = mpz_cmp_ui (H, 0);
 378   if (err < 0)
 379     {
 380       mpz_add (H, H, modulus);
 381     }
 382   else if (!err)
 383     {
 384       mpz_set_ui (R->x, 1);
 385       mpz_set_ui (R->y, 1);
 386       mpz_set_ui (R->z, 0);
 387       mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
 388
 389       return GNUTLS_E_SUCCESS;
 390     }
 391 #else
 392   if (mpz_cmp_ui (H, 0) < 0)
 393     mpz_add (H, H, modulus);
 394 #endif
 395
 396   /* t0 = 2H */
 397   mpz_add (t0, H, H);
 398   if (mpz_cmp (t0, modulus) >= 0)
 399     mpz_sub (t0, t0, modulus);
 400   /* t1 = (2H)^2 */
 401   /* it is the original I */
 402   mpz_mul (t1, t0, t0);
 403   mpz_mod (t1, t1, modulus);
 404
 405   /* J = H * I = H * t1 */
 406   mpz_mul (J, t1, H);
 407   mpz_mod (J, J, modulus);
 408
 409   /* V = X1 * I = X1 * t1 */
 410   mpz_mul (V, t1, P->x);
 411   mpz_mod (V, V, modulus);
 412
 413   /* we've calculated all needed vars:
 414    * H, J, r, V
 415    * now, we will calculate the coordinates */
 416
 417   /* Z = 2 * Z1 * H = Z1 * t0 */
 418   mpz_mul (R->z, P->z, t0);
 419   mpz_mod (R->z, R->z, modulus);
 420
 421
 422   /* t0 = (r)^2 */
 423   mpz_mul (t0, r, r);
 424   mpz_mod (t0, t0, modulus);
 425   /* t0 = t0 - J */
 426   mpz_sub (t0, t0, J);
 427   if (mpz_cmp_ui (t0, 0) < 0)
 428     mpz_add (t0, t0, modulus);
 429   /* t1 = 2V */
 430   mpz_add (t1, V, V);
 431   if (mpz_cmp (t1, modulus) >= 0)
 432     mpz_sub (t1, t1, modulus);
 433   /* X = r^2 - J - 2V = t0 - t1 */
 434   mpz_sub (R->x, t0, t1);
 435   if (mpz_cmp_ui (R->x, 0) < 0)
 436     mpz_add (R->x, R->x, modulus);
 437
 438
 439   /* t1 = V - X */
 440   mpz_sub (t1, V, R->x);
 441   if (mpz_cmp_ui (t1, 0) < 0)
 442     mpz_add (t1, t1, modulus);
 443   /* t0 = r * t1 */
 444   mpz_mul (t0, r, t1);
 445   mpz_mod (t0, t0, modulus);
 446   /* t1 = Y1 * J */
 447   mpz_mul (t1, J, P->y);
 448   mpz_mod (t1, t1, modulus);
 449   /* t1 = 2 * t1 */
 450   mpz_add (t1, t1, t1);
 451   if (mpz_cmp (t1, modulus) >= 0)
 452     mpz_sub (t1, t1, modulus);
 453   /* Y = r * (V - X) - 2 * Y1 * J = t0 - t1 */
 454   mpz_sub (R->y, t0, t1);
 455   if (mpz_cmp_ui (R->y, 0) < 0)
 456     mpz_add (R->y, R->y, modulus);
 457
 458
 459   mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
 460
 461   return GNUTLS_E_SUCCESS;
 462 }