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