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