1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263 |
- #include "tls.h"
- #ifndef DISABLE_PSTM
- static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c);
- int32 pstm_init_size(psPool_t *pool, pstm_int * a, uint32 size)
- {
- a->dp = xzalloc(sizeof (pstm_digit) * size);
- a->used = 0;
- a->alloc = size;
- a->sign = PSTM_ZPOS;
- return PSTM_OKAY;
- }
- int32 pstm_init(psPool_t *pool, pstm_int * a)
- {
- a->dp = xzalloc(sizeof (pstm_digit) * PSTM_DEFAULT_INIT);
- a->used = 0;
- a->alloc = PSTM_DEFAULT_INIT;
- a->sign = PSTM_ZPOS;
- return PSTM_OKAY;
- }
- int32 pstm_grow(pstm_int * a, int size)
- {
- int i;
- pstm_digit *tmp;
- if (a->alloc < size) {
- tmp = xrealloc(a->dp, sizeof (pstm_digit) * size);
- a->dp = tmp;
- i = a->alloc;
- a->alloc = size;
- for (; i < a->alloc; i++) {
- a->dp[i] = 0;
- }
- }
- return PSTM_OKAY;
- }
- int32 pstm_copy(pstm_int * a, pstm_int * b)
- {
- int32 res, n;
- if (a == b) {
- return PSTM_OKAY;
- }
- if (b->alloc < a->used) {
- if ((res = pstm_grow (b, a->used)) != PSTM_OKAY) {
- return res;
- }
- }
- {
- register pstm_digit *tmpa, *tmpb;
-
-
- tmpa = a->dp;
-
- tmpb = b->dp;
-
- for (n = 0; n < a->used; n++) {
- *tmpb++ = *tmpa++;
- }
-
- for (; n < b->used; n++) {
- *tmpb++ = 0;
- }
- }
- b->used = a->used;
- b->sign = a->sign;
- return PSTM_OKAY;
- }
- void pstm_clamp(pstm_int * a)
- {
- while (a->used > 0 && a->dp[a->used - 1] == 0) {
- --(a->used);
- }
- if (a->used == 0) {
- a->sign = PSTM_ZPOS;
- }
- }
- void pstm_clear(pstm_int * a)
- {
- int32 i;
- if (a != NULL && a->dp != NULL) {
- for (i = 0; i < a->used; i++) {
- a->dp[i] = 0;
- }
- psFree (a->dp, a->pool);
- a->dp = NULL;
- a->alloc = a->used = 0;
- a->sign = PSTM_ZPOS;
- }
- }
- void pstm_clear_multi(pstm_int *mp0, pstm_int *mp1, pstm_int *mp2,
- pstm_int *mp3, pstm_int *mp4, pstm_int *mp5,
- pstm_int *mp6, pstm_int *mp7)
- {
- int32 n;
- pstm_int *tempArray[9];
- tempArray[0] = mp0;
- tempArray[1] = mp1;
- tempArray[2] = mp2;
- tempArray[3] = mp3;
- tempArray[4] = mp4;
- tempArray[5] = mp5;
- tempArray[6] = mp6;
- tempArray[7] = mp7;
- tempArray[8] = NULL;
- for (n = 0; tempArray[n] != NULL; n++) {
- if ((tempArray[n] != NULL) && (tempArray[n]->dp != NULL)) {
- pstm_clear(tempArray[n]);
- }
- }
- }
- void pstm_zero(pstm_int * a)
- {
- int32 n;
- pstm_digit *tmp;
- a->sign = PSTM_ZPOS;
- a->used = 0;
- tmp = a->dp;
- for (n = 0; n < a->alloc; n++) {
- *tmp++ = 0;
- }
- }
- int32 pstm_cmp_mag(pstm_int * a, pstm_int * b)
- {
- int n;
- pstm_digit *tmpa, *tmpb;
- if (a->used > b->used) {
- return PSTM_GT;
- }
- if (a->used < b->used) {
- return PSTM_LT;
- }
-
- tmpa = a->dp + (a->used - 1);
-
- tmpb = b->dp + (a->used - 1);
- for (n = 0; n < a->used; ++n, --tmpa, --tmpb) {
- if (*tmpa > *tmpb) {
- return PSTM_GT;
- }
- if (*tmpa < *tmpb) {
- return PSTM_LT;
- }
- }
- return PSTM_EQ;
- }
- int32 pstm_cmp(pstm_int * a, pstm_int * b)
- {
- if (a->sign != b->sign) {
- if (a->sign == PSTM_NEG) {
- return PSTM_LT;
- } else {
- return PSTM_GT;
- }
- }
- if (a->sign == PSTM_NEG) {
-
- return pstm_cmp_mag(b, a);
- } else {
- return pstm_cmp_mag(a, b);
- }
- }
- int32 pstm_init_for_read_unsigned_bin(psPool_t *pool, pstm_int *a, uint32 len)
- {
- int32 size;
- size = (((len / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
- / DIGIT_BIT) + 2;
- return pstm_init_size(pool, a, size);
- }
- int32 pstm_read_unsigned_bin(pstm_int *a, unsigned char *b, int32 c)
- {
-
- pstm_zero (a);
- #if (defined(ENDIAN_LITTLE) || defined(ENDIAN_BIG)) && !defined(PSTM_64BIT)
-
- #if defined(ENDIAN_LITTLE) && defined(ENDIAN_BIG)
- #error Both ENDIAN_LITTLE and ENDIAN_BIG defined.
- #endif
- {
- unsigned char *pd;
- if ((unsigned)c > (PSTM_MAX_SIZE * sizeof(pstm_digit))) {
- uint32 excess = c - (PSTM_MAX_SIZE * sizeof(pstm_digit));
- c -= excess;
- b += excess;
- }
- a->used = ((c + sizeof(pstm_digit) - 1)/sizeof(pstm_digit));
- if (a->alloc < a->used) {
- if (pstm_grow(a, a->used) != PSTM_OKAY) {
- return PSTM_MEM;
- }
- }
- pd = (unsigned char *)a->dp;
-
- #ifdef ENDIAN_BIG
- {
-
- int32 idx = (c - 1) & ~3;
- switch (c % 4) {
- case 0: do { pd[idx+0] = *b++;
- case 3: pd[idx+1] = *b++;
- case 2: pd[idx+2] = *b++;
- case 1: pd[idx+3] = *b++;
- idx -= 4;
- } while ((c -= 4) > 0);
- }
- }
- #else
- for (c -= 1; c >= 0; c -= 1) {
- pd[c] = *b++;
- }
- #endif
- }
- #else
-
- a->used = (((c / sizeof(pstm_digit)) * (sizeof(pstm_digit) * CHAR_BIT))
- / DIGIT_BIT) + 2;
- if (a->alloc < a->used) {
- if (pstm_grow(a, a->used) != PSTM_OKAY) {
- return PSTM_MEM;
- }
- }
-
- for (; c > 0; c--) {
- if (pstm_mul_2d (a, 8, a) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- a->dp[0] |= *b++;
- a->used += 1;
- }
- #endif
- pstm_clamp (a);
- return PS_SUCCESS;
- }
- int pstm_count_bits (pstm_int * a)
- {
- int r;
- pstm_digit q;
- if (a->used == 0) {
- return 0;
- }
-
- r = (a->used - 1) * DIGIT_BIT;
-
- q = a->dp[a->used - 1];
- while (q > ((pstm_digit) 0)) {
- ++r;
- q >>= ((pstm_digit) 1);
- }
- return r;
- }
- int32 pstm_unsigned_bin_size(pstm_int *a)
- {
- int32 size = pstm_count_bits (a);
- return (size / 8 + ((size & 7) != 0 ? 1 : 0));
- }
- void pstm_set(pstm_int *a, pstm_digit b)
- {
- pstm_zero(a);
- a->dp[0] = b;
- a->used = a->dp[0] ? 1 : 0;
- }
- void pstm_rshd(pstm_int *a, int x)
- {
- int y;
-
- if (x >= a->used) {
- pstm_zero(a);
- return;
- }
-
- for (y = 0; y < a->used - x; y++) {
- a->dp[y] = a->dp[y+x];
- }
-
- for (; y < a->used; y++) {
- a->dp[y] = 0;
- }
-
- a->used -= x;
- pstm_clamp(a);
- }
- int32 pstm_lshd(pstm_int * a, int b)
- {
- int x;
- int32 res;
- if (b <= 0) {
- return PSTM_OKAY;
- }
- if (a->alloc < a->used + b) {
- if ((res = pstm_grow (a, a->used + b)) != PSTM_OKAY) {
- return res;
- }
- }
- {
- register pstm_digit *top, *bottom;
- a->used += b;
-
- top = a->dp + a->used - 1;
-
- bottom = a->dp + a->used - 1 - b;
- for (x = a->used - 1; x >= b; x--) {
- *top-- = *bottom--;
- }
-
- top = a->dp;
- for (x = 0; x < b; x++) {
- *top++ = 0;
- }
- }
- return PSTM_OKAY;
- }
- int32 pstm_2expt(pstm_int *a, int b)
- {
- int z;
-
- pstm_zero (a);
- if (b < 0) {
- return PSTM_OKAY;
- }
- z = b / DIGIT_BIT;
- if (z >= PSTM_MAX_SIZE) {
- return PS_LIMIT_FAIL;
- }
-
- a->used = z + 1;
- if (a->used > a->alloc) {
- if (pstm_grow(a, a->used) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
-
- a->dp[z] = ((pstm_digit)1) << (b % DIGIT_BIT);
- return PSTM_OKAY;
- }
- int32 pstm_mul_2(pstm_int * a, pstm_int * b)
- {
- int32 res;
- int x, oldused;
- if (b->alloc < a->used + 1) {
- if ((res = pstm_grow (b, a->used + 1)) != PSTM_OKAY) {
- return res;
- }
- }
- oldused = b->used;
- b->used = a->used;
- {
- register pstm_digit r, rr, *tmpa, *tmpb;
-
- tmpa = a->dp;
-
- tmpb = b->dp;
-
- r = 0;
- for (x = 0; x < a->used; x++) {
- rr = *tmpa >> ((pstm_digit)(DIGIT_BIT - 1));
- *tmpb++ = ((*tmpa++ << ((pstm_digit)1)) | r);
- r = rr;
- }
-
- if (r != 0 && b->used != (PSTM_MAX_SIZE-1)) {
-
- *tmpb = 1;
- ++(b->used);
- }
- tmpb = b->dp + b->used;
- for (x = b->used; x < oldused; x++) {
- *tmpb++ = 0;
- }
- }
- b->sign = a->sign;
- return PSTM_OKAY;
- }
- int32 s_pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
- {
- int oldbused, oldused;
- int32 x;
- pstm_word t;
- if (b->used > a->used) {
- return PS_LIMIT_FAIL;
- }
- if (c->alloc < a->used) {
- if ((x = pstm_grow (c, a->used)) != PSTM_OKAY) {
- return x;
- }
- }
- oldused = c->used;
- oldbused = b->used;
- c->used = a->used;
- t = 0;
- for (x = 0; x < oldbused; x++) {
- t = ((pstm_word)a->dp[x]) - (((pstm_word)b->dp[x]) + t);
- c->dp[x] = (pstm_digit)t;
- t = (t >> DIGIT_BIT)&1;
- }
- for (; x < a->used; x++) {
- t = ((pstm_word)a->dp[x]) - t;
- c->dp[x] = (pstm_digit)t;
- t = (t >> DIGIT_BIT);
- }
- for (; x < oldused; x++) {
- c->dp[x] = 0;
- }
- pstm_clamp(c);
- return PSTM_OKAY;
- }
- static int32 s_pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
- {
- int x, y, oldused;
- register pstm_word t, adp, bdp;
- y = a->used;
- if (b->used > y) {
- y = b->used;
- }
- oldused = c->used;
- c->used = y;
- if (c->used > c->alloc) {
- if (pstm_grow(c, c->used) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- t = 0;
- for (x = 0; x < y; x++) {
- if (a->used < x) {
- adp = 0;
- } else {
- adp = (pstm_word)a->dp[x];
- }
- if (b->used < x) {
- bdp = 0;
- } else {
- bdp = (pstm_word)b->dp[x];
- }
- t += (adp) + (bdp);
- c->dp[x] = (pstm_digit)t;
- t >>= DIGIT_BIT;
- }
- if (t != 0 && x < PSTM_MAX_SIZE) {
- if (c->used == c->alloc) {
- if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- c->dp[c->used++] = (pstm_digit)t;
- ++x;
- }
- c->used = x;
- for (; x < oldused; x++) {
- c->dp[x] = 0;
- }
- pstm_clamp(c);
- return PSTM_OKAY;
- }
- int32 pstm_sub(pstm_int *a, pstm_int *b, pstm_int *c)
- {
- int32 res;
- int sa, sb;
- sa = a->sign;
- sb = b->sign;
- if (sa != sb) {
- c->sign = sa;
- if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
- return res;
- }
- } else {
- if (pstm_cmp_mag (a, b) != PSTM_LT) {
-
- c->sign = sa;
-
- if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
- return res;
- }
- } else {
-
- c->sign = (sa == PSTM_ZPOS) ? PSTM_NEG : PSTM_ZPOS;
-
- if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
- return res;
- }
- }
- }
- return PS_SUCCESS;
- }
- int32 pstm_sub_d(psPool_t *pool, pstm_int *a, pstm_digit b, pstm_int *c)
- {
- pstm_int tmp;
- int32 res;
- if (pstm_init_size(pool, &tmp, sizeof(pstm_digit)) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- pstm_set(&tmp, b);
- res = pstm_sub(a, &tmp, c);
- pstm_clear(&tmp);
- return res;
- }
- int32 pstm_montgomery_setup(pstm_int *a, pstm_digit *rho)
- {
- pstm_digit x, b;
- b = a->dp[0];
- if ((b & 1) == 0) {
- psTraceCrypto("pstm_montogomery_setup failure\n");
- return PS_ARG_FAIL;
- }
- x = (((b + 2) & 4) << 1) + b;
- x *= 2 - b * x;
- x *= 2 - b * x;
- x *= 2 - b * x;
- #ifdef PSTM_64BIT
- x *= 2 - b * x;
- #endif
-
- *rho = (pstm_digit)(((pstm_word) 1 << ((pstm_word) DIGIT_BIT)) -
- ((pstm_word)x));
- return PSTM_OKAY;
- }
- int32 pstm_montgomery_calc_normalization(pstm_int *a, pstm_int *b)
- {
- int32 x;
- int bits;
-
- bits = pstm_count_bits (b) % DIGIT_BIT;
- if (!bits) bits = DIGIT_BIT;
-
- if (b->used > 1) {
- if ((x = pstm_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) !=
- PSTM_OKAY) {
- return x;
- }
- } else {
- pstm_set(a, 1);
- bits = 1;
- }
-
- for (x = bits - 1; x < (int32)DIGIT_BIT; x++) {
- if (pstm_mul_2 (a, a) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- if (pstm_cmp_mag (a, b) != PSTM_LT) {
- if (s_pstm_sub (a, b, a) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- }
- return PSTM_OKAY;
- }
- static int32 pstm_mul_2d(pstm_int *a, int b, pstm_int *c)
- {
- pstm_digit carry, carrytmp, shift;
- int x;
-
- if (pstm_copy(a, c) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
-
- if (b >= DIGIT_BIT) {
- if (pstm_lshd(c, b/DIGIT_BIT) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- b %= DIGIT_BIT;
-
- if (b != 0) {
- carry = 0;
- shift = DIGIT_BIT - b;
- for (x = 0; x < c->used; x++) {
- carrytmp = c->dp[x] >> shift;
- c->dp[x] = (c->dp[x] << b) + carry;
- carry = carrytmp;
- }
-
- if (carry && x < PSTM_MAX_SIZE) {
- if (c->used == c->alloc) {
- if (pstm_grow(c, c->alloc + 1) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- c->dp[c->used++] = carry;
- }
- }
- pstm_clamp(c);
- return PSTM_OKAY;
- }
- static int32 pstm_mod_2d(pstm_int *a, int b, pstm_int *c)
- {
- int x;
-
- if (b <= 0) {
- pstm_zero(c);
- return PSTM_OKAY;
- }
-
- if (pstm_copy(a, c) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
-
- if (b >= (DIGIT_BIT * a->used)) {
- return PSTM_OKAY;
- }
-
- for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++)
- {
- c->dp[x] = 0;
- }
-
- c->dp[b / DIGIT_BIT] &= ~((pstm_digit)0) >> (DIGIT_BIT - b);
- pstm_clamp (c);
- return PSTM_OKAY;
- }
- int32 pstm_mul_d(pstm_int *a, pstm_digit b, pstm_int *c)
- {
- pstm_word w;
- int32 res;
- int x, oldused;
- if (c->alloc < a->used + 1) {
- if ((res = pstm_grow (c, a->used + 1)) != PSTM_OKAY) {
- return res;
- }
- }
- oldused = c->used;
- c->used = a->used;
- c->sign = a->sign;
- w = 0;
- for (x = 0; x < a->used; x++) {
- w = ((pstm_word)a->dp[x]) * ((pstm_word)b) + w;
- c->dp[x] = (pstm_digit)w;
- w = w >> DIGIT_BIT;
- }
- if (w != 0 && (a->used != PSTM_MAX_SIZE)) {
- c->dp[c->used++] = (pstm_digit)w;
- ++x;
- }
- for (; x < oldused; x++) {
- c->dp[x] = 0;
- }
- pstm_clamp(c);
- return PSTM_OKAY;
- }
- int32 pstm_div_2d(psPool_t *pool, pstm_int *a, int b, pstm_int *c,
- pstm_int *d)
- {
- pstm_digit D, r, rr;
- int32 res;
- int x;
- pstm_int t;
-
- if (b <= 0) {
- if (pstm_copy (a, c) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- if (d != NULL) {
- pstm_zero (d);
- }
- return PSTM_OKAY;
- }
-
- if (d != NULL) {
- if (pstm_init(pool, &t) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- if (pstm_mod_2d (a, b, &t) != PSTM_OKAY) {
- res = PS_MEM_FAIL;
- goto LBL_DONE;
- }
- }
-
- if (pstm_copy(a, c) != PSTM_OKAY) {
- res = PS_MEM_FAIL;
- goto LBL_DONE;
- }
-
- if (b >= (int32)DIGIT_BIT) {
- pstm_rshd (c, b / DIGIT_BIT);
- }
-
- D = (pstm_digit) (b % DIGIT_BIT);
- if (D != 0) {
- register pstm_digit *tmpc, mask, shift;
-
- mask = (((pstm_digit)1) << D) - 1;
-
- shift = DIGIT_BIT - D;
-
- tmpc = c->dp + (c->used - 1);
-
- r = 0;
- for (x = c->used - 1; x >= 0; x--) {
-
- rr = *tmpc & mask;
-
- *tmpc = (*tmpc >> D) | (r << shift);
- --tmpc;
-
- r = rr;
- }
- }
- pstm_clamp (c);
- res = PSTM_OKAY;
- LBL_DONE:
- if (d != NULL) {
- if (pstm_copy(&t, d) != PSTM_OKAY) {
- res = PS_MEM_FAIL;
- }
- pstm_clear(&t);
- }
- return res;
- }
- int32 pstm_div_2(pstm_int * a, pstm_int * b)
- {
- int x, oldused;
- if (b->alloc < a->used) {
- if (pstm_grow(b, a->used) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- oldused = b->used;
- b->used = a->used;
- {
- register pstm_digit r, rr, *tmpa, *tmpb;
-
- tmpa = a->dp + b->used - 1;
-
- tmpb = b->dp + b->used - 1;
-
- r = 0;
- for (x = b->used - 1; x >= 0; x--) {
-
- rr = *tmpa & 1;
-
- *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
-
- r = rr;
- }
-
- tmpb = b->dp + b->used;
- for (x = b->used; x < oldused; x++) {
- *tmpb++ = 0;
- }
- }
- b->sign = a->sign;
- pstm_clamp (b);
- return PSTM_OKAY;
- }
- int32 pstm_init_copy(psPool_t *pool, pstm_int * a, pstm_int * b, int toSqr)
- {
- int x;
- int32 res;
- if (a == b) {
- return PSTM_OKAY;
- }
- x = b->alloc;
- if (toSqr) {
- if ((b->used * 2) + 2 >= x) {
- x = (b->used * 2) + 3;
- }
- }
- if ((res = pstm_init_size(pool, a, x)) != PSTM_OKAY) {
- return res;
- }
- return pstm_copy(b, a);
- }
- #if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
- static uint32 psDiv64(uint64 *numerator, uint32 denominator)
- {
- uint64 rem = *numerator;
- uint64 b = denominator;
- uint64 res = 0;
- uint64 d = 1;
- uint32 high = rem >> 32;
- if (high >= denominator) {
- high /= denominator;
- res = (uint64) high << 32;
- rem -= (uint64) (high * denominator) << 32;
- }
- while ((int64)b > 0 && b < rem) {
- b = b+b;
- d = d+d;
- }
- do {
- if (rem >= b) {
- rem -= b;
- res += d;
- }
- b >>= 1;
- d >>= 1;
- } while (d);
- *numerator = res;
- return rem;
- }
- #endif
- #if defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
- typedef unsigned long uint128 __attribute__ ((mode(TI)));
- static uint64 psDiv128(uint128 *numerator, uint64 denominator)
- {
- uint128 rem = *numerator;
- uint128 b = denominator;
- uint128 res = 0;
- uint128 d = 1;
- uint64 high = rem >> 64;
- if (high >= denominator) {
- high /= denominator;
- res = (uint128) high << 64;
- rem -= (uint128) (high * denominator) << 64;
- }
- while ((uint128)b > 0 && b < rem) {
- b = b+b;
- d = d+d;
- }
- do {
- if (rem >= b) {
- rem -= b;
- res += d;
- }
- b >>= 1;
- d >>= 1;
- } while (d);
- *numerator = res;
- return rem;
- }
- #endif
- int32 pstm_div(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
- pstm_int *d)
- {
- pstm_int q, x, y, t1, t2;
- int32 res;
- int n, t, i, norm, neg;
-
- if (pstm_iszero (b) == 1) {
- return PS_LIMIT_FAIL;
- }
-
- if (pstm_cmp_mag (a, b) == PSTM_LT) {
- if (d != NULL) {
- if (pstm_copy(a, d) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
- }
- if (c != NULL) {
- pstm_zero (c);
- }
- return PSTM_OKAY;
- }
- if ((res = pstm_init_size(pool, &t1, a->alloc)) != PSTM_OKAY) {
- return res;
- }
- if ((res = pstm_init_size(pool, &t2, 3)) != PSTM_OKAY) {
- goto LBL_T1;
- }
- if ((res = pstm_init_copy(pool, &x, a, 0)) != PSTM_OKAY) {
- goto LBL_T2;
- }
- if ((res = pstm_init_size(pool, &y, b->used * 3)) != PSTM_OKAY) {
- goto LBL_X;
- }
- if ((res = pstm_copy(b, &y)) != PSTM_OKAY) {
- goto LBL_Y;
- }
-
- neg = (a->sign == b->sign) ? PSTM_ZPOS : PSTM_NEG;
- x.sign = y.sign = PSTM_ZPOS;
-
- norm = pstm_count_bits(&y) % DIGIT_BIT;
- if (norm < (int32)(DIGIT_BIT-1)) {
- norm = (DIGIT_BIT-1) - norm;
- if ((res = pstm_mul_2d(&x, norm, &x)) != PSTM_OKAY) {
- goto LBL_Y;
- }
- if ((res = pstm_mul_2d(&y, norm, &y)) != PSTM_OKAY) {
- goto LBL_Y;
- }
- } else {
- norm = 0;
- }
-
- n = x.used - 1;
- t = y.used - 1;
- if ((res = pstm_init_size(pool, &q, n - t + 1)) != PSTM_OKAY) {
- goto LBL_Y;
- }
- q.used = n - t + 1;
-
- if ((res = pstm_lshd(&y, n - t)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- while (pstm_cmp (&x, &y) != PSTM_LT) {
- ++(q.dp[n - t]);
- if ((res = pstm_sub(&x, &y, &x)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- }
-
- pstm_rshd (&y, n - t);
-
- for (i = n; i >= (t + 1); i--) {
- if (i > x.used) {
- continue;
- }
-
- if (x.dp[i] == y.dp[t]) {
- q.dp[i - t - 1] = (pstm_digit)((((pstm_word)1) << DIGIT_BIT) - 1);
- } else {
- pstm_word tmp;
- tmp = ((pstm_word) x.dp[i]) << ((pstm_word) DIGIT_BIT);
- tmp |= ((pstm_word) x.dp[i - 1]);
- #if defined(USE_MATRIX_DIV64) && defined(PSTM_32BIT)
- psDiv64(&tmp, y.dp[t]);
- #elif defined(USE_MATRIX_DIV128) && defined(PSTM_64BIT)
- psDiv128(&tmp, y.dp[t]);
- #else
- tmp /= ((pstm_word) y.dp[t]);
- #endif
- q.dp[i - t - 1] = (pstm_digit) (tmp);
- }
-
- q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
- do {
- q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
-
- pstm_zero (&t1);
- t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
- t1.dp[1] = y.dp[t];
- t1.used = 2;
- if ((res = pstm_mul_d (&t1, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
- goto LBL_Q;
- }
-
- t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
- t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
- t2.dp[2] = x.dp[i];
- t2.used = 3;
- } while (pstm_cmp_mag(&t1, &t2) == PSTM_GT);
-
- if ((res = pstm_mul_d(&y, q.dp[i - t - 1], &t1)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- if ((res = pstm_lshd(&t1, i - t - 1)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- if ((res = pstm_sub(&x, &t1, &x)) != PSTM_OKAY) {
- goto LBL_Q;
- }
-
- if (x.sign == PSTM_NEG) {
- if ((res = pstm_copy(&y, &t1)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- if ((res = pstm_lshd (&t1, i - t - 1)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- if ((res = pstm_add (&x, &t1, &x)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
- }
- }
-
- x.sign = x.used == 0 ? PSTM_ZPOS : a->sign;
- if (c != NULL) {
- pstm_clamp (&q);
- if (pstm_copy (&q, c) != PSTM_OKAY) {
- res = PS_MEM_FAIL;
- goto LBL_Q;
- }
- c->sign = neg;
- }
- if (d != NULL) {
- if ((res = pstm_div_2d (pool, &x, norm, &x, NULL)) != PSTM_OKAY) {
- goto LBL_Q;
- }
- for (i = b->used; i < x.used; i++) {
- x.dp[i] = 0;
- }
- pstm_clamp(&x);
- if (pstm_copy (&x, d) != PSTM_OKAY) {
- res = PS_MEM_FAIL;
- goto LBL_Q;
- }
- }
- res = PSTM_OKAY;
- LBL_Q:pstm_clear (&q);
- LBL_Y:pstm_clear (&y);
- LBL_X:pstm_clear (&x);
- LBL_T2:pstm_clear (&t2);
- LBL_T1:pstm_clear (&t1);
- return res;
- }
- void pstm_exch(pstm_int * a, pstm_int * b)
- {
- pstm_int t;
- t = *a;
- *a = *b;
- *b = t;
- }
- int32 pstm_mod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
- {
- pstm_int t;
- int32 err;
- if ((err = pstm_init_size(pool, &t, b->alloc)) != PSTM_OKAY) {
- return err;
- }
- if ((err = pstm_div(pool, a, b, NULL, &t)) != PSTM_OKAY) {
- pstm_clear (&t);
- return err;
- }
- if (t.sign != b->sign) {
- err = pstm_add(&t, b, c);
- } else {
- pstm_exch (&t, c);
- }
- pstm_clear (&t);
- return err;
- }
- int32 pstm_mulmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c,
- pstm_int *d)
- {
- int32 res;
- int size;
- pstm_int tmp;
- size = a->used + b->used + 1;
- if ((a == d) && (size < a->alloc)) {
- size = a->alloc;
- }
- if ((res = pstm_init_size(pool, &tmp, size)) != PSTM_OKAY) {
- return res;
- }
- if ((res = pstm_mul_comba(pool, a, b, &tmp, NULL, 0)) != PSTM_OKAY) {
- pstm_clear(&tmp);
- return res;
- }
- res = pstm_mod(pool, &tmp, c, d);
- pstm_clear(&tmp);
- return res;
- }
- int32 pstm_exptmod(psPool_t *pool, pstm_int *G, pstm_int *X, pstm_int *P,
- pstm_int *Y)
- {
- pstm_int M[32], res;
- pstm_digit buf, mp;
- pstm_digit *paD;
- int32 err, bitbuf;
- int bitcpy, bitcnt, mode, digidx, x, y, winsize;
- uint32 paDlen;
-
- x = pstm_count_bits(X);
- if (x < 50) {
- winsize = 2;
- } else {
- winsize = PS_EXPTMOD_WINSIZE;
- }
-
- if ((err = pstm_montgomery_setup (P, &mp)) != PSTM_OKAY) {
- return err;
- }
-
- if ((err = pstm_init_size(pool, &res, (P->used * 2) + 1)) != PSTM_OKAY) {
- return err;
- }
-
- if ((err = pstm_montgomery_calc_normalization (&res, P)) != PSTM_OKAY) {
- goto LBL_RES;
- }
- if ((err = pstm_init_size(pool, &M[1], res.used)) != PSTM_OKAY) {
- goto LBL_RES;
- }
-
- if (pstm_cmp_mag(P, G) != PSTM_GT) {
-
- if ((err = pstm_mod(pool, G, P, &M[1])) != PSTM_OKAY) {
- goto LBL_M;
- }
- } else {
- if ((err = pstm_copy(G, &M[1])) != PSTM_OKAY) {
- goto LBL_M;
- }
- }
- if ((err = pstm_mulmod (pool, &M[1], &res, P, &M[1])) != PSTM_OKAY) {
- goto LBL_M;
- }
- paDlen = ((M[1].used + 3) * 2) * sizeof(pstm_digit);
- paD = xzalloc(paDlen);
- if (pstm_init_copy(pool, &M[1 << (winsize - 1)], &M[1], 1) != PSTM_OKAY) {
- err = PS_MEM_FAIL;
- goto LBL_PAD;
- }
- for (x = 0; x < (winsize - 1); x++) {
- if ((err = pstm_sqr_comba (pool, &M[1 << (winsize - 1)],
- &M[1 << (winsize - 1)], paD, paDlen)) != PSTM_OKAY) {
- goto LBL_PAD;
- }
- if ((err = pstm_montgomery_reduce(pool, &M[1 << (winsize - 1)], P, mp,
- paD, paDlen)) != PSTM_OKAY) {
- goto LBL_PAD;
- }
- }
- for (x = (1<<(winsize-1)) + 1; x < (1 << winsize); x++) {
- if ((err = pstm_init_size(pool, &M[x], M[1<<(winsize-1)].alloc + 1))
- != PSTM_OKAY) {
- for (y = 1<<(winsize-1); y < x; y++) {
- pstm_clear(&M[y]);
- }
- goto LBL_PAD;
- }
- }
-
- for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
- if ((err = pstm_mul_comba(pool, &M[x - 1], &M[1], &M[x], paD, paDlen))
- != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &M[x], P, mp, paD, paDlen)) !=
- PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- }
-
- mode = 0;
- bitcnt = 1;
- buf = 0;
- digidx = X->used - 1;
- bitcpy = 0;
- bitbuf = 0;
- for (;;) {
-
- if (--bitcnt == 0) {
-
- if (digidx == -1) {
- break;
- }
-
- buf = X->dp[digidx--];
- bitcnt = (int32)DIGIT_BIT;
- }
-
- y = (pstm_digit)(buf >> (DIGIT_BIT - 1)) & 1;
- buf <<= (pstm_digit)1;
- if (mode == 0 && y == 0) {
- continue;
- }
-
- if (mode == 1 && y == 0) {
- if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
- PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
- != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- continue;
- }
-
- bitbuf |= (y << (winsize - ++bitcpy));
- mode = 2;
- if (bitcpy == winsize) {
-
- for (x = 0; x < winsize; x++) {
- if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
- PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
- paDlen)) != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- }
-
- if ((err = pstm_mul_comba(pool, &res, &M[bitbuf], &res, paD,
- paDlen)) != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
- != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
-
- bitcpy = 0;
- bitbuf = 0;
- mode = 1;
- }
- }
-
- if (mode == 2 && bitcpy > 0) {
-
- for (x = 0; x < bitcpy; x++) {
- if ((err = pstm_sqr_comba(pool, &res, &res, paD, paDlen)) !=
- PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen))
- != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
-
- bitbuf <<= 1;
- if ((bitbuf & (1 << winsize)) != 0) {
-
- if ((err = pstm_mul_comba(pool, &res, &M[1], &res, paD, paDlen))
- != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD,
- paDlen)) != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- }
- }
- }
- if ((err = pstm_montgomery_reduce(pool, &res, P, mp, paD, paDlen)) !=
- PSTM_OKAY) {
- goto LBL_MARRAY;
- }
-
- if ((err = pstm_copy (&res, Y)) != PSTM_OKAY) {
- goto LBL_MARRAY;
- }
- err = PSTM_OKAY;
- LBL_MARRAY:
- for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
- pstm_clear(&M[x]);
- }
- LBL_PAD:psFree(paD, pool);
- LBL_M: pstm_clear(&M[1]);
- LBL_RES:pstm_clear(&res);
- return err;
- }
- int32 pstm_add(pstm_int *a, pstm_int *b, pstm_int *c)
- {
- int32 res;
- int sa, sb;
-
- sa = a->sign;
- sb = b->sign;
-
- if (sa == sb) {
-
- c->sign = sa;
- if ((res = s_pstm_add (a, b, c)) != PSTM_OKAY) {
- return res;
- }
- } else {
- if (pstm_cmp_mag (a, b) == PSTM_LT) {
- c->sign = sb;
- if ((res = s_pstm_sub (b, a, c)) != PSTM_OKAY) {
- return res;
- }
- } else {
- c->sign = sa;
- if ((res = s_pstm_sub (a, b, c)) != PSTM_OKAY) {
- return res;
- }
- }
- }
- return PS_SUCCESS;
- }
- static void pstm_reverse (unsigned char *s, int len)
- {
- int32 ix, iy;
- unsigned char t;
- ix = 0;
- iy = len - 1;
- while (ix < iy) {
- t = s[ix];
- s[ix] = s[iy];
- s[iy] = t;
- ++ix;
- --iy;
- }
- }
- int32 pstm_to_unsigned_bin_nr(psPool_t *pool, pstm_int *a, unsigned char *b)
- {
- int32 res;
- int x;
- pstm_int t = { 0 };
- if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
- return res;
- }
- x = 0;
- while (pstm_iszero (&t) == 0) {
- b[x++] = (unsigned char) (t.dp[0] & 255);
- if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
- pstm_clear(&t);
- return res;
- }
- }
- pstm_clear(&t);
- return PS_SUCCESS;
- }
- int32 pstm_to_unsigned_bin(psPool_t *pool, pstm_int *a, unsigned char *b)
- {
- int32 res;
- int x;
- pstm_int t = { 0 };
- if ((res = pstm_init_copy(pool, &t, a, 0)) != PSTM_OKAY) {
- return res;
- }
- x = 0;
- while (pstm_iszero (&t) == 0) {
- b[x++] = (unsigned char) (t.dp[0] & 255);
- if ((res = pstm_div_2d (pool, &t, 8, &t, NULL)) != PSTM_OKAY) {
- pstm_clear(&t);
- return res;
- }
- }
- pstm_reverse (b, x);
- pstm_clear(&t);
- return PS_SUCCESS;
- }
- int32 pstm_cmp_d(pstm_int *a, pstm_digit b)
- {
-
- if ((b && a->used == 0) || a->sign == PSTM_NEG) {
- return PSTM_LT;
- }
-
- if (a->used > 1) {
- return PSTM_GT;
- }
-
- if (a->dp[0] > b) {
- return PSTM_GT;
- } else if (a->dp[0] < b) {
- return PSTM_LT;
- } else {
- return PSTM_EQ;
- }
- }
- #define pstm_invmod_slow(pool, a, b, c) \
- pstm_invmod_slow( a, b, c)
- static int32 pstm_invmod_slow(psPool_t *pool, pstm_int * a, pstm_int * b,
- pstm_int * c)
- {
- pstm_int x, y, u, v, A, B, C, D;
- int32 res;
-
- if (b->sign == PSTM_NEG || pstm_iszero(b) == 1) {
- return PS_LIMIT_FAIL;
- }
-
- if (pstm_init_size(pool, &x, b->used) != PSTM_OKAY) {
- return PS_MEM_FAIL;
- }
-
- if ((res = pstm_mod(pool, a, b, &x)) != PSTM_OKAY) {
- goto LBL_X;
- }
- if (pstm_init_copy(pool, &y, b, 0) != PSTM_OKAY) {
- goto LBL_X;
- }
-
- if (pstm_iseven (&x) == 1 && pstm_iseven (&y) == 1) {
- res = PS_FAILURE;
- goto LBL_Y;
- }
-
- if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
- goto LBL_Y;
- }
- if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
- goto LBL_U;
- }
- if ((res = pstm_init_size(pool, &A, sizeof(pstm_digit))) != PSTM_OKAY) {
- goto LBL_V;
- }
- if ((res = pstm_init_size(pool, &D, sizeof(pstm_digit))) != PSTM_OKAY) {
- goto LBL_A;
- }
- pstm_set (&A, 1);
- pstm_set (&D, 1);
- if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
- goto LBL_D;
- }
- if ((res = pstm_init(pool, &C)) != PSTM_OKAY) {
- goto LBL_B;
- }
- top:
-
- while (pstm_iseven (&u) == 1) {
-
- if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
- goto LBL_C;
- }
-
- if (pstm_isodd (&A) == 1 || pstm_isodd (&B) == 1) {
-
- if ((res = pstm_add (&A, &y, &A)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- if ((res = pstm_div_2 (&A, &A)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- while (pstm_iseven (&v) == 1) {
-
- if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
- goto LBL_C;
- }
-
- if (pstm_isodd (&C) == 1 || pstm_isodd (&D) == 1) {
-
- if ((res = pstm_add (&C, &y, &C)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- if ((res = pstm_div_2 (&C, &C)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- if (pstm_cmp (&u, &v) != PSTM_LT) {
-
- if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&A, &C, &A)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
- goto LBL_C;
- }
- } else {
-
- if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&C, &A, &C)) != PSTM_OKAY) {
- goto LBL_C;
- }
- if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- if (pstm_iszero (&u) == 0)
- goto top;
-
-
- if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
- res = PS_FAILURE;
- goto LBL_C;
- }
-
- while (pstm_cmp_d(&C, 0) == PSTM_LT) {
- if ((res = pstm_add(&C, b, &C)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- while (pstm_cmp_mag(&C, b) != PSTM_LT) {
- if ((res = pstm_sub(&C, b, &C)) != PSTM_OKAY) {
- goto LBL_C;
- }
- }
-
- if ((res = pstm_copy(&C, c)) != PSTM_OKAY) {
- goto LBL_C;
- }
- res = PSTM_OKAY;
- LBL_C: pstm_clear(&C);
- LBL_D: pstm_clear(&D);
- LBL_B: pstm_clear(&B);
- LBL_A: pstm_clear(&A);
- LBL_V: pstm_clear(&v);
- LBL_U: pstm_clear(&u);
- LBL_Y: pstm_clear(&y);
- LBL_X: pstm_clear(&x);
- return res;
- }
- int32 pstm_invmod(psPool_t *pool, pstm_int *a, pstm_int *b, pstm_int *c)
- {
- pstm_int x, y, u, v, B, D;
- int32 res;
- int neg, sanity;
-
- if (pstm_iseven (b) == 1) {
- return pstm_invmod_slow(pool, a,b,c);
- }
-
- if ((res = pstm_init_copy(pool, &x, b, 0)) != PSTM_OKAY) {
- return res;
- }
- if ((res = pstm_init_size(pool, &y, a->alloc)) != PSTM_OKAY) {
- goto LBL_X;
- }
-
- pstm_abs(a, &y);
-
- if ((res = pstm_init_copy(pool, &u, &x, 0)) != PSTM_OKAY) {
- goto LBL_Y;
- }
- if ((res = pstm_init_copy(pool, &v, &y, 0)) != PSTM_OKAY) {
- goto LBL_U;
- }
- if ((res = pstm_init(pool, &B)) != PSTM_OKAY) {
- goto LBL_V;
- }
- if ((res = pstm_init(pool, &D)) != PSTM_OKAY) {
- goto LBL_B;
- }
- pstm_set (&D, 1);
- sanity = 0;
- top:
-
- while (pstm_iseven (&u) == 1) {
-
- if ((res = pstm_div_2 (&u, &u)) != PSTM_OKAY) {
- goto LBL_D;
- }
-
- if (pstm_isodd (&B) == 1) {
- if ((res = pstm_sub (&B, &x, &B)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
-
- if ((res = pstm_div_2 (&B, &B)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
-
- while (pstm_iseven (&v) == 1) {
-
- if ((res = pstm_div_2 (&v, &v)) != PSTM_OKAY) {
- goto LBL_D;
- }
-
- if (pstm_isodd (&D) == 1) {
-
- if ((res = pstm_sub (&D, &x, &D)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
-
- if ((res = pstm_div_2 (&D, &D)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
-
- if (pstm_cmp (&u, &v) != PSTM_LT) {
-
- if ((res = pstm_sub (&u, &v, &u)) != PSTM_OKAY) {
- goto LBL_D;
- }
- if ((res = pstm_sub (&B, &D, &B)) != PSTM_OKAY) {
- goto LBL_D;
- }
- } else {
-
- if ((res = pstm_sub (&v, &u, &v)) != PSTM_OKAY) {
- goto LBL_D;
- }
- if ((res = pstm_sub (&D, &B, &D)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
-
- if (sanity++ > 1000) {
- res = PS_LIMIT_FAIL;
- goto LBL_D;
- }
- if (pstm_iszero (&u) == 0) {
- goto top;
- }
-
-
- if (pstm_cmp_d (&v, 1) != PSTM_EQ) {
- res = PS_FAILURE;
- goto LBL_D;
- }
-
- neg = a->sign;
- while (D.sign == PSTM_NEG) {
- if ((res = pstm_add (&D, b, &D)) != PSTM_OKAY) {
- goto LBL_D;
- }
- }
- if ((res = pstm_copy (&D, c)) != PSTM_OKAY) {
- goto LBL_D;
- }
- c->sign = neg;
- res = PSTM_OKAY;
- LBL_D: pstm_clear(&D);
- LBL_B: pstm_clear(&B);
- LBL_V: pstm_clear(&v);
- LBL_U: pstm_clear(&u);
- LBL_Y: pstm_clear(&y);
- LBL_X: pstm_clear(&x);
- return res;
- }
- #endif
|