mpi.h (12302B)
1 /* 2 * mpi.h 3 * 4 * Arbitrary precision integer arithmetic library 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 9 10 #ifndef _H_MPI_ 11 #define _H_MPI_ 12 13 #include "mpi-config.h" 14 15 #include "seccomon.h" 16 SEC_BEGIN_PROTOS 17 18 #if MP_DEBUG 19 #undef MP_IOFUNC 20 #define MP_IOFUNC 1 21 #endif 22 23 #if MP_IOFUNC 24 #include <stdio.h> 25 #include <ctype.h> 26 #endif 27 28 #include <limits.h> 29 30 #if defined(BSDI) 31 #undef ULLONG_MAX 32 #endif 33 34 #include <sys/types.h> 35 36 #define MP_NEG 1 37 #define MP_ZPOS 0 38 39 #define MP_OKAY 0 /* no error, all is well */ 40 #define MP_YES 0 /* yes (boolean result) */ 41 #define MP_NO -1 /* no (boolean result) */ 42 #define MP_MEM -2 /* out of memory */ 43 #define MP_RANGE -3 /* argument out of range */ 44 #define MP_BADARG -4 /* invalid parameter */ 45 #define MP_UNDEF -5 /* answer is undefined */ 46 #define MP_LAST_CODE MP_UNDEF 47 48 /* Comparison constants */ 49 #define MP_LT -1 50 #define MP_EQ 0 51 #define MP_GT 1 52 53 typedef unsigned int mp_sign; 54 typedef unsigned int mp_size; 55 typedef int mp_err; 56 57 #define MP_32BIT_MAX 4294967295U 58 59 #if !defined(ULONG_MAX) 60 #error "ULONG_MAX not defined" 61 #elif !defined(UINT_MAX) 62 #error "UINT_MAX not defined" 63 #elif !defined(USHRT_MAX) 64 #error "USHRT_MAX not defined" 65 #endif 66 67 #if defined(ULLONG_MAX) /* C99, Solaris */ 68 #define MP_ULONG_LONG_MAX ULLONG_MAX 69 /* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */ 70 #elif defined(ULONG_LONG_MAX) /* HPUX */ 71 #define MP_ULONG_LONG_MAX ULONG_LONG_MAX 72 #elif defined(ULONGLONG_MAX) /* AIX */ 73 #define MP_ULONG_LONG_MAX ULONGLONG_MAX 74 #endif 75 76 /* We only use unsigned long for mp_digit iff long is more than 32 bits. */ 77 #if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX 78 typedef unsigned long mp_digit; 79 #define MP_DIGIT_MAX ULONG_MAX 80 #define MP_DIGIT_FMT "%016lX" /* printf() format for 1 digit */ 81 #define MP_HALF_DIGIT_MAX UINT_MAX 82 #undef MP_NO_MP_WORD 83 #define MP_NO_MP_WORD 1 84 #undef MP_USE_LONG_DIGIT 85 #define MP_USE_LONG_DIGIT 1 86 #undef MP_USE_LONG_LONG_DIGIT 87 88 #elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX) 89 typedef unsigned long long mp_digit; 90 #define MP_DIGIT_MAX MP_ULONG_LONG_MAX 91 #define MP_DIGIT_FMT "%016llX" /* printf() format for 1 digit */ 92 #define MP_HALF_DIGIT_MAX UINT_MAX 93 #undef MP_NO_MP_WORD 94 #define MP_NO_MP_WORD 1 95 #undef MP_USE_LONG_LONG_DIGIT 96 #define MP_USE_LONG_LONG_DIGIT 1 97 #undef MP_USE_LONG_DIGIT 98 99 #else 100 typedef unsigned int mp_digit; 101 #define MP_DIGIT_MAX UINT_MAX 102 #define MP_DIGIT_FMT "%08X" /* printf() format for 1 digit */ 103 #define MP_HALF_DIGIT_MAX USHRT_MAX 104 #undef MP_USE_UINT_DIGIT 105 #define MP_USE_UINT_DIGIT 1 106 #undef MP_USE_LONG_LONG_DIGIT 107 #undef MP_USE_LONG_DIGIT 108 #endif 109 110 #if !defined(MP_NO_MP_WORD) 111 #if defined(MP_USE_UINT_DIGIT) && \ 112 (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX)) 113 114 #if (ULONG_MAX > UINT_MAX) 115 typedef unsigned long mp_word; 116 typedef long mp_sword; 117 #define MP_WORD_MAX ULONG_MAX 118 119 #else 120 typedef unsigned long long mp_word; 121 typedef long long mp_sword; 122 #define MP_WORD_MAX MP_ULONG_LONG_MAX 123 #endif 124 125 #else 126 #define MP_NO_MP_WORD 1 127 #endif 128 #endif /* !defined(MP_NO_MP_WORD) */ 129 130 #if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD) 131 typedef unsigned int mp_word; 132 typedef int mp_sword; 133 #define MP_WORD_MAX UINT_MAX 134 #endif 135 136 #define MP_DIGIT_SIZE sizeof(mp_digit) 137 #define MP_DIGIT_BIT (CHAR_BIT * MP_DIGIT_SIZE) 138 #define MP_WORD_BIT (CHAR_BIT * sizeof(mp_word)) 139 #define MP_RADIX (1 + (mp_word)MP_DIGIT_MAX) 140 141 #define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT / 2) 142 #define MP_HALF_RADIX (1 + (mp_digit)MP_HALF_DIGIT_MAX) 143 /* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named 144 ** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's 145 ** consistent with the other _HALF_ names. 146 */ 147 148 /* Macros for accessing the mp_int internals */ 149 #define MP_SIGN(MP) ((MP)->sign) 150 #define MP_USED(MP) ((MP)->used) 151 #define MP_ALLOC(MP) ((MP)->alloc) 152 #define MP_DIGITS(MP) ((MP)->dp) 153 #define MP_DIGIT(MP, N) (MP)->dp[(N)] 154 155 /* This defines the maximum I/O base (minimum is 2) */ 156 #define MP_MAX_RADIX 64 157 158 /* Constant Time Macros on mp_digits */ 159 #define MP_CT_HIGH_TO_LOW(x) ((mp_digit)((mp_digit)(x) >> (MP_DIGIT_BIT - 1))) 160 #define MP_CT_TRUE ((mp_digit)1) 161 #define MP_CT_FALSE ((mp_digit)0) 162 163 /* basic zero and non zero tests */ 164 #define MP_CT_NOT_ZERO(x) (MP_CT_HIGH_TO_LOW(((x) | (((mp_digit)0) - (x))))) 165 #define MP_CT_ZERO(x) (MP_CT_TRUE ^ MP_CT_HIGH_TO_LOW(((x) | (((mp_digit)0) - (x))))) 166 167 /* basic constant-time helper macro for equalities and inequalities. 168 * The inequalities will produce incorrect results if 169 * abs(a-b) >= MP_DIGIT_SIZE/2. This can be avoided if unsigned values stay 170 * within the range 0-MP_DIGIT_MAX/2. */ 171 #define MP_CT_EQ(a, b) MP_CT_ZERO(((a) ^ (b))) 172 #define MP_CT_NE(a, b) MP_CT_NOT_ZERO(((a) ^ (b))) 173 #define MP_CT_GT(a, b) MP_CT_HIGH_TO_LOW((b) - (a)) 174 #define MP_CT_LT(a, b) MP_CT_HIGH_TO_LOW((a) - (b)) 175 #define MP_CT_GE(a, b) (MP_CT_TRUE ^ MP_CT_LT(a, b)) 176 #define MP_CT_LE(a, b) (MP_CT_TRUE ^ MP_CT_GT(a, b)) 177 178 /* use constant time result to select a boolean value 179 * or an mp digit depending on the args */ 180 #define MP_CT_SEL(m, l, r) ((r) ^ ((m) & ((r) ^ (l)))) 181 #define MP_CT_SELB(m, l, r) MP_CT_SEL(m, l, r) /* mask, l and r are booleans */ 182 #define MP_CT_SEL_DIGIT(m, l, r) MP_CT_SEL(m, l, r) /*mask, l, and r are mp_digit */ 183 184 /* full inequalities that work with full mp_digit values */ 185 #define MP_CT_OVERFLOW(a, b, c, d) \ 186 MP_CT_SELB(MP_CT_HIGH_TO_LOW((a) ^ (b)), \ 187 (MP_CT_HIGH_TO_LOW(d)), c) 188 #define MP_CT_LTU(a, b) MP_CT_OVERFLOW(a, b, MP_CT_LT(a, b), b) 189 190 typedef struct { 191 mp_sign sign; /* sign of this quantity */ 192 mp_size alloc; /* how many digits allocated */ 193 mp_size used; /* how many digits used */ 194 mp_digit *dp; /* the digits themselves */ 195 } mp_int; 196 197 /* Default precision */ 198 mp_size mp_get_prec(void); 199 void mp_set_prec(mp_size prec); 200 201 /* Memory management */ 202 mp_err mp_init(mp_int *mp); 203 mp_err mp_init_size(mp_int *mp, mp_size prec); 204 mp_err mp_init_copy(mp_int *mp, const mp_int *from); 205 mp_err mp_copy(const mp_int *from, mp_int *to); 206 void mp_exch(mp_int *mp1, mp_int *mp2); 207 void mp_clear(mp_int *mp); 208 void mp_zero(mp_int *mp); 209 void mp_set(mp_int *mp, mp_digit d); 210 mp_err mp_set_int(mp_int *mp, long z); 211 #define mp_set_long(mp, z) mp_set_int(mp, z) 212 mp_err mp_set_ulong(mp_int *mp, unsigned long z); 213 214 /* Single digit arithmetic */ 215 mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b); 216 mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b); 217 mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b); 218 mp_err mp_mul_2(const mp_int *a, mp_int *c); 219 mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r); 220 mp_err mp_div_2(const mp_int *a, mp_int *c); 221 mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c); 222 223 /* Sign manipulations */ 224 mp_err mp_abs(const mp_int *a, mp_int *b); 225 mp_err mp_neg(const mp_int *a, mp_int *b); 226 227 /* Full arithmetic */ 228 mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c); 229 mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c); 230 mp_err mp_subCT(const mp_int *a, mp_int *b, mp_int *c, mp_digit *borrow); 231 mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c); 232 mp_err mp_mulCT(mp_int *a, mp_int *b, mp_int *c, mp_size setSize); 233 #if MP_SQUARE 234 mp_err mp_sqr(const mp_int *a, mp_int *b); 235 #else 236 #define mp_sqr(a, b) mp_mul(a, a, b) 237 #endif 238 mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r); 239 mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r); 240 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); 241 mp_err mp_2expt(mp_int *a, mp_digit k); 242 243 /* Modular arithmetic */ 244 #if MP_MODARITH 245 mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c); 246 mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c); 247 mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 248 mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 249 mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 250 #if MP_SQUARE 251 mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c); 252 #else 253 #define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c) 254 #endif 255 mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); 256 mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c); 257 #endif /* MP_MODARITH */ 258 259 /* montgomery math */ 260 mp_err mp_to_mont(const mp_int *x, const mp_int *N, mp_int *xMont); 261 mp_digit mp_calculate_mont_n0i(const mp_int *N); 262 mp_err mp_reduceCT(const mp_int *a, const mp_int *m, mp_digit n0i, mp_int *ct); 263 mp_err mp_mulmontmodCT(mp_int *a, mp_int *b, const mp_int *m, mp_digit n0i, mp_int *c); 264 265 /* Comparisons */ 266 int mp_cmp_z(const mp_int *a); 267 int mp_cmp_d(const mp_int *a, mp_digit d); 268 int mp_cmp(const mp_int *a, const mp_int *b); 269 int mp_cmp_mag(const mp_int *a, const mp_int *b); 270 int mp_isodd(const mp_int *a); 271 int mp_iseven(const mp_int *a); 272 mp_err mp_selectCT(mp_digit cond, const mp_int *a, const mp_int *b, mp_int *ret); 273 274 /* Number theoretic */ 275 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); 276 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); 277 mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y); 278 mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c); 279 mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c); 280 281 /* Input and output */ 282 #if MP_IOFUNC 283 void mp_print(mp_int *mp, FILE *ofp); 284 #endif /* end MP_IOFUNC */ 285 286 /* Base conversion */ 287 mp_err mp_read_raw(mp_int *mp, char *str, int len); 288 int mp_raw_size(mp_int *mp); 289 mp_err mp_toraw(mp_int *mp, char *str); 290 mp_err mp_read_radix(mp_int *mp, const char *str, int radix); 291 mp_err mp_read_variable_radix(mp_int *a, const char *str, int default_radix); 292 int mp_radix_size(mp_int *mp, int radix); 293 mp_err mp_toradix(mp_int *mp, char *str, int radix); 294 int mp_tovalue(char ch, int r); 295 296 #define mp_tobinary(M, S) mp_toradix((M), (S), 2) 297 #define mp_tooctal(M, S) mp_toradix((M), (S), 8) 298 #define mp_todecimal(M, S) mp_toradix((M), (S), 10) 299 #define mp_tohex(M, S) mp_toradix((M), (S), 16) 300 301 /* Error strings */ 302 const char *mp_strerror(mp_err ec); 303 304 /* Octet string conversion functions */ 305 mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len); 306 unsigned int mp_unsigned_octet_size(const mp_int *mp); 307 mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); 308 mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); 309 mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len); 310 311 /* Miscellaneous */ 312 mp_size mp_trailing_zeros(const mp_int *mp); 313 void freebl_cpuid(unsigned long op, unsigned long *eax, 314 unsigned long *ebx, unsigned long *ecx, 315 unsigned long *edx); 316 mp_err mp_cswap(mp_digit condition, mp_int *a, mp_int *b, mp_size numdigits); 317 318 #define MP_CHECKOK(x) \ 319 if (MP_OKAY > (res = (x))) \ 320 goto CLEANUP 321 #define MP_CHECKERR(x) \ 322 if (MP_OKAY > (res = (x))) \ 323 goto CLEANUP 324 325 #define NEG MP_NEG 326 #define ZPOS MP_ZPOS 327 #define DIGIT_MAX MP_DIGIT_MAX 328 #define DIGIT_BIT MP_DIGIT_BIT 329 #define DIGIT_FMT MP_DIGIT_FMT 330 #define RADIX MP_RADIX 331 #define MAX_RADIX MP_MAX_RADIX 332 #define SIGN(MP) MP_SIGN(MP) 333 #define USED(MP) MP_USED(MP) 334 #define ALLOC(MP) MP_ALLOC(MP) 335 #define DIGITS(MP) MP_DIGITS(MP) 336 #define DIGIT(MP, N) MP_DIGIT(MP, N) 337 338 /* Functions which return an mp_err value will NULL-check their arguments via 339 * ARGCHK(condition, return), where the caller is responsible for checking the 340 * mp_err return code. For functions that return an integer type, the caller 341 * has no way to tell if the value is an error code or a legitimate value. 342 * Therefore, ARGMPCHK(condition) will trigger an assertion failure on debug 343 * builds, but no-op in optimized builds. */ 344 #if MP_ARGCHK == 1 345 #define ARGMPCHK(X) /* */ 346 #define ARGCHK(X, Y) \ 347 { \ 348 if (!(X)) { \ 349 return (Y); \ 350 } \ 351 } 352 #elif MP_ARGCHK == 2 353 #include <assert.h> 354 #define ARGMPCHK(X) assert(X) 355 #define ARGCHK(X, Y) assert(X) 356 #else 357 #define ARGMPCHK(X) /* */ 358 #define ARGCHK(X, Y) /* */ 359 #endif 360 361 #ifdef CT_VERIF 362 void mp_taint(mp_int *mp); 363 void mp_untaint(mp_int *mp); 364 #endif 365 366 SEC_END_PROTOS 367 368 #endif /* end _H_MPI_ */