← Back to branch summary

~ubuntu-branches/ubuntu/precise/nss/precise-security

« back to all changes in this revision

Viewing changes to mozilla/security/nss/lib/freebl/mpi/mpmontg.c

  • Committer: Package Import Robot
  • Author(s): Marc Deslauriers
  • Date: 2013-11-14 14:58:07 UTC
  • mfrom: (1.1.19)
  • Revision ID: package-import@ubuntu.com-20131114145807-ay302kimn72ovt88
Tags: 3.15.3-0ubuntu0.12.04.1
* SECURITY UPDATE: New upstream release to fix multiple security issues
  and add TLSv1.2 support.
  - CVE-2013-1739
  - CVE-2013-1741
  - CVE-2013-5605
  - CVE-2013-5606
* Adjusted packaging for 3.15.3:
  - debian/patches/*: refreshed.
  - debian/patches/lower-dhe-priority.patch: removed, no longer needed,
    was a workaround for an old version of firefox.
  - debian/libnss3.symbols: added new symbols.
  - debian/rules: updated for new source layout.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/security/nss/lib/freebl/mpi/mpmontg.c
1
 
/* This Source Code Form is subject to the terms of the Mozilla Public
2
 
 * License, v. 2.0. If a copy of the MPL was not distributed with this
3
 
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
 
/* $Id: mpmontg.c,v 1.25 2012/11/14 01:14:11 wtc%google.com Exp $ */
5
 
 
6
 
/* This file implements moduluar exponentiation using Montgomery's
7
 
 * method for modular reduction.  This file implements the method
8
 
 * described as "Improvement 2" in the paper "A Cryptogrpahic Library for
9
 
 * the Motorola DSP56000" by Stephen R. Dusse' and Burton S. Kaliski Jr.
10
 
 * published in "Advances in Cryptology: Proceedings of EUROCRYPT '90"
11
 
 * "Lecture Notes in Computer Science" volume 473, 1991, pg 230-244,
12
 
 * published by Springer Verlag.
13
 
 */
14
 
 
15
 
#define MP_USING_CACHE_SAFE_MOD_EXP 1 
16
 
#include <string.h>
17
 
#include "mpi-priv.h"
18
 
#include "mplogic.h"
19
 
#include "mpprime.h"
20
 
#ifdef MP_USING_MONT_MULF
21
 
#include "montmulf.h"
22
 
#endif
23
 
#include <stddef.h> /* ptrdiff_t */
24
 
 
25
 
/* if MP_CHAR_STORE_SLOW is defined, we  */
26
 
/* need to know endianness of this platform. */
27
 
#ifdef MP_CHAR_STORE_SLOW
28
 
#if !defined(MP_IS_BIG_ENDIAN) && !defined(MP_IS_LITTLE_ENDIAN)
29
 
#error "You must define MP_IS_BIG_ENDIAN or MP_IS_LITTLE_ENDIAN\n" \
30
 
       "  if you define MP_CHAR_STORE_SLOW."
31
 
#endif
32
 
#endif
33
 
 
34
 
#define STATIC
35
 
 
36
 
#define MAX_ODD_INTS    32   /* 2 ** (WINDOW_BITS - 1) */
37
 
 
38
 
/*! computes T = REDC(T), 2^b == R 
39
 
    \param T < RN
40
 
*/
41
 
mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm)
42
 
{
43
 
  mp_err res;
44
 
  mp_size i;
45
 
 
46
 
  i = (MP_USED(&mmm->N) << 1) + 1;
47
 
  MP_CHECKOK( s_mp_pad(T, i) );
48
 
  for (i = 0; i < MP_USED(&mmm->N); ++i ) {
49
 
    mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
50
 
    /* T += N * m_i * (MP_RADIX ** i); */
51
 
    MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
52
 
  }
53
 
  s_mp_clamp(T);
54
 
 
55
 
  /* T /= R */
56
 
  s_mp_rshd( T, MP_USED(&mmm->N) );
57
 
 
58
 
  if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
59
 
    /* T = T - N */
60
 
    MP_CHECKOK( s_mp_sub(T, &mmm->N) );
61
 
#ifdef DEBUG
62
 
    if ((res = mp_cmp(T, &mmm->N)) >= 0) {
63
 
      res = MP_UNDEF;
64
 
      goto CLEANUP;
65
 
    }
66
 
#endif
67
 
  }
68
 
  res = MP_OKAY;
69
 
CLEANUP:
70
 
  return res;
71
 
}
72
 
 
73
 
#if !defined(MP_MONT_USE_MP_MUL)
74
 
 
75
 
/*! c <- REDC( a * b ) mod N
76
 
    \param a < N  i.e. "reduced"
77
 
    \param b < N  i.e. "reduced"
78
 
    \param mmm modulus N and n0' of N
79
 
*/
80
 
mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 
81
 
                   mp_mont_modulus *mmm)
82
 
{
83
 
  mp_digit *pb;
84
 
  mp_digit m_i;
85
 
  mp_err   res;
86
 
  mp_size  ib; /* "index b": index of current digit of B */
87
 
  mp_size  useda, usedb;
88
 
 
89
 
  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
90
 
 
91
 
  if (MP_USED(a) < MP_USED(b)) {
92
 
    const mp_int *xch = b;      /* switch a and b, to do fewer outer loops */
93
 
    b = a;
94
 
    a = xch;
95
 
  }
96
 
 
97
 
  MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
98
 
  ib = (MP_USED(&mmm->N) << 1) + 1;
99
 
  if((res = s_mp_pad(c, ib)) != MP_OKAY)
100
 
    goto CLEANUP;
101
 
 
102
 
  useda = MP_USED(a);
103
 
  pb = MP_DIGITS(b);
104
 
  s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
105
 
  s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
106
 
  m_i = MP_DIGIT(c, 0) * mmm->n0prime;
107
 
  s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);
108
 
 
109
 
  /* Outer loop:  Digits of b */
110
 
  usedb = MP_USED(b);
111
 
  for (ib = 1; ib < usedb; ib++) {
112
 
    mp_digit b_i    = *pb++;
113
 
 
114
 
    /* Inner product:  Digits of a */
115
 
    if (b_i)
116
 
      s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
117
 
    m_i = MP_DIGIT(c, ib) * mmm->n0prime;
118
 
    s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
119
 
  }
120
 
  if (usedb < MP_USED(&mmm->N)) {
121
 
    for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
122
 
      m_i = MP_DIGIT(c, ib) * mmm->n0prime;
123
 
      s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
124
 
    }
125
 
  }
126
 
  s_mp_clamp(c);
127
 
  s_mp_rshd( c, MP_USED(&mmm->N) ); /* c /= R */
128
 
  if (s_mp_cmp(c, &mmm->N) >= 0) {
129
 
    MP_CHECKOK( s_mp_sub(c, &mmm->N) );
130
 
  }
131
 
  res = MP_OKAY;
132
 
 
133
 
CLEANUP:
134
 
  return res;
135
 
}
136
 
#endif
137
 
 
138
 
STATIC
139
 
mp_err s_mp_to_mont(const mp_int *x, mp_mont_modulus *mmm, mp_int *xMont)
140
 
{
141
 
  mp_err res;
142
 
 
143
 
  /* xMont = x * R mod N   where  N is modulus */
144
 
  MP_CHECKOK( mp_copy( x, xMont ) );
145
 
  MP_CHECKOK( s_mp_lshd( xMont, MP_USED(&mmm->N) ) );   /* xMont = x << b */
146
 
  MP_CHECKOK( mp_div(xMont, &mmm->N, 0, xMont) );       /*         mod N */
147
 
CLEANUP:
148
 
  return res;
149
 
}
150
 
 
151
 
#ifdef MP_USING_MONT_MULF
152
 
 
153
 
/* the floating point multiply is already cache safe,
154
 
 * don't turn on cache safe unless we specifically
155
 
 * force it */
156
 
#ifndef MP_FORCE_CACHE_SAFE
157
 
#undef MP_USING_CACHE_SAFE_MOD_EXP
158
 
#endif
159
 
 
160
 
unsigned int mp_using_mont_mulf = 1;
161
 
 
162
 
/* computes montgomery square of the integer in mResult */
163
 
#define SQR \
164
 
  conv_i32_to_d32_and_d16(dm1, d16Tmp, mResult, nLen); \
165
 
  mont_mulf_noconv(mResult, dm1, d16Tmp, \
166
 
                   dTmp, dn, MP_DIGITS(modulus), nLen, dn0)
167
 
 
168
 
/* computes montgomery product of x and the integer in mResult */
169
 
#define MUL(x) \
170
 
  conv_i32_to_d32(dm1, mResult, nLen); \
171
 
  mont_mulf_noconv(mResult, dm1, oddPowers[x], \
172
 
                   dTmp, dn, MP_DIGITS(modulus), nLen, dn0)
173
 
 
174
 
/* Do modular exponentiation using floating point multiply code. */
175
 
mp_err mp_exptmod_f(const mp_int *   montBase, 
176
 
                    const mp_int *   exponent, 
177
 
                    const mp_int *   modulus, 
178
 
                    mp_int *         result, 
179
 
                    mp_mont_modulus *mmm, 
180
 
                    int              nLen, 
181
 
                    mp_size          bits_in_exponent, 
182
 
                    mp_size          window_bits,
183
 
                    mp_size          odd_ints)
184
 
{
185
 
  mp_digit *mResult;
186
 
  double   *dBuf = 0, *dm1, *dn, *dSqr, *d16Tmp, *dTmp;
187
 
  double    dn0;
188
 
  mp_size   i;
189
 
  mp_err    res;
190
 
  int       expOff;
191
 
  int       dSize = 0, oddPowSize, dTmpSize;
192
 
  mp_int    accum1;
193
 
  double   *oddPowers[MAX_ODD_INTS];
194
 
 
195
 
  /* function for computing n0prime only works if n0 is odd */
196
 
 
197
 
  MP_DIGITS(&accum1) = 0;
198
 
 
199
 
  for (i = 0; i < MAX_ODD_INTS; ++i)
200
 
    oddPowers[i] = 0;
201
 
 
202
 
  MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
203
 
 
204
 
  mp_set(&accum1, 1);
205
 
  MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
206
 
  MP_CHECKOK( s_mp_pad(&accum1, nLen) );
207
 
 
208
 
  oddPowSize = 2 * nLen + 1;
209
 
  dTmpSize   = 2 * oddPowSize;
210
 
  dSize = sizeof(double) * (nLen * 4 + 1 + 
211
 
                            ((odd_ints + 1) * oddPowSize) + dTmpSize);
212
 
  dBuf   = (double *)malloc(dSize);
213
 
  dm1    = dBuf;                /* array of d32 */
214
 
  dn     = dBuf   + nLen;       /* array of d32 */
215
 
  dSqr   = dn     + nLen;       /* array of d32 */
216
 
  d16Tmp = dSqr   + nLen;       /* array of d16 */
217
 
  dTmp   = d16Tmp + oddPowSize;
218
 
 
219
 
  for (i = 0; i < odd_ints; ++i) {
220
 
      oddPowers[i] = dTmp;
221
 
      dTmp += oddPowSize;
222
 
  }
223
 
  mResult = (mp_digit *)(dTmp + dTmpSize);      /* size is nLen + 1 */
224
 
 
225
 
  /* Make dn and dn0 */
226
 
  conv_i32_to_d32(dn, MP_DIGITS(modulus), nLen);
227
 
  dn0 = (double)(mmm->n0prime & 0xffff);
228
 
 
229
 
  /* Make dSqr */
230
 
  conv_i32_to_d32_and_d16(dm1, oddPowers[0], MP_DIGITS(montBase), nLen);
231
 
  mont_mulf_noconv(mResult, dm1, oddPowers[0], 
232
 
                   dTmp, dn, MP_DIGITS(modulus), nLen, dn0);
233
 
  conv_i32_to_d32(dSqr, mResult, nLen);
234
 
 
235
 
  for (i = 1; i < odd_ints; ++i) {
236
 
    mont_mulf_noconv(mResult, dSqr, oddPowers[i - 1], 
237
 
                     dTmp, dn, MP_DIGITS(modulus), nLen, dn0);
238
 
    conv_i32_to_d16(oddPowers[i], mResult, nLen);
239
 
  }
240
 
 
241
 
  s_mp_copy(MP_DIGITS(&accum1), mResult, nLen); /* from, to, len */
242
 
 
243
 
  for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
244
 
    mp_size smallExp;
245
 
    MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
246
 
    smallExp = (mp_size)res;
247
 
 
248
 
    if (window_bits == 1) {
249
 
      if (!smallExp) {
250
 
        SQR;
251
 
      } else if (smallExp & 1) {
252
 
        SQR; MUL(0); 
253
 
      } else {
254
 
        abort();
255
 
      }
256
 
    } else if (window_bits == 4) {
257
 
      if (!smallExp) {
258
 
        SQR; SQR; SQR; SQR;
259
 
      } else if (smallExp & 1) {
260
 
        SQR; SQR; SQR; SQR; MUL(smallExp/2); 
261
 
      } else if (smallExp & 2) {
262
 
        SQR; SQR; SQR; MUL(smallExp/4); SQR; 
263
 
      } else if (smallExp & 4) {
264
 
        SQR; SQR; MUL(smallExp/8); SQR; SQR; 
265
 
      } else if (smallExp & 8) {
266
 
        SQR; MUL(smallExp/16); SQR; SQR; SQR; 
267
 
      } else {
268
 
        abort();
269
 
      }
270
 
    } else if (window_bits == 5) {
271
 
      if (!smallExp) {
272
 
        SQR; SQR; SQR; SQR; SQR; 
273
 
      } else if (smallExp & 1) {
274
 
        SQR; SQR; SQR; SQR; SQR; MUL(smallExp/2);
275
 
      } else if (smallExp & 2) {
276
 
        SQR; SQR; SQR; SQR; MUL(smallExp/4); SQR;
277
 
      } else if (smallExp & 4) {
278
 
        SQR; SQR; SQR; MUL(smallExp/8); SQR; SQR;
279
 
      } else if (smallExp & 8) {
280
 
        SQR; SQR; MUL(smallExp/16); SQR; SQR; SQR;
281
 
      } else if (smallExp & 0x10) {
282
 
        SQR; MUL(smallExp/32); SQR; SQR; SQR; SQR;
283
 
      } else {
284
 
        abort();
285
 
      }
286
 
    } else if (window_bits == 6) {
287
 
      if (!smallExp) {
288
 
        SQR; SQR; SQR; SQR; SQR; SQR;
289
 
      } else if (smallExp & 1) {
290
 
        SQR; SQR; SQR; SQR; SQR; SQR; MUL(smallExp/2); 
291
 
      } else if (smallExp & 2) {
292
 
        SQR; SQR; SQR; SQR; SQR; MUL(smallExp/4); SQR; 
293
 
      } else if (smallExp & 4) {
294
 
        SQR; SQR; SQR; SQR; MUL(smallExp/8); SQR; SQR; 
295
 
      } else if (smallExp & 8) {
296
 
        SQR; SQR; SQR; MUL(smallExp/16); SQR; SQR; SQR; 
297
 
      } else if (smallExp & 0x10) {
298
 
        SQR; SQR; MUL(smallExp/32); SQR; SQR; SQR; SQR; 
299
 
      } else if (smallExp & 0x20) {
300
 
        SQR; MUL(smallExp/64); SQR; SQR; SQR; SQR; SQR; 
301
 
      } else {
302
 
        abort();
303
 
      }
304
 
    } else {
305
 
      abort();
306
 
    }
307
 
  }
308
 
 
309
 
  s_mp_copy(mResult, MP_DIGITS(&accum1), nLen); /* from, to, len */
310
 
 
311
 
  res = s_mp_redc(&accum1, mmm);
312
 
  mp_exch(&accum1, result);
313
 
 
314
 
CLEANUP:
315
 
  mp_clear(&accum1);
316
 
  if (dBuf) {
317
 
    if (dSize)
318
 
      memset(dBuf, 0, dSize);
319
 
    free(dBuf);
320
 
  }
321
 
 
322
 
  return res;
323
 
}
324
 
#undef SQR
325
 
#undef MUL
326
 
#endif
327
 
 
328
 
#define SQR(a,b) \
329
 
  MP_CHECKOK( mp_sqr(a, b) );\
330
 
  MP_CHECKOK( s_mp_redc(b, mmm) )
331
 
 
332
 
#if defined(MP_MONT_USE_MP_MUL)
333
 
#define MUL(x,a,b) \
334
 
  MP_CHECKOK( mp_mul(a, oddPowers + (x), b) ); \
335
 
  MP_CHECKOK( s_mp_redc(b, mmm) ) 
336
 
#else
337
 
#define MUL(x,a,b) \
338
 
  MP_CHECKOK( s_mp_mul_mont(a, oddPowers + (x), b, mmm) )
339
 
#endif
340
 
 
341
 
#define SWAPPA ptmp = pa1; pa1 = pa2; pa2 = ptmp
342
 
 
343
 
/* Do modular exponentiation using integer multiply code. */
344
 
mp_err mp_exptmod_i(const mp_int *   montBase, 
345
 
                    const mp_int *   exponent, 
346
 
                    const mp_int *   modulus, 
347
 
                    mp_int *         result, 
348
 
                    mp_mont_modulus *mmm, 
349
 
                    int              nLen, 
350
 
                    mp_size          bits_in_exponent, 
351
 
                    mp_size          window_bits,
352
 
                    mp_size          odd_ints)
353
 
{
354
 
  mp_int *pa1, *pa2, *ptmp;
355
 
  mp_size i;
356
 
  mp_err  res;
357
 
  int     expOff;
358
 
  mp_int  accum1, accum2, power2, oddPowers[MAX_ODD_INTS];
359
 
 
360
 
  /* power2 = base ** 2; oddPowers[i] = base ** (2*i + 1); */
361
 
  /* oddPowers[i] = base ** (2*i + 1); */
362
 
 
363
 
  MP_DIGITS(&accum1) = 0;
364
 
  MP_DIGITS(&accum2) = 0;
365
 
  MP_DIGITS(&power2) = 0;
366
 
  for (i = 0; i < MAX_ODD_INTS; ++i) {
367
 
    MP_DIGITS(oddPowers + i) = 0;
368
 
  }
369
 
 
370
 
  MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
371
 
  MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );
372
 
 
373
 
  MP_CHECKOK( mp_init_copy(&oddPowers[0], montBase) );
374
 
 
375
 
  mp_init_size(&power2, nLen + 2 * MP_USED(montBase) + 2);
376
 
  MP_CHECKOK( mp_sqr(montBase, &power2) );      /* power2 = montBase ** 2 */
377
 
  MP_CHECKOK( s_mp_redc(&power2, mmm) );
378
 
 
379
 
  for (i = 1; i < odd_ints; ++i) {
380
 
    mp_init_size(oddPowers + i, nLen + 2 * MP_USED(&power2) + 2);
381
 
    MP_CHECKOK( mp_mul(oddPowers + (i - 1), &power2, oddPowers + i) );
382
 
    MP_CHECKOK( s_mp_redc(oddPowers + i, mmm) );
383
 
  }
384
 
 
385
 
  /* set accumulator to montgomery residue of 1 */
386
 
  mp_set(&accum1, 1);
387
 
  MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
388
 
  pa1 = &accum1;
389
 
  pa2 = &accum2;
390
 
 
391
 
  for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
392
 
    mp_size smallExp;
393
 
    MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
394
 
    smallExp = (mp_size)res;
395
 
 
396
 
    if (window_bits == 1) {
397
 
      if (!smallExp) {
398
 
        SQR(pa1,pa2); SWAPPA;
399
 
      } else if (smallExp & 1) {
400
 
        SQR(pa1,pa2); MUL(0,pa2,pa1);
401
 
      } else {
402
 
        abort();
403
 
      }
404
 
    } else if (window_bits == 4) {
405
 
      if (!smallExp) {
406
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
407
 
      } else if (smallExp & 1) {
408
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
409
 
        MUL(smallExp/2, pa1,pa2); SWAPPA;
410
 
      } else if (smallExp & 2) {
411
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
412
 
        MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
413
 
      } else if (smallExp & 4) {
414
 
        SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/8,pa1,pa2); 
415
 
        SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
416
 
      } else if (smallExp & 8) {
417
 
        SQR(pa1,pa2); MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); 
418
 
        SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
419
 
      } else {
420
 
        abort();
421
 
      }
422
 
    } else if (window_bits == 5) {
423
 
      if (!smallExp) {
424
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
425
 
        SQR(pa1,pa2); SWAPPA;
426
 
      } else if (smallExp & 1) {
427
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
428
 
        SQR(pa1,pa2); MUL(smallExp/2,pa2,pa1);
429
 
      } else if (smallExp & 2) {
430
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
431
 
        MUL(smallExp/4,pa1,pa2); SQR(pa2,pa1);
432
 
      } else if (smallExp & 4) {
433
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
434
 
        MUL(smallExp/8,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
435
 
      } else if (smallExp & 8) {
436
 
        SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/16,pa1,pa2); 
437
 
        SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
438
 
      } else if (smallExp & 0x10) {
439
 
        SQR(pa1,pa2); MUL(smallExp/32,pa2,pa1); SQR(pa1,pa2); 
440
 
        SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
441
 
      } else {
442
 
        abort();
443
 
      }
444
 
    } else if (window_bits == 6) {
445
 
      if (!smallExp) {
446
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
447
 
        SQR(pa1,pa2); SQR(pa2,pa1);
448
 
      } else if (smallExp & 1) {
449
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
450
 
        SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/2,pa1,pa2); SWAPPA;
451
 
      } else if (smallExp & 2) {
452
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
453
 
        SQR(pa1,pa2); MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
454
 
      } else if (smallExp & 4) {
455
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
456
 
        MUL(smallExp/8,pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
457
 
      } else if (smallExp & 8) {
458
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
459
 
        MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
460
 
        SQR(pa1,pa2); SWAPPA;
461
 
      } else if (smallExp & 0x10) {
462
 
        SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/32,pa1,pa2); 
463
 
        SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
464
 
      } else if (smallExp & 0x20) {
465
 
        SQR(pa1,pa2); MUL(smallExp/64,pa2,pa1); SQR(pa1,pa2); 
466
 
        SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
467
 
      } else {
468
 
        abort();
469
 
      }
470
 
    } else {
471
 
      abort();
472
 
    }
473
 
  }
474
 
 
475
 
  res = s_mp_redc(pa1, mmm);
476
 
  mp_exch(pa1, result);
477
 
 
478
 
CLEANUP:
479
 
  mp_clear(&accum1);
480
 
  mp_clear(&accum2);
481
 
  mp_clear(&power2);
482
 
  for (i = 0; i < odd_ints; ++i) {
483
 
    mp_clear(oddPowers + i);
484
 
  }
485
 
  return res;
486
 
}
487
 
#undef SQR
488
 
#undef MUL
489
 
 
490
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
491
 
unsigned int mp_using_cache_safe_exp = 1;
492
 
#endif
493
 
 
494
 
mp_err mp_set_safe_modexp(int value) 
495
 
{
496
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
497
 
 mp_using_cache_safe_exp = value;
498
 
 return MP_OKAY;
499
 
#else
500
 
 if (value == 0) {
501
 
   return MP_OKAY;
502
 
 }
503
 
 return MP_BADARG;
504
 
#endif
505
 
}
506
 
 
507
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
508
 
#define WEAVE_WORD_SIZE 4
509
 
 
510
 
#ifndef MP_CHAR_STORE_SLOW
511
 
/*
512
 
 * mpi_to_weave takes an array of bignums, a matrix in which each bignum 
513
 
 * occupies all the columns of a row, and transposes it into a matrix in 
514
 
 * which each bignum occupies a column of every row.  The first row of the
515
 
 * input matrix becomes the first column of the output matrix.  The n'th
516
 
 * row of input becomes the n'th column of output.  The input data is said
517
 
 * to be "interleaved" or "woven" into the output matrix.
518
 
 *
519
 
 * The array of bignums is left in this woven form.  Each time a single
520
 
 * bignum value is needed, it is recreated by fetching the n'th column, 
521
 
 * forming a single row which is the new bignum.
522
 
 *
523
 
 * The purpose of this interleaving is make it impossible to determine which
524
 
 * of the bignums is being used in any one operation by examining the pattern
525
 
 * of cache misses.
526
 
 *
527
 
 * The weaving function does not transpose the entire input matrix in one call.
528
 
 * It transposes 4 rows of mp_ints into their respective columns of output.
529
 
 *
530
 
 * There are two different implementations of the weaving and unweaving code
531
 
 * in this file.  One uses byte loads and stores.  The second uses loads and
532
 
 * stores of mp_weave_word size values.  The weaved forms of these two 
533
 
 * implementations differ.  Consequently, each one has its own explanation.
534
 
 *
535
 
 * Here is the explanation for the byte-at-a-time implementation.
536
 
 *
537
 
 * This implementation treats each mp_int bignum as an array of bytes, 
538
 
 * rather than as an array of mp_digits.  It stores those bytes as a 
539
 
 * column of bytes in the output matrix.  It doesn't care if the machine
540
 
 * uses big-endian or little-endian byte ordering within mp_digits.
541
 
 * The first byte of the mp_digit array becomes the first byte in the output
542
 
 * column, regardless of whether that byte is the MSB or LSB of the mp_digit.
543
 
 *
544
 
 * "bignums" is an array of mp_ints.
545
 
 * It points to four rows, four mp_ints, a subset of a larger array of mp_ints.
546
 
 *
547
 
 * "weaved" is the weaved output matrix. 
548
 
 * The first byte of bignums[0] is stored in weaved[0].
549
 
 * 
550
 
 * "nBignums" is the total number of bignums in the array of which "bignums" 
551
 
 * is a part.  
552
 
 *
553
 
 * "nDigits" is the size in mp_digits of each mp_int in the "bignums" array. 
554
 
 * mp_ints that use less than nDigits digits are logically padded with zeros 
555
 
 * while being stored in the weaved array.
556
 
 */
557
 
mp_err mpi_to_weave(const mp_int  *bignums, 
558
 
                    unsigned char *weaved, 
559
 
                    mp_size nDigits,  /* in each mp_int of input */
560
 
                    mp_size nBignums) /* in the entire source array */
561
 
{
562
 
  mp_size i;
563
 
  unsigned char * endDest = weaved + (nDigits * nBignums * sizeof(mp_digit));
564
 
 
565
 
  for (i=0; i < WEAVE_WORD_SIZE; i++) {
566
 
    mp_size used = MP_USED(&bignums[i]);
567
 
    unsigned char *pSrc   = (unsigned char *)MP_DIGITS(&bignums[i]);
568
 
    unsigned char *endSrc = pSrc + (used * sizeof(mp_digit));
569
 
    unsigned char *pDest  = weaved + i;
570
 
 
571
 
    ARGCHK(MP_SIGN(&bignums[i]) == MP_ZPOS, MP_BADARG);
572
 
    ARGCHK(used <= nDigits, MP_BADARG);
573
 
 
574
 
    for (; pSrc < endSrc; pSrc++) {
575
 
      *pDest = *pSrc;
576
 
      pDest += nBignums;
577
 
    }
578
 
    while (pDest < endDest) {
579
 
      *pDest = 0;
580
 
      pDest += nBignums;
581
 
    }
582
 
  }
583
 
 
584
 
  return MP_OKAY;
585
 
}
586
 
 
587
 
/* Reverse the operation above for one mp_int.
588
 
 * Reconstruct one mp_int from its column in the weaved array.
589
 
 * "pSrc" points to the offset into the weave array of the bignum we 
590
 
 * are going to reconstruct.
591
 
 */
592
 
mp_err weave_to_mpi(mp_int *a,                /* output, result */
593
 
                    const unsigned char *pSrc, /* input, byte matrix */
594
 
                    mp_size nDigits,          /* per mp_int output */
595
 
                    mp_size nBignums)         /* bignums in weaved matrix */
596
 
{
597
 
  unsigned char *pDest   = (unsigned char *)MP_DIGITS(a);
598
 
  unsigned char *endDest = pDest + (nDigits * sizeof(mp_digit));
599
 
 
600
 
  MP_SIGN(a) = MP_ZPOS;
601
 
  MP_USED(a) = nDigits;
602
 
 
603
 
  for (; pDest < endDest; pSrc += nBignums, pDest++) {
604
 
    *pDest = *pSrc;
605
 
  }
606
 
  s_mp_clamp(a);
607
 
  return MP_OKAY;
608
 
}
609
 
 
610
 
#else
611
 
 
612
 
/* Need a primitive that we know is 32 bits long... */
613
 
/* this is true on all modern processors we know of today*/
614
 
typedef unsigned int mp_weave_word;
615
 
 
616
 
/*
617
 
 * on some platforms character stores into memory is very expensive since they
618
 
 * generate a read/modify/write operation on the bus. On those platforms
619
 
 * we need to do integer writes to the bus. Because of some unrolled code,
620
 
 * in this current code the size of mp_weave_word must be four. The code that
621
 
 * makes this assumption explicity is called out. (on some platforms a write
622
 
 * of 4 bytes still requires a single read-modify-write operation.
623
 
 *
624
 
 * This function is takes the identical parameters as the function above, 
625
 
 * however it lays out the final array differently. Where the previous function
626
 
 * treats the mpi_int as an byte array, this function treats it as an array of
627
 
 * mp_digits where each digit is stored in big endian order.
628
 
 * 
629
 
 * since we need to interleave on a byte by byte basis, we need to collect 
630
 
 * several mpi structures together into a single uint32 before we write. We
631
 
 * also need to make sure the uint32 is arranged so that the first value of 
632
 
 * the first array winds up in b[0]. This means construction of that uint32
633
 
 * is endian specific (even though the layout of the mp_digits in the array 
634
 
 * is always big endian).
635
 
 *
636
 
 * The final data is stored as follows :
637
 
 *
638
 
 * Our same logical array p array, m is sizeof(mp_digit),
639
 
 * N is still count and n is now b_size. If we define p[i].digit[j]0 as the 
640
 
 * most significant byte of the word p[i].digit[j], p[i].digit[j]1 as 
641
 
 * the next most significant byte of p[i].digit[j], ...  and p[i].digit[j]m-1
642
 
 * is the least significant byte. 
643
 
 * Our array would look like:
644
 
 * p[0].digit[0]0     p[1].digit[0]0    ...  p[N-2].digit[0]0    p[N-1].digit[0]0
645
 
 * p[0].digit[0]1     p[1].digit[0]1    ...  p[N-2].digit[0]1    p[N-1].digit[0]1
646
 
 *                .                                         .
647
 
 * p[0].digit[0]m-1   p[1].digit[0]m-1  ...  p[N-2].digit[0]m-1  p[N-1].digit[0]m-1
648
 
 * p[0].digit[1]0     p[1].digit[1]0    ...  p[N-2].digit[1]0    p[N-1].digit[1]0
649
 
 *                .                                         .
650
 
 *                .                                         .
651
 
 * p[0].digit[n-1]m-2 p[1].digit[n-1]m-2 ... p[N-2].digit[n-1]m-2 p[N-1].digit[n-1]m-2
652
 
 * p[0].digit[n-1]m-1 p[1].digit[n-1]m-1 ... p[N-2].digit[n-1]m-1 p[N-1].digit[n-1]m-1 
653
 
 *
654
 
 */
655
 
mp_err mpi_to_weave(const mp_int *a, unsigned char *b, 
656
 
                                        mp_size b_size, mp_size count)
657
 
{
658
 
  mp_size i;
659
 
  mp_digit *digitsa0;
660
 
  mp_digit *digitsa1;
661
 
  mp_digit *digitsa2;
662
 
  mp_digit *digitsa3;
663
 
  mp_size   useda0;
664
 
  mp_size   useda1;
665
 
  mp_size   useda2;
666
 
  mp_size   useda3;
667
 
  mp_weave_word *weaved = (mp_weave_word *)b;
668
 
 
669
 
  count = count/sizeof(mp_weave_word);
670
 
 
671
 
  /* this code pretty much depends on this ! */
672
 
#if MP_ARGCHK == 2
673
 
  assert(WEAVE_WORD_SIZE == 4); 
674
 
  assert(sizeof(mp_weave_word) == 4);
675
 
#endif
676
 
 
677
 
  digitsa0 = MP_DIGITS(&a[0]);
678
 
  digitsa1 = MP_DIGITS(&a[1]);
679
 
  digitsa2 = MP_DIGITS(&a[2]);
680
 
  digitsa3 = MP_DIGITS(&a[3]);
681
 
  useda0 = MP_USED(&a[0]);
682
 
  useda1 = MP_USED(&a[1]);
683
 
  useda2 = MP_USED(&a[2]);
684
 
  useda3 = MP_USED(&a[3]);
685
 
 
686
 
  ARGCHK(MP_SIGN(&a[0]) == MP_ZPOS, MP_BADARG);
687
 
  ARGCHK(MP_SIGN(&a[1]) == MP_ZPOS, MP_BADARG);
688
 
  ARGCHK(MP_SIGN(&a[2]) == MP_ZPOS, MP_BADARG);
689
 
  ARGCHK(MP_SIGN(&a[3]) == MP_ZPOS, MP_BADARG);
690
 
  ARGCHK(useda0 <= b_size, MP_BADARG);
691
 
  ARGCHK(useda1 <= b_size, MP_BADARG);
692
 
  ARGCHK(useda2 <= b_size, MP_BADARG);
693
 
  ARGCHK(useda3 <= b_size, MP_BADARG);
694
 
 
695
 
#define SAFE_FETCH(digit, used, word) ((word) < (used) ? (digit[word]) : 0)
696
 
 
697
 
  for (i=0; i < b_size; i++) {
698
 
    mp_digit d0 = SAFE_FETCH(digitsa0,useda0,i);
699
 
    mp_digit d1 = SAFE_FETCH(digitsa1,useda1,i);
700
 
    mp_digit d2 = SAFE_FETCH(digitsa2,useda2,i);
701
 
    mp_digit d3 = SAFE_FETCH(digitsa3,useda3,i);
702
 
    register mp_weave_word acc;
703
 
 
704
 
/*
705
 
 * ONE_STEP takes the MSB of each of our current digits and places that
706
 
 * byte in the appropriate position for writing to the weaved array.
707
 
 *  On little endian:
708
 
 *   b3 b2 b1 b0
709
 
 *  On big endian:
710
 
 *   b0 b1 b2 b3
711
 
 *  When the data is written it would always wind up:
712
 
 *   b[0] = b0
713
 
 *   b[1] = b1
714
 
 *   b[2] = b2
715
 
 *   b[3] = b3
716
 
 *
717
 
 * Once we've written the MSB, we shift the whole digit up left one
718
 
 * byte, putting the Next Most Significant Byte in the MSB position,
719
 
 * so we we repeat the next one step that byte will be written.
720
 
 * NOTE: This code assumes sizeof(mp_weave_word) and MP_WEAVE_WORD_SIZE
721
 
 * is 4.
722
 
 */
723
 
#ifdef MP_IS_LITTLE_ENDIAN 
724
 
#define MPI_WEAVE_ONE_STEP \
725
 
    acc  = (d0 >> (MP_DIGIT_BIT-8))  & 0x000000ff; d0 <<= 8; /*b0*/ \
726
 
    acc |= (d1 >> (MP_DIGIT_BIT-16)) & 0x0000ff00; d1 <<= 8; /*b1*/ \
727
 
    acc |= (d2 >> (MP_DIGIT_BIT-24)) & 0x00ff0000; d2 <<= 8; /*b2*/ \
728
 
    acc |= (d3 >> (MP_DIGIT_BIT-32)) & 0xff000000; d3 <<= 8; /*b3*/ \
729
 
    *weaved = acc; weaved += count;
730
 
#else 
731
 
#define MPI_WEAVE_ONE_STEP \
732
 
    acc  = (d0 >> (MP_DIGIT_BIT-32)) & 0xff000000; d0 <<= 8; /*b0*/ \
733
 
    acc |= (d1 >> (MP_DIGIT_BIT-24)) & 0x00ff0000; d1 <<= 8; /*b1*/ \
734
 
    acc |= (d2 >> (MP_DIGIT_BIT-16)) & 0x0000ff00; d2 <<= 8; /*b2*/ \
735
 
    acc |= (d3 >> (MP_DIGIT_BIT-8))  & 0x000000ff; d3 <<= 8; /*b3*/ \
736
 
    *weaved = acc; weaved += count;
737
 
#endif 
738
 
   switch (sizeof(mp_digit)) {
739
 
   case 32:
740
 
    MPI_WEAVE_ONE_STEP
741
 
    MPI_WEAVE_ONE_STEP
742
 
    MPI_WEAVE_ONE_STEP
743
 
    MPI_WEAVE_ONE_STEP
744
 
    MPI_WEAVE_ONE_STEP
745
 
    MPI_WEAVE_ONE_STEP
746
 
    MPI_WEAVE_ONE_STEP
747
 
    MPI_WEAVE_ONE_STEP
748
 
    MPI_WEAVE_ONE_STEP
749
 
    MPI_WEAVE_ONE_STEP
750
 
    MPI_WEAVE_ONE_STEP
751
 
    MPI_WEAVE_ONE_STEP
752
 
    MPI_WEAVE_ONE_STEP
753
 
    MPI_WEAVE_ONE_STEP
754
 
    MPI_WEAVE_ONE_STEP
755
 
    MPI_WEAVE_ONE_STEP
756
 
   case 16:
757
 
    MPI_WEAVE_ONE_STEP
758
 
    MPI_WEAVE_ONE_STEP
759
 
    MPI_WEAVE_ONE_STEP
760
 
    MPI_WEAVE_ONE_STEP
761
 
    MPI_WEAVE_ONE_STEP
762
 
    MPI_WEAVE_ONE_STEP
763
 
    MPI_WEAVE_ONE_STEP
764
 
    MPI_WEAVE_ONE_STEP
765
 
   case 8:
766
 
    MPI_WEAVE_ONE_STEP
767
 
    MPI_WEAVE_ONE_STEP
768
 
    MPI_WEAVE_ONE_STEP
769
 
    MPI_WEAVE_ONE_STEP
770
 
   case 4:
771
 
    MPI_WEAVE_ONE_STEP
772
 
    MPI_WEAVE_ONE_STEP
773
 
   case 2:
774
 
    MPI_WEAVE_ONE_STEP
775
 
   case 1:
776
 
    MPI_WEAVE_ONE_STEP
777
 
    break;
778
 
   }
779
 
  }
780
 
 
781
 
  return MP_OKAY;
782
 
}
783
 
 
784
 
/* reverse the operation above for one entry.
785
 
 * b points to the offset into the weave array of the power we are
786
 
 * calculating */
787
 
mp_err weave_to_mpi(mp_int *a, const unsigned char *b, 
788
 
                                        mp_size b_size, mp_size count)
789
 
{
790
 
  mp_digit *pb = MP_DIGITS(a);
791
 
  mp_digit *end = &pb[b_size];
792
 
 
793
 
  MP_SIGN(a) = MP_ZPOS;
794
 
  MP_USED(a) = b_size;
795
 
 
796
 
  for (; pb < end; pb++) {
797
 
    register mp_digit digit;
798
 
 
799
 
    digit = *b << 8; b += count;
800
 
#define MPI_UNWEAVE_ONE_STEP  digit |= *b; b += count; digit = digit << 8;
801
 
    switch (sizeof(mp_digit)) {
802
 
    case 32:
803
 
        MPI_UNWEAVE_ONE_STEP 
804
 
        MPI_UNWEAVE_ONE_STEP 
805
 
        MPI_UNWEAVE_ONE_STEP 
806
 
        MPI_UNWEAVE_ONE_STEP 
807
 
        MPI_UNWEAVE_ONE_STEP 
808
 
        MPI_UNWEAVE_ONE_STEP 
809
 
        MPI_UNWEAVE_ONE_STEP 
810
 
        MPI_UNWEAVE_ONE_STEP 
811
 
        MPI_UNWEAVE_ONE_STEP 
812
 
        MPI_UNWEAVE_ONE_STEP 
813
 
        MPI_UNWEAVE_ONE_STEP 
814
 
        MPI_UNWEAVE_ONE_STEP 
815
 
        MPI_UNWEAVE_ONE_STEP 
816
 
        MPI_UNWEAVE_ONE_STEP 
817
 
        MPI_UNWEAVE_ONE_STEP 
818
 
        MPI_UNWEAVE_ONE_STEP 
819
 
    case 16:
820
 
        MPI_UNWEAVE_ONE_STEP 
821
 
        MPI_UNWEAVE_ONE_STEP 
822
 
        MPI_UNWEAVE_ONE_STEP 
823
 
        MPI_UNWEAVE_ONE_STEP 
824
 
        MPI_UNWEAVE_ONE_STEP 
825
 
        MPI_UNWEAVE_ONE_STEP 
826
 
        MPI_UNWEAVE_ONE_STEP 
827
 
        MPI_UNWEAVE_ONE_STEP 
828
 
    case 8:
829
 
        MPI_UNWEAVE_ONE_STEP 
830
 
        MPI_UNWEAVE_ONE_STEP 
831
 
        MPI_UNWEAVE_ONE_STEP 
832
 
        MPI_UNWEAVE_ONE_STEP 
833
 
    case 4:
834
 
        MPI_UNWEAVE_ONE_STEP 
835
 
        MPI_UNWEAVE_ONE_STEP 
836
 
    case 2:
837
 
        break;
838
 
    }
839
 
    digit |= *b; b += count; 
840
 
 
841
 
    *pb = digit;
842
 
  }
843
 
  s_mp_clamp(a);
844
 
  return MP_OKAY;
845
 
}
846
 
#endif
847
 
 
848
 
 
849
 
#define SQR(a,b) \
850
 
  MP_CHECKOK( mp_sqr(a, b) );\
851
 
  MP_CHECKOK( s_mp_redc(b, mmm) )
852
 
 
853
 
#if defined(MP_MONT_USE_MP_MUL)
854
 
#define MUL_NOWEAVE(x,a,b) \
855
 
  MP_CHECKOK( mp_mul(a, x, b) ); \
856
 
  MP_CHECKOK( s_mp_redc(b, mmm) ) 
857
 
#else
858
 
#define MUL_NOWEAVE(x,a,b) \
859
 
  MP_CHECKOK( s_mp_mul_mont(a, x, b, mmm) )
860
 
#endif
861
 
 
862
 
#define MUL(x,a,b) \
863
 
  MP_CHECKOK( weave_to_mpi(&tmp, powers + (x), nLen, num_powers) ); \
864
 
  MUL_NOWEAVE(&tmp,a,b)
865
 
 
866
 
#define SWAPPA ptmp = pa1; pa1 = pa2; pa2 = ptmp
867
 
#define MP_ALIGN(x,y) ((((ptrdiff_t)(x))+((y)-1))&(((ptrdiff_t)0)-(y)))
868
 
 
869
 
/* Do modular exponentiation using integer multiply code. */
870
 
mp_err mp_exptmod_safe_i(const mp_int *   montBase, 
871
 
                    const mp_int *   exponent, 
872
 
                    const mp_int *   modulus, 
873
 
                    mp_int *         result, 
874
 
                    mp_mont_modulus *mmm, 
875
 
                    int              nLen, 
876
 
                    mp_size          bits_in_exponent, 
877
 
                    mp_size          window_bits,
878
 
                    mp_size          num_powers)
879
 
{
880
 
  mp_int *pa1, *pa2, *ptmp;
881
 
  mp_size i;
882
 
  mp_size first_window;
883
 
  mp_err  res;
884
 
  int     expOff;
885
 
  mp_int  accum1, accum2, accum[WEAVE_WORD_SIZE];
886
 
  mp_int  tmp;
887
 
  unsigned char *powersArray;
888
 
  unsigned char *powers;
889
 
 
890
 
  MP_DIGITS(&accum1) = 0;
891
 
  MP_DIGITS(&accum2) = 0;
892
 
  MP_DIGITS(&accum[0]) = 0;
893
 
  MP_DIGITS(&accum[1]) = 0;
894
 
  MP_DIGITS(&accum[2]) = 0;
895
 
  MP_DIGITS(&accum[3]) = 0;
896
 
  MP_DIGITS(&tmp) = 0;
897
 
 
898
 
  powersArray = (unsigned char *)malloc(num_powers*(nLen*sizeof(mp_digit)+1));
899
 
  if (powersArray == NULL) {
900
 
    res = MP_MEM;
901
 
    goto CLEANUP;
902
 
  }
903
 
 
904
 
  /* powers[i] = base ** (i); */
905
 
  powers = (unsigned char *)MP_ALIGN(powersArray,num_powers);
906
 
 
907
 
  /* grab the first window value. This allows us to preload accumulator1
908
 
   * and save a conversion, some squares and a multiple*/
909
 
  MP_CHECKOK( mpl_get_bits(exponent, 
910
 
                                bits_in_exponent-window_bits, window_bits) );
911
 
  first_window = (mp_size)res;
912
 
 
913
 
  MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
914
 
  MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );
915
 
  MP_CHECKOK( mp_init_size(&tmp, 3 * nLen + 2) );
916
 
 
917
 
  /* build the first WEAVE_WORD powers inline */
918
 
  /* if WEAVE_WORD_SIZE is not 4, this code will have to change */
919
 
  if (num_powers > 2) {
920
 
    MP_CHECKOK( mp_init_size(&accum[0], 3 * nLen + 2) );
921
 
    MP_CHECKOK( mp_init_size(&accum[1], 3 * nLen + 2) );
922
 
    MP_CHECKOK( mp_init_size(&accum[2], 3 * nLen + 2) );
923
 
    MP_CHECKOK( mp_init_size(&accum[3], 3 * nLen + 2) );
924
 
    mp_set(&accum[0], 1);
925
 
    MP_CHECKOK( s_mp_to_mont(&accum[0], mmm, &accum[0]) );
926
 
    MP_CHECKOK( mp_copy(montBase, &accum[1]) );
927
 
    SQR(montBase, &accum[2]);
928
 
    MUL_NOWEAVE(montBase, &accum[2], &accum[3]);
929
 
    MP_CHECKOK( mpi_to_weave(accum, powers, nLen, num_powers) );
930
 
    if (first_window < 4) {
931
 
      MP_CHECKOK( mp_copy(&accum[first_window], &accum1) );
932
 
      first_window = num_powers;
933
 
    }
934
 
  } else {
935
 
      if (first_window == 0) {
936
 
        mp_set(&accum1, 1);
937
 
        MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
938
 
      } else {
939
 
        /* assert first_window == 1? */
940
 
        MP_CHECKOK( mp_copy(montBase, &accum1) );
941
 
      }
942
 
  }
943
 
 
944
 
  /*
945
 
   * calculate all the powers in the powers array.
946
 
   * this adds 2**(k-1)-2 square operations over just calculating the
947
 
   * odd powers where k is the window size in the two other mp_modexpt
948
 
   * implementations in this file. We will get some of that
949
 
   * back by not needing the first 'k' squares and one multiply for the 
950
 
   * first window */ 
951
 
  for (i = WEAVE_WORD_SIZE; i < num_powers; i++) {
952
 
    int acc_index = i & (WEAVE_WORD_SIZE-1); /* i % WEAVE_WORD_SIZE */
953
 
    if ( i & 1 ) {
954
 
      MUL_NOWEAVE(montBase, &accum[acc_index-1] , &accum[acc_index]);
955
 
      /* we've filled the array do our 'per array' processing */
956
 
      if (acc_index == (WEAVE_WORD_SIZE-1)) {
957
 
        MP_CHECKOK( mpi_to_weave(accum, powers + i - (WEAVE_WORD_SIZE-1),
958
 
                                                         nLen, num_powers) );
959
 
 
960
 
        if (first_window <= i) {
961
 
          MP_CHECKOK( mp_copy(&accum[first_window & (WEAVE_WORD_SIZE-1)], 
962
 
                                                                &accum1) );
963
 
          first_window = num_powers;
964
 
        }
965
 
      }
966
 
    } else {
967
 
      /* up to 8 we can find 2^i-1 in the accum array, but at 8 we our source
968
 
       * and target are the same so we need to copy.. After that, the
969
 
       * value is overwritten, so we need to fetch it from the stored
970
 
       * weave array */
971
 
      if (i > 2* WEAVE_WORD_SIZE) {
972
 
        MP_CHECKOK(weave_to_mpi(&accum2, powers+i/2, nLen, num_powers));
973
 
        SQR(&accum2, &accum[acc_index]);
974
 
      } else {
975
 
        int half_power_index = (i/2) & (WEAVE_WORD_SIZE-1);
976
 
        if (half_power_index == acc_index) {
977
 
           /* copy is cheaper than weave_to_mpi */
978
 
           MP_CHECKOK(mp_copy(&accum[half_power_index], &accum2));
979
 
           SQR(&accum2,&accum[acc_index]);
980
 
        } else {
981
 
           SQR(&accum[half_power_index],&accum[acc_index]);
982
 
        }
983
 
      }
984
 
    }
985
 
  }
986
 
  /* if the accum1 isn't set, Then there is something wrong with our logic 
987
 
   * above and is an internal programming error. 
988
 
   */
989
 
#if MP_ARGCHK == 2
990
 
  assert(MP_USED(&accum1) != 0);
991
 
#endif
992
 
 
993
 
  /* set accumulator to montgomery residue of 1 */
994
 
  pa1 = &accum1;
995
 
  pa2 = &accum2;
996
 
 
997
 
  for (expOff = bits_in_exponent - window_bits*2; expOff >= 0; expOff -= window_bits) {
998
 
    mp_size smallExp;
999
 
    MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
1000
 
    smallExp = (mp_size)res;
1001
 
 
1002
 
    /* handle unroll the loops */
1003
 
    switch (window_bits) {
1004
 
    case 1:
1005
 
        if (!smallExp) {
1006
 
            SQR(pa1,pa2); SWAPPA;
1007
 
        } else if (smallExp & 1) {
1008
 
            SQR(pa1,pa2); MUL_NOWEAVE(montBase,pa2,pa1);
1009
 
        } else {
1010
 
            abort();
1011
 
        }
1012
 
        break;
1013
 
    case 6:
1014
 
        SQR(pa1,pa2); SQR(pa2,pa1); 
1015
 
        /* fall through */
1016
 
    case 4:
1017
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
1018
 
        MUL(smallExp, pa1,pa2); SWAPPA;
1019
 
        break;
1020
 
    case 5:
1021
 
        SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
1022
 
        SQR(pa1,pa2); MUL(smallExp,pa2,pa1);
1023
 
        break;
1024
 
    default:
1025
 
        abort(); /* could do a loop? */
1026
 
    }
1027
 
  }
1028
 
 
1029
 
  res = s_mp_redc(pa1, mmm);
1030
 
  mp_exch(pa1, result);
1031
 
 
1032
 
CLEANUP:
1033
 
  mp_clear(&accum1);
1034
 
  mp_clear(&accum2);
1035
 
  mp_clear(&accum[0]);
1036
 
  mp_clear(&accum[1]);
1037
 
  mp_clear(&accum[2]);
1038
 
  mp_clear(&accum[3]);
1039
 
  mp_clear(&tmp);
1040
 
  /* PORT_Memset(powers,0,num_powers*nLen*sizeof(mp_digit)); */
1041
 
  free(powersArray);
1042
 
  return res;
1043
 
}
1044
 
#undef SQR
1045
 
#undef MUL
1046
 
#endif
1047
 
 
1048
 
mp_err mp_exptmod(const mp_int *inBase, const mp_int *exponent, 
1049
 
                  const mp_int *modulus, mp_int *result)
1050
 
{
1051
 
  const mp_int *base;
1052
 
  mp_size bits_in_exponent, i, window_bits, odd_ints;
1053
 
  mp_err  res;
1054
 
  int     nLen;
1055
 
  mp_int  montBase, goodBase;
1056
 
  mp_mont_modulus mmm;
1057
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
1058
 
  static unsigned int max_window_bits;
1059
 
#endif
1060
 
 
1061
 
  /* function for computing n0prime only works if n0 is odd */
1062
 
  if (!mp_isodd(modulus))
1063
 
    return s_mp_exptmod(inBase, exponent, modulus, result);
1064
 
 
1065
 
  MP_DIGITS(&montBase) = 0;
1066
 
  MP_DIGITS(&goodBase) = 0;
1067
 
 
1068
 
  if (mp_cmp(inBase, modulus) < 0) {
1069
 
    base = inBase;
1070
 
  } else {
1071
 
    MP_CHECKOK( mp_init(&goodBase) );
1072
 
    base = &goodBase;
1073
 
    MP_CHECKOK( mp_mod(inBase, modulus, &goodBase) );
1074
 
  }
1075
 
 
1076
 
  nLen  = MP_USED(modulus);
1077
 
  MP_CHECKOK( mp_init_size(&montBase, 2 * nLen + 2) );
1078
 
 
1079
 
  mmm.N = *modulus;                     /* a copy of the mp_int struct */
1080
 
 
1081
 
  /* compute n0', given n0, n0' = -(n0 ** -1) mod MP_RADIX
1082
 
  **            where n0 = least significant mp_digit of N, the modulus.
1083
 
  */
1084
 
  mmm.n0prime = 0 - s_mp_invmod_radix( MP_DIGIT(modulus, 0) );
1085
 
 
1086
 
  MP_CHECKOK( s_mp_to_mont(base, &mmm, &montBase) );
1087
 
 
1088
 
  bits_in_exponent = mpl_significant_bits(exponent);
1089
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
1090
 
  if (mp_using_cache_safe_exp) {
1091
 
    if (bits_in_exponent > 780)
1092
 
        window_bits = 6;
1093
 
    else if (bits_in_exponent > 256)
1094
 
        window_bits = 5;
1095
 
    else if (bits_in_exponent > 20)
1096
 
        window_bits = 4;
1097
 
       /* RSA public key exponents are typically under 20 bits (common values 
1098
 
        * are: 3, 17, 65537) and a 4-bit window is inefficient
1099
 
        */
1100
 
    else 
1101
 
        window_bits = 1;
1102
 
  } else
1103
 
#endif
1104
 
  if (bits_in_exponent > 480)
1105
 
    window_bits = 6;
1106
 
  else if (bits_in_exponent > 160)
1107
 
    window_bits = 5;
1108
 
  else if (bits_in_exponent > 20)
1109
 
    window_bits = 4;
1110
 
  /* RSA public key exponents are typically under 20 bits (common values 
1111
 
   * are: 3, 17, 65537) and a 4-bit window is inefficient
1112
 
   */
1113
 
  else 
1114
 
    window_bits = 1;
1115
 
 
1116
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
1117
 
  /*
1118
 
   * clamp the window size based on
1119
 
   * the cache line size.
1120
 
   */
1121
 
  if (!max_window_bits) {
1122
 
    unsigned long cache_size = s_mpi_getProcessorLineSize();
1123
 
    /* processor has no cache, use 'fast' code always */
1124
 
    if (cache_size == 0) {
1125
 
      mp_using_cache_safe_exp = 0;
1126
 
    } 
1127
 
    if ((cache_size == 0) || (cache_size >= 64)) {
1128
 
      max_window_bits = 6;
1129
 
    } else if (cache_size >= 32) {
1130
 
      max_window_bits = 5;
1131
 
    } else if (cache_size >= 16) {
1132
 
      max_window_bits = 4;
1133
 
    } else max_window_bits = 1; /* should this be an assert? */
1134
 
  }
1135
 
 
1136
 
  /* clamp the window size down before we caclulate bits_in_exponent */
1137
 
  if (mp_using_cache_safe_exp) {
1138
 
    if (window_bits > max_window_bits) {
1139
 
      window_bits = max_window_bits;
1140
 
    }
1141
 
  }
1142
 
#endif
1143
 
 
1144
 
  odd_ints = 1 << (window_bits - 1);
1145
 
  i = bits_in_exponent % window_bits;
1146
 
  if (i != 0) {
1147
 
    bits_in_exponent += window_bits - i;
1148
 
  } 
1149
 
 
1150
 
#ifdef MP_USING_MONT_MULF
1151
 
  if (mp_using_mont_mulf) {
1152
 
    MP_CHECKOK( s_mp_pad(&montBase, nLen) );
1153
 
    res = mp_exptmod_f(&montBase, exponent, modulus, result, &mmm, nLen, 
1154
 
                     bits_in_exponent, window_bits, odd_ints);
1155
 
  } else
1156
 
#endif
1157
 
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
1158
 
  if (mp_using_cache_safe_exp) {
1159
 
    res = mp_exptmod_safe_i(&montBase, exponent, modulus, result, &mmm, nLen, 
1160
 
                     bits_in_exponent, window_bits, 1 << window_bits);
1161
 
  } else
1162
 
#endif
1163
 
  res = mp_exptmod_i(&montBase, exponent, modulus, result, &mmm, nLen, 
1164
 
                     bits_in_exponent, window_bits, odd_ints);
1165
 
 
1166
 
CLEANUP:
1167
 
  mp_clear(&montBase);
1168
 
  mp_clear(&goodBase);
1169
 
  /* Don't mp_clear mmm.N because it is merely a copy of modulus.
1170
 
  ** Just zap it.
1171
 
  */
1172
 
  memset(&mmm, 0, sizeof mmm);
1173
 
  return res;
1174
 
}