bignum.c

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