Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
8774 | rgimad | 1 | /* |
2 | * Elliptic curves over GF(p): generic functions |
||
3 | * |
||
4 | * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved |
||
5 | * SPDX-License-Identifier: GPL-2.0 |
||
6 | * |
||
7 | * This program is free software; you can redistribute it and/or modify |
||
8 | * it under the terms of the GNU General Public License as published by |
||
9 | * the Free Software Foundation; either version 2 of the License, or |
||
10 | * (at your option) any later version. |
||
11 | * |
||
12 | * This program is distributed in the hope that it will be useful, |
||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
15 | * GNU General Public License for more details. |
||
16 | * |
||
17 | * You should have received a copy of the GNU General Public License along |
||
18 | * with this program; if not, write to the Free Software Foundation, Inc., |
||
19 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
||
20 | * |
||
21 | * This file is part of mbed TLS (https://tls.mbed.org) |
||
22 | */ |
||
23 | |||
24 | /* |
||
25 | * References: |
||
26 | * |
||
27 | * SEC1 http://www.secg.org/index.php?action=secg,docs_secg |
||
28 | * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone |
||
29 | * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf |
||
30 | * RFC 4492 for the related TLS structures and constants |
||
31 | * RFC 7748 for the Curve448 and Curve25519 curve definitions |
||
32 | * |
||
33 | * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf |
||
34 | * |
||
35 | * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis |
||
36 | * for elliptic curve cryptosystems. In : Cryptographic Hardware and |
||
37 | * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302. |
||
38 | * |
||
39 | * |
||
40 | * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to |
||
41 | * render ECC resistant against Side Channel Attacks. IACR Cryptology |
||
42 | * ePrint Archive, 2004, vol. 2004, p. 342. |
||
43 | * |
||
44 | */ |
||
45 | |||
46 | #if !defined(MBEDTLS_CONFIG_FILE) |
||
47 | #include "mbedtls/config.h" |
||
48 | #else |
||
49 | #include MBEDTLS_CONFIG_FILE |
||
50 | #endif |
||
51 | |||
52 | /** |
||
53 | * \brief Function level alternative implementation. |
||
54 | * |
||
55 | * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to |
||
56 | * replace certain functions in this module. The alternative implementations are |
||
57 | * typically hardware accelerators and need to activate the hardware before the |
||
58 | * computation starts and deactivate it after it finishes. The |
||
59 | * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve |
||
60 | * this purpose. |
||
61 | * |
||
62 | * To preserve the correct functionality the following conditions must hold: |
||
63 | * |
||
64 | * - The alternative implementation must be activated by |
||
65 | * mbedtls_internal_ecp_init() before any of the replaceable functions is |
||
66 | * called. |
||
67 | * - mbedtls_internal_ecp_free() must \b only be called when the alternative |
||
68 | * implementation is activated. |
||
69 | * - mbedtls_internal_ecp_init() must \b not be called when the alternative |
||
70 | * implementation is activated. |
||
71 | * - Public functions must not return while the alternative implementation is |
||
72 | * activated. |
||
73 | * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and |
||
74 | * before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
75 | * \endcode ensures that the alternative implementation supports the current |
||
76 | * group. |
||
77 | */ |
||
78 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
79 | #endif |
||
80 | |||
81 | #if defined(MBEDTLS_ECP_C) |
||
82 | |||
83 | #include "mbedtls/ecp.h" |
||
84 | #include "mbedtls/threading.h" |
||
85 | #include "mbedtls/platform_util.h" |
||
86 | |||
87 | #include |
||
88 | |||
89 | #if !defined(MBEDTLS_ECP_ALT) |
||
90 | |||
91 | /* Parameter validation macros based on platform_util.h */ |
||
92 | #define ECP_VALIDATE_RET( cond ) \ |
||
93 | MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA ) |
||
94 | #define ECP_VALIDATE( cond ) \ |
||
95 | MBEDTLS_INTERNAL_VALIDATE( cond ) |
||
96 | |||
97 | #if defined(MBEDTLS_PLATFORM_C) |
||
98 | #include "mbedtls/platform.h" |
||
99 | #else |
||
100 | #include |
||
101 | #include |
||
102 | #define mbedtls_printf printf |
||
103 | #define mbedtls_calloc calloc |
||
104 | #define mbedtls_free free |
||
105 | #endif |
||
106 | |||
107 | #include "mbedtls/ecp_internal.h" |
||
108 | |||
109 | #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \ |
||
110 | !defined(inline) && !defined(__cplusplus) |
||
111 | #define inline __inline |
||
112 | #endif |
||
113 | |||
114 | #if defined(MBEDTLS_SELF_TEST) |
||
115 | /* |
||
116 | * Counts of point addition and doubling, and field multiplications. |
||
117 | * Used to test resistance of point multiplication to simple timing attacks. |
||
118 | */ |
||
119 | static unsigned long add_count, dbl_count, mul_count; |
||
120 | #endif |
||
121 | |||
122 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
123 | /* |
||
124 | * Maximum number of "basic operations" to be done in a row. |
||
125 | * |
||
126 | * Default value 0 means that ECC operations will not yield. |
||
127 | * Note that regardless of the value of ecp_max_ops, always at |
||
128 | * least one step is performed before yielding. |
||
129 | * |
||
130 | * Setting ecp_max_ops=1 can be suitable for testing purposes |
||
131 | * as it will interrupt computation at all possible points. |
||
132 | */ |
||
133 | static unsigned ecp_max_ops = 0; |
||
134 | |||
135 | /* |
||
136 | * Set ecp_max_ops |
||
137 | */ |
||
138 | void mbedtls_ecp_set_max_ops( unsigned max_ops ) |
||
139 | { |
||
140 | ecp_max_ops = max_ops; |
||
141 | } |
||
142 | |||
143 | /* |
||
144 | * Check if restart is enabled |
||
145 | */ |
||
146 | int mbedtls_ecp_restart_is_enabled( void ) |
||
147 | { |
||
148 | return( ecp_max_ops != 0 ); |
||
149 | } |
||
150 | |||
151 | /* |
||
152 | * Restart sub-context for ecp_mul_comb() |
||
153 | */ |
||
154 | struct mbedtls_ecp_restart_mul |
||
155 | { |
||
156 | mbedtls_ecp_point R; /* current intermediate result */ |
||
157 | size_t i; /* current index in various loops, 0 outside */ |
||
158 | mbedtls_ecp_point *T; /* table for precomputed points */ |
||
159 | unsigned char T_size; /* number of points in table T */ |
||
160 | enum { /* what were we doing last time we returned? */ |
||
161 | ecp_rsm_init = 0, /* nothing so far, dummy initial state */ |
||
162 | ecp_rsm_pre_dbl, /* precompute 2^n multiples */ |
||
163 | ecp_rsm_pre_norm_dbl, /* normalize precomputed 2^n multiples */ |
||
164 | ecp_rsm_pre_add, /* precompute remaining points by adding */ |
||
165 | ecp_rsm_pre_norm_add, /* normalize all precomputed points */ |
||
166 | ecp_rsm_comb_core, /* ecp_mul_comb_core() */ |
||
167 | ecp_rsm_final_norm, /* do the final normalization */ |
||
168 | } state; |
||
169 | }; |
||
170 | |||
171 | /* |
||
172 | * Init restart_mul sub-context |
||
173 | */ |
||
174 | static void ecp_restart_rsm_init( mbedtls_ecp_restart_mul_ctx *ctx ) |
||
175 | { |
||
176 | mbedtls_ecp_point_init( &ctx->R ); |
||
177 | ctx->i = 0; |
||
178 | ctx->T = NULL; |
||
179 | ctx->T_size = 0; |
||
180 | ctx->state = ecp_rsm_init; |
||
181 | } |
||
182 | |||
183 | /* |
||
184 | * Free the components of a restart_mul sub-context |
||
185 | */ |
||
186 | static void ecp_restart_rsm_free( mbedtls_ecp_restart_mul_ctx *ctx ) |
||
187 | { |
||
188 | unsigned char i; |
||
189 | |||
190 | if( ctx == NULL ) |
||
191 | return; |
||
192 | |||
193 | mbedtls_ecp_point_free( &ctx->R ); |
||
194 | |||
195 | if( ctx->T != NULL ) |
||
196 | { |
||
197 | for( i = 0; i < ctx->T_size; i++ ) |
||
198 | mbedtls_ecp_point_free( ctx->T + i ); |
||
199 | mbedtls_free( ctx->T ); |
||
200 | } |
||
201 | |||
202 | ecp_restart_rsm_init( ctx ); |
||
203 | } |
||
204 | |||
205 | /* |
||
206 | * Restart context for ecp_muladd() |
||
207 | */ |
||
208 | struct mbedtls_ecp_restart_muladd |
||
209 | { |
||
210 | mbedtls_ecp_point mP; /* mP value */ |
||
211 | mbedtls_ecp_point R; /* R intermediate result */ |
||
212 | enum { /* what should we do next? */ |
||
213 | ecp_rsma_mul1 = 0, /* first multiplication */ |
||
214 | ecp_rsma_mul2, /* second multiplication */ |
||
215 | ecp_rsma_add, /* addition */ |
||
216 | ecp_rsma_norm, /* normalization */ |
||
217 | } state; |
||
218 | }; |
||
219 | |||
220 | /* |
||
221 | * Init restart_muladd sub-context |
||
222 | */ |
||
223 | static void ecp_restart_ma_init( mbedtls_ecp_restart_muladd_ctx *ctx ) |
||
224 | { |
||
225 | mbedtls_ecp_point_init( &ctx->mP ); |
||
226 | mbedtls_ecp_point_init( &ctx->R ); |
||
227 | ctx->state = ecp_rsma_mul1; |
||
228 | } |
||
229 | |||
230 | /* |
||
231 | * Free the components of a restart_muladd sub-context |
||
232 | */ |
||
233 | static void ecp_restart_ma_free( mbedtls_ecp_restart_muladd_ctx *ctx ) |
||
234 | { |
||
235 | if( ctx == NULL ) |
||
236 | return; |
||
237 | |||
238 | mbedtls_ecp_point_free( &ctx->mP ); |
||
239 | mbedtls_ecp_point_free( &ctx->R ); |
||
240 | |||
241 | ecp_restart_ma_init( ctx ); |
||
242 | } |
||
243 | |||
244 | /* |
||
245 | * Initialize a restart context |
||
246 | */ |
||
247 | void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx ) |
||
248 | { |
||
249 | ECP_VALIDATE( ctx != NULL ); |
||
250 | ctx->ops_done = 0; |
||
251 | ctx->depth = 0; |
||
252 | ctx->rsm = NULL; |
||
253 | ctx->ma = NULL; |
||
254 | } |
||
255 | |||
256 | /* |
||
257 | * Free the components of a restart context |
||
258 | */ |
||
259 | void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx *ctx ) |
||
260 | { |
||
261 | if( ctx == NULL ) |
||
262 | return; |
||
263 | |||
264 | ecp_restart_rsm_free( ctx->rsm ); |
||
265 | mbedtls_free( ctx->rsm ); |
||
266 | |||
267 | ecp_restart_ma_free( ctx->ma ); |
||
268 | mbedtls_free( ctx->ma ); |
||
269 | |||
270 | mbedtls_ecp_restart_init( ctx ); |
||
271 | } |
||
272 | |||
273 | /* |
||
274 | * Check if we can do the next step |
||
275 | */ |
||
276 | int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp, |
||
277 | mbedtls_ecp_restart_ctx *rs_ctx, |
||
278 | unsigned ops ) |
||
279 | { |
||
280 | ECP_VALIDATE_RET( grp != NULL ); |
||
281 | |||
282 | if( rs_ctx != NULL && ecp_max_ops != 0 ) |
||
283 | { |
||
284 | /* scale depending on curve size: the chosen reference is 256-bit, |
||
285 | * and multiplication is quadratic. Round to the closest integer. */ |
||
286 | if( grp->pbits >= 512 ) |
||
287 | ops *= 4; |
||
288 | else if( grp->pbits >= 384 ) |
||
289 | ops *= 2; |
||
290 | |||
291 | /* Avoid infinite loops: always allow first step. |
||
292 | * Because of that, however, it's not generally true |
||
293 | * that ops_done <= ecp_max_ops, so the check |
||
294 | * ops_done > ecp_max_ops below is mandatory. */ |
||
295 | if( ( rs_ctx->ops_done != 0 ) && |
||
296 | ( rs_ctx->ops_done > ecp_max_ops || |
||
297 | ops > ecp_max_ops - rs_ctx->ops_done ) ) |
||
298 | { |
||
299 | return( MBEDTLS_ERR_ECP_IN_PROGRESS ); |
||
300 | } |
||
301 | |||
302 | /* update running count */ |
||
303 | rs_ctx->ops_done += ops; |
||
304 | } |
||
305 | |||
306 | return( 0 ); |
||
307 | } |
||
308 | |||
309 | /* Call this when entering a function that needs its own sub-context */ |
||
310 | #define ECP_RS_ENTER( SUB ) do { \ |
||
311 | /* reset ops count for this call if top-level */ \ |
||
312 | if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) \ |
||
313 | rs_ctx->ops_done = 0; \ |
||
314 | \ |
||
315 | /* set up our own sub-context if needed */ \ |
||
316 | if( mbedtls_ecp_restart_is_enabled() && \ |
||
317 | rs_ctx != NULL && rs_ctx->SUB == NULL ) \ |
||
318 | { \ |
||
319 | rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) ); \ |
||
320 | if( rs_ctx->SUB == NULL ) \ |
||
321 | return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); \ |
||
322 | \ |
||
323 | ecp_restart_## SUB ##_init( rs_ctx->SUB ); \ |
||
324 | } \ |
||
325 | } while( 0 ) |
||
326 | |||
327 | /* Call this when leaving a function that needs its own sub-context */ |
||
328 | #define ECP_RS_LEAVE( SUB ) do { \ |
||
329 | /* clear our sub-context when not in progress (done or error) */ \ |
||
330 | if( rs_ctx != NULL && rs_ctx->SUB != NULL && \ |
||
331 | ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) \ |
||
332 | { \ |
||
333 | ecp_restart_## SUB ##_free( rs_ctx->SUB ); \ |
||
334 | mbedtls_free( rs_ctx->SUB ); \ |
||
335 | rs_ctx->SUB = NULL; \ |
||
336 | } \ |
||
337 | \ |
||
338 | if( rs_ctx != NULL ) \ |
||
339 | rs_ctx->depth--; \ |
||
340 | } while( 0 ) |
||
341 | |||
342 | #else /* MBEDTLS_ECP_RESTARTABLE */ |
||
343 | |||
344 | #define ECP_RS_ENTER( sub ) (void) rs_ctx; |
||
345 | #define ECP_RS_LEAVE( sub ) (void) rs_ctx; |
||
346 | |||
347 | #endif /* MBEDTLS_ECP_RESTARTABLE */ |
||
348 | |||
349 | #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \ |
||
350 | defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \ |
||
351 | defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \ |
||
352 | defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \ |
||
353 | defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \ |
||
354 | defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \ |
||
355 | defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \ |
||
356 | defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \ |
||
357 | defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \ |
||
358 | defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \ |
||
359 | defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) |
||
360 | #define ECP_SHORTWEIERSTRASS |
||
361 | #endif |
||
362 | |||
363 | #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \ |
||
364 | defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) |
||
365 | #define ECP_MONTGOMERY |
||
366 | #endif |
||
367 | |||
368 | /* |
||
369 | * Curve types: internal for now, might be exposed later |
||
370 | */ |
||
371 | typedef enum |
||
372 | { |
||
373 | ECP_TYPE_NONE = 0, |
||
374 | ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */ |
||
375 | ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */ |
||
376 | } ecp_curve_type; |
||
377 | |||
378 | /* |
||
379 | * List of supported curves: |
||
380 | * - internal ID |
||
381 | * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2) |
||
382 | * - size in bits |
||
383 | * - readable name |
||
384 | * |
||
385 | * Curves are listed in order: largest curves first, and for a given size, |
||
386 | * fastest curves first. This provides the default order for the SSL module. |
||
387 | * |
||
388 | * Reminder: update profiles in x509_crt.c when adding a new curves! |
||
389 | */ |
||
390 | static const mbedtls_ecp_curve_info ecp_supported_curves[] = |
||
391 | { |
||
392 | #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) |
||
393 | { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" }, |
||
394 | #endif |
||
395 | #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) |
||
396 | { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" }, |
||
397 | #endif |
||
398 | #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) |
||
399 | { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" }, |
||
400 | #endif |
||
401 | #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) |
||
402 | { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" }, |
||
403 | #endif |
||
404 | #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) |
||
405 | { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" }, |
||
406 | #endif |
||
407 | #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) |
||
408 | { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" }, |
||
409 | #endif |
||
410 | #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) |
||
411 | { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" }, |
||
412 | #endif |
||
413 | #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) |
||
414 | { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" }, |
||
415 | #endif |
||
416 | #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) |
||
417 | { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" }, |
||
418 | #endif |
||
419 | #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) |
||
420 | { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" }, |
||
421 | #endif |
||
422 | #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) |
||
423 | { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, |
||
424 | #endif |
||
425 | { MBEDTLS_ECP_DP_NONE, 0, 0, NULL }, |
||
426 | }; |
||
427 | |||
428 | #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \ |
||
429 | sizeof( ecp_supported_curves[0] ) |
||
430 | |||
431 | static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES]; |
||
432 | |||
433 | /* |
||
434 | * List of supported curves and associated info |
||
435 | */ |
||
436 | const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void ) |
||
437 | { |
||
438 | return( ecp_supported_curves ); |
||
439 | } |
||
440 | |||
441 | /* |
||
442 | * List of supported curves, group ID only |
||
443 | */ |
||
444 | const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void ) |
||
445 | { |
||
446 | static int init_done = 0; |
||
447 | |||
448 | if( ! init_done ) |
||
449 | { |
||
450 | size_t i = 0; |
||
451 | const mbedtls_ecp_curve_info *curve_info; |
||
452 | |||
453 | for( curve_info = mbedtls_ecp_curve_list(); |
||
454 | curve_info->grp_id != MBEDTLS_ECP_DP_NONE; |
||
455 | curve_info++ ) |
||
456 | { |
||
457 | ecp_supported_grp_id[i++] = curve_info->grp_id; |
||
458 | } |
||
459 | ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE; |
||
460 | |||
461 | init_done = 1; |
||
462 | } |
||
463 | |||
464 | return( ecp_supported_grp_id ); |
||
465 | } |
||
466 | |||
467 | /* |
||
468 | * Get the curve info for the internal identifier |
||
469 | */ |
||
470 | const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id ) |
||
471 | { |
||
472 | const mbedtls_ecp_curve_info *curve_info; |
||
473 | |||
474 | for( curve_info = mbedtls_ecp_curve_list(); |
||
475 | curve_info->grp_id != MBEDTLS_ECP_DP_NONE; |
||
476 | curve_info++ ) |
||
477 | { |
||
478 | if( curve_info->grp_id == grp_id ) |
||
479 | return( curve_info ); |
||
480 | } |
||
481 | |||
482 | return( NULL ); |
||
483 | } |
||
484 | |||
485 | /* |
||
486 | * Get the curve info from the TLS identifier |
||
487 | */ |
||
488 | const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id ) |
||
489 | { |
||
490 | const mbedtls_ecp_curve_info *curve_info; |
||
491 | |||
492 | for( curve_info = mbedtls_ecp_curve_list(); |
||
493 | curve_info->grp_id != MBEDTLS_ECP_DP_NONE; |
||
494 | curve_info++ ) |
||
495 | { |
||
496 | if( curve_info->tls_id == tls_id ) |
||
497 | return( curve_info ); |
||
498 | } |
||
499 | |||
500 | return( NULL ); |
||
501 | } |
||
502 | |||
503 | /* |
||
504 | * Get the curve info from the name |
||
505 | */ |
||
506 | const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name ) |
||
507 | { |
||
508 | const mbedtls_ecp_curve_info *curve_info; |
||
509 | |||
510 | if( name == NULL ) |
||
511 | return( NULL ); |
||
512 | |||
513 | for( curve_info = mbedtls_ecp_curve_list(); |
||
514 | curve_info->grp_id != MBEDTLS_ECP_DP_NONE; |
||
515 | curve_info++ ) |
||
516 | { |
||
517 | if( strcmp( curve_info->name, name ) == 0 ) |
||
518 | return( curve_info ); |
||
519 | } |
||
520 | |||
521 | return( NULL ); |
||
522 | } |
||
523 | |||
524 | /* |
||
525 | * Get the type of a curve |
||
526 | */ |
||
527 | static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp ) |
||
528 | { |
||
529 | if( grp->G.X.p == NULL ) |
||
530 | return( ECP_TYPE_NONE ); |
||
531 | |||
532 | if( grp->G.Y.p == NULL ) |
||
533 | return( ECP_TYPE_MONTGOMERY ); |
||
534 | else |
||
535 | return( ECP_TYPE_SHORT_WEIERSTRASS ); |
||
536 | } |
||
537 | |||
538 | /* |
||
539 | * Initialize (the components of) a point |
||
540 | */ |
||
541 | void mbedtls_ecp_point_init( mbedtls_ecp_point *pt ) |
||
542 | { |
||
543 | ECP_VALIDATE( pt != NULL ); |
||
544 | |||
545 | mbedtls_mpi_init( &pt->X ); |
||
546 | mbedtls_mpi_init( &pt->Y ); |
||
547 | mbedtls_mpi_init( &pt->Z ); |
||
548 | } |
||
549 | |||
550 | /* |
||
551 | * Initialize (the components of) a group |
||
552 | */ |
||
553 | void mbedtls_ecp_group_init( mbedtls_ecp_group *grp ) |
||
554 | { |
||
555 | ECP_VALIDATE( grp != NULL ); |
||
556 | |||
557 | grp->id = MBEDTLS_ECP_DP_NONE; |
||
558 | mbedtls_mpi_init( &grp->P ); |
||
559 | mbedtls_mpi_init( &grp->A ); |
||
560 | mbedtls_mpi_init( &grp->B ); |
||
561 | mbedtls_ecp_point_init( &grp->G ); |
||
562 | mbedtls_mpi_init( &grp->N ); |
||
563 | grp->pbits = 0; |
||
564 | grp->nbits = 0; |
||
565 | grp->h = 0; |
||
566 | grp->modp = NULL; |
||
567 | grp->t_pre = NULL; |
||
568 | grp->t_post = NULL; |
||
569 | grp->t_data = NULL; |
||
570 | grp->T = NULL; |
||
571 | grp->T_size = 0; |
||
572 | } |
||
573 | |||
574 | /* |
||
575 | * Initialize (the components of) a key pair |
||
576 | */ |
||
577 | void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key ) |
||
578 | { |
||
579 | ECP_VALIDATE( key != NULL ); |
||
580 | |||
581 | mbedtls_ecp_group_init( &key->grp ); |
||
582 | mbedtls_mpi_init( &key->d ); |
||
583 | mbedtls_ecp_point_init( &key->Q ); |
||
584 | } |
||
585 | |||
586 | /* |
||
587 | * Unallocate (the components of) a point |
||
588 | */ |
||
589 | void mbedtls_ecp_point_free( mbedtls_ecp_point *pt ) |
||
590 | { |
||
591 | if( pt == NULL ) |
||
592 | return; |
||
593 | |||
594 | mbedtls_mpi_free( &( pt->X ) ); |
||
595 | mbedtls_mpi_free( &( pt->Y ) ); |
||
596 | mbedtls_mpi_free( &( pt->Z ) ); |
||
597 | } |
||
598 | |||
599 | /* |
||
600 | * Unallocate (the components of) a group |
||
601 | */ |
||
602 | void mbedtls_ecp_group_free( mbedtls_ecp_group *grp ) |
||
603 | { |
||
604 | size_t i; |
||
605 | |||
606 | if( grp == NULL ) |
||
607 | return; |
||
608 | |||
609 | if( grp->h != 1 ) |
||
610 | { |
||
611 | mbedtls_mpi_free( &grp->P ); |
||
612 | mbedtls_mpi_free( &grp->A ); |
||
613 | mbedtls_mpi_free( &grp->B ); |
||
614 | mbedtls_ecp_point_free( &grp->G ); |
||
615 | mbedtls_mpi_free( &grp->N ); |
||
616 | } |
||
617 | |||
618 | if( grp->T != NULL ) |
||
619 | { |
||
620 | for( i = 0; i < grp->T_size; i++ ) |
||
621 | mbedtls_ecp_point_free( &grp->T[i] ); |
||
622 | mbedtls_free( grp->T ); |
||
623 | } |
||
624 | |||
625 | mbedtls_platform_zeroize( grp, sizeof( mbedtls_ecp_group ) ); |
||
626 | } |
||
627 | |||
628 | /* |
||
629 | * Unallocate (the components of) a key pair |
||
630 | */ |
||
631 | void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key ) |
||
632 | { |
||
633 | if( key == NULL ) |
||
634 | return; |
||
635 | |||
636 | mbedtls_ecp_group_free( &key->grp ); |
||
637 | mbedtls_mpi_free( &key->d ); |
||
638 | mbedtls_ecp_point_free( &key->Q ); |
||
639 | } |
||
640 | |||
641 | /* |
||
642 | * Copy the contents of a point |
||
643 | */ |
||
644 | int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) |
||
645 | { |
||
646 | int ret; |
||
647 | ECP_VALIDATE_RET( P != NULL ); |
||
648 | ECP_VALIDATE_RET( Q != NULL ); |
||
649 | |||
650 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) ); |
||
651 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) ); |
||
652 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) ); |
||
653 | |||
654 | cleanup: |
||
655 | return( ret ); |
||
656 | } |
||
657 | |||
658 | /* |
||
659 | * Copy the contents of a group object |
||
660 | */ |
||
661 | int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src ) |
||
662 | { |
||
663 | ECP_VALIDATE_RET( dst != NULL ); |
||
664 | ECP_VALIDATE_RET( src != NULL ); |
||
665 | |||
666 | return( mbedtls_ecp_group_load( dst, src->id ) ); |
||
667 | } |
||
668 | |||
669 | /* |
||
670 | * Set point to zero |
||
671 | */ |
||
672 | int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt ) |
||
673 | { |
||
674 | int ret; |
||
675 | ECP_VALIDATE_RET( pt != NULL ); |
||
676 | |||
677 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) ); |
||
678 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) ); |
||
679 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) ); |
||
680 | |||
681 | cleanup: |
||
682 | return( ret ); |
||
683 | } |
||
684 | |||
685 | /* |
||
686 | * Tell if a point is zero |
||
687 | */ |
||
688 | int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt ) |
||
689 | { |
||
690 | ECP_VALIDATE_RET( pt != NULL ); |
||
691 | |||
692 | return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ); |
||
693 | } |
||
694 | |||
695 | /* |
||
696 | * Compare two points lazily |
||
697 | */ |
||
698 | int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P, |
||
699 | const mbedtls_ecp_point *Q ) |
||
700 | { |
||
701 | ECP_VALIDATE_RET( P != NULL ); |
||
702 | ECP_VALIDATE_RET( Q != NULL ); |
||
703 | |||
704 | if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 && |
||
705 | mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 && |
||
706 | mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 ) |
||
707 | { |
||
708 | return( 0 ); |
||
709 | } |
||
710 | |||
711 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
712 | } |
||
713 | |||
714 | /* |
||
715 | * Import a non-zero point from ASCII strings |
||
716 | */ |
||
717 | int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix, |
||
718 | const char *x, const char *y ) |
||
719 | { |
||
720 | int ret; |
||
721 | ECP_VALIDATE_RET( P != NULL ); |
||
722 | ECP_VALIDATE_RET( x != NULL ); |
||
723 | ECP_VALIDATE_RET( y != NULL ); |
||
724 | |||
725 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) ); |
||
726 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) ); |
||
727 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); |
||
728 | |||
729 | cleanup: |
||
730 | return( ret ); |
||
731 | } |
||
732 | |||
733 | /* |
||
734 | * Export a point into unsigned binary data (SEC1 2.3.3) |
||
735 | */ |
||
736 | int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, |
||
737 | const mbedtls_ecp_point *P, |
||
738 | int format, size_t *olen, |
||
739 | unsigned char *buf, size_t buflen ) |
||
740 | { |
||
741 | int ret = 0; |
||
742 | size_t plen; |
||
743 | ECP_VALIDATE_RET( grp != NULL ); |
||
744 | ECP_VALIDATE_RET( P != NULL ); |
||
745 | ECP_VALIDATE_RET( olen != NULL ); |
||
746 | ECP_VALIDATE_RET( buf != NULL ); |
||
747 | ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED || |
||
748 | format == MBEDTLS_ECP_PF_COMPRESSED ); |
||
749 | |||
750 | /* |
||
751 | * Common case: P == 0 |
||
752 | */ |
||
753 | if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) |
||
754 | { |
||
755 | if( buflen < 1 ) |
||
756 | return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); |
||
757 | |||
758 | buf[0] = 0x00; |
||
759 | *olen = 1; |
||
760 | |||
761 | return( 0 ); |
||
762 | } |
||
763 | |||
764 | plen = mbedtls_mpi_size( &grp->P ); |
||
765 | |||
766 | if( format == MBEDTLS_ECP_PF_UNCOMPRESSED ) |
||
767 | { |
||
768 | *olen = 2 * plen + 1; |
||
769 | |||
770 | if( buflen < *olen ) |
||
771 | return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); |
||
772 | |||
773 | buf[0] = 0x04; |
||
774 | MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); |
||
775 | MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) ); |
||
776 | } |
||
777 | else if( format == MBEDTLS_ECP_PF_COMPRESSED ) |
||
778 | { |
||
779 | *olen = plen + 1; |
||
780 | |||
781 | if( buflen < *olen ) |
||
782 | return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); |
||
783 | |||
784 | buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 ); |
||
785 | MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); |
||
786 | } |
||
787 | |||
788 | cleanup: |
||
789 | return( ret ); |
||
790 | } |
||
791 | |||
792 | /* |
||
793 | * Import a point from unsigned binary data (SEC1 2.3.4) |
||
794 | */ |
||
795 | int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, |
||
796 | mbedtls_ecp_point *pt, |
||
797 | const unsigned char *buf, size_t ilen ) |
||
798 | { |
||
799 | int ret; |
||
800 | size_t plen; |
||
801 | ECP_VALIDATE_RET( grp != NULL ); |
||
802 | ECP_VALIDATE_RET( pt != NULL ); |
||
803 | ECP_VALIDATE_RET( buf != NULL ); |
||
804 | |||
805 | if( ilen < 1 ) |
||
806 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
807 | |||
808 | if( buf[0] == 0x00 ) |
||
809 | { |
||
810 | if( ilen == 1 ) |
||
811 | return( mbedtls_ecp_set_zero( pt ) ); |
||
812 | else |
||
813 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
814 | } |
||
815 | |||
816 | plen = mbedtls_mpi_size( &grp->P ); |
||
817 | |||
818 | if( buf[0] != 0x04 ) |
||
819 | return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); |
||
820 | |||
821 | if( ilen != 2 * plen + 1 ) |
||
822 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
823 | |||
824 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) ); |
||
825 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) ); |
||
826 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); |
||
827 | |||
828 | cleanup: |
||
829 | return( ret ); |
||
830 | } |
||
831 | |||
832 | /* |
||
833 | * Import a point from a TLS ECPoint record (RFC 4492) |
||
834 | * struct { |
||
835 | * opaque point <1..2^8-1>; |
||
836 | * } ECPoint; |
||
837 | */ |
||
838 | int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, |
||
839 | mbedtls_ecp_point *pt, |
||
840 | const unsigned char **buf, size_t buf_len ) |
||
841 | { |
||
842 | unsigned char data_len; |
||
843 | const unsigned char *buf_start; |
||
844 | ECP_VALIDATE_RET( grp != NULL ); |
||
845 | ECP_VALIDATE_RET( pt != NULL ); |
||
846 | ECP_VALIDATE_RET( buf != NULL ); |
||
847 | ECP_VALIDATE_RET( *buf != NULL ); |
||
848 | |||
849 | /* |
||
850 | * We must have at least two bytes (1 for length, at least one for data) |
||
851 | */ |
||
852 | if( buf_len < 2 ) |
||
853 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
854 | |||
855 | data_len = *(*buf)++; |
||
856 | if( data_len < 1 || data_len > buf_len - 1 ) |
||
857 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
858 | |||
859 | /* |
||
860 | * Save buffer start for read_binary and update buf |
||
861 | */ |
||
862 | buf_start = *buf; |
||
863 | *buf += data_len; |
||
864 | |||
865 | return( mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ) ); |
||
866 | } |
||
867 | |||
868 | /* |
||
869 | * Export a point as a TLS ECPoint record (RFC 4492) |
||
870 | * struct { |
||
871 | * opaque point <1..2^8-1>; |
||
872 | * } ECPoint; |
||
873 | */ |
||
874 | int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt, |
||
875 | int format, size_t *olen, |
||
876 | unsigned char *buf, size_t blen ) |
||
877 | { |
||
878 | int ret; |
||
879 | ECP_VALIDATE_RET( grp != NULL ); |
||
880 | ECP_VALIDATE_RET( pt != NULL ); |
||
881 | ECP_VALIDATE_RET( olen != NULL ); |
||
882 | ECP_VALIDATE_RET( buf != NULL ); |
||
883 | ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED || |
||
884 | format == MBEDTLS_ECP_PF_COMPRESSED ); |
||
885 | |||
886 | /* |
||
887 | * buffer length must be at least one, for our length byte |
||
888 | */ |
||
889 | if( blen < 1 ) |
||
890 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
891 | |||
892 | if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format, |
||
893 | olen, buf + 1, blen - 1) ) != 0 ) |
||
894 | return( ret ); |
||
895 | |||
896 | /* |
||
897 | * write length to the first byte and update total length |
||
898 | */ |
||
899 | buf[0] = (unsigned char) *olen; |
||
900 | ++*olen; |
||
901 | |||
902 | return( 0 ); |
||
903 | } |
||
904 | |||
905 | /* |
||
906 | * Set a group from an ECParameters record (RFC 4492) |
||
907 | */ |
||
908 | int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, |
||
909 | const unsigned char **buf, size_t len ) |
||
910 | { |
||
911 | int ret; |
||
912 | mbedtls_ecp_group_id grp_id; |
||
913 | ECP_VALIDATE_RET( grp != NULL ); |
||
914 | ECP_VALIDATE_RET( buf != NULL ); |
||
915 | ECP_VALIDATE_RET( *buf != NULL ); |
||
916 | |||
917 | if( ( ret = mbedtls_ecp_tls_read_group_id( &grp_id, buf, len ) ) != 0 ) |
||
918 | return( ret ); |
||
919 | |||
920 | return( mbedtls_ecp_group_load( grp, grp_id ) ); |
||
921 | } |
||
922 | |||
923 | /* |
||
924 | * Read a group id from an ECParameters record (RFC 4492) and convert it to |
||
925 | * mbedtls_ecp_group_id. |
||
926 | */ |
||
927 | int mbedtls_ecp_tls_read_group_id( mbedtls_ecp_group_id *grp, |
||
928 | const unsigned char **buf, size_t len ) |
||
929 | { |
||
930 | uint16_t tls_id; |
||
931 | const mbedtls_ecp_curve_info *curve_info; |
||
932 | ECP_VALIDATE_RET( grp != NULL ); |
||
933 | ECP_VALIDATE_RET( buf != NULL ); |
||
934 | ECP_VALIDATE_RET( *buf != NULL ); |
||
935 | |||
936 | /* |
||
937 | * We expect at least three bytes (see below) |
||
938 | */ |
||
939 | if( len < 3 ) |
||
940 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
941 | |||
942 | /* |
||
943 | * First byte is curve_type; only named_curve is handled |
||
944 | */ |
||
945 | if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE ) |
||
946 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
947 | |||
948 | /* |
||
949 | * Next two bytes are the namedcurve value |
||
950 | */ |
||
951 | tls_id = *(*buf)++; |
||
952 | tls_id <<= 8; |
||
953 | tls_id |= *(*buf)++; |
||
954 | |||
955 | if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL ) |
||
956 | return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); |
||
957 | |||
958 | *grp = curve_info->grp_id; |
||
959 | |||
960 | return( 0 ); |
||
961 | } |
||
962 | |||
963 | /* |
||
964 | * Write the ECParameters record corresponding to a group (RFC 4492) |
||
965 | */ |
||
966 | int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen, |
||
967 | unsigned char *buf, size_t blen ) |
||
968 | { |
||
969 | const mbedtls_ecp_curve_info *curve_info; |
||
970 | ECP_VALIDATE_RET( grp != NULL ); |
||
971 | ECP_VALIDATE_RET( buf != NULL ); |
||
972 | ECP_VALIDATE_RET( olen != NULL ); |
||
973 | |||
974 | if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL ) |
||
975 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
976 | |||
977 | /* |
||
978 | * We are going to write 3 bytes (see below) |
||
979 | */ |
||
980 | *olen = 3; |
||
981 | if( blen < *olen ) |
||
982 | return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); |
||
983 | |||
984 | /* |
||
985 | * First byte is curve_type, always named_curve |
||
986 | */ |
||
987 | *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE; |
||
988 | |||
989 | /* |
||
990 | * Next two bytes are the namedcurve value |
||
991 | */ |
||
992 | buf[0] = curve_info->tls_id >> 8; |
||
993 | buf[1] = curve_info->tls_id & 0xFF; |
||
994 | |||
995 | return( 0 ); |
||
996 | } |
||
997 | |||
998 | /* |
||
999 | * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi. |
||
1000 | * See the documentation of struct mbedtls_ecp_group. |
||
1001 | * |
||
1002 | * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf. |
||
1003 | */ |
||
1004 | static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp ) |
||
1005 | { |
||
1006 | int ret; |
||
1007 | |||
1008 | if( grp->modp == NULL ) |
||
1009 | return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) ); |
||
1010 | |||
1011 | /* N->s < 0 is a much faster test, which fails only if N is 0 */ |
||
1012 | if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) || |
||
1013 | mbedtls_mpi_bitlen( N ) > 2 * grp->pbits ) |
||
1014 | { |
||
1015 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
1016 | } |
||
1017 | |||
1018 | MBEDTLS_MPI_CHK( grp->modp( N ) ); |
||
1019 | |||
1020 | /* N->s < 0 is a much faster test, which fails only if N is 0 */ |
||
1021 | while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) |
||
1022 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) ); |
||
1023 | |||
1024 | while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 ) |
||
1025 | /* we known P, N and the result are positive */ |
||
1026 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) ); |
||
1027 | |||
1028 | cleanup: |
||
1029 | return( ret ); |
||
1030 | } |
||
1031 | |||
1032 | /* |
||
1033 | * Fast mod-p functions expect their argument to be in the 0..p^2 range. |
||
1034 | * |
||
1035 | * In order to guarantee that, we need to ensure that operands of |
||
1036 | * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will |
||
1037 | * bring the result back to this range. |
||
1038 | * |
||
1039 | * The following macros are shortcuts for doing that. |
||
1040 | */ |
||
1041 | |||
1042 | /* |
||
1043 | * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi |
||
1044 | */ |
||
1045 | #if defined(MBEDTLS_SELF_TEST) |
||
1046 | #define INC_MUL_COUNT mul_count++; |
||
1047 | #else |
||
1048 | #define INC_MUL_COUNT |
||
1049 | #endif |
||
1050 | |||
1051 | #define MOD_MUL( N ) \ |
||
1052 | do \ |
||
1053 | { \ |
||
1054 | MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) ); \ |
||
1055 | INC_MUL_COUNT \ |
||
1056 | } while( 0 ) |
||
1057 | |||
1058 | /* |
||
1059 | * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi |
||
1060 | * N->s < 0 is a very fast test, which fails only if N is 0 |
||
1061 | */ |
||
1062 | #define MOD_SUB( N ) \ |
||
1063 | while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 ) \ |
||
1064 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) ) |
||
1065 | |||
1066 | /* |
||
1067 | * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. |
||
1068 | * We known P, N and the result are positive, so sub_abs is correct, and |
||
1069 | * a bit faster. |
||
1070 | */ |
||
1071 | #define MOD_ADD( N ) \ |
||
1072 | while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 ) \ |
||
1073 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) ) |
||
1074 | |||
1075 | #if defined(ECP_SHORTWEIERSTRASS) |
||
1076 | /* |
||
1077 | * For curves in short Weierstrass form, we do all the internal operations in |
||
1078 | * Jacobian coordinates. |
||
1079 | * |
||
1080 | * For multiplication, we'll use a comb method with coutermeasueres against |
||
1081 | * SPA, hence timing attacks. |
||
1082 | */ |
||
1083 | |||
1084 | /* |
||
1085 | * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) |
||
1086 | * Cost: 1N := 1I + 3M + 1S |
||
1087 | */ |
||
1088 | static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) |
||
1089 | { |
||
1090 | int ret; |
||
1091 | mbedtls_mpi Zi, ZZi; |
||
1092 | |||
1093 | if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ) |
||
1094 | return( 0 ); |
||
1095 | |||
1096 | #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) |
||
1097 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
1098 | return( mbedtls_internal_ecp_normalize_jac( grp, pt ) ); |
||
1099 | #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ |
||
1100 | |||
1101 | mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); |
||
1102 | |||
1103 | /* |
||
1104 | * X = X / Z^2 mod p |
||
1105 | */ |
||
1106 | MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); |
||
1107 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); |
||
1108 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X ); |
||
1109 | |||
1110 | /* |
||
1111 | * Y = Y / Z^3 mod p |
||
1112 | */ |
||
1113 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y ); |
||
1114 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y ); |
||
1115 | |||
1116 | /* |
||
1117 | * Z = 1 |
||
1118 | */ |
||
1119 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); |
||
1120 | |||
1121 | cleanup: |
||
1122 | |||
1123 | mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); |
||
1124 | |||
1125 | return( ret ); |
||
1126 | } |
||
1127 | |||
1128 | /* |
||
1129 | * Normalize jacobian coordinates of an array of (pointers to) points, |
||
1130 | * using Montgomery's trick to perform only one inversion mod P. |
||
1131 | * (See for example Cohen's "A Course in Computational Algebraic Number |
||
1132 | * Theory", Algorithm 10.3.4.) |
||
1133 | * |
||
1134 | * Warning: fails (returning an error) if one of the points is zero! |
||
1135 | * This should never happen, see choice of w in ecp_mul_comb(). |
||
1136 | * |
||
1137 | * Cost: 1N(t) := 1I + (6t - 3)M + 1S |
||
1138 | */ |
||
1139 | static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, |
||
1140 | mbedtls_ecp_point *T[], size_t T_size ) |
||
1141 | { |
||
1142 | int ret; |
||
1143 | size_t i; |
||
1144 | mbedtls_mpi *c, u, Zi, ZZi; |
||
1145 | |||
1146 | if( T_size < 2 ) |
||
1147 | return( ecp_normalize_jac( grp, *T ) ); |
||
1148 | |||
1149 | #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) |
||
1150 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
1151 | return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) ); |
||
1152 | #endif |
||
1153 | |||
1154 | if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL ) |
||
1155 | return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); |
||
1156 | |||
1157 | for( i = 0; i < T_size; i++ ) |
||
1158 | mbedtls_mpi_init( &c[i] ); |
||
1159 | |||
1160 | mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); |
||
1161 | |||
1162 | /* |
||
1163 | * c[i] = Z_0 * ... * Z_i |
||
1164 | */ |
||
1165 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); |
||
1166 | for( i = 1; i < T_size; i++ ) |
||
1167 | { |
||
1168 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); |
||
1169 | MOD_MUL( c[i] ); |
||
1170 | } |
||
1171 | |||
1172 | /* |
||
1173 | * u = 1 / (Z_0 * ... * Z_n) mod P |
||
1174 | */ |
||
1175 | MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) ); |
||
1176 | |||
1177 | for( i = T_size - 1; ; i-- ) |
||
1178 | { |
||
1179 | /* |
||
1180 | * Zi = 1 / Z_i mod p |
||
1181 | * u = 1 / (Z_0 * ... * Z_i) mod P |
||
1182 | */ |
||
1183 | if( i == 0 ) { |
||
1184 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) ); |
||
1185 | } |
||
1186 | else |
||
1187 | { |
||
1188 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); |
||
1189 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); |
||
1190 | } |
||
1191 | |||
1192 | /* |
||
1193 | * proceed as in normalize() |
||
1194 | */ |
||
1195 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); |
||
1196 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); |
||
1197 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); |
||
1198 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); |
||
1199 | |||
1200 | /* |
||
1201 | * Post-precessing: reclaim some memory by shrinking coordinates |
||
1202 | * - not storing Z (always 1) |
||
1203 | * - shrinking other coordinates, but still keeping the same number of |
||
1204 | * limbs as P, as otherwise it will too likely be regrown too fast. |
||
1205 | */ |
||
1206 | MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) ); |
||
1207 | MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) ); |
||
1208 | mbedtls_mpi_free( &T[i]->Z ); |
||
1209 | |||
1210 | if( i == 0 ) |
||
1211 | break; |
||
1212 | } |
||
1213 | |||
1214 | cleanup: |
||
1215 | |||
1216 | mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); |
||
1217 | for( i = 0; i < T_size; i++ ) |
||
1218 | mbedtls_mpi_free( &c[i] ); |
||
1219 | mbedtls_free( c ); |
||
1220 | |||
1221 | return( ret ); |
||
1222 | } |
||
1223 | |||
1224 | /* |
||
1225 | * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. |
||
1226 | * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid |
||
1227 | */ |
||
1228 | static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, |
||
1229 | mbedtls_ecp_point *Q, |
||
1230 | unsigned char inv ) |
||
1231 | { |
||
1232 | int ret; |
||
1233 | unsigned char nonzero; |
||
1234 | mbedtls_mpi mQY; |
||
1235 | |||
1236 | mbedtls_mpi_init( &mQY ); |
||
1237 | |||
1238 | /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ |
||
1239 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) ); |
||
1240 | nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0; |
||
1241 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) ); |
||
1242 | |||
1243 | cleanup: |
||
1244 | mbedtls_mpi_free( &mQY ); |
||
1245 | |||
1246 | return( ret ); |
||
1247 | } |
||
1248 | |||
1249 | /* |
||
1250 | * Point doubling R = 2 P, Jacobian coordinates |
||
1251 | * |
||
1252 | * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . |
||
1253 | * |
||
1254 | * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR |
||
1255 | * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. |
||
1256 | * |
||
1257 | * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. |
||
1258 | * |
||
1259 | * Cost: 1D := 3M + 4S (A == 0) |
||
1260 | * 4M + 4S (A == -3) |
||
1261 | * 3M + 6S + 1a otherwise |
||
1262 | */ |
||
1263 | static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
1264 | const mbedtls_ecp_point *P ) |
||
1265 | { |
||
1266 | int ret; |
||
1267 | mbedtls_mpi M, S, T, U; |
||
1268 | |||
1269 | #if defined(MBEDTLS_SELF_TEST) |
||
1270 | dbl_count++; |
||
1271 | #endif |
||
1272 | |||
1273 | #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) |
||
1274 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
1275 | return( mbedtls_internal_ecp_double_jac( grp, R, P ) ); |
||
1276 | #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ |
||
1277 | |||
1278 | mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); |
||
1279 | |||
1280 | /* Special case for A = -3 */ |
||
1281 | if( grp->A.p == NULL ) |
||
1282 | { |
||
1283 | /* M = 3(X + Z^2)(X - Z^2) */ |
||
1284 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); |
||
1285 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T ); |
||
1286 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U ); |
||
1287 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); |
||
1288 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); |
||
1289 | } |
||
1290 | else |
||
1291 | { |
||
1292 | /* M = 3.X^2 */ |
||
1293 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S ); |
||
1294 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); |
||
1295 | |||
1296 | /* Optimize away for "koblitz" curves with A = 0 */ |
||
1297 | if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 ) |
||
1298 | { |
||
1299 | /* M += A.Z^4 */ |
||
1300 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); |
||
1301 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); |
||
1302 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); |
||
1303 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); |
||
1304 | } |
||
1305 | } |
||
1306 | |||
1307 | /* S = 4.X.Y^2 */ |
||
1308 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T ); |
||
1309 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); |
||
1310 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S ); |
||
1311 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); |
||
1312 | |||
1313 | /* U = 8.Y^4 */ |
||
1314 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); |
||
1315 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); |
||
1316 | |||
1317 | /* T = M^2 - 2.S */ |
||
1318 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); |
||
1319 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); |
||
1320 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); |
||
1321 | |||
1322 | /* S = M(S - T) - U */ |
||
1323 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); |
||
1324 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); |
||
1325 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); |
||
1326 | |||
1327 | /* U = 2.Y.Z */ |
||
1328 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U ); |
||
1329 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); |
||
1330 | |||
1331 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) ); |
||
1332 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) ); |
||
1333 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) ); |
||
1334 | |||
1335 | cleanup: |
||
1336 | mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); |
||
1337 | |||
1338 | return( ret ); |
||
1339 | } |
||
1340 | |||
1341 | /* |
||
1342 | * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) |
||
1343 | * |
||
1344 | * The coordinates of Q must be normalized (= affine), |
||
1345 | * but those of P don't need to. R is not normalized. |
||
1346 | * |
||
1347 | * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. |
||
1348 | * None of these cases can happen as intermediate step in ecp_mul_comb(): |
||
1349 | * - at each step, P, Q and R are multiples of the base point, the factor |
||
1350 | * being less than its order, so none of them is zero; |
||
1351 | * - Q is an odd multiple of the base point, P an even multiple, |
||
1352 | * due to the choice of precomputed points in the modified comb method. |
||
1353 | * So branches for these cases do not leak secret information. |
||
1354 | * |
||
1355 | * We accept Q->Z being unset (saving memory in tables) as meaning 1. |
||
1356 | * |
||
1357 | * Cost: 1A := 8M + 3S |
||
1358 | */ |
||
1359 | static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
1360 | const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) |
||
1361 | { |
||
1362 | int ret; |
||
1363 | mbedtls_mpi T1, T2, T3, T4, X, Y, Z; |
||
1364 | |||
1365 | #if defined(MBEDTLS_SELF_TEST) |
||
1366 | add_count++; |
||
1367 | #endif |
||
1368 | |||
1369 | #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) |
||
1370 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
1371 | return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) ); |
||
1372 | #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ |
||
1373 | |||
1374 | /* |
||
1375 | * Trivial cases: P == 0 or Q == 0 (case 1) |
||
1376 | */ |
||
1377 | if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) |
||
1378 | return( mbedtls_ecp_copy( R, Q ) ); |
||
1379 | |||
1380 | if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 ) |
||
1381 | return( mbedtls_ecp_copy( R, P ) ); |
||
1382 | |||
1383 | /* |
||
1384 | * Make sure Q coordinates are normalized |
||
1385 | */ |
||
1386 | if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 ) |
||
1387 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
1388 | |||
1389 | mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); |
||
1390 | mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); |
||
1391 | |||
1392 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 ); |
||
1393 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); |
||
1394 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); |
||
1395 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); |
||
1396 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); |
||
1397 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); |
||
1398 | |||
1399 | /* Special cases (2) and (3) */ |
||
1400 | if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) |
||
1401 | { |
||
1402 | if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 ) |
||
1403 | { |
||
1404 | ret = ecp_double_jac( grp, R, P ); |
||
1405 | goto cleanup; |
||
1406 | } |
||
1407 | else |
||
1408 | { |
||
1409 | ret = mbedtls_ecp_set_zero( R ); |
||
1410 | goto cleanup; |
||
1411 | } |
||
1412 | } |
||
1413 | |||
1414 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z ); |
||
1415 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); |
||
1416 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); |
||
1417 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); |
||
1418 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); |
||
1419 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); |
||
1420 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); |
||
1421 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); |
||
1422 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); |
||
1423 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); |
||
1424 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); |
||
1425 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); |
||
1426 | |||
1427 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) ); |
||
1428 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) ); |
||
1429 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) ); |
||
1430 | |||
1431 | cleanup: |
||
1432 | |||
1433 | mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 ); |
||
1434 | mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); |
||
1435 | |||
1436 | return( ret ); |
||
1437 | } |
||
1438 | |||
1439 | /* |
||
1440 | * Randomize jacobian coordinates: |
||
1441 | * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l |
||
1442 | * This is sort of the reverse operation of ecp_normalize_jac(). |
||
1443 | * |
||
1444 | * This countermeasure was first suggested in [2]. |
||
1445 | */ |
||
1446 | static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, |
||
1447 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
||
1448 | { |
||
1449 | int ret; |
||
1450 | mbedtls_mpi l, ll; |
||
1451 | size_t p_size; |
||
1452 | int count = 0; |
||
1453 | |||
1454 | #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) |
||
1455 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
1456 | return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) ); |
||
1457 | #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ |
||
1458 | |||
1459 | p_size = ( grp->pbits + 7 ) / 8; |
||
1460 | mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll ); |
||
1461 | |||
1462 | /* Generate l such that 1 < l < p */ |
||
1463 | do |
||
1464 | { |
||
1465 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); |
||
1466 | |||
1467 | while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) |
||
1468 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); |
||
1469 | |||
1470 | if( count++ > 10 ) |
||
1471 | return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); |
||
1472 | } |
||
1473 | while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); |
||
1474 | |||
1475 | /* Z = l * Z */ |
||
1476 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z ); |
||
1477 | |||
1478 | /* X = l^2 * X */ |
||
1479 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); |
||
1480 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X ); |
||
1481 | |||
1482 | /* Y = l^3 * Y */ |
||
1483 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); |
||
1484 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y ); |
||
1485 | |||
1486 | cleanup: |
||
1487 | mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll ); |
||
1488 | |||
1489 | return( ret ); |
||
1490 | } |
||
1491 | |||
1492 | /* |
||
1493 | * Check and define parameters used by the comb method (see below for details) |
||
1494 | */ |
||
1495 | #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 |
||
1496 | #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" |
||
1497 | #endif |
||
1498 | |||
1499 | /* d = ceil( n / w ) */ |
||
1500 | #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2 |
||
1501 | |||
1502 | /* number of precomputed points */ |
||
1503 | #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) ) |
||
1504 | |||
1505 | /* |
||
1506 | * Compute the representation of m that will be used with our comb method. |
||
1507 | * |
||
1508 | * The basic comb method is described in GECC 3.44 for example. We use a |
||
1509 | * modified version that provides resistance to SPA by avoiding zero |
||
1510 | * digits in the representation as in [3]. We modify the method further by |
||
1511 | * requiring that all K_i be odd, which has the small cost that our |
||
1512 | * representation uses one more K_i, due to carries, but saves on the size of |
||
1513 | * the precomputed table. |
||
1514 | * |
||
1515 | * Summary of the comb method and its modifications: |
||
1516 | * |
||
1517 | * - The goal is to compute m*P for some w*d-bit integer m. |
||
1518 | * |
||
1519 | * - The basic comb method splits m into the w-bit integers |
||
1520 | * x[0] .. x[d-1] where x[i] consists of the bits in m whose |
||
1521 | * index has residue i modulo d, and computes m * P as |
||
1522 | * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where |
||
1523 | * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P. |
||
1524 | * |
||
1525 | * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by |
||
1526 | * .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] .., |
||
1527 | * thereby successively converting it into a form where all summands |
||
1528 | * are nonzero, at the cost of negative summands. This is the basic idea of [3]. |
||
1529 | * |
||
1530 | * - More generally, even if x[i+1] != 0, we can first transform the sum as |
||
1531 | * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] .., |
||
1532 | * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]]. |
||
1533 | * Performing and iterating this procedure for those x[i] that are even |
||
1534 | * (keeping track of carry), we can transform the original sum into one of the form |
||
1535 | * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]] |
||
1536 | * with all x'[i] odd. It is therefore only necessary to know S at odd indices, |
||
1537 | * which is why we are only computing half of it in the first place in |
||
1538 | * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb. |
||
1539 | * |
||
1540 | * - For the sake of compactness, only the seven low-order bits of x[i] |
||
1541 | * are used to represent its absolute value (K_i in the paper), and the msb |
||
1542 | * of x[i] encodes the sign (s_i in the paper): it is set if and only if |
||
1543 | * if s_i == -1; |
||
1544 | * |
||
1545 | * Calling conventions: |
||
1546 | * - x is an array of size d + 1 |
||
1547 | * - w is the size, ie number of teeth, of the comb, and must be between |
||
1548 | * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) |
||
1549 | * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d |
||
1550 | * (the result will be incorrect if these assumptions are not satisfied) |
||
1551 | */ |
||
1552 | static void ecp_comb_recode_core( unsigned char x[], size_t d, |
||
1553 | unsigned char w, const mbedtls_mpi *m ) |
||
1554 | { |
||
1555 | size_t i, j; |
||
1556 | unsigned char c, cc, adjust; |
||
1557 | |||
1558 | memset( x, 0, d+1 ); |
||
1559 | |||
1560 | /* First get the classical comb values (except for x_d = 0) */ |
||
1561 | for( i = 0; i < d; i++ ) |
||
1562 | for( j = 0; j < w; j++ ) |
||
1563 | x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j; |
||
1564 | |||
1565 | /* Now make sure x_1 .. x_d are odd */ |
||
1566 | c = 0; |
||
1567 | for( i = 1; i <= d; i++ ) |
||
1568 | { |
||
1569 | /* Add carry and update it */ |
||
1570 | cc = x[i] & c; |
||
1571 | x[i] = x[i] ^ c; |
||
1572 | c = cc; |
||
1573 | |||
1574 | /* Adjust if needed, avoiding branches */ |
||
1575 | adjust = 1 - ( x[i] & 0x01 ); |
||
1576 | c |= x[i] & ( x[i-1] * adjust ); |
||
1577 | x[i] = x[i] ^ ( x[i-1] * adjust ); |
||
1578 | x[i-1] |= adjust << 7; |
||
1579 | } |
||
1580 | } |
||
1581 | |||
1582 | /* |
||
1583 | * Precompute points for the adapted comb method |
||
1584 | * |
||
1585 | * Assumption: T must be able to hold 2^{w - 1} elements. |
||
1586 | * |
||
1587 | * Operation: If i = i_{w-1} ... i_1 is the binary representation of i, |
||
1588 | * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P. |
||
1589 | * |
||
1590 | * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) |
||
1591 | * |
||
1592 | * Note: Even comb values (those where P would be omitted from the |
||
1593 | * sum defining T[i] above) are not needed in our adaption |
||
1594 | * the comb method. See ecp_comb_recode_core(). |
||
1595 | * |
||
1596 | * This function currently works in four steps: |
||
1597 | * (1) [dbl] Computation of intermediate T[i] for 2-power values of i |
||
1598 | * (2) [norm_dbl] Normalization of coordinates of these T[i] |
||
1599 | * (3) [add] Computation of all T[i] |
||
1600 | * (4) [norm_add] Normalization of all T[i] |
||
1601 | * |
||
1602 | * Step 1 can be interrupted but not the others; together with the final |
||
1603 | * coordinate normalization they are the largest steps done at once, depending |
||
1604 | * on the window size. Here are operation counts for P-256: |
||
1605 | * |
||
1606 | * step (2) (3) (4) |
||
1607 | * w = 5 142 165 208 |
||
1608 | * w = 4 136 77 160 |
||
1609 | * w = 3 130 33 136 |
||
1610 | * w = 2 124 11 124 |
||
1611 | * |
||
1612 | * So if ECC operations are blocking for too long even with a low max_ops |
||
1613 | * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order |
||
1614 | * to minimize maximum blocking time. |
||
1615 | */ |
||
1616 | static int ecp_precompute_comb( const mbedtls_ecp_group *grp, |
||
1617 | mbedtls_ecp_point T[], const mbedtls_ecp_point *P, |
||
1618 | unsigned char w, size_t d, |
||
1619 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
1620 | { |
||
1621 | int ret; |
||
1622 | unsigned char i; |
||
1623 | size_t j = 0; |
||
1624 | const unsigned char T_size = 1U << ( w - 1 ); |
||
1625 | mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1]; |
||
1626 | |||
1627 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1628 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1629 | { |
||
1630 | if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) |
||
1631 | goto dbl; |
||
1632 | if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl ) |
||
1633 | goto norm_dbl; |
||
1634 | if( rs_ctx->rsm->state == ecp_rsm_pre_add ) |
||
1635 | goto add; |
||
1636 | if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add ) |
||
1637 | goto norm_add; |
||
1638 | } |
||
1639 | #else |
||
1640 | (void) rs_ctx; |
||
1641 | #endif |
||
1642 | |||
1643 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1644 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1645 | { |
||
1646 | rs_ctx->rsm->state = ecp_rsm_pre_dbl; |
||
1647 | |||
1648 | /* initial state for the loop */ |
||
1649 | rs_ctx->rsm->i = 0; |
||
1650 | } |
||
1651 | |||
1652 | dbl: |
||
1653 | #endif |
||
1654 | /* |
||
1655 | * Set T[0] = P and |
||
1656 | * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) |
||
1657 | */ |
||
1658 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) ); |
||
1659 | |||
1660 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1661 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) |
||
1662 | j = rs_ctx->rsm->i; |
||
1663 | else |
||
1664 | #endif |
||
1665 | j = 0; |
||
1666 | |||
1667 | for( ; j < d * ( w - 1 ); j++ ) |
||
1668 | { |
||
1669 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL ); |
||
1670 | |||
1671 | i = 1U << ( j / d ); |
||
1672 | cur = T + i; |
||
1673 | |||
1674 | if( j % d == 0 ) |
||
1675 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) ); |
||
1676 | |||
1677 | MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) ); |
||
1678 | } |
||
1679 | |||
1680 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1681 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1682 | rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl; |
||
1683 | |||
1684 | norm_dbl: |
||
1685 | #endif |
||
1686 | /* |
||
1687 | * Normalize current elements in T. As T has holes, |
||
1688 | * use an auxiliary array of pointers to elements in T. |
||
1689 | */ |
||
1690 | j = 0; |
||
1691 | for( i = 1; i < T_size; i <<= 1 ) |
||
1692 | TT[j++] = T + i; |
||
1693 | |||
1694 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); |
||
1695 | |||
1696 | MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); |
||
1697 | |||
1698 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1699 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1700 | rs_ctx->rsm->state = ecp_rsm_pre_add; |
||
1701 | |||
1702 | add: |
||
1703 | #endif |
||
1704 | /* |
||
1705 | * Compute the remaining ones using the minimal number of additions |
||
1706 | * Be careful to update T[2^l] only after using it! |
||
1707 | */ |
||
1708 | MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD ); |
||
1709 | |||
1710 | for( i = 1; i < T_size; i <<= 1 ) |
||
1711 | { |
||
1712 | j = i; |
||
1713 | while( j-- ) |
||
1714 | MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); |
||
1715 | } |
||
1716 | |||
1717 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1718 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1719 | rs_ctx->rsm->state = ecp_rsm_pre_norm_add; |
||
1720 | |||
1721 | norm_add: |
||
1722 | #endif |
||
1723 | /* |
||
1724 | * Normalize final elements in T. Even though there are no holes now, we |
||
1725 | * still need the auxiliary array for homogeneity with the previous |
||
1726 | * call. Also, skip T[0] which is already normalised, being a copy of P. |
||
1727 | */ |
||
1728 | for( j = 0; j + 1 < T_size; j++ ) |
||
1729 | TT[j] = T + j + 1; |
||
1730 | |||
1731 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); |
||
1732 | |||
1733 | MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); |
||
1734 | |||
1735 | cleanup: |
||
1736 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1737 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && |
||
1738 | ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) |
||
1739 | { |
||
1740 | if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) |
||
1741 | rs_ctx->rsm->i = j; |
||
1742 | } |
||
1743 | #endif |
||
1744 | |||
1745 | return( ret ); |
||
1746 | } |
||
1747 | |||
1748 | /* |
||
1749 | * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] |
||
1750 | * |
||
1751 | * See ecp_comb_recode_core() for background |
||
1752 | */ |
||
1753 | static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
1754 | const mbedtls_ecp_point T[], unsigned char T_size, |
||
1755 | unsigned char i ) |
||
1756 | { |
||
1757 | int ret; |
||
1758 | unsigned char ii, j; |
||
1759 | |||
1760 | /* Ignore the "sign" bit and scale down */ |
||
1761 | ii = ( i & 0x7Fu ) >> 1; |
||
1762 | |||
1763 | /* Read the whole table to thwart cache-based timing attacks */ |
||
1764 | for( j = 0; j < T_size; j++ ) |
||
1765 | { |
||
1766 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) ); |
||
1767 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) ); |
||
1768 | } |
||
1769 | |||
1770 | /* Safely invert result if i is "negative" */ |
||
1771 | MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); |
||
1772 | |||
1773 | cleanup: |
||
1774 | return( ret ); |
||
1775 | } |
||
1776 | |||
1777 | /* |
||
1778 | * Core multiplication algorithm for the (modified) comb method. |
||
1779 | * This part is actually common with the basic comb method (GECC 3.44) |
||
1780 | * |
||
1781 | * Cost: d A + d D + 1 R |
||
1782 | */ |
||
1783 | static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
1784 | const mbedtls_ecp_point T[], unsigned char T_size, |
||
1785 | const unsigned char x[], size_t d, |
||
1786 | int (*f_rng)(void *, unsigned char *, size_t), |
||
1787 | void *p_rng, |
||
1788 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
1789 | { |
||
1790 | int ret; |
||
1791 | mbedtls_ecp_point Txi; |
||
1792 | size_t i; |
||
1793 | |||
1794 | mbedtls_ecp_point_init( &Txi ); |
||
1795 | |||
1796 | #if !defined(MBEDTLS_ECP_RESTARTABLE) |
||
1797 | (void) rs_ctx; |
||
1798 | #endif |
||
1799 | |||
1800 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1801 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && |
||
1802 | rs_ctx->rsm->state != ecp_rsm_comb_core ) |
||
1803 | { |
||
1804 | rs_ctx->rsm->i = 0; |
||
1805 | rs_ctx->rsm->state = ecp_rsm_comb_core; |
||
1806 | } |
||
1807 | |||
1808 | /* new 'if' instead of nested for the sake of the 'else' branch */ |
||
1809 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) |
||
1810 | { |
||
1811 | /* restore current index (R already pointing to rs_ctx->rsm->R) */ |
||
1812 | i = rs_ctx->rsm->i; |
||
1813 | } |
||
1814 | else |
||
1815 | #endif |
||
1816 | { |
||
1817 | /* Start with a non-zero point and randomize its coordinates */ |
||
1818 | i = d; |
||
1819 | MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) ); |
||
1820 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) ); |
||
1821 | if( f_rng != 0 ) |
||
1822 | MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); |
||
1823 | } |
||
1824 | |||
1825 | while( i != 0 ) |
||
1826 | { |
||
1827 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD ); |
||
1828 | --i; |
||
1829 | |||
1830 | MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) ); |
||
1831 | MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) ); |
||
1832 | MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); |
||
1833 | } |
||
1834 | |||
1835 | cleanup: |
||
1836 | |||
1837 | mbedtls_ecp_point_free( &Txi ); |
||
1838 | |||
1839 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1840 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && |
||
1841 | ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) |
||
1842 | { |
||
1843 | rs_ctx->rsm->i = i; |
||
1844 | /* no need to save R, already pointing to rs_ctx->rsm->R */ |
||
1845 | } |
||
1846 | #endif |
||
1847 | |||
1848 | return( ret ); |
||
1849 | } |
||
1850 | |||
1851 | /* |
||
1852 | * Recode the scalar to get constant-time comb multiplication |
||
1853 | * |
||
1854 | * As the actual scalar recoding needs an odd scalar as a starting point, |
||
1855 | * this wrapper ensures that by replacing m by N - m if necessary, and |
||
1856 | * informs the caller that the result of multiplication will be negated. |
||
1857 | * |
||
1858 | * This works because we only support large prime order for Short Weierstrass |
||
1859 | * curves, so N is always odd hence either m or N - m is. |
||
1860 | * |
||
1861 | * See ecp_comb_recode_core() for background. |
||
1862 | */ |
||
1863 | static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp, |
||
1864 | const mbedtls_mpi *m, |
||
1865 | unsigned char k[COMB_MAX_D + 1], |
||
1866 | size_t d, |
||
1867 | unsigned char w, |
||
1868 | unsigned char *parity_trick ) |
||
1869 | { |
||
1870 | int ret; |
||
1871 | mbedtls_mpi M, mm; |
||
1872 | |||
1873 | mbedtls_mpi_init( &M ); |
||
1874 | mbedtls_mpi_init( &mm ); |
||
1875 | |||
1876 | /* N is always odd (see above), just make extra sure */ |
||
1877 | if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 ) |
||
1878 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
1879 | |||
1880 | /* do we need the parity trick? */ |
||
1881 | *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 ); |
||
1882 | |||
1883 | /* execute parity fix in constant time */ |
||
1884 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) ); |
||
1885 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) ); |
||
1886 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) ); |
||
1887 | |||
1888 | /* actual scalar recoding */ |
||
1889 | ecp_comb_recode_core( k, d, w, &M ); |
||
1890 | |||
1891 | cleanup: |
||
1892 | mbedtls_mpi_free( &mm ); |
||
1893 | mbedtls_mpi_free( &M ); |
||
1894 | |||
1895 | return( ret ); |
||
1896 | } |
||
1897 | |||
1898 | /* |
||
1899 | * Perform comb multiplication (for short Weierstrass curves) |
||
1900 | * once the auxiliary table has been pre-computed. |
||
1901 | * |
||
1902 | * Scalar recoding may use a parity trick that makes us compute -m * P, |
||
1903 | * if that is the case we'll need to recover m * P at the end. |
||
1904 | */ |
||
1905 | static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp, |
||
1906 | mbedtls_ecp_point *R, |
||
1907 | const mbedtls_mpi *m, |
||
1908 | const mbedtls_ecp_point *T, |
||
1909 | unsigned char T_size, |
||
1910 | unsigned char w, |
||
1911 | size_t d, |
||
1912 | int (*f_rng)(void *, unsigned char *, size_t), |
||
1913 | void *p_rng, |
||
1914 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
1915 | { |
||
1916 | int ret; |
||
1917 | unsigned char parity_trick; |
||
1918 | unsigned char k[COMB_MAX_D + 1]; |
||
1919 | mbedtls_ecp_point *RR = R; |
||
1920 | |||
1921 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1922 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1923 | { |
||
1924 | RR = &rs_ctx->rsm->R; |
||
1925 | |||
1926 | if( rs_ctx->rsm->state == ecp_rsm_final_norm ) |
||
1927 | goto final_norm; |
||
1928 | } |
||
1929 | #endif |
||
1930 | |||
1931 | MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w, |
||
1932 | &parity_trick ) ); |
||
1933 | MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d, |
||
1934 | f_rng, p_rng, rs_ctx ) ); |
||
1935 | MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) ); |
||
1936 | |||
1937 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1938 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1939 | rs_ctx->rsm->state = ecp_rsm_final_norm; |
||
1940 | |||
1941 | final_norm: |
||
1942 | #endif |
||
1943 | /* |
||
1944 | * Knowledge of the jacobian coordinates may leak the last few bits of the |
||
1945 | * scalar [1], and since our MPI implementation isn't constant-flow, |
||
1946 | * inversion (used for coordinate normalization) may leak the full value |
||
1947 | * of its input via side-channels [2]. |
||
1948 | * |
||
1949 | * [1] https://eprint.iacr.org/2003/191 |
||
1950 | * [2] https://eprint.iacr.org/2020/055 |
||
1951 | * |
||
1952 | * Avoid the leak by randomizing coordinates before we normalize them. |
||
1953 | */ |
||
1954 | if( f_rng != 0 ) |
||
1955 | MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, RR, f_rng, p_rng ) ); |
||
1956 | |||
1957 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); |
||
1958 | MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) ); |
||
1959 | |||
1960 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
1961 | if( rs_ctx != NULL && rs_ctx->rsm != NULL ) |
||
1962 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) ); |
||
1963 | #endif |
||
1964 | |||
1965 | cleanup: |
||
1966 | return( ret ); |
||
1967 | } |
||
1968 | |||
1969 | /* |
||
1970 | * Pick window size based on curve size and whether we optimize for base point |
||
1971 | */ |
||
1972 | static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp, |
||
1973 | unsigned char p_eq_g ) |
||
1974 | { |
||
1975 | unsigned char w; |
||
1976 | |||
1977 | /* |
||
1978 | * Minimize the number of multiplications, that is minimize |
||
1979 | * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) |
||
1980 | * (see costs of the various parts, with 1S = 1M) |
||
1981 | */ |
||
1982 | w = grp->nbits >= 384 ? 5 : 4; |
||
1983 | |||
1984 | /* |
||
1985 | * If P == G, pre-compute a bit more, since this may be re-used later. |
||
1986 | * Just adding one avoids upping the cost of the first mul too much, |
||
1987 | * and the memory cost too. |
||
1988 | */ |
||
1989 | if( p_eq_g ) |
||
1990 | w++; |
||
1991 | |||
1992 | /* |
||
1993 | * Make sure w is within bounds. |
||
1994 | * (The last test is useful only for very small curves in the test suite.) |
||
1995 | */ |
||
1996 | if( w > MBEDTLS_ECP_WINDOW_SIZE ) |
||
1997 | w = MBEDTLS_ECP_WINDOW_SIZE; |
||
1998 | if( w >= grp->nbits ) |
||
1999 | w = 2; |
||
2000 | |||
2001 | return( w ); |
||
2002 | } |
||
2003 | |||
2004 | /* |
||
2005 | * Multiplication using the comb method - for curves in short Weierstrass form |
||
2006 | * |
||
2007 | * This function is mainly responsible for administrative work: |
||
2008 | * - managing the restart context if enabled |
||
2009 | * - managing the table of precomputed points (passed between the below two |
||
2010 | * functions): allocation, computation, ownership tranfer, freeing. |
||
2011 | * |
||
2012 | * It delegates the actual arithmetic work to: |
||
2013 | * ecp_precompute_comb() and ecp_mul_comb_with_precomp() |
||
2014 | * |
||
2015 | * See comments on ecp_comb_recode_core() regarding the computation strategy. |
||
2016 | */ |
||
2017 | static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2018 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2019 | int (*f_rng)(void *, unsigned char *, size_t), |
||
2020 | void *p_rng, |
||
2021 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
2022 | { |
||
2023 | int ret; |
||
2024 | unsigned char w, p_eq_g, i; |
||
2025 | size_t d; |
||
2026 | unsigned char T_size, T_ok; |
||
2027 | mbedtls_ecp_point *T; |
||
2028 | |||
2029 | ECP_RS_ENTER( rsm ); |
||
2030 | |||
2031 | /* Is P the base point ? */ |
||
2032 | #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 |
||
2033 | p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 && |
||
2034 | mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 ); |
||
2035 | #else |
||
2036 | p_eq_g = 0; |
||
2037 | #endif |
||
2038 | |||
2039 | /* Pick window size and deduce related sizes */ |
||
2040 | w = ecp_pick_window_size( grp, p_eq_g ); |
||
2041 | T_size = 1U << ( w - 1 ); |
||
2042 | d = ( grp->nbits + w - 1 ) / w; |
||
2043 | |||
2044 | /* Pre-computed table: do we have it already for the base point? */ |
||
2045 | if( p_eq_g && grp->T != NULL ) |
||
2046 | { |
||
2047 | /* second pointer to the same table, will be deleted on exit */ |
||
2048 | T = grp->T; |
||
2049 | T_ok = 1; |
||
2050 | } |
||
2051 | else |
||
2052 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2053 | /* Pre-computed table: do we have one in progress? complete? */ |
||
2054 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL ) |
||
2055 | { |
||
2056 | /* transfer ownership of T from rsm to local function */ |
||
2057 | T = rs_ctx->rsm->T; |
||
2058 | rs_ctx->rsm->T = NULL; |
||
2059 | rs_ctx->rsm->T_size = 0; |
||
2060 | |||
2061 | /* This effectively jumps to the call to mul_comb_after_precomp() */ |
||
2062 | T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core; |
||
2063 | } |
||
2064 | else |
||
2065 | #endif |
||
2066 | /* Allocate table if we didn't have any */ |
||
2067 | { |
||
2068 | T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) ); |
||
2069 | if( T == NULL ) |
||
2070 | { |
||
2071 | ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; |
||
2072 | goto cleanup; |
||
2073 | } |
||
2074 | |||
2075 | for( i = 0; i < T_size; i++ ) |
||
2076 | mbedtls_ecp_point_init( &T[i] ); |
||
2077 | |||
2078 | T_ok = 0; |
||
2079 | } |
||
2080 | |||
2081 | /* Compute table (or finish computing it) if not done already */ |
||
2082 | if( !T_ok ) |
||
2083 | { |
||
2084 | MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) ); |
||
2085 | |||
2086 | if( p_eq_g ) |
||
2087 | { |
||
2088 | /* almost transfer ownership of T to the group, but keep a copy of |
||
2089 | * the pointer to use for calling the next function more easily */ |
||
2090 | grp->T = T; |
||
2091 | grp->T_size = T_size; |
||
2092 | } |
||
2093 | } |
||
2094 | |||
2095 | /* Actual comb multiplication using precomputed points */ |
||
2096 | MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m, |
||
2097 | T, T_size, w, d, |
||
2098 | f_rng, p_rng, rs_ctx ) ); |
||
2099 | |||
2100 | cleanup: |
||
2101 | |||
2102 | /* does T belong to the group? */ |
||
2103 | if( T == grp->T ) |
||
2104 | T = NULL; |
||
2105 | |||
2106 | /* does T belong to the restart context? */ |
||
2107 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2108 | if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL ) |
||
2109 | { |
||
2110 | /* transfer ownership of T from local function to rsm */ |
||
2111 | rs_ctx->rsm->T_size = T_size; |
||
2112 | rs_ctx->rsm->T = T; |
||
2113 | T = NULL; |
||
2114 | } |
||
2115 | #endif |
||
2116 | |||
2117 | /* did T belong to us? then let's destroy it! */ |
||
2118 | if( T != NULL ) |
||
2119 | { |
||
2120 | for( i = 0; i < T_size; i++ ) |
||
2121 | mbedtls_ecp_point_free( &T[i] ); |
||
2122 | mbedtls_free( T ); |
||
2123 | } |
||
2124 | |||
2125 | /* don't free R while in progress in case R == P */ |
||
2126 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2127 | if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) |
||
2128 | #endif |
||
2129 | /* prevent caller from using invalid value */ |
||
2130 | if( ret != 0 ) |
||
2131 | mbedtls_ecp_point_free( R ); |
||
2132 | |||
2133 | ECP_RS_LEAVE( rsm ); |
||
2134 | |||
2135 | return( ret ); |
||
2136 | } |
||
2137 | |||
2138 | #endif /* ECP_SHORTWEIERSTRASS */ |
||
2139 | |||
2140 | #if defined(ECP_MONTGOMERY) |
||
2141 | /* |
||
2142 | * For Montgomery curves, we do all the internal arithmetic in projective |
||
2143 | * coordinates. Import/export of points uses only the x coordinates, which is |
||
2144 | * internaly represented as X / Z. |
||
2145 | * |
||
2146 | * For scalar multiplication, we'll use a Montgomery ladder. |
||
2147 | */ |
||
2148 | |||
2149 | /* |
||
2150 | * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 |
||
2151 | * Cost: 1M + 1I |
||
2152 | */ |
||
2153 | static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) |
||
2154 | { |
||
2155 | int ret; |
||
2156 | |||
2157 | #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) |
||
2158 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
2159 | return( mbedtls_internal_ecp_normalize_mxz( grp, P ) ); |
||
2160 | #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ |
||
2161 | |||
2162 | MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); |
||
2163 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); |
||
2164 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); |
||
2165 | |||
2166 | cleanup: |
||
2167 | return( ret ); |
||
2168 | } |
||
2169 | |||
2170 | /* |
||
2171 | * Randomize projective x/z coordinates: |
||
2172 | * (X, Z) -> (l X, l Z) for random l |
||
2173 | * This is sort of the reverse operation of ecp_normalize_mxz(). |
||
2174 | * |
||
2175 | * This countermeasure was first suggested in [2]. |
||
2176 | * Cost: 2M |
||
2177 | */ |
||
2178 | static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, |
||
2179 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
||
2180 | { |
||
2181 | int ret; |
||
2182 | mbedtls_mpi l; |
||
2183 | size_t p_size; |
||
2184 | int count = 0; |
||
2185 | |||
2186 | #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) |
||
2187 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
2188 | return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ); |
||
2189 | #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ |
||
2190 | |||
2191 | p_size = ( grp->pbits + 7 ) / 8; |
||
2192 | mbedtls_mpi_init( &l ); |
||
2193 | |||
2194 | /* Generate l such that 1 < l < p */ |
||
2195 | do |
||
2196 | { |
||
2197 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); |
||
2198 | |||
2199 | while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) |
||
2200 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); |
||
2201 | |||
2202 | if( count++ > 10 ) |
||
2203 | return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); |
||
2204 | } |
||
2205 | while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); |
||
2206 | |||
2207 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X ); |
||
2208 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z ); |
||
2209 | |||
2210 | cleanup: |
||
2211 | mbedtls_mpi_free( &l ); |
||
2212 | |||
2213 | return( ret ); |
||
2214 | } |
||
2215 | |||
2216 | /* |
||
2217 | * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), |
||
2218 | * for Montgomery curves in x/z coordinates. |
||
2219 | * |
||
2220 | * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 |
||
2221 | * with |
||
2222 | * d = X1 |
||
2223 | * P = (X2, Z2) |
||
2224 | * Q = (X3, Z3) |
||
2225 | * R = (X4, Z4) |
||
2226 | * S = (X5, Z5) |
||
2227 | * and eliminating temporary variables tO, ..., t4. |
||
2228 | * |
||
2229 | * Cost: 5M + 4S |
||
2230 | */ |
||
2231 | static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, |
||
2232 | mbedtls_ecp_point *R, mbedtls_ecp_point *S, |
||
2233 | const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, |
||
2234 | const mbedtls_mpi *d ) |
||
2235 | { |
||
2236 | int ret; |
||
2237 | mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; |
||
2238 | |||
2239 | #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) |
||
2240 | if( mbedtls_internal_ecp_grp_capable( grp ) ) |
||
2241 | return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) ); |
||
2242 | #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ |
||
2243 | |||
2244 | mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); |
||
2245 | mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); |
||
2246 | mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); |
||
2247 | |||
2248 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); |
||
2249 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); |
||
2250 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); |
||
2251 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); |
||
2252 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); |
||
2253 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); |
||
2254 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); |
||
2255 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); |
||
2256 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); |
||
2257 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); |
||
2258 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); |
||
2259 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); |
||
2260 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); |
||
2261 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); |
||
2262 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); |
||
2263 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); |
||
2264 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); |
||
2265 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); |
||
2266 | |||
2267 | cleanup: |
||
2268 | mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); |
||
2269 | mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); |
||
2270 | mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); |
||
2271 | |||
2272 | return( ret ); |
||
2273 | } |
||
2274 | |||
2275 | /* |
||
2276 | * Multiplication with Montgomery ladder in x/z coordinates, |
||
2277 | * for curves in Montgomery form |
||
2278 | */ |
||
2279 | static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2280 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2281 | int (*f_rng)(void *, unsigned char *, size_t), |
||
2282 | void *p_rng ) |
||
2283 | { |
||
2284 | int ret; |
||
2285 | size_t i; |
||
2286 | unsigned char b; |
||
2287 | mbedtls_ecp_point RP; |
||
2288 | mbedtls_mpi PX; |
||
2289 | |||
2290 | mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); |
||
2291 | |||
2292 | /* Save PX and read from P before writing to R, in case P == R */ |
||
2293 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); |
||
2294 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); |
||
2295 | |||
2296 | /* Set R to zero in modified x/z coordinates */ |
||
2297 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) ); |
||
2298 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); |
||
2299 | mbedtls_mpi_free( &R->Y ); |
||
2300 | |||
2301 | /* RP.X might be sligtly larger than P, so reduce it */ |
||
2302 | MOD_ADD( RP.X ); |
||
2303 | |||
2304 | /* Randomize coordinates of the starting point */ |
||
2305 | if( f_rng != NULL ) |
||
2306 | MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); |
||
2307 | |||
2308 | /* Loop invariant: R = result so far, RP = R + P */ |
||
2309 | i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ |
||
2310 | while( i-- > 0 ) |
||
2311 | { |
||
2312 | b = mbedtls_mpi_get_bit( m, i ); |
||
2313 | /* |
||
2314 | * if (b) R = 2R + P else R = 2R, |
||
2315 | * which is: |
||
2316 | * if (b) double_add( RP, R, RP, R ) |
||
2317 | * else double_add( R, RP, R, RP ) |
||
2318 | * but using safe conditional swaps to avoid leaks |
||
2319 | */ |
||
2320 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); |
||
2321 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); |
||
2322 | MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); |
||
2323 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); |
||
2324 | MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); |
||
2325 | } |
||
2326 | |||
2327 | /* |
||
2328 | * Knowledge of the projective coordinates may leak the last few bits of the |
||
2329 | * scalar [1], and since our MPI implementation isn't constant-flow, |
||
2330 | * inversion (used for coordinate normalization) may leak the full value |
||
2331 | * of its input via side-channels [2]. |
||
2332 | * |
||
2333 | * [1] https://eprint.iacr.org/2003/191 |
||
2334 | * [2] https://eprint.iacr.org/2020/055 |
||
2335 | * |
||
2336 | * Avoid the leak by randomizing coordinates before we normalize them. |
||
2337 | */ |
||
2338 | if( f_rng != NULL ) |
||
2339 | MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, R, f_rng, p_rng ) ); |
||
2340 | |||
2341 | MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); |
||
2342 | |||
2343 | cleanup: |
||
2344 | mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); |
||
2345 | |||
2346 | return( ret ); |
||
2347 | } |
||
2348 | |||
2349 | #endif /* ECP_MONTGOMERY */ |
||
2350 | |||
2351 | /* |
||
2352 | * Restartable multiplication R = m * P |
||
2353 | */ |
||
2354 | int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2355 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2356 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng, |
||
2357 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
2358 | { |
||
2359 | int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; |
||
2360 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2361 | char is_grp_capable = 0; |
||
2362 | #endif |
||
2363 | ECP_VALIDATE_RET( grp != NULL ); |
||
2364 | ECP_VALIDATE_RET( R != NULL ); |
||
2365 | ECP_VALIDATE_RET( m != NULL ); |
||
2366 | ECP_VALIDATE_RET( P != NULL ); |
||
2367 | |||
2368 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2369 | /* reset ops count for this call if top-level */ |
||
2370 | if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) |
||
2371 | rs_ctx->ops_done = 0; |
||
2372 | #endif |
||
2373 | |||
2374 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2375 | if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) |
||
2376 | MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); |
||
2377 | #endif /* MBEDTLS_ECP_INTERNAL_ALT */ |
||
2378 | |||
2379 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2380 | /* skip argument check when restarting */ |
||
2381 | if( rs_ctx == NULL || rs_ctx->rsm == NULL ) |
||
2382 | #endif |
||
2383 | { |
||
2384 | /* check_privkey is free */ |
||
2385 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK ); |
||
2386 | |||
2387 | /* Common sanity checks */ |
||
2388 | MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) ); |
||
2389 | MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) ); |
||
2390 | } |
||
2391 | |||
2392 | ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; |
||
2393 | #if defined(ECP_MONTGOMERY) |
||
2394 | if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) |
||
2395 | MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) ); |
||
2396 | #endif |
||
2397 | #if defined(ECP_SHORTWEIERSTRASS) |
||
2398 | if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) |
||
2399 | MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) ); |
||
2400 | #endif |
||
2401 | |||
2402 | cleanup: |
||
2403 | |||
2404 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2405 | if( is_grp_capable ) |
||
2406 | mbedtls_internal_ecp_free( grp ); |
||
2407 | #endif /* MBEDTLS_ECP_INTERNAL_ALT */ |
||
2408 | |||
2409 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2410 | if( rs_ctx != NULL ) |
||
2411 | rs_ctx->depth--; |
||
2412 | #endif |
||
2413 | |||
2414 | return( ret ); |
||
2415 | } |
||
2416 | |||
2417 | /* |
||
2418 | * Multiplication R = m * P |
||
2419 | */ |
||
2420 | int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2421 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2422 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
||
2423 | { |
||
2424 | ECP_VALIDATE_RET( grp != NULL ); |
||
2425 | ECP_VALIDATE_RET( R != NULL ); |
||
2426 | ECP_VALIDATE_RET( m != NULL ); |
||
2427 | ECP_VALIDATE_RET( P != NULL ); |
||
2428 | return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) ); |
||
2429 | } |
||
2430 | |||
2431 | #if defined(ECP_SHORTWEIERSTRASS) |
||
2432 | /* |
||
2433 | * Check that an affine point is valid as a public key, |
||
2434 | * short weierstrass curves (SEC1 3.2.3.1) |
||
2435 | */ |
||
2436 | static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) |
||
2437 | { |
||
2438 | int ret; |
||
2439 | mbedtls_mpi YY, RHS; |
||
2440 | |||
2441 | /* pt coordinates must be normalized for our checks */ |
||
2442 | if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 || |
||
2443 | mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 || |
||
2444 | mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || |
||
2445 | mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) |
||
2446 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2447 | |||
2448 | mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); |
||
2449 | |||
2450 | /* |
||
2451 | * YY = Y^2 |
||
2452 | * RHS = X (X^2 + A) + B = X^3 + A X + B |
||
2453 | */ |
||
2454 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); |
||
2455 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); |
||
2456 | |||
2457 | /* Special case for A = -3 */ |
||
2458 | if( grp->A.p == NULL ) |
||
2459 | { |
||
2460 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); |
||
2461 | } |
||
2462 | else |
||
2463 | { |
||
2464 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); |
||
2465 | } |
||
2466 | |||
2467 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); |
||
2468 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); |
||
2469 | |||
2470 | if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) |
||
2471 | ret = MBEDTLS_ERR_ECP_INVALID_KEY; |
||
2472 | |||
2473 | cleanup: |
||
2474 | |||
2475 | mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); |
||
2476 | |||
2477 | return( ret ); |
||
2478 | } |
||
2479 | #endif /* ECP_SHORTWEIERSTRASS */ |
||
2480 | |||
2481 | /* |
||
2482 | * R = m * P with shortcuts for m == 1 and m == -1 |
||
2483 | * NOT constant-time - ONLY for short Weierstrass! |
||
2484 | */ |
||
2485 | static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, |
||
2486 | mbedtls_ecp_point *R, |
||
2487 | const mbedtls_mpi *m, |
||
2488 | const mbedtls_ecp_point *P, |
||
2489 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
2490 | { |
||
2491 | int ret; |
||
2492 | |||
2493 | if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) |
||
2494 | { |
||
2495 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); |
||
2496 | } |
||
2497 | else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) |
||
2498 | { |
||
2499 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); |
||
2500 | if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 ) |
||
2501 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) ); |
||
2502 | } |
||
2503 | else |
||
2504 | { |
||
2505 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P, |
||
2506 | NULL, NULL, rs_ctx ) ); |
||
2507 | } |
||
2508 | |||
2509 | cleanup: |
||
2510 | return( ret ); |
||
2511 | } |
||
2512 | |||
2513 | /* |
||
2514 | * Restartable linear combination |
||
2515 | * NOT constant-time |
||
2516 | */ |
||
2517 | int mbedtls_ecp_muladd_restartable( |
||
2518 | mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2519 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2520 | const mbedtls_mpi *n, const mbedtls_ecp_point *Q, |
||
2521 | mbedtls_ecp_restart_ctx *rs_ctx ) |
||
2522 | { |
||
2523 | int ret; |
||
2524 | mbedtls_ecp_point mP; |
||
2525 | mbedtls_ecp_point *pmP = &mP; |
||
2526 | mbedtls_ecp_point *pR = R; |
||
2527 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2528 | char is_grp_capable = 0; |
||
2529 | #endif |
||
2530 | ECP_VALIDATE_RET( grp != NULL ); |
||
2531 | ECP_VALIDATE_RET( R != NULL ); |
||
2532 | ECP_VALIDATE_RET( m != NULL ); |
||
2533 | ECP_VALIDATE_RET( P != NULL ); |
||
2534 | ECP_VALIDATE_RET( n != NULL ); |
||
2535 | ECP_VALIDATE_RET( Q != NULL ); |
||
2536 | |||
2537 | if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) |
||
2538 | return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); |
||
2539 | |||
2540 | mbedtls_ecp_point_init( &mP ); |
||
2541 | |||
2542 | ECP_RS_ENTER( ma ); |
||
2543 | |||
2544 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2545 | if( rs_ctx != NULL && rs_ctx->ma != NULL ) |
||
2546 | { |
||
2547 | /* redirect intermediate results to restart context */ |
||
2548 | pmP = &rs_ctx->ma->mP; |
||
2549 | pR = &rs_ctx->ma->R; |
||
2550 | |||
2551 | /* jump to next operation */ |
||
2552 | if( rs_ctx->ma->state == ecp_rsma_mul2 ) |
||
2553 | goto mul2; |
||
2554 | if( rs_ctx->ma->state == ecp_rsma_add ) |
||
2555 | goto add; |
||
2556 | if( rs_ctx->ma->state == ecp_rsma_norm ) |
||
2557 | goto norm; |
||
2558 | } |
||
2559 | #endif /* MBEDTLS_ECP_RESTARTABLE */ |
||
2560 | |||
2561 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) ); |
||
2562 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2563 | if( rs_ctx != NULL && rs_ctx->ma != NULL ) |
||
2564 | rs_ctx->ma->state = ecp_rsma_mul2; |
||
2565 | |||
2566 | mul2: |
||
2567 | #endif |
||
2568 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR, n, Q, rs_ctx ) ); |
||
2569 | |||
2570 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2571 | if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) |
||
2572 | MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); |
||
2573 | #endif /* MBEDTLS_ECP_INTERNAL_ALT */ |
||
2574 | |||
2575 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2576 | if( rs_ctx != NULL && rs_ctx->ma != NULL ) |
||
2577 | rs_ctx->ma->state = ecp_rsma_add; |
||
2578 | |||
2579 | add: |
||
2580 | #endif |
||
2581 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD ); |
||
2582 | MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) ); |
||
2583 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2584 | if( rs_ctx != NULL && rs_ctx->ma != NULL ) |
||
2585 | rs_ctx->ma->state = ecp_rsma_norm; |
||
2586 | |||
2587 | norm: |
||
2588 | #endif |
||
2589 | MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); |
||
2590 | MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) ); |
||
2591 | |||
2592 | #if defined(MBEDTLS_ECP_RESTARTABLE) |
||
2593 | if( rs_ctx != NULL && rs_ctx->ma != NULL ) |
||
2594 | MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) ); |
||
2595 | #endif |
||
2596 | |||
2597 | cleanup: |
||
2598 | #if defined(MBEDTLS_ECP_INTERNAL_ALT) |
||
2599 | if( is_grp_capable ) |
||
2600 | mbedtls_internal_ecp_free( grp ); |
||
2601 | #endif /* MBEDTLS_ECP_INTERNAL_ALT */ |
||
2602 | |||
2603 | mbedtls_ecp_point_free( &mP ); |
||
2604 | |||
2605 | ECP_RS_LEAVE( ma ); |
||
2606 | |||
2607 | return( ret ); |
||
2608 | } |
||
2609 | |||
2610 | /* |
||
2611 | * Linear combination |
||
2612 | * NOT constant-time |
||
2613 | */ |
||
2614 | int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, |
||
2615 | const mbedtls_mpi *m, const mbedtls_ecp_point *P, |
||
2616 | const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) |
||
2617 | { |
||
2618 | ECP_VALIDATE_RET( grp != NULL ); |
||
2619 | ECP_VALIDATE_RET( R != NULL ); |
||
2620 | ECP_VALIDATE_RET( m != NULL ); |
||
2621 | ECP_VALIDATE_RET( P != NULL ); |
||
2622 | ECP_VALIDATE_RET( n != NULL ); |
||
2623 | ECP_VALIDATE_RET( Q != NULL ); |
||
2624 | return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) ); |
||
2625 | } |
||
2626 | |||
2627 | #if defined(ECP_MONTGOMERY) |
||
2628 | /* |
||
2629 | * Check validity of a public key for Montgomery curves with x-only schemes |
||
2630 | */ |
||
2631 | static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) |
||
2632 | { |
||
2633 | /* [Curve25519 p. 5] Just check X is the correct number of bytes */ |
||
2634 | /* Allow any public value, if it's too big then we'll just reduce it mod p |
||
2635 | * (RFC 7748 sec. 5 para. 3). */ |
||
2636 | if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) |
||
2637 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2638 | |||
2639 | return( 0 ); |
||
2640 | } |
||
2641 | #endif /* ECP_MONTGOMERY */ |
||
2642 | |||
2643 | /* |
||
2644 | * Check that a point is valid as a public key |
||
2645 | */ |
||
2646 | int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, |
||
2647 | const mbedtls_ecp_point *pt ) |
||
2648 | { |
||
2649 | ECP_VALIDATE_RET( grp != NULL ); |
||
2650 | ECP_VALIDATE_RET( pt != NULL ); |
||
2651 | |||
2652 | /* Must use affine coordinates */ |
||
2653 | if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) |
||
2654 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2655 | |||
2656 | #if defined(ECP_MONTGOMERY) |
||
2657 | if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) |
||
2658 | return( ecp_check_pubkey_mx( grp, pt ) ); |
||
2659 | #endif |
||
2660 | #if defined(ECP_SHORTWEIERSTRASS) |
||
2661 | if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) |
||
2662 | return( ecp_check_pubkey_sw( grp, pt ) ); |
||
2663 | #endif |
||
2664 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
2665 | } |
||
2666 | |||
2667 | /* |
||
2668 | * Check that an mbedtls_mpi is valid as a private key |
||
2669 | */ |
||
2670 | int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, |
||
2671 | const mbedtls_mpi *d ) |
||
2672 | { |
||
2673 | ECP_VALIDATE_RET( grp != NULL ); |
||
2674 | ECP_VALIDATE_RET( d != NULL ); |
||
2675 | |||
2676 | #if defined(ECP_MONTGOMERY) |
||
2677 | if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) |
||
2678 | { |
||
2679 | /* see RFC 7748 sec. 5 para. 5 */ |
||
2680 | if( mbedtls_mpi_get_bit( d, 0 ) != 0 || |
||
2681 | mbedtls_mpi_get_bit( d, 1 ) != 0 || |
||
2682 | mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ |
||
2683 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2684 | |||
2685 | /* see [Curve25519] page 5 */ |
||
2686 | if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 ) |
||
2687 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2688 | |||
2689 | return( 0 ); |
||
2690 | } |
||
2691 | #endif /* ECP_MONTGOMERY */ |
||
2692 | #if defined(ECP_SHORTWEIERSTRASS) |
||
2693 | if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) |
||
2694 | { |
||
2695 | /* see SEC1 3.2 */ |
||
2696 | if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || |
||
2697 | mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) |
||
2698 | return( MBEDTLS_ERR_ECP_INVALID_KEY ); |
||
2699 | else |
||
2700 | return( 0 ); |
||
2701 | } |
||
2702 | #endif /* ECP_SHORTWEIERSTRASS */ |
||
2703 | |||
2704 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
2705 | } |
||
2706 | |||
2707 | /* |
||
2708 | * Generate a private key |
||
2709 | */ |
||
2710 | int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, |
||
2711 | mbedtls_mpi *d, |
||
2712 | int (*f_rng)(void *, unsigned char *, size_t), |
||
2713 | void *p_rng ) |
||
2714 | { |
||
2715 | int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; |
||
2716 | size_t n_size; |
||
2717 | |||
2718 | ECP_VALIDATE_RET( grp != NULL ); |
||
2719 | ECP_VALIDATE_RET( d != NULL ); |
||
2720 | ECP_VALIDATE_RET( f_rng != NULL ); |
||
2721 | |||
2722 | n_size = ( grp->nbits + 7 ) / 8; |
||
2723 | |||
2724 | #if defined(ECP_MONTGOMERY) |
||
2725 | if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) |
||
2726 | { |
||
2727 | /* [M225] page 5 */ |
||
2728 | size_t b; |
||
2729 | |||
2730 | do { |
||
2731 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); |
||
2732 | } while( mbedtls_mpi_bitlen( d ) == 0); |
||
2733 | |||
2734 | /* Make sure the most significant bit is nbits */ |
||
2735 | b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */ |
||
2736 | if( b > grp->nbits ) |
||
2737 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) ); |
||
2738 | else |
||
2739 | MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) ); |
||
2740 | |||
2741 | /* Make sure the last two bits are unset for Curve448, three bits for |
||
2742 | Curve25519 */ |
||
2743 | MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); |
||
2744 | MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); |
||
2745 | if( grp->nbits == 254 ) |
||
2746 | { |
||
2747 | MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); |
||
2748 | } |
||
2749 | } |
||
2750 | #endif /* ECP_MONTGOMERY */ |
||
2751 | |||
2752 | #if defined(ECP_SHORTWEIERSTRASS) |
||
2753 | if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) |
||
2754 | { |
||
2755 | /* SEC1 3.2.1: Generate d such that 1 <= n < N */ |
||
2756 | int count = 0; |
||
2757 | unsigned cmp = 0; |
||
2758 | |||
2759 | /* |
||
2760 | * Match the procedure given in RFC 6979 (deterministic ECDSA): |
||
2761 | * - use the same byte ordering; |
||
2762 | * - keep the leftmost nbits bits of the generated octet string; |
||
2763 | * - try until result is in the desired range. |
||
2764 | * This also avoids any biais, which is especially important for ECDSA. |
||
2765 | */ |
||
2766 | do |
||
2767 | { |
||
2768 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); |
||
2769 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) ); |
||
2770 | |||
2771 | /* |
||
2772 | * Each try has at worst a probability 1/2 of failing (the msb has |
||
2773 | * a probability 1/2 of being 0, and then the result will be < N), |
||
2774 | * so after 30 tries failure probability is a most 2**(-30). |
||
2775 | * |
||
2776 | * For most curves, 1 try is enough with overwhelming probability, |
||
2777 | * since N starts with a lot of 1s in binary, but some curves |
||
2778 | * such as secp224k1 are actually very close to the worst case. |
||
2779 | */ |
||
2780 | if( ++count > 30 ) |
||
2781 | return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); |
||
2782 | |||
2783 | ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp ); |
||
2784 | if( ret != 0 ) |
||
2785 | { |
||
2786 | goto cleanup; |
||
2787 | } |
||
2788 | } |
||
2789 | while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 ); |
||
2790 | } |
||
2791 | #endif /* ECP_SHORTWEIERSTRASS */ |
||
2792 | |||
2793 | cleanup: |
||
2794 | return( ret ); |
||
2795 | } |
||
2796 | |||
2797 | /* |
||
2798 | * Generate a keypair with configurable base point |
||
2799 | */ |
||
2800 | int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, |
||
2801 | const mbedtls_ecp_point *G, |
||
2802 | mbedtls_mpi *d, mbedtls_ecp_point *Q, |
||
2803 | int (*f_rng)(void *, unsigned char *, size_t), |
||
2804 | void *p_rng ) |
||
2805 | { |
||
2806 | int ret; |
||
2807 | ECP_VALIDATE_RET( grp != NULL ); |
||
2808 | ECP_VALIDATE_RET( d != NULL ); |
||
2809 | ECP_VALIDATE_RET( G != NULL ); |
||
2810 | ECP_VALIDATE_RET( Q != NULL ); |
||
2811 | ECP_VALIDATE_RET( f_rng != NULL ); |
||
2812 | |||
2813 | MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) ); |
||
2814 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); |
||
2815 | |||
2816 | cleanup: |
||
2817 | return( ret ); |
||
2818 | } |
||
2819 | |||
2820 | /* |
||
2821 | * Generate key pair, wrapper for conventional base point |
||
2822 | */ |
||
2823 | int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, |
||
2824 | mbedtls_mpi *d, mbedtls_ecp_point *Q, |
||
2825 | int (*f_rng)(void *, unsigned char *, size_t), |
||
2826 | void *p_rng ) |
||
2827 | { |
||
2828 | ECP_VALIDATE_RET( grp != NULL ); |
||
2829 | ECP_VALIDATE_RET( d != NULL ); |
||
2830 | ECP_VALIDATE_RET( Q != NULL ); |
||
2831 | ECP_VALIDATE_RET( f_rng != NULL ); |
||
2832 | |||
2833 | return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) ); |
||
2834 | } |
||
2835 | |||
2836 | /* |
||
2837 | * Generate a keypair, prettier wrapper |
||
2838 | */ |
||
2839 | int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, |
||
2840 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
||
2841 | { |
||
2842 | int ret; |
||
2843 | ECP_VALIDATE_RET( key != NULL ); |
||
2844 | ECP_VALIDATE_RET( f_rng != NULL ); |
||
2845 | |||
2846 | if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) |
||
2847 | return( ret ); |
||
2848 | |||
2849 | return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); |
||
2850 | } |
||
2851 | |||
2852 | /* |
||
2853 | * Check a public-private key pair |
||
2854 | */ |
||
2855 | int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) |
||
2856 | { |
||
2857 | int ret; |
||
2858 | mbedtls_ecp_point Q; |
||
2859 | mbedtls_ecp_group grp; |
||
2860 | ECP_VALIDATE_RET( pub != NULL ); |
||
2861 | ECP_VALIDATE_RET( prv != NULL ); |
||
2862 | |||
2863 | if( pub->grp.id == MBEDTLS_ECP_DP_NONE || |
||
2864 | pub->grp.id != prv->grp.id || |
||
2865 | mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || |
||
2866 | mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || |
||
2867 | mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) |
||
2868 | { |
||
2869 | return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); |
||
2870 | } |
||
2871 | |||
2872 | mbedtls_ecp_point_init( &Q ); |
||
2873 | mbedtls_ecp_group_init( &grp ); |
||
2874 | |||
2875 | /* mbedtls_ecp_mul() needs a non-const group... */ |
||
2876 | mbedtls_ecp_group_copy( &grp, &prv->grp ); |
||
2877 | |||
2878 | /* Also checks d is valid */ |
||
2879 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); |
||
2880 | |||
2881 | if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) || |
||
2882 | mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || |
||
2883 | mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) |
||
2884 | { |
||
2885 | ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; |
||
2886 | goto cleanup; |
||
2887 | } |
||
2888 | |||
2889 | cleanup: |
||
2890 | mbedtls_ecp_point_free( &Q ); |
||
2891 | mbedtls_ecp_group_free( &grp ); |
||
2892 | |||
2893 | return( ret ); |
||
2894 | } |
||
2895 | |||
2896 | #if defined(MBEDTLS_SELF_TEST) |
||
2897 | |||
2898 | /* |
||
2899 | * Checkup routine |
||
2900 | */ |
||
2901 | int mbedtls_ecp_self_test( int verbose ) |
||
2902 | { |
||
2903 | int ret; |
||
2904 | size_t i; |
||
2905 | mbedtls_ecp_group grp; |
||
2906 | mbedtls_ecp_point R, P; |
||
2907 | mbedtls_mpi m; |
||
2908 | unsigned long add_c_prev, dbl_c_prev, mul_c_prev; |
||
2909 | /* exponents especially adapted for secp192r1 */ |
||
2910 | const char *exponents[] = |
||
2911 | { |
||
2912 | "000000000000000000000000000000000000000000000001", /* one */ |
||
2913 | "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ |
||
2914 | "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ |
||
2915 | "400000000000000000000000000000000000000000000000", /* one and zeros */ |
||
2916 | "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ |
||
2917 | "555555555555555555555555555555555555555555555555", /* 101010... */ |
||
2918 | }; |
||
2919 | |||
2920 | mbedtls_ecp_group_init( &grp ); |
||
2921 | mbedtls_ecp_point_init( &R ); |
||
2922 | mbedtls_ecp_point_init( &P ); |
||
2923 | mbedtls_mpi_init( &m ); |
||
2924 | |||
2925 | /* Use secp192r1 if available, or any available curve */ |
||
2926 | #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) |
||
2927 | MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); |
||
2928 | #else |
||
2929 | MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); |
||
2930 | #endif |
||
2931 | |||
2932 | if( verbose != 0 ) |
||
2933 | mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); |
||
2934 | |||
2935 | /* Do a dummy multiplication first to trigger precomputation */ |
||
2936 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); |
||
2937 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); |
||
2938 | |||
2939 | add_count = 0; |
||
2940 | dbl_count = 0; |
||
2941 | mul_count = 0; |
||
2942 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); |
||
2943 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); |
||
2944 | |||
2945 | for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) |
||
2946 | { |
||
2947 | add_c_prev = add_count; |
||
2948 | dbl_c_prev = dbl_count; |
||
2949 | mul_c_prev = mul_count; |
||
2950 | add_count = 0; |
||
2951 | dbl_count = 0; |
||
2952 | mul_count = 0; |
||
2953 | |||
2954 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); |
||
2955 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); |
||
2956 | |||
2957 | if( add_count != add_c_prev || |
||
2958 | dbl_count != dbl_c_prev || |
||
2959 | mul_count != mul_c_prev ) |
||
2960 | { |
||
2961 | if( verbose != 0 ) |
||
2962 | mbedtls_printf( "failed (%u)\n", (unsigned int) i ); |
||
2963 | |||
2964 | ret = 1; |
||
2965 | goto cleanup; |
||
2966 | } |
||
2967 | } |
||
2968 | |||
2969 | if( verbose != 0 ) |
||
2970 | mbedtls_printf( "passed\n" ); |
||
2971 | |||
2972 | if( verbose != 0 ) |
||
2973 | mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); |
||
2974 | /* We computed P = 2G last time, use it */ |
||
2975 | |||
2976 | add_count = 0; |
||
2977 | dbl_count = 0; |
||
2978 | mul_count = 0; |
||
2979 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); |
||
2980 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); |
||
2981 | |||
2982 | for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) |
||
2983 | { |
||
2984 | add_c_prev = add_count; |
||
2985 | dbl_c_prev = dbl_count; |
||
2986 | mul_c_prev = mul_count; |
||
2987 | add_count = 0; |
||
2988 | dbl_count = 0; |
||
2989 | mul_count = 0; |
||
2990 | |||
2991 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); |
||
2992 | MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); |
||
2993 | |||
2994 | if( add_count != add_c_prev || |
||
2995 | dbl_count != dbl_c_prev || |
||
2996 | mul_count != mul_c_prev ) |
||
2997 | { |
||
2998 | if( verbose != 0 ) |
||
2999 | mbedtls_printf( "failed (%u)\n", (unsigned int) i ); |
||
3000 | |||
3001 | ret = 1; |
||
3002 | goto cleanup; |
||
3003 | } |
||
3004 | } |
||
3005 | |||
3006 | if( verbose != 0 ) |
||
3007 | mbedtls_printf( "passed\n" ); |
||
3008 | |||
3009 | cleanup: |
||
3010 | |||
3011 | if( ret < 0 && verbose != 0 ) |
||
3012 | mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); |
||
3013 | |||
3014 | mbedtls_ecp_group_free( &grp ); |
||
3015 | mbedtls_ecp_point_free( &R ); |
||
3016 | mbedtls_ecp_point_free( &P ); |
||
3017 | mbedtls_mpi_free( &m ); |
||
3018 | |||
3019 | if( verbose != 0 ) |
||
3020 | mbedtls_printf( "\n" ); |
||
3021 | |||
3022 | return( ret ); |
||
3023 | } |
||
3024 | |||
3025 | #endif /* MBEDTLS_SELF_TEST */ |
||
3026 | |||
3027 | #endif /* !MBEDTLS_ECP_ALT */ |
||
3028 | |||
3029 | #endif /* MBEDTLS_ECP_C */>>>>>>=>>>>=>>>>>><>>>=><=>>=><=>>><>>><>><>=>><>>>=>><>>=>>>>>>>>>>>>>>=><=>>>1..2^8-1>>>1..2^8-1>>>>>>=>> |