3 Copyright (C) 2014 Niels Möller
5 This file is part of GNU Nettle.
7 GNU Nettle is free software: you can redistribute it and/or
8 modify it under the terms of either:
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.
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.
20 or both in parallel, as here.
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.
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/.
38 #include "curve25519.h"
41 #include "ecc-internal.h"
43 /* Intended to be compatible with NaCl's crypto_scalarmult. */
45 curve25519_mul (uint8_t *q, const uint8_t *n, const uint8_t *p)
47 const struct ecc_curve *ecc = &_nettle_curve25519;
53 /* FIXME: Could save some more scratch space, e.g., by letting BB
54 overlap C, D, and CB overlap A, D. And possibly reusing some of
57 #define x2 (scratch + ecc->p.size)
58 #define z2 (scratch + 2*ecc->p.size)
59 #define x3 (scratch + 3*ecc->p.size)
60 #define z3 (scratch + 4*ecc->p.size)
62 #define A (scratch + 5*ecc->p.size)
63 #define B (scratch + 6*ecc->p.size)
64 #define C (scratch + 7*ecc->p.size)
65 #define D (scratch + 8*ecc->p.size)
66 #define AA (scratch + 9*ecc->p.size)
67 #define BB (scratch +10*ecc->p.size)
68 #define E (scratch + 10*ecc->p.size) /* Overlap BB */
69 #define DA (scratch + 9*ecc->p.size) /* Overlap AA */
70 #define CB (scratch + 10*ecc->p.size) /* Overlap BB */
72 itch = ecc->p.size * 12;
73 scratch = gmp_alloc_limbs (itch);
75 mpn_set_base256_le (x1, ecc->p.size, p, CURVE25519_SIZE);
77 /* Initialize, x2 = x1, z2 = 1 */
78 mpn_copyi (x2, x1, ecc->p.size);
80 mpn_zero (z2+1, ecc->p.size - 1);
82 /* Get x3, z3 from doubling. Since bit 254 is forced to 1. */
83 ecc_modp_add (ecc, A, x2, z2);
84 ecc_modp_sub (ecc, B, x2, z2);
85 ecc_modp_sqr (ecc, AA, A);
86 ecc_modp_sqr (ecc, BB, B);
87 ecc_modp_mul (ecc, x3, AA, BB);
88 ecc_modp_sub (ecc, E, AA, BB);
89 ecc_modp_addmul_1 (ecc, AA, E, 121665);
90 ecc_modp_mul (ecc, z3, E, AA);
92 for (i = 253; i >= 3; i--)
94 int bit = (n[i/8] >> (i & 7)) & 1;
96 cnd_swap (bit, x2, x3, 2*ecc->p.size);
98 /* Formulas from draft-turner-thecurve25519function-00-Mont. We
99 compute new coordinates in memory-address order, since mul
100 and sqr clobbers higher limbs. */
101 ecc_modp_add (ecc, A, x2, z2);
102 ecc_modp_sub (ecc, B, x2, z2);
103 ecc_modp_sqr (ecc, AA, A);
104 ecc_modp_sqr (ecc, BB, B);
105 ecc_modp_mul (ecc, x2, AA, BB); /* Last use of BB */
106 ecc_modp_sub (ecc, E, AA, BB);
107 ecc_modp_addmul_1 (ecc, AA, E, 121665);
108 ecc_modp_add (ecc, C, x3, z3);
109 ecc_modp_sub (ecc, D, x3, z3);
110 ecc_modp_mul (ecc, z2, E, AA); /* Last use of E and AA */
111 ecc_modp_mul (ecc, DA, D, A); /* Last use of D, A. FIXME: could
113 ecc_modp_mul (ecc, CB, C, B);
115 ecc_modp_add (ecc, C, DA, CB);
116 ecc_modp_sqr (ecc, x3, C);
117 ecc_modp_sub (ecc, C, DA, CB);
118 ecc_modp_sqr (ecc, DA, C);
119 ecc_modp_mul (ecc, z3, DA, x1);
121 cnd_swap (bit, x2, x3, 2*ecc->p.size);
123 /* Do the 3 low zero bits, just duplicating x2 */
126 ecc_modp_add (ecc, A, x2, z2);
127 ecc_modp_sub (ecc, B, x2, z2);
128 ecc_modp_sqr (ecc, AA, A);
129 ecc_modp_sqr (ecc, BB, B);
130 ecc_modp_mul (ecc, x2, AA, BB);
131 ecc_modp_sub (ecc, E, AA, BB);
132 ecc_modp_addmul_1 (ecc, AA, E, 121665);
133 ecc_modp_mul (ecc, z2, E, AA);
135 ecc->p.invert (&ecc->p, x3, z2, z3 + ecc->p.size);
136 ecc_modp_mul (ecc, z3, x2, x3);
137 cy = mpn_sub_n (x2, z3, ecc->p.m, ecc->p.size);
138 cnd_copy (cy, x2, z3, ecc->p.size);
139 mpn_get_base256_le (q, CURVE25519_SIZE, x2, ecc->p.size);
141 gmp_free_limbs (scratch, itch);