src/src/pdkim/bignum.h

   1 /**
   2  * \file bignum.h
   3  *
   4  *  Copyright (C) 2006-2009, Paul Bakker <polarssl_maintainer at polarssl.org>
   5  *  All rights reserved.
   6  *
   7  *  Joined copyright on original XySSL code with: Christophe Devine
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License along
  20  *  with this program; if not, write to the Free Software Foundation, Inc.,
  21  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  22  */
  23
  24 /* $Cambridge: exim/src/src/pdkim/bignum.h,v 1.3 2009/12/07 13:05:07 tom Exp $ */
  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, 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( 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( mpi *X );
 148
 149 /**
 150  * \brief          Return the total size in bytes
 151  *
 152  * \param X        MPI to use
 153  */
 154 int mpi_size( 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, 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  *
 177  * \note           Call this function with *slen = 0 to obtain the
 178  *                 minimum required buffer size in *slen.
 179  */
 180 int mpi_write_string( mpi *X, int radix, char *s, int *slen );
 181
 182 /**
 183  * \brief          Read X from an opened file
 184  *
 185  * \param X        Destination MPI
 186  * \param radix    Input numeric base
 187  * \param fin      Input file handle
 188  *
 189  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 190  */
 191 int mpi_read_file( mpi *X, int radix, FILE *fin );
 192
 193 /**
 194  * \brief          Write X into an opened file, or stdout if fout is NULL
 195  *
 196  * \param p        Prefix, can be NULL
 197  * \param X        Source MPI
 198  * \param radix    Output numeric base
 199  * \param fout     Output file handle (can be NULL)
 200  *
 201  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 202  *
 203  * \note           Set fout == NULL to print X on the console.
 204  */
 205 int mpi_write_file( const char *p, mpi *X, int radix, FILE *fout );
 206
 207 /**
 208  * \brief          Import X from unsigned binary data, big endian
 209  *
 210  * \param X        Destination MPI
 211  * \param buf      Input buffer
 212  * \param buflen   Input buffer size
 213  *
 214  * \return         0 if successful,
 215  *                 1 if memory allocation failed
 216  */
 217 int mpi_read_binary( mpi *X, unsigned char *buf, int buflen );
 218
 219 /**
 220  * \brief          Export X into unsigned binary data, big endian
 221  *
 222  * \param X        Source MPI
 223  * \param buf      Output buffer
 224  * \param buflen   Output buffer size
 225  *
 226  * \return         0 if successful,
 227  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 228  */
 229 int mpi_write_binary( mpi *X, unsigned char *buf, int buflen );
 230
 231 /**
 232  * \brief          Left-shift: X <<= count
 233  *
 234  * \param X        MPI to shift
 235  * \param count    Amount to shift
 236  *
 237  * \return         0 if successful,
 238  *                 1 if memory allocation failed
 239  */
 240 int mpi_shift_l( mpi *X, int count );
 241
 242 /**
 243  * \brief          Right-shift: X >>= count
 244  *
 245  * \param X        MPI to shift
 246  * \param count    Amount to shift
 247  *
 248  * \return         0 if successful,
 249  *                 1 if memory allocation failed
 250  */
 251 int mpi_shift_r( mpi *X, int count );
 252
 253 /**
 254  * \brief          Compare unsigned values
 255  *
 256  * \param X        Left-hand MPI
 257  * \param Y        Right-hand MPI
 258  *
 259  * \return         1 if |X| is greater than |Y|,
 260  *                -1 if |X| is lesser  than |Y| or
 261  *                 0 if |X| is equal to |Y|
 262  */
 263 int mpi_cmp_abs( mpi *X, mpi *Y );
 264
 265 /**
 266  * \brief          Compare signed values
 267  *
 268  * \param X        Left-hand MPI
 269  * \param Y        Right-hand MPI
 270  *
 271  * \return         1 if X is greater than Y,
 272  *                -1 if X is lesser  than Y or
 273  *                 0 if X is equal to Y
 274  */
 275 int mpi_cmp_mpi( mpi *X, mpi *Y );
 276
 277 /**
 278  * \brief          Compare signed values
 279  *
 280  * \param X        Left-hand MPI
 281  * \param z        The integer value to compare to
 282  *
 283  * \return         1 if X is greater than z,
 284  *                -1 if X is lesser  than z or
 285  *                 0 if X is equal to z
 286  */
 287 int mpi_cmp_int( mpi *X, int z );
 288
 289 /**
 290  * \brief          Unsigned addition: X = |A| + |B|
 291  *
 292  * \param X        Destination MPI
 293  * \param A        Left-hand MPI
 294  * \param B        Right-hand MPI
 295  *
 296  * \return         0 if successful,
 297  *                 1 if memory allocation failed
 298  */
 299 int mpi_add_abs( mpi *X, mpi *A, mpi *B );
 300
 301 /**
 302  * \brief          Unsigned substraction: X = |A| - |B|
 303  *
 304  * \param X        Destination MPI
 305  * \param A        Left-hand MPI
 306  * \param B        Right-hand MPI
 307  *
 308  * \return         0 if successful,
 309  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 310  */
 311 int mpi_sub_abs( mpi *X, mpi *A, mpi *B );
 312
 313 /**
 314  * \brief          Signed addition: X = A + B
 315  *
 316  * \param X        Destination MPI
 317  * \param A        Left-hand MPI
 318  * \param B        Right-hand MPI
 319  *
 320  * \return         0 if successful,
 321  *                 1 if memory allocation failed
 322  */
 323 int mpi_add_mpi( mpi *X, mpi *A, mpi *B );
 324
 325 /**
 326  * \brief          Signed substraction: X = A - B
 327  *
 328  * \param X        Destination MPI
 329  * \param A        Left-hand MPI
 330  * \param B        Right-hand MPI
 331  *
 332  * \return         0 if successful,
 333  *                 1 if memory allocation failed
 334  */
 335 int mpi_sub_mpi( mpi *X, mpi *A, mpi *B );
 336
 337 /**
 338  * \brief          Signed addition: X = A + b
 339  *
 340  * \param X        Destination MPI
 341  * \param A        Left-hand MPI
 342  * \param b        The integer value to add
 343  *
 344  * \return         0 if successful,
 345  *                 1 if memory allocation failed
 346  */
 347 int mpi_add_int( mpi *X, mpi *A, int b );
 348
 349 /**
 350  * \brief          Signed substraction: X = A - b
 351  *
 352  * \param X        Destination MPI
 353  * \param A        Left-hand MPI
 354  * \param b        The integer value to subtract
 355  *
 356  * \return         0 if successful,
 357  *                 1 if memory allocation failed
 358  */
 359 int mpi_sub_int( mpi *X, mpi *A, int b );
 360
 361 /**
 362  * \brief          Baseline multiplication: X = A * B
 363  *
 364  * \param X        Destination MPI
 365  * \param A        Left-hand MPI
 366  * \param B        Right-hand MPI
 367  *
 368  * \return         0 if successful,
 369  *                 1 if memory allocation failed
 370  */
 371 int mpi_mul_mpi( mpi *X, mpi *A, mpi *B );
 372
 373 /**
 374  * \brief          Baseline multiplication: X = A * b
 375  *                 Note: b is an unsigned integer type, thus
 376  *                 Negative values of b are ignored.
 377  *
 378  * \param X        Destination MPI
 379  * \param A        Left-hand MPI
 380  * \param b        The integer value to multiply with
 381  *
 382  * \return         0 if successful,
 383  *                 1 if memory allocation failed
 384  */
 385 int mpi_mul_int( mpi *X, mpi *A, t_int b );
 386
 387 /**
 388  * \brief          Division by mpi: A = Q * B + R
 389  *
 390  * \param Q        Destination MPI for the quotient
 391  * \param R        Destination MPI for the rest value
 392  * \param A        Left-hand MPI
 393  * \param B        Right-hand MPI
 394  *
 395  * \return         0 if successful,
 396  *                 1 if memory allocation failed,
 397  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 398  *
 399  * \note           Either Q or R can be NULL.
 400  */
 401 int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B );
 402
 403 /**
 404  * \brief          Division by int: A = Q * b + R
 405  *
 406  * \param Q        Destination MPI for the quotient
 407  * \param R        Destination MPI for the rest value
 408  * \param A        Left-hand MPI
 409  * \param b        Integer to divide by
 410  *
 411  * \return         0 if successful,
 412  *                 1 if memory allocation failed,
 413  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 414  *
 415  * \note           Either Q or R can be NULL.
 416  */
 417 int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b );
 418
 419 /**
 420  * \brief          Modulo: R = A mod B
 421  *
 422  * \param R        Destination MPI for the rest value
 423  * \param A        Left-hand MPI
 424  * \param B        Right-hand MPI
 425  *
 426  * \return         0 if successful,
 427  *                 1 if memory allocation failed,
 428  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0,
 429  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0
 430  */
 431 int mpi_mod_mpi( mpi *R, mpi *A, mpi *B );
 432
 433 /**
 434  * \brief          Modulo: r = A mod b
 435  *
 436  * \param a        Destination t_int
 437  * \param A        Left-hand MPI
 438  * \param b        Integer to divide by
 439  *
 440  * \return         0 if successful,
 441  *                 1 if memory allocation failed,
 442  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0,
 443  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0
 444  */
 445 int mpi_mod_int( t_int *r, mpi *A, int b );
 446
 447 /**
 448  * \brief          Sliding-window exponentiation: X = A^E mod N
 449  *
 450  * \param X        Destination MPI
 451  * \param A        Left-hand MPI
 452  * \param E        Exponent MPI
 453  * \param N        Modular MPI
 454  * \param _RR      Speed-up MPI used for recalculations
 455  *
 456  * \return         0 if successful,
 457  *                 1 if memory allocation failed,
 458  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
 459  *
 460  * \note           _RR is used to avoid re-computing R*R mod N across
 461  *                 multiple calls, which speeds up things a bit. It can
 462  *                 be set to NULL if the extra performance is unneeded.
 463  */
 464 int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR );
 465
 466 /**
 467  * \brief          Greatest common divisor: G = gcd(A, B)
 468  *
 469  * \param G        Destination MPI
 470  * \param A        Left-hand MPI
 471  * \param B        Right-hand MPI
 472  *
 473  * \return         0 if successful,
 474  *                 1 if memory allocation failed
 475  */
 476 int mpi_gcd( mpi *G, mpi *A, mpi *B );
 477
 478 /**
 479  * \brief          Modular inverse: X = A^-1 mod N
 480  *
 481  * \param X        Destination MPI
 482  * \param A        Left-hand MPI
 483  * \param N        Right-hand MPI
 484  *
 485  * \return         0 if successful,
 486  *                 1 if memory allocation failed,
 487  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
 488                    POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
 489  */
 490 int mpi_inv_mod( mpi *X, mpi *A, mpi *N );
 491
 492 /**
 493  * \brief          Miller-Rabin primality test
 494  *
 495  * \param X        MPI to check
 496  * \param f_rng    RNG function
 497  * \param p_rng    RNG parameter
 498  *
 499  * \return         0 if successful (probably prime),
 500  *                 1 if memory allocation failed,
 501  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
 502  */
 503 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng );
 504
 505 /**
 506  * \brief          Prime number generation
 507  *
 508  * \param X        Destination MPI
 509  * \param nbits    Required size of X in bits
 510  * \param dh_flag  If 1, then (X-1)/2 will be prime too
 511  * \param f_rng    RNG function
 512  * \param p_rng    RNG parameter
 513  *
 514  * \return         0 if successful (probably prime),
 515  *                 1 if memory allocation failed,
 516  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
 517  */
 518 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
 519                    int (*f_rng)(void *), void *p_rng );
 520
 521 #ifdef __cplusplus
 522 }
 523 #endif
 524
 525 #endif /* bignum.h */