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