mbedTLSLibrary - mbed TLS library

Users » ansond » Code » mbedTLSLibrary

mbed TLS library

Dependents: HTTPClient-SSL WS_SERVER

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

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

initial commit

Who changed what in which revision?

User	Revision	Line number	New contents of line
ansond	0:137634ff4186	1	/*
ansond	0:137634ff4186	2	* Multi-precision integer library
ansond	0:137634ff4186	3	*
ansond	0:137634ff4186	4	* Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
ansond	0:137634ff4186	5	*
ansond	0:137634ff4186	6	* This file is part of mbed TLS (https://tls.mbed.org)
ansond	0:137634ff4186	7	*
ansond	0:137634ff4186	8	* This program is free software; you can redistribute it and/or modify
ansond	0:137634ff4186	9	* it under the terms of the GNU General Public License as published by
ansond	0:137634ff4186	10	* the Free Software Foundation; either version 2 of the License, or
ansond	0:137634ff4186	11	* (at your option) any later version.
ansond	0:137634ff4186	12	*
ansond	0:137634ff4186	13	* This program is distributed in the hope that it will be useful,
ansond	0:137634ff4186	14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
ansond	0:137634ff4186	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
ansond	0:137634ff4186	16	* GNU General Public License for more details.
ansond	0:137634ff4186	17	*
ansond	0:137634ff4186	18	* You should have received a copy of the GNU General Public License along
ansond	0:137634ff4186	19	* with this program; if not, write to the Free Software Foundation, Inc.,
ansond	0:137634ff4186	20	* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
ansond	0:137634ff4186	21	*/
ansond	0:137634ff4186	22	/*
ansond	0:137634ff4186	23	* This MPI implementation is based on:
ansond	0:137634ff4186	24	*
ansond	0:137634ff4186	25	* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
ansond	0:137634ff4186	26	* http://www.stillhq.com/extracted/gnupg-api/mpi/
ansond	0:137634ff4186	27	* http://math.libtomcrypt.com/files/tommath.pdf
ansond	0:137634ff4186	28	*/
ansond	0:137634ff4186	29
ansond	0:137634ff4186	30	#if !defined(POLARSSL_CONFIG_FILE)
ansond	0:137634ff4186	31	#include "polarssl/config.h"
ansond	0:137634ff4186	32	#else
ansond	0:137634ff4186	33	#include POLARSSL_CONFIG_FILE
ansond	0:137634ff4186	34	#endif
ansond	0:137634ff4186	35
ansond	0:137634ff4186	36	#if defined(POLARSSL_BIGNUM_C)
ansond	0:137634ff4186	37
ansond	0:137634ff4186	38	#include "polarssl/bignum.h"
ansond	0:137634ff4186	39	#include "polarssl/bn_mul.h"
ansond	0:137634ff4186	40
ansond	0:137634ff4186	41	#include <string.h>
ansond	0:137634ff4186	42
ansond	0:137634ff4186	43	#if defined(POLARSSL_PLATFORM_C)
ansond	0:137634ff4186	44	#include "polarssl/platform.h"
ansond	0:137634ff4186	45	#else
ansond	0:137634ff4186	46	#include <stdio.h>
ansond	0:137634ff4186	47	#include <stdlib.h>
ansond	0:137634ff4186	48	#define polarssl_printf printf
ansond	0:137634ff4186	49	#define polarssl_malloc malloc
ansond	0:137634ff4186	50	#define polarssl_free free
ansond	0:137634ff4186	51	#endif
ansond	0:137634ff4186	52
ansond	0:137634ff4186	53	/* Implementation that should never be optimized out by the compiler */
ansond	0:137634ff4186	54	static void polarssl_zeroize( void *v, size_t n ) {
ansond	0:137634ff4186	55	volatile unsigned char p = v; while( n-- ) p++ = 0;
ansond	0:137634ff4186	56	}
ansond	0:137634ff4186	57
ansond	0:137634ff4186	58	#define ciL (sizeof(t_uint)) /* chars in limb */
ansond	0:137634ff4186	59	#define biL (ciL << 3) /* bits in limb */
ansond	0:137634ff4186	60	#define biH (ciL << 2) /* half limb size */
ansond	0:137634ff4186	61
ansond	0:137634ff4186	62	/*
ansond	0:137634ff4186	63	* Convert between bits/chars and number of limbs
ansond	0:137634ff4186	64	*/
ansond	0:137634ff4186	65	#define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
ansond	0:137634ff4186	66	#define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
ansond	0:137634ff4186	67
ansond	0:137634ff4186	68	/*
ansond	0:137634ff4186	69	* Initialize one MPI
ansond	0:137634ff4186	70	*/
ansond	0:137634ff4186	71	void mpi_init( mpi *X )
ansond	0:137634ff4186	72	{
ansond	0:137634ff4186	73	if( X == NULL )
ansond	0:137634ff4186	74	return;
ansond	0:137634ff4186	75
ansond	0:137634ff4186	76	X->s = 1;
ansond	0:137634ff4186	77	X->n = 0;
ansond	0:137634ff4186	78	X->p = NULL;
ansond	0:137634ff4186	79	}
ansond	0:137634ff4186	80
ansond	0:137634ff4186	81	/*
ansond	0:137634ff4186	82	* Unallocate one MPI
ansond	0:137634ff4186	83	*/
ansond	0:137634ff4186	84	void mpi_free( mpi *X )
ansond	0:137634ff4186	85	{
ansond	0:137634ff4186	86	if( X == NULL )
ansond	0:137634ff4186	87	return;
ansond	0:137634ff4186	88
ansond	0:137634ff4186	89	if( X->p != NULL )
ansond	0:137634ff4186	90	{
ansond	0:137634ff4186	91	polarssl_zeroize( X->p, X->n * ciL );
ansond	0:137634ff4186	92	polarssl_free( X->p );
ansond	0:137634ff4186	93	}
ansond	0:137634ff4186	94
ansond	0:137634ff4186	95	X->s = 1;
ansond	0:137634ff4186	96	X->n = 0;
ansond	0:137634ff4186	97	X->p = NULL;
ansond	0:137634ff4186	98	}
ansond	0:137634ff4186	99
ansond	0:137634ff4186	100	/*
ansond	0:137634ff4186	101	* Enlarge to the specified number of limbs
ansond	0:137634ff4186	102	*/
ansond	0:137634ff4186	103	int mpi_grow( mpi *X, size_t nblimbs )
ansond	0:137634ff4186	104	{
ansond	0:137634ff4186	105	t_uint *p;
ansond	0:137634ff4186	106
ansond	0:137634ff4186	107	if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
ansond	0:137634ff4186	108	return( POLARSSL_ERR_MPI_MALLOC_FAILED );
ansond	0:137634ff4186	109
ansond	0:137634ff4186	110	if( X->n < nblimbs )
ansond	0:137634ff4186	111	{
ansond	0:137634ff4186	112	if( ( p = polarssl_malloc( nblimbs * ciL ) ) == NULL )
ansond	0:137634ff4186	113	return( POLARSSL_ERR_MPI_MALLOC_FAILED );
ansond	0:137634ff4186	114
ansond	0:137634ff4186	115	memset( p, 0, nblimbs * ciL );
ansond	0:137634ff4186	116
ansond	0:137634ff4186	117	if( X->p != NULL )
ansond	0:137634ff4186	118	{
ansond	0:137634ff4186	119	memcpy( p, X->p, X->n * ciL );
ansond	0:137634ff4186	120	polarssl_zeroize( X->p, X->n * ciL );
ansond	0:137634ff4186	121	polarssl_free( X->p );
ansond	0:137634ff4186	122	}
ansond	0:137634ff4186	123
ansond	0:137634ff4186	124	X->n = nblimbs;
ansond	0:137634ff4186	125	X->p = p;
ansond	0:137634ff4186	126	}
ansond	0:137634ff4186	127
ansond	0:137634ff4186	128	return( 0 );
ansond	0:137634ff4186	129	}
ansond	0:137634ff4186	130
ansond	0:137634ff4186	131	/*
ansond	0:137634ff4186	132	* Resize down as much as possible,
ansond	0:137634ff4186	133	* while keeping at least the specified number of limbs
ansond	0:137634ff4186	134	*/
ansond	0:137634ff4186	135	int mpi_shrink( mpi *X, size_t nblimbs )
ansond	0:137634ff4186	136	{
ansond	0:137634ff4186	137	t_uint *p;
ansond	0:137634ff4186	138	size_t i;
ansond	0:137634ff4186	139
ansond	0:137634ff4186	140	/* Actually resize up in this case */
ansond	0:137634ff4186	141	if( X->n <= nblimbs )
ansond	0:137634ff4186	142	return( mpi_grow( X, nblimbs ) );
ansond	0:137634ff4186	143
ansond	0:137634ff4186	144	for( i = X->n - 1; i > 0; i-- )
ansond	0:137634ff4186	145	if( X->p[i] != 0 )
ansond	0:137634ff4186	146	break;
ansond	0:137634ff4186	147	i++;
ansond	0:137634ff4186	148
ansond	0:137634ff4186	149	if( i < nblimbs )
ansond	0:137634ff4186	150	i = nblimbs;
ansond	0:137634ff4186	151
ansond	0:137634ff4186	152	if( ( p = polarssl_malloc( i * ciL ) ) == NULL )
ansond	0:137634ff4186	153	return( POLARSSL_ERR_MPI_MALLOC_FAILED );
ansond	0:137634ff4186	154
ansond	0:137634ff4186	155	memset( p, 0, i * ciL );
ansond	0:137634ff4186	156
ansond	0:137634ff4186	157	if( X->p != NULL )
ansond	0:137634ff4186	158	{
ansond	0:137634ff4186	159	memcpy( p, X->p, i * ciL );
ansond	0:137634ff4186	160	polarssl_zeroize( X->p, X->n * ciL );
ansond	0:137634ff4186	161	polarssl_free( X->p );
ansond	0:137634ff4186	162	}
ansond	0:137634ff4186	163
ansond	0:137634ff4186	164	X->n = i;
ansond	0:137634ff4186	165	X->p = p;
ansond	0:137634ff4186	166
ansond	0:137634ff4186	167	return( 0 );
ansond	0:137634ff4186	168	}
ansond	0:137634ff4186	169
ansond	0:137634ff4186	170	/*
ansond	0:137634ff4186	171	* Copy the contents of Y into X
ansond	0:137634ff4186	172	*/
ansond	0:137634ff4186	173	int mpi_copy( mpi X, const mpi Y )
ansond	0:137634ff4186	174	{
ansond	0:137634ff4186	175	int ret;
ansond	0:137634ff4186	176	size_t i;
ansond	0:137634ff4186	177
ansond	0:137634ff4186	178	if( X == Y )
ansond	0:137634ff4186	179	return( 0 );
ansond	0:137634ff4186	180
ansond	0:137634ff4186	181	if( Y->p == NULL )
ansond	0:137634ff4186	182	{
ansond	0:137634ff4186	183	mpi_free( X );
ansond	0:137634ff4186	184	return( 0 );
ansond	0:137634ff4186	185	}
ansond	0:137634ff4186	186
ansond	0:137634ff4186	187	for( i = Y->n - 1; i > 0; i-- )
ansond	0:137634ff4186	188	if( Y->p[i] != 0 )
ansond	0:137634ff4186	189	break;
ansond	0:137634ff4186	190	i++;
ansond	0:137634ff4186	191
ansond	0:137634ff4186	192	X->s = Y->s;
ansond	0:137634ff4186	193
ansond	0:137634ff4186	194	MPI_CHK( mpi_grow( X, i ) );
ansond	0:137634ff4186	195
ansond	0:137634ff4186	196	memset( X->p, 0, X->n * ciL );
ansond	0:137634ff4186	197	memcpy( X->p, Y->p, i * ciL );
ansond	0:137634ff4186	198
ansond	0:137634ff4186	199	cleanup:
ansond	0:137634ff4186	200
ansond	0:137634ff4186	201	return( ret );
ansond	0:137634ff4186	202	}
ansond	0:137634ff4186	203
ansond	0:137634ff4186	204	/*
ansond	0:137634ff4186	205	* Swap the contents of X and Y
ansond	0:137634ff4186	206	*/
ansond	0:137634ff4186	207	void mpi_swap( mpi X, mpi Y )
ansond	0:137634ff4186	208	{
ansond	0:137634ff4186	209	mpi T;
ansond	0:137634ff4186	210
ansond	0:137634ff4186	211	memcpy( &T, X, sizeof( mpi ) );
ansond	0:137634ff4186	212	memcpy( X, Y, sizeof( mpi ) );
ansond	0:137634ff4186	213	memcpy( Y, &T, sizeof( mpi ) );
ansond	0:137634ff4186	214	}
ansond	0:137634ff4186	215
ansond	0:137634ff4186	216	/*
ansond	0:137634ff4186	217	* Conditionally assign X = Y, without leaking information
ansond	0:137634ff4186	218	* about whether the assignment was made or not.
ansond	0:137634ff4186	219	* (Leaking information about the respective sizes of X and Y is ok however.)
ansond	0:137634ff4186	220	*/
ansond	0:137634ff4186	221	int mpi_safe_cond_assign( mpi X, const mpi Y, unsigned char assign )
ansond	0:137634ff4186	222	{
ansond	0:137634ff4186	223	int ret = 0;
ansond	0:137634ff4186	224	size_t i;
ansond	0:137634ff4186	225
ansond	0:137634ff4186	226	/* make sure assign is 0 or 1 in a time-constant manner */
ansond	0:137634ff4186	227	assign = (assign \| (unsigned char)-assign) >> 7;
ansond	0:137634ff4186	228
ansond	0:137634ff4186	229	MPI_CHK( mpi_grow( X, Y->n ) );
ansond	0:137634ff4186	230
ansond	0:137634ff4186	231	X->s = X->s * ( 1 - assign ) + Y->s * assign;
ansond	0:137634ff4186	232
ansond	0:137634ff4186	233	for( i = 0; i < Y->n; i++ )
ansond	0:137634ff4186	234	X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
ansond	0:137634ff4186	235
ansond	0:137634ff4186	236	for( ; i < X->n; i++ )
ansond	0:137634ff4186	237	X->p[i] *= ( 1 - assign );
ansond	0:137634ff4186	238
ansond	0:137634ff4186	239	cleanup:
ansond	0:137634ff4186	240	return( ret );
ansond	0:137634ff4186	241	}
ansond	0:137634ff4186	242
ansond	0:137634ff4186	243	/*
ansond	0:137634ff4186	244	* Conditionally swap X and Y, without leaking information
ansond	0:137634ff4186	245	* about whether the swap was made or not.
ansond	0:137634ff4186	246	* Here it is not ok to simply swap the pointers, which whould lead to
ansond	0:137634ff4186	247	* different memory access patterns when X and Y are used afterwards.
ansond	0:137634ff4186	248	*/
ansond	0:137634ff4186	249	int mpi_safe_cond_swap( mpi X, mpi Y, unsigned char swap )
ansond	0:137634ff4186	250	{
ansond	0:137634ff4186	251	int ret, s;
ansond	0:137634ff4186	252	size_t i;
ansond	0:137634ff4186	253	t_uint tmp;
ansond	0:137634ff4186	254
ansond	0:137634ff4186	255	if( X == Y )
ansond	0:137634ff4186	256	return( 0 );
ansond	0:137634ff4186	257
ansond	0:137634ff4186	258	/* make sure swap is 0 or 1 in a time-constant manner */
ansond	0:137634ff4186	259	swap = (swap \| (unsigned char)-swap) >> 7;
ansond	0:137634ff4186	260
ansond	0:137634ff4186	261	MPI_CHK( mpi_grow( X, Y->n ) );
ansond	0:137634ff4186	262	MPI_CHK( mpi_grow( Y, X->n ) );
ansond	0:137634ff4186	263
ansond	0:137634ff4186	264	s = X->s;
ansond	0:137634ff4186	265	X->s = X->s * ( 1 - swap ) + Y->s * swap;
ansond	0:137634ff4186	266	Y->s = Y->s * ( 1 - swap ) + s * swap;
ansond	0:137634ff4186	267
ansond	0:137634ff4186	268
ansond	0:137634ff4186	269	for( i = 0; i < X->n; i++ )
ansond	0:137634ff4186	270	{
ansond	0:137634ff4186	271	tmp = X->p[i];
ansond	0:137634ff4186	272	X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
ansond	0:137634ff4186	273	Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
ansond	0:137634ff4186	274	}
ansond	0:137634ff4186	275
ansond	0:137634ff4186	276	cleanup:
ansond	0:137634ff4186	277	return( ret );
ansond	0:137634ff4186	278	}
ansond	0:137634ff4186	279
ansond	0:137634ff4186	280	/*
ansond	0:137634ff4186	281	* Set value from integer
ansond	0:137634ff4186	282	*/
ansond	0:137634ff4186	283	int mpi_lset( mpi *X, t_sint z )
ansond	0:137634ff4186	284	{
ansond	0:137634ff4186	285	int ret;
ansond	0:137634ff4186	286
ansond	0:137634ff4186	287	MPI_CHK( mpi_grow( X, 1 ) );
ansond	0:137634ff4186	288	memset( X->p, 0, X->n * ciL );
ansond	0:137634ff4186	289
ansond	0:137634ff4186	290	X->p[0] = ( z < 0 ) ? -z : z;
ansond	0:137634ff4186	291	X->s = ( z < 0 ) ? -1 : 1;
ansond	0:137634ff4186	292
ansond	0:137634ff4186	293	cleanup:
ansond	0:137634ff4186	294
ansond	0:137634ff4186	295	return( ret );
ansond	0:137634ff4186	296	}
ansond	0:137634ff4186	297
ansond	0:137634ff4186	298	/*
ansond	0:137634ff4186	299	* Get a specific bit
ansond	0:137634ff4186	300	*/
ansond	0:137634ff4186	301	int mpi_get_bit( const mpi *X, size_t pos )
ansond	0:137634ff4186	302	{
ansond	0:137634ff4186	303	if( X->n * biL <= pos )
ansond	0:137634ff4186	304	return( 0 );
ansond	0:137634ff4186	305
ansond	0:137634ff4186	306	return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
ansond	0:137634ff4186	307	}
ansond	0:137634ff4186	308
ansond	0:137634ff4186	309	/*
ansond	0:137634ff4186	310	* Set a bit to a specific value of 0 or 1
ansond	0:137634ff4186	311	*/
ansond	0:137634ff4186	312	int mpi_set_bit( mpi *X, size_t pos, unsigned char val )
ansond	0:137634ff4186	313	{
ansond	0:137634ff4186	314	int ret = 0;
ansond	0:137634ff4186	315	size_t off = pos / biL;
ansond	0:137634ff4186	316	size_t idx = pos % biL;
ansond	0:137634ff4186	317
ansond	0:137634ff4186	318	if( val != 0 && val != 1 )
ansond	0:137634ff4186	319	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	320
ansond	0:137634ff4186	321	if( X->n * biL <= pos )
ansond	0:137634ff4186	322	{
ansond	0:137634ff4186	323	if( val == 0 )
ansond	0:137634ff4186	324	return( 0 );
ansond	0:137634ff4186	325
ansond	0:137634ff4186	326	MPI_CHK( mpi_grow( X, off + 1 ) );
ansond	0:137634ff4186	327	}
ansond	0:137634ff4186	328
ansond	0:137634ff4186	329	X->p[off] &= ~( (t_uint) 0x01 << idx );
ansond	0:137634ff4186	330	X->p[off] \|= (t_uint) val << idx;
ansond	0:137634ff4186	331
ansond	0:137634ff4186	332	cleanup:
ansond	0:137634ff4186	333
ansond	0:137634ff4186	334	return( ret );
ansond	0:137634ff4186	335	}
ansond	0:137634ff4186	336
ansond	0:137634ff4186	337	/*
ansond	0:137634ff4186	338	* Return the number of least significant bits
ansond	0:137634ff4186	339	*/
ansond	0:137634ff4186	340	size_t mpi_lsb( const mpi *X )
ansond	0:137634ff4186	341	{
ansond	0:137634ff4186	342	size_t i, j, count = 0;
ansond	0:137634ff4186	343
ansond	0:137634ff4186	344	for( i = 0; i < X->n; i++ )
ansond	0:137634ff4186	345	for( j = 0; j < biL; j++, count++ )
ansond	0:137634ff4186	346	if( ( ( X->p[i] >> j ) & 1 ) != 0 )
ansond	0:137634ff4186	347	return( count );
ansond	0:137634ff4186	348
ansond	0:137634ff4186	349	return( 0 );
ansond	0:137634ff4186	350	}
ansond	0:137634ff4186	351
ansond	0:137634ff4186	352	/*
ansond	0:137634ff4186	353	* Return the number of most significant bits
ansond	0:137634ff4186	354	*/
ansond	0:137634ff4186	355	size_t mpi_msb( const mpi *X )
ansond	0:137634ff4186	356	{
ansond	0:137634ff4186	357	size_t i, j;
ansond	0:137634ff4186	358
ansond	0:137634ff4186	359	if( X->n == 0 )
ansond	0:137634ff4186	360	return( 0 );
ansond	0:137634ff4186	361
ansond	0:137634ff4186	362	for( i = X->n - 1; i > 0; i-- )
ansond	0:137634ff4186	363	if( X->p[i] != 0 )
ansond	0:137634ff4186	364	break;
ansond	0:137634ff4186	365
ansond	0:137634ff4186	366	for( j = biL; j > 0; j-- )
ansond	0:137634ff4186	367	if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
ansond	0:137634ff4186	368	break;
ansond	0:137634ff4186	369
ansond	0:137634ff4186	370	return( ( i * biL ) + j );
ansond	0:137634ff4186	371	}
ansond	0:137634ff4186	372
ansond	0:137634ff4186	373	/*
ansond	0:137634ff4186	374	* Return the total size in bytes
ansond	0:137634ff4186	375	*/
ansond	0:137634ff4186	376	size_t mpi_size( const mpi *X )
ansond	0:137634ff4186	377	{
ansond	0:137634ff4186	378	return( ( mpi_msb( X ) + 7 ) >> 3 );
ansond	0:137634ff4186	379	}
ansond	0:137634ff4186	380
ansond	0:137634ff4186	381	/*
ansond	0:137634ff4186	382	* Convert an ASCII character to digit value
ansond	0:137634ff4186	383	*/
ansond	0:137634ff4186	384	static int mpi_get_digit( t_uint *d, int radix, char c )
ansond	0:137634ff4186	385	{
ansond	0:137634ff4186	386	*d = 255;
ansond	0:137634ff4186	387
ansond	0:137634ff4186	388	if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
ansond	0:137634ff4186	389	if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
ansond	0:137634ff4186	390	if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
ansond	0:137634ff4186	391
ansond	0:137634ff4186	392	if( *d >= (t_uint) radix )
ansond	0:137634ff4186	393	return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
ansond	0:137634ff4186	394
ansond	0:137634ff4186	395	return( 0 );
ansond	0:137634ff4186	396	}
ansond	0:137634ff4186	397
ansond	0:137634ff4186	398	/*
ansond	0:137634ff4186	399	* Import from an ASCII string
ansond	0:137634ff4186	400	*/
ansond	0:137634ff4186	401	int mpi_read_string( mpi X, int radix, const char s )
ansond	0:137634ff4186	402	{
ansond	0:137634ff4186	403	int ret;
ansond	0:137634ff4186	404	size_t i, j, slen, n;
ansond	0:137634ff4186	405	t_uint d;
ansond	0:137634ff4186	406	mpi T;
ansond	0:137634ff4186	407
ansond	0:137634ff4186	408	if( radix < 2 \|\| radix > 16 )
ansond	0:137634ff4186	409	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	410
ansond	0:137634ff4186	411	mpi_init( &T );
ansond	0:137634ff4186	412
ansond	0:137634ff4186	413	slen = strlen( s );
ansond	0:137634ff4186	414
ansond	0:137634ff4186	415	if( radix == 16 )
ansond	0:137634ff4186	416	{
ansond	0:137634ff4186	417	n = BITS_TO_LIMBS( slen << 2 );
ansond	0:137634ff4186	418
ansond	0:137634ff4186	419	MPI_CHK( mpi_grow( X, n ) );
ansond	0:137634ff4186	420	MPI_CHK( mpi_lset( X, 0 ) );
ansond	0:137634ff4186	421
ansond	0:137634ff4186	422	for( i = slen, j = 0; i > 0; i--, j++ )
ansond	0:137634ff4186	423	{
ansond	0:137634ff4186	424	if( i == 1 && s[i - 1] == '-' )
ansond	0:137634ff4186	425	{
ansond	0:137634ff4186	426	X->s = -1;
ansond	0:137634ff4186	427	break;
ansond	0:137634ff4186	428	}
ansond	0:137634ff4186	429
ansond	0:137634ff4186	430	MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
ansond	0:137634ff4186	431	X->p[j / ( 2 * ciL )] \|= d << ( ( j % ( 2 * ciL ) ) << 2 );
ansond	0:137634ff4186	432	}
ansond	0:137634ff4186	433	}
ansond	0:137634ff4186	434	else
ansond	0:137634ff4186	435	{
ansond	0:137634ff4186	436	MPI_CHK( mpi_lset( X, 0 ) );
ansond	0:137634ff4186	437
ansond	0:137634ff4186	438	for( i = 0; i < slen; i++ )
ansond	0:137634ff4186	439	{
ansond	0:137634ff4186	440	if( i == 0 && s[i] == '-' )
ansond	0:137634ff4186	441	{
ansond	0:137634ff4186	442	X->s = -1;
ansond	0:137634ff4186	443	continue;
ansond	0:137634ff4186	444	}
ansond	0:137634ff4186	445
ansond	0:137634ff4186	446	MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
ansond	0:137634ff4186	447	MPI_CHK( mpi_mul_int( &T, X, radix ) );
ansond	0:137634ff4186	448
ansond	0:137634ff4186	449	if( X->s == 1 )
ansond	0:137634ff4186	450	{
ansond	0:137634ff4186	451	MPI_CHK( mpi_add_int( X, &T, d ) );
ansond	0:137634ff4186	452	}
ansond	0:137634ff4186	453	else
ansond	0:137634ff4186	454	{
ansond	0:137634ff4186	455	MPI_CHK( mpi_sub_int( X, &T, d ) );
ansond	0:137634ff4186	456	}
ansond	0:137634ff4186	457	}
ansond	0:137634ff4186	458	}
ansond	0:137634ff4186	459
ansond	0:137634ff4186	460	cleanup:
ansond	0:137634ff4186	461
ansond	0:137634ff4186	462	mpi_free( &T );
ansond	0:137634ff4186	463
ansond	0:137634ff4186	464	return( ret );
ansond	0:137634ff4186	465	}
ansond	0:137634ff4186	466
ansond	0:137634ff4186	467	/*
ansond	0:137634ff4186	468	* Helper to write the digits high-order first
ansond	0:137634ff4186	469	*/
ansond	0:137634ff4186	470	static int mpi_write_hlp( mpi X, int radix, char *p )
ansond	0:137634ff4186	471	{
ansond	0:137634ff4186	472	int ret;
ansond	0:137634ff4186	473	t_uint r;
ansond	0:137634ff4186	474
ansond	0:137634ff4186	475	if( radix < 2 \|\| radix > 16 )
ansond	0:137634ff4186	476	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	477
ansond	0:137634ff4186	478	MPI_CHK( mpi_mod_int( &r, X, radix ) );
ansond	0:137634ff4186	479	MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
ansond	0:137634ff4186	480
ansond	0:137634ff4186	481	if( mpi_cmp_int( X, 0 ) != 0 )
ansond	0:137634ff4186	482	MPI_CHK( mpi_write_hlp( X, radix, p ) );
ansond	0:137634ff4186	483
ansond	0:137634ff4186	484	if( r < 10 )
ansond	0:137634ff4186	485	(p)++ = (char)( r + 0x30 );
ansond	0:137634ff4186	486	else
ansond	0:137634ff4186	487	(p)++ = (char)( r + 0x37 );
ansond	0:137634ff4186	488
ansond	0:137634ff4186	489	cleanup:
ansond	0:137634ff4186	490
ansond	0:137634ff4186	491	return( ret );
ansond	0:137634ff4186	492	}
ansond	0:137634ff4186	493
ansond	0:137634ff4186	494	/*
ansond	0:137634ff4186	495	* Export into an ASCII string
ansond	0:137634ff4186	496	*/
ansond	0:137634ff4186	497	int mpi_write_string( const mpi X, int radix, char s, size_t *slen )
ansond	0:137634ff4186	498	{
ansond	0:137634ff4186	499	int ret = 0;
ansond	0:137634ff4186	500	size_t n;
ansond	0:137634ff4186	501	char *p;
ansond	0:137634ff4186	502	mpi T;
ansond	0:137634ff4186	503
ansond	0:137634ff4186	504	if( radix < 2 \|\| radix > 16 )
ansond	0:137634ff4186	505	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	506
ansond	0:137634ff4186	507	n = mpi_msb( X );
ansond	0:137634ff4186	508	if( radix >= 4 ) n >>= 1;
ansond	0:137634ff4186	509	if( radix >= 16 ) n >>= 1;
ansond	0:137634ff4186	510	n += 3;
ansond	0:137634ff4186	511
ansond	0:137634ff4186	512	if( *slen < n )
ansond	0:137634ff4186	513	{
ansond	0:137634ff4186	514	*slen = n;
ansond	0:137634ff4186	515	return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
ansond	0:137634ff4186	516	}
ansond	0:137634ff4186	517
ansond	0:137634ff4186	518	p = s;
ansond	0:137634ff4186	519	mpi_init( &T );
ansond	0:137634ff4186	520
ansond	0:137634ff4186	521	if( X->s == -1 )
ansond	0:137634ff4186	522	*p++ = '-';
ansond	0:137634ff4186	523
ansond	0:137634ff4186	524	if( radix == 16 )
ansond	0:137634ff4186	525	{
ansond	0:137634ff4186	526	int c;
ansond	0:137634ff4186	527	size_t i, j, k;
ansond	0:137634ff4186	528
ansond	0:137634ff4186	529	for( i = X->n, k = 0; i > 0; i-- )
ansond	0:137634ff4186	530	{
ansond	0:137634ff4186	531	for( j = ciL; j > 0; j-- )
ansond	0:137634ff4186	532	{
ansond	0:137634ff4186	533	c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
ansond	0:137634ff4186	534
ansond	0:137634ff4186	535	if( c == 0 && k == 0 && ( i + j ) != 2 )
ansond	0:137634ff4186	536	continue;
ansond	0:137634ff4186	537
ansond	0:137634ff4186	538	*(p++) = "0123456789ABCDEF" [c / 16];
ansond	0:137634ff4186	539	*(p++) = "0123456789ABCDEF" [c % 16];
ansond	0:137634ff4186	540	k = 1;
ansond	0:137634ff4186	541	}
ansond	0:137634ff4186	542	}
ansond	0:137634ff4186	543	}
ansond	0:137634ff4186	544	else
ansond	0:137634ff4186	545	{
ansond	0:137634ff4186	546	MPI_CHK( mpi_copy( &T, X ) );
ansond	0:137634ff4186	547
ansond	0:137634ff4186	548	if( T.s == -1 )
ansond	0:137634ff4186	549	T.s = 1;
ansond	0:137634ff4186	550
ansond	0:137634ff4186	551	MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
ansond	0:137634ff4186	552	}
ansond	0:137634ff4186	553
ansond	0:137634ff4186	554	*p++ = '\0';
ansond	0:137634ff4186	555	*slen = p - s;
ansond	0:137634ff4186	556
ansond	0:137634ff4186	557	cleanup:
ansond	0:137634ff4186	558
ansond	0:137634ff4186	559	mpi_free( &T );
ansond	0:137634ff4186	560
ansond	0:137634ff4186	561	return( ret );
ansond	0:137634ff4186	562	}
ansond	0:137634ff4186	563
ansond	0:137634ff4186	564	#if defined(POLARSSL_FS_IO)
ansond	0:137634ff4186	565	/*
ansond	0:137634ff4186	566	* Read X from an opened file
ansond	0:137634ff4186	567	*/
ansond	0:137634ff4186	568	int mpi_read_file( mpi X, int radix, FILE fin )
ansond	0:137634ff4186	569	{
ansond	0:137634ff4186	570	t_uint d;
ansond	0:137634ff4186	571	size_t slen;
ansond	0:137634ff4186	572	char *p;
ansond	0:137634ff4186	573	/*
ansond	0:137634ff4186	574	* Buffer should have space for (short) label and decimal formatted MPI,
ansond	0:137634ff4186	575	* newline characters and '\0'
ansond	0:137634ff4186	576	*/
ansond	0:137634ff4186	577	char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
ansond	0:137634ff4186	578
ansond	0:137634ff4186	579	memset( s, 0, sizeof( s ) );
ansond	0:137634ff4186	580	if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
ansond	0:137634ff4186	581	return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
ansond	0:137634ff4186	582
ansond	0:137634ff4186	583	slen = strlen( s );
ansond	0:137634ff4186	584	if( slen == sizeof( s ) - 2 )
ansond	0:137634ff4186	585	return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
ansond	0:137634ff4186	586
ansond	0:137634ff4186	587	if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
ansond	0:137634ff4186	588	if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
ansond	0:137634ff4186	589
ansond	0:137634ff4186	590	p = s + slen;
ansond	0:137634ff4186	591	while( --p >= s )
ansond	0:137634ff4186	592	if( mpi_get_digit( &d, radix, *p ) != 0 )
ansond	0:137634ff4186	593	break;
ansond	0:137634ff4186	594
ansond	0:137634ff4186	595	return( mpi_read_string( X, radix, p + 1 ) );
ansond	0:137634ff4186	596	}
ansond	0:137634ff4186	597
ansond	0:137634ff4186	598	/*
ansond	0:137634ff4186	599	* Write X into an opened file (or stdout if fout == NULL)
ansond	0:137634ff4186	600	*/
ansond	0:137634ff4186	601	int mpi_write_file( const char p, const mpi X, int radix, FILE *fout )
ansond	0:137634ff4186	602	{
ansond	0:137634ff4186	603	int ret;
ansond	0:137634ff4186	604	size_t n, slen, plen;
ansond	0:137634ff4186	605	/*
ansond	0:137634ff4186	606	* Buffer should have space for (short) label and decimal formatted MPI,
ansond	0:137634ff4186	607	* newline characters and '\0'
ansond	0:137634ff4186	608	*/
ansond	0:137634ff4186	609	char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
ansond	0:137634ff4186	610
ansond	0:137634ff4186	611	n = sizeof( s );
ansond	0:137634ff4186	612	memset( s, 0, n );
ansond	0:137634ff4186	613	n -= 2;
ansond	0:137634ff4186	614
ansond	0:137634ff4186	615	MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) );
ansond	0:137634ff4186	616
ansond	0:137634ff4186	617	if( p == NULL ) p = "";
ansond	0:137634ff4186	618
ansond	0:137634ff4186	619	plen = strlen( p );
ansond	0:137634ff4186	620	slen = strlen( s );
ansond	0:137634ff4186	621	s[slen++] = '\r';
ansond	0:137634ff4186	622	s[slen++] = '\n';
ansond	0:137634ff4186	623
ansond	0:137634ff4186	624	if( fout != NULL )
ansond	0:137634ff4186	625	{
ansond	0:137634ff4186	626	if( fwrite( p, 1, plen, fout ) != plen \|\|
ansond	0:137634ff4186	627	fwrite( s, 1, slen, fout ) != slen )
ansond	0:137634ff4186	628	return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
ansond	0:137634ff4186	629	}
ansond	0:137634ff4186	630	else
ansond	0:137634ff4186	631	polarssl_printf( "%s%s", p, s );
ansond	0:137634ff4186	632
ansond	0:137634ff4186	633	cleanup:
ansond	0:137634ff4186	634
ansond	0:137634ff4186	635	return( ret );
ansond	0:137634ff4186	636	}
ansond	0:137634ff4186	637	#endif /* POLARSSL_FS_IO */
ansond	0:137634ff4186	638
ansond	0:137634ff4186	639	/*
ansond	0:137634ff4186	640	* Import X from unsigned binary data, big endian
ansond	0:137634ff4186	641	*/
ansond	0:137634ff4186	642	int mpi_read_binary( mpi X, const unsigned char buf, size_t buflen )
ansond	0:137634ff4186	643	{
ansond	0:137634ff4186	644	int ret;
ansond	0:137634ff4186	645	size_t i, j, n;
ansond	0:137634ff4186	646
ansond	0:137634ff4186	647	for( n = 0; n < buflen; n++ )
ansond	0:137634ff4186	648	if( buf[n] != 0 )
ansond	0:137634ff4186	649	break;
ansond	0:137634ff4186	650
ansond	0:137634ff4186	651	MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
ansond	0:137634ff4186	652	MPI_CHK( mpi_lset( X, 0 ) );
ansond	0:137634ff4186	653
ansond	0:137634ff4186	654	for( i = buflen, j = 0; i > n; i--, j++ )
ansond	0:137634ff4186	655	X->p[j / ciL] \|= ((t_uint) buf[i - 1]) << ((j % ciL) << 3);
ansond	0:137634ff4186	656
ansond	0:137634ff4186	657	cleanup:
ansond	0:137634ff4186	658
ansond	0:137634ff4186	659	return( ret );
ansond	0:137634ff4186	660	}
ansond	0:137634ff4186	661
ansond	0:137634ff4186	662	/*
ansond	0:137634ff4186	663	* Export X into unsigned binary data, big endian
ansond	0:137634ff4186	664	*/
ansond	0:137634ff4186	665	int mpi_write_binary( const mpi X, unsigned char buf, size_t buflen )
ansond	0:137634ff4186	666	{
ansond	0:137634ff4186	667	size_t i, j, n;
ansond	0:137634ff4186	668
ansond	0:137634ff4186	669	n = mpi_size( X );
ansond	0:137634ff4186	670
ansond	0:137634ff4186	671	if( buflen < n )
ansond	0:137634ff4186	672	return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
ansond	0:137634ff4186	673
ansond	0:137634ff4186	674	memset( buf, 0, buflen );
ansond	0:137634ff4186	675
ansond	0:137634ff4186	676	for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
ansond	0:137634ff4186	677	buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
ansond	0:137634ff4186	678
ansond	0:137634ff4186	679	return( 0 );
ansond	0:137634ff4186	680	}
ansond	0:137634ff4186	681
ansond	0:137634ff4186	682	/*
ansond	0:137634ff4186	683	* Left-shift: X <<= count
ansond	0:137634ff4186	684	*/
ansond	0:137634ff4186	685	int mpi_shift_l( mpi *X, size_t count )
ansond	0:137634ff4186	686	{
ansond	0:137634ff4186	687	int ret;
ansond	0:137634ff4186	688	size_t i, v0, t1;
ansond	0:137634ff4186	689	t_uint r0 = 0, r1;
ansond	0:137634ff4186	690
ansond	0:137634ff4186	691	v0 = count / (biL );
ansond	0:137634ff4186	692	t1 = count & (biL - 1);
ansond	0:137634ff4186	693
ansond	0:137634ff4186	694	i = mpi_msb( X ) + count;
ansond	0:137634ff4186	695
ansond	0:137634ff4186	696	if( X->n * biL < i )
ansond	0:137634ff4186	697	MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
ansond	0:137634ff4186	698
ansond	0:137634ff4186	699	ret = 0;
ansond	0:137634ff4186	700
ansond	0:137634ff4186	701	/*
ansond	0:137634ff4186	702	* shift by count / limb_size
ansond	0:137634ff4186	703	*/
ansond	0:137634ff4186	704	if( v0 > 0 )
ansond	0:137634ff4186	705	{
ansond	0:137634ff4186	706	for( i = X->n; i > v0; i-- )
ansond	0:137634ff4186	707	X->p[i - 1] = X->p[i - v0 - 1];
ansond	0:137634ff4186	708
ansond	0:137634ff4186	709	for( ; i > 0; i-- )
ansond	0:137634ff4186	710	X->p[i - 1] = 0;
ansond	0:137634ff4186	711	}
ansond	0:137634ff4186	712
ansond	0:137634ff4186	713	/*
ansond	0:137634ff4186	714	* shift by count % limb_size
ansond	0:137634ff4186	715	*/
ansond	0:137634ff4186	716	if( t1 > 0 )
ansond	0:137634ff4186	717	{
ansond	0:137634ff4186	718	for( i = v0; i < X->n; i++ )
ansond	0:137634ff4186	719	{
ansond	0:137634ff4186	720	r1 = X->p[i] >> (biL - t1);
ansond	0:137634ff4186	721	X->p[i] <<= t1;
ansond	0:137634ff4186	722	X->p[i] \|= r0;
ansond	0:137634ff4186	723	r0 = r1;
ansond	0:137634ff4186	724	}
ansond	0:137634ff4186	725	}
ansond	0:137634ff4186	726
ansond	0:137634ff4186	727	cleanup:
ansond	0:137634ff4186	728
ansond	0:137634ff4186	729	return( ret );
ansond	0:137634ff4186	730	}
ansond	0:137634ff4186	731
ansond	0:137634ff4186	732	/*
ansond	0:137634ff4186	733	* Right-shift: X >>= count
ansond	0:137634ff4186	734	*/
ansond	0:137634ff4186	735	int mpi_shift_r( mpi *X, size_t count )
ansond	0:137634ff4186	736	{
ansond	0:137634ff4186	737	size_t i, v0, v1;
ansond	0:137634ff4186	738	t_uint r0 = 0, r1;
ansond	0:137634ff4186	739
ansond	0:137634ff4186	740	v0 = count / biL;
ansond	0:137634ff4186	741	v1 = count & (biL - 1);
ansond	0:137634ff4186	742
ansond	0:137634ff4186	743	if( v0 > X->n \|\| ( v0 == X->n && v1 > 0 ) )
ansond	0:137634ff4186	744	return mpi_lset( X, 0 );
ansond	0:137634ff4186	745
ansond	0:137634ff4186	746	/*
ansond	0:137634ff4186	747	* shift by count / limb_size
ansond	0:137634ff4186	748	*/
ansond	0:137634ff4186	749	if( v0 > 0 )
ansond	0:137634ff4186	750	{
ansond	0:137634ff4186	751	for( i = 0; i < X->n - v0; i++ )
ansond	0:137634ff4186	752	X->p[i] = X->p[i + v0];
ansond	0:137634ff4186	753
ansond	0:137634ff4186	754	for( ; i < X->n; i++ )
ansond	0:137634ff4186	755	X->p[i] = 0;
ansond	0:137634ff4186	756	}
ansond	0:137634ff4186	757
ansond	0:137634ff4186	758	/*
ansond	0:137634ff4186	759	* shift by count % limb_size
ansond	0:137634ff4186	760	*/
ansond	0:137634ff4186	761	if( v1 > 0 )
ansond	0:137634ff4186	762	{
ansond	0:137634ff4186	763	for( i = X->n; i > 0; i-- )
ansond	0:137634ff4186	764	{
ansond	0:137634ff4186	765	r1 = X->p[i - 1] << (biL - v1);
ansond	0:137634ff4186	766	X->p[i - 1] >>= v1;
ansond	0:137634ff4186	767	X->p[i - 1] \|= r0;
ansond	0:137634ff4186	768	r0 = r1;
ansond	0:137634ff4186	769	}
ansond	0:137634ff4186	770	}
ansond	0:137634ff4186	771
ansond	0:137634ff4186	772	return( 0 );
ansond	0:137634ff4186	773	}
ansond	0:137634ff4186	774
ansond	0:137634ff4186	775	/*
ansond	0:137634ff4186	776	* Compare unsigned values
ansond	0:137634ff4186	777	*/
ansond	0:137634ff4186	778	int mpi_cmp_abs( const mpi X, const mpi Y )
ansond	0:137634ff4186	779	{
ansond	0:137634ff4186	780	size_t i, j;
ansond	0:137634ff4186	781
ansond	0:137634ff4186	782	for( i = X->n; i > 0; i-- )
ansond	0:137634ff4186	783	if( X->p[i - 1] != 0 )
ansond	0:137634ff4186	784	break;
ansond	0:137634ff4186	785
ansond	0:137634ff4186	786	for( j = Y->n; j > 0; j-- )
ansond	0:137634ff4186	787	if( Y->p[j - 1] != 0 )
ansond	0:137634ff4186	788	break;
ansond	0:137634ff4186	789
ansond	0:137634ff4186	790	if( i == 0 && j == 0 )
ansond	0:137634ff4186	791	return( 0 );
ansond	0:137634ff4186	792
ansond	0:137634ff4186	793	if( i > j ) return( 1 );
ansond	0:137634ff4186	794	if( j > i ) return( -1 );
ansond	0:137634ff4186	795
ansond	0:137634ff4186	796	for( ; i > 0; i-- )
ansond	0:137634ff4186	797	{
ansond	0:137634ff4186	798	if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
ansond	0:137634ff4186	799	if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
ansond	0:137634ff4186	800	}
ansond	0:137634ff4186	801
ansond	0:137634ff4186	802	return( 0 );
ansond	0:137634ff4186	803	}
ansond	0:137634ff4186	804
ansond	0:137634ff4186	805	/*
ansond	0:137634ff4186	806	* Compare signed values
ansond	0:137634ff4186	807	*/
ansond	0:137634ff4186	808	int mpi_cmp_mpi( const mpi X, const mpi Y )
ansond	0:137634ff4186	809	{
ansond	0:137634ff4186	810	size_t i, j;
ansond	0:137634ff4186	811
ansond	0:137634ff4186	812	for( i = X->n; i > 0; i-- )
ansond	0:137634ff4186	813	if( X->p[i - 1] != 0 )
ansond	0:137634ff4186	814	break;
ansond	0:137634ff4186	815
ansond	0:137634ff4186	816	for( j = Y->n; j > 0; j-- )
ansond	0:137634ff4186	817	if( Y->p[j - 1] != 0 )
ansond	0:137634ff4186	818	break;
ansond	0:137634ff4186	819
ansond	0:137634ff4186	820	if( i == 0 && j == 0 )
ansond	0:137634ff4186	821	return( 0 );
ansond	0:137634ff4186	822
ansond	0:137634ff4186	823	if( i > j ) return( X->s );
ansond	0:137634ff4186	824	if( j > i ) return( -Y->s );
ansond	0:137634ff4186	825
ansond	0:137634ff4186	826	if( X->s > 0 && Y->s < 0 ) return( 1 );
ansond	0:137634ff4186	827	if( Y->s > 0 && X->s < 0 ) return( -1 );
ansond	0:137634ff4186	828
ansond	0:137634ff4186	829	for( ; i > 0; i-- )
ansond	0:137634ff4186	830	{
ansond	0:137634ff4186	831	if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
ansond	0:137634ff4186	832	if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
ansond	0:137634ff4186	833	}
ansond	0:137634ff4186	834
ansond	0:137634ff4186	835	return( 0 );
ansond	0:137634ff4186	836	}
ansond	0:137634ff4186	837
ansond	0:137634ff4186	838	/*
ansond	0:137634ff4186	839	* Compare signed values
ansond	0:137634ff4186	840	*/
ansond	0:137634ff4186	841	int mpi_cmp_int( const mpi *X, t_sint z )
ansond	0:137634ff4186	842	{
ansond	0:137634ff4186	843	mpi Y;
ansond	0:137634ff4186	844	t_uint p[1];
ansond	0:137634ff4186	845
ansond	0:137634ff4186	846	*p = ( z < 0 ) ? -z : z;
ansond	0:137634ff4186	847	Y.s = ( z < 0 ) ? -1 : 1;
ansond	0:137634ff4186	848	Y.n = 1;
ansond	0:137634ff4186	849	Y.p = p;
ansond	0:137634ff4186	850
ansond	0:137634ff4186	851	return( mpi_cmp_mpi( X, &Y ) );
ansond	0:137634ff4186	852	}
ansond	0:137634ff4186	853
ansond	0:137634ff4186	854	/*
ansond	0:137634ff4186	855	* Unsigned addition: X = \|A\| + \|B\| (HAC 14.7)
ansond	0:137634ff4186	856	*/
ansond	0:137634ff4186	857	int mpi_add_abs( mpi X, const mpi A, const mpi *B )
ansond	0:137634ff4186	858	{
ansond	0:137634ff4186	859	int ret;
ansond	0:137634ff4186	860	size_t i, j;
ansond	0:137634ff4186	861	t_uint o, p, c;
ansond	0:137634ff4186	862
ansond	0:137634ff4186	863	if( X == B )
ansond	0:137634ff4186	864	{
ansond	0:137634ff4186	865	const mpi *T = A; A = X; B = T;
ansond	0:137634ff4186	866	}
ansond	0:137634ff4186	867
ansond	0:137634ff4186	868	if( X != A )
ansond	0:137634ff4186	869	MPI_CHK( mpi_copy( X, A ) );
ansond	0:137634ff4186	870
ansond	0:137634ff4186	871	/*
ansond	0:137634ff4186	872	* X should always be positive as a result of unsigned additions.
ansond	0:137634ff4186	873	*/
ansond	0:137634ff4186	874	X->s = 1;
ansond	0:137634ff4186	875
ansond	0:137634ff4186	876	for( j = B->n; j > 0; j-- )
ansond	0:137634ff4186	877	if( B->p[j - 1] != 0 )
ansond	0:137634ff4186	878	break;
ansond	0:137634ff4186	879
ansond	0:137634ff4186	880	MPI_CHK( mpi_grow( X, j ) );
ansond	0:137634ff4186	881
ansond	0:137634ff4186	882	o = B->p; p = X->p; c = 0;
ansond	0:137634ff4186	883
ansond	0:137634ff4186	884	for( i = 0; i < j; i++, o++, p++ )
ansond	0:137634ff4186	885	{
ansond	0:137634ff4186	886	p += c; c = ( p < c );
ansond	0:137634ff4186	887	p += o; c += ( p < o );
ansond	0:137634ff4186	888	}
ansond	0:137634ff4186	889
ansond	0:137634ff4186	890	while( c != 0 )
ansond	0:137634ff4186	891	{
ansond	0:137634ff4186	892	if( i >= X->n )
ansond	0:137634ff4186	893	{
ansond	0:137634ff4186	894	MPI_CHK( mpi_grow( X, i + 1 ) );
ansond	0:137634ff4186	895	p = X->p + i;
ansond	0:137634ff4186	896	}
ansond	0:137634ff4186	897
ansond	0:137634ff4186	898	p += c; c = ( p < c ); i++; p++;
ansond	0:137634ff4186	899	}
ansond	0:137634ff4186	900
ansond	0:137634ff4186	901	cleanup:
ansond	0:137634ff4186	902
ansond	0:137634ff4186	903	return( ret );
ansond	0:137634ff4186	904	}
ansond	0:137634ff4186	905
ansond	0:137634ff4186	906	/*
ansond	0:137634ff4186	907	* Helper for mpi subtraction
ansond	0:137634ff4186	908	*/
ansond	0:137634ff4186	909	static void mpi_sub_hlp( size_t n, t_uint s, t_uint d )
ansond	0:137634ff4186	910	{
ansond	0:137634ff4186	911	size_t i;
ansond	0:137634ff4186	912	t_uint c, z;
ansond	0:137634ff4186	913
ansond	0:137634ff4186	914	for( i = c = 0; i < n; i++, s++, d++ )
ansond	0:137634ff4186	915	{
ansond	0:137634ff4186	916	z = ( d < c ); d -= c;
ansond	0:137634ff4186	917	c = ( d < s ) + z; d -= s;
ansond	0:137634ff4186	918	}
ansond	0:137634ff4186	919
ansond	0:137634ff4186	920	while( c != 0 )
ansond	0:137634ff4186	921	{
ansond	0:137634ff4186	922	z = ( d < c ); d -= c;
ansond	0:137634ff4186	923	c = z; i++; d++;
ansond	0:137634ff4186	924	}
ansond	0:137634ff4186	925	}
ansond	0:137634ff4186	926
ansond	0:137634ff4186	927	/*
ansond	0:137634ff4186	928	* Unsigned subtraction: X = \|A\| - \|B\| (HAC 14.9)
ansond	0:137634ff4186	929	*/
ansond	0:137634ff4186	930	int mpi_sub_abs( mpi X, const mpi A, const mpi *B )
ansond	0:137634ff4186	931	{
ansond	0:137634ff4186	932	mpi TB;
ansond	0:137634ff4186	933	int ret;
ansond	0:137634ff4186	934	size_t n;
ansond	0:137634ff4186	935
ansond	0:137634ff4186	936	if( mpi_cmp_abs( A, B ) < 0 )
ansond	0:137634ff4186	937	return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
ansond	0:137634ff4186	938
ansond	0:137634ff4186	939	mpi_init( &TB );
ansond	0:137634ff4186	940
ansond	0:137634ff4186	941	if( X == B )
ansond	0:137634ff4186	942	{
ansond	0:137634ff4186	943	MPI_CHK( mpi_copy( &TB, B ) );
ansond	0:137634ff4186	944	B = &TB;
ansond	0:137634ff4186	945	}
ansond	0:137634ff4186	946
ansond	0:137634ff4186	947	if( X != A )
ansond	0:137634ff4186	948	MPI_CHK( mpi_copy( X, A ) );
ansond	0:137634ff4186	949
ansond	0:137634ff4186	950	/*
ansond	0:137634ff4186	951	* X should always be positive as a result of unsigned subtractions.
ansond	0:137634ff4186	952	*/
ansond	0:137634ff4186	953	X->s = 1;
ansond	0:137634ff4186	954
ansond	0:137634ff4186	955	ret = 0;
ansond	0:137634ff4186	956
ansond	0:137634ff4186	957	for( n = B->n; n > 0; n-- )
ansond	0:137634ff4186	958	if( B->p[n - 1] != 0 )
ansond	0:137634ff4186	959	break;
ansond	0:137634ff4186	960
ansond	0:137634ff4186	961	mpi_sub_hlp( n, B->p, X->p );
ansond	0:137634ff4186	962
ansond	0:137634ff4186	963	cleanup:
ansond	0:137634ff4186	964
ansond	0:137634ff4186	965	mpi_free( &TB );
ansond	0:137634ff4186	966
ansond	0:137634ff4186	967	return( ret );
ansond	0:137634ff4186	968	}
ansond	0:137634ff4186	969
ansond	0:137634ff4186	970	/*
ansond	0:137634ff4186	971	* Signed addition: X = A + B
ansond	0:137634ff4186	972	*/
ansond	0:137634ff4186	973	int mpi_add_mpi( mpi X, const mpi A, const mpi *B )
ansond	0:137634ff4186	974	{
ansond	0:137634ff4186	975	int ret, s = A->s;
ansond	0:137634ff4186	976
ansond	0:137634ff4186	977	if( A->s * B->s < 0 )
ansond	0:137634ff4186	978	{
ansond	0:137634ff4186	979	if( mpi_cmp_abs( A, B ) >= 0 )
ansond	0:137634ff4186	980	{
ansond	0:137634ff4186	981	MPI_CHK( mpi_sub_abs( X, A, B ) );
ansond	0:137634ff4186	982	X->s = s;
ansond	0:137634ff4186	983	}
ansond	0:137634ff4186	984	else
ansond	0:137634ff4186	985	{
ansond	0:137634ff4186	986	MPI_CHK( mpi_sub_abs( X, B, A ) );
ansond	0:137634ff4186	987	X->s = -s;
ansond	0:137634ff4186	988	}
ansond	0:137634ff4186	989	}
ansond	0:137634ff4186	990	else
ansond	0:137634ff4186	991	{
ansond	0:137634ff4186	992	MPI_CHK( mpi_add_abs( X, A, B ) );
ansond	0:137634ff4186	993	X->s = s;
ansond	0:137634ff4186	994	}
ansond	0:137634ff4186	995
ansond	0:137634ff4186	996	cleanup:
ansond	0:137634ff4186	997
ansond	0:137634ff4186	998	return( ret );
ansond	0:137634ff4186	999	}
ansond	0:137634ff4186	1000
ansond	0:137634ff4186	1001	/*
ansond	0:137634ff4186	1002	* Signed subtraction: X = A - B
ansond	0:137634ff4186	1003	*/
ansond	0:137634ff4186	1004	int mpi_sub_mpi( mpi X, const mpi A, const mpi *B )
ansond	0:137634ff4186	1005	{
ansond	0:137634ff4186	1006	int ret, s = A->s;
ansond	0:137634ff4186	1007
ansond	0:137634ff4186	1008	if( A->s * B->s > 0 )
ansond	0:137634ff4186	1009	{
ansond	0:137634ff4186	1010	if( mpi_cmp_abs( A, B ) >= 0 )
ansond	0:137634ff4186	1011	{
ansond	0:137634ff4186	1012	MPI_CHK( mpi_sub_abs( X, A, B ) );
ansond	0:137634ff4186	1013	X->s = s;
ansond	0:137634ff4186	1014	}
ansond	0:137634ff4186	1015	else
ansond	0:137634ff4186	1016	{
ansond	0:137634ff4186	1017	MPI_CHK( mpi_sub_abs( X, B, A ) );
ansond	0:137634ff4186	1018	X->s = -s;
ansond	0:137634ff4186	1019	}
ansond	0:137634ff4186	1020	}
ansond	0:137634ff4186	1021	else
ansond	0:137634ff4186	1022	{
ansond	0:137634ff4186	1023	MPI_CHK( mpi_add_abs( X, A, B ) );
ansond	0:137634ff4186	1024	X->s = s;
ansond	0:137634ff4186	1025	}
ansond	0:137634ff4186	1026
ansond	0:137634ff4186	1027	cleanup:
ansond	0:137634ff4186	1028
ansond	0:137634ff4186	1029	return( ret );
ansond	0:137634ff4186	1030	}
ansond	0:137634ff4186	1031
ansond	0:137634ff4186	1032	/*
ansond	0:137634ff4186	1033	* Signed addition: X = A + b
ansond	0:137634ff4186	1034	*/
ansond	0:137634ff4186	1035	int mpi_add_int( mpi X, const mpi A, t_sint b )
ansond	0:137634ff4186	1036	{
ansond	0:137634ff4186	1037	mpi _B;
ansond	0:137634ff4186	1038	t_uint p[1];
ansond	0:137634ff4186	1039
ansond	0:137634ff4186	1040	p[0] = ( b < 0 ) ? -b : b;
ansond	0:137634ff4186	1041	_B.s = ( b < 0 ) ? -1 : 1;
ansond	0:137634ff4186	1042	_B.n = 1;
ansond	0:137634ff4186	1043	_B.p = p;
ansond	0:137634ff4186	1044
ansond	0:137634ff4186	1045	return( mpi_add_mpi( X, A, &_B ) );
ansond	0:137634ff4186	1046	}
ansond	0:137634ff4186	1047
ansond	0:137634ff4186	1048	/*
ansond	0:137634ff4186	1049	* Signed subtraction: X = A - b
ansond	0:137634ff4186	1050	*/
ansond	0:137634ff4186	1051	int mpi_sub_int( mpi X, const mpi A, t_sint b )
ansond	0:137634ff4186	1052	{
ansond	0:137634ff4186	1053	mpi _B;
ansond	0:137634ff4186	1054	t_uint p[1];
ansond	0:137634ff4186	1055
ansond	0:137634ff4186	1056	p[0] = ( b < 0 ) ? -b : b;
ansond	0:137634ff4186	1057	_B.s = ( b < 0 ) ? -1 : 1;
ansond	0:137634ff4186	1058	_B.n = 1;
ansond	0:137634ff4186	1059	_B.p = p;
ansond	0:137634ff4186	1060
ansond	0:137634ff4186	1061	return( mpi_sub_mpi( X, A, &_B ) );
ansond	0:137634ff4186	1062	}
ansond	0:137634ff4186	1063
ansond	0:137634ff4186	1064	/*
ansond	0:137634ff4186	1065	* Helper for mpi multiplication
ansond	0:137634ff4186	1066	*/
ansond	0:137634ff4186	1067	static
ansond	0:137634ff4186	1068	#if defined(__APPLE__) && defined(__arm__)
ansond	0:137634ff4186	1069	/*
ansond	0:137634ff4186	1070	* Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
ansond	0:137634ff4186	1071	* appears to need this to prevent bad ARM code generation at -O3.
ansond	0:137634ff4186	1072	*/
ansond	0:137634ff4186	1073	__attribute__ ((noinline))
ansond	0:137634ff4186	1074	#endif
ansond	0:137634ff4186	1075	void mpi_mul_hlp( size_t i, t_uint s, t_uint d, t_uint b )
ansond	0:137634ff4186	1076	{
ansond	0:137634ff4186	1077	t_uint c = 0, t = 0;
ansond	0:137634ff4186	1078
ansond	0:137634ff4186	1079	#if defined(MULADDC_HUIT)
ansond	0:137634ff4186	1080	for( ; i >= 8; i -= 8 )
ansond	0:137634ff4186	1081	{
ansond	0:137634ff4186	1082	MULADDC_INIT
ansond	0:137634ff4186	1083	MULADDC_HUIT
ansond	0:137634ff4186	1084	MULADDC_STOP
ansond	0:137634ff4186	1085	}
ansond	0:137634ff4186	1086
ansond	0:137634ff4186	1087	for( ; i > 0; i-- )
ansond	0:137634ff4186	1088	{
ansond	0:137634ff4186	1089	MULADDC_INIT
ansond	0:137634ff4186	1090	MULADDC_CORE
ansond	0:137634ff4186	1091	MULADDC_STOP
ansond	0:137634ff4186	1092	}
ansond	0:137634ff4186	1093	#else /* MULADDC_HUIT */
ansond	0:137634ff4186	1094	for( ; i >= 16; i -= 16 )
ansond	0:137634ff4186	1095	{
ansond	0:137634ff4186	1096	MULADDC_INIT
ansond	0:137634ff4186	1097	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1098	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1099	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1100	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1101
ansond	0:137634ff4186	1102	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1103	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1104	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1105	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1106	MULADDC_STOP
ansond	0:137634ff4186	1107	}
ansond	0:137634ff4186	1108
ansond	0:137634ff4186	1109	for( ; i >= 8; i -= 8 )
ansond	0:137634ff4186	1110	{
ansond	0:137634ff4186	1111	MULADDC_INIT
ansond	0:137634ff4186	1112	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1113	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1114
ansond	0:137634ff4186	1115	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1116	MULADDC_CORE MULADDC_CORE
ansond	0:137634ff4186	1117	MULADDC_STOP
ansond	0:137634ff4186	1118	}
ansond	0:137634ff4186	1119
ansond	0:137634ff4186	1120	for( ; i > 0; i-- )
ansond	0:137634ff4186	1121	{
ansond	0:137634ff4186	1122	MULADDC_INIT
ansond	0:137634ff4186	1123	MULADDC_CORE
ansond	0:137634ff4186	1124	MULADDC_STOP
ansond	0:137634ff4186	1125	}
ansond	0:137634ff4186	1126	#endif /* MULADDC_HUIT */
ansond	0:137634ff4186	1127
ansond	0:137634ff4186	1128	t++;
ansond	0:137634ff4186	1129
ansond	0:137634ff4186	1130	do {
ansond	0:137634ff4186	1131	d += c; c = ( d < c ); d++;
ansond	0:137634ff4186	1132	}
ansond	0:137634ff4186	1133	while( c != 0 );
ansond	0:137634ff4186	1134	}
ansond	0:137634ff4186	1135
ansond	0:137634ff4186	1136	/*
ansond	0:137634ff4186	1137	* Baseline multiplication: X = A * B (HAC 14.12)
ansond	0:137634ff4186	1138	*/
ansond	0:137634ff4186	1139	int mpi_mul_mpi( mpi X, const mpi A, const mpi *B )
ansond	0:137634ff4186	1140	{
ansond	0:137634ff4186	1141	int ret;
ansond	0:137634ff4186	1142	size_t i, j;
ansond	0:137634ff4186	1143	mpi TA, TB;
ansond	0:137634ff4186	1144
ansond	0:137634ff4186	1145	mpi_init( &TA ); mpi_init( &TB );
ansond	0:137634ff4186	1146
ansond	0:137634ff4186	1147	if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
ansond	0:137634ff4186	1148	if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
ansond	0:137634ff4186	1149
ansond	0:137634ff4186	1150	for( i = A->n; i > 0; i-- )
ansond	0:137634ff4186	1151	if( A->p[i - 1] != 0 )
ansond	0:137634ff4186	1152	break;
ansond	0:137634ff4186	1153
ansond	0:137634ff4186	1154	for( j = B->n; j > 0; j-- )
ansond	0:137634ff4186	1155	if( B->p[j - 1] != 0 )
ansond	0:137634ff4186	1156	break;
ansond	0:137634ff4186	1157
ansond	0:137634ff4186	1158	MPI_CHK( mpi_grow( X, i + j ) );
ansond	0:137634ff4186	1159	MPI_CHK( mpi_lset( X, 0 ) );
ansond	0:137634ff4186	1160
ansond	0:137634ff4186	1161	for( i++; j > 0; j-- )
ansond	0:137634ff4186	1162	mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
ansond	0:137634ff4186	1163
ansond	0:137634ff4186	1164	X->s = A->s * B->s;
ansond	0:137634ff4186	1165
ansond	0:137634ff4186	1166	cleanup:
ansond	0:137634ff4186	1167
ansond	0:137634ff4186	1168	mpi_free( &TB ); mpi_free( &TA );
ansond	0:137634ff4186	1169
ansond	0:137634ff4186	1170	return( ret );
ansond	0:137634ff4186	1171	}
ansond	0:137634ff4186	1172
ansond	0:137634ff4186	1173	/*
ansond	0:137634ff4186	1174	* Baseline multiplication: X = A * b
ansond	0:137634ff4186	1175	*/
ansond	0:137634ff4186	1176	int mpi_mul_int( mpi X, const mpi A, t_sint b )
ansond	0:137634ff4186	1177	{
ansond	0:137634ff4186	1178	mpi _B;
ansond	0:137634ff4186	1179	t_uint p[1];
ansond	0:137634ff4186	1180
ansond	0:137634ff4186	1181	_B.s = 1;
ansond	0:137634ff4186	1182	_B.n = 1;
ansond	0:137634ff4186	1183	_B.p = p;
ansond	0:137634ff4186	1184	p[0] = b;
ansond	0:137634ff4186	1185
ansond	0:137634ff4186	1186	return( mpi_mul_mpi( X, A, &_B ) );
ansond	0:137634ff4186	1187	}
ansond	0:137634ff4186	1188
ansond	0:137634ff4186	1189	/*
ansond	0:137634ff4186	1190	* Division by mpi: A = Q * B + R (HAC 14.20)
ansond	0:137634ff4186	1191	*/
ansond	0:137634ff4186	1192	int mpi_div_mpi( mpi Q, mpi R, const mpi A, const mpi B )
ansond	0:137634ff4186	1193	{
ansond	0:137634ff4186	1194	int ret;
ansond	0:137634ff4186	1195	size_t i, n, t, k;
ansond	0:137634ff4186	1196	mpi X, Y, Z, T1, T2;
ansond	0:137634ff4186	1197
ansond	0:137634ff4186	1198	if( mpi_cmp_int( B, 0 ) == 0 )
ansond	0:137634ff4186	1199	return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
ansond	0:137634ff4186	1200
ansond	0:137634ff4186	1201	mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
ansond	0:137634ff4186	1202	mpi_init( &T1 ); mpi_init( &T2 );
ansond	0:137634ff4186	1203
ansond	0:137634ff4186	1204	if( mpi_cmp_abs( A, B ) < 0 )
ansond	0:137634ff4186	1205	{
ansond	0:137634ff4186	1206	if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
ansond	0:137634ff4186	1207	if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
ansond	0:137634ff4186	1208	return( 0 );
ansond	0:137634ff4186	1209	}
ansond	0:137634ff4186	1210
ansond	0:137634ff4186	1211	MPI_CHK( mpi_copy( &X, A ) );
ansond	0:137634ff4186	1212	MPI_CHK( mpi_copy( &Y, B ) );
ansond	0:137634ff4186	1213	X.s = Y.s = 1;
ansond	0:137634ff4186	1214
ansond	0:137634ff4186	1215	MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
ansond	0:137634ff4186	1216	MPI_CHK( mpi_lset( &Z, 0 ) );
ansond	0:137634ff4186	1217	MPI_CHK( mpi_grow( &T1, 2 ) );
ansond	0:137634ff4186	1218	MPI_CHK( mpi_grow( &T2, 3 ) );
ansond	0:137634ff4186	1219
ansond	0:137634ff4186	1220	k = mpi_msb( &Y ) % biL;
ansond	0:137634ff4186	1221	if( k < biL - 1 )
ansond	0:137634ff4186	1222	{
ansond	0:137634ff4186	1223	k = biL - 1 - k;
ansond	0:137634ff4186	1224	MPI_CHK( mpi_shift_l( &X, k ) );
ansond	0:137634ff4186	1225	MPI_CHK( mpi_shift_l( &Y, k ) );
ansond	0:137634ff4186	1226	}
ansond	0:137634ff4186	1227	else k = 0;
ansond	0:137634ff4186	1228
ansond	0:137634ff4186	1229	n = X.n - 1;
ansond	0:137634ff4186	1230	t = Y.n - 1;
ansond	0:137634ff4186	1231	MPI_CHK( mpi_shift_l( &Y, biL * ( n - t ) ) );
ansond	0:137634ff4186	1232
ansond	0:137634ff4186	1233	while( mpi_cmp_mpi( &X, &Y ) >= 0 )
ansond	0:137634ff4186	1234	{
ansond	0:137634ff4186	1235	Z.p[n - t]++;
ansond	0:137634ff4186	1236	MPI_CHK( mpi_sub_mpi( &X, &X, &Y ) );
ansond	0:137634ff4186	1237	}
ansond	0:137634ff4186	1238	MPI_CHK( mpi_shift_r( &Y, biL * ( n - t ) ) );
ansond	0:137634ff4186	1239
ansond	0:137634ff4186	1240	for( i = n; i > t ; i-- )
ansond	0:137634ff4186	1241	{
ansond	0:137634ff4186	1242	if( X.p[i] >= Y.p[t] )
ansond	0:137634ff4186	1243	Z.p[i - t - 1] = ~0;
ansond	0:137634ff4186	1244	else
ansond	0:137634ff4186	1245	{
ansond	0:137634ff4186	1246	#if defined(POLARSSL_HAVE_UDBL)
ansond	0:137634ff4186	1247	t_udbl r;
ansond	0:137634ff4186	1248
ansond	0:137634ff4186	1249	r = (t_udbl) X.p[i] << biL;
ansond	0:137634ff4186	1250	r \|= (t_udbl) X.p[i - 1];
ansond	0:137634ff4186	1251	r /= Y.p[t];
ansond	0:137634ff4186	1252	if( r > ( (t_udbl) 1 << biL ) - 1 )
ansond	0:137634ff4186	1253	r = ( (t_udbl) 1 << biL ) - 1;
ansond	0:137634ff4186	1254
ansond	0:137634ff4186	1255	Z.p[i - t - 1] = (t_uint) r;
ansond	0:137634ff4186	1256	#else
ansond	0:137634ff4186	1257	/*
ansond	0:137634ff4186	1258	* __udiv_qrnnd_c, from gmp/longlong.h
ansond	0:137634ff4186	1259	*/
ansond	0:137634ff4186	1260	t_uint q0, q1, r0, r1;
ansond	0:137634ff4186	1261	t_uint d0, d1, d, m;
ansond	0:137634ff4186	1262
ansond	0:137634ff4186	1263	d = Y.p[t];
ansond	0:137634ff4186	1264	d0 = ( d << biH ) >> biH;
ansond	0:137634ff4186	1265	d1 = ( d >> biH );
ansond	0:137634ff4186	1266
ansond	0:137634ff4186	1267	q1 = X.p[i] / d1;
ansond	0:137634ff4186	1268	r1 = X.p[i] - d1 * q1;
ansond	0:137634ff4186	1269	r1 <<= biH;
ansond	0:137634ff4186	1270	r1 \|= ( X.p[i - 1] >> biH );
ansond	0:137634ff4186	1271
ansond	0:137634ff4186	1272	m = q1 * d0;
ansond	0:137634ff4186	1273	if( r1 < m )
ansond	0:137634ff4186	1274	{
ansond	0:137634ff4186	1275	q1--, r1 += d;
ansond	0:137634ff4186	1276	while( r1 >= d && r1 < m )
ansond	0:137634ff4186	1277	q1--, r1 += d;
ansond	0:137634ff4186	1278	}
ansond	0:137634ff4186	1279	r1 -= m;
ansond	0:137634ff4186	1280
ansond	0:137634ff4186	1281	q0 = r1 / d1;
ansond	0:137634ff4186	1282	r0 = r1 - d1 * q0;
ansond	0:137634ff4186	1283	r0 <<= biH;
ansond	0:137634ff4186	1284	r0 \|= ( X.p[i - 1] << biH ) >> biH;
ansond	0:137634ff4186	1285
ansond	0:137634ff4186	1286	m = q0 * d0;
ansond	0:137634ff4186	1287	if( r0 < m )
ansond	0:137634ff4186	1288	{
ansond	0:137634ff4186	1289	q0--, r0 += d;
ansond	0:137634ff4186	1290	while( r0 >= d && r0 < m )
ansond	0:137634ff4186	1291	q0--, r0 += d;
ansond	0:137634ff4186	1292	}
ansond	0:137634ff4186	1293	r0 -= m;
ansond	0:137634ff4186	1294
ansond	0:137634ff4186	1295	Z.p[i - t - 1] = ( q1 << biH ) \| q0;
ansond	0:137634ff4186	1296	#endif /* POLARSSL_HAVE_UDBL && !64-bit Apple with Clang 5.0 */
ansond	0:137634ff4186	1297	}
ansond	0:137634ff4186	1298
ansond	0:137634ff4186	1299	Z.p[i - t - 1]++;
ansond	0:137634ff4186	1300	do
ansond	0:137634ff4186	1301	{
ansond	0:137634ff4186	1302	Z.p[i - t - 1]--;
ansond	0:137634ff4186	1303
ansond	0:137634ff4186	1304	MPI_CHK( mpi_lset( &T1, 0 ) );
ansond	0:137634ff4186	1305	T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
ansond	0:137634ff4186	1306	T1.p[1] = Y.p[t];
ansond	0:137634ff4186	1307	MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
ansond	0:137634ff4186	1308
ansond	0:137634ff4186	1309	MPI_CHK( mpi_lset( &T2, 0 ) );
ansond	0:137634ff4186	1310	T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
ansond	0:137634ff4186	1311	T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
ansond	0:137634ff4186	1312	T2.p[2] = X.p[i];
ansond	0:137634ff4186	1313	}
ansond	0:137634ff4186	1314	while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
ansond	0:137634ff4186	1315
ansond	0:137634ff4186	1316	MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
ansond	0:137634ff4186	1317	MPI_CHK( mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
ansond	0:137634ff4186	1318	MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
ansond	0:137634ff4186	1319
ansond	0:137634ff4186	1320	if( mpi_cmp_int( &X, 0 ) < 0 )
ansond	0:137634ff4186	1321	{
ansond	0:137634ff4186	1322	MPI_CHK( mpi_copy( &T1, &Y ) );
ansond	0:137634ff4186	1323	MPI_CHK( mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
ansond	0:137634ff4186	1324	MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
ansond	0:137634ff4186	1325	Z.p[i - t - 1]--;
ansond	0:137634ff4186	1326	}
ansond	0:137634ff4186	1327	}
ansond	0:137634ff4186	1328
ansond	0:137634ff4186	1329	if( Q != NULL )
ansond	0:137634ff4186	1330	{
ansond	0:137634ff4186	1331	MPI_CHK( mpi_copy( Q, &Z ) );
ansond	0:137634ff4186	1332	Q->s = A->s * B->s;
ansond	0:137634ff4186	1333	}
ansond	0:137634ff4186	1334
ansond	0:137634ff4186	1335	if( R != NULL )
ansond	0:137634ff4186	1336	{
ansond	0:137634ff4186	1337	MPI_CHK( mpi_shift_r( &X, k ) );
ansond	0:137634ff4186	1338	X.s = A->s;
ansond	0:137634ff4186	1339	MPI_CHK( mpi_copy( R, &X ) );
ansond	0:137634ff4186	1340
ansond	0:137634ff4186	1341	if( mpi_cmp_int( R, 0 ) == 0 )
ansond	0:137634ff4186	1342	R->s = 1;
ansond	0:137634ff4186	1343	}
ansond	0:137634ff4186	1344
ansond	0:137634ff4186	1345	cleanup:
ansond	0:137634ff4186	1346
ansond	0:137634ff4186	1347	mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
ansond	0:137634ff4186	1348	mpi_free( &T1 ); mpi_free( &T2 );
ansond	0:137634ff4186	1349
ansond	0:137634ff4186	1350	return( ret );
ansond	0:137634ff4186	1351	}
ansond	0:137634ff4186	1352
ansond	0:137634ff4186	1353	/*
ansond	0:137634ff4186	1354	* Division by int: A = Q * b + R
ansond	0:137634ff4186	1355	*/
ansond	0:137634ff4186	1356	int mpi_div_int( mpi Q, mpi R, const mpi *A, t_sint b )
ansond	0:137634ff4186	1357	{
ansond	0:137634ff4186	1358	mpi _B;
ansond	0:137634ff4186	1359	t_uint p[1];
ansond	0:137634ff4186	1360
ansond	0:137634ff4186	1361	p[0] = ( b < 0 ) ? -b : b;
ansond	0:137634ff4186	1362	_B.s = ( b < 0 ) ? -1 : 1;
ansond	0:137634ff4186	1363	_B.n = 1;
ansond	0:137634ff4186	1364	_B.p = p;
ansond	0:137634ff4186	1365
ansond	0:137634ff4186	1366	return( mpi_div_mpi( Q, R, A, &_B ) );
ansond	0:137634ff4186	1367	}
ansond	0:137634ff4186	1368
ansond	0:137634ff4186	1369	/*
ansond	0:137634ff4186	1370	* Modulo: R = A mod B
ansond	0:137634ff4186	1371	*/
ansond	0:137634ff4186	1372	int mpi_mod_mpi( mpi R, const mpi A, const mpi *B )
ansond	0:137634ff4186	1373	{
ansond	0:137634ff4186	1374	int ret;
ansond	0:137634ff4186	1375
ansond	0:137634ff4186	1376	if( mpi_cmp_int( B, 0 ) < 0 )
ansond	0:137634ff4186	1377	return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
ansond	0:137634ff4186	1378
ansond	0:137634ff4186	1379	MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
ansond	0:137634ff4186	1380
ansond	0:137634ff4186	1381	while( mpi_cmp_int( R, 0 ) < 0 )
ansond	0:137634ff4186	1382	MPI_CHK( mpi_add_mpi( R, R, B ) );
ansond	0:137634ff4186	1383
ansond	0:137634ff4186	1384	while( mpi_cmp_mpi( R, B ) >= 0 )
ansond	0:137634ff4186	1385	MPI_CHK( mpi_sub_mpi( R, R, B ) );
ansond	0:137634ff4186	1386
ansond	0:137634ff4186	1387	cleanup:
ansond	0:137634ff4186	1388
ansond	0:137634ff4186	1389	return( ret );
ansond	0:137634ff4186	1390	}
ansond	0:137634ff4186	1391
ansond	0:137634ff4186	1392	/*
ansond	0:137634ff4186	1393	* Modulo: r = A mod b
ansond	0:137634ff4186	1394	*/
ansond	0:137634ff4186	1395	int mpi_mod_int( t_uint r, const mpi A, t_sint b )
ansond	0:137634ff4186	1396	{
ansond	0:137634ff4186	1397	size_t i;
ansond	0:137634ff4186	1398	t_uint x, y, z;
ansond	0:137634ff4186	1399
ansond	0:137634ff4186	1400	if( b == 0 )
ansond	0:137634ff4186	1401	return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
ansond	0:137634ff4186	1402
ansond	0:137634ff4186	1403	if( b < 0 )
ansond	0:137634ff4186	1404	return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
ansond	0:137634ff4186	1405
ansond	0:137634ff4186	1406	/*
ansond	0:137634ff4186	1407	* handle trivial cases
ansond	0:137634ff4186	1408	*/
ansond	0:137634ff4186	1409	if( b == 1 )
ansond	0:137634ff4186	1410	{
ansond	0:137634ff4186	1411	*r = 0;
ansond	0:137634ff4186	1412	return( 0 );
ansond	0:137634ff4186	1413	}
ansond	0:137634ff4186	1414
ansond	0:137634ff4186	1415	if( b == 2 )
ansond	0:137634ff4186	1416	{
ansond	0:137634ff4186	1417	*r = A->p[0] & 1;
ansond	0:137634ff4186	1418	return( 0 );
ansond	0:137634ff4186	1419	}
ansond	0:137634ff4186	1420
ansond	0:137634ff4186	1421	/*
ansond	0:137634ff4186	1422	* general case
ansond	0:137634ff4186	1423	*/
ansond	0:137634ff4186	1424	for( i = A->n, y = 0; i > 0; i-- )
ansond	0:137634ff4186	1425	{
ansond	0:137634ff4186	1426	x = A->p[i - 1];
ansond	0:137634ff4186	1427	y = ( y << biH ) \| ( x >> biH );
ansond	0:137634ff4186	1428	z = y / b;
ansond	0:137634ff4186	1429	y -= z * b;
ansond	0:137634ff4186	1430
ansond	0:137634ff4186	1431	x <<= biH;
ansond	0:137634ff4186	1432	y = ( y << biH ) \| ( x >> biH );
ansond	0:137634ff4186	1433	z = y / b;
ansond	0:137634ff4186	1434	y -= z * b;
ansond	0:137634ff4186	1435	}
ansond	0:137634ff4186	1436
ansond	0:137634ff4186	1437	/*
ansond	0:137634ff4186	1438	* If A is negative, then the current y represents a negative value.
ansond	0:137634ff4186	1439	* Flipping it to the positive side.
ansond	0:137634ff4186	1440	*/
ansond	0:137634ff4186	1441	if( A->s < 0 && y != 0 )
ansond	0:137634ff4186	1442	y = b - y;
ansond	0:137634ff4186	1443
ansond	0:137634ff4186	1444	*r = y;
ansond	0:137634ff4186	1445
ansond	0:137634ff4186	1446	return( 0 );
ansond	0:137634ff4186	1447	}
ansond	0:137634ff4186	1448
ansond	0:137634ff4186	1449	/*
ansond	0:137634ff4186	1450	* Fast Montgomery initialization (thanks to Tom St Denis)
ansond	0:137634ff4186	1451	*/
ansond	0:137634ff4186	1452	static void mpi_montg_init( t_uint mm, const mpi N )
ansond	0:137634ff4186	1453	{
ansond	0:137634ff4186	1454	t_uint x, m0 = N->p[0];
ansond	0:137634ff4186	1455	unsigned int i;
ansond	0:137634ff4186	1456
ansond	0:137634ff4186	1457	x = m0;
ansond	0:137634ff4186	1458	x += ( ( m0 + 2 ) & 4 ) << 1;
ansond	0:137634ff4186	1459
ansond	0:137634ff4186	1460	for( i = biL; i >= 8; i /= 2 )
ansond	0:137634ff4186	1461	x = ( 2 - ( m0 x ) );
ansond	0:137634ff4186	1462
ansond	0:137634ff4186	1463	*mm = ~x + 1;
ansond	0:137634ff4186	1464	}
ansond	0:137634ff4186	1465
ansond	0:137634ff4186	1466	/*
ansond	0:137634ff4186	1467	* Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
ansond	0:137634ff4186	1468	*/
ansond	0:137634ff4186	1469	static void mpi_montmul( mpi A, const mpi B, const mpi *N, t_uint mm,
ansond	0:137634ff4186	1470	const mpi *T )
ansond	0:137634ff4186	1471	{
ansond	0:137634ff4186	1472	size_t i, n, m;
ansond	0:137634ff4186	1473	t_uint u0, u1, *d;
ansond	0:137634ff4186	1474
ansond	0:137634ff4186	1475	memset( T->p, 0, T->n * ciL );
ansond	0:137634ff4186	1476
ansond	0:137634ff4186	1477	d = T->p;
ansond	0:137634ff4186	1478	n = N->n;
ansond	0:137634ff4186	1479	m = ( B->n < n ) ? B->n : n;
ansond	0:137634ff4186	1480
ansond	0:137634ff4186	1481	for( i = 0; i < n; i++ )
ansond	0:137634ff4186	1482	{
ansond	0:137634ff4186	1483	/*
ansond	0:137634ff4186	1484	* T = (T + u0B + u1N) / 2^biL
ansond	0:137634ff4186	1485	*/
ansond	0:137634ff4186	1486	u0 = A->p[i];
ansond	0:137634ff4186	1487	u1 = ( d[0] + u0 * B->p[0] ) * mm;
ansond	0:137634ff4186	1488
ansond	0:137634ff4186	1489	mpi_mul_hlp( m, B->p, d, u0 );
ansond	0:137634ff4186	1490	mpi_mul_hlp( n, N->p, d, u1 );
ansond	0:137634ff4186	1491
ansond	0:137634ff4186	1492	*d++ = u0; d[n + 1] = 0;
ansond	0:137634ff4186	1493	}
ansond	0:137634ff4186	1494
ansond	0:137634ff4186	1495	memcpy( A->p, d, ( n + 1 ) * ciL );
ansond	0:137634ff4186	1496
ansond	0:137634ff4186	1497	if( mpi_cmp_abs( A, N ) >= 0 )
ansond	0:137634ff4186	1498	mpi_sub_hlp( n, N->p, A->p );
ansond	0:137634ff4186	1499	else
ansond	0:137634ff4186	1500	/* prevent timing attacks */
ansond	0:137634ff4186	1501	mpi_sub_hlp( n, A->p, T->p );
ansond	0:137634ff4186	1502	}
ansond	0:137634ff4186	1503
ansond	0:137634ff4186	1504	/*
ansond	0:137634ff4186	1505	* Montgomery reduction: A = A * R^-1 mod N
ansond	0:137634ff4186	1506	*/
ansond	0:137634ff4186	1507	static void mpi_montred( mpi A, const mpi N, t_uint mm, const mpi *T )
ansond	0:137634ff4186	1508	{
ansond	0:137634ff4186	1509	t_uint z = 1;
ansond	0:137634ff4186	1510	mpi U;
ansond	0:137634ff4186	1511
ansond	0:137634ff4186	1512	U.n = U.s = (int) z;
ansond	0:137634ff4186	1513	U.p = &z;
ansond	0:137634ff4186	1514
ansond	0:137634ff4186	1515	mpi_montmul( A, &U, N, mm, T );
ansond	0:137634ff4186	1516	}
ansond	0:137634ff4186	1517
ansond	0:137634ff4186	1518	/*
ansond	0:137634ff4186	1519	* Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
ansond	0:137634ff4186	1520	*/
ansond	0:137634ff4186	1521	int mpi_exp_mod( mpi X, const mpi A, const mpi E, const mpi N, mpi *_RR )
ansond	0:137634ff4186	1522	{
ansond	0:137634ff4186	1523	int ret;
ansond	0:137634ff4186	1524	size_t wbits, wsize, one = 1;
ansond	0:137634ff4186	1525	size_t i, j, nblimbs;
ansond	0:137634ff4186	1526	size_t bufsize, nbits;
ansond	0:137634ff4186	1527	t_uint ei, mm, state;
ansond	0:137634ff4186	1528	mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos;
ansond	0:137634ff4186	1529	int neg;
ansond	0:137634ff4186	1530
ansond	0:137634ff4186	1531	if( mpi_cmp_int( N, 0 ) < 0 \|\| ( N->p[0] & 1 ) == 0 )
ansond	0:137634ff4186	1532	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	1533
ansond	0:137634ff4186	1534	if( mpi_cmp_int( E, 0 ) < 0 )
ansond	0:137634ff4186	1535	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	1536
ansond	0:137634ff4186	1537	/*
ansond	0:137634ff4186	1538	* Init temps and window size
ansond	0:137634ff4186	1539	*/
ansond	0:137634ff4186	1540	mpi_montg_init( &mm, N );
ansond	0:137634ff4186	1541	mpi_init( &RR ); mpi_init( &T );
ansond	0:137634ff4186	1542	mpi_init( &Apos );
ansond	0:137634ff4186	1543	memset( W, 0, sizeof( W ) );
ansond	0:137634ff4186	1544
ansond	0:137634ff4186	1545	i = mpi_msb( E );
ansond	0:137634ff4186	1546
ansond	0:137634ff4186	1547	wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
ansond	0:137634ff4186	1548	( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
ansond	0:137634ff4186	1549
ansond	0:137634ff4186	1550	if( wsize > POLARSSL_MPI_WINDOW_SIZE )
ansond	0:137634ff4186	1551	wsize = POLARSSL_MPI_WINDOW_SIZE;
ansond	0:137634ff4186	1552
ansond	0:137634ff4186	1553	j = N->n + 1;
ansond	0:137634ff4186	1554	MPI_CHK( mpi_grow( X, j ) );
ansond	0:137634ff4186	1555	MPI_CHK( mpi_grow( &W[1], j ) );
ansond	0:137634ff4186	1556	MPI_CHK( mpi_grow( &T, j * 2 ) );
ansond	0:137634ff4186	1557
ansond	0:137634ff4186	1558	/*
ansond	0:137634ff4186	1559	* Compensate for negative A (and correct at the end)
ansond	0:137634ff4186	1560	*/
ansond	0:137634ff4186	1561	neg = ( A->s == -1 );
ansond	0:137634ff4186	1562	if( neg )
ansond	0:137634ff4186	1563	{
ansond	0:137634ff4186	1564	MPI_CHK( mpi_copy( &Apos, A ) );
ansond	0:137634ff4186	1565	Apos.s = 1;
ansond	0:137634ff4186	1566	A = &Apos;
ansond	0:137634ff4186	1567	}
ansond	0:137634ff4186	1568
ansond	0:137634ff4186	1569	/*
ansond	0:137634ff4186	1570	* If 1st call, pre-compute R^2 mod N
ansond	0:137634ff4186	1571	*/
ansond	0:137634ff4186	1572	if( _RR == NULL \|\| _RR->p == NULL )
ansond	0:137634ff4186	1573	{
ansond	0:137634ff4186	1574	MPI_CHK( mpi_lset( &RR, 1 ) );
ansond	0:137634ff4186	1575	MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
ansond	0:137634ff4186	1576	MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
ansond	0:137634ff4186	1577
ansond	0:137634ff4186	1578	if( _RR != NULL )
ansond	0:137634ff4186	1579	memcpy( _RR, &RR, sizeof( mpi ) );
ansond	0:137634ff4186	1580	}
ansond	0:137634ff4186	1581	else
ansond	0:137634ff4186	1582	memcpy( &RR, _RR, sizeof( mpi ) );
ansond	0:137634ff4186	1583
ansond	0:137634ff4186	1584	/*
ansond	0:137634ff4186	1585	* W[1] = A * R^2 * R^-1 mod N = A * R mod N
ansond	0:137634ff4186	1586	*/
ansond	0:137634ff4186	1587	if( mpi_cmp_mpi( A, N ) >= 0 )
ansond	0:137634ff4186	1588	MPI_CHK( mpi_mod_mpi( &W[1], A, N ) );
ansond	0:137634ff4186	1589	else
ansond	0:137634ff4186	1590	MPI_CHK( mpi_copy( &W[1], A ) );
ansond	0:137634ff4186	1591
ansond	0:137634ff4186	1592	mpi_montmul( &W[1], &RR, N, mm, &T );
ansond	0:137634ff4186	1593
ansond	0:137634ff4186	1594	/*
ansond	0:137634ff4186	1595	* X = R^2 * R^-1 mod N = R mod N
ansond	0:137634ff4186	1596	*/
ansond	0:137634ff4186	1597	MPI_CHK( mpi_copy( X, &RR ) );
ansond	0:137634ff4186	1598	mpi_montred( X, N, mm, &T );
ansond	0:137634ff4186	1599
ansond	0:137634ff4186	1600	if( wsize > 1 )
ansond	0:137634ff4186	1601	{
ansond	0:137634ff4186	1602	/*
ansond	0:137634ff4186	1603	* W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
ansond	0:137634ff4186	1604	*/
ansond	0:137634ff4186	1605	j = one << ( wsize - 1 );
ansond	0:137634ff4186	1606
ansond	0:137634ff4186	1607	MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
ansond	0:137634ff4186	1608	MPI_CHK( mpi_copy( &W[j], &W[1] ) );
ansond	0:137634ff4186	1609
ansond	0:137634ff4186	1610	for( i = 0; i < wsize - 1; i++ )
ansond	0:137634ff4186	1611	mpi_montmul( &W[j], &W[j], N, mm, &T );
ansond	0:137634ff4186	1612
ansond	0:137634ff4186	1613	/*
ansond	0:137634ff4186	1614	* W[i] = W[i - 1] * W[1]
ansond	0:137634ff4186	1615	*/
ansond	0:137634ff4186	1616	for( i = j + 1; i < ( one << wsize ); i++ )
ansond	0:137634ff4186	1617	{
ansond	0:137634ff4186	1618	MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
ansond	0:137634ff4186	1619	MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
ansond	0:137634ff4186	1620
ansond	0:137634ff4186	1621	mpi_montmul( &W[i], &W[1], N, mm, &T );
ansond	0:137634ff4186	1622	}
ansond	0:137634ff4186	1623	}
ansond	0:137634ff4186	1624
ansond	0:137634ff4186	1625	nblimbs = E->n;
ansond	0:137634ff4186	1626	bufsize = 0;
ansond	0:137634ff4186	1627	nbits = 0;
ansond	0:137634ff4186	1628	wbits = 0;
ansond	0:137634ff4186	1629	state = 0;
ansond	0:137634ff4186	1630
ansond	0:137634ff4186	1631	while( 1 )
ansond	0:137634ff4186	1632	{
ansond	0:137634ff4186	1633	if( bufsize == 0 )
ansond	0:137634ff4186	1634	{
ansond	0:137634ff4186	1635	if( nblimbs == 0 )
ansond	0:137634ff4186	1636	break;
ansond	0:137634ff4186	1637
ansond	0:137634ff4186	1638	nblimbs--;
ansond	0:137634ff4186	1639
ansond	0:137634ff4186	1640	bufsize = sizeof( t_uint ) << 3;
ansond	0:137634ff4186	1641	}
ansond	0:137634ff4186	1642
ansond	0:137634ff4186	1643	bufsize--;
ansond	0:137634ff4186	1644
ansond	0:137634ff4186	1645	ei = (E->p[nblimbs] >> bufsize) & 1;
ansond	0:137634ff4186	1646
ansond	0:137634ff4186	1647	/*
ansond	0:137634ff4186	1648	* skip leading 0s
ansond	0:137634ff4186	1649	*/
ansond	0:137634ff4186	1650	if( ei == 0 && state == 0 )
ansond	0:137634ff4186	1651	continue;
ansond	0:137634ff4186	1652
ansond	0:137634ff4186	1653	if( ei == 0 && state == 1 )
ansond	0:137634ff4186	1654	{
ansond	0:137634ff4186	1655	/*
ansond	0:137634ff4186	1656	* out of window, square X
ansond	0:137634ff4186	1657	*/
ansond	0:137634ff4186	1658	mpi_montmul( X, X, N, mm, &T );
ansond	0:137634ff4186	1659	continue;
ansond	0:137634ff4186	1660	}
ansond	0:137634ff4186	1661
ansond	0:137634ff4186	1662	/*
ansond	0:137634ff4186	1663	* add ei to current window
ansond	0:137634ff4186	1664	*/
ansond	0:137634ff4186	1665	state = 2;
ansond	0:137634ff4186	1666
ansond	0:137634ff4186	1667	nbits++;
ansond	0:137634ff4186	1668	wbits \|= ( ei << ( wsize - nbits ) );
ansond	0:137634ff4186	1669
ansond	0:137634ff4186	1670	if( nbits == wsize )
ansond	0:137634ff4186	1671	{
ansond	0:137634ff4186	1672	/*
ansond	0:137634ff4186	1673	* X = X^wsize R^-1 mod N
ansond	0:137634ff4186	1674	*/
ansond	0:137634ff4186	1675	for( i = 0; i < wsize; i++ )
ansond	0:137634ff4186	1676	mpi_montmul( X, X, N, mm, &T );
ansond	0:137634ff4186	1677
ansond	0:137634ff4186	1678	/*
ansond	0:137634ff4186	1679	* X = X * W[wbits] R^-1 mod N
ansond	0:137634ff4186	1680	*/
ansond	0:137634ff4186	1681	mpi_montmul( X, &W[wbits], N, mm, &T );
ansond	0:137634ff4186	1682
ansond	0:137634ff4186	1683	state--;
ansond	0:137634ff4186	1684	nbits = 0;
ansond	0:137634ff4186	1685	wbits = 0;
ansond	0:137634ff4186	1686	}
ansond	0:137634ff4186	1687	}
ansond	0:137634ff4186	1688
ansond	0:137634ff4186	1689	/*
ansond	0:137634ff4186	1690	* process the remaining bits
ansond	0:137634ff4186	1691	*/
ansond	0:137634ff4186	1692	for( i = 0; i < nbits; i++ )
ansond	0:137634ff4186	1693	{
ansond	0:137634ff4186	1694	mpi_montmul( X, X, N, mm, &T );
ansond	0:137634ff4186	1695
ansond	0:137634ff4186	1696	wbits <<= 1;
ansond	0:137634ff4186	1697
ansond	0:137634ff4186	1698	if( ( wbits & ( one << wsize ) ) != 0 )
ansond	0:137634ff4186	1699	mpi_montmul( X, &W[1], N, mm, &T );
ansond	0:137634ff4186	1700	}
ansond	0:137634ff4186	1701
ansond	0:137634ff4186	1702	/*
ansond	0:137634ff4186	1703	* X = A^E * R * R^-1 mod N = A^E mod N
ansond	0:137634ff4186	1704	*/
ansond	0:137634ff4186	1705	mpi_montred( X, N, mm, &T );
ansond	0:137634ff4186	1706
ansond	0:137634ff4186	1707	if( neg )
ansond	0:137634ff4186	1708	{
ansond	0:137634ff4186	1709	X->s = -1;
ansond	0:137634ff4186	1710	MPI_CHK( mpi_add_mpi( X, N, X ) );
ansond	0:137634ff4186	1711	}
ansond	0:137634ff4186	1712
ansond	0:137634ff4186	1713	cleanup:
ansond	0:137634ff4186	1714
ansond	0:137634ff4186	1715	for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
ansond	0:137634ff4186	1716	mpi_free( &W[i] );
ansond	0:137634ff4186	1717
ansond	0:137634ff4186	1718	mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
ansond	0:137634ff4186	1719
ansond	0:137634ff4186	1720	if( _RR == NULL \|\| _RR->p == NULL )
ansond	0:137634ff4186	1721	mpi_free( &RR );
ansond	0:137634ff4186	1722
ansond	0:137634ff4186	1723	return( ret );
ansond	0:137634ff4186	1724	}
ansond	0:137634ff4186	1725
ansond	0:137634ff4186	1726	/*
ansond	0:137634ff4186	1727	* Greatest common divisor: G = gcd(A, B) (HAC 14.54)
ansond	0:137634ff4186	1728	*/
ansond	0:137634ff4186	1729	int mpi_gcd( mpi G, const mpi A, const mpi *B )
ansond	0:137634ff4186	1730	{
ansond	0:137634ff4186	1731	int ret;
ansond	0:137634ff4186	1732	size_t lz, lzt;
ansond	0:137634ff4186	1733	mpi TG, TA, TB;
ansond	0:137634ff4186	1734
ansond	0:137634ff4186	1735	mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
ansond	0:137634ff4186	1736
ansond	0:137634ff4186	1737	MPI_CHK( mpi_copy( &TA, A ) );
ansond	0:137634ff4186	1738	MPI_CHK( mpi_copy( &TB, B ) );
ansond	0:137634ff4186	1739
ansond	0:137634ff4186	1740	lz = mpi_lsb( &TA );
ansond	0:137634ff4186	1741	lzt = mpi_lsb( &TB );
ansond	0:137634ff4186	1742
ansond	0:137634ff4186	1743	if( lzt < lz )
ansond	0:137634ff4186	1744	lz = lzt;
ansond	0:137634ff4186	1745
ansond	0:137634ff4186	1746	MPI_CHK( mpi_shift_r( &TA, lz ) );
ansond	0:137634ff4186	1747	MPI_CHK( mpi_shift_r( &TB, lz ) );
ansond	0:137634ff4186	1748
ansond	0:137634ff4186	1749	TA.s = TB.s = 1;
ansond	0:137634ff4186	1750
ansond	0:137634ff4186	1751	while( mpi_cmp_int( &TA, 0 ) != 0 )
ansond	0:137634ff4186	1752	{
ansond	0:137634ff4186	1753	MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
ansond	0:137634ff4186	1754	MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
ansond	0:137634ff4186	1755
ansond	0:137634ff4186	1756	if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
ansond	0:137634ff4186	1757	{
ansond	0:137634ff4186	1758	MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
ansond	0:137634ff4186	1759	MPI_CHK( mpi_shift_r( &TA, 1 ) );
ansond	0:137634ff4186	1760	}
ansond	0:137634ff4186	1761	else
ansond	0:137634ff4186	1762	{
ansond	0:137634ff4186	1763	MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
ansond	0:137634ff4186	1764	MPI_CHK( mpi_shift_r( &TB, 1 ) );
ansond	0:137634ff4186	1765	}
ansond	0:137634ff4186	1766	}
ansond	0:137634ff4186	1767
ansond	0:137634ff4186	1768	MPI_CHK( mpi_shift_l( &TB, lz ) );
ansond	0:137634ff4186	1769	MPI_CHK( mpi_copy( G, &TB ) );
ansond	0:137634ff4186	1770
ansond	0:137634ff4186	1771	cleanup:
ansond	0:137634ff4186	1772
ansond	0:137634ff4186	1773	mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
ansond	0:137634ff4186	1774
ansond	0:137634ff4186	1775	return( ret );
ansond	0:137634ff4186	1776	}
ansond	0:137634ff4186	1777
ansond	0:137634ff4186	1778	/*
ansond	0:137634ff4186	1779	* Fill X with size bytes of random.
ansond	0:137634ff4186	1780	*
ansond	0:137634ff4186	1781	* Use a temporary bytes representation to make sure the result is the same
ansond	0:137634ff4186	1782	* regardless of the platform endianness (useful when f_rng is actually
ansond	0:137634ff4186	1783	* deterministic, eg for tests).
ansond	0:137634ff4186	1784	*/
ansond	0:137634ff4186	1785	int mpi_fill_random( mpi *X, size_t size,
ansond	0:137634ff4186	1786	int (f_rng)(void , unsigned char *, size_t),
ansond	0:137634ff4186	1787	void *p_rng )
ansond	0:137634ff4186	1788	{
ansond	0:137634ff4186	1789	int ret;
ansond	0:137634ff4186	1790	unsigned char buf[POLARSSL_MPI_MAX_SIZE];
ansond	0:137634ff4186	1791
ansond	0:137634ff4186	1792	if( size > POLARSSL_MPI_MAX_SIZE )
ansond	0:137634ff4186	1793	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	1794
ansond	0:137634ff4186	1795	MPI_CHK( f_rng( p_rng, buf, size ) );
ansond	0:137634ff4186	1796	MPI_CHK( mpi_read_binary( X, buf, size ) );
ansond	0:137634ff4186	1797
ansond	0:137634ff4186	1798	cleanup:
ansond	0:137634ff4186	1799	return( ret );
ansond	0:137634ff4186	1800	}
ansond	0:137634ff4186	1801
ansond	0:137634ff4186	1802	/*
ansond	0:137634ff4186	1803	* Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
ansond	0:137634ff4186	1804	*/
ansond	0:137634ff4186	1805	int mpi_inv_mod( mpi X, const mpi A, const mpi *N )
ansond	0:137634ff4186	1806	{
ansond	0:137634ff4186	1807	int ret;
ansond	0:137634ff4186	1808	mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
ansond	0:137634ff4186	1809
ansond	0:137634ff4186	1810	if( mpi_cmp_int( N, 0 ) <= 0 )
ansond	0:137634ff4186	1811	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	1812
ansond	0:137634ff4186	1813	mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
ansond	0:137634ff4186	1814	mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
ansond	0:137634ff4186	1815	mpi_init( &V1 ); mpi_init( &V2 );
ansond	0:137634ff4186	1816
ansond	0:137634ff4186	1817	MPI_CHK( mpi_gcd( &G, A, N ) );
ansond	0:137634ff4186	1818
ansond	0:137634ff4186	1819	if( mpi_cmp_int( &G, 1 ) != 0 )
ansond	0:137634ff4186	1820	{
ansond	0:137634ff4186	1821	ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
ansond	0:137634ff4186	1822	goto cleanup;
ansond	0:137634ff4186	1823	}
ansond	0:137634ff4186	1824
ansond	0:137634ff4186	1825	MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
ansond	0:137634ff4186	1826	MPI_CHK( mpi_copy( &TU, &TA ) );
ansond	0:137634ff4186	1827	MPI_CHK( mpi_copy( &TB, N ) );
ansond	0:137634ff4186	1828	MPI_CHK( mpi_copy( &TV, N ) );
ansond	0:137634ff4186	1829
ansond	0:137634ff4186	1830	MPI_CHK( mpi_lset( &U1, 1 ) );
ansond	0:137634ff4186	1831	MPI_CHK( mpi_lset( &U2, 0 ) );
ansond	0:137634ff4186	1832	MPI_CHK( mpi_lset( &V1, 0 ) );
ansond	0:137634ff4186	1833	MPI_CHK( mpi_lset( &V2, 1 ) );
ansond	0:137634ff4186	1834
ansond	0:137634ff4186	1835	do
ansond	0:137634ff4186	1836	{
ansond	0:137634ff4186	1837	while( ( TU.p[0] & 1 ) == 0 )
ansond	0:137634ff4186	1838	{
ansond	0:137634ff4186	1839	MPI_CHK( mpi_shift_r( &TU, 1 ) );
ansond	0:137634ff4186	1840
ansond	0:137634ff4186	1841	if( ( U1.p[0] & 1 ) != 0 \|\| ( U2.p[0] & 1 ) != 0 )
ansond	0:137634ff4186	1842	{
ansond	0:137634ff4186	1843	MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
ansond	0:137634ff4186	1844	MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
ansond	0:137634ff4186	1845	}
ansond	0:137634ff4186	1846
ansond	0:137634ff4186	1847	MPI_CHK( mpi_shift_r( &U1, 1 ) );
ansond	0:137634ff4186	1848	MPI_CHK( mpi_shift_r( &U2, 1 ) );
ansond	0:137634ff4186	1849	}
ansond	0:137634ff4186	1850
ansond	0:137634ff4186	1851	while( ( TV.p[0] & 1 ) == 0 )
ansond	0:137634ff4186	1852	{
ansond	0:137634ff4186	1853	MPI_CHK( mpi_shift_r( &TV, 1 ) );
ansond	0:137634ff4186	1854
ansond	0:137634ff4186	1855	if( ( V1.p[0] & 1 ) != 0 \|\| ( V2.p[0] & 1 ) != 0 )
ansond	0:137634ff4186	1856	{
ansond	0:137634ff4186	1857	MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
ansond	0:137634ff4186	1858	MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
ansond	0:137634ff4186	1859	}
ansond	0:137634ff4186	1860
ansond	0:137634ff4186	1861	MPI_CHK( mpi_shift_r( &V1, 1 ) );
ansond	0:137634ff4186	1862	MPI_CHK( mpi_shift_r( &V2, 1 ) );
ansond	0:137634ff4186	1863	}
ansond	0:137634ff4186	1864
ansond	0:137634ff4186	1865	if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
ansond	0:137634ff4186	1866	{
ansond	0:137634ff4186	1867	MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
ansond	0:137634ff4186	1868	MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
ansond	0:137634ff4186	1869	MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
ansond	0:137634ff4186	1870	}
ansond	0:137634ff4186	1871	else
ansond	0:137634ff4186	1872	{
ansond	0:137634ff4186	1873	MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
ansond	0:137634ff4186	1874	MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
ansond	0:137634ff4186	1875	MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
ansond	0:137634ff4186	1876	}
ansond	0:137634ff4186	1877	}
ansond	0:137634ff4186	1878	while( mpi_cmp_int( &TU, 0 ) != 0 );
ansond	0:137634ff4186	1879
ansond	0:137634ff4186	1880	while( mpi_cmp_int( &V1, 0 ) < 0 )
ansond	0:137634ff4186	1881	MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
ansond	0:137634ff4186	1882
ansond	0:137634ff4186	1883	while( mpi_cmp_mpi( &V1, N ) >= 0 )
ansond	0:137634ff4186	1884	MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
ansond	0:137634ff4186	1885
ansond	0:137634ff4186	1886	MPI_CHK( mpi_copy( X, &V1 ) );
ansond	0:137634ff4186	1887
ansond	0:137634ff4186	1888	cleanup:
ansond	0:137634ff4186	1889
ansond	0:137634ff4186	1890	mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
ansond	0:137634ff4186	1891	mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
ansond	0:137634ff4186	1892	mpi_free( &V1 ); mpi_free( &V2 );
ansond	0:137634ff4186	1893
ansond	0:137634ff4186	1894	return( ret );
ansond	0:137634ff4186	1895	}
ansond	0:137634ff4186	1896
ansond	0:137634ff4186	1897	#if defined(POLARSSL_GENPRIME)
ansond	0:137634ff4186	1898
ansond	0:137634ff4186	1899	static const int small_prime[] =
ansond	0:137634ff4186	1900	{
ansond	0:137634ff4186	1901	3, 5, 7, 11, 13, 17, 19, 23,
ansond	0:137634ff4186	1902	29, 31, 37, 41, 43, 47, 53, 59,
ansond	0:137634ff4186	1903	61, 67, 71, 73, 79, 83, 89, 97,
ansond	0:137634ff4186	1904	101, 103, 107, 109, 113, 127, 131, 137,
ansond	0:137634ff4186	1905	139, 149, 151, 157, 163, 167, 173, 179,
ansond	0:137634ff4186	1906	181, 191, 193, 197, 199, 211, 223, 227,
ansond	0:137634ff4186	1907	229, 233, 239, 241, 251, 257, 263, 269,
ansond	0:137634ff4186	1908	271, 277, 281, 283, 293, 307, 311, 313,
ansond	0:137634ff4186	1909	317, 331, 337, 347, 349, 353, 359, 367,
ansond	0:137634ff4186	1910	373, 379, 383, 389, 397, 401, 409, 419,
ansond	0:137634ff4186	1911	421, 431, 433, 439, 443, 449, 457, 461,
ansond	0:137634ff4186	1912	463, 467, 479, 487, 491, 499, 503, 509,
ansond	0:137634ff4186	1913	521, 523, 541, 547, 557, 563, 569, 571,
ansond	0:137634ff4186	1914	577, 587, 593, 599, 601, 607, 613, 617,
ansond	0:137634ff4186	1915	619, 631, 641, 643, 647, 653, 659, 661,
ansond	0:137634ff4186	1916	673, 677, 683, 691, 701, 709, 719, 727,
ansond	0:137634ff4186	1917	733, 739, 743, 751, 757, 761, 769, 773,
ansond	0:137634ff4186	1918	787, 797, 809, 811, 821, 823, 827, 829,
ansond	0:137634ff4186	1919	839, 853, 857, 859, 863, 877, 881, 883,
ansond	0:137634ff4186	1920	887, 907, 911, 919, 929, 937, 941, 947,
ansond	0:137634ff4186	1921	953, 967, 971, 977, 983, 991, 997, -103
ansond	0:137634ff4186	1922	};
ansond	0:137634ff4186	1923
ansond	0:137634ff4186	1924	/*
ansond	0:137634ff4186	1925	* Small divisors test (X must be positive)
ansond	0:137634ff4186	1926	*
ansond	0:137634ff4186	1927	* Return values:
ansond	0:137634ff4186	1928	* 0: no small factor (possible prime, more tests needed)
ansond	0:137634ff4186	1929	* 1: certain prime
ansond	0:137634ff4186	1930	* POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
ansond	0:137634ff4186	1931	* other negative: error
ansond	0:137634ff4186	1932	*/
ansond	0:137634ff4186	1933	static int mpi_check_small_factors( const mpi *X )
ansond	0:137634ff4186	1934	{
ansond	0:137634ff4186	1935	int ret = 0;
ansond	0:137634ff4186	1936	size_t i;
ansond	0:137634ff4186	1937	t_uint r;
ansond	0:137634ff4186	1938
ansond	0:137634ff4186	1939	if( ( X->p[0] & 1 ) == 0 )
ansond	0:137634ff4186	1940	return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
ansond	0:137634ff4186	1941
ansond	0:137634ff4186	1942	for( i = 0; small_prime[i] > 0; i++ )
ansond	0:137634ff4186	1943	{
ansond	0:137634ff4186	1944	if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
ansond	0:137634ff4186	1945	return( 1 );
ansond	0:137634ff4186	1946
ansond	0:137634ff4186	1947	MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
ansond	0:137634ff4186	1948
ansond	0:137634ff4186	1949	if( r == 0 )
ansond	0:137634ff4186	1950	return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
ansond	0:137634ff4186	1951	}
ansond	0:137634ff4186	1952
ansond	0:137634ff4186	1953	cleanup:
ansond	0:137634ff4186	1954	return( ret );
ansond	0:137634ff4186	1955	}
ansond	0:137634ff4186	1956
ansond	0:137634ff4186	1957	/*
ansond	0:137634ff4186	1958	* Miller-Rabin pseudo-primality test (HAC 4.24)
ansond	0:137634ff4186	1959	*/
ansond	0:137634ff4186	1960	static int mpi_miller_rabin( const mpi *X,
ansond	0:137634ff4186	1961	int (f_rng)(void , unsigned char *, size_t),
ansond	0:137634ff4186	1962	void *p_rng )
ansond	0:137634ff4186	1963	{
ansond	0:137634ff4186	1964	int ret, count;
ansond	0:137634ff4186	1965	size_t i, j, k, n, s;
ansond	0:137634ff4186	1966	mpi W, R, T, A, RR;
ansond	0:137634ff4186	1967
ansond	0:137634ff4186	1968	mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
ansond	0:137634ff4186	1969	mpi_init( &RR );
ansond	0:137634ff4186	1970
ansond	0:137634ff4186	1971	/*
ansond	0:137634ff4186	1972	* W = \|X\| - 1
ansond	0:137634ff4186	1973	* R = W >> lsb( W )
ansond	0:137634ff4186	1974	*/
ansond	0:137634ff4186	1975	MPI_CHK( mpi_sub_int( &W, X, 1 ) );
ansond	0:137634ff4186	1976	s = mpi_lsb( &W );
ansond	0:137634ff4186	1977	MPI_CHK( mpi_copy( &R, &W ) );
ansond	0:137634ff4186	1978	MPI_CHK( mpi_shift_r( &R, s ) );
ansond	0:137634ff4186	1979
ansond	0:137634ff4186	1980	i = mpi_msb( X );
ansond	0:137634ff4186	1981	/*
ansond	0:137634ff4186	1982	* HAC, table 4.4
ansond	0:137634ff4186	1983	*/
ansond	0:137634ff4186	1984	n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
ansond	0:137634ff4186	1985	( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
ansond	0:137634ff4186	1986	( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
ansond	0:137634ff4186	1987
ansond	0:137634ff4186	1988	for( i = 0; i < n; i++ )
ansond	0:137634ff4186	1989	{
ansond	0:137634ff4186	1990	/*
ansond	0:137634ff4186	1991	* pick a random A, 1 < A < \|X\| - 1
ansond	0:137634ff4186	1992	*/
ansond	0:137634ff4186	1993
ansond	0:137634ff4186	1994	count = 0;
ansond	0:137634ff4186	1995	do {
ansond	0:137634ff4186	1996	MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
ansond	0:137634ff4186	1997
ansond	0:137634ff4186	1998	j = mpi_msb( &A );
ansond	0:137634ff4186	1999	k = mpi_msb( &W );
ansond	0:137634ff4186	2000	if (j > k) {
ansond	0:137634ff4186	2001	MPI_CHK( mpi_shift_r( &A, j - k ) );
ansond	0:137634ff4186	2002	}
ansond	0:137634ff4186	2003
ansond	0:137634ff4186	2004	if (count++ > 30) {
ansond	0:137634ff4186	2005	return POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
ansond	0:137634ff4186	2006	}
ansond	0:137634ff4186	2007
ansond	0:137634ff4186	2008	} while ( (mpi_cmp_mpi( &A, &W ) >= 0) \|\|
ansond	0:137634ff4186	2009	(mpi_cmp_int( &A, 1 ) <= 0) );
ansond	0:137634ff4186	2010
ansond	0:137634ff4186	2011	/*
ansond	0:137634ff4186	2012	* A = A^R mod \|X\|
ansond	0:137634ff4186	2013	*/
ansond	0:137634ff4186	2014	MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
ansond	0:137634ff4186	2015
ansond	0:137634ff4186	2016	if( mpi_cmp_mpi( &A, &W ) == 0 \|\|
ansond	0:137634ff4186	2017	mpi_cmp_int( &A, 1 ) == 0 )
ansond	0:137634ff4186	2018	continue;
ansond	0:137634ff4186	2019
ansond	0:137634ff4186	2020	j = 1;
ansond	0:137634ff4186	2021	while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
ansond	0:137634ff4186	2022	{
ansond	0:137634ff4186	2023	/*
ansond	0:137634ff4186	2024	* A = A * A mod \|X\|
ansond	0:137634ff4186	2025	*/
ansond	0:137634ff4186	2026	MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
ansond	0:137634ff4186	2027	MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
ansond	0:137634ff4186	2028
ansond	0:137634ff4186	2029	if( mpi_cmp_int( &A, 1 ) == 0 )
ansond	0:137634ff4186	2030	break;
ansond	0:137634ff4186	2031
ansond	0:137634ff4186	2032	j++;
ansond	0:137634ff4186	2033	}
ansond	0:137634ff4186	2034
ansond	0:137634ff4186	2035	/*
ansond	0:137634ff4186	2036	* not prime if A != \|X\| - 1 or A == 1
ansond	0:137634ff4186	2037	*/
ansond	0:137634ff4186	2038	if( mpi_cmp_mpi( &A, &W ) != 0 \|\|
ansond	0:137634ff4186	2039	mpi_cmp_int( &A, 1 ) == 0 )
ansond	0:137634ff4186	2040	{
ansond	0:137634ff4186	2041	ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
ansond	0:137634ff4186	2042	break;
ansond	0:137634ff4186	2043	}
ansond	0:137634ff4186	2044	}
ansond	0:137634ff4186	2045
ansond	0:137634ff4186	2046	cleanup:
ansond	0:137634ff4186	2047	mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
ansond	0:137634ff4186	2048	mpi_free( &RR );
ansond	0:137634ff4186	2049
ansond	0:137634ff4186	2050	return( ret );
ansond	0:137634ff4186	2051	}
ansond	0:137634ff4186	2052
ansond	0:137634ff4186	2053	/*
ansond	0:137634ff4186	2054	* Pseudo-primality test: small factors, then Miller-Rabin
ansond	0:137634ff4186	2055	*/
ansond	0:137634ff4186	2056	int mpi_is_prime( mpi *X,
ansond	0:137634ff4186	2057	int (f_rng)(void , unsigned char *, size_t),
ansond	0:137634ff4186	2058	void *p_rng )
ansond	0:137634ff4186	2059	{
ansond	0:137634ff4186	2060	int ret;
ansond	0:137634ff4186	2061	mpi XX;
ansond	0:137634ff4186	2062
ansond	0:137634ff4186	2063	XX.s = 1;
ansond	0:137634ff4186	2064	XX.n = X->n;
ansond	0:137634ff4186	2065	XX.p = X->p;
ansond	0:137634ff4186	2066
ansond	0:137634ff4186	2067	if( mpi_cmp_int( &XX, 0 ) == 0 \|\|
ansond	0:137634ff4186	2068	mpi_cmp_int( &XX, 1 ) == 0 )
ansond	0:137634ff4186	2069	return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
ansond	0:137634ff4186	2070
ansond	0:137634ff4186	2071	if( mpi_cmp_int( &XX, 2 ) == 0 )
ansond	0:137634ff4186	2072	return( 0 );
ansond	0:137634ff4186	2073
ansond	0:137634ff4186	2074	if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
ansond	0:137634ff4186	2075	{
ansond	0:137634ff4186	2076	if( ret == 1 )
ansond	0:137634ff4186	2077	return( 0 );
ansond	0:137634ff4186	2078
ansond	0:137634ff4186	2079	return( ret );
ansond	0:137634ff4186	2080	}
ansond	0:137634ff4186	2081
ansond	0:137634ff4186	2082	return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
ansond	0:137634ff4186	2083	}
ansond	0:137634ff4186	2084
ansond	0:137634ff4186	2085	/*
ansond	0:137634ff4186	2086	* Prime number generation
ansond	0:137634ff4186	2087	*/
ansond	0:137634ff4186	2088	int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
ansond	0:137634ff4186	2089	int (f_rng)(void , unsigned char *, size_t),
ansond	0:137634ff4186	2090	void *p_rng )
ansond	0:137634ff4186	2091	{
ansond	0:137634ff4186	2092	int ret;
ansond	0:137634ff4186	2093	size_t k, n;
ansond	0:137634ff4186	2094	t_uint r;
ansond	0:137634ff4186	2095	mpi Y;
ansond	0:137634ff4186	2096
ansond	0:137634ff4186	2097	if( nbits < 3 \|\| nbits > POLARSSL_MPI_MAX_BITS )
ansond	0:137634ff4186	2098	return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
ansond	0:137634ff4186	2099
ansond	0:137634ff4186	2100	mpi_init( &Y );
ansond	0:137634ff4186	2101
ansond	0:137634ff4186	2102	n = BITS_TO_LIMBS( nbits );
ansond	0:137634ff4186	2103
ansond	0:137634ff4186	2104	MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
ansond	0:137634ff4186	2105
ansond	0:137634ff4186	2106	k = mpi_msb( X );
ansond	0:137634ff4186	2107	if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits + 1 ) );
ansond	0:137634ff4186	2108
ansond	0:137634ff4186	2109	mpi_set_bit( X, nbits-1, 1 );
ansond	0:137634ff4186	2110
ansond	0:137634ff4186	2111	X->p[0] \|= 1;
ansond	0:137634ff4186	2112
ansond	0:137634ff4186	2113	if( dh_flag == 0 )
ansond	0:137634ff4186	2114	{
ansond	0:137634ff4186	2115	while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
ansond	0:137634ff4186	2116	{
ansond	0:137634ff4186	2117	if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
ansond	0:137634ff4186	2118	goto cleanup;
ansond	0:137634ff4186	2119
ansond	0:137634ff4186	2120	MPI_CHK( mpi_add_int( X, X, 2 ) );
ansond	0:137634ff4186	2121	}
ansond	0:137634ff4186	2122	}
ansond	0:137634ff4186	2123	else
ansond	0:137634ff4186	2124	{
ansond	0:137634ff4186	2125	/*
ansond	0:137634ff4186	2126	* An necessary condition for Y and X = 2Y + 1 to be prime
ansond	0:137634ff4186	2127	* is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
ansond	0:137634ff4186	2128	* Make sure it is satisfied, while keeping X = 3 mod 4
ansond	0:137634ff4186	2129	*/
ansond	0:137634ff4186	2130
ansond	0:137634ff4186	2131	X->p[0] \|= 2;
ansond	0:137634ff4186	2132
ansond	0:137634ff4186	2133	MPI_CHK( mpi_mod_int( &r, X, 3 ) );
ansond	0:137634ff4186	2134	if( r == 0 )
ansond	0:137634ff4186	2135	MPI_CHK( mpi_add_int( X, X, 8 ) );
ansond	0:137634ff4186	2136	else if( r == 1 )
ansond	0:137634ff4186	2137	MPI_CHK( mpi_add_int( X, X, 4 ) );
ansond	0:137634ff4186	2138
ansond	0:137634ff4186	2139	/* Set Y = (X-1) / 2, which is X / 2 because X is odd */
ansond	0:137634ff4186	2140	MPI_CHK( mpi_copy( &Y, X ) );
ansond	0:137634ff4186	2141	MPI_CHK( mpi_shift_r( &Y, 1 ) );
ansond	0:137634ff4186	2142
ansond	0:137634ff4186	2143	while( 1 )
ansond	0:137634ff4186	2144	{
ansond	0:137634ff4186	2145	/*
ansond	0:137634ff4186	2146	* First, check small factors for X and Y
ansond	0:137634ff4186	2147	* before doing Miller-Rabin on any of them
ansond	0:137634ff4186	2148	*/
ansond	0:137634ff4186	2149	if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
ansond	0:137634ff4186	2150	( ret = mpi_check_small_factors( &Y ) ) == 0 &&
ansond	0:137634ff4186	2151	( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
ansond	0:137634ff4186	2152	( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
ansond	0:137634ff4186	2153	{
ansond	0:137634ff4186	2154	break;
ansond	0:137634ff4186	2155	}
ansond	0:137634ff4186	2156
ansond	0:137634ff4186	2157	if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
ansond	0:137634ff4186	2158	goto cleanup;
ansond	0:137634ff4186	2159
ansond	0:137634ff4186	2160	/*
ansond	0:137634ff4186	2161	* Next candidates. We want to preserve Y = (X-1) / 2 and
ansond	0:137634ff4186	2162	* Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
ansond	0:137634ff4186	2163	* so up Y by 6 and X by 12.
ansond	0:137634ff4186	2164	*/
ansond	0:137634ff4186	2165	MPI_CHK( mpi_add_int( X, X, 12 ) );
ansond	0:137634ff4186	2166	MPI_CHK( mpi_add_int( &Y, &Y, 6 ) );
ansond	0:137634ff4186	2167	}
ansond	0:137634ff4186	2168	}
ansond	0:137634ff4186	2169
ansond	0:137634ff4186	2170	cleanup:
ansond	0:137634ff4186	2171
ansond	0:137634ff4186	2172	mpi_free( &Y );
ansond	0:137634ff4186	2173
ansond	0:137634ff4186	2174	return( ret );
ansond	0:137634ff4186	2175	}
ansond	0:137634ff4186	2176
ansond	0:137634ff4186	2177	#endif /* POLARSSL_GENPRIME */
ansond	0:137634ff4186	2178
ansond	0:137634ff4186	2179	#if defined(POLARSSL_SELF_TEST)
ansond	0:137634ff4186	2180
ansond	0:137634ff4186	2181	#define GCD_PAIR_COUNT 3
ansond	0:137634ff4186	2182
ansond	0:137634ff4186	2183	static const int gcd_pairs[GCD_PAIR_COUNT][3] =
ansond	0:137634ff4186	2184	{
ansond	0:137634ff4186	2185	{ 693, 609, 21 },
ansond	0:137634ff4186	2186	{ 1764, 868, 28 },
ansond	0:137634ff4186	2187	{ 768454923, 542167814, 1 }
ansond	0:137634ff4186	2188	};
ansond	0:137634ff4186	2189
ansond	0:137634ff4186	2190	/*
ansond	0:137634ff4186	2191	* Checkup routine
ansond	0:137634ff4186	2192	*/
ansond	0:137634ff4186	2193	int mpi_self_test( int verbose )
ansond	0:137634ff4186	2194	{
ansond	0:137634ff4186	2195	int ret, i;
ansond	0:137634ff4186	2196	mpi A, E, N, X, Y, U, V;
ansond	0:137634ff4186	2197
ansond	0:137634ff4186	2198	mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
ansond	0:137634ff4186	2199	mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
ansond	0:137634ff4186	2200
ansond	0:137634ff4186	2201	MPI_CHK( mpi_read_string( &A, 16,
ansond	0:137634ff4186	2202	"EFE021C2645FD1DC586E69184AF4A31E" \
ansond	0:137634ff4186	2203	"D5F53E93B5F123FA41680867BA110131" \
ansond	0:137634ff4186	2204	"944FE7952E2517337780CB0DB80E61AA" \
ansond	0:137634ff4186	2205	"E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
ansond	0:137634ff4186	2206
ansond	0:137634ff4186	2207	MPI_CHK( mpi_read_string( &E, 16,
ansond	0:137634ff4186	2208	"B2E7EFD37075B9F03FF989C7C5051C20" \
ansond	0:137634ff4186	2209	"34D2A323810251127E7BF8625A4F49A5" \
ansond	0:137634ff4186	2210	"F3E27F4DA8BD59C47D6DAABA4C8127BD" \
ansond	0:137634ff4186	2211	"5B5C25763222FEFCCFC38B832366C29E" ) );
ansond	0:137634ff4186	2212
ansond	0:137634ff4186	2213	MPI_CHK( mpi_read_string( &N, 16,
ansond	0:137634ff4186	2214	"0066A198186C18C10B2F5ED9B522752A" \
ansond	0:137634ff4186	2215	"9830B69916E535C8F047518A889A43A5" \
ansond	0:137634ff4186	2216	"94B6BED27A168D31D4A52F88925AA8F5" ) );
ansond	0:137634ff4186	2217
ansond	0:137634ff4186	2218	MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
ansond	0:137634ff4186	2219
ansond	0:137634ff4186	2220	MPI_CHK( mpi_read_string( &U, 16,
ansond	0:137634ff4186	2221	"602AB7ECA597A3D6B56FF9829A5E8B85" \
ansond	0:137634ff4186	2222	"9E857EA95A03512E2BAE7391688D264A" \
ansond	0:137634ff4186	2223	"A5663B0341DB9CCFD2C4C5F421FEC814" \
ansond	0:137634ff4186	2224	"8001B72E848A38CAE1C65F78E56ABDEF" \
ansond	0:137634ff4186	2225	"E12D3C039B8A02D6BE593F0BBBDA56F1" \
ansond	0:137634ff4186	2226	"ECF677152EF804370C1A305CAF3B5BF1" \
ansond	0:137634ff4186	2227	"30879B56C61DE584A0F53A2447A51E" ) );
ansond	0:137634ff4186	2228
ansond	0:137634ff4186	2229	if( verbose != 0 )
ansond	0:137634ff4186	2230	polarssl_printf( " MPI test #1 (mul_mpi): " );
ansond	0:137634ff4186	2231
ansond	0:137634ff4186	2232	if( mpi_cmp_mpi( &X, &U ) != 0 )
ansond	0:137634ff4186	2233	{
ansond	0:137634ff4186	2234	if( verbose != 0 )
ansond	0:137634ff4186	2235	polarssl_printf( "failed\n" );
ansond	0:137634ff4186	2236
ansond	0:137634ff4186	2237	ret = 1;
ansond	0:137634ff4186	2238	goto cleanup;
ansond	0:137634ff4186	2239	}
ansond	0:137634ff4186	2240
ansond	0:137634ff4186	2241	if( verbose != 0 )
ansond	0:137634ff4186	2242	polarssl_printf( "passed\n" );
ansond	0:137634ff4186	2243
ansond	0:137634ff4186	2244	MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
ansond	0:137634ff4186	2245
ansond	0:137634ff4186	2246	MPI_CHK( mpi_read_string( &U, 16,
ansond	0:137634ff4186	2247	"256567336059E52CAE22925474705F39A94" ) );
ansond	0:137634ff4186	2248
ansond	0:137634ff4186	2249	MPI_CHK( mpi_read_string( &V, 16,
ansond	0:137634ff4186	2250	"6613F26162223DF488E9CD48CC132C7A" \
ansond	0:137634ff4186	2251	"0AC93C701B001B092E4E5B9F73BCD27B" \
ansond	0:137634ff4186	2252	"9EE50D0657C77F374E903CDFA4C642" ) );
ansond	0:137634ff4186	2253
ansond	0:137634ff4186	2254	if( verbose != 0 )
ansond	0:137634ff4186	2255	polarssl_printf( " MPI test #2 (div_mpi): " );
ansond	0:137634ff4186	2256
ansond	0:137634ff4186	2257	if( mpi_cmp_mpi( &X, &U ) != 0 \|\|
ansond	0:137634ff4186	2258	mpi_cmp_mpi( &Y, &V ) != 0 )
ansond	0:137634ff4186	2259	{
ansond	0:137634ff4186	2260	if( verbose != 0 )
ansond	0:137634ff4186	2261	polarssl_printf( "failed\n" );
ansond	0:137634ff4186	2262
ansond	0:137634ff4186	2263	ret = 1;
ansond	0:137634ff4186	2264	goto cleanup;
ansond	0:137634ff4186	2265	}
ansond	0:137634ff4186	2266
ansond	0:137634ff4186	2267	if( verbose != 0 )
ansond	0:137634ff4186	2268	polarssl_printf( "passed\n" );
ansond	0:137634ff4186	2269
ansond	0:137634ff4186	2270	MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
ansond	0:137634ff4186	2271
ansond	0:137634ff4186	2272	MPI_CHK( mpi_read_string( &U, 16,
ansond	0:137634ff4186	2273	"36E139AEA55215609D2816998ED020BB" \
ansond	0:137634ff4186	2274	"BD96C37890F65171D948E9BC7CBAA4D9" \
ansond	0:137634ff4186	2275	"325D24D6A3C12710F10A09FA08AB87" ) );
ansond	0:137634ff4186	2276
ansond	0:137634ff4186	2277	if( verbose != 0 )
ansond	0:137634ff4186	2278	polarssl_printf( " MPI test #3 (exp_mod): " );
ansond	0:137634ff4186	2279
ansond	0:137634ff4186	2280	if( mpi_cmp_mpi( &X, &U ) != 0 )
ansond	0:137634ff4186	2281	{
ansond	0:137634ff4186	2282	if( verbose != 0 )
ansond	0:137634ff4186	2283	polarssl_printf( "failed\n" );
ansond	0:137634ff4186	2284
ansond	0:137634ff4186	2285	ret = 1;
ansond	0:137634ff4186	2286	goto cleanup;
ansond	0:137634ff4186	2287	}
ansond	0:137634ff4186	2288
ansond	0:137634ff4186	2289	if( verbose != 0 )
ansond	0:137634ff4186	2290	polarssl_printf( "passed\n" );
ansond	0:137634ff4186	2291
ansond	0:137634ff4186	2292	MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
ansond	0:137634ff4186	2293
ansond	0:137634ff4186	2294	MPI_CHK( mpi_read_string( &U, 16,
ansond	0:137634ff4186	2295	"003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
ansond	0:137634ff4186	2296	"C3DBA76456363A10869622EAC2DD84EC" \
ansond	0:137634ff4186	2297	"C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
ansond	0:137634ff4186	2298
ansond	0:137634ff4186	2299	if( verbose != 0 )
ansond	0:137634ff4186	2300	polarssl_printf( " MPI test #4 (inv_mod): " );
ansond	0:137634ff4186	2301
ansond	0:137634ff4186	2302	if( mpi_cmp_mpi( &X, &U ) != 0 )
ansond	0:137634ff4186	2303	{
ansond	0:137634ff4186	2304	if( verbose != 0 )
ansond	0:137634ff4186	2305	polarssl_printf( "failed\n" );
ansond	0:137634ff4186	2306
ansond	0:137634ff4186	2307	ret = 1;
ansond	0:137634ff4186	2308	goto cleanup;
ansond	0:137634ff4186	2309	}
ansond	0:137634ff4186	2310
ansond	0:137634ff4186	2311	if( verbose != 0 )
ansond	0:137634ff4186	2312	polarssl_printf( "passed\n" );
ansond	0:137634ff4186	2313
ansond	0:137634ff4186	2314	if( verbose != 0 )
ansond	0:137634ff4186	2315	polarssl_printf( " MPI test #5 (simple gcd): " );
ansond	0:137634ff4186	2316
ansond	0:137634ff4186	2317	for( i = 0; i < GCD_PAIR_COUNT; i++ )
ansond	0:137634ff4186	2318	{
ansond	0:137634ff4186	2319	MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
ansond	0:137634ff4186	2320	MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
ansond	0:137634ff4186	2321
ansond	0:137634ff4186	2322	MPI_CHK( mpi_gcd( &A, &X, &Y ) );
ansond	0:137634ff4186	2323
ansond	0:137634ff4186	2324	if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
ansond	0:137634ff4186	2325	{
ansond	0:137634ff4186	2326	if( verbose != 0 )
ansond	0:137634ff4186	2327	polarssl_printf( "failed at %d\n", i );
ansond	0:137634ff4186	2328
ansond	0:137634ff4186	2329	ret = 1;
ansond	0:137634ff4186	2330	goto cleanup;
ansond	0:137634ff4186	2331	}
ansond	0:137634ff4186	2332	}
ansond	0:137634ff4186	2333
ansond	0:137634ff4186	2334	if( verbose != 0 )
ansond	0:137634ff4186	2335	polarssl_printf( "passed\n" );
ansond	0:137634ff4186	2336
ansond	0:137634ff4186	2337	cleanup:
ansond	0:137634ff4186	2338
ansond	0:137634ff4186	2339	if( ret != 0 && verbose != 0 )
ansond	0:137634ff4186	2340	polarssl_printf( "Unexpected error, return code = %08X\n", ret );
ansond	0:137634ff4186	2341
ansond	0:137634ff4186	2342	mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
ansond	0:137634ff4186	2343	mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
ansond	0:137634ff4186	2344
ansond	0:137634ff4186	2345	if( verbose != 0 )
ansond	0:137634ff4186	2346	polarssl_printf( "\n" );
ansond	0:137634ff4186	2347
ansond	0:137634ff4186	2348	return( ret );
ansond	0:137634ff4186	2349	}
ansond	0:137634ff4186	2350
ansond	0:137634ff4186	2351	#endif /* POLARSSL_SELF_TEST */
ansond	0:137634ff4186	2352
ansond	0:137634ff4186	2353	#endif /* POLARSSL_BIGNUM_C */
ansond	0:137634ff4186	2354

Repository toolbox

Export to desktop IDE

Repository details

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

This repository is Public (Unlisted).

The code in this repository is Apache licensed.

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

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning