Bug Summary

File:s/lib/freebl/mpi/mpmontg.c
Warning:line 54, column 14
Although the value stored to 'res' is used in the enclosing expression, the value is never actually read from 'res'

Annotated Source Code

Press '?' to see keyboard shortcuts

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