1 /* ecc-dup-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, correct!
44 */
45 void
ecc_dup_jj(const struct ecc_curve * ecc,mp_limb_t * r,const mp_limb_t * p,mp_limb_t * scratch)46 ecc_dup_jj (const struct ecc_curve *ecc,
47 mp_limb_t *r, const mp_limb_t *p,
48 mp_limb_t *scratch)
49 {
50 /* Formulas (from djb,
51 http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
52
53 Computation Operation Live variables
54 delta = z^2 sqr delta
55 gamma = y^2 sqr delta, gamma
56 z' = (y+z)^2-gamma-delta sqr delta, gamma
57 alpha = 3*(x-delta)*(x+delta) mul gamma, beta, alpha
58 beta = x*gamma mul gamma, beta, alpha
59 x' = alpha^2-8*beta sqr gamma, beta, alpha
60 y' = alpha*(4*beta-x')-8*gamma^2 mul, sqr
61 */
62
63 #define delta scratch
64 #define gamma (scratch + ecc->p.size)
65 #define beta (scratch + 2*ecc->p.size)
66 #define g2 (scratch + 3*ecc->p.size)
67 #define sum (scratch + 4*ecc->p.size)
68 #define alpha scratch /* Overlap delta */
69
70 #define xp p
71 #define yp (p + ecc->p.size)
72 #define zp (p + 2*ecc->p.size)
73
74 /* delta */
75 ecc_modp_sqr (ecc, delta, zp);
76
77 /* gamma */
78 ecc_modp_sqr (ecc, gamma, yp);
79
80 /* z'. Can use beta area as scratch. */
81 ecc_modp_add (ecc, r + 2*ecc->p.size, yp, zp);
82 ecc_modp_sqr (ecc, beta, r + 2*ecc->p.size);
83 ecc_modp_sub (ecc, beta, beta, gamma);
84 ecc_modp_sub (ecc, r + 2*ecc->p.size, beta, delta);
85
86 /* alpha. Can use beta area as scratch, and overwrite delta. */
87 ecc_modp_add (ecc, sum, xp, delta);
88 ecc_modp_sub (ecc, delta, xp, delta);
89 ecc_modp_mul (ecc, beta, sum, delta);
90 ecc_modp_mul_1 (ecc, alpha, beta, 3);
91
92 /* beta */
93 ecc_modp_mul (ecc, beta, xp, gamma);
94
95 /* Do gamma^2 and 4*beta early, to get them out of the way. We can
96 then use the old area at gamma as scratch. */
97 ecc_modp_sqr (ecc, g2, gamma);
98 ecc_modp_mul_1 (ecc, sum, beta, 4);
99
100 /* x' */
101 ecc_modp_sqr (ecc, gamma, alpha); /* Overwrites gamma and beta */
102 ecc_modp_submul_1 (ecc, gamma, sum, 2);
103 mpn_copyi (r, gamma, ecc->p.size);
104
105 /* y' */
106 ecc_modp_sub (ecc, sum, sum, r);
107 ecc_modp_mul (ecc, gamma, sum, alpha);
108 ecc_modp_submul_1 (ecc, gamma, g2, 8);
109 mpn_copyi (r + ecc->p.size, gamma, ecc->p.size);
110 }
111