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