mbedtls - mbed TLS upgraded to 2.6.0

Arcola » Code » mbedtls

mbed TLS upgraded to 2.6.0

library/ecp.c@0:cdf462088d13, 2017-01-05 (annotated)

Committer:: markrad
Date:: Thu Jan 05 00:18:44 2017 +0000
Revision:: 0:cdf462088d13
Child:: 2:bbdeda018a3c

Initial commit

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	29 Sep 2017
Imports:	3
Forks:	0
Commits:	3
Dependents:	0
Dependencies:	0
Followers:	5

This repository is Public (Unlisted).

The code in this repository is Apache licensed.

library/ecp.c@0:cdf462088d13, 2017-01-05 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning