aes-gcm-test-program - Example program to test AES-GCM functionality. Us…

Users » HannesTschofenig » Code » aes-gcm-test-program

Hannes Tschofenig / Mbed 2 deprecated aes-gcm-test-program

Example program to test AES-GCM functionality. Used for a workshop

SSL/library/ecp.c@0:796d0f61a05b, 2018-09-27 (annotated)

Committer:: HannesTschofenig
Date:: Thu Sep 27 06:34:22 2018 +0000
Revision:: 0:796d0f61a05b

Example AES-GCM test program

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	27 Sep 2018
Imports:	11
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	1
Followers:	1

The code in this repository is Apache licensed.

SSL/library/ecp.c@0:796d0f61a05b, 2018-09-27 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning