home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / GERMTEST.C < prev    next >
C/C++ Source or Header  |  1996-01-31  |  7KB  |  302 lines
  1. /*
  2.  * germtest.c - Random Sophie Germain prime generator.
  3.  *
  4.  * Copyright (c) 1995  Colin Plumb.  All rights reserved.
  5.  * For licensing and other legal details, see the file legal.c.
  6.  *
  7.  * This generates random Sophie Germain primes using the command
  8.  * line as a seed value.  It uses George Marsaglia's "mother of all
  9.  * random number generators" to (using the command line as a seed)
  10.  * to pick the starting search value and then searches sequentially
  11.  * for the next Sophie Germain prime p (a prime such that q = (p-1)/2
  12.  * is also prime).
  13.  *
  14.  * This is a really good way to burn a lot of CPU cycles.
  15.  */
  16. #if HAVE_CONFIG_H
  17. #include "config.h"
  18. #endif
  19.  
  20. #include <stdio.h>
  21. #if !NO_STRING_H
  22. #include <string.h>
  23. #elif HAVE_STRINGS_H
  24. #include <strings.h>
  25. #endif
  26. #if NEED_MEMORY_H
  27. #include <memory.h>
  28. #endif
  29.  
  30. #include "bn.h"
  31. #include "germain.h"
  32. #include "sieve.h"
  33.  
  34. #include "cputime.h"
  35.  
  36. #define BNDEBUG 1
  37.  
  38. #include "bnprint.h"
  39. #define bndPut(prompt, bn) bnPrint(stdout, prompt, bn, "\n")
  40. #define bndPrintf printf
  41.  
  42. /*
  43.  * Generate random numbers according to George Marsaglia's
  44.  * Mother Of All Random Number Generators.  This has a
  45.  * period of 0x17768215025F82EA0378038A03A203CA7FFF,
  46.  * or decimal 2043908804452974490458343567652678881935359.
  47.  */
  48. static unsigned mstate[8];
  49. static unsigned mcarry;
  50. static unsigned mindex;
  51.  
  52. static unsigned
  53. mRandom(void)
  54. {
  55.     unsigned long t;
  56.  
  57.     t = mcarry +
  58.         mstate[ mindex     ] * 1941ul +
  59.         mstate[(mindex+1)&7] * 1860ul +
  60.         mstate[(mindex+2)&7] * 1812ul +
  61.         mstate[(mindex+3)&7] * 1776ul +
  62.         mstate[(mindex+4)&7] * 1492ul +
  63.         mstate[(mindex+5)&7] * 1215ul +
  64.         mstate[(mindex+6)&7] * 1066ul +
  65.         mstate[(mindex+7)&7] * 12013ul;
  66.     mcarry = (unsigned)(t >> 16);    /* 0 <= mcarry <= 0x5a87 */
  67.     mindex = (mindex-1) & 7;
  68.     return mstate[mindex] = (unsigned)(t & 0xffff);
  69. }
  70.  
  71. /*
  72.  * Initialize the RNG based on the given seed.
  73.  * A zero-length seed will produce pretty lousy numbers,
  74.  * but it will work.
  75.  */
  76. static void
  77. mSeed(unsigned char const *seed, unsigned len)
  78. {
  79.     unsigned i;
  80.  
  81.     for (i = 0; i < 8; i++)
  82.         mstate[i] = 0;
  83.     mcarry = 1;
  84.     while (len--) {
  85.         mcarry += *seed++;
  86.         (void)mRandom();
  87.     }
  88. }
  89.  
  90.  
  91. /*
  92.  * Generate a bignum of a specified length, with the given
  93.  * high and low 8 bits. "High" is merged into the high 8 bits of the
  94.  * number.  For example, set it to 0x80 to ensure that the number is
  95.  * exactly "bits" bits long (i.e. 2^(bits-1) <= bn < 2^bits).
  96.  * "Low" is merged into the low 8 bits.  For example, set it to
  97.  * 1 to ensure that you generate an odd number.  "High" is merged
  98.  * into the high bits; set it to 0x80 to ensure that the high bit
  99.  * is set in the returned value.
  100.  */
  101. static int
  102. genRandBn(struct BigNum *bn, unsigned bits, unsigned char high,
  103. unsigned char low, unsigned char const *seed, unsigned len)
  104. {
  105.     unsigned char buf[64];
  106.     unsigned bytes;
  107.     unsigned l = 0;    /* Current position */
  108.     unsigned i;
  109.  
  110.     bnSetQ(bn, 0);
  111.     mSeed(seed, len);
  112.  
  113.     bytes = (bits+7) / 8;    /* Number of bytes to use */
  114.  
  115.     for (i = 0; i < sizeof(buf); i++)
  116.         buf[i] = (unsigned char)mRandom();
  117.     buf[sizeof(buf)-1] |= low;
  118.  
  119.     while (bytes > sizeof(buf)) {
  120.         bytes -= sizeof(buf);
  121.         /* Merge in low half of high bits, if necessary */
  122.         if (bytes == 1 && (bits & 7))
  123.             buf[0] |= high << (bits & 7);
  124.         if (bnInsertBigBytes(bn, buf, l, sizeof(buf)) < 0)
  125.             return -1;
  126.         l += sizeof(buf);
  127.         for (i = 0; i < sizeof(buf); i++)
  128.             buf[i] = (unsigned char)mRandom();
  129.     }
  130.  
  131.     /* Do the final "bytes"-long section, using the tail bytes in buf */
  132.     /* Mask off excess high bits */
  133.     buf[sizeof(buf)-bytes] &= 255 >> (-bits & 7);
  134.     /* Merge in specified high bits */
  135.     buf[sizeof(buf)-bytes] |= high >> (-bits & 7);
  136.     if (bytes > 1 && (bits & 7))
  137.         buf[sizeof(buf)-bytes+1] |= high << (bits & 7);
  138.     /* Merge in the appropriate bytes of the buffer */
  139.     if (bnInsertBigBytes(bn, buf+sizeof(buf)-bytes, l, bytes) < 0)
  140.         return -1;
  141.     return 0;
  142. }
  143.  
  144. struct Progress {
  145.     FILE *f;
  146.     unsigned column;
  147.     unsigned wrap;
  148. };
  149.  
  150. /* Print a progress indicator, with line-wrap */
  151. static int
  152. genProgress(void *arg, int c)
  153. {
  154.     struct Progress *p = arg;
  155.     if (++p->column > p->wrap) {
  156.         putc('\n', p->f);
  157.         p->column = 1;
  158.     }
  159.     putc(c, p->f);
  160.     fflush(p->f);
  161.     return 0;
  162. }
  163.  
  164. static int
  165. genSophieGermain(struct BigNum *bn, unsigned bits,
  166.     unsigned char const *seed, unsigned len, FILE *f)
  167. {
  168. #if CLOCK_AVAIL
  169.     timetype start, stop;
  170.     unsigned long s;
  171. #endif
  172.     int i;
  173.     unsigned char s1[1024], s2[1024];
  174.     unsigned p1, p2;
  175.     struct BigNum step;
  176.     struct Progress progress;
  177.  
  178.     if (f)
  179.         fprintf(f, "Generating a %u-bit Sophie Germain prime with \"%.*s\"\n",
  180.             bits, (int)len, (char *)seed);
  181.     progress.f = f;
  182.     progress.column = 0;
  183.     progress.wrap = 78;
  184.  
  185.     /* Find p - choose a starting place */
  186.     if (genRandBn(bn, bits, 0xC0, 3, seed, len) < 0)
  187.         return -1;
  188. #if BNDEBUG /* DEBUG - check that sieve works properly */
  189.     bnBegin(&step);
  190.     bnSetQ(&step, 2);
  191.     sieveBuild(s1, 1024, bn, 2, 0);
  192.     sieveBuildBig(s2, 1024, bn, &step, 0);
  193.     p1 = p2 = 0;
  194.     if (s1[0] != s2[0])
  195.         printf("Difference: s1[0] = %x s2[0] = %x\n", s1[0], s2[0]);
  196.     do {
  197.         p1 = sieveSearch(s1, 1024, p1);
  198.         p2 = sieveSearch(s2, 1024, p2);
  199.  
  200.         if (p1 != p2)
  201.             printf("Difference: p1 = %u p2 = %u\n", p1, p2);
  202.     } while (p1 && p2);
  203.  
  204.     bnEnd(&step);
  205. #endif
  206.     /* And search for a prime */
  207. #if CLOCK_AVAIL
  208.     gettime(&start);
  209. #endif
  210.     i = germainPrimeGen(bn, f ? genProgress : 0, (void *)&progress);
  211.     if (i < 0)
  212.         return -1;
  213. #if CLOCK_AVAIL
  214.     gettime(&stop);
  215. #endif
  216.     if (f) {
  217.         putc('\n', f);
  218.         fprintf(f, "%d modular exponentiations performed.\n", i);
  219.     }
  220. #if CLOCK_AVAIL
  221.     subtime(stop, start);
  222.     s = sec(stop);
  223.     bndPrintf("%u-bit time = %lu.%03u sec.", bits, s, msec(stop));
  224.     if (s > 60) {
  225.         putchar(' ');
  226.         putchar('(');
  227.         if (s > 3600)
  228.             printf("%u:%02u", (unsigned)(s/3600),
  229.                    (unsigned)(s/60%60));
  230.         else
  231.             printf("%u", (unsigned)(s/60));
  232.         printf(":%02u)", (unsigned)(s%60));
  233.     }
  234.     putchar('\n');
  235. #endif
  236.  
  237.     bndPut("p = ", bn);
  238.  
  239.     return 0;
  240. }
  241.  
  242. /* Copy the command line to the buffer. */
  243. static unsigned
  244. copy(unsigned char *buf, int argc, char **argv)
  245. {
  246.     unsigned pos, len;
  247.     
  248.     pos = 0;
  249.     while (--argc) {
  250.         len = strlen(*++argv);
  251.         memcpy(buf, *argv, len);
  252.         buf += len;
  253.         pos += len;
  254.         if (argc > 1) {
  255.             *buf++ = ' ';
  256.             pos++;
  257.         }
  258.     }
  259.     return pos;
  260. }
  261.  
  262. int
  263. main(int argc, char **argv)
  264. {
  265.     unsigned len;
  266.     struct BigNum bn;
  267.     unsigned char buf[1024];
  268.  
  269.     if (argc < 2) {
  270.         fprintf(stderr, "Usage: %s <seed>\n", argv[0]);
  271.         fputs("\
  272. <seed> should be a a string of bytes to be hashed to seed the prime\n\
  273. generator.  Note that unquoted whitespace between words will be counted\n\
  274. as a single space.  To include multiple spaces, quote them.\n", stderr);
  275.         return 1;
  276.     }
  277.  
  278.     len = copy(buf, argc, argv);
  279.  
  280.     bnInit();
  281.     bnBegin(&bn);
  282.     
  283.     genSophieGermain(&bn, 0x100, buf, len, stdout);
  284.     genSophieGermain(&bn, 0x200, buf, len, stdout);
  285.     genSophieGermain(&bn, 0x300, buf, len, stdout);
  286.     genSophieGermain(&bn, 0x400, buf, len, stdout);
  287.     genSophieGermain(&bn, 0x500, buf, len, stdout);
  288.     genSophieGermain(&bn, 0x600, buf, len, stdout);
  289. #if 0
  290.     /* These get *really* slow */
  291.     genSophieGermain(&bn, 0x600, buf, len, stdout);
  292.     genSophieGermain(&bn, 0x800, buf, len, stdout);
  293.     genSophieGermain(&bn, 0xc00, buf, len, stdout);
  294.     /* Like, plan on a *week* or more for this one. */
  295.     genSophieGermain(&bn, 0x1000, buf, len, stdout);
  296. #endif
  297.  
  298.     bnEnd(&bn);
  299.  
  300.     return 0;
  301. }
  302.