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