summaryrefslogtreecommitdiffstats
path: root/third_party/heimdal/lib/hcrypto/libtommath/etc
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/heimdal/lib/hcrypto/libtommath/etc')
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.12
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.c81
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/drprime.c67
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.2825
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.txt9
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/makefile44
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.icc67
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.msvc24
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/mersenne.c138
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/mont.c44
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/pprime.c411
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/prime.1024414
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/prime.512205
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/timer.asm37
-rw-r--r--third_party/heimdal/lib/hcrypto/libtommath/etc/tune.c542
-rwxr-xr-xthird_party/heimdal/lib/hcrypto/libtommath/etc/tune_it.sh107
16 files changed, 2217 insertions, 0 deletions
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.1 b/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.1
new file mode 100644
index 0000000..c41ded1
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.1
@@ -0,0 +1,2 @@
+256-bits (k = 36113) = 115792089237316195423570985008687907853269984665640564039457584007913129603823
+512-bits (k = 38117) = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006045979
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.c
new file mode 100644
index 0000000..95ed2de
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/2kprime.c
@@ -0,0 +1,81 @@
+/* Makes safe primes of a 2k nature */
+#include <tommath.h>
+#include <time.h>
+
+static int sizes[] = {256, 512, 768, 1024, 1536, 2048, 3072, 4096};
+
+int main(void)
+{
+ char buf[2000];
+ size_t x;
+ mp_bool y;
+ mp_int q, p;
+ FILE *out;
+ clock_t t1;
+ mp_digit z;
+
+ mp_init_multi(&q, &p, NULL);
+
+ out = fopen("2kprime.1", "w");
+ if (out != NULL) {
+ for (x = 0; x < (sizeof(sizes) / sizeof(sizes[0])); x++) {
+top:
+ mp_2expt(&q, sizes[x]);
+ mp_add_d(&q, 3uL, &q);
+ z = -3;
+
+ t1 = clock();
+ for (;;) {
+ mp_sub_d(&q, 4uL, &q);
+ z += 4uL;
+
+ if (z > MP_MASK) {
+ printf("No primes of size %d found\n", sizes[x]);
+ break;
+ }
+
+ if ((clock() - t1) > CLOCKS_PER_SEC) {
+ printf(".");
+ fflush(stdout);
+ /* sleep((clock() - t1 + CLOCKS_PER_SEC/2)/CLOCKS_PER_SEC); */
+ t1 = clock();
+ }
+
+ /* quick test on q */
+ mp_prime_is_prime(&q, 1, &y);
+ if (y == MP_NO) {
+ continue;
+ }
+
+ /* find (q-1)/2 */
+ mp_sub_d(&q, 1uL, &p);
+ mp_div_2(&p, &p);
+ mp_prime_is_prime(&p, 3, &y);
+ if (y == MP_NO) {
+ continue;
+ }
+
+ /* test on q */
+ mp_prime_is_prime(&q, 3, &y);
+ if (y == MP_NO) {
+ continue;
+ }
+
+ break;
+ }
+
+ if (y == MP_NO) {
+ ++sizes[x];
+ goto top;
+ }
+
+ mp_to_decimal(&q, buf, sizeof(buf));
+ printf("\n\n%d-bits (k = %lu) = %s\n", sizes[x], z, buf);
+ fprintf(out, "%d-bits (k = %lu) = %s\n", sizes[x], z, buf);
+ fflush(out);
+ }
+ fclose(out);
+ }
+
+ return 0;
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/drprime.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprime.c
new file mode 100644
index 0000000..64e31ef
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprime.c
@@ -0,0 +1,67 @@
+/* Makes safe primes of a DR nature */
+#include <tommath.h>
+
+static int sizes[] = { 1+256/MP_DIGIT_BIT, 1+512/MP_DIGIT_BIT, 1+768/MP_DIGIT_BIT, 1+1024/MP_DIGIT_BIT, 1+2048/MP_DIGIT_BIT, 1+4096/MP_DIGIT_BIT };
+
+int main(void)
+{
+ mp_bool res;
+ int x, y;
+ char buf[4096];
+ FILE *out;
+ mp_int a, b;
+
+ mp_init(&a);
+ mp_init(&b);
+
+ out = fopen("drprimes.txt", "w");
+ if (out != NULL) {
+ for (x = 0; x < (int)(sizeof(sizes)/sizeof(sizes[0])); x++) {
+top:
+ printf("Seeking a %d-bit safe prime\n", sizes[x] * MP_DIGIT_BIT);
+ mp_grow(&a, sizes[x]);
+ mp_zero(&a);
+ for (y = 1; y < sizes[x]; y++) {
+ a.dp[y] = MP_MASK;
+ }
+
+ /* make a DR modulus */
+ a.dp[0] = -1;
+ a.used = sizes[x];
+
+ /* now loop */
+ res = MP_NO;
+ for (;;) {
+ a.dp[0] += 4uL;
+ if (a.dp[0] >= MP_MASK) break;
+ mp_prime_is_prime(&a, 1, &res);
+ if (res == MP_NO) continue;
+ printf(".");
+ fflush(stdout);
+ mp_sub_d(&a, 1uL, &b);
+ mp_div_2(&b, &b);
+ mp_prime_is_prime(&b, 3, &res);
+ if (res == MP_NO) continue;
+ mp_prime_is_prime(&a, 3, &res);
+ if (res == MP_YES) break;
+ }
+
+ if (res != MP_YES) {
+ printf("Error not DR modulus\n");
+ sizes[x] += 1;
+ goto top;
+ } else {
+ mp_to_decimal(&a, buf, sizeof(buf));
+ printf("\n\np == %s\n\n", buf);
+ fprintf(out, "%d-bit prime:\np == %s\n\n", mp_count_bits(&a), buf);
+ fflush(out);
+ }
+ }
+ fclose(out);
+ }
+
+ mp_clear(&a);
+ mp_clear(&b);
+
+ return 0;
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.28 b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.28
new file mode 100644
index 0000000..9d438ad
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.28
@@ -0,0 +1,25 @@
+DR safe primes for 28-bit digits.
+
+224-bit prime:
+p == 26959946667150639794667015087019630673637144422540572481103341844143
+
+532-bit prime:
+p == 14059105607947488696282932836518693308967803494693489478439861164411992439598399594747002144074658928593502845729752797260025831423419686528151609940203368691747
+
+784-bit prime:
+p == 101745825697019260773923519755878567461315282017759829107608914364075275235254395622580447400994175578963163918967182013639660669771108475957692810857098847138903161308502419410142185759152435680068435915159402496058513611411688900243039
+
+1036-bit prime:
+p == 736335108039604595805923406147184530889923370574768772191969612422073040099331944991573923112581267542507986451953227192970402893063850485730703075899286013451337291468249027691733891486704001513279827771740183629161065194874727962517148100775228363421083691764065477590823919364012917984605619526140821798437127
+
+1540-bit prime:
+p == 38564998830736521417281865696453025806593491967131023221754800625044118265468851210705360385717536794615180260494208076605798671660719333199513807806252394423283413430106003596332513246682903994829528690198205120921557533726473585751382193953592127439965050261476810842071573684505878854588706623484573925925903505747545471088867712185004135201289273405614415899438276535626346098904241020877974002916168099951885406379295536200413493190419727789712076165162175783
+
+2072-bit prime:
+p == 542189391331696172661670440619180536749994166415993334151601745392193484590296600979602378676624808129613777993466242203025054573692562689251250471628358318743978285860720148446448885701001277560572526947619392551574490839286458454994488665744991822837769918095117129546414124448777033941223565831420390846864429504774477949153794689948747680362212954278693335653935890352619041936727463717926744868338358149568368643403037768649616778526013610493696186055899318268339432671541328195724261329606699831016666359440874843103020666106568222401047720269951530296879490444224546654729111504346660859907296364097126834834235287147
+
+3080-bit prime:
+p == 1487259134814709264092032648525971038895865645148901180585340454985524155135260217788758027400478312256339496385275012465661575576202252063145698732079880294664220579764848767704076761853197216563262660046602703973050798218246170835962005598561669706844469447435461092542265792444947706769615695252256130901271870341005768912974433684521436211263358097522726462083917939091760026658925757076733484173202927141441492573799914240222628795405623953109131594523623353044898339481494120112723445689647986475279242446083151413667587008191682564376412347964146113898565886683139407005941383669325997475076910488086663256335689181157957571445067490187939553165903773554290260531009121879044170766615232300936675369451260747671432073394867530820527479172464106442450727640226503746586340279816318821395210726268291535648506190714616083163403189943334431056876038286530365757187367147446004855912033137386225053275419626102417236133948503
+
+4116-bit prime:
+p == 1095121115716677802856811290392395128588168592409109494900178008967955253005183831872715423151551999734857184538199864469605657805519106717529655044054833197687459782636297255219742994736751541815269727940751860670268774903340296040006114013971309257028332849679096824800250742691718610670812374272414086863715763724622797509437062518082383056050144624962776302147890521249477060215148275163688301275847155316042279405557632639366066847442861422164832655874655824221577849928863023018366835675399949740429332468186340518172487073360822220449055340582568461568645259954873303616953776393853174845132081121976327462740354930744487429617202585015510744298530101547706821590188733515880733527449780963163909830077616357506845523215289297624086914545378511082534229620116563260168494523906566709418166011112754529766183554579321224940951177394088465596712620076240067370589036924024728375076210477267488679008016579588696191194060127319035195370137160936882402244399699172017835144537488486396906144217720028992863941288217185353914991583400421682751000603596655790990815525126154394344641336397793791497068253936771017031980867706707490224041075826337383538651825493679503771934836094655802776331664261631740148281763487765852746577808019633679
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.txt b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.txt
new file mode 100644
index 0000000..7c97f67
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/drprimes.txt
@@ -0,0 +1,9 @@
+300-bit prime:
+p == 2037035976334486086268445688409378161051468393665936250636140449354381298610415201576637819
+
+540-bit prime:
+p == 3599131035634557106248430806148785487095757694641533306480604458089470064537190296255232548883112685719936728506816716098566612844395439751206810991770626477344739
+
+780-bit prime:
+p == 6359114106063703798370219984742410466332205126109989319225557147754704702203399726411277962562135973685197744935448875852478791860694279747355800678568677946181447581781401213133886609947027230004277244697462656003655947791725966271167
+
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile
new file mode 100644
index 0000000..85bb09e
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile
@@ -0,0 +1,44 @@
+LTM_CFLAGS += -Wall -W -Wextra -Wshadow -O3 -I../
+LTM_CFLAGS += $(CFLAGS)
+
+# default lib name (requires install with root)
+# LIBNAME=-ltommath
+
+# libname when you can't install the lib with install
+LIBNAME=../libtommath.a
+
+#provable primes
+pprime: pprime.o
+ $(CC) $(LTM_CFLAGS) pprime.o $(LIBNAME) -o pprime
+
+# portable [well requires clock()] tuning app
+tune: tune.o
+ $(CC) $(LTM_CFLAGS) tune.o $(LIBNAME) -o tune
+ ./tune_it.sh
+
+test_standalone: tune.o
+ # The benchmark program works as a testtool, too
+ $(CC) $(LTM_CFLAGS) tune.o $(LIBNAME) -o test
+
+# spits out mersenne primes
+mersenne: mersenne.o
+ $(CC) $(LTM_CFLAGS) mersenne.o $(LIBNAME) -o mersenne
+
+# finds DR safe primes for the given config
+drprime: drprime.o
+ $(CC) $(LTM_CFLAGS) drprime.o $(LIBNAME) -o drprime
+
+# finds 2k safe primes for the given config
+2kprime: 2kprime.o
+ $(CC) $(LTM_CFLAGS) 2kprime.o $(LIBNAME) -o 2kprime
+
+mont: mont.o
+ $(CC) $(LTM_CFLAGS) mont.o $(LIBNAME) -o mont
+
+
+clean:
+ rm -f *.log *.o *.obj *.exe pprime tune mersenne drprime mont 2kprime pprime.dat \
+ tuning_list multiplying squaring test *.da *.dyn *.dpi *~
+ rm -rf .libs
+
+.PHONY: tune
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.icc b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.icc
new file mode 100644
index 0000000..9217f7b
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.icc
@@ -0,0 +1,67 @@
+CC = icc
+
+CFLAGS += -I../
+
+# optimize for SPEED
+#
+# -mcpu= can be pentium, pentiumpro (covers PII through PIII) or pentium4
+# -ax? specifies make code specifically for ? but compatible with IA-32
+# -x? specifies compile solely for ? [not specifically IA-32 compatible]
+#
+# where ? is
+# K - PIII
+# W - first P4 [Williamette]
+# N - P4 Northwood
+# P - P4 Prescott
+# B - Blend of P4 and PM [mobile]
+#
+# Default to just generic max opts
+CFLAGS += -O3 -xP -ip
+
+# default lib name (requires install with root)
+# LIBNAME=-ltommath
+
+# libname when you can't install the lib with install
+LIBNAME=../libtommath.a
+
+#provable primes
+pprime: pprime.o
+ $(CC) pprime.o $(LIBNAME) -o pprime
+
+tune: tune.o
+ $(CC) $(CFLAGS) tune.o $(LIBNAME) -o tune
+ ./tune_it.sh
+
+# same app but using RDTSC for higher precision [requires 80586+], coff based gcc installs [e.g. ming, cygwin, djgpp]
+tune86: tune.c
+ nasm -f coff timer.asm
+ $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86
+
+# for cygwin
+tune86c: tune.c
+ nasm -f gnuwin32 timer.asm
+ $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86
+
+#make tune86 for linux or any ELF format
+tune86l: tune.c
+ nasm -f elf -DUSE_ELF timer.asm
+ $(CC) -DX86_TIMER $(CFLAGS) tune.c timer.o $(LIBNAME) -o tune86l
+
+# spits out mersenne primes
+mersenne: mersenne.o
+ $(CC) mersenne.o $(LIBNAME) -o mersenne
+
+# fines DR safe primes for the given config
+drprime: drprime.o
+ $(CC) drprime.o $(LIBNAME) -o drprime
+
+# fines 2k safe primes for the given config
+2kprime: 2kprime.o
+ $(CC) 2kprime.o $(LIBNAME) -o 2kprime
+
+mont: mont.o
+ $(CC) mont.o $(LIBNAME) -o mont
+
+
+clean:
+ rm -f *.log *.o *.obj *.exe pprime tune mersenne drprime tune86 tune86l mont 2kprime pprime.dat *.il tuning_list
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.msvc b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.msvc
new file mode 100644
index 0000000..592a437
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/makefile.msvc
@@ -0,0 +1,24 @@
+#MSVC Makefile
+#
+#Tom St Denis
+
+CFLAGS = /I../ /Ox /DWIN32 /W3
+
+pprime: pprime.obj
+ cl pprime.obj ../tommath.lib
+
+mersenne: mersenne.obj
+ cl mersenne.obj ../tommath.lib
+
+tune: tune.obj
+ cl tune.obj ../tommath.lib
+
+
+mont: mont.obj
+ cl mont.obj ../tommath.lib
+
+drprime: drprime.obj
+ cl drprime.obj ../tommath.lib
+
+2kprime: 2kprime.obj
+ cl 2kprime.obj ../tommath.lib
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/mersenne.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/mersenne.c
new file mode 100644
index 0000000..0c9f52f
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/mersenne.c
@@ -0,0 +1,138 @@
+/* Finds Mersenne primes using the Lucas-Lehmer test
+ *
+ * Tom St Denis, tomstdenis@gmail.com
+ */
+#include <time.h>
+#include <tommath.h>
+
+static mp_err is_mersenne(long s, mp_bool *pp)
+{
+ mp_int n, u;
+ mp_err res;
+ int k;
+
+ *pp = MP_NO;
+
+ if ((res = mp_init(&n)) != MP_OKAY) {
+ return res;
+ }
+
+ if ((res = mp_init(&u)) != MP_OKAY) {
+ goto LBL_N;
+ }
+
+ /* n = 2^s - 1 */
+ if ((res = mp_2expt(&n, (int)s)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+ if ((res = mp_sub_d(&n, 1uL, &n)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+
+ /* set u=4 */
+ mp_set(&u, 4uL);
+
+ /* for k=1 to s-2 do */
+ for (k = 1; k <= (s - 2); k++) {
+ /* u = u^2 - 2 mod n */
+ if ((res = mp_sqr(&u, &u)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+ if ((res = mp_sub_d(&u, 2uL, &u)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+
+ /* make sure u is positive */
+ while (u.sign == MP_NEG) {
+ if ((res = mp_add(&u, &n, &u)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+ }
+
+ /* reduce */
+ if ((res = mp_reduce_2k(&u, &n, 1uL)) != MP_OKAY) {
+ goto LBL_MU;
+ }
+ }
+
+ /* if u == 0 then its prime */
+ if (mp_iszero(&u) == MP_YES) {
+ mp_prime_is_prime(&n, 8, pp);
+ if (*pp != MP_YES) printf("FAILURE\n");
+ }
+
+ res = MP_OKAY;
+LBL_MU:
+ mp_clear(&u);
+LBL_N:
+ mp_clear(&n);
+ return res;
+}
+
+/* square root of a long < 65536 */
+static long i_sqrt(long x)
+{
+ long x1, x2;
+
+ x2 = 16;
+ do {
+ x1 = x2;
+ x2 = x1 - ((x1 * x1) - x) / (2 * x1);
+ } while (x1 != x2);
+
+ if ((x1 * x1) > x) {
+ --x1;
+ }
+
+ return x1;
+}
+
+/* is the long prime by brute force */
+static int isprime(long k)
+{
+ long y, z;
+
+ y = i_sqrt(k);
+ for (z = 2; z <= y; z++) {
+ if ((k % z) == 0)
+ return 0;
+ }
+ return 1;
+}
+
+
+int main(void)
+{
+ mp_bool pp;
+ long k;
+ clock_t tt;
+
+ k = 3;
+
+ for (;;) {
+ /* start time */
+ tt = clock();
+
+ /* test if 2^k - 1 is prime */
+ if (is_mersenne(k, &pp) != MP_OKAY) {
+ printf("Whoa error\n");
+ return -1;
+ }
+
+ if (pp == MP_YES) {
+ /* count time */
+ tt = clock() - tt;
+
+ /* display if prime */
+ printf("2^%-5ld - 1 is prime, test took %ld ticks\n", k, (long)tt);
+ }
+
+ /* goto next odd exponent */
+ k += 2;
+
+ /* but make sure its prime */
+ while (isprime(k) == 0) {
+ k += 2;
+ }
+ }
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/mont.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/mont.c
new file mode 100644
index 0000000..4652410
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/mont.c
@@ -0,0 +1,44 @@
+/* tests the montgomery routines */
+#include <tommath.h>
+#include <stdlib.h>
+#include <time.h>
+
+int main(void)
+{
+ mp_int modulus, R, p, pp;
+ mp_digit mp;
+ int x, y;
+
+ srand(time(NULL));
+ mp_init_multi(&modulus, &R, &p, &pp, NULL);
+
+ /* loop through various sizes */
+ for (x = 4; x < 256; x++) {
+ printf("DIGITS == %3d...", x);
+ fflush(stdout);
+
+ /* make up the odd modulus */
+ mp_rand(&modulus, x);
+ modulus.dp[0] |= 1uL;
+
+ /* now find the R value */
+ mp_montgomery_calc_normalization(&R, &modulus);
+ mp_montgomery_setup(&modulus, &mp);
+
+ /* now run through a bunch tests */
+ for (y = 0; y < 1000; y++) {
+ mp_rand(&p, x/2); /* p = random */
+ mp_mul(&p, &R, &pp); /* pp = R * p */
+ mp_montgomery_reduce(&pp, &modulus, mp);
+
+ /* should be equal to p */
+ if (mp_cmp(&pp, &p) != MP_EQ) {
+ printf("FAILURE!\n");
+ exit(-1);
+ }
+ }
+ printf("PASSED\n");
+ }
+
+ return 0;
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/pprime.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/pprime.c
new file mode 100644
index 0000000..009a18c
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/pprime.c
@@ -0,0 +1,411 @@
+/* Generates provable primes
+ *
+ * See http://gmail.com:8080/papers/pp.pdf for more info.
+ *
+ * Tom St Denis, tomstdenis@gmail.com, http://tom.gmail.com
+ */
+#include <stdlib.h>
+#include <time.h>
+#include "tommath.h"
+
+static int n_prime;
+static FILE *primes;
+
+/* fast square root */
+static mp_digit i_sqrt(mp_word x)
+{
+ mp_word x1, x2;
+
+ x2 = x;
+ do {
+ x1 = x2;
+ x2 = x1 - ((x1 * x1) - x) / (2u * x1);
+ } while (x1 != x2);
+
+ if ((x1 * x1) > x) {
+ --x1;
+ }
+
+ return x1;
+}
+
+
+/* generates a prime digit */
+static void gen_prime(void)
+{
+ mp_digit r, x, y, next;
+ FILE *out;
+
+ out = fopen("pprime.dat", "wb");
+ if (out != NULL) {
+
+ /* write first set of primes */
+ /* *INDENT-OFF* */
+ r = 3uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 5uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 7uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 11uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 13uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 17uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 19uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 23uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 29uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ r = 31uL; fwrite(&r, 1uL, sizeof(mp_digit), out);
+ /* *INDENT-ON* */
+
+ /* get square root, since if 'r' is composite its factors must be < than this */
+ y = i_sqrt(r);
+ next = (y + 1uL) * (y + 1uL);
+
+ for (;;) {
+ do {
+ r += 2uL; /* next candidate */
+ r &= MP_MASK;
+ if (r < 31uL) break;
+
+ /* update sqrt ? */
+ if (next <= r) {
+ ++y;
+ next = (y + 1uL) * (y + 1uL);
+ }
+
+ /* loop if divisible by 3,5,7,11,13,17,19,23,29 */
+ if ((r % 3uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 5uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 7uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 11uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 13uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 17uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 19uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 23uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+ if ((r % 29uL) == 0uL) {
+ x = 0uL;
+ continue;
+ }
+
+ /* now check if r is divisible by x + k={1,7,11,13,17,19,23,29} */
+ for (x = 30uL; x <= y; x += 30uL) {
+ if ((r % (x + 1uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 7uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 11uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 13uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 17uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 19uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 23uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ if ((r % (x + 29uL)) == 0uL) {
+ x = 0uL;
+ break;
+ }
+ }
+ } while (x == 0uL);
+ if (r > 31uL) {
+ fwrite(&r, 1uL, sizeof(mp_digit), out);
+ printf("%9lu\r", r);
+ fflush(stdout);
+ }
+ if (r < 31uL) break;
+ }
+
+ fclose(out);
+ }
+}
+
+static void load_tab(void)
+{
+ primes = fopen("pprime.dat", "rb");
+ if (primes == NULL) {
+ gen_prime();
+ primes = fopen("pprime.dat", "rb");
+ }
+ fseek(primes, 0L, SEEK_END);
+ n_prime = ftell(primes) / sizeof(mp_digit);
+}
+
+static mp_digit prime_digit(void)
+{
+ int n;
+ mp_digit d;
+
+ n = abs(rand()) % n_prime;
+ fseek(primes, n * sizeof(mp_digit), SEEK_SET);
+ fread(&d, 1uL, sizeof(mp_digit), primes);
+ return d;
+}
+
+
+/* makes a prime of at least k bits */
+static mp_err pprime(int k, int li, mp_int *p, mp_int *q)
+{
+ mp_int a, b, c, n, x, y, z, v;
+ mp_err res;
+ int ii;
+ static const mp_digit bases[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
+
+ /* single digit ? */
+ if (k <= (int) MP_DIGIT_BIT) {
+ mp_set(p, prime_digit());
+ return MP_OKAY;
+ }
+
+ if ((res = mp_init(&c)) != MP_OKAY) {
+ return res;
+ }
+
+ if ((res = mp_init(&v)) != MP_OKAY) {
+ goto LBL_C;
+ }
+
+ /* product of first 50 primes */
+ if ((res =
+ mp_read_radix(&v,
+ "19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190",
+ 10)) != MP_OKAY) {
+ goto LBL_V;
+ }
+
+ if ((res = mp_init(&a)) != MP_OKAY) {
+ goto LBL_V;
+ }
+
+ /* set the prime */
+ mp_set(&a, prime_digit());
+
+ if ((res = mp_init(&b)) != MP_OKAY) {
+ goto LBL_A;
+ }
+
+ if ((res = mp_init(&n)) != MP_OKAY) {
+ goto LBL_B;
+ }
+
+ if ((res = mp_init(&x)) != MP_OKAY) {
+ goto LBL_N;
+ }
+
+ if ((res = mp_init(&y)) != MP_OKAY) {
+ goto LBL_X;
+ }
+
+ if ((res = mp_init(&z)) != MP_OKAY) {
+ goto LBL_Y;
+ }
+
+ /* now loop making the single digit */
+ while (mp_count_bits(&a) < k) {
+ fprintf(stderr, "prime has %4d bits left\r", k - mp_count_bits(&a));
+ fflush(stderr);
+top:
+ mp_set(&b, prime_digit());
+
+ /* now compute z = a * b * 2 */
+ if ((res = mp_mul(&a, &b, &z)) != MP_OKAY) { /* z = a * b */
+ goto LBL_Z;
+ }
+
+ if ((res = mp_copy(&z, &c)) != MP_OKAY) { /* c = a * b */
+ goto LBL_Z;
+ }
+
+ if ((res = mp_mul_2(&z, &z)) != MP_OKAY) { /* z = 2 * a * b */
+ goto LBL_Z;
+ }
+
+ /* n = z + 1 */
+ if ((res = mp_add_d(&z, 1uL, &n)) != MP_OKAY) { /* n = z + 1 */
+ goto LBL_Z;
+ }
+
+ /* check (n, v) == 1 */
+ if ((res = mp_gcd(&n, &v, &y)) != MP_OKAY) { /* y = (n, v) */
+ goto LBL_Z;
+ }
+
+ if (mp_cmp_d(&y, 1uL) != MP_EQ)
+ goto top;
+
+ /* now try base x=bases[ii] */
+ for (ii = 0; ii < li; ii++) {
+ mp_set(&x, bases[ii]);
+
+ /* compute x^a mod n */
+ if ((res = mp_exptmod(&x, &a, &n, &y)) != MP_OKAY) { /* y = x^a mod n */
+ goto LBL_Z;
+ }
+
+ /* if y == 1 loop */
+ if (mp_cmp_d(&y, 1uL) == MP_EQ)
+ continue;
+
+ /* now x^2a mod n */
+ if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2a mod n */
+ goto LBL_Z;
+ }
+
+ if (mp_cmp_d(&y, 1uL) == MP_EQ)
+ continue;
+
+ /* compute x^b mod n */
+ if ((res = mp_exptmod(&x, &b, &n, &y)) != MP_OKAY) { /* y = x^b mod n */
+ goto LBL_Z;
+ }
+
+ /* if y == 1 loop */
+ if (mp_cmp_d(&y, 1uL) == MP_EQ)
+ continue;
+
+ /* now x^2b mod n */
+ if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2b mod n */
+ goto LBL_Z;
+ }
+
+ if (mp_cmp_d(&y, 1uL) == MP_EQ)
+ continue;
+
+ /* compute x^c mod n == x^ab mod n */
+ if ((res = mp_exptmod(&x, &c, &n, &y)) != MP_OKAY) { /* y = x^ab mod n */
+ goto LBL_Z;
+ }
+
+ /* if y == 1 loop */
+ if (mp_cmp_d(&y, 1uL) == MP_EQ)
+ continue;
+
+ /* now compute (x^c mod n)^2 */
+ if ((res = mp_sqrmod(&y, &n, &y)) != MP_OKAY) { /* y = x^2ab mod n */
+ goto LBL_Z;
+ }
+
+ /* y should be 1 */
+ if (mp_cmp_d(&y, 1uL) != MP_EQ)
+ continue;
+ break;
+ }
+
+ /* no bases worked? */
+ if (ii == li)
+ goto top;
+
+ {
+ char buf[4096];
+
+ mp_to_decimal(&n, buf, sizeof(buf));
+ printf("Certificate of primality for:\n%s\n\n", buf);
+ mp_to_decimal(&a, buf, sizeof(buf));
+ printf("A == \n%s\n\n", buf);
+ mp_to_decimal(&b, buf, sizeof(buf));
+ printf("B == \n%s\n\nG == %lu\n", buf, bases[ii]);
+ printf("----------------------------------------------------------------\n");
+ }
+
+ /* a = n */
+ mp_copy(&n, &a);
+ }
+
+ /* get q to be the order of the large prime subgroup */
+ mp_sub_d(&n, 1uL, q);
+ mp_div_2(q, q);
+ mp_div(q, &b, q, NULL);
+
+ mp_exch(&n, p);
+
+ res = MP_OKAY;
+LBL_Z:
+ mp_clear(&z);
+LBL_Y:
+ mp_clear(&y);
+LBL_X:
+ mp_clear(&x);
+LBL_N:
+ mp_clear(&n);
+LBL_B:
+ mp_clear(&b);
+LBL_A:
+ mp_clear(&a);
+LBL_V:
+ mp_clear(&v);
+LBL_C:
+ mp_clear(&c);
+ return res;
+}
+
+
+int main(void)
+{
+ mp_int p, q;
+ char buf[4096];
+ int k, li;
+ clock_t t1;
+
+ srand(time(NULL));
+ load_tab();
+
+ printf("Enter # of bits: \n");
+ fgets(buf, sizeof(buf), stdin);
+ sscanf(buf, "%d", &k);
+
+ printf("Enter number of bases to try (1 to 8):\n");
+ fgets(buf, sizeof(buf), stdin);
+ sscanf(buf, "%d", &li);
+
+
+ mp_init(&p);
+ mp_init(&q);
+
+ t1 = clock();
+ pprime(k, li, &p, &q);
+ t1 = clock() - t1;
+
+ printf("\n\nTook %d ticks, %d bits\n", t1, mp_count_bits(&p));
+
+ mp_to_decimal(&p, buf, sizeof(buf));
+ printf("P == %s\n", buf);
+ mp_to_decimal(&q, buf, sizeof(buf));
+ printf("Q == %s\n", buf);
+
+ return 0;
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.1024 b/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.1024
new file mode 100644
index 0000000..5636e2d
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.1024
@@ -0,0 +1,414 @@
+Enter # of bits:
+Enter number of bases to try (1 to 8):
+Certificate of primality for:
+36360080703173363
+
+A ==
+89963569
+
+B ==
+202082249
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+4851595597739856136987139
+
+A ==
+36360080703173363
+
+B ==
+66715963
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+19550639734462621430325731591027
+
+A ==
+4851595597739856136987139
+
+B ==
+2014867
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+10409036141344317165691858509923818734539
+
+A ==
+19550639734462621430325731591027
+
+B ==
+266207047
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1049829549988285012736475602118094726647504414203
+
+A ==
+10409036141344317165691858509923818734539
+
+B ==
+50428759
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+77194737385528288387712399596835459931920358844586615003
+
+A ==
+1049829549988285012736475602118094726647504414203
+
+B ==
+36765367
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+35663756695365208574443215955488689578374232732893628896541201763
+
+A ==
+77194737385528288387712399596835459931920358844586615003
+
+B ==
+230998627
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+16711831463502165169495622246023119698415848120292671294127567620396469803
+
+A ==
+35663756695365208574443215955488689578374232732893628896541201763
+
+B ==
+234297127
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+6163534781560285962890718925972249753147470953579266394395432475622345597103528739
+
+A ==
+16711831463502165169495622246023119698415848120292671294127567620396469803
+
+B ==
+184406323
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+814258256205243497704094951432575867360065658372158511036259934640748088306764553488803787
+
+A ==
+6163534781560285962890718925972249753147470953579266394395432475622345597103528739
+
+B ==
+66054487
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+176469695533271657902814176811660357049007467856432383037590673407330246967781451723764079581998187
+
+A ==
+814258256205243497704094951432575867360065658372158511036259934640748088306764553488803787
+
+B ==
+108362239
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+44924492859445516541759485198544012102424796403707253610035148063863073596051272171194806669756971406400419
+
+A ==
+176469695533271657902814176811660357049007467856432383037590673407330246967781451723764079581998187
+
+B ==
+127286707
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+20600996927219343383225424320134474929609459588323857796871086845924186191561749519858600696159932468024710985371059
+
+A ==
+44924492859445516541759485198544012102424796403707253610035148063863073596051272171194806669756971406400419
+
+B ==
+229284691
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+6295696427695493110141186605837397185848992307978456138112526915330347715236378041486547994708748840844217371233735072572979
+
+A ==
+20600996927219343383225424320134474929609459588323857796871086845924186191561749519858600696159932468024710985371059
+
+B ==
+152800771
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+3104984078042317488749073016454213579257792635142218294052134804187631661145261015102617582090263808696699966840735333252107678792123
+
+A ==
+6295696427695493110141186605837397185848992307978456138112526915330347715236378041486547994708748840844217371233735072572979
+
+B ==
+246595759
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+26405175827665701256325699315126705508919255051121452292124404943796947287968603975320562847910946802396632302209435206627913466015741799499
+
+A ==
+3104984078042317488749073016454213579257792635142218294052134804187631661145261015102617582090263808696699966840735333252107678792123
+
+B ==
+4252063
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+11122146237908413610034600609460545703591095894418599759742741406628055069007082998134905595800236452010905900391505454890446585211975124558601770163
+
+A ==
+26405175827665701256325699315126705508919255051121452292124404943796947287968603975320562847910946802396632302209435206627913466015741799499
+
+B ==
+210605419
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1649861642047798890580354082088712649911849362201343649289384923147797960364736011515757482030049342943790127685185806092659832129486307035500638595572396187
+
+A ==
+11122146237908413610034600609460545703591095894418599759742741406628055069007082998134905595800236452010905900391505454890446585211975124558601770163
+
+B ==
+74170111
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+857983367126266717607389719637086684134462613006415859877666235955788392464081914127715967940968197765042399904117392707518175220864852816390004264107201177394565363
+
+A ==
+1649861642047798890580354082088712649911849362201343649289384923147797960364736011515757482030049342943790127685185806092659832129486307035500638595572396187
+
+B ==
+260016763
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+175995909353623703257072120479340610010337144085688850745292031336724691277374210929188442230237711063783727092685448718515661641054886101716698390145283196296702450566161283
+
+A ==
+857983367126266717607389719637086684134462613006415859877666235955788392464081914127715967940968197765042399904117392707518175220864852816390004264107201177394565363
+
+B ==
+102563707
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+48486002551155667224487059713350447239190772068092630563272168418880661006593537218144160068395218642353495339720640699721703003648144463556291315694787862009052641640656933232794283
+
+A ==
+175995909353623703257072120479340610010337144085688850745292031336724691277374210929188442230237711063783727092685448718515661641054886101716698390145283196296702450566161283
+
+B ==
+137747527
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+13156468011529105025061495011938518171328604045212410096476697450506055664012861932372156505805788068791146986282263016790631108386790291275939575123375304599622623328517354163964228279867403
+
+A ==
+48486002551155667224487059713350447239190772068092630563272168418880661006593537218144160068395218642353495339720640699721703003648144463556291315694787862009052641640656933232794283
+
+B ==
+135672847
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+6355194692790533601105154341731997464407930009404822926832136060319955058388106456084549316415200519472481147942263916585428906582726749131479465958107142228236909665306781538860053107680830113869123
+
+A ==
+13156468011529105025061495011938518171328604045212410096476697450506055664012861932372156505805788068791146986282263016790631108386790291275939575123375304599622623328517354163964228279867403
+
+B ==
+241523587
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+3157116676535430302794438027544146642863331358530722860333745617571010460905857862561870488000265751138954271040017454405707755458702044884023184574412221802502351503929935224995314581932097706874819348858083
+
+A ==
+6355194692790533601105154341731997464407930009404822926832136060319955058388106456084549316415200519472481147942263916585428906582726749131479465958107142228236909665306781538860053107680830113869123
+
+B ==
+248388667
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+390533129219992506725320633489467713907837370444962163378727819939092929448752905310115311180032249230394348337568973177802874166228132778126338883671958897238722734394783244237133367055422297736215754829839364158067
+
+A ==
+3157116676535430302794438027544146642863331358530722860333745617571010460905857862561870488000265751138954271040017454405707755458702044884023184574412221802502351503929935224995314581932097706874819348858083
+
+B ==
+61849651
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+48583654555070224891047847050732516652910250240135992225139515777200432486685999462997073444468380434359929499498804723793106565291183220444221080449740542884172281158126259373095216435009661050109711341419005972852770440739
+
+A ==
+390533129219992506725320633489467713907837370444962163378727819939092929448752905310115311180032249230394348337568973177802874166228132778126338883671958897238722734394783244237133367055422297736215754829839364158067
+
+B ==
+62201707
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+25733035251905120039135866524384525138869748427727001128764704499071378939227862068500633813538831598776578372709963673670934388213622433800015759585470542686333039614931682098922935087822950084908715298627996115185849260703525317419
+
+A ==
+48583654555070224891047847050732516652910250240135992225139515777200432486685999462997073444468380434359929499498804723793106565291183220444221080449740542884172281158126259373095216435009661050109711341419005972852770440739
+
+B ==
+264832231
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+2804594464939948901906623499531073917980499195397462605359913717827014360538186518540781517129548650937632008683280555602633122170458773895504894807182664540529077836857897972175530148107545939211339044386106111633510166695386323426241809387
+
+A ==
+25733035251905120039135866524384525138869748427727001128764704499071378939227862068500633813538831598776578372709963673670934388213622433800015759585470542686333039614931682098922935087822950084908715298627996115185849260703525317419
+
+B ==
+54494047
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+738136612083433720096707308165797114449914259256979340471077690416567237592465306112484843530074782721390528773594351482384711900456440808251196845265132086486672447136822046628407467459921823150600138073268385534588238548865012638209515923513516547
+
+A ==
+2804594464939948901906623499531073917980499195397462605359913717827014360538186518540781517129548650937632008683280555602633122170458773895504894807182664540529077836857897972175530148107545939211339044386106111633510166695386323426241809387
+
+B ==
+131594179
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+392847529056126766528615419937165193421166694172790666626558750047057558168124866940509180171236517681470100877687445134633784815352076138790217228749332398026714192707447855731679485746120589851992221508292976900578299504461333767437280988393026452846013683
+
+A ==
+738136612083433720096707308165797114449914259256979340471077690416567237592465306112484843530074782721390528773594351482384711900456440808251196845265132086486672447136822046628407467459921823150600138073268385534588238548865012638209515923513516547
+
+B ==
+266107603
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+168459393231883505975876919268398655632763956627405508859662408056221544310200546265681845397346956580604208064328814319465940958080244889692368602591598503944015835190587740756859842792554282496742843600573336023639256008687581291233481455395123454655488735304365627
+
+A ==
+392847529056126766528615419937165193421166694172790666626558750047057558168124866940509180171236517681470100877687445134633784815352076138790217228749332398026714192707447855731679485746120589851992221508292976900578299504461333767437280988393026452846013683
+
+B ==
+214408111
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+14865774288636941404884923981945833072113667565310054952177860608355263252462409554658728941191929400198053290113492910272458441655458514080123870132092365833472436407455910185221474386718838138135065780840839893113912689594815485706154461164071775481134379794909690501684643
+
+A ==
+168459393231883505975876919268398655632763956627405508859662408056221544310200546265681845397346956580604208064328814319465940958080244889692368602591598503944015835190587740756859842792554282496742843600573336023639256008687581291233481455395123454655488735304365627
+
+B ==
+44122723
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1213301773203241614897109856134894783021668292000023984098824423682568173639394290886185366993108292039068940333907505157813934962357206131450244004178619265868614859794316361031904412926604138893775068853175215502104744339658944443630407632290152772487455298652998368296998719996019
+
+A ==
+14865774288636941404884923981945833072113667565310054952177860608355263252462409554658728941191929400198053290113492910272458441655458514080123870132092365833472436407455910185221474386718838138135065780840839893113912689594815485706154461164071775481134379794909690501684643
+
+B ==
+40808563
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+186935245989515158127969129347464851990429060640910951266513740972248428651109062997368144722015290092846666943896556191257222521203647606911446635194198213436423080005867489516421559330500722264446765608763224572386410155413161172707802334865729654109050873820610813855041667633843601286843
+
+A ==
+1213301773203241614897109856134894783021668292000023984098824423682568173639394290886185366993108292039068940333907505157813934962357206131450244004178619265868614859794316361031904412926604138893775068853175215502104744339658944443630407632290152772487455298652998368296998719996019
+
+B ==
+77035759
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+83142661079751490510739960019112406284111408348732592580459037404394946037094409915127399165633756159385609671956087845517678367844901424617866988187132480585966721962585586730693443536100138246516868613250009028187662080828012497191775172228832247706080044971423654632146928165751885302331924491683
+
+A ==
+186935245989515158127969129347464851990429060640910951266513740972248428651109062997368144722015290092846666943896556191257222521203647606911446635194198213436423080005867489516421559330500722264446765608763224572386410155413161172707802334865729654109050873820610813855041667633843601286843
+
+B ==
+222383587
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443
+
+A ==
+83142661079751490510739960019112406284111408348732592580459037404394946037094409915127399165633756159385609671956087845517678367844901424617866988187132480585966721962585586730693443536100138246516868613250009028187662080828012497191775172228832247706080044971423654632146928165751885302331924491683
+
+B ==
+23407687
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1663606652988091811284014366560171522582683318514519379924950390627250155440313691226744227787921928894551755219495501365555370027257568506349958010457682898612082048959464465369892842603765280317696116552850664773291371490339084156052244256635115997453399761029567033971998617303988376172539172702246575225837054723
+
+A ==
+3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443
+
+B ==
+213701827
+
+G == 2
+----------------------------------------------------------------
+
+
+Took 33057 ticks, 1048 bits
+P == 1663606652988091811284014366560171522582683318514519379924950390627250155440313691226744227787921928894551755219495501365555370027257568506349958010457682898612082048959464465369892842603765280317696116552850664773291371490339084156052244256635115997453399761029567033971998617303988376172539172702246575225837054723
+Q == 3892354773803809855317742245039794448230625839512638747643814927766738642436392673485997449586432241626440927010641564064764336402368634186618250134234189066179771240232458249806850838490410473462391401438160528157981942499581634732706904411807195259620779379274017704050790865030808501633772117217899534443
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.512 b/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.512
new file mode 100644
index 0000000..cb6ec30
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/prime.512
@@ -0,0 +1,205 @@
+Enter # of bits:
+Enter number of bases to try (1 to 8):
+Certificate of primality for:
+85933926807634727
+
+A ==
+253758023
+
+B ==
+169322581
+
+G == 5
+----------------------------------------------------------------
+Certificate of primality for:
+23930198825086241462113799
+
+A ==
+85933926807634727
+
+B ==
+139236037
+
+G == 11
+----------------------------------------------------------------
+Certificate of primality for:
+6401844647261612602378676572510019
+
+A ==
+23930198825086241462113799
+
+B ==
+133760791
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+269731366027728777712034888684015329354259
+
+A ==
+6401844647261612602378676572510019
+
+B ==
+21066691
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+37942338209025571690075025099189467992329684223707
+
+A ==
+269731366027728777712034888684015329354259
+
+B ==
+70333567
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+15306904714258982484473490774101705363308327436988160248323
+
+A ==
+37942338209025571690075025099189467992329684223707
+
+B ==
+201712723
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1616744757018513392810355191503853040357155275733333124624513530099
+
+A ==
+15306904714258982484473490774101705363308327436988160248323
+
+B ==
+52810963
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+464222094814208047161771036072622485188658077940154689939306386289983787983
+
+A ==
+1616744757018513392810355191503853040357155275733333124624513530099
+
+B ==
+143566909
+
+G == 5
+----------------------------------------------------------------
+Certificate of primality for:
+187429931674053784626487560729643601208757374994177258429930699354770049369025096447
+
+A ==
+464222094814208047161771036072622485188658077940154689939306386289983787983
+
+B ==
+201875281
+
+G == 5
+----------------------------------------------------------------
+Certificate of primality for:
+100579220846502621074093727119851331775052664444339632682598589456666938521976625305832917563
+
+A ==
+187429931674053784626487560729643601208757374994177258429930699354770049369025096447
+
+B ==
+268311523
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1173616081309758475197022137833792133815753368965945885089720153370737965497134878651384030219765163
+
+A ==
+100579220846502621074093727119851331775052664444339632682598589456666938521976625305832917563
+
+B ==
+5834287
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+191456913489905913185935197655672585713573070349044195411728114905691721186574907738081340754373032735283623
+
+A ==
+1173616081309758475197022137833792133815753368965945885089720153370737965497134878651384030219765163
+
+B ==
+81567097
+
+G == 5
+----------------------------------------------------------------
+Certificate of primality for:
+57856530489201750164178576399448868489243874083056587683743345599898489554401618943240901541005080049321706789987519
+
+A ==
+191456913489905913185935197655672585713573070349044195411728114905691721186574907738081340754373032735283623
+
+B ==
+151095433
+
+G == 7
+----------------------------------------------------------------
+Certificate of primality for:
+13790529750452576698109671710773784949185621244122040804792403407272729038377767162233653248852099545134831722512085881814803
+
+A ==
+57856530489201750164178576399448868489243874083056587683743345599898489554401618943240901541005080049321706789987519
+
+B ==
+119178679
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+7075985989000817742677547821106534174334812111605018857703825637170140040509067704269696198231266351631132464035671858077052876058979
+
+A ==
+13790529750452576698109671710773784949185621244122040804792403407272729038377767162233653248852099545134831722512085881814803
+
+B ==
+256552363
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+1227273006232588072907488910282307435921226646895131225407452056677899411162892829564455154080310937471747140942360789623819327234258162420463
+
+A ==
+7075985989000817742677547821106534174334812111605018857703825637170140040509067704269696198231266351631132464035671858077052876058979
+
+B ==
+86720989
+
+G == 5
+----------------------------------------------------------------
+Certificate of primality for:
+446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763
+
+A ==
+1227273006232588072907488910282307435921226646895131225407452056677899411162892829564455154080310937471747140942360789623819327234258162420463
+
+B ==
+182015287
+
+G == 2
+----------------------------------------------------------------
+Certificate of primality for:
+5290203010849586596974953717018896543907195901082056939587768479377028575911127944611236020459652034082251335583308070846379514569838984811187823420951275243
+
+A ==
+446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763
+
+B ==
+5920567
+
+G == 2
+----------------------------------------------------------------
+
+
+Took 3454 ticks, 521 bits
+P == 5290203010849586596974953717018896543907195901082056939587768479377028575911127944611236020459652034082251335583308070846379514569838984811187823420951275243
+Q == 446764896913554613686067036908702877942872355053329937790398156069936255759889884246832779737114032666318220500106499161852193765380831330106375235763
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/timer.asm b/third_party/heimdal/lib/hcrypto/libtommath/etc/timer.asm
new file mode 100644
index 0000000..35890d9
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/timer.asm
@@ -0,0 +1,37 @@
+; x86 timer in NASM
+;
+; Tom St Denis, tomstdenis@iahu.ca
+[bits 32]
+[section .data]
+time dd 0, 0
+
+[section .text]
+
+%ifdef USE_ELF
+[global t_start]
+t_start:
+%else
+[global _t_start]
+_t_start:
+%endif
+ push edx
+ push eax
+ rdtsc
+ mov [time+0],edx
+ mov [time+4],eax
+ pop eax
+ pop edx
+ ret
+
+%ifdef USE_ELF
+[global t_read]
+t_read:
+%else
+[global _t_read]
+_t_read:
+%endif
+ rdtsc
+ sub eax,[time+4]
+ sbb edx,[time+0]
+ ret
+ \ No newline at end of file
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/tune.c b/third_party/heimdal/lib/hcrypto/libtommath/etc/tune.c
new file mode 100644
index 0000000..e7b99fc
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/tune.c
@@ -0,0 +1,542 @@
+/* Tune the Karatsuba parameters
+ *
+ * Tom St Denis, tstdenis82@gmail.com
+ */
+#include "../tommath.h"
+#include "../tommath_private.h"
+#include <time.h>
+#include <inttypes.h>
+#include <errno.h>
+
+/*
+ Please take in mind that both multiplicands are of the same size. The balancing
+ mechanism in mp_balance works well but has some overhead itself. You can test
+ the behaviour of it with the option "-o" followed by a (small) positive number 'x'
+ to generate ratios of the form 1:x.
+*/
+
+static uint64_t s_timer_function(void);
+static void s_timer_start(void);
+static uint64_t s_timer_stop(void);
+static uint64_t s_time_mul(int size);
+static uint64_t s_time_sqr(int size);
+static void s_usage(char *s);
+
+static uint64_t s_timer_function(void)
+{
+#if _POSIX_C_SOURCE >= 199309L
+#define LTM_BILLION 1000000000
+ struct timespec ts;
+
+ /* TODO: Sets errno in case of error. Use? */
+ clock_gettime(CLOCK_MONOTONIC, &ts);
+ return (((uint64_t)ts.tv_sec) * LTM_BILLION + (uint64_t)ts.tv_nsec);
+#else
+ clock_t t;
+ t = clock();
+ if (t < (clock_t)(0)) {
+ return (uint64_t)(0);
+ }
+ return (uint64_t)(t);
+#endif
+}
+
+/* generic ISO C timer */
+static uint64_t s_timer_tmp;
+static void s_timer_start(void)
+{
+ s_timer_tmp = s_timer_function();
+}
+static uint64_t s_timer_stop(void)
+{
+ return s_timer_function() - s_timer_tmp;
+}
+
+
+static int s_check_result;
+static int s_number_of_test_loops;
+static int s_stabilization_extra;
+static int s_offset = 1;
+
+#define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
+static uint64_t s_time_mul(int size)
+{
+ int x;
+ mp_err e;
+ mp_int a, b, c, d;
+ uint64_t t1;
+
+ if ((e = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+
+ if ((e = mp_rand(&a, size * s_offset)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+ if ((e = mp_rand(&b, size)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+
+ s_timer_start();
+ for (x = 0; x < s_number_of_test_loops; x++) {
+ if ((e = mp_mul(&a,&b,&c)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+ if (s_check_result == 1) {
+ if ((e = s_mp_mul(&a,&b,&d)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&c, &d) != MP_EQ) {
+ /* Time of 0 cannot happen (famous last words?) */
+ t1 = 0uLL;
+ goto LTM_ERR;
+ }
+ }
+ }
+
+ t1 = s_timer_stop();
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, &d, NULL);
+ return t1;
+}
+
+static uint64_t s_time_sqr(int size)
+{
+ int x;
+ mp_err e;
+ mp_int a, b, c;
+ uint64_t t1;
+
+ if ((e = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+
+ if ((e = mp_rand(&a, size)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+
+ s_timer_start();
+ for (x = 0; x < s_number_of_test_loops; x++) {
+ if ((e = mp_sqr(&a,&b)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+ if (s_check_result == 1) {
+ if ((e = s_mp_sqr(&a,&c)) != MP_OKAY) {
+ t1 = UINT64_MAX;
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&c, &b) != MP_EQ) {
+ t1 = 0uLL;
+ goto LTM_ERR;
+ }
+ }
+ }
+
+ t1 = s_timer_stop();
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, NULL);
+ return t1;
+}
+
+struct tune_args {
+ int testmode;
+ int verbose;
+ int print;
+ int bncore;
+ int terse;
+ int upper_limit_print;
+ int increment_print;
+} args;
+
+static void s_run(const char *name, uint64_t (*op)(int), int *cutoff)
+{
+ int x, count = 0;
+ uint64_t t1, t2;
+ if ((args.verbose == 1) || (args.testmode == 1)) {
+ printf("# %s.\n", name);
+ }
+ for (x = 8; x < args.upper_limit_print; x += args.increment_print) {
+ *cutoff = INT_MAX;
+ t1 = op(x);
+ if ((t1 == 0uLL) || (t1 == UINT64_MAX)) {
+ fprintf(stderr,"%s failed at x = INT_MAX (%s)\n", name,
+ (t1 == 0uLL)?"wrong result":"internal error");
+ exit(EXIT_FAILURE);
+ }
+ *cutoff = x;
+ t2 = op(x);
+ if ((t2 == 0uLL) || (t2 == UINT64_MAX)) {
+ fprintf(stderr,"%s failed (%s)\n", name,
+ (t2 == 0uLL)?"wrong result":"internal error");
+ exit(EXIT_FAILURE);
+ }
+ if (args.verbose == 1) {
+ printf("%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1);
+ }
+ if (t2 < t1) {
+ if (count == s_stabilization_extra) {
+ count = 0;
+ break;
+ } else if (count < s_stabilization_extra) {
+ count++;
+ }
+ } else if (count > 0) {
+ count--;
+ }
+ }
+ *cutoff = x - s_stabilization_extra * args.increment_print;
+}
+
+static long s_strtol(const char *str, char **endptr, const char *err)
+{
+ const int base = 10;
+ char *_endptr;
+ long val;
+ errno = 0;
+ val = strtol(str, &_endptr, base);
+ if ((val > INT_MAX || val < 0) || (errno != 0)) {
+ fprintf(stderr, "Value %s not usable\n", str);
+ exit(EXIT_FAILURE);
+ }
+ if (_endptr == str) {
+ fprintf(stderr, "%s\n", err);
+ exit(EXIT_FAILURE);
+ }
+ if (endptr) *endptr = _endptr;
+ return val;
+}
+
+static int s_exit_code = EXIT_FAILURE;
+static void s_usage(char *s)
+{
+ fprintf(stderr,"Usage: %s [TvcpGbtrSLFfMmosh]\n",s);
+ fprintf(stderr," -T testmode, for use with testme.sh\n");
+ fprintf(stderr," -v verbose, print all timings\n");
+ fprintf(stderr," -c check results\n");
+ fprintf(stderr," -p print benchmark of final cutoffs in files \"multiplying\"\n");
+ fprintf(stderr," and \"squaring\"\n");
+ fprintf(stderr," -G [string] suffix for the filenames listed above\n");
+ fprintf(stderr," Implies '-p'\n");
+ fprintf(stderr," -b print benchmark of bncore.c\n");
+ fprintf(stderr," -t prints space (0x20) separated results\n");
+ fprintf(stderr," -r [64] number of rounds\n");
+ fprintf(stderr," -S [0xdeadbeef] seed for PRNG\n");
+ fprintf(stderr," -L [3] number of negative values accumulated until the result is accepted\n");
+ fprintf(stderr," -M [3000] upper limit of T-C tests/prints\n");
+ fprintf(stderr," -m [1] increment of T-C tests/prints\n");
+ fprintf(stderr," -o [1] multiplier for the second multiplicand\n");
+ fprintf(stderr," (Not for computing the cut-offs!)\n");
+ fprintf(stderr," -s 'preset' use values in 'preset' for printing.\n");
+ fprintf(stderr," 'preset' is a comma separated string with cut-offs for\n");
+ fprintf(stderr," ksm, kss, tc3m, tc3s in that order\n");
+ fprintf(stderr," ksm = karatsuba multiplication\n");
+ fprintf(stderr," kss = karatsuba squaring\n");
+ fprintf(stderr," tc3m = Toom-Cook 3-way multiplication\n");
+ fprintf(stderr," tc3s = Toom-Cook 3-way squaring\n");
+ fprintf(stderr," Implies '-p'\n");
+ fprintf(stderr," -h this message\n");
+ exit(s_exit_code);
+}
+
+struct cutoffs {
+ int KARATSUBA_MUL, KARATSUBA_SQR;
+ int TOOM_MUL, TOOM_SQR;
+};
+
+const struct cutoffs max_cutoffs =
+{ INT_MAX, INT_MAX, INT_MAX, INT_MAX };
+
+static void set_cutoffs(const struct cutoffs *c)
+{
+ KARATSUBA_MUL_CUTOFF = c->KARATSUBA_MUL;
+ KARATSUBA_SQR_CUTOFF = c->KARATSUBA_SQR;
+ TOOM_MUL_CUTOFF = c->TOOM_MUL;
+ TOOM_SQR_CUTOFF = c->TOOM_SQR;
+}
+
+static void get_cutoffs(struct cutoffs *c)
+{
+ c->KARATSUBA_MUL = KARATSUBA_MUL_CUTOFF;
+ c->KARATSUBA_SQR = KARATSUBA_SQR_CUTOFF;
+ c->TOOM_MUL = TOOM_MUL_CUTOFF;
+ c->TOOM_SQR = TOOM_SQR_CUTOFF;
+
+}
+
+int main(int argc, char **argv)
+{
+ uint64_t t1, t2;
+ int x, i, j;
+ size_t n;
+
+ int printpreset = 0;
+ /*int preset[8];*/
+ char *endptr, *str;
+
+ uint64_t seed = 0xdeadbeef;
+
+ int opt;
+ struct cutoffs orig, updated;
+
+ FILE *squaring, *multiplying;
+ char mullog[256] = "multiplying";
+ char sqrlog[256] = "squaring";
+ s_number_of_test_loops = 64;
+ s_stabilization_extra = 3;
+
+ MP_ZERO_BUFFER(&args, sizeof(args));
+
+ args.testmode = 0;
+ args.verbose = 0;
+ args.print = 0;
+ args.bncore = 0;
+ args.terse = 0;
+
+ args.upper_limit_print = 3000;
+ args.increment_print = 1;
+
+ /* Very simple option parser, please treat it nicely. */
+ if (argc != 1) {
+ for (opt = 1; (opt < argc) && (argv[opt][0] == '-'); opt++) {
+ switch (argv[opt][1]) {
+ case 'T':
+ args.testmode = 1;
+ s_check_result = 1;
+ args.upper_limit_print = 1000;
+ args.increment_print = 11;
+ s_number_of_test_loops = 1;
+ s_stabilization_extra = 1;
+ s_offset = 1;
+ break;
+ case 'v':
+ args.verbose = 1;
+ break;
+ case 'c':
+ s_check_result = 1;
+ break;
+ case 'p':
+ args.print = 1;
+ break;
+ case 'G':
+ args.print = 1;
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ /* manual strcat() */
+ for (i = 0; i < 255; i++) {
+ if (mullog[i] == '\0') {
+ break;
+ }
+ }
+ for (j = 0; i < 255; j++, i++) {
+ mullog[i] = argv[opt][j];
+ if (argv[opt][j] == '\0') {
+ break;
+ }
+ }
+ for (i = 0; i < 255; i++) {
+ if (sqrlog[i] == '\0') {
+ break;
+ }
+ }
+ for (j = 0; i < 255; j++, i++) {
+ sqrlog[i] = argv[opt][j];
+ if (argv[opt][j] == '\0') {
+ break;
+ }
+ }
+ break;
+ case 'b':
+ args.bncore = 1;
+ break;
+ case 't':
+ args.terse = 1;
+ break;
+ case 'S':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ str = argv[opt];
+ errno = 0;
+ seed = (uint64_t)s_strtol(argv[opt], NULL, "No seed given?\n");
+ break;
+ case 'L':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ s_stabilization_extra = (int)s_strtol(argv[opt], NULL, "No value for option \"-L\"given");
+ break;
+ case 'o':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ s_offset = (int)s_strtol(argv[opt], NULL, "No value for the offset given");
+ break;
+ case 'r':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ s_number_of_test_loops = (int)s_strtol(argv[opt], NULL, "No value for the number of rounds given");
+ break;
+
+ case 'M':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ args.upper_limit_print = (int)s_strtol(argv[opt], NULL, "No value for the upper limit of T-C tests given");
+ break;
+ case 'm':
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ args.increment_print = (int)s_strtol(argv[opt], NULL, "No value for the increment for the T-C tests given");
+ break;
+ case 's':
+ printpreset = 1;
+ args.print = 1;
+ opt++;
+ if (opt >= argc) {
+ s_usage(argv[0]);
+ }
+ str = argv[opt];
+ KARATSUBA_MUL_CUTOFF = (int)s_strtol(str, &endptr, "[1/4] No value for KARATSUBA_MUL_CUTOFF given");
+ str = endptr + 1;
+ KARATSUBA_SQR_CUTOFF = (int)s_strtol(str, &endptr, "[2/4] No value for KARATSUBA_SQR_CUTOFF given");
+ str = endptr + 1;
+ TOOM_MUL_CUTOFF = (int)s_strtol(str, &endptr, "[3/4] No value for TOOM_MUL_CUTOFF given");
+ str = endptr + 1;
+ TOOM_SQR_CUTOFF = (int)s_strtol(str, &endptr, "[4/4] No value for TOOM_SQR_CUTOFF given");
+ break;
+ case 'h':
+ s_exit_code = EXIT_SUCCESS;
+ /* FALLTHROUGH */
+ default:
+ s_usage(argv[0]);
+ }
+ }
+ }
+
+ /*
+ mp_rand uses the cryptographically secure
+ source of the OS by default. That is too expensive, too slow and
+ most important for a benchmark: it is not repeatable.
+ */
+ s_mp_rand_jenkins_init(seed);
+ mp_rand_source(s_mp_rand_jenkins);
+
+ get_cutoffs(&orig);
+
+ updated = max_cutoffs;
+ if ((args.bncore == 0) && (printpreset == 0)) {
+ struct {
+ const char *name;
+ int *cutoff, *update;
+ uint64_t (*fn)(int);
+ } test[] = {
+#define T_MUL_SQR(n, o, f) { #n, &o##_CUTOFF, &(updated.o), MP_HAS(S_MP_##o) ? f : NULL }
+ /*
+ The influence of the Comba multiplication cannot be
+ eradicated programmatically. It depends on the size
+ of the macro MP_WPARRAY in tommath.h which needs to
+ be changed manually (to 0 (zero)).
+ */
+ T_MUL_SQR("Karatsuba multiplication", KARATSUBA_MUL, s_time_mul),
+ T_MUL_SQR("Karatsuba squaring", KARATSUBA_SQR, s_time_sqr),
+ T_MUL_SQR("Toom-Cook 3-way multiplying", TOOM_MUL, s_time_mul),
+ T_MUL_SQR("Toom-Cook 3-way squaring", TOOM_SQR, s_time_sqr),
+#undef T_MUL_SQR
+ };
+ /* Turn all limits from bncore.c to the max */
+ set_cutoffs(&max_cutoffs);
+ for (n = 0; n < sizeof(test)/sizeof(test[0]); ++n) {
+ if (test[n].fn) {
+ s_run(test[n].name, test[n].fn, test[n].cutoff);
+ *test[n].update = *test[n].cutoff;
+ *test[n].cutoff = INT_MAX;
+ }
+ }
+ }
+ if (args.terse == 1) {
+ printf("%d %d %d %d\n",
+ updated.KARATSUBA_MUL,
+ updated.KARATSUBA_SQR,
+ updated.TOOM_MUL,
+ updated.TOOM_SQR);
+ } else {
+ printf("KARATSUBA_MUL_CUTOFF = %d\n", updated.KARATSUBA_MUL);
+ printf("KARATSUBA_SQR_CUTOFF = %d\n", updated.KARATSUBA_SQR);
+ printf("TOOM_MUL_CUTOFF = %d\n", updated.TOOM_MUL);
+ printf("TOOM_SQR_CUTOFF = %d\n", updated.TOOM_SQR);
+ }
+
+ if (args.print == 1) {
+ printf("Printing data for graphing to \"%s\" and \"%s\"\n",mullog, sqrlog);
+
+ multiplying = fopen(mullog, "w+");
+ if (multiplying == NULL) {
+ fprintf(stderr, "Opening file \"%s\" failed\n", mullog);
+ exit(EXIT_FAILURE);
+ }
+
+ squaring = fopen(sqrlog, "w+");
+ if (squaring == NULL) {
+ fprintf(stderr, "Opening file \"%s\" failed\n",sqrlog);
+ exit(EXIT_FAILURE);
+ }
+
+ for (x = 8; x < args.upper_limit_print; x += args.increment_print) {
+ set_cutoffs(&max_cutoffs);
+ t1 = s_time_mul(x);
+ set_cutoffs(&orig);
+ t2 = s_time_mul(x);
+ fprintf(multiplying, "%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1);
+ fflush(multiplying);
+ if (args.verbose == 1) {
+ printf("MUL %d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1);
+ fflush(stdout);
+ }
+ set_cutoffs(&max_cutoffs);
+ t1 = s_time_sqr(x);
+ set_cutoffs(&orig);
+ t2 = s_time_sqr(x);
+ fprintf(squaring,"%d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1);
+ fflush(squaring);
+ if (args.verbose == 1) {
+ printf("SQR %d: %9"PRIu64" %9"PRIu64", %9"PRIi64"\n", x, t1, t2, (int64_t)t2 - (int64_t)t1);
+ fflush(stdout);
+ }
+ }
+ printf("Finished. Data for graphing in \"%s\" and \"%s\"\n",mullog, sqrlog);
+ if (args.verbose == 1) {
+ set_cutoffs(&orig);
+ if (args.terse == 1) {
+ printf("%d %d %d %d\n",
+ KARATSUBA_MUL_CUTOFF,
+ KARATSUBA_SQR_CUTOFF,
+ TOOM_MUL_CUTOFF,
+ TOOM_SQR_CUTOFF);
+ } else {
+ printf("KARATSUBA_MUL_CUTOFF = %d\n", KARATSUBA_MUL_CUTOFF);
+ printf("KARATSUBA_SQR_CUTOFF = %d\n", KARATSUBA_SQR_CUTOFF);
+ printf("TOOM_MUL_CUTOFF = %d\n", TOOM_MUL_CUTOFF);
+ printf("TOOM_SQR_CUTOFF = %d\n", TOOM_SQR_CUTOFF);
+ }
+ }
+ }
+ exit(EXIT_SUCCESS);
+}
diff --git a/third_party/heimdal/lib/hcrypto/libtommath/etc/tune_it.sh b/third_party/heimdal/lib/hcrypto/libtommath/etc/tune_it.sh
new file mode 100755
index 0000000..5e0fe7c
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/libtommath/etc/tune_it.sh
@@ -0,0 +1,107 @@
+#!/bin/sh
+
+die() {
+ echo "$1 failed"
+ echo "Exiting"
+ exit $2
+}
+# A linear congruential generator is sufficient for the purpose.
+SEED=3735928559
+LCG() {
+ SEED=$(((1103515245 * $SEED + 12345) % 2147483648))
+ echo $SEED
+}
+median() {
+# read everything besides the header from file $1
+# | cut-out the required column $2
+# | sort all the entries numerically
+# | show only the first $3 entries
+# | show only the last entry
+ tail -n +2 $1 | cut -d' ' -f$2 | sort -n | head -n $3 | tail -n 1
+}
+
+MPWD=$(dirname $(readlink -f "$0"))
+FILE_NAME="tuning_list"
+TOMMATH_CUTOFFS_H="$MPWD/../tommath_cutoffs.h"
+BACKUP_SUFFIX=".orig"
+RNUM=0
+
+#############################################################################
+# It would be a good idea to isolate these processes (with e.g.: cpuset) #
+# #
+# It is not a good idea to e.g: watch high resolution videos while this #
+# test are running if you do not have enough memory to avoid page faults. #
+#############################################################################
+
+# Number of rounds overall.
+LIMIT=100
+# Number of loops for each input.
+RLOOPS=10
+# Offset ( > 0 ) . Runs tests with asymmetric input of the form 1:OFFSET
+# Please use another destination for TOMMATH_CUTOFFS_H if you change OFFSET, because the numbers
+# with an offset different from 1 (one) are not usable as the general cut-off values
+# in "tommath_cutoffs.h".
+OFFSET=1
+# Number ( >= 3 ) of positive results (TC-is-faster) accumulated until it is accepted.
+# Due to the algorithm used to compute the median in this Posix compliant shell script
+# the value needs to be 3 (three), not less, to keep the variation small.
+LAG=3
+# Keep the temporary file $FILE_NAME. Set to 0 (zero) to remove it at the end.
+# The file is in a format fit to feed into R directly. If you do it and find the median
+# of this program to be off by more than a couple: please contact the authors and report
+# the numbers from this program and R and the standard deviation. This program is known
+# to get larger errors if the standard deviation is larger than ~50.
+KEEP_TEMP=1
+
+echo "You might like to watch the numbers go up to $LIMIT but it will take a long time!"
+
+# Might not have sufficient rights or disc full.
+echo "km ks tc3m tc3s" > $FILE_NAME || die "Writing header to $FILE_NAME" $?
+i=1
+while [ $i -le $LIMIT ]; do
+ RNUM=$(LCG)
+ printf "\r%d" $i
+ "$MPWD"/tune -t -r $RLOOPS -L $LAG -S "$RNUM" -o $OFFSET >> $FILE_NAME || die "tune" $?
+ i=$((i + 1))
+done
+
+if [ $KEEP_TEMP -eq 0 ]; then
+ rm -v $FILE_NAME || die "Removing $KEEP_TEMP" $?
+fi
+
+echo "Writing cut-off values to \"$TOMMATH_CUTOFFS_H\"."
+echo "In case of failure: a copy of \"$TOMMATH_CUTOFFS_H\" is in \"$TOMMATH_CUTOFFS_H$BACKUP_SUFFIX\""
+
+cp -v $TOMMATH_CUTOFFS_H $TOMMATH_CUTOFFS_H$BACKUP_SUFFIX || die "Making backup copy of $TOMMATH_CUTOFFS_H" $?
+
+cat << END_OF_INPUT > $TOMMATH_CUTOFFS_H || die "Writing header to $TOMMATH_CUTOFFS_H" $?
+/* LibTomMath, multiple-precision integer library -- Tom St Denis */
+/* SPDX-License-Identifier: Unlicense */
+/*
+ Current values evaluated on an AMD A8-6600K (64-bit).
+ Type "make tune" to optimize them for your machine but
+ be aware that it may take a long time. It took 2:30 minutes
+ on the aforementioned machine for example.
+ */
+END_OF_INPUT
+
+# The Posix shell does not offer an array data type so we create
+# the median with 'standard tools'^TM
+
+# read the file (without the first line) and count the lines
+i=$(tail -n +2 $FILE_NAME | wc -l)
+# our median point will be at $i entries
+i=$(( (i / 2) + 1 ))
+TMP=$(median $FILE_NAME 1 $i)
+echo "#define MP_DEFAULT_KARATSUBA_MUL_CUTOFF $TMP"
+echo "#define MP_DEFAULT_KARATSUBA_MUL_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(km) Appending to $TOMMATH_CUTOFFS_H" $?
+TMP=$(median $FILE_NAME 2 $i)
+echo "#define MP_DEFAULT_KARATSUBA_SQR_CUTOFF $TMP"
+echo "#define MP_DEFAULT_KARATSUBA_SQR_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(ks) Appending to $TOMMATH_CUTOFFS_H" $?
+TMP=$(median $FILE_NAME 3 $i)
+echo "#define MP_DEFAULT_TOOM_MUL_CUTOFF $TMP"
+echo "#define MP_DEFAULT_TOOM_MUL_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(tc3m) Appending to $TOMMATH_CUTOFFS_H" $?
+TMP=$(median $FILE_NAME 4 $i)
+echo "#define MP_DEFAULT_TOOM_SQR_CUTOFF $TMP"
+echo "#define MP_DEFAULT_TOOM_SQR_CUTOFF $TMP" >> $TOMMATH_CUTOFFS_H || die "(tc3s) Appending to $TOMMATH_CUTOFFS_H" $?
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-09 09:30:02 +0000