ecc-add-jja.c

   1 /* ecc-dup-jj.c */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #if HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include "ecc.h"
  30 #include "ecc-internal.h"
  31
  32 /* NOTE: Behaviour for corner cases:
  33
  34    + p = 0   ==>  r = 0 (invalid except if also q = 0)
  35
  36    + q = 0   ==>  r = invalid
  37
  38    + p = -q  ==>  r = 0, correct!
  39
  40    + p = q   ==>  r = 0, invalid
  41 */
  42
  43 mp_size_t
  44 ecc_add_jja_itch (const struct ecc_curve *ecc)
  45 {
  46   return ECC_ADD_JJA_ITCH (ecc->size);
  47 }
  48
  49 void
  50 ecc_add_jja (const struct ecc_curve *ecc,
  51              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
  52              mp_limb_t *scratch)
  53 {
  54   /* Formulas, from djb,
  55      http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
  56
  57      Computation                Operation       Live variables
  58
  59       ZZ = Z_1^2                sqr             ZZ
  60       H = X_2*ZZ - X_1          mul (djb: U_2)  ZZ, H
  61       HH = H^2                  sqr             ZZ, H, HH
  62       ZZZ = ZZ*Z_1              mul             ZZ, H, HH, ZZZ
  63       Z_3 = (Z_1+H)^2-ZZ-HH     sqr             H, HH, ZZZ
  64       W = 2 (Y_2*ZZZ - Y_1)     mul (djb: S_2)  H, HH, W
  65       I = 4*HH                                  H, W, I
  66       J = H*I                   mul             W, I, J
  67       V = X_1*I                 mul             W, J, V
  68       X_3 = W^2-J-2*V           sqr             W, J, V
  69       Y_3 = W*(V-X_3)-2*Y_1*J   mul, mul
  70   */
  71 #define zz  scratch
  72 #define h  (scratch + ecc->size)
  73 #define hh (scratch + 2*ecc->size)
  74 #define w  (scratch + 3*ecc->size)
  75 #define j  (scratch + 4*ecc->size)
  76 #define v   scratch
  77
  78 #define x1  p
  79 #define y1 (p + ecc->size)
  80 #define z1 (p + 2*ecc->size)
  81 #define x2  q
  82 #define y2 (q + ecc->size)
  83
  84   /* zz */
  85   ecc_modp_sqr (ecc, zz, z1);
  86   /* h*/
  87   ecc_modp_mul (ecc, h, x2, zz);
  88   ecc_modp_sub (ecc, h, h, x1);
  89   /* hh */
  90   ecc_modp_sqr (ecc, hh, h);
  91   /* Do z^3 early, store at w. */
  92   ecc_modp_mul (ecc, w, zz, z1);
  93   /* z_3, use j area for scratch */
  94   ecc_modp_add (ecc, r + 2*ecc->size, p + 2*ecc->size, h);
  95   ecc_modp_sqr (ecc, j, r + 2*ecc->size);
  96   ecc_modp_sub (ecc, j, j, zz);
  97   ecc_modp_sub (ecc, r + 2*ecc->size, j, hh);
  98
  99   /* w */
 100   ecc_modp_mul (ecc, j, y2, w);
 101   ecc_modp_sub (ecc, w, j, y1);
 102   ecc_modp_mul_1 (ecc, w, w, 2);
 103
 104   /* i replaces hh, j */
 105   ecc_modp_mul_1 (ecc, hh, hh, 4);
 106   ecc_modp_mul (ecc, j, hh, h);
 107
 108   /* v */
 109   ecc_modp_mul (ecc, v, x1, hh);
 110
 111   /* x_3, use (h, hh) as sqratch */
 112   ecc_modp_sqr (ecc, h, w);
 113   ecc_modp_sub (ecc, r, h, j);
 114   ecc_modp_submul_1 (ecc, r, v, 2);
 115
 116   /* y_3, use (h, hh) as sqratch */
 117   ecc_modp_mul (ecc, h, y1, j); /* frees j */
 118   ecc_modp_sub (ecc, r + ecc->size, v, r);
 119   ecc_modp_mul (ecc, j, r + ecc->size, w);
 120   ecc_modp_submul_1 (ecc, j, h, 2);
 121   mpn_copyi (r + ecc->size, j, ecc->size);
 122 }