src/src/pdkim/bignum.h

   1 /**
   2  * \file bignum.h
   3  *
   4  *  Copyright (C) 2006-2010, Brainspark B.V.
   5  *
   6  *  This file is part of PolarSSL (http://www.polarssl.org)
   7  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
   8  *
   9  *  All rights reserved.
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License along
  22  *  with this program; if not, write to the Free Software Foundation, Inc.,
  23  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24  */
  25
  26 #ifndef POLARSSL_BIGNUM_H
  27 #define POLARSSL_BIGNUM_H
  28
  29 #include <stdio.h>
  30
  31 #define POLARSSL_ERR_MPI_FILE_IO_ERROR                     0x0002
  32 #define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    0x0004
  33 #define POLARSSL_ERR_MPI_INVALID_CHARACTER                 0x0006
  34 #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  0x0008
  35 #define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    0x000A
  36 #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  0x000C
  37 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    0x000E
  38
  39 #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
  40
  41 /*
  42  * Define the base integer type, architecture-wise
  43  */
  44 #if defined(POLARSSL_HAVE_INT8)
  45 typedef unsigned char  t_int;
  46 typedef unsigned short t_dbl;
  47 #else
  48 #if defined(POLARSSL_HAVE_INT16)
  49 typedef unsigned short t_int;
  50 typedef unsigned long  t_dbl;
  51 #else
  52   typedef unsigned long t_int;
  53   #if defined(_MSC_VER) && defined(_M_IX86)
  54   typedef unsigned __int64 t_dbl;
  55   #else
  56     #if defined(__amd64__) || defined(__x86_64__)    || \
  57         defined(__ppc64__) || defined(__powerpc64__) || \
  58         defined(__ia64__)  || defined(__alpha__)
  59     typedef unsigned int t_dbl __attribute__((mode(TI)));
  60     #else
  61       #if defined(POLARSSL_HAVE_LONGLONG)
  62       typedef unsigned long long t_dbl;
  63       #endif
  64     #endif
  65   #endif
  66 #endif
  67 #endif
  68
  69 /**
  70  * \brief          MPI structure
  71  */
  72 typedef struct
  73 {
  74     int s;              /*!<  integer sign      */
  75     int n;              /*!<  total # of limbs  */
  76     t_int *p;           /*!<  pointer to limbs  */
  77 }
  78 mpi;
  79
  80 #ifdef __cplusplus
  81 extern "C" {
  82 #endif
  83
  84 /**
  85  * \brief          Initialize one or more mpi
  86  */
  87 void mpi_init( mpi *X, ... );
  88
  89 /**
  90  * \brief          Unallocate one or more mpi
  91  */
  92 void mpi_free( mpi *X, ... );
  93
  94 /**
  95  * \brief          Enlarge to the specified number of limbs
  96  *
  97  * \param X        MPI to grow
  98  * \param nblimbs  The target number of limbs
  99  *
 100  * \return         0 if successful,
 101  *                 1 if memory allocation failed
 102  */
 103 int mpi_grow( mpi *X, int nblimbs );
 104
 105 /**
 106  * \brief          Copy the contents of Y into X
 107  *
 108  * \param X        Destination MPI
 109  * \param Y        Source MPI
 110  *
 111  * \return         0 if successful,
 112  *                 1 if memory allocation failed
 113  */
 114 int mpi_copy( mpi *X, const mpi *Y );
 115
 116 /**
 117  * \brief          Swap the contents of X and Y
 118  *
 119  * \param X        First MPI value
 120  * \param Y        Second MPI value
 121  */
 122 void mpi_swap( mpi *X, mpi *Y );
 123
 124 /**
 125  * \brief          Set value from integer
 126  *
 127  * \param X        MPI to set
 128  * \param z        Value to use
 129  *
 130  * \return         0 if successful,
 131  *                 1 if memory allocation failed
 132  */
 133 int mpi_lset( mpi *X, int z );
 134
 135 /**
 136  * \brief          Return the number of least significant bits
 137  *
 138  * \param X        MPI to use
 139  */
 140 int mpi_lsb( const mpi *X );
 141
 142 /**
 143  * \brief          Return the number of most significant bits
 144  *
 145  * \param X        MPI to use
 146  */
 147 int mpi_msb( const mpi *X );
 148
 149 /**
 150  * \brief          Return the total size in bytes
 151  *
 152  * \param X        MPI to use
 153  */
 154 int mpi_size( const mpi *X );
 155
 156 /**
 157  * \brief          Import from an ASCII string
 158  *
 159  * \param X        Destination MPI
 160  * \param radix    Input numeric base
 161  * \param s        Null-terminated string buffer
 162  *
 163  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 164  */
 165 int mpi_read_string( mpi *X, int radix, const char *s );
 166
 167 /**
 168  * \brief          Export into an ASCII string
 169  *
 170  * \param X        Source MPI
 171  * \param radix    Output numeric base
 172  * \param s        String buffer
 173  * \param slen     String buffer size
 174  *
 175  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code.
 176  *                 *slen is always updated to reflect the amount
 177  *                 of data that has (or would have) been written.
 178  *
 179  * \note           Call this function with *slen = 0 to obtain the
 180  *                 minimum required buffer size in *slen.
 181  */
 182 int mpi_write_string( const mpi *X, int radix, char *s, int *slen );
 183
 184 /**
 185  * \brief          Read X from an opened file
 186  *
 187  * \param X        Destination MPI
 188  * \param radix    Input numeric base
 189  * \param fin      Input file handle
 190  *
 191  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 192  */
 193 int mpi_read_file( mpi *X, int radix, FILE *fin );
 194
 195 /**
 196  * \brief          Write X into an opened file, or stdout if fout is NULL
 197  *
 198  * \param p        Prefix, can be NULL
 199  * \param X        Source MPI
 200  * \param radix    Output numeric base
 201  * \param fout     Output file handle (can be NULL)
 202  *
 203  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 204  *
 205  * \note           Set fout == NULL to print X on the console.
 206  */
 207 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
 208
 209 /**
 210  * \brief          Import X from unsigned binary data, big endian
 211  *
 212  * \param X        Destination MPI
 213  * \param buf      Input buffer
 214  * \param buflen   Input buffer size
 215  *
 216  * \return         0 if successful,
 217  *                 1 if memory allocation failed
 218  */
 219 int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen );
 220
 221 /**
 222  * \brief          Export X into unsigned binary data, big endian
 223  *
 224  * \param X        Source MPI
 225  * \param buf      Output buffer
 226  * \param buflen   Output buffer size
 227  *
 228  * \return         0 if successful,
 229  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 230  */
 231 int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen );
 232
 233 /**
 234  * \brief          Left-shift: X <<= count
 235  *
 236  * \param X        MPI to shift
 237  * \param count    Amount to shift
 238  *
 239  * \return         0 if successful,
 240  *                 1 if memory allocation failed
 241  */
 242 int mpi_shift_l( mpi *X, int count );
 243
 244 /**
 245  * \brief          Right-shift: X >>= count
 246  *
 247  * \param X        MPI to shift
 248  * \param count    Amount to shift
 249  *
 250  * \return         0 if successful,
 251  *                 1 if memory allocation failed
 252  */
 253 int mpi_shift_r( mpi *X, int count );
 254
 255 /**
 256  * \brief          Compare unsigned values
 257  *
 258  * \param X        Left-hand MPI
 259  * \param Y        Right-hand MPI
 260  *
 261  * \return         1 if |X| is greater than |Y|,
 262  *                -1 if |X| is lesser  than |Y| or
 263  *                 0 if |X| is equal to |Y|
 264  */
 265 int mpi_cmp_abs( const mpi *X, const mpi *Y );
 266
 267 /**
 268  * \brief          Compare signed values
 269  *
 270  * \param X        Left-hand MPI
 271  * \param Y        Right-hand MPI
 272  *
 273  * \return         1 if X is greater than Y,
 274  *                -1 if X is lesser  than Y or
 275  *                 0 if X is equal to Y
 276  */
 277 int mpi_cmp_mpi( const mpi *X, const mpi *Y );
 278
 279 /**
 280  * \brief          Compare signed values
 281  *
 282  * \param X        Left-hand MPI
 283  * \param z        The integer value to compare to
 284  *
 285  * \return         1 if X is greater than z,
 286  *                -1 if X is lesser  than z or
 287  *                 0 if X is equal to z
 288  */
 289 int mpi_cmp_int( const mpi *X, int z );
 290
 291 /**
 292  * \brief          Unsigned addition: X = |A| + |B|
 293  *
 294  * \param X        Destination MPI
 295  * \param A        Left-hand MPI
 296  * \param B        Right-hand MPI
 297  *
 298  * \return         0 if successful,
 299  *                 1 if memory allocation failed
 300  */
 301 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
 302
 303 /**
 304  * \brief          Unsigned substraction: X = |A| - |B|
 305  *
 306  * \param X        Destination MPI
 307  * \param A        Left-hand MPI
 308  * \param B        Right-hand MPI
 309  *
 310  * \return         0 if successful,
 311  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 312  */
 313 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
 314
 315 /**
 316  * \brief          Signed addition: X = A + B
 317  *
 318  * \param X        Destination MPI
 319  * \param A        Left-hand MPI
 320  * \param B        Right-hand MPI
 321  *
 322  * \return         0 if successful,
 323  *                 1 if memory allocation failed
 324  */
 325 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
 326
 327 /**
 328  * \brief          Signed substraction: X = A - B
 329  *
 330  * \param X        Destination MPI
 331  * \param A        Left-hand MPI
 332  * \param B        Right-hand MPI
 333  *
 334  * \return         0 if successful,
 335  *                 1 if memory allocation failed
 336  */
 337 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
 338
 339 /**
 340  * \brief          Signed addition: X = A + b
 341  *
 342  * \param X        Destination MPI
 343  * \param A        Left-hand MPI
 344  * \param b        The integer value to add
 345  *
 346  * \return         0 if successful,
 347  *                 1 if memory allocation failed
 348  */
 349 int mpi_add_int( mpi *X, const mpi *A, int b );
 350
 351 /**
 352  * \brief          Signed substraction: X = A - b
 353  *
 354  * \param X        Destination MPI
 355  * \param A        Left-hand MPI
 356  * \param b        The integer value to subtract
 357  *
 358  * \return         0 if successful,
 359  *                 1 if memory allocation failed
 360  */
 361 int mpi_sub_int( mpi *X, const mpi *A, int b );
 362
 363 /**
 364  * \brief          Baseline multiplication: X = A * B
 365  *
 366  * \param X        Destination MPI
 367  * \param A        Left-hand MPI
 368  * \param B        Right-hand MPI
 369  *
 370  * \return         0 if successful,
 371  *                 1 if memory allocation failed
 372  */
 373 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
 374
 375 /**
 376  * \brief          Baseline multiplication: X = A * b
 377  *                 Note: b is an unsigned integer type, thus
 378  *                 Negative values of b are ignored.
 379  *
 380  * \param X        Destination MPI
 381  * \param A        Left-hand MPI
 382  * \param b        The integer value to multiply with
 383  *
 384  * \return         0 if successful,
 385  *                 1 if memory allocation failed
 386  */
 387 int mpi_mul_int( mpi *X, const mpi *A, t_int b );
 388
 389 /**
 390  * \brief          Division by mpi: A = Q * B + R
 391  *
 392  * \param Q        Destination MPI for the quotient
 393  * \param R        Destination MPI for the rest value
 394  * \param A        Left-hand MPI
 395  * \param B        Right-hand MPI
 396  *
 397  * \return         0 if successful,
 398  *                 1 if memory allocation failed,
 399  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 400  *
 401  * \note           Either Q or R can be NULL.
 402  */
 403 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
 404
 405 /**
 406  * \brief          Division by int: A = Q * b + R
 407  *
 408  * \param Q        Destination MPI for the quotient
 409  * \param R        Destination MPI for the rest value
 410  * \param A        Left-hand MPI
 411  * \param b        Integer to divide by
 412  *
 413  * \return         0 if successful,
 414  *                 1 if memory allocation failed,
 415  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 416  *
 417  * \note           Either Q or R can be NULL.
 418  */
 419 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b );
 420
 421 /**
 422  * \brief          Modulo: R = A mod B
 423  *
 424  * \param R        Destination MPI for the rest value
 425  * \param A        Left-hand MPI
 426  * \param B        Right-hand MPI
 427  *
 428  * \return         0 if successful,
 429  *                 1 if memory allocation failed,
 430  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0,
 431  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0
 432  */
 433 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
 434
 435 /**
 436  * \brief          Modulo: r = A mod b
 437  *
 438  * \param r        Destination t_int
 439  * \param A        Left-hand MPI
 440  * \param b        Integer to divide by
 441  *
 442  * \return         0 if successful,
 443  *                 1 if memory allocation failed,
 444  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0,
 445  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0
 446  */
 447 int mpi_mod_int( t_int *r, const mpi *A, int b );
 448
 449 /**
 450  * \brief          Sliding-window exponentiation: X = A^E mod N
 451  *
 452  * \param X        Destination MPI
 453  * \param A        Left-hand MPI
 454  * \param E        Exponent MPI
 455  * \param N        Modular MPI
 456  * \param _RR      Speed-up MPI used for recalculations
 457  *
 458  * \return         0 if successful,
 459  *                 1 if memory allocation failed,
 460  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
 461  *
 462  * \note           _RR is used to avoid re-computing R*R mod N across
 463  *                 multiple calls, which speeds up things a bit. It can
 464  *                 be set to NULL if the extra performance is unneeded.
 465  */
 466 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
 467
 468 /**
 469  * \brief          Greatest common divisor: G = gcd(A, B)
 470  *
 471  * \param G        Destination MPI
 472  * \param A        Left-hand MPI
 473  * \param B        Right-hand MPI
 474  *
 475  * \return         0 if successful,
 476  *                 1 if memory allocation failed
 477  */
 478 int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
 479
 480 /**
 481  * \brief          Modular inverse: X = A^-1 mod N
 482  *
 483  * \param X        Destination MPI
 484  * \param A        Left-hand MPI
 485  * \param N        Right-hand MPI
 486  *
 487  * \return         0 if successful,
 488  *                 1 if memory allocation failed,
 489  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
 490                    POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
 491  */
 492 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
 493
 494 /**
 495  * \brief          Miller-Rabin primality test
 496  *
 497  * \param X        MPI to check
 498  * \param f_rng    RNG function
 499  * \param p_rng    RNG parameter
 500  *
 501  * \return         0 if successful (probably prime),
 502  *                 1 if memory allocation failed,
 503  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
 504  */
 505 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng );
 506
 507 /**
 508  * \brief          Prime number generation
 509  *
 510  * \param X        Destination MPI
 511  * \param nbits    Required size of X in bits
 512  * \param dh_flag  If 1, then (X-1)/2 will be prime too
 513  * \param f_rng    RNG function
 514  * \param p_rng    RNG parameter
 515  *
 516  * \return         0 if successful (probably prime),
 517  *                 1 if memory allocation failed,
 518  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
 519  */
 520 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
 521                    int (*f_rng)(void *), void *p_rng );
 522
 523 #ifdef __cplusplus
 524 }
 525 #endif
 526
 527 #endif /* bignum.h */