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