mbed-os - mbed os with nrf51 internal bandgap enabled to re…

Users » elessair » Code » mbed-os

mbed os with nrf51 internal bandgap enabled to read battery level

Dependents: BLE_file_test BLE_Blink ExternalEncoder

features/mbedtls/src/ecp.c@0:f269e3021894, 2016-10-23 (annotated)

Committer:: elessair
Date:: Sun Oct 23 15:10:02 2016 +0000
Revision:: 0:f269e3021894

Initial commit

Who changed what in which revision?

User	Revision	Line number	New contents of line
elessair	0:f269e3021894	1	/*
elessair	0:f269e3021894	2	* Elliptic curves over GF(p): generic functions
elessair	0:f269e3021894	3	*
elessair	0:f269e3021894	4	* Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
elessair	0:f269e3021894	5	* SPDX-License-Identifier: Apache-2.0
elessair	0:f269e3021894	6	*
elessair	0:f269e3021894	7	* Licensed under the Apache License, Version 2.0 (the "License"); you may
elessair	0:f269e3021894	8	* not use this file except in compliance with the License.
elessair	0:f269e3021894	9	* You may obtain a copy of the License at
elessair	0:f269e3021894	10	*
elessair	0:f269e3021894	11	* http://www.apache.org/licenses/LICENSE-2.0
elessair	0:f269e3021894	12	*
elessair	0:f269e3021894	13	* Unless required by applicable law or agreed to in writing, software
elessair	0:f269e3021894	14	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
elessair	0:f269e3021894	15	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
elessair	0:f269e3021894	16	* See the License for the specific language governing permissions and
elessair	0:f269e3021894	17	* limitations under the License.
elessair	0:f269e3021894	18	*
elessair	0:f269e3021894	19	* This file is part of mbed TLS (https://tls.mbed.org)
elessair	0:f269e3021894	20	*/
elessair	0:f269e3021894	21
elessair	0:f269e3021894	22	/*
elessair	0:f269e3021894	23	* References:
elessair	0:f269e3021894	24	*
elessair	0:f269e3021894	25	* SEC1 http://www.secg.org/index.php?action=secg,docs_secg
elessair	0:f269e3021894	26	* GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
elessair	0:f269e3021894	27	* FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
elessair	0:f269e3021894	28	* RFC 4492 for the related TLS structures and constants
elessair	0:f269e3021894	29	*
elessair	0:f269e3021894	30	* [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
elessair	0:f269e3021894	31	*
elessair	0:f269e3021894	32	* [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
elessair	0:f269e3021894	33	* for elliptic curve cryptosystems. In : Cryptographic Hardware and
elessair	0:f269e3021894	34	* Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
elessair	0:f269e3021894	35	* <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
elessair	0:f269e3021894	36	*
elessair	0:f269e3021894	37	* [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
elessair	0:f269e3021894	38	* render ECC resistant against Side Channel Attacks. IACR Cryptology
elessair	0:f269e3021894	39	* ePrint Archive, 2004, vol. 2004, p. 342.
elessair	0:f269e3021894	40	* <http://eprint.iacr.org/2004/342.pdf>
elessair	0:f269e3021894	41	*/
elessair	0:f269e3021894	42
elessair	0:f269e3021894	43	#if !defined(MBEDTLS_CONFIG_FILE)
elessair	0:f269e3021894	44	#include "mbedtls/config.h"
elessair	0:f269e3021894	45	#else
elessair	0:f269e3021894	46	#include MBEDTLS_CONFIG_FILE
elessair	0:f269e3021894	47	#endif
elessair	0:f269e3021894	48
elessair	0:f269e3021894	49	#if defined(MBEDTLS_ECP_C)
elessair	0:f269e3021894	50
elessair	0:f269e3021894	51	#include "mbedtls/ecp.h"
elessair	0:f269e3021894	52
elessair	0:f269e3021894	53	#include <string.h>
elessair	0:f269e3021894	54
elessair	0:f269e3021894	55	#if defined(MBEDTLS_PLATFORM_C)
elessair	0:f269e3021894	56	#include "mbedtls/platform.h"
elessair	0:f269e3021894	57	#else
elessair	0:f269e3021894	58	#include <stdlib.h>
elessair	0:f269e3021894	59	#include <stdio.h>
elessair	0:f269e3021894	60	#define mbedtls_printf printf
elessair	0:f269e3021894	61	#define mbedtls_calloc calloc
elessair	0:f269e3021894	62	#define mbedtls_free free
elessair	0:f269e3021894	63	#endif
elessair	0:f269e3021894	64
elessair	0:f269e3021894	65	#if ( defined(__ARMCC_VERSION) \|\| defined(_MSC_VER) ) && \
elessair	0:f269e3021894	66	!defined(inline) && !defined(__cplusplus)
elessair	0:f269e3021894	67	#define inline __inline
elessair	0:f269e3021894	68	#endif
elessair	0:f269e3021894	69
elessair	0:f269e3021894	70	/* Implementation that should never be optimized out by the compiler */
elessair	0:f269e3021894	71	static void mbedtls_zeroize( void *v, size_t n ) {
elessair	0:f269e3021894	72	volatile unsigned char p = v; while( n-- ) p++ = 0;
elessair	0:f269e3021894	73	}
elessair	0:f269e3021894	74
elessair	0:f269e3021894	75	#if defined(MBEDTLS_SELF_TEST)
elessair	0:f269e3021894	76	/*
elessair	0:f269e3021894	77	* Counts of point addition and doubling, and field multiplications.
elessair	0:f269e3021894	78	* Used to test resistance of point multiplication to simple timing attacks.
elessair	0:f269e3021894	79	*/
elessair	0:f269e3021894	80	static unsigned long add_count, dbl_count, mul_count;
elessair	0:f269e3021894	81	#endif
elessair	0:f269e3021894	82
elessair	0:f269e3021894	83	#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) \|\| \
elessair	0:f269e3021894	84	defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) \|\| \
elessair	0:f269e3021894	85	defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) \|\| \
elessair	0:f269e3021894	86	defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) \|\| \
elessair	0:f269e3021894	87	defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) \|\| \
elessair	0:f269e3021894	88	defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) \|\| \
elessair	0:f269e3021894	89	defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) \|\| \
elessair	0:f269e3021894	90	defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) \|\| \
elessair	0:f269e3021894	91	defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) \|\| \
elessair	0:f269e3021894	92	defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) \|\| \
elessair	0:f269e3021894	93	defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
elessair	0:f269e3021894	94	#define ECP_SHORTWEIERSTRASS
elessair	0:f269e3021894	95	#endif
elessair	0:f269e3021894	96
elessair	0:f269e3021894	97	#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
elessair	0:f269e3021894	98	#define ECP_MONTGOMERY
elessair	0:f269e3021894	99	#endif
elessair	0:f269e3021894	100
elessair	0:f269e3021894	101	/*
elessair	0:f269e3021894	102	* Curve types: internal for now, might be exposed later
elessair	0:f269e3021894	103	*/
elessair	0:f269e3021894	104	typedef enum
elessair	0:f269e3021894	105	{
elessair	0:f269e3021894	106	ECP_TYPE_NONE = 0,
elessair	0:f269e3021894	107	ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
elessair	0:f269e3021894	108	ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
elessair	0:f269e3021894	109	} ecp_curve_type;
elessair	0:f269e3021894	110
elessair	0:f269e3021894	111	/*
elessair	0:f269e3021894	112	* List of supported curves:
elessair	0:f269e3021894	113	* - internal ID
elessair	0:f269e3021894	114	* - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
elessair	0:f269e3021894	115	* - size in bits
elessair	0:f269e3021894	116	* - readable name
elessair	0:f269e3021894	117	*
elessair	0:f269e3021894	118	* Curves are listed in order: largest curves first, and for a given size,
elessair	0:f269e3021894	119	* fastest curves first. This provides the default order for the SSL module.
elessair	0:f269e3021894	120	*
elessair	0:f269e3021894	121	* Reminder: update profiles in x509_crt.c when adding a new curves!
elessair	0:f269e3021894	122	*/
elessair	0:f269e3021894	123	static const mbedtls_ecp_curve_info ecp_supported_curves[] =
elessair	0:f269e3021894	124	{
elessair	0:f269e3021894	125	#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
elessair	0:f269e3021894	126	{ MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
elessair	0:f269e3021894	127	#endif
elessair	0:f269e3021894	128	#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
elessair	0:f269e3021894	129	{ MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
elessair	0:f269e3021894	130	#endif
elessair	0:f269e3021894	131	#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
elessair	0:f269e3021894	132	{ MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
elessair	0:f269e3021894	133	#endif
elessair	0:f269e3021894	134	#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
elessair	0:f269e3021894	135	{ MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
elessair	0:f269e3021894	136	#endif
elessair	0:f269e3021894	137	#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
elessair	0:f269e3021894	138	{ MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
elessair	0:f269e3021894	139	#endif
elessair	0:f269e3021894	140	#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
elessair	0:f269e3021894	141	{ MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
elessair	0:f269e3021894	142	#endif
elessair	0:f269e3021894	143	#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
elessair	0:f269e3021894	144	{ MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
elessair	0:f269e3021894	145	#endif
elessair	0:f269e3021894	146	#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
elessair	0:f269e3021894	147	{ MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
elessair	0:f269e3021894	148	#endif
elessair	0:f269e3021894	149	#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
elessair	0:f269e3021894	150	{ MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
elessair	0:f269e3021894	151	#endif
elessair	0:f269e3021894	152	#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
elessair	0:f269e3021894	153	{ MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
elessair	0:f269e3021894	154	#endif
elessair	0:f269e3021894	155	#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
elessair	0:f269e3021894	156	{ MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
elessair	0:f269e3021894	157	#endif
elessair	0:f269e3021894	158	{ MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
elessair	0:f269e3021894	159	};
elessair	0:f269e3021894	160
elessair	0:f269e3021894	161	#define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
elessair	0:f269e3021894	162	sizeof( ecp_supported_curves[0] )
elessair	0:f269e3021894	163
elessair	0:f269e3021894	164	static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
elessair	0:f269e3021894	165
elessair	0:f269e3021894	166	/*
elessair	0:f269e3021894	167	* List of supported curves and associated info
elessair	0:f269e3021894	168	*/
elessair	0:f269e3021894	169	const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
elessair	0:f269e3021894	170	{
elessair	0:f269e3021894	171	return( ecp_supported_curves );
elessair	0:f269e3021894	172	}
elessair	0:f269e3021894	173
elessair	0:f269e3021894	174	/*
elessair	0:f269e3021894	175	* List of supported curves, group ID only
elessair	0:f269e3021894	176	*/
elessair	0:f269e3021894	177	const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
elessair	0:f269e3021894	178	{
elessair	0:f269e3021894	179	static int init_done = 0;
elessair	0:f269e3021894	180
elessair	0:f269e3021894	181	if( ! init_done )
elessair	0:f269e3021894	182	{
elessair	0:f269e3021894	183	size_t i = 0;
elessair	0:f269e3021894	184	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	185
elessair	0:f269e3021894	186	for( curve_info = mbedtls_ecp_curve_list();
elessair	0:f269e3021894	187	curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
elessair	0:f269e3021894	188	curve_info++ )
elessair	0:f269e3021894	189	{
elessair	0:f269e3021894	190	ecp_supported_grp_id[i++] = curve_info->grp_id;
elessair	0:f269e3021894	191	}
elessair	0:f269e3021894	192	ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
elessair	0:f269e3021894	193
elessair	0:f269e3021894	194	init_done = 1;
elessair	0:f269e3021894	195	}
elessair	0:f269e3021894	196
elessair	0:f269e3021894	197	return( ecp_supported_grp_id );
elessair	0:f269e3021894	198	}
elessair	0:f269e3021894	199
elessair	0:f269e3021894	200	/*
elessair	0:f269e3021894	201	* Get the curve info for the internal identifier
elessair	0:f269e3021894	202	*/
elessair	0:f269e3021894	203	const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
elessair	0:f269e3021894	204	{
elessair	0:f269e3021894	205	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	206
elessair	0:f269e3021894	207	for( curve_info = mbedtls_ecp_curve_list();
elessair	0:f269e3021894	208	curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
elessair	0:f269e3021894	209	curve_info++ )
elessair	0:f269e3021894	210	{
elessair	0:f269e3021894	211	if( curve_info->grp_id == grp_id )
elessair	0:f269e3021894	212	return( curve_info );
elessair	0:f269e3021894	213	}
elessair	0:f269e3021894	214
elessair	0:f269e3021894	215	return( NULL );
elessair	0:f269e3021894	216	}
elessair	0:f269e3021894	217
elessair	0:f269e3021894	218	/*
elessair	0:f269e3021894	219	* Get the curve info from the TLS identifier
elessair	0:f269e3021894	220	*/
elessair	0:f269e3021894	221	const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
elessair	0:f269e3021894	222	{
elessair	0:f269e3021894	223	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	224
elessair	0:f269e3021894	225	for( curve_info = mbedtls_ecp_curve_list();
elessair	0:f269e3021894	226	curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
elessair	0:f269e3021894	227	curve_info++ )
elessair	0:f269e3021894	228	{
elessair	0:f269e3021894	229	if( curve_info->tls_id == tls_id )
elessair	0:f269e3021894	230	return( curve_info );
elessair	0:f269e3021894	231	}
elessair	0:f269e3021894	232
elessair	0:f269e3021894	233	return( NULL );
elessair	0:f269e3021894	234	}
elessair	0:f269e3021894	235
elessair	0:f269e3021894	236	/*
elessair	0:f269e3021894	237	* Get the curve info from the name
elessair	0:f269e3021894	238	*/
elessair	0:f269e3021894	239	const mbedtls_ecp_curve_info mbedtls_ecp_curve_info_from_name( const char name )
elessair	0:f269e3021894	240	{
elessair	0:f269e3021894	241	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	242
elessair	0:f269e3021894	243	for( curve_info = mbedtls_ecp_curve_list();
elessair	0:f269e3021894	244	curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
elessair	0:f269e3021894	245	curve_info++ )
elessair	0:f269e3021894	246	{
elessair	0:f269e3021894	247	if( strcmp( curve_info->name, name ) == 0 )
elessair	0:f269e3021894	248	return( curve_info );
elessair	0:f269e3021894	249	}
elessair	0:f269e3021894	250
elessair	0:f269e3021894	251	return( NULL );
elessair	0:f269e3021894	252	}
elessair	0:f269e3021894	253
elessair	0:f269e3021894	254	/*
elessair	0:f269e3021894	255	* Get the type of a curve
elessair	0:f269e3021894	256	*/
elessair	0:f269e3021894	257	static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
elessair	0:f269e3021894	258	{
elessair	0:f269e3021894	259	if( grp->G.X.p == NULL )
elessair	0:f269e3021894	260	return( ECP_TYPE_NONE );
elessair	0:f269e3021894	261
elessair	0:f269e3021894	262	if( grp->G.Y.p == NULL )
elessair	0:f269e3021894	263	return( ECP_TYPE_MONTGOMERY );
elessair	0:f269e3021894	264	else
elessair	0:f269e3021894	265	return( ECP_TYPE_SHORT_WEIERSTRASS );
elessair	0:f269e3021894	266	}
elessair	0:f269e3021894	267
elessair	0:f269e3021894	268	/*
elessair	0:f269e3021894	269	* Initialize (the components of) a point
elessair	0:f269e3021894	270	*/
elessair	0:f269e3021894	271	void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
elessair	0:f269e3021894	272	{
elessair	0:f269e3021894	273	if( pt == NULL )
elessair	0:f269e3021894	274	return;
elessair	0:f269e3021894	275
elessair	0:f269e3021894	276	mbedtls_mpi_init( &pt->X );
elessair	0:f269e3021894	277	mbedtls_mpi_init( &pt->Y );
elessair	0:f269e3021894	278	mbedtls_mpi_init( &pt->Z );
elessair	0:f269e3021894	279	}
elessair	0:f269e3021894	280
elessair	0:f269e3021894	281	/*
elessair	0:f269e3021894	282	* Initialize (the components of) a group
elessair	0:f269e3021894	283	*/
elessair	0:f269e3021894	284	void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
elessair	0:f269e3021894	285	{
elessair	0:f269e3021894	286	if( grp == NULL )
elessair	0:f269e3021894	287	return;
elessair	0:f269e3021894	288
elessair	0:f269e3021894	289	memset( grp, 0, sizeof( mbedtls_ecp_group ) );
elessair	0:f269e3021894	290	}
elessair	0:f269e3021894	291
elessair	0:f269e3021894	292	/*
elessair	0:f269e3021894	293	* Initialize (the components of) a key pair
elessair	0:f269e3021894	294	*/
elessair	0:f269e3021894	295	void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
elessair	0:f269e3021894	296	{
elessair	0:f269e3021894	297	if( key == NULL )
elessair	0:f269e3021894	298	return;
elessair	0:f269e3021894	299
elessair	0:f269e3021894	300	mbedtls_ecp_group_init( &key->grp );
elessair	0:f269e3021894	301	mbedtls_mpi_init( &key->d );
elessair	0:f269e3021894	302	mbedtls_ecp_point_init( &key->Q );
elessair	0:f269e3021894	303	}
elessair	0:f269e3021894	304
elessair	0:f269e3021894	305	/*
elessair	0:f269e3021894	306	* Unallocate (the components of) a point
elessair	0:f269e3021894	307	*/
elessair	0:f269e3021894	308	void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
elessair	0:f269e3021894	309	{
elessair	0:f269e3021894	310	if( pt == NULL )
elessair	0:f269e3021894	311	return;
elessair	0:f269e3021894	312
elessair	0:f269e3021894	313	mbedtls_mpi_free( &( pt->X ) );
elessair	0:f269e3021894	314	mbedtls_mpi_free( &( pt->Y ) );
elessair	0:f269e3021894	315	mbedtls_mpi_free( &( pt->Z ) );
elessair	0:f269e3021894	316	}
elessair	0:f269e3021894	317
elessair	0:f269e3021894	318	/*
elessair	0:f269e3021894	319	* Unallocate (the components of) a group
elessair	0:f269e3021894	320	*/
elessair	0:f269e3021894	321	void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
elessair	0:f269e3021894	322	{
elessair	0:f269e3021894	323	size_t i;
elessair	0:f269e3021894	324
elessair	0:f269e3021894	325	if( grp == NULL )
elessair	0:f269e3021894	326	return;
elessair	0:f269e3021894	327
elessair	0:f269e3021894	328	if( grp->h != 1 )
elessair	0:f269e3021894	329	{
elessair	0:f269e3021894	330	mbedtls_mpi_free( &grp->P );
elessair	0:f269e3021894	331	mbedtls_mpi_free( &grp->A );
elessair	0:f269e3021894	332	mbedtls_mpi_free( &grp->B );
elessair	0:f269e3021894	333	mbedtls_ecp_point_free( &grp->G );
elessair	0:f269e3021894	334	mbedtls_mpi_free( &grp->N );
elessair	0:f269e3021894	335	}
elessair	0:f269e3021894	336
elessair	0:f269e3021894	337	if( grp->T != NULL )
elessair	0:f269e3021894	338	{
elessair	0:f269e3021894	339	for( i = 0; i < grp->T_size; i++ )
elessair	0:f269e3021894	340	mbedtls_ecp_point_free( &grp->T[i] );
elessair	0:f269e3021894	341	mbedtls_free( grp->T );
elessair	0:f269e3021894	342	}
elessair	0:f269e3021894	343
elessair	0:f269e3021894	344	mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
elessair	0:f269e3021894	345	}
elessair	0:f269e3021894	346
elessair	0:f269e3021894	347	/*
elessair	0:f269e3021894	348	* Unallocate (the components of) a key pair
elessair	0:f269e3021894	349	*/
elessair	0:f269e3021894	350	void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
elessair	0:f269e3021894	351	{
elessair	0:f269e3021894	352	if( key == NULL )
elessair	0:f269e3021894	353	return;
elessair	0:f269e3021894	354
elessair	0:f269e3021894	355	mbedtls_ecp_group_free( &key->grp );
elessair	0:f269e3021894	356	mbedtls_mpi_free( &key->d );
elessair	0:f269e3021894	357	mbedtls_ecp_point_free( &key->Q );
elessair	0:f269e3021894	358	}
elessair	0:f269e3021894	359
elessair	0:f269e3021894	360	/*
elessair	0:f269e3021894	361	* Copy the contents of a point
elessair	0:f269e3021894	362	*/
elessair	0:f269e3021894	363	int mbedtls_ecp_copy( mbedtls_ecp_point P, const mbedtls_ecp_point Q )
elessair	0:f269e3021894	364	{
elessair	0:f269e3021894	365	int ret;
elessair	0:f269e3021894	366
elessair	0:f269e3021894	367	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
elessair	0:f269e3021894	368	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
elessair	0:f269e3021894	369	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
elessair	0:f269e3021894	370
elessair	0:f269e3021894	371	cleanup:
elessair	0:f269e3021894	372	return( ret );
elessair	0:f269e3021894	373	}
elessair	0:f269e3021894	374
elessair	0:f269e3021894	375	/*
elessair	0:f269e3021894	376	* Copy the contents of a group object
elessair	0:f269e3021894	377	*/
elessair	0:f269e3021894	378	int mbedtls_ecp_group_copy( mbedtls_ecp_group dst, const mbedtls_ecp_group src )
elessair	0:f269e3021894	379	{
elessair	0:f269e3021894	380	return mbedtls_ecp_group_load( dst, src->id );
elessair	0:f269e3021894	381	}
elessair	0:f269e3021894	382
elessair	0:f269e3021894	383	/*
elessair	0:f269e3021894	384	* Set point to zero
elessair	0:f269e3021894	385	*/
elessair	0:f269e3021894	386	int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
elessair	0:f269e3021894	387	{
elessair	0:f269e3021894	388	int ret;
elessair	0:f269e3021894	389
elessair	0:f269e3021894	390	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
elessair	0:f269e3021894	391	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
elessair	0:f269e3021894	392	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
elessair	0:f269e3021894	393
elessair	0:f269e3021894	394	cleanup:
elessair	0:f269e3021894	395	return( ret );
elessair	0:f269e3021894	396	}
elessair	0:f269e3021894	397
elessair	0:f269e3021894	398	/*
elessair	0:f269e3021894	399	* Tell if a point is zero
elessair	0:f269e3021894	400	*/
elessair	0:f269e3021894	401	int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
elessair	0:f269e3021894	402	{
elessair	0:f269e3021894	403	return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
elessair	0:f269e3021894	404	}
elessair	0:f269e3021894	405
elessair	0:f269e3021894	406	/*
elessair	0:f269e3021894	407	* Compare two points lazyly
elessair	0:f269e3021894	408	*/
elessair	0:f269e3021894	409	int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
elessair	0:f269e3021894	410	const mbedtls_ecp_point *Q )
elessair	0:f269e3021894	411	{
elessair	0:f269e3021894	412	if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
elessair	0:f269e3021894	413	mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
elessair	0:f269e3021894	414	mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
elessair	0:f269e3021894	415	{
elessair	0:f269e3021894	416	return( 0 );
elessair	0:f269e3021894	417	}
elessair	0:f269e3021894	418
elessair	0:f269e3021894	419	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	420	}
elessair	0:f269e3021894	421
elessair	0:f269e3021894	422	/*
elessair	0:f269e3021894	423	* Import a non-zero point from ASCII strings
elessair	0:f269e3021894	424	*/
elessair	0:f269e3021894	425	int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
elessair	0:f269e3021894	426	const char x, const char y )
elessair	0:f269e3021894	427	{
elessair	0:f269e3021894	428	int ret;
elessair	0:f269e3021894	429
elessair	0:f269e3021894	430	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
elessair	0:f269e3021894	431	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
elessair	0:f269e3021894	432	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
elessair	0:f269e3021894	433
elessair	0:f269e3021894	434	cleanup:
elessair	0:f269e3021894	435	return( ret );
elessair	0:f269e3021894	436	}
elessair	0:f269e3021894	437
elessair	0:f269e3021894	438	/*
elessair	0:f269e3021894	439	* Export a point into unsigned binary data (SEC1 2.3.3)
elessair	0:f269e3021894	440	*/
elessair	0:f269e3021894	441	int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group grp, const mbedtls_ecp_point P,
elessair	0:f269e3021894	442	int format, size_t *olen,
elessair	0:f269e3021894	443	unsigned char *buf, size_t buflen )
elessair	0:f269e3021894	444	{
elessair	0:f269e3021894	445	int ret = 0;
elessair	0:f269e3021894	446	size_t plen;
elessair	0:f269e3021894	447
elessair	0:f269e3021894	448	if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
elessair	0:f269e3021894	449	format != MBEDTLS_ECP_PF_COMPRESSED )
elessair	0:f269e3021894	450	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	451
elessair	0:f269e3021894	452	/*
elessair	0:f269e3021894	453	* Common case: P == 0
elessair	0:f269e3021894	454	*/
elessair	0:f269e3021894	455	if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
elessair	0:f269e3021894	456	{
elessair	0:f269e3021894	457	if( buflen < 1 )
elessair	0:f269e3021894	458	return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
elessair	0:f269e3021894	459
elessair	0:f269e3021894	460	buf[0] = 0x00;
elessair	0:f269e3021894	461	*olen = 1;
elessair	0:f269e3021894	462
elessair	0:f269e3021894	463	return( 0 );
elessair	0:f269e3021894	464	}
elessair	0:f269e3021894	465
elessair	0:f269e3021894	466	plen = mbedtls_mpi_size( &grp->P );
elessair	0:f269e3021894	467
elessair	0:f269e3021894	468	if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
elessair	0:f269e3021894	469	{
elessair	0:f269e3021894	470	olen = 2 plen + 1;
elessair	0:f269e3021894	471
elessair	0:f269e3021894	472	if( buflen < *olen )
elessair	0:f269e3021894	473	return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
elessair	0:f269e3021894	474
elessair	0:f269e3021894	475	buf[0] = 0x04;
elessair	0:f269e3021894	476	MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
elessair	0:f269e3021894	477	MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
elessair	0:f269e3021894	478	}
elessair	0:f269e3021894	479	else if( format == MBEDTLS_ECP_PF_COMPRESSED )
elessair	0:f269e3021894	480	{
elessair	0:f269e3021894	481	*olen = plen + 1;
elessair	0:f269e3021894	482
elessair	0:f269e3021894	483	if( buflen < *olen )
elessair	0:f269e3021894	484	return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
elessair	0:f269e3021894	485
elessair	0:f269e3021894	486	buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
elessair	0:f269e3021894	487	MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
elessair	0:f269e3021894	488	}
elessair	0:f269e3021894	489
elessair	0:f269e3021894	490	cleanup:
elessair	0:f269e3021894	491	return( ret );
elessair	0:f269e3021894	492	}
elessair	0:f269e3021894	493
elessair	0:f269e3021894	494	/*
elessair	0:f269e3021894	495	* Import a point from unsigned binary data (SEC1 2.3.4)
elessair	0:f269e3021894	496	*/
elessair	0:f269e3021894	497	int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group grp, mbedtls_ecp_point pt,
elessair	0:f269e3021894	498	const unsigned char *buf, size_t ilen )
elessair	0:f269e3021894	499	{
elessair	0:f269e3021894	500	int ret;
elessair	0:f269e3021894	501	size_t plen;
elessair	0:f269e3021894	502
elessair	0:f269e3021894	503	if( ilen < 1 )
elessair	0:f269e3021894	504	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	505
elessair	0:f269e3021894	506	if( buf[0] == 0x00 )
elessair	0:f269e3021894	507	{
elessair	0:f269e3021894	508	if( ilen == 1 )
elessair	0:f269e3021894	509	return( mbedtls_ecp_set_zero( pt ) );
elessair	0:f269e3021894	510	else
elessair	0:f269e3021894	511	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	512	}
elessair	0:f269e3021894	513
elessair	0:f269e3021894	514	plen = mbedtls_mpi_size( &grp->P );
elessair	0:f269e3021894	515
elessair	0:f269e3021894	516	if( buf[0] != 0x04 )
elessair	0:f269e3021894	517	return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
elessair	0:f269e3021894	518
elessair	0:f269e3021894	519	if( ilen != 2 * plen + 1 )
elessair	0:f269e3021894	520	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	521
elessair	0:f269e3021894	522	MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
elessair	0:f269e3021894	523	MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
elessair	0:f269e3021894	524	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
elessair	0:f269e3021894	525
elessair	0:f269e3021894	526	cleanup:
elessair	0:f269e3021894	527	return( ret );
elessair	0:f269e3021894	528	}
elessair	0:f269e3021894	529
elessair	0:f269e3021894	530	/*
elessair	0:f269e3021894	531	* Import a point from a TLS ECPoint record (RFC 4492)
elessair	0:f269e3021894	532	* struct {
elessair	0:f269e3021894	533	* opaque point <1..2^8-1>;
elessair	0:f269e3021894	534	* } ECPoint;
elessair	0:f269e3021894	535	*/
elessair	0:f269e3021894	536	int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group grp, mbedtls_ecp_point pt,
elessair	0:f269e3021894	537	const unsigned char **buf, size_t buf_len )
elessair	0:f269e3021894	538	{
elessair	0:f269e3021894	539	unsigned char data_len;
elessair	0:f269e3021894	540	const unsigned char *buf_start;
elessair	0:f269e3021894	541
elessair	0:f269e3021894	542	/*
elessair	0:f269e3021894	543	* We must have at least two bytes (1 for length, at least one for data)
elessair	0:f269e3021894	544	*/
elessair	0:f269e3021894	545	if( buf_len < 2 )
elessair	0:f269e3021894	546	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	547
elessair	0:f269e3021894	548	data_len = (buf)++;
elessair	0:f269e3021894	549	if( data_len < 1 \|\| data_len > buf_len - 1 )
elessair	0:f269e3021894	550	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	551
elessair	0:f269e3021894	552	/*
elessair	0:f269e3021894	553	* Save buffer start for read_binary and update buf
elessair	0:f269e3021894	554	*/
elessair	0:f269e3021894	555	buf_start = *buf;
elessair	0:f269e3021894	556	*buf += data_len;
elessair	0:f269e3021894	557
elessair	0:f269e3021894	558	return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
elessair	0:f269e3021894	559	}
elessair	0:f269e3021894	560
elessair	0:f269e3021894	561	/*
elessair	0:f269e3021894	562	* Export a point as a TLS ECPoint record (RFC 4492)
elessair	0:f269e3021894	563	* struct {
elessair	0:f269e3021894	564	* opaque point <1..2^8-1>;
elessair	0:f269e3021894	565	* } ECPoint;
elessair	0:f269e3021894	566	*/
elessair	0:f269e3021894	567	int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group grp, const mbedtls_ecp_point pt,
elessair	0:f269e3021894	568	int format, size_t *olen,
elessair	0:f269e3021894	569	unsigned char *buf, size_t blen )
elessair	0:f269e3021894	570	{
elessair	0:f269e3021894	571	int ret;
elessair	0:f269e3021894	572
elessair	0:f269e3021894	573	/*
elessair	0:f269e3021894	574	* buffer length must be at least one, for our length byte
elessair	0:f269e3021894	575	*/
elessair	0:f269e3021894	576	if( blen < 1 )
elessair	0:f269e3021894	577	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	578
elessair	0:f269e3021894	579	if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
elessair	0:f269e3021894	580	olen, buf + 1, blen - 1) ) != 0 )
elessair	0:f269e3021894	581	return( ret );
elessair	0:f269e3021894	582
elessair	0:f269e3021894	583	/*
elessair	0:f269e3021894	584	* write length to the first byte and update total length
elessair	0:f269e3021894	585	*/
elessair	0:f269e3021894	586	buf[0] = (unsigned char) *olen;
elessair	0:f269e3021894	587	++*olen;
elessair	0:f269e3021894	588
elessair	0:f269e3021894	589	return( 0 );
elessair	0:f269e3021894	590	}
elessair	0:f269e3021894	591
elessair	0:f269e3021894	592	/*
elessair	0:f269e3021894	593	* Set a group from an ECParameters record (RFC 4492)
elessair	0:f269e3021894	594	*/
elessair	0:f269e3021894	595	int mbedtls_ecp_tls_read_group( mbedtls_ecp_group grp, const unsigned char *buf, size_t len )
elessair	0:f269e3021894	596	{
elessair	0:f269e3021894	597	uint16_t tls_id;
elessair	0:f269e3021894	598	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	599
elessair	0:f269e3021894	600	/*
elessair	0:f269e3021894	601	* We expect at least three bytes (see below)
elessair	0:f269e3021894	602	*/
elessair	0:f269e3021894	603	if( len < 3 )
elessair	0:f269e3021894	604	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	605
elessair	0:f269e3021894	606	/*
elessair	0:f269e3021894	607	* First byte is curve_type; only named_curve is handled
elessair	0:f269e3021894	608	*/
elessair	0:f269e3021894	609	if( (buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
elessair	0:f269e3021894	610	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	611
elessair	0:f269e3021894	612	/*
elessair	0:f269e3021894	613	* Next two bytes are the namedcurve value
elessair	0:f269e3021894	614	*/
elessair	0:f269e3021894	615	tls_id = (buf)++;
elessair	0:f269e3021894	616	tls_id <<= 8;
elessair	0:f269e3021894	617	tls_id \|= (buf)++;
elessair	0:f269e3021894	618
elessair	0:f269e3021894	619	if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
elessair	0:f269e3021894	620	return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
elessair	0:f269e3021894	621
elessair	0:f269e3021894	622	return mbedtls_ecp_group_load( grp, curve_info->grp_id );
elessair	0:f269e3021894	623	}
elessair	0:f269e3021894	624
elessair	0:f269e3021894	625	/*
elessair	0:f269e3021894	626	* Write the ECParameters record corresponding to a group (RFC 4492)
elessair	0:f269e3021894	627	*/
elessair	0:f269e3021894	628	int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group grp, size_t olen,
elessair	0:f269e3021894	629	unsigned char *buf, size_t blen )
elessair	0:f269e3021894	630	{
elessair	0:f269e3021894	631	const mbedtls_ecp_curve_info *curve_info;
elessair	0:f269e3021894	632
elessair	0:f269e3021894	633	if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
elessair	0:f269e3021894	634	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	635
elessair	0:f269e3021894	636	/*
elessair	0:f269e3021894	637	* We are going to write 3 bytes (see below)
elessair	0:f269e3021894	638	*/
elessair	0:f269e3021894	639	*olen = 3;
elessair	0:f269e3021894	640	if( blen < *olen )
elessair	0:f269e3021894	641	return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
elessair	0:f269e3021894	642
elessair	0:f269e3021894	643	/*
elessair	0:f269e3021894	644	* First byte is curve_type, always named_curve
elessair	0:f269e3021894	645	*/
elessair	0:f269e3021894	646	*buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
elessair	0:f269e3021894	647
elessair	0:f269e3021894	648	/*
elessair	0:f269e3021894	649	* Next two bytes are the namedcurve value
elessair	0:f269e3021894	650	*/
elessair	0:f269e3021894	651	buf[0] = curve_info->tls_id >> 8;
elessair	0:f269e3021894	652	buf[1] = curve_info->tls_id & 0xFF;
elessair	0:f269e3021894	653
elessair	0:f269e3021894	654	return( 0 );
elessair	0:f269e3021894	655	}
elessair	0:f269e3021894	656
elessair	0:f269e3021894	657	/*
elessair	0:f269e3021894	658	* Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
elessair	0:f269e3021894	659	* See the documentation of struct mbedtls_ecp_group.
elessair	0:f269e3021894	660	*
elessair	0:f269e3021894	661	* This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
elessair	0:f269e3021894	662	*/
elessair	0:f269e3021894	663	static int ecp_modp( mbedtls_mpi N, const mbedtls_ecp_group grp )
elessair	0:f269e3021894	664	{
elessair	0:f269e3021894	665	int ret;
elessair	0:f269e3021894	666
elessair	0:f269e3021894	667	if( grp->modp == NULL )
elessair	0:f269e3021894	668	return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
elessair	0:f269e3021894	669
elessair	0:f269e3021894	670	/* N->s < 0 is a much faster test, which fails only if N is 0 */
elessair	0:f269e3021894	671	if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) \|\|
elessair	0:f269e3021894	672	mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
elessair	0:f269e3021894	673	{
elessair	0:f269e3021894	674	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	675	}
elessair	0:f269e3021894	676
elessair	0:f269e3021894	677	MBEDTLS_MPI_CHK( grp->modp( N ) );
elessair	0:f269e3021894	678
elessair	0:f269e3021894	679	/* N->s < 0 is a much faster test, which fails only if N is 0 */
elessair	0:f269e3021894	680	while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
elessair	0:f269e3021894	681	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
elessair	0:f269e3021894	682
elessair	0:f269e3021894	683	while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
elessair	0:f269e3021894	684	/* we known P, N and the result are positive */
elessair	0:f269e3021894	685	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
elessair	0:f269e3021894	686
elessair	0:f269e3021894	687	cleanup:
elessair	0:f269e3021894	688	return( ret );
elessair	0:f269e3021894	689	}
elessair	0:f269e3021894	690
elessair	0:f269e3021894	691	/*
elessair	0:f269e3021894	692	* Fast mod-p functions expect their argument to be in the 0..p^2 range.
elessair	0:f269e3021894	693	*
elessair	0:f269e3021894	694	* In order to guarantee that, we need to ensure that operands of
elessair	0:f269e3021894	695	* mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
elessair	0:f269e3021894	696	* bring the result back to this range.
elessair	0:f269e3021894	697	*
elessair	0:f269e3021894	698	* The following macros are shortcuts for doing that.
elessair	0:f269e3021894	699	*/
elessair	0:f269e3021894	700
elessair	0:f269e3021894	701	/*
elessair	0:f269e3021894	702	* Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
elessair	0:f269e3021894	703	*/
elessair	0:f269e3021894	704	#if defined(MBEDTLS_SELF_TEST)
elessair	0:f269e3021894	705	#define INC_MUL_COUNT mul_count++;
elessair	0:f269e3021894	706	#else
elessair	0:f269e3021894	707	#define INC_MUL_COUNT
elessair	0:f269e3021894	708	#endif
elessair	0:f269e3021894	709
elessair	0:f269e3021894	710	#define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
elessair	0:f269e3021894	711	while( 0 )
elessair	0:f269e3021894	712
elessair	0:f269e3021894	713	/*
elessair	0:f269e3021894	714	* Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
elessair	0:f269e3021894	715	* N->s < 0 is a very fast test, which fails only if N is 0
elessair	0:f269e3021894	716	*/
elessair	0:f269e3021894	717	#define MOD_SUB( N ) \
elessair	0:f269e3021894	718	while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \
elessair	0:f269e3021894	719	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
elessair	0:f269e3021894	720
elessair	0:f269e3021894	721	/*
elessair	0:f269e3021894	722	* Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
elessair	0:f269e3021894	723	* We known P, N and the result are positive, so sub_abs is correct, and
elessair	0:f269e3021894	724	* a bit faster.
elessair	0:f269e3021894	725	*/
elessair	0:f269e3021894	726	#define MOD_ADD( N ) \
elessair	0:f269e3021894	727	while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
elessair	0:f269e3021894	728	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
elessair	0:f269e3021894	729
elessair	0:f269e3021894	730	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	731	/*
elessair	0:f269e3021894	732	* For curves in short Weierstrass form, we do all the internal operations in
elessair	0:f269e3021894	733	* Jacobian coordinates.
elessair	0:f269e3021894	734	*
elessair	0:f269e3021894	735	* For multiplication, we'll use a comb method with coutermeasueres against
elessair	0:f269e3021894	736	* SPA, hence timing attacks.
elessair	0:f269e3021894	737	*/
elessair	0:f269e3021894	738
elessair	0:f269e3021894	739	/*
elessair	0:f269e3021894	740	* Normalize jacobian coordinates so that Z == 0 \|\| Z == 1 (GECC 3.2.1)
elessair	0:f269e3021894	741	* Cost: 1N := 1I + 3M + 1S
elessair	0:f269e3021894	742	*/
elessair	0:f269e3021894	743	static int ecp_normalize_jac( const mbedtls_ecp_group grp, mbedtls_ecp_point pt )
elessair	0:f269e3021894	744	{
elessair	0:f269e3021894	745	int ret;
elessair	0:f269e3021894	746	mbedtls_mpi Zi, ZZi;
elessair	0:f269e3021894	747
elessair	0:f269e3021894	748	if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
elessair	0:f269e3021894	749	return( 0 );
elessair	0:f269e3021894	750
elessair	0:f269e3021894	751	mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
elessair	0:f269e3021894	752
elessair	0:f269e3021894	753	/*
elessair	0:f269e3021894	754	* X = X / Z^2 mod p
elessair	0:f269e3021894	755	*/
elessair	0:f269e3021894	756	MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
elessair	0:f269e3021894	757	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
elessair	0:f269e3021894	758	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
elessair	0:f269e3021894	759
elessair	0:f269e3021894	760	/*
elessair	0:f269e3021894	761	* Y = Y / Z^3 mod p
elessair	0:f269e3021894	762	*/
elessair	0:f269e3021894	763	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
elessair	0:f269e3021894	764	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
elessair	0:f269e3021894	765
elessair	0:f269e3021894	766	/*
elessair	0:f269e3021894	767	* Z = 1
elessair	0:f269e3021894	768	*/
elessair	0:f269e3021894	769	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
elessair	0:f269e3021894	770
elessair	0:f269e3021894	771	cleanup:
elessair	0:f269e3021894	772
elessair	0:f269e3021894	773	mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
elessair	0:f269e3021894	774
elessair	0:f269e3021894	775	return( ret );
elessair	0:f269e3021894	776	}
elessair	0:f269e3021894	777
elessair	0:f269e3021894	778	/*
elessair	0:f269e3021894	779	* Normalize jacobian coordinates of an array of (pointers to) points,
elessair	0:f269e3021894	780	* using Montgomery's trick to perform only one inversion mod P.
elessair	0:f269e3021894	781	* (See for example Cohen's "A Course in Computational Algebraic Number
elessair	0:f269e3021894	782	* Theory", Algorithm 10.3.4.)
elessair	0:f269e3021894	783	*
elessair	0:f269e3021894	784	* Warning: fails (returning an error) if one of the points is zero!
elessair	0:f269e3021894	785	* This should never happen, see choice of w in ecp_mul_comb().
elessair	0:f269e3021894	786	*
elessair	0:f269e3021894	787	* Cost: 1N(t) := 1I + (6t - 3)M + 1S
elessair	0:f269e3021894	788	*/
elessair	0:f269e3021894	789	static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
elessair	0:f269e3021894	790	mbedtls_ecp_point *T[], size_t t_len )
elessair	0:f269e3021894	791	{
elessair	0:f269e3021894	792	int ret;
elessair	0:f269e3021894	793	size_t i;
elessair	0:f269e3021894	794	mbedtls_mpi *c, u, Zi, ZZi;
elessair	0:f269e3021894	795
elessair	0:f269e3021894	796	if( t_len < 2 )
elessair	0:f269e3021894	797	return( ecp_normalize_jac( grp, *T ) );
elessair	0:f269e3021894	798
elessair	0:f269e3021894	799	if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
elessair	0:f269e3021894	800	return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
elessair	0:f269e3021894	801
elessair	0:f269e3021894	802	mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
elessair	0:f269e3021894	803
elessair	0:f269e3021894	804	/*
elessair	0:f269e3021894	805	* c[i] = Z_0 * ... * Z_i
elessair	0:f269e3021894	806	*/
elessair	0:f269e3021894	807	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
elessair	0:f269e3021894	808	for( i = 1; i < t_len; i++ )
elessair	0:f269e3021894	809	{
elessair	0:f269e3021894	810	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
elessair	0:f269e3021894	811	MOD_MUL( c[i] );
elessair	0:f269e3021894	812	}
elessair	0:f269e3021894	813
elessair	0:f269e3021894	814	/*
elessair	0:f269e3021894	815	* u = 1 / (Z_0 * ... * Z_n) mod P
elessair	0:f269e3021894	816	*/
elessair	0:f269e3021894	817	MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
elessair	0:f269e3021894	818
elessair	0:f269e3021894	819	for( i = t_len - 1; ; i-- )
elessair	0:f269e3021894	820	{
elessair	0:f269e3021894	821	/*
elessair	0:f269e3021894	822	* Zi = 1 / Z_i mod p
elessair	0:f269e3021894	823	* u = 1 / (Z_0 * ... * Z_i) mod P
elessair	0:f269e3021894	824	*/
elessair	0:f269e3021894	825	if( i == 0 ) {
elessair	0:f269e3021894	826	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
elessair	0:f269e3021894	827	}
elessair	0:f269e3021894	828	else
elessair	0:f269e3021894	829	{
elessair	0:f269e3021894	830	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
elessair	0:f269e3021894	831	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
elessair	0:f269e3021894	832	}
elessair	0:f269e3021894	833
elessair	0:f269e3021894	834	/*
elessair	0:f269e3021894	835	* proceed as in normalize()
elessair	0:f269e3021894	836	*/
elessair	0:f269e3021894	837	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
elessair	0:f269e3021894	838	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
elessair	0:f269e3021894	839	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
elessair	0:f269e3021894	840	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
elessair	0:f269e3021894	841
elessair	0:f269e3021894	842	/*
elessair	0:f269e3021894	843	* Post-precessing: reclaim some memory by shrinking coordinates
elessair	0:f269e3021894	844	* - not storing Z (always 1)
elessair	0:f269e3021894	845	* - shrinking other coordinates, but still keeping the same number of
elessair	0:f269e3021894	846	* limbs as P, as otherwise it will too likely be regrown too fast.
elessair	0:f269e3021894	847	*/
elessair	0:f269e3021894	848	MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
elessair	0:f269e3021894	849	MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
elessair	0:f269e3021894	850	mbedtls_mpi_free( &T[i]->Z );
elessair	0:f269e3021894	851
elessair	0:f269e3021894	852	if( i == 0 )
elessair	0:f269e3021894	853	break;
elessair	0:f269e3021894	854	}
elessair	0:f269e3021894	855
elessair	0:f269e3021894	856	cleanup:
elessair	0:f269e3021894	857
elessair	0:f269e3021894	858	mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
elessair	0:f269e3021894	859	for( i = 0; i < t_len; i++ )
elessair	0:f269e3021894	860	mbedtls_mpi_free( &c[i] );
elessair	0:f269e3021894	861	mbedtls_free( c );
elessair	0:f269e3021894	862
elessair	0:f269e3021894	863	return( ret );
elessair	0:f269e3021894	864	}
elessair	0:f269e3021894	865
elessair	0:f269e3021894	866	/*
elessair	0:f269e3021894	867	* Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
elessair	0:f269e3021894	868	* "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
elessair	0:f269e3021894	869	*/
elessair	0:f269e3021894	870	static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
elessair	0:f269e3021894	871	mbedtls_ecp_point *Q,
elessair	0:f269e3021894	872	unsigned char inv )
elessair	0:f269e3021894	873	{
elessair	0:f269e3021894	874	int ret;
elessair	0:f269e3021894	875	unsigned char nonzero;
elessair	0:f269e3021894	876	mbedtls_mpi mQY;
elessair	0:f269e3021894	877
elessair	0:f269e3021894	878	mbedtls_mpi_init( &mQY );
elessair	0:f269e3021894	879
elessair	0:f269e3021894	880	/* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
elessair	0:f269e3021894	881	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
elessair	0:f269e3021894	882	nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
elessair	0:f269e3021894	883	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
elessair	0:f269e3021894	884
elessair	0:f269e3021894	885	cleanup:
elessair	0:f269e3021894	886	mbedtls_mpi_free( &mQY );
elessair	0:f269e3021894	887
elessair	0:f269e3021894	888	return( ret );
elessair	0:f269e3021894	889	}
elessair	0:f269e3021894	890
elessair	0:f269e3021894	891	/*
elessair	0:f269e3021894	892	* Point doubling R = 2 P, Jacobian coordinates
elessair	0:f269e3021894	893	*
elessair	0:f269e3021894	894	* Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
elessair	0:f269e3021894	895	*
elessair	0:f269e3021894	896	* We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
elessair	0:f269e3021894	897	* (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
elessair	0:f269e3021894	898	*
elessair	0:f269e3021894	899	* Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
elessair	0:f269e3021894	900	*
elessair	0:f269e3021894	901	* Cost: 1D := 3M + 4S (A == 0)
elessair	0:f269e3021894	902	* 4M + 4S (A == -3)
elessair	0:f269e3021894	903	* 3M + 6S + 1a otherwise
elessair	0:f269e3021894	904	*/
elessair	0:f269e3021894	905	static int ecp_double_jac( const mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	906	const mbedtls_ecp_point *P )
elessair	0:f269e3021894	907	{
elessair	0:f269e3021894	908	int ret;
elessair	0:f269e3021894	909	mbedtls_mpi M, S, T, U;
elessair	0:f269e3021894	910
elessair	0:f269e3021894	911	#if defined(MBEDTLS_SELF_TEST)
elessair	0:f269e3021894	912	dbl_count++;
elessair	0:f269e3021894	913	#endif
elessair	0:f269e3021894	914
elessair	0:f269e3021894	915	mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
elessair	0:f269e3021894	916
elessair	0:f269e3021894	917	/* Special case for A = -3 */
elessair	0:f269e3021894	918	if( grp->A.p == NULL )
elessair	0:f269e3021894	919	{
elessair	0:f269e3021894	920	/* M = 3(X + Z^2)(X - Z^2) */
elessair	0:f269e3021894	921	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
elessair	0:f269e3021894	922	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T );
elessair	0:f269e3021894	923	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U );
elessair	0:f269e3021894	924	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S );
elessair	0:f269e3021894	925	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
elessair	0:f269e3021894	926	}
elessair	0:f269e3021894	927	else
elessair	0:f269e3021894	928	{
elessair	0:f269e3021894	929	/* M = 3.X^2 */
elessair	0:f269e3021894	930	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S );
elessair	0:f269e3021894	931	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
elessair	0:f269e3021894	932
elessair	0:f269e3021894	933	/* Optimize away for "koblitz" curves with A = 0 */
elessair	0:f269e3021894	934	if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
elessair	0:f269e3021894	935	{
elessair	0:f269e3021894	936	/* M += A.Z^4 */
elessair	0:f269e3021894	937	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
elessair	0:f269e3021894	938	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T );
elessair	0:f269e3021894	939	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S );
elessair	0:f269e3021894	940	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M );
elessair	0:f269e3021894	941	}
elessair	0:f269e3021894	942	}
elessair	0:f269e3021894	943
elessair	0:f269e3021894	944	/* S = 4.X.Y^2 */
elessair	0:f269e3021894	945	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T );
elessair	0:f269e3021894	946	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T );
elessair	0:f269e3021894	947	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S );
elessair	0:f269e3021894	948	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S );
elessair	0:f269e3021894	949
elessair	0:f269e3021894	950	/* U = 8.Y^4 */
elessair	0:f269e3021894	951	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U );
elessair	0:f269e3021894	952	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
elessair	0:f269e3021894	953
elessair	0:f269e3021894	954	/* T = M^2 - 2.S */
elessair	0:f269e3021894	955	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T );
elessair	0:f269e3021894	956	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
elessair	0:f269e3021894	957	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
elessair	0:f269e3021894	958
elessair	0:f269e3021894	959	/* S = M(S - T) - U */
elessair	0:f269e3021894	960	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S );
elessair	0:f269e3021894	961	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S );
elessair	0:f269e3021894	962	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S );
elessair	0:f269e3021894	963
elessair	0:f269e3021894	964	/* U = 2.Y.Z */
elessair	0:f269e3021894	965	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U );
elessair	0:f269e3021894	966	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
elessair	0:f269e3021894	967
elessair	0:f269e3021894	968	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
elessair	0:f269e3021894	969	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
elessair	0:f269e3021894	970	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
elessair	0:f269e3021894	971
elessair	0:f269e3021894	972	cleanup:
elessair	0:f269e3021894	973	mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
elessair	0:f269e3021894	974
elessair	0:f269e3021894	975	return( ret );
elessair	0:f269e3021894	976	}
elessair	0:f269e3021894	977
elessair	0:f269e3021894	978	/*
elessair	0:f269e3021894	979	* Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
elessair	0:f269e3021894	980	*
elessair	0:f269e3021894	981	* The coordinates of Q must be normalized (= affine),
elessair	0:f269e3021894	982	* but those of P don't need to. R is not normalized.
elessair	0:f269e3021894	983	*
elessair	0:f269e3021894	984	* Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
elessair	0:f269e3021894	985	* None of these cases can happen as intermediate step in ecp_mul_comb():
elessair	0:f269e3021894	986	* - at each step, P, Q and R are multiples of the base point, the factor
elessair	0:f269e3021894	987	* being less than its order, so none of them is zero;
elessair	0:f269e3021894	988	* - Q is an odd multiple of the base point, P an even multiple,
elessair	0:f269e3021894	989	* due to the choice of precomputed points in the modified comb method.
elessair	0:f269e3021894	990	* So branches for these cases do not leak secret information.
elessair	0:f269e3021894	991	*
elessair	0:f269e3021894	992	* We accept Q->Z being unset (saving memory in tables) as meaning 1.
elessair	0:f269e3021894	993	*
elessair	0:f269e3021894	994	* Cost: 1A := 8M + 3S
elessair	0:f269e3021894	995	*/
elessair	0:f269e3021894	996	static int ecp_add_mixed( const mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	997	const mbedtls_ecp_point P, const mbedtls_ecp_point Q )
elessair	0:f269e3021894	998	{
elessair	0:f269e3021894	999	int ret;
elessair	0:f269e3021894	1000	mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
elessair	0:f269e3021894	1001
elessair	0:f269e3021894	1002	#if defined(MBEDTLS_SELF_TEST)
elessair	0:f269e3021894	1003	add_count++;
elessair	0:f269e3021894	1004	#endif
elessair	0:f269e3021894	1005
elessair	0:f269e3021894	1006	/*
elessair	0:f269e3021894	1007	* Trivial cases: P == 0 or Q == 0 (case 1)
elessair	0:f269e3021894	1008	*/
elessair	0:f269e3021894	1009	if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
elessair	0:f269e3021894	1010	return( mbedtls_ecp_copy( R, Q ) );
elessair	0:f269e3021894	1011
elessair	0:f269e3021894	1012	if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
elessair	0:f269e3021894	1013	return( mbedtls_ecp_copy( R, P ) );
elessair	0:f269e3021894	1014
elessair	0:f269e3021894	1015	/*
elessair	0:f269e3021894	1016	* Make sure Q coordinates are normalized
elessair	0:f269e3021894	1017	*/
elessair	0:f269e3021894	1018	if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
elessair	0:f269e3021894	1019	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1020
elessair	0:f269e3021894	1021	mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
elessair	0:f269e3021894	1022	mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
elessair	0:f269e3021894	1023
elessair	0:f269e3021894	1024	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
elessair	0:f269e3021894	1025	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
elessair	0:f269e3021894	1026	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
elessair	0:f269e3021894	1027	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
elessair	0:f269e3021894	1028	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
elessair	0:f269e3021894	1029	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
elessair	0:f269e3021894	1030
elessair	0:f269e3021894	1031	/* Special cases (2) and (3) */
elessair	0:f269e3021894	1032	if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
elessair	0:f269e3021894	1033	{
elessair	0:f269e3021894	1034	if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
elessair	0:f269e3021894	1035	{
elessair	0:f269e3021894	1036	ret = ecp_double_jac( grp, R, P );
elessair	0:f269e3021894	1037	goto cleanup;
elessair	0:f269e3021894	1038	}
elessair	0:f269e3021894	1039	else
elessair	0:f269e3021894	1040	{
elessair	0:f269e3021894	1041	ret = mbedtls_ecp_set_zero( R );
elessair	0:f269e3021894	1042	goto cleanup;
elessair	0:f269e3021894	1043	}
elessair	0:f269e3021894	1044	}
elessair	0:f269e3021894	1045
elessair	0:f269e3021894	1046	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
elessair	0:f269e3021894	1047	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
elessair	0:f269e3021894	1048	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
elessair	0:f269e3021894	1049	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
elessair	0:f269e3021894	1050	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
elessair	0:f269e3021894	1051	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
elessair	0:f269e3021894	1052	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
elessair	0:f269e3021894	1053	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
elessair	0:f269e3021894	1054	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
elessair	0:f269e3021894	1055	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
elessair	0:f269e3021894	1056	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
elessair	0:f269e3021894	1057	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
elessair	0:f269e3021894	1058
elessair	0:f269e3021894	1059	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
elessair	0:f269e3021894	1060	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
elessair	0:f269e3021894	1061	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
elessair	0:f269e3021894	1062
elessair	0:f269e3021894	1063	cleanup:
elessair	0:f269e3021894	1064
elessair	0:f269e3021894	1065	mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
elessair	0:f269e3021894	1066	mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
elessair	0:f269e3021894	1067
elessair	0:f269e3021894	1068	return( ret );
elessair	0:f269e3021894	1069	}
elessair	0:f269e3021894	1070
elessair	0:f269e3021894	1071	/*
elessair	0:f269e3021894	1072	* Randomize jacobian coordinates:
elessair	0:f269e3021894	1073	* (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
elessair	0:f269e3021894	1074	* This is sort of the reverse operation of ecp_normalize_jac().
elessair	0:f269e3021894	1075	*
elessair	0:f269e3021894	1076	* This countermeasure was first suggested in [2].
elessair	0:f269e3021894	1077	*/
elessair	0:f269e3021894	1078	static int ecp_randomize_jac( const mbedtls_ecp_group grp, mbedtls_ecp_point pt,
elessair	0:f269e3021894	1079	int (f_rng)(void , unsigned char , size_t), void p_rng )
elessair	0:f269e3021894	1080	{
elessair	0:f269e3021894	1081	int ret;
elessair	0:f269e3021894	1082	mbedtls_mpi l, ll;
elessair	0:f269e3021894	1083	size_t p_size = ( grp->pbits + 7 ) / 8;
elessair	0:f269e3021894	1084	int count = 0;
elessair	0:f269e3021894	1085
elessair	0:f269e3021894	1086	mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
elessair	0:f269e3021894	1087
elessair	0:f269e3021894	1088	/* Generate l such that 1 < l < p */
elessair	0:f269e3021894	1089	do
elessair	0:f269e3021894	1090	{
elessair	0:f269e3021894	1091	mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng );
elessair	0:f269e3021894	1092
elessair	0:f269e3021894	1093	while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
elessair	0:f269e3021894	1094	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
elessair	0:f269e3021894	1095
elessair	0:f269e3021894	1096	if( count++ > 10 )
elessair	0:f269e3021894	1097	return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
elessair	0:f269e3021894	1098	}
elessair	0:f269e3021894	1099	while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
elessair	0:f269e3021894	1100
elessair	0:f269e3021894	1101	/* Z = l * Z */
elessair	0:f269e3021894	1102	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
elessair	0:f269e3021894	1103
elessair	0:f269e3021894	1104	/* X = l^2 * X */
elessair	0:f269e3021894	1105	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
elessair	0:f269e3021894	1106	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
elessair	0:f269e3021894	1107
elessair	0:f269e3021894	1108	/* Y = l^3 * Y */
elessair	0:f269e3021894	1109	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
elessair	0:f269e3021894	1110	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
elessair	0:f269e3021894	1111
elessair	0:f269e3021894	1112	cleanup:
elessair	0:f269e3021894	1113	mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
elessair	0:f269e3021894	1114
elessair	0:f269e3021894	1115	return( ret );
elessair	0:f269e3021894	1116	}
elessair	0:f269e3021894	1117
elessair	0:f269e3021894	1118	/*
elessair	0:f269e3021894	1119	* Check and define parameters used by the comb method (see below for details)
elessair	0:f269e3021894	1120	*/
elessair	0:f269e3021894	1121	#if MBEDTLS_ECP_WINDOW_SIZE < 2 \|\| MBEDTLS_ECP_WINDOW_SIZE > 7
elessair	0:f269e3021894	1122	#error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
elessair	0:f269e3021894	1123	#endif
elessair	0:f269e3021894	1124
elessair	0:f269e3021894	1125	/* d = ceil( n / w ) */
elessair	0:f269e3021894	1126	#define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
elessair	0:f269e3021894	1127
elessair	0:f269e3021894	1128	/* number of precomputed points */
elessair	0:f269e3021894	1129	#define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
elessair	0:f269e3021894	1130
elessair	0:f269e3021894	1131	/*
elessair	0:f269e3021894	1132	* Compute the representation of m that will be used with our comb method.
elessair	0:f269e3021894	1133	*
elessair	0:f269e3021894	1134	* The basic comb method is described in GECC 3.44 for example. We use a
elessair	0:f269e3021894	1135	* modified version that provides resistance to SPA by avoiding zero
elessair	0:f269e3021894	1136	* digits in the representation as in [3]. We modify the method further by
elessair	0:f269e3021894	1137	* requiring that all K_i be odd, which has the small cost that our
elessair	0:f269e3021894	1138	* representation uses one more K_i, due to carries.
elessair	0:f269e3021894	1139	*
elessair	0:f269e3021894	1140	* Also, for the sake of compactness, only the seven low-order bits of x[i]
elessair	0:f269e3021894	1141	* are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in
elessair	0:f269e3021894	1142	* the paper): it is set if and only if if s_i == -1;
elessair	0:f269e3021894	1143	*
elessair	0:f269e3021894	1144	* Calling conventions:
elessair	0:f269e3021894	1145	* - x is an array of size d + 1
elessair	0:f269e3021894	1146	* - w is the size, ie number of teeth, of the comb, and must be between
elessair	0:f269e3021894	1147	* 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
elessair	0:f269e3021894	1148	* - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
elessair	0:f269e3021894	1149	* (the result will be incorrect if these assumptions are not satisfied)
elessair	0:f269e3021894	1150	*/
elessair	0:f269e3021894	1151	static void ecp_comb_fixed( unsigned char x[], size_t d,
elessair	0:f269e3021894	1152	unsigned char w, const mbedtls_mpi *m )
elessair	0:f269e3021894	1153	{
elessair	0:f269e3021894	1154	size_t i, j;
elessair	0:f269e3021894	1155	unsigned char c, cc, adjust;
elessair	0:f269e3021894	1156
elessair	0:f269e3021894	1157	memset( x, 0, d+1 );
elessair	0:f269e3021894	1158
elessair	0:f269e3021894	1159	/* First get the classical comb values (except for x_d = 0) */
elessair	0:f269e3021894	1160	for( i = 0; i < d; i++ )
elessair	0:f269e3021894	1161	for( j = 0; j < w; j++ )
elessair	0:f269e3021894	1162	x[i] \|= mbedtls_mpi_get_bit( m, i + d * j ) << j;
elessair	0:f269e3021894	1163
elessair	0:f269e3021894	1164	/* Now make sure x_1 .. x_d are odd */
elessair	0:f269e3021894	1165	c = 0;
elessair	0:f269e3021894	1166	for( i = 1; i <= d; i++ )
elessair	0:f269e3021894	1167	{
elessair	0:f269e3021894	1168	/* Add carry and update it */
elessair	0:f269e3021894	1169	cc = x[i] & c;
elessair	0:f269e3021894	1170	x[i] = x[i] ^ c;
elessair	0:f269e3021894	1171	c = cc;
elessair	0:f269e3021894	1172
elessair	0:f269e3021894	1173	/* Adjust if needed, avoiding branches */
elessair	0:f269e3021894	1174	adjust = 1 - ( x[i] & 0x01 );
elessair	0:f269e3021894	1175	c \|= x[i] & ( x[i-1] * adjust );
elessair	0:f269e3021894	1176	x[i] = x[i] ^ ( x[i-1] * adjust );
elessair	0:f269e3021894	1177	x[i-1] \|= adjust << 7;
elessair	0:f269e3021894	1178	}
elessair	0:f269e3021894	1179	}
elessair	0:f269e3021894	1180
elessair	0:f269e3021894	1181	/*
elessair	0:f269e3021894	1182	* Precompute points for the comb method
elessair	0:f269e3021894	1183	*
elessair	0:f269e3021894	1184	* If i = i_{w-1} ... i_1 is the binary representation of i, then
elessair	0:f269e3021894	1185	* T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P
elessair	0:f269e3021894	1186	*
elessair	0:f269e3021894	1187	* T must be able to hold 2^{w - 1} elements
elessair	0:f269e3021894	1188	*
elessair	0:f269e3021894	1189	* Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
elessair	0:f269e3021894	1190	*/
elessair	0:f269e3021894	1191	static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
elessair	0:f269e3021894	1192	mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
elessair	0:f269e3021894	1193	unsigned char w, size_t d )
elessair	0:f269e3021894	1194	{
elessair	0:f269e3021894	1195	int ret;
elessair	0:f269e3021894	1196	unsigned char i, k;
elessair	0:f269e3021894	1197	size_t j;
elessair	0:f269e3021894	1198	mbedtls_ecp_point cur, TT[COMB_MAX_PRE - 1];
elessair	0:f269e3021894	1199
elessair	0:f269e3021894	1200	/*
elessair	0:f269e3021894	1201	* Set T[0] = P and
elessair	0:f269e3021894	1202	* T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
elessair	0:f269e3021894	1203	*/
elessair	0:f269e3021894	1204	MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
elessair	0:f269e3021894	1205
elessair	0:f269e3021894	1206	k = 0;
elessair	0:f269e3021894	1207	for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
elessair	0:f269e3021894	1208	{
elessair	0:f269e3021894	1209	cur = T + i;
elessair	0:f269e3021894	1210	MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
elessair	0:f269e3021894	1211	for( j = 0; j < d; j++ )
elessair	0:f269e3021894	1212	MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
elessair	0:f269e3021894	1213
elessair	0:f269e3021894	1214	TT[k++] = cur;
elessair	0:f269e3021894	1215	}
elessair	0:f269e3021894	1216
elessair	0:f269e3021894	1217	MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
elessair	0:f269e3021894	1218
elessair	0:f269e3021894	1219	/*
elessair	0:f269e3021894	1220	* Compute the remaining ones using the minimal number of additions
elessair	0:f269e3021894	1221	* Be careful to update T[2^l] only after using it!
elessair	0:f269e3021894	1222	*/
elessair	0:f269e3021894	1223	k = 0;
elessair	0:f269e3021894	1224	for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
elessair	0:f269e3021894	1225	{
elessair	0:f269e3021894	1226	j = i;
elessair	0:f269e3021894	1227	while( j-- )
elessair	0:f269e3021894	1228	{
elessair	0:f269e3021894	1229	MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
elessair	0:f269e3021894	1230	TT[k++] = &T[i + j];
elessair	0:f269e3021894	1231	}
elessair	0:f269e3021894	1232	}
elessair	0:f269e3021894	1233
elessair	0:f269e3021894	1234	MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
elessair	0:f269e3021894	1235
elessair	0:f269e3021894	1236	cleanup:
elessair	0:f269e3021894	1237	return( ret );
elessair	0:f269e3021894	1238	}
elessair	0:f269e3021894	1239
elessair	0:f269e3021894	1240	/*
elessair	0:f269e3021894	1241	* Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
elessair	0:f269e3021894	1242	*/
elessair	0:f269e3021894	1243	static int ecp_select_comb( const mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1244	const mbedtls_ecp_point T[], unsigned char t_len,
elessair	0:f269e3021894	1245	unsigned char i )
elessair	0:f269e3021894	1246	{
elessair	0:f269e3021894	1247	int ret;
elessair	0:f269e3021894	1248	unsigned char ii, j;
elessair	0:f269e3021894	1249
elessair	0:f269e3021894	1250	/* Ignore the "sign" bit and scale down */
elessair	0:f269e3021894	1251	ii = ( i & 0x7Fu ) >> 1;
elessair	0:f269e3021894	1252
elessair	0:f269e3021894	1253	/* Read the whole table to thwart cache-based timing attacks */
elessair	0:f269e3021894	1254	for( j = 0; j < t_len; j++ )
elessair	0:f269e3021894	1255	{
elessair	0:f269e3021894	1256	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
elessair	0:f269e3021894	1257	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
elessair	0:f269e3021894	1258	}
elessair	0:f269e3021894	1259
elessair	0:f269e3021894	1260	/* Safely invert result if i is "negative" */
elessair	0:f269e3021894	1261	MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
elessair	0:f269e3021894	1262
elessair	0:f269e3021894	1263	cleanup:
elessair	0:f269e3021894	1264	return( ret );
elessair	0:f269e3021894	1265	}
elessair	0:f269e3021894	1266
elessair	0:f269e3021894	1267	/*
elessair	0:f269e3021894	1268	* Core multiplication algorithm for the (modified) comb method.
elessair	0:f269e3021894	1269	* This part is actually common with the basic comb method (GECC 3.44)
elessair	0:f269e3021894	1270	*
elessair	0:f269e3021894	1271	* Cost: d A + d D + 1 R
elessair	0:f269e3021894	1272	*/
elessair	0:f269e3021894	1273	static int ecp_mul_comb_core( const mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1274	const mbedtls_ecp_point T[], unsigned char t_len,
elessair	0:f269e3021894	1275	const unsigned char x[], size_t d,
elessair	0:f269e3021894	1276	int (f_rng)(void , unsigned char *, size_t),
elessair	0:f269e3021894	1277	void *p_rng )
elessair	0:f269e3021894	1278	{
elessair	0:f269e3021894	1279	int ret;
elessair	0:f269e3021894	1280	mbedtls_ecp_point Txi;
elessair	0:f269e3021894	1281	size_t i;
elessair	0:f269e3021894	1282
elessair	0:f269e3021894	1283	mbedtls_ecp_point_init( &Txi );
elessair	0:f269e3021894	1284
elessair	0:f269e3021894	1285	/* Start with a non-zero point and randomize its coordinates */
elessair	0:f269e3021894	1286	i = d;
elessair	0:f269e3021894	1287	MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
elessair	0:f269e3021894	1288	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
elessair	0:f269e3021894	1289	if( f_rng != 0 )
elessair	0:f269e3021894	1290	MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
elessair	0:f269e3021894	1291
elessair	0:f269e3021894	1292	while( i-- != 0 )
elessair	0:f269e3021894	1293	{
elessair	0:f269e3021894	1294	MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
elessair	0:f269e3021894	1295	MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
elessair	0:f269e3021894	1296	MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
elessair	0:f269e3021894	1297	}
elessair	0:f269e3021894	1298
elessair	0:f269e3021894	1299	cleanup:
elessair	0:f269e3021894	1300	mbedtls_ecp_point_free( &Txi );
elessair	0:f269e3021894	1301
elessair	0:f269e3021894	1302	return( ret );
elessair	0:f269e3021894	1303	}
elessair	0:f269e3021894	1304
elessair	0:f269e3021894	1305	/*
elessair	0:f269e3021894	1306	* Multiplication using the comb method,
elessair	0:f269e3021894	1307	* for curves in short Weierstrass form
elessair	0:f269e3021894	1308	*/
elessair	0:f269e3021894	1309	static int ecp_mul_comb( mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1310	const mbedtls_mpi m, const mbedtls_ecp_point P,
elessair	0:f269e3021894	1311	int (f_rng)(void , unsigned char *, size_t),
elessair	0:f269e3021894	1312	void *p_rng )
elessair	0:f269e3021894	1313	{
elessair	0:f269e3021894	1314	int ret;
elessair	0:f269e3021894	1315	unsigned char w, m_is_odd, p_eq_g, pre_len, i;
elessair	0:f269e3021894	1316	size_t d;
elessair	0:f269e3021894	1317	unsigned char k[COMB_MAX_D + 1];
elessair	0:f269e3021894	1318	mbedtls_ecp_point *T;
elessair	0:f269e3021894	1319	mbedtls_mpi M, mm;
elessair	0:f269e3021894	1320
elessair	0:f269e3021894	1321	mbedtls_mpi_init( &M );
elessair	0:f269e3021894	1322	mbedtls_mpi_init( &mm );
elessair	0:f269e3021894	1323
elessair	0:f269e3021894	1324	/* we need N to be odd to trnaform m in an odd number, check now */
elessair	0:f269e3021894	1325	if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
elessair	0:f269e3021894	1326	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1327
elessair	0:f269e3021894	1328	/*
elessair	0:f269e3021894	1329	* Minimize the number of multiplications, that is minimize
elessair	0:f269e3021894	1330	* 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
elessair	0:f269e3021894	1331	* (see costs of the various parts, with 1S = 1M)
elessair	0:f269e3021894	1332	*/
elessair	0:f269e3021894	1333	w = grp->nbits >= 384 ? 5 : 4;
elessair	0:f269e3021894	1334
elessair	0:f269e3021894	1335	/*
elessair	0:f269e3021894	1336	* If P == G, pre-compute a bit more, since this may be re-used later.
elessair	0:f269e3021894	1337	* Just adding one avoids upping the cost of the first mul too much,
elessair	0:f269e3021894	1338	* and the memory cost too.
elessair	0:f269e3021894	1339	*/
elessair	0:f269e3021894	1340	#if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
elessair	0:f269e3021894	1341	p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
elessair	0:f269e3021894	1342	mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
elessair	0:f269e3021894	1343	if( p_eq_g )
elessair	0:f269e3021894	1344	w++;
elessair	0:f269e3021894	1345	#else
elessair	0:f269e3021894	1346	p_eq_g = 0;
elessair	0:f269e3021894	1347	#endif
elessair	0:f269e3021894	1348
elessair	0:f269e3021894	1349	/*
elessair	0:f269e3021894	1350	* Make sure w is within bounds.
elessair	0:f269e3021894	1351	* (The last test is useful only for very small curves in the test suite.)
elessair	0:f269e3021894	1352	*/
elessair	0:f269e3021894	1353	if( w > MBEDTLS_ECP_WINDOW_SIZE )
elessair	0:f269e3021894	1354	w = MBEDTLS_ECP_WINDOW_SIZE;
elessair	0:f269e3021894	1355	if( w >= grp->nbits )
elessair	0:f269e3021894	1356	w = 2;
elessair	0:f269e3021894	1357
elessair	0:f269e3021894	1358	/* Other sizes that depend on w */
elessair	0:f269e3021894	1359	pre_len = 1U << ( w - 1 );
elessair	0:f269e3021894	1360	d = ( grp->nbits + w - 1 ) / w;
elessair	0:f269e3021894	1361
elessair	0:f269e3021894	1362	/*
elessair	0:f269e3021894	1363	* Prepare precomputed points: if P == G we want to
elessair	0:f269e3021894	1364	* use grp->T if already initialized, or initialize it.
elessair	0:f269e3021894	1365	*/
elessair	0:f269e3021894	1366	T = p_eq_g ? grp->T : NULL;
elessair	0:f269e3021894	1367
elessair	0:f269e3021894	1368	if( T == NULL )
elessair	0:f269e3021894	1369	{
elessair	0:f269e3021894	1370	T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) );
elessair	0:f269e3021894	1371	if( T == NULL )
elessair	0:f269e3021894	1372	{
elessair	0:f269e3021894	1373	ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
elessair	0:f269e3021894	1374	goto cleanup;
elessair	0:f269e3021894	1375	}
elessair	0:f269e3021894	1376
elessair	0:f269e3021894	1377	MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
elessair	0:f269e3021894	1378
elessair	0:f269e3021894	1379	if( p_eq_g )
elessair	0:f269e3021894	1380	{
elessair	0:f269e3021894	1381	grp->T = T;
elessair	0:f269e3021894	1382	grp->T_size = pre_len;
elessair	0:f269e3021894	1383	}
elessair	0:f269e3021894	1384	}
elessair	0:f269e3021894	1385
elessair	0:f269e3021894	1386	/*
elessair	0:f269e3021894	1387	* Make sure M is odd (M = m or M = N - m, since N is odd)
elessair	0:f269e3021894	1388	* using the fact that m * P = - (N - m) * P
elessair	0:f269e3021894	1389	*/
elessair	0:f269e3021894	1390	m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 );
elessair	0:f269e3021894	1391	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
elessair	0:f269e3021894	1392	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
elessair	0:f269e3021894	1393	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) );
elessair	0:f269e3021894	1394
elessair	0:f269e3021894	1395	/*
elessair	0:f269e3021894	1396	* Go for comb multiplication, R = M * P
elessair	0:f269e3021894	1397	*/
elessair	0:f269e3021894	1398	ecp_comb_fixed( k, d, w, &M );
elessair	0:f269e3021894	1399	MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
elessair	0:f269e3021894	1400
elessair	0:f269e3021894	1401	/*
elessair	0:f269e3021894	1402	* Now get m * P from M * P and normalize it
elessair	0:f269e3021894	1403	*/
elessair	0:f269e3021894	1404	MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
elessair	0:f269e3021894	1405	MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
elessair	0:f269e3021894	1406
elessair	0:f269e3021894	1407	cleanup:
elessair	0:f269e3021894	1408
elessair	0:f269e3021894	1409	if( T != NULL && ! p_eq_g )
elessair	0:f269e3021894	1410	{
elessair	0:f269e3021894	1411	for( i = 0; i < pre_len; i++ )
elessair	0:f269e3021894	1412	mbedtls_ecp_point_free( &T[i] );
elessair	0:f269e3021894	1413	mbedtls_free( T );
elessair	0:f269e3021894	1414	}
elessair	0:f269e3021894	1415
elessair	0:f269e3021894	1416	mbedtls_mpi_free( &M );
elessair	0:f269e3021894	1417	mbedtls_mpi_free( &mm );
elessair	0:f269e3021894	1418
elessair	0:f269e3021894	1419	if( ret != 0 )
elessair	0:f269e3021894	1420	mbedtls_ecp_point_free( R );
elessair	0:f269e3021894	1421
elessair	0:f269e3021894	1422	return( ret );
elessair	0:f269e3021894	1423	}
elessair	0:f269e3021894	1424
elessair	0:f269e3021894	1425	#endif /* ECP_SHORTWEIERSTRASS */
elessair	0:f269e3021894	1426
elessair	0:f269e3021894	1427	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1428	/*
elessair	0:f269e3021894	1429	* For Montgomery curves, we do all the internal arithmetic in projective
elessair	0:f269e3021894	1430	* coordinates. Import/export of points uses only the x coordinates, which is
elessair	0:f269e3021894	1431	* internaly represented as X / Z.
elessair	0:f269e3021894	1432	*
elessair	0:f269e3021894	1433	* For scalar multiplication, we'll use a Montgomery ladder.
elessair	0:f269e3021894	1434	*/
elessair	0:f269e3021894	1435
elessair	0:f269e3021894	1436	/*
elessair	0:f269e3021894	1437	* Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
elessair	0:f269e3021894	1438	* Cost: 1M + 1I
elessair	0:f269e3021894	1439	*/
elessair	0:f269e3021894	1440	static int ecp_normalize_mxz( const mbedtls_ecp_group grp, mbedtls_ecp_point P )
elessair	0:f269e3021894	1441	{
elessair	0:f269e3021894	1442	int ret;
elessair	0:f269e3021894	1443
elessair	0:f269e3021894	1444	MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
elessair	0:f269e3021894	1445	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
elessair	0:f269e3021894	1446	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
elessair	0:f269e3021894	1447
elessair	0:f269e3021894	1448	cleanup:
elessair	0:f269e3021894	1449	return( ret );
elessair	0:f269e3021894	1450	}
elessair	0:f269e3021894	1451
elessair	0:f269e3021894	1452	/*
elessair	0:f269e3021894	1453	* Randomize projective x/z coordinates:
elessair	0:f269e3021894	1454	* (X, Z) -> (l X, l Z) for random l
elessair	0:f269e3021894	1455	* This is sort of the reverse operation of ecp_normalize_mxz().
elessair	0:f269e3021894	1456	*
elessair	0:f269e3021894	1457	* This countermeasure was first suggested in [2].
elessair	0:f269e3021894	1458	* Cost: 2M
elessair	0:f269e3021894	1459	*/
elessair	0:f269e3021894	1460	static int ecp_randomize_mxz( const mbedtls_ecp_group grp, mbedtls_ecp_point P,
elessair	0:f269e3021894	1461	int (f_rng)(void , unsigned char , size_t), void p_rng )
elessair	0:f269e3021894	1462	{
elessair	0:f269e3021894	1463	int ret;
elessair	0:f269e3021894	1464	mbedtls_mpi l;
elessair	0:f269e3021894	1465	size_t p_size = ( grp->pbits + 7 ) / 8;
elessair	0:f269e3021894	1466	int count = 0;
elessair	0:f269e3021894	1467
elessair	0:f269e3021894	1468	mbedtls_mpi_init( &l );
elessair	0:f269e3021894	1469
elessair	0:f269e3021894	1470	/* Generate l such that 1 < l < p */
elessair	0:f269e3021894	1471	do
elessair	0:f269e3021894	1472	{
elessair	0:f269e3021894	1473	mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng );
elessair	0:f269e3021894	1474
elessair	0:f269e3021894	1475	while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
elessair	0:f269e3021894	1476	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
elessair	0:f269e3021894	1477
elessair	0:f269e3021894	1478	if( count++ > 10 )
elessair	0:f269e3021894	1479	return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
elessair	0:f269e3021894	1480	}
elessair	0:f269e3021894	1481	while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
elessair	0:f269e3021894	1482
elessair	0:f269e3021894	1483	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
elessair	0:f269e3021894	1484	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
elessair	0:f269e3021894	1485
elessair	0:f269e3021894	1486	cleanup:
elessair	0:f269e3021894	1487	mbedtls_mpi_free( &l );
elessair	0:f269e3021894	1488
elessair	0:f269e3021894	1489	return( ret );
elessair	0:f269e3021894	1490	}
elessair	0:f269e3021894	1491
elessair	0:f269e3021894	1492	/*
elessair	0:f269e3021894	1493	* Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
elessair	0:f269e3021894	1494	* for Montgomery curves in x/z coordinates.
elessair	0:f269e3021894	1495	*
elessair	0:f269e3021894	1496	* http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
elessair	0:f269e3021894	1497	* with
elessair	0:f269e3021894	1498	* d = X1
elessair	0:f269e3021894	1499	* P = (X2, Z2)
elessair	0:f269e3021894	1500	* Q = (X3, Z3)
elessair	0:f269e3021894	1501	* R = (X4, Z4)
elessair	0:f269e3021894	1502	* S = (X5, Z5)
elessair	0:f269e3021894	1503	* and eliminating temporary variables tO, ..., t4.
elessair	0:f269e3021894	1504	*
elessair	0:f269e3021894	1505	* Cost: 5M + 4S
elessair	0:f269e3021894	1506	*/
elessair	0:f269e3021894	1507	static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
elessair	0:f269e3021894	1508	mbedtls_ecp_point R, mbedtls_ecp_point S,
elessair	0:f269e3021894	1509	const mbedtls_ecp_point P, const mbedtls_ecp_point Q,
elessair	0:f269e3021894	1510	const mbedtls_mpi *d )
elessair	0:f269e3021894	1511	{
elessair	0:f269e3021894	1512	int ret;
elessair	0:f269e3021894	1513	mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
elessair	0:f269e3021894	1514
elessair	0:f269e3021894	1515	mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
elessair	0:f269e3021894	1516	mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
elessair	0:f269e3021894	1517	mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
elessair	0:f269e3021894	1518
elessair	0:f269e3021894	1519	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
elessair	0:f269e3021894	1520	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
elessair	0:f269e3021894	1521	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
elessair	0:f269e3021894	1522	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
elessair	0:f269e3021894	1523	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
elessair	0:f269e3021894	1524	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
elessair	0:f269e3021894	1525	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
elessair	0:f269e3021894	1526	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
elessair	0:f269e3021894	1527	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
elessair	0:f269e3021894	1528	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
elessair	0:f269e3021894	1529	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
elessair	0:f269e3021894	1530	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
elessair	0:f269e3021894	1531	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
elessair	0:f269e3021894	1532	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
elessair	0:f269e3021894	1533	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
elessair	0:f269e3021894	1534	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
elessair	0:f269e3021894	1535	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
elessair	0:f269e3021894	1536	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
elessair	0:f269e3021894	1537
elessair	0:f269e3021894	1538	cleanup:
elessair	0:f269e3021894	1539	mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
elessair	0:f269e3021894	1540	mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
elessair	0:f269e3021894	1541	mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
elessair	0:f269e3021894	1542
elessair	0:f269e3021894	1543	return( ret );
elessair	0:f269e3021894	1544	}
elessair	0:f269e3021894	1545
elessair	0:f269e3021894	1546	/*
elessair	0:f269e3021894	1547	* Multiplication with Montgomery ladder in x/z coordinates,
elessair	0:f269e3021894	1548	* for curves in Montgomery form
elessair	0:f269e3021894	1549	*/
elessair	0:f269e3021894	1550	static int ecp_mul_mxz( mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1551	const mbedtls_mpi m, const mbedtls_ecp_point P,
elessair	0:f269e3021894	1552	int (f_rng)(void , unsigned char *, size_t),
elessair	0:f269e3021894	1553	void *p_rng )
elessair	0:f269e3021894	1554	{
elessair	0:f269e3021894	1555	int ret;
elessair	0:f269e3021894	1556	size_t i;
elessair	0:f269e3021894	1557	unsigned char b;
elessair	0:f269e3021894	1558	mbedtls_ecp_point RP;
elessair	0:f269e3021894	1559	mbedtls_mpi PX;
elessair	0:f269e3021894	1560
elessair	0:f269e3021894	1561	mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
elessair	0:f269e3021894	1562
elessair	0:f269e3021894	1563	/* Save PX and read from P before writing to R, in case P == R */
elessair	0:f269e3021894	1564	MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );
elessair	0:f269e3021894	1565	MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
elessair	0:f269e3021894	1566
elessair	0:f269e3021894	1567	/* Set R to zero in modified x/z coordinates */
elessair	0:f269e3021894	1568	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );
elessair	0:f269e3021894	1569	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );
elessair	0:f269e3021894	1570	mbedtls_mpi_free( &R->Y );
elessair	0:f269e3021894	1571
elessair	0:f269e3021894	1572	/* RP.X might be sligtly larger than P, so reduce it */
elessair	0:f269e3021894	1573	MOD_ADD( RP.X );
elessair	0:f269e3021894	1574
elessair	0:f269e3021894	1575	/* Randomize coordinates of the starting point */
elessair	0:f269e3021894	1576	if( f_rng != NULL )
elessair	0:f269e3021894	1577	MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
elessair	0:f269e3021894	1578
elessair	0:f269e3021894	1579	/* Loop invariant: R = result so far, RP = R + P */
elessair	0:f269e3021894	1580	i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
elessair	0:f269e3021894	1581	while( i-- > 0 )
elessair	0:f269e3021894	1582	{
elessair	0:f269e3021894	1583	b = mbedtls_mpi_get_bit( m, i );
elessair	0:f269e3021894	1584	/*
elessair	0:f269e3021894	1585	* if (b) R = 2R + P else R = 2R,
elessair	0:f269e3021894	1586	* which is:
elessair	0:f269e3021894	1587	* if (b) double_add( RP, R, RP, R )
elessair	0:f269e3021894	1588	* else double_add( R, RP, R, RP )
elessair	0:f269e3021894	1589	* but using safe conditional swaps to avoid leaks
elessair	0:f269e3021894	1590	*/
elessair	0:f269e3021894	1591	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
elessair	0:f269e3021894	1592	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
elessair	0:f269e3021894	1593	MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
elessair	0:f269e3021894	1594	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
elessair	0:f269e3021894	1595	MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
elessair	0:f269e3021894	1596	}
elessair	0:f269e3021894	1597
elessair	0:f269e3021894	1598	MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
elessair	0:f269e3021894	1599
elessair	0:f269e3021894	1600	cleanup:
elessair	0:f269e3021894	1601	mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
elessair	0:f269e3021894	1602
elessair	0:f269e3021894	1603	return( ret );
elessair	0:f269e3021894	1604	}
elessair	0:f269e3021894	1605
elessair	0:f269e3021894	1606	#endif /* ECP_MONTGOMERY */
elessair	0:f269e3021894	1607
elessair	0:f269e3021894	1608	/*
elessair	0:f269e3021894	1609	* Multiplication R = m * P
elessair	0:f269e3021894	1610	*/
elessair	0:f269e3021894	1611	int mbedtls_ecp_mul( mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1612	const mbedtls_mpi m, const mbedtls_ecp_point P,
elessair	0:f269e3021894	1613	int (f_rng)(void , unsigned char , size_t), void p_rng )
elessair	0:f269e3021894	1614	{
elessair	0:f269e3021894	1615	int ret;
elessair	0:f269e3021894	1616
elessair	0:f269e3021894	1617	/* Common sanity checks */
elessair	0:f269e3021894	1618	if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 )
elessair	0:f269e3021894	1619	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1620
elessair	0:f269e3021894	1621	if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 \|\|
elessair	0:f269e3021894	1622	( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 )
elessair	0:f269e3021894	1623	return( ret );
elessair	0:f269e3021894	1624
elessair	0:f269e3021894	1625	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1626	if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
elessair	0:f269e3021894	1627	return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
elessair	0:f269e3021894	1628	#endif
elessair	0:f269e3021894	1629	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	1630	if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
elessair	0:f269e3021894	1631	return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
elessair	0:f269e3021894	1632	#endif
elessair	0:f269e3021894	1633	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1634	}
elessair	0:f269e3021894	1635
elessair	0:f269e3021894	1636	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	1637	/*
elessair	0:f269e3021894	1638	* Check that an affine point is valid as a public key,
elessair	0:f269e3021894	1639	* short weierstrass curves (SEC1 3.2.3.1)
elessair	0:f269e3021894	1640	*/
elessair	0:f269e3021894	1641	static int ecp_check_pubkey_sw( const mbedtls_ecp_group grp, const mbedtls_ecp_point pt )
elessair	0:f269e3021894	1642	{
elessair	0:f269e3021894	1643	int ret;
elessair	0:f269e3021894	1644	mbedtls_mpi YY, RHS;
elessair	0:f269e3021894	1645
elessair	0:f269e3021894	1646	/* pt coordinates must be normalized for our checks */
elessair	0:f269e3021894	1647	if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 \|\|
elessair	0:f269e3021894	1648	mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 \|\|
elessair	0:f269e3021894	1649	mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 \|\|
elessair	0:f269e3021894	1650	mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
elessair	0:f269e3021894	1651	return( MBEDTLS_ERR_ECP_INVALID_KEY );
elessair	0:f269e3021894	1652
elessair	0:f269e3021894	1653	mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
elessair	0:f269e3021894	1654
elessair	0:f269e3021894	1655	/*
elessair	0:f269e3021894	1656	* YY = Y^2
elessair	0:f269e3021894	1657	* RHS = X (X^2 + A) + B = X^3 + A X + B
elessair	0:f269e3021894	1658	*/
elessair	0:f269e3021894	1659	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
elessair	0:f269e3021894	1660	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
elessair	0:f269e3021894	1661
elessair	0:f269e3021894	1662	/* Special case for A = -3 */
elessair	0:f269e3021894	1663	if( grp->A.p == NULL )
elessair	0:f269e3021894	1664	{
elessair	0:f269e3021894	1665	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
elessair	0:f269e3021894	1666	}
elessair	0:f269e3021894	1667	else
elessair	0:f269e3021894	1668	{
elessair	0:f269e3021894	1669	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
elessair	0:f269e3021894	1670	}
elessair	0:f269e3021894	1671
elessair	0:f269e3021894	1672	MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
elessair	0:f269e3021894	1673	MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
elessair	0:f269e3021894	1674
elessair	0:f269e3021894	1675	if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
elessair	0:f269e3021894	1676	ret = MBEDTLS_ERR_ECP_INVALID_KEY;
elessair	0:f269e3021894	1677
elessair	0:f269e3021894	1678	cleanup:
elessair	0:f269e3021894	1679
elessair	0:f269e3021894	1680	mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
elessair	0:f269e3021894	1681
elessair	0:f269e3021894	1682	return( ret );
elessair	0:f269e3021894	1683	}
elessair	0:f269e3021894	1684	#endif /* ECP_SHORTWEIERSTRASS */
elessair	0:f269e3021894	1685
elessair	0:f269e3021894	1686	/*
elessair	0:f269e3021894	1687	* R = m * P with shortcuts for m == 1 and m == -1
elessair	0:f269e3021894	1688	* NOT constant-time - ONLY for short Weierstrass!
elessair	0:f269e3021894	1689	*/
elessair	0:f269e3021894	1690	static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
elessair	0:f269e3021894	1691	mbedtls_ecp_point *R,
elessair	0:f269e3021894	1692	const mbedtls_mpi *m,
elessair	0:f269e3021894	1693	const mbedtls_ecp_point *P )
elessair	0:f269e3021894	1694	{
elessair	0:f269e3021894	1695	int ret;
elessair	0:f269e3021894	1696
elessair	0:f269e3021894	1697	if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
elessair	0:f269e3021894	1698	{
elessair	0:f269e3021894	1699	MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
elessair	0:f269e3021894	1700	}
elessair	0:f269e3021894	1701	else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
elessair	0:f269e3021894	1702	{
elessair	0:f269e3021894	1703	MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
elessair	0:f269e3021894	1704	if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
elessair	0:f269e3021894	1705	MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
elessair	0:f269e3021894	1706	}
elessair	0:f269e3021894	1707	else
elessair	0:f269e3021894	1708	{
elessair	0:f269e3021894	1709	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) );
elessair	0:f269e3021894	1710	}
elessair	0:f269e3021894	1711
elessair	0:f269e3021894	1712	cleanup:
elessair	0:f269e3021894	1713	return( ret );
elessair	0:f269e3021894	1714	}
elessair	0:f269e3021894	1715
elessair	0:f269e3021894	1716	/*
elessair	0:f269e3021894	1717	* Linear combination
elessair	0:f269e3021894	1718	* NOT constant-time
elessair	0:f269e3021894	1719	*/
elessair	0:f269e3021894	1720	int mbedtls_ecp_muladd( mbedtls_ecp_group grp, mbedtls_ecp_point R,
elessair	0:f269e3021894	1721	const mbedtls_mpi m, const mbedtls_ecp_point P,
elessair	0:f269e3021894	1722	const mbedtls_mpi n, const mbedtls_ecp_point Q )
elessair	0:f269e3021894	1723	{
elessair	0:f269e3021894	1724	int ret;
elessair	0:f269e3021894	1725	mbedtls_ecp_point mP;
elessair	0:f269e3021894	1726
elessair	0:f269e3021894	1727	if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
elessair	0:f269e3021894	1728	return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
elessair	0:f269e3021894	1729
elessair	0:f269e3021894	1730	mbedtls_ecp_point_init( &mP );
elessair	0:f269e3021894	1731
elessair	0:f269e3021894	1732	MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) );
elessair	0:f269e3021894	1733	MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) );
elessair	0:f269e3021894	1734
elessair	0:f269e3021894	1735	MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) );
elessair	0:f269e3021894	1736	MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
elessair	0:f269e3021894	1737
elessair	0:f269e3021894	1738	cleanup:
elessair	0:f269e3021894	1739	mbedtls_ecp_point_free( &mP );
elessair	0:f269e3021894	1740
elessair	0:f269e3021894	1741	return( ret );
elessair	0:f269e3021894	1742	}
elessair	0:f269e3021894	1743
elessair	0:f269e3021894	1744
elessair	0:f269e3021894	1745	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1746	/*
elessair	0:f269e3021894	1747	* Check validity of a public key for Montgomery curves with x-only schemes
elessair	0:f269e3021894	1748	*/
elessair	0:f269e3021894	1749	static int ecp_check_pubkey_mx( const mbedtls_ecp_group grp, const mbedtls_ecp_point pt )
elessair	0:f269e3021894	1750	{
elessair	0:f269e3021894	1751	/* [Curve25519 p. 5] Just check X is the correct number of bytes */
elessair	0:f269e3021894	1752	if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
elessair	0:f269e3021894	1753	return( MBEDTLS_ERR_ECP_INVALID_KEY );
elessair	0:f269e3021894	1754
elessair	0:f269e3021894	1755	return( 0 );
elessair	0:f269e3021894	1756	}
elessair	0:f269e3021894	1757	#endif /* ECP_MONTGOMERY */
elessair	0:f269e3021894	1758
elessair	0:f269e3021894	1759	/*
elessair	0:f269e3021894	1760	* Check that a point is valid as a public key
elessair	0:f269e3021894	1761	*/
elessair	0:f269e3021894	1762	int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group grp, const mbedtls_ecp_point pt )
elessair	0:f269e3021894	1763	{
elessair	0:f269e3021894	1764	/* Must use affine coordinates */
elessair	0:f269e3021894	1765	if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
elessair	0:f269e3021894	1766	return( MBEDTLS_ERR_ECP_INVALID_KEY );
elessair	0:f269e3021894	1767
elessair	0:f269e3021894	1768	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1769	if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
elessair	0:f269e3021894	1770	return( ecp_check_pubkey_mx( grp, pt ) );
elessair	0:f269e3021894	1771	#endif
elessair	0:f269e3021894	1772	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	1773	if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
elessair	0:f269e3021894	1774	return( ecp_check_pubkey_sw( grp, pt ) );
elessair	0:f269e3021894	1775	#endif
elessair	0:f269e3021894	1776	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1777	}
elessair	0:f269e3021894	1778
elessair	0:f269e3021894	1779	/*
elessair	0:f269e3021894	1780	* Check that an mbedtls_mpi is valid as a private key
elessair	0:f269e3021894	1781	*/
elessair	0:f269e3021894	1782	int mbedtls_ecp_check_privkey( const mbedtls_ecp_group grp, const mbedtls_mpi d )
elessair	0:f269e3021894	1783	{
elessair	0:f269e3021894	1784	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1785	if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
elessair	0:f269e3021894	1786	{
elessair	0:f269e3021894	1787	/* see [Curve25519] page 5 */
elessair	0:f269e3021894	1788	if( mbedtls_mpi_get_bit( d, 0 ) != 0 \|\|
elessair	0:f269e3021894	1789	mbedtls_mpi_get_bit( d, 1 ) != 0 \|\|
elessair	0:f269e3021894	1790	mbedtls_mpi_get_bit( d, 2 ) != 0 \|\|
elessair	0:f269e3021894	1791	mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */
elessair	0:f269e3021894	1792	return( MBEDTLS_ERR_ECP_INVALID_KEY );
elessair	0:f269e3021894	1793	else
elessair	0:f269e3021894	1794	return( 0 );
elessair	0:f269e3021894	1795	}
elessair	0:f269e3021894	1796	#endif /* ECP_MONTGOMERY */
elessair	0:f269e3021894	1797	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	1798	if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
elessair	0:f269e3021894	1799	{
elessair	0:f269e3021894	1800	/* see SEC1 3.2 */
elessair	0:f269e3021894	1801	if( mbedtls_mpi_cmp_int( d, 1 ) < 0 \|\|
elessair	0:f269e3021894	1802	mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
elessair	0:f269e3021894	1803	return( MBEDTLS_ERR_ECP_INVALID_KEY );
elessair	0:f269e3021894	1804	else
elessair	0:f269e3021894	1805	return( 0 );
elessair	0:f269e3021894	1806	}
elessair	0:f269e3021894	1807	#endif /* ECP_SHORTWEIERSTRASS */
elessair	0:f269e3021894	1808
elessair	0:f269e3021894	1809	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1810	}
elessair	0:f269e3021894	1811
elessair	0:f269e3021894	1812	/*
elessair	0:f269e3021894	1813	* Generate a keypair with configurable base point
elessair	0:f269e3021894	1814	*/
elessair	0:f269e3021894	1815	int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
elessair	0:f269e3021894	1816	const mbedtls_ecp_point *G,
elessair	0:f269e3021894	1817	mbedtls_mpi d, mbedtls_ecp_point Q,
elessair	0:f269e3021894	1818	int (f_rng)(void , unsigned char *, size_t),
elessair	0:f269e3021894	1819	void *p_rng )
elessair	0:f269e3021894	1820	{
elessair	0:f269e3021894	1821	int ret;
elessair	0:f269e3021894	1822	size_t n_size = ( grp->nbits + 7 ) / 8;
elessair	0:f269e3021894	1823
elessair	0:f269e3021894	1824	#if defined(ECP_MONTGOMERY)
elessair	0:f269e3021894	1825	if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
elessair	0:f269e3021894	1826	{
elessair	0:f269e3021894	1827	/* [M225] page 5 */
elessair	0:f269e3021894	1828	size_t b;
elessair	0:f269e3021894	1829
elessair	0:f269e3021894	1830	do {
elessair	0:f269e3021894	1831	MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
elessair	0:f269e3021894	1832	} while( mbedtls_mpi_bitlen( d ) == 0);
elessair	0:f269e3021894	1833
elessair	0:f269e3021894	1834	/* Make sure the most significant bit is nbits */
elessair	0:f269e3021894	1835	b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
elessair	0:f269e3021894	1836	if( b > grp->nbits )
elessair	0:f269e3021894	1837	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
elessair	0:f269e3021894	1838	else
elessair	0:f269e3021894	1839	MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
elessair	0:f269e3021894	1840
elessair	0:f269e3021894	1841	/* Make sure the last three bits are unset */
elessair	0:f269e3021894	1842	MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
elessair	0:f269e3021894	1843	MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
elessair	0:f269e3021894	1844	MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
elessair	0:f269e3021894	1845	}
elessair	0:f269e3021894	1846	else
elessair	0:f269e3021894	1847	#endif /* ECP_MONTGOMERY */
elessair	0:f269e3021894	1848	#if defined(ECP_SHORTWEIERSTRASS)
elessair	0:f269e3021894	1849	if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
elessair	0:f269e3021894	1850	{
elessair	0:f269e3021894	1851	/* SEC1 3.2.1: Generate d such that 1 <= n < N */
elessair	0:f269e3021894	1852	int count = 0;
elessair	0:f269e3021894	1853	unsigned char rnd[MBEDTLS_ECP_MAX_BYTES];
elessair	0:f269e3021894	1854
elessair	0:f269e3021894	1855	/*
elessair	0:f269e3021894	1856	* Match the procedure given in RFC 6979 (deterministic ECDSA):
elessair	0:f269e3021894	1857	* - use the same byte ordering;
elessair	0:f269e3021894	1858	* - keep the leftmost nbits bits of the generated octet string;
elessair	0:f269e3021894	1859	* - try until result is in the desired range.
elessair	0:f269e3021894	1860	* This also avoids any biais, which is especially important for ECDSA.
elessair	0:f269e3021894	1861	*/
elessair	0:f269e3021894	1862	do
elessair	0:f269e3021894	1863	{
elessair	0:f269e3021894	1864	MBEDTLS_MPI_CHK( f_rng( p_rng, rnd, n_size ) );
elessair	0:f269e3021894	1865	MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( d, rnd, n_size ) );
elessair	0:f269e3021894	1866	MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
elessair	0:f269e3021894	1867
elessair	0:f269e3021894	1868	/*
elessair	0:f269e3021894	1869	* Each try has at worst a probability 1/2 of failing (the msb has
elessair	0:f269e3021894	1870	* a probability 1/2 of being 0, and then the result will be < N),
elessair	0:f269e3021894	1871	* so after 30 tries failure probability is a most 2**(-30).
elessair	0:f269e3021894	1872	*
elessair	0:f269e3021894	1873	* For most curves, 1 try is enough with overwhelming probability,
elessair	0:f269e3021894	1874	* since N starts with a lot of 1s in binary, but some curves
elessair	0:f269e3021894	1875	* such as secp224k1 are actually very close to the worst case.
elessair	0:f269e3021894	1876	*/
elessair	0:f269e3021894	1877	if( ++count > 30 )
elessair	0:f269e3021894	1878	return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
elessair	0:f269e3021894	1879	}
elessair	0:f269e3021894	1880	while( mbedtls_mpi_cmp_int( d, 1 ) < 0 \|\|
elessair	0:f269e3021894	1881	mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
elessair	0:f269e3021894	1882	}
elessair	0:f269e3021894	1883	else
elessair	0:f269e3021894	1884	#endif /* ECP_SHORTWEIERSTRASS */
elessair	0:f269e3021894	1885	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1886
elessair	0:f269e3021894	1887	cleanup:
elessair	0:f269e3021894	1888	if( ret != 0 )
elessair	0:f269e3021894	1889	return( ret );
elessair	0:f269e3021894	1890
elessair	0:f269e3021894	1891	return( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
elessair	0:f269e3021894	1892	}
elessair	0:f269e3021894	1893
elessair	0:f269e3021894	1894	/*
elessair	0:f269e3021894	1895	* Generate key pair, wrapper for conventional base point
elessair	0:f269e3021894	1896	*/
elessair	0:f269e3021894	1897	int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
elessair	0:f269e3021894	1898	mbedtls_mpi d, mbedtls_ecp_point Q,
elessair	0:f269e3021894	1899	int (f_rng)(void , unsigned char *, size_t),
elessair	0:f269e3021894	1900	void *p_rng )
elessair	0:f269e3021894	1901	{
elessair	0:f269e3021894	1902	return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
elessair	0:f269e3021894	1903	}
elessair	0:f269e3021894	1904
elessair	0:f269e3021894	1905	/*
elessair	0:f269e3021894	1906	* Generate a keypair, prettier wrapper
elessair	0:f269e3021894	1907	*/
elessair	0:f269e3021894	1908	int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
elessair	0:f269e3021894	1909	int (f_rng)(void , unsigned char , size_t), void p_rng )
elessair	0:f269e3021894	1910	{
elessair	0:f269e3021894	1911	int ret;
elessair	0:f269e3021894	1912
elessair	0:f269e3021894	1913	if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
elessair	0:f269e3021894	1914	return( ret );
elessair	0:f269e3021894	1915
elessair	0:f269e3021894	1916	return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
elessair	0:f269e3021894	1917	}
elessair	0:f269e3021894	1918
elessair	0:f269e3021894	1919	/*
elessair	0:f269e3021894	1920	* Check a public-private key pair
elessair	0:f269e3021894	1921	*/
elessair	0:f269e3021894	1922	int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair pub, const mbedtls_ecp_keypair prv )
elessair	0:f269e3021894	1923	{
elessair	0:f269e3021894	1924	int ret;
elessair	0:f269e3021894	1925	mbedtls_ecp_point Q;
elessair	0:f269e3021894	1926	mbedtls_ecp_group grp;
elessair	0:f269e3021894	1927
elessair	0:f269e3021894	1928	if( pub->grp.id == MBEDTLS_ECP_DP_NONE \|\|
elessair	0:f269e3021894	1929	pub->grp.id != prv->grp.id \|\|
elessair	0:f269e3021894	1930	mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) \|\|
elessair	0:f269e3021894	1931	mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) \|\|
elessair	0:f269e3021894	1932	mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
elessair	0:f269e3021894	1933	{
elessair	0:f269e3021894	1934	return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
elessair	0:f269e3021894	1935	}
elessair	0:f269e3021894	1936
elessair	0:f269e3021894	1937	mbedtls_ecp_point_init( &Q );
elessair	0:f269e3021894	1938	mbedtls_ecp_group_init( &grp );
elessair	0:f269e3021894	1939
elessair	0:f269e3021894	1940	/* mbedtls_ecp_mul() needs a non-const group... */
elessair	0:f269e3021894	1941	mbedtls_ecp_group_copy( &grp, &prv->grp );
elessair	0:f269e3021894	1942
elessair	0:f269e3021894	1943	/* Also checks d is valid */
elessair	0:f269e3021894	1944	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
elessair	0:f269e3021894	1945
elessair	0:f269e3021894	1946	if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) \|\|
elessair	0:f269e3021894	1947	mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) \|\|
elessair	0:f269e3021894	1948	mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
elessair	0:f269e3021894	1949	{
elessair	0:f269e3021894	1950	ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
elessair	0:f269e3021894	1951	goto cleanup;
elessair	0:f269e3021894	1952	}
elessair	0:f269e3021894	1953
elessair	0:f269e3021894	1954	cleanup:
elessair	0:f269e3021894	1955	mbedtls_ecp_point_free( &Q );
elessair	0:f269e3021894	1956	mbedtls_ecp_group_free( &grp );
elessair	0:f269e3021894	1957
elessair	0:f269e3021894	1958	return( ret );
elessair	0:f269e3021894	1959	}
elessair	0:f269e3021894	1960
elessair	0:f269e3021894	1961	#if defined(MBEDTLS_SELF_TEST)
elessair	0:f269e3021894	1962
elessair	0:f269e3021894	1963	/*
elessair	0:f269e3021894	1964	* Checkup routine
elessair	0:f269e3021894	1965	*/
elessair	0:f269e3021894	1966	int mbedtls_ecp_self_test( int verbose )
elessair	0:f269e3021894	1967	{
elessair	0:f269e3021894	1968	int ret;
elessair	0:f269e3021894	1969	size_t i;
elessair	0:f269e3021894	1970	mbedtls_ecp_group grp;
elessair	0:f269e3021894	1971	mbedtls_ecp_point R, P;
elessair	0:f269e3021894	1972	mbedtls_mpi m;
elessair	0:f269e3021894	1973	unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
elessair	0:f269e3021894	1974	/* exponents especially adapted for secp192r1 */
elessair	0:f269e3021894	1975	const char *exponents[] =
elessair	0:f269e3021894	1976	{
elessair	0:f269e3021894	1977	"000000000000000000000000000000000000000000000001", /* one */
elessair	0:f269e3021894	1978	"FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
elessair	0:f269e3021894	1979	"5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
elessair	0:f269e3021894	1980	"400000000000000000000000000000000000000000000000", /* one and zeros */
elessair	0:f269e3021894	1981	"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
elessair	0:f269e3021894	1982	"555555555555555555555555555555555555555555555555", /* 101010... */
elessair	0:f269e3021894	1983	};
elessair	0:f269e3021894	1984
elessair	0:f269e3021894	1985	mbedtls_ecp_group_init( &grp );
elessair	0:f269e3021894	1986	mbedtls_ecp_point_init( &R );
elessair	0:f269e3021894	1987	mbedtls_ecp_point_init( &P );
elessair	0:f269e3021894	1988	mbedtls_mpi_init( &m );
elessair	0:f269e3021894	1989
elessair	0:f269e3021894	1990	/* Use secp192r1 if available, or any available curve */
elessair	0:f269e3021894	1991	#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
elessair	0:f269e3021894	1992	MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
elessair	0:f269e3021894	1993	#else
elessair	0:f269e3021894	1994	MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
elessair	0:f269e3021894	1995	#endif
elessair	0:f269e3021894	1996
elessair	0:f269e3021894	1997	if( verbose != 0 )
elessair	0:f269e3021894	1998	mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
elessair	0:f269e3021894	1999
elessair	0:f269e3021894	2000	/* Do a dummy multiplication first to trigger precomputation */
elessair	0:f269e3021894	2001	MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
elessair	0:f269e3021894	2002	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
elessair	0:f269e3021894	2003
elessair	0:f269e3021894	2004	add_count = 0;
elessair	0:f269e3021894	2005	dbl_count = 0;
elessair	0:f269e3021894	2006	mul_count = 0;
elessair	0:f269e3021894	2007	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
elessair	0:f269e3021894	2008	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
elessair	0:f269e3021894	2009
elessair	0:f269e3021894	2010	for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
elessair	0:f269e3021894	2011	{
elessair	0:f269e3021894	2012	add_c_prev = add_count;
elessair	0:f269e3021894	2013	dbl_c_prev = dbl_count;
elessair	0:f269e3021894	2014	mul_c_prev = mul_count;
elessair	0:f269e3021894	2015	add_count = 0;
elessair	0:f269e3021894	2016	dbl_count = 0;
elessair	0:f269e3021894	2017	mul_count = 0;
elessair	0:f269e3021894	2018
elessair	0:f269e3021894	2019	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
elessair	0:f269e3021894	2020	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
elessair	0:f269e3021894	2021
elessair	0:f269e3021894	2022	if( add_count != add_c_prev \|\|
elessair	0:f269e3021894	2023	dbl_count != dbl_c_prev \|\|
elessair	0:f269e3021894	2024	mul_count != mul_c_prev )
elessair	0:f269e3021894	2025	{
elessair	0:f269e3021894	2026	if( verbose != 0 )
elessair	0:f269e3021894	2027	mbedtls_printf( "failed (%u)\n", (unsigned int) i );
elessair	0:f269e3021894	2028
elessair	0:f269e3021894	2029	ret = 1;
elessair	0:f269e3021894	2030	goto cleanup;
elessair	0:f269e3021894	2031	}
elessair	0:f269e3021894	2032	}
elessair	0:f269e3021894	2033
elessair	0:f269e3021894	2034	if( verbose != 0 )
elessair	0:f269e3021894	2035	mbedtls_printf( "passed\n" );
elessair	0:f269e3021894	2036
elessair	0:f269e3021894	2037	if( verbose != 0 )
elessair	0:f269e3021894	2038	mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
elessair	0:f269e3021894	2039	/* We computed P = 2G last time, use it */
elessair	0:f269e3021894	2040
elessair	0:f269e3021894	2041	add_count = 0;
elessair	0:f269e3021894	2042	dbl_count = 0;
elessair	0:f269e3021894	2043	mul_count = 0;
elessair	0:f269e3021894	2044	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
elessair	0:f269e3021894	2045	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
elessair	0:f269e3021894	2046
elessair	0:f269e3021894	2047	for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
elessair	0:f269e3021894	2048	{
elessair	0:f269e3021894	2049	add_c_prev = add_count;
elessair	0:f269e3021894	2050	dbl_c_prev = dbl_count;
elessair	0:f269e3021894	2051	mul_c_prev = mul_count;
elessair	0:f269e3021894	2052	add_count = 0;
elessair	0:f269e3021894	2053	dbl_count = 0;
elessair	0:f269e3021894	2054	mul_count = 0;
elessair	0:f269e3021894	2055
elessair	0:f269e3021894	2056	MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
elessair	0:f269e3021894	2057	MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
elessair	0:f269e3021894	2058
elessair	0:f269e3021894	2059	if( add_count != add_c_prev \|\|
elessair	0:f269e3021894	2060	dbl_count != dbl_c_prev \|\|
elessair	0:f269e3021894	2061	mul_count != mul_c_prev )
elessair	0:f269e3021894	2062	{
elessair	0:f269e3021894	2063	if( verbose != 0 )
elessair	0:f269e3021894	2064	mbedtls_printf( "failed (%u)\n", (unsigned int) i );
elessair	0:f269e3021894	2065
elessair	0:f269e3021894	2066	ret = 1;
elessair	0:f269e3021894	2067	goto cleanup;
elessair	0:f269e3021894	2068	}
elessair	0:f269e3021894	2069	}
elessair	0:f269e3021894	2070
elessair	0:f269e3021894	2071	if( verbose != 0 )
elessair	0:f269e3021894	2072	mbedtls_printf( "passed\n" );
elessair	0:f269e3021894	2073
elessair	0:f269e3021894	2074	cleanup:
elessair	0:f269e3021894	2075
elessair	0:f269e3021894	2076	if( ret < 0 && verbose != 0 )
elessair	0:f269e3021894	2077	mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
elessair	0:f269e3021894	2078
elessair	0:f269e3021894	2079	mbedtls_ecp_group_free( &grp );
elessair	0:f269e3021894	2080	mbedtls_ecp_point_free( &R );
elessair	0:f269e3021894	2081	mbedtls_ecp_point_free( &P );
elessair	0:f269e3021894	2082	mbedtls_mpi_free( &m );
elessair	0:f269e3021894	2083
elessair	0:f269e3021894	2084	if( verbose != 0 )
elessair	0:f269e3021894	2085	mbedtls_printf( "\n" );
elessair	0:f269e3021894	2086
elessair	0:f269e3021894	2087	return( ret );
elessair	0:f269e3021894	2088	}
elessair	0:f269e3021894	2089
elessair	0:f269e3021894	2090	#endif /* MBEDTLS_SELF_TEST */
elessair	0:f269e3021894	2091
elessair	0:f269e3021894	2092	#endif /* MBEDTLS_ECP_C */

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	23 Oct 2016
Imports:	1689
Forks:	1
Commits:	1
Dependents:	3
Dependencies:	0
Followers:	20

features/mbedtls/src/ecp.c@0:f269e3021894, 2016-10-23 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning