Denislam Valeev / Mbed OS Nucleo_rtos_basic

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

mbed-os/features/mbedtls/src/bignum.c@0:e056ac8fecf8, 2018-03-13 (annotated)

Committer:
valeyev
Date:
Tue Mar 13 07:17:50 2018 +0000
Revision:
0:e056ac8fecf8
looking for...

Who changed what in which revision?

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