src/src/pdkim/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  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License along
  19  *  with this program; if not, write to the Free Software Foundation, Inc.,
  20  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 /* $Cambridge: exim/src/src/pdkim/bignum.h,v 1.2 2009/06/10 07:34:05 tom Exp $ */
  24
  25 #ifndef POLARSSL_BIGNUM_H
  26 #define POLARSSL_BIGNUM_H
  27
  28 #include <stdio.h>
  29
  30 #define POLARSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002
  31 #define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004
  32 #define POLARSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006
  33 #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008
  34 #define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A
  35 #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C
  36 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E
  37
  38 #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
  39
  40 /*
  41  * Define the base integer type, architecture-wise
  42  */
  43 #if defined(POLARSSL_HAVE_INT8)
  44 typedef unsigned char  t_int;
  45 typedef unsigned short t_dbl;
  46 #else
  47 #if defined(POLARSSL_HAVE_INT16)
  48 typedef unsigned short t_int;
  49 typedef unsigned long  t_dbl;
  50 #else
  51   typedef unsigned long t_int;
  52   #if defined(_MSC_VER) && defined(_M_IX86)
  53   typedef unsigned __int64 t_dbl;
  54   #else
  55     #if defined(__amd64__) || defined(__x86_64__)    || \
  56         defined(__ppc64__) || defined(__powerpc64__) || \
  57         defined(__ia64__)  || defined(__alpha__)
  58     typedef unsigned int t_dbl __attribute__((mode(TI)));
  59     #else
  60     typedef unsigned long long t_dbl;
  61     #endif
  62   #endif
  63 #endif
  64 #endif
  65
  66 /**
  67  * \brief          MPI structure
  68  */
  69 typedef struct
  70 {
  71     int s;              /*!<  integer sign      */
  72     int n;              /*!<  total # of limbs  */
  73     t_int *p;           /*!<  pointer to limbs  */
  74 }
  75 mpi;
  76
  77 #ifdef __cplusplus
  78 extern "C" {
  79 #endif
  80
  81 /**
  82  * \brief          Initialize one or more mpi
  83  */
  84 void mpi_init( mpi *X, ... );
  85
  86 /**
  87  * \brief          Unallocate one or more mpi
  88  */
  89 void mpi_free( mpi *X, ... );
  90
  91 /**
  92  * \brief          Enlarge to the specified number of limbs
  93  *
  94  * \return         0 if successful,
  95  *                 1 if memory allocation failed
  96  */
  97 int mpi_grow( mpi *X, int nblimbs );
  98
  99 /**
 100  * \brief          Copy the contents of Y into X
 101  *
 102  * \return         0 if successful,
 103  *                 1 if memory allocation failed
 104  */
 105 int mpi_copy( mpi *X, mpi *Y );
 106
 107 /**
 108  * \brief          Swap the contents of X and Y
 109  */
 110 void mpi_swap( mpi *X, mpi *Y );
 111
 112 /**
 113  * \brief          Set value from integer
 114  *
 115  * \return         0 if successful,
 116  *                 1 if memory allocation failed
 117  */
 118 int mpi_lset( mpi *X, int z );
 119
 120 /**
 121  * \brief          Return the number of least significant bits
 122  */
 123 int mpi_lsb( mpi *X );
 124
 125 /**
 126  * \brief          Return the number of most significant bits
 127  */
 128 int mpi_msb( mpi *X );
 129
 130 /**
 131  * \brief          Return the total size in bytes
 132  */
 133 int mpi_size( mpi *X );
 134
 135 /**
 136  * \brief          Import from an ASCII string
 137  *
 138  * \param X        destination mpi
 139  * \param radix    input numeric base
 140  * \param s        null-terminated string buffer
 141  *
 142  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 143  */
 144 int mpi_read_string( mpi *X, int radix, char *s );
 145
 146 /**
 147  * \brief          Export into an ASCII string
 148  *
 149  * \param X        source mpi
 150  * \param radix    output numeric base
 151  * \param s        string buffer
 152  * \param slen     string buffer size
 153  *
 154  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 155  *
 156  * \note           Call this function with *slen = 0 to obtain the
 157  *                 minimum required buffer size in *slen.
 158  */
 159 int mpi_write_string( mpi *X, int radix, char *s, int *slen );
 160
 161 /**
 162  * \brief          Read X from an opened file
 163  *
 164  * \param X        destination mpi
 165  * \param radix    input numeric base
 166  * \param fin      input file handle
 167  *
 168  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 169  */
 170 int mpi_read_file( mpi *X, int radix, FILE *fin );
 171
 172 /**
 173  * \brief          Write X into an opened file, or stdout
 174  *
 175  * \param p        prefix, can be NULL
 176  * \param X        source mpi
 177  * \param radix    output numeric base
 178  * \param fout     output file handle
 179  *
 180  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
 181  *
 182  * \note           Set fout == NULL to print X on the console.
 183  */
 184 int mpi_write_file( char *p, mpi *X, int radix, FILE *fout );
 185
 186 /**
 187  * \brief          Import X from unsigned binary data, big endian
 188  *
 189  * \param X        destination mpi
 190  * \param buf      input buffer
 191  * \param buflen   input buffer size
 192  *
 193  * \return         0 if successful,
 194  *                 1 if memory allocation failed
 195  */
 196 int mpi_read_binary( mpi *X, unsigned char *buf, int buflen );
 197
 198 /**
 199  * \brief          Export X into unsigned binary data, big endian
 200  *
 201  * \param X        source mpi
 202  * \param buf      output buffer
 203  * \param buflen   output buffer size
 204  *
 205  * \return         0 if successful,
 206  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 207  *
 208  * \note           Call this function with *buflen = 0 to obtain the
 209  *                 minimum required buffer size in *buflen.
 210  */
 211 int mpi_write_binary( mpi *X, unsigned char *buf, int buflen );
 212
 213 /**
 214  * \brief          Left-shift: X <<= count
 215  *
 216  * \return         0 if successful,
 217  *                 1 if memory allocation failed
 218  */
 219 int mpi_shift_l( mpi *X, int count );
 220
 221 /**
 222  * \brief          Right-shift: X >>= count
 223  *
 224  * \return         0 if successful,
 225  *                 1 if memory allocation failed
 226  */
 227 int mpi_shift_r( mpi *X, int count );
 228
 229 /**
 230  * \brief          Compare unsigned values
 231  *
 232  * \return         1 if |X| is greater than |Y|,
 233  *                -1 if |X| is lesser  than |Y| or
 234  *                 0 if |X| is equal to |Y|
 235  */
 236 int mpi_cmp_abs( mpi *X, mpi *Y );
 237
 238 /**
 239  * \brief          Compare signed values
 240  *
 241  * \return         1 if X is greater than Y,
 242  *                -1 if X is lesser  than Y or
 243  *                 0 if X is equal to Y
 244  */
 245 int mpi_cmp_mpi( mpi *X, mpi *Y );
 246
 247 /**
 248  * \brief          Compare signed values
 249  *
 250  * \return         1 if X is greater than z,
 251  *                -1 if X is lesser  than z or
 252  *                 0 if X is equal to z
 253  */
 254 int mpi_cmp_int( mpi *X, int z );
 255
 256 /**
 257  * \brief          Unsigned addition: X = |A| + |B|
 258  *
 259  * \return         0 if successful,
 260  *                 1 if memory allocation failed
 261  */
 262 int mpi_add_abs( mpi *X, mpi *A, mpi *B );
 263
 264 /**
 265  * \brief          Unsigned substraction: X = |A| - |B|
 266  *
 267  * \return         0 if successful,
 268  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 269  */
 270 int mpi_sub_abs( mpi *X, mpi *A, mpi *B );
 271
 272 /**
 273  * \brief          Signed addition: X = A + B
 274  *
 275  * \return         0 if successful,
 276  *                 1 if memory allocation failed
 277  */
 278 int mpi_add_mpi( mpi *X, mpi *A, mpi *B );
 279
 280 /**
 281  * \brief          Signed substraction: X = A - B
 282  *
 283  * \return         0 if successful,
 284  *                 1 if memory allocation failed
 285  */
 286 int mpi_sub_mpi( mpi *X, mpi *A, mpi *B );
 287
 288 /**
 289  * \brief          Signed addition: X = A + b
 290  *
 291  * \return         0 if successful,
 292  *                 1 if memory allocation failed
 293  */
 294 int mpi_add_int( mpi *X, mpi *A, int b );
 295
 296 /**
 297  * \brief          Signed substraction: X = A - b
 298  *
 299  * \return         0 if successful,
 300  *                 1 if memory allocation failed
 301  */
 302 int mpi_sub_int( mpi *X, mpi *A, int b );
 303
 304 /**
 305  * \brief          Baseline multiplication: X = A * B
 306  *
 307  * \return         0 if successful,
 308  *                 1 if memory allocation failed
 309  */
 310 int mpi_mul_mpi( mpi *X, mpi *A, mpi *B );
 311
 312 /**
 313  * \brief          Baseline multiplication: X = A * b
 314  *
 315  * \return         0 if successful,
 316  *                 1 if memory allocation failed
 317  */
 318 int mpi_mul_int( mpi *X, mpi *A, t_int b );
 319
 320 /**
 321  * \brief          Division by mpi: A = Q * B + R
 322  *
 323  * \return         0 if successful,
 324  *                 1 if memory allocation failed,
 325  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 326  *
 327  * \note           Either Q or R can be NULL.
 328  */
 329 int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B );
 330
 331 /**
 332  * \brief          Division by int: A = Q * b + R
 333  *
 334  * \return         0 if successful,
 335  *                 1 if memory allocation failed,
 336  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 337  *
 338  * \note           Either Q or R can be NULL.
 339  */
 340 int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b );
 341
 342 /**
 343  * \brief          Modulo: R = A mod B
 344  *
 345  * \return         0 if successful,
 346  *                 1 if memory allocation failed,
 347  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 348  */
 349 int mpi_mod_mpi( mpi *R, mpi *A, mpi *B );
 350
 351 /**
 352  * \brief          Modulo: r = A mod b
 353  *
 354  * \return         0 if successful,
 355  *                 1 if memory allocation failed,
 356  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 357  */
 358 int mpi_mod_int( t_int *r, mpi *A, int b );
 359
 360 /**
 361  * \brief          Sliding-window exponentiation: X = A^E mod N
 362  *
 363  * \return         0 if successful,
 364  *                 1 if memory allocation failed,
 365  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
 366  *
 367  * \note           _RR is used to avoid re-computing R*R mod N across
 368  *                 multiple calls, which speeds up things a bit. It can
 369  *                 be set to NULL if the extra performance is unneeded.
 370  */
 371 int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR );
 372
 373 /**
 374  * \brief          Greatest common divisor: G = gcd(A, B)
 375  *
 376  * \return         0 if successful,
 377  *                 1 if memory allocation failed
 378  */
 379 int mpi_gcd( mpi *G, mpi *A, mpi *B );
 380
 381 /**
 382  * \brief          Modular inverse: X = A^-1 mod N
 383  *
 384  * \return         0 if successful,
 385  *                 1 if memory allocation failed,
 386  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
 387  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
 388  */
 389 int mpi_inv_mod( mpi *X, mpi *A, mpi *N );
 390
 391 #ifdef __cplusplus
 392 }
 393 #endif
 394
 395 #endif /* bignum.h */