dropbear: mpi.c comparison

comparison mpi.c @ 15:6362d3854bb4 libtomcrypt-orig

0.96 release of LibTomCrypt

author	Matt Johnston <matt@ucc.asn.au>
date	Tue, 15 Jun 2004 14:07:21 +0000
parents	7faae8f46238
children	5d99163f7e32

comparison

equal deleted inserted replaced

-:7faae8f46238
+:6362d3854bb4
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 static const struct {
 int code;
 char *msg;
 } msgs[] = {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes the modular inverse via binary extended euclidean algorithm,
 * that is c = 1/a mod b
 *
 * Based on mp_invmod except this is optimized for the case where b is
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes xR**-1 == x (mod N) via Montgomery Reduction
 *
 * This is an optimized implementation of mp_montgomery_reduce
 * which uses the comba method to quickly calculate the columns of the
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Fast (comba) multiplier
 *
 * This is the fast column-array [comba] multiplier.  It is
 * designed to compute the columns of the product first
 }
 }
 /* setup dest */
-olduse = c->used;
+olduse  = c->used;
 c->used = digs;
 {
 register mp_digit *tmpc;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* this is a modified version of fast_s_mp_mul_digs that only produces
 * output digits *above* digs.  See the comments for fast_s_mp_mul_digs
 * to see how it works.
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* fast squaring
 *
 * This is the comba method where the columns of the product
 * are computed first then the carries are computed.  This
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes a = 2**b
 *
 * Simple algorithm which zeroes the int, grows it then just sets one bit
 * as required.
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* b = |a|
 *
 * Simple function copies the input and fixes the sign to positive
 */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* high level addition (handles signs) */
 int mp_add (mp_int * a, mp_int * b, mp_int * c)
 {
 int     sa, sb, res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* single digit addition */
 int
 mp_add_d (mp_int * a, mp_digit b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* d = a + b (mod c) */
 int
 mp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* AND two ints together */
 int
 mp_and (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* trim unused digits
 *
 * This is used to ensure that leading zero digits are
 * trimed and the leading "used" digit will be non-zero
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* clear one (frees)  */
 void
 mp_clear (mp_int * a)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 #include <stdarg.h>
 void mp_clear_multi(mp_int *mp, ...)
 {
 mp_int* next_mp = mp;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* compare two ints (signed)*/
 int
 mp_cmp (mp_int * a, mp_int * b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* compare a digit */
 int mp_cmp_d(mp_int * a, mp_digit b)
 {
 /* compare based on sign */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* compare maginitude of two ints (unsigned) */
 int mp_cmp_mag (mp_int * a, mp_int * b)
 {
 int     n;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 static const int lnz[16] = {
 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
 };
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* copy, b = a */
 int
 mp_copy (mp_int * a, mp_int * b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* returns the number of bits in an int */
 int
 mp_count_bits (mp_int * a)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* integer signed division.
 * c*b + d == a [e.g. a/b, c=quotient, d=remainder]
 * HAC pp.598 Algorithm 14.20
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* b = a/2 */
 int mp_div_2(mp_int * a, mp_int * b)
 {
 int     x, res, oldused;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* shift right by a certain bit count (store quotient in c, optional remainder in d) */
 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
 {
 mp_digit D, r, rr;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* divide by three (based on routine from MPI and the GMP manual) */
 int
 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 static int s_is_power_of_two(mp_digit b, int *p)
 {
 int x;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* determines if a number is a valid DR modulus */
 int mp_dr_is_modulus(mp_int *a)
 {
 int ix;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
 *
 * Based on algorithm from the paper
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* determines the setup value */
 void mp_dr_setup(mp_int *a, mp_digit *d)
 {
 /* the casts are required if DIGIT_BIT is one less than
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* swap the elements of two integers, for cases where you can't simply swap the
 * mp_int pointers around
 */
 void
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* calculate c = a**b  using a square-multiply algorithm */
 int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
 {
 int     res, x;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* this is a shell function that calls either the normal or Montgomery
 * exptmod functions.  Originally the call to the montgomery code was
 * embedded in the normal function but that wasted alot of stack space
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85
 *
 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation.
 * The value of k changes based on the size of the exponent.
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Extended euclidean algorithm of (a, b) produces
 a*u1 + b*u2 = u3
 */
 int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3)
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* read a bigint from a file stream in ASCII */
 int mp_fread(mp_int *a, int radix, FILE *stream)
 {
 int err, ch, neg, y;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 int mp_fwrite(mp_int *a, int radix, FILE *stream)
 {
 char *buf;
 int err, len, x;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Greatest Common Divisor using the binary method */
 int mp_gcd (mp_int * a, mp_int * b, mp_int * c)
 {
 mp_int  u, v;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* get the lower 32-bits of an mp_int */
 unsigned long mp_get_int(mp_int * a)
 {
 int i;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* grow as required */
 int mp_grow (mp_int * a, int size)
 {
 int     i;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* init a new bigint */
 int mp_init (mp_int * a)
 {
 /* allocate memory required and clear it */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* creates "a" then copies b into it */
 int mp_init_copy (mp_int * a, mp_int * b)
 {
 int     res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 #include <stdarg.h>
 int mp_init_multi(mp_int *mp, ...)
 {
 mp_err res = MP_OKAY;      /* Assume ok until proven otherwise */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* initialize and set a digit */
 int mp_init_set (mp_int * a, mp_digit b)
 {
 int err;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* initialize and set a digit */
 int mp_init_set_int (mp_int * a, unsigned long b)
 {
 int err;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* init an mp_init for a given size */
 int mp_init_size (mp_int * a, int size)
 {
 /* pad size so there are always extra digits */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* hac 14.61, pp608 */
 int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
 {
 mp_int  x, y, u, v, A, B, C, D;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Check if remainders are possible squares - fast exclude non-squares */
 static const char rem_128[128] = {
 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes the jacobi c = (a | n) (or Legendre if n is prime)
 * HAC pp. 73 Algorithm 2.149
 */
 int mp_jacobi (mp_int * a, mp_int * p, int *c)
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* c = |a| * |b| using Karatsuba Multiplication using
 * three half size multiplications
 *
 * Let B represent the radix [e.g. 2**DIGIT_BIT] and
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Karatsuba squaring, computes b = a*a using three
 * half size squarings
 *
 * See comments of mp_karatsuba_mul for details.  It
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes least common multiple as |a*b|/(a, b) */
 int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
 {
 int     res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* shift left a certain amount of digits */
 int mp_lshd (mp_int * a, int b)
 {
 int     x, res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* c = a mod b, 0 <= c < b */
 int
 mp_mod (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* calc a value mod 2**b */
 int
 mp_mod_2d (mp_int * a, int b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 int
 mp_mod_d (mp_int * a, mp_digit b, mp_digit * c)
 {
 return mp_div_d(a, b, NULL, c);
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* calculates a = B^n mod b for Montgomery reduction
 * Where B is the base [e.g. 2^DIGIT_BIT].
 * B^n mod b is computed by first computing
 * A = B^(n-1) which doesn't require a reduction but a simple OR.
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
 int
 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* setups the montgomery reduction stuff */
 int
 mp_montgomery_setup (mp_int * n, mp_digit * rho)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* high level multiplication (handles sign) */
 int mp_mul (mp_int * a, mp_int * b, mp_int * c)
 {
 int     res, neg;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* b = a*2 */
 int mp_mul_2(mp_int * a, mp_int * b)
 {
 int     x, res, oldused;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* shift left by a certain bit count */
 int mp_mul_2d (mp_int * a, int b, mp_int * c)
 {
 mp_digit d;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* multiply by a digit */
 int
 mp_mul_d (mp_int * a, mp_digit b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* d = a * b (mod c) */
 int
 mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* find the n'th root of an integer
 *
 * Result found such that (c)**b <= a and (c+1)**b > a
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* b = -a */
 int mp_neg (mp_int * a, mp_int * b)
 {
 int     res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* OR two ints together */
 int mp_or (mp_int * a, mp_int * b, mp_int * c)
 {
 int     res, ix, px;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* performs one Fermat test.
 *
 * If "a" were prime then b**a == b (mod a) since the order of
 * the multiplicative sub-group would be phi(a) = a-1.  That means
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* determines if an integers is divisible by one
 * of the first PRIME_SIZE primes or not
 *
 * sets result to 0 if not, 1 if yes
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* performs a variable number of rounds of Miller-Rabin
 *
 * Probability of error after t rounds is no more than
 * (1/4)^t when 1 <= t <= PRIME_SIZE
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Miller-Rabin test of "a" to the base of "b" as described in
 * HAC pp. 139 Algorithm 4.24
 *
 * Sets result to 0 if definitely composite or 1 if probably prime.
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* finds the next prime after the number "a" using "t" trials
 * of Miller-Rabin.
 *
 * bbs_style = 1 means the prime must be congruent to 3 mod 4
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* makes a truly random prime of a given size (bits),
 *
 * Flags are as follows:
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* returns size of ASCII reprensentation */
 int mp_radix_size (mp_int * a, int radix, int *size)
 {
 int     res, digs;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* chars used in radix conversions */
 const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
 /* End: bn_mp_radix_smap.c */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* makes a pseudo-random int of a given size */
 int
 mp_rand (mp_int * a, int digits)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* read a string [ASCII] in a given radix */
 int mp_read_radix (mp_int * a, char *str, int radix)
 {
 int     y, res, neg;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* read signed bin, big endian, first byte is 0==positive or 1==negative */
 int
 mp_read_signed_bin (mp_int * a, unsigned char *b, int c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* reads a unsigned char array, assumes the msb is stored first [big endian] */
 int
 mp_read_unsigned_bin (mp_int * a, unsigned char *b, int c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* reduces x mod m, assumes 0 < x < m**2, mu is
 * precomputed via mp_reduce_setup.
 * From HAC pp.604 Algorithm 14.42
 */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* reduces a modulo n where n is of the form 2**p - d */
 int
 mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* determines the setup value */
 int
 mp_reduce_2k_setup(mp_int *a, mp_digit *d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* determines if mp_reduce_2k can be used */
 int mp_reduce_is_2k(mp_int *a)
 {
 int ix, iy, iz, iw;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* pre-calculate the value required for Barrett reduction
 * For a given modulus "b" it calulates the value required in "a"
 */
 int
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* shift right a certain amount of digits */
 void mp_rshd (mp_int * a, int b)
 {
 int     x;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* set to a digit */
 void mp_set (mp_int * a, mp_digit b)
 {
 mp_zero (a);
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* set a 32-bit const */
 int mp_set_int (mp_int * a, unsigned long b)
 {
 int     x, res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* shrink a bignum */
 int mp_shrink (mp_int * a)
 {
 mp_digit *tmp;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* get the size for an signed equivalent */
 int mp_signed_bin_size (mp_int * a)
 {
 return 1 + mp_unsigned_bin_size (a);
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* computes b = a*a */
 int
 mp_sqr (mp_int * a, mp_int * b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* c = a * a (mod b) */
 int
 mp_sqrmod (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* this function is less generic than mp_n_root, simpler and faster */
 int mp_sqrt(mp_int *arg, mp_int *ret)
 {
 int res;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* high level subtraction (handles signs) */
 int
 mp_sub (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* single digit subtraction */
 int
 mp_sub_d (mp_int * a, mp_digit b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* d = a - b (mod c) */
 int
 mp_submod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* store in signed [big endian] format */
 int
 mp_to_signed_bin (mp_int * a, unsigned char *b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* store in unsigned [big endian] format */
 int
 mp_to_unsigned_bin (mp_int * a, unsigned char *b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* multiplication using the Toom-Cook 3-way algorithm */
 int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c)
 {
 mp_int w0, w1, w2, w3, w4, tmp1, tmp2, a0, a1, a2, b0, b1, b2;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* squaring using Toom-Cook 3-way algorithm */
 int
 mp_toom_sqr(mp_int *a, mp_int *b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* stores a bignum as a ASCII string in a given radix (2..64) */
 int mp_toradix (mp_int * a, char *str, int radix)
 {
 int     res, digs;
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* stores a bignum as a ASCII string in a given radix (2..64)
 *
 * Stores upto maxlen-1 chars and always a NULL byte
 */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* get the size for an unsigned equivalent */
 int
 mp_unsigned_bin_size (mp_int * a)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* XOR two ints together */
 int
 mp_xor (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* set to zero */
 void
 mp_zero (mp_int * a)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* this table gives the # of rabin miller trials for a prob of failure lower than 2^-96 */
 static const struct {
 int k, t;
 } sizes[] = {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 const mp_digit __prime_tab[] = {
 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F,
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* reverse an array, used for radix code */
 void
 bn_reverse (unsigned char *s, int len)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* low level addition, based on HAC pp.594, Algorithm 14.7 */
 int
 s_mp_add (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 #ifdef MP_LOW_MEM
 #define TAB_SIZE 32
 #else
 #define TAB_SIZE 256
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* multiplies |a| * |b| and only computes upto digs digits of result
 * HAC pp. 595, Algorithm 14.12  Modified so you can control how
 * many digits of output are created.
 */
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* multiplies |a| * |b| and does not compute the lower digs digits
 * [meant to get the higher part of the product]
 */
 int
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* low level squaring, b = a*a, HAC pp.596-597, Algorithm 14.16 */
 int
 s_mp_sqr (mp_int * a, mp_int * b)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */
 int
 s_mp_sub (mp_int * a, mp_int * b, mp_int * c)
 {
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [email protected], http://math.libtomcrypt.org
 */
-#include <tommath.h>
+#include <ltc_tommath.h>
 /* Known optimal configurations
 CPU                    /Compiler     /MUL CUTOFF/SQR CUTOFF
 -------------------------------------------------------------
-Intel P4               /GCC v3.2     /        70/       108
+Intel P4 Northwood     /GCC v3.3.3   /        59/        81/profiled build
-AMD Athlon XP          /GCC v3.2     /       109/       127
+Intel P4 Northwood     /GCC v3.3.3   /        59/        80/profiled_single build
+Intel P4 Northwood     /ICC v8.0     /        57/        70/profiled build
+Intel P4 Northwood     /ICC v8.0     /        54/        76/profiled_single build
+AMD Athlon XP          /GCC v3.2     /       109/       127/
 */
-/* configured for a AMD XP Thoroughbred core with etc/tune.c */
+int     KARATSUBA_MUL_CUTOFF = 57,      /* Min. number of digits before Karatsuba multiplication is used. */
-int     KARATSUBA_MUL_CUTOFF = 70,      /* Min. number of digits before Karatsuba multiplication is used. */
+KARATSUBA_SQR_CUTOFF = 70,      /* Min. number of digits before Karatsuba squaring is used. */
-KARATSUBA_SQR_CUTOFF = 108,      /* Min. number of digits before Karatsuba squaring is used. */
 TOOM_MUL_CUTOFF      = 350,      /* no optimal values of these are known yet so set em high */
 TOOM_SQR_CUTOFF      = 400;
 /* End: bncore.c */

Mercurial > dropbear

comparison mpi.c @ 15:6362d3854bb4 libtomcrypt-orig