X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/5dd5f9ec28f304ca377c42fd7f711d6cf12b90e1..5c19dc3ae3bd8e40a9c028b0deddd50ff337692c:/OSX/libsecurity_cryptkit/lib/CurveParamDocs/fmodule.c?ds=inline diff --git a/OSX/libsecurity_cryptkit/lib/CurveParamDocs/fmodule.c b/OSX/libsecurity_cryptkit/lib/CurveParamDocs/fmodule.c new file mode 100644 index 00000000..492b33b3 --- /dev/null +++ b/OSX/libsecurity_cryptkit/lib/CurveParamDocs/fmodule.c @@ -0,0 +1,410 @@ +/************************************************************** + * + * fmodule.c + * + * Factoring utilities. + * + * Updates: + * 13 Apr 98 REC - creation + * + * c. 1998 Perfectly Scientific, Inc. + * All Rights Reserved. + * + * + *************************************************************/ + +/* include files */ + +#include +#include +#include +#include +#ifdef _WIN32 + +#include + +#endif + +#include +#include "giants.h" +#include "fmodule.h" +#include "ellmont.h" + +#define NUM_PRIMES 6542 /* PrimePi[2^16]. */ +#define GENERAL_MOD 0 +#define FERMAT_MOD 1 +#define MERSENNE_MOD (-1) +#define D 100 /* A decimation parameter for stage-2 ECM factoring. */ + +/* compiler options */ + +#ifdef _WIN32 +#pragma warning( disable : 4127 4706 ) /* disable conditional is constant warning */ +#endif + + +/* global variables */ + +extern int pr[NUM_PRIMES]; /* Primes array from tools.c. */ + +unsigned short factors[NUM_PRIMES], exponents[NUM_PRIMES]; +int modmode = GENERAL_MOD; +int curshorts = 0; +static giant t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL; +static giant An = NULL, Ad = NULL; +static point_mont pt1, pt2; +point_mont pb[D+2]; +giant xzb[D+2]; + +static int verbosity = 0; + +/************************************************************** + * + * Functions + * + **************************************************************/ + +int +init_fmodule(int shorts) { + curshorts = shorts; + pb[0] = NULL; /* To guarantee proper ECM initialization. */ + t1 = newgiant(shorts); + t2 = newgiant(shorts); + t3 = newgiant(shorts); + t4 = newgiant(shorts); + An = newgiant(shorts); + Ad = newgiant(shorts); + pt1 = new_point_mont(shorts); + pt2 = new_point_mont(shorts); +} + +void +verbose(int state) +/* Call verbose(1) for output during factoring processes, + call verbose(0) to silence all that. + */ +{ + verbosity = state; +} + +void +dot(void) +{ + printf("."); + fflush(stdout); +} + +void +set_mod_mode(int mode) +/* Call this with mode := 1, 0, -1, for Fermat-mod, general mod, and Mersenne mod, + respectively; the point being that the special cases of + Fermat- and Mersenne-mod are much faster than + general mod. If all mods will be with respect to a number-to-be-factored, + of the form N = 2^m + 1, use Fermat mod; while if N = 2^m-1, use Mersenne mod. + */ +{ + modmode = mode; +} + +void +special_modg( + giant N, + giant t +) +{ + switch (modmode) + { + case MERSENNE_MOD: + mersennemod(bitlen(N), t); + break; + case FERMAT_MOD: + fermatmod(bitlen(N)-1, t); + break; + default: + modg(N, t); + break; + } +} + +unsigned short * +prime_list() { + return(&factors[0]); +} + +unsigned short * +exponent_list() { + return(&exponents[0]); +} + +int +sieve(giant N, int sievelim) +/* Returns number of N's prime factors < min(sievelim, 2^16), + with N reduced accordingly by said factors. + The n-th entry of factors[] becomes the n-th prime + factor of N, with corresponding exponent + becoming the n-th element of exponents[]. + */ +{ int j, pcount, rem; + unsigned short pri; + + pcount = 0; + exponents[0] = 0; + for (j=0; j < NUM_PRIMES; j++) + { + pri = pr[j]; + if(pri > sievelim) break; + do { + gtog(N, t1); + rem = idivg(pri, t1); + if(rem == 0) { + ++exponents[pcount]; + gtog(t1, N); + } + } while(rem == 0); + if(exponents[pcount] > 0) { + factors[pcount] = pr[j]; + ++pcount; + exponents[pcount] = 0; + } + } + return(pcount); +} + +int +pollard_rho(giant N, giant fact, int steps, int abort) +/* Perform Pollard-rho x:= 3; loop(x:= x^2 + 2), a total of steps times. + Parameter fact will be a nontrivial factor found, in which case + N is also modified as: N := N/fact. + The function returns 0 if no nontrivial factor found, else returns 1. + The abort parameter, when set, causes the factorer to exit on the + first nontrivial factor found (the requisite GCD is checked + every 1000 steps). If abort := 0, the full number + of steps are always performed, then one solitary GCD is taken, + before exit. + */ +{ + int j, found = 0; + + itog(3, t1); + gtog(t1, t2); + itog(1, fact); + for(j=0; j < steps; j++) { + squareg(t1); iaddg(2, t1); special_modg(N, t1); + squareg(t2); iaddg(2, t2); special_modg(N, t2); + squareg(t2); iaddg(2, t2); special_modg(N, t2); + gtog(t2, t3); subg(t1,t3); mulg(t3, fact); special_modg(N, fact); + if(((j % 1000 == 999) && abort) || (j == steps-1)) { + if(verbosity) dot(); + gcdg(N, fact); + if(!isone(fact)) { + found = (gcompg(N, fact) == 0) ? 0 : 1; + break; + } + } + } + if(verbosity) { printf("\n"); fflush(stdout); } + if(found) { + divg(fact, N); + return(1); + } + itog(1, fact); + return(0); +} + +int +pollard_pminus1(giant N, giant fact, int lim, int abort) +/* Perform Pollard-(p-1); where we test + + GCD[N, 3^P - 1], + + where P is an accumulation of primes <= min(lim, 2^16), + to appropriate powers. + Parameter fact will be a nontrivial factor found, in which case + N is also modified as: N := N/fact. + The function returns 0 if no nontrivial factor found, else returns 1. + The abort parameter, when set, causes the factorer to exit on the + first nontrivial factor found (the requisite GCD is checked + every 100 steps). If abort := 0, the full number + of steps are always performed, then one solitary GCD is taken, + before exit. + */ +{ int cnt, j, k, pri, found = 0; + + itog(3, fact); + for (j=0; j< NUM_PRIMES; j++) + { + pri = pr[j]; + if((pri > lim) || (j == NUM_PRIMES-1) || (abort && (j % 100 == 99))) { + if(verbosity) dot(); + gtog(fact, t1); + itog(1, t2); + subg(t2, t1); + special_modg(N, t1); + gcdg(N, t1); + if(!isone(t1)) { + found = (gcompg(N, t1) == 0) ? 0 : 1; + break; + } + if(pri > lim) break; + } + if(pri < 19) { cnt = 20-pri; /* Smaller primes get higher powers. */ + } else if(pri < 100) { + cnt = 2; + } else cnt = 1; + for (k=0; k< cnt; k++) + { + powermod(fact, pri, N); + } + } + if(verbosity) { printf("\n"); fflush(stdout); } + if(found) { + gtog(t1, fact); + divg(fact, N); + return(1); + } + itog(1, fact); + return(0); +} + +int +ecm(giant N, giant fact, int S, unsigned int B, unsigned int C) +/* Perform elliptic curve method (ECM), with: + Brent seed parameter = S + Stage-one limit = B + Stage-two limit = C + This function: + returns 1 if nontrivial factor is found in stage 1 of ECM; + returns 2 if nontrivial factor is found in stage 2 of ECM; + returns 0 otherwise. + In the positive return, parameter fact is the factor and N := N/fact. + */ +{ unsigned int pri, q; + int j, cnt, count, k; + + if(verbosity) { + printf("Finding curve and point, B = %u, C = %u, seed = %d...", B, C, S); + fflush(stdout); + } + find_curve_point_brent(pt1, S, An, Ad, N); + if(verbosity) { + printf("\n"); + printf("Commencing stage 1 of ECM...\n"); + fflush(stdout); + } + + q = pr[NUM_PRIMES-1]; + count = 0; + for(j=0; ; j++) { + if(j < NUM_PRIMES) { + pri = pr[j]; + } else { + q += 2; + if(primeq(q)) pri = q; + else continue; + } + if(verbosity) if((++count) % 100 == 0) dot(); + if(pri > B) break; + if(pri < 19) { cnt = 20-pri; + } else if(pri < 100) { + cnt = 2; + } else cnt = 1; + for(k = 0; k < cnt; k++) + ell_mul_int_brent(pt1, pri, An, Ad, N); + } + k = 19; + while (kz, fact); + gcdg(N, fact); + if((!isone(fact)) && (gcompg(N, fact) != 0)) { + divg(fact, N); + return(1); + } + if(B >= C) { /* No stage 2 planned. */ + itog(1, fact); + return(0); + } + +/* Commence second stage of ECM. */ + if(verbosity) { + printf("\n"); + printf("Commencing stage 2 of ECM...\n"); + fflush(stdout); + } + if(pb[0] == NULL) { + for(k=0; k < D+2; k++) { + pb[k] = new_point_mont(curshorts); + xzb[k] = newgiant(curshorts); + + } + } + k = ((int)B)/D; + ptop_mont(pt1, pb[0]); + ell_mul_int_brent(pb[0], k*D+1 , An, Ad, N); + ptop_mont(pt1, pb[D+1]); + ell_mul_int_brent(pb[D+1], (k+2)*D+1 , An, Ad, N); + + for (j=1; j <= D; j++) + { + ptop_mont(pt1, pb[j]); + ell_mul_int_brent(pb[j], 2*j , An, Ad, N); + gtog(pb[j]->z, xzb[j]); + mulg(pb[j]->x, xzb[j]); + special_modg(N, xzb[j]); + } + itog(1, fact); + count = 0; + while (1) { + if(verbosity) if((++count) % 10 == 0) dot(); + gtog(pb[0]->z, xzb[0]); + mulg(pb[0]->x, xzb[0]); + special_modg(N, xzb[0]); + mulg(pb[0]->z, fact); + special_modg(N, fact); /* Accumulate. */ + for (j = 1; j < D; j++) { + if (!primeq(k*D+1+2*j)) continue; +/* Next, accumulate (xa - xb)(za + zb) - xa za + xb zb. */ + gtog(pb[0]->x, t1); + subg(pb[j]->x, t1); + gtog(pb[0]->z, t2); + addg(pb[j]->z, t2); + mulg(t1, t2); + special_modg(N, t1); + subg(xzb[0], t2); + addg(xzb[j], t2); + special_modg(N, t2); + mulg(t2, fact); + special_modg(N, fact); + } + k += 2; + if(k*D > C) + break; + ptop_mont(pb[D+1], pt2); + ell_odd_brent(pb[D], pb[D+1], pb[0], N); + ptop_mont(pt2, pb[0]); + } + if(verbosity) { printf("\n"); fflush(stdout); } + + gcdg(N, fact); + if((!isone(fact)) && (gcompg(N, fact) != 0)) { + divg(fact, N); + return(2); /* Return value of 2 for stage-2 success! */ + } + itog(1, fact); + return(0); +} + +