Return to random.c CVS log

Up to [PGP] / pgp / src

Annotation of pgp/src/random.c, revision 1.1

1.1     ! root        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: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.