ecc-dup-eh.c 4.23 KB
Newer Older
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
/* ecc-dup-eh.c

   Copyright (C) 2014 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle 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
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/

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

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

Daiki Ueno's avatar
Daiki Ueno committed
39
/* Double a point on a twisted Edwards curve, in homogeneous coordinates */
40 41 42 43 44 45
void
ecc_dup_eh (const struct ecc_curve *ecc,
	    mp_limb_t *r, const mp_limb_t *p,
	    mp_limb_t *scratch)
{
  /* Formulas (from djb,
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp):

     B = (X1+Y1)^2
     C = X1^2
     D = Y1^2
     (E = a*C = -C)
     F = E+D
     H = Z1^2
     J = F-2*H
     X3 = (B-C-D)*J
     Y3 = F*(E-D)
     Z3 = F*J         (-C+D)*(-C+D - 2Z1^2)

     In the formula for Y3, we have E - D = -(C+D). To avoid explicit
     negation, negate all of X3, Y3, Z3, and use
61 62

     Computation	Operation	Live variables
63

64 65 66 67 68 69
     B = (X1+Y1)^2	sqr		B
     C = X1^2		sqr		B, C
     D = Y1^2		sqr		B, C, D
     F = -C+D				B, C, D, F
     H = Z1^2		sqr		B, C, D, F, H
     J = 2*H - F			B, C, D, F, J
70
     X3 = (B-C-D)*J	mul		C, F, J  (Replace C <-- C+D)
71 72 73 74
     Y3 = F*(C+D)	mul		F, J
     Z3 = F*J		mul

     3M+4S
75
  */
76
  /* FIXME: Could reduce scratch need by reusing D storage. */
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
#define B scratch
#define C (scratch  + ecc->p.size)
#define D (scratch  + 2*ecc->p.size)
#define F (scratch  + 3*ecc->p.size)
#define J (scratch  + 4*ecc->p.size)

  /* B */
  ecc_modp_add (ecc, F, p, p + ecc->p.size);
  ecc_modp_sqr (ecc, B, F);

  /* C */
  ecc_modp_sqr (ecc, C, p);
  /* D */
  ecc_modp_sqr (ecc, D, p + ecc->p.size);
  /* Can use r as scratch, even for in-place operation. */
92
  ecc_modp_sqr (ecc, r, p + 2*ecc->p.size);
93 94 95
  /* F, */
  ecc_modp_sub (ecc, F, D, C);
  /* B - C - D */
96
  ecc_modp_add (ecc, C, C, D);
97 98
  ecc_modp_sub (ecc, B, B, C);
  /* J */
99
  ecc_modp_add (ecc, r, r, r);
100
  ecc_modp_sub (ecc, J, r, F);
101 102

  /* x' */
103
  ecc_modp_mul (ecc, r, B, J);
104
  /* y' */
105
  ecc_modp_mul (ecc, r + ecc->p.size, F, C);
106
  /* z' */
107 108
  ecc_modp_mul (ecc, B, F, J);
  mpn_copyi (r + 2*ecc->p.size, B, ecc->p.size);
109
}
Daiki Ueno's avatar
Daiki Ueno committed
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162

void
ecc_dup_eh_untwisted (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-edwards-projective.html#doubling-dbl-2007-bl):

     Computation	Operation	Live variables

     b = (x+y)^2	sqr		b
     c = x^2		sqr		b, c
     d = y^2		sqr		b, c, d
     e = c+d				b, c, d, e
     h = z^2		sqr		b, c, d, e, h
     j = e-2*h				b, c, d, e, j
     x' = (b-e)*j	mul		c, d, e, j
     y' = e*(c-d)	mul		e, j
     z' = e*j		mul
  */
#define b scratch
#define c (scratch  + ecc->p.size)
#define d (scratch  + 2*ecc->p.size)
#define e (scratch  + 3*ecc->p.size)
#define j (scratch  + 4*ecc->p.size)

  /* b */
  ecc_modp_add (ecc, e, p, p + ecc->p.size);
  ecc_modp_sqr (ecc, b, e);

  /* c */
  ecc_modp_sqr (ecc, c, p);
  /* d */
  ecc_modp_sqr (ecc, d, p + ecc->p.size);
  /* h, can use r as scratch, even for in-place operation. */
  ecc_modp_sqr (ecc, r, p + 2*ecc->p.size);
  /* e, */
  ecc_modp_add (ecc, e, c, d);
  /* j */
  ecc_modp_add (ecc, r, r, r);
  ecc_modp_sub (ecc, j, e, r);

  /* x' */
  ecc_modp_sub (ecc, b, b, e);
  ecc_modp_mul (ecc, r, b, j);
  /* y' */
  ecc_modp_sub (ecc, c, c, d); /* Redundant */
  ecc_modp_mul (ecc, r + ecc->p.size, e, c);
  /* z' */
  ecc_modp_mul (ecc, b, e, j);
  mpn_copyi (r + 2*ecc->p.size, b, ecc->p.size);
}