bntest16.c

包含哈希,对称以及非对称的经典算法 包含经典事例

/*
 * Test driver for low-level bignum library (16-bit version).
 * This access the low-level library directly.  It is NOT an
 * example of how to program with the library normally!  By
 * accessing the library at a low level, it is possible to
 * exercise the smallest components and thus localize bugs
 * more accurately.  This is especially useful when writing
 * assembly-language primitives.
 *
 * This also does timing tests on modular exponentiation.
 * Modular exponentiation is so computationally expensive that
 * the fact that this code omits one level of interface glue
 * has no perceptible effect on the results.
 */
#if HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdio.h>
#if !NO_STDLIB_H
#include <stdlib.h>	/* For strtol */
#endif
#if !NO_STRING_H
#include <string.h>
#elif HAVE_STRINGS_H
#include <strings.h>
#endif
#if NEED_MEMORY_H
#include <memory.h>
#endif

#include "cputime.h"
#include "lbn16.h"

#include "kludge.h"

/* Work with up to 2048-bit numbers */
#define MAXBITS 2048
#define SIZE (MAXBITS/16 + 1)

/* Additive congruential random number generator, x[i] = x[i-24] + x[i-55] */
static BNWORD16 randp[55];
static BNWORD16 *randp1 = randp, *randp2 = randp+24;

static BNWORD16
rand16(void)
{
        if (++randp2 == randp+55) {
                randp2 = randp;
                randp1++;
        } else if (++randp1 == randp+55) {
                randp1 = randp;
        }

        return  *randp1 += *randp2;
}

/*
 * CRC-3_2: x^3_2+x^26+x^23+x^22+x^1_6+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1
 *
 * The additive congruential RNG is seeded with a single integer,
 * which is shuffled with a CRC polynomial to generate the initial
 * table values.  The Polynomial is the same size as the words being
 * used.
 *
 * Thus, in the various versions of this library, we actually use this
 * polynomial as-is, this polynomial mod x^17, and this polynomial with
 * the leading coefficient deleted and replaced with x^6_4.  As-is,
 * it's irreducible, so it has a long period.  Modulo x^17, it factors as
 * (x^4+x^3+x^2+x+1) * (x^12+x^11+x^8+x^7+x^6+x^5+x^4+x^3+1),
 * which still has a large enough period (4095) for the use it's put to.
 * With the leading coefficient moved up, it factors as
 * (x^50+x^49+x^48+x^47+x^46+x^43+x^41+x^40+x^38+x^37+x^36+x^35+x^34+x^33+
 *  x^31+x^30+x^29+x^28+x^27+x^25+x^23+x^18+x^1_6+x^15+x^14+x^13+x^11+x^9+
 *  x^8+x^7+x^6+x^5+x^3+x^2+1)*(x^11+x^10+x^9+x^5+x^4+x^3+1)*(x^3+x+1),
 * which definitely has a long enough period to serve for initialization.
 * 
 * The effort put into this PRNG is kind of unwarranted given the trivial
 * use it's being put to, but oh, well.  It does have the nice advantage
 * of producing numbers that are portable between platforms, so if there's
 * a problem with one platform, you can compare all the intermediate
 * results with another platform.
 */
#define POLY (BNWORD16)0x04c11db7

static void
srand16(BNWORD16 seed)
{
        int i, j;

        for (i = 0; i < 55; i++) {
                for (j = 0; j < 16; j++)
                        if (seed >> (16-1))
                                seed = (seed << 1) ^ POLY;
                        else
                                seed <<= 1;
                randp[i] = seed;
        }
        for (i = 0; i < 3*55; i ++)
                rand16();
}

static void
randnum(BNWORD16 *num, unsigned len)
{
        while (len--)
                BIGLITTLE(*--num,*num++) = rand16();
}

static void
bnprint16(BNWORD16 const *num, unsigned len)
{
        BIGLITTLE(num -= len, num += len);

        while (len--)
                printf("%0*lX", 16/4, (unsigned long)BIGLITTLE(*num++,*--num));
}

static void
bnput16(char const *prompt, BNWORD16 const *num, unsigned len)
{
        fputs(prompt, stdout);
        bnprint16(num, len);
        putchar('\n');
}

/*
 * One of our tests uses a known prime.  The following selections were
 * taken from the tables at the end of Hans Reisel's "Prime Numbers and
 * Computer Methods for Factorization", second edition - an excellent book.
 * (ISBN 0-8176-3743-5 ISBN 3-7643-3743-5)
 */
#if 0
/* P31=1839605 17620282 38179967 87333633 from the factors of 3^256+2^256 */
static unsigned char const prime[] = {
        0x17,0x38,0x15,0xBC,0x8B,0xBB,0xE9,0xEF,0x01,0xA9,0xFD,0x3A,0x01
};
#elif 0
/* P48=40554942 04557502 46193993 36199835 4279613_2 73199617 from the same */
static unsigned char const prime[] = {
        0x47,0x09,0x77,0x07,0xCF,0xFD,0xE1,0x54,0x3E,0x24,
        0xF7,0xF1,0x7A,0x3E,0x91,0x51,0xCC,0xC7,0xD4,0x01
};
#elif 0
/*
 * P75 = 450 55287640 97906895 47687014 5808213_2
 *  05219565 99525911 39967964 66003_258 91979521
 * from the factors of 4^128+3+128
 * (The "026" and "062" are to prevent a Bad String from appearing here.)
 */
static unsigned char const prime[] = {
	0xFF,0x00,0xFF,0x00,0xFF,0x01,0x06,0x4F,0xF8,0xED,
	0xA3,0x37,0x23,0x2A,0x04,0xEA,0xF9,0x5F,0x30,0x4C,
	0xAE,0xCD, 026,0x4E, 062,0x10,0x04,0x7D,0x0D,0x79,
	0x01
};
#else
/*
 * P75 = 664 85659796 45277755 9123_2190 67300940
 *  51844953 78793489 59444670 35675855 57440257
 * from the factors of 5^128+4^128
 * (The "026" is to prevent a Bad String from appearing here.)
 */
static unsigned char const prime[] = {
	0x01,0x78,0x4B,0xA5,0xD3,0x30,0x03,0xEB,0x73,0xE6,
	0x0F,0x4E,0x31,0x7D,0xBC,0xE2,0xA0,0xD4, 026,0x3F,
	0x3C,0xEA,0x1B,0x44,0xAD,0x39,0xE7,0xE5,0xAD,0x19,
	0x67,0x01
};
#endif

static int
usage(char const *name)
{
        fprintf(stderr, "Usage: %s [modbits [expbits [expbits2]]\n"
"With no arguments, just runs test suite.  If modbits is given, runs\n"
"quick validation test, then runs timing tests of modular exponentiation.\n"
"If expbits is given, it is used as an exponent size, otherwise it defaults\n"
"to the same as modbits.  If expbits2 is given it is used as the second\n"
"exponent size in the double-exponentiation tests, otherwise it defaults\n"
"to the same as expbits.  All are limited to %u bits.\n",
                name, (unsigned)MAXBITS);
        return 1;
}

int
main(int argc, char **argv)
{
	unsigned i, j, k, l, m;
	int z;
	BNWORD16 t, carry, borrow;
	BNWORD16 a[SIZE], b[SIZE], c[SIZE], d[SIZE];
	BNWORD16 e[SIZE], f[SIZE];
	long modbits = 0, expbits = 0, expbits2 = 0;
	char *p;
#define A BIGLITTLE((a+SIZE),a)
#define B BIGLITTLE((b+SIZE),b)
#define C BIGLITTLE((c+SIZE),c)
#define D BIGLITTLE((d+SIZE),d)
#define E BIGLITTLE((e+SIZE),e)
#define F BIGLITTLE((f+SIZE),f)
        static unsigned const smallprimes[] = {
                2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43
        };

        srand16(1);

        puts(BIGLITTLE("Big-endian machine","Little-endian machine"));

	/*
	 * Parse the command line.  The do{} loop is a dummy, to have
	 * something to break out of when done with the command line.
	 */
	do {
		if (argc <= 1)
			break;
                modbits = strtol(argv[1], &p, 0);
                if (modbits < 3 || modbits > MAXBITS || *p) {
                        fprintf(stderr, "Illegal modbits: \"%s\"\n", argv[1]);
                        return usage(argv[0]);
                }
		if (argc <= 2) {
			expbits2 = expbits = modbits;
			break;
		}
		expbits = strtol(argv[2], &p, 0);
		if (expbits < 3 || expbits > MAXBITS || *p) {
			fprintf(stderr, "Illegal expbits: \"%s\"\n", argv[2]);
			return usage(argv[0]);
		}
		if (argc <= 3) {
			expbits2 = expbits;
			break;
		}
		expbits2 = strtol(argv[3], &p, 0);
		if (expbits2 < 3 || expbits2 > MAXBITS || *p) {
			fprintf(stderr, "Illegal expbits2: \"%s\"\n", argv[3]);
			return usage(argv[0]);
		}
		if (argc <= 4)
			break;
		fprintf(stderr, "Unexpected fourth argument \"%s\"\n",
		        argv[4]);
		return usage(argv[0]);
	} while (0);

        /* B is a nice not-so-little prime */
        lbnInsertBigBytes_16(B, prime, 0, sizeof(prime));
        ((unsigned char *)c)[0] = 0;
        lbnInsertBigBytes_16(B, (unsigned char *)c, sizeof(prime), 1);
        lbnExtractBigBytes_16(B, (unsigned char *)c, 0, sizeof(prime)+1);
        i = (sizeof(prime)-1)/(16/8)+1;        /* Size of array in words */
        if (((unsigned char *)c)[0] ||
            memcmp(prime, (unsigned char *)c+1, sizeof(prime)) != 0)
        {
                printf("Input != output!:\n   ");
                for (k = 0; k < sizeof(prime); k++)
                        printf("%02X ", prime[k]);
                putchar('\n');
                for (k = 0; k < sizeof(prime)+1; k++)
                        printf("%02X ", ((unsigned char *)c)[k]);
                putchar('\n');
                bnput16("p = ", B, i);

        }

        /* Timing test code - only if requested on the command line */
	if (modbits) {
#if CLOCK_AVAIL
		timetype start, stop;
		unsigned long cursec, expsec, twoexpsec, dblexpsec;
		unsigned curms, expms, twoexpms, dblexpms;

		expsec = twoexpsec = dblexpsec = 0;
		expms = twoexpms = dblexpms = 0;
#endif

		lbnCopy_16(C,B,i);
		lbnSub1_16(C,i,1);        /* C is exponent: p-1 */

		puts("Testing modexp with a known prime.  "
		     "All results should be 1.");
		bnput16("p   = ", B, i);
		bnput16("p-1 = ", C, i);
		lbnTwoExpMod_16(A, C, i, B, i);
		bnput16("2^(p-1) mod p = ", A, i);
		for (j = 0; j < 10; j++) {
			randnum(A,i);
			(void)lbnDiv_16(D,A,i,B,i);

			bnput16("a = ", A, i);
			lbnExpMod_16(A, A, i, C, i, B, i);
			bnput16("a^(p-1) mod p = ", A, i);
		}

		printf("\n"
		       "Timing exponentiations modulo a %d-bit modulus, i.e.\n"
		       "2^<%d> mod <%d> bits, <%d>^<%d> mod <%d> bits and\n"
		       "<%d>^<%d> * <%d>^<%d> mod <%d> bits\n",
		       (int)modbits, (int)expbits, (int)modbits,
		       (int)modbits, (int)expbits, (int)modbits,
		       (int)modbits, (int)expbits, (int)modbits, (int)expbits2,
		       (int)modbits);

		i = ((int)modbits-1)/16+1;
		k = ((int)expbits-1)/16+1;
		l = ((int)expbits2-1)/16+1;
		for (j = 0; j < 25; j++) {
			randnum(A,i);        /* Base */
			randnum(B,k);        /* Exponent */
			randnum(C,i);        /* Modulus */
			randnum(D,i);        /* Base2 */
			randnum(E,l);        /* Exponent */
			/* Clip bases and mod to appropriate number of bits */
			t = ((BNWORD16)2<<((modbits-1)%16)) - 1;
			*(BIGLITTLE(A-i,A+i-1)) &= t;
			*(BIGLITTLE(C-i,C+i-1)) &= t;
			*(BIGLITTLE(D-i,D+i-1)) &= t;
			/* Make modulus large (msbit set) and odd (lsbit set) */
			*(BIGLITTLE(C-i,C+i-1)) |= (t >> 1) + 1;
			BIGLITTLE(C[-1],C[0]) |= 1;

			/* Clip exponent to appropriate number of bits */
			t = ((BNWORD16)2<<((expbits-1)%16)) - 1;
			*(BIGLITTLE(B-k,B+k-1)) &= t;
			/* Make exponent large (msbit set) */
			*(BIGLITTLE(B-k,B+k-1)) |= (t >> 1) + 1;
			/* The same for exponent 2 */
			t = ((BNWORD16)2<<((expbits2-1)%16)) - 1;
			*(BIGLITTLE(E-l,E+l-1)) &= t;
			*(BIGLITTLE(E-l,E+l-1)) |= (t >> 1) + 1;

			m = lbnBits_16(A, i);
			if (m > (unsigned)modbits) {
				bnput16("a = ", a, i);
				printf("%u bits, should be <= %d\n",
				       m, (int)modbits);
			}
			m = lbnBits_16(B, k);
			if (m != (unsigned)expbits) {
				bnput16("b = ", b, i);
				printf("%u bits, should be %d\n",
				       m, (int)expbits);
			}
			m = lbnBits_16(C, i);
			if (m != (unsigned)modbits) {
				bnput16("c = ", c, k);
				printf("%u bits, should be %d\n",
				       m, (int)modbits);
			}
			m = lbnBits_16(D, i);
			if (m > (unsigned)modbits) {
				bnput16("d = ", d, i);
				printf("%u bits, should be <= %d\n",
				       m, (int)modbits);
			}
			m = lbnBits_16(E, l);
			if (m != (unsigned)expbits2) {
				bnput16("e = ", e, i);
				printf("%u bits, should be %d\n",
				       m, (int)expbits2);
			}
#if CLOCK_AVAIL
			gettime(&start);
#endif
			lbnTwoExpMod_16(A, B, k, C, i);
#if CLOCK_AVAIL