Kenji Arai
/
mbed-os_TYBLE16
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.
Dependents: TYBLE16_simple_data_logger TYBLE16_MP3_Air
Embed:
(wiki syntax)
Show/hide line numbers
bignum.c
00001 /* 00002 * Multi-precision integer library 00003 * 00004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved 00005 * SPDX-License-Identifier: Apache-2.0 00006 * 00007 * Licensed under the Apache License, Version 2.0 (the "License"); you may 00008 * not use this file except in compliance with the License. 00009 * You may obtain a copy of the License at 00010 * 00011 * http://www.apache.org/licenses/LICENSE-2.0 00012 * 00013 * Unless required by applicable law or agreed to in writing, software 00014 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 00015 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00016 * See the License for the specific language governing permissions and 00017 * limitations under the License. 00018 * 00019 * This file is part of mbed TLS (https://tls.mbed.org) 00020 */ 00021 00022 /* 00023 * The following sources were referenced in the design of this Multi-precision 00024 * Integer library: 00025 * 00026 * [1] Handbook of Applied Cryptography - 1997 00027 * Menezes, van Oorschot and Vanstone 00028 * 00029 * [2] Multi-Precision Math 00030 * Tom St Denis 00031 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf 00032 * 00033 * [3] GNU Multi-Precision Arithmetic Library 00034 * https://gmplib.org/manual/index.html 00035 * 00036 */ 00037 00038 #if !defined(MBEDTLS_CONFIG_FILE) 00039 #include "mbedtls/config.h" 00040 #else 00041 #include MBEDTLS_CONFIG_FILE 00042 #endif 00043 00044 #if defined(MBEDTLS_BIGNUM_C) 00045 00046 #include "mbedtls/bignum.h" 00047 #include "mbedtls/bn_mul.h" 00048 #include "mbedtls/platform_util.h" 00049 00050 #include <string.h> 00051 00052 #if defined(MBEDTLS_PLATFORM_C) 00053 #include "mbedtls/platform.h" 00054 #else 00055 #include <stdio.h> 00056 #include <stdlib.h> 00057 #define mbedtls_printf printf 00058 #define mbedtls_calloc calloc 00059 #define mbedtls_free free 00060 #endif 00061 00062 #define MPI_VALIDATE_RET( cond ) \ 00063 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA ) 00064 #define MPI_VALIDATE( cond ) \ 00065 MBEDTLS_INTERNAL_VALIDATE( cond ) 00066 00067 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */ 00068 #define biL (ciL << 3) /* bits in limb */ 00069 #define biH (ciL << 2) /* half limb size */ 00070 00071 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */ 00072 00073 /* 00074 * Convert between bits/chars and number of limbs 00075 * Divide first in order to avoid potential overflows 00076 */ 00077 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) ) 00078 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) ) 00079 00080 /* Implementation that should never be optimized out by the compiler */ 00081 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n ) 00082 { 00083 mbedtls_platform_zeroize( v, ciL * n ); 00084 } 00085 00086 /* 00087 * Initialize one MPI 00088 */ 00089 void mbedtls_mpi_init( mbedtls_mpi *X ) 00090 { 00091 MPI_VALIDATE( X != NULL ); 00092 00093 X->s = 1; 00094 X->n = 0; 00095 X->p = NULL; 00096 } 00097 00098 /* 00099 * Unallocate one MPI 00100 */ 00101 void mbedtls_mpi_free( mbedtls_mpi *X ) 00102 { 00103 if( X == NULL ) 00104 return; 00105 00106 if( X->p != NULL ) 00107 { 00108 mbedtls_mpi_zeroize( X->p , X->n ); 00109 mbedtls_free( X->p ); 00110 } 00111 00112 X->s = 1; 00113 X->n = 0; 00114 X->p = NULL; 00115 } 00116 00117 /* 00118 * Enlarge to the specified number of limbs 00119 */ 00120 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ) 00121 { 00122 mbedtls_mpi_uint *p; 00123 MPI_VALIDATE_RET( X != NULL ); 00124 00125 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS ) 00126 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 00127 00128 if( X->n < nblimbs ) 00129 { 00130 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL ) 00131 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 00132 00133 if( X->p != NULL ) 00134 { 00135 memcpy( p, X->p , X->n * ciL ); 00136 mbedtls_mpi_zeroize( X->p , X->n ); 00137 mbedtls_free( X->p ); 00138 } 00139 00140 X->n = nblimbs; 00141 X->p = p; 00142 } 00143 00144 return( 0 ); 00145 } 00146 00147 /* 00148 * Resize down as much as possible, 00149 * while keeping at least the specified number of limbs 00150 */ 00151 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ) 00152 { 00153 mbedtls_mpi_uint *p; 00154 size_t i; 00155 MPI_VALIDATE_RET( X != NULL ); 00156 00157 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS ) 00158 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 00159 00160 /* Actually resize up in this case */ 00161 if( X->n <= nblimbs ) 00162 return( mbedtls_mpi_grow( X, nblimbs ) ); 00163 00164 for( i = X->n - 1; i > 0; i-- ) 00165 if( X->p [i] != 0 ) 00166 break; 00167 i++; 00168 00169 if( i < nblimbs ) 00170 i = nblimbs; 00171 00172 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL ) 00173 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 00174 00175 if( X->p != NULL ) 00176 { 00177 memcpy( p, X->p , i * ciL ); 00178 mbedtls_mpi_zeroize( X->p , X->n ); 00179 mbedtls_free( X->p ); 00180 } 00181 00182 X->n = i; 00183 X->p = p; 00184 00185 return( 0 ); 00186 } 00187 00188 /* 00189 * Copy the contents of Y into X 00190 */ 00191 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ) 00192 { 00193 int ret = 0; 00194 size_t i; 00195 MPI_VALIDATE_RET( X != NULL ); 00196 MPI_VALIDATE_RET( Y != NULL ); 00197 00198 if( X == Y ) 00199 return( 0 ); 00200 00201 if( Y->p == NULL ) 00202 { 00203 mbedtls_mpi_free( X ); 00204 return( 0 ); 00205 } 00206 00207 for( i = Y->n - 1; i > 0; i-- ) 00208 if( Y->p [i] != 0 ) 00209 break; 00210 i++; 00211 00212 X->s = Y->s ; 00213 00214 if( X->n < i ) 00215 { 00216 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) ); 00217 } 00218 else 00219 { 00220 memset( X->p + i, 0, ( X->n - i ) * ciL ); 00221 } 00222 00223 memcpy( X->p , Y->p , i * ciL ); 00224 00225 cleanup: 00226 00227 return( ret ); 00228 } 00229 00230 /* 00231 * Swap the contents of X and Y 00232 */ 00233 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ) 00234 { 00235 mbedtls_mpi T; 00236 MPI_VALIDATE( X != NULL ); 00237 MPI_VALIDATE( Y != NULL ); 00238 00239 memcpy( &T, X, sizeof( mbedtls_mpi ) ); 00240 memcpy( X, Y, sizeof( mbedtls_mpi ) ); 00241 memcpy( Y, &T, sizeof( mbedtls_mpi ) ); 00242 } 00243 00244 /* 00245 * Conditionally assign X = Y, without leaking information 00246 * about whether the assignment was made or not. 00247 * (Leaking information about the respective sizes of X and Y is ok however.) 00248 */ 00249 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign ) 00250 { 00251 int ret = 0; 00252 size_t i; 00253 MPI_VALIDATE_RET( X != NULL ); 00254 MPI_VALIDATE_RET( Y != NULL ); 00255 00256 /* make sure assign is 0 or 1 in a time-constant manner */ 00257 assign = (assign | (unsigned char)-assign) >> 7; 00258 00259 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); 00260 00261 X->s = X->s * ( 1 - assign ) + Y->s * assign; 00262 00263 for( i = 0; i < Y->n; i++ ) 00264 X->p [i] = X->p [i] * ( 1 - assign ) + Y->p [i] * assign; 00265 00266 for( ; i < X->n; i++ ) 00267 X->p [i] *= ( 1 - assign ); 00268 00269 cleanup: 00270 return( ret ); 00271 } 00272 00273 /* 00274 * Conditionally swap X and Y, without leaking information 00275 * about whether the swap was made or not. 00276 * Here it is not ok to simply swap the pointers, which whould lead to 00277 * different memory access patterns when X and Y are used afterwards. 00278 */ 00279 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap ) 00280 { 00281 int ret, s; 00282 size_t i; 00283 mbedtls_mpi_uint tmp; 00284 MPI_VALIDATE_RET( X != NULL ); 00285 MPI_VALIDATE_RET( Y != NULL ); 00286 00287 if( X == Y ) 00288 return( 0 ); 00289 00290 /* make sure swap is 0 or 1 in a time-constant manner */ 00291 swap = (swap | (unsigned char)-swap) >> 7; 00292 00293 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); 00294 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) ); 00295 00296 s = X->s ; 00297 X->s = X->s * ( 1 - swap ) + Y->s * swap; 00298 Y->s = Y->s * ( 1 - swap ) + s * swap; 00299 00300 00301 for( i = 0; i < X->n ; i++ ) 00302 { 00303 tmp = X->p [i]; 00304 X->p [i] = X->p [i] * ( 1 - swap ) + Y->p [i] * swap; 00305 Y->p [i] = Y->p [i] * ( 1 - swap ) + tmp * swap; 00306 } 00307 00308 cleanup: 00309 return( ret ); 00310 } 00311 00312 /* 00313 * Set value from integer 00314 */ 00315 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ) 00316 { 00317 int ret; 00318 MPI_VALIDATE_RET( X != NULL ); 00319 00320 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) ); 00321 memset( X->p , 0, X->n * ciL ); 00322 00323 X->p [0] = ( z < 0 ) ? -z : z; 00324 X->s = ( z < 0 ) ? -1 : 1; 00325 00326 cleanup: 00327 00328 return( ret ); 00329 } 00330 00331 /* 00332 * Get a specific bit 00333 */ 00334 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ) 00335 { 00336 MPI_VALIDATE_RET( X != NULL ); 00337 00338 if( X->n * biL <= pos ) 00339 return( 0 ); 00340 00341 return( ( X->p [pos / biL] >> ( pos % biL ) ) & 0x01 ); 00342 } 00343 00344 /* Get a specific byte, without range checks. */ 00345 #define GET_BYTE( X, i ) \ 00346 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff ) 00347 00348 /* 00349 * Set a bit to a specific value of 0 or 1 00350 */ 00351 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ) 00352 { 00353 int ret = 0; 00354 size_t off = pos / biL; 00355 size_t idx = pos % biL; 00356 MPI_VALIDATE_RET( X != NULL ); 00357 00358 if( val != 0 && val != 1 ) 00359 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00360 00361 if( X->n * biL <= pos ) 00362 { 00363 if( val == 0 ) 00364 return( 0 ); 00365 00366 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) ); 00367 } 00368 00369 X->p [off] &= ~( (mbedtls_mpi_uint) 0x01 << idx ); 00370 X->p [off] |= (mbedtls_mpi_uint) val << idx; 00371 00372 cleanup: 00373 00374 return( ret ); 00375 } 00376 00377 /* 00378 * Return the number of less significant zero-bits 00379 */ 00380 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ) 00381 { 00382 size_t i, j, count = 0; 00383 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 ); 00384 00385 for( i = 0; i < X->n ; i++ ) 00386 for( j = 0; j < biL; j++, count++ ) 00387 if( ( ( X->p [i] >> j ) & 1 ) != 0 ) 00388 return( count ); 00389 00390 return( 0 ); 00391 } 00392 00393 /* 00394 * Count leading zero bits in a given integer 00395 */ 00396 static size_t mbedtls_clz( const mbedtls_mpi_uint x ) 00397 { 00398 size_t j; 00399 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1); 00400 00401 for( j = 0; j < biL; j++ ) 00402 { 00403 if( x & mask ) break; 00404 00405 mask >>= 1; 00406 } 00407 00408 return j; 00409 } 00410 00411 /* 00412 * Return the number of bits 00413 */ 00414 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ) 00415 { 00416 size_t i, j; 00417 00418 if( X->n == 0 ) 00419 return( 0 ); 00420 00421 for( i = X->n - 1; i > 0; i-- ) 00422 if( X->p [i] != 0 ) 00423 break; 00424 00425 j = biL - mbedtls_clz( X->p [i] ); 00426 00427 return( ( i * biL ) + j ); 00428 } 00429 00430 /* 00431 * Return the total size in bytes 00432 */ 00433 size_t mbedtls_mpi_size( const mbedtls_mpi *X ) 00434 { 00435 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 ); 00436 } 00437 00438 /* 00439 * Convert an ASCII character to digit value 00440 */ 00441 static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c ) 00442 { 00443 *d = 255; 00444 00445 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30; 00446 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37; 00447 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57; 00448 00449 if( *d >= (mbedtls_mpi_uint) radix ) 00450 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER ); 00451 00452 return( 0 ); 00453 } 00454 00455 /* 00456 * Import from an ASCII string 00457 */ 00458 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) 00459 { 00460 int ret; 00461 size_t i, j, slen, n; 00462 mbedtls_mpi_uint d; 00463 mbedtls_mpi T; 00464 MPI_VALIDATE_RET( X != NULL ); 00465 MPI_VALIDATE_RET( s != NULL ); 00466 00467 if( radix < 2 || radix > 16 ) 00468 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00469 00470 mbedtls_mpi_init( &T ); 00471 00472 slen = strlen( s ); 00473 00474 if( radix == 16 ) 00475 { 00476 if( slen > MPI_SIZE_T_MAX >> 2 ) 00477 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00478 00479 n = BITS_TO_LIMBS( slen << 2 ); 00480 00481 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) ); 00482 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 00483 00484 for( i = slen, j = 0; i > 0; i--, j++ ) 00485 { 00486 if( i == 1 && s[i - 1] == '-' ) 00487 { 00488 X->s = -1; 00489 break; 00490 } 00491 00492 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); 00493 X->p [j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 ); 00494 } 00495 } 00496 else 00497 { 00498 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 00499 00500 for( i = 0; i < slen; i++ ) 00501 { 00502 if( i == 0 && s[i] == '-' ) 00503 { 00504 X->s = -1; 00505 continue; 00506 } 00507 00508 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); 00509 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) ); 00510 00511 if( X->s == 1 ) 00512 { 00513 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) ); 00514 } 00515 else 00516 { 00517 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) ); 00518 } 00519 } 00520 } 00521 00522 cleanup: 00523 00524 mbedtls_mpi_free( &T ); 00525 00526 return( ret ); 00527 } 00528 00529 /* 00530 * Helper to write the digits high-order first. 00531 */ 00532 static int mpi_write_hlp( mbedtls_mpi *X, int radix, 00533 char **p, const size_t buflen ) 00534 { 00535 int ret; 00536 mbedtls_mpi_uint r; 00537 size_t length = 0; 00538 char *p_end = *p + buflen; 00539 00540 do 00541 { 00542 if( length >= buflen ) 00543 { 00544 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 00545 } 00546 00547 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) ); 00548 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) ); 00549 /* 00550 * Write the residue in the current position, as an ASCII character. 00551 */ 00552 if( r < 0xA ) 00553 *(--p_end) = (char)( '0' + r ); 00554 else 00555 *(--p_end) = (char)( 'A' + ( r - 0xA ) ); 00556 00557 length++; 00558 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 ); 00559 00560 memmove( *p, p_end, length ); 00561 *p += length; 00562 00563 cleanup: 00564 00565 return( ret ); 00566 } 00567 00568 /* 00569 * Export into an ASCII string 00570 */ 00571 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, 00572 char *buf, size_t buflen, size_t *olen ) 00573 { 00574 int ret = 0; 00575 size_t n; 00576 char *p; 00577 mbedtls_mpi T; 00578 MPI_VALIDATE_RET( X != NULL ); 00579 MPI_VALIDATE_RET( olen != NULL ); 00580 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 00581 00582 if( radix < 2 || radix > 16 ) 00583 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00584 00585 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */ 00586 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present 00587 * `n`. If radix > 4, this might be a strict 00588 * overapproximation of the number of 00589 * radix-adic digits needed to present `n`. */ 00590 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to 00591 * present `n`. */ 00592 00593 n += 1; /* Terminating null byte */ 00594 n += 1; /* Compensate for the divisions above, which round down `n` 00595 * in case it's not even. */ 00596 n += 1; /* Potential '-'-sign. */ 00597 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing, 00598 * which always uses an even number of hex-digits. */ 00599 00600 if( buflen < n ) 00601 { 00602 *olen = n; 00603 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 00604 } 00605 00606 p = buf; 00607 mbedtls_mpi_init( &T ); 00608 00609 if( X->s == -1 ) 00610 { 00611 *p++ = '-'; 00612 buflen--; 00613 } 00614 00615 if( radix == 16 ) 00616 { 00617 int c; 00618 size_t i, j, k; 00619 00620 for( i = X->n , k = 0; i > 0; i-- ) 00621 { 00622 for( j = ciL; j > 0; j-- ) 00623 { 00624 c = ( X->p [i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF; 00625 00626 if( c == 0 && k == 0 && ( i + j ) != 2 ) 00627 continue; 00628 00629 *(p++) = "0123456789ABCDEF" [c / 16]; 00630 *(p++) = "0123456789ABCDEF" [c % 16]; 00631 k = 1; 00632 } 00633 } 00634 } 00635 else 00636 { 00637 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) ); 00638 00639 if( T.s == -1 ) 00640 T.s = 1; 00641 00642 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) ); 00643 } 00644 00645 *p++ = '\0'; 00646 *olen = p - buf; 00647 00648 cleanup: 00649 00650 mbedtls_mpi_free( &T ); 00651 00652 return( ret ); 00653 } 00654 00655 #if defined(MBEDTLS_FS_IO) 00656 /* 00657 * Read X from an opened file 00658 */ 00659 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ) 00660 { 00661 mbedtls_mpi_uint d; 00662 size_t slen; 00663 char *p; 00664 /* 00665 * Buffer should have space for (short) label and decimal formatted MPI, 00666 * newline characters and '\0' 00667 */ 00668 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; 00669 00670 MPI_VALIDATE_RET( X != NULL ); 00671 MPI_VALIDATE_RET( fin != NULL ); 00672 00673 if( radix < 2 || radix > 16 ) 00674 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00675 00676 memset( s, 0, sizeof( s ) ); 00677 if( fgets( s, sizeof( s ) - 1, fin ) == NULL ) 00678 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); 00679 00680 slen = strlen( s ); 00681 if( slen == sizeof( s ) - 2 ) 00682 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 00683 00684 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; } 00685 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; } 00686 00687 p = s + slen; 00688 while( p-- > s ) 00689 if( mpi_get_digit( &d, radix, *p ) != 0 ) 00690 break; 00691 00692 return( mbedtls_mpi_read_string( X, radix, p + 1 ) ); 00693 } 00694 00695 /* 00696 * Write X into an opened file (or stdout if fout == NULL) 00697 */ 00698 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout ) 00699 { 00700 int ret; 00701 size_t n, slen, plen; 00702 /* 00703 * Buffer should have space for (short) label and decimal formatted MPI, 00704 * newline characters and '\0' 00705 */ 00706 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; 00707 MPI_VALIDATE_RET( X != NULL ); 00708 00709 if( radix < 2 || radix > 16 ) 00710 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 00711 00712 memset( s, 0, sizeof( s ) ); 00713 00714 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) ); 00715 00716 if( p == NULL ) p = ""; 00717 00718 plen = strlen( p ); 00719 slen = strlen( s ); 00720 s[slen++] = '\r'; 00721 s[slen++] = '\n'; 00722 00723 if( fout != NULL ) 00724 { 00725 if( fwrite( p, 1, plen, fout ) != plen || 00726 fwrite( s, 1, slen, fout ) != slen ) 00727 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); 00728 } 00729 else 00730 mbedtls_printf( "%s%s", p, s ); 00731 00732 cleanup: 00733 00734 return( ret ); 00735 } 00736 #endif /* MBEDTLS_FS_IO */ 00737 00738 00739 /* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint 00740 * into the storage form used by mbedtls_mpi. */ 00741 00742 static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x ) 00743 { 00744 uint8_t i; 00745 unsigned char *x_ptr; 00746 mbedtls_mpi_uint tmp = 0; 00747 00748 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ ) 00749 { 00750 tmp <<= CHAR_BIT; 00751 tmp |= (mbedtls_mpi_uint) *x_ptr; 00752 } 00753 00754 return( tmp ); 00755 } 00756 00757 static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x ) 00758 { 00759 #if defined(__BYTE_ORDER__) 00760 00761 /* Nothing to do on bigendian systems. */ 00762 #if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ ) 00763 return( x ); 00764 #endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */ 00765 00766 #if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ ) 00767 00768 /* For GCC and Clang, have builtins for byte swapping. */ 00769 #if defined(__GNUC__) && defined(__GNUC_PREREQ) 00770 #if __GNUC_PREREQ(4,3) 00771 #define have_bswap 00772 #endif 00773 #endif 00774 00775 #if defined(__clang__) && defined(__has_builtin) 00776 #if __has_builtin(__builtin_bswap32) && \ 00777 __has_builtin(__builtin_bswap64) 00778 #define have_bswap 00779 #endif 00780 #endif 00781 00782 #if defined(have_bswap) 00783 /* The compiler is hopefully able to statically evaluate this! */ 00784 switch( sizeof(mbedtls_mpi_uint) ) 00785 { 00786 case 4: 00787 return( __builtin_bswap32(x) ); 00788 case 8: 00789 return( __builtin_bswap64(x) ); 00790 } 00791 #endif 00792 #endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */ 00793 #endif /* __BYTE_ORDER__ */ 00794 00795 /* Fall back to C-based reordering if we don't know the byte order 00796 * or we couldn't use a compiler-specific builtin. */ 00797 return( mpi_uint_bigendian_to_host_c( x ) ); 00798 } 00799 00800 static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs ) 00801 { 00802 mbedtls_mpi_uint *cur_limb_left; 00803 mbedtls_mpi_uint *cur_limb_right; 00804 if( limbs == 0 ) 00805 return; 00806 00807 /* 00808 * Traverse limbs and 00809 * - adapt byte-order in each limb 00810 * - swap the limbs themselves. 00811 * For that, simultaneously traverse the limbs from left to right 00812 * and from right to left, as long as the left index is not bigger 00813 * than the right index (it's not a problem if limbs is odd and the 00814 * indices coincide in the last iteration). 00815 */ 00816 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 ); 00817 cur_limb_left <= cur_limb_right; 00818 cur_limb_left++, cur_limb_right-- ) 00819 { 00820 mbedtls_mpi_uint tmp; 00821 /* Note that if cur_limb_left == cur_limb_right, 00822 * this code effectively swaps the bytes only once. */ 00823 tmp = mpi_uint_bigendian_to_host( *cur_limb_left ); 00824 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right ); 00825 *cur_limb_right = tmp; 00826 } 00827 } 00828 00829 /* 00830 * Import X from unsigned binary data, little endian 00831 */ 00832 int mbedtls_mpi_read_binary_le( mbedtls_mpi *X, 00833 const unsigned char *buf, size_t buflen ) 00834 { 00835 int ret; 00836 size_t i; 00837 size_t const limbs = CHARS_TO_LIMBS( buflen ); 00838 00839 /* Ensure that target MPI has exactly the necessary number of limbs */ 00840 if( X->n != limbs ) 00841 { 00842 mbedtls_mpi_free( X ); 00843 mbedtls_mpi_init( X ); 00844 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) ); 00845 } 00846 00847 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 00848 00849 for( i = 0; i < buflen; i++ ) 00850 X->p [i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3); 00851 00852 cleanup: 00853 00854 /* 00855 * This function is also used to import keys. However, wiping the buffers 00856 * upon failure is not necessary because failure only can happen before any 00857 * input is copied. 00858 */ 00859 return( ret ); 00860 } 00861 00862 /* 00863 * Import X from unsigned binary data, big endian 00864 */ 00865 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen ) 00866 { 00867 int ret; 00868 size_t const limbs = CHARS_TO_LIMBS( buflen ); 00869 size_t const overhead = ( limbs * ciL ) - buflen; 00870 unsigned char *Xp; 00871 00872 MPI_VALIDATE_RET( X != NULL ); 00873 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 00874 00875 /* Ensure that target MPI has exactly the necessary number of limbs */ 00876 if( X->n != limbs ) 00877 { 00878 mbedtls_mpi_free( X ); 00879 mbedtls_mpi_init( X ); 00880 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) ); 00881 } 00882 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 00883 00884 /* Avoid calling `memcpy` with NULL source argument, 00885 * even if buflen is 0. */ 00886 if( buf != NULL ) 00887 { 00888 Xp = (unsigned char*) X->p ; 00889 memcpy( Xp + overhead, buf, buflen ); 00890 00891 mpi_bigendian_to_host( X->p , limbs ); 00892 } 00893 00894 cleanup: 00895 00896 /* 00897 * This function is also used to import keys. However, wiping the buffers 00898 * upon failure is not necessary because failure only can happen before any 00899 * input is copied. 00900 */ 00901 return( ret ); 00902 } 00903 00904 /* 00905 * Export X into unsigned binary data, little endian 00906 */ 00907 int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X, 00908 unsigned char *buf, size_t buflen ) 00909 { 00910 size_t stored_bytes = X->n * ciL; 00911 size_t bytes_to_copy; 00912 size_t i; 00913 00914 if( stored_bytes < buflen ) 00915 { 00916 bytes_to_copy = stored_bytes; 00917 } 00918 else 00919 { 00920 bytes_to_copy = buflen; 00921 00922 /* The output buffer is smaller than the allocated size of X. 00923 * However X may fit if its leading bytes are zero. */ 00924 for( i = bytes_to_copy; i < stored_bytes; i++ ) 00925 { 00926 if( GET_BYTE( X, i ) != 0 ) 00927 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 00928 } 00929 } 00930 00931 for( i = 0; i < bytes_to_copy; i++ ) 00932 buf[i] = GET_BYTE( X, i ); 00933 00934 if( stored_bytes < buflen ) 00935 { 00936 /* Write trailing 0 bytes */ 00937 memset( buf + stored_bytes, 0, buflen - stored_bytes ); 00938 } 00939 00940 return( 0 ); 00941 } 00942 00943 /* 00944 * Export X into unsigned binary data, big endian 00945 */ 00946 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, 00947 unsigned char *buf, size_t buflen ) 00948 { 00949 size_t stored_bytes; 00950 size_t bytes_to_copy; 00951 unsigned char *p; 00952 size_t i; 00953 00954 MPI_VALIDATE_RET( X != NULL ); 00955 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 00956 00957 stored_bytes = X->n * ciL; 00958 00959 if( stored_bytes < buflen ) 00960 { 00961 /* There is enough space in the output buffer. Write initial 00962 * null bytes and record the position at which to start 00963 * writing the significant bytes. In this case, the execution 00964 * trace of this function does not depend on the value of the 00965 * number. */ 00966 bytes_to_copy = stored_bytes; 00967 p = buf + buflen - stored_bytes; 00968 memset( buf, 0, buflen - stored_bytes ); 00969 } 00970 else 00971 { 00972 /* The output buffer is smaller than the allocated size of X. 00973 * However X may fit if its leading bytes are zero. */ 00974 bytes_to_copy = buflen; 00975 p = buf; 00976 for( i = bytes_to_copy; i < stored_bytes; i++ ) 00977 { 00978 if( GET_BYTE( X, i ) != 0 ) 00979 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 00980 } 00981 } 00982 00983 for( i = 0; i < bytes_to_copy; i++ ) 00984 p[bytes_to_copy - i - 1] = GET_BYTE( X, i ); 00985 00986 return( 0 ); 00987 } 00988 00989 /* 00990 * Left-shift: X <<= count 00991 */ 00992 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ) 00993 { 00994 int ret; 00995 size_t i, v0, t1; 00996 mbedtls_mpi_uint r0 = 0, r1; 00997 MPI_VALIDATE_RET( X != NULL ); 00998 00999 v0 = count / (biL ); 01000 t1 = count & (biL - 1); 01001 01002 i = mbedtls_mpi_bitlen( X ) + count; 01003 01004 if( X->n * biL < i ) 01005 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) ); 01006 01007 ret = 0; 01008 01009 /* 01010 * shift by count / limb_size 01011 */ 01012 if( v0 > 0 ) 01013 { 01014 for( i = X->n ; i > v0; i-- ) 01015 X->p [i - 1] = X->p [i - v0 - 1]; 01016 01017 for( ; i > 0; i-- ) 01018 X->p [i - 1] = 0; 01019 } 01020 01021 /* 01022 * shift by count % limb_size 01023 */ 01024 if( t1 > 0 ) 01025 { 01026 for( i = v0; i < X->n ; i++ ) 01027 { 01028 r1 = X->p [i] >> (biL - t1); 01029 X->p [i] <<= t1; 01030 X->p [i] |= r0; 01031 r0 = r1; 01032 } 01033 } 01034 01035 cleanup: 01036 01037 return( ret ); 01038 } 01039 01040 /* 01041 * Right-shift: X >>= count 01042 */ 01043 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ) 01044 { 01045 size_t i, v0, v1; 01046 mbedtls_mpi_uint r0 = 0, r1; 01047 MPI_VALIDATE_RET( X != NULL ); 01048 01049 v0 = count / biL; 01050 v1 = count & (biL - 1); 01051 01052 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) ) 01053 return mbedtls_mpi_lset( X, 0 ); 01054 01055 /* 01056 * shift by count / limb_size 01057 */ 01058 if( v0 > 0 ) 01059 { 01060 for( i = 0; i < X->n - v0; i++ ) 01061 X->p [i] = X->p [i + v0]; 01062 01063 for( ; i < X->n; i++ ) 01064 X->p [i] = 0; 01065 } 01066 01067 /* 01068 * shift by count % limb_size 01069 */ 01070 if( v1 > 0 ) 01071 { 01072 for( i = X->n ; i > 0; i-- ) 01073 { 01074 r1 = X->p [i - 1] << (biL - v1); 01075 X->p [i - 1] >>= v1; 01076 X->p [i - 1] |= r0; 01077 r0 = r1; 01078 } 01079 } 01080 01081 return( 0 ); 01082 } 01083 01084 /* 01085 * Compare unsigned values 01086 */ 01087 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 01088 { 01089 size_t i, j; 01090 MPI_VALIDATE_RET( X != NULL ); 01091 MPI_VALIDATE_RET( Y != NULL ); 01092 01093 for( i = X->n ; i > 0; i-- ) 01094 if( X->p [i - 1] != 0 ) 01095 break; 01096 01097 for( j = Y->n ; j > 0; j-- ) 01098 if( Y->p [j - 1] != 0 ) 01099 break; 01100 01101 if( i == 0 && j == 0 ) 01102 return( 0 ); 01103 01104 if( i > j ) return( 1 ); 01105 if( j > i ) return( -1 ); 01106 01107 for( ; i > 0; i-- ) 01108 { 01109 if( X->p [i - 1] > Y->p [i - 1] ) return( 1 ); 01110 if( X->p [i - 1] < Y->p [i - 1] ) return( -1 ); 01111 } 01112 01113 return( 0 ); 01114 } 01115 01116 /* 01117 * Compare signed values 01118 */ 01119 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 01120 { 01121 size_t i, j; 01122 MPI_VALIDATE_RET( X != NULL ); 01123 MPI_VALIDATE_RET( Y != NULL ); 01124 01125 for( i = X->n ; i > 0; i-- ) 01126 if( X->p [i - 1] != 0 ) 01127 break; 01128 01129 for( j = Y->n ; j > 0; j-- ) 01130 if( Y->p [j - 1] != 0 ) 01131 break; 01132 01133 if( i == 0 && j == 0 ) 01134 return( 0 ); 01135 01136 if( i > j ) return( X->s ); 01137 if( j > i ) return( -Y->s ); 01138 01139 if( X->s > 0 && Y->s < 0 ) return( 1 ); 01140 if( Y->s > 0 && X->s < 0 ) return( -1 ); 01141 01142 for( ; i > 0; i-- ) 01143 { 01144 if( X->p [i - 1] > Y->p [i - 1] ) return( X->s ); 01145 if( X->p [i - 1] < Y->p [i - 1] ) return( -X->s ); 01146 } 01147 01148 return( 0 ); 01149 } 01150 01151 /* 01152 * Compare signed values 01153 */ 01154 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ) 01155 { 01156 mbedtls_mpi Y; 01157 mbedtls_mpi_uint p[1]; 01158 MPI_VALIDATE_RET( X != NULL ); 01159 01160 *p = ( z < 0 ) ? -z : z; 01161 Y.s = ( z < 0 ) ? -1 : 1; 01162 Y.n = 1; 01163 Y.p = p; 01164 01165 return( mbedtls_mpi_cmp_mpi( X, &Y ) ); 01166 } 01167 01168 /* 01169 * Unsigned addition: X = |A| + |B| (HAC 14.7) 01170 */ 01171 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01172 { 01173 int ret; 01174 size_t i, j; 01175 mbedtls_mpi_uint *o, *p, c, tmp; 01176 MPI_VALIDATE_RET( X != NULL ); 01177 MPI_VALIDATE_RET( A != NULL ); 01178 MPI_VALIDATE_RET( B != NULL ); 01179 01180 if( X == B ) 01181 { 01182 const mbedtls_mpi *T = A; A = X; B = T; 01183 } 01184 01185 if( X != A ) 01186 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 01187 01188 /* 01189 * X should always be positive as a result of unsigned additions. 01190 */ 01191 X->s = 1; 01192 01193 for( j = B->n ; j > 0; j-- ) 01194 if( B->p [j - 1] != 0 ) 01195 break; 01196 01197 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 01198 01199 o = B->p ; p = X->p ; c = 0; 01200 01201 /* 01202 * tmp is used because it might happen that p == o 01203 */ 01204 for( i = 0; i < j; i++, o++, p++ ) 01205 { 01206 tmp= *o; 01207 *p += c; c = ( *p < c ); 01208 *p += tmp; c += ( *p < tmp ); 01209 } 01210 01211 while( c != 0 ) 01212 { 01213 if( i >= X->n ) 01214 { 01215 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) ); 01216 p = X->p + i; 01217 } 01218 01219 *p += c; c = ( *p < c ); i++; p++; 01220 } 01221 01222 cleanup: 01223 01224 return( ret ); 01225 } 01226 01227 /* 01228 * Helper for mbedtls_mpi subtraction 01229 */ 01230 static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d ) 01231 { 01232 size_t i; 01233 mbedtls_mpi_uint c, z; 01234 01235 for( i = c = 0; i < n; i++, s++, d++ ) 01236 { 01237 z = ( *d < c ); *d -= c; 01238 c = ( *d < *s ) + z; *d -= *s; 01239 } 01240 01241 while( c != 0 ) 01242 { 01243 z = ( *d < c ); *d -= c; 01244 c = z; d++; 01245 } 01246 } 01247 01248 /* 01249 * Unsigned subtraction: X = |A| - |B| (HAC 14.9) 01250 */ 01251 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01252 { 01253 mbedtls_mpi TB; 01254 int ret; 01255 size_t n; 01256 MPI_VALIDATE_RET( X != NULL ); 01257 MPI_VALIDATE_RET( A != NULL ); 01258 MPI_VALIDATE_RET( B != NULL ); 01259 01260 if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) 01261 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 01262 01263 mbedtls_mpi_init( &TB ); 01264 01265 if( X == B ) 01266 { 01267 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); 01268 B = &TB; 01269 } 01270 01271 if( X != A ) 01272 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 01273 01274 /* 01275 * X should always be positive as a result of unsigned subtractions. 01276 */ 01277 X->s = 1; 01278 01279 ret = 0; 01280 01281 for( n = B->n ; n > 0; n-- ) 01282 if( B->p [n - 1] != 0 ) 01283 break; 01284 01285 mpi_sub_hlp( n, B->p , X->p ); 01286 01287 cleanup: 01288 01289 mbedtls_mpi_free( &TB ); 01290 01291 return( ret ); 01292 } 01293 01294 /* 01295 * Signed addition: X = A + B 01296 */ 01297 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01298 { 01299 int ret, s; 01300 MPI_VALIDATE_RET( X != NULL ); 01301 MPI_VALIDATE_RET( A != NULL ); 01302 MPI_VALIDATE_RET( B != NULL ); 01303 01304 s = A->s ; 01305 if( A->s * B->s < 0 ) 01306 { 01307 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 01308 { 01309 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 01310 X->s = s; 01311 } 01312 else 01313 { 01314 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 01315 X->s = -s; 01316 } 01317 } 01318 else 01319 { 01320 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 01321 X->s = s; 01322 } 01323 01324 cleanup: 01325 01326 return( ret ); 01327 } 01328 01329 /* 01330 * Signed subtraction: X = A - B 01331 */ 01332 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01333 { 01334 int ret, s; 01335 MPI_VALIDATE_RET( X != NULL ); 01336 MPI_VALIDATE_RET( A != NULL ); 01337 MPI_VALIDATE_RET( B != NULL ); 01338 01339 s = A->s ; 01340 if( A->s * B->s > 0 ) 01341 { 01342 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 01343 { 01344 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 01345 X->s = s; 01346 } 01347 else 01348 { 01349 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 01350 X->s = -s; 01351 } 01352 } 01353 else 01354 { 01355 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 01356 X->s = s; 01357 } 01358 01359 cleanup: 01360 01361 return( ret ); 01362 } 01363 01364 /* 01365 * Signed addition: X = A + b 01366 */ 01367 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 01368 { 01369 mbedtls_mpi _B; 01370 mbedtls_mpi_uint p[1]; 01371 MPI_VALIDATE_RET( X != NULL ); 01372 MPI_VALIDATE_RET( A != NULL ); 01373 01374 p[0] = ( b < 0 ) ? -b : b; 01375 _B.s = ( b < 0 ) ? -1 : 1; 01376 _B.n = 1; 01377 _B.p = p; 01378 01379 return( mbedtls_mpi_add_mpi( X, A, &_B ) ); 01380 } 01381 01382 /* 01383 * Signed subtraction: X = A - b 01384 */ 01385 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 01386 { 01387 mbedtls_mpi _B; 01388 mbedtls_mpi_uint p[1]; 01389 MPI_VALIDATE_RET( X != NULL ); 01390 MPI_VALIDATE_RET( A != NULL ); 01391 01392 p[0] = ( b < 0 ) ? -b : b; 01393 _B.s = ( b < 0 ) ? -1 : 1; 01394 _B.n = 1; 01395 _B.p = p; 01396 01397 return( mbedtls_mpi_sub_mpi( X, A, &_B ) ); 01398 } 01399 01400 /* 01401 * Helper for mbedtls_mpi multiplication 01402 */ 01403 static 01404 #if defined(__APPLE__) && defined(__arm__) 01405 /* 01406 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn) 01407 * appears to need this to prevent bad ARM code generation at -O3. 01408 */ 01409 __attribute__ ((noinline)) 01410 #endif 01411 void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b ) 01412 { 01413 mbedtls_mpi_uint c = 0, t = 0; 01414 01415 #if defined(MULADDC_HUIT) 01416 for( ; i >= 8; i -= 8 ) 01417 { 01418 MULADDC_INIT 01419 MULADDC_HUIT 01420 MULADDC_STOP 01421 } 01422 01423 for( ; i > 0; i-- ) 01424 { 01425 MULADDC_INIT 01426 MULADDC_CORE 01427 MULADDC_STOP 01428 } 01429 #else /* MULADDC_HUIT */ 01430 for( ; i >= 16; i -= 16 ) 01431 { 01432 MULADDC_INIT 01433 MULADDC_CORE MULADDC_CORE 01434 MULADDC_CORE MULADDC_CORE 01435 MULADDC_CORE MULADDC_CORE 01436 MULADDC_CORE MULADDC_CORE 01437 01438 MULADDC_CORE MULADDC_CORE 01439 MULADDC_CORE MULADDC_CORE 01440 MULADDC_CORE MULADDC_CORE 01441 MULADDC_CORE MULADDC_CORE 01442 MULADDC_STOP 01443 } 01444 01445 for( ; i >= 8; i -= 8 ) 01446 { 01447 MULADDC_INIT 01448 MULADDC_CORE MULADDC_CORE 01449 MULADDC_CORE MULADDC_CORE 01450 01451 MULADDC_CORE MULADDC_CORE 01452 MULADDC_CORE MULADDC_CORE 01453 MULADDC_STOP 01454 } 01455 01456 for( ; i > 0; i-- ) 01457 { 01458 MULADDC_INIT 01459 MULADDC_CORE 01460 MULADDC_STOP 01461 } 01462 #endif /* MULADDC_HUIT */ 01463 01464 t++; 01465 01466 do { 01467 *d += c; c = ( *d < c ); d++; 01468 } 01469 while( c != 0 ); 01470 } 01471 01472 /* 01473 * Baseline multiplication: X = A * B (HAC 14.12) 01474 */ 01475 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01476 { 01477 int ret; 01478 size_t i, j; 01479 mbedtls_mpi TA, TB; 01480 MPI_VALIDATE_RET( X != NULL ); 01481 MPI_VALIDATE_RET( A != NULL ); 01482 MPI_VALIDATE_RET( B != NULL ); 01483 01484 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB ); 01485 01486 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; } 01487 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; } 01488 01489 for( i = A->n ; i > 0; i-- ) 01490 if( A->p [i - 1] != 0 ) 01491 break; 01492 01493 for( j = B->n ; j > 0; j-- ) 01494 if( B->p [j - 1] != 0 ) 01495 break; 01496 01497 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) ); 01498 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 01499 01500 for( ; j > 0; j-- ) 01501 mpi_mul_hlp( i, A->p , X->p + j - 1, B->p [j - 1] ); 01502 01503 X->s = A->s * B->s ; 01504 01505 cleanup: 01506 01507 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA ); 01508 01509 return( ret ); 01510 } 01511 01512 /* 01513 * Baseline multiplication: X = A * b 01514 */ 01515 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ) 01516 { 01517 mbedtls_mpi _B; 01518 mbedtls_mpi_uint p[1]; 01519 MPI_VALIDATE_RET( X != NULL ); 01520 MPI_VALIDATE_RET( A != NULL ); 01521 01522 _B.s = 1; 01523 _B.n = 1; 01524 _B.p = p; 01525 p[0] = b; 01526 01527 return( mbedtls_mpi_mul_mpi( X, A, &_B ) ); 01528 } 01529 01530 /* 01531 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and 01532 * mbedtls_mpi_uint divisor, d 01533 */ 01534 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1, 01535 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r ) 01536 { 01537 #if defined(MBEDTLS_HAVE_UDBL) 01538 mbedtls_t_udbl dividend, quotient; 01539 #else 01540 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; 01541 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1; 01542 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; 01543 mbedtls_mpi_uint u0_msw, u0_lsw; 01544 size_t s; 01545 #endif 01546 01547 /* 01548 * Check for overflow 01549 */ 01550 if( 0 == d || u1 >= d ) 01551 { 01552 if (r != NULL) *r = ~0; 01553 01554 return ( ~0 ); 01555 } 01556 01557 #if defined(MBEDTLS_HAVE_UDBL) 01558 dividend = (mbedtls_t_udbl) u1 << biL; 01559 dividend |= (mbedtls_t_udbl) u0; 01560 quotient = dividend / d; 01561 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 ) 01562 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1; 01563 01564 if( r != NULL ) 01565 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) ); 01566 01567 return (mbedtls_mpi_uint) quotient; 01568 #else 01569 01570 /* 01571 * Algorithm D, Section 4.3.1 - The Art of Computer Programming 01572 * Vol. 2 - Seminumerical Algorithms, Knuth 01573 */ 01574 01575 /* 01576 * Normalize the divisor, d, and dividend, u0, u1 01577 */ 01578 s = mbedtls_clz( d ); 01579 d = d << s; 01580 01581 u1 = u1 << s; 01582 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) ); 01583 u0 = u0 << s; 01584 01585 d1 = d >> biH; 01586 d0 = d & uint_halfword_mask; 01587 01588 u0_msw = u0 >> biH; 01589 u0_lsw = u0 & uint_halfword_mask; 01590 01591 /* 01592 * Find the first quotient and remainder 01593 */ 01594 q1 = u1 / d1; 01595 r0 = u1 - d1 * q1; 01596 01597 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) ) 01598 { 01599 q1 -= 1; 01600 r0 += d1; 01601 01602 if ( r0 >= radix ) break; 01603 } 01604 01605 rAX = ( u1 * radix ) + ( u0_msw - q1 * d ); 01606 q0 = rAX / d1; 01607 r0 = rAX - q0 * d1; 01608 01609 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) ) 01610 { 01611 q0 -= 1; 01612 r0 += d1; 01613 01614 if ( r0 >= radix ) break; 01615 } 01616 01617 if (r != NULL) 01618 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s; 01619 01620 quotient = q1 * radix + q0; 01621 01622 return quotient; 01623 #endif 01624 } 01625 01626 /* 01627 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) 01628 */ 01629 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 01630 const mbedtls_mpi *B ) 01631 { 01632 int ret; 01633 size_t i, n, t, k; 01634 mbedtls_mpi X, Y, Z, T1, T2; 01635 MPI_VALIDATE_RET( A != NULL ); 01636 MPI_VALIDATE_RET( B != NULL ); 01637 01638 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 ) 01639 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 01640 01641 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); 01642 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); 01643 01644 if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) 01645 { 01646 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) ); 01647 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) ); 01648 return( 0 ); 01649 } 01650 01651 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) ); 01652 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) ); 01653 X.s = Y.s = 1; 01654 01655 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) ); 01656 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) ); 01657 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) ); 01658 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) ); 01659 01660 k = mbedtls_mpi_bitlen( &Y ) % biL; 01661 if( k < biL - 1 ) 01662 { 01663 k = biL - 1 - k; 01664 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) ); 01665 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) ); 01666 } 01667 else k = 0; 01668 01669 n = X.n - 1; 01670 t = Y.n - 1; 01671 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) ); 01672 01673 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 ) 01674 { 01675 Z.p [n - t]++; 01676 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) ); 01677 } 01678 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) ); 01679 01680 for( i = n; i > t ; i-- ) 01681 { 01682 if( X.p [i] >= Y.p [t] ) 01683 Z.p [i - t - 1] = ~0; 01684 else 01685 { 01686 Z.p [i - t - 1] = mbedtls_int_div_int( X.p [i], X.p [i - 1], 01687 Y.p [t], NULL); 01688 } 01689 01690 Z.p [i - t - 1]++; 01691 do 01692 { 01693 Z.p [i - t - 1]--; 01694 01695 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) ); 01696 T1.p [0] = ( t < 1 ) ? 0 : Y.p [t - 1]; 01697 T1.p [1] = Y.p [t]; 01698 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p [i - t - 1] ) ); 01699 01700 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) ); 01701 T2.p [0] = ( i < 2 ) ? 0 : X.p [i - 2]; 01702 T2.p [1] = ( i < 1 ) ? 0 : X.p [i - 1]; 01703 T2.p [2] = X.p [i]; 01704 } 01705 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 ); 01706 01707 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p [i - t - 1] ) ); 01708 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 01709 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); 01710 01711 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 ) 01712 { 01713 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) ); 01714 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 01715 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) ); 01716 Z.p [i - t - 1]--; 01717 } 01718 } 01719 01720 if( Q != NULL ) 01721 { 01722 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) ); 01723 Q->s = A->s * B->s ; 01724 } 01725 01726 if( R != NULL ) 01727 { 01728 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) ); 01729 X.s = A->s ; 01730 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) ); 01731 01732 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 ) 01733 R->s = 1; 01734 } 01735 01736 cleanup: 01737 01738 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 01739 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); 01740 01741 return( ret ); 01742 } 01743 01744 /* 01745 * Division by int: A = Q * b + R 01746 */ 01747 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, 01748 const mbedtls_mpi *A, 01749 mbedtls_mpi_sint b ) 01750 { 01751 mbedtls_mpi _B; 01752 mbedtls_mpi_uint p[1]; 01753 MPI_VALIDATE_RET( A != NULL ); 01754 01755 p[0] = ( b < 0 ) ? -b : b; 01756 _B.s = ( b < 0 ) ? -1 : 1; 01757 _B.n = 1; 01758 _B.p = p; 01759 01760 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) ); 01761 } 01762 01763 /* 01764 * Modulo: R = A mod B 01765 */ 01766 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ) 01767 { 01768 int ret; 01769 MPI_VALIDATE_RET( R != NULL ); 01770 MPI_VALIDATE_RET( A != NULL ); 01771 MPI_VALIDATE_RET( B != NULL ); 01772 01773 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 ) 01774 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 01775 01776 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) ); 01777 01778 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 ) 01779 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) ); 01780 01781 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 ) 01782 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) ); 01783 01784 cleanup: 01785 01786 return( ret ); 01787 } 01788 01789 /* 01790 * Modulo: r = A mod b 01791 */ 01792 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 01793 { 01794 size_t i; 01795 mbedtls_mpi_uint x, y, z; 01796 MPI_VALIDATE_RET( r != NULL ); 01797 MPI_VALIDATE_RET( A != NULL ); 01798 01799 if( b == 0 ) 01800 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 01801 01802 if( b < 0 ) 01803 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 01804 01805 /* 01806 * handle trivial cases 01807 */ 01808 if( b == 1 ) 01809 { 01810 *r = 0; 01811 return( 0 ); 01812 } 01813 01814 if( b == 2 ) 01815 { 01816 *r = A->p [0] & 1; 01817 return( 0 ); 01818 } 01819 01820 /* 01821 * general case 01822 */ 01823 for( i = A->n , y = 0; i > 0; i-- ) 01824 { 01825 x = A->p [i - 1]; 01826 y = ( y << biH ) | ( x >> biH ); 01827 z = y / b; 01828 y -= z * b; 01829 01830 x <<= biH; 01831 y = ( y << biH ) | ( x >> biH ); 01832 z = y / b; 01833 y -= z * b; 01834 } 01835 01836 /* 01837 * If A is negative, then the current y represents a negative value. 01838 * Flipping it to the positive side. 01839 */ 01840 if( A->s < 0 && y != 0 ) 01841 y = b - y; 01842 01843 *r = y; 01844 01845 return( 0 ); 01846 } 01847 01848 /* 01849 * Fast Montgomery initialization (thanks to Tom St Denis) 01850 */ 01851 static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) 01852 { 01853 mbedtls_mpi_uint x, m0 = N->p [0]; 01854 unsigned int i; 01855 01856 x = m0; 01857 x += ( ( m0 + 2 ) & 4 ) << 1; 01858 01859 for( i = biL; i >= 8; i /= 2 ) 01860 x *= ( 2 - ( m0 * x ) ); 01861 01862 *mm = ~x + 1; 01863 } 01864 01865 /* 01866 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) 01867 */ 01868 static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, 01869 const mbedtls_mpi *T ) 01870 { 01871 size_t i, n, m; 01872 mbedtls_mpi_uint u0, u1, *d; 01873 01874 if( T->n < N->n + 1 || T->p == NULL ) 01875 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 01876 01877 memset( T->p , 0, T->n * ciL ); 01878 01879 d = T->p ; 01880 n = N->n ; 01881 m = ( B->n < n ) ? B->n : n; 01882 01883 for( i = 0; i < n; i++ ) 01884 { 01885 /* 01886 * T = (T + u0*B + u1*N) / 2^biL 01887 */ 01888 u0 = A->p [i]; 01889 u1 = ( d[0] + u0 * B->p [0] ) * mm; 01890 01891 mpi_mul_hlp( m, B->p , d, u0 ); 01892 mpi_mul_hlp( n, N->p , d, u1 ); 01893 01894 *d++ = u0; d[n + 1] = 0; 01895 } 01896 01897 memcpy( A->p , d, ( n + 1 ) * ciL ); 01898 01899 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 ) 01900 mpi_sub_hlp( n, N->p , A->p ); 01901 else 01902 /* prevent timing attacks */ 01903 mpi_sub_hlp( n, A->p , T->p ); 01904 01905 return( 0 ); 01906 } 01907 01908 /* 01909 * Montgomery reduction: A = A * R^-1 mod N 01910 */ 01911 static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, 01912 mbedtls_mpi_uint mm, const mbedtls_mpi *T ) 01913 { 01914 mbedtls_mpi_uint z = 1; 01915 mbedtls_mpi U; 01916 01917 U.n = U.s = (int) z; 01918 U.p = &z; 01919 01920 return( mpi_montmul( A, &U, N, mm, T ) ); 01921 } 01922 01923 /* 01924 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) 01925 */ 01926 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, 01927 const mbedtls_mpi *E, const mbedtls_mpi *N, 01928 mbedtls_mpi *_RR ) 01929 { 01930 int ret; 01931 size_t wbits, wsize, one = 1; 01932 size_t i, j, nblimbs; 01933 size_t bufsize, nbits; 01934 mbedtls_mpi_uint ei, mm, state; 01935 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos; 01936 int neg; 01937 01938 MPI_VALIDATE_RET( X != NULL ); 01939 MPI_VALIDATE_RET( A != NULL ); 01940 MPI_VALIDATE_RET( E != NULL ); 01941 MPI_VALIDATE_RET( N != NULL ); 01942 01943 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p [0] & 1 ) == 0 ) 01944 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 01945 01946 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 ) 01947 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 01948 01949 /* 01950 * Init temps and window size 01951 */ 01952 mpi_montg_init( &mm, N ); 01953 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T ); 01954 mbedtls_mpi_init( &Apos ); 01955 memset( W, 0, sizeof( W ) ); 01956 01957 i = mbedtls_mpi_bitlen( E ); 01958 01959 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : 01960 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; 01961 01962 #if( MBEDTLS_MPI_WINDOW_SIZE < 6 ) 01963 if( wsize > MBEDTLS_MPI_WINDOW_SIZE ) 01964 wsize = MBEDTLS_MPI_WINDOW_SIZE; 01965 #endif 01966 01967 j = N->n + 1; 01968 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 01969 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) ); 01970 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) ); 01971 01972 /* 01973 * Compensate for negative A (and correct at the end) 01974 */ 01975 neg = ( A->s == -1 ); 01976 if( neg ) 01977 { 01978 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) ); 01979 Apos.s = 1; 01980 A = &Apos; 01981 } 01982 01983 /* 01984 * If 1st call, pre-compute R^2 mod N 01985 */ 01986 if( _RR == NULL || _RR->p == NULL ) 01987 { 01988 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) ); 01989 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) ); 01990 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) ); 01991 01992 if( _RR != NULL ) 01993 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) ); 01994 } 01995 else 01996 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) ); 01997 01998 /* 01999 * W[1] = A * R^2 * R^-1 mod N = A * R mod N 02000 */ 02001 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 ) 02002 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) ); 02003 else 02004 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) ); 02005 02006 MBEDTLS_MPI_CHK( mpi_montmul( &W[1], &RR, N, mm, &T ) ); 02007 02008 /* 02009 * X = R^2 * R^-1 mod N = R mod N 02010 */ 02011 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) ); 02012 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) ); 02013 02014 if( wsize > 1 ) 02015 { 02016 /* 02017 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1) 02018 */ 02019 j = one << ( wsize - 1 ); 02020 02021 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) ); 02022 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) ); 02023 02024 for( i = 0; i < wsize - 1; i++ ) 02025 MBEDTLS_MPI_CHK( mpi_montmul( &W[j], &W[j], N, mm, &T ) ); 02026 02027 /* 02028 * W[i] = W[i - 1] * W[1] 02029 */ 02030 for( i = j + 1; i < ( one << wsize ); i++ ) 02031 { 02032 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) ); 02033 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) ); 02034 02035 MBEDTLS_MPI_CHK( mpi_montmul( &W[i], &W[1], N, mm, &T ) ); 02036 } 02037 } 02038 02039 nblimbs = E->n ; 02040 bufsize = 0; 02041 nbits = 0; 02042 wbits = 0; 02043 state = 0; 02044 02045 while( 1 ) 02046 { 02047 if( bufsize == 0 ) 02048 { 02049 if( nblimbs == 0 ) 02050 break; 02051 02052 nblimbs--; 02053 02054 bufsize = sizeof( mbedtls_mpi_uint ) << 3; 02055 } 02056 02057 bufsize--; 02058 02059 ei = (E->p [nblimbs] >> bufsize) & 1; 02060 02061 /* 02062 * skip leading 0s 02063 */ 02064 if( ei == 0 && state == 0 ) 02065 continue; 02066 02067 if( ei == 0 && state == 1 ) 02068 { 02069 /* 02070 * out of window, square X 02071 */ 02072 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); 02073 continue; 02074 } 02075 02076 /* 02077 * add ei to current window 02078 */ 02079 state = 2; 02080 02081 nbits++; 02082 wbits |= ( ei << ( wsize - nbits ) ); 02083 02084 if( nbits == wsize ) 02085 { 02086 /* 02087 * X = X^wsize R^-1 mod N 02088 */ 02089 for( i = 0; i < wsize; i++ ) 02090 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); 02091 02092 /* 02093 * X = X * W[wbits] R^-1 mod N 02094 */ 02095 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[wbits], N, mm, &T ) ); 02096 02097 state--; 02098 nbits = 0; 02099 wbits = 0; 02100 } 02101 } 02102 02103 /* 02104 * process the remaining bits 02105 */ 02106 for( i = 0; i < nbits; i++ ) 02107 { 02108 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); 02109 02110 wbits <<= 1; 02111 02112 if( ( wbits & ( one << wsize ) ) != 0 ) 02113 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[1], N, mm, &T ) ); 02114 } 02115 02116 /* 02117 * X = A^E * R * R^-1 mod N = A^E mod N 02118 */ 02119 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) ); 02120 02121 if( neg && E->n != 0 && ( E->p [0] & 1 ) != 0 ) 02122 { 02123 X->s = -1; 02124 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) ); 02125 } 02126 02127 cleanup: 02128 02129 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ ) 02130 mbedtls_mpi_free( &W[i] ); 02131 02132 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos ); 02133 02134 if( _RR == NULL || _RR->p == NULL ) 02135 mbedtls_mpi_free( &RR ); 02136 02137 return( ret ); 02138 } 02139 02140 /* 02141 * Greatest common divisor: G = gcd(A, B) (HAC 14.54) 02142 */ 02143 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ) 02144 { 02145 int ret; 02146 size_t lz, lzt; 02147 mbedtls_mpi TA, TB; 02148 02149 MPI_VALIDATE_RET( G != NULL ); 02150 MPI_VALIDATE_RET( A != NULL ); 02151 MPI_VALIDATE_RET( B != NULL ); 02152 02153 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB ); 02154 02155 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); 02156 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); 02157 02158 lz = mbedtls_mpi_lsb( &TA ); 02159 lzt = mbedtls_mpi_lsb( &TB ); 02160 02161 if( lzt < lz ) 02162 lz = lzt; 02163 02164 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) ); 02165 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) ); 02166 02167 TA.s = TB.s = 1; 02168 02169 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 ) 02170 { 02171 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) ); 02172 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) ); 02173 02174 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 ) 02175 { 02176 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) ); 02177 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) ); 02178 } 02179 else 02180 { 02181 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) ); 02182 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) ); 02183 } 02184 } 02185 02186 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) ); 02187 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) ); 02188 02189 cleanup: 02190 02191 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB ); 02192 02193 return( ret ); 02194 } 02195 02196 /* 02197 * Fill X with size bytes of random. 02198 * 02199 * Use a temporary bytes representation to make sure the result is the same 02200 * regardless of the platform endianness (useful when f_rng is actually 02201 * deterministic, eg for tests). 02202 */ 02203 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 02204 int (*f_rng)(void *, unsigned char *, size_t), 02205 void *p_rng ) 02206 { 02207 int ret; 02208 size_t const limbs = CHARS_TO_LIMBS( size ); 02209 size_t const overhead = ( limbs * ciL ) - size; 02210 unsigned char *Xp; 02211 02212 MPI_VALIDATE_RET( X != NULL ); 02213 MPI_VALIDATE_RET( f_rng != NULL ); 02214 02215 /* Ensure that target MPI has exactly the necessary number of limbs */ 02216 if( X->n != limbs ) 02217 { 02218 mbedtls_mpi_free( X ); 02219 mbedtls_mpi_init( X ); 02220 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) ); 02221 } 02222 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 02223 02224 Xp = (unsigned char*) X->p ; 02225 f_rng( p_rng, Xp + overhead, size ); 02226 02227 mpi_bigendian_to_host( X->p , limbs ); 02228 02229 cleanup: 02230 return( ret ); 02231 } 02232 02233 /* 02234 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) 02235 */ 02236 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ) 02237 { 02238 int ret; 02239 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; 02240 MPI_VALIDATE_RET( X != NULL ); 02241 MPI_VALIDATE_RET( A != NULL ); 02242 MPI_VALIDATE_RET( N != NULL ); 02243 02244 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ) 02245 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 02246 02247 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 ); 02248 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV ); 02249 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 ); 02250 02251 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) ); 02252 02253 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 ) 02254 { 02255 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 02256 goto cleanup; 02257 } 02258 02259 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) ); 02260 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) ); 02261 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) ); 02262 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) ); 02263 02264 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) ); 02265 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) ); 02266 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) ); 02267 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) ); 02268 02269 do 02270 { 02271 while( ( TU.p [0] & 1 ) == 0 ) 02272 { 02273 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) ); 02274 02275 if( ( U1.p [0] & 1 ) != 0 || ( U2.p [0] & 1 ) != 0 ) 02276 { 02277 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) ); 02278 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) ); 02279 } 02280 02281 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) ); 02282 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) ); 02283 } 02284 02285 while( ( TV.p [0] & 1 ) == 0 ) 02286 { 02287 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) ); 02288 02289 if( ( V1.p [0] & 1 ) != 0 || ( V2.p [0] & 1 ) != 0 ) 02290 { 02291 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) ); 02292 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) ); 02293 } 02294 02295 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) ); 02296 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) ); 02297 } 02298 02299 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 ) 02300 { 02301 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) ); 02302 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) ); 02303 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) ); 02304 } 02305 else 02306 { 02307 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) ); 02308 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) ); 02309 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) ); 02310 } 02311 } 02312 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 ); 02313 02314 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 ) 02315 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) ); 02316 02317 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 ) 02318 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) ); 02319 02320 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) ); 02321 02322 cleanup: 02323 02324 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 ); 02325 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV ); 02326 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 ); 02327 02328 return( ret ); 02329 } 02330 02331 #if defined(MBEDTLS_GENPRIME) 02332 02333 static const int small_prime[] = 02334 { 02335 3, 5, 7, 11, 13, 17, 19, 23, 02336 29, 31, 37, 41, 43, 47, 53, 59, 02337 61, 67, 71, 73, 79, 83, 89, 97, 02338 101, 103, 107, 109, 113, 127, 131, 137, 02339 139, 149, 151, 157, 163, 167, 173, 179, 02340 181, 191, 193, 197, 199, 211, 223, 227, 02341 229, 233, 239, 241, 251, 257, 263, 269, 02342 271, 277, 281, 283, 293, 307, 311, 313, 02343 317, 331, 337, 347, 349, 353, 359, 367, 02344 373, 379, 383, 389, 397, 401, 409, 419, 02345 421, 431, 433, 439, 443, 449, 457, 461, 02346 463, 467, 479, 487, 491, 499, 503, 509, 02347 521, 523, 541, 547, 557, 563, 569, 571, 02348 577, 587, 593, 599, 601, 607, 613, 617, 02349 619, 631, 641, 643, 647, 653, 659, 661, 02350 673, 677, 683, 691, 701, 709, 719, 727, 02351 733, 739, 743, 751, 757, 761, 769, 773, 02352 787, 797, 809, 811, 821, 823, 827, 829, 02353 839, 853, 857, 859, 863, 877, 881, 883, 02354 887, 907, 911, 919, 929, 937, 941, 947, 02355 953, 967, 971, 977, 983, 991, 997, -103 02356 }; 02357 02358 /* 02359 * Small divisors test (X must be positive) 02360 * 02361 * Return values: 02362 * 0: no small factor (possible prime, more tests needed) 02363 * 1: certain prime 02364 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 02365 * other negative: error 02366 */ 02367 static int mpi_check_small_factors( const mbedtls_mpi *X ) 02368 { 02369 int ret = 0; 02370 size_t i; 02371 mbedtls_mpi_uint r; 02372 02373 if( ( X->p [0] & 1 ) == 0 ) 02374 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 02375 02376 for( i = 0; small_prime[i] > 0; i++ ) 02377 { 02378 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 ) 02379 return( 1 ); 02380 02381 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) ); 02382 02383 if( r == 0 ) 02384 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 02385 } 02386 02387 cleanup: 02388 return( ret ); 02389 } 02390 02391 /* 02392 * Miller-Rabin pseudo-primality test (HAC 4.24) 02393 */ 02394 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds, 02395 int (*f_rng)(void *, unsigned char *, size_t), 02396 void *p_rng ) 02397 { 02398 int ret, count; 02399 size_t i, j, k, s; 02400 mbedtls_mpi W, R, T, A, RR; 02401 02402 MPI_VALIDATE_RET( X != NULL ); 02403 MPI_VALIDATE_RET( f_rng != NULL ); 02404 02405 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); 02406 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A ); 02407 mbedtls_mpi_init( &RR ); 02408 02409 /* 02410 * W = |X| - 1 02411 * R = W >> lsb( W ) 02412 */ 02413 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) ); 02414 s = mbedtls_mpi_lsb( &W ); 02415 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) ); 02416 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) ); 02417 02418 for( i = 0; i < rounds; i++ ) 02419 { 02420 /* 02421 * pick a random A, 1 < A < |X| - 1 02422 */ 02423 count = 0; 02424 do { 02425 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); 02426 02427 j = mbedtls_mpi_bitlen( &A ); 02428 k = mbedtls_mpi_bitlen( &W ); 02429 if (j > k) { 02430 A.p [A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1; 02431 } 02432 02433 if (count++ > 30) { 02434 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 02435 goto cleanup; 02436 } 02437 02438 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 || 02439 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 ); 02440 02441 /* 02442 * A = A^R mod |X| 02443 */ 02444 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) ); 02445 02446 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 || 02447 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 02448 continue; 02449 02450 j = 1; 02451 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ) 02452 { 02453 /* 02454 * A = A * A mod |X| 02455 */ 02456 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) ); 02457 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) ); 02458 02459 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 02460 break; 02461 02462 j++; 02463 } 02464 02465 /* 02466 * not prime if A != |X| - 1 or A == 1 02467 */ 02468 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 || 02469 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 02470 { 02471 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 02472 break; 02473 } 02474 } 02475 02476 cleanup: 02477 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); 02478 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A ); 02479 mbedtls_mpi_free( &RR ); 02480 02481 return( ret ); 02482 } 02483 02484 /* 02485 * Pseudo-primality test: small factors, then Miller-Rabin 02486 */ 02487 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds, 02488 int (*f_rng)(void *, unsigned char *, size_t), 02489 void *p_rng ) 02490 { 02491 int ret; 02492 mbedtls_mpi XX; 02493 MPI_VALIDATE_RET( X != NULL ); 02494 MPI_VALIDATE_RET( f_rng != NULL ); 02495 02496 XX.s = 1; 02497 XX.n = X->n ; 02498 XX.p = X->p ; 02499 02500 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 || 02501 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 ) 02502 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 02503 02504 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 ) 02505 return( 0 ); 02506 02507 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 ) 02508 { 02509 if( ret == 1 ) 02510 return( 0 ); 02511 02512 return( ret ); 02513 } 02514 02515 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) ); 02516 } 02517 02518 #if !defined(MBEDTLS_DEPRECATED_REMOVED) 02519 /* 02520 * Pseudo-primality test, error probability 2^-80 02521 */ 02522 int mbedtls_mpi_is_prime( const mbedtls_mpi *X, 02523 int (*f_rng)(void *, unsigned char *, size_t), 02524 void *p_rng ) 02525 { 02526 MPI_VALIDATE_RET( X != NULL ); 02527 MPI_VALIDATE_RET( f_rng != NULL ); 02528 02529 /* 02530 * In the past our key generation aimed for an error rate of at most 02531 * 2^-80. Since this function is deprecated, aim for the same certainty 02532 * here as well. 02533 */ 02534 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) ); 02535 } 02536 #endif 02537 02538 /* 02539 * Prime number generation 02540 * 02541 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must 02542 * be either 1024 bits or 1536 bits long, and flags must contain 02543 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. 02544 */ 02545 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags, 02546 int (*f_rng)(void *, unsigned char *, size_t), 02547 void *p_rng ) 02548 { 02549 #ifdef MBEDTLS_HAVE_INT64 02550 // ceil(2^63.5) 02551 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL 02552 #else 02553 // ceil(2^31.5) 02554 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U 02555 #endif 02556 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 02557 size_t k, n; 02558 int rounds; 02559 mbedtls_mpi_uint r; 02560 mbedtls_mpi Y; 02561 02562 MPI_VALIDATE_RET( X != NULL ); 02563 MPI_VALIDATE_RET( f_rng != NULL ); 02564 02565 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS ) 02566 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 02567 02568 mbedtls_mpi_init( &Y ); 02569 02570 n = BITS_TO_LIMBS( nbits ); 02571 02572 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 ) 02573 { 02574 /* 02575 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 02576 */ 02577 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 : 02578 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 : 02579 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 ); 02580 } 02581 else 02582 { 02583 /* 02584 * 2^-100 error probability, number of rounds computed based on HAC, 02585 * fact 4.48 02586 */ 02587 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 : 02588 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 : 02589 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 : 02590 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 ); 02591 } 02592 02593 while( 1 ) 02594 { 02595 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); 02596 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ 02597 if( X->p [n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue; 02598 02599 k = n * biL; 02600 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) ); 02601 X->p [0] |= 1; 02602 02603 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 ) 02604 { 02605 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng ); 02606 02607 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 02608 goto cleanup; 02609 } 02610 else 02611 { 02612 /* 02613 * An necessary condition for Y and X = 2Y + 1 to be prime 02614 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 02615 * Make sure it is satisfied, while keeping X = 3 mod 4 02616 */ 02617 02618 X->p [0] |= 2; 02619 02620 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) ); 02621 if( r == 0 ) 02622 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) ); 02623 else if( r == 1 ) 02624 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) ); 02625 02626 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 02627 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) ); 02628 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) ); 02629 02630 while( 1 ) 02631 { 02632 /* 02633 * First, check small factors for X and Y 02634 * before doing Miller-Rabin on any of them 02635 */ 02636 if( ( ret = mpi_check_small_factors( X ) ) == 0 && 02637 ( ret = mpi_check_small_factors( &Y ) ) == 0 && 02638 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) ) 02639 == 0 && 02640 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) ) 02641 == 0 ) 02642 goto cleanup; 02643 02644 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 02645 goto cleanup; 02646 02647 /* 02648 * Next candidates. We want to preserve Y = (X-1) / 2 and 02649 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 02650 * so up Y by 6 and X by 12. 02651 */ 02652 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) ); 02653 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) ); 02654 } 02655 } 02656 } 02657 02658 cleanup: 02659 02660 mbedtls_mpi_free( &Y ); 02661 02662 return( ret ); 02663 } 02664 02665 #endif /* MBEDTLS_GENPRIME */ 02666 02667 #if defined(MBEDTLS_SELF_TEST) 02668 02669 #define GCD_PAIR_COUNT 3 02670 02671 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 02672 { 02673 { 693, 609, 21 }, 02674 { 1764, 868, 28 }, 02675 { 768454923, 542167814, 1 } 02676 }; 02677 02678 /* 02679 * Checkup routine 02680 */ 02681 int mbedtls_mpi_self_test( int verbose ) 02682 { 02683 int ret, i; 02684 mbedtls_mpi A, E, N, X, Y, U, V; 02685 02686 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X ); 02687 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V ); 02688 02689 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16, 02690 "EFE021C2645FD1DC586E69184AF4A31E" \ 02691 "D5F53E93B5F123FA41680867BA110131" \ 02692 "944FE7952E2517337780CB0DB80E61AA" \ 02693 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) ); 02694 02695 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16, 02696 "B2E7EFD37075B9F03FF989C7C5051C20" \ 02697 "34D2A323810251127E7BF8625A4F49A5" \ 02698 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 02699 "5B5C25763222FEFCCFC38B832366C29E" ) ); 02700 02701 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16, 02702 "0066A198186C18C10B2F5ED9B522752A" \ 02703 "9830B69916E535C8F047518A889A43A5" \ 02704 "94B6BED27A168D31D4A52F88925AA8F5" ) ); 02705 02706 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) ); 02707 02708 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 02709 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 02710 "9E857EA95A03512E2BAE7391688D264A" \ 02711 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 02712 "8001B72E848A38CAE1C65F78E56ABDEF" \ 02713 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 02714 "ECF677152EF804370C1A305CAF3B5BF1" \ 02715 "30879B56C61DE584A0F53A2447A51E" ) ); 02716 02717 if( verbose != 0 ) 02718 mbedtls_printf( " MPI test #1 (mul_mpi): " ); 02719 02720 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 02721 { 02722 if( verbose != 0 ) 02723 mbedtls_printf( "failed\n" ); 02724 02725 ret = 1; 02726 goto cleanup; 02727 } 02728 02729 if( verbose != 0 ) 02730 mbedtls_printf( "passed\n" ); 02731 02732 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) ); 02733 02734 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 02735 "256567336059E52CAE22925474705F39A94" ) ); 02736 02737 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16, 02738 "6613F26162223DF488E9CD48CC132C7A" \ 02739 "0AC93C701B001B092E4E5B9F73BCD27B" \ 02740 "9EE50D0657C77F374E903CDFA4C642" ) ); 02741 02742 if( verbose != 0 ) 02743 mbedtls_printf( " MPI test #2 (div_mpi): " ); 02744 02745 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 || 02746 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 ) 02747 { 02748 if( verbose != 0 ) 02749 mbedtls_printf( "failed\n" ); 02750 02751 ret = 1; 02752 goto cleanup; 02753 } 02754 02755 if( verbose != 0 ) 02756 mbedtls_printf( "passed\n" ); 02757 02758 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) ); 02759 02760 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 02761 "36E139AEA55215609D2816998ED020BB" \ 02762 "BD96C37890F65171D948E9BC7CBAA4D9" \ 02763 "325D24D6A3C12710F10A09FA08AB87" ) ); 02764 02765 if( verbose != 0 ) 02766 mbedtls_printf( " MPI test #3 (exp_mod): " ); 02767 02768 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 02769 { 02770 if( verbose != 0 ) 02771 mbedtls_printf( "failed\n" ); 02772 02773 ret = 1; 02774 goto cleanup; 02775 } 02776 02777 if( verbose != 0 ) 02778 mbedtls_printf( "passed\n" ); 02779 02780 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) ); 02781 02782 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 02783 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 02784 "C3DBA76456363A10869622EAC2DD84EC" \ 02785 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) ); 02786 02787 if( verbose != 0 ) 02788 mbedtls_printf( " MPI test #4 (inv_mod): " ); 02789 02790 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 02791 { 02792 if( verbose != 0 ) 02793 mbedtls_printf( "failed\n" ); 02794 02795 ret = 1; 02796 goto cleanup; 02797 } 02798 02799 if( verbose != 0 ) 02800 mbedtls_printf( "passed\n" ); 02801 02802 if( verbose != 0 ) 02803 mbedtls_printf( " MPI test #5 (simple gcd): " ); 02804 02805 for( i = 0; i < GCD_PAIR_COUNT; i++ ) 02806 { 02807 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) ); 02808 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) ); 02809 02810 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) ); 02811 02812 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) 02813 { 02814 if( verbose != 0 ) 02815 mbedtls_printf( "failed at %d\n", i ); 02816 02817 ret = 1; 02818 goto cleanup; 02819 } 02820 } 02821 02822 if( verbose != 0 ) 02823 mbedtls_printf( "passed\n" ); 02824 02825 cleanup: 02826 02827 if( ret != 0 && verbose != 0 ) 02828 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 02829 02830 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X ); 02831 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V ); 02832 02833 if( verbose != 0 ) 02834 mbedtls_printf( "\n" ); 02835 02836 return( ret ); 02837 } 02838 02839 #endif /* MBEDTLS_SELF_TEST */ 02840 02841 #endif /* MBEDTLS_BIGNUM_C */
Generated on Tue Jul 12 2022 13:54:03 by
1.7.2