src/xyssl/bignum.h

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