1/*
2 * atomTime.c - measure performance of mulg, gsquare, feemod,
3 * gshift{left,right}, elliptic, ellMulProj
4 */
5
6#include "ckconfig.h"
7#include "ckutilsPlatform.h"
8#include "CryptKitSA.h"
9#include "ckutilities.h"		/* needs private headers */
10#include "curveParams.h"		/* ditto */
11#include "falloc.h"				/* ditto */
12#include "elliptic.h"
13#include "ellipticProj.h"
14#include <stdlib.h>
15#include <stdio.h>
16#include <time.h>
17
18/* default loops for "fast" and "slow" ops respecitively */
19#define LOOPS_DEF_FAST	10000
20#define LOOPS_DEF_SLOW	100
21
22#define NUM_BORROW	100
23
24/* individual enables - normally all on, disable to zero in on one test */
25#define MULG_ENABLE	    1
26#define GSQUARE_ENABLE	    1
27#define FEEMOD_ENABLE	    1
28#define BORROW_ENABLE	    1
29#define	SHIFT_ENABLE	    1
30#define BINVAUX_ENABLE	    1
31#define MAKE_RECIP_ENABLE   1
32#define MODGRECIP_ENABLE    1
33#define KEYGEN_ENABLE	    1
34#define ELLIPTIC_ENABLE	    1
35#define ELL_SIMPLE_ENABLE   1
36
37static void usage(char **argv)
38{
39	printf("Usage: %s [l=loops_fast] [L=loops_slow] [q(uick)] [D=depth]\n", argv[0]);
40	exit(1);
41}
42
43/*
44 * Fill numGiants with random data of length bits.
45 */
46static void genRandGiants(giant *giants,
47	unsigned numGiants,
48	unsigned bits,
49	feeRand rand)
50{
51	int i;
52	giant g;
53	unsigned char *rdata;
54	unsigned bytes = (bits + 7) / 8;
55	giantDigit mask = 0;
56	unsigned giantMsd = 0;	// index of MSD
57	unsigned log2BitsPerDigit;
58	unsigned bitsPerDigit;
59
60	/* just to satisfy compiler - make sure it's always called */
61	if(giants == NULL) {
62	    return;
63	}
64
65	log2BitsPerDigit = GIANT_LOG2_BITS_PER_DIGIT;
66	bitsPerDigit = GIANT_BITS_PER_DIGIT;
67
68	if((bits & 7) != 0) {
69		/*
70		 * deserializeGiant() has a resolution of one byte. We
71		 * need more resolution - that is, we'll be creating
72		 * giants a little larger than we need, and we'll mask off
73		 * some bits in the giants' m.s. digit.
74		 * This assumes that data fills the giantDigits such
75		 * that if bytes mod GIANT_BYTES_PER_DIGIT != 0, the
76		 * empty byte(s) in the MSD are in the m.s. byte(s).
77		 */
78		giantMsd = bits >> log2BitsPerDigit;
79		mask = (1 << (bits & (bitsPerDigit - 1))) - 1;
80	}
81	rdata = fmalloc(bytes);
82	for(i=0; i<numGiants; i++) {
83		g = giants[i];
84		feeRandBytes(rand, rdata, bytes);
85		deserializeGiant(rdata, g, bytes);
86		if(mask != 0) {
87			int j;
88
89		        g->n[giantMsd] &= mask;
90
91			/*
92			 * We've zeroed out some bits; we might have to
93			 * adjust the sign of the giant as well. Note that
94			 * deserializeGiant always yields positive
95			 * giants....
96			 */
97			for(j=(g->sign - 1); j!=0; j--) {
98			    if(g->n[j] == 0) {
99				(g->sign)--;
100			    }
101			    else {
102				break;
103			    }
104			}
105		}
106	}
107	ffree(rdata);
108	return;
109}
110
111#if	CRYPTKIT_ELL_PROJ_ENABLE
112/*
113 * Assumes the presence of numEllPoints items in *points, and that the
114 * x coordinate in each point is init'd to a random giant. Uses the x
115 * coords as seeds to make normalized points of the entire *points array.
116 */
117static void makePoints(pointProjStruct *points,
118	unsigned numEllPoints,
119	curveParams *cp)
120{
121	int i;
122	giant seed = newGiant(cp->maxDigits);
123
124	for(i=0; i<numEllPoints; i++) {
125		gtog(points[i].x, seed);
126		findPointProj(&points[i], seed, cp);
127	}
128	freeGiant(seed);
129}
130
131#endif	/* CRYPTKIT_ELL_PROJ_ENABLE */
132
133int main(int argc, char **argv)
134{
135	int 		arg;
136	char 		*argp;
137	unsigned 	loopsFast = LOOPS_DEF_FAST;
138	unsigned	loopsSlow = LOOPS_DEF_SLOW;
139	unsigned	maxLoops;
140	unsigned	depth;
141	feeRand 	rand;
142	giant 		*giants;
143	unsigned 	seed;
144	int		i;
145	int		j;
146	PLAT_TIME	startTime;
147	PLAT_TIME	endTime;
148	double		elapsed;
149	unsigned	numGiants;
150	#if CRYPTKIT_ELL_PROJ_ENABLE
151	unsigned	numEllGiants;		// for elliptic ops
152	unsigned	numEllPoints;		// for elliptic ops
153	#endif
154	curveParams	*cp;
155	unsigned	quick = 0;
156	unsigned	minDepth = 0;
157	unsigned	maxDepth = FEE_DEPTH_MAX;
158	unsigned	basePrimeLen;
159	int		*shiftCnt;
160	char		*curveType;
161	#if CRYPTKIT_ELL_PROJ_ENABLE
162	pointProjStruct	*points;
163	#endif
164	giant		z = NULL;
165	giant		modGiant = NULL;
166	giant		recip = NULL;
167	feePubKey	*keyArray = NULL;
168	giant		gborrow[NUM_BORROW];
169
170    	/* just to satisfy compiler - make sure it's always called */
171	genRandGiants(NULL, 0, 0, 0);
172
173	for(arg=1; arg<argc; arg++) {
174		argp = argv[arg];
175		switch(argp[0]) {
176		    case 'l':
177		    	loopsFast = atoi(&argp[2]);
178			break;
179		    case 'L':
180		    	loopsSlow = atoi(&argp[2]);
181			break;
182		    case 'q':
183		    	quick = 1;
184			break;
185		    case 'D':
186		    	minDepth = maxDepth = atoi(&argp[2]);
187			break;
188		    default:
189		    	usage(argv);
190			break;
191		}
192	}
193
194	/*
195	 * Common random generator
196	 */
197	time((unsigned long *)&seed);
198	rand = feeRandAllocWithSeed(seed);
199
200	maxLoops = loopsFast;
201	if(loopsSlow > maxLoops) {
202	    maxLoops = loopsSlow;
203	}
204
205	/*
206	 * Alloc array of giants big enough for squaring at the largest
207	 * key size, enough of them for 'loops' mulgs
208	 */
209	cp = curveParamsForDepth(FEE_DEPTH_LARGEST);
210	numGiants = maxLoops * 2;			// 2 giants per loop
211	if(loopsSlow > (maxLoops / 4)) {
212	    /* findPointProj needs 4 giants per loop */
213	    numGiants *= 4;
214	}
215	#if CRYPTKIT_ELL_PROJ_ENABLE
216	numEllGiants = loopsSlow * 2;
217	numEllPoints = loopsSlow * 2;
218	#endif
219	giants = fmalloc(numGiants * sizeof(giant));
220	if(giants == NULL) {
221		printf("malloc failure\n");
222		exit(1);
223	}
224	for(i=0; i<numGiants; i++) {
225		giants[i] = newGiant(cp->maxDigits);
226		if(giants[i] == NULL) {
227			printf("malloc failure\n");
228			exit(1);
229		}
230	}
231	freeCurveParams(cp);
232
233	#if CRYPTKIT_ELL_PROJ_ENABLE
234	/*
235	 * Projective points - two per ellLoop. The giants come from
236	 * giants[]. We reserve an extra giant per point.
237	 * We're assuming that numEllPoints < (4 * numGiants).
238	 */
239	points = fmalloc(numEllPoints * sizeof(pointProjStruct));
240	if(points == NULL) {
241		printf("malloc failure\n");
242		exit(1);
243	}
244	j=0;
245	for(i=0; i<numEllPoints; i++) {
246		points[i].x = giants[j++];
247		points[i].y = giants[j++];
248		points[i].z = giants[j++];
249		j++;				// skip a giant
250	}
251	#endif
252
253	/* feePubKey array */
254	keyArray = fmalloc(sizeof(feePubKey) * loopsSlow);
255	if(keyArray == NULL) {
256		printf("malloc failure\n");
257		exit(1);
258	}
259
260	/*
261	 * Alloc an array of shiftCnt ints
262	 */
263	shiftCnt = fmalloc(maxLoops * sizeof(int));
264	if(shiftCnt == NULL) {
265		printf("malloc failure\n");
266		exit(1);
267	}
268
269	for(depth=minDepth; depth<=maxDepth; depth++) {
270
271		if(quick) {
272		    if((depth != FEE_DEPTH_127M) &&
273		       (depth != FEE_DEPTH_161W)) {
274		       	continue;
275		    }
276		}
277
278		/*
279		 * Get curve params for this depth
280	 	 */
281		cp = curveParamsForDepth(depth);
282		if(cp == NULL) {
283			printf("malloc failure\n");
284			exit(1);
285		}
286		switch(cp->curveType) {
287		    case FCT_Montgomery:
288		    	curveType = "FCT_Montgomery";
289			break;
290		    case FCT_Weierstrass:
291			curveType = "FCT_Weierstrass";
292			break;
293		    case FCT_General:
294		    	curveType = "FCT_General";
295			break;
296		    default:
297		    	printf("***Unknown curveType!\n");
298			exit(1);
299		}
300
301		switch(cp->primeType) {
302		    case FPT_General:
303		    	printf("depth=%d; FPT_General, %s; keysize=%d;\n",
304				depth, curveType, bitlen(cp->basePrime));
305			break;
306		    case FPT_Mersenne:
307			printf("depth=%d; FPT_Mersenne, %s; q=%d\n",
308				depth, curveType, cp->q);
309			break;
310		    default:
311			printf("depth=%d; FPT_FEE, %s; q=%d k=%d\n",
312				depth, curveType, cp->q, cp->k);
313			break;
314		}
315		basePrimeLen = bitlen(cp->basePrime);
316
317		/*
318		 * mulg test
319		 * bitlen(giant) <= bitlen(basePrime);
320		 * giants[n+1] *= giants[n]
321		 */
322		#if	MULG_ENABLE
323		genRandGiants(giants, numGiants, basePrimeLen, rand);
324		PLAT_GET_TIME(startTime);
325		for(i=0; i<numGiants; i+=2) {
326			mulg(giants[i], giants[i+1]);
327		}
328		PLAT_GET_TIME(endTime);
329		elapsed = PLAT_GET_NS(startTime, endTime);
330		printf("   mulg:             %12.2f ns per op\n",
331			elapsed / (numGiants / 2));
332		#endif	/* MULG_ENABLE */
333
334		/*
335		 * gsquare test
336		 * bitlen(giant) <= bitlen(basePrime);
337		 * gsquare(giants[n])
338		 */
339		#if	GSQUARE_ENABLE
340		genRandGiants(giants, numGiants, basePrimeLen, rand);
341		PLAT_GET_TIME(startTime);
342		for(i=0; i<loopsFast; i++) {
343			gsquare(giants[i]);
344		}
345		PLAT_GET_TIME(endTime);
346		elapsed = PLAT_GET_NS(startTime, endTime);
347		printf("   gsquare:          %12.2f ns per op\n", elapsed / loopsFast);
348		#endif	/* GSQUARE_ENABLE */
349
350		/*
351		 * feemod test
352		 * bitlen(giant) <= ((2 * bitlen(basePrime) - 2);
353		 * feemod(giants[n])
354		 */
355		#if	FEEMOD_ENABLE
356		genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2,
357			rand);
358		PLAT_GET_TIME(startTime);
359		for(i=0; i<loopsFast; i++) {
360			feemod(cp, giants[i]);
361		}
362		PLAT_GET_TIME(endTime);
363		elapsed = PLAT_GET_NS(startTime, endTime);
364		printf("   feemod:           %12.2f ns per op\n", elapsed / loopsFast);
365		#endif	/* FEEMOD_ENABLE */
366
367
368		/*
369		 * borrowGiant test
370		 */
371		#if	BORROW_ENABLE
372		PLAT_GET_TIME(startTime);
373		for(i=0; i<loopsFast; i++) {
374		    for(j=0; j<NUM_BORROW; j++) {
375		    	gborrow[j] = borrowGiant(cp->maxDigits);
376		    }
377		    for(j=0; j<NUM_BORROW; j++) {
378		    	returnGiant(gborrow[j]);
379		    }
380		}
381		PLAT_GET_TIME(endTime);
382		elapsed = PLAT_GET_NS(startTime, endTime);
383		printf("   borrow/return:    %12.2f ns per op\n",
384			elapsed / (loopsFast * NUM_BORROW));
385		#endif	/* BORROW_ENABLE */
386
387		/*
388		 * shiftright test
389		 * bitlen(giant) <= bitlen(basePrime)
390		 * 0 <= shiftCnt <= bitlen(basePrime)
391		 * gshiftright(giants[i])
392		 */
393		#if	SHIFT_ENABLE
394		genRandGiants(giants, numGiants, basePrimeLen, rand);
395		for(i=0; i<loopsFast; i++) {
396			shiftCnt[i] = feeRandNextNum(rand) % basePrimeLen;
397		}
398		PLAT_GET_TIME(startTime);
399		for(i=0; i<loopsFast; i++) {
400			gshiftright(shiftCnt[i], giants[i]);
401		}
402		PLAT_GET_TIME(endTime);
403		elapsed = PLAT_GET_NS(startTime, endTime);
404		printf("   gshiftright:      %12.2f ns per op\n", elapsed / loopsFast);
405
406		/*
407		 * shiftleft test
408		 * bitlen(giant) <= bitlen(basePrime)
409		 * 1 <= shiftCnt <= bitlen(basePrime)
410		 * gshiftleft(giants[i]
411		 */
412		genRandGiants(giants, numGiants, basePrimeLen, rand);
413		PLAT_GET_TIME(startTime);
414		for(i=0; i<loopsFast; i++) {
415			gshiftright(shiftCnt[i], giants[i]);
416		}
417		PLAT_GET_TIME(endTime);
418		elapsed = PLAT_GET_NS(startTime, endTime);
419		printf("   gshiftleft:       %12.2f ns per op\n", elapsed / loopsFast);
420		#endif	/* SHIFT_ENABLE */
421
422		/*
423		 * binvaux test
424		 * bitlen(giant) <= bitlen(basePrime);
425		 * binvaux(basePrime, giants[n+1])
426		 */
427		#if	BINVAUX_ENABLE
428		genRandGiants(giants, loopsSlow, basePrimeLen, rand);
429		PLAT_GET_TIME(startTime);
430		for(i=0; i<loopsSlow; i++) {
431			binvaux(cp->basePrime, giants[i]);
432		}
433		PLAT_GET_TIME(endTime);
434		elapsed = PLAT_GET_US(startTime, endTime);
435		printf("   binvaux:          %12.2f us per op\n",
436			elapsed / loopsSlow);
437		#endif	/* BINVAUX_ENABLE */
438
439		/*
440		 * make_recip test
441		 * bitlen(giant) <= bitlen(basePrime);
442		 * make_recip(giants[n], giants[n+1]
443		 */
444		#if	MAKE_RECIP_ENABLE
445		genRandGiants(giants, numGiants, basePrimeLen, rand);
446		PLAT_GET_TIME(startTime);
447		for(i=0; i<loopsSlow*2; i+=2) {
448			make_recip(giants[i], giants[i+1]);
449		}
450		PLAT_GET_TIME(endTime);
451		elapsed = PLAT_GET_US(startTime, endTime);
452		printf("   make_recip:       %12.2f us per op\n",
453			elapsed / loopsSlow);
454		#endif	/* MAKE_RECIP_ENABLE */
455
456		/*
457		 * modg_via_recip test
458		 * bitlen(giant) <= ((2 * bitlen(basePrime) - 2);
459		 * bitlen(modGiant) <= bitlen(basePrime)
460		 * calc recip of modGiant
461		 * modg_via_recip(giants[i])
462		 */
463		#if	MODGRECIP_ENABLE
464		genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2,
465			rand);
466		modGiant = borrowGiant(cp->maxDigits);
467		recip = borrowGiant(cp->maxDigits);
468		genRandGiants(&modGiant, 1, basePrimeLen, rand);
469		make_recip(modGiant, recip);
470
471		PLAT_GET_TIME(startTime);
472		for(i=0; i<loopsSlow; i++) {
473			modg_via_recip(modGiant, recip, giants[i]);
474		}
475		PLAT_GET_TIME(endTime);
476		elapsed = PLAT_GET_NS(startTime, endTime);
477		printf("   modg_via_recip:   %12.2f ns per op\n",
478			elapsed / loopsSlow);
479		returnGiant(modGiant);
480		modGiant = NULL;
481		returnGiant(recip);
482		recip = NULL;
483		#endif	/* MODGRECIP_ENABLE */
484
485		/*
486		 * key generate test
487		 * keyArray[n] = feePubKeyAlloc();
488		 * feePubKeyInitFromPrivData(keyArray[n] );
489		 */
490		#if KEYGEN_ENABLE
491		PLAT_GET_TIME(startTime);
492		for(i=0; i<loopsSlow; i++) {
493		 	keyArray[i] = feePubKeyAlloc();
494			if(keyArray[i] == NULL) {
495				printf("malloc failure\n");
496				exit(1);
497			}
498			/* fixme how about some better seed data */
499		 	feePubKeyInitFromPrivDataDepth(keyArray[i],
500				(unsigned char *)"somePrivData",
501				12,
502				depth,
503				1);
504		}
505		PLAT_GET_TIME(endTime);
506		elapsed = PLAT_GET_US(startTime, endTime);
507		printf("   keygen:           %12.2f us per op\n",
508			elapsed / loopsSlow);
509		for(i=0; i<loopsSlow; i++) {
510			feePubKeyFree(keyArray[i]);
511		}
512		#endif	/* KEYGEN_ENABLE*/
513
514		/*
515		 * elliptic test
516		 * bitlen(giant) <= bitlen(basePrime);
517		 * {giants[n], 1} *=  giants[n+1]   (elliptic mult)
518		 */
519		#if ELLIPTIC_ENABLE
520		genRandGiants(giants, numGiants, basePrimeLen, rand);
521		z = borrowGiant(cp->maxDigits);
522		PLAT_GET_TIME(startTime);
523		for(i=0; i<loopsSlow; i+=2) {
524			/* superoptimized int_to_giant(1) */
525			z->n[0] = 1;
526			z->sign = 1;
527			elliptic(giants[i], z, giants[i+1], cp);
528		}
529		PLAT_GET_TIME(endTime);
530		elapsed = PLAT_GET_US(startTime, endTime);
531		printf("   elliptic:         %12.2f us per op\n",
532			elapsed / (loopsSlow / 2));
533		#endif	/* ELLIPTIC_ENABLE*/
534
535		/*
536		 * elliptic_simple test
537		 * bitlen(giant) <= bitlen(basePrime);
538		 * giants[n] *= giants[n+1] (elliptic mult)
539		 */
540		#if ELL_SIMPLE_ENABLE
541		genRandGiants(giants, numGiants, basePrimeLen, rand);
542		PLAT_GET_TIME(startTime);
543		for(i=0; i<loopsSlow*2; i+=2) {
544			elliptic_simple(giants[i], giants[i+1], cp);
545		}
546		PLAT_GET_TIME(endTime);
547		elapsed = PLAT_GET_US(startTime, endTime);
548		printf("   elliptic_simple:  %12.2f us per op\n",
549			elapsed / loopsSlow);
550		#endif	/* ELL_SIMPLE_ENABLE */
551
552		if(cp->curveType != FCT_Weierstrass) {
553			goto loopEnd;
554		}
555
556		#if CRYPTKIT_ELL_PROJ_ENABLE
557		/*
558		 * ellMulProj test
559		 * bitlen(giant) <= bitlen(basePrime);
560		 * point[n+1] = point[n] * giants[4n+3]
561		 *
562		 * note we're cooking up way more giants than we have to;
563		 * we really only need the x's and k's. But what the heck.
564		 */
565		genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
566		makePoints(points, numEllPoints, cp);
567		PLAT_GET_TIME(startTime);
568		for(i=0; i<loopsSlow; i+=2) {
569			ellMulProj(&points[i], &points[i+1],
570				giants[4*i+3], cp);
571		}
572		PLAT_GET_TIME(endTime);
573		elapsed = PLAT_GET_US(startTime, endTime);
574		printf("   ellMulProj:       %12.2f us per op\n",
575			elapsed / (loopsSlow / 2));
576
577		/*
578		 * ellMulProjSimple test
579		 * bitlen(giant) <= bitlen(basePrime);
580		 * point[n] *= giants[4n+3] (projective elliptic mult)
581		 */
582		genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
583		makePoints(points, numEllPoints, cp);
584		PLAT_GET_TIME(startTime);
585		for(i=0; i<loopsSlow; i++) {
586			ellMulProjSimple(&points[i], giants[4*i+3], cp);
587		}
588		PLAT_GET_TIME(endTime);
589		elapsed = PLAT_GET_US(startTime, endTime);
590		printf("   ellMulProjSimple: %12.2f us per op\n",
591			elapsed / loopsSlow);
592
593		/*
594		 * ellAddProj test
595		 * bitlen(giant) <= bitlen(basePrime);
596		 * point[n] += point[n+1] (projective elliptic add)
597		 */
598		genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
599		makePoints(points, numEllPoints, cp);
600		PLAT_GET_TIME(startTime);
601		for(i=0; i<loopsSlow; i+=2) {
602			ellAddProj(&points[i], &points[i+1], cp);
603		}
604		PLAT_GET_TIME(endTime);
605		elapsed = PLAT_GET_NS(startTime, endTime);
606		printf("   ellAddProj:       %12.2f ns per op\n",
607			elapsed / loopsSlow);
608
609		/*
610		 * ellDoubleProj test
611		 * bitlen(giant) <= bitlen(basePrime);
612		 * ellDoubleProj(point[n])
613		 */
614		genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
615		makePoints(points, numEllPoints, cp);
616		PLAT_GET_TIME(startTime);
617		for(i=0; i<loopsSlow; i++) {
618			ellDoubleProj(&points[i], cp);
619		}
620		PLAT_GET_TIME(endTime);
621		elapsed = PLAT_GET_NS(startTime, endTime);
622		printf("   ellDoubleProj:    %12.2f ns per op\n",
623			elapsed / loopsSlow);
624
625		/*
626		 * findPointProj test
627		 * bitlen(giant) <= bitlen(basePrime);
628		 * findPointProj(point[n], giants[4n+3])
629		 */
630		genRandGiants(giants, 4 * loopsSlow, basePrimeLen, rand);
631		PLAT_GET_TIME(startTime);
632		for(i=0; i<loopsSlow; i++) {
633			findPointProj(&points[i], giants[4*i + 3], cp);
634		}
635		PLAT_GET_TIME(endTime);
636		elapsed = PLAT_GET_US(startTime, endTime);
637		printf("   findPointProj:    %12.2f us per op\n",
638			elapsed / loopsSlow);
639
640		#endif	/* CRYPTKIT_ELL_PROJ_ENABLE */
641
642loopEnd:
643		freeCurveParams(cp);
644	}
645
646	feeRandFree(rand);
647	for(i=0; i<numGiants; i++) {
648		freeGiant(giants[i]);
649	}
650	ffree(giants);
651	if(z) {
652	    freeGiant(z);
653	}
654	if(recip) {
655	    freeGiant(recip);
656	}
657	if(modGiant) {
658	    freeGiant(modGiant);
659	}
660	return 0;
661}
662
663