home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / fileutil / pgp10src.arj / RANDOM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-25  |  14.4 KB  |  384 lines
  1. /**********************************************************************
  2.     random.c - C source code for random number generation - 19 Nov 86
  3.     (c) Copyright 1986 by Philip Zimmermann.  All rights reserved.  
  4.     Revised Jul 88 by PRZ and again Dec 88 by Allan Hoeltje
  5.         to use IBM PC 8253 timer0 for a faster counter.
  6.     Revised Apr 89 by PRZ to recycle random bytes.
  7.     Last revised 15 Dec 90 by PRZ.
  8.  
  9.     This code generates truly random numbers derived from a counter that is 
  10.     incremented continuously while the keyboard is scanned for user input.
  11.     Every time the user touches a key, the least significant bits of the 
  12.     counter are pushed on a stack.  Later, this supply of random bytes can
  13.     be popped off the stack by applications requiring stochastic numbers.
  14.     Cryptographic applications require this kind of randomness.
  15.  
  16.     The only requirement to make this work is that keypress must be called 
  17.     frequently, and/or getkey must be called to read the keyboard.  
  18.  
  19.     Note that you can only get as many random bytes as the number of 
  20.     bytes accumulated by the user touching the keyboard.
  21. **********************************************************************/
  22.  
  23. #include    <stdio.h>    /* for putchar() and printf() */
  24. #include    <conio.h>    /* for kbhit() and getch() */
  25. #include    "random.h"
  26.  
  27. /* #define USEPCTIMER  /* use fast hardware timer on IBM PC or AT or clone */
  28. /* #define DEBUG */
  29.  
  30. #ifdef DEBUG
  31. #define DEBUGprintf1(x) fprintf(stderr,x)
  32. #define DEBUGprintf2(x,y) fprintf(stderr,x,y)
  33. #else
  34. #define DEBUGprintf1(x)
  35. #define DEBUGprintf2(x,y)
  36. #endif
  37.  
  38.  
  39. static int randseed=0; /* used only by pseudorand() function. */
  40. int pseudorand(void)
  41. /*    Home-grown 16-bit LCG pseudorandom generator. */
  42. {    randseed = (randseed*31421 + 6927) & 0xffff;
  43.     return (randseed);
  44. }    /* pseudorand */
  45.  
  46.  
  47. int randcount = 0 ;        /* # of random bytes accumulated in pool */
  48. static byte randpool[256] = {0} ;    /* pool of truly random bytes */
  49. static int recyclecount = 0 ;    /* # of recycled random bytes accumulated */
  50. static byte recyclepool[256] = {0} ; /* pool of recycled random bytes */
  51. static int recycleptr = 0;    /* points to next byte to grab in recyclepool */
  52.  
  53. /* fastcounter is a free-running counter incremented in main event loop */
  54. static byte fastcounter = 0;    /* not needed if we can use the PC timer. */
  55.  
  56.  
  57. #ifdef USEPCTIMER    /* we will use fast hardware timer on IBM PC */
  58. /* #include <conio.h>    /* function definitions for inp() and outp() */
  59. /* outp() and inp() works only for Microsoft C for IBM PC or AT */
  60. /* timer0 on 8253-5 on IBM PC or AT tics every .84 usec. */
  61. #define timer0        0x40    /* 8253 timer 0 port */
  62. #define timercntl    0x43    /* 8253 control register */
  63. #define timer0rwl    0x00    /* read lo/hi bytes of cntr 2 with latch */
  64. #define timer0rnl    0x30    /* read lo/hi bytes of cntr 2 w/o latch */
  65.  
  66. static byte latched_hitimer = 0; /* captured by keyboard ISR */
  67. static byte latched_lotimer = 0; /* captured by keyboard ISR */
  68. /* when kbisr captures timer, timer_latched is set. */
  69. static boolean timer_latched = FALSE;
  70.  
  71. static void kbisr(void)    /* Keyboard Interrupt Service Routine (ISR) */
  72. /*
  73.     kbisr should be called on the way into, or on the way out of,
  74.     or from within the DOS keyboard ISR, as long as it gets called
  75.     at the time of a keyboard interrupt.  Assumes that the real
  76.     DOS keyboard ISR captures the keystroke in the normal way.
  77.     Only the hardware timer counter is captured by the kbisr routine,
  78.     leaving the actual keystroke capture to the normal DOS keyboard ISR.
  79.     We indicate that a timer capture has taken place by setting 
  80.     timer_latched.
  81.  
  82.     NOTE: WE STILL NEED TO FIND A WAY to connect this subroutine with the 
  83.     normal keyboard ISR, so that kbisr gets called when there's a keyboard 
  84.     interrupt.
  85. */
  86. {    outp(timercntl,timer0rwl);
  87.     latched_lotimer = inp(timer0);
  88.     latched_hitimer = inp(timer0);
  89.     timer_latched = TRUE;
  90. }    /* kbisr */
  91.  
  92. static unsigned short pctimer0(void)
  93. {
  94. /*    Reads and returns the hardware 8253 timer0 on the PC or AT
  95. **    or clone, shifted right 1 bit.
  96. **
  97. **    DO NOT SET THE HARDWARE COUNTER TO ZERO. It is already initialized
  98. **    by the system to be used by the clock.  It is set up in mode 3
  99. **    (square wave rate generator) and counts down by 2 from 0 (0xFFFF+1)
  100. **    to produce an 18.2 Hz square wave.  We may, however, READ the
  101. **    lo and hi bytes without causing any problems.  BUT just
  102. **    remember that the lo byte will always be even (since it is
  103. **    counting by two).
  104. **
  105. **    Note that we can not use counter 1 since it is tied to the
  106. **    dynamic RAM refresh hardware.  Counter 2 is tied to the 8255
  107. **    PPI chip to do things like sound.  Though it would be safe to
  108. **    use counter 2 it is not desirable since we would have to turn
  109. **    the speaker on in order to make the timer count!  Normally one
  110. **    sets counter 2 to mode 3 (square wave generator) to sound the
  111. **    speaker.  You can set mode 2 (pulse generator) and the speaker
  112. **    hardly makes any sound at all, a click when you turn it on and
  113. **    a click when you turn it off.  Counter 0 should be safe if
  114. **    we only read the counter bytes.
  115. **
  116. **    WARNING:  To use the hardware timer the way it really should be
  117. **    used, we ought to capture it via a keyboard interrupt service
  118. **    routine (ISR).    Otherwise, we may experience weaknesses in randomness
  119. **    due to harmonic relationships between the hardware counter frequency
  120. **    and the keyboard software polling frequency.  Unfortunately, this
  121. **    implementation does not currently use keyboard interrupts to
  122. **    capture the counter.  This is not a problem if we don't use the
  123. **    hardware counter, but instead use the software counter fastcounter.
  124. **    Thus, the hardware counter should not be used at all, unless we
  125. **    support it with an ISR.
  126. */
  127.     unsigned short t ;
  128.     /* See if timer has been latched by kbisr(). */
  129.     if (!timer_latched) /* The timer was not already latched. */
  130.         kbisr();    /* latch timer */
  131.     /* return latched timer and clear latch */
  132.     t = (     (((unsigned short) latched_hitimer) << 8) |
  133.          ((unsigned short) latched_lotimer)
  134.         ) >> 1 ;
  135.     timer_latched = FALSE;
  136.     return (t) ;
  137. }    /* pctimer0 */
  138.  
  139. #endif    /* ifdef USEPCTIMER */
  140.  
  141.  
  142. void capturecounter(void)
  143. /*    Push a fast counter on the random stack.  Should be called when
  144. **    the user touches a key or clicks the mouse.
  145. */
  146. {
  147.     static unsigned int accum = 0;
  148.     static byte abits = 0;    /* number of accumulated bits in accum */
  149.  
  150. #ifdef USEPCTIMER    /* we will use fast hardware timer on IBM PC */
  151. #define cbits 8        /* number of bits of counter to capture each time */
  152.     fastcounter += pctimer0();
  153. #else            /* no fast hardware timer available */
  154. #define cbits 4        /* number of bits of counter to capture each time */
  155. #endif    /* ifdef USEPCTIMER */
  156. #define cbitsmask ((1 << cbits)-1)
  157.  
  158.     accum = (accum << cbits) | (unsigned int) (fastcounter & cbitsmask);
  159.     abits += cbits;
  160.     while (abits >= 8) 
  161.     {    if (randcount < sizeof(randpool))
  162.             /* take lower byte of accum */
  163.             randpool[randcount++] = accum;
  164.         abits -= 8;
  165.         accum >>= 8;
  166.     }
  167.     fastcounter = 0;
  168. #undef cbitsmask
  169. }    /* capturecounter */
  170.  
  171.  
  172. /* Because these truly random bytes are so unwieldy to accumulate,
  173.    they can be regarded as a precious resource.  Unfortunately,
  174.    cryptographic key generation algorithms may require a great many
  175.    random bytes while searching about for large random prime numbers.
  176.    Fortunately, they need not all be truly random.  We only need as
  177.    many truly random bytes as there are bytes in the large prime we
  178.    are searching for.  These random bytes can be recycled and modified
  179.    via pseudorandom numbers until the key is generated, without losing
  180.    any of the integrity of randomness of the final key.
  181. */
  182.  
  183.  
  184. static void randstir(void)
  185. /* Stir up the recycled random number bin, via a pseudorandom generator */
  186. {    int i;
  187.     i = recyclecount;
  188.     while (i--)
  189.         recyclepool[i] ^= (byte) pseudorand();
  190.     DEBUGprintf2(" Stirring %d recycled bytes. ",recyclecount);
  191. }    /* randstir */
  192.  
  193.  
  194. short randload(short bitcount)
  195. /*    Flushes stale recycled random bits and copies a fresh supply of raw 
  196.     random bits from randpool to recyclepool.  Returns actual number of 
  197.     bits transferred.  Formerly named randrecycle. */
  198. {    int bytecount;
  199.     bytecount = (bitcount+7)/8;
  200.     bytecount = min(bytecount,randcount);
  201.     randflush();    /* reset recyclecount, discarding recyclepool */
  202.     while (bytecount--)
  203.         recyclepool[recyclecount++] = randpool[--randcount];
  204.     DEBUGprintf2("\nAllocating %d recycleable random bytes. ",recyclecount);
  205.     return(recyclecount*8);
  206. }    /* randload */
  207.  
  208.  
  209. void randflush(void)    /* destroys pool of recycled random numbers */
  210. /* Ensures no sensitive data remains in memory that can be recovered later. */
  211. {    recyclecount = sizeof (recyclepool);
  212.     while (recyclecount)
  213.         recyclepool[--recyclecount]=0;
  214.     /* recyclecount is left at 0 */
  215.     recycleptr = 0;
  216. }    /* randflush */
  217.  
  218.  
  219. short randombyte(void)
  220. /*    Returns truly random byte from pool, or a pseudorandom value
  221. **    if pool is empty.  It is recommended that the caller check
  222. **    the value of randcount before calling randombyte.
  223. */
  224. {    
  225.     /* First try to get a cheap recycled random byte, if there are any. */
  226.     if (recyclecount)    /* nonempty recycled pool */
  227.     {    if (++recycleptr >= recyclecount)    /* ran out? */
  228.         {    recycleptr = 0;    /* ran out of recycled random numbers */
  229.             randstir();    /* stir up recycled bits */
  230.         }
  231.         return (recyclepool[recycleptr]);
  232.     }
  233.  
  234.     /* Empty recycled pool.  Try a more expensive fresh random byte. */
  235.     if (randcount)    /* nonempty random pool--return a very random number */
  236.         return (randpool[--randcount]);
  237.  
  238.     /* Alas, fresh random pool is empty.  Get a pseudorandom byte.
  239.        Pseudorandom numbers are risky for cryptographic applications.
  240.        Although we will return a pseudorandom byte in the low order byte,
  241.        indicate error by making the result negative in the high byte.
  242.     */
  243.     /* DEBUGprintf1("\007Warning: random pool empty! "); */
  244.     return ( (pseudorand() & 0xFF) ^ (-1) );
  245. }    /* randombyte */
  246.  
  247.  
  248. static short keybuf = 0;    /* used only by keypress() and getkey()    */
  249.  
  250. boolean keypress(void)    /* TRUE iff keyboard input ready */
  251. {    /* Accumulates random numbers by timing user keystrokes. */
  252.     static short lastkey = 0; /* used to detect autorepeat key sequences */
  253.     static short next_to_lastkey = 0; /* allows a single repeated key */
  254.  
  255. #ifndef USEPCTIMER    /* no fast hardware timer available */
  256.     fastcounter++;    /* used in lieu of fast hardware timer counter */
  257. #endif    /* ifndef USEPCTIMER */
  258.  
  259.     if (keybuf & 0x100)    /* bit 8 means keybuf contains valid data */
  260.         return( TRUE );    /* key was hit the last time thru */
  261.  
  262.     if (kbhit() == 0)    /* keyboard was not hit */
  263.         return( FALSE );
  264.  
  265.     keybuf = getch() | 0x100; /* set data latch bit */
  266.  
  267.     /* Keyboard was hit.  Decide whether to call capturecounter... */
  268.  
  269.     /*  Guard against typahead buffer defeating fastcounter's randomness.
  270.     **  This could be a problem for multicharacter sequences generated
  271.     **  by a function key expansion or by the user generating keystrokes
  272.     **  faster than our event loop can handle them.  Only the last 
  273.     **  character of a multicharacter sequence will trigger the counter
  274.     **  capture.  Also, don't let the keyboard's autorepeat feature
  275.     **  produce nonrandom counter capture.  However, we do allow a 
  276.     **  single repeated character to trigger counter capture, because
  277.     **  many english words have double letter combinations, and it's 
  278.     **  unlikely a typist would exploit the autorepeat feature to
  279.     **  type a simple double letter sequence.
  280.     */
  281.  
  282.     if (kbhit() == 0)    /* nothing in typahead buffer */
  283.     {    /* don't capture counter if key repeated */
  284.         if (keybuf != lastkey)
  285.             capturecounter(); /* save current random number seed */
  286.         else if (keybuf != next_to_lastkey) /* allow single repeat */
  287.             capturecounter();
  288.         next_to_lastkey = lastkey;
  289.         lastkey = keybuf;
  290.     }
  291.     return( TRUE );
  292. }    /* keypress */
  293.  
  294.  
  295. short getkey(void)    /* Returns data from keyboard (no echo). */
  296. {    /* Also accumulates random numbers via keypress(). */
  297.     while(! keypress() );        /* loop until key is pressed. */
  298.     return( keybuf &= 0xff);    /* clear latch bit 8 */
  299. }    /* getkey */
  300.  
  301.  
  302. #define BS 8    /* ASCII backspace */
  303. #define CR 13    /* ASCII carriage return */
  304. #define LF 10    /* ASCII linefeed */
  305.  
  306.  
  307. int getstring(char *strbuf, int maxlen, boolean echo)
  308. /*    Gets string from user, with no control characters allowed.
  309.     Also accumulates random numbers by calling getkey().
  310.     maxlen is max length allowed for string.
  311.     echo is TRUE iff we should echo keyboard to screen.
  312.     Returns null-terminated string in strbuf. 
  313. */
  314. {    short i;
  315.     char c;
  316.     i=0;
  317.     while (TRUE)
  318.     {    c = getkey();
  319.          if (c==BS) 
  320.         {    if (i) 
  321.             {    if (echo) 
  322.                 {    fputc(BS,stderr);
  323.                     fputc(' ',stderr);
  324.                     fputc(BS,stderr);
  325.                 }
  326.                 i--;
  327.             }
  328.             continue;
  329.         }
  330.          if (echo) fputc(c,stderr);
  331.         if (c==CR) 
  332.         {    if (echo) fputc(LF,stderr);
  333.             break;
  334.         }
  335.         if (c==LF)
  336.             break;
  337.         if (c=='\n')
  338.             break;
  339.         if (c<' ')    /* any ASCII control character */
  340.             break;
  341.         strbuf[i++] = c;
  342.         if (i>=maxlen) 
  343.         {    fprintf(stderr,"\007*\n");    /* -Enough! */
  344.             while (keypress())
  345.                 getkey();    /* clean up any typeahead */
  346.             break;
  347.         }
  348.     }
  349.     strbuf[i] = '\0';    /* null termination of string */
  350.     return(i);        /* returns string length */
  351. }    /* getstring */
  352.  
  353.  
  354. void randaccum(short bitcount)    /* Get this many random bits ready */
  355. /* We will need a series of truly random bits for key generation.
  356.    In most implementations, our random number supply is derived from
  357.    random keyboard delays rather than a hardware random number
  358.    chip.  So we will have to ensure we have a large enough pool of
  359.    accumulated random numbers from the keyboard.  Later, randombyte
  360.    will return bytes one at a time from the accumulated pool of
  361.    random numbers.  For ergonomic reasons, we may want to prefill
  362.    this random pool all at once initially.  This routine prefills
  363.    a pool of random bits. */
  364. {    short nbytes;
  365.     char c;
  366.     nbytes = min((bitcount+7)/8,sizeof(randpool));
  367.  
  368.     if (randcount < nbytes)    /* if we don't have enough already */
  369.     {    fprintf(stderr,"\nWe need to generate %d random bytes.  This is done by measuring the",
  370.             nbytes-randcount);
  371.         fprintf(stderr,"\ntime intervals between your keystrokes.  Please enter some text on your");
  372.         fprintf(stderr,"\nkeyboard, at least %d nonrepeating keystrokes, until you hear the bell:\n",
  373.             (8*(nbytes-randcount)+cbits-1)/cbits);
  374.         while (randcount < nbytes) 
  375.         {    c=getkey();
  376.             fputc(c,stderr);
  377.             if (c==CR) fputc(LF,stderr);
  378.         }
  379.         fprintf(stderr,"\007*\n-Enough, thank you.\n");
  380.         while (keypress()) getkey();    /* clean up any typeahead */
  381.     }    /* if (randcount < nbytes) */
  382. }    /* randaccum */
  383.  
  384.