ecc-dup-jj.c 3.19 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
/* ecc-dup-jj.c */

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2013 Niels Möller
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02111-1301, USA.
 */

/* Development of Nettle's ECC support was funded by Internetfonden. */

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include "ecc.h"
#include "ecc-internal.h"

/* NOTE: Behaviour for corner cases:

   + p = 0  ==>  r = 0, correct!
*/
mp_size_t
ecc_dup_jj_itch (const struct ecc_curve *ecc)
{
  return ECC_DUP_JJ_ITCH (ecc->size);
}

void
ecc_dup_jj (const struct ecc_curve *ecc,
	    mp_limb_t *r, const mp_limb_t *p,
	    mp_limb_t *scratch)
{
  /* Formulas (from djb,
     http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):

     Computation			Operation	Live variables
     delta = z^2			sqr		delta
     gamma = y^2			sqr		delta, gamma
     z' = (y+z)^2-gamma-delta		sqr		delta, gamma
     alpha = 3*(x-delta)*(x+delta)	mul		gamma, beta, alpha
     beta = x*gamma			mul		gamma, beta, alpha
     x' = alpha^2-8*beta		sqr		gamma, beta, alpha
     y' = alpha*(4*beta-x')-8*gamma^2	mul, sqr
  */

#define delta  scratch
#define gamma (scratch + ecc->size)
#define beta  (scratch + 2*ecc->size)
#define g2    (scratch + 3*ecc->size)
#define sum   (scratch + 4*ecc->size)
#define alpha  scratch /* Overlap delta */
  
#define xp p
#define yp (p + ecc->size)
#define zp (p + 2*ecc->size)
  
  /* delta */
  ecc_modp_sqr (ecc, delta, zp);

  /* gamma */
  ecc_modp_sqr (ecc, gamma, yp);

  /* z'. Can use beta area as scratch. */
  ecc_modp_add (ecc, r + 2*ecc->size, yp, zp);
  ecc_modp_sqr (ecc, beta, r + 2*ecc->size);
  ecc_modp_sub (ecc, beta, beta, gamma);
  ecc_modp_sub (ecc, r + 2*ecc->size, beta, delta);
  
  /* alpha. Can use beta area as scratch, and overwrite delta. */
  ecc_modp_add (ecc, sum, xp, delta);
  ecc_modp_sub (ecc, delta, xp, delta);
  ecc_modp_mul (ecc, beta, sum, delta);
  ecc_modp_mul_1 (ecc, alpha, beta, 3);

  /* beta */
  ecc_modp_mul (ecc, beta, xp, gamma);

  /* Do gamma^2 and 4*beta early, to get them out of the way. We can
     then use the old area at gamma as scratch. */
  ecc_modp_sqr (ecc, g2, gamma);
  ecc_modp_mul_1 (ecc, sum, beta, 4);
  
  /* x' */
  ecc_modp_sqr (ecc, gamma, alpha);   /* Overwrites gamma and beta */
  ecc_modp_submul_1 (ecc, gamma, sum, 2);
  mpn_copyi (r, gamma, ecc->size);

  /* y' */
  ecc_modp_sub (ecc, sum, sum, r);
  ecc_modp_mul (ecc, gamma, sum, alpha);
  ecc_modp_submul_1 (ecc, gamma, g2, 8);
  mpn_copyi (r + ecc->size, gamma, ecc->size);
}