package/px5g/src/polarssl/bignum.h

   1 /**
   2  * \file bignum.h
   3  *
   4  *  Based on XySSL: Copyright (C) 2006-2008  Christophe Devine
   5  *
   6  *  Copyright (C) 2009  Paul Bakker <polarssl_maintainer at polarssl dot org>
   7  *
   8  *  All rights reserved.
   9  *
  10  *  Redistribution and use in source and binary forms, with or without
  11  *  modification, are permitted provided that the following conditions
  12  *  are met:
  13  *
  14  *    * Redistributions of source code must retain the above copyright
  15  *      notice, this list of conditions and the following disclaimer.
  16  *    * Redistributions in binary form must reproduce the above copyright
  17  *      notice, this list of conditions and the following disclaimer in the
  18  *      documentation and/or other materials provided with the distribution.
  19  *    * Neither the names of PolarSSL or XySSL nor the names of its contributors
  20  *      may be used to endorse or promote products derived from this software
  21  *      without specific prior written permission.
  22  *
  23  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  *  TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  *  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  *  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  *  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  *  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 #ifndef POLARSSL_BIGNUM_H
  36 #define POLARSSL_BIGNUM_H
  37
  38 #include <stdio.h>
  39
  40 #define POLARSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002
  41 #define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004
  42 #define POLARSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006
  43 #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008
  44 #define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A
  45 #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C
  46 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E
  47
  48 #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
  49
  50 /*
  51  * Define the base integer type, architecture-wise
  52  */
  53 #if defined(POLARSSL_HAVE_INT8)
  54 typedef unsigned char  t_int;
  55 typedef unsigned short t_dbl;
  56 #else
  57 #if defined(POLARSSL_HAVE_INT16)
  58 typedef unsigned short t_int;
  59 typedef unsigned long  t_dbl;
  60 #else
  61   typedef unsigned long t_int;
  62   #if defined(_MSC_VER) && defined(_M_IX86)
  63   typedef unsigned __int64 t_dbl;
  64   #else
  65     #if defined(__amd64__) || defined(__x86_64__)    || \
  66         defined(__ppc64__) || defined(__powerpc64__) || \
  67         defined(__ia64__)  || defined(__alpha__)
  68     typedef unsigned int t_dbl __attribute__((mode(TI)));
  69     #else
  70     typedef unsigned long long t_dbl;
  71     #endif
  72   #endif
  73 #endif
  74 #endif
  75
  76 /**
  77  * \brief          MPI structure
  78  */
  79 typedef struct
  80 {
  81     int s;              /*!<  integer sign      */
  82     int n;              /*!<  total # of limbs  */
  83     t_int *p;           /*!<  pointer to limbs  */
  84 }
  85 mpi;
  86
  87 #ifdef __cplusplus
  88 extern "C" {
  89 #endif
  90
  91 /**
  92  * \brief          Initialize one or more mpi
  93  */
  94 void mpi_init( mpi *X, ... );
  95
  96 /**
  97  * \brief          Unallocate one or more mpi
  98  */
  99 void mpi_free( mpi *X, ... );
 100
 101 /**
 102  * \brief          Enlarge to the specified number of limbs
 103  *
 104  * \return         0 if successful,
 105  *                 1 if memory allocation failed
 106  */
 107 int mpi_grow( mpi *X, int nblimbs );
 108
 109 /**
 110  * \brief          Copy the contents of Y into X
 111  *
 112  * \return         0 if successful,
 113  *                 1 if memory allocation failed
 114  */
 115 int mpi_copy( mpi *X, mpi *Y );
 116
 117 /**
 118  * \brief          Swap the contents of X and Y
 119  */
 120 void mpi_swap( mpi *X, mpi *Y );
 121
 122 /**
 123  * \brief          Set value from integer
 124  *
 125  * \return         0 if successful,
 126  *                 1 if memory allocation failed
 127  */
 128 int mpi_lset( mpi *X, int z );
 129
 130 /**
 131  * \brief          Return the number of least significant bits
 132  */
 133 int mpi_lsb( mpi *X );
 134
 135 /**
 136  * \brief          Return the number of most significant bits
 137  */
 138 int mpi_msb( mpi *X );
 139
 140 /**
 141  * \brief          Return the total size in bytes
 142  */
 143 int mpi_size( mpi *X );
 144
 145 /**
 146  * \brief          Import from an ASCII string
 147  *
 148  * \param X        destination mpi
 149  * \param radix    input numeric base
 150  * \param s        null-terminated string buffer
 151  *
 152  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 153  */
 154 int mpi_read_string( mpi *X, int radix, char *s );
 155
 156 /**
 157  * \brief          Export into an ASCII string
 158  *
 159  * \param X        source mpi
 160  * \param radix    output numeric base
 161  * \param s        string buffer
 162  * \param slen     string buffer size
 163  *
 164  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 165  *
 166  * \note           Call this function with *slen = 0 to obtain the
 167  *                 minimum required buffer size in *slen.
 168  */
 169 int mpi_write_string( mpi *X, int radix, char *s, int *slen );
 170
 171 /**
 172  * \brief          Read X from an opened file
 173  *
 174  * \param X        destination mpi
 175  * \param radix    input numeric base
 176  * \param fin      input file handle
 177  *
 178  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 179  */
 180 int mpi_read_file( mpi *X, int radix, FILE *fin );
 181
 182 /**
 183  * \brief          Write X into an opened file, or stdout
 184  *
 185  * \param p        prefix, can be NULL
 186  * \param X        source mpi
 187  * \param radix    output numeric base
 188  * \param fout     output file handle
 189  *
 190  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 191  *
 192  * \note           Set fout == NULL to print X on the console.
 193  */
 194 int mpi_write_file( char *p, mpi *X, int radix, FILE *fout );
 195
 196 /**
 197  * \brief          Import X from unsigned binary data, big endian
 198  *
 199  * \param X        destination mpi
 200  * \param buf      input buffer
 201  * \param buflen   input buffer size
 202  *
 203  * \return         0 if successful,
 204  *                 1 if memory allocation failed
 205  */
 206 int mpi_read_binary( mpi *X, unsigned char *buf, int buflen );
 207
 208 /**
 209  * \brief          Export X into unsigned binary data, big endian
 210  *
 211  * \param X        source mpi
 212  * \param buf      output buffer
 213  * \param buflen   output buffer size
 214  *
 215  * \return         0 if successful,
 216  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 217  *
 218  * \note           Call this function with *buflen = 0 to obtain the
 219  *                 minimum required buffer size in *buflen.
 220  */
 221 int mpi_write_binary( mpi *X, unsigned char *buf, int buflen );
 222
 223 /**
 224  * \brief          Left-shift: X <<= count
 225  *
 226  * \return         0 if successful,
 227  *                 1 if memory allocation failed
 228  */
 229 int mpi_shift_l( mpi *X, int count );
 230
 231 /**
 232  * \brief          Right-shift: X >>= count
 233  *
 234  * \return         0 if successful,
 235  *                 1 if memory allocation failed
 236  */
 237 int mpi_shift_r( mpi *X, int count );
 238
 239 /**
 240  * \brief          Compare unsigned values
 241  *
 242  * \return         1 if |X| is greater than |Y|,
 243  *                -1 if |X| is lesser  than |Y| or
 244  *                 0 if |X| is equal to |Y|
 245  */
 246 int mpi_cmp_abs( mpi *X, mpi *Y );
 247
 248 /**
 249  * \brief          Compare signed values
 250  *
 251  * \return         1 if X is greater than Y,
 252  *                -1 if X is lesser  than Y or
 253  *                 0 if X is equal to Y
 254  */
 255 int mpi_cmp_mpi( mpi *X, mpi *Y );
 256
 257 /**
 258  * \brief          Compare signed values
 259  *
 260  * \return         1 if X is greater than z,
 261  *                -1 if X is lesser  than z or
 262  *                 0 if X is equal to z
 263  */
 264 int mpi_cmp_int( mpi *X, int z );
 265
 266 /**
 267  * \brief          Unsigned addition: X = |A| + |B|
 268  *
 269  * \return         0 if successful,
 270  *                 1 if memory allocation failed
 271  */
 272 int mpi_add_abs( mpi *X, mpi *A, mpi *B );
 273
 274 /**
 275  * \brief          Unsigned substraction: X = |A| - |B|
 276  *
 277  * \return         0 if successful,
 278  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 279  */
 280 int mpi_sub_abs( mpi *X, mpi *A, mpi *B );
 281
 282 /**
 283  * \brief          Signed addition: X = A + B
 284  *
 285  * \return         0 if successful,
 286  *                 1 if memory allocation failed
 287  */
 288 int mpi_add_mpi( mpi *X, mpi *A, mpi *B );
 289
 290 /**
 291  * \brief          Signed substraction: X = A - B
 292  *
 293  * \return         0 if successful,
 294  *                 1 if memory allocation failed
 295  */
 296 int mpi_sub_mpi( mpi *X, mpi *A, mpi *B );
 297
 298 /**
 299  * \brief          Signed addition: X = A + b
 300  *
 301  * \return         0 if successful,
 302  *                 1 if memory allocation failed
 303  */
 304 int mpi_add_int( mpi *X, mpi *A, int b );
 305
 306 /**
 307  * \brief          Signed substraction: X = A - b
 308  *
 309  * \return         0 if successful,
 310  *                 1 if memory allocation failed
 311  */
 312 int mpi_sub_int( mpi *X, mpi *A, int b );
 313
 314 /**
 315  * \brief          Baseline multiplication: X = A * B
 316  *
 317  * \return         0 if successful,
 318  *                 1 if memory allocation failed
 319  */
 320 int mpi_mul_mpi( mpi *X, mpi *A, mpi *B );
 321
 322 /**
 323  * \brief          Baseline multiplication: X = A * b
 324  *
 325  * \return         0 if successful,
 326  *                 1 if memory allocation failed
 327  */
 328 int mpi_mul_int( mpi *X, mpi *A, t_int b );
 329
 330 /**
 331  * \brief          Division by mpi: A = Q * B + R
 332  *
 333  * \return         0 if successful,
 334  *                 1 if memory allocation failed,
 335  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 336  *
 337  * \note           Either Q or R can be NULL.
 338  */
 339 int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B );
 340
 341 /**
 342  * \brief          Division by int: A = Q * b + R
 343  *
 344  * \return         0 if successful,
 345  *                 1 if memory allocation failed,
 346  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 347  *
 348  * \note           Either Q or R can be NULL.
 349  */
 350 int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b );
 351
 352 /**
 353  * \brief          Modulo: R = A mod B
 354  *
 355  * \return         0 if successful,
 356  *                 1 if memory allocation failed,
 357  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 358  */
 359 int mpi_mod_mpi( mpi *R, mpi *A, mpi *B );
 360
 361 /**
 362  * \brief          Modulo: r = A mod b
 363  *
 364  * \return         0 if successful,
 365  *                 1 if memory allocation failed,
 366  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 367  */
 368 int mpi_mod_int( t_int *r, mpi *A, int b );
 369
 370 /**
 371  * \brief          Sliding-window exponentiation: X = A^E mod N
 372  *
 373  * \return         0 if successful,
 374  *                 1 if memory allocation failed,
 375  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
 376  *
 377  * \note           _RR is used to avoid re-computing R*R mod N across
 378  *                 multiple calls, which speeds up things a bit. It can
 379  *                 be set to NULL if the extra performance is unneeded.
 380  */
 381 int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR );
 382
 383 /**
 384  * \brief          Greatest common divisor: G = gcd(A, B)
 385  *
 386  * \return         0 if successful,
 387  *                 1 if memory allocation failed
 388  */
 389 int mpi_gcd( mpi *G, mpi *A, mpi *B );
 390
 391 /**
 392  * \brief          Modular inverse: X = A^-1 mod N
 393  *
 394  * \return         0 if successful,
 395  *                 1 if memory allocation failed,
 396  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
 397  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
 398  */
 399 int mpi_inv_mod( mpi *X, mpi *A, mpi *N );
 400
 401 /**
 402  * \brief          Miller-Rabin primality test
 403  *
 404  * \return         0 if successful (probably prime),
 405  *                 1 if memory allocation failed,
 406  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
 407  */
 408 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng );
 409
 410 /**
 411  * \brief          Prime number generation
 412  *
 413  * \param X        destination mpi
 414  * \param nbits    required size of X in bits
 415  * \param dh_flag  if 1, then (X-1)/2 will be prime too
 416  * \param f_rng    RNG function
 417  * \param p_rng    RNG parameter
 418  *
 419  * \return         0 if successful (probably prime),
 420  *                 1 if memory allocation failed,
 421  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
 422  */
 423 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
 424                    int (*f_rng)(void *), void *p_rng );
 425
 426 /**
 427  * \brief          Checkup routine
 428  *
 429  * \return         0 if successful, or 1 if the test failed
 430  */
 431 int mpi_self_test( int verbose );
 432
 433 #ifdef __cplusplus
 434 }
 435 #endif
 436
 437 #endif /* bignum.h */