rsaenh: Declare some functions static
Andrew Talbot
andrew.talbot at talbotville.com
Fri Jan 23 13:33:59 CST 2009
Changelog:
rsaenh: Declare some functions static.
diff --git a/dlls/rsaenh/mpi.c b/dlls/rsaenh/mpi.c
index 1a5affd..e8a88d3 100644
--- a/dlls/rsaenh/mpi.c
+++ b/dlls/rsaenh/mpi.c
@@ -1863,6 +1863,304 @@ int mp_exptmod (const mp_int * G, const mp_int * X, mp_int * P, mp_int * Y)
}
}
+/* b = a*2 */
+static int mp_mul_2(const mp_int * a, mp_int * b)
+{
+ int x, res, oldused;
+
+ /* grow to accommodate result */
+ if (b->alloc < a->used + 1) {
+ if ((res = mp_grow (b, a->used + 1)) != MP_OKAY) {
+ return res;
+ }
+ }
+
+ oldused = b->used;
+ b->used = a->used;
+
+ {
+ register mp_digit r, rr, *tmpa, *tmpb;
+
+ /* alias for source */
+ tmpa = a->dp;
+
+ /* alias for dest */
+ tmpb = b->dp;
+
+ /* carry */
+ r = 0;
+ for (x = 0; x < a->used; x++) {
+
+ /* get what will be the *next* carry bit from the
+ * MSB of the current digit
+ */
+ rr = *tmpa >> ((mp_digit)(DIGIT_BIT - 1));
+
+ /* now shift up this digit, add in the carry [from the previous] */
+ *tmpb++ = ((*tmpa++ << ((mp_digit)1)) | r) & MP_MASK;
+
+ /* copy the carry that would be from the source
+ * digit into the next iteration
+ */
+ r = rr;
+ }
+
+ /* new leading digit? */
+ if (r != 0) {
+ /* add a MSB which is always 1 at this point */
+ *tmpb = 1;
+ ++(b->used);
+ }
+
+ /* now zero any excess digits on the destination
+ * that we didn't write to
+ */
+ tmpb = b->dp + b->used;
+ for (x = b->used; x < oldused; x++) {
+ *tmpb++ = 0;
+ }
+ }
+ b->sign = a->sign;
+ return MP_OKAY;
+}
+
+/* setups the montgomery reduction stuff */
+static int
+mp_montgomery_setup (const mp_int * n, mp_digit * rho)
+{
+ mp_digit x, b;
+
+/* fast inversion mod 2**k
+ *
+ * Based on the fact that
+ *
+ * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
+ * => 2*X*A - X*X*A*A = 1
+ * => 2*(1) - (1) = 1
+ */
+ b = n->dp[0];
+
+ if ((b & 1) == 0) {
+ return MP_VAL;
+ }
+
+ x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
+ x *= 2 - b * x; /* here x*a==1 mod 2**8 */
+ x *= 2 - b * x; /* here x*a==1 mod 2**16 */
+ x *= 2 - b * x; /* here x*a==1 mod 2**32 */
+
+ /* rho = -1/m mod b */
+ *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;
+
+ return MP_OKAY;
+}
+
+/*
+ * computes a = B**n mod b without division or multiplication useful for
+ * normalizing numbers in a Montgomery system.
+
+ * shifts with subtractions when the result is greater than b.
+ *
+ * The method is slightly modified to shift B unconditionally up to just under
+ * the leading bit of b. This saves a lot of multiple precision shifting.
+ */
+static int mp_montgomery_calc_normalization (mp_int * a, const mp_int * b)
+{
+ int x, bits, res;
+
+ /* how many bits of last digit does b use */
+ bits = mp_count_bits (b) % DIGIT_BIT;
+
+
+ if (b->used > 1) {
+ if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) {
+ return res;
+ }
+ } else {
+ mp_set(a, 1);
+ bits = 1;
+ }
+
+
+ /* now compute C = A * B mod b */
+ for (x = bits - 1; x < DIGIT_BIT; x++) {
+ if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
+ return res;
+ }
+ if (mp_cmp_mag (a, b) != MP_LT) {
+ if ((res = s_mp_sub (a, b, a)) != MP_OKAY) {
+ return res;
+ }
+ }
+ }
+
+ return MP_OKAY;
+}
+
+/* computes xR**-1 == x (mod N) via Montgomery Reduction */
+static int
+mp_montgomery_reduce (mp_int * x, const mp_int * n, mp_digit rho)
+{
+ int ix, res, digs;
+ mp_digit mu;
+
+ /* can the fast reduction [comba] method be used?
+ *
+ * Note that unlike in mul you're safely allowed *less*
+ * than the available columns [255 per default] since carries
+ * are fixed up in the inner loop.
+ */
+ digs = n->used * 2 + 1;
+ if ((digs < MP_WARRAY) &&
+ n->used <
+ (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
+ return fast_mp_montgomery_reduce (x, n, rho);
+ }
+
+ /* grow the input as required */
+ if (x->alloc < digs) {
+ if ((res = mp_grow (x, digs)) != MP_OKAY) {
+ return res;
+ }
+ }
+ x->used = digs;
+
+ for (ix = 0; ix < n->used; ix++) {
+ /* mu = ai * rho mod b
+ *
+ * The value of rho must be precalculated via
+ * montgomery_setup() such that
+ * it equals -1/n0 mod b this allows the
+ * following inner loop to reduce the
+ * input one digit at a time
+ */
+ mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK);
+
+ /* a = a + mu * m * b**i */
+ {
+ register int iy;
+ register mp_digit *tmpn, *tmpx, u;
+ register mp_word r;
+
+ /* alias for digits of the modulus */
+ tmpn = n->dp;
+
+ /* alias for the digits of x [the input] */
+ tmpx = x->dp + ix;
+
+ /* set the carry to zero */
+ u = 0;
+
+ /* Multiply and add in place */
+ for (iy = 0; iy < n->used; iy++) {
+ /* compute product and sum */
+ r = ((mp_word)mu) * ((mp_word)*tmpn++) +
+ ((mp_word) u) + ((mp_word) * tmpx);
+
+ /* get carry */
+ u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
+
+ /* fix digit */
+ *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK));
+ }
+ /* At this point the ix'th digit of x should be zero */
+
+
+ /* propagate carries upwards as required*/
+ while (u) {
+ *tmpx += u;
+ u = *tmpx >> DIGIT_BIT;
+ *tmpx++ &= MP_MASK;
+ }
+ }
+ }
+
+ /* at this point the n.used'th least
+ * significant digits of x are all zero
+ * which means we can shift x to the
+ * right by n.used digits and the
+ * residue is unchanged.
+ */
+
+ /* x = x/b**n.used */
+ mp_clamp(x);
+ mp_rshd (x, n->used);
+
+ /* if x >= n then x = x - n */
+ if (mp_cmp_mag (x, n) != MP_LT) {
+ return s_mp_sub (x, n, x);
+ }
+
+ return MP_OKAY;
+}
+
+/* determines k value for 2k reduction */
+static int
+mp_reduce_2k_setup(const mp_int *a, mp_digit *d)
+{
+ int res, p;
+ mp_int tmp;
+
+ if ((res = mp_init(&tmp)) != MP_OKAY) {
+ return res;
+ }
+
+ p = mp_count_bits(a);
+ if ((res = mp_2expt(&tmp, p)) != MP_OKAY) {
+ mp_clear(&tmp);
+ return res;
+ }
+
+ if ((res = s_mp_sub(&tmp, a, &tmp)) != MP_OKAY) {
+ mp_clear(&tmp);
+ return res;
+ }
+
+ *d = tmp.dp[0];
+ mp_clear(&tmp);
+ return MP_OKAY;
+}
+
+/* reduces a modulo n where n is of the form 2**p - d [0 <= a]*/
+static int
+mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d)
+{
+ mp_int q;
+ int p, res;
+
+ if ((res = mp_init(&q)) != MP_OKAY) {
+ return res;
+ }
+
+ p = mp_count_bits(n);
+top:
+ /* q = a/2**p, a = a mod 2**p */
+ if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
+ goto ERR;
+ }
+
+ if (d != 1) {
+ /* q = q * d */
+ if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
+ goto ERR;
+ }
+ }
+
+ /* a = a + q */
+ if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
+ goto ERR;
+ }
+
+ if (mp_cmp_mag(a, n) != MP_LT) {
+ s_mp_sub(a, n, a);
+ goto top;
+ }
+
+ERR:
+ mp_clear(&q);
+ return res;
+}
+
/* 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.
@@ -2774,234 +3072,6 @@ mp_mod_d (const mp_int * a, mp_digit b, mp_digit * c)
return mp_div_d(a, b, NULL, c);
}
-/* b = a*2 */
-static int mp_mul_2(const mp_int * a, mp_int * b)
-{
- int x, res, oldused;
-
- /* grow to accommodate result */
- if (b->alloc < a->used + 1) {
- if ((res = mp_grow (b, a->used + 1)) != MP_OKAY) {
- return res;
- }
- }
-
- oldused = b->used;
- b->used = a->used;
-
- {
- register mp_digit r, rr, *tmpa, *tmpb;
-
- /* alias for source */
- tmpa = a->dp;
-
- /* alias for dest */
- tmpb = b->dp;
-
- /* carry */
- r = 0;
- for (x = 0; x < a->used; x++) {
-
- /* get what will be the *next* carry bit from the
- * MSB of the current digit
- */
- rr = *tmpa >> ((mp_digit)(DIGIT_BIT - 1));
-
- /* now shift up this digit, add in the carry [from the previous] */
- *tmpb++ = ((*tmpa++ << ((mp_digit)1)) | r) & MP_MASK;
-
- /* copy the carry that would be from the source
- * digit into the next iteration
- */
- r = rr;
- }
-
- /* new leading digit? */
- if (r != 0) {
- /* add a MSB which is always 1 at this point */
- *tmpb = 1;
- ++(b->used);
- }
-
- /* now zero any excess digits on the destination
- * that we didn't write to
- */
- tmpb = b->dp + b->used;
- for (x = b->used; x < oldused; x++) {
- *tmpb++ = 0;
- }
- }
- b->sign = a->sign;
- return MP_OKAY;
-}
-
-/*
- * shifts with subtractions when the result is greater than b.
- *
- * The method is slightly modified to shift B unconditionally up to just under
- * the leading bit of b. This saves a lot of multiple precision shifting.
- */
-int mp_montgomery_calc_normalization (mp_int * a, const mp_int * b)
-{
- int x, bits, res;
-
- /* how many bits of last digit does b use */
- bits = mp_count_bits (b) % DIGIT_BIT;
-
-
- if (b->used > 1) {
- if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) {
- return res;
- }
- } else {
- mp_set(a, 1);
- bits = 1;
- }
-
-
- /* now compute C = A * B mod b */
- for (x = bits - 1; x < DIGIT_BIT; x++) {
- if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
- return res;
- }
- if (mp_cmp_mag (a, b) != MP_LT) {
- if ((res = s_mp_sub (a, b, a)) != MP_OKAY) {
- return res;
- }
- }
- }
-
- return MP_OKAY;
-}
-
-/* computes xR**-1 == x (mod N) via Montgomery Reduction */
-int
-mp_montgomery_reduce (mp_int * x, const mp_int * n, mp_digit rho)
-{
- int ix, res, digs;
- mp_digit mu;
-
- /* can the fast reduction [comba] method be used?
- *
- * Note that unlike in mul you're safely allowed *less*
- * than the available columns [255 per default] since carries
- * are fixed up in the inner loop.
- */
- digs = n->used * 2 + 1;
- if ((digs < MP_WARRAY) &&
- n->used <
- (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
- return fast_mp_montgomery_reduce (x, n, rho);
- }
-
- /* grow the input as required */
- if (x->alloc < digs) {
- if ((res = mp_grow (x, digs)) != MP_OKAY) {
- return res;
- }
- }
- x->used = digs;
-
- for (ix = 0; ix < n->used; ix++) {
- /* mu = ai * rho mod b
- *
- * The value of rho must be precalculated via
- * montgomery_setup() such that
- * it equals -1/n0 mod b this allows the
- * following inner loop to reduce the
- * input one digit at a time
- */
- mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK);
-
- /* a = a + mu * m * b**i */
- {
- register int iy;
- register mp_digit *tmpn, *tmpx, u;
- register mp_word r;
-
- /* alias for digits of the modulus */
- tmpn = n->dp;
-
- /* alias for the digits of x [the input] */
- tmpx = x->dp + ix;
-
- /* set the carry to zero */
- u = 0;
-
- /* Multiply and add in place */
- for (iy = 0; iy < n->used; iy++) {
- /* compute product and sum */
- r = ((mp_word)mu) * ((mp_word)*tmpn++) +
- ((mp_word) u) + ((mp_word) * tmpx);
-
- /* get carry */
- u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
-
- /* fix digit */
- *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK));
- }
- /* At this point the ix'th digit of x should be zero */
-
-
- /* propagate carries upwards as required*/
- while (u) {
- *tmpx += u;
- u = *tmpx >> DIGIT_BIT;
- *tmpx++ &= MP_MASK;
- }
- }
- }
-
- /* at this point the n.used'th least
- * significant digits of x are all zero
- * which means we can shift x to the
- * right by n.used digits and the
- * residue is unchanged.
- */
-
- /* x = x/b**n.used */
- mp_clamp(x);
- mp_rshd (x, n->used);
-
- /* if x >= n then x = x - n */
- if (mp_cmp_mag (x, n) != MP_LT) {
- return s_mp_sub (x, n, x);
- }
-
- return MP_OKAY;
-}
-
-/* setups the montgomery reduction stuff */
-int
-mp_montgomery_setup (const mp_int * n, mp_digit * rho)
-{
- mp_digit x, b;
-
-/* fast inversion mod 2**k
- *
- * Based on the fact that
- *
- * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
- * => 2*X*A - X*X*A*A = 1
- * => 2*(1) - (1) = 1
- */
- b = n->dp[0];
-
- if ((b & 1) == 0) {
- return MP_VAL;
- }
-
- x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
- x *= 2 - b * x; /* here x*a==1 mod 2**8 */
- x *= 2 - b * x; /* here x*a==1 mod 2**16 */
- x *= 2 - b * x; /* here x*a==1 mod 2**32 */
-
- /* rho = -1/m mod b */
- *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;
-
- return MP_OKAY;
-}
-
/* high level multiplication (handles sign) */
int mp_mul (const mp_int * a, const mp_int * b, mp_int * c)
{
@@ -3425,11 +3495,26 @@ mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
return MP_OKAY;
}
-/* reduces x mod m, assumes 0 < x < m**2, mu is
- * precomputed via mp_reduce_setup.
+/* pre-calculate the value required for Barrett reduction
+ * For a given modulus "b" it calulates the value required in "a"
+ */
+static int mp_reduce_setup (mp_int * a, const mp_int * b)
+{
+ int res;
+
+ if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
+ return res;
+ }
+ return mp_div (a, b, a, NULL);
+}
+
+/* Barrett Reduction, reduces x mod m, assumes 0 < x < m**2, mu is precomputed
+ * via mp_reduce_setup. Note if 0 > x > -(m*m) then you can merely compute
+ * the reduction as -1 * mp_reduce(mp_abs(x)) [pseudo code].
+ *
* From HAC pp.604 Algorithm 14.42
*/
-int
+static int
mp_reduce (mp_int * x, const mp_int * m, const mp_int * mu)
{
mp_int q;
@@ -3494,86 +3579,6 @@ CLEANUP:
return res;
}
-/* reduces a modulo n where n is of the form 2**p - d */
-int
-mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d)
-{
- mp_int q;
- int p, res;
-
- if ((res = mp_init(&q)) != MP_OKAY) {
- return res;
- }
-
- p = mp_count_bits(n);
-top:
- /* q = a/2**p, a = a mod 2**p */
- if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
- goto ERR;
- }
-
- if (d != 1) {
- /* q = q * d */
- if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
- goto ERR;
- }
- }
-
- /* a = a + q */
- if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
- goto ERR;
- }
-
- if (mp_cmp_mag(a, n) != MP_LT) {
- s_mp_sub(a, n, a);
- goto top;
- }
-
-ERR:
- mp_clear(&q);
- return res;
-}
-
-/* determines the setup value */
-int
-mp_reduce_2k_setup(const mp_int *a, mp_digit *d)
-{
- int res, p;
- mp_int tmp;
-
- if ((res = mp_init(&tmp)) != MP_OKAY) {
- return res;
- }
-
- p = mp_count_bits(a);
- if ((res = mp_2expt(&tmp, p)) != MP_OKAY) {
- mp_clear(&tmp);
- return res;
- }
-
- if ((res = s_mp_sub(&tmp, a, &tmp)) != MP_OKAY) {
- mp_clear(&tmp);
- return res;
- }
-
- *d = tmp.dp[0];
- mp_clear(&tmp);
- return MP_OKAY;
-}
-
-/* pre-calculate the value required for Barrett reduction
- * For a given modulus "b" it calulates the value required in "a"
- */
-int mp_reduce_setup (mp_int * a, const mp_int * b)
-{
- int res;
-
- if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
- return res;
- }
- return mp_div (a, b, a, NULL);
-}
-
/* shift right a certain amount of digits */
void mp_rshd (mp_int * a, int b)
{
diff --git a/dlls/rsaenh/tomcrypt.h b/dlls/rsaenh/tomcrypt.h
index 0efa086..e513cda 100644
--- a/dlls/rsaenh/tomcrypt.h
+++ b/dlls/rsaenh/tomcrypt.h
@@ -386,39 +386,12 @@ int mp_is_square(mp_int *arg, int *ret);
/* computes the jacobi c = (a | n) (or Legendre if b is prime) */
int mp_jacobi(mp_int *a, mp_int *n, int *c);
-/* used to setup the Barrett reduction for a given modulus b */
-int mp_reduce_setup(mp_int *a, const mp_int *b);
-
-/* Barrett Reduction, computes a (mod b) with a precomputed value c
- *
- * Assumes that 0 < a <= b*b, note if 0 > a > -(b*b) then you can merely
- * compute the reduction as -1 * mp_reduce(mp_abs(a)) [pseudo code].
- */
-int mp_reduce(mp_int *a, const mp_int *b, const mp_int *c);
-
-/* setups the montgomery reduction */
-int mp_montgomery_setup(const mp_int *a, mp_digit *mp);
-
-/* computes a = B**n mod b without division or multiplication useful for
- * normalizing numbers in a Montgomery system.
- */
-int mp_montgomery_calc_normalization(mp_int *a, const mp_int *b);
-
-/* computes x/R == x (mod N) via Montgomery Reduction */
-int mp_montgomery_reduce(mp_int *a, const mp_int *m, mp_digit mp);
-
/* returns 1 if a is a valid DR modulus */
int mp_dr_is_modulus(mp_int *a);
/* returns true if a can be reduced with mp_reduce_2k */
int mp_reduce_is_2k(mp_int *a);
-/* determines k value for 2k reduction */
-int mp_reduce_2k_setup(const mp_int *a, mp_digit *d);
-
-/* reduces a modulo b where b is of the form 2**p - k [0 <= a] */
-int mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d);
-
/* d = a**b (mod c) */
int mp_exptmod(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d);
More information about the wine-patches
mailing list