tls_pstm.c 50 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308
  1. /*
  2. * Copyright (C) 2017 Denys Vlasenko
  3. *
  4. * Licensed under GPLv2, see file LICENSE in this source tree.
  5. */
  6. #include "tls.h"
  7. /* The file is taken almost verbatim from matrixssl-3-7-2b-open/crypto/math/.
  8. * Changes are flagged with //bbox
  9. */
  10. /**
  11. * @file pstm.c
  12. * @version 33ef80f (HEAD, tag: MATRIXSSL-3-7-2-OPEN, tag: MATRIXSSL-3-7-2-COMM, origin/master, origin/HEAD, master)
  13. *
  14. * Multiprecision number implementation.
  15. */
  16. /*
  17. * Copyright (c) 2013-2015 INSIDE Secure Corporation
  18. * Copyright (c) PeerSec Networks, 2002-2011
  19. * All Rights Reserved
  20. *
  21. * The latest version of this code is available at http://www.matrixssl.org
  22. *
  23. * This software is open source; you can redistribute it and/or modify
  24. * it under the terms of the GNU General Public License as published by
  25. * the Free Software Foundation; either version 2 of the License, or
  26. * (at your option) any later version.
  27. *
  28. * This General Public License does NOT permit incorporating this software
  29. * into proprietary programs. If you are unable to comply with the GPL, a
  30. * commercial license for this software may be purchased from INSIDE at
  31. * http://www.insidesecure.com/eng/Company/Locations
  32. *
  33. * This program is distributed in WITHOUT ANY WARRANTY; without even the
  34. * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  35. * See the GNU General Public License for more details.
  36. *
  37. * You should have received a copy of the GNU General Public License
  38. * along with this program; if not, write to the Free Software
  39. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  40. * http://www.gnu.org/copyleft/gpl.html
  41. */
  42. /******************************************************************************/
  43. //bbox
  44. //#include "../cryptoApi.h"
  45. #ifndef DISABLE_PSTM
  46. #undef pstm_mul_2d
  47. static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c); //bbox: was int16 b
  48. #define pstm_mul_2d(a, b, c) (pstm_mul_2d(a, b, c), PSTM_OKAY)
  49. /******************************************************************************/
  50. /*
  51. init an pstm_int for a given size
  52. */
  53. #undef pstm_init_size
  54. #define pstm_init_size(pool, a, size) \
  55. pstm_init_size( a, size)
  56. int32 FAST_FUNC pstm_init_size(psPool_t *pool, pstm_int * a, uint32 size)
  57. {
  58. //bbox
  59. // uint16 x;
  60. /*
  61. alloc mem
  62. */
  63. a->dp = xzalloc(sizeof (pstm_digit) * size);//bbox
  64. //bbox a->pool = pool;
  65. a->used = 0;
  66. a->alloc = size;
  67. a->sign = PSTM_ZPOS;
  68. /*
  69. zero the digits
  70. */
  71. //bbox
  72. // for (x = 0; x < size; x++) {
  73. // a->dp[x] = 0;
  74. // }
  75. return PSTM_OKAY;
  76. }
  77. #undef pstm_init_size
  78. #define pstm_init_size(pool, a, size) (pstm_init_size(a, size), PSTM_OKAY)
  79. /******************************************************************************/
  80. /*
  81. Init a new pstm_int.
  82. */
  83. #undef pstm_init
  84. #define pstm_init(pool, a) \
  85. pstm_init( a)
  86. static int32 pstm_init(psPool_t *pool, pstm_int * a)
  87. {
  88. //bbox
  89. // int32 i;
  90. /*
  91. allocate memory required and clear it
  92. */
  93. a->dp = xzalloc(sizeof (pstm_digit) * PSTM_DEFAULT_INIT);//bbox
  94. /*
  95. set the digits to zero
  96. */
  97. //bbox
  98. // for (i = 0; i < PSTM_DEFAULT_INIT; i++) {
  99. // a->dp[i] = 0;
  100. // }
  101. /*
  102. set the used to zero, allocated digits to the default precision and sign
  103. to positive
  104. */
  105. //bbox a->pool = pool;
  106. a->used = 0;
  107. a->alloc = PSTM_DEFAULT_INIT;
  108. a->sign = PSTM_ZPOS;
  109. return PSTM_OKAY;
  110. }
  111. #undef pstm_init
  112. #define pstm_init(pool, a) (pstm_init(a), PSTM_OKAY)
  113. /******************************************************************************/
  114. /*
  115. Grow as required
  116. */
  117. #undef pstm_grow
  118. int32 FAST_FUNC pstm_grow(pstm_int * a, int size)
  119. {
  120. int i; //bbox: was int16
  121. pstm_digit *tmp;
  122. /*
  123. If the alloc size is smaller alloc more ram.
  124. */
  125. if (a->alloc < size) {
  126. /*
  127. Reallocate the array a->dp
  128. We store the return in a temporary variable in case the operation
  129. failed we don't want to overwrite the dp member of a.
  130. */
  131. tmp = xrealloc(a->dp, sizeof (pstm_digit) * size);//bbox
  132. /*
  133. reallocation succeeded so set a->dp
  134. */
  135. a->dp = tmp;
  136. /*
  137. zero excess digits
  138. */
  139. i = a->alloc;
  140. a->alloc = size;
  141. for (; i < a->alloc; i++) {
  142. a->dp[i] = 0;
  143. }
  144. }
  145. return PSTM_OKAY;
  146. }
  147. #define pstm_grow(a, size) (pstm_grow(a, size), PSTM_OKAY)
  148. /******************************************************************************/
  149. /*
  150. copy, b = a (b must be pre-allocated)
  151. */
  152. #undef pstm_copy
  153. int32 pstm_copy(pstm_int * a, pstm_int * b)
  154. {
  155. int32 res, n;
  156. /*
  157. If dst == src do nothing
  158. */
  159. if (a == b) {
  160. return PSTM_OKAY;
  161. }
  162. /*
  163. Grow dest
  164. */
  165. if (b->alloc < a->used) {
  166. if ((res = pstm_grow (b, a->used)) != PSTM_OKAY) {
  167. return res;
  168. }
  169. }
  170. /*
  171. Zero b and copy the parameters over
  172. */
  173. {
  174. register pstm_digit *tmpa, *tmpb;
  175. /* pointer aliases */
  176. /* source */
  177. tmpa = a->dp;
  178. /* destination */
  179. tmpb = b->dp;
  180. /* copy all the digits */
  181. for (n = 0; n < a->used; n++) {
  182. *tmpb++ = *tmpa++;
  183. }
  184. /* clear high digits */
  185. for (; n < b->used; n++) {
  186. *tmpb++ = 0;
  187. }
  188. }
  189. /*
  190. copy used count and sign
  191. */
  192. b->used = a->used;
  193. b->sign = a->sign;
  194. return PSTM_OKAY;
  195. }
  196. #define pstm_copy(a, b) (pstm_copy(a, b), PSTM_OKAY)
  197. /******************************************************************************/
  198. /*
  199. Trim unused digits
  200. This is used to ensure that leading zero digits are trimed and the
  201. leading "used" digit will be non-zero. Typically very fast. Also fixes
  202. the sign if there are no more leading digits
  203. */
  204. void FAST_FUNC pstm_clamp(pstm_int * a)
  205. {
  206. /* decrease used while the most significant digit is zero. */
  207. while (a->used > 0 && a->dp[a->used - 1] == 0) {
  208. --(a->used);
  209. }
  210. /* reset the sign flag if used == 0 */
  211. if (a->used == 0) {
  212. a->sign = PSTM_ZPOS;
  213. }
  214. }
  215. /******************************************************************************/
  216. /*
  217. clear one (frees).
  218. */
  219. void FAST_FUNC pstm_clear(pstm_int * a)
  220. {
  221. int32 i;
  222. /*
  223. only do anything if a hasn't been freed previously
  224. */
  225. if (a != NULL && a->dp != NULL) {
  226. /*
  227. first zero the digits
  228. */
  229. for (i = 0; i < a->used; i++) {
  230. a->dp[i] = 0;
  231. }
  232. psFree (a->dp, a->pool);
  233. /*
  234. reset members to make debugging easier
  235. */
  236. a->dp = NULL;
  237. a->alloc = a->used = 0;
  238. a->sign = PSTM_ZPOS;
  239. }
  240. }
  241. /******************************************************************************/
  242. /*
  243. clear many (frees).
  244. */
  245. #if 0 //UNUSED
  246. void pstm_clear_multi(pstm_int *mp0, pstm_int *mp1, pstm_int *mp2,
  247. pstm_int *mp3, pstm_int *mp4, pstm_int *mp5,
  248. pstm_int *mp6, pstm_int *mp7)
  249. {
  250. int32 n; /* Number of ok inits */
  251. pstm_int *tempArray[9];
  252. tempArray[0] = mp0;
  253. tempArray[1] = mp1;
  254. tempArray[2] = mp2;
  255. tempArray[3] = mp3;
  256. tempArray[4] = mp4;
  257. tempArray[5] = mp5;
  258. tempArray[6] = mp6;
  259. tempArray[7] = mp7;
  260. tempArray[8] = NULL;
  261. for (n = 0; tempArray[n] != NULL; n++) {
  262. if ((tempArray[n] != NULL) && (tempArray[n]->dp != NULL)) {
  263. pstm_clear(tempArray[n]);
  264. }
  265. }
  266. }
  267. #endif
  268. /******************************************************************************/
  269. /*
  270. Set to zero.
  271. */
  272. static void pstm_zero(pstm_int * a)
  273. {
  274. int32 n;
  275. pstm_digit *tmp;
  276. a->sign = PSTM_ZPOS;
  277. a->used = 0;
  278. tmp = a->dp;
  279. for (n = 0; n < a->alloc; n++) {
  280. *tmp++ = 0;
  281. }
  282. }
  283. /******************************************************************************/
  284. /*
  285. Compare maginitude of two ints (unsigned).
  286. */
  287. int32 FAST_FUNC pstm_cmp_mag(pstm_int * a, pstm_int * b)
  288. {
  289. int n; //bbox: was int16
  290. pstm_digit *tmpa, *tmpb;
  291. /*
  292. compare based on # of non-zero digits
  293. */
  294. if (a->used > b->used) {
  295. return PSTM_GT;
  296. }
  297. if (a->used < b->used) {
  298. return PSTM_LT;
  299. }
  300. /* alias for a */
  301. tmpa = a->dp + (a->used - 1);
  302. /* alias for b */
  303. tmpb = b->dp + (a->used - 1);
  304. /*
  305. compare based on digits
  306. */
  307. for (n = 0; n < a->used; ++n, --tmpa, --tmpb) {
  308. if (*tmpa > *tmpb) {
  309. return PSTM_GT;
  310. }
  311. if (*tmpa < *tmpb) {
  312. return PSTM_LT;
  313. }
  314. }
  315. return PSTM_EQ;
  316. }
  317. /******************************************************************************/
  318. /*
  319. Compare two ints (signed)
  320. */
  321. int32 FAST_FUNC pstm_cmp(pstm_int * a, pstm_int * b)
  322. {
  323. /*
  324. compare based on sign
  325. */
  326. if (a->sign != b->sign) {
  327. if (a->sign == PSTM_NEG) {
  328. return PSTM_LT;
  329. } else {
  330. return PSTM_GT;
  331. }
  332. }
  333. /*
  334. compare digits
  335. */
  336. if (a->sign == PSTM_NEG) {
  337. /* if negative compare opposite direction */
  338. return pstm_cmp_mag(b, a);
  339. } else {
  340. return pstm_cmp_mag(a, b);
  341. }
  342. }
  343. /******************************************************************************/
  344. /*
  345. pstm_ints can be initialized more precisely when they will populated
  346. using pstm_read_unsigned_bin since the length of the byte stream is known
  347. */
  348. int32 FAST_FUNC pstm_init_for_read_unsigned_bin(psPool_t *pool, pstm_int *a, uint32 len)
  349. {
  350. int32 size;
  351. /*
  352. Need to set this based on how many words max it will take to store the bin.
  353. The magic + 2:
  354. 1 to round up for the remainder of this integer math
  355. 1 for the initial carry of '1' bits that fall between DIGIT_BIT and 8
  356. */
  357. size = (((len / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
  358. / DIGIT_BIT) + 2;
  359. return pstm_init_size(pool, a, size);
  360. }
  361. /******************************************************************************/
  362. /*
  363. Reads a unsigned char array into pstm_int format. User should have
  364. called pstm_init_for_read_unsigned_bin first. There is some grow logic
  365. here if the default pstm_init was used but we don't really want to hit it.
  366. */
  367. int32 FAST_FUNC pstm_read_unsigned_bin(pstm_int *a, unsigned char *b, int32 c)
  368. {
  369. /* zero the int */
  370. pstm_zero (a);
  371. /*
  372. If we know the endianness of this architecture, and we're using
  373. 32-bit pstm_digits, we can optimize this
  374. */
  375. #if (defined(ENDIAN_LITTLE) || defined(ENDIAN_BIG)) && !defined(PSTM_64BIT)
  376. /* But not for both simultaneously */
  377. #if defined(ENDIAN_LITTLE) && defined(ENDIAN_BIG)
  378. #error Both ENDIAN_LITTLE and ENDIAN_BIG defined.
  379. #endif
  380. {
  381. unsigned char *pd;
  382. if ((unsigned)c > (PSTM_MAX_SIZE * sizeof(pstm_digit))) {
  383. uint32 excess = c - (PSTM_MAX_SIZE * sizeof(pstm_digit));
  384. c -= excess;
  385. b += excess;
  386. }
  387. a->used = ((c + sizeof(pstm_digit) - 1)/sizeof(pstm_digit));
  388. if (a->alloc < a->used) {
  389. if (pstm_grow(a, a->used) != PSTM_OKAY) {
  390. return PSTM_MEM;
  391. }
  392. }
  393. pd = (unsigned char *)a->dp;
  394. /* read the bytes in */
  395. #ifdef ENDIAN_BIG
  396. {
  397. /* Use Duff's device to unroll the loop. */
  398. int32 idx = (c - 1) & ~3;
  399. switch (c % 4) {
  400. case 0: do { pd[idx+0] = *b++;
  401. case 3: pd[idx+1] = *b++;
  402. case 2: pd[idx+2] = *b++;
  403. case 1: pd[idx+3] = *b++;
  404. idx -= 4;
  405. } while ((c -= 4) > 0);
  406. }
  407. }
  408. #else
  409. for (c -= 1; c >= 0; c -= 1) {
  410. pd[c] = *b++;
  411. }
  412. #endif
  413. }
  414. #else
  415. /* Big enough based on the len? */
  416. a->used = (((c / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
  417. / DIGIT_BIT) + 2;
  418. if (a->alloc < a->used) {
  419. if (pstm_grow(a, a->used) != PSTM_OKAY) {
  420. return PSTM_MEM;
  421. }
  422. }
  423. /* read the bytes in */
  424. for (; c > 0; c--) {
  425. if (pstm_mul_2d (a, 8, a) != PSTM_OKAY) {
  426. return PS_MEM_FAIL;
  427. }
  428. a->dp[0] |= *b++;
  429. a->used += 1;
  430. }
  431. #endif
  432. pstm_clamp (a);
  433. return PS_SUCCESS;
  434. }
  435. /******************************************************************************/
  436. /*
  437. */
  438. static int pstm_count_bits(pstm_int * a)
  439. {
  440. int r; //bbox: was int16
  441. pstm_digit q;
  442. if (a->used == 0) {
  443. return 0;
  444. }
  445. /* get number of digits and add that */
  446. r = (a->used - 1) * DIGIT_BIT;
  447. /* take the last digit and count the bits in it */
  448. q = a->dp[a->used - 1];
  449. while (q > ((pstm_digit) 0)) {
  450. ++r;
  451. q >>= ((pstm_digit) 1);
  452. }
  453. return r;
  454. }
  455. /******************************************************************************/
  456. int32 FAST_FUNC pstm_unsigned_bin_size(pstm_int *a)
  457. {
  458. int32 size = pstm_count_bits (a);
  459. return (size / 8 + ((size & 7) != 0 ? 1 : 0));
  460. }
  461. /******************************************************************************/
  462. static void pstm_set(pstm_int *a, pstm_digit b)
  463. {
  464. pstm_zero(a);
  465. a->dp[0] = b;
  466. a->used = a->dp[0] ? 1 : 0;
  467. }
  468. /******************************************************************************/
  469. /*
  470. Right shift
  471. */
  472. static void pstm_rshd(pstm_int *a, int x)
  473. {
  474. int y; //bbox: was int16
  475. /* too many digits just zero and return */
  476. if (x >= a->used) {
  477. pstm_zero(a);
  478. return;
  479. }
  480. /* shift */
  481. for (y = 0; y < a->used - x; y++) {
  482. a->dp[y] = a->dp[y+x];
  483. }
  484. /* zero rest */
  485. for (; y < a->used; y++) {
  486. a->dp[y] = 0;
  487. }
  488. /* decrement count */
  489. a->used -= x;
  490. pstm_clamp(a);
  491. }
  492. /******************************************************************************/
  493. /*
  494. Shift left a certain amount of digits.
  495. */
  496. #undef pstm_lshd
  497. static int32 pstm_lshd(pstm_int * a, int b)
  498. {
  499. int x; //bbox: was int16
  500. int32 res;
  501. /*
  502. If its less than zero return.
  503. */
  504. if (b <= 0) {
  505. return PSTM_OKAY;
  506. }
  507. /*
  508. Grow to fit the new digits.
  509. */
  510. if (a->alloc < a->used + b) {
  511. if ((res = pstm_grow (a, a->used + b)) != PSTM_OKAY) {
  512. return res;
  513. }
  514. }
  515. {
  516. register pstm_digit *top, *bottom;
  517. /*
  518. Increment the used by the shift amount then copy upwards.
  519. */
  520. a->used += b;
  521. /* top */
  522. top = a->dp + a->used - 1;
  523. /* base */
  524. bottom = a->dp + a->used - 1 - b;
  525. /*
  526. This is implemented using a sliding window except the window goes the
  527. other way around. Copying from the bottom to the top.
  528. */
  529. for (x = a->used - 1; x >= b; x--) {
  530. *top-- = *bottom--;
  531. }
  532. /* zero the lower digits */
  533. top = a->dp;
  534. for (x = 0; x < b; x++) {
  535. *top++ = 0;
  536. }
  537. }
  538. return PSTM_OKAY;
  539. }
  540. #define pstm_lshd(a, b) (pstm_lshd(a, b), PSTM_OKAY)
  541. /******************************************************************************/
  542. /*
  543. computes a = 2**b
  544. */
  545. static int32 pstm_2expt(pstm_int *a, int b)
  546. {
  547. int z; //bbox: was int16
  548. /* zero a as per default */
  549. pstm_zero (a);
  550. if (b < 0) {
  551. return PSTM_OKAY;
  552. }
  553. z = b / DIGIT_BIT;
  554. if (z >= PSTM_MAX_SIZE) {
  555. return PS_LIMIT_FAIL;
  556. }
  557. /* set the used count of where the bit will go */
  558. a->used = z + 1;
  559. if (a->used > a->alloc) {
  560. if (pstm_grow(a, a->used) != PSTM_OKAY) {
  561. return PS_MEM_FAIL;
  562. }
  563. }
  564. /* put the single bit in its place */
  565. a->dp[z] = ((pstm_digit)1) << (b % DIGIT_BIT);
  566. return PSTM_OKAY;
  567. }
  568. /******************************************************************************/
  569. /*
  570. */
  571. int32 FAST_FUNC pstm_mul_2(pstm_int * a, pstm_int * b)
  572. {
  573. int32 res;
  574. int x, oldused; //bbox: was int16
  575. /*
  576. grow to accomodate result
  577. */
  578. if (b->alloc < a->used + 1) {
  579. if ((res = pstm_grow (b, a->used + 1)) != PSTM_OKAY) {
  580. return res;
  581. }
  582. }
  583. oldused = b->used;
  584. b->used = a->used;
  585. {
  586. register pstm_digit r, rr, *tmpa, *tmpb;
  587. /* alias for source */
  588. tmpa = a->dp;
  589. /* alias for dest */
  590. tmpb = b->dp;
  591. /* carry */
  592. r = 0;
  593. for (x = 0; x < a->used; x++) {
  594. /*
  595. get what will be the *next* carry bit from the
  596. MSB of the current digit
  597. */
  598. rr = *tmpa >> ((pstm_digit)(DIGIT_BIT - 1));
  599. /*
  600. now shift up this digit, add in the carry [from the previous]
  601. */
  602. *tmpb++ = ((*tmpa++ << ((pstm_digit)1)) | r);
  603. /*
  604. copy the carry that would be from the source
  605. digit into the next iteration
  606. */
  607. r = rr;
  608. }
  609. /* new leading digit? */
  610. if (r != 0 && b->used != (PSTM_MAX_SIZE-1)) {
  611. /* add a MSB which is always 1 at this point */
  612. *tmpb = 1;
  613. ++(b->used);
  614. }
  615. /*
  616. now zero any excess digits on the destination that we didn't write to
  617. */
  618. tmpb = b->dp + b->used;
  619. for (x = b->used; x < oldused; x++) {
  620. *tmpb++ = 0;
  621. }
  622. }
  623. b->sign = a->sign;
  624. return PSTM_OKAY;
  625. }
  626. /******************************************************************************/
  627. /*
  628. unsigned subtraction ||a|| >= ||b|| ALWAYS!
  629. */
  630. int32 FAST_FUNC s_pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
  631. {
  632. int oldbused, oldused; //bbox: was int16
  633. int32 x;
  634. pstm_word t;
  635. if (b->used > a->used) {
  636. return PS_LIMIT_FAIL;
  637. }
  638. if (c->alloc < a->used) {
  639. if ((x = pstm_grow (c, a->used)) != PSTM_OKAY) {
  640. return x;
  641. }
  642. }
  643. oldused = c->used;
  644. oldbused = b->used;
  645. c->used = a->used;
  646. t = 0;
  647. for (x = 0; x < oldbused; x++) {
  648. t = ((pstm_word)a->dp[x]) - (((pstm_word)b->dp[x]) + t);
  649. c->dp[x] = (pstm_digit)t;
  650. t = (t >> DIGIT_BIT)&1;
  651. }
  652. for (; x < a->used; x++) {
  653. t = ((pstm_word)a->dp[x]) - t;
  654. c->dp[x] = (pstm_digit)t;
  655. t = (t >> DIGIT_BIT);
  656. }
  657. for (; x < oldused; x++) {
  658. c->dp[x] = 0;
  659. }
  660. pstm_clamp(c);
  661. return PSTM_OKAY;
  662. }
  663. /******************************************************************************/
  664. /*
  665. unsigned addition
  666. */
  667. static int32 s_pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
  668. {
  669. int x, y, oldused; //bbox: was int16
  670. register pstm_word t, adp, bdp;
  671. y = a->used;
  672. if (b->used > y) {
  673. y = b->used;
  674. }
  675. oldused = c->used;
  676. c->used = y;
  677. if (c->used > c->alloc) {
  678. if (pstm_grow(c, c->used) != PSTM_OKAY) {
  679. return PS_MEM_FAIL;
  680. }
  681. }
  682. t = 0;
  683. for (x = 0; x < y; x++) {
  684. if (a->used < x) {
  685. adp = 0;
  686. } else {
  687. adp = (pstm_word)a->dp[x];
  688. }
  689. if (b->used < x) {
  690. bdp = 0;
  691. } else {
  692. bdp = (pstm_word)b->dp[x];
  693. }
  694. t += (adp) + (bdp);
  695. c->dp[x] = (pstm_digit)t;
  696. t >>= DIGIT_BIT;
  697. }
  698. if (t != 0 && x < PSTM_MAX_SIZE) {
  699. if (c->used == c->alloc) {
  700. if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
  701. return PS_MEM_FAIL;
  702. }
  703. }
  704. c->dp[c->used++] = (pstm_digit)t;
  705. ++x;
  706. }
  707. c->used = x;
  708. for (; x < oldused; x++) {
  709. c->dp[x] = 0;
  710. }
  711. pstm_clamp(c);
  712. return PSTM_OKAY;
  713. }
  714. /******************************************************************************/
  715. /*
  716. */
  717. int32 FAST_FUNC pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
  718. {
  719. int32 res;
  720. int sa, sb; //bbox: was int16
  721. sa = a->sign;
  722. sb = b->sign;
  723. if (sa != sb) {
  724. /*
  725. subtract a negative from a positive, OR a positive from a negative.
  726. For both, ADD their magnitudes, and use the sign of the first number.
  727. */
  728. c->sign = sa;
  729. if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
  730. return res;
  731. }
  732. } else {
  733. /*
  734. subtract a positive from a positive, OR a negative from a negative.
  735. First, take the difference between their magnitudes, then...
  736. */
  737. if (pstm_cmp_mag (a, b) != PSTM_LT) {
  738. /* Copy the sign from the first */
  739. c->sign = sa;
  740. /* The first has a larger or equal magnitude */
  741. if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
  742. return res;
  743. }
  744. } else {
  745. /* The result has the _opposite_ sign from the first number. */
  746. c->sign = (sa == PSTM_ZPOS) ? PSTM_NEG : PSTM_ZPOS;
  747. /* The second has a larger magnitude */
  748. if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
  749. return res;
  750. }
  751. }
  752. }
  753. return PS_SUCCESS;
  754. }
  755. /******************************************************************************/
  756. /*
  757. c = a - b
  758. */
  759. #if 0 //UNUSED
  760. int32 pstm_sub_d(psPool_t *pool, pstm_int *a, pstm_digit b, pstm_int *c)
  761. {
  762. pstm_int tmp;
  763. int32 res;
  764. if (pstm_init_size(pool, &tmp, sizeof(pstm_digit)) != PSTM_OKAY) {
  765. return PS_MEM_FAIL;
  766. }
  767. pstm_set(&tmp, b);
  768. res = pstm_sub(a, &tmp, c);
  769. pstm_clear(&tmp);
  770. return res;
  771. }
  772. #endif
  773. /******************************************************************************/
  774. /*
  775. setups the montgomery reduction
  776. */
  777. static int32 pstm_montgomery_setup(pstm_int *a, pstm_digit *rho)
  778. {
  779. pstm_digit x, b;
  780. /*
  781. fast inversion mod 2**k
  782. Based on the fact that
  783. XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
  784. => 2*X*A - X*X*A*A = 1
  785. => 2*(1) - (1) = 1
  786. */
  787. b = a->dp[0];
  788. if ((b & 1) == 0) {
  789. psTraceCrypto("pstm_montogomery_setup failure\n");
  790. return PS_ARG_FAIL;
  791. }
  792. x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
  793. x *= 2 - b * x; /* here x*a==1 mod 2**8 */
  794. x *= 2 - b * x; /* here x*a==1 mod 2**16 */
  795. x *= 2 - b * x; /* here x*a==1 mod 2**32 */
  796. #ifdef PSTM_64BIT
  797. x *= 2 - b * x; /* here x*a==1 mod 2**64 */
  798. #endif
  799. /* rho = -1/m mod b */
  800. *rho = (pstm_digit)(((pstm_word) 1 << ((pstm_word) DIGIT_BIT)) -
  801. ((pstm_word)x));
  802. return PSTM_OKAY;
  803. }
  804. /******************************************************************************/
  805. /*
  806. * computes a = B**n mod b without division or multiplication useful for
  807. * normalizing numbers in a Montgomery system.
  808. */
  809. static int32 pstm_montgomery_calc_normalization(pstm_int *a, pstm_int *b)
  810. {
  811. int32 x;
  812. int bits; //bbox: was int16
  813. /* how many bits of last digit does b use */
  814. bits = pstm_count_bits (b) % DIGIT_BIT;
  815. if (!bits) bits = DIGIT_BIT;
  816. /* compute A = B^(n-1) * 2^(bits-1) */
  817. if (b->used > 1) {
  818. if ((x = pstm_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) !=
  819. PSTM_OKAY) {
  820. return x;
  821. }
  822. } else {
  823. pstm_set(a, 1);
  824. bits = 1;
  825. }
  826. /* now compute C = A * B mod b */
  827. for (x = bits - 1; x < (int32)DIGIT_BIT; x++) {
  828. if (pstm_mul_2 (a, a) != PSTM_OKAY) {
  829. return PS_MEM_FAIL;
  830. }
  831. if (pstm_cmp_mag (a, b) != PSTM_LT) {
  832. if (s_pstm_sub (a, b, a) != PSTM_OKAY) {
  833. return PS_MEM_FAIL;
  834. }
  835. }
  836. }
  837. return PSTM_OKAY;
  838. }
  839. /******************************************************************************/
  840. /*
  841. c = a * 2**d
  842. */
  843. #undef pstm_mul_2d
  844. static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c)
  845. {
  846. pstm_digit carry, carrytmp, shift;
  847. int x; //bbox: was int16
  848. /* copy it */
  849. if (pstm_copy(a, c) != PSTM_OKAY) {
  850. return PS_MEM_FAIL;
  851. }
  852. /* handle whole digits */
  853. if (b >= DIGIT_BIT) {
  854. if (pstm_lshd(c, b/DIGIT_BIT) != PSTM_OKAY) {
  855. return PS_MEM_FAIL;
  856. }
  857. }
  858. b %= DIGIT_BIT;
  859. /* shift the digits */
  860. if (b != 0) {
  861. carry = 0;
  862. shift = DIGIT_BIT - b;
  863. for (x = 0; x < c->used; x++) {
  864. carrytmp = c->dp[x] >> shift;
  865. c->dp[x] = (c->dp[x] << b) + carry;
  866. carry = carrytmp;
  867. }
  868. /* store last carry if room */
  869. if (carry && x < PSTM_MAX_SIZE) {
  870. if (c->used == c->alloc) {
  871. if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
  872. return PS_MEM_FAIL;
  873. }
  874. }
  875. c->dp[c->used++] = carry;
  876. }
  877. }
  878. pstm_clamp(c);
  879. return PSTM_OKAY;
  880. }
  881. #define pstm_mul_2d(a, b, c) (pstm_mul_2d(a, b, c), PSTM_OKAY)
  882. /******************************************************************************/
  883. /*
  884. c = a mod 2**d
  885. */
  886. #undef pstm_mod_2d
  887. static int32 pstm_mod_2d(pstm_int *a, int b, pstm_int *c) //bbox: was int16 b
  888. {
  889. int x; //bbox: was int16
  890. /* zero if count less than or equal to zero */
  891. if (b <= 0) {
  892. pstm_zero(c);
  893. return PSTM_OKAY;
  894. }
  895. /* get copy of input */
  896. if (pstm_copy(a, c) != PSTM_OKAY) {
  897. return PS_MEM_FAIL;
  898. }
  899. /* if 2**d is larger than we just return */
  900. if (b >= (DIGIT_BIT * a->used)) {
  901. return PSTM_OKAY;
  902. }
  903. /* zero digits above the last digit of the modulus */
  904. for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++)
  905. {
  906. c->dp[x] = 0;
  907. }
  908. /* clear the digit that is not completely outside/inside the modulus */
  909. c->dp[b / DIGIT_BIT] &= ~((pstm_digit)0) >> (DIGIT_BIT - b);
  910. pstm_clamp (c);
  911. return PSTM_OKAY;
  912. }
  913. #define pstm_mod_2d(a, b, c) (pstm_mod_2d(a, b, c), PSTM_OKAY)
  914. /******************************************************************************/
  915. /*
  916. c = a * b
  917. */
  918. #undef pstm_mul_d
  919. static int32 pstm_mul_d(pstm_int *a, pstm_digit b, pstm_int *c)
  920. {
  921. pstm_word w;
  922. int32 res;
  923. int x, oldused; //bbox: was int16
  924. if (c->alloc < a->used + 1) {
  925. if ((res = pstm_grow (c, a->used + 1)) != PSTM_OKAY) {
  926. return res;
  927. }
  928. }
  929. oldused = c->used;
  930. c->used = a->used;
  931. c->sign = a->sign;
  932. w = 0;
  933. for (x = 0; x < a->used; x++) {
  934. w = ((pstm_word)a->dp[x]) * ((pstm_word)b) + w;
  935. c->dp[x] = (pstm_digit)w;
  936. w = w >> DIGIT_BIT;
  937. }
  938. if (w != 0 && (a->used != PSTM_MAX_SIZE)) {
  939. c->dp[c->used++] = (pstm_digit)w;
  940. ++x;
  941. }
  942. for (; x < oldused; x++) {
  943. c->dp[x] = 0;
  944. }
  945. pstm_clamp(c);
  946. return PSTM_OKAY;
  947. }
  948. #define pstm_mul_d(a, b, c) (pstm_mul_d(a, b, c), PSTM_OKAY)
  949. /******************************************************************************/
  950. /*
  951. c = a / 2**b
  952. */
  953. #undef pstm_div_2d
  954. #define pstm_div_2d(pool, a, b, c, d) \
  955. pstm_div_2d( a, b, c, d)
  956. static int32 pstm_div_2d(psPool_t *pool, pstm_int *a, int b, pstm_int *c,
  957. pstm_int *d)
  958. {
  959. pstm_digit D, r, rr;
  960. int32 res;
  961. int x; //bbox: was int16
  962. pstm_int t;
  963. /* if the shift count is <= 0 then we do no work */
  964. if (b <= 0) {
  965. if (pstm_copy (a, c) != PSTM_OKAY) {
  966. return PS_MEM_FAIL;
  967. }
  968. if (d != NULL) {
  969. pstm_zero (d);
  970. }
  971. return PSTM_OKAY;
  972. }
  973. /* get the remainder */
  974. if (d != NULL) {
  975. if (pstm_init(pool, &t) != PSTM_OKAY) {
  976. return PS_MEM_FAIL;
  977. }
  978. if (pstm_mod_2d (a, b, &t) != PSTM_OKAY) {
  979. res = PS_MEM_FAIL;
  980. goto LBL_DONE;
  981. }
  982. }
  983. /* copy */
  984. if (pstm_copy(a, c) != PSTM_OKAY) {
  985. res = PS_MEM_FAIL;
  986. goto LBL_DONE;
  987. }
  988. /* shift by as many digits in the bit count */
  989. if (b >= (int32)DIGIT_BIT) {
  990. pstm_rshd (c, b / DIGIT_BIT);
  991. }
  992. /* shift any bit count < DIGIT_BIT */
  993. D = (pstm_digit) (b % DIGIT_BIT);
  994. if (D != 0) {
  995. register pstm_digit *tmpc, mask, shift;
  996. /* mask */
  997. mask = (((pstm_digit)1) << D) - 1;
  998. /* shift for lsb */
  999. shift = DIGIT_BIT - D;
  1000. /* alias */
  1001. tmpc = c->dp + (c->used - 1);
  1002. /* carry */
  1003. r = 0;
  1004. for (x = c->used - 1; x >= 0; x--) {
  1005. /* get the lower bits of this word in a temp */
  1006. rr = *tmpc & mask;
  1007. /* shift the current word and mix in the carry bits from previous */
  1008. *tmpc = (*tmpc >> D) | (r << shift);
  1009. --tmpc;
  1010. /* set the carry to the carry bits of the current word above */
  1011. r = rr;
  1012. }
  1013. }
  1014. pstm_clamp (c);
  1015. res = PSTM_OKAY;
  1016. LBL_DONE:
  1017. if (d != NULL) {
  1018. if (pstm_copy(&t, d) != PSTM_OKAY) {
  1019. res = PS_MEM_FAIL;
  1020. }
  1021. pstm_clear(&t);
  1022. }
  1023. return res;
  1024. }
  1025. #undef pstm_div_2d
  1026. #define pstm_div_2d(pool, a, b, c, d) (pstm_div_2d(a, b, c, d), PSTM_OKAY)
  1027. /******************************************************************************/
  1028. /*
  1029. b = a/2
  1030. */
  1031. #if 0 //UNUSED
  1032. int32 pstm_div_2(pstm_int * a, pstm_int * b)
  1033. {
  1034. int x, oldused; //bbox: was int16
  1035. if (b->alloc < a->used) {
  1036. if (pstm_grow(b, a->used) != PSTM_OKAY) {
  1037. return PS_MEM_FAIL;
  1038. }
  1039. }
  1040. oldused = b->used;
  1041. b->used = a->used;
  1042. {
  1043. register pstm_digit r, rr, *tmpa, *tmpb;
  1044. /* source alias */
  1045. tmpa = a->dp + b->used - 1;
  1046. /* dest alias */
  1047. tmpb = b->dp + b->used - 1;
  1048. /* carry */
  1049. r = 0;
  1050. for (x = b->used - 1; x >= 0; x--) {
  1051. /* get the carry for the next iteration */
  1052. rr = *tmpa & 1;
  1053. /* shift the current digit, add in carry and store */
  1054. *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
  1055. /* forward carry to next iteration */
  1056. r = rr;
  1057. }
  1058. /* zero excess digits */
  1059. tmpb = b->dp + b->used;
  1060. for (x = b->used; x < oldused; x++) {
  1061. *tmpb++ = 0;
  1062. }
  1063. }
  1064. b->sign = a->sign;
  1065. pstm_clamp (b);
  1066. return PSTM_OKAY;
  1067. }
  1068. #endif
  1069. /******************************************************************************/
  1070. /*
  1071. Creates "a" then copies b into it
  1072. */
  1073. #undef pstm_init_copy
  1074. #define pstm_init_copy(pool, a, b, toSqr) \
  1075. pstm_init_copy( a, b, toSqr)
  1076. static int32 pstm_init_copy(psPool_t *pool, pstm_int * a, pstm_int * b, int toSqr)
  1077. {
  1078. int x; //bbox: was int16
  1079. int32 res;
  1080. if (a == b) {
  1081. return PSTM_OKAY;
  1082. }
  1083. x = b->alloc;
  1084. if (toSqr) {
  1085. /*
  1086. Smart-size: Increasing size of a if b->used is roughly half
  1087. of b->alloc because usage has shown that a lot of these copies
  1088. go on to be squared and need these extra digits
  1089. */
  1090. if ((b->used * 2) + 2 >= x) {
  1091. x = (b->used * 2) + 3;
  1092. }
  1093. }
  1094. if ((res = pstm_init_size(pool, a, x)) != PSTM_OKAY) {
  1095. return res;
  1096. }
  1097. return pstm_copy(b, a);
  1098. }
  1099. #undef pstm_init_copy
  1100. #define pstm_init_copy(pool, a, b, toSqr) (pstm_init_copy(a, b, toSqr), PSTM_OKAY)
  1101. /******************************************************************************/
  1102. /*
  1103. With some compilers, we have seen issues linking with the builtin
  1104. 64 bit division routine. The issues with either manifest in a failure
  1105. to find 'udivdi3' at link time, or a runtime invalid instruction fault
  1106. during an RSA operation.
  1107. The routine below divides a 64 bit unsigned int by a 32 bit unsigned int
  1108. explicitly, rather than using the division operation
  1109. The 64 bit result is placed in the 'numerator' parameter
  1110. The 32 bit mod (remainder) of the division is the return parameter
  1111. Based on implementations by:
  1112. Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
  1113. Copyright (C) 1999 Hewlett-Packard Co
  1114. Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
  1115. */
  1116. #if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
  1117. static uint32 psDiv64(uint64 *numerator, uint32 denominator)
  1118. {
  1119. uint64 rem = *numerator;
  1120. uint64 b = denominator;
  1121. uint64 res = 0;
  1122. uint64 d = 1;
  1123. uint32 high = rem >> 32;
  1124. if (high >= denominator) {
  1125. high /= denominator;
  1126. res = (uint64) high << 32;
  1127. rem -= (uint64) (high * denominator) << 32;
  1128. }
  1129. while ((int64)b > 0 && b < rem) {
  1130. b = b+b;
  1131. d = d+d;
  1132. }
  1133. do {
  1134. if (rem >= b) {
  1135. rem -= b;
  1136. res += d;
  1137. }
  1138. b >>= 1;
  1139. d >>= 1;
  1140. } while (d);
  1141. *numerator = res;
  1142. return rem;
  1143. }
  1144. #endif /* USE_MATRIX_DIV64 */
  1145. #if defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
  1146. typedef unsigned long uint128 __attribute__ ((mode(TI)));
  1147. static uint64 psDiv128(uint128 *numerator, uint64 denominator)
  1148. {
  1149. uint128 rem = *numerator;
  1150. uint128 b = denominator;
  1151. uint128 res = 0;
  1152. uint128 d = 1;
  1153. uint64 high = rem >> 64;
  1154. if (high >= denominator) {
  1155. high /= denominator;
  1156. res = (uint128) high << 64;
  1157. rem -= (uint128) (high * denominator) << 64;
  1158. }
  1159. while ((uint128)b > 0 && b < rem) {
  1160. b = b+b;
  1161. d = d+d;
  1162. }
  1163. do {
  1164. if (rem >= b) {
  1165. rem -= b;
  1166. res += d;
  1167. }
  1168. b >>= 1;
  1169. d >>= 1;
  1170. } while (d);
  1171. *numerator = res;
  1172. return rem;
  1173. }
  1174. #endif /* USE_MATRIX_DIV128 */
  1175. /******************************************************************************/
  1176. /*
  1177. a/b => cb + d == a
  1178. */
  1179. static int32 pstm_div(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
  1180. pstm_int *d)
  1181. {
  1182. pstm_int q, x, y, t1, t2;
  1183. int32 res;
  1184. int n, t, i, norm, neg; //bbox: was int16
  1185. /* is divisor zero ? */
  1186. if (pstm_iszero (b) == 1) {
  1187. return PS_LIMIT_FAIL;
  1188. }
  1189. /* if a < b then q=0, r = a */
  1190. if (pstm_cmp_mag (a, b) == PSTM_LT) {
  1191. if (d != NULL) {
  1192. if (pstm_copy(a, d) != PSTM_OKAY) {
  1193. return PS_MEM_FAIL;
  1194. }
  1195. }
  1196. if (c != NULL) {
  1197. pstm_zero (c);
  1198. }
  1199. return PSTM_OKAY;
  1200. }
  1201. /*
  1202. Smart-size inits
  1203. */
  1204. if ((res = pstm_init_size(pool, &t1, a->alloc)) != PSTM_OKAY) {
  1205. return res;
  1206. }
  1207. if ((res = pstm_init_size(pool, &t2, 3)) != PSTM_OKAY) {
  1208. goto LBL_T1;
  1209. }
  1210. if ((res = pstm_init_copy(pool, &x, a, 0)) != PSTM_OKAY) {
  1211. goto LBL_T2;
  1212. }
  1213. /*
  1214. Used to be an init_copy on b but pstm_grow was always hit with triple size
  1215. */
  1216. if ((res = pstm_init_size(pool, &y, b->used * 3)) != PSTM_OKAY) {
  1217. goto LBL_X;
  1218. }
  1219. if ((res = pstm_copy(b, &y)) != PSTM_OKAY) {
  1220. goto LBL_Y;
  1221. }
  1222. /* fix the sign */
  1223. neg = (a->sign == b->sign) ? PSTM_ZPOS : PSTM_NEG;
  1224. x.sign = y.sign = PSTM_ZPOS;
  1225. /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */
  1226. norm = pstm_count_bits(&y) % DIGIT_BIT;
  1227. if (norm < (int32)(DIGIT_BIT-1)) {
  1228. norm = (DIGIT_BIT-1) - norm;
  1229. if ((res = pstm_mul_2d(&x, norm, &x)) != PSTM_OKAY) {
  1230. goto LBL_Y;
  1231. }
  1232. if ((res = pstm_mul_2d(&y, norm, &y)) != PSTM_OKAY) {
  1233. goto LBL_Y;
  1234. }
  1235. } else {
  1236. norm = 0;
  1237. }
  1238. /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
  1239. n = x.used - 1;
  1240. t = y.used - 1;
  1241. if ((res = pstm_init_size(pool, &q, n - t + 1)) != PSTM_OKAY) {
  1242. goto LBL_Y;
  1243. }
  1244. q.used = n - t + 1;
  1245. /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
  1246. if ((res = pstm_lshd(&y, n - t)) != PSTM_OKAY) { /* y = y*b**{n-t} */
  1247. goto LBL_Q;
  1248. }
  1249. while (pstm_cmp (&x, &y) != PSTM_LT) {
  1250. ++(q.dp[n - t]);
  1251. if ((res = pstm_sub(&x, &y, &x)) != PSTM_OKAY) {
  1252. goto LBL_Q;
  1253. }
  1254. }
  1255. /* reset y by shifting it back down */
  1256. pstm_rshd (&y, n - t);
  1257. /* step 3. for i from n down to (t + 1) */
  1258. for (i = n; i >= (t + 1); i--) {
  1259. if (i > x.used) {
  1260. continue;
  1261. }
  1262. /* step 3.1 if xi == yt then set q{i-t-1} to b-1,
  1263. * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
  1264. if (x.dp[i] == y.dp[t]) {
  1265. q.dp[i - t - 1] = (pstm_digit)((((pstm_word)1) << DIGIT_BIT) - 1);
  1266. } else {
  1267. pstm_word tmp;
  1268. tmp = ((pstm_word) x.dp[i]) << ((pstm_word) DIGIT_BIT);
  1269. tmp |= ((pstm_word) x.dp[i - 1]);
  1270. #if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
  1271. psDiv64(&tmp, y.dp[t]);
  1272. #elif defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
  1273. psDiv128(&tmp, y.dp[t]);
  1274. #else
  1275. tmp /= ((pstm_word) y.dp[t]);
  1276. #endif /* USE_MATRIX_DIV64 */
  1277. q.dp[i - t - 1] = (pstm_digit) (tmp);
  1278. }
  1279. /* while (q{i-t-1} * (yt * b + y{t-1})) >
  1280. xi * b**2 + xi-1 * b + xi-2
  1281. do q{i-t-1} -= 1;
  1282. */
  1283. q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
  1284. do {
  1285. q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
  1286. /* find left hand */
  1287. pstm_zero (&t1);
  1288. t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
  1289. t1.dp[1] = y.dp[t];
  1290. t1.used = 2;
  1291. if ((res = pstm_mul_d (&t1, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
  1292. goto LBL_Q;
  1293. }
  1294. /* find right hand */
  1295. t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
  1296. t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
  1297. t2.dp[2] = x.dp[i];
  1298. t2.used = 3;
  1299. } while (pstm_cmp_mag(&t1, &t2) == PSTM_GT);
  1300. /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
  1301. if ((res = pstm_mul_d(&y, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
  1302. goto LBL_Q;
  1303. }
  1304. if ((res = pstm_lshd(&t1, i - t - 1)) != PSTM_OKAY) {
  1305. goto LBL_Q;
  1306. }
  1307. if ((res = pstm_sub(&x, &t1, &x)) != PSTM_OKAY) {
  1308. goto LBL_Q;
  1309. }
  1310. /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
  1311. if (x.sign == PSTM_NEG) {
  1312. if ((res = pstm_copy(&y, &t1)) != PSTM_OKAY) {
  1313. goto LBL_Q;
  1314. }
  1315. if ((res = pstm_lshd (&t1, i - t - 1)) != PSTM_OKAY) {
  1316. goto LBL_Q;
  1317. }
  1318. if ((res = pstm_add (&x, &t1, &x)) != PSTM_OKAY) {
  1319. goto LBL_Q;
  1320. }
  1321. q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
  1322. }
  1323. }
  1324. /*
  1325. now q is the quotient and x is the remainder (which we have to normalize)
  1326. */
  1327. /* get sign before writing to c */
  1328. x.sign = x.used == 0 ? PSTM_ZPOS : a->sign;
  1329. if (c != NULL) {
  1330. pstm_clamp (&q);
  1331. if (pstm_copy (&q, c) != PSTM_OKAY) {
  1332. res = PS_MEM_FAIL;
  1333. goto LBL_Q;
  1334. }
  1335. c->sign = neg;
  1336. }
  1337. if (d != NULL) {
  1338. if ((res = pstm_div_2d (pool, &x, norm, &x, NULL)) != PSTM_OKAY) {
  1339. goto LBL_Q;
  1340. }
  1341. /*
  1342. the following is a kludge, essentially we were seeing the right
  1343. remainder but with excess digits that should have been zero
  1344. */
  1345. for (i = b->used; i < x.used; i++) {
  1346. x.dp[i] = 0;
  1347. }
  1348. pstm_clamp(&x);
  1349. if (pstm_copy (&x, d) != PSTM_OKAY) {
  1350. res = PS_MEM_FAIL;
  1351. goto LBL_Q;
  1352. }
  1353. }
  1354. res = PSTM_OKAY;
  1355. LBL_Q:pstm_clear (&q);
  1356. LBL_Y:pstm_clear (&y);
  1357. LBL_X:pstm_clear (&x);
  1358. LBL_T2:pstm_clear (&t2);
  1359. LBL_T1:pstm_clear (&t1);
  1360. return res;
  1361. }
  1362. /******************************************************************************/
  1363. /*
  1364. Swap the elements of two integers, for cases where you can't simply swap
  1365. the pstm_int pointers around
  1366. */
  1367. static void pstm_exch(pstm_int * a, pstm_int * b)
  1368. {
  1369. pstm_int t;
  1370. t = *a;
  1371. *a = *b;
  1372. *b = t;
  1373. }
  1374. /******************************************************************************/
  1375. /*
  1376. c = a mod b, 0 <= c < b
  1377. */
  1378. static int32 pstm_mod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
  1379. {
  1380. pstm_int t;
  1381. int32 err;
  1382. /*
  1383. Smart-size
  1384. */
  1385. if ((err = pstm_init_size(pool, &t, b->alloc)) != PSTM_OKAY) {
  1386. return err;
  1387. }
  1388. if ((err = pstm_div(pool, a, b, NULL, &t)) != PSTM_OKAY) {
  1389. pstm_clear (&t);
  1390. return err;
  1391. }
  1392. if (t.sign != b->sign) {
  1393. err = pstm_add(&t, b, c);
  1394. } else {
  1395. pstm_exch (&t, c);
  1396. }
  1397. pstm_clear (&t);
  1398. return err;
  1399. }
  1400. /******************************************************************************/
  1401. /*
  1402. d = a * b (mod c)
  1403. */
  1404. int32 FAST_FUNC pstm_mulmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
  1405. pstm_int *d)
  1406. {
  1407. int32 res;
  1408. int size; //bbox: was int16
  1409. pstm_int tmp;
  1410. /*
  1411. Smart-size pstm_inits. d is an output that is influenced by this local 't'
  1412. so don't shrink 'd' if it wants to becuase this will lead to an pstm_grow
  1413. in RSA operations
  1414. */
  1415. size = a->used + b->used + 1;
  1416. if ((a == d) && (size < a->alloc)) {
  1417. size = a->alloc;
  1418. }
  1419. if ((res = pstm_init_size(pool, &tmp, size)) != PSTM_OKAY) {
  1420. return res;
  1421. }
  1422. if ((res = pstm_mul_comba(pool, a, b, &tmp, NULL, 0)) != PSTM_OKAY) {
  1423. pstm_clear(&tmp);
  1424. return res;
  1425. }
  1426. res = pstm_mod(pool, &tmp, c, d);
  1427. pstm_clear(&tmp);
  1428. return res;
  1429. }
  1430. /******************************************************************************/
  1431. /*
  1432. * y = g**x (mod b)
  1433. * Some restrictions... x must be positive and < b
  1434. */
  1435. int32 FAST_FUNC pstm_exptmod(psPool_t *pool, pstm_int *G, pstm_int *X, pstm_int *P,
  1436. pstm_int *Y)
  1437. {
  1438. pstm_int M[32], res; /* Keep this winsize based: (1 << max_winsize) */
  1439. pstm_digit buf, mp;
  1440. pstm_digit *paD;
  1441. int32 err, bitbuf;
  1442. int bitcpy, bitcnt, mode, digidx, x, y, winsize; //bbox: was int16
  1443. uint32 paDlen;
  1444. /* set window size from what user set as optimization */
  1445. x = pstm_count_bits(X);
  1446. if (x < 50) {
  1447. winsize = 2;
  1448. } else {
  1449. winsize = PS_EXPTMOD_WINSIZE;
  1450. }
  1451. /* now setup montgomery */
  1452. if ((err = pstm_montgomery_setup (P, &mp)) != PSTM_OKAY) {
  1453. return err;
  1454. }
  1455. /* setup result */
  1456. if ((err = pstm_init_size(pool, &res, (P->used * 2) + 1)) != PSTM_OKAY) {
  1457. return err;
  1458. }
  1459. /*
  1460. create M table
  1461. The M table contains powers of the input base, e.g. M[x] = G^x mod P
  1462. The first half of the table is not computed though except for M[0] and M[1]
  1463. */
  1464. /* now we need R mod m */
  1465. if ((err = pstm_montgomery_calc_normalization (&res, P)) != PSTM_OKAY) {
  1466. goto LBL_RES;
  1467. }
  1468. /*
  1469. init M array
  1470. init first cell
  1471. */
  1472. if ((err = pstm_init_size(pool, &M[1], res.used)) != PSTM_OKAY) {
  1473. goto LBL_RES;
  1474. }
  1475. /* now set M[1] to G * R mod m */
  1476. if (pstm_cmp_mag(P, G) != PSTM_GT) {
  1477. /* G > P so we reduce it first */
  1478. if ((err = pstm_mod(pool, G, P, &M[1])) != PSTM_OKAY) {
  1479. goto LBL_M;
  1480. }
  1481. } else {
  1482. if ((err = pstm_copy(G, &M[1])) != PSTM_OKAY) {
  1483. goto LBL_M;
  1484. }
  1485. }
  1486. if ((err = pstm_mulmod (pool, &M[1], &res, P, &M[1])) != PSTM_OKAY) {
  1487. goto LBL_M;
  1488. }
  1489. /*
  1490. Pre-allocated digit. Used for mul, sqr, AND reduce
  1491. */
  1492. paDlen = ((M[1].used + 3) * 2) * sizeof(pstm_digit);
  1493. paD = xzalloc(paDlen);//bbox
  1494. /*
  1495. compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times
  1496. */
  1497. if (pstm_init_copy(pool, &M[1 << (winsize - 1)], &M[1], 1) != PSTM_OKAY) {
  1498. err = PS_MEM_FAIL;
  1499. goto LBL_PAD;
  1500. }
  1501. for (x = 0; x < (winsize - 1); x++) {
  1502. if ((err = pstm_sqr_comba (pool, &M[1 << (winsize - 1)],
  1503. &M[1 << (winsize - 1)], paD, paDlen)) != PSTM_OKAY) {
  1504. goto LBL_PAD;
  1505. }
  1506. if ((err = pstm_montgomery_reduce(pool, &M[1 << (winsize - 1)], P, mp,
  1507. paD, paDlen)) != PSTM_OKAY) {
  1508. goto LBL_PAD;
  1509. }
  1510. }
  1511. /*
  1512. now init the second half of the array
  1513. */
  1514. for (x = (1<<(winsize-1)) + 1; x < (1 << winsize); x++) {
  1515. if ((err = pstm_init_size(pool, &M[x], M[1<<(winsize-1)].alloc + 1))
  1516. != PSTM_OKAY) {
  1517. for (y = 1<<(winsize-1); y < x; y++) {
  1518. pstm_clear(&M[y]);
  1519. }
  1520. goto LBL_PAD;
  1521. }
  1522. }
  1523. /* create upper table */
  1524. for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
  1525. if ((err = pstm_mul_comba(pool, &M[x - 1], &M[1], &M[x], paD, paDlen))
  1526. != PSTM_OKAY) {
  1527. goto LBL_MARRAY;
  1528. }
  1529. if ((err = pstm_montgomery_reduce(pool, &M[x], P, mp, paD, paDlen)) !=
  1530. PSTM_OKAY) {
  1531. goto LBL_MARRAY;
  1532. }
  1533. }
  1534. /* set initial mode and bit cnt */
  1535. mode = 0;
  1536. bitcnt = 1;
  1537. buf = 0;
  1538. digidx = X->used - 1;
  1539. bitcpy = 0;
  1540. bitbuf = 0;
  1541. for (;;) {
  1542. /* grab next digit as required */
  1543. if (--bitcnt == 0) {
  1544. /* if digidx == -1 we are out of digits so break */
  1545. if (digidx == -1) {
  1546. break;
  1547. }
  1548. /* read next digit and reset bitcnt */
  1549. buf = X->dp[digidx--];
  1550. bitcnt = (int32)DIGIT_BIT;
  1551. }
  1552. /* grab the next msb from the exponent */
  1553. y = (pstm_digit)(buf >> (DIGIT_BIT - 1)) & 1;
  1554. buf <<= (pstm_digit)1;
  1555. /*
  1556. If the bit is zero and mode == 0 then we ignore it.
  1557. These represent the leading zero bits before the first 1 bit
  1558. in the exponent. Technically this opt is not required but it
  1559. does lower the # of trivial squaring/reductions used
  1560. */
  1561. if (mode == 0 && y == 0) {
  1562. continue;
  1563. }
  1564. /* if the bit is zero and mode == 1 then we square */
  1565. if (mode == 1 && y == 0) {
  1566. if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
  1567. PSTM_OKAY) {
  1568. goto LBL_MARRAY;
  1569. }
  1570. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
  1571. != PSTM_OKAY) {
  1572. goto LBL_MARRAY;
  1573. }
  1574. continue;
  1575. }
  1576. /* else we add it to the window */
  1577. bitbuf |= (y << (winsize - ++bitcpy));
  1578. mode = 2;
  1579. if (bitcpy == winsize) {
  1580. /* ok window is filled so square as required and mul square first */
  1581. for (x = 0; x < winsize; x++) {
  1582. if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
  1583. PSTM_OKAY) {
  1584. goto LBL_MARRAY;
  1585. }
  1586. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
  1587. paDlen)) != PSTM_OKAY) {
  1588. goto LBL_MARRAY;
  1589. }
  1590. }
  1591. /* then multiply */
  1592. if ((err = pstm_mul_comba(pool, &res, &M[bitbuf], &res, paD,
  1593. paDlen)) != PSTM_OKAY) {
  1594. goto LBL_MARRAY;
  1595. }
  1596. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
  1597. != PSTM_OKAY) {
  1598. goto LBL_MARRAY;
  1599. }
  1600. /* empty window and reset */
  1601. bitcpy = 0;
  1602. bitbuf = 0;
  1603. mode = 1;
  1604. }
  1605. }
  1606. /* if bits remain then square/multiply */
  1607. if (mode == 2 && bitcpy > 0) {
  1608. /* square then multiply if the bit is set */
  1609. for (x = 0; x < bitcpy; x++) {
  1610. if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
  1611. PSTM_OKAY) {
  1612. goto LBL_MARRAY;
  1613. }
  1614. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
  1615. != PSTM_OKAY) {
  1616. goto LBL_MARRAY;
  1617. }
  1618. /* get next bit of the window */
  1619. bitbuf <<= 1;
  1620. if ((bitbuf & (1 << winsize)) != 0) {
  1621. /* then multiply */
  1622. if ((err = pstm_mul_comba(pool, &res, &M[1], &res, paD, paDlen))
  1623. != PSTM_OKAY) {
  1624. goto LBL_MARRAY;
  1625. }
  1626. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
  1627. paDlen)) != PSTM_OKAY) {
  1628. goto LBL_MARRAY;
  1629. }
  1630. }
  1631. }
  1632. }
  1633. /*
  1634. Fix up result if Montgomery reduction is used recall that any value in a
  1635. Montgomery system is actually multiplied by R mod n. So we have to reduce
  1636. one more time to cancel out the factor of R.
  1637. */
  1638. if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen)) !=
  1639. PSTM_OKAY) {
  1640. goto LBL_MARRAY;
  1641. }
  1642. /* swap res with Y */
  1643. if ((err = pstm_copy (&res, Y)) != PSTM_OKAY) {
  1644. goto LBL_MARRAY;
  1645. }
  1646. err = PSTM_OKAY;
  1647. LBL_MARRAY:
  1648. for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
  1649. pstm_clear(&M[x]);
  1650. }
  1651. LBL_PAD:psFree(paD, pool);
  1652. LBL_M: pstm_clear(&M[1]);
  1653. LBL_RES:pstm_clear(&res);
  1654. return err;
  1655. }
  1656. /******************************************************************************/
  1657. /*
  1658. */
  1659. int32 FAST_FUNC pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
  1660. {
  1661. int32 res;
  1662. int sa, sb; //bbox: was int16
  1663. /* get sign of both inputs */
  1664. sa = a->sign;
  1665. sb = b->sign;
  1666. /* handle two cases, not four */
  1667. if (sa == sb) {
  1668. /* both positive or both negative, add their mags, copy the sign */
  1669. c->sign = sa;
  1670. if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
  1671. return res;
  1672. }
  1673. } else {
  1674. /*
  1675. one positive, the other negative
  1676. subtract the one with the greater magnitude from the one of the lesser
  1677. magnitude. The result gets the sign of the one with the greater mag.
  1678. */
  1679. if (pstm_cmp_mag (a, b) == PSTM_LT) {
  1680. c->sign = sb;
  1681. if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
  1682. return res;
  1683. }
  1684. } else {
  1685. c->sign = sa;
  1686. if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
  1687. return res;
  1688. }
  1689. }
  1690. }
  1691. return PS_SUCCESS;
  1692. }
  1693. /******************************************************************************/
  1694. /*
  1695. reverse an array, used for radix code
  1696. */
  1697. static void pstm_reverse (unsigned char *s, int len) //bbox: was int16 len
  1698. {
  1699. int32 ix, iy;
  1700. unsigned char t;
  1701. ix = 0;
  1702. iy = len - 1;
  1703. while (ix < iy) {
  1704. t = s[ix];
  1705. s[ix] = s[iy];
  1706. s[iy] = t;
  1707. ++ix;
  1708. --iy;
  1709. }
  1710. }
  1711. /******************************************************************************/
  1712. /*
  1713. No reverse. Useful in some of the EIP-154 PKA stuff where special byte
  1714. order seems to come into play more often
  1715. */
  1716. #if 0 //UNUSED
  1717. int32 pstm_to_unsigned_bin_nr(psPool_t *pool, pstm_int *a, unsigned char *b)
  1718. {
  1719. int32 res;
  1720. int x; //bbox: was int16
  1721. pstm_int t = { 0 };
  1722. if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
  1723. return res;
  1724. }
  1725. x = 0;
  1726. while (pstm_iszero (&t) == 0) {
  1727. b[x++] = (unsigned char) (t.dp[0] & 255);
  1728. if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
  1729. pstm_clear(&t);
  1730. return res;
  1731. }
  1732. }
  1733. pstm_clear(&t);
  1734. return PS_SUCCESS;
  1735. }
  1736. #endif
  1737. /******************************************************************************/
  1738. /*
  1739. */
  1740. int32 FAST_FUNC pstm_to_unsigned_bin(psPool_t *pool, pstm_int *a, unsigned char *b)
  1741. {
  1742. int32 res;
  1743. int x; //bbox: was int16
  1744. pstm_int t = { 0 };
  1745. if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
  1746. return res;
  1747. }
  1748. x = 0;
  1749. while (pstm_iszero (&t) == 0) {
  1750. b[x++] = (unsigned char) (t.dp[0] & 255);
  1751. if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
  1752. pstm_clear(&t);
  1753. return res;
  1754. }
  1755. }
  1756. pstm_reverse (b, x);
  1757. pstm_clear(&t);
  1758. return PS_SUCCESS;
  1759. }
  1760. #if 0 //UNUSED
  1761. /******************************************************************************/
  1762. /*
  1763. compare against a single digit
  1764. */
  1765. static int32 pstm_cmp_d(pstm_int *a, pstm_digit b)
  1766. {
  1767. /* compare based on sign */
  1768. if ((b && a->used == 0) || a->sign == PSTM_NEG) {
  1769. return PSTM_LT;
  1770. }
  1771. /* compare based on magnitude */
  1772. if (a->used > 1) {
  1773. return PSTM_GT;
  1774. }
  1775. /* compare the only digit of a to b */
  1776. if (a->dp[0] > b) {
  1777. return PSTM_GT;
  1778. } else if (a->dp[0] < b) {
  1779. return PSTM_LT;
  1780. } else {
  1781. return PSTM_EQ;
  1782. }
  1783. }
  1784. /*
  1785. Need invmod for ECC and also private key loading for hardware crypto
  1786. in cases where dQ > dP. The values must be switched and a new qP must be
  1787. calculated using this function
  1788. */
  1789. //bbox: pool unused
  1790. #define pstm_invmod_slow(pool, a, b, c) \
  1791. pstm_invmod_slow( a, b, c)
  1792. static int32 pstm_invmod_slow(psPool_t *pool, pstm_int * a, pstm_int * b,
  1793. pstm_int * c)
  1794. {
  1795. pstm_int x, y, u, v, A, B, C, D;
  1796. int32 res;
  1797. /* b cannot be negative */
  1798. if (b->sign == PSTM_NEG || pstm_iszero(b) == 1) {
  1799. return PS_LIMIT_FAIL;
  1800. }
  1801. /* init temps */
  1802. if (pstm_init_size(pool, &x, b->used) != PSTM_OKAY) {
  1803. return PS_MEM_FAIL;
  1804. }
  1805. /* x = a, y = b */
  1806. if ((res = pstm_mod(pool, a, b, &x)) != PSTM_OKAY) {
  1807. goto LBL_X;
  1808. }
  1809. if (pstm_init_copy(pool, &y, b, 0) != PSTM_OKAY) {
  1810. goto LBL_X;
  1811. }
  1812. /* 2. [modified] if x,y are both even then return an error! */
  1813. if (pstm_iseven (&x) == 1 && pstm_iseven (&y) == 1) {
  1814. res = PS_FAILURE;
  1815. goto LBL_Y;
  1816. }
  1817. /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
  1818. if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
  1819. goto LBL_Y;
  1820. }
  1821. if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
  1822. goto LBL_U;
  1823. }
  1824. if ((res = pstm_init_size(pool, &A, sizeof(pstm_digit))) != PSTM_OKAY) {
  1825. goto LBL_V;
  1826. }
  1827. if ((res = pstm_init_size(pool, &D, sizeof(pstm_digit))) != PSTM_OKAY) {
  1828. goto LBL_A;
  1829. }
  1830. pstm_set (&A, 1);
  1831. pstm_set (&D, 1);
  1832. if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
  1833. goto LBL_D;
  1834. }
  1835. if ((res = pstm_init(pool, &C)) != PSTM_OKAY) {
  1836. goto LBL_B;
  1837. }
  1838. top:
  1839. /* 4. while u is even do */
  1840. while (pstm_iseven (&u) == 1) {
  1841. /* 4.1 u = u/2 */
  1842. if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
  1843. goto LBL_C;
  1844. }
  1845. /* 4.2 if A or B is odd then */
  1846. if (pstm_isodd (&A) == 1 || pstm_isodd (&B) == 1) {
  1847. /* A = (A+y)/2, B = (B-x)/2 */
  1848. if ((res = pstm_add (&A, &y, &A)) != PSTM_OKAY) {
  1849. goto LBL_C;
  1850. }
  1851. if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
  1852. goto LBL_C;
  1853. }
  1854. }
  1855. /* A = A/2, B = B/2 */
  1856. if ((res = pstm_div_2 (&A, &A)) != PSTM_OKAY) {
  1857. goto LBL_C;
  1858. }
  1859. if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
  1860. goto LBL_C;
  1861. }
  1862. }
  1863. /* 5. while v is even do */
  1864. while (pstm_iseven (&v) == 1) {
  1865. /* 5.1 v = v/2 */
  1866. if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
  1867. goto LBL_C;
  1868. }
  1869. /* 5.2 if C or D is odd then */
  1870. if (pstm_isodd (&C) == 1 || pstm_isodd (&D) == 1) {
  1871. /* C = (C+y)/2, D = (D-x)/2 */
  1872. if ((res = pstm_add (&C, &y, &C)) != PSTM_OKAY) {
  1873. goto LBL_C;
  1874. }
  1875. if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
  1876. goto LBL_C;
  1877. }
  1878. }
  1879. /* C = C/2, D = D/2 */
  1880. if ((res = pstm_div_2 (&C, &C)) != PSTM_OKAY) {
  1881. goto LBL_C;
  1882. }
  1883. if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
  1884. goto LBL_C;
  1885. }
  1886. }
  1887. /* 6. if u >= v then */
  1888. if (pstm_cmp (&u, &v) != PSTM_LT) {
  1889. /* u = u - v, A = A - C, B = B - D */
  1890. if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
  1891. goto LBL_C;
  1892. }
  1893. if ((res = pstm_sub (&A, &C, &A)) != PSTM_OKAY) {
  1894. goto LBL_C;
  1895. }
  1896. if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
  1897. goto LBL_C;
  1898. }
  1899. } else {
  1900. /* v - v - u, C = C - A, D = D - B */
  1901. if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
  1902. goto LBL_C;
  1903. }
  1904. if ((res = pstm_sub (&C, &A, &C)) != PSTM_OKAY) {
  1905. goto LBL_C;
  1906. }
  1907. if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
  1908. goto LBL_C;
  1909. }
  1910. }
  1911. /* if not zero goto step 4 */
  1912. if (pstm_iszero (&u) == 0)
  1913. goto top;
  1914. /* now a = C, b = D, gcd == g*v */
  1915. /* if v != 1 then there is no inverse */
  1916. if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
  1917. res = PS_FAILURE;
  1918. goto LBL_C;
  1919. }
  1920. /* if its too low */
  1921. while (pstm_cmp_d(&C, 0) == PSTM_LT) {
  1922. if ((res = pstm_add(&C, b, &C)) != PSTM_OKAY) {
  1923. goto LBL_C;
  1924. }
  1925. }
  1926. /* too big */
  1927. while (pstm_cmp_mag(&C, b) != PSTM_LT) {
  1928. if ((res = pstm_sub(&C, b, &C)) != PSTM_OKAY) {
  1929. goto LBL_C;
  1930. }
  1931. }
  1932. /* C is now the inverse */
  1933. if ((res = pstm_copy(&C, c)) != PSTM_OKAY) {
  1934. goto LBL_C;
  1935. }
  1936. res = PSTM_OKAY;
  1937. LBL_C: pstm_clear(&C);
  1938. LBL_D: pstm_clear(&D);
  1939. LBL_B: pstm_clear(&B);
  1940. LBL_A: pstm_clear(&A);
  1941. LBL_V: pstm_clear(&v);
  1942. LBL_U: pstm_clear(&u);
  1943. LBL_Y: pstm_clear(&y);
  1944. LBL_X: pstm_clear(&x);
  1945. return res;
  1946. }
  1947. /* c = 1/a (mod b) for odd b only */
  1948. int32 pstm_invmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
  1949. {
  1950. pstm_int x, y, u, v, B, D;
  1951. int32 res;
  1952. int neg, sanity; //bbox: was uint16
  1953. /* 2. [modified] b must be odd */
  1954. if (pstm_iseven (b) == 1) {
  1955. return pstm_invmod_slow(pool, a,b,c);
  1956. }
  1957. /* x == modulus, y == value to invert */
  1958. if ((res = pstm_init_copy(pool, &x, b, 0)) != PSTM_OKAY) {
  1959. return res;
  1960. }
  1961. if ((res = pstm_init_size(pool, &y, a->alloc)) != PSTM_OKAY) {
  1962. goto LBL_X;
  1963. }
  1964. /* we need y = |a| */
  1965. pstm_abs(a, &y);
  1966. /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
  1967. if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
  1968. goto LBL_Y;
  1969. }
  1970. if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
  1971. goto LBL_U;
  1972. }
  1973. if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
  1974. goto LBL_V;
  1975. }
  1976. if ((res = pstm_init(pool, &D)) != PSTM_OKAY) {
  1977. goto LBL_B;
  1978. }
  1979. pstm_set (&D, 1);
  1980. sanity = 0;
  1981. top:
  1982. /* 4. while u is even do */
  1983. while (pstm_iseven (&u) == 1) {
  1984. /* 4.1 u = u/2 */
  1985. if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
  1986. goto LBL_D;
  1987. }
  1988. /* 4.2 if B is odd then */
  1989. if (pstm_isodd (&B) == 1) {
  1990. if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
  1991. goto LBL_D;
  1992. }
  1993. }
  1994. /* B = B/2 */
  1995. if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
  1996. goto LBL_D;
  1997. }
  1998. }
  1999. /* 5. while v is even do */
  2000. while (pstm_iseven (&v) == 1) {
  2001. /* 5.1 v = v/2 */
  2002. if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
  2003. goto LBL_D;
  2004. }
  2005. /* 5.2 if D is odd then */
  2006. if (pstm_isodd (&D) == 1) {
  2007. /* D = (D-x)/2 */
  2008. if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
  2009. goto LBL_D;
  2010. }
  2011. }
  2012. /* D = D/2 */
  2013. if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
  2014. goto LBL_D;
  2015. }
  2016. }
  2017. /* 6. if u >= v then */
  2018. if (pstm_cmp (&u, &v) != PSTM_LT) {
  2019. /* u = u - v, B = B - D */
  2020. if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
  2021. goto LBL_D;
  2022. }
  2023. if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
  2024. goto LBL_D;
  2025. }
  2026. } else {
  2027. /* v - v - u, D = D - B */
  2028. if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
  2029. goto LBL_D;
  2030. }
  2031. if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
  2032. goto LBL_D;
  2033. }
  2034. }
  2035. /* if not zero goto step 4 */
  2036. if (sanity++ > 1000) {
  2037. res = PS_LIMIT_FAIL;
  2038. goto LBL_D;
  2039. }
  2040. if (pstm_iszero (&u) == 0) {
  2041. goto top;
  2042. }
  2043. /* now a = C, b = D, gcd == g*v */
  2044. /* if v != 1 then there is no inverse */
  2045. if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
  2046. res = PS_FAILURE;
  2047. goto LBL_D;
  2048. }
  2049. /* b is now the inverse */
  2050. neg = a->sign;
  2051. while (D.sign == PSTM_NEG) {
  2052. if ((res = pstm_add (&D, b, &D)) != PSTM_OKAY) {
  2053. goto LBL_D;
  2054. }
  2055. }
  2056. if ((res = pstm_copy (&D, c)) != PSTM_OKAY) {
  2057. goto LBL_D;
  2058. }
  2059. c->sign = neg;
  2060. res = PSTM_OKAY;
  2061. LBL_D: pstm_clear(&D);
  2062. LBL_B: pstm_clear(&B);
  2063. LBL_V: pstm_clear(&v);
  2064. LBL_U: pstm_clear(&u);
  2065. LBL_Y: pstm_clear(&y);
  2066. LBL_X: pstm_clear(&x);
  2067. return res;
  2068. }
  2069. #endif //UNUSED
  2070. #endif /* !DISABLE_PSTM */
  2071. /******************************************************************************/