include/tropicssl/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 TROPICSSL_BIGNUM_H
  36 #define TROPICSSL_BIGNUM_H
  37
  38 #include <stdio.h>
  39
  40 #define TROPICSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002
  41 #define TROPICSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004
  42 #define TROPICSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006
  43 #define TROPICSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008
  44 #define TROPICSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A
  45 #define TROPICSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C
  46 #define TROPICSSL_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(TROPICSSL_HAVE_INT8)
  54 typedef unsigned char t_int;
  55 typedef unsigned short t_dbl;
  56 #else
  57 #if defined(TROPICSSL_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         int s;                  /*!<  integer sign      */
  81         int n;                  /*!<  total # of limbs  */
  82         t_int *p;               /*!<  pointer to limbs  */
  83 } mpi;
  84
  85 #ifdef __cplusplus
  86 extern "C" {
  87 #endif
  88
  89         /**
  90          * \brief          Initialize one MPI
  91          */
  92         void mpi_init(mpi * X);
  93
  94         /**
  95          * \brief          Unallocate one MPI
  96          */
  97         void mpi_free(mpi * X);
  98
  99         /**
 100          * \brief          Enlarge to the specified number of limbs
 101          *
 102          * \return         0 if successful,
 103          *                 1 if memory allocation failed
 104          */
 105         int mpi_grow(mpi * X, int nblimbs);
 106
 107         /**
 108          * \brief          Copy the contents of Y into X
 109          *
 110          * \return         0 if successful,
 111          *                 1 if memory allocation failed
 112          */
 113         int mpi_copy(mpi * X, const mpi * Y);
 114
 115         /**
 116          * \brief          Swap the contents of X and Y
 117          */
 118         void mpi_swap(mpi * X, mpi * Y);
 119
 120         /**
 121          * \brief          Set value from integer
 122          *
 123          * \return         0 if successful,
 124          *                 1 if memory allocation failed
 125          */
 126         int mpi_lset(mpi * X, int z);
 127
 128         /**
 129          * \brief          Return the number of least significant bits
 130          */
 131         int mpi_lsb(const mpi * X);
 132
 133         /**
 134          * \brief          Return the number of most significant bits
 135          */
 136         int mpi_msb(const mpi * X);
 137
 138         /**
 139          * \brief          Return the total size in bytes
 140          */
 141         int mpi_size(const mpi * X);
 142
 143         /**
 144          * \brief          Import from an ASCII string
 145          *
 146          * \param X        destination mpi
 147          * \param radix    input numeric base
 148          * \param s        null-terminated string buffer
 149          *
 150          * \return         0 if successful, or an TROPICSSL_ERR_MPI_XXX error code
 151          */
 152         int mpi_read_string(mpi * X, int radix, const char *s);
 153
 154         /**
 155          * \brief          Export into an ASCII string
 156          *
 157          * \param X        source mpi
 158          * \param radix    output numeric base
 159          * \param s        string buffer
 160          * \param slen     string buffer size
 161          *
 162          * \return         0 if successful, or an TROPICSSL_ERR_MPI_XXX error code
 163          *
 164          * \note           Call this function with *slen = 0 to obtain the
 165          *                 minimum required buffer size in *slen.
 166          */
 167         int mpi_write_string(const mpi * X, int radix, char *s, int *slen);
 168
 169         /**
 170          * \brief          Read X from an opened file
 171          *
 172          * \param X        destination mpi
 173          * \param radix    input numeric base
 174          * \param fin      input file handle
 175          *
 176          * \return         0 if successful, or an TROPICSSL_ERR_MPI_XXX error code
 177          */
 178         int mpi_read_file(mpi * X, int radix, FILE * fin);
 179
 180         /**
 181          * \brief          Write X into an opened file, or stdout
 182          *
 183          * \param p        prefix, can be NULL
 184          * \param X        source mpi
 185          * \param radix    output numeric base
 186          * \param fout     output file handle
 187          *
 188          * \return         0 if successful, or an TROPICSSL_ERR_MPI_XXX error code
 189          *
 190          * \note           Set fout == NULL to print X on the console.
 191          */
 192         int mpi_write_file(const char *p, const mpi * X, int radix, FILE * fout);
 193
 194         /**
 195          * \brief          Import X from unsigned binary data, big endian
 196          *
 197          * \param X        destination mpi
 198          * \param buf      input buffer
 199          * \param buflen   input buffer size
 200          *
 201          * \return         0 if successful,
 202          *                 1 if memory allocation failed
 203          */
 204         int mpi_read_binary(mpi * X, const unsigned char *buf, int buflen);
 205
 206         /**
 207          * \brief          Export X into unsigned binary data, big endian
 208          *
 209          * \param X        source mpi
 210          * \param buf      output buffer
 211          * \param buflen   output buffer size
 212          *
 213          * \return         0 if successful,
 214          *                 TROPICSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 215          *
 216          * \note           Call this function with *buflen = 0 to obtain the
 217          *                 minimum required buffer size in *buflen.
 218          */
 219         int mpi_write_binary(const mpi * X, unsigned char *buf, int buflen);
 220
 221         /**
 222          * \brief          Left-shift: X <<= count
 223          *
 224          * \return         0 if successful,
 225          *                 1 if memory allocation failed
 226          */
 227         int mpi_shift_l(mpi * X, int count);
 228
 229         /**
 230          * \brief          Right-shift: X >>= count
 231          *
 232          * \return         0 if successful,
 233          *                 1 if memory allocation failed
 234          */
 235         int mpi_shift_r(mpi * X, int count);
 236
 237         /**
 238          * \brief          Compare unsigned values
 239          *
 240          * \return         1 if |X| is greater than |Y|,
 241          *                -1 if |X| is lesser  than |Y| or
 242          *                 0 if |X| is equal to |Y|
 243          */
 244         int mpi_cmp_abs(const mpi * X, const mpi * Y);
 245
 246         /**
 247          * \brief          Compare signed values
 248          *
 249          * \return         1 if X is greater than Y,
 250          *                -1 if X is lesser  than Y or
 251          *                 0 if X is equal to Y
 252          */
 253         int mpi_cmp_mpi(const mpi * X, const mpi * Y);
 254
 255         /**
 256          * \brief          Compare signed values
 257          *
 258          * \return         1 if X is greater than z,
 259          *                -1 if X is lesser  than z or
 260          *                 0 if X is equal to z
 261          */
 262         int mpi_cmp_int(const mpi * X, int z);
 263
 264         /**
 265          * \brief          Unsigned addition: X = |A| + |B|
 266          *
 267          * \return         0 if successful,
 268          *                 1 if memory allocation failed
 269          */
 270         int mpi_add_abs(mpi * X, const mpi * A, const mpi * B);
 271
 272         /**
 273          * \brief          Unsigned substraction: X = |A| - |B|
 274          *
 275          * \return         0 if successful,
 276          *                 TROPICSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 277          */
 278         int mpi_sub_abs(mpi * X, const mpi * A, const mpi * B);
 279
 280         /**
 281          * \brief          Signed addition: X = A + B
 282          *
 283          * \return         0 if successful,
 284          *                 1 if memory allocation failed
 285          */
 286         int mpi_add_mpi(mpi * X, const mpi * A, const mpi * B);
 287
 288         /**
 289          * \brief          Signed substraction: X = A - B
 290          *
 291          * \return         0 if successful,
 292          *                 1 if memory allocation failed
 293          */
 294         int mpi_sub_mpi(mpi * X, const mpi * A, const mpi * B);
 295
 296         /**
 297          * \brief          Signed addition: X = A + b
 298          *
 299          * \return         0 if successful,
 300          *                 1 if memory allocation failed
 301          */
 302         int mpi_add_int(mpi * X, const mpi * A, int b);
 303
 304         /**
 305          * \brief          Signed substraction: X = A - b
 306          *
 307          * \return         0 if successful,
 308          *                 1 if memory allocation failed
 309          */
 310         int mpi_sub_int(mpi * X, const mpi * A, int 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_mpi(mpi * X, const mpi * A, const mpi * B);
 319
 320         /**
 321          * \brief          Baseline multiplication: X = A * b
 322          *
 323          * \return         0 if successful,
 324          *                 1 if memory allocation failed
 325          */
 326         int mpi_mul_int(mpi * X, const mpi * A, t_int b);
 327
 328         /**
 329          * \brief          Division by mpi: A = Q * B + R
 330          *
 331          * \return         0 if successful,
 332          *                 1 if memory allocation failed,
 333          *                 TROPICSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 334          *
 335          * \note           Either Q or R can be NULL.
 336          */
 337         int mpi_div_mpi(mpi * Q, mpi * R, const mpi * A, const mpi * B);
 338
 339         /**
 340          * \brief          Division by int: A = Q * b + R
 341          *
 342          * \return         0 if successful,
 343          *                 1 if memory allocation failed,
 344          *                 TROPICSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 345          *
 346          * \note           Either Q or R can be NULL.
 347          */
 348         int mpi_div_int(mpi * Q, mpi * R, const mpi * A, int b);
 349
 350         /**
 351          * \brief          Modulo: R = A mod B
 352          *
 353          * \return         0 if successful,
 354          *                 1 if memory allocation failed,
 355          *                 TROPICSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
 356          */
 357         int mpi_mod_mpi(mpi * R, const mpi * A, const mpi * B);
 358
 359         /**
 360          * \brief          Modulo: r = A mod b
 361          *
 362          * \return         0 if successful,
 363          *                 1 if memory allocation failed,
 364          *                 TROPICSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
 365          */
 366         int mpi_mod_int(t_int * r, const mpi * A, int b);
 367
 368         /**
 369          * \brief          Sliding-window exponentiation: X = A^E mod N
 370          *
 371          * \return         0 if successful,
 372          *                 1 if memory allocation failed,
 373          *                 TROPICSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
 374          *
 375          * \note           _RR is used to avoid re-computing R*R mod N across
 376          *                 multiple calls, which speeds up things a bit. It can
 377          *                 be set to NULL if the extra performance is unneeded.
 378          */
 379         int mpi_exp_mod(mpi * X, const mpi * A, const mpi * E, const mpi * N, mpi * _RR);
 380
 381         /**
 382          * \brief          Greatest common divisor: G = gcd(A, B)
 383          *
 384          * \return         0 if successful,
 385          *                 1 if memory allocation failed
 386          */
 387         int mpi_gcd(mpi * G, const mpi * A, const mpi * B);
 388
 389         /**
 390          * \brief          Modular inverse: X = A^-1 mod N
 391          *
 392          * \return         0 if successful,
 393          *                 1 if memory allocation failed,
 394          *                 TROPICSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
 395          *                 TROPICSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
 396          */
 397         int mpi_inv_mod(mpi * X, const mpi * A, const mpi * N);
 398
 399         /**
 400          * \brief          Miller-Rabin primality test
 401          *
 402          * \return         0 if successful (probably prime),
 403          *                 1 if memory allocation failed,
 404          *                 TROPICSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
 405          */
 406         int mpi_is_prime(mpi * X, int (*f_rng) (void *), void *p_rng);
 407
 408         /**
 409          * \brief          Prime number generation
 410          *
 411          * \param X        destination mpi
 412          * \param nbits    required size of X in bits
 413          * \param dh_flag  if 1, then (X-1)/2 will be prime too
 414          * \param f_rng    RNG function
 415          * \param p_rng    RNG parameter
 416          *
 417          * \return         0 if successful (probably prime),
 418          *                 1 if memory allocation failed,
 419          *                 TROPICSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
 420          */
 421         int mpi_gen_prime(mpi * X, int nbits, int dh_flag,
 422                           int (*f_rng) (void *), void *p_rng);
 423
 424         /**
 425          * \brief          Checkup routine
 426          *
 427          * \return         0 if successful, or 1 if the test failed
 428          */
 429         int mpi_self_test(int verbose);
 430
 431 #ifdef __cplusplus
 432 }
 433 #endif
 434 #endif                          /* bignum.h */