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