ecc-dup-jj.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, correct!
  35 */
  36 mp_size_t
  37 ecc_dup_jj_itch (const struct ecc_curve *ecc)
  38 {
  39   return ECC_DUP_JJ_ITCH (ecc->size);
  40 }
  41
  42 void
  43 ecc_dup_jj (const struct ecc_curve *ecc,
  44             mp_limb_t *r, const mp_limb_t *p,
  45             mp_limb_t *scratch)
  46 {
  47   /* Formulas (from djb,
  48      http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
  49
  50      Computation                        Operation       Live variables
  51      delta = z^2                        sqr             delta
  52      gamma = y^2                        sqr             delta, gamma
  53      z' = (y+z)^2-gamma-delta           sqr             delta, gamma
  54      alpha = 3*(x-delta)*(x+delta)      mul             gamma, beta, alpha
  55      beta = x*gamma                     mul             gamma, beta, alpha
  56      x' = alpha^2-8*beta                sqr             gamma, beta, alpha
  57      y' = alpha*(4*beta-x')-8*gamma^2   mul, sqr
  58   */
  59
  60 #define delta  scratch
  61 #define gamma (scratch + ecc->size)
  62 #define beta  (scratch + 2*ecc->size)
  63 #define g2    (scratch + 3*ecc->size)
  64 #define sum   (scratch + 4*ecc->size)
  65 #define alpha  scratch /* Overlap delta */
  66
  67 #define xp p
  68 #define yp (p + ecc->size)
  69 #define zp (p + 2*ecc->size)
  70
  71   /* delta */
  72   ecc_modp_sqr (ecc, delta, zp);
  73
  74   /* gamma */
  75   ecc_modp_sqr (ecc, gamma, yp);
  76
  77   /* z'. Can use beta area as scratch. */
  78   ecc_modp_add (ecc, r + 2*ecc->size, yp, zp);
  79   ecc_modp_sqr (ecc, beta, r + 2*ecc->size);
  80   ecc_modp_sub (ecc, beta, beta, gamma);
  81   ecc_modp_sub (ecc, r + 2*ecc->size, beta, delta);
  82
  83   /* alpha. Can use beta area as scratch, and overwrite delta. */
  84   ecc_modp_add (ecc, sum, xp, delta);
  85   ecc_modp_sub (ecc, delta, xp, delta);
  86   ecc_modp_mul (ecc, beta, sum, delta);
  87   ecc_modp_mul_1 (ecc, alpha, beta, 3);
  88
  89   /* beta */
  90   ecc_modp_mul (ecc, beta, xp, gamma);
  91
  92   /* Do gamma^2 and 4*beta early, to get them out of the way. We can
  93      then use the old area at gamma as scratch. */
  94   ecc_modp_sqr (ecc, g2, gamma);
  95   ecc_modp_mul_1 (ecc, sum, beta, 4);
  96
  97   /* x' */
  98   ecc_modp_sqr (ecc, gamma, alpha);   /* Overwrites gamma and beta */
  99   ecc_modp_submul_1 (ecc, gamma, sum, 2);
 100   mpn_copyi (r, gamma, ecc->size);
 101
 102   /* y' */
 103   ecc_modp_sub (ecc, sum, sum, r);
 104   ecc_modp_mul (ecc, gamma, sum, alpha);
 105   ecc_modp_submul_1 (ecc, gamma, g2, 8);
 106   mpn_copyi (r + ecc->size, gamma, ecc->size);
 107 }