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 /* Note that 255 % GMP_NUMB_BITS == 0 isn't supported, so x1 always
76 holds at least 256 bits. */
77 mpn_set_base256_le (x1, ecc->p.size, p, CURVE25519_SIZE);
78 /* Clear bit 255, as required by RFC 7748. */
79 x1[255/GMP_NUMB_BITS] &= ~((mp_limb_t) 1 << (255 % GMP_NUMB_BITS));
81 /* Initialize, x2 = x1, z2 = 1 */
82 mpn_copyi (x2, x1, ecc->p.size);
84 mpn_zero (z2+1, ecc->p.size - 1);
86 /* Get x3, z3 from doubling. Since bit 254 is forced to 1. */
87 ecc_modp_add (ecc, A, x2, z2);
88 ecc_modp_sub (ecc, B, x2, z2);
89 ecc_modp_sqr (ecc, AA, A);
90 ecc_modp_sqr (ecc, BB, B);
91 ecc_modp_mul (ecc, x3, AA, BB);
92 ecc_modp_sub (ecc, E, AA, BB);
93 ecc_modp_addmul_1 (ecc, AA, E, 121665);
94 ecc_modp_mul (ecc, z3, E, AA);
96 for (i = 253; i >= 3; i--)
98 int bit = (n[i/8] >> (i & 7)) & 1;
100 cnd_swap (bit, x2, x3, 2*ecc->p.size);
102 /* Formulas from draft-turner-thecurve25519function-00-Mont. We
103 compute new coordinates in memory-address order, since mul
104 and sqr clobbers higher limbs. */
105 ecc_modp_add (ecc, A, x2, z2);
106 ecc_modp_sub (ecc, B, x2, z2);
107 ecc_modp_sqr (ecc, AA, A);
108 ecc_modp_sqr (ecc, BB, B);
109 ecc_modp_mul (ecc, x2, AA, BB); /* Last use of BB */
110 ecc_modp_sub (ecc, E, AA, BB);
111 ecc_modp_addmul_1 (ecc, AA, E, 121665);
112 ecc_modp_add (ecc, C, x3, z3);
113 ecc_modp_sub (ecc, D, x3, z3);
114 ecc_modp_mul (ecc, z2, E, AA); /* Last use of E and AA */
115 ecc_modp_mul (ecc, DA, D, A); /* Last use of D, A. FIXME: could
117 ecc_modp_mul (ecc, CB, C, B);
119 ecc_modp_add (ecc, C, DA, CB);
120 ecc_modp_sqr (ecc, x3, C);
121 ecc_modp_sub (ecc, C, DA, CB);
122 ecc_modp_sqr (ecc, DA, C);
123 ecc_modp_mul (ecc, z3, DA, x1);
125 /* FIXME: Could be combined with the loop's initial cnd_swap. */
126 cnd_swap (bit, x2, x3, 2*ecc->p.size);
128 /* Do the 3 low zero bits, just duplicating x2 */
131 ecc_modp_add (ecc, A, x2, z2);
132 ecc_modp_sub (ecc, B, x2, z2);
133 ecc_modp_sqr (ecc, AA, A);
134 ecc_modp_sqr (ecc, BB, B);
135 ecc_modp_mul (ecc, x2, AA, BB);
136 ecc_modp_sub (ecc, E, AA, BB);
137 ecc_modp_addmul_1 (ecc, AA, E, 121665);
138 ecc_modp_mul (ecc, z2, E, AA);
140 ecc->p.invert (&ecc->p, x3, z2, z3 + ecc->p.size);
141 ecc_modp_mul (ecc, z3, x2, x3);
142 cy = mpn_sub_n (x2, z3, ecc->p.m, ecc->p.size);
143 cnd_copy (cy, x2, z3, ecc->p.size);
144 mpn_get_base256_le (q, CURVE25519_SIZE, x2, ecc->p.size);
146 gmp_free_limbs (scratch, itch);