6_songs-from-the-cloud - This is a fork due to permission issues

Users » timbeight » Code » 6_songs-from-the-cloud

Timothy Beight / Mbed 2 deprecated 6_songs-from-the-cloud

This is a fork due to permission issues

Dependencies: mbed Socket lwip-eth lwip-sys lwip

Fork of 6_songs-from-the-cloud by MakingMusicWorkshop

mbed-client/mbedtls/source/bignum.c@0:f7c60d3e7b8a, 2016-05-18 (annotated)

Committer:: maclobdell
Date:: Wed May 18 19:06:32 2016 +0000
Revision:: 0:f7c60d3e7b8a

clean version

Who changed what in which revision?

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

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	19 May 2016
Imports:	0
Forks:	0
Commits:	2
Dependents:	0
Dependencies:	5
Followers:	1

mbed-client/mbedtls/source/bignum.c@0:f7c60d3e7b8a, 2016-05-18 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning