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