mbedtls - mbed TLS Build

Users » williequesada » Code » mbedtls

mbed TLS Build

library/bignum.c@0:cdf462088d13, 2017-01-05 (annotated)

Committer:: markrad
Date:: Thu Jan 05 00:18:44 2017 +0000
Revision:: 0:cdf462088d13

Initial commit

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Repository details

Type:	Library
Created:	04 Jun 2019
Imports:	32
Forks:	0
Commits:	2
Dependents:	1
Dependencies:	0
Followers:	5

Developers

Willie Solano

Pablo Andrés Araya Castillo

library/bignum.c@0:cdf462088d13, 2017-01-05 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Developers

Important Information for this Arm website

Access Warning