ecc-add-eh.c 4.66 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
/* ecc-add-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"

/* Add two points on an Edwards curve, with result and first point in
   homogeneous coordinates. */
void
ecc_add_eh (const struct ecc_curve *ecc,
	    mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
	    mp_limb_t *scratch)
{
#define x1 p
47 48
#define y1 (p + ecc->p.size)
#define z1 (p + 2*ecc->p.size)
Niels Möller's avatar
Niels Möller committed
49 50

#define x2 q
51
#define y2 (q + ecc->p.size)
Niels Möller's avatar
Niels Möller committed
52 53

#define x3 r
54 55
#define y3 (r + ecc->p.size)
#define z3 (r + 2*ecc->p.size)
Niels Möller's avatar
Niels Möller committed
56 57

  /* Formulas (from djb,
Niels Möller's avatar
Niels Möller committed
58
     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#addition-madd-2008-bbjlp
Niels Möller's avatar
Niels Möller committed
59 60 61

     Computation	Operation	Live variables

62 63
     C = x1*x2		mul		C
     D = y1*y2		mul		C, D
Niels Möller's avatar
Niels Möller committed
64 65 66
     T = (x1+y1)*(x2+y2) mul		C, D, T
         - C - D
     E = b*C*D          2 mul		C, E, T  (Replace C <-- D+C)
67 68 69
     B = z1^2		sqr		B, C, E, T
     F = B - E				B, C, E, F, T
     G = B + E     			C, F, G, T
Niels Möller's avatar
Niels Möller committed
70 71
     x3 = z1 * F * T    2 mul		C, F, G, T
     y3 = z1*G*(D+C)	2 mul		F, G
Niels Möller's avatar
Niels Möller committed
72
     z3 = F*G		mul
Niels Möller's avatar
Niels Möller committed
73 74 75 76 77

     10M + 1S

     We have different sign for E, hence swapping F and G, because our
     ecc->b corresponds to -b above.
Niels Möller's avatar
Niels Möller committed
78
  */
79
#define C (scratch)
80 81
#define D (scratch + 1*ecc->p.size)
#define T (scratch + 2*ecc->p.size)
Daiki Ueno's avatar
Daiki Ueno committed
82
#define E (scratch + 3*ecc->p.size)
83
#define B (scratch + 4*ecc->p.size)
84 85
#define F D
#define G E
Daiki Ueno's avatar
Daiki Ueno committed
86

Niels Möller's avatar
Niels Möller committed
87 88
  ecc_modp_mul (ecc, C, x1, x2);
  ecc_modp_mul (ecc, D, y1, y2);
89 90 91 92 93 94 95 96
  ecc_modp_add (ecc, x3, x1, y1);
  ecc_modp_add (ecc, y3, x2, y2);
  ecc_modp_mul (ecc, T, x3, y3);
  ecc_modp_sub (ecc, T, T, C);
  ecc_modp_sub (ecc, T, T, D);
  ecc_modp_mul (ecc, x3, C, D);
  ecc_modp_mul (ecc, E, x3, ecc->b);

Niels Möller's avatar
Niels Möller committed
97
  ecc_modp_add (ecc, C, D, C);
98
  ecc_modp_sqr (ecc, B, z1);
Niels Möller's avatar
Niels Möller committed
99
  ecc_modp_sub (ecc, F, B, E);
Daiki Ueno's avatar
Daiki Ueno committed
100
  ecc_modp_add (ecc, G, B, E);
Niels Möller's avatar
Niels Möller committed
101 102

  /* x3 */
Niels Möller's avatar
Niels Möller committed
103
  ecc_modp_mul (ecc, B, G, T);
104
  ecc_modp_mul (ecc, x3, B, z1);
Niels Möller's avatar
Niels Möller committed
105 106

  /* y3 */
Niels Möller's avatar
Niels Möller committed
107
  ecc_modp_mul (ecc, B, F, z1);
Niels Möller's avatar
Niels Möller committed
108
  ecc_modp_mul (ecc, y3, B, C); /* Clobbers z1 in case r == p. */
Niels Möller's avatar
Niels Möller committed
109 110

  /* z3 */
111
  ecc_modp_mul (ecc, B, F, G);
112
  mpn_copyi (z3, B, ecc->p.size);
Niels Möller's avatar
Niels Möller committed
113
}
Daiki Ueno's avatar
Daiki Ueno committed
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 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181

void
ecc_add_eh_untwisted (const struct ecc_curve *ecc,
		      mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
		      mp_limb_t *scratch)
{
#define x1 p
#define y1 (p + ecc->p.size)
#define z1 (p + 2*ecc->p.size)

#define x2 q
#define y2 (q + ecc->p.size)

#define x3 r
#define y3 (r + ecc->p.size)
#define z3 (r + 2*ecc->p.size)

  /* Formulas (from djb,
     http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):

     Computation	Operation	Live variables

     C = x1*x2		mul		C
     D = y1*y2		mul		C, D
     T = (x1+y1)(x2+y2) - C - D		C, D, T
     E = b*C*D		2 mul		C, E, T  (Replace C <-- D - C)
     B = z1^2		sqr		B, C, E, T
     F = B - E				B, C, E, F, T
     G = B + E     			C, F, G, T
     x3 = z1*F*T	3 mul		C, F, G, T
     y3 = z1*G*(D-C)	2 mul		F, G
     z3 = F*G		mul
  */
#define C (scratch)
#define D (scratch + 1*ecc->p.size)
#define T (scratch + 2*ecc->p.size)
#define E (scratch + 3*ecc->p.size)
#define B (scratch + 4*ecc->p.size)
#define F D
#define G E

  ecc_modp_mul (ecc, C, x1, x2);
  ecc_modp_mul (ecc, D, y1, y2);
  ecc_modp_add (ecc, x3, x1, y1);
  ecc_modp_add (ecc, y3, x2, y2);
  ecc_modp_mul (ecc, T, x3, y3);
  ecc_modp_sub (ecc, T, T, C);
  ecc_modp_sub (ecc, T, T, D);
  ecc_modp_mul (ecc, x3, C, D);
  ecc_modp_mul (ecc, E, x3, ecc->b);

  ecc_modp_sub (ecc, C, D, C);
  ecc_modp_sqr (ecc, B, z1);
  ecc_modp_sub (ecc, F, B, E);
  ecc_modp_add (ecc, G, B, E);

  /* x3 */
  ecc_modp_mul (ecc, B, F, T);
  ecc_modp_mul (ecc, x3, B, z1);

  /* y3 */
  ecc_modp_mul (ecc, B, G, z1);
  ecc_modp_mul (ecc, y3, B, C); /* Clobbers z1 in case r == p. */

  /* z3 */
  ecc_modp_mul (ecc, B, F, G);
  mpn_copyi (z3, B, ecc->p.size);
}