mbed-os - mbed-os

EL4121 Embedded System » Code » mbed-os

mbed-os

Dependents: cobaLCDJoyMotor_Thread odometry_omni_3roda_v3 odometry_omni_3roda_v1 odometry_omni_3roda_v2 ... more

features/mbedtls/src/bignum.c@0:b74591d5ab33, 2017-12-11 (annotated)

Committer:: be_bryan
Date:: Mon Dec 11 17:54:04 2017 +0000
Revision:: 0:b74591d5ab33

motor ++

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	12 Dec 2017
Imports:	1018
Forks:	0
Commits:	1
Dependents:	14
Dependencies:	0
Followers:	23

features/mbedtls/src/bignum.c@0:b74591d5ab33, 2017-12-11 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning