ecc-add-ehh.c 3.08 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 39 40 41 42 43 44 45
/* ecc-add-ehh.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, in homogeneous coordinates */
void
ecc_add_ehh (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
Niels Möller's avatar
Niels Möller committed
46 47
#define y1 (p + ecc->p.size)
#define z1 (p + 2*ecc->p.size)
48 49

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

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

  /* Formulas (from djb,
58
     http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#addition-add-2007-bl):
59 60 61

     Computation	Operation	Live variables

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

74 75 76
     But when working with the twist curve, we have to negate the
     factor C = x1*x2. We change subtract to add in the y3
     expression, and swap F and G.
77
  */
78
#define C scratch
Niels Möller's avatar
Niels Möller committed
79 80 81 82 83
#define D (scratch + ecc->p.size)
#define T (scratch + 2*ecc->p.size)
#define E (scratch + 3*ecc->p.size) 
#define A (scratch + 4*ecc->p.size)
#define B (scratch + 5*ecc->p.size)
84 85 86
#define F D
#define G E

87 88
  ecc_modp_mul (ecc, C, x1, x2);
  ecc_modp_mul (ecc, D, y1, y2);
89 90 91 92 93 94 95
  ecc_modp_add (ecc, A, x1, y1);
  ecc_modp_add (ecc, B, x2, y2);
  ecc_modp_mul (ecc, T, A, B);
  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);
96
  ecc_modp_add (ecc, C, D, C);	/* ! */
97 98 99 100
  
  ecc_modp_mul (ecc, A, z1, z2);
  ecc_modp_sqr (ecc, B, A);

101 102 103 104
  ecc_modp_sub (ecc, F, B, E);
  ecc_modp_add (ecc, G, B, E);

  /* x3 */
105
  ecc_modp_mul (ecc, B, G, T); /* ! */
106
  ecc_modp_mul (ecc, x3, B, A);
107 108

  /* y3 */
109
  ecc_modp_mul (ecc, B, F, C); /* ! */
110
  ecc_modp_mul (ecc, y3, B, A);
111 112

  /* z3 */
113
  ecc_modp_mul (ecc, B, F, G);
Niels Möller's avatar
Niels Möller committed
114
  mpn_copyi (z3, B, ecc->p.size);
115
}