ecc-add-eh.c 2.86 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
Niels Möller's avatar
Niels Möller committed
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
Niels Möller's avatar
Niels Möller committed
51
#define y2 (q + ecc->p.size)
Niels Möller's avatar
Niels Möller committed
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)
Niels Möller's avatar
Niels Möller committed
56
57
58
59
60
61

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

     Computation	Operation	Live variables

62
63
64
65
66
67
68
69
     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
Niels Möller's avatar
Niels Möller committed
70
71
72
     y3 = z1*G*(D-C)	2 mul		F, G
     z3 = F*G		mul
  */
73
#define C (scratch)
Niels Möller's avatar
Niels Möller committed
74
75
76
77
#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)
78
79
80
#define F D
#define G E
  
Niels Möller's avatar
Niels Möller committed
81
82
  ecc_modp_mul (ecc, C, x1, x2);
  ecc_modp_mul (ecc, D, y1, y2);
83
84
85
86
87
88
89
90
  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);

91
  ecc_modp_add (ecc, C, D, C); /* ! */
92
  ecc_modp_sqr (ecc, B, z1);
Niels Möller's avatar
Niels Möller committed
93
  ecc_modp_sub (ecc, F, B, E);
94
  ecc_modp_add (ecc, G, B, E);  
Niels Möller's avatar
Niels Möller committed
95
96

  /* x3 */
97
  ecc_modp_mul (ecc, B, G, T); /* ! */
98
  ecc_modp_mul (ecc, x3, B, z1);
Niels Möller's avatar
Niels Möller committed
99
100

  /* y3 */
Niels Möller's avatar
Niels Möller committed
101
102
  ecc_modp_mul (ecc, B, F, z1); /* ! */
  ecc_modp_mul (ecc, y3, B, C); /* Clobbers z1 in case r == p. */
Niels Möller's avatar
Niels Möller committed
103
104

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