![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to random.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to random.c CVS log | Up to [PGP] / pgp / src |
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.