1 /* ecc-add-jj.c
2
3 Copyright (C) 2013 Niels Möller
4
5 This file is part of GNU Nettle.
6
7 GNU Nettle is free software: you can redistribute it and/or
8 modify it under the terms of either:
9
10 * the GNU Lesser General Public License as published by the Free
11 Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
13
14 or
15
16 * the GNU General Public License as published by the Free
17 Software Foundation; either version 2 of the License, or (at your
18 option) any later version.
19
20 or both in parallel, as here.
21
22 GNU Nettle is distributed in the hope that it will be useful,
23 but WITHOUT ANY WARRANTY; without even the implied warranty of
24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 General Public License for more details.
26
27 You should have received copies of the GNU General Public License and
28 the GNU Lesser General Public License along with this program. If
29 not, see http://www.gnu.org/licenses/.
30 */
31
32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
33
34 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include "ecc.h"
39 #include "ecc-internal.h"
40
41 /* NOTE: Behaviour for corner cases:
42
43 + p = 0 ==> r = 0 (invalid except if also q = 0)
44
45 + q = 0 ==> r = invalid
46
47 + p = -q ==> r = 0, correct!
48
49 + p = q ==> r = 0, invalid
50 */
51
52 void
ecc_add_jja(const struct ecc_curve * ecc,mp_limb_t * r,const mp_limb_t * p,const mp_limb_t * q,mp_limb_t * scratch)53 ecc_add_jja (const struct ecc_curve *ecc,
54 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
55 mp_limb_t *scratch)
56 {
57 #define x1 p
58 #define y1 (p + ecc->p.size)
59 #define z1 (p + 2*ecc->p.size)
60 #define x2 q
61 #define y2 (q + ecc->p.size)
62
63 #define x3 r
64 #define y3 (r + ecc->p.size)
65 #define z3 (r + 2*ecc->p.size)
66
67 /* Formulas, from djb,
68 http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
69
70 Computation Operation Live variables
71
72 ZZ = Z_1^2 sqr ZZ
73 H = X_2*ZZ - X_1 mul (djb: U_2) ZZ, H
74 HH = H^2 sqr ZZ, H, HH
75 ZZZ = ZZ*Z_1 mul ZZ, H, HH, ZZZ
76 Z_3 = (Z_1+H)^2-ZZ-HH sqr H, HH, ZZZ
77 W = 2 (Y_2*ZZZ - Y_1) mul (djb: S_2) H, HH, W
78 I = 4*HH H, W, I
79 J = H*I mul W, I, J
80 V = X_1*I mul W, J, V
81 X_3 = W^2-J-2*V sqr W, J, V
82 Y_3 = W*(V-X_3)-2*Y_1*J mul, mul
83 */
84 #define zz scratch
85 #define h (scratch + ecc->p.size)
86 #define w (scratch + 2*ecc->p.size)
87 #define hh zz
88 #define i zz
89 #define v zz
90 #define j h
91 #define tp (scratch + 3*ecc->p.size)
92
93 /* zz */
94 ecc_mod_sqr (&ecc->p, zz, z1, tp); /* zz */
95 /* h*/
96 ecc_mod_mul (&ecc->p, h, x2, zz, tp); /* zz, h */
97 ecc_mod_sub (&ecc->p, h, h, x1);
98 /* Do z^3 early, store at w. */
99 ecc_mod_mul (&ecc->p, w, zz, z1, tp); /* zz, h, w */
100 /* z_3 */
101 ecc_mod_add (&ecc->p, z3, z1, h);
102 ecc_mod_sqr (&ecc->p, z3, z3, tp);
103 ecc_mod_sub (&ecc->p, z3, z3, zz); /* h, w */
104 /* hh */
105 ecc_mod_sqr (&ecc->p, hh, h, tp); /* h, w, hh */
106 ecc_mod_sub (&ecc->p, z3, z3, hh);
107
108 /* w */
109 ecc_mod_mul (&ecc->p, w, y2, w, tp);
110 ecc_mod_sub (&ecc->p, w, w, y1);
111 ecc_mod_add (&ecc->p, w, w, w);
112
113 /* i replaces hh */
114 ecc_mod_mul_1 (&ecc->p, i, hh, 4); /* h, w, i */
115 /* j replaces h */
116 ecc_mod_mul (&ecc->p, j, i, h, tp); /* w, i, j */
117
118 /* v replaces i */
119 ecc_mod_mul (&ecc->p, v, x1, i, tp);
120
121 /* x_3 */
122 ecc_mod_sqr (&ecc->p, x3, w, tp);
123 ecc_mod_sub (&ecc->p, x3, x3, j);
124 ecc_mod_submul_1 (&ecc->p, x3, v, 2);
125
126 /* y_3 */
127 ecc_mod_mul (&ecc->p, j, y1, j, tp);
128 ecc_mod_sub (&ecc->p, y3, v, x3);
129 ecc_mod_mul (&ecc->p, y3, y3, w, tp);
130 ecc_mod_submul_1 (&ecc->p, y3, j, 2);
131 }
132