bn_exp.c 43 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367
  1. /*
  2. * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include "internal/cryptlib.h"
  10. #include "internal/constant_time_locl.h"
  11. #include "bn_lcl.h"
  12. #include <stdlib.h>
  13. #ifdef _WIN32
  14. # include <malloc.h>
  15. # ifndef alloca
  16. # define alloca _alloca
  17. # endif
  18. #elif defined(__GNUC__)
  19. # ifndef alloca
  20. # define alloca(s) __builtin_alloca((s))
  21. # endif
  22. #elif defined(__sun)
  23. # include <alloca.h>
  24. #endif
  25. #include "rsaz_exp.h"
  26. #undef SPARC_T4_MONT
  27. #if defined(OPENSSL_BN_ASM_MONT) && (defined(__sparc__) || defined(__sparc))
  28. # include "sparc_arch.h"
  29. extern unsigned int OPENSSL_sparcv9cap_P[];
  30. # define SPARC_T4_MONT
  31. #endif
  32. /* maximum precomputation table size for *variable* sliding windows */
  33. #define TABLE_SIZE 32
  34. /* this one works - simple but works */
  35. int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  36. {
  37. int i, bits, ret = 0;
  38. BIGNUM *v, *rr;
  39. if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
  40. || BN_get_flags(a, BN_FLG_CONSTTIME) != 0) {
  41. /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
  42. BNerr(BN_F_BN_EXP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
  43. return 0;
  44. }
  45. BN_CTX_start(ctx);
  46. rr = ((r == a) || (r == p)) ? BN_CTX_get(ctx) : r;
  47. v = BN_CTX_get(ctx);
  48. if (rr == NULL || v == NULL)
  49. goto err;
  50. if (BN_copy(v, a) == NULL)
  51. goto err;
  52. bits = BN_num_bits(p);
  53. if (BN_is_odd(p)) {
  54. if (BN_copy(rr, a) == NULL)
  55. goto err;
  56. } else {
  57. if (!BN_one(rr))
  58. goto err;
  59. }
  60. for (i = 1; i < bits; i++) {
  61. if (!BN_sqr(v, v, ctx))
  62. goto err;
  63. if (BN_is_bit_set(p, i)) {
  64. if (!BN_mul(rr, rr, v, ctx))
  65. goto err;
  66. }
  67. }
  68. if (r != rr && BN_copy(r, rr) == NULL)
  69. goto err;
  70. ret = 1;
  71. err:
  72. BN_CTX_end(ctx);
  73. bn_check_top(r);
  74. return ret;
  75. }
  76. int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
  77. BN_CTX *ctx)
  78. {
  79. int ret;
  80. bn_check_top(a);
  81. bn_check_top(p);
  82. bn_check_top(m);
  83. /*-
  84. * For even modulus m = 2^k*m_odd, it might make sense to compute
  85. * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
  86. * exponentiation for the odd part), using appropriate exponent
  87. * reductions, and combine the results using the CRT.
  88. *
  89. * For now, we use Montgomery only if the modulus is odd; otherwise,
  90. * exponentiation using the reciprocal-based quick remaindering
  91. * algorithm is used.
  92. *
  93. * (Timing obtained with expspeed.c [computations a^p mod m
  94. * where a, p, m are of the same length: 256, 512, 1024, 2048,
  95. * 4096, 8192 bits], compared to the running time of the
  96. * standard algorithm:
  97. *
  98. * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
  99. * 55 .. 77 % [UltraSparc processor, but
  100. * debug-solaris-sparcv8-gcc conf.]
  101. *
  102. * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
  103. * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
  104. *
  105. * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
  106. * at 2048 and more bits, but at 512 and 1024 bits, it was
  107. * slower even than the standard algorithm!
  108. *
  109. * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
  110. * should be obtained when the new Montgomery reduction code
  111. * has been integrated into OpenSSL.)
  112. */
  113. #define MONT_MUL_MOD
  114. #define MONT_EXP_WORD
  115. #define RECP_MUL_MOD
  116. #ifdef MONT_MUL_MOD
  117. if (BN_is_odd(m)) {
  118. # ifdef MONT_EXP_WORD
  119. if (a->top == 1 && !a->neg
  120. && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)
  121. && (BN_get_flags(a, BN_FLG_CONSTTIME) == 0)
  122. && (BN_get_flags(m, BN_FLG_CONSTTIME) == 0)) {
  123. BN_ULONG A = a->d[0];
  124. ret = BN_mod_exp_mont_word(r, A, p, m, ctx, NULL);
  125. } else
  126. # endif
  127. ret = BN_mod_exp_mont(r, a, p, m, ctx, NULL);
  128. } else
  129. #endif
  130. #ifdef RECP_MUL_MOD
  131. {
  132. ret = BN_mod_exp_recp(r, a, p, m, ctx);
  133. }
  134. #else
  135. {
  136. ret = BN_mod_exp_simple(r, a, p, m, ctx);
  137. }
  138. #endif
  139. bn_check_top(r);
  140. return ret;
  141. }
  142. int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
  143. const BIGNUM *m, BN_CTX *ctx)
  144. {
  145. int i, j, bits, ret = 0, wstart, wend, window, wvalue;
  146. int start = 1;
  147. BIGNUM *aa;
  148. /* Table of variables obtained from 'ctx' */
  149. BIGNUM *val[TABLE_SIZE];
  150. BN_RECP_CTX recp;
  151. if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
  152. || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
  153. || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
  154. /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
  155. BNerr(BN_F_BN_MOD_EXP_RECP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
  156. return 0;
  157. }
  158. bits = BN_num_bits(p);
  159. if (bits == 0) {
  160. /* x**0 mod 1 is still zero. */
  161. if (BN_is_one(m)) {
  162. ret = 1;
  163. BN_zero(r);
  164. } else {
  165. ret = BN_one(r);
  166. }
  167. return ret;
  168. }
  169. BN_CTX_start(ctx);
  170. aa = BN_CTX_get(ctx);
  171. val[0] = BN_CTX_get(ctx);
  172. if (val[0] == NULL)
  173. goto err;
  174. BN_RECP_CTX_init(&recp);
  175. if (m->neg) {
  176. /* ignore sign of 'm' */
  177. if (!BN_copy(aa, m))
  178. goto err;
  179. aa->neg = 0;
  180. if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0)
  181. goto err;
  182. } else {
  183. if (BN_RECP_CTX_set(&recp, m, ctx) <= 0)
  184. goto err;
  185. }
  186. if (!BN_nnmod(val[0], a, m, ctx))
  187. goto err; /* 1 */
  188. if (BN_is_zero(val[0])) {
  189. BN_zero(r);
  190. ret = 1;
  191. goto err;
  192. }
  193. window = BN_window_bits_for_exponent_size(bits);
  194. if (window > 1) {
  195. if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx))
  196. goto err; /* 2 */
  197. j = 1 << (window - 1);
  198. for (i = 1; i < j; i++) {
  199. if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
  200. !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx))
  201. goto err;
  202. }
  203. }
  204. start = 1; /* This is used to avoid multiplication etc
  205. * when there is only the value '1' in the
  206. * buffer. */
  207. wvalue = 0; /* The 'value' of the window */
  208. wstart = bits - 1; /* The top bit of the window */
  209. wend = 0; /* The bottom bit of the window */
  210. if (!BN_one(r))
  211. goto err;
  212. for (;;) {
  213. if (BN_is_bit_set(p, wstart) == 0) {
  214. if (!start)
  215. if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
  216. goto err;
  217. if (wstart == 0)
  218. break;
  219. wstart--;
  220. continue;
  221. }
  222. /*
  223. * We now have wstart on a 'set' bit, we now need to work out how bit
  224. * a window to do. To do this we need to scan forward until the last
  225. * set bit before the end of the window
  226. */
  227. j = wstart;
  228. wvalue = 1;
  229. wend = 0;
  230. for (i = 1; i < window; i++) {
  231. if (wstart - i < 0)
  232. break;
  233. if (BN_is_bit_set(p, wstart - i)) {
  234. wvalue <<= (i - wend);
  235. wvalue |= 1;
  236. wend = i;
  237. }
  238. }
  239. /* wend is the size of the current window */
  240. j = wend + 1;
  241. /* add the 'bytes above' */
  242. if (!start)
  243. for (i = 0; i < j; i++) {
  244. if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
  245. goto err;
  246. }
  247. /* wvalue will be an odd number < 2^window */
  248. if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx))
  249. goto err;
  250. /* move the 'window' down further */
  251. wstart -= wend + 1;
  252. wvalue = 0;
  253. start = 0;
  254. if (wstart < 0)
  255. break;
  256. }
  257. ret = 1;
  258. err:
  259. BN_CTX_end(ctx);
  260. BN_RECP_CTX_free(&recp);
  261. bn_check_top(r);
  262. return ret;
  263. }
  264. int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
  265. const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
  266. {
  267. int i, j, bits, ret = 0, wstart, wend, window, wvalue;
  268. int start = 1;
  269. BIGNUM *d, *r;
  270. const BIGNUM *aa;
  271. /* Table of variables obtained from 'ctx' */
  272. BIGNUM *val[TABLE_SIZE];
  273. BN_MONT_CTX *mont = NULL;
  274. if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
  275. || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
  276. || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
  277. return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
  278. }
  279. bn_check_top(a);
  280. bn_check_top(p);
  281. bn_check_top(m);
  282. if (!BN_is_odd(m)) {
  283. BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS);
  284. return 0;
  285. }
  286. bits = BN_num_bits(p);
  287. if (bits == 0) {
  288. /* x**0 mod 1 is still zero. */
  289. if (BN_is_one(m)) {
  290. ret = 1;
  291. BN_zero(rr);
  292. } else {
  293. ret = BN_one(rr);
  294. }
  295. return ret;
  296. }
  297. BN_CTX_start(ctx);
  298. d = BN_CTX_get(ctx);
  299. r = BN_CTX_get(ctx);
  300. val[0] = BN_CTX_get(ctx);
  301. if (val[0] == NULL)
  302. goto err;
  303. /*
  304. * If this is not done, things will break in the montgomery part
  305. */
  306. if (in_mont != NULL)
  307. mont = in_mont;
  308. else {
  309. if ((mont = BN_MONT_CTX_new()) == NULL)
  310. goto err;
  311. if (!BN_MONT_CTX_set(mont, m, ctx))
  312. goto err;
  313. }
  314. if (a->neg || BN_ucmp(a, m) >= 0) {
  315. if (!BN_nnmod(val[0], a, m, ctx))
  316. goto err;
  317. aa = val[0];
  318. } else
  319. aa = a;
  320. if (BN_is_zero(aa)) {
  321. BN_zero(rr);
  322. ret = 1;
  323. goto err;
  324. }
  325. if (!BN_to_montgomery(val[0], aa, mont, ctx))
  326. goto err; /* 1 */
  327. window = BN_window_bits_for_exponent_size(bits);
  328. if (window > 1) {
  329. if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx))
  330. goto err; /* 2 */
  331. j = 1 << (window - 1);
  332. for (i = 1; i < j; i++) {
  333. if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
  334. !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx))
  335. goto err;
  336. }
  337. }
  338. start = 1; /* This is used to avoid multiplication etc
  339. * when there is only the value '1' in the
  340. * buffer. */
  341. wvalue = 0; /* The 'value' of the window */
  342. wstart = bits - 1; /* The top bit of the window */
  343. wend = 0; /* The bottom bit of the window */
  344. #if 1 /* by Shay Gueron's suggestion */
  345. j = m->top; /* borrow j */
  346. if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
  347. if (bn_wexpand(r, j) == NULL)
  348. goto err;
  349. /* 2^(top*BN_BITS2) - m */
  350. r->d[0] = (0 - m->d[0]) & BN_MASK2;
  351. for (i = 1; i < j; i++)
  352. r->d[i] = (~m->d[i]) & BN_MASK2;
  353. r->top = j;
  354. /*
  355. * Upper words will be zero if the corresponding words of 'm' were
  356. * 0xfff[...], so decrement r->top accordingly.
  357. */
  358. bn_correct_top(r);
  359. } else
  360. #endif
  361. if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
  362. goto err;
  363. for (;;) {
  364. if (BN_is_bit_set(p, wstart) == 0) {
  365. if (!start) {
  366. if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
  367. goto err;
  368. }
  369. if (wstart == 0)
  370. break;
  371. wstart--;
  372. continue;
  373. }
  374. /*
  375. * We now have wstart on a 'set' bit, we now need to work out how bit
  376. * a window to do. To do this we need to scan forward until the last
  377. * set bit before the end of the window
  378. */
  379. j = wstart;
  380. wvalue = 1;
  381. wend = 0;
  382. for (i = 1; i < window; i++) {
  383. if (wstart - i < 0)
  384. break;
  385. if (BN_is_bit_set(p, wstart - i)) {
  386. wvalue <<= (i - wend);
  387. wvalue |= 1;
  388. wend = i;
  389. }
  390. }
  391. /* wend is the size of the current window */
  392. j = wend + 1;
  393. /* add the 'bytes above' */
  394. if (!start)
  395. for (i = 0; i < j; i++) {
  396. if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
  397. goto err;
  398. }
  399. /* wvalue will be an odd number < 2^window */
  400. if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx))
  401. goto err;
  402. /* move the 'window' down further */
  403. wstart -= wend + 1;
  404. wvalue = 0;
  405. start = 0;
  406. if (wstart < 0)
  407. break;
  408. }
  409. #if defined(SPARC_T4_MONT)
  410. if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {
  411. j = mont->N.top; /* borrow j */
  412. val[0]->d[0] = 1; /* borrow val[0] */
  413. for (i = 1; i < j; i++)
  414. val[0]->d[i] = 0;
  415. val[0]->top = j;
  416. if (!BN_mod_mul_montgomery(rr, r, val[0], mont, ctx))
  417. goto err;
  418. } else
  419. #endif
  420. if (!BN_from_montgomery(rr, r, mont, ctx))
  421. goto err;
  422. ret = 1;
  423. err:
  424. if (in_mont == NULL)
  425. BN_MONT_CTX_free(mont);
  426. BN_CTX_end(ctx);
  427. bn_check_top(rr);
  428. return ret;
  429. }
  430. #if defined(SPARC_T4_MONT)
  431. static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos)
  432. {
  433. BN_ULONG ret = 0;
  434. int wordpos;
  435. wordpos = bitpos / BN_BITS2;
  436. bitpos %= BN_BITS2;
  437. if (wordpos >= 0 && wordpos < a->top) {
  438. ret = a->d[wordpos] & BN_MASK2;
  439. if (bitpos) {
  440. ret >>= bitpos;
  441. if (++wordpos < a->top)
  442. ret |= a->d[wordpos] << (BN_BITS2 - bitpos);
  443. }
  444. }
  445. return ret & BN_MASK2;
  446. }
  447. #endif
  448. /*
  449. * BN_mod_exp_mont_consttime() stores the precomputed powers in a specific
  450. * layout so that accessing any of these table values shows the same access
  451. * pattern as far as cache lines are concerned. The following functions are
  452. * used to transfer a BIGNUM from/to that table.
  453. */
  454. static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top,
  455. unsigned char *buf, int idx,
  456. int window)
  457. {
  458. int i, j;
  459. int width = 1 << window;
  460. BN_ULONG *table = (BN_ULONG *)buf;
  461. if (top > b->top)
  462. top = b->top; /* this works because 'buf' is explicitly
  463. * zeroed */
  464. for (i = 0, j = idx; i < top; i++, j += width) {
  465. table[j] = b->d[i];
  466. }
  467. return 1;
  468. }
  469. static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,
  470. unsigned char *buf, int idx,
  471. int window)
  472. {
  473. int i, j;
  474. int width = 1 << window;
  475. /*
  476. * We declare table 'volatile' in order to discourage compiler
  477. * from reordering loads from the table. Concern is that if
  478. * reordered in specific manner loads might give away the
  479. * information we are trying to conceal. Some would argue that
  480. * compiler can reorder them anyway, but it can as well be
  481. * argued that doing so would be violation of standard...
  482. */
  483. volatile BN_ULONG *table = (volatile BN_ULONG *)buf;
  484. if (bn_wexpand(b, top) == NULL)
  485. return 0;
  486. if (window <= 3) {
  487. for (i = 0; i < top; i++, table += width) {
  488. BN_ULONG acc = 0;
  489. for (j = 0; j < width; j++) {
  490. acc |= table[j] &
  491. ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
  492. }
  493. b->d[i] = acc;
  494. }
  495. } else {
  496. int xstride = 1 << (window - 2);
  497. BN_ULONG y0, y1, y2, y3;
  498. i = idx >> (window - 2); /* equivalent of idx / xstride */
  499. idx &= xstride - 1; /* equivalent of idx % xstride */
  500. y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1);
  501. y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1);
  502. y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1);
  503. y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1);
  504. for (i = 0; i < top; i++, table += width) {
  505. BN_ULONG acc = 0;
  506. for (j = 0; j < xstride; j++) {
  507. acc |= ( (table[j + 0 * xstride] & y0) |
  508. (table[j + 1 * xstride] & y1) |
  509. (table[j + 2 * xstride] & y2) |
  510. (table[j + 3 * xstride] & y3) )
  511. & ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
  512. }
  513. b->d[i] = acc;
  514. }
  515. }
  516. b->top = top;
  517. bn_correct_top(b);
  518. return 1;
  519. }
  520. /*
  521. * Given a pointer value, compute the next address that is a cache line
  522. * multiple.
  523. */
  524. #define MOD_EXP_CTIME_ALIGN(x_) \
  525. ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
  526. /*
  527. * This variant of BN_mod_exp_mont() uses fixed windows and the special
  528. * precomputation memory layout to limit data-dependency to a minimum to
  529. * protect secret exponents (cf. the hyper-threading timing attacks pointed
  530. * out by Colin Percival,
  531. * http://www.daemonology.net/hyperthreading-considered-harmful/)
  532. */
  533. int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
  534. const BIGNUM *m, BN_CTX *ctx,
  535. BN_MONT_CTX *in_mont)
  536. {
  537. int i, bits, ret = 0, window, wvalue;
  538. int top;
  539. BN_MONT_CTX *mont = NULL;
  540. int numPowers;
  541. unsigned char *powerbufFree = NULL;
  542. int powerbufLen = 0;
  543. unsigned char *powerbuf = NULL;
  544. BIGNUM tmp, am;
  545. #if defined(SPARC_T4_MONT)
  546. unsigned int t4 = 0;
  547. #endif
  548. bn_check_top(a);
  549. bn_check_top(p);
  550. bn_check_top(m);
  551. if (!BN_is_odd(m)) {
  552. BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME, BN_R_CALLED_WITH_EVEN_MODULUS);
  553. return 0;
  554. }
  555. top = m->top;
  556. /*
  557. * Use all bits stored in |p|, rather than |BN_num_bits|, so we do not leak
  558. * whether the top bits are zero.
  559. */
  560. bits = p->top * BN_BITS2;
  561. if (bits == 0) {
  562. /* x**0 mod 1 is still zero. */
  563. if (BN_is_one(m)) {
  564. ret = 1;
  565. BN_zero(rr);
  566. } else {
  567. ret = BN_one(rr);
  568. }
  569. return ret;
  570. }
  571. BN_CTX_start(ctx);
  572. /*
  573. * Allocate a montgomery context if it was not supplied by the caller. If
  574. * this is not done, things will break in the montgomery part.
  575. */
  576. if (in_mont != NULL)
  577. mont = in_mont;
  578. else {
  579. if ((mont = BN_MONT_CTX_new()) == NULL)
  580. goto err;
  581. if (!BN_MONT_CTX_set(mont, m, ctx))
  582. goto err;
  583. }
  584. #ifdef RSAZ_ENABLED
  585. if (!a->neg) {
  586. /*
  587. * If the size of the operands allow it, perform the optimized
  588. * RSAZ exponentiation. For further information see
  589. * crypto/bn/rsaz_exp.c and accompanying assembly modules.
  590. */
  591. if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024)
  592. && rsaz_avx2_eligible()) {
  593. if (NULL == bn_wexpand(rr, 16))
  594. goto err;
  595. RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d,
  596. mont->n0[0]);
  597. rr->top = 16;
  598. rr->neg = 0;
  599. bn_correct_top(rr);
  600. ret = 1;
  601. goto err;
  602. } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) {
  603. if (NULL == bn_wexpand(rr, 8))
  604. goto err;
  605. RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d);
  606. rr->top = 8;
  607. rr->neg = 0;
  608. bn_correct_top(rr);
  609. ret = 1;
  610. goto err;
  611. }
  612. }
  613. #endif
  614. /* Get the window size to use with size of p. */
  615. window = BN_window_bits_for_ctime_exponent_size(bits);
  616. #if defined(SPARC_T4_MONT)
  617. if (window >= 5 && (top & 15) == 0 && top <= 64 &&
  618. (OPENSSL_sparcv9cap_P[1] & (CFR_MONTMUL | CFR_MONTSQR)) ==
  619. (CFR_MONTMUL | CFR_MONTSQR) && (t4 = OPENSSL_sparcv9cap_P[0]))
  620. window = 5;
  621. else
  622. #endif
  623. #if defined(OPENSSL_BN_ASM_MONT5)
  624. if (window >= 5) {
  625. window = 5; /* ~5% improvement for RSA2048 sign, and even
  626. * for RSA4096 */
  627. /* reserve space for mont->N.d[] copy */
  628. powerbufLen += top * sizeof(mont->N.d[0]);
  629. }
  630. #endif
  631. (void)0;
  632. /*
  633. * Allocate a buffer large enough to hold all of the pre-computed powers
  634. * of am, am itself and tmp.
  635. */
  636. numPowers = 1 << window;
  637. powerbufLen += sizeof(m->d[0]) * (top * numPowers +
  638. ((2 * top) >
  639. numPowers ? (2 * top) : numPowers));
  640. #ifdef alloca
  641. if (powerbufLen < 3072)
  642. powerbufFree =
  643. alloca(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH);
  644. else
  645. #endif
  646. if ((powerbufFree =
  647. OPENSSL_malloc(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH))
  648. == NULL)
  649. goto err;
  650. powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
  651. memset(powerbuf, 0, powerbufLen);
  652. #ifdef alloca
  653. if (powerbufLen < 3072)
  654. powerbufFree = NULL;
  655. #endif
  656. /* lay down tmp and am right after powers table */
  657. tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0]) * top * numPowers);
  658. am.d = tmp.d + top;
  659. tmp.top = am.top = 0;
  660. tmp.dmax = am.dmax = top;
  661. tmp.neg = am.neg = 0;
  662. tmp.flags = am.flags = BN_FLG_STATIC_DATA;
  663. /* prepare a^0 in Montgomery domain */
  664. #if 1 /* by Shay Gueron's suggestion */
  665. if (m->d[top - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
  666. /* 2^(top*BN_BITS2) - m */
  667. tmp.d[0] = (0 - m->d[0]) & BN_MASK2;
  668. for (i = 1; i < top; i++)
  669. tmp.d[i] = (~m->d[i]) & BN_MASK2;
  670. tmp.top = top;
  671. } else
  672. #endif
  673. if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx))
  674. goto err;
  675. /* prepare a^1 in Montgomery domain */
  676. if (a->neg || BN_ucmp(a, m) >= 0) {
  677. if (!BN_nnmod(&am, a, m, ctx))
  678. goto err;
  679. if (!BN_to_montgomery(&am, &am, mont, ctx))
  680. goto err;
  681. } else if (!BN_to_montgomery(&am, a, mont, ctx))
  682. goto err;
  683. #if defined(SPARC_T4_MONT)
  684. if (t4) {
  685. typedef int (*bn_pwr5_mont_f) (BN_ULONG *tp, const BN_ULONG *np,
  686. const BN_ULONG *n0, const void *table,
  687. int power, int bits);
  688. int bn_pwr5_mont_t4_8(BN_ULONG *tp, const BN_ULONG *np,
  689. const BN_ULONG *n0, const void *table,
  690. int power, int bits);
  691. int bn_pwr5_mont_t4_16(BN_ULONG *tp, const BN_ULONG *np,
  692. const BN_ULONG *n0, const void *table,
  693. int power, int bits);
  694. int bn_pwr5_mont_t4_24(BN_ULONG *tp, const BN_ULONG *np,
  695. const BN_ULONG *n0, const void *table,
  696. int power, int bits);
  697. int bn_pwr5_mont_t4_32(BN_ULONG *tp, const BN_ULONG *np,
  698. const BN_ULONG *n0, const void *table,
  699. int power, int bits);
  700. static const bn_pwr5_mont_f pwr5_funcs[4] = {
  701. bn_pwr5_mont_t4_8, bn_pwr5_mont_t4_16,
  702. bn_pwr5_mont_t4_24, bn_pwr5_mont_t4_32
  703. };
  704. bn_pwr5_mont_f pwr5_worker = pwr5_funcs[top / 16 - 1];
  705. typedef int (*bn_mul_mont_f) (BN_ULONG *rp, const BN_ULONG *ap,
  706. const void *bp, const BN_ULONG *np,
  707. const BN_ULONG *n0);
  708. int bn_mul_mont_t4_8(BN_ULONG *rp, const BN_ULONG *ap, const void *bp,
  709. const BN_ULONG *np, const BN_ULONG *n0);
  710. int bn_mul_mont_t4_16(BN_ULONG *rp, const BN_ULONG *ap,
  711. const void *bp, const BN_ULONG *np,
  712. const BN_ULONG *n0);
  713. int bn_mul_mont_t4_24(BN_ULONG *rp, const BN_ULONG *ap,
  714. const void *bp, const BN_ULONG *np,
  715. const BN_ULONG *n0);
  716. int bn_mul_mont_t4_32(BN_ULONG *rp, const BN_ULONG *ap,
  717. const void *bp, const BN_ULONG *np,
  718. const BN_ULONG *n0);
  719. static const bn_mul_mont_f mul_funcs[4] = {
  720. bn_mul_mont_t4_8, bn_mul_mont_t4_16,
  721. bn_mul_mont_t4_24, bn_mul_mont_t4_32
  722. };
  723. bn_mul_mont_f mul_worker = mul_funcs[top / 16 - 1];
  724. void bn_mul_mont_vis3(BN_ULONG *rp, const BN_ULONG *ap,
  725. const void *bp, const BN_ULONG *np,
  726. const BN_ULONG *n0, int num);
  727. void bn_mul_mont_t4(BN_ULONG *rp, const BN_ULONG *ap,
  728. const void *bp, const BN_ULONG *np,
  729. const BN_ULONG *n0, int num);
  730. void bn_mul_mont_gather5_t4(BN_ULONG *rp, const BN_ULONG *ap,
  731. const void *table, const BN_ULONG *np,
  732. const BN_ULONG *n0, int num, int power);
  733. void bn_flip_n_scatter5_t4(const BN_ULONG *inp, size_t num,
  734. void *table, size_t power);
  735. void bn_gather5_t4(BN_ULONG *out, size_t num,
  736. void *table, size_t power);
  737. void bn_flip_t4(BN_ULONG *dst, BN_ULONG *src, size_t num);
  738. BN_ULONG *np = mont->N.d, *n0 = mont->n0;
  739. int stride = 5 * (6 - (top / 16 - 1)); /* multiple of 5, but less
  740. * than 32 */
  741. /*
  742. * BN_to_montgomery can contaminate words above .top [in
  743. * BN_DEBUG[_DEBUG] build]...
  744. */
  745. for (i = am.top; i < top; i++)
  746. am.d[i] = 0;
  747. for (i = tmp.top; i < top; i++)
  748. tmp.d[i] = 0;
  749. bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, 0);
  750. bn_flip_n_scatter5_t4(am.d, top, powerbuf, 1);
  751. if (!(*mul_worker) (tmp.d, am.d, am.d, np, n0) &&
  752. !(*mul_worker) (tmp.d, am.d, am.d, np, n0))
  753. bn_mul_mont_vis3(tmp.d, am.d, am.d, np, n0, top);
  754. bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, 2);
  755. for (i = 3; i < 32; i++) {
  756. /* Calculate a^i = a^(i-1) * a */
  757. if (!(*mul_worker) (tmp.d, tmp.d, am.d, np, n0) &&
  758. !(*mul_worker) (tmp.d, tmp.d, am.d, np, n0))
  759. bn_mul_mont_vis3(tmp.d, tmp.d, am.d, np, n0, top);
  760. bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, i);
  761. }
  762. /* switch to 64-bit domain */
  763. np = alloca(top * sizeof(BN_ULONG));
  764. top /= 2;
  765. bn_flip_t4(np, mont->N.d, top);
  766. bits--;
  767. for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--)
  768. wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
  769. bn_gather5_t4(tmp.d, top, powerbuf, wvalue);
  770. /*
  771. * Scan the exponent one window at a time starting from the most
  772. * significant bits.
  773. */
  774. while (bits >= 0) {
  775. if (bits < stride)
  776. stride = bits + 1;
  777. bits -= stride;
  778. wvalue = bn_get_bits(p, bits + 1);
  779. if ((*pwr5_worker) (tmp.d, np, n0, powerbuf, wvalue, stride))
  780. continue;
  781. /* retry once and fall back */
  782. if ((*pwr5_worker) (tmp.d, np, n0, powerbuf, wvalue, stride))
  783. continue;
  784. bits += stride - 5;
  785. wvalue >>= stride - 5;
  786. wvalue &= 31;
  787. bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top);
  788. bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top);
  789. bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top);
  790. bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top);
  791. bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top);
  792. bn_mul_mont_gather5_t4(tmp.d, tmp.d, powerbuf, np, n0, top,
  793. wvalue);
  794. }
  795. bn_flip_t4(tmp.d, tmp.d, top);
  796. top *= 2;
  797. /* back to 32-bit domain */
  798. tmp.top = top;
  799. bn_correct_top(&tmp);
  800. OPENSSL_cleanse(np, top * sizeof(BN_ULONG));
  801. } else
  802. #endif
  803. #if defined(OPENSSL_BN_ASM_MONT5)
  804. if (window == 5 && top > 1) {
  805. /*
  806. * This optimization uses ideas from http://eprint.iacr.org/2011/239,
  807. * specifically optimization of cache-timing attack countermeasures
  808. * and pre-computation optimization.
  809. */
  810. /*
  811. * Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as
  812. * 512-bit RSA is hardly relevant, we omit it to spare size...
  813. */
  814. void bn_mul_mont_gather5(BN_ULONG *rp, const BN_ULONG *ap,
  815. const void *table, const BN_ULONG *np,
  816. const BN_ULONG *n0, int num, int power);
  817. void bn_scatter5(const BN_ULONG *inp, size_t num,
  818. void *table, size_t power);
  819. void bn_gather5(BN_ULONG *out, size_t num, void *table, size_t power);
  820. void bn_power5(BN_ULONG *rp, const BN_ULONG *ap,
  821. const void *table, const BN_ULONG *np,
  822. const BN_ULONG *n0, int num, int power);
  823. int bn_get_bits5(const BN_ULONG *ap, int off);
  824. int bn_from_montgomery(BN_ULONG *rp, const BN_ULONG *ap,
  825. const BN_ULONG *not_used, const BN_ULONG *np,
  826. const BN_ULONG *n0, int num);
  827. BN_ULONG *n0 = mont->n0, *np;
  828. /*
  829. * BN_to_montgomery can contaminate words above .top [in
  830. * BN_DEBUG[_DEBUG] build]...
  831. */
  832. for (i = am.top; i < top; i++)
  833. am.d[i] = 0;
  834. for (i = tmp.top; i < top; i++)
  835. tmp.d[i] = 0;
  836. /*
  837. * copy mont->N.d[] to improve cache locality
  838. */
  839. for (np = am.d + top, i = 0; i < top; i++)
  840. np[i] = mont->N.d[i];
  841. bn_scatter5(tmp.d, top, powerbuf, 0);
  842. bn_scatter5(am.d, am.top, powerbuf, 1);
  843. bn_mul_mont(tmp.d, am.d, am.d, np, n0, top);
  844. bn_scatter5(tmp.d, top, powerbuf, 2);
  845. # if 0
  846. for (i = 3; i < 32; i++) {
  847. /* Calculate a^i = a^(i-1) * a */
  848. bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
  849. bn_scatter5(tmp.d, top, powerbuf, i);
  850. }
  851. # else
  852. /* same as above, but uses squaring for 1/2 of operations */
  853. for (i = 4; i < 32; i *= 2) {
  854. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  855. bn_scatter5(tmp.d, top, powerbuf, i);
  856. }
  857. for (i = 3; i < 8; i += 2) {
  858. int j;
  859. bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
  860. bn_scatter5(tmp.d, top, powerbuf, i);
  861. for (j = 2 * i; j < 32; j *= 2) {
  862. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  863. bn_scatter5(tmp.d, top, powerbuf, j);
  864. }
  865. }
  866. for (; i < 16; i += 2) {
  867. bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
  868. bn_scatter5(tmp.d, top, powerbuf, i);
  869. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  870. bn_scatter5(tmp.d, top, powerbuf, 2 * i);
  871. }
  872. for (; i < 32; i += 2) {
  873. bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
  874. bn_scatter5(tmp.d, top, powerbuf, i);
  875. }
  876. # endif
  877. bits--;
  878. for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--)
  879. wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
  880. bn_gather5(tmp.d, top, powerbuf, wvalue);
  881. /*
  882. * Scan the exponent one window at a time starting from the most
  883. * significant bits.
  884. */
  885. if (top & 7)
  886. while (bits >= 0) {
  887. for (wvalue = 0, i = 0; i < 5; i++, bits--)
  888. wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
  889. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  890. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  891. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  892. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  893. bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
  894. bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top,
  895. wvalue);
  896. } else {
  897. while (bits >= 0) {
  898. wvalue = bn_get_bits5(p->d, bits - 4);
  899. bits -= 5;
  900. bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue);
  901. }
  902. }
  903. ret = bn_from_montgomery(tmp.d, tmp.d, NULL, np, n0, top);
  904. tmp.top = top;
  905. bn_correct_top(&tmp);
  906. if (ret) {
  907. if (!BN_copy(rr, &tmp))
  908. ret = 0;
  909. goto err; /* non-zero ret means it's not error */
  910. }
  911. } else
  912. #endif
  913. {
  914. if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, window))
  915. goto err;
  916. if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, window))
  917. goto err;
  918. /*
  919. * If the window size is greater than 1, then calculate
  920. * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) (even
  921. * powers could instead be computed as (a^(i/2))^2 to use the slight
  922. * performance advantage of sqr over mul).
  923. */
  924. if (window > 1) {
  925. if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx))
  926. goto err;
  927. if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2,
  928. window))
  929. goto err;
  930. for (i = 3; i < numPowers; i++) {
  931. /* Calculate a^i = a^(i-1) * a */
  932. if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx))
  933. goto err;
  934. if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i,
  935. window))
  936. goto err;
  937. }
  938. }
  939. bits--;
  940. for (wvalue = 0, i = bits % window; i >= 0; i--, bits--)
  941. wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
  942. if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf, wvalue,
  943. window))
  944. goto err;
  945. /*
  946. * Scan the exponent one window at a time starting from the most
  947. * significant bits.
  948. */
  949. while (bits >= 0) {
  950. wvalue = 0; /* The 'value' of the window */
  951. /* Scan the window, squaring the result as we go */
  952. for (i = 0; i < window; i++, bits--) {
  953. if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx))
  954. goto err;
  955. wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
  956. }
  957. /*
  958. * Fetch the appropriate pre-computed value from the pre-buf
  959. */
  960. if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, wvalue,
  961. window))
  962. goto err;
  963. /* Multiply the result into the intermediate result */
  964. if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx))
  965. goto err;
  966. }
  967. }
  968. /* Convert the final result from montgomery to standard format */
  969. #if defined(SPARC_T4_MONT)
  970. if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {
  971. am.d[0] = 1; /* borrow am */
  972. for (i = 1; i < top; i++)
  973. am.d[i] = 0;
  974. if (!BN_mod_mul_montgomery(rr, &tmp, &am, mont, ctx))
  975. goto err;
  976. } else
  977. #endif
  978. if (!BN_from_montgomery(rr, &tmp, mont, ctx))
  979. goto err;
  980. ret = 1;
  981. err:
  982. if (in_mont == NULL)
  983. BN_MONT_CTX_free(mont);
  984. if (powerbuf != NULL) {
  985. OPENSSL_cleanse(powerbuf, powerbufLen);
  986. OPENSSL_free(powerbufFree);
  987. }
  988. BN_CTX_end(ctx);
  989. return ret;
  990. }
  991. int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
  992. const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
  993. {
  994. BN_MONT_CTX *mont = NULL;
  995. int b, bits, ret = 0;
  996. int r_is_one;
  997. BN_ULONG w, next_w;
  998. BIGNUM *r, *t;
  999. BIGNUM *swap_tmp;
  1000. #define BN_MOD_MUL_WORD(r, w, m) \
  1001. (BN_mul_word(r, (w)) && \
  1002. (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \
  1003. (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
  1004. /*
  1005. * BN_MOD_MUL_WORD is only used with 'w' large, so the BN_ucmp test is
  1006. * probably more overhead than always using BN_mod (which uses BN_copy if
  1007. * a similar test returns true).
  1008. */
  1009. /*
  1010. * We can use BN_mod and do not need BN_nnmod because our accumulator is
  1011. * never negative (the result of BN_mod does not depend on the sign of
  1012. * the modulus).
  1013. */
  1014. #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
  1015. (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
  1016. if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
  1017. || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
  1018. /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
  1019. BNerr(BN_F_BN_MOD_EXP_MONT_WORD, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
  1020. return 0;
  1021. }
  1022. bn_check_top(p);
  1023. bn_check_top(m);
  1024. if (!BN_is_odd(m)) {
  1025. BNerr(BN_F_BN_MOD_EXP_MONT_WORD, BN_R_CALLED_WITH_EVEN_MODULUS);
  1026. return 0;
  1027. }
  1028. if (m->top == 1)
  1029. a %= m->d[0]; /* make sure that 'a' is reduced */
  1030. bits = BN_num_bits(p);
  1031. if (bits == 0) {
  1032. /* x**0 mod 1 is still zero. */
  1033. if (BN_is_one(m)) {
  1034. ret = 1;
  1035. BN_zero(rr);
  1036. } else {
  1037. ret = BN_one(rr);
  1038. }
  1039. return ret;
  1040. }
  1041. if (a == 0) {
  1042. BN_zero(rr);
  1043. ret = 1;
  1044. return ret;
  1045. }
  1046. BN_CTX_start(ctx);
  1047. r = BN_CTX_get(ctx);
  1048. t = BN_CTX_get(ctx);
  1049. if (t == NULL)
  1050. goto err;
  1051. if (in_mont != NULL)
  1052. mont = in_mont;
  1053. else {
  1054. if ((mont = BN_MONT_CTX_new()) == NULL)
  1055. goto err;
  1056. if (!BN_MONT_CTX_set(mont, m, ctx))
  1057. goto err;
  1058. }
  1059. r_is_one = 1; /* except for Montgomery factor */
  1060. /* bits-1 >= 0 */
  1061. /* The result is accumulated in the product r*w. */
  1062. w = a; /* bit 'bits-1' of 'p' is always set */
  1063. for (b = bits - 2; b >= 0; b--) {
  1064. /* First, square r*w. */
  1065. next_w = w * w;
  1066. if ((next_w / w) != w) { /* overflow */
  1067. if (r_is_one) {
  1068. if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
  1069. goto err;
  1070. r_is_one = 0;
  1071. } else {
  1072. if (!BN_MOD_MUL_WORD(r, w, m))
  1073. goto err;
  1074. }
  1075. next_w = 1;
  1076. }
  1077. w = next_w;
  1078. if (!r_is_one) {
  1079. if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
  1080. goto err;
  1081. }
  1082. /* Second, multiply r*w by 'a' if exponent bit is set. */
  1083. if (BN_is_bit_set(p, b)) {
  1084. next_w = w * a;
  1085. if ((next_w / a) != w) { /* overflow */
  1086. if (r_is_one) {
  1087. if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
  1088. goto err;
  1089. r_is_one = 0;
  1090. } else {
  1091. if (!BN_MOD_MUL_WORD(r, w, m))
  1092. goto err;
  1093. }
  1094. next_w = a;
  1095. }
  1096. w = next_w;
  1097. }
  1098. }
  1099. /* Finally, set r:=r*w. */
  1100. if (w != 1) {
  1101. if (r_is_one) {
  1102. if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
  1103. goto err;
  1104. r_is_one = 0;
  1105. } else {
  1106. if (!BN_MOD_MUL_WORD(r, w, m))
  1107. goto err;
  1108. }
  1109. }
  1110. if (r_is_one) { /* can happen only if a == 1 */
  1111. if (!BN_one(rr))
  1112. goto err;
  1113. } else {
  1114. if (!BN_from_montgomery(rr, r, mont, ctx))
  1115. goto err;
  1116. }
  1117. ret = 1;
  1118. err:
  1119. if (in_mont == NULL)
  1120. BN_MONT_CTX_free(mont);
  1121. BN_CTX_end(ctx);
  1122. bn_check_top(rr);
  1123. return ret;
  1124. }
  1125. /* The old fallback, simple version :-) */
  1126. int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
  1127. const BIGNUM *m, BN_CTX *ctx)
  1128. {
  1129. int i, j, bits, ret = 0, wstart, wend, window, wvalue;
  1130. int start = 1;
  1131. BIGNUM *d;
  1132. /* Table of variables obtained from 'ctx' */
  1133. BIGNUM *val[TABLE_SIZE];
  1134. if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
  1135. || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
  1136. || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
  1137. /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
  1138. BNerr(BN_F_BN_MOD_EXP_SIMPLE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
  1139. return 0;
  1140. }
  1141. bits = BN_num_bits(p);
  1142. if (bits == 0) {
  1143. /* x**0 mod 1 is still zero. */
  1144. if (BN_is_one(m)) {
  1145. ret = 1;
  1146. BN_zero(r);
  1147. } else {
  1148. ret = BN_one(r);
  1149. }
  1150. return ret;
  1151. }
  1152. BN_CTX_start(ctx);
  1153. d = BN_CTX_get(ctx);
  1154. val[0] = BN_CTX_get(ctx);
  1155. if (val[0] == NULL)
  1156. goto err;
  1157. if (!BN_nnmod(val[0], a, m, ctx))
  1158. goto err; /* 1 */
  1159. if (BN_is_zero(val[0])) {
  1160. BN_zero(r);
  1161. ret = 1;
  1162. goto err;
  1163. }
  1164. window = BN_window_bits_for_exponent_size(bits);
  1165. if (window > 1) {
  1166. if (!BN_mod_mul(d, val[0], val[0], m, ctx))
  1167. goto err; /* 2 */
  1168. j = 1 << (window - 1);
  1169. for (i = 1; i < j; i++) {
  1170. if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
  1171. !BN_mod_mul(val[i], val[i - 1], d, m, ctx))
  1172. goto err;
  1173. }
  1174. }
  1175. start = 1; /* This is used to avoid multiplication etc
  1176. * when there is only the value '1' in the
  1177. * buffer. */
  1178. wvalue = 0; /* The 'value' of the window */
  1179. wstart = bits - 1; /* The top bit of the window */
  1180. wend = 0; /* The bottom bit of the window */
  1181. if (!BN_one(r))
  1182. goto err;
  1183. for (;;) {
  1184. if (BN_is_bit_set(p, wstart) == 0) {
  1185. if (!start)
  1186. if (!BN_mod_mul(r, r, r, m, ctx))
  1187. goto err;
  1188. if (wstart == 0)
  1189. break;
  1190. wstart--;
  1191. continue;
  1192. }
  1193. /*
  1194. * We now have wstart on a 'set' bit, we now need to work out how bit
  1195. * a window to do. To do this we need to scan forward until the last
  1196. * set bit before the end of the window
  1197. */
  1198. j = wstart;
  1199. wvalue = 1;
  1200. wend = 0;
  1201. for (i = 1; i < window; i++) {
  1202. if (wstart - i < 0)
  1203. break;
  1204. if (BN_is_bit_set(p, wstart - i)) {
  1205. wvalue <<= (i - wend);
  1206. wvalue |= 1;
  1207. wend = i;
  1208. }
  1209. }
  1210. /* wend is the size of the current window */
  1211. j = wend + 1;
  1212. /* add the 'bytes above' */
  1213. if (!start)
  1214. for (i = 0; i < j; i++) {
  1215. if (!BN_mod_mul(r, r, r, m, ctx))
  1216. goto err;
  1217. }
  1218. /* wvalue will be an odd number < 2^window */
  1219. if (!BN_mod_mul(r, r, val[wvalue >> 1], m, ctx))
  1220. goto err;
  1221. /* move the 'window' down further */
  1222. wstart -= wend + 1;
  1223. wvalue = 0;
  1224. start = 0;
  1225. if (wstart < 0)
  1226. break;
  1227. }
  1228. ret = 1;
  1229. err:
  1230. BN_CTX_end(ctx);
  1231. bn_check_top(r);
  1232. return ret;
  1233. }