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@1:0ddbe2d3319c, 2016-05-19 (annotated)

Committer:
timbeight
Date:
Thu May 19 16:02:10 2016 +0000
Revision:
1:0ddbe2d3319c
Parent:
0:f7c60d3e7b8a 
This is my first commit while in the class.

Who changed what in which revision?

UserRevisionLine numberNew 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 + u0*B + u1*N) / 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 */