Doug Anson
mbed TLS library
Dependents: HTTPClient-SSL WS_SERVER
Embed:
(wiki syntax)
Show/hide line numbers
bignum.c
00001 /* 00002 * Multi-precision integer library 00003 * 00004 * Copyright (C) 2006-2014, ARM Limited, All Rights Reserved 00005 * 00006 * This file is part of mbed TLS (https://tls.mbed.org) 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU General Public License as published by 00010 * the Free Software Foundation; either version 2 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * This program is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU General Public License along 00019 * with this program; if not, write to the Free Software Foundation, Inc., 00020 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00021 */ 00022 /* 00023 * This MPI implementation is based on: 00024 * 00025 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf 00026 * http://www.stillhq.com/extracted/gnupg-api/mpi/ 00027 * http://math.libtomcrypt.com/files/tommath.pdf 00028 */ 00029 00030 #if !defined(POLARSSL_CONFIG_FILE) 00031 #include "polarssl/config.h" 00032 #else 00033 #include POLARSSL_CONFIG_FILE 00034 #endif 00035 00036 #if defined(POLARSSL_BIGNUM_C) 00037 00038 #include "polarssl/bignum.h" 00039 #include "polarssl/bn_mul.h" 00040 00041 #include <string.h> 00042 00043 #if defined(POLARSSL_PLATFORM_C) 00044 #include "polarssl/platform.h" 00045 #else 00046 #include <stdio.h> 00047 #include <stdlib.h> 00048 #define polarssl_printf printf 00049 #define polarssl_malloc malloc 00050 #define polarssl_free free 00051 #endif 00052 00053 /* Implementation that should never be optimized out by the compiler */ 00054 static void polarssl_zeroize( void *v, size_t n ) { 00055 volatile unsigned char *p = v; while( n-- ) *p++ = 0; 00056 } 00057 00058 #define ciL (sizeof(t_uint)) /* chars in limb */ 00059 #define biL (ciL << 3) /* bits in limb */ 00060 #define biH (ciL << 2) /* half limb size */ 00061 00062 /* 00063 * Convert between bits/chars and number of limbs 00064 */ 00065 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL) 00066 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL) 00067 00068 /* 00069 * Initialize one MPI 00070 */ 00071 void mpi_init( mpi *X ) 00072 { 00073 if( X == NULL ) 00074 return; 00075 00076 X->s = 1; 00077 X->n = 0; 00078 X->p = NULL; 00079 } 00080 00081 /* 00082 * Unallocate one MPI 00083 */ 00084 void mpi_free( mpi *X ) 00085 { 00086 if( X == NULL ) 00087 return; 00088 00089 if( X->p != NULL ) 00090 { 00091 polarssl_zeroize( X->p , X->n * ciL ); 00092 polarssl_free( X->p ); 00093 } 00094 00095 X->s = 1; 00096 X->n = 0; 00097 X->p = NULL; 00098 } 00099 00100 /* 00101 * Enlarge to the specified number of limbs 00102 */ 00103 int mpi_grow( mpi *X, size_t nblimbs ) 00104 { 00105 t_uint *p; 00106 00107 if( nblimbs > POLARSSL_MPI_MAX_LIMBS ) 00108 return( POLARSSL_ERR_MPI_MALLOC_FAILED ); 00109 00110 if( X->n < nblimbs ) 00111 { 00112 if( ( p = polarssl_malloc( nblimbs * ciL ) ) == NULL ) 00113 return( POLARSSL_ERR_MPI_MALLOC_FAILED ); 00114 00115 memset( p, 0, nblimbs * ciL ); 00116 00117 if( X->p != NULL ) 00118 { 00119 memcpy( p, X->p , X->n * ciL ); 00120 polarssl_zeroize( X->p , X->n * ciL ); 00121 polarssl_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 mpi_shrink( mpi *X, size_t nblimbs ) 00136 { 00137 t_uint *p; 00138 size_t i; 00139 00140 /* Actually resize up in this case */ 00141 if( X->n <= nblimbs ) 00142 return( 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 = polarssl_malloc( i * ciL ) ) == NULL ) 00153 return( POLARSSL_ERR_MPI_MALLOC_FAILED ); 00154 00155 memset( p, 0, i * ciL ); 00156 00157 if( X->p != NULL ) 00158 { 00159 memcpy( p, X->p , i * ciL ); 00160 polarssl_zeroize( X->p , X->n * ciL ); 00161 polarssl_free( X->p ); 00162 } 00163 00164 X->n = i; 00165 X->p = p; 00166 00167 return( 0 ); 00168 } 00169 00170 /* 00171 * Copy the contents of Y into X 00172 */ 00173 int mpi_copy( mpi *X, const mpi *Y ) 00174 { 00175 int ret; 00176 size_t i; 00177 00178 if( X == Y ) 00179 return( 0 ); 00180 00181 if( Y->p == NULL ) 00182 { 00183 mpi_free( X ); 00184 return( 0 ); 00185 } 00186 00187 for( i = Y->n - 1; i > 0; i-- ) 00188 if( Y->p [i] != 0 ) 00189 break; 00190 i++; 00191 00192 X->s = Y->s ; 00193 00194 MPI_CHK( mpi_grow( X, i ) ); 00195 00196 memset( X->p , 0, X->n * ciL ); 00197 memcpy( X->p , Y->p , i * ciL ); 00198 00199 cleanup: 00200 00201 return( ret ); 00202 } 00203 00204 /* 00205 * Swap the contents of X and Y 00206 */ 00207 void mpi_swap( mpi *X, mpi *Y ) 00208 { 00209 mpi T; 00210 00211 memcpy( &T, X, sizeof( mpi ) ); 00212 memcpy( X, Y, sizeof( mpi ) ); 00213 memcpy( Y, &T, sizeof( mpi ) ); 00214 } 00215 00216 /* 00217 * Conditionally assign X = Y, without leaking information 00218 * about whether the assignment was made or not. 00219 * (Leaking information about the respective sizes of X and Y is ok however.) 00220 */ 00221 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign ) 00222 { 00223 int ret = 0; 00224 size_t i; 00225 00226 /* make sure assign is 0 or 1 in a time-constant manner */ 00227 assign = (assign | (unsigned char)-assign) >> 7; 00228 00229 MPI_CHK( mpi_grow( X, Y->n ) ); 00230 00231 X->s = X->s * ( 1 - assign ) + Y->s * assign; 00232 00233 for( i = 0; i < Y->n; i++ ) 00234 X->p [i] = X->p [i] * ( 1 - assign ) + Y->p [i] * assign; 00235 00236 for( ; i < X->n; i++ ) 00237 X->p [i] *= ( 1 - assign ); 00238 00239 cleanup: 00240 return( ret ); 00241 } 00242 00243 /* 00244 * Conditionally swap X and Y, without leaking information 00245 * about whether the swap was made or not. 00246 * Here it is not ok to simply swap the pointers, which whould lead to 00247 * different memory access patterns when X and Y are used afterwards. 00248 */ 00249 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char swap ) 00250 { 00251 int ret, s; 00252 size_t i; 00253 t_uint tmp; 00254 00255 if( X == Y ) 00256 return( 0 ); 00257 00258 /* make sure swap is 0 or 1 in a time-constant manner */ 00259 swap = (swap | (unsigned char)-swap) >> 7; 00260 00261 MPI_CHK( mpi_grow( X, Y->n ) ); 00262 MPI_CHK( mpi_grow( Y, X->n ) ); 00263 00264 s = X->s ; 00265 X->s = X->s * ( 1 - swap ) + Y->s * swap; 00266 Y->s = Y->s * ( 1 - swap ) + s * swap; 00267 00268 00269 for( i = 0; i < X->n ; i++ ) 00270 { 00271 tmp = X->p [i]; 00272 X->p [i] = X->p [i] * ( 1 - swap ) + Y->p [i] * swap; 00273 Y->p [i] = Y->p [i] * ( 1 - swap ) + tmp * swap; 00274 } 00275 00276 cleanup: 00277 return( ret ); 00278 } 00279 00280 /* 00281 * Set value from integer 00282 */ 00283 int mpi_lset( mpi *X, t_sint z ) 00284 { 00285 int ret; 00286 00287 MPI_CHK( mpi_grow( X, 1 ) ); 00288 memset( X->p , 0, X->n * ciL ); 00289 00290 X->p [0] = ( z < 0 ) ? -z : z; 00291 X->s = ( z < 0 ) ? -1 : 1; 00292 00293 cleanup: 00294 00295 return( ret ); 00296 } 00297 00298 /* 00299 * Get a specific bit 00300 */ 00301 int mpi_get_bit( const mpi *X, size_t pos ) 00302 { 00303 if( X->n * biL <= pos ) 00304 return( 0 ); 00305 00306 return( ( X->p [pos / biL] >> ( pos % biL ) ) & 0x01 ); 00307 } 00308 00309 /* 00310 * Set a bit to a specific value of 0 or 1 00311 */ 00312 int mpi_set_bit( mpi *X, size_t pos, unsigned char val ) 00313 { 00314 int ret = 0; 00315 size_t off = pos / biL; 00316 size_t idx = pos % biL; 00317 00318 if( val != 0 && val != 1 ) 00319 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 00320 00321 if( X->n * biL <= pos ) 00322 { 00323 if( val == 0 ) 00324 return( 0 ); 00325 00326 MPI_CHK( mpi_grow( X, off + 1 ) ); 00327 } 00328 00329 X->p [off] &= ~( (t_uint) 0x01 << idx ); 00330 X->p [off] |= (t_uint) val << idx; 00331 00332 cleanup: 00333 00334 return( ret ); 00335 } 00336 00337 /* 00338 * Return the number of least significant bits 00339 */ 00340 size_t mpi_lsb( const mpi *X ) 00341 { 00342 size_t i, j, count = 0; 00343 00344 for( i = 0; i < X->n ; i++ ) 00345 for( j = 0; j < biL; j++, count++ ) 00346 if( ( ( X->p [i] >> j ) & 1 ) != 0 ) 00347 return( count ); 00348 00349 return( 0 ); 00350 } 00351 00352 /* 00353 * Return the number of most significant bits 00354 */ 00355 size_t mpi_msb( const mpi *X ) 00356 { 00357 size_t i, j; 00358 00359 if( X->n == 0 ) 00360 return( 0 ); 00361 00362 for( i = X->n - 1; i > 0; i-- ) 00363 if( X->p [i] != 0 ) 00364 break; 00365 00366 for( j = biL; j > 0; j-- ) 00367 if( ( ( X->p [i] >> ( j - 1 ) ) & 1 ) != 0 ) 00368 break; 00369 00370 return( ( i * biL ) + j ); 00371 } 00372 00373 /* 00374 * Return the total size in bytes 00375 */ 00376 size_t mpi_size( const mpi *X ) 00377 { 00378 return( ( mpi_msb( X ) + 7 ) >> 3 ); 00379 } 00380 00381 /* 00382 * Convert an ASCII character to digit value 00383 */ 00384 static int mpi_get_digit( t_uint *d, int radix, char c ) 00385 { 00386 *d = 255; 00387 00388 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30; 00389 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37; 00390 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57; 00391 00392 if( *d >= (t_uint) radix ) 00393 return( POLARSSL_ERR_MPI_INVALID_CHARACTER ); 00394 00395 return( 0 ); 00396 } 00397 00398 /* 00399 * Import from an ASCII string 00400 */ 00401 int mpi_read_string( mpi *X, int radix, const char *s ) 00402 { 00403 int ret; 00404 size_t i, j, slen, n; 00405 t_uint d; 00406 mpi T; 00407 00408 if( radix < 2 || radix > 16 ) 00409 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 00410 00411 mpi_init( &T ); 00412 00413 slen = strlen( s ); 00414 00415 if( radix == 16 ) 00416 { 00417 n = BITS_TO_LIMBS( slen << 2 ); 00418 00419 MPI_CHK( mpi_grow( X, n ) ); 00420 MPI_CHK( mpi_lset( X, 0 ) ); 00421 00422 for( i = slen, j = 0; i > 0; i--, j++ ) 00423 { 00424 if( i == 1 && s[i - 1] == '-' ) 00425 { 00426 X->s = -1; 00427 break; 00428 } 00429 00430 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); 00431 X->p [j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 ); 00432 } 00433 } 00434 else 00435 { 00436 MPI_CHK( mpi_lset( X, 0 ) ); 00437 00438 for( i = 0; i < slen; i++ ) 00439 { 00440 if( i == 0 && s[i] == '-' ) 00441 { 00442 X->s = -1; 00443 continue; 00444 } 00445 00446 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); 00447 MPI_CHK( mpi_mul_int( &T, X, radix ) ); 00448 00449 if( X->s == 1 ) 00450 { 00451 MPI_CHK( mpi_add_int( X, &T, d ) ); 00452 } 00453 else 00454 { 00455 MPI_CHK( mpi_sub_int( X, &T, d ) ); 00456 } 00457 } 00458 } 00459 00460 cleanup: 00461 00462 mpi_free( &T ); 00463 00464 return( ret ); 00465 } 00466 00467 /* 00468 * Helper to write the digits high-order first 00469 */ 00470 static int mpi_write_hlp( mpi *X, int radix, char **p ) 00471 { 00472 int ret; 00473 t_uint r; 00474 00475 if( radix < 2 || radix > 16 ) 00476 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 00477 00478 MPI_CHK( mpi_mod_int( &r, X, radix ) ); 00479 MPI_CHK( mpi_div_int( X, NULL, X, radix ) ); 00480 00481 if( mpi_cmp_int( X, 0 ) != 0 ) 00482 MPI_CHK( mpi_write_hlp( X, radix, p ) ); 00483 00484 if( r < 10 ) 00485 *(*p)++ = (char)( r + 0x30 ); 00486 else 00487 *(*p)++ = (char)( r + 0x37 ); 00488 00489 cleanup: 00490 00491 return( ret ); 00492 } 00493 00494 /* 00495 * Export into an ASCII string 00496 */ 00497 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen ) 00498 { 00499 int ret = 0; 00500 size_t n; 00501 char *p; 00502 mpi T; 00503 00504 if( radix < 2 || radix > 16 ) 00505 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 00506 00507 n = mpi_msb( X ); 00508 if( radix >= 4 ) n >>= 1; 00509 if( radix >= 16 ) n >>= 1; 00510 n += 3; 00511 00512 if( *slen < n ) 00513 { 00514 *slen = n; 00515 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL ); 00516 } 00517 00518 p = s; 00519 mpi_init( &T ); 00520 00521 if( X->s == -1 ) 00522 *p++ = '-'; 00523 00524 if( radix == 16 ) 00525 { 00526 int c; 00527 size_t i, j, k; 00528 00529 for( i = X->n , k = 0; i > 0; i-- ) 00530 { 00531 for( j = ciL; j > 0; j-- ) 00532 { 00533 c = ( X->p [i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF; 00534 00535 if( c == 0 && k == 0 && ( i + j ) != 2 ) 00536 continue; 00537 00538 *(p++) = "0123456789ABCDEF" [c / 16]; 00539 *(p++) = "0123456789ABCDEF" [c % 16]; 00540 k = 1; 00541 } 00542 } 00543 } 00544 else 00545 { 00546 MPI_CHK( mpi_copy( &T, X ) ); 00547 00548 if( T.s == -1 ) 00549 T.s = 1; 00550 00551 MPI_CHK( mpi_write_hlp( &T, radix, &p ) ); 00552 } 00553 00554 *p++ = '\0'; 00555 *slen = p - s; 00556 00557 cleanup: 00558 00559 mpi_free( &T ); 00560 00561 return( ret ); 00562 } 00563 00564 #if defined(POLARSSL_FS_IO) 00565 /* 00566 * Read X from an opened file 00567 */ 00568 int mpi_read_file( mpi *X, int radix, FILE *fin ) 00569 { 00570 t_uint d; 00571 size_t slen; 00572 char *p; 00573 /* 00574 * Buffer should have space for (short) label and decimal formatted MPI, 00575 * newline characters and '\0' 00576 */ 00577 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ]; 00578 00579 memset( s, 0, sizeof( s ) ); 00580 if( fgets( s, sizeof( s ) - 1, fin ) == NULL ) 00581 return( POLARSSL_ERR_MPI_FILE_IO_ERROR ); 00582 00583 slen = strlen( s ); 00584 if( slen == sizeof( s ) - 2 ) 00585 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL ); 00586 00587 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; } 00588 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; } 00589 00590 p = s + slen; 00591 while( --p >= s ) 00592 if( mpi_get_digit( &d, radix, *p ) != 0 ) 00593 break; 00594 00595 return( mpi_read_string( X, radix, p + 1 ) ); 00596 } 00597 00598 /* 00599 * Write X into an opened file (or stdout if fout == NULL) 00600 */ 00601 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout ) 00602 { 00603 int ret; 00604 size_t n, slen, plen; 00605 /* 00606 * Buffer should have space for (short) label and decimal formatted MPI, 00607 * newline characters and '\0' 00608 */ 00609 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ]; 00610 00611 n = sizeof( s ); 00612 memset( s, 0, n ); 00613 n -= 2; 00614 00615 MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &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( POLARSSL_ERR_MPI_FILE_IO_ERROR ); 00629 } 00630 else 00631 polarssl_printf( "%s%s", p, s ); 00632 00633 cleanup: 00634 00635 return( ret ); 00636 } 00637 #endif /* POLARSSL_FS_IO */ 00638 00639 /* 00640 * Import X from unsigned binary data, big endian 00641 */ 00642 int mpi_read_binary( 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 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) ); 00652 MPI_CHK( mpi_lset( X, 0 ) ); 00653 00654 for( i = buflen, j = 0; i > n; i--, j++ ) 00655 X->p [j / ciL] |= ((t_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 mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen ) 00666 { 00667 size_t i, j, n; 00668 00669 n = mpi_size( X ); 00670 00671 if( buflen < n ) 00672 return( POLARSSL_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 mpi_shift_l( mpi *X, size_t count ) 00686 { 00687 int ret; 00688 size_t i, v0, t1; 00689 t_uint r0 = 0, r1; 00690 00691 v0 = count / (biL ); 00692 t1 = count & (biL - 1); 00693 00694 i = mpi_msb( X ) + count; 00695 00696 if( X->n * biL < i ) 00697 MPI_CHK( 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 mpi_shift_r( mpi *X, size_t count ) 00736 { 00737 size_t i, v0, v1; 00738 t_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 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 mpi_cmp_abs( const mpi *X, const 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 mpi_cmp_mpi( const mpi *X, const 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 mpi_cmp_int( const mpi *X, t_sint z ) 00842 { 00843 mpi Y; 00844 t_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( mpi_cmp_mpi( X, &Y ) ); 00852 } 00853 00854 /* 00855 * Unsigned addition: X = |A| + |B| (HAC 14.7) 00856 */ 00857 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B ) 00858 { 00859 int ret; 00860 size_t i, j; 00861 t_uint *o, *p, c; 00862 00863 if( X == B ) 00864 { 00865 const mpi *T = A; A = X; B = T; 00866 } 00867 00868 if( X != A ) 00869 MPI_CHK( 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 MPI_CHK( 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 MPI_CHK( 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 mpi subtraction 00908 */ 00909 static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d ) 00910 { 00911 size_t i; 00912 t_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 mpi_sub_abs( mpi *X, const mpi *A, const mpi *B ) 00931 { 00932 mpi TB; 00933 int ret; 00934 size_t n; 00935 00936 if( mpi_cmp_abs( A, B ) < 0 ) 00937 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE ); 00938 00939 mpi_init( &TB ); 00940 00941 if( X == B ) 00942 { 00943 MPI_CHK( mpi_copy( &TB, B ) ); 00944 B = &TB; 00945 } 00946 00947 if( X != A ) 00948 MPI_CHK( 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 mpi_free( &TB ); 00966 00967 return( ret ); 00968 } 00969 00970 /* 00971 * Signed addition: X = A + B 00972 */ 00973 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B ) 00974 { 00975 int ret, s = A->s ; 00976 00977 if( A->s * B->s < 0 ) 00978 { 00979 if( mpi_cmp_abs( A, B ) >= 0 ) 00980 { 00981 MPI_CHK( mpi_sub_abs( X, A, B ) ); 00982 X->s = s; 00983 } 00984 else 00985 { 00986 MPI_CHK( mpi_sub_abs( X, B, A ) ); 00987 X->s = -s; 00988 } 00989 } 00990 else 00991 { 00992 MPI_CHK( 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 mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B ) 01005 { 01006 int ret, s = A->s ; 01007 01008 if( A->s * B->s > 0 ) 01009 { 01010 if( mpi_cmp_abs( A, B ) >= 0 ) 01011 { 01012 MPI_CHK( mpi_sub_abs( X, A, B ) ); 01013 X->s = s; 01014 } 01015 else 01016 { 01017 MPI_CHK( mpi_sub_abs( X, B, A ) ); 01018 X->s = -s; 01019 } 01020 } 01021 else 01022 { 01023 MPI_CHK( 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 mpi_add_int( mpi *X, const mpi *A, t_sint b ) 01036 { 01037 mpi _B; 01038 t_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( mpi_add_mpi( X, A, &_B ) ); 01046 } 01047 01048 /* 01049 * Signed subtraction: X = A - b 01050 */ 01051 int mpi_sub_int( mpi *X, const mpi *A, t_sint b ) 01052 { 01053 mpi _B; 01054 t_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( mpi_sub_mpi( X, A, &_B ) ); 01062 } 01063 01064 /* 01065 * Helper for 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, t_uint *s, t_uint *d, t_uint b ) 01076 { 01077 t_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 mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B ) 01140 { 01141 int ret; 01142 size_t i, j; 01143 mpi TA, TB; 01144 01145 mpi_init( &TA ); mpi_init( &TB ); 01146 01147 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; } 01148 if( X == B ) { MPI_CHK( 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 MPI_CHK( mpi_grow( X, i + j ) ); 01159 MPI_CHK( 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 mpi_free( &TB ); mpi_free( &TA ); 01169 01170 return( ret ); 01171 } 01172 01173 /* 01174 * Baseline multiplication: X = A * b 01175 */ 01176 int mpi_mul_int( mpi *X, const mpi *A, t_sint b ) 01177 { 01178 mpi _B; 01179 t_uint p[1]; 01180 01181 _B.s = 1; 01182 _B.n = 1; 01183 _B.p = p; 01184 p[0] = b; 01185 01186 return( mpi_mul_mpi( X, A, &_B ) ); 01187 } 01188 01189 /* 01190 * Division by mpi: A = Q * B + R (HAC 14.20) 01191 */ 01192 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) 01193 { 01194 int ret; 01195 size_t i, n, t, k; 01196 mpi X, Y, Z, T1, T2; 01197 01198 if( mpi_cmp_int( B, 0 ) == 0 ) 01199 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO ); 01200 01201 mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z ); 01202 mpi_init( &T1 ); mpi_init( &T2 ); 01203 01204 if( mpi_cmp_abs( A, B ) < 0 ) 01205 { 01206 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) ); 01207 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) ); 01208 return( 0 ); 01209 } 01210 01211 MPI_CHK( mpi_copy( &X, A ) ); 01212 MPI_CHK( mpi_copy( &Y, B ) ); 01213 X.s = Y.s = 1; 01214 01215 MPI_CHK( mpi_grow( &Z, A->n + 2 ) ); 01216 MPI_CHK( mpi_lset( &Z, 0 ) ); 01217 MPI_CHK( mpi_grow( &T1, 2 ) ); 01218 MPI_CHK( mpi_grow( &T2, 3 ) ); 01219 01220 k = mpi_msb( &Y ) % biL; 01221 if( k < biL - 1 ) 01222 { 01223 k = biL - 1 - k; 01224 MPI_CHK( mpi_shift_l( &X, k ) ); 01225 MPI_CHK( mpi_shift_l( &Y, k ) ); 01226 } 01227 else k = 0; 01228 01229 n = X.n - 1; 01230 t = Y.n - 1; 01231 MPI_CHK( mpi_shift_l( &Y, biL * ( n - t ) ) ); 01232 01233 while( mpi_cmp_mpi( &X, &Y ) >= 0 ) 01234 { 01235 Z.p [n - t]++; 01236 MPI_CHK( mpi_sub_mpi( &X, &X, &Y ) ); 01237 } 01238 MPI_CHK( 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(POLARSSL_HAVE_UDBL) 01247 t_udbl r; 01248 01249 r = (t_udbl) X.p [i] << biL; 01250 r |= (t_udbl) X.p [i - 1]; 01251 r /= Y.p [t]; 01252 if( r > ( (t_udbl) 1 << biL ) - 1 ) 01253 r = ( (t_udbl) 1 << biL ) - 1; 01254 01255 Z.p [i - t - 1] = (t_uint) r; 01256 #else 01257 /* 01258 * __udiv_qrnnd_c, from gmp/longlong.h 01259 */ 01260 t_uint q0, q1, r0, r1; 01261 t_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 /* POLARSSL_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 MPI_CHK( mpi_lset( &T1, 0 ) ); 01305 T1.p [0] = ( t < 1 ) ? 0 : Y.p [t - 1]; 01306 T1.p [1] = Y.p [t]; 01307 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p [i - t - 1] ) ); 01308 01309 MPI_CHK( 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( mpi_cmp_mpi( &T1, &T2 ) > 0 ); 01315 01316 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p [i - t - 1] ) ); 01317 MPI_CHK( mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 01318 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) ); 01319 01320 if( mpi_cmp_int( &X, 0 ) < 0 ) 01321 { 01322 MPI_CHK( mpi_copy( &T1, &Y ) ); 01323 MPI_CHK( mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 01324 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) ); 01325 Z.p [i - t - 1]--; 01326 } 01327 } 01328 01329 if( Q != NULL ) 01330 { 01331 MPI_CHK( mpi_copy( Q, &Z ) ); 01332 Q->s = A->s * B->s ; 01333 } 01334 01335 if( R != NULL ) 01336 { 01337 MPI_CHK( mpi_shift_r( &X, k ) ); 01338 X.s = A->s ; 01339 MPI_CHK( mpi_copy( R, &X ) ); 01340 01341 if( mpi_cmp_int( R, 0 ) == 0 ) 01342 R->s = 1; 01343 } 01344 01345 cleanup: 01346 01347 mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z ); 01348 mpi_free( &T1 ); mpi_free( &T2 ); 01349 01350 return( ret ); 01351 } 01352 01353 /* 01354 * Division by int: A = Q * b + R 01355 */ 01356 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b ) 01357 { 01358 mpi _B; 01359 t_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( mpi_div_mpi( Q, R, A, &_B ) ); 01367 } 01368 01369 /* 01370 * Modulo: R = A mod B 01371 */ 01372 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B ) 01373 { 01374 int ret; 01375 01376 if( mpi_cmp_int( B, 0 ) < 0 ) 01377 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE ); 01378 01379 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) ); 01380 01381 while( mpi_cmp_int( R, 0 ) < 0 ) 01382 MPI_CHK( mpi_add_mpi( R, R, B ) ); 01383 01384 while( mpi_cmp_mpi( R, B ) >= 0 ) 01385 MPI_CHK( 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 mpi_mod_int( t_uint *r, const mpi *A, t_sint b ) 01396 { 01397 size_t i; 01398 t_uint x, y, z; 01399 01400 if( b == 0 ) 01401 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO ); 01402 01403 if( b < 0 ) 01404 return( POLARSSL_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( t_uint *mm, const mpi *N ) 01453 { 01454 t_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( mpi *A, const mpi *B, const mpi *N, t_uint mm, 01470 const mpi *T ) 01471 { 01472 size_t i, n, m; 01473 t_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( 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( mpi *A, const mpi *N, t_uint mm, const mpi *T ) 01508 { 01509 t_uint z = 1; 01510 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 mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, 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 t_uint ei, mm, state; 01528 mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos; 01529 int neg; 01530 01531 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p [0] & 1 ) == 0 ) 01532 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 01533 01534 if( mpi_cmp_int( E, 0 ) < 0 ) 01535 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 01536 01537 /* 01538 * Init temps and window size 01539 */ 01540 mpi_montg_init( &mm, N ); 01541 mpi_init( &RR ); mpi_init( &T ); 01542 mpi_init( &Apos ); 01543 memset( W, 0, sizeof( W ) ); 01544 01545 i = mpi_msb( E ); 01546 01547 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : 01548 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; 01549 01550 if( wsize > POLARSSL_MPI_WINDOW_SIZE ) 01551 wsize = POLARSSL_MPI_WINDOW_SIZE; 01552 01553 j = N->n + 1; 01554 MPI_CHK( mpi_grow( X, j ) ); 01555 MPI_CHK( mpi_grow( &W[1], j ) ); 01556 MPI_CHK( 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 MPI_CHK( 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 MPI_CHK( mpi_lset( &RR, 1 ) ); 01575 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) ); 01576 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) ); 01577 01578 if( _RR != NULL ) 01579 memcpy( _RR, &RR, sizeof( mpi ) ); 01580 } 01581 else 01582 memcpy( &RR, _RR, sizeof( mpi ) ); 01583 01584 /* 01585 * W[1] = A * R^2 * R^-1 mod N = A * R mod N 01586 */ 01587 if( mpi_cmp_mpi( A, N ) >= 0 ) 01588 MPI_CHK( mpi_mod_mpi( &W[1], A, N ) ); 01589 else 01590 MPI_CHK( 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 MPI_CHK( 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 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) ); 01608 MPI_CHK( 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 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) ); 01619 MPI_CHK( 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( t_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 MPI_CHK( mpi_add_mpi( X, N, X ) ); 01711 } 01712 01713 cleanup: 01714 01715 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ ) 01716 mpi_free( &W[i] ); 01717 01718 mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos ); 01719 01720 if( _RR == NULL || _RR->p == NULL ) 01721 mpi_free( &RR ); 01722 01723 return( ret ); 01724 } 01725 01726 /* 01727 * Greatest common divisor: G = gcd(A, B) (HAC 14.54) 01728 */ 01729 int mpi_gcd( mpi *G, const mpi *A, const mpi *B ) 01730 { 01731 int ret; 01732 size_t lz, lzt; 01733 mpi TG, TA, TB; 01734 01735 mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB ); 01736 01737 MPI_CHK( mpi_copy( &TA, A ) ); 01738 MPI_CHK( mpi_copy( &TB, B ) ); 01739 01740 lz = mpi_lsb( &TA ); 01741 lzt = mpi_lsb( &TB ); 01742 01743 if( lzt < lz ) 01744 lz = lzt; 01745 01746 MPI_CHK( mpi_shift_r( &TA, lz ) ); 01747 MPI_CHK( mpi_shift_r( &TB, lz ) ); 01748 01749 TA.s = TB.s = 1; 01750 01751 while( mpi_cmp_int( &TA, 0 ) != 0 ) 01752 { 01753 MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) ); 01754 MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) ); 01755 01756 if( mpi_cmp_mpi( &TA, &TB ) >= 0 ) 01757 { 01758 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) ); 01759 MPI_CHK( mpi_shift_r( &TA, 1 ) ); 01760 } 01761 else 01762 { 01763 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) ); 01764 MPI_CHK( mpi_shift_r( &TB, 1 ) ); 01765 } 01766 } 01767 01768 MPI_CHK( mpi_shift_l( &TB, lz ) ); 01769 MPI_CHK( mpi_copy( G, &TB ) ); 01770 01771 cleanup: 01772 01773 mpi_free( &TG ); mpi_free( &TA ); 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 mpi_fill_random( 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[POLARSSL_MPI_MAX_SIZE]; 01791 01792 if( size > POLARSSL_MPI_MAX_SIZE ) 01793 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 01794 01795 MPI_CHK( f_rng( p_rng, buf, size ) ); 01796 MPI_CHK( 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 mpi_inv_mod( mpi *X, const mpi *A, const mpi *N ) 01806 { 01807 int ret; 01808 mpi G, TA, TU, U1, U2, TB, TV, V1, V2; 01809 01810 if( mpi_cmp_int( N, 0 ) <= 0 ) 01811 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 01812 01813 mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 ); 01814 mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV ); 01815 mpi_init( &V1 ); mpi_init( &V2 ); 01816 01817 MPI_CHK( mpi_gcd( &G, A, N ) ); 01818 01819 if( mpi_cmp_int( &G, 1 ) != 0 ) 01820 { 01821 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE; 01822 goto cleanup; 01823 } 01824 01825 MPI_CHK( mpi_mod_mpi( &TA, A, N ) ); 01826 MPI_CHK( mpi_copy( &TU, &TA ) ); 01827 MPI_CHK( mpi_copy( &TB, N ) ); 01828 MPI_CHK( mpi_copy( &TV, N ) ); 01829 01830 MPI_CHK( mpi_lset( &U1, 1 ) ); 01831 MPI_CHK( mpi_lset( &U2, 0 ) ); 01832 MPI_CHK( mpi_lset( &V1, 0 ) ); 01833 MPI_CHK( mpi_lset( &V2, 1 ) ); 01834 01835 do 01836 { 01837 while( ( TU.p [0] & 1 ) == 0 ) 01838 { 01839 MPI_CHK( mpi_shift_r( &TU, 1 ) ); 01840 01841 if( ( U1.p [0] & 1 ) != 0 || ( U2.p [0] & 1 ) != 0 ) 01842 { 01843 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) ); 01844 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) ); 01845 } 01846 01847 MPI_CHK( mpi_shift_r( &U1, 1 ) ); 01848 MPI_CHK( mpi_shift_r( &U2, 1 ) ); 01849 } 01850 01851 while( ( TV.p [0] & 1 ) == 0 ) 01852 { 01853 MPI_CHK( mpi_shift_r( &TV, 1 ) ); 01854 01855 if( ( V1.p [0] & 1 ) != 0 || ( V2.p [0] & 1 ) != 0 ) 01856 { 01857 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) ); 01858 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) ); 01859 } 01860 01861 MPI_CHK( mpi_shift_r( &V1, 1 ) ); 01862 MPI_CHK( mpi_shift_r( &V2, 1 ) ); 01863 } 01864 01865 if( mpi_cmp_mpi( &TU, &TV ) >= 0 ) 01866 { 01867 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) ); 01868 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) ); 01869 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) ); 01870 } 01871 else 01872 { 01873 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) ); 01874 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) ); 01875 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) ); 01876 } 01877 } 01878 while( mpi_cmp_int( &TU, 0 ) != 0 ); 01879 01880 while( mpi_cmp_int( &V1, 0 ) < 0 ) 01881 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) ); 01882 01883 while( mpi_cmp_mpi( &V1, N ) >= 0 ) 01884 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) ); 01885 01886 MPI_CHK( mpi_copy( X, &V1 ) ); 01887 01888 cleanup: 01889 01890 mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 ); 01891 mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV ); 01892 mpi_free( &V1 ); mpi_free( &V2 ); 01893 01894 return( ret ); 01895 } 01896 01897 #if defined(POLARSSL_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 * POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 01931 * other negative: error 01932 */ 01933 static int mpi_check_small_factors( const mpi *X ) 01934 { 01935 int ret = 0; 01936 size_t i; 01937 t_uint r; 01938 01939 if( ( X->p [0] & 1 ) == 0 ) 01940 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE ); 01941 01942 for( i = 0; small_prime[i] > 0; i++ ) 01943 { 01944 if( mpi_cmp_int( X, small_prime[i] ) <= 0 ) 01945 return( 1 ); 01946 01947 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) ); 01948 01949 if( r == 0 ) 01950 return( POLARSSL_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 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 mpi W, R, T, A, RR; 01967 01968 mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A ); 01969 mpi_init( &RR ); 01970 01971 /* 01972 * W = |X| - 1 01973 * R = W >> lsb( W ) 01974 */ 01975 MPI_CHK( mpi_sub_int( &W, X, 1 ) ); 01976 s = mpi_lsb( &W ); 01977 MPI_CHK( mpi_copy( &R, &W ) ); 01978 MPI_CHK( mpi_shift_r( &R, s ) ); 01979 01980 i = mpi_msb( 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 01994 count = 0; 01995 do { 01996 MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); 01997 01998 j = mpi_msb( &A ); 01999 k = mpi_msb( &W ); 02000 if (j > k) { 02001 MPI_CHK( mpi_shift_r( &A, j - k ) ); 02002 } 02003 02004 if (count++ > 30) { 02005 return POLARSSL_ERR_MPI_NOT_ACCEPTABLE; 02006 } 02007 02008 } while ( (mpi_cmp_mpi( &A, &W ) >= 0) || 02009 (mpi_cmp_int( &A, 1 ) <= 0) ); 02010 02011 /* 02012 * A = A^R mod |X| 02013 */ 02014 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) ); 02015 02016 if( mpi_cmp_mpi( &A, &W ) == 0 || 02017 mpi_cmp_int( &A, 1 ) == 0 ) 02018 continue; 02019 02020 j = 1; 02021 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 ) 02022 { 02023 /* 02024 * A = A * A mod |X| 02025 */ 02026 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) ); 02027 MPI_CHK( mpi_mod_mpi( &A, &T, X ) ); 02028 02029 if( mpi_cmp_int( &A, 1 ) == 0 ) 02030 break; 02031 02032 j++; 02033 } 02034 02035 /* 02036 * not prime if A != |X| - 1 or A == 1 02037 */ 02038 if( mpi_cmp_mpi( &A, &W ) != 0 || 02039 mpi_cmp_int( &A, 1 ) == 0 ) 02040 { 02041 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE; 02042 break; 02043 } 02044 } 02045 02046 cleanup: 02047 mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A ); 02048 mpi_free( &RR ); 02049 02050 return( ret ); 02051 } 02052 02053 /* 02054 * Pseudo-primality test: small factors, then Miller-Rabin 02055 */ 02056 int mpi_is_prime( mpi *X, 02057 int (*f_rng)(void *, unsigned char *, size_t), 02058 void *p_rng ) 02059 { 02060 int ret; 02061 mpi XX; 02062 02063 XX.s = 1; 02064 XX.n = X->n ; 02065 XX.p = X->p ; 02066 02067 if( mpi_cmp_int( &XX, 0 ) == 0 || 02068 mpi_cmp_int( &XX, 1 ) == 0 ) 02069 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE ); 02070 02071 if( mpi_cmp_int( &XX, 2 ) == 0 ) 02072 return( 0 ); 02073 02074 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 ) 02075 { 02076 if( ret == 1 ) 02077 return( 0 ); 02078 02079 return( ret ); 02080 } 02081 02082 return( mpi_miller_rabin( &XX, f_rng, p_rng ) ); 02083 } 02084 02085 /* 02086 * Prime number generation 02087 */ 02088 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag, 02089 int (*f_rng)(void *, unsigned char *, size_t), 02090 void *p_rng ) 02091 { 02092 int ret; 02093 size_t k, n; 02094 t_uint r; 02095 mpi Y; 02096 02097 if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS ) 02098 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); 02099 02100 mpi_init( &Y ); 02101 02102 n = BITS_TO_LIMBS( nbits ); 02103 02104 MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); 02105 02106 k = mpi_msb( X ); 02107 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits + 1 ) ); 02108 02109 mpi_set_bit( X, nbits-1, 1 ); 02110 02111 X->p [0] |= 1; 02112 02113 if( dh_flag == 0 ) 02114 { 02115 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 ) 02116 { 02117 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE ) 02118 goto cleanup; 02119 02120 MPI_CHK( mpi_add_int( X, X, 2 ) ); 02121 } 02122 } 02123 else 02124 { 02125 /* 02126 * An necessary condition for Y and X = 2Y + 1 to be prime 02127 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 02128 * Make sure it is satisfied, while keeping X = 3 mod 4 02129 */ 02130 02131 X->p [0] |= 2; 02132 02133 MPI_CHK( mpi_mod_int( &r, X, 3 ) ); 02134 if( r == 0 ) 02135 MPI_CHK( mpi_add_int( X, X, 8 ) ); 02136 else if( r == 1 ) 02137 MPI_CHK( mpi_add_int( X, X, 4 ) ); 02138 02139 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 02140 MPI_CHK( mpi_copy( &Y, X ) ); 02141 MPI_CHK( mpi_shift_r( &Y, 1 ) ); 02142 02143 while( 1 ) 02144 { 02145 /* 02146 * First, check small factors for X and Y 02147 * before doing Miller-Rabin on any of them 02148 */ 02149 if( ( ret = mpi_check_small_factors( X ) ) == 0 && 02150 ( ret = mpi_check_small_factors( &Y ) ) == 0 && 02151 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 && 02152 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 ) 02153 { 02154 break; 02155 } 02156 02157 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE ) 02158 goto cleanup; 02159 02160 /* 02161 * Next candidates. We want to preserve Y = (X-1) / 2 and 02162 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 02163 * so up Y by 6 and X by 12. 02164 */ 02165 MPI_CHK( mpi_add_int( X, X, 12 ) ); 02166 MPI_CHK( mpi_add_int( &Y, &Y, 6 ) ); 02167 } 02168 } 02169 02170 cleanup: 02171 02172 mpi_free( &Y ); 02173 02174 return( ret ); 02175 } 02176 02177 #endif /* POLARSSL_GENPRIME */ 02178 02179 #if defined(POLARSSL_SELF_TEST) 02180 02181 #define GCD_PAIR_COUNT 3 02182 02183 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 02184 { 02185 { 693, 609, 21 }, 02186 { 1764, 868, 28 }, 02187 { 768454923, 542167814, 1 } 02188 }; 02189 02190 /* 02191 * Checkup routine 02192 */ 02193 int mpi_self_test( int verbose ) 02194 { 02195 int ret, i; 02196 mpi A, E, N, X, Y, U, V; 02197 02198 mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X ); 02199 mpi_init( &Y ); mpi_init( &U ); mpi_init( &V ); 02200 02201 MPI_CHK( mpi_read_string( &A, 16, 02202 "EFE021C2645FD1DC586E69184AF4A31E" \ 02203 "D5F53E93B5F123FA41680867BA110131" \ 02204 "944FE7952E2517337780CB0DB80E61AA" \ 02205 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) ); 02206 02207 MPI_CHK( mpi_read_string( &E, 16, 02208 "B2E7EFD37075B9F03FF989C7C5051C20" \ 02209 "34D2A323810251127E7BF8625A4F49A5" \ 02210 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 02211 "5B5C25763222FEFCCFC38B832366C29E" ) ); 02212 02213 MPI_CHK( mpi_read_string( &N, 16, 02214 "0066A198186C18C10B2F5ED9B522752A" \ 02215 "9830B69916E535C8F047518A889A43A5" \ 02216 "94B6BED27A168D31D4A52F88925AA8F5" ) ); 02217 02218 MPI_CHK( mpi_mul_mpi( &X, &A, &N ) ); 02219 02220 MPI_CHK( mpi_read_string( &U, 16, 02221 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 02222 "9E857EA95A03512E2BAE7391688D264A" \ 02223 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 02224 "8001B72E848A38CAE1C65F78E56ABDEF" \ 02225 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 02226 "ECF677152EF804370C1A305CAF3B5BF1" \ 02227 "30879B56C61DE584A0F53A2447A51E" ) ); 02228 02229 if( verbose != 0 ) 02230 polarssl_printf( " MPI test #1 (mul_mpi): " ); 02231 02232 if( mpi_cmp_mpi( &X, &U ) != 0 ) 02233 { 02234 if( verbose != 0 ) 02235 polarssl_printf( "failed\n" ); 02236 02237 ret = 1; 02238 goto cleanup; 02239 } 02240 02241 if( verbose != 0 ) 02242 polarssl_printf( "passed\n" ); 02243 02244 MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) ); 02245 02246 MPI_CHK( mpi_read_string( &U, 16, 02247 "256567336059E52CAE22925474705F39A94" ) ); 02248 02249 MPI_CHK( mpi_read_string( &V, 16, 02250 "6613F26162223DF488E9CD48CC132C7A" \ 02251 "0AC93C701B001B092E4E5B9F73BCD27B" \ 02252 "9EE50D0657C77F374E903CDFA4C642" ) ); 02253 02254 if( verbose != 0 ) 02255 polarssl_printf( " MPI test #2 (div_mpi): " ); 02256 02257 if( mpi_cmp_mpi( &X, &U ) != 0 || 02258 mpi_cmp_mpi( &Y, &V ) != 0 ) 02259 { 02260 if( verbose != 0 ) 02261 polarssl_printf( "failed\n" ); 02262 02263 ret = 1; 02264 goto cleanup; 02265 } 02266 02267 if( verbose != 0 ) 02268 polarssl_printf( "passed\n" ); 02269 02270 MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) ); 02271 02272 MPI_CHK( mpi_read_string( &U, 16, 02273 "36E139AEA55215609D2816998ED020BB" \ 02274 "BD96C37890F65171D948E9BC7CBAA4D9" \ 02275 "325D24D6A3C12710F10A09FA08AB87" ) ); 02276 02277 if( verbose != 0 ) 02278 polarssl_printf( " MPI test #3 (exp_mod): " ); 02279 02280 if( mpi_cmp_mpi( &X, &U ) != 0 ) 02281 { 02282 if( verbose != 0 ) 02283 polarssl_printf( "failed\n" ); 02284 02285 ret = 1; 02286 goto cleanup; 02287 } 02288 02289 if( verbose != 0 ) 02290 polarssl_printf( "passed\n" ); 02291 02292 MPI_CHK( mpi_inv_mod( &X, &A, &N ) ); 02293 02294 MPI_CHK( mpi_read_string( &U, 16, 02295 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 02296 "C3DBA76456363A10869622EAC2DD84EC" \ 02297 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) ); 02298 02299 if( verbose != 0 ) 02300 polarssl_printf( " MPI test #4 (inv_mod): " ); 02301 02302 if( mpi_cmp_mpi( &X, &U ) != 0 ) 02303 { 02304 if( verbose != 0 ) 02305 polarssl_printf( "failed\n" ); 02306 02307 ret = 1; 02308 goto cleanup; 02309 } 02310 02311 if( verbose != 0 ) 02312 polarssl_printf( "passed\n" ); 02313 02314 if( verbose != 0 ) 02315 polarssl_printf( " MPI test #5 (simple gcd): " ); 02316 02317 for( i = 0; i < GCD_PAIR_COUNT; i++ ) 02318 { 02319 MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) ); 02320 MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) ); 02321 02322 MPI_CHK( mpi_gcd( &A, &X, &Y ) ); 02323 02324 if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) 02325 { 02326 if( verbose != 0 ) 02327 polarssl_printf( "failed at %d\n", i ); 02328 02329 ret = 1; 02330 goto cleanup; 02331 } 02332 } 02333 02334 if( verbose != 0 ) 02335 polarssl_printf( "passed\n" ); 02336 02337 cleanup: 02338 02339 if( ret != 0 && verbose != 0 ) 02340 polarssl_printf( "Unexpected error, return code = %08X\n", ret ); 02341 02342 mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X ); 02343 mpi_free( &Y ); mpi_free( &U ); mpi_free( &V ); 02344 02345 if( verbose != 0 ) 02346 polarssl_printf( "\n" ); 02347 02348 return( ret ); 02349 } 02350 02351 #endif /* POLARSSL_SELF_TEST */ 02352 02353 #endif /* POLARSSL_BIGNUM_C */ 02354
Generated on Tue Jul 12 2022 13:50:36 by
1.7.2