mbedTLSLibrary - mbed TLS library

Users » ansond » Code » mbedTLSLibrary

mbed TLS library

Dependents: HTTPClient-SSL WS_SERVER

polarssl/ecp.c@0:137634ff4186, 2015-06-11 (annotated)

Committer:: ansond
Date:: Thu Jun 11 03:27:03 2015 +0000
Revision:: 0:137634ff4186

initial commit

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	11 Jun 2015
Imports:	10
Forks:	0
Commits:	1
Dependents:	2
Dependencies:	0
Followers:	1

This repository is Public (Unlisted).

The code in this repository is Apache licensed.

polarssl/ecp.c@0:137634ff4186, 2015-06-11 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning