1 /* ecc-curve25519.c
2
3 Arithmetic and tables for curve25519,
4
5 Copyright (C) 2014 Niels Möller
6
7 This file is part of GNU Nettle.
8
9 GNU Nettle is free software: you can redistribute it and/or
10 modify it under the terms of either:
11
12 * the GNU Lesser General Public License as published by the Free
13 Software Foundation; either version 3 of the License, or (at your
14 option) any later version.
15
16 or
17
18 * the GNU General Public License as published by the Free
19 Software Foundation; either version 2 of the License, or (at your
20 option) any later version.
21
22 or both in parallel, as here.
23
24 GNU Nettle is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 General Public License for more details.
28
29 You should have received copies of the GNU General Public License and
30 the GNU Lesser General Public License along with this program. If
31 not, see http://www.gnu.org/licenses/.
32 */
33
34 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include <assert.h>
39
40 #include "ecc.h"
41 #include "ecc-internal.h"
42
43 #define USE_REDC 0
44
45 #include "ecc-curve25519.h"
46
47 #define PHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255)
48
49 #if HAVE_NATIVE_ecc_curve25519_modp
50
51 #define ecc_curve25519_modp _nettle_ecc_curve25519_modp
52 void
53 ecc_curve25519_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp);
54 #else
55
56 #if PHIGH_BITS == 0
57 #error Unsupported limb size */
58 #endif
59
60 static void
ecc_curve25519_modp(const struct ecc_modulo * m UNUSED,mp_limb_t * rp,mp_limb_t * xp)61 ecc_curve25519_modp(const struct ecc_modulo *m UNUSED, mp_limb_t *rp, mp_limb_t *xp)
62 {
63 mp_limb_t hi, cy;
64
65 cy = mpn_addmul_1 (xp, xp + ECC_LIMB_SIZE, ECC_LIMB_SIZE,
66 (mp_limb_t) 19 << PHIGH_BITS);
67 hi = xp[ECC_LIMB_SIZE-1];
68 cy = (cy << PHIGH_BITS) + (hi >> (GMP_NUMB_BITS - PHIGH_BITS));
69 rp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
70 + sec_add_1 (rp, xp, ECC_LIMB_SIZE - 1, 19 * cy);
71 }
72 #endif /* HAVE_NATIVE_ecc_curve25519_modp */
73
74 #define QHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 252)
75
76 #if QHIGH_BITS == 0
77 #error Unsupported limb size */
78 #endif
79
80 static void
ecc_curve25519_modq(const struct ecc_modulo * q,mp_limb_t * rp,mp_limb_t * xp)81 ecc_curve25519_modq (const struct ecc_modulo *q, mp_limb_t *rp, mp_limb_t *xp)
82 {
83 mp_size_t n;
84 mp_limb_t cy;
85
86 /* n is the offset where we add in the next term */
87 for (n = ECC_LIMB_SIZE; n-- > 0;)
88 {
89 cy = mpn_submul_1 (xp + n,
90 q->B_shifted, ECC_LIMB_SIZE,
91 xp[n + ECC_LIMB_SIZE]);
92 /* Top limb of mBmodq_shifted is zero, so we get cy == 0 or 1 */
93 assert (cy < 2);
94 mpn_cnd_add_n (cy, xp+n, xp+n, q->m, ECC_LIMB_SIZE);
95 }
96
97 cy = mpn_submul_1 (xp, q->m, ECC_LIMB_SIZE,
98 xp[ECC_LIMB_SIZE-1] >> (GMP_NUMB_BITS - QHIGH_BITS));
99 assert (cy < 2);
100 mpn_cnd_add_n (cy, rp, xp, q->m, ECC_LIMB_SIZE);
101 }
102
103 /* Computes a^{(p-5)/8} = a^{2^{252}-3} mod m. Needs 4 * n scratch
104 space. */
105 static void
ecc_mod_pow_252m3(const struct ecc_modulo * m,mp_limb_t * rp,const mp_limb_t * ap,mp_limb_t * scratch)106 ecc_mod_pow_252m3 (const struct ecc_modulo *m,
107 mp_limb_t *rp, const mp_limb_t *ap, mp_limb_t *scratch)
108 {
109 #define a7 scratch
110 #define t0 (scratch + ECC_LIMB_SIZE)
111 #define tp (scratch + 2*ECC_LIMB_SIZE)
112
113 /* a^{2^252 - 3} = a^{(p-5)/8}, using the addition chain
114 2^252 - 3
115 = 1 + (2^252-4)
116 = 1 + 4 (2^250-1)
117 = 1 + 4 (2^125+1)(2^125-1)
118 = 1 + 4 (2^125+1)(1+2(2^124-1))
119 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^62-1))
120 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(2^31-1))
121 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^28-1)))
122 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^14-1)))
123 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(2^7-1)))
124 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^6-1))))
125 = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^3+1)*7)))
126 */
127
128 ecc_mod_pow_2kp1 (m, a7, ap, 1, tp); /* a^3 */
129 ecc_mod_sqr (m, a7, a7, tp); /* a^6 */
130 ecc_mod_mul (m, a7, a7, ap, tp); /* a^7 */
131 ecc_mod_pow_2kp1 (m, rp, a7, 3, tp); /* a^63 = a^{2^6-1} */
132 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^7-2} */
133 ecc_mod_mul (m, rp, rp, ap, tp); /* a^{2^7-1} */
134 ecc_mod_pow_2kp1 (m, t0, rp, 7, tp); /* a^{2^14-1}*/
135 ecc_mod_pow_2kp1 (m, rp, t0, 14, tp); /* a^{2^28-1} */
136 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^29-2} */
137 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^30-4} */
138 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^31-8} */
139 ecc_mod_mul (m, rp, rp, a7, tp); /* a^{2^31-1} */
140 ecc_mod_pow_2kp1 (m, t0, rp, 31, tp); /* a^{2^62-1} */
141 ecc_mod_pow_2kp1 (m, rp, t0, 62, tp); /* a^{2^124-1}*/
142 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^125-2} */
143 ecc_mod_mul (m, rp, rp, ap, tp); /* a^{2^125-1} */
144 ecc_mod_pow_2kp1 (m, t0, rp, 125, tp);/* a^{2^250-1} */
145 ecc_mod_sqr (m, rp, t0, tp); /* a^{2^251-2} */
146 ecc_mod_sqr (m, rp, rp, tp); /* a^{2^252-4} */
147 ecc_mod_mul (m, rp, rp, ap, tp); /* a^{2^252-3} */
148 #undef a7
149 #undef t0
150 #undef tp
151 }
152
153 /* Scratch as for ecc_mod_pow_252m3 above. */
154 #define ECC_25519_INV_ITCH (4*ECC_LIMB_SIZE)
155
156 static void
ecc_curve25519_inv(const struct ecc_modulo * p,mp_limb_t * rp,const mp_limb_t * ap,mp_limb_t * scratch)157 ecc_curve25519_inv (const struct ecc_modulo *p,
158 mp_limb_t *rp, const mp_limb_t *ap,
159 mp_limb_t *scratch)
160 {
161 /* Addition chain
162
163 p - 2 = 2^{255} - 21
164 = 1 + 2 (1 + 4 (2^{252}-3))
165 */
166 ecc_mod_pow_252m3 (p, rp, ap, scratch);
167 ecc_mod_sqr (p, rp, rp, scratch);
168 ecc_mod_sqr (p, rp, rp, scratch);
169 ecc_mod_mul (p, rp, ap, rp, scratch);
170 ecc_mod_sqr (p, rp, rp, scratch);
171 ecc_mod_mul (p, rp, ap, rp, scratch);
172 }
173
174 /* First, do a canonical reduction, then check if zero */
175 static int
ecc_curve25519_zero_p(const struct ecc_modulo * p,mp_limb_t * xp)176 ecc_curve25519_zero_p (const struct ecc_modulo *p, mp_limb_t *xp)
177 {
178 mp_limb_t cy;
179 mp_limb_t w;
180 mp_size_t i;
181 #if PHIGH_BITS > 0
182 mp_limb_t hi = xp[ECC_LIMB_SIZE-1];
183 xp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
184 + sec_add_1 (xp, xp, ECC_LIMB_SIZE - 1, 19 * (hi >> (GMP_NUMB_BITS - PHIGH_BITS)));
185 #endif
186 cy = mpn_sub_n (xp, xp, p->m, ECC_LIMB_SIZE);
187 mpn_cnd_add_n (cy, xp, xp, p->m, ECC_LIMB_SIZE);
188
189 for (i = 0, w = 0; i < ECC_LIMB_SIZE; i++)
190 w |= xp[i];
191 return w == 0;
192 }
193
194 /* Compute x such that x^2 = u/v (mod p). Returns one on success, zero
195 on failure. We use the e = 2 special case of the Shanks-Tonelli
196 algorithm (see http://www.math.vt.edu/people/brown/doc/sqrts.pdf,
197 or Henri Cohen, Computational Algebraic Number Theory, 1.5.1).
198
199 To avoid a separate inversion, we also use a trick of djb's, to
200 compute the candidate root as
201
202 x = (u/v)^{(p+3)/8} = u v^3 (u v^7)^{(p-5)/8}.
203 */
204 #if ECC_SQRT_E != 2
205 #error Broken curve25519 parameters
206 #endif
207
208 /* Needs 2*n space + scratch for ecc_mod_pow_252m3. */
209 #define ECC_25519_SQRT_ITCH (6*ECC_LIMB_SIZE)
210
211 static int
ecc_curve25519_sqrt(const struct ecc_modulo * p,mp_limb_t * rp,const mp_limb_t * up,const mp_limb_t * vp,mp_limb_t * scratch)212 ecc_curve25519_sqrt(const struct ecc_modulo *p, mp_limb_t *rp,
213 const mp_limb_t *up, const mp_limb_t *vp,
214 mp_limb_t *scratch)
215 {
216 int pos, neg;
217
218 #define uv3 scratch
219 #define uv7 (scratch + ECC_LIMB_SIZE)
220
221 #define v2 uv7
222 #define uv uv3
223 #define v4 uv7
224
225 #define scratch_out (scratch + 2 * ECC_LIMB_SIZE)
226
227 #define x2 scratch
228 #define vx2 (scratch + ECC_LIMB_SIZE)
229 #define t0 (scratch + 2*ECC_LIMB_SIZE)
230
231 /* Live values */
232 ecc_mod_sqr (p, v2, vp, scratch_out); /* v2 */
233 ecc_mod_mul (p, uv, up, vp, scratch_out); /* uv, v2 */
234 ecc_mod_mul (p, uv3, uv, v2, scratch_out); /* uv3, v2 */
235 ecc_mod_sqr (p, v4, v2, scratch_out); /* uv3, v4 */
236 ecc_mod_mul (p, uv7, uv3, v4, scratch_out); /* uv7 */
237 ecc_mod_pow_252m3 (p, rp, uv7, scratch_out); /* uv3, uv7p */
238 ecc_mod_mul (p, rp, rp, uv3, scratch_out); /* none */
239
240 /* Check sign. If square root exists, have v x^2 = ±u */
241 ecc_mod_sqr (p, x2, rp, t0);
242 ecc_mod_mul (p, vx2, x2, vp, t0);
243 ecc_mod_add (p, t0, vx2, up);
244 neg = ecc_curve25519_zero_p (p, t0);
245 ecc_mod_sub (p, t0, up, vx2);
246 pos = ecc_curve25519_zero_p (p, t0);
247
248 ecc_mod_mul (p, t0, rp, ecc_sqrt_z, t0);
249 cnd_copy (neg, rp, t0, ECC_LIMB_SIZE);
250 return pos | neg;
251
252 #undef uv3
253 #undef uv7
254 #undef v2
255 #undef uv
256 #undef v4
257 #undef scratch_out
258 #undef x2
259 #undef vx2
260 #undef t0
261 }
262
263 const struct ecc_curve _nettle_curve25519 =
264 {
265 {
266 255,
267 ECC_LIMB_SIZE,
268 ECC_BMODP_SIZE,
269 0,
270 ECC_25519_INV_ITCH,
271 ECC_25519_SQRT_ITCH,
272
273 ecc_p,
274 ecc_Bmodp,
275 ecc_Bmodp_shifted,
276 NULL,
277 ecc_pp1h,
278
279 ecc_curve25519_modp,
280 ecc_curve25519_modp,
281 ecc_curve25519_inv,
282 ecc_curve25519_sqrt,
283 },
284 {
285 253,
286 ECC_LIMB_SIZE,
287 ECC_BMODQ_SIZE,
288 0,
289 ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
290 0,
291
292 ecc_q,
293 ecc_Bmodq,
294 ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */
295 NULL,
296 ecc_qp1h,
297
298 ecc_curve25519_modq,
299 ecc_curve25519_modq,
300 ecc_mod_inv,
301 NULL,
302 },
303
304 0, /* No redc */
305 ECC_PIPPENGER_K,
306 ECC_PIPPENGER_C,
307
308 ECC_ADD_TH_ITCH (ECC_LIMB_SIZE),
309 ECC_ADD_THH_ITCH (ECC_LIMB_SIZE),
310 ECC_DUP_TH_ITCH (ECC_LIMB_SIZE),
311 ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE),
312 ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
313 ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_25519_INV_ITCH),
314
315 ecc_add_th,
316 ecc_add_thh,
317 ecc_dup_th,
318 ecc_mul_a_eh,
319 ecc_mul_g_eh,
320 ecc_eh_to_a,
321
322 ecc_b, /* Edwards curve constant. */
323 ecc_unit,
324 ecc_table
325 };
326