BBR_1Ebene - BBR 1 Ebene

Users » borlanic » Code » BBR_1Ebene

BBR 1 Ebene

mbed-os/features/mbedtls/src/ecp.c@0:fbdae7e6d805, 2018-05-14 (annotated)

Committer:: borlanic
Date:: Mon May 14 11:29:06 2018 +0000
Revision:: 0:fbdae7e6d805

BBR

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed OS
Created:	14 May 2018
Imports:	0
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	0
Followers:	3

mbed-os/features/mbedtls/src/ecp.c@0:fbdae7e6d805, 2018-05-14 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning