mbed-os - mbed os with nrf51 internal bandgap enabled to re…

Users » elessair » Code » mbed-os

mbed os with nrf51 internal bandgap enabled to read battery level

Dependents: BLE_file_test BLE_Blink ExternalEncoder

features/mbedtls/src/bignum.c@0:f269e3021894, 2016-10-23 (annotated)

Committer:: elessair
Date:: Sun Oct 23 15:10:02 2016 +0000
Revision:: 0:f269e3021894

Initial commit

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	23 Oct 2016
Imports:	1689
Forks:	1
Commits:	1
Dependents:	3
Dependencies:	0
Followers:	20

features/mbedtls/src/bignum.c@0:f269e3021894, 2016-10-23 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning