1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654 |
- #include "ptwist.h"
- #include <stdint.h>
- #include <string.h>
- #if defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 1))
-
- typedef __uint128_t uint128_t;
- #else
- #error "Need GCC 3.1 or later to define type uint128_t"
- #endif
- typedef uint8_t u8;
- typedef uint64_t fslice;
- typedef fslice coord[3];
- typedef coord point[3];
- #include <stdio.h>
- #include <stdlib.h>
- typedef u8 felem_bytearray[21];
- static const felem_bytearray ptwist168_curve_params[5] = {
- {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
- 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
- 0xFF},
- {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
- 0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFE,
- 0xFC},
- {0x4E,0x35,0x5E,0x95,0xCA,0xFE,0xDD,0x48,0x6E,0xBC,
- 0x69,0xBA,0xD3,0x16,0x46,0xD3,0x20,0xE0,0x1D,0xC7,
- 0xD6},
- {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
- 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
- 0x02},
- {0xEA,0x67,0x47,0xB7,0x5A,0xF8,0xC7,0xF9,0x3C,0x1F,
- 0x5E,0x6D,0x32,0x0F,0x88,0xB9,0xBE,0x15,0x66,0xD2,
- 0xF2}
- };
- static void bin21_to_felem(fslice out[3], const u8 in[21])
- {
- out[0] = *((const uint64_t *)(in)) & 0x00ffffffffffffff;
- out[1] = (*((const uint64_t *)(in+7))) & 0x00ffffffffffffff;
- out[2] = (*((const uint64_t *)(in+14))) & 0x00ffffffffffffff;
- }
- static void felem_to_bin21(u8 out[21], const fslice in[3])
- {
- unsigned i;
- for (i = 0; i < 7; ++i)
- {
- out[i] = in[0]>>(8*i);
- out[i+7] = in[1]>>(8*i);
- out[i+14] = in[2]>>(8*i);
- }
- }
- #if 0
- static void flip_endian(u8 *out, const u8 *in, unsigned len)
- {
- unsigned i;
- for (i = 0; i < len; ++i)
- out[i] = in[len-1-i];
- }
- #endif
- static void felem_sum64(fslice out[3], const fslice in[3])
- {
- out[0] += in[0];
- out[1] += in[1];
- out[2] += in[2];
- }
- static void felem_diff64(fslice out[3], const fslice in[3])
- {
-
-
- static const uint64_t a = (((uint64_t) 3) << 56) - ((uint64_t) 3);
- static const uint64_t b = (((uint64_t) 3) << 56) - ((uint64_t) 771);
-
-
- out[0] += b;
- out[1] += a;
- out[2] += a;
- out[0] -= in[0];
- out[1] -= in[1];
- out[2] -= in[2];
- }
- static void felem_diff128(uint128_t out[5], const uint128_t in[5])
- {
-
- static const uint128_t a = (((uint128_t)3) << 118) - ((uint128_t) 192);
- static const uint128_t b = (((uint128_t)3) << 118) - ((uint128_t) 49536);
- static const uint128_t c = (((uint128_t)3) << 118);
- static const uint128_t d = (((uint128_t)3) << 118) - ((uint128_t) 12681408);;
-
- out[0] += d;
- out[1] += c;
- out[2] += b;
- out[3] += a;
- out[4] += a;
- out[0] -= in[0];
- out[1] -= in[1];
- out[2] -= in[2];
- out[3] -= in[3];
- out[4] -= in[4];
- }
- static void felem_diff_128_64(uint128_t out[5], const fslice in[3])
- {
-
- static const uint128_t a = (((uint128_t) 3) << 62) - ((uint128_t) 192);
- static const uint128_t b = (((uint128_t) 3) << 62) - ((uint128_t) 49344);
-
- out[0] += b;
- out[1] += a;
- out[2] += a;
- out[0] -= in[0];
- out[1] -= in[1];
- out[2] -= in[2];
- }
- static void felem_scalar64(fslice out[3], const fslice scalar)
- {
- out[0] *= scalar;
- out[1] *= scalar;
- out[2] *= scalar;
- }
- static void felem_scalar128(uint128_t out[5], const uint128_t scalar)
- {
- out[0] *= scalar;
- out[1] *= scalar;
- out[2] *= scalar;
- out[3] *= scalar;
- out[4] *= scalar;
- }
- static void felem_square(uint128_t out[5], const fslice in[3])
- {
- out[0] = ((uint128_t) in[0]) * in[0];
- out[1] = ((uint128_t) in[0]) * in[1] * 2;
- out[2] = ((uint128_t) in[0]) * in[2] * 2 + ((uint128_t) in[1]) * in[1];
- out[3] = ((uint128_t) in[1]) * in[2] * 2;
- out[4] = ((uint128_t) in[2]) * in[2];
- }
- static void felem_mul(uint128_t out[5], const fslice in1[3], const fslice in2[3])
- {
- out[0] = ((uint128_t) in1[0]) * in2[0];
- out[1] = ((uint128_t) in1[0]) * in2[1] + ((uint128_t) in1[1]) * in2[0];
- out[2] = ((uint128_t) in1[0]) * in2[2] + ((uint128_t) in1[1]) * in2[1] +
- ((uint128_t) in1[2]) * in2[0];
- out[3] = ((uint128_t) in1[1]) * in2[2] +
- ((uint128_t) in1[2]) * in2[1];
- out[4] = ((uint128_t) in1[2]) * in2[2];
- }
- #define M257(x) (((x)<<8)+(x))
- static void felem_reduce(fslice out[3], const uint128_t in[5])
- {
- static const uint128_t two56m1 = (((uint128_t) 1)<<56) -
- ((uint128_t)1);
- uint128_t output[3];
- output[0] = in[0];
- output[1] = in[1];
- output[2] = in[2];
-
- output[2] += M257(in[4] >> 56);
- output[1] += M257(in[4] & two56m1);
- output[1] += M257(in[3] >> 56);
- output[0] += M257(in[3] & two56m1);
-
- output[0] += M257(output[2] >> 56);
- output[2] &= two56m1;
-
- output[1] += output[0] >> 56;
- output[0] &= two56m1;
- output[2] += output[1] >> 56;
- output[1] &= two56m1;
-
- output[0] += M257(output[2] >> 56);
- output[2] &= two56m1;
-
- output[1] += output[0] >> 56;
- out[0] = output[0] & two56m1;
- out[2] = output[2] + (output[1] >> 56);
- out[1] = output[1] & two56m1;
- }
- static void felem_contract(fslice out[3], const fslice in[3])
- {
- static const uint64_t two56m1 = (((uint64_t) 1)<<56) -
- ((uint64_t)1);
- static const uint64_t two56m257 = (((uint64_t) 1)<<56) -
- ((uint64_t)257);
- uint64_t a;
-
-
-
- out[0] = in[0] + M257(in[2] >> 56);
- out[2] = in[2] & two56m1;
-
- out[1] = in[1] + (out[0] >> 56);
- out[0] &= two56m1;
- out[2] += out[1] >> 56;
- out[1] &= two56m1;
-
- a = ((out[2] == two56m1) & (out[1] == two56m1) & (out[0] >= two56m257));
- out[2] -= two56m1*a;
- out[1] -= two56m1*a;
- out[0] -= two56m257*a;
- }
- static void felem_neg(fslice out[3], const fslice in[3])
- {
-
-
- static const uint64_t a = (((uint64_t) 3) << 56) - ((uint64_t) 3);
- static const uint64_t b = (((uint64_t) 3) << 56) - ((uint64_t) 771);
- static const uint64_t two56m1 = (((uint64_t) 1) << 56) - ((uint64_t) 1);
- fslice tmp[3];
-
-
- tmp[0] = b - in[0];
- tmp[1] = a - in[1];
- tmp[2] = a - in[2];
-
- tmp[1] += tmp[0] >> 56;
- tmp[0] &= two56m1;
- tmp[2] += tmp[1] >> 56;
- tmp[1] &= two56m1;
- felem_contract(out, tmp);
- }
- static fslice felem_is_zero(const fslice in[3])
- {
- fslice zero, two168m8m1, two169m9m2;
- static const uint64_t two56m1 = (((uint64_t) 1)<<56) -
- ((uint64_t)1);
- static const uint64_t two56m257 = (((uint64_t) 1)<<56) -
- ((uint64_t)257);
- static const uint64_t two57m1 = (((uint64_t) 1)<<57) -
- ((uint64_t)1);
- static const uint64_t two56m514 = (((uint64_t) 1)<<56) -
- ((uint64_t)514);
- zero = (in[0] == 0) & (in[1] == 0) & (in[2] == 0);
- two168m8m1 = (in[2] == two56m1) & (in[1] == two56m1) &
- (in[0] == two56m257);
- two169m9m2 = (in[2] == two57m1) & (in[1] == two56m1) &
- (in[0] == two56m514);
- return (zero | two168m8m1 | two169m9m2);
- }
- static void felem_inv(fslice out[3], const fslice in[3])
- {
- fslice ftmp[3], ftmp2[3], ftmp3[3], ftmp4[3];
- uint128_t tmp[5];
- unsigned i;
- felem_square(tmp, in); felem_reduce(ftmp, tmp);
- felem_mul(tmp, in, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 5; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp, ftmp2); felem_reduce(ftmp3, tmp);
-
- felem_square(tmp, ftmp3); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 11; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp3); felem_reduce(ftmp3, tmp);
-
- felem_square(tmp, ftmp3); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 23; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp3); felem_reduce(ftmp4, tmp);
-
- felem_square(tmp, ftmp4); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 23; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp3); felem_reduce(ftmp4, tmp);
-
- felem_square(tmp, ftmp4); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 5; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, in, ftmp2); felem_reduce(ftmp4, tmp);
-
- felem_square(tmp, ftmp4); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 78; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp4, ftmp2); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, in, ftmp2); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 7; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, in, ftmp2); felem_reduce(out, tmp);
-
- }
- static void felem_sqrt(fslice out[3], const fslice in[3])
- {
- fslice ftmp[3], ftmp2[3];
- uint128_t tmp[5];
- unsigned i;
- felem_square(tmp, in); felem_reduce(ftmp, tmp);
- felem_mul(tmp, in, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp2, tmp);
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- felem_mul(tmp, ftmp2, in); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 4; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp, ftmp2); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 9; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 19; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 39; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp);
-
- felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 79; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_mul(tmp, ftmp, ftmp2); felem_reduce(ftmp2, tmp);
- for (i = 0; i < 5; ++i)
- {
- felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp);
- }
- felem_square(tmp, ftmp2); felem_reduce(out, tmp);
-
- }
- static void
- copy_conditional(fslice *out, const fslice *in, unsigned len, fslice icopy)
- {
- unsigned i;
-
- const fslice copy = -icopy;
- for (i = 0; i < len; ++i)
- {
- const fslice tmp = copy & (in[i] ^ out[i]);
- out[i] ^= tmp;
- }
- }
- static void select_conditional(fslice *out, const fslice *in1, const fslice *in2,
- unsigned len, fslice isel)
- {
- unsigned i;
-
- const fslice sel = -isel;
- for (i = 0; i < len; ++i)
- {
- const fslice tmp = sel & (in1[i] ^ in2[i]);
- out[i] = in1[i] ^ tmp;
- }
- }
- static void
- point_double(fslice x_out[3], fslice y_out[3], fslice z_out[3],
- const fslice x_in[3], const fslice y_in[3], const fslice z_in[3])
- {
- uint128_t tmp[5], tmp2[5];
- fslice delta[3];
- fslice gamma[3];
- fslice beta[3];
- fslice alpha[3];
- fslice ftmp[3], ftmp2[3];
- memcpy(ftmp, x_in, 3 * sizeof(fslice));
- memcpy(ftmp2, x_in, 3 * sizeof(fslice));
-
- felem_square(tmp, z_in);
- felem_reduce(delta, tmp);
-
- felem_square(tmp, y_in);
- felem_reduce(gamma, tmp);
-
- felem_mul(tmp, x_in, gamma);
- felem_reduce(beta, tmp);
-
- felem_diff64(ftmp, delta);
-
- felem_sum64(ftmp2, delta);
-
- felem_scalar64(ftmp2, 3);
-
- felem_mul(tmp, ftmp, ftmp2);
-
- felem_reduce(alpha, tmp);
-
- felem_square(tmp, alpha);
-
- memcpy(ftmp, beta, 3 * sizeof(fslice));
- felem_scalar64(ftmp, 8);
-
- felem_diff_128_64(tmp, ftmp);
-
- felem_reduce(x_out, tmp);
-
- felem_sum64(delta, gamma);
-
- memcpy(ftmp, y_in, 3 * sizeof(fslice));
- felem_sum64(ftmp, z_in);
-
- felem_square(tmp, ftmp);
-
- felem_diff_128_64(tmp, delta);
-
- felem_reduce(z_out, tmp);
-
- felem_scalar64(beta, 4);
-
- felem_diff64(beta, x_out);
-
- felem_mul(tmp, alpha, beta);
-
- felem_square(tmp2, gamma);
-
- felem_scalar128(tmp2, 8);
-
- felem_diff128(tmp, tmp2);
-
- felem_reduce(y_out, tmp);
- }
- static void point_add(fslice x3[3], fslice y3[3], fslice z3[3],
- const fslice x1[3], const fslice y1[3], const fslice z1[3],
- const fslice x2[3], const fslice y2[3], const fslice z2[3])
- {
- fslice ftmp[3], ftmp2[3], ftmp3[3], ftmp4[3], ftmp5[3];
- fslice xout[3], yout[3], zout[3];
- uint128_t tmp[5], tmp2[5];
- fslice z1_is_zero, z2_is_zero, x_equal, y_equal;
-
- felem_square(tmp, z1);
- felem_reduce(ftmp, tmp);
-
- felem_square(tmp, z2);
- felem_reduce(ftmp2, tmp);
-
- felem_mul(tmp, ftmp, z1);
- felem_reduce(ftmp3, tmp);
-
- felem_mul(tmp, ftmp2, z2);
- felem_reduce(ftmp4, tmp);
-
- felem_mul(tmp, ftmp3, y2);
-
-
- felem_mul(tmp2, ftmp4, y1);
- felem_reduce(ftmp4, tmp2);
-
- felem_diff_128_64(tmp, ftmp4);
-
- felem_reduce(ftmp3, tmp);
-
- felem_mul(tmp, ftmp, x2);
-
-
- felem_mul(tmp2, ftmp2, x1);
- felem_reduce(ftmp2, tmp2);
-
- felem_diff128(tmp, tmp2);
-
- felem_reduce(ftmp, tmp);
-
- x_equal = felem_is_zero(ftmp);
- y_equal = felem_is_zero(ftmp3);
- z1_is_zero = felem_is_zero(z1);
- z2_is_zero = felem_is_zero(z2);
-
- if (x_equal && y_equal && !z1_is_zero && !z2_is_zero)
- {
- point_double(x3, y3, z3, x1, y1, z1);
- return;
- }
-
- felem_mul(tmp, z1, z2);
- felem_reduce(ftmp5, tmp);
-
- felem_mul(tmp, ftmp, ftmp5);
- felem_reduce(zout, tmp);
-
- memcpy(ftmp5, ftmp, 3 * sizeof(fslice));
- felem_square(tmp, ftmp);
- felem_reduce(ftmp, tmp);
-
- felem_mul(tmp, ftmp, ftmp5);
- felem_reduce(ftmp5, tmp);
-
- felem_mul(tmp, ftmp2, ftmp);
- felem_reduce(ftmp2, tmp);
-
- felem_mul(tmp, ftmp4, ftmp5);
-
-
- felem_square(tmp2, ftmp3);
-
-
- felem_diff_128_64(tmp2, ftmp5);
-
-
- memcpy(ftmp5, ftmp2, 3 * sizeof(fslice));
- felem_scalar64(ftmp5, 2);
-
-
- felem_diff_128_64(tmp2, ftmp5);
-
- felem_reduce(xout, tmp2);
-
- felem_diff64(ftmp2, xout);
-
-
- felem_mul(tmp2, ftmp3, ftmp2);
-
-
- felem_diff128(tmp2, tmp);
-
- felem_reduce(yout, tmp2);
-
-
- copy_conditional(xout, x2, 3, z1_is_zero);
- select_conditional(x3, xout, x1, 3, z2_is_zero);
- copy_conditional(yout, y2, 3, z1_is_zero);
- select_conditional(y3, yout, y1, 3, z2_is_zero);
- copy_conditional(zout, z2, 3, z1_is_zero);
- select_conditional(z3, zout, z1, 3, z2_is_zero);
- }
- static void affine_x(coord out, point P)
- {
- coord z1, z2, xin;
- uint128_t tmp[7];
- if (felem_is_zero(P[2])) return;
- felem_inv(z2, P[2]);
- felem_square(tmp, z2); felem_reduce(z1, tmp);
- felem_mul(tmp, P[0], z1); felem_reduce(xin, tmp);
- felem_contract(out, xin);
- }
- static void point_mul(point out, point in, const felem_bytearray s)
- {
- int i;
- point tmp;
- point table[16];
- memset(table[0], 0, sizeof(point));
- memmove(table[1], in, sizeof(point));
- for(i=2; i<16; i+=2) {
- point_double(table[i][0], table[i][1], table[i][2],
- table[i/2][0], table[i/2][1], table[i/2][2]);
- point_add(table[i+1][0], table[i+1][1], table[i+1][2],
- table[i][0], table[i][1], table[i][2],
- in[0], in[1], in[2]);
- }
-
- memset(tmp, 0, sizeof(point));
- for(i=0;i<21;i++) {
- u8 oh = s[20-i] >> 4;
- u8 ol = s[20-i] & 0x0f;
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_add(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2],
- table[oh][0], table[oh][1], table[oh][2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_double(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2]);
- point_add(tmp[0], tmp[1], tmp[2], tmp[0], tmp[1], tmp[2],
- table[ol][0], table[ol][1], table[ol][2]);
- }
- memmove(out, tmp, sizeof(point));
- }
- #if 0
- static void select_point(const fslice bits[4], const fslice pre_comp[16][3][4],
- fslice out[12])
- {
- fslice tmp[5][12];
- select_conditional(tmp[0], pre_comp[7][0], pre_comp[15][0], 12, bits[3]);
- select_conditional(tmp[1], pre_comp[3][0], pre_comp[11][0], 12, bits[3]);
- select_conditional(tmp[2], tmp[1], tmp[0], 12, bits[2]);
- select_conditional(tmp[0], pre_comp[5][0], pre_comp[13][0], 12, bits[3]);
- select_conditional(tmp[1], pre_comp[1][0], pre_comp[9][0], 12, bits[3]);
- select_conditional(tmp[3], tmp[1], tmp[0], 12, bits[2]);
- select_conditional(tmp[4], tmp[3], tmp[2], 12, bits[1]);
- select_conditional(tmp[0], pre_comp[6][0], pre_comp[14][0], 12, bits[3]);
- select_conditional(tmp[1], pre_comp[2][0], pre_comp[10][0], 12, bits[3]);
- select_conditional(tmp[2], tmp[1], tmp[0], 12, bits[2]);
- select_conditional(tmp[0], pre_comp[4][0], pre_comp[12][0], 12, bits[3]);
- select_conditional(tmp[1], pre_comp[0][0], pre_comp[8][0], 12, bits[3]);
- select_conditional(tmp[3], tmp[1], tmp[0], 12, bits[2]);
- select_conditional(tmp[1], tmp[3], tmp[2], 12, bits[1]);
- select_conditional(out, tmp[1], tmp[4], 12, bits[0]);
- }
- static void batch_mul(fslice x_out[4], fslice y_out[4], fslice z_out[4],
- const felem_bytearray scalars[], const unsigned num_points, const u8 *g_scalar,
- const fslice pre_comp[][16][3][4], const fslice g_pre_comp[16][3][4])
- {
- unsigned i, j, num;
- unsigned gen_mul = (g_scalar != NULL);
- fslice nq[12], nqt[12], tmp[12];
- fslice bits[4];
- u8 byte;
-
- memset(nq, 0, 12 * sizeof(fslice));
-
- for (i = (num_points ? 28 : 7); i > 0; --i)
- {
- for (j = 0; j < 8; ++j)
- {
-
- point_double(nq, nq+4, nq+8, nq, nq+4, nq+8);
-
- if ((gen_mul) && (i <= 7))
- {
- bits[3] = (g_scalar[i+20] >> (7-j)) & 1;
- bits[2] = (g_scalar[i+13] >> (7-j)) & 1;
- bits[1] = (g_scalar[i+6] >> (7-j)) & 1;
- bits[0] = (g_scalar[i-1] >> (7-j)) & 1;
-
- select_point(bits, g_pre_comp, tmp);
- memcpy(nqt, nq, 12 * sizeof(fslice));
- point_add(nq, nq+4, nq+8, nqt, nqt+4, nqt+8,
- tmp, tmp+4, tmp+8);
- }
-
- if (j % 4 == 3)
- {
-
- for (num = 0; num < num_points; ++num)
- {
- byte = scalars[num][i-1];
- bits[3] = (byte >> (10-j)) & 1;
- bits[2] = (byte >> (9-j)) & 1;
- bits[1] = (byte >> (8-j)) & 1;
- bits[0] = (byte >> (7-j)) & 1;
-
- select_point(bits,
- pre_comp[num], tmp);
- memcpy(nqt, nq, 12 * sizeof(fslice));
- point_add(nq, nq+4, nq+8, nqt, nqt+4,
- nqt+8, tmp, tmp+4, tmp+8);
- }
- }
- }
- }
- memcpy(x_out, nq, 4 * sizeof(fslice));
- memcpy(y_out, nq+4, 4 * sizeof(fslice));
- memcpy(z_out, nq+8, 4 * sizeof(fslice));
- }
- static NISTP224_PRE_COMP *nistp224_pre_comp_new()
- {
- NISTP224_PRE_COMP *ret = NULL;
- ret = (NISTP224_PRE_COMP *)OPENSSL_malloc(sizeof(NISTP224_PRE_COMP));
- if (!ret)
- {
- ECerr(EC_F_NISTP224_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
- return ret;
- }
- memset(ret->g_pre_comp, 0, sizeof(ret->g_pre_comp));
- ret->references = 1;
- return ret;
- }
- static void *nistp224_pre_comp_dup(void *src_)
- {
- NISTP224_PRE_COMP *src = src_;
-
- CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
- return src_;
- }
- static void nistp224_pre_comp_free(void *pre_)
- {
- int i;
- NISTP224_PRE_COMP *pre = pre_;
- if (!pre)
- return;
- i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
- if (i > 0)
- return;
- OPENSSL_free(pre);
- }
- static void nistp224_pre_comp_clear_free(void *pre_)
- {
- int i;
- NISTP224_PRE_COMP *pre = pre_;
- if (!pre)
- return;
- i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
- if (i > 0)
- return;
- OPENSSL_cleanse(pre, sizeof *pre);
- OPENSSL_free(pre);
- }
- int ec_GFp_nistp224_group_init(EC_GROUP *group)
- {
- int ret;
- ret = ec_GFp_simple_group_init(group);
- group->a_is_minus3 = 1;
- return ret;
- }
- int ec_GFp_nistp224_group_set_curve(EC_GROUP *group, const BIGNUM *p,
- const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
- {
- int ret = 0;
- BN_CTX *new_ctx = NULL;
- BIGNUM *curve_p, *curve_a, *curve_b;
- if (ctx == NULL)
- if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0;
- BN_CTX_start(ctx);
- if (((curve_p = BN_CTX_get(ctx)) == NULL) ||
- ((curve_a = BN_CTX_get(ctx)) == NULL) ||
- ((curve_b = BN_CTX_get(ctx)) == NULL)) goto err;
- BN_bin2bn(nistp224_curve_params[0], sizeof(felem_bytearray), curve_p);
- BN_bin2bn(nistp224_curve_params[1], sizeof(felem_bytearray), curve_a);
- BN_bin2bn(nistp224_curve_params[2], sizeof(felem_bytearray), curve_b);
- if ((BN_cmp(curve_p, p)) || (BN_cmp(curve_a, a)) ||
- (BN_cmp(curve_b, b)))
- {
- ECerr(EC_F_EC_GFP_NISTP224_GROUP_SET_CURVE,
- EC_R_WRONG_CURVE_PARAMETERS);
- goto err;
- }
- group->field_mod_func = BN_nist_mod_224;
- ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
- err:
- BN_CTX_end(ctx);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- return ret;
- }
- int ec_GFp_nistp224_point_get_affine_coordinates(const EC_GROUP *group,
- const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
- {
- fslice z1[4], z2[4], x_in[4], y_in[4], x_out[4], y_out[4];
- uint128_t tmp[7];
- if (EC_POINT_is_at_infinity(group, point))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
- EC_R_POINT_AT_INFINITY);
- return 0;
- }
- if ((!BN_to_felem(x_in, &point->X)) || (!BN_to_felem(y_in, &point->Y)) ||
- (!BN_to_felem(z1, &point->Z))) return 0;
- felem_inv(z2, z1);
- felem_square(tmp, z2); felem_reduce(z1, tmp);
- felem_mul(tmp, x_in, z1); felem_reduce(x_in, tmp);
- felem_contract(x_out, x_in);
- if (x != NULL)
- {
- if (!felem_to_BN(x, x_out)) {
- ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
- ERR_R_BN_LIB);
- return 0;
- }
- }
- felem_mul(tmp, z1, z2); felem_reduce(z1, tmp);
- felem_mul(tmp, y_in, z1); felem_reduce(y_in, tmp);
- felem_contract(y_out, y_in);
- if (y != NULL)
- {
- if (!felem_to_BN(y, y_out)) {
- ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
- ERR_R_BN_LIB);
- return 0;
- }
- }
- return 1;
- }
- int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
- const BIGNUM *scalar, size_t num, const EC_POINT *points[],
- const BIGNUM *scalars[], BN_CTX *ctx)
- {
- int ret = 0;
- int i, j;
- BN_CTX *new_ctx = NULL;
- BIGNUM *x, *y, *z, *tmp_scalar;
- felem_bytearray g_secret;
- felem_bytearray *secrets = NULL;
- fslice (*pre_comp)[16][3][4] = NULL;
- felem_bytearray tmp;
- unsigned num_bytes;
- int have_pre_comp = 0;
- size_t num_points = num;
- fslice x_in[4], y_in[4], z_in[4], x_out[4], y_out[4], z_out[4];
- NISTP224_PRE_COMP *pre = NULL;
- fslice (*g_pre_comp)[3][4] = NULL;
- EC_POINT *generator = NULL;
- const EC_POINT *p = NULL;
- const BIGNUM *p_scalar = NULL;
- if (ctx == NULL)
- if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0;
- BN_CTX_start(ctx);
- if (((x = BN_CTX_get(ctx)) == NULL) ||
- ((y = BN_CTX_get(ctx)) == NULL) ||
- ((z = BN_CTX_get(ctx)) == NULL) ||
- ((tmp_scalar = BN_CTX_get(ctx)) == NULL))
- goto err;
- if (scalar != NULL)
- {
- pre = EC_EX_DATA_get_data(group->extra_data,
- nistp224_pre_comp_dup, nistp224_pre_comp_free,
- nistp224_pre_comp_clear_free);
- if (pre)
-
- g_pre_comp = pre->g_pre_comp;
- else
-
- g_pre_comp = (fslice (*)[3][4]) gmul;
- generator = EC_POINT_new(group);
- if (generator == NULL)
- goto err;
-
- if (!felem_to_BN(x, g_pre_comp[1][0]) ||
- !felem_to_BN(y, g_pre_comp[1][1]) ||
- !felem_to_BN(z, g_pre_comp[1][2]))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
- goto err;
- }
- if (!EC_POINT_set_Jprojective_coordinates_GFp(group,
- generator, x, y, z, ctx))
- goto err;
- if (0 == EC_POINT_cmp(group, generator, group->generator, ctx))
-
- have_pre_comp = 1;
- else
-
- num_points = num_points + 1;
- }
- secrets = OPENSSL_malloc(num_points * sizeof(felem_bytearray));
- pre_comp = OPENSSL_malloc(num_points * 16 * 3 * 4 * sizeof(fslice));
- if ((num_points) && ((secrets == NULL) || (pre_comp == NULL)))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_MALLOC_FAILURE);
- goto err;
- }
-
- memset(secrets, 0, num_points * sizeof(felem_bytearray));
- memset(pre_comp, 0, num_points * 16 * 3 * 4 * sizeof(fslice));
- for (i = 0; i < num_points; ++i)
- {
- if (i == num)
-
- {
- p = EC_GROUP_get0_generator(group);
- p_scalar = scalar;
- }
- else
-
- {
- p = points[i];
- p_scalar = scalars[i];
- }
- if ((p_scalar != NULL) && (p != NULL))
- {
- num_bytes = BN_num_bytes(p_scalar);
-
- if ((num_bytes > sizeof(felem_bytearray)) || (BN_is_negative(p_scalar)))
- {
-
- if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
- goto err;
- }
- num_bytes = BN_bn2bin(tmp_scalar, tmp);
- }
- else
- BN_bn2bin(p_scalar, tmp);
- flip_endian(secrets[i], tmp, num_bytes);
-
- if ((!BN_to_felem(x_out, &p->X)) ||
- (!BN_to_felem(y_out, &p->Y)) ||
- (!BN_to_felem(z_out, &p->Z))) goto err;
- memcpy(pre_comp[i][1][0], x_out, 4 * sizeof(fslice));
- memcpy(pre_comp[i][1][1], y_out, 4 * sizeof(fslice));
- memcpy(pre_comp[i][1][2], z_out, 4 * sizeof(fslice));
- for (j = 1; j < 8; ++j)
- {
- point_double(pre_comp[i][2*j][0],
- pre_comp[i][2*j][1],
- pre_comp[i][2*j][2],
- pre_comp[i][j][0],
- pre_comp[i][j][1],
- pre_comp[i][j][2]);
- point_add(pre_comp[i][2*j+1][0],
- pre_comp[i][2*j+1][1],
- pre_comp[i][2*j+1][2],
- pre_comp[i][1][0],
- pre_comp[i][1][1],
- pre_comp[i][1][2],
- pre_comp[i][2*j][0],
- pre_comp[i][2*j][1],
- pre_comp[i][2*j][2]);
- }
- }
- }
-
- if ((scalar != NULL) && (have_pre_comp))
- {
- memset(g_secret, 0, sizeof g_secret);
- num_bytes = BN_num_bytes(scalar);
-
- if ((num_bytes > sizeof(felem_bytearray)) || (BN_is_negative(scalar)))
- {
-
- if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
- goto err;
- }
- num_bytes = BN_bn2bin(tmp_scalar, tmp);
- }
- else
- BN_bn2bin(scalar, tmp);
- flip_endian(g_secret, tmp, num_bytes);
-
- batch_mul(x_out, y_out, z_out,
- (const felem_bytearray (*)) secrets, num_points,
- g_secret, (const fslice (*)[16][3][4]) pre_comp,
- (const fslice (*)[3][4]) g_pre_comp);
- }
- else
-
- batch_mul(x_out, y_out, z_out,
- (const felem_bytearray (*)) secrets, num_points,
- NULL, (const fslice (*)[16][3][4]) pre_comp, NULL);
-
- felem_contract(x_in, x_out);
- felem_contract(y_in, y_out);
- felem_contract(z_in, z_out);
- if ((!felem_to_BN(x, x_in)) || (!felem_to_BN(y, y_in)) ||
- (!felem_to_BN(z, z_in)))
- {
- ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
- goto err;
- }
- ret = EC_POINT_set_Jprojective_coordinates_GFp(group, r, x, y, z, ctx);
- err:
- BN_CTX_end(ctx);
- if (generator != NULL)
- EC_POINT_free(generator);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- if (secrets != NULL)
- OPENSSL_free(secrets);
- if (pre_comp != NULL)
- OPENSSL_free(pre_comp);
- return ret;
- }
- int ec_GFp_nistp224_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
- {
- int ret = 0;
- NISTP224_PRE_COMP *pre = NULL;
- int i, j;
- BN_CTX *new_ctx = NULL;
- BIGNUM *x, *y;
- EC_POINT *generator = NULL;
-
- EC_EX_DATA_free_data(&group->extra_data, nistp224_pre_comp_dup,
- nistp224_pre_comp_free, nistp224_pre_comp_clear_free);
- if (ctx == NULL)
- if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0;
- BN_CTX_start(ctx);
- if (((x = BN_CTX_get(ctx)) == NULL) ||
- ((y = BN_CTX_get(ctx)) == NULL))
- goto err;
-
- if (group->generator == NULL) goto err;
- generator = EC_POINT_new(group);
- if (generator == NULL)
- goto err;
- BN_bin2bn(nistp224_curve_params[3], sizeof (felem_bytearray), x);
- BN_bin2bn(nistp224_curve_params[4], sizeof (felem_bytearray), y);
- if (!EC_POINT_set_affine_coordinates_GFp(group, generator, x, y, ctx))
- goto err;
- if ((pre = nistp224_pre_comp_new()) == NULL)
- goto err;
-
- if (0 == EC_POINT_cmp(group, generator, group->generator, ctx))
- {
- memcpy(pre->g_pre_comp, gmul, sizeof(pre->g_pre_comp));
- ret = 1;
- goto err;
- }
- if ((!BN_to_felem(pre->g_pre_comp[1][0], &group->generator->X)) ||
- (!BN_to_felem(pre->g_pre_comp[1][1], &group->generator->Y)) ||
- (!BN_to_felem(pre->g_pre_comp[1][2], &group->generator->Z)))
- goto err;
-
- for (i = 1; i < 5; ++i)
- {
- point_double(pre->g_pre_comp[2*i][0], pre->g_pre_comp[2*i][1],
- pre->g_pre_comp[2*i][2], pre->g_pre_comp[i][0],
- pre->g_pre_comp[i][1], pre->g_pre_comp[i][2]);
- for (j = 0; j < 55; ++j)
- {
- point_double(pre->g_pre_comp[2*i][0],
- pre->g_pre_comp[2*i][1],
- pre->g_pre_comp[2*i][2],
- pre->g_pre_comp[2*i][0],
- pre->g_pre_comp[2*i][1],
- pre->g_pre_comp[2*i][2]);
- }
- }
-
- memset(pre->g_pre_comp[0], 0, sizeof(pre->g_pre_comp[0]));
-
-
- point_add(pre->g_pre_comp[6][0], pre->g_pre_comp[6][1],
- pre->g_pre_comp[6][2], pre->g_pre_comp[4][0],
- pre->g_pre_comp[4][1], pre->g_pre_comp[4][2],
- pre->g_pre_comp[2][0], pre->g_pre_comp[2][1],
- pre->g_pre_comp[2][2]);
-
- point_add(pre->g_pre_comp[10][0], pre->g_pre_comp[10][1],
- pre->g_pre_comp[10][2], pre->g_pre_comp[8][0],
- pre->g_pre_comp[8][1], pre->g_pre_comp[8][2],
- pre->g_pre_comp[2][0], pre->g_pre_comp[2][1],
- pre->g_pre_comp[2][2]);
-
- point_add(pre->g_pre_comp[12][0], pre->g_pre_comp[12][1],
- pre->g_pre_comp[12][2], pre->g_pre_comp[8][0],
- pre->g_pre_comp[8][1], pre->g_pre_comp[8][2],
- pre->g_pre_comp[4][0], pre->g_pre_comp[4][1],
- pre->g_pre_comp[4][2]);
-
- point_add(pre->g_pre_comp[14][0], pre->g_pre_comp[14][1],
- pre->g_pre_comp[14][2], pre->g_pre_comp[12][0],
- pre->g_pre_comp[12][1], pre->g_pre_comp[12][2],
- pre->g_pre_comp[2][0], pre->g_pre_comp[2][1],
- pre->g_pre_comp[2][2]);
- for (i = 1; i < 8; ++i)
- {
-
- point_add(pre->g_pre_comp[2*i+1][0], pre->g_pre_comp[2*i+1][1],
- pre->g_pre_comp[2*i+1][2], pre->g_pre_comp[2*i][0],
- pre->g_pre_comp[2*i][1], pre->g_pre_comp[2*i][2],
- pre->g_pre_comp[1][0], pre->g_pre_comp[1][1],
- pre->g_pre_comp[1][2]);
- }
- if (!EC_EX_DATA_set_data(&group->extra_data, pre, nistp224_pre_comp_dup,
- nistp224_pre_comp_free, nistp224_pre_comp_clear_free))
- goto err;
- ret = 1;
- pre = NULL;
- err:
- BN_CTX_end(ctx);
- if (generator != NULL)
- EC_POINT_free(generator);
- if (new_ctx != NULL)
- BN_CTX_free(new_ctx);
- if (pre)
- nistp224_pre_comp_free(pre);
- return ret;
- }
- int ec_GFp_nistp224_have_precompute_mult(const EC_GROUP *group)
- {
- if (EC_EX_DATA_get_data(group->extra_data, nistp224_pre_comp_dup,
- nistp224_pre_comp_free, nistp224_pre_comp_clear_free)
- != NULL)
- return 1;
- else
- return 0;
- }
- #endif
- #ifdef TESTING
- #include <sys/time.h>
- static u8 ctoh(char c)
- {
- if (c >= '0' && c <= '9') return c-'0';
- if (c >= 'a' && c <= 'f') return c-'a'+10;
- if (c >= 'A' && c <= 'F') return c-'A'+10;
- return 0;
- }
- static void arg_to_bytearray(felem_bytearray ba, const char *arg)
- {
-
- int size = sizeof(felem_bytearray);
- int arglen = strlen(arg);
- int argsize = (arglen+1)/2;
- const char *argp = arg + arglen;
- u8 *bap = ba;
- memset(ba, 0, size);
- if (size < argsize) {
- fprintf(stderr, "Arg too long: %s\n", arg);
- exit(1);
- }
- while (argp > arg+1) {
- argp -= 2;
- *bap = (ctoh(argp[0])<<4)|(ctoh(argp[1]));
- ++bap;
- }
- if (arglen & 1) {
-
- argp -= 1;
- *bap = ctoh(argp[0]);
- }
- }
- static void arg_to_coord(coord c, const char *arg)
- {
- felem_bytearray ba;
- arg_to_bytearray(ba, arg);
-
- bin21_to_felem(c, ba);
- }
- int main(int argc, char **argv)
- {
- point infinity, P, Q, P2, PQ;
- felem_bytearray s;
- int i;
- struct timeval st, et;
- unsigned long el;
- int niter = 1000;
- memset(infinity, 0, sizeof(infinity));
- memset(P, 0, sizeof(P));
- memset(Q, 0, sizeof(Q));
- if (argc != 6) {
- fprintf(stderr, "Usage: %s Px Py Qx Qy s\n", argv[0]);
- exit(1);
- }
- arg_to_coord(P[0], argv[1]);
- arg_to_coord(P[1], argv[2]);
- P[2][0] = 1;
- dump_point("P", P);
- arg_to_coord(Q[0], argv[3]);
- arg_to_coord(Q[1], argv[4]);
- Q[2][0] = 1;
- dump_point("Q", Q);
- arg_to_bytearray(s, argv[5]);
- point_double(P2[0], P2[1], P2[2], P[0], P[1], P[2]);
- affine(P2);
- point_add(PQ[0], PQ[1], PQ[2], P[0], P[1], P[2], Q[0], Q[1], Q[2]);
- affine(PQ);
- dump_point("P2", P2);
- dump_point("PQ", PQ);
- gettimeofday(&st, NULL);
- for (i=0;i<niter;++i) {
- point_mul(P, P, s);
- affine(P);
- }
- gettimeofday(&et, NULL);
- el = (et.tv_sec-st.tv_sec)*1000000 + (et.tv_usec-st.tv_usec);
- fprintf(stderr, "%lu / %d = %lu us\n", el, niter, el/niter);
- dump_point("Ps", P);
- return 0;
- }
- #endif
- void ptwist_pointmul(byte out[PTWIST_BYTES], const byte x[PTWIST_BYTES],
- const byte seckey[PTWIST_BYTES])
- {
-
- point P, Q;
- coord z, r2, Qx;
- uint128_t tmp[5];
- int ontwist;
- static const coord three = { 3, 0, 0 };
- static const coord b =
- { 0x46d320e01dc7d6, 0x486ebc69bad316, 0x4e355e95cafedd };
-
- bin21_to_felem(P[0], x);
-
- felem_square(tmp, P[0]); felem_reduce(z, tmp);
- felem_diff64(z, three);
- felem_mul(tmp, z, P[0]); felem_reduce(z, tmp);
- felem_sum64(z, b);
-
-
- felem_sqrt(P[1], z);
-
-
- felem_square(tmp, P[1]); felem_diff_128_64(tmp, z); felem_reduce(r2, tmp);
- if (felem_is_zero(r2)) {
-
- ontwist = 0;
- } else {
-
- ontwist = 1;
- felem_neg(P[0], P[0]);
- }
-
- memset(P[2], 0, sizeof(coord));
- P[2][0] = 1;
-
-
- point_mul(Q, P, seckey);
- affine_x(Qx, Q);
-
-
- if (ontwist) {
- felem_neg(Qx, Qx);
- }
-
- felem_to_bin21(out, Qx);
-
- }
|