1 /* mpn_powm_sec -- Compute R = U^E mod M. Safe variant, not leaking time info.
3 Copyright 2007, 2008, 2009 Free Software Foundation, Inc.
5 This file is part of the GNU MP Library.
7 The GNU MP Library is free software; you can redistribute it and/or modify
8 it under the terms of the GNU Lesser General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
12 The GNU MP Library is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15 License for more details.
17 You should have received a copy of the GNU Lesser General Public License
18 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
22 BASIC ALGORITHM, Compute b^e mod n, where n is odd.
26 2. While w^2 < n (and there are more bits in e)
27 w <- power left-to-right base-2 without reduction
29 3. t <- (B^n * b) / n Convert to REDC form
31 4. Compute power table of e-dependent size
33 5. While there are more bits in e
34 w <- power left-to-right base-k with reduction
39 * Make getbits a macro, thereby allowing it to update the index operand.
40 That will simplify the code using getbits. (Perhaps make getbits' sibling
41 getbit then have similar form, for symmetry.)
43 * Write an itch function.
45 * Choose window size without looping. (Superoptimize or think(tm).)
47 * Make it sub-quadratic.
49 * Call new division functions, not mpn_tdiv_qr.
51 * Is redc obsolete with improved SB division?
53 * Consider special code for one-limb M.
55 * Handle even M (in mpz_powm_sec) with two modexps and CRT.
62 #define WANT_CACHE_SECURITY 1
65 #define getbit(p,bi) \
66 ((p[(bi - 1) / GMP_LIMB_BITS] >> (bi - 1) % GMP_LIMB_BITS) & 1)
68 static inline mp_limb_t
69 getbits (const mp_limb_t
*p
, unsigned long bi
, int nbits
)
77 return p
[0] & (((mp_limb_t
) 1 << bi
) - 1);
81 bi
-= nbits
; /* bit index of low bit to extract */
82 i
= bi
/ GMP_LIMB_BITS
; /* word index of low bit to extract */
83 bi
%= GMP_LIMB_BITS
; /* bit index in low word */
84 r
= p
[i
] >> bi
; /* extract (low) bits */
85 nbits_in_r
= GMP_LIMB_BITS
- bi
; /* number of bits now in r */
86 if (nbits_in_r
< nbits
) /* did we get enough bits? */
87 r
+= p
[i
+ 1] << nbits_in_r
; /* prepend bits from higher word */
88 return r
& (((mp_limb_t
) 1 << nbits
) - 1);
92 #undef HAVE_NATIVE_mpn_addmul_2
94 #ifndef HAVE_NATIVE_mpn_addmul_2
95 #define REDC_2_THRESHOLD MP_SIZE_T_MAX
98 #ifndef REDC_2_THRESHOLD
99 #define REDC_2_THRESHOLD 4
102 static void mpn_redc_n () {ASSERT_ALWAYS(0);}
105 win_size (unsigned long eb
)
108 static unsigned long x
[] = {1,4,27,100,325,1026,2905,7848,20457,51670,~0ul};
109 for (k
= 0; eb
> x
[k
]; k
++)
114 #define MPN_REDC_X(rp, tp, mp, n, mip) \
117 mpn_redc_1 (rp, tp, mp, n, mip[0]); \
118 else if (redc_x == 2) \
119 mpn_redc_2 (rp, tp, mp, n, mip); \
121 mpn_redc_n (rp, tp, mp, n, mip); \
124 /* Convert U to REDC form, U_r = B^n * U mod M */
126 redcify (mp_ptr rp
, mp_srcptr up
, mp_size_t un
, mp_srcptr mp
, mp_size_t n
)
132 tp
= TMP_ALLOC_LIMBS (un
+ n
);
133 qp
= TMP_ALLOC_LIMBS (un
+ 1); /* FIXME: Put at tp+? */
136 MPN_COPY (tp
+ n
, up
, un
);
137 mpn_tdiv_qr (qp
, rp
, 0L, tp
, un
+ n
, mp
, n
);
141 /* rp[n-1..0] = bp[bn-1..0] ^ ep[en-1..0] mod mp[n-1..0]
142 Requires that mp[n-1..0] is odd.
143 Requires that ep[en-1..0] is > 1.
144 Uses scratch space tp[3n..0], i.e., 3n+1 words. */
146 mpn_powm_sec (mp_ptr rp
, mp_srcptr bp
, mp_size_t bn
,
147 mp_srcptr ep
, mp_size_t en
,
148 mp_srcptr mp
, mp_size_t n
, mp_ptr tp
)
153 int windowsize
, this_windowsize
;
155 mp_ptr pp
, this_pp
, last_pp
;
160 ASSERT (en
> 1 || (en
== 1 && ep
[0] > 1));
161 ASSERT (n
>= 1 && ((mp
[0] & 1) != 0));
165 count_leading_zeros (cnt
, ep
[en
- 1]);
166 ebi
= en
* GMP_LIMB_BITS
- cnt
;
168 windowsize
= win_size (ebi
);
170 if (BELOW_THRESHOLD (n
, REDC_2_THRESHOLD
))
172 binvert_limb (mip
[0], mp
[0]);
176 #if defined (HAVE_NATIVE_mpn_addmul_2)
179 mpn_binvert (mip
, mp
, 2, tp
);
180 mip
[0] = -mip
[0]; mip
[1] = ~mip
[1];
185 mpn_binvert (mip
, mp
, n
, tp
);
189 pp
= TMP_ALLOC_LIMBS (n
<< windowsize
);
193 redcify (this_pp
, this_pp
+ n
, 1, mp
, n
);
195 redcify (this_pp
, bp
, bn
, mp
, n
);
197 /* Precompute powers of b and put them in the temporary area at pp. */
198 for (i
= (1 << windowsize
) - 2; i
> 0; i
--)
202 mpn_mul_n (tp
, last_pp
, pp
+ n
, n
);
203 MPN_REDC_X (this_pp
, tp
, mp
, n
, mip
);
206 expbits
= getbits (ep
, ebi
, windowsize
);
211 MPN_COPY (rp
, pp
+ n
* expbits
, n
);
215 expbits
= getbits (ep
, ebi
, windowsize
);
217 this_windowsize
= windowsize
;
220 this_windowsize
+= ebi
;
226 mpn_sqr_n (tp
, rp
, n
);
227 MPN_REDC_X (rp
, tp
, mp
, n
, mip
);
230 while (this_windowsize
!= 0);
232 #if WANT_CACHE_SECURITY
233 mpn_tabselect (tp
+ 2*n
, pp
, n
, 1 << windowsize
, expbits
);
234 mpn_mul_n (tp
, rp
, tp
+ 2*n
, n
);
236 mpn_mul_n (tp
, rp
, pp
+ n
* expbits
, n
);
238 MPN_REDC_X (rp
, tp
, mp
, n
, mip
);
241 MPN_COPY (tp
, rp
, n
);
242 MPN_ZERO (tp
+ n
, n
);
243 MPN_REDC_X (rp
, tp
, mp
, n
, mip
);
244 if (mpn_cmp (rp
, mp
, n
) >= 0)
245 mpn_sub_n (rp
, rp
, mp
, n
);
249 #if ! HAVE_NATIVE_mpn_tabselect
250 /* Select entry `which' from table `tab', which has nents entries, each `n'
251 limbs. Store the selected entry at rp. Reads entire table to avoid
252 sideband information leaks. O(n*nents). */
255 mpn_tabselect (volatile mp_limb_t
*rp
, volatile mp_limb_t
*tab
, mp_size_t n
,
256 mp_size_t nents
, mp_size_t which
)
260 volatile mp_limb_t
*tp
;
262 for (k
= 0; k
< nents
; k
++)
264 mask
= -(mp_limb_t
) (which
== k
);
266 for (i
= 0; i
< n
; i
++)
268 rp
[i
] = (rp
[i
] & ~mask
) | (tp
[i
] & mask
);