From eabcef995c322e2e89f3e41d1c5d99149798fc95 Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka Date: Tue, 19 Mar 2013 14:03:59 +0900 Subject: [PATCH] import PolarSSL 1.2.6's bignum --- polarssl/include/polarssl/bignum.h | 306 +++++++++++---- polarssl/library/bignum.c | 602 ++++++++++++++++------------- 2 files changed, 571 insertions(+), 337 deletions(-) diff --git a/polarssl/include/polarssl/bignum.h b/polarssl/include/polarssl/bignum.h index 6070332..e02db3f 100644 --- a/polarssl/include/polarssl/bignum.h +++ b/polarssl/include/polarssl/bignum.h @@ -1,6 +1,8 @@ /** * \file bignum.h * + * \brief Multi-precision integer library + * * Copyright (C) 2006-2010, Brainspark B.V. * * This file is part of PolarSSL (http://www.polarssl.org) @@ -26,44 +28,131 @@ #define POLARSSL_BIGNUM_H #include +#include + +#include "config.h" + +#ifdef _MSC_VER +#include +#if (_MSC_VER <= 1200) +typedef signed short int16_t; +typedef unsigned short uint16_t; +#else +typedef INT16 int16_t; +typedef UINT16 uint16_t; +#endif +typedef INT32 int32_t; +typedef INT64 int64_t; +typedef UINT32 uint32_t; +typedef UINT64 uint64_t; +#else +#include +#endif -#define POLARSSL_ERR_MPI_FILE_IO_ERROR 0x0002 -#define POLARSSL_ERR_MPI_BAD_INPUT_DATA 0x0004 -#define POLARSSL_ERR_MPI_INVALID_CHARACTER 0x0006 -#define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL 0x0008 -#define POLARSSL_ERR_MPI_NEGATIVE_VALUE 0x000A -#define POLARSSL_ERR_MPI_DIVISION_BY_ZERO 0x000C -#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE 0x000E +#define POLARSSL_ERR_MPI_FILE_IO_ERROR -0x0002 /**< An error occurred while reading from or writing to a file. */ +#define POLARSSL_ERR_MPI_BAD_INPUT_DATA -0x0004 /**< Bad input parameters to function. */ +#define POLARSSL_ERR_MPI_INVALID_CHARACTER -0x0006 /**< There is an invalid character in the digit string. */ +#define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL -0x0008 /**< The buffer is too small to write to. */ +#define POLARSSL_ERR_MPI_NEGATIVE_VALUE -0x000A /**< The input arguments are negative or result in illegal output. */ +#define POLARSSL_ERR_MPI_DIVISION_BY_ZERO -0x000C /**< The input argument for division is zero, which is not allowed. */ +#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE -0x000E /**< The input arguments are not acceptable. */ +#define POLARSSL_ERR_MPI_MALLOC_FAILED -0x0010 /**< Memory allocation failed. */ #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup +/* + * Maximum size MPIs are allowed to grow to in number of limbs. + */ +#define POLARSSL_MPI_MAX_LIMBS 10000 + +/* + * Maximum window size used for modular exponentiation. Default: 6 + * Minimum value: 1. Maximum value: 6. + * + * Result is an array of ( 2 << POLARSSL_MPI_WINDOW_SIZE ) MPIs used + * for the sliding window calculation. (So 64 by default) + * + * Reduction in size, reduces speed. + */ +#define POLARSSL_MPI_WINDOW_SIZE 6 /**< Maximum windows size used. */ + +/* + * Maximum size of MPIs allowed in bits and bytes for user-MPIs. + * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits ) + * + * Note: Calculations can results temporarily in larger MPIs. So the number + * of limbs required (POLARSSL_MPI_MAX_LIMBS) is higher. + */ +#define POLARSSL_MPI_MAX_SIZE 512 /**< Maximum number of bytes for usable MPIs. */ +#define POLARSSL_MPI_MAX_BITS ( 8 * POLARSSL_MPI_MAX_SIZE ) /**< Maximum number of bits for usable MPIs. */ + +/* + * When reading from files with mpi_read_file() and writing to files with + * mpi_write_file() the buffer should have space + * for a (short) label, the MPI (in the provided radix), the newline + * characters and the '\0'. + * + * By default we assume at least a 10 char label, a minimum radix of 10 + * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars). + * Autosized at compile time for at least a 10 char label, a minimum radix + * of 10 (decimal) for a number of POLARSSL_MPI_MAX_BITS size. + * + * This used to be statically sized to 1250 for a maximum of 4096 bit + * numbers (1234 decimal chars). + * + * Calculate using the formula: + * POLARSSL_MPI_RW_BUFFER_SIZE = ceil(POLARSSL_MPI_MAX_BITS / ln(10) * ln(2)) + + * LabelSize + 6 + */ +#define POLARSSL_MPI_MAX_BITS_SCALE100 ( 100 * POLARSSL_MPI_MAX_BITS ) +#define LN_2_DIV_LN_10_SCALE100 332 +#define POLARSSL_MPI_RW_BUFFER_SIZE ( ((POLARSSL_MPI_MAX_BITS_SCALE100 + LN_2_DIV_LN_10_SCALE100 - 1) / LN_2_DIV_LN_10_SCALE100) + 10 + 6 ) + /* * Define the base integer type, architecture-wise */ #if defined(POLARSSL_HAVE_INT8) -typedef unsigned char t_int; -typedef unsigned short t_dbl; +typedef signed char t_sint; +typedef unsigned char t_uint; +typedef uint16_t t_udbl; +#define POLARSSL_HAVE_UDBL #else #if defined(POLARSSL_HAVE_INT16) -typedef unsigned short t_int; -typedef unsigned long t_dbl; +typedef int16_t t_sint; +typedef uint16_t t_uint; +typedef uint32_t t_udbl; +#define POLARSSL_HAVE_UDBL #else - typedef unsigned long t_int; - #if defined(_MSC_VER) && defined(_M_IX86) - typedef unsigned __int64 t_dbl; + #if ( defined(_MSC_VER) && defined(_M_AMD64) ) + typedef int64_t t_sint; + typedef uint64_t t_uint; #else - #if defined(__amd64__) || defined(__x86_64__) || \ - defined(__ppc64__) || defined(__powerpc64__) || \ - defined(__ia64__) || defined(__alpha__) - typedef unsigned int t_dbl __attribute__((mode(TI))); + #if ( defined(__GNUC__) && ( \ + defined(__amd64__) || defined(__x86_64__) || \ + defined(__ppc64__) || defined(__powerpc64__) || \ + defined(__ia64__) || defined(__alpha__) || \ + (defined(__sparc__) && defined(__arch64__)) || \ + defined(__s390x__) ) ) + typedef int64_t t_sint; + typedef uint64_t t_uint; + typedef unsigned int t_udbl __attribute__((mode(TI))); + #define POLARSSL_HAVE_UDBL #else - #if defined(POLARSSL_HAVE_LONGLONG) - typedef unsigned long long t_dbl; - #endif + typedef int32_t t_sint; + typedef uint32_t t_uint; + #if ( defined(_MSC_VER) && defined(_M_IX86) ) + typedef uint64_t t_udbl; + #define POLARSSL_HAVE_UDBL + #else + #if defined( POLARSSL_HAVE_LONGLONG ) + typedef unsigned long long t_udbl; + #define POLARSSL_HAVE_UDBL + #endif + #endif #endif #endif -#endif -#endif +#endif /* POLARSSL_HAVE_INT16 */ +#endif /* POLARSSL_HAVE_INT8 */ /** * \brief MPI structure @@ -71,8 +160,8 @@ typedef unsigned long t_dbl; typedef struct { int s; /*!< integer sign */ - int n; /*!< total # of limbs */ - t_int *p; /*!< pointer to limbs */ + size_t n; /*!< total # of limbs */ + t_uint *p; /*!< pointer to limbs */ } mpi; @@ -81,14 +170,18 @@ extern "C" { #endif /** - * \brief Initialize one or more mpi + * \brief Initialize one MPI + * + * \param X One MPI to initialize. */ -void mpi_init( mpi *X, ... ); +void mpi_init( mpi *X ); /** - * \brief Unallocate one or more mpi + * \brief Unallocate one MPI + * + * \param X One MPI to unallocate. */ -void mpi_free( mpi *X, ... ); +void mpi_free( mpi *X ); /** * \brief Enlarge to the specified number of limbs @@ -97,9 +190,9 @@ void mpi_free( mpi *X, ... ); * \param nblimbs The target number of limbs * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_grow( mpi *X, int nblimbs ); +int mpi_grow( mpi *X, size_t nblimbs ); /** * \brief Copy the contents of Y into X @@ -108,7 +201,7 @@ int mpi_grow( mpi *X, int nblimbs ); * \param Y Source MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_copy( mpi *X, const mpi *Y ); @@ -127,30 +220,62 @@ void mpi_swap( mpi *X, mpi *Y ); * \param z Value to use * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed + */ +int mpi_lset( mpi *X, t_sint z ); + +/** + * \brief Get a specific bit from X + * + * \param X MPI to use + * \param pos Zero-based index of the bit in X + * + * \return Either a 0 or a 1 */ -int mpi_lset( mpi *X, int z ); +int mpi_get_bit( const mpi *X, size_t pos ); /** - * \brief Return the number of least significant bits + * \brief Set a bit of X to a specific value of 0 or 1 + * + * \note Will grow X if necessary to set a bit to 1 in a not yet + * existing limb. Will not grow if bit should be set to 0 * * \param X MPI to use + * \param pos Zero-based index of the bit in X + * \param val The value to set the bit to (0 or 1) + * + * \return 0 if successful, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, + * POLARSSL_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1 */ -int mpi_lsb( const mpi *X ); +int mpi_set_bit( mpi *X, size_t pos, unsigned char val ); /** - * \brief Return the number of most significant bits + * \brief Return the number of zero-bits before the least significant + * '1' bit + * + * Note: Thus also the zero-based index of the least significant '1' bit * * \param X MPI to use */ -int mpi_msb( const mpi *X ); +size_t mpi_lsb( const mpi *X ); + +/** + * \brief Return the number of bits up to and including the most + * significant '1' bit' + * + * Note: Thus also the one-based index of the most significant '1' bit + * + * \param X MPI to use + */ +size_t mpi_msb( const mpi *X ); /** * \brief Return the total size in bytes * * \param X MPI to use */ -int mpi_size( const mpi *X ); +size_t mpi_size( const mpi *X ); /** * \brief Import from an ASCII string @@ -159,7 +284,7 @@ int mpi_size( const mpi *X ); * \param radix Input numeric base * \param s Null-terminated string buffer * - * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code + * \return 0 if successful, or a POLARSSL_ERR_MPI_XXX error code */ int mpi_read_string( mpi *X, int radix, const char *s ); @@ -171,15 +296,16 @@ int mpi_read_string( mpi *X, int radix, const char *s ); * \param s String buffer * \param slen String buffer size * - * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code. + * \return 0 if successful, or a POLARSSL_ERR_MPI_XXX error code. * *slen is always updated to reflect the amount * of data that has (or would have) been written. * * \note Call this function with *slen = 0 to obtain the * minimum required buffer size in *slen. */ -int mpi_write_string( const mpi *X, int radix, char *s, int *slen ); +int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen ); +#if defined(POLARSSL_FS_IO) /** * \brief Read X from an opened file * @@ -187,7 +313,9 @@ int mpi_write_string( const mpi *X, int radix, char *s, int *slen ); * \param radix Input numeric base * \param fin Input file handle * - * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code + * \return 0 if successful, POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if + * the file read buffer is too small or a + * POLARSSL_ERR_MPI_XXX error code */ int mpi_read_file( mpi *X, int radix, FILE *fin ); @@ -199,11 +327,12 @@ int mpi_read_file( mpi *X, int radix, FILE *fin ); * \param radix Output numeric base * \param fout Output file handle (can be NULL) * - * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code + * \return 0 if successful, or a POLARSSL_ERR_MPI_XXX error code * * \note Set fout == NULL to print X on the console. */ int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout ); +#endif /* POLARSSL_FS_IO */ /** * \brief Import X from unsigned binary data, big endian @@ -213,9 +342,9 @@ int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout ); * \param buflen Input buffer size * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen ); +int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen ); /** * \brief Export X into unsigned binary data, big endian @@ -227,7 +356,7 @@ int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen ); * \return 0 if successful, * POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough */ -int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen ); +int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen ); /** * \brief Left-shift: X <<= count @@ -236,9 +365,9 @@ int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen ); * \param count Amount to shift * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_shift_l( mpi *X, int count ); +int mpi_shift_l( mpi *X, size_t count ); /** * \brief Right-shift: X >>= count @@ -247,9 +376,9 @@ int mpi_shift_l( mpi *X, int count ); * \param count Amount to shift * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_shift_r( mpi *X, int count ); +int mpi_shift_r( mpi *X, size_t count ); /** * \brief Compare unsigned values @@ -285,7 +414,7 @@ int mpi_cmp_mpi( const mpi *X, const mpi *Y ); * -1 if X is lesser than z or * 0 if X is equal to z */ -int mpi_cmp_int( const mpi *X, int z ); +int mpi_cmp_int( const mpi *X, t_sint z ); /** * \brief Unsigned addition: X = |A| + |B| @@ -295,7 +424,7 @@ int mpi_cmp_int( const mpi *X, int z ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_add_abs( mpi *X, const mpi *A, const mpi *B ); @@ -319,7 +448,7 @@ int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B ); @@ -331,7 +460,7 @@ int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B ); @@ -343,9 +472,9 @@ int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B ); * \param b The integer value to add * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_add_int( mpi *X, const mpi *A, int b ); +int mpi_add_int( mpi *X, const mpi *A, t_sint b ); /** * \brief Signed substraction: X = A - b @@ -355,9 +484,9 @@ int mpi_add_int( mpi *X, const mpi *A, int b ); * \param b The integer value to subtract * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_sub_int( mpi *X, const mpi *A, int b ); +int mpi_sub_int( mpi *X, const mpi *A, t_sint b ); /** * \brief Baseline multiplication: X = A * B @@ -367,7 +496,7 @@ int mpi_sub_int( mpi *X, const mpi *A, int b ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B ); @@ -381,9 +510,9 @@ int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B ); * \param b The integer value to multiply with * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ -int mpi_mul_int( mpi *X, const mpi *A, t_int b ); +int mpi_mul_int( mpi *X, const mpi *A, t_sint b ); /** * \brief Division by mpi: A = Q * B + R @@ -394,7 +523,7 @@ int mpi_mul_int( mpi *X, const mpi *A, t_int b ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0 * * \note Either Q or R can be NULL. @@ -410,12 +539,12 @@ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ); * \param b Integer to divide by * * \return 0 if successful, - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0 * * \note Either Q or R can be NULL. */ -int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b ); +int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b ); /** * \brief Modulo: R = A mod B @@ -425,7 +554,7 @@ int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0, * POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0 */ @@ -434,16 +563,16 @@ int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B ); /** * \brief Modulo: r = A mod b * - * \param r Destination t_int + * \param r Destination t_uint * \param A Left-hand MPI * \param b Integer to divide by * * \return 0 if successful, - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0, * POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0 */ -int mpi_mod_int( t_int *r, const mpi *A, int b ); +int mpi_mod_int( t_uint *r, const mpi *A, t_sint b ); /** * \brief Sliding-window exponentiation: X = A^E mod N @@ -455,8 +584,9 @@ int mpi_mod_int( t_int *r, const mpi *A, int b ); * \param _RR Speed-up MPI used for recalculations * * \return 0 if successful, - * 1 if memory allocation failed, - * POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, + * POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even or if + * E is negative * * \note _RR is used to avoid re-computing R*R mod N across * multiple calls, which speeds up things a bit. It can @@ -464,6 +594,21 @@ int mpi_mod_int( t_int *r, const mpi *A, int b ); */ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ); +/** + * \brief Fill an MPI X with size bytes of random + * + * \param X Destination MPI + * \param size Size in bytes + * \param f_rng RNG function + * \param p_rng RNG parameter + * + * \return 0 if successful, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed + */ +int mpi_fill_random( mpi *X, size_t size, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ); + /** * \brief Greatest common divisor: G = gcd(A, B) * @@ -472,7 +617,7 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ); * \param B Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed */ int mpi_gcd( mpi *G, const mpi *A, const mpi *B ); @@ -484,7 +629,7 @@ int mpi_gcd( mpi *G, const mpi *A, const mpi *B ); * \param N Right-hand MPI * * \return 0 if successful, - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N */ @@ -498,26 +643,29 @@ int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N ); * \param p_rng RNG parameter * * \return 0 if successful (probably prime), - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime */ -int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng ); +int mpi_is_prime( mpi *X, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ); /** * \brief Prime number generation * * \param X Destination MPI - * \param nbits Required size of X in bits + * \param nbits Required size of X in bits ( 3 <= nbits <= POLARSSL_MPI_MAX_BITS ) * \param dh_flag If 1, then (X-1)/2 will be prime too * \param f_rng RNG function * \param p_rng RNG parameter * * \return 0 if successful (probably prime), - * 1 if memory allocation failed, + * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed, * POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3 */ -int mpi_gen_prime( mpi *X, int nbits, int dh_flag, - unsigned char (*f_rng)(void *), void *p_rng ); +int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ); /** * \brief Checkup routine diff --git a/polarssl/library/bignum.c b/polarssl/library/bignum.c index dbe85d8..d9845da 100644 --- a/polarssl/library/bignum.c +++ b/polarssl/library/bignum.c @@ -37,11 +37,9 @@ #include "polarssl/bignum.h" #include "polarssl/bn_mul.h" -#include #include -#include -#define ciL ((int) sizeof(t_int)) /* chars in limb */ +#define ciL (sizeof(t_uint)) /* chars in limb */ #define biL (ciL << 3) /* bits in limb */ #define biH (ciL << 2) /* half limb size */ @@ -52,64 +50,51 @@ #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL) /* - * Initialize one or more mpi + * Initialize one MPI */ -void mpi_init( mpi *X, ... ) +void mpi_init( mpi *X ) { - va_list args; + if( X == NULL ) + return; - va_start( args, X ); - - while( X != NULL ) - { - X->s = 1; - X->n = 0; - X->p = NULL; - - X = va_arg( args, mpi* ); - } - - va_end( args ); + X->s = 1; + X->n = 0; + X->p = NULL; } /* - * Unallocate one or more mpi + * Unallocate one MPI */ -void mpi_free( mpi *X, ... ) +void mpi_free( mpi *X ) { - va_list args; - - va_start( args, X ); + if( X == NULL ) + return; - while( X != NULL ) + if( X->p != NULL ) { - if( X->p != NULL ) - { - memset( X->p, 0, X->n * ciL ); - free( X->p ); - } - - X->s = 1; - X->n = 0; - X->p = NULL; - - X = va_arg( args, mpi* ); + memset( X->p, 0, X->n * ciL ); + free( X->p ); } - va_end( args ); + X->s = 1; + X->n = 0; + X->p = NULL; } /* * Enlarge to the specified number of limbs */ -int mpi_grow( mpi *X, int nblimbs ) +int mpi_grow( mpi *X, size_t nblimbs ) { - t_int *p; + t_uint *p; + + if( nblimbs > POLARSSL_MPI_MAX_LIMBS ) + return( POLARSSL_ERR_MPI_MALLOC_FAILED ); if( X->n < nblimbs ) { - if( ( p = (t_int *) malloc( nblimbs * ciL ) ) == NULL ) - return( 1 ); + if( ( p = (t_uint *) malloc( nblimbs * ciL ) ) == NULL ) + return( POLARSSL_ERR_MPI_MALLOC_FAILED ); memset( p, 0, nblimbs * ciL ); @@ -132,7 +117,8 @@ int mpi_grow( mpi *X, int nblimbs ) */ int mpi_copy( mpi *X, const mpi *Y ) { - int ret, i; + int ret; + size_t i; if( X == Y ) return( 0 ); @@ -169,7 +155,7 @@ void mpi_swap( mpi *X, mpi *Y ) /* * Set value from integer */ -int mpi_lset( mpi *X, int z ) +int mpi_lset( mpi *X, t_sint z ) { int ret; @@ -184,15 +170,53 @@ cleanup: return( ret ); } +/* + * Get a specific bit + */ +int mpi_get_bit( const mpi *X, size_t pos ) +{ + if( X->n * biL <= pos ) + return( 0 ); + + return ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01; +} + +/* + * Set a bit to a specific value of 0 or 1 + */ +int mpi_set_bit( mpi *X, size_t pos, unsigned char val ) +{ + int ret = 0; + size_t off = pos / biL; + size_t idx = pos % biL; + + if( val != 0 && val != 1 ) + return POLARSSL_ERR_MPI_BAD_INPUT_DATA; + + if( X->n * biL <= pos ) + { + if( val == 0 ) + return ( 0 ); + + MPI_CHK( mpi_grow( X, off + 1 ) ); + } + + X->p[off] = ( X->p[off] & ~( 0x01 << idx ) ) | ( val << idx ); + +cleanup: + + return( ret ); +} + /* * Return the number of least significant bits */ -int mpi_lsb( const mpi *X ) +size_t mpi_lsb( const mpi *X ) { - int i, j, count = 0; + size_t i, j, count = 0; for( i = 0; i < X->n; i++ ) - for( j = 0; j < (int) biL; j++, count++ ) + for( j = 0; j < biL; j++, count++ ) if( ( ( X->p[i] >> j ) & 1 ) != 0 ) return( count ); @@ -202,34 +226,33 @@ int mpi_lsb( const mpi *X ) /* * Return the number of most significant bits */ -int mpi_msb( const mpi *X ) +size_t mpi_msb( const mpi *X ) { - int i, j; + size_t i, j; for( i = X->n - 1; i > 0; i-- ) if( X->p[i] != 0 ) break; - for( j = biL - 1; j >= 0; j-- ) - if( ( ( X->p[i] >> j ) & 1 ) != 0 ) + for( j = biL; j > 0; j-- ) + if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 ) break; - return( ( i * biL ) + j + 1 ); + return( ( i * biL ) + j ); } /* * Return the total size in bytes */ -int mpi_size( const mpi *X ) +size_t mpi_size( const mpi *X ) { return( ( mpi_msb( X ) + 7 ) >> 3 ); } -#if 0 /* * Convert an ASCII character to digit value */ -static int mpi_get_digit( t_int *d, int radix, char c ) +static int mpi_get_digit( t_uint *d, int radix, char c ) { *d = 255; @@ -237,7 +260,7 @@ static int mpi_get_digit( t_int *d, int radix, char c ) if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37; if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57; - if( *d >= (t_int) radix ) + if( *d >= (t_uint) radix ) return( POLARSSL_ERR_MPI_INVALID_CHARACTER ); return( 0 ); @@ -248,14 +271,15 @@ static int mpi_get_digit( t_int *d, int radix, char c ) */ int mpi_read_string( mpi *X, int radix, const char *s ) { - int ret, i, j, n, slen; - t_int d; + int ret; + size_t i, j, slen, n; + t_uint d; mpi T; if( radix < 2 || radix > 16 ) return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); - mpi_init( &T, NULL ); + mpi_init( &T ); slen = strlen( s ); @@ -266,15 +290,15 @@ int mpi_read_string( mpi *X, int radix, const char *s ) MPI_CHK( mpi_grow( X, n ) ); MPI_CHK( mpi_lset( X, 0 ) ); - for( i = slen - 1, j = 0; i >= 0; i--, j++ ) + for( i = slen, j = 0; i > 0; i--, j++ ) { - if( i == 0 && s[i] == '-' ) + if( i == 1 && s[i - 1] == '-' ) { X->s = -1; break; } - MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); + MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 ); } } @@ -306,7 +330,7 @@ int mpi_read_string( mpi *X, int radix, const char *s ) cleanup: - mpi_free( &T, NULL ); + mpi_free( &T ); return( ret ); } @@ -317,7 +341,7 @@ cleanup: static int mpi_write_hlp( mpi *X, int radix, char **p ) { int ret; - t_int r; + t_uint r; if( radix < 2 || radix > 16 ) return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); @@ -341,9 +365,10 @@ cleanup: /* * Export into an ASCII string */ -int mpi_write_string( const mpi *X, int radix, char *s, int *slen ) +int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen ) { - int ret = 0, n; + int ret = 0; + size_t n; char *p; mpi T; @@ -362,25 +387,27 @@ int mpi_write_string( const mpi *X, int radix, char *s, int *slen ) } p = s; - mpi_init( &T, NULL ); + mpi_init( &T ); if( X->s == -1 ) *p++ = '-'; if( radix == 16 ) { - int c, i, j, k; + int c; + size_t i, j, k; - for( i = X->n - 1, k = 0; i >= 0; i-- ) + for( i = X->n, k = 0; i > 0; i-- ) { - for( j = ciL - 1; j >= 0; j-- ) + for( j = ciL; j > 0; j-- ) { - c = ( X->p[i] >> (j << 3) ) & 0xFF; + c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF; - if( c == 0 && k == 0 && (i + j) != 0 ) + if( c == 0 && k == 0 && ( i + j + 3 ) != 0 ) continue; - p += sprintf( p, "%02X", c ); + *(p++) = "0123456789ABCDEF" [c / 16]; + *(p++) = "0123456789ABCDEF" [c % 16]; k = 1; } } @@ -400,26 +427,34 @@ int mpi_write_string( const mpi *X, int radix, char *s, int *slen ) cleanup: - mpi_free( &T, NULL ); + mpi_free( &T ); return( ret ); } +#if defined(POLARSSL_FS_IO) /* * Read X from an opened file */ int mpi_read_file( mpi *X, int radix, FILE *fin ) { - t_int d; - int slen; + t_uint d; + size_t slen; char *p; - char s[1024]; + /* + * Buffer should have space for (short) label and decimal formatted MPI, + * newline characters and '\0' + */ + char s[ POLARSSL_MPI_RW_BUFFER_SIZE ]; memset( s, 0, sizeof( s ) ); if( fgets( s, sizeof( s ) - 1, fin ) == NULL ) return( POLARSSL_ERR_MPI_FILE_IO_ERROR ); slen = strlen( s ); + if( slen == sizeof( s ) - 2 ) + return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL ); + if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; } if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; } @@ -436,16 +471,19 @@ int mpi_read_file( mpi *X, int radix, FILE *fin ) */ int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout ) { - int n, ret; - size_t slen; - size_t plen; - char s[2048]; + int ret; + size_t n, slen, plen; + /* + * Buffer should have space for (short) label and decimal formatted MPI, + * newline characters and '\0' + */ + char s[ POLARSSL_MPI_RW_BUFFER_SIZE ]; n = sizeof( s ); memset( s, 0, n ); n -= 2; - MPI_CHK( mpi_write_string( X, radix, s, (int *) &n ) ); + MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) ); if( p == NULL ) p = ""; @@ -467,14 +505,15 @@ cleanup: return( ret ); } -#endif +#endif /* POLARSSL_FS_IO */ /* * Import X from unsigned binary data, big endian */ -int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen ) +int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen ) { - int ret, i, j, n; + int ret; + size_t i, j, n; for( n = 0; n < buflen; n++ ) if( buf[n] != 0 ) @@ -483,8 +522,8 @@ int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen ) MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) ); MPI_CHK( mpi_lset( X, 0 ) ); - for( i = buflen - 1, j = 0; i >= n; i--, j++ ) - X->p[j / ciL] |= ((t_int) buf[i]) << ((j % ciL) << 3); + for( i = buflen, j = 0; i > n; i--, j++ ) + X->p[j / ciL] |= ((t_uint) buf[i - 1]) << ((j % ciL) << 3); cleanup: @@ -494,9 +533,9 @@ cleanup: /* * Export X into unsigned binary data, big endian */ -int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen ) +int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen ) { - int i, j, n; + size_t i, j, n; n = mpi_size( X ); @@ -514,17 +553,18 @@ int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen ) /* * Left-shift: X <<= count */ -int mpi_shift_l( mpi *X, int count ) +int mpi_shift_l( mpi *X, size_t count ) { - int ret, i, v0, t1; - t_int r0 = 0, r1; + int ret; + size_t i, v0, t1; + t_uint r0 = 0, r1; v0 = count / (biL ); t1 = count & (biL - 1); i = mpi_msb( X ) + count; - if( X->n * (int) biL < i ) + if( X->n * biL < i ) MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) ); ret = 0; @@ -534,11 +574,11 @@ int mpi_shift_l( mpi *X, int count ) */ if( v0 > 0 ) { - for( i = X->n - 1; i >= v0; i-- ) - X->p[i] = X->p[i - v0]; + for( i = X->n; i > v0; i-- ) + X->p[i - 1] = X->p[i - v0 - 1]; - for( ; i >= 0; i-- ) - X->p[i] = 0; + for( ; i > 0; i-- ) + X->p[i - 1] = 0; } /* @@ -563,14 +603,17 @@ cleanup: /* * Right-shift: X >>= count */ -int mpi_shift_r( mpi *X, int count ) +int mpi_shift_r( mpi *X, size_t count ) { - int i, v0, v1; - t_int r0 = 0, r1; + size_t i, v0, v1; + t_uint r0 = 0, r1; v0 = count / biL; v1 = count & (biL - 1); + if( v0 > X->n || ( v0 == X->n && v1 > 0 ) ) + return mpi_lset( X, 0 ); + /* * shift by count / limb_size */ @@ -588,11 +631,11 @@ int mpi_shift_r( mpi *X, int count ) */ if( v1 > 0 ) { - for( i = X->n - 1; i >= 0; i-- ) + for( i = X->n; i > 0; i-- ) { - r1 = X->p[i] << (biL - v1); - X->p[i] >>= v1; - X->p[i] |= r0; + r1 = X->p[i - 1] << (biL - v1); + X->p[i - 1] >>= v1; + X->p[i - 1] |= r0; r0 = r1; } } @@ -605,26 +648,26 @@ int mpi_shift_r( mpi *X, int count ) */ int mpi_cmp_abs( const mpi *X, const mpi *Y ) { - int i, j; + size_t i, j; - for( i = X->n - 1; i >= 0; i-- ) - if( X->p[i] != 0 ) + for( i = X->n; i > 0; i-- ) + if( X->p[i - 1] != 0 ) break; - for( j = Y->n - 1; j >= 0; j-- ) - if( Y->p[j] != 0 ) + for( j = Y->n; j > 0; j-- ) + if( Y->p[j - 1] != 0 ) break; - if( i < 0 && j < 0 ) + if( i == 0 && j == 0 ) return( 0 ); if( i > j ) return( 1 ); if( j > i ) return( -1 ); - for( ; i >= 0; i-- ) + for( ; i > 0; i-- ) { - if( X->p[i] > Y->p[i] ) return( 1 ); - if( X->p[i] < Y->p[i] ) return( -1 ); + if( X->p[i - 1] > Y->p[i - 1] ) return( 1 ); + if( X->p[i - 1] < Y->p[i - 1] ) return( -1 ); } return( 0 ); @@ -635,17 +678,17 @@ int mpi_cmp_abs( const mpi *X, const mpi *Y ) */ int mpi_cmp_mpi( const mpi *X, const mpi *Y ) { - int i, j; + size_t i, j; - for( i = X->n - 1; i >= 0; i-- ) - if( X->p[i] != 0 ) + for( i = X->n; i > 0; i-- ) + if( X->p[i - 1] != 0 ) break; - for( j = Y->n - 1; j >= 0; j-- ) - if( Y->p[j] != 0 ) + for( j = Y->n; j > 0; j-- ) + if( Y->p[j - 1] != 0 ) break; - if( i < 0 && j < 0 ) + if( i == 0 && j == 0 ) return( 0 ); if( i > j ) return( X->s ); @@ -654,10 +697,10 @@ int mpi_cmp_mpi( const mpi *X, const mpi *Y ) if( X->s > 0 && Y->s < 0 ) return( 1 ); if( Y->s > 0 && X->s < 0 ) return( -1 ); - for( ; i >= 0; i-- ) + for( ; i > 0; i-- ) { - if( X->p[i] > Y->p[i] ) return( X->s ); - if( X->p[i] < Y->p[i] ) return( -X->s ); + if( X->p[i - 1] > Y->p[i - 1] ) return( X->s ); + if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s ); } return( 0 ); @@ -666,10 +709,10 @@ int mpi_cmp_mpi( const mpi *X, const mpi *Y ) /* * Compare signed values */ -int mpi_cmp_int( const mpi *X, int z ) +int mpi_cmp_int( const mpi *X, t_sint z ) { mpi Y; - t_int p[1]; + t_uint p[1]; *p = ( z < 0 ) ? -z : z; Y.s = ( z < 0 ) ? -1 : 1; @@ -684,8 +727,9 @@ int mpi_cmp_int( const mpi *X, int z ) */ int mpi_add_abs( mpi *X, const mpi *A, const mpi *B ) { - int ret, i, j; - t_int *o, *p, c; + int ret; + size_t i, j; + t_uint *o, *p, c; if( X == B ) { @@ -700,15 +744,15 @@ int mpi_add_abs( mpi *X, const mpi *A, const mpi *B ) */ X->s = 1; - for( j = B->n - 1; j >= 0; j-- ) - if( B->p[j] != 0 ) + for( j = B->n; j > 0; j-- ) + if( B->p[j - 1] != 0 ) break; - MPI_CHK( mpi_grow( X, j + 1 ) ); + MPI_CHK( mpi_grow( X, j ) ); o = B->p; p = X->p; c = 0; - for( i = 0; i <= j; i++, o++, p++ ) + for( i = 0; i < j; i++, o++, p++ ) { *p += c; c = ( *p < c ); *p += *o; c += ( *p < *o ); @@ -722,7 +766,7 @@ int mpi_add_abs( mpi *X, const mpi *A, const mpi *B ) p = X->p + i; } - *p += c; c = ( *p < c ); i++; + *p += c; c = ( *p < c ); i++; p++; } cleanup: @@ -733,10 +777,10 @@ cleanup: /* * Helper for mpi substraction */ -static void mpi_sub_hlp( int n, t_int *s, t_int *d ) +static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d ) { - int i; - t_int c, z; + size_t i; + t_uint c, z; for( i = c = 0; i < n; i++, s++, d++ ) { @@ -757,12 +801,13 @@ static void mpi_sub_hlp( int n, t_int *s, t_int *d ) int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B ) { mpi TB; - int ret, n; + int ret; + size_t n; if( mpi_cmp_abs( A, B ) < 0 ) return( POLARSSL_ERR_MPI_NEGATIVE_VALUE ); - mpi_init( &TB, NULL ); + mpi_init( &TB ); if( X == B ) { @@ -780,15 +825,15 @@ int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B ) ret = 0; - for( n = B->n - 1; n >= 0; n-- ) - if( B->p[n] != 0 ) + for( n = B->n; n > 0; n-- ) + if( B->p[n - 1] != 0 ) break; - mpi_sub_hlp( n + 1, B->p, X->p ); + mpi_sub_hlp( n, B->p, X->p ); cleanup: - mpi_free( &TB, NULL ); + mpi_free( &TB ); return( ret ); } @@ -858,10 +903,10 @@ cleanup: /* * Signed addition: X = A + b */ -int mpi_add_int( mpi *X, const mpi *A, int b ) +int mpi_add_int( mpi *X, const mpi *A, t_sint b ) { mpi _B; - t_int p[1]; + t_uint p[1]; p[0] = ( b < 0 ) ? -b : b; _B.s = ( b < 0 ) ? -1 : 1; @@ -874,10 +919,10 @@ int mpi_add_int( mpi *X, const mpi *A, int b ) /* * Signed substraction: X = A - b */ -int mpi_sub_int( mpi *X, const mpi *A, int b ) +int mpi_sub_int( mpi *X, const mpi *A, t_sint b ) { mpi _B; - t_int p[1]; + t_uint p[1]; p[0] = ( b < 0 ) ? -b : b; _B.s = ( b < 0 ) ? -1 : 1; @@ -890,20 +935,11 @@ int mpi_sub_int( mpi *X, const mpi *A, int b ) /* * Helper for mpi multiplication */ -static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b ) +static void mpi_mul_hlp( size_t i, t_uint *s, t_uint *d, t_uint b ) { - t_int c = 0, t = 0; - -#if defined(MULADDC_1024_LOOP) - MULADDC_1024_LOOP + t_uint c = 0, t = 0; - for( ; i > 0; i-- ) - { - MULADDC_INIT - MULADDC_CORE - MULADDC_STOP - } -#elif defined(MULADDC_HUIT) +#if defined(MULADDC_HUIT) for( ; i >= 8; i -= 8 ) { MULADDC_INIT @@ -965,33 +1001,34 @@ static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b ) */ int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B ) { - int ret, i, j; + int ret; + size_t i, j; mpi TA, TB; - mpi_init( &TA, &TB, NULL ); + mpi_init( &TA ); mpi_init( &TB ); if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; } if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; } - for( i = A->n - 1; i >= 0; i-- ) - if( A->p[i] != 0 ) + for( i = A->n; i > 0; i-- ) + if( A->p[i - 1] != 0 ) break; - for( j = B->n - 1; j >= 0; j-- ) - if( B->p[j] != 0 ) + for( j = B->n; j > 0; j-- ) + if( B->p[j - 1] != 0 ) break; - MPI_CHK( mpi_grow( X, i + j + 2 ) ); + MPI_CHK( mpi_grow( X, i + j ) ); MPI_CHK( mpi_lset( X, 0 ) ); - for( i++; j >= 0; j-- ) - mpi_mul_hlp( i, A->p, X->p + j, B->p[j] ); + for( i++; j > 0; j-- ) + mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] ); X->s = A->s * B->s; cleanup: - mpi_free( &TB, &TA, NULL ); + mpi_free( &TB ); mpi_free( &TA ); return( ret ); } @@ -999,10 +1036,10 @@ cleanup: /* * Baseline multiplication: X = A * b */ -int mpi_mul_int( mpi *X, const mpi *A, t_int b ) +int mpi_mul_int( mpi *X, const mpi *A, t_sint b ) { mpi _B; - t_int p[1]; + t_uint p[1]; _B.s = 1; _B.n = 1; @@ -1017,13 +1054,15 @@ int mpi_mul_int( mpi *X, const mpi *A, t_int b ) */ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) { - int ret, i, n, t, k; + int ret; + size_t i, n, t, k; mpi X, Y, Z, T1, T2; if( mpi_cmp_int( B, 0 ) == 0 ) return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO ); - mpi_init( &X, &Y, &Z, &T1, &T2, NULL ); + mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z ); + mpi_init( &T1 ); mpi_init( &T2 ); if( mpi_cmp_abs( A, B ) < 0 ) { @@ -1042,7 +1081,7 @@ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) MPI_CHK( mpi_grow( &T2, 3 ) ); k = mpi_msb( &Y ) % biL; - if( k < (int) biL - 1 ) + if( k < biL - 1 ) { k = biL - 1 - k; MPI_CHK( mpi_shift_l( &X, k ) ); @@ -1052,7 +1091,7 @@ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) n = X.n - 1; t = Y.n - 1; - mpi_shift_l( &Y, biL * (n - t) ); + MPI_CHK( mpi_shift_l( &Y, biL * (n - t) ) ); while( mpi_cmp_mpi( &X, &Y ) >= 0 ) { @@ -1067,22 +1106,22 @@ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) Z.p[i - t - 1] = ~0; else { -#if defined(POLARSSL_HAVE_LONGLONG) - t_dbl r; +#if defined(POLARSSL_HAVE_UDBL) + t_udbl r; - r = (t_dbl) X.p[i] << biL; - r |= (t_dbl) X.p[i - 1]; + r = (t_udbl) X.p[i] << biL; + r |= (t_udbl) X.p[i - 1]; r /= Y.p[t]; - if( r > ((t_dbl) 1 << biL) - 1) - r = ((t_dbl) 1 << biL) - 1; + if( r > ((t_udbl) 1 << biL) - 1) + r = ((t_udbl) 1 << biL) - 1; - Z.p[i - t - 1] = (t_int) r; + Z.p[i - t - 1] = (t_uint) r; #else /* * __udiv_qrnnd_c, from gmp/longlong.h */ - t_int q0, q1, r0, r1; - t_int d0, d1, d, m; + t_uint q0, q1, r0, r1; + t_uint d0, d1, d, m; d = Y.p[t]; d0 = ( d << biH ) >> biH; @@ -1159,31 +1198,28 @@ int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B ) if( R != NULL ) { mpi_shift_r( &X, k ); + X.s = A->s; mpi_copy( R, &X ); - R->s = A->s; if( mpi_cmp_int( R, 0 ) == 0 ) R->s = 1; } cleanup: - mpi_free( &X, &Y, &Z, &T1, &T2, NULL ); + mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z ); + mpi_free( &T1 ); mpi_free( &T2 ); return( ret ); } /* * Division by int: A = Q * b + R - * - * Returns 0 if successful - * 1 if memory allocation failed - * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0 */ -int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b ) +int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b ) { mpi _B; - t_int p[1]; + t_uint p[1]; p[0] = ( b < 0 ) ? -b : b; _B.s = ( b < 0 ) ? -1 : 1; @@ -1219,10 +1255,10 @@ cleanup: /* * Modulo: r = A mod b */ -int mpi_mod_int( t_int *r, const mpi *A, int b ) +int mpi_mod_int( t_uint *r, const mpi *A, t_sint b ) { - int i; - t_int x, y, z; + size_t i; + t_uint x, y, z; if( b == 0 ) return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO ); @@ -1248,9 +1284,9 @@ int mpi_mod_int( t_int *r, const mpi *A, int b ) /* * general case */ - for( i = A->n - 1, y = 0; i >= 0; i-- ) + for( i = A->n, y = 0; i > 0; i-- ) { - x = A->p[i]; + x = A->p[i - 1]; y = ( y << biH ) | ( x >> biH ); z = y / b; y -= z * b; @@ -1276,9 +1312,9 @@ int mpi_mod_int( t_int *r, const mpi *A, int b ) /* * Fast Montgomery initialization (thanks to Tom St Denis) */ -static void mpi_montg_init( t_int *mm, const mpi *N ) +static void mpi_montg_init( t_uint *mm, const mpi *N ) { - t_int x, m0 = N->p[0]; + t_uint x, m0 = N->p[0]; x = m0; x += ( ( m0 + 2 ) & 4 ) << 1; @@ -1294,10 +1330,10 @@ static void mpi_montg_init( t_int *mm, const mpi *N ) /* * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) */ -static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_int mm, const mpi *T ) +static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_uint mm, const mpi *T ) { - int i, n, m; - t_int u0, u1, *d; + size_t i, n, m; + t_uint u0, u1, *d; memset( T->p, 0, T->n * ciL ); @@ -1331,12 +1367,12 @@ static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_int mm, const mpi /* * Montgomery reduction: A = A * R^-1 mod N */ -static void mpi_montred( mpi *A, const mpi *N, t_int mm, const mpi *T ) +static void mpi_montred( mpi *A, const mpi *N, t_uint mm, const mpi *T ) { - t_int z = 1; + t_uint z = 1; mpi U; - U.n = U.s = z; + U.n = U.s = (int) z; U.p = &z; mpi_montmul( A, &U, N, mm, T ); @@ -1347,19 +1383,25 @@ static void mpi_montred( mpi *A, const mpi *N, t_int mm, const mpi *T ) */ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) { - int ret, i, j, wsize, wbits; - int bufsize, nblimbs, nbits; - t_int ei, mm, state; - mpi RR, T, W[64]; + int ret; + size_t wbits, wsize, one = 1; + size_t i, j, nblimbs; + size_t bufsize, nbits; + t_uint ei, mm, state; + mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos; + int neg; if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 ) return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); + if( mpi_cmp_int( E, 0 ) < 0 ) + return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); + /* * Init temps and window size */ mpi_montg_init( &mm, N ); - mpi_init( &RR, &T, NULL ); + mpi_init( &RR ); mpi_init( &T ); memset( W, 0, sizeof( W ) ); i = mpi_msb( E ); @@ -1367,11 +1409,27 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; + if( wsize > POLARSSL_MPI_WINDOW_SIZE ) + wsize = POLARSSL_MPI_WINDOW_SIZE; + j = N->n + 1; MPI_CHK( mpi_grow( X, j ) ); MPI_CHK( mpi_grow( &W[1], j ) ); MPI_CHK( mpi_grow( &T, j * 2 ) ); + /* + * Compensate for negative A (and correct at the end) + */ + neg = ( A->s == -1 ); + + mpi_init( &Apos ); + if( neg ) + { + MPI_CHK( mpi_copy( &Apos, A ) ); + Apos.s = 1; + A = &Apos; + } + /* * If 1st call, pre-compute R^2 mod N */ @@ -1407,7 +1465,7 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) /* * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1) */ - j = 1 << (wsize - 1); + j = one << (wsize - 1); MPI_CHK( mpi_grow( &W[j], N->n + 1 ) ); MPI_CHK( mpi_copy( &W[j], &W[1] ) ); @@ -1418,7 +1476,7 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) /* * W[i] = W[i - 1] * W[1] */ - for( i = j + 1; i < (1 << wsize); i++ ) + for( i = j + 1; i < (one << wsize); i++ ) { MPI_CHK( mpi_grow( &W[i], N->n + 1 ) ); MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) ); @@ -1440,7 +1498,7 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) if( nblimbs-- == 0 ) break; - bufsize = sizeof( t_int ) << 3; + bufsize = sizeof( t_uint ) << 3; } bufsize--; @@ -1498,7 +1556,7 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) wbits <<= 1; - if( (wbits & (1 << wsize)) != 0 ) + if( (wbits & (one << wsize)) != 0 ) mpi_montmul( X, &W[1], N, mm, &T ); } @@ -1507,14 +1565,21 @@ int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR ) */ mpi_montred( X, N, mm, &T ); + if( neg ) + { + X->s = -1; + mpi_add_mpi( X, N, X ); + } + cleanup: - for( i = (1 << (wsize - 1)); i < (1 << wsize); i++ ) - mpi_free( &W[i], NULL ); + for( i = (one << (wsize - 1)); i < (one << wsize); i++ ) + mpi_free( &W[i] ); + + mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos ); - if( _RR != NULL ) - mpi_free( &W[1], &T, NULL ); - else mpi_free( &W[1], &T, &RR, NULL ); + if( _RR == NULL ) + mpi_free( &RR ); return( ret ); } @@ -1524,10 +1589,11 @@ cleanup: */ int mpi_gcd( mpi *G, const mpi *A, const mpi *B ) { - int ret, lz, lzt; + int ret; + size_t lz, lzt; mpi TG, TA, TB; - mpi_init( &TG, &TA, &TB, NULL ); + mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB ); MPI_CHK( mpi_copy( &TA, A ) ); MPI_CHK( mpi_copy( &TB, B ) ); @@ -1565,8 +1631,23 @@ int mpi_gcd( mpi *G, const mpi *A, const mpi *B ) cleanup: - mpi_free( &TB, &TA, &TG, NULL ); + mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB ); + + return( ret ); +} + +int mpi_fill_random( mpi *X, size_t size, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ) +{ + int ret; + + MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( size ) ) ); + MPI_CHK( mpi_lset( X, 0 ) ); + + MPI_CHK( f_rng( p_rng, (unsigned char *) X->p, size ) ); +cleanup: return( ret ); } @@ -1581,8 +1662,9 @@ int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N ) if( mpi_cmp_int( N, 0 ) <= 0 ) return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); - mpi_init( &TA, &TU, &U1, &U2, &G, - &TB, &TV, &V1, &V2, NULL ); + mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 ); + mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV ); + mpi_init( &V1 ); mpi_init( &V2 ); MPI_CHK( mpi_gcd( &G, A, N ) ); @@ -1657,8 +1739,9 @@ int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N ) cleanup: - mpi_free( &V2, &V1, &TV, &TB, &G, - &U2, &U1, &TU, &TA, NULL ); + mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 ); + mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV ); + mpi_free( &V1 ); mpi_free( &V2 ); return( ret ); } @@ -1693,11 +1776,13 @@ static const int small_prime[] = /* * Miller-Rabin primality test (HAC 4.24) */ -int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng ) +int mpi_is_prime( mpi *X, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ) { - int ret, i, j, n, s, xs; + int ret, xs; + size_t i, j, n, s; mpi W, R, T, A, RR; - unsigned char *p; if( mpi_cmp_int( X, 0 ) == 0 || mpi_cmp_int( X, 1 ) == 0 ) @@ -1706,7 +1791,8 @@ int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng ) if( mpi_cmp_int( X, 2 ) == 0 ) return( 0 ); - mpi_init( &W, &R, &T, &A, &RR, NULL ); + mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A ); + mpi_init( &RR ); xs = X->s; X->s = 1; @@ -1718,7 +1804,7 @@ int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng ) for( i = 0; small_prime[i] > 0; i++ ) { - t_int r; + t_uint r; if( mpi_cmp_int( X, small_prime[i] ) <= 0 ) return( 0 ); @@ -1751,14 +1837,13 @@ int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng ) /* * pick a random A, 1 < A < |X| - 1 */ - MPI_CHK( mpi_grow( &A, X->n ) ); - - p = (unsigned char *) A.p; - for( j = 0; j < A.n * ciL; j++ ) - *p++ = f_rng( p_rng ); + MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); - j = mpi_msb( &A ) - mpi_msb( &W ); - MPI_CHK( mpi_shift_r( &A, j + 1 ) ); + if( mpi_cmp_mpi( &A, &W ) >= 0 ) + { + j = mpi_msb( &A ) - mpi_msb( &W ); + MPI_CHK( mpi_shift_r( &A, j + 1 ) ); + } A.p[0] |= 3; /* @@ -1800,7 +1885,8 @@ cleanup: X->s = xs; - mpi_free( &RR, &A, &T, &R, &W, NULL ); + mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A ); + mpi_free( &RR ); return( ret ); } @@ -1808,26 +1894,22 @@ cleanup: /* * Prime number generation */ -int mpi_gen_prime( mpi *X, int nbits, int dh_flag, - unsigned char (*f_rng)(void *), void *p_rng ) +int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag, + int (*f_rng)(void *, unsigned char *, size_t), + void *p_rng ) { - int ret, k, n; - unsigned char *p; + int ret; + size_t k, n; mpi Y; - if( nbits < 3 ) + if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS ) return( POLARSSL_ERR_MPI_BAD_INPUT_DATA ); - mpi_init( &Y, NULL ); + mpi_init( &Y ); n = BITS_TO_LIMBS( nbits ); - MPI_CHK( mpi_grow( X, n ) ); - MPI_CHK( mpi_lset( X, 0 ) ); - - p = (unsigned char *) X->p; - for( k = 0; k < X->n * ciL; k++ ) - *p++ = f_rng( p_rng ); + MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); k = mpi_msb( X ); if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) ); @@ -1872,7 +1954,7 @@ int mpi_gen_prime( mpi *X, int nbits, int dh_flag, cleanup: - mpi_free( &Y, NULL ); + mpi_free( &Y ); return( ret ); } @@ -1881,7 +1963,7 @@ cleanup: #if defined(POLARSSL_SELF_TEST) -#define GCD_PAIR_COUNT 3 +#define GCD_PAIR_COUNT 3 static const int gcd_pairs[GCD_PAIR_COUNT][3] = { @@ -1898,7 +1980,8 @@ int mpi_self_test( int verbose ) int ret, i; mpi A, E, N, X, Y, U, V; - mpi_init( &A, &E, &N, &X, &Y, &U, &V, NULL ); + mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X ); + mpi_init( &Y ); mpi_init( &U ); mpi_init( &V ); MPI_CHK( mpi_read_string( &A, 16, "EFE021C2645FD1DC586E69184AF4A31E" \ @@ -1988,6 +2071,7 @@ int mpi_self_test( int verbose ) if( verbose != 0 ) printf( "passed\n" ); +#if defined(POLARSSL_GENPRIME) MPI_CHK( mpi_inv_mod( &X, &A, &N ) ); MPI_CHK( mpi_read_string( &U, 16, @@ -2008,6 +2092,7 @@ int mpi_self_test( int verbose ) if( verbose != 0 ) printf( "passed\n" ); +#endif if( verbose != 0 ) printf( " MPI test #5 (simple gcd): " ); @@ -2015,17 +2100,17 @@ int mpi_self_test( int verbose ) for ( i = 0; i < GCD_PAIR_COUNT; i++) { MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) ); - MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) ); + MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) ); - MPI_CHK( mpi_gcd( &A, &X, &Y ) ); + MPI_CHK( mpi_gcd( &A, &X, &Y ) ); - if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) - { - if( verbose != 0 ) - printf( "failed at %d\n", i ); + if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) + { + if( verbose != 0 ) + printf( "failed at %d\n", i ); - return( 1 ); - } + return( 1 ); + } } if( verbose != 0 ) @@ -2036,7 +2121,8 @@ cleanup: if( ret != 0 && verbose != 0 ) printf( "Unexpected error, return code = %08X\n", ret ); - mpi_free( &V, &U, &Y, &X, &N, &E, &A, NULL ); + mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X ); + mpi_free( &Y ); mpi_free( &U ); mpi_free( &V ); if( verbose != 0 ) printf( "\n" ); -- 2.20.1