home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1817 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  5.3 KB
  1. From: istvan@hhb.UUCP (Istvan Mohos)
  2. Newsgroups: sci.crypt,alt.sources
  3. Subject: padrand(); /* random numbers from one-time pads */
  4. Message-ID: <578@hhb.UUCP>
  5. Date: 13 Sep 90 13:06:19 GMT
  6.  
  7.  
  8. In article <2260@lectroid.sw.stratus.com> cme (Carl Ellison) writes:
  9. >In article <2208@ux.acs.umn.edu> dhoyt@vx.acs.umn.edu writes:
  10. >> I'll try to find a
  11. >>difference between noise and a pad.  Could it have something to do with noise
  12. >>being additive and the pad is an exclusive or?  Statistical quantum theory?
  13.  
  14. >It's nothing so difficult.  After either XOR or ADD with a true random
  15. >1-time pad, every possible cyphertext value is *exactly equally* likely.
  16. >Therefore, every possible plaintext value is *exactly equally* likely.
  17.  
  18. The C source of the padrand() routine posted here, is hereby placed in
  19. the Public Domain.  A primitive driver (main) is enclosed for convenient
  20. testing.  The verbal description of the algorithm immediately below, is
  21. "Copyright 1990, Istvan Mohos, All Rights Reserved".
  22.  
  23. An often cited and axiomatic observation of cryptology is the security
  24. of information encrypted using one-time pads as keys.  Practical
  25. one-time pads are non-cyclic non-monotone text, of sufficient length to
  26. mask the plaintext.  An instance of a one-time pad represents a
  27. perfectly random selection of a single key out of a potentially infinite
  28. number of choices.  One should be able to capture and use this "perfect
  29. randomness" in seeking other goals than security of encryption.  The
  30. random number generator described here defines an alternate utility of
  31. one-time pads.
  32.  
  33. Although the text of one-time pads is non-cyclic, the byte stream is
  34. subject to regularities of character distribution as the function of the
  35. language.  Two methods of combating uneven distribution are implemented
  36. in the padrand() routine.  Firstly, the *minimum* of information is
  37. extracted from each pad byte, evaluating only whether the (ASCII) value
  38. of the byte is even or odd.  The second method simply increments the
  39. value of every other pad byte by one, with a "limping adder".
  40.  
  41. If the pad stream contains an equal number of even and odd bytes, the
  42. adder flips a (statistically) equal number of even bytes to odd and odd
  43. bytes to even, so the overall distribution remains the same.  If there
  44. is an imbalance of even/odd bytes in the pad stream, half of the
  45. additional (even or odd) bytes causing the imbalance is likely to be
  46. converted to the opposite, dampening the divergence.
  47.  
  48. The resulting even/odd flags are shifted into a binary bit field; the
  49. user can select the width of the field.
  50.  
  51. The routine opens and reads the specified pad file, "using up"
  52. bitfield-width-bytes at each call for generating a new random number.
  53. The value returned is between 0 and the maximum value that can fit in
  54. the selected bit width.  When the pad is exhausted, the routine closes
  55. the file and returns -1.  At the next call, the (new or reused) file is
  56. opened and the process starts again.
  57.  
  58. The program is somewhat wasteful of pad text, and is intended for Unix
  59. environments where on-line text is abundant (as evidenced by directories
  60. /usr/dict, /usr/man, ~TeX/TeXdoc and the like) but hardware random
  61. number generators are absent.  Accordingly, "int" is assumed to be
  62. 32-bits wide; bits 1 through 31 are used for controlling the range of
  63. the generated numbers.  A different magnitude may be selected at every
  64. call.  Requests for larger ranges are silently masked down to 31 bits.
  65.  
  66. As additional controls, (char *)NULL passed for the pad name closes an
  67. open pad in preparation for switching to a new pad; negative field
  68. widths (not subject to the range limitation) are interpreted as commands
  69. to bump the file pointer by the absolute value of the negative field;
  70. zero field width flips the "limping adder" to its complement.  Control
  71. operations or I/O failures return small negative int values specific to
  72. the operation or to the failure, and do not produce random numbers.
  73.  
  74. #include <stdio.h>
  75. main ()
  76. {
  77.     char namebuf[1024];
  78.     register char *name = namebuf;
  79.     register int bits, rand;
  80.  
  81.     for (;; name = namebuf) {
  82.         fprintf(stderr, "bit width: "), gets(name), bits = atoi(name);
  83.         fprintf(stderr, "file name: "), gets(name);
  84.         if (!strlen(name))
  85.             name = NULL;
  86.         do
  87.             printf("%d\n", rand = padrand(name, bits)), fflush(stdout);
  88.         while (rand >= 0);
  89.     }
  90. }
  91.  
  92. /********************************************
  93. * generate random numbers from text
  94. * Istvan Mohos, 1990 --- in the Public Domain
  95. *********************************************/
  96. #define INTWID 32
  97. int
  98. padrand (pad, bits)
  99. char *pad;
  100. register int bits;
  101. {
  102.     FILE *fopen();
  103.     static FILE *fp = NULL;
  104.     static int silkie = 0;
  105.     register int rand = 0;
  106.     register int chr;
  107.  
  108.     if (pad == NULL) {
  109.         if (fp != NULL)
  110.             (void) fclose (fp), fp = NULL;
  111.         silkie = 0;
  112.         return (-6);
  113.     }
  114.     if (fp == NULL && (fp = fopen (pad, "r")) == NULL) {
  115.         silkie = 0;
  116.         return (-5);
  117.     }
  118.     if (bits < 0) {
  119.         if (fseek (fp, (long)abs(bits), 1) == 0)
  120.             return (-4);
  121.         (void) fclose (fp);
  122.         fp = NULL;
  123.         silkie = 0;
  124.         return (-3);
  125.     }
  126.     if ((bits &= INTWID-1) == 0) {
  127.         silkie = !silkie;
  128.         return (-2);
  129.     }
  130.     for (; --bits >= 0; silkie = !silkie) {
  131.         if ((chr = fgetc (fp)) == EOF) {
  132.             (void) fclose (fp);
  133.             fp = NULL;
  134.             silkie = 0;
  135.             return (-1);
  136.         }
  137.         chr += silkie;
  138.         rand <<= 1;
  139.         rand += chr&1;
  140.     }
  141.     return (rand);
  142. }
  143. -- 
  144.         Istvan Mohos
  145.         ...uunet!pyrdc!pyrnj!hhb!istvan
  146.         1000 Wyckoff Ave. Mahwah NJ 07430 201-848-8000
  147. ======================================================
  148.