PolarSSL v1.1.4
bignum.c
Go to the documentation of this file.
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