blob: 0c9feae3f66b42cc7e3724aa0ef2d5e2cad920d3 [file] [log] [blame]
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01001/*
Manuel Pégourié-Gonnard32b04c12013-12-02 15:49:09 +01002 * Elliptic curves over GF(p): generic functions
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01003 *
Manuel Pégourié-Gonnard6fb81872015-07-27 11:11:48 +02004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
Manuel Pégourié-Gonnard37ff1402015-09-04 14:21:07 +02005 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010018 *
Manuel Pégourié-Gonnardfe446432015-03-06 13:17:10 +000019 * This file is part of mbed TLS (https://tls.mbed.org)
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010020 */
21
22/*
23 * References:
24 *
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +010025 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +010026 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
Manuel Pégourié-Gonnard62aad142012-11-10 00:27:12 +010027 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +010028 * RFC 4492 for the related TLS structures and constants
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +020029 *
Manuel Pégourié-Gonnard07894332015-06-23 00:18:41 +020030 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +010031 *
Manuel Pégourié-Gonnard998930a2015-04-03 13:48:06 +020032 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +020033 * for elliptic curve cryptosystems. In : Cryptographic Hardware and
34 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
35 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +010036 *
Manuel Pégourié-Gonnard998930a2015-04-03 13:48:06 +020037 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +010038 * render ECC resistant against Side Channel Attacks. IACR Cryptology
39 * ePrint Archive, 2004, vol. 2004, p. 342.
40 * <http://eprint.iacr.org/2004/342.pdf>
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010041 */
42
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020043#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000044#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020045#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020046#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020047#endif
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010048
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020049#if defined(MBEDTLS_ECP_C)
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010050
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000051#include "mbedtls/ecp.h"
Janos Follath430d3372016-11-03 14:25:37 +000052#include "mbedtls/threading.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020053
Rich Evans00ab4702015-02-06 13:43:58 +000054#include <string.h>
55
Janos Follathb0697532016-08-18 12:38:46 +010056#if !defined(MBEDTLS_ECP_ALT)
57
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020058#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000059#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020060#else
Rich Evans00ab4702015-02-06 13:43:58 +000061#include <stdlib.h>
Manuel Pégourié-Gonnard981732b2015-02-17 15:46:45 +000062#include <stdio.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020063#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020064#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020065#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020066#endif
67
Janos Follath47d28f02016-11-01 13:22:05 +000068#include "mbedtls/ecp_internal.h"
Janos Follathb0697532016-08-18 12:38:46 +010069
Manuel Pégourié-Gonnard0223ab92015-10-05 11:40:01 +010070#if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
71 !defined(inline) && !defined(__cplusplus)
Paul Bakker6a6087e2013-10-28 18:53:08 +010072#define inline __inline
Manuel Pégourié-Gonnard20af64d2015-07-07 18:33:39 +020073#endif
Paul Bakker6a6087e2013-10-28 18:53:08 +010074
Paul Bakker34617722014-06-13 17:20:13 +020075/* Implementation that should never be optimized out by the compiler */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020076static void mbedtls_zeroize( void *v, size_t n ) {
Paul Bakker34617722014-06-13 17:20:13 +020077 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
78}
79
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020080#if defined(MBEDTLS_SELF_TEST)
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +010081/*
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +010082 * Counts of point addition and doubling, and field multiplications.
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +020083 * Used to test resistance of point multiplication to simple timing attacks.
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +010084 */
Manuel Pégourié-Gonnard43863ee2013-12-01 16:51:27 +010085static unsigned long add_count, dbl_count, mul_count;
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +010086#endif
87
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +020088#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard054433c2017-03-22 11:18:33 +010089/*
90 * Maximum number of "basic operations" to be done in a row.
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +020091 *
92 * Default value 0 means that ECC operations will not yield.
93 * Note that regardless of the value of ecp_max_ops, always at
94 * least one step is performed before yielding.
95 *
96 * Setting ecp_max_ops=1 can be suitable for testing purposes
97 * as it will interrupt computation at all possible points.
Manuel Pégourié-Gonnard054433c2017-03-22 11:18:33 +010098 */
99static unsigned ecp_max_ops = 0;
100
101/*
102 * Set ecp_max_ops
103 */
104void mbedtls_ecp_set_max_ops( unsigned max_ops )
105{
106 ecp_max_ops = max_ops;
107}
Manuel Pégourié-Gonnard510d5ca2017-03-08 11:41:47 +0100108
109/*
Manuel Pégourié-Gonnarda0c5bcc2017-04-21 11:33:57 +0200110 * Check if restart is enabled
111 */
112int mbedtls_ecp_restart_enabled( void )
113{
114 return( ecp_max_ops != 0 );
115}
116
117/*
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200118 * Restart sub-context for ecp_mul_comb()
Manuel Pégourié-Gonnard510d5ca2017-03-08 11:41:47 +0100119 */
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200120struct mbedtls_ecp_restart_mul
121{
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +0100122 mbedtls_ecp_point R; /* current intermediate result */
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +0100123 size_t i; /* current index in various loops, 0 outside */
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +0100124 mbedtls_ecp_point *T; /* table for precomputed points */
125 unsigned char T_size; /* number of points in table T */
126 enum { /* what's the next step ? */
Manuel Pégourié-Gonnard45fd0162017-03-22 08:24:42 +0100127 ecp_rsm_init = 0, /* just getting started */
128 ecp_rsm_pre_norm_dbl, /* normalize precomputed 2^n multiples */
129 ecp_rsm_pre_add, /* precompute remaining points by adding */
130 ecp_rsm_pre_norm_add, /* normalize all precomputed points */
131 ecp_rsm_T_done, /* call ecp_mul_comb_after_precomp() */
132 ecp_rsm_final_norm, /* do the final normalization */
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100133 } state;
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100134};
Manuel Pégourié-Gonnard510d5ca2017-03-08 11:41:47 +0100135
136/*
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200137 * Init restart_mul sub-context
Manuel Pégourié-Gonnard510d5ca2017-03-08 11:41:47 +0100138 */
Manuel Pégourié-Gonnard45fd0162017-03-22 08:24:42 +0100139static void ecp_restart_mul_init( mbedtls_ecp_restart_mul_ctx *ctx )
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100140{
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200141 mbedtls_ecp_point_init( &ctx->R );
142 ctx->i = 0;
143 ctx->T = NULL;
144 ctx->T_size = 0;
145 ctx->state = ecp_rsm_init;
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100146}
147
148/*
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200149 * Free the components of a restart_mul sub-context
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100150 */
Manuel Pégourié-Gonnard45fd0162017-03-22 08:24:42 +0100151static void ecp_restart_mul_free( mbedtls_ecp_restart_mul_ctx *ctx )
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100152{
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +0100153 unsigned char i;
154
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100155 if( ctx == NULL )
156 return;
Manuel Pégourié-Gonnard78d564a2017-03-14 11:48:38 +0100157
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +0100158 mbedtls_ecp_point_free( &ctx->R );
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100159
Manuel Pégourié-Gonnard31f0ef72017-05-17 10:05:58 +0200160 if( ctx->T != NULL )
161 {
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +0100162 for( i = 0; i < ctx->T_size; i++ )
163 mbedtls_ecp_point_free( ctx->T + i );
164 mbedtls_free( ctx->T );
165 }
166
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200167 ecp_restart_mul_init( ctx );
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +0100168}
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100169
170/*
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200171 * Restart context for ecp_muladd()
172 */
173struct mbedtls_ecp_restart_muladd
174{
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +0200175 mbedtls_ecp_point mP; /* mP value */
176 mbedtls_ecp_point R; /* R intermediate result */
177 enum { /* what should we do next? */
178 ecp_rsma_mul1 = 0, /* first multiplication */
179 ecp_rsma_mul2, /* second multiplication */
180 ecp_rsma_add, /* addition */
181 ecp_rsma_norm, /* normalization */
182 } state;
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200183};
184
185/*
186 * Init restart_muladd sub-context
187 */
188static void ecp_restart_muladd_init( mbedtls_ecp_restart_muladd_ctx *ctx )
189{
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200190 mbedtls_ecp_point_init( &ctx->mP );
191 mbedtls_ecp_point_init( &ctx->R );
192 ctx->state = ecp_rsma_mul1;
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200193}
194
195/*
196 * Free the components of a restart_muladd sub-context
197 */
198static void ecp_restart_muladd_free( mbedtls_ecp_restart_muladd_ctx *ctx )
199{
200 if( ctx == NULL )
201 return;
202
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +0200203 mbedtls_ecp_point_free( &ctx->mP );
204 mbedtls_ecp_point_free( &ctx->R );
205
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200206 ecp_restart_muladd_init( ctx );
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +0200207}
208
209/*
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +0200210 * Initialize a restart context
211 */
212void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx )
213{
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200214 ctx->ops_done = 0;
215 ctx->depth = 0;
216 ctx->rsm = NULL;
217 ctx->ma = NULL;
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +0200218}
219
220/*
221 * Free the components of a restart context
222 */
223void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx *ctx )
224{
225 if( ctx == NULL )
226 return;
227
228 ecp_restart_mul_free( ctx->rsm );
229 mbedtls_free( ctx->rsm );
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +0200230
231 ecp_restart_muladd_free( ctx->ma );
232 mbedtls_free( ctx->ma );
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200233
234 mbedtls_ecp_restart_init( ctx );
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +0200235}
236
237/*
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100238 * Check if we can do the next step
239 */
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +0200240int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp,
241 mbedtls_ecp_restart_ctx *rs_ctx,
242 unsigned ops )
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100243{
Manuel Pégourié-Gonnard646393b2017-04-20 10:03:45 +0200244 if( rs_ctx != NULL && ecp_max_ops != 0 )
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100245 {
Manuel Pégourié-Gonnarde6854492017-03-20 14:35:19 +0100246 /* scale depending on curve size: the chosen reference is 256-bit,
247 * and multiplication is quadratic. Round to the closest integer. */
248 if( grp->pbits >= 512 )
249 ops *= 4;
250 else if( grp->pbits >= 384 )
251 ops *= 2;
252
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100253 /* avoid infinite loops: always allow first step */
Manuel Pégourié-Gonnard646393b2017-04-20 10:03:45 +0200254 if( rs_ctx->ops_done != 0 && rs_ctx->ops_done + ops > ecp_max_ops )
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100255 return( MBEDTLS_ERR_ECP_IN_PROGRESS );
256
Manuel Pégourié-Gonnarde6854492017-03-20 14:35:19 +0100257 /* update running count */
Manuel Pégourié-Gonnard646393b2017-04-20 10:03:45 +0200258 rs_ctx->ops_done += ops;
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +0100259 }
260
261 return( 0 );
262}
263
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +0200264#endif /* MBEDTLS_ECP_RESTARTABLE */
Manuel Pégourié-Gonnard054433c2017-03-22 11:18:33 +0100265
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200266#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \
267 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
268 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \
269 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \
270 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \
271 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \
272 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \
273 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \
274 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \
275 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \
276 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200277#define ECP_SHORTWEIERSTRASS
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100278#endif
279
Manuel Pégourié-Gonnard07894332015-06-23 00:18:41 +0200280#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200281#define ECP_MONTGOMERY
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100282#endif
283
284/*
285 * Curve types: internal for now, might be exposed later
286 */
287typedef enum
288{
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200289 ECP_TYPE_NONE = 0,
290 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
291 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100292} ecp_curve_type;
293
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100294/*
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200295 * List of supported curves:
296 * - internal ID
Manuel Pégourié-Gonnard8195c1a2013-10-07 19:40:41 +0200297 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200298 * - size in bits
Manuel Pégourié-Gonnard8195c1a2013-10-07 19:40:41 +0200299 * - readable name
Gergely Budaie40c4692014-01-22 11:22:20 +0100300 *
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100301 * Curves are listed in order: largest curves first, and for a given size,
302 * fastest curves first. This provides the default order for the SSL module.
Manuel Pégourié-Gonnard88db5da2015-06-15 14:34:59 +0200303 *
304 * Reminder: update profiles in x509_crt.c when adding a new curves!
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200305 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200306static const mbedtls_ecp_curve_info ecp_supported_curves[] =
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200307{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200308#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
309 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200310#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200311#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
312 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
Gergely Budaie40c4692014-01-22 11:22:20 +0100313#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200314#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
315 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200316#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200317#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
318 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
Gergely Budaie40c4692014-01-22 11:22:20 +0100319#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200320#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
321 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200322#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200323#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
324 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100325#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200326#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
327 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
Gergely Budaie40c4692014-01-22 11:22:20 +0100328#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200329#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
330 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200331#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200332#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
333 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
Manuel Pégourié-Gonnard9bcff392014-01-10 18:26:48 +0100334#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200335#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
336 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100337#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200338#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
339 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
Manuel Pégourié-Gonnard9bcff392014-01-10 18:26:48 +0100340#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200341 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200342};
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100343
Manuel Pégourié-Gonnardba782bb2014-07-08 13:31:34 +0200344#define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
345 sizeof( ecp_supported_curves[0] )
346
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200347static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200348
349/*
Manuel Pégourié-Gonnardda179e42013-09-18 15:31:24 +0200350 * List of supported curves and associated info
351 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200352const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
Manuel Pégourié-Gonnardda179e42013-09-18 15:31:24 +0200353{
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200354 return( ecp_supported_curves );
Manuel Pégourié-Gonnardda179e42013-09-18 15:31:24 +0200355}
356
357/*
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100358 * List of supported curves, group ID only
359 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200360const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100361{
362 static int init_done = 0;
363
364 if( ! init_done )
365 {
366 size_t i = 0;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200367 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100368
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200369 for( curve_info = mbedtls_ecp_curve_list();
370 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100371 curve_info++ )
372 {
373 ecp_supported_grp_id[i++] = curve_info->grp_id;
374 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200375 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100376
377 init_done = 1;
378 }
379
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200380 return( ecp_supported_grp_id );
Manuel Pégourié-Gonnardac719412014-02-04 14:48:50 +0100381}
382
383/*
384 * Get the curve info for the internal identifier
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200385 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200386const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200387{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200388 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200389
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200390 for( curve_info = mbedtls_ecp_curve_list();
391 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200392 curve_info++ )
393 {
394 if( curve_info->grp_id == grp_id )
395 return( curve_info );
396 }
397
398 return( NULL );
399}
400
401/*
402 * Get the curve info from the TLS identifier
403 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200404const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200405{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200406 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200407
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200408 for( curve_info = mbedtls_ecp_curve_list();
409 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200410 curve_info++ )
411 {
412 if( curve_info->tls_id == tls_id )
413 return( curve_info );
414 }
415
416 return( NULL );
417}
418
419/*
Manuel Pégourié-Gonnard0267e3d2013-11-30 15:10:14 +0100420 * Get the curve info from the name
421 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200422const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
Manuel Pégourié-Gonnard0267e3d2013-11-30 15:10:14 +0100423{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200424 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnard0267e3d2013-11-30 15:10:14 +0100425
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200426 for( curve_info = mbedtls_ecp_curve_list();
427 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
Manuel Pégourié-Gonnard0267e3d2013-11-30 15:10:14 +0100428 curve_info++ )
429 {
Manuel Pégourié-Gonnardcb46fd82015-05-28 17:06:07 +0200430 if( strcmp( curve_info->name, name ) == 0 )
Manuel Pégourié-Gonnard0267e3d2013-11-30 15:10:14 +0100431 return( curve_info );
432 }
433
434 return( NULL );
435}
436
437/*
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100438 * Get the type of a curve
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +0100439 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200440static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +0100441{
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100442 if( grp->G.X.p == NULL )
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200443 return( ECP_TYPE_NONE );
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100444
445 if( grp->G.Y.p == NULL )
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200446 return( ECP_TYPE_MONTGOMERY );
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100447 else
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200448 return( ECP_TYPE_SHORT_WEIERSTRASS );
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +0100449}
450
451/*
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100452 * Initialize (the components of) a point
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100453 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200454void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100455{
456 if( pt == NULL )
457 return;
458
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200459 mbedtls_mpi_init( &pt->X );
460 mbedtls_mpi_init( &pt->Y );
461 mbedtls_mpi_init( &pt->Z );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100462}
463
464/*
465 * Initialize (the components of) a group
466 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200467void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100468{
469 if( grp == NULL )
470 return;
471
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +0200472 grp->id = 0;
473 mbedtls_mpi_init( &grp->P );
474 mbedtls_mpi_init( &grp->A );
475 mbedtls_mpi_init( &grp->B );
476 mbedtls_ecp_point_init( &grp->G );
477 mbedtls_mpi_init( &grp->N );
478 grp->pbits = 0;
479 grp->nbits = 0;
480 grp->h = 0;
481 grp->modp = NULL;
482 grp->t_pre = NULL;
483 grp->t_post = NULL;
484 grp->t_data = NULL;
485 grp->T = NULL;
486 grp->T_size = 0;
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100487}
488
489/*
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200490 * Initialize (the components of) a key pair
491 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200492void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200493{
Paul Bakker66d5d072014-06-17 16:39:18 +0200494 if( key == NULL )
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200495 return;
496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200497 mbedtls_ecp_group_init( &key->grp );
498 mbedtls_mpi_init( &key->d );
499 mbedtls_ecp_point_init( &key->Q );
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200500}
501
502/*
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100503 * Unallocate (the components of) a point
504 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200505void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100506{
507 if( pt == NULL )
508 return;
509
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200510 mbedtls_mpi_free( &( pt->X ) );
511 mbedtls_mpi_free( &( pt->Y ) );
512 mbedtls_mpi_free( &( pt->Z ) );
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100513}
514
515/*
516 * Unallocate (the components of) a group
517 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200518void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100519{
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +0200520 size_t i;
521
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100522 if( grp == NULL )
523 return;
524
Manuel Pégourié-Gonnard1f82b042013-12-06 12:51:50 +0100525 if( grp->h != 1 )
526 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200527 mbedtls_mpi_free( &grp->P );
528 mbedtls_mpi_free( &grp->A );
529 mbedtls_mpi_free( &grp->B );
530 mbedtls_ecp_point_free( &grp->G );
531 mbedtls_mpi_free( &grp->N );
Manuel Pégourié-Gonnard1f82b042013-12-06 12:51:50 +0100532 }
Manuel Pégourié-Gonnardc9727702013-09-16 18:56:28 +0200533
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +0200534 if( grp->T != NULL )
535 {
536 for( i = 0; i < grp->T_size; i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200537 mbedtls_ecp_point_free( &grp->T[i] );
538 mbedtls_free( grp->T );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +0200539 }
540
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200541 mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +0100542}
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +0100543
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +0100544/*
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200545 * Unallocate (the components of) a key pair
546 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200547void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200548{
Paul Bakker66d5d072014-06-17 16:39:18 +0200549 if( key == NULL )
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200550 return;
551
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200552 mbedtls_ecp_group_free( &key->grp );
553 mbedtls_mpi_free( &key->d );
554 mbedtls_ecp_point_free( &key->Q );
Manuel Pégourié-Gonnardb8c6e0e2013-07-01 13:40:52 +0200555}
556
557/*
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200558 * Copy the contents of a point
559 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200560int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200561{
562 int ret;
563
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200564 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
565 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
566 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200567
568cleanup:
569 return( ret );
570}
571
572/*
573 * Copy the contents of a group object
574 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200575int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200576{
Manuel Pégourié-Gonnarde3a062b2015-05-11 18:46:47 +0200577 return mbedtls_ecp_group_load( dst, src->id );
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200578}
579
580/*
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100581 * Set point to zero
582 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200583int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100584{
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100585 int ret;
586
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200587 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
588 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
589 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100590
591cleanup:
592 return( ret );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100593}
594
595/*
Manuel Pégourié-Gonnard6545ca72013-01-26 16:05:22 +0100596 * Tell if a point is zero
597 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200598int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnard6545ca72013-01-26 16:05:22 +0100599{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200600 return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
Manuel Pégourié-Gonnard6545ca72013-01-26 16:05:22 +0100601}
602
603/*
Manuel Pégourié-Gonnard6029a852015-08-11 15:44:41 +0200604 * Compare two points lazyly
605 */
606int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
607 const mbedtls_ecp_point *Q )
608{
609 if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
610 mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
611 mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
612 {
613 return( 0 );
614 }
615
616 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
617}
618
619/*
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100620 * Import a non-zero point from ASCII strings
621 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200622int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100623 const char *x, const char *y )
624{
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +0100625 int ret;
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100626
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200627 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
628 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
629 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100630
631cleanup:
632 return( ret );
633}
634
635/*
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100636 * Export a point into unsigned binary data (SEC1 2.3.3)
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100637 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200638int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100639 int format, size_t *olen,
Manuel Pégourié-Gonnard7e860252013-02-10 10:58:48 +0100640 unsigned char *buf, size_t buflen )
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100641{
Paul Bakkera280d0f2013-04-08 13:40:17 +0200642 int ret = 0;
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100643 size_t plen;
644
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200645 if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
646 format != MBEDTLS_ECP_PF_COMPRESSED )
647 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100648
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100649 /*
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100650 * Common case: P == 0
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100651 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200652 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100653 {
654 if( buflen < 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200655 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100656
657 buf[0] = 0x00;
658 *olen = 1;
659
660 return( 0 );
661 }
662
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200663 plen = mbedtls_mpi_size( &grp->P );
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100664
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200665 if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100666 {
667 *olen = 2 * plen + 1;
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100668
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100669 if( buflen < *olen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200670 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100671
672 buf[0] = 0x04;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200673 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
674 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100675 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200676 else if( format == MBEDTLS_ECP_PF_COMPRESSED )
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100677 {
678 *olen = plen + 1;
679
680 if( buflen < *olen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200681 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100682
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200683 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
684 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
Manuel Pégourié-Gonnard37d218a2012-11-24 15:19:55 +0100685 }
Manuel Pégourié-Gonnarde19feb52012-11-24 14:10:14 +0100686
687cleanup:
688 return( ret );
689}
690
691/*
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100692 * Import a point from unsigned binary data (SEC1 2.3.4)
693 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
Manuel Pégourié-Gonnard5246ee52014-03-19 16:18:38 +0100695 const unsigned char *buf, size_t ilen )
696{
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100697 int ret;
698 size_t plen;
699
Paul Bakker82788fb2014-10-20 13:59:19 +0200700 if( ilen < 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200701 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard67dbe1e2014-07-08 13:09:24 +0200702
Manuel Pégourié-Gonnardc042cf02014-03-26 14:12:20 +0100703 if( buf[0] == 0x00 )
704 {
705 if( ilen == 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200706 return( mbedtls_ecp_set_zero( pt ) );
Manuel Pégourié-Gonnardc042cf02014-03-26 14:12:20 +0100707 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200708 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnardc042cf02014-03-26 14:12:20 +0100709 }
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100710
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200711 plen = mbedtls_mpi_size( &grp->P );
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100712
Manuel Pégourié-Gonnard5246ee52014-03-19 16:18:38 +0100713 if( buf[0] != 0x04 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200714 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
Manuel Pégourié-Gonnard5246ee52014-03-19 16:18:38 +0100715
716 if( ilen != 2 * plen + 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200717 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100718
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200719 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
720 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
721 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
Manuel Pégourié-Gonnard5e402d82012-11-24 16:19:42 +0100722
723cleanup:
724 return( ret );
725}
726
727/*
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100728 * Import a point from a TLS ECPoint record (RFC 4492)
729 * struct {
730 * opaque point <1..2^8-1>;
731 * } ECPoint;
732 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200733int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
Manuel Pégourié-Gonnard98f51812013-02-10 13:38:29 +0100734 const unsigned char **buf, size_t buf_len )
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100735{
736 unsigned char data_len;
Manuel Pégourié-Gonnard98f51812013-02-10 13:38:29 +0100737 const unsigned char *buf_start;
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100738
739 /*
Manuel Pégourié-Gonnard67dbe1e2014-07-08 13:09:24 +0200740 * We must have at least two bytes (1 for length, at least one for data)
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100741 */
742 if( buf_len < 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200743 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100744
Manuel Pégourié-Gonnard98f51812013-02-10 13:38:29 +0100745 data_len = *(*buf)++;
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100746 if( data_len < 1 || data_len > buf_len - 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200747 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100748
Manuel Pégourié-Gonnard98f51812013-02-10 13:38:29 +0100749 /*
750 * Save buffer start for read_binary and update buf
751 */
752 buf_start = *buf;
753 *buf += data_len;
754
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200755 return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100756}
757
758/*
759 * Export a point as a TLS ECPoint record (RFC 4492)
760 * struct {
761 * opaque point <1..2^8-1>;
762 * } ECPoint;
763 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200764int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100765 int format, size_t *olen,
766 unsigned char *buf, size_t blen )
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100767{
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100768 int ret;
769
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100770 /*
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100771 * buffer length must be at least one, for our length byte
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100772 */
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100773 if( blen < 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200774 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100775
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200776 if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100777 olen, buf + 1, blen - 1) ) != 0 )
778 return( ret );
779
780 /*
781 * write length to the first byte and update total length
782 */
Paul Bakkerb9cfaa02013-10-11 18:58:55 +0200783 buf[0] = (unsigned char) *olen;
Manuel Pégourié-Gonnard420f1eb2013-02-10 12:22:46 +0100784 ++*olen;
785
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200786 return( 0 );
Manuel Pégourié-Gonnard00794052013-02-09 19:00:07 +0100787}
788
789/*
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100790 * Set a group from an ECParameters record (RFC 4492)
791 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200792int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100793{
Manuel Pégourié-Gonnardf24b4a72013-09-23 18:14:50 +0200794 uint16_t tls_id;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200795 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100796
797 /*
798 * We expect at least three bytes (see below)
799 */
800 if( len < 3 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200801 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100802
803 /*
804 * First byte is curve_type; only named_curve is handled
805 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200806 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
807 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100808
809 /*
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100810 * Next two bytes are the namedcurve value
Manuel Pégourié-Gonnard1a967282013-02-09 17:03:58 +0100811 */
Manuel Pégourié-Gonnardf24b4a72013-09-23 18:14:50 +0200812 tls_id = *(*buf)++;
813 tls_id <<= 8;
814 tls_id |= *(*buf)++;
815
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200816 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
817 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
Manuel Pégourié-Gonnardf24b4a72013-09-23 18:14:50 +0200818
Manuel Pégourié-Gonnarde3a062b2015-05-11 18:46:47 +0200819 return mbedtls_ecp_group_load( grp, curve_info->grp_id );
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100820}
821
822/*
823 * Write the ECParameters record corresponding to a group (RFC 4492)
824 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200825int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100826 unsigned char *buf, size_t blen )
827{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200828 const mbedtls_ecp_curve_info *curve_info;
Manuel Pégourié-Gonnardf24b4a72013-09-23 18:14:50 +0200829
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200830 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
831 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200832
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100833 /*
834 * We are going to write 3 bytes (see below)
835 */
836 *olen = 3;
837 if( blen < *olen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200838 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100839
840 /*
841 * First byte is curve_type, always named_curve
842 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200843 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100844
845 /*
846 * Next two bytes are the namedcurve value
847 */
Manuel Pégourié-Gonnardf24b4a72013-09-23 18:14:50 +0200848 buf[0] = curve_info->tls_id >> 8;
849 buf[1] = curve_info->tls_id & 0xFF;
Manuel Pégourié-Gonnardb3258872013-02-10 12:06:19 +0100850
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200851 return( 0 );
Manuel Pégourié-Gonnarda5402fe2012-11-07 20:24:05 +0100852}
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100853
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200854/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200855 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
856 * See the documentation of struct mbedtls_ecp_group.
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200857 *
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200858 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200859 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200860static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200861{
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200862 int ret;
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200863
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200864 if( grp->modp == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200865 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200866
867 /* N->s < 0 is a much faster test, which fails only if N is 0 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200868 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200869 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200870 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200871 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200872 }
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200873
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200874 MBEDTLS_MPI_CHK( grp->modp( N ) );
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200875
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200876 /* N->s < 0 is a much faster test, which fails only if N is 0 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200877 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
878 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200879
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200880 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200881 /* we known P, N and the result are positive */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200882 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200883
Manuel Pégourié-Gonnardcae6f3e2013-10-23 20:19:57 +0200884cleanup:
885 return( ret );
Manuel Pégourié-Gonnard70380392013-09-16 16:19:53 +0200886}
Manuel Pégourié-Gonnard568c9cf2013-09-16 17:30:04 +0200887
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100888/*
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +0100889 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
Manuel Pégourié-Gonnarddada4da2012-11-10 14:23:17 +0100890 *
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +0100891 * In order to guarantee that, we need to ensure that operands of
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200892 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
Manuel Pégourié-Gonnarddada4da2012-11-10 14:23:17 +0100893 * bring the result back to this range.
894 *
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +0100895 * The following macros are shortcuts for doing that.
Manuel Pégourié-Gonnarddada4da2012-11-10 14:23:17 +0100896 */
897
898/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200899 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100900 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200901#if defined(MBEDTLS_SELF_TEST)
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +0100902#define INC_MUL_COUNT mul_count++;
903#else
904#define INC_MUL_COUNT
905#endif
906
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200907#define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +0100908 while( 0 )
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100909
910/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200911 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
Manuel Pégourié-Gonnardc9e387c2013-10-17 17:15:35 +0200912 * N->s < 0 is a very fast test, which fails only if N is 0
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100913 */
914#define MOD_SUB( N ) \
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200915 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \
916 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100917
918/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200919 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
Manuel Pégourié-Gonnardc9e387c2013-10-17 17:15:35 +0200920 * We known P, N and the result are positive, so sub_abs is correct, and
921 * a bit faster.
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100922 */
923#define MOD_ADD( N ) \
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200924 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
925 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100926
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +0200927#if defined(ECP_SHORTWEIERSTRASS)
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +0100928/*
929 * For curves in short Weierstrass form, we do all the internal operations in
930 * Jacobian coordinates.
931 *
932 * For multiplication, we'll use a comb method with coutermeasueres against
933 * SPA, hence timing attacks.
934 */
935
Manuel Pégourié-Gonnard84d1aea2012-11-09 02:09:38 +0100936/*
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100937 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +0100938 * Cost: 1N := 1I + 3M + 1S
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100939 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200940static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100941{
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +0100942 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200943 mbedtls_mpi Zi, ZZi;
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100944
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200945 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100946 return( 0 );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100947
Janos Follathb0697532016-08-18 12:38:46 +0100948#if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +0200949 if( mbedtls_internal_ecp_grp_capable( grp ) )
950 return( mbedtls_internal_ecp_normalize_jac( grp, pt ) );
Janos Follath372697b2016-10-28 16:53:11 +0100951#endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +0200952
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200953 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100954
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100955 /*
956 * X = X / Z^2 mod p
957 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200958 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
959 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
960 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100961
962 /*
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100963 * Y = Y / Z^3 mod p
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100964 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200965 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
966 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100967
968 /*
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +0100969 * Z = 1
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100970 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200971 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100972
973cleanup:
974
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200975 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
Manuel Pégourié-Gonnardd070f512012-11-08 17:40:51 +0100976
977 return( ret );
978}
979
980/*
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +0100981 * Normalize jacobian coordinates of an array of (pointers to) points,
Manuel Pégourié-Gonnard3680c822012-11-21 18:49:45 +0100982 * using Montgomery's trick to perform only one inversion mod P.
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +0100983 * (See for example Cohen's "A Course in Computational Algebraic Number
984 * Theory", Algorithm 10.3.4.)
985 *
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +0200986 * Warning: fails (returning an error) if one of the points is zero!
Manuel Pégourié-Gonnard7a949d32013-12-05 10:26:01 +0100987 * This should never happen, see choice of w in ecp_mul_comb().
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +0100988 *
989 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +0100990 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200991static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +0200992 mbedtls_ecp_point *T[], size_t T_size )
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +0100993{
994 int ret;
995 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200996 mbedtls_mpi *c, u, Zi, ZZi;
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +0100997
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +0200998 if( T_size < 2 )
Manuel Pégourié-Gonnard3c0b4ea2013-12-02 19:44:41 +0100999 return( ecp_normalize_jac( grp, *T ) );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001000
Janos Follathb0697532016-08-18 12:38:46 +01001001#if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02001002 if( mbedtls_internal_ecp_grp_capable( grp ) )
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001003 return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) );
Janos Follathb0697532016-08-18 12:38:46 +01001004#endif
1005
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001006 if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +02001007 return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001008
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +02001009 for( i = 0; i < T_size; i++ )
1010 mbedtls_mpi_init( &c[i] );
1011
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001012 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001013
1014 /*
1015 * c[i] = Z_0 * ... * Z_i
1016 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001017 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001018 for( i = 1; i < T_size; i++ )
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001019 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001020 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001021 MOD_MUL( c[i] );
1022 }
1023
1024 /*
1025 * u = 1 / (Z_0 * ... * Z_n) mod P
1026 */
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001027 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001028
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001029 for( i = T_size - 1; ; i-- )
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001030 {
1031 /*
1032 * Zi = 1 / Z_i mod p
1033 * u = 1 / (Z_0 * ... * Z_i) mod P
1034 */
1035 if( i == 0 ) {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001036 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001037 }
1038 else
1039 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001040 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
1041 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001042 }
1043
1044 /*
1045 * proceed as in normalize()
1046 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001047 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
1048 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
1049 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
1050 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
Manuel Pégourié-Gonnard1f789b82013-12-30 17:31:56 +01001051
1052 /*
1053 * Post-precessing: reclaim some memory by shrinking coordinates
1054 * - not storing Z (always 1)
1055 * - shrinking other coordinates, but still keeping the same number of
1056 * limbs as P, as otherwise it will too likely be regrown too fast.
1057 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001058 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
1059 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
1060 mbedtls_mpi_free( &T[i]->Z );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001061
1062 if( i == 0 )
1063 break;
1064 }
1065
1066cleanup:
1067
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001068 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001069 for( i = 0; i < T_size; i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001070 mbedtls_mpi_free( &c[i] );
1071 mbedtls_free( c );
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001072
1073 return( ret );
1074}
1075
Manuel Pégourié-Gonnardcdd44322012-11-21 16:00:55 +01001076/*
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001077 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
1078 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
1079 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001080static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
1081 mbedtls_ecp_point *Q,
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001082 unsigned char inv )
1083{
1084 int ret;
1085 unsigned char nonzero;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001086 mbedtls_mpi mQY;
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001087
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001088 mbedtls_mpi_init( &mQY );
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001089
1090 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001091 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
1092 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
1093 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001094
1095cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001096 mbedtls_mpi_free( &mQY );
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001097
1098 return( ret );
1099}
1100
1101/*
Manuel Pégourié-Gonnard0cd6f982013-10-10 15:55:39 +02001102 * Point doubling R = 2 P, Jacobian coordinates
Manuel Pégourié-Gonnard0ace4b32013-10-10 12:44:27 +02001103 *
Peter Dettmance661b22015-02-07 14:43:51 +07001104 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +01001105 *
Peter Dettmance661b22015-02-07 14:43:51 +07001106 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
1107 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
1108 *
1109 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1110 *
1111 * Cost: 1D := 3M + 4S (A == 0)
1112 * 4M + 4S (A == -3)
1113 * 3M + 6S + 1a otherwise
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001114 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001115static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1116 const mbedtls_ecp_point *P )
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001117{
1118 int ret;
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001119 mbedtls_mpi M, S, T, U;
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001120
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001121#if defined(MBEDTLS_SELF_TEST)
Manuel Pégourié-Gonnard0cd6f982013-10-10 15:55:39 +02001122 dbl_count++;
1123#endif
1124
Janos Follathb0697532016-08-18 12:38:46 +01001125#if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02001126 if( mbedtls_internal_ecp_grp_capable( grp ) )
1127 return( mbedtls_internal_ecp_double_jac( grp, R, P ) );
Janos Follath372697b2016-10-28 16:53:11 +01001128#endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01001129
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001130 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01001131
1132 /* Special case for A = -3 */
1133 if( grp->A.p == NULL )
1134 {
Peter Dettmance661b22015-02-07 14:43:51 +07001135 /* M = 3(X + Z^2)(X - Z^2) */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001136 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
1137 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T );
1138 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U );
1139 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S );
1140 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01001141 }
1142 else
Peter Vaskovica676acf2014-08-06 00:48:39 +02001143 {
Peter Dettmance661b22015-02-07 14:43:51 +07001144 /* M = 3.X^2 */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001145 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S );
1146 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
Peter Dettmance661b22015-02-07 14:43:51 +07001147
1148 /* Optimize away for "koblitz" curves with A = 0 */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001149 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
Peter Dettmance661b22015-02-07 14:43:51 +07001150 {
1151 /* M += A.Z^4 */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001152 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
1153 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T );
1154 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S );
1155 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M );
Peter Dettmance661b22015-02-07 14:43:51 +07001156 }
Peter Vaskovica676acf2014-08-06 00:48:39 +02001157 }
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01001158
Peter Dettmance661b22015-02-07 14:43:51 +07001159 /* S = 4.X.Y^2 */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001160 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T );
1161 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T );
1162 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S );
1163 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S );
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001164
Peter Dettmance661b22015-02-07 14:43:51 +07001165 /* U = 8.Y^4 */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001166 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U );
1167 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
Peter Dettmance661b22015-02-07 14:43:51 +07001168
1169 /* T = M^2 - 2.S */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001170 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T );
1171 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
1172 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
Peter Dettmance661b22015-02-07 14:43:51 +07001173
1174 /* S = M(S - T) - U */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001175 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S );
1176 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S );
1177 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S );
Peter Dettmance661b22015-02-07 14:43:51 +07001178
1179 /* U = 2.Y.Z */
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001180 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U );
1181 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
Peter Dettmance661b22015-02-07 14:43:51 +07001182
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001183 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
1184 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
1185 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001186
1187cleanup:
Manuel Pégourié-Gonnard2088ba62015-05-12 10:36:26 +02001188 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
Manuel Pégourié-Gonnard1c4aa242013-10-09 16:09:46 +02001189
1190 return( ret );
1191}
1192
1193/*
Manuel Pégourié-Gonnard469a2092013-11-21 18:20:43 +01001194 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
Manuel Pégourié-Gonnard9674fd02012-11-19 21:23:27 +01001195 *
1196 * The coordinates of Q must be normalized (= affine),
1197 * but those of P don't need to. R is not normalized.
1198 *
Manuel Pégourié-Gonnardaade42f2013-11-21 19:19:54 +01001199 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
Manuel Pégourié-Gonnard7a949d32013-12-05 10:26:01 +01001200 * None of these cases can happen as intermediate step in ecp_mul_comb():
Manuel Pégourié-Gonnardaade42f2013-11-21 19:19:54 +01001201 * - at each step, P, Q and R are multiples of the base point, the factor
1202 * being less than its order, so none of them is zero;
1203 * - Q is an odd multiple of the base point, P an even multiple,
1204 * due to the choice of precomputed points in the modified comb method.
1205 * So branches for these cases do not leak secret information.
1206 *
Manuel Pégourié-Gonnard72c172a2013-12-30 16:04:55 +01001207 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1208 *
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +01001209 * Cost: 1A := 8M + 3S
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001210 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001211static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1212 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001213{
Manuel Pégourié-Gonnard47123252012-11-10 14:44:24 +01001214 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001215 mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001216
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001217#if defined(MBEDTLS_SELF_TEST)
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01001218 add_count++;
1219#endif
1220
Janos Follathb0697532016-08-18 12:38:46 +01001221#if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02001222 if( mbedtls_internal_ecp_grp_capable( grp ) )
1223 return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) );
Janos Follath372697b2016-10-28 16:53:11 +01001224#endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01001225
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001226 /*
Manuel Pégourié-Gonnardaade42f2013-11-21 19:19:54 +01001227 * Trivial cases: P == 0 or Q == 0 (case 1)
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001228 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001229 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1230 return( mbedtls_ecp_copy( R, Q ) );
Manuel Pégourié-Gonnard469a2092013-11-21 18:20:43 +01001231
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001232 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
1233 return( mbedtls_ecp_copy( R, P ) );
Manuel Pégourié-Gonnard1c2782c2012-11-19 20:16:28 +01001234
1235 /*
1236 * Make sure Q coordinates are normalized
1237 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001238 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
1239 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001240
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001241 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
1242 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +01001243
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001244 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
1245 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
1246 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
1247 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
1248 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
1249 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001250
Manuel Pégourié-Gonnardaade42f2013-11-21 19:19:54 +01001251 /* Special cases (2) and (3) */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001252 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
Manuel Pégourié-Gonnard7e0adfb2012-11-08 23:21:46 +01001253 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001254 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
Manuel Pégourié-Gonnard7e0adfb2012-11-08 23:21:46 +01001255 {
1256 ret = ecp_double_jac( grp, R, P );
1257 goto cleanup;
1258 }
1259 else
1260 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001261 ret = mbedtls_ecp_set_zero( R );
Manuel Pégourié-Gonnard7e0adfb2012-11-08 23:21:46 +01001262 goto cleanup;
1263 }
1264 }
1265
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001266 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
1267 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
1268 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
1269 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
1270 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
1271 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
1272 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
1273 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
1274 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
1275 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
1276 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
1277 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
Manuel Pégourié-Gonnard7e0adfb2012-11-08 23:21:46 +01001278
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001279 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
1280 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
1281 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001282
1283cleanup:
1284
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001285 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
1286 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +01001287
1288 return( ret );
1289}
1290
1291/*
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001292 * Randomize jacobian coordinates:
1293 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
Manuel Pégourié-Gonnard3c0b4ea2013-12-02 19:44:41 +01001294 * This is sort of the reverse operation of ecp_normalize_jac().
Manuel Pégourié-Gonnard44aab792013-11-21 10:53:59 +01001295 *
1296 * This countermeasure was first suggested in [2].
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001297 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001298static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001299 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1300{
1301 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001302 mbedtls_mpi l, ll;
Janos Follathb0697532016-08-18 12:38:46 +01001303 size_t p_size;
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001304 int count = 0;
1305
Janos Follathb0697532016-08-18 12:38:46 +01001306#if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02001307 if( mbedtls_internal_ecp_grp_capable( grp ) )
1308 return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) );
Janos Follath372697b2016-10-28 16:53:11 +01001309#endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01001310
1311 p_size = ( grp->pbits + 7 ) / 8;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001312 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001313
1314 /* Generate l such that 1 < l < p */
1315 do
1316 {
Ron Eldorca6ff582017-01-12 14:50:50 +02001317 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001318
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001319 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1320 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001321
1322 if( count++ > 10 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001323 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001324 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001325 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001326
1327 /* Z = l * Z */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001328 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001329
1330 /* X = l^2 * X */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001331 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
1332 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001333
1334 /* Y = l^3 * Y */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001335 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
1336 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001337
1338cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001339 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
Manuel Pégourié-Gonnard07de4b12013-09-02 16:26:04 +02001340
1341 return( ret );
1342}
1343
1344/*
Manuel Pégourié-Gonnardc30200e2013-11-20 18:39:55 +01001345 * Check and define parameters used by the comb method (see below for details)
1346 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001347#if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1348#error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
Manuel Pégourié-Gonnardc30200e2013-11-20 18:39:55 +01001349#endif
1350
1351/* d = ceil( n / w ) */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001352#define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
Manuel Pégourié-Gonnardc30200e2013-11-20 18:39:55 +01001353
1354/* number of precomputed points */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001355#define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
Manuel Pégourié-Gonnardc30200e2013-11-20 18:39:55 +01001356
1357/*
1358 * Compute the representation of m that will be used with our comb method.
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001359 *
1360 * The basic comb method is described in GECC 3.44 for example. We use a
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001361 * modified version that provides resistance to SPA by avoiding zero
1362 * digits in the representation as in [3]. We modify the method further by
1363 * requiring that all K_i be odd, which has the small cost that our
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001364 * representation uses one more K_i, due to carries, but saves on the size of
1365 * the precomputed table.
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001366 *
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001367 * Summary of the comb method and its modifications:
1368 *
1369 * - The goal is to compute m*P for some w*d-bit integer m.
1370 *
1371 * - The basic comb method splits m into the w-bit integers
1372 * x[0] .. x[d-1] where x[i] consists of the bits in m whose
1373 * index has residue i modulo d, and computes m * P as
1374 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
1375 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
1376 *
1377 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
1378 * .. + 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]] ..,
1379 * thereby successively converting it into a form where all summands
1380 * are nonzero, at the cost of negative summands. This is the basic idea of [3].
1381 *
1382 * - More generally, even if x[i+1] != 0, we can first transform the sum as
1383 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
1384 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
1385 * Performing and iterating this procedure for those x[i] that are even
1386 * (keeping track of carry), we can transform the original sum into one of the form
1387 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
1388 * with all x'[i] odd. It is therefore only necessary to know S at odd indices,
1389 * which is why we are only computing half of it in the first place in
1390 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
1391 *
1392 * - For the sake of compactness, only the seven low-order bits of x[i]
1393 * are used to represent its absolute value (K_i in the paper), and the msb
1394 * of x[i] encodes the the sign (s_i in the paper): it is set if and only if
1395 * if s_i == -1;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001396 *
1397 * Calling conventions:
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001398 * - x is an array of size d + 1
Manuel Pégourié-Gonnardc30200e2013-11-20 18:39:55 +01001399 * - w is the size, ie number of teeth, of the comb, and must be between
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001400 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001401 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1402 * (the result will be incorrect if these assumptions are not satisfied)
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001403 */
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001404static void ecp_comb_recode_core( unsigned char x[], size_t d,
1405 unsigned char w, const mbedtls_mpi *m )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001406{
1407 size_t i, j;
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001408 unsigned char c, cc, adjust;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001409
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001410 memset( x, 0, d+1 );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001411
Manuel Pégourié-Gonnardedc1a1f2013-11-21 09:50:00 +01001412 /* First get the classical comb values (except for x_d = 0) */
1413 for( i = 0; i < d; i++ )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001414 for( j = 0; j < w; j++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001415 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001416
Manuel Pégourié-Gonnardedc1a1f2013-11-21 09:50:00 +01001417 /* Now make sure x_1 .. x_d are odd */
1418 c = 0;
1419 for( i = 1; i <= d; i++ )
1420 {
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001421 /* Add carry and update it */
1422 cc = x[i] & c;
1423 x[i] = x[i] ^ c;
1424 c = cc;
1425
Manuel Pégourié-Gonnardedc1a1f2013-11-21 09:50:00 +01001426 /* Adjust if needed, avoiding branches */
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001427 adjust = 1 - ( x[i] & 0x01 );
1428 c |= x[i] & ( x[i-1] * adjust );
1429 x[i] = x[i] ^ ( x[i-1] * adjust );
1430 x[i-1] |= adjust << 7;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001431 }
1432}
1433
1434/*
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001435 * Precompute points for the adapted comb method
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001436 *
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001437 * Assumption: T must be able to hold 2^{w - 1} elements.
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001438 *
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001439 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
1440 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +01001441 *
1442 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001443 *
1444 * Note: Even comb values (those where P would be omitted from the
1445 * sum defining T[i] above) are not needed in our adaption
1446 * the the comb method. See ecp_comb_recode_core().
1447 *
1448 * This function currently works in four steps:
1449 * (1) Computation of intermediate T[i] for 2-powers values of i
1450 * (restart state is ecp_rsm_init).
1451 * (2) Normalization of coordinates of these T[i]
1452 * (restart state is ecp_rsm_pre_norm_dbl).
1453 * (3) Computation of all T[i] (restart state is ecp_rsm_pre_add).
1454 * (4) Normalization of all T[i] (restart state is ecp_rsm_pre_norm_add)
1455 * The final restart state is ecp_rsm_T_done.
1456 *
1457 * Step 1 can be interrupted but not the others; together with the final
1458 * coordinate normalization they are the largest steps done at once, depending
1459 * on the window size. Here are operation counts for P-256:
1460 *
1461 * step (2) (3) (4)
1462 * w = 5 142 165 208
1463 * w = 4 136 77 160
1464 * w = 3 130 33 136
1465 * w = 2 124 11 124
1466 *
1467 * So if ECC operations are blocking for too long even with a low max_ops
1468 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
1469 * to minimize maximum blocking time.
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001470 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001471static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
1472 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001473 unsigned char w, size_t d,
1474 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001475{
1476 int ret;
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001477 unsigned char i;
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001478 size_t j = 0;
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001479 const unsigned char T_size = 1U << ( w - 1 );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001480 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001481
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001482#if !defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001483 (void) rs_ctx;
1484#endif
1485
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001486#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001487 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001488 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001489 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add )
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001490 goto norm_add;
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001491 if( rs_ctx->rsm->state == ecp_rsm_pre_add )
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001492 goto add;
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001493 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl )
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001494 goto norm_dbl;
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001495 }
1496#endif
1497
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001498 /*
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001499 * Set T[0] = P and
1500 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001501 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001502 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001503
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001504#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001505 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 )
1506 j = rs_ctx->rsm->i;
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001507 else
1508#endif
1509 j = 0;
1510
1511 for( ; j < d * ( w - 1 ); j++ )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001512 {
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02001513 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL );
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001514
Manuel Pégourié-Gonnardae557072017-03-20 12:21:24 +01001515 i = 1U << ( j / d );
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001516 cur = T + i;
Manuel Pégourié-Gonnardae557072017-03-20 12:21:24 +01001517
1518 if( j % d == 0 )
1519 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
1520
1521 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001522 }
1523
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001524#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001525 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001526 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001527 rs_ctx->rsm->i = 0;
1528 rs_ctx->rsm->state++;
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001529 }
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001530#endif
1531
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001532 /*
1533 * Normalize current elements in T. As T has holes,
1534 * use an auxiliary array of pointers to elements in T.
1535 */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001536#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001537norm_dbl:
1538#endif
1539
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001540 j = 0;
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001541 for( i = 1; i < T_size; i <<= 1 )
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001542 TT[j++] = T + i;
1543
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02001544 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001545
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001546 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001547
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001548#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001549 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1550 rs_ctx->rsm->state++;
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001551#endif
1552
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001553 /*
1554 * Compute the remaining ones using the minimal number of additions
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001555 * Be careful to update T[2^l] only after using it!
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001556 */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001557#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001558add:
1559#endif
1560
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001561 MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD );
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001562
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001563 for( i = 1; i < T_size; i <<= 1 )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001564 {
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001565 j = i;
1566 while( j-- )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001567 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001568 }
1569
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001570#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001571 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1572 rs_ctx->rsm->state++;
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001573#endif
1574
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001575 /*
1576 * Normalize final elements in T. Even though there are no holes now,
1577 * we still need the auxiliary array for homogeneity with last time.
Manuel Pégourié-Gonnard67c83fb2017-03-20 10:08:53 +01001578 * Also, skip T[0] which is already normalised, being a copy of P.
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001579 */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001580#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001581norm_add:
1582#endif
1583
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001584 for( j = 0; j + 1 < T_size; j++ )
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001585 TT[j] = T + j + 1;
1586
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02001587 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
Manuel Pégourié-Gonnarde2d7cb32017-03-20 10:24:17 +01001588
Manuel Pégourié-Gonnardfc3e0be2017-03-20 09:29:31 +01001589 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
Manuel Pégourié-Gonnarde2820122013-11-21 10:08:50 +01001590
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001591#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001592 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1593 rs_ctx->rsm->state++;
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001594#endif
1595
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001596cleanup:
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001597#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001598 if( rs_ctx != NULL && rs_ctx->rsm != NULL &&
1599 ret == MBEDTLS_ERR_ECP_IN_PROGRESS )
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001600 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001601 if( rs_ctx->rsm->state == ecp_rsm_init )
1602 rs_ctx->rsm->i = j;
Manuel Pégourié-Gonnard213541a2017-03-20 12:50:41 +01001603 }
1604#endif
Janos Follathb0697532016-08-18 12:38:46 +01001605
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001606 return( ret );
1607}
1608
1609/*
Manuel Pégourié-Gonnard101a39f2013-11-20 14:47:19 +01001610 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001611 *
1612 * See ecp_comb_recode_core() for background
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001613 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001614static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001615 const mbedtls_ecp_point T[], unsigned char T_size,
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001616 unsigned char i )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001617{
1618 int ret;
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001619 unsigned char ii, j;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001620
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001621 /* Ignore the "sign" bit and scale down */
1622 ii = ( i & 0x7Fu ) >> 1;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001623
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001624 /* Read the whole table to thwart cache-based timing attacks */
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001625 for( j = 0; j < T_size; j++ )
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001626 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001627 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
1628 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001629 }
1630
Manuel Pégourié-Gonnard01fca5e2013-11-21 17:47:12 +01001631 /* Safely invert result if i is "negative" */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001632 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001633
1634cleanup:
1635 return( ret );
1636}
1637
1638/*
1639 * Core multiplication algorithm for the (modified) comb method.
1640 * This part is actually common with the basic comb method (GECC 3.44)
Manuel Pégourié-Gonnard04a02252013-11-20 22:57:38 +01001641 *
1642 * Cost: d A + d D + 1 R
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001643 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001644static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001645 const mbedtls_ecp_point T[], unsigned char T_size,
Manuel Pégourié-Gonnard70c14372013-11-20 20:07:26 +01001646 const unsigned char x[], size_t d,
1647 int (*f_rng)(void *, unsigned char *, size_t),
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001648 void *p_rng,
1649 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001650{
1651 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001652 mbedtls_ecp_point Txi;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001653 size_t i;
1654
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001655 mbedtls_ecp_point_init( &Txi );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001656
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001657#if !defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001658 (void) rs_ctx;
1659#endif
1660
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001661#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001662 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 )
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001663 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001664 /* restore current index (R already pointing to rs_ctx->rsm->R) */
1665 i = rs_ctx->rsm->i;
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001666 }
1667 else
1668#endif
1669 {
1670 /* Start with a non-zero point and randomize its coordinates */
1671 i = d;
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001672 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) );
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001673 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
1674 if( f_rng != 0 )
1675 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1676 }
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001677
1678 while( i-- != 0 )
1679 {
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02001680 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001681 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001682 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001683 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001684 }
1685
1686cleanup:
Janos Follathb0697532016-08-18 12:38:46 +01001687
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001688 mbedtls_ecp_point_free( &Txi );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001689
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001690#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001691 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001692 {
1693 if( ret == 0 )
1694 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001695 rs_ctx->rsm->state++;
1696 rs_ctx->rsm->i = 0;
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001697 }
1698 else if( ret == MBEDTLS_ERR_ECP_IN_PROGRESS )
1699 {
1700 /* was decreased before actually doing it */
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001701 rs_ctx->rsm->i = i + 1;
1702 /* no need to save R, already pointing to rs_ctx->rsm->R */
Manuel Pégourié-Gonnardc5d844b2017-03-15 13:06:28 +01001703 }
1704 }
1705#endif
1706
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001707 return( ret );
1708}
1709
1710/*
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001711 * Recode the scalar to get constant-time comb multiplication
1712 *
1713 * As the actual scalar recoding needs an odd scalar as a starting point,
1714 * this wrapper ensures that by replacing m by N - m if necessary, and
1715 * informs the caller that the result of multiplication will be negated.
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001716 *
1717 * See ecp_comb_recode_core() for background.
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001718 */
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001719static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp,
1720 const mbedtls_mpi *m,
1721 unsigned char k[COMB_MAX_D + 1],
1722 size_t d,
1723 unsigned char w,
1724 unsigned char *parity_trick )
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001725{
1726 int ret;
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001727 mbedtls_mpi M, mm;
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001728
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001729 mbedtls_mpi_init( &M );
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001730 mbedtls_mpi_init( &mm );
1731
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001732 /* N is odd with all real-world curves, just make extra sure */
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001733 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
1734 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1735
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001736 /* do we need the parity trick? */
1737 *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 );
1738
1739 /* execute parity fix in constant time */
1740 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001741 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001742 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) );
1743
1744 /* actual scalar recoding */
1745 ecp_comb_recode_core( k, d, w, &M );
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001746
1747cleanup:
1748 mbedtls_mpi_free( &mm );
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001749 mbedtls_mpi_free( &M );
Manuel Pégourié-Gonnardec5606a2017-03-09 12:46:45 +01001750
1751 return( ret );
1752}
1753
1754/*
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001755 * Perform comb multiplication (for short Weierstrass curves)
1756 * once the auxiliary table has been pre-computed.
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001757 *
1758 * Scalar recoding may use a parity trick that makes us compute -m * P,
1759 * if that is the case we'll need to recover m * P at the end.
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001760 */
1761static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp,
1762 mbedtls_ecp_point *R,
1763 const mbedtls_mpi *m,
1764 const mbedtls_ecp_point *T,
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001765 unsigned char T_size,
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001766 unsigned char w,
1767 size_t d,
1768 int (*f_rng)(void *, unsigned char *, size_t),
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001769 void *p_rng,
1770 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001771{
1772 int ret;
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001773 unsigned char parity_trick;
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001774 unsigned char k[COMB_MAX_D + 1];
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +01001775 mbedtls_ecp_point *RR = R;
1776
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001777#if !defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001778 (void) rs_ctx;
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +01001779#endif
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001780
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001781#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001782 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1783 RR = &rs_ctx->rsm->R;
1784#endif
1785
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001786#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001787 if( rs_ctx == NULL || rs_ctx->rsm == NULL ||
1788 rs_ctx->rsm->state < ecp_rsm_final_norm )
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001789#endif
1790 {
1791 MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w,
1792 &parity_trick ) );
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001793 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d,
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001794 f_rng, p_rng, rs_ctx ) );
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001795 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) );
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001796
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001797#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001798 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1799 rs_ctx->rsm->state++;
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001800#endif
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001801 }
Manuel Pégourié-Gonnard62738e92017-03-14 10:00:21 +01001802
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02001803 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +01001804 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) );
1805
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001806#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard28d16282017-08-23 17:33:27 +02001807 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1808 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) );
Manuel Pégourié-Gonnard8962ddb2017-03-14 12:11:21 +01001809#endif
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001810
1811cleanup:
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001812 return( ret );
1813}
1814
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001815/*
Manuel Pégourié-Gonnard4b2336d2017-03-09 13:23:50 +01001816 * Pick window size based on curve size and whether we optimize for base point
1817 */
1818static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp,
1819 unsigned char p_eq_g )
1820{
1821 unsigned char w;
1822
1823 /*
1824 * Minimize the number of multiplications, that is minimize
1825 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
1826 * (see costs of the various parts, with 1S = 1M)
1827 */
1828 w = grp->nbits >= 384 ? 5 : 4;
1829
1830 /*
1831 * If P == G, pre-compute a bit more, since this may be re-used later.
1832 * Just adding one avoids upping the cost of the first mul too much,
1833 * and the memory cost too.
1834 */
1835 if( p_eq_g )
1836 w++;
1837
1838 /*
1839 * Make sure w is within bounds.
1840 * (The last test is useful only for very small curves in the test suite.)
1841 */
1842 if( w > MBEDTLS_ECP_WINDOW_SIZE )
1843 w = MBEDTLS_ECP_WINDOW_SIZE;
1844 if( w >= grp->nbits )
1845 w = 2;
1846
1847 return( w );
1848}
1849
1850/*
Manuel Pégourié-Gonnard07bf6f52017-03-16 17:21:38 +01001851 * Multiplication using the comb method - for curves in short Weierstrass form
1852 *
1853 * This function is mainly responsible for administrative work:
1854 * - managing the restart context if enabled
1855 * - managing the table of precomputed points (passed between the above two
1856 * functions): allocation, computation, ownership tranfer, freeing.
1857 *
1858 * It delegates the actual arithmetic work to:
1859 * ecp_precompute_comb() and ecp_mul_comb_with_precomp()
1860 *
1861 * See comments on ecp_comb_recode_core() regarding the computation strategy.
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001862 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001863static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1864 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01001865 int (*f_rng)(void *, unsigned char *, size_t),
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001866 void *p_rng,
1867 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001868{
1869 int ret;
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +01001870 unsigned char w, p_eq_g = 0, i;
Manuel Pégourié-Gonnardd7283502013-11-21 20:00:38 +01001871 size_t d;
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001872 unsigned char T_size = 0, T_ok = 0;
Manuel Pégourié-Gonnard7306dff2017-03-09 12:23:45 +01001873 mbedtls_ecp_point *T = NULL;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001874
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001875#if !defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001876 (void) rs_ctx;
1877#endif
1878
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001879#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard646393b2017-04-20 10:03:45 +02001880 /* set up our own sub-context if needed */
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001881 if( ecp_max_ops != 0 && rs_ctx != NULL && rs_ctx->rsm == NULL )
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +01001882 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001883 rs_ctx->rsm = mbedtls_calloc( 1, sizeof( mbedtls_ecp_restart_mul_ctx ) );
1884 if( rs_ctx->rsm == NULL )
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +01001885 return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
Manuel Pégourié-Gonnard78d564a2017-03-14 11:48:38 +01001886
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001887 ecp_restart_mul_init( rs_ctx->rsm );
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +01001888 }
Manuel Pégourié-Gonnard510d5ca2017-03-08 11:41:47 +01001889#endif
1890
Manuel Pégourié-Gonnard22be6352017-03-09 13:02:35 +01001891 /* Is P the base point ? */
1892#if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
1893 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
1894 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
Manuel Pégourié-Gonnard22be6352017-03-09 13:02:35 +01001895#endif
1896
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001897 /* Pick window size and deduce related sizes */
Manuel Pégourié-Gonnard4b2336d2017-03-09 13:23:50 +01001898 w = ecp_pick_window_size( grp, p_eq_g );
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001899 T_size = 1U << ( w - 1 );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001900 d = ( grp->nbits + w - 1 ) / w;
1901
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001902 /* Pre-computed table: do we have it already for the base point? */
1903 if( p_eq_g && grp->T != NULL )
1904 {
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001905 /* second pointer to the same table, will be deleted on exit */
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001906 T = grp->T;
1907 T_ok = 1;
1908 }
Manuel Pégourié-Gonnardedc1a1f2013-11-21 09:50:00 +01001909
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001910#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001911 /* Pre-computed table: do we have one in progress? complete? */
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001912 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL && T == NULL )
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +01001913 {
Manuel Pégourié-Gonnard45fd0162017-03-22 08:24:42 +01001914 /* transfer ownership of T from rsm to local function */
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001915 T = rs_ctx->rsm->T;
1916 rs_ctx->rsm->T = NULL;
1917 rs_ctx->rsm->T_size = 0;
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001918
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001919 if( rs_ctx->rsm->state >= ecp_rsm_T_done )
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001920 T_ok = 1;
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +01001921 }
1922#endif
1923
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001924 /* Allocate table if we didn't have any */
Manuel Pégourié-Gonnardedc1a1f2013-11-21 09:50:00 +01001925 if( T == NULL )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001926 {
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001927 T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001928 if( T == NULL )
1929 {
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +02001930 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001931 goto cleanup;
1932 }
Manuel Pégourié-Gonnard5bd38b12017-08-23 16:55:59 +02001933
1934 for( i = 0; i < T_size; i++ )
1935 mbedtls_ecp_point_init( &T[i] );
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001936 }
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001937
Manuel Pégourié-Gonnard085b1df2017-03-16 16:56:04 +01001938 /* Compute table (or finish computing it) if not done already */
1939 if( !T_ok )
1940 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001941 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001942
1943 if( p_eq_g )
1944 {
Manuel Pégourié-Gonnard7037e222017-08-23 14:30:36 +02001945 /* almost transfer ownership of T to the group, but keep a copy of
1946 * the pointer to use for caling the next function more easily */
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001947 grp->T = T;
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001948 grp->T_size = T_size;
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001949 }
1950 }
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001951
Manuel Pégourié-Gonnard391f4412017-03-13 12:26:21 +01001952 /* Actual comb multiplication using precomputed points */
1953 MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m,
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001954 T, T_size, w, d,
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001955 f_rng, p_rng, rs_ctx ) );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001956
1957cleanup:
1958
Manuel Pégourié-Gonnard07bf6f52017-03-16 17:21:38 +01001959 /* does T belong to the group? */
1960 if( T == grp->T )
1961 T = NULL;
1962
1963 /* does T belong to the restart context? */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001964#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001965 if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL )
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +01001966 {
Manuel Pégourié-Gonnard45fd0162017-03-22 08:24:42 +01001967 /* transfer ownership of T from local function to rsm */
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001968 rs_ctx->rsm->T_size = T_size;
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001969 rs_ctx->rsm->T = T;
Manuel Pégourié-Gonnardc9c0aa62017-03-16 14:53:26 +01001970 T = NULL;
1971 }
1972#endif
1973
Manuel Pégourié-Gonnard07bf6f52017-03-16 17:21:38 +01001974 /* did T belong to us? then let's destroy it! */
1975 if( T != NULL )
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001976 {
Manuel Pégourié-Gonnard92cceb22017-08-23 16:27:29 +02001977 for( i = 0; i < T_size; i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001978 mbedtls_ecp_point_free( &T[i] );
1979 mbedtls_free( T );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001980 }
1981
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001982 /* don't free R while in progress in case R == P */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001983#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard2fad7ae2017-03-14 13:13:13 +01001984 if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS )
1985#endif
Manuel Pégourié-Gonnard07bf6f52017-03-16 17:21:38 +01001986 /* prevent caller from using invalid value */
Manuel Pégourié-Gonnardaade42f2013-11-21 19:19:54 +01001987 if( ret != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001988 mbedtls_ecp_point_free( R );
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01001989
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02001990 /* clear our sub-context when not in progress (done or error) */
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02001991#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnardb948f7d2017-08-23 17:58:40 +02001992 if( rs_ctx != NULL && rs_ctx->rsm != NULL &&
1993 ret != MBEDTLS_ERR_ECP_IN_PROGRESS )
Manuel Pégourié-Gonnard31f0ef72017-05-17 10:05:58 +02001994 {
Manuel Pégourié-Gonnard3cade222017-04-20 09:31:00 +02001995 ecp_restart_mul_free( rs_ctx->rsm );
1996 mbedtls_free( rs_ctx->rsm );
1997 rs_ctx->rsm = NULL;
Manuel Pégourié-Gonnard77af79a2017-03-14 10:58:00 +01001998 }
1999#endif
2000
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01002001 return( ret );
2002}
2003
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002004#endif /* ECP_SHORTWEIERSTRASS */
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +01002005
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002006#if defined(ECP_MONTGOMERY)
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +01002007/*
2008 * For Montgomery curves, we do all the internal arithmetic in projective
2009 * coordinates. Import/export of points uses only the x coordinates, which is
2010 * internaly represented as X / Z.
2011 *
2012 * For scalar multiplication, we'll use a Montgomery ladder.
2013 */
2014
Manuel Pégourié-Gonnardd1c1ba92013-11-16 15:50:12 +01002015/*
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002016 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
2017 * Cost: 1M + 1I
2018 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002019static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002020{
2021 int ret;
2022
Janos Follathb0697532016-08-18 12:38:46 +01002023#if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002024 if( mbedtls_internal_ecp_grp_capable( grp ) )
2025 return( mbedtls_internal_ecp_normalize_mxz( grp, P ) );
Janos Follath372697b2016-10-28 16:53:11 +01002026#endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01002027
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002028 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
2029 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
2030 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002031
2032cleanup:
2033 return( ret );
2034}
2035
2036/*
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002037 * Randomize projective x/z coordinates:
2038 * (X, Z) -> (l X, l Z) for random l
2039 * This is sort of the reverse operation of ecp_normalize_mxz().
2040 *
2041 * This countermeasure was first suggested in [2].
2042 * Cost: 2M
2043 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002044static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002045 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2046{
2047 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002048 mbedtls_mpi l;
Janos Follathb0697532016-08-18 12:38:46 +01002049 size_t p_size;
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002050 int count = 0;
2051
Janos Follathb0697532016-08-18 12:38:46 +01002052#if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002053 if( mbedtls_internal_ecp_grp_capable( grp ) )
2054 return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
Janos Follath372697b2016-10-28 16:53:11 +01002055#endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01002056
2057 p_size = ( grp->pbits + 7 ) / 8;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002058 mbedtls_mpi_init( &l );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002059
2060 /* Generate l such that 1 < l < p */
2061 do
2062 {
Ron Eldorca6ff582017-01-12 14:50:50 +02002063 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002064
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002065 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
2066 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002067
2068 if( count++ > 10 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002069 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002070 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002071 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002072
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002073 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
2074 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002075
2076cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002077 mbedtls_mpi_free( &l );
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002078
2079 return( ret );
2080}
2081
2082/*
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002083 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
2084 * for Montgomery curves in x/z coordinates.
2085 *
2086 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
2087 * with
2088 * d = X1
2089 * P = (X2, Z2)
2090 * Q = (X3, Z3)
2091 * R = (X4, Z4)
2092 * S = (X5, Z5)
2093 * and eliminating temporary variables tO, ..., t4.
2094 *
2095 * Cost: 5M + 4S
2096 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002097static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
2098 mbedtls_ecp_point *R, mbedtls_ecp_point *S,
2099 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
2100 const mbedtls_mpi *d )
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002101{
2102 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002103 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002104
Janos Follathb0697532016-08-18 12:38:46 +01002105#if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002106 if( mbedtls_internal_ecp_grp_capable( grp ) )
2107 return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) );
Janos Follath372697b2016-10-28 16:53:11 +01002108#endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
Janos Follathb0697532016-08-18 12:38:46 +01002109
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002110 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
2111 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
2112 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002113
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002114 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
2115 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
2116 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
2117 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
2118 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
2119 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
2120 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
2121 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
2122 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
2123 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
2124 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
2125 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
2126 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
2127 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
2128 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
2129 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
2130 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
2131 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002132
2133cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002134 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
2135 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
2136 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002137
2138 return( ret );
2139}
2140
2141/*
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002142 * Multiplication with Montgomery ladder in x/z coordinates,
2143 * for curves in Montgomery form
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002144 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002145static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2146 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002147 int (*f_rng)(void *, unsigned char *, size_t),
2148 void *p_rng )
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002149{
2150 int ret;
2151 size_t i;
Manuel Pégourié-Gonnardb6f45a62013-12-04 21:54:36 +01002152 unsigned char b;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002153 mbedtls_ecp_point RP;
2154 mbedtls_mpi PX;
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002155
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002156 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002157
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002158 /* Save PX and read from P before writing to R, in case P == R */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002159 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );
2160 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
Manuel Pégourié-Gonnard357ff652013-12-04 18:39:17 +01002161
2162 /* Set R to zero in modified x/z coordinates */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002163 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );
2164 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );
2165 mbedtls_mpi_free( &R->Y );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002166
Manuel Pégourié-Gonnard93f41db2013-12-05 10:48:42 +01002167 /* RP.X might be sligtly larger than P, so reduce it */
2168 MOD_ADD( RP.X );
2169
Manuel Pégourié-Gonnard3afa07f2013-12-03 13:28:21 +01002170 /* Randomize coordinates of the starting point */
Manuel Pégourié-Gonnard357ff652013-12-04 18:39:17 +01002171 if( f_rng != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002172 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002173
Manuel Pégourié-Gonnardb6f45a62013-12-04 21:54:36 +01002174 /* Loop invariant: R = result so far, RP = R + P */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002175 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002176 while( i-- > 0 )
2177 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002178 b = mbedtls_mpi_get_bit( m, i );
Manuel Pégourié-Gonnardb6f45a62013-12-04 21:54:36 +01002179 /*
2180 * if (b) R = 2R + P else R = 2R,
2181 * which is:
2182 * if (b) double_add( RP, R, RP, R )
2183 * else double_add( R, RP, R, RP )
2184 * but using safe conditional swaps to avoid leaks
2185 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002186 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
2187 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
2188 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
2189 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
2190 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002191 }
2192
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002193 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002194
2195cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002196 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002197
2198 return( ret );
2199}
2200
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002201#endif /* ECP_MONTGOMERY */
Manuel Pégourié-Gonnard7c94d8b2013-12-04 23:15:46 +01002202
Manuel Pégourié-Gonnardd9ea82e2013-12-03 12:02:28 +01002203/*
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002204 * Restartable multiplication R = m * P
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002205 */
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002206int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002207 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002208 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
2209 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002210{
Janos Follathb0697532016-08-18 12:38:46 +01002211 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
Janos Follathc44ab972016-11-18 16:38:23 +00002212#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2213 char is_grp_capable = 0;
2214#endif
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002215
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002216#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002217 /* reset ops count for this call if top-level */
2218 if( rs_ctx != NULL && rs_ctx->depth++ == 0 )
2219 rs_ctx->ops_done = 0;
2220#endif
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002221
Janos Follathc44ab972016-11-18 16:38:23 +00002222#if defined(MBEDTLS_ECP_INTERNAL_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002223 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )
Janos Follathc44ab972016-11-18 16:38:23 +00002224 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
Janos Follathc44ab972016-11-18 16:38:23 +00002225#endif /* MBEDTLS_ECP_INTERNAL_ALT */
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002226
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002227#if defined(MBEDTLS_ECP_RESTARTABLE) && defined(ECP_SHORTWEIERSTRASS)
Manuel Pégourié-Gonnarda08cd1a2017-04-20 11:29:43 +02002228 /* skip argument check when restarting */
2229 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ||
2230 rs_ctx == NULL || rs_ctx->rsm == NULL )
2231#endif
2232 {
Manuel Pégourié-Gonnard5314f232017-04-21 12:36:59 +02002233 /* check_privkey is free */
2234 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK );
2235
Manuel Pégourié-Gonnarda08cd1a2017-04-20 11:29:43 +02002236 /* Common sanity checks */
2237 MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) );
2238 MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) );
Manuel Pégourié-Gonnarda08cd1a2017-04-20 11:29:43 +02002239 }
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002240
2241 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002242#if defined(ECP_MONTGOMERY)
2243 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002244 MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
Janos Follath430d3372016-11-03 14:25:37 +00002245#endif
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002246#if defined(ECP_SHORTWEIERSTRASS)
2247 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002248 MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) );
Janos Follath430d3372016-11-03 14:25:37 +00002249#endif
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002250
Janos Follath6c8ccd52016-11-29 15:37:09 +00002251cleanup:
Janos Follathb0697532016-08-18 12:38:46 +01002252
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002253#if defined(MBEDTLS_ECP_INTERNAL_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002254 if( is_grp_capable )
Janos Follathc44ab972016-11-18 16:38:23 +00002255 mbedtls_internal_ecp_free( grp );
Janos Follathc44ab972016-11-18 16:38:23 +00002256#endif /* MBEDTLS_ECP_INTERNAL_ALT */
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002257
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002258#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard3a256122017-04-20 11:20:26 +02002259 if( rs_ctx != NULL )
2260 rs_ctx->depth--;
2261#endif
2262
Janos Follathb0697532016-08-18 12:38:46 +01002263 return( ret );
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002264}
2265
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002266/*
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002267 * Multiplication R = m * P
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002268 */
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002269int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002270 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002271 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002272{
Manuel Pégourié-Gonnard884569c2017-04-20 10:10:59 +02002273 return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) );
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002274}
Manuel Pégourié-Gonnardb739a712017-04-19 10:11:56 +02002275
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002276#if defined(ECP_SHORTWEIERSTRASS)
Manuel Pégourié-Gonnarda0179b82013-12-04 11:49:20 +01002277/*
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002278 * Check that an affine point is valid as a public key,
2279 * short weierstrass curves (SEC1 3.2.3.1)
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002280 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002281static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002282{
2283 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002284 mbedtls_mpi YY, RHS;
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002285
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +01002286 /* pt coordinates must be normalized for our checks */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002287 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||
2288 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||
2289 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
2290 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
2291 return( MBEDTLS_ERR_ECP_INVALID_KEY );
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002292
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002293 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002294
2295 /*
2296 * YY = Y^2
Manuel Pégourié-Gonnardcd7458a2013-10-08 13:11:30 +02002297 * RHS = X (X^2 + A) + B = X^3 + A X + B
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002298 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002299 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
2300 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01002301
2302 /* Special case for A = -3 */
2303 if( grp->A.p == NULL )
2304 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002305 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01002306 }
2307 else
2308 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002309 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
Manuel Pégourié-Gonnard73cc01d2013-12-06 12:41:30 +01002310 }
2311
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002312 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
2313 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002314
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002315 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
2316 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002317
2318cleanup:
2319
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002320 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002321
2322 return( ret );
2323}
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002324#endif /* ECP_SHORTWEIERSTRASS */
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002325
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002326/*
Manuel Pégourié-Gonnardde9f9532015-10-23 15:50:37 +02002327 * R = m * P with shortcuts for m == 1 and m == -1
2328 * NOT constant-time - ONLY for short Weierstrass!
2329 */
2330static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
2331 mbedtls_ecp_point *R,
2332 const mbedtls_mpi *m,
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002333 const mbedtls_ecp_point *P,
2334 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnardde9f9532015-10-23 15:50:37 +02002335{
2336 int ret;
2337
2338 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
2339 {
2340 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2341 }
2342 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
2343 {
2344 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2345 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
2346 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
2347 }
2348 else
2349 {
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002350 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P,
2351 NULL, NULL, rs_ctx ) );
Manuel Pégourié-Gonnardde9f9532015-10-23 15:50:37 +02002352 }
2353
2354cleanup:
2355 return( ret );
2356}
2357
2358/*
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002359 * Restartable linear combination
Manuel Pégourié-Gonnardde9f9532015-10-23 15:50:37 +02002360 * NOT constant-time
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002361 */
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002362int mbedtls_ecp_muladd_restartable(
2363 mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002364 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002365 const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
2366 mbedtls_ecp_restart_ctx *rs_ctx )
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002367{
2368 int ret;
2369 mbedtls_ecp_point mP;
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002370 mbedtls_ecp_point *pmP = &mP;
2371 mbedtls_ecp_point *pR = R;
Janos Follathc44ab972016-11-18 16:38:23 +00002372#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2373 char is_grp_capable = 0;
2374#endif
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002375
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002376#if !defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002377 (void) rs_ctx;
2378#endif
2379
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002380 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
2381 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
2382
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002383 mbedtls_ecp_point_init( &mP );
2384
2385#if defined(MBEDTLS_ECP_INTERNAL_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002386 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002387 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002388#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2389
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002390#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002391 /* reset ops count for this call if top-level */
2392 if( rs_ctx != NULL && rs_ctx->depth++ == 0 )
2393 rs_ctx->ops_done = 0;
2394
2395 /* set up our own sub-context if needed */
2396 if( ecp_max_ops != 0 && rs_ctx != NULL && rs_ctx->ma == NULL )
2397 {
2398 rs_ctx->ma = mbedtls_calloc( 1, sizeof( mbedtls_ecp_restart_muladd_ctx ) );
2399 if( rs_ctx->ma == NULL )
2400 return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
2401
2402 ecp_restart_muladd_init( rs_ctx->ma );
2403 }
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002404
2405 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2406 {
2407 /* redirect intermediate results to restart context */
2408 pmP = &rs_ctx->ma->mP;
2409 pR = &rs_ctx->ma->R;
2410
2411 /* jump to next operation */
2412 if( rs_ctx->ma->state == ecp_rsma_mul2 )
2413 goto mul2;
2414 if( rs_ctx->ma->state == ecp_rsma_add )
2415 goto add;
2416 if( rs_ctx->ma->state == ecp_rsma_norm )
2417 goto norm;
2418 }
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002419#endif /* MBEDTLS_ECP_RESTARTABLE */
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002420
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002421 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) );
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002422#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002423 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2424 rs_ctx->ma->state++;
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002425
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002426mul2:
2427#endif
2428 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR, n, Q, rs_ctx ) );
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002429#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002430 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2431 rs_ctx->ma->state++;
Manuel Pégourié-Gonnard1a7c5ef2015-08-13 10:19:09 +02002432
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002433add:
2434#endif
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02002435 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD );
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002436 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) );
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002437#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002438 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2439 rs_ctx->ma->state++;
Janos Follath430d3372016-11-03 14:25:37 +00002440
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002441norm:
2442#endif
Manuel Pégourié-Gonnardc7511482017-04-20 16:31:00 +02002443 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002444 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) );
2445
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002446#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002447 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2448 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) );
2449#endif
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002450
2451cleanup:
Janos Follathc44ab972016-11-18 16:38:23 +00002452#if defined(MBEDTLS_ECP_INTERNAL_ALT)
Manuel Pégourié-Gonnardebac5d32017-08-23 16:23:36 +02002453 if( is_grp_capable )
Janos Follathc44ab972016-11-18 16:38:23 +00002454 mbedtls_internal_ecp_free( grp );
Janos Follathc44ab972016-11-18 16:38:23 +00002455#endif /* MBEDTLS_ECP_INTERNAL_ALT */
Manuel Pégourié-Gonnard1631d632017-04-20 14:48:56 +02002456
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002457 mbedtls_ecp_point_free( &mP );
2458
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002459#if defined(MBEDTLS_ECP_RESTARTABLE)
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002460 /* clear our sub-context when not in progress (done or error) */
Manuel Pégourié-Gonnardb948f7d2017-08-23 17:58:40 +02002461 if( rs_ctx != NULL && rs_ctx->ma != NULL &&
2462 ret != MBEDTLS_ERR_ECP_IN_PROGRESS )
Manuel Pégourié-Gonnard31f0ef72017-05-17 10:05:58 +02002463 {
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002464 ecp_restart_muladd_free( rs_ctx->ma );
2465 mbedtls_free( rs_ctx->ma );
2466 rs_ctx->ma = NULL;
2467 }
2468
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002469 if( rs_ctx != NULL )
2470 rs_ctx->depth--;
Manuel Pégourié-Gonnard4b9c51e2017-04-20 15:50:26 +02002471#endif /* MBEDTLS_ECP_RESTARTABLE */
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002472
Manuel Pégourié-Gonnard56cc88a2015-05-11 18:40:45 +02002473 return( ret );
2474}
2475
Manuel Pégourié-Gonnard54dd6522017-04-20 13:36:18 +02002476/*
2477 * Linear combination
2478 * NOT constant-time
2479 */
2480int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2481 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2482 const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
2483{
2484 return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) );
2485}
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002486
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002487#if defined(ECP_MONTGOMERY)
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002488/*
2489 * Check validity of a public key for Montgomery curves with x-only schemes
2490 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002491static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002492{
Manuel Pégourié-Gonnard07894332015-06-23 00:18:41 +02002493 /* [Curve25519 p. 5] Just check X is the correct number of bytes */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002494 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
2495 return( MBEDTLS_ERR_ECP_INVALID_KEY );
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002496
2497 return( 0 );
2498}
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002499#endif /* ECP_MONTGOMERY */
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002500
2501/*
2502 * Check that a point is valid as a public key
2503 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002504int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002505{
2506 /* Must use affine coordinates */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002507 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
2508 return( MBEDTLS_ERR_ECP_INVALID_KEY );
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002509
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002510#if defined(ECP_MONTGOMERY)
2511 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002512 return( ecp_check_pubkey_mx( grp, pt ) );
2513#endif
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002514#if defined(ECP_SHORTWEIERSTRASS)
2515 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002516 return( ecp_check_pubkey_sw( grp, pt ) );
2517#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002518 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002519}
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002520
2521/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002522 * Check that an mbedtls_mpi is valid as a private key
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002523 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002524int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d )
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002525{
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002526#if defined(ECP_MONTGOMERY)
2527 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +01002528 {
Manuel Pégourié-Gonnard07894332015-06-23 00:18:41 +02002529 /* see [Curve25519] page 5 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002530 if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||
2531 mbedtls_mpi_get_bit( d, 1 ) != 0 ||
2532 mbedtls_mpi_get_bit( d, 2 ) != 0 ||
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002533 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002534 return( MBEDTLS_ERR_ECP_INVALID_KEY );
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002535 else
2536 return( 0 );
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +01002537 }
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002538#endif /* ECP_MONTGOMERY */
2539#if defined(ECP_SHORTWEIERSTRASS)
2540 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +01002541 {
2542 /* see SEC1 3.2 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002543 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
2544 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
2545 return( MBEDTLS_ERR_ECP_INVALID_KEY );
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002546 else
2547 return( 0 );
Manuel Pégourié-Gonnard312d2e82013-12-04 11:08:01 +01002548 }
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002549#endif /* ECP_SHORTWEIERSTRASS */
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002550
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002551 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnardc8dc2952013-07-01 14:06:13 +02002552}
2553
2554/*
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002555 * Generate a private key
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002556 */
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002557int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp,
2558 mbedtls_mpi *d,
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002559 int (*f_rng)(void *, unsigned char *, size_t),
2560 void *p_rng )
2561{
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002562 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
Paul Bakker66d5d072014-06-17 16:39:18 +02002563 size_t n_size = ( grp->nbits + 7 ) / 8;
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002564
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002565#if defined(ECP_MONTGOMERY)
2566 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002567 {
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002568 /* [M225] page 5 */
2569 size_t b;
2570
Janos Follath98e28a72016-05-31 14:03:54 +01002571 do {
2572 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
2573 } while( mbedtls_mpi_bitlen( d ) == 0);
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002574
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002575 /* Make sure the most significant bit is nbits */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002576 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002577 if( b > grp->nbits )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002578 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002579 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002580 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002581
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002582 /* Make sure the last three bits are unset */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002583 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
2584 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
2585 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002586 }
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002587#endif /* ECP_MONTGOMERY */
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002588
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002589#if defined(ECP_SHORTWEIERSTRASS)
2590 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002591 {
2592 /* SEC1 3.2.1: Generate d such that 1 <= n < N */
Manuel Pégourié-Gonnardd9622732013-12-05 10:06:06 +01002593 int count = 0;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002594 unsigned char rnd[MBEDTLS_ECP_MAX_BYTES];
Manuel Pégourié-Gonnard79f73b92014-01-03 12:35:05 +01002595
2596 /*
2597 * Match the procedure given in RFC 6979 (deterministic ECDSA):
2598 * - use the same byte ordering;
2599 * - keep the leftmost nbits bits of the generated octet string;
2600 * - try until result is in the desired range.
2601 * This also avoids any biais, which is especially important for ECDSA.
Manuel Pégourié-Gonnard67543962017-04-21 13:19:43 +02002602 *
2603 * Each try has at worst a probability 1/2 of failing (the msb has
2604 * a probability 1/2 of being 0, and then the result will be < N),
2605 * so after 30 tries failure probability is a most 2**(-30).
2606 *
2607 * For most curves, 1 try is enough with overwhelming probability,
2608 * since N starts with a lot of 1s in binary, but some curves
2609 * such as secp224k1 are actually very close to the worst case.
Manuel Pégourié-Gonnard79f73b92014-01-03 12:35:05 +01002610 */
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002611 do
2612 {
Manuel Pégourié-Gonnard67543962017-04-21 13:19:43 +02002613 if( ++count > 30 )
2614 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
2615
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002616 MBEDTLS_MPI_CHK( f_rng( p_rng, rnd, n_size ) );
2617 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( d, rnd, n_size ) );
2618 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002619 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002620 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
2621 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
Manuel Pégourié-Gonnardfe0af402013-12-04 18:14:55 +01002622 }
Manuel Pégourié-Gonnard8408a942015-04-09 12:14:31 +02002623#endif /* ECP_SHORTWEIERSTRASS */
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002624
Manuel Pégourié-Gonnardc9573992014-01-03 12:54:00 +01002625cleanup:
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002626 return( ret );
2627}
Manuel Pégourié-Gonnardc9573992014-01-03 12:54:00 +01002628
Manuel Pégourié-Gonnarda7937f92017-04-20 15:37:46 +02002629/*
2630 * Generate a keypair with configurable base point
2631 */
2632int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
2633 const mbedtls_ecp_point *G,
2634 mbedtls_mpi *d, mbedtls_ecp_point *Q,
2635 int (*f_rng)(void *, unsigned char *, size_t),
2636 void *p_rng )
2637{
2638 int ret;
2639
2640 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) );
2641 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
2642
2643cleanup:
2644 return( ret );
Manuel Pégourié-Gonnardd9a3f472015-08-11 14:31:03 +02002645}
2646
2647/*
2648 * Generate key pair, wrapper for conventional base point
2649 */
2650int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
2651 mbedtls_mpi *d, mbedtls_ecp_point *Q,
2652 int (*f_rng)(void *, unsigned char *, size_t),
2653 void *p_rng )
2654{
2655 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
Manuel Pégourié-Gonnard45a035a2013-01-26 14:42:45 +01002656}
Manuel Pégourié-Gonnardefaa31e2012-11-06 21:34:35 +01002657
Manuel Pégourié-Gonnard104ee1d2013-11-30 14:13:16 +01002658/*
2659 * Generate a keypair, prettier wrapper
2660 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002661int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
Manuel Pégourié-Gonnard104ee1d2013-11-30 14:13:16 +01002662 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2663{
2664 int ret;
2665
Manuel Pégourié-Gonnarde3a062b2015-05-11 18:46:47 +02002666 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
Manuel Pégourié-Gonnard104ee1d2013-11-30 14:13:16 +01002667 return( ret );
2668
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002669 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
Manuel Pégourié-Gonnard104ee1d2013-11-30 14:13:16 +01002670}
2671
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002672/*
2673 * Check a public-private key pair
2674 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002675int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002676{
2677 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002678 mbedtls_ecp_point Q;
2679 mbedtls_ecp_group grp;
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002680
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002681 if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002682 pub->grp.id != prv->grp.id ||
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002683 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
2684 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
2685 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002686 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002687 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002688 }
2689
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002690 mbedtls_ecp_point_init( &Q );
2691 mbedtls_ecp_group_init( &grp );
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002692
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002693 /* mbedtls_ecp_mul() needs a non-const group... */
2694 mbedtls_ecp_group_copy( &grp, &prv->grp );
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002695
2696 /* Also checks d is valid */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002697 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002698
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002699 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
2700 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
2701 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002702 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002703 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002704 goto cleanup;
2705 }
2706
2707cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002708 mbedtls_ecp_point_free( &Q );
2709 mbedtls_ecp_group_free( &grp );
Manuel Pégourié-Gonnard30668d62014-11-06 15:25:32 +01002710
2711 return( ret );
2712}
2713
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002714#if defined(MBEDTLS_SELF_TEST)
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01002715
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +01002716/*
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01002717 * Checkup routine
2718 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002719int mbedtls_ecp_self_test( int verbose )
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01002720{
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002721 int ret;
2722 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002723 mbedtls_ecp_group grp;
2724 mbedtls_ecp_point R, P;
2725 mbedtls_mpi m;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002726 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
Manuel Pégourié-Gonnardb8012fc2013-10-10 15:40:49 +02002727 /* exponents especially adapted for secp192r1 */
Paul Bakkerb6c5d2e2013-06-25 16:25:17 +02002728 const char *exponents[] =
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002729 {
Manuel Pégourié-Gonnardb63f9e92012-11-21 13:00:58 +01002730 "000000000000000000000000000000000000000000000001", /* one */
Manuel Pégourié-Gonnardff27b7c2013-11-21 09:28:03 +01002731 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
Manuel Pégourié-Gonnardb63f9e92012-11-21 13:00:58 +01002732 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
Manuel Pégourié-Gonnardff27b7c2013-11-21 09:28:03 +01002733 "400000000000000000000000000000000000000000000000", /* one and zeros */
2734 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
2735 "555555555555555555555555555555555555555555555555", /* 101010... */
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002736 };
2737
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002738 mbedtls_ecp_group_init( &grp );
2739 mbedtls_ecp_point_init( &R );
2740 mbedtls_ecp_point_init( &P );
2741 mbedtls_mpi_init( &m );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002742
Manuel Pégourié-Gonnardb8012fc2013-10-10 15:40:49 +02002743 /* Use secp192r1 if available, or any available curve */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002744#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
Manuel Pégourié-Gonnarde3a062b2015-05-11 18:46:47 +02002745 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
Paul Bakker5dc6b5f2013-06-29 23:26:34 +02002746#else
Manuel Pégourié-Gonnarde3a062b2015-05-11 18:46:47 +02002747 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
Manuel Pégourié-Gonnardb8012fc2013-10-10 15:40:49 +02002748#endif
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002749
2750 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002751 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002752
2753 /* Do a dummy multiplication first to trigger precomputation */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002754 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
2755 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002756
2757 add_count = 0;
2758 dbl_count = 0;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002759 mul_count = 0;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002760 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2761 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002762
2763 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2764 {
2765 add_c_prev = add_count;
2766 dbl_c_prev = dbl_count;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002767 mul_c_prev = mul_count;
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002768 add_count = 0;
2769 dbl_count = 0;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002770 mul_count = 0;
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002771
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002772 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2773 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002774
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002775 if( add_count != add_c_prev ||
2776 dbl_count != dbl_c_prev ||
2777 mul_count != mul_c_prev )
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002778 {
2779 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002780 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002781
2782 ret = 1;
2783 goto cleanup;
2784 }
2785 }
2786
2787 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002788 mbedtls_printf( "passed\n" );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002789
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002790 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002791 mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002792 /* We computed P = 2G last time, use it */
2793
2794 add_count = 0;
2795 dbl_count = 0;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002796 mul_count = 0;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002797 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2798 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002799
2800 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2801 {
2802 add_c_prev = add_count;
2803 dbl_c_prev = dbl_count;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002804 mul_c_prev = mul_count;
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002805 add_count = 0;
2806 dbl_count = 0;
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002807 mul_count = 0;
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002808
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002809 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2810 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002811
Manuel Pégourié-Gonnard91814812013-11-21 20:23:55 +01002812 if( add_count != add_c_prev ||
2813 dbl_count != dbl_c_prev ||
2814 mul_count != mul_c_prev )
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002815 {
2816 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002817 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002818
2819 ret = 1;
2820 goto cleanup;
2821 }
2822 }
2823
2824 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002825 mbedtls_printf( "passed\n" );
Manuel Pégourié-Gonnard161ef962013-09-17 19:13:10 +02002826
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002827cleanup:
2828
2829 if( ret < 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002830 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002831
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002832 mbedtls_ecp_group_free( &grp );
2833 mbedtls_ecp_point_free( &R );
2834 mbedtls_ecp_point_free( &P );
2835 mbedtls_mpi_free( &m );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002836
2837 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002838 mbedtls_printf( "\n" );
Manuel Pégourié-Gonnardb4a310b2012-11-13 20:57:00 +01002839
2840 return( ret );
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01002841}
2842
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002843#endif /* MBEDTLS_SELF_TEST */
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01002844
Janos Follathb0697532016-08-18 12:38:46 +01002845#endif /* !MBEDTLS_ECP_ALT */
2846
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002847#endif /* MBEDTLS_ECP_C */