home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume2 / xrand < prev    next >
Internet Message Format  |  1991-08-07  |  21KB
  1. From: agn@UNH.CS.CMU.EDU (Andreas Nowatzyk)
  2. Newsgroups: comp.sources.misc
  3. Subject: v02i096: xrand, xcrypt -- a random number generator & application
  4. Message-ID: <8804131846.AA29500@rutgers.edu>
  5. Date: 13 Apr 88 17:19:34 GMT
  6. Approved: allbery@ncoast.UUCP
  7.  
  8. comp.sources.misc: Volume 2, Issue 96
  9. Submitted-By: "Andreas Nowatzyk" <agn@UNH.CS.CMU.EDU>
  10. Archive-Name: xrand
  11.  
  12. The attached random-number generator was writen because of a need for
  13. a good source of random numbers for a research project that involved
  14. systems without such facility (for example a research prototype with
  15. only a C-compiler and minimal libraries).
  16.  
  17. Since the results are critical to my work, a serious attempt was made
  18. to write a 'really good' RNG: that is several CPU weeks on assorted
  19. machines were spend to try out (and discard) various approaches.
  20.  
  21. The generator below is based on 2 well known methods: Linear Congruential
  22. (LCGs) and Additive Congruential generators (ACGs). 
  23.  
  24. The LCG produces the longest possible sequence of 32 bit 'random' numbers,
  25. each being unique in that sequence (it has only 32 bits of state).
  26. It suffers from 2 problems:
  27. a) Independence isn't great, that is the (n+1)th number is somewhat
  28.    related to the preceding one, unlike flipping a coin where knowing the
  29.    past outcomes don't help to predict the next result.
  30. b) Taking parts of a LCG generated number can be quite non-random: for
  31.    example, looking at only the least significant byte gives a permuted
  32.    8-bit counter (that has a  period length of only 256).
  33. The advantage of an LCA is that it is perfectly uniform when run for the
  34. entire period length (and very uniform for smaller sequences too, if
  35. the parameters are chosen carefully).
  36.  
  37. ACG's have extremly long period lengths and provide good independence.
  38. Unfortunately, uniformity isn't not too great. Furthermore, I didn't
  39. find any theoretically analysis of ACG's that addresses uniformity.
  40.  
  41. The RNG given below will return numbers generated by an LCA that are
  42. permuted under control of a ACG. 2 permutations take place: the
  43. 4 bytes of one LCG generated number are subjected to one of 16 permutations
  44. selected by 4 bits of the ACG. The permutation a such that byte of the
  45. result may come from each byte of the LCG number. This effectively destroys
  46. the structure within a word. Finally, the sequence of such numbers is
  47. permuted within a range of 256 numbers. This greatly improves independence.
  48.  
  49. xcrypt is a recreational application (as I have little need for secrecy) 
  50. of this random number generator to en/decrypt files. However, I do believe
  51. that this byproduct is quite strong and a challenge ($50)
  52. to this effect has been posted to sci.crypt. Breaking xcrypt would probably
  53. reveal a flaw in xrand and I'm highly interested in any such problem.
  54.  
  55.   Cheers  --  Andreas
  56.  
  57. -------------------- Cut here --------------------
  58. #
  59. # type    sh /usru0/agn/x.shar   to unpack this archive.
  60. #
  61. echo extracting xrand.1...
  62. cat >xrand.1 <<'!E!O!F!'
  63. .TH XRAND 3 4/13/88
  64. .CM 4
  65. .SH NAME
  66. xrand \- pseudo random number generators
  67. .SH SYNOPSIS
  68. void rnd_init(seed)
  69. unsigned seed;
  70.  
  71. long rnd_i()
  72.  
  73. unsigned long rnd_u()
  74.  
  75. long rnd_ri(range)
  76. long range;
  77.  
  78. double rnd_01d()
  79.  
  80. double rnd_ned(lamda)
  81. double lamda;
  82. .SH DESCRIPTION
  83. xrand is a collection of pseudo-random number generators that were
  84. carefully tested for uniform distribution and independence.
  85. These tests included testing parts of the generated numbers
  86. (say a byte or a bit) for the same properties.
  87.  
  88. .B rnd_init
  89. must be called before any random numbers are drawn.
  90. Different seeds will
  91. yield different, but deterministic sequences of random numbers with
  92. like statistical properties.
  93. .B rnd_i
  94. returns positive integers,
  95. .B rnd_u
  96. returns unsigned integers (all 32 bit are 
  97. .I random
  98. ), 
  99. .B rnd_ri
  100. returns integers in the range [0..range-1],
  101. .B rnd_01d
  102. returns doubles in the range of [0.0..1.0),
  103. .B rnd_ned
  104. returns negative-exponential distributed doubles in
  105. the range [0.0..+infinity).
  106. .SH ENVIRONMENT
  107. .B rnd_ned
  108. requires
  109. .B log()
  110. from the math library.
  111. .SH "SEE ALSO"
  112. .I rand(3C),
  113. which produces pseudo-random numbers which are not very random and
  114. .I
  115. random(3),
  116. which is about 45% faster than xrand but has inferior uniformity.
  117. .SH BUGS
  118. .B xrand
  119. assumes that long words have 32 bits and that 2's complement
  120. arithmetic is used.
  121. .SH HISTORY
  122. .TP
  123. 13-Apr-88  Andreas Nowatzyk (agn) at Carnegie-Mellon University
  124. Created.
  125. !E!O!F!
  126. #
  127. # type    sh /usru0/agn/x.shar   to unpack this archive.
  128. #
  129. echo extracting xrand.c...
  130. cat >xrand.c <<'!E!O!F!'
  131. #include <math.h>
  132.  
  133. /* Random number generators:
  134.  *
  135.  *  rnd_init (unsigned seed) 
  136.  *            : initializes the generator
  137.  *
  138.  *  rnd_i ()        : returns positive integers [0,0x7fffffff]
  139.  *  rnd_u ()        : returns unsigned's        [0,0xffffffff]
  140.  *  rnd_ri (long n)    : returns positive integers [0,n-1]
  141.  *  rnd_01d ()        : returns doubles        [0.0,1.0)
  142.  *              Note: ")" is no typo - rnd_01d will not return a 1.0,
  143.  *                              but can return the next smaller FP number.
  144.  *  rnd_ned (double lam): returns neg. exponential distributed doubles [0.0,+inf)
  145.  *
  146.  *  Algorithm M as describes in Knuth's "Art of Computer Programming", Vol 2. 1969
  147.  *  is used with a linear congruential generator (to get a good uniform
  148.  *  distribution) that is permuted with a Fibonacci additive congruential
  149.  *  generator to get good independence.
  150.  *
  151.  *  Bit, byte, and word distributions were extensively tested and pass
  152.  *  Chi-squared test near perfect scores (>7E8 numbers tested, Uniformity
  153.  *  assumption holds with probability > 0.999)
  154.  *
  155.  *  Run-up tests for on 7E8 numbers confirm independence with
  156.  *  probability > 0.97.
  157.  *
  158.  *  Plotting random points in 2d reveals no apparent structure.
  159.  *
  160.  *  Autocorrelation on sequences of 5E5 numbers (A(i) = SUM X(n)*X(n-i), i=1..512)
  161.  *  results in no obvious structure (A(i) ~ const).
  162.  *
  163.  *  On a SUN 3/60, rnd_u() takes about 19.4 usec per call, which is about 44%
  164.  *  slower than Berkeley's random() (13.5 usec/call).
  165.  *
  166.  *  Except for speed and memory requirements, this generator outperforms
  167.  *  random() for all tests. (random() scored rather low on uniformity tests,
  168.  *  while independence test differences were less dramatic).
  169.  *
  170.  *  Thanks to M.Mauldin, H.Walker, J.Saxe and M.Molloy for inspiration & help.
  171.  *
  172.  *  (c) Copyright 1988 by A. Nowatzyk
  173.  *
  174.  */
  175.  
  176. /* LC-parameter selection follows recommendations in 
  177.  * "Handbook of Mathematical Functions" by Abramowitz & Stegun 10th, edi.
  178.  */
  179. #define LC_A 66049            /* = 251^2, ~= sqrt(2^32)            */
  180. #define LC_C 3907864577            /* result of a long trial & error series    */
  181.  
  182. #define Xrnd(x) (x * LC_A + LC_C)   /* the LC polynomial            */
  183.             
  184. static unsigned long Fib[55];        /* will use X(n) = X(n-55) - X(n-24)    */
  185. static int Fib_ind;            /* current index in circular buffer        */
  186. static unsigned long Xrnd_var;        /* LCA - recurrence variable        */
  187. static unsigned long auxtab[256];   /* temporal permutation table        */
  188. static unsigned long prmtab[64] = { /* spatial permutation table        */
  189.     0xffffffff, 0x00000000,  0x00000000,  0x00000000,  /* 3210 */
  190.     0x0000ffff, 0x00ff0000,  0x00000000,  0xff000000,  /* 2310 */
  191.     0xff0000ff, 0x0000ff00,  0x00000000,  0x00ff0000,  /* 3120 */
  192.     0x00ff00ff, 0x00000000,  0xff00ff00,  0x00000000,  /* 1230 */
  193.  
  194.     0xffff0000, 0x000000ff,  0x00000000,  0x0000ff00,  /* 3201 */
  195.     0x00000000, 0x00ff00ff,  0x00000000,  0xff00ff00,  /* 2301 */
  196.     0xff000000, 0x00000000,  0x000000ff,  0x00ffff00,  /* 3102 */
  197.     0x00000000, 0x00000000,  0x00000000,  0xffffffff,  /* 2103 */
  198.  
  199.     0xff00ff00, 0x00000000,  0x00ff00ff,  0x00000000,  /* 3012 */
  200.     0x0000ff00, 0x00000000,  0x00ff0000,  0xff0000ff,  /* 2013 */
  201.     0x00000000, 0x00000000,  0xffffffff,  0x00000000,  /* 1032 */
  202.     0x00000000, 0x0000ff00,  0xffff0000,  0x000000ff,  /* 1023 */
  203.  
  204.     0x00000000, 0xffffffff,  0x00000000,  0x00000000,  /* 0321 */
  205.     0x00ffff00, 0xff000000,  0x00000000,  0x000000ff,  /* 0213 */
  206.     0x00000000, 0xff000000,  0x0000ffff,  0x00ff0000,  /* 0132 */
  207.     0x00000000, 0xff00ff00,  0x00000000,  0x00ff00ff   /* 0123 */
  208. };
  209.  
  210. union hack {                /* used to access doubles as unsigneds    */
  211.     double d;
  212.     unsigned long u[2];
  213. };
  214.  
  215. static union hack man;            /* mantissa bit vector            */
  216.  
  217. rnd_init (seed)                /* modified: seed 0-31 use precomputed stuff */
  218.     unsigned seed;
  219. {
  220.     register unsigned long u;
  221.     register int i;
  222.     double x, y;
  223.     union hack t;
  224.  
  225.     static unsigned seed_tab[32] = {
  226.         0xbdcc47e5, 0x54aea45d, 0xec0df859, 0xda84637b,
  227.         0xc8c6cb4f, 0x35574b01, 0x28260b7d, 0x0d07fdbf,
  228.         0x9faaeeb0, 0x613dd169, 0x5ce2d818, 0x85b9e706,
  229.         0xab2469db, 0xda02b0dc, 0x45c60d6e, 0xffe49d10,
  230.         0x7224fea3, 0xf9684fc9, 0xfc7ee074, 0x326ce92a,
  231.         0x366d13b5, 0x17aaa731, 0xeb83a675, 0x7781cb32,
  232.         0x4ec7c92d, 0x7f187521, 0x2cf346b4, 0xad13310f,
  233.         0xb89cff2b, 0x12164de1, 0xa865168d, 0x32b56cdf  };
  234.  
  235.     if (seed < 32)
  236.     u = seed_tab[seed];
  237.     else
  238.     u = seed ^ seed_tab[seed & 31];
  239.  
  240.     for (i = 55; i--;)            /* set up Fibonacci additive congruential    */
  241.     Fib[i] = u = Xrnd(u);
  242.  
  243.     for (i = 256; i--;)
  244.     auxtab[i] = u = Xrnd(u);
  245.  
  246.     Fib_ind = u % 55;            /* select a starting point            */
  247.  
  248.     Xrnd_var = u;
  249.  
  250.     if (sizeof(x) != 2 * sizeof(unsigned long)) {
  251.     x = 0.0;
  252.     y = 1.0;
  253.     y /= x;                /*** intentional divide by 0: rnd_01d will
  254.                      not work because a double doesn't fit
  255.                      in 2 unsigned longs on your machine! ***/
  256.     };
  257.  
  258.     x = 1.0;
  259.     y = 0.5;
  260.     do {                /* find largest fp-number < 2.0        */
  261.     t.d = x;
  262.     x += y;
  263.     y *= 0.5;
  264.     } while (x != t.d && x < 2.0);
  265.  
  266.     man.d = 1.0;
  267.     man.u[0] ^= t.u[0];
  268.     man.u[1] ^= t.u[1];            /* man is now 1 for each mantissa bit    */
  269. }
  270.  
  271. long rnd_i ()
  272. /*
  273.  * returns a positive, uniformly distributed random number in [0,0x7fffffff]
  274.  */
  275. { 
  276.     register unsigned long i, j, *t = Fib;
  277.  
  278.     i = Fib_ind;
  279.     j = t[i];                    /* = X(n-55) */
  280.     j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */
  281.     t[i] = j;
  282.     if (++i >= 55) i = 0;
  283.     Fib_ind = i;
  284.  
  285.     t = &auxtab[(j >> 24) & 0xff];
  286.     i = *t;
  287.     Xrnd_var = *t = Xrnd(Xrnd_var);
  288.     t = &prmtab[j & 0x3c];
  289.  
  290.     j =  *t++ & i;
  291.     j |= *t++ & ((i << 24) | ((i >>  8) & 0x00ffffff));
  292.     j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff));
  293.     j |= *t   & ((i <<  8) | ((i >> 24) & 0x000000ff));
  294.     
  295.     return j & 0x7fffff;
  296. }
  297.  
  298. unsigned long rnd_u ()
  299. /*
  300.  * same as rnd_i, but gives full 32 bit range
  301.  */
  302. { 
  303.     register unsigned long i, j, *t = Fib;
  304.  
  305.     i = Fib_ind;
  306.     j = t[i];                    /* = X(n-55) */
  307.     j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */
  308.     t[i] = j;
  309.     if (++i >= 55) i = 0;
  310.     Fib_ind = i;
  311.  
  312.     t = &auxtab[(j >> 24) & 0xff];
  313.     i = *t;
  314.     Xrnd_var = *t = Xrnd(Xrnd_var);
  315.     t = &prmtab[j & 0x3c];
  316.  
  317.     j =  *t++ & i;
  318.     j |= *t++ & ((i << 24) | ((i >>  8) & 0x00ffffff));
  319.     j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff));
  320.     j |= *t   & ((i <<  8) | ((i >> 24) & 0x000000ff));
  321.     
  322.     return j;
  323. }
  324.  
  325. long rnd_ri (rng)
  326.     long rng;
  327. /*
  328.  * randint: Return a random integer in a given Range [0..rng-1]
  329.  *          Note:  0 < rng
  330.  */
  331. {
  332.     register unsigned long  r, a;
  333.  
  334.     do {
  335.     r = rnd_i();
  336.     a = (r / rng) + 1;
  337.     a *= rng;
  338.     } while (a >= 0x7ffffff);
  339.     
  340.     a--;
  341.     return a - r;
  342. }
  343.  
  344. double rnd_01d ()
  345. /*
  346.  * returns a uniformly distributed double in the range of [0..1)
  347.  *         or  0.0 <= rnd_01d() < 1.0 to be precise
  348.  *
  349.  * Note: this code assumes that 2 'unsigned long's can hold a 'double'
  350.  *       (works on SUN-3's, SUN-4's, MIPS, VAXen, IBM RT's)
  351.  */
  352. {
  353.     union hack t;
  354.  
  355.     t.d = 1.0;
  356.  
  357.     t.u[0] |= rnd_u() & man.u[0];          /* munch in 1st part   */
  358.     t.u[1] |= rnd_u() & man.u[1];          /* munch in 2nd part   */
  359.  
  360.     return t.d - 1.0;
  361. }
  362.  
  363. double rnd_ned (lam)
  364.     double lam;
  365. /*
  366.  * returns a neg. exponential distributed double in the range of [0..+infinity)
  367.  *         or  0.0 <= rnd_neg() < +infinity to be precise
  368.  *
  369.  * Note: this code assumes that 2 'unsigned long's can hold a 'double'
  370.  *       it also assumes that 'log()' behaves as advertised.
  371.  *
  372.  */
  373. {
  374.     union hack t;
  375.  
  376.     t.d = 1.0;
  377.  
  378.     t.u[0] |= rnd_u() & man.u[0];          /* munch in 1st part   */
  379.     t.u[1] |= rnd_u() & man.u[1];          /* munch in 2nd part   */
  380.  
  381.     return -log(2.0 - t.d) / lam;
  382. }
  383. !E!O!F!
  384. #
  385. # type    sh /usru0/agn/x.shar   to unpack this archive.
  386. #
  387. echo extracting xcrypt.1...
  388. cat >xcrypt.1 <<'!E!O!F!'
  389. .TH XCRYPT 1 4/13/88
  390. .CM 4
  391. .SH NAME
  392. xcrypt \- data encryption/decryption program
  393. .SH SYNOPSIS
  394. encrypt <plain-text file> <cipher-text file>
  395.  
  396. decrypt <cipher-text file> <plain-text file>
  397. .SH DESCRIPTION
  398. .B xcrypt
  399. uses the observation that a good pseudo-random number
  400. generator can be used to generate a strong encryption.
  401. .B xcrypt
  402. is based on
  403. .B xrand(3)
  404. that was extensively tested for randomness (some CPU-week were devoted
  405. to this effort).
  406.  
  407. .B xcrypt
  408. invoked with a name starting with either 'e' or 'E' will write an
  409. encrypted version of the plain-text file to the cipher text file.
  410. Any other invocation will cause an decryption.
  411. Both files are treated as binary files. ASCII-text files will become
  412. binary files upon encryption.
  413. The key string will be prompted from <stdin>.
  414. .B xcrypt
  415. will compute for a few seconds before starting the translation, which
  416. is essentially I/O limited.
  417. This initialization phase is indispensable
  418. and was designed to thwart brute force key guessing attempts.
  419. Key lengths of 10-1000 characters are meaningful.
  420. .SH ENVIRONMENT
  421. .B xcrypt
  422. requires
  423. .B xrand(3)
  424. .SH HISTORY
  425. .TP
  426. 13-Apr-88  Andreas Nowatzyk (agn) at Carnegie-Mellon University
  427. Created.
  428. !E!O!F!
  429. #
  430. # type    sh /usru0/agn/x.shar   to unpack this archive.
  431. #
  432. echo extracting xcrypt.c...
  433. cat >xcrypt.c <<'!E!O!F!'
  434. /*
  435.  * xcrypt: a Encryption / Decryption program.
  436.  *
  437.  * xcrypt is loosely based on an idea that was proposed by M.Mauldin @ CMU
  438.  * (and potentially many other): use a pseudo-random number generator (RNG)
  439.  * to produce one-time pads.
  440.  *
  441.  * So, the basic approach is simply to initialize the RNG with the
  442.  * encryption key and then decide what part of the RNG output is
  443.  * used to encrypt the message. In xcrypt, a high quality RNG is
  444.  * employed that was extensively tested for uniform distribution
  445.  * and independence. This is expected to yield a rather strong encryption.
  446.  *
  447.  * Selecting the starting point of the random number sequence is based on a
  448.  * seed that is derived from the unix time()-call and the process ID.
  449.  * This seed (4 bytes) is prefixed to the ciphertext (similar to the typical
  450.  * unix password encoding scheme). You may consider transmitting the seed
  451.  * by an other channel.
  452.  *
  453.  * Actually, both the seed and the key are used to determine the initial
  454.  * state of the RNG, which is less computationally expensive than letting
  455.  * the RNG run for value-of(seed) iterations.
  456.  *
  457.  * This particular RNG has 9990bits of state (yes, more than 1Kbyte!), so
  458.  * so keys of 1000 char are still meaningful (albeit cumbersome).
  459.  *
  460.  * In order to thwart a key-guessing, brute force attack, the RNG is
  461.  * run for 60000 to 120000 iterations before the output is used for
  462.  * encryption. The RNG output of this initialization phase is used to
  463.  * construct 2 sets of 256 permutations of [0,1,...,255], that will
  464.  * be used later. Thus, any shortcut of these iterations (the actual
  465.  * number depends on the key and is not known to the attacker) would
  466.  * also have to produce all the intermediate results. Given the low
  467.  * complexity of an iteration, it's non-linearity and the intermediate
  468.  * result requirement, it appears to me that it is provable that no
  469.  * dramatic shortcut exists.
  470.  *
  471.  * The RNG delivers 32bit random numbers. All 32 bits are
  472.  * used to encrypt an 8bit character:
  473.  *    1. use 8bit to XOR the plaintext character
  474.  *    2. use 8bit to select a random permutation (from set 1, see above)
  475.  *    3. use 8bit to XOR the result of step 2
  476.  *    4. use 8bit to select a random permutation (set 2)
  477.  * Every bit of the RNG output will change the plain-to-cipher text
  478.  * character mapping, but unlike the simple XOR case, it is not possible
  479.  * to reconstruct the RNG output from a plain/cipher text pair (you
  480.  * would have to guess about 24bits!).
  481.  *
  482.  * The strength of xcrypt is based on:
  483.  *   1. a high quality RNG with plenty of state information.
  484.  *   2. a computation intensive initialization phase
  485.  *   3. 'information loss' in the encryption phase that
  486.  *      prevents the reconstruction of the 'PAD' even in the
  487.  *      known plain text case.
  488.  *
  489.  * Note: 'xcrypt' is a small just-for-fun program, but the underlying
  490.  *       RNG was written and extensively tested as part of a serious
  491.  *       research project.
  492.  *
  493.  * April, 1988  A. Nowatzyk
  494.  *
  495.  */
  496.  
  497. #include <stdio.h>
  498. #include <sys/file.h>
  499.  
  500. char perm_tab1[0x10000];    /* permutation tables        */
  501. char perm_tab2[0x10000];
  502.  
  503. #include "xrand.c"
  504.  
  505. main(argc, argv)
  506. int    argc;
  507. char    *argv[];
  508. {
  509.     unsigned        seed;
  510.     char            buf[4];
  511.     int             ifd, ofd;
  512.  
  513.     if (argc != 3 || 0 > (ifd = open(argv[1], O_RDONLY)) || 
  514.         0 > (ofd = open(argv[2], O_WRONLY | O_CREAT, 0600))) {
  515.     fprintf(stderr, "en/decrypt <input-file> <output-file>\n");
  516.     exit(1);
  517.     }
  518.  
  519.     if (*argv[0] == 'e' || *argv[0] == 'E') {    /** encryption **/
  520.  
  521.     seed = time(0l);    /* get an arbitrary seed    */
  522.     seed ^= getpid();
  523.  
  524.     get_key(seed);        /* get the key            */
  525.  
  526.     buf[0] = seed;        /* write out the seed        */
  527.     buf[1] = seed >> 8;
  528.     buf[2] = seed >> 16;
  529.     buf[3] = seed >> 24;
  530.     write(ofd, buf, 4);
  531.  
  532.     encrypt(ifd, ofd);
  533.     
  534.     } else {            /** decryption ******************/
  535.  
  536.     if (4 != read(ifd, buf, 4)) {    /* retrieve seed    */
  537.         fprintf(stderr, "Can't read '%s'\n", argv[1]);
  538.         exit(1);
  539.     }
  540.     seed  =  buf[0]        & 0x000000ff;
  541.     seed |= (buf[1] << 8)  & 0x0000ff00;
  542.     seed |= (buf[2] << 16) & 0x00ff0000;
  543.     seed |= (buf[3] << 24) & 0xff000000;
  544.  
  545.     get_key(seed);        /* get the key            */
  546.  
  547.     inv_tab(perm_tab1);    /* invert permutation tables    */
  548.     inv_tab(perm_tab2);
  549.     
  550.     decrypt(ifd, ofd);
  551.     }
  552.  
  553.     close(ifd);
  554.     close(ofd);
  555.     exit(0);
  556. }
  557.  
  558. get_key(seed)
  559.     unsigned seed;
  560. {
  561.     char            buf[1024];
  562.     register int    i, j, k;
  563.     static char    *key_chars = 
  564.     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
  565.     register char   t;
  566.  
  567.     rnd_init(seed);
  568.  
  569.     printf("Key:");        /* I know, there are better ways */
  570.     gets(buf);
  571.  
  572.     for (i = 0, j = 0; buf[i] && i < 1024; i++)
  573.     for (k = 0; key_chars[k]; k++)
  574.         if (buf[i] == key_chars[k]) {
  575.         j++;
  576.         Fib[(7 * k) % 55] ^= 625111 * k + rnd_u();
  577.         buf[i] = '?';    /* munch key over        */
  578.         break;
  579.         }
  580.  
  581.     if (j < 10)
  582.     fprintf(stderr, "Warning: your key is rather short\n");
  583.  
  584.     i = rnd_u();        /* initial permutation table 1    */
  585.     for (j = 0; j < 256; j++) {
  586.     for (k = 0; k < 256; k++)
  587.         perm_tab1[j * 256 + k] = i + k;
  588.     i++;
  589.     }
  590.     for (j = 30000 + rnd_ri(30000l); j--;) {    /* shuffle pt 1 */
  591.     i = rnd_u();
  592.     k = (i & 0xff00) | ((i >> 24) & 0xff);
  593.     i &= 0xffff;
  594.                 /* the random number is broken into
  595.                  * 3 parts, n1, n2, n3 of 1 byte each.
  596.                  * the n1-th and n2-th elements of
  597.                                  * the n3-th permutation are transposed.
  598.                                  */
  599.     t = perm_tab1[k];
  600.     perm_tab1[k] = perm_tab1[i];
  601.     perm_tab1[i] = t;
  602.     }
  603.  
  604.     i = rnd_u();        /* initial permutation table 2    */
  605.     for (j = 0; j < 256; j++) {
  606.     for (k = 0; k < 256; k++)
  607.         perm_tab2[j * 256 + k] = i + k;
  608.     i++;
  609.     }
  610.     for (j = 30000 + rnd_ri(30000l); j--;) {    /* shuffle pt 2 */
  611.     i = rnd_u();
  612.     k = (i & 0xff00) | ((i >> 24) & 0xff);
  613.     i &= 0xffff;
  614.     t = perm_tab2[k];
  615.     perm_tab2[k] = perm_tab2[i];
  616.     perm_tab2[i] = t;
  617.     }
  618. }
  619.  
  620. inv_tab(pt)            /* compute inverse permutations */
  621.     char *pt;
  622. {
  623.     register int i, j;
  624.     char t[256];
  625.  
  626.     for (i = 0; i < 256; i++) {
  627.     for (j = 0; j < 256; j++)
  628.         t[pt[i * 256 + j] & 0xff] = j;
  629.     for (j = 0; j < 256; j++)
  630.         pt[i * 256 + j] = t[j];
  631.     }
  632. }
  633.  
  634. encrypt (ifd, ofd)        /* encrypt stuff        */
  635.     int ifd, ofd;
  636. {
  637.     register int i, j, k;
  638.     register unsigned long u;
  639.     register char *p;
  640.     char buf[1024];
  641.  
  642.     while (0 < (i = read(ifd, buf, 1024))) {
  643.     for (p = buf, j = i; j--; p++) {
  644.  
  645.         u = rnd_u();        /* draw a random number */
  646.  
  647.         k = *p & 0xff;        /* get char to encrypt    */
  648.  
  649.         k ^= u & 0xffff;        /* step 1        */
  650.         k = perm_tab1[k] & 0xff;
  651.  
  652.         k ^= (u >> 16) & 0xffff;    /* step 2        */
  653.         *p = perm_tab2[k];
  654.     }
  655.     write(ofd, buf, i);
  656.     }
  657. }
  658.  
  659. decrypt (ifd, ofd)        /* decrypt stuff        */
  660.     int ifd, ofd;
  661. {
  662.     register int i, j, k;
  663.     register unsigned long u;
  664.     register char *p;
  665.     char buf[1024];
  666.  
  667.     while (0 < (i = read(ifd, buf, 1024))) {
  668.     for (p = buf, j = i; j--; p++) {
  669.  
  670.         u = rnd_u();        /* draw a random number */
  671.  
  672.         k = *p & 0xff;        /* get char to decrypt    */
  673.  
  674.         k |= (u >> 16) & 0xff00;    /* undo step 2        */
  675.         k = (perm_tab2[k] ^ (u >> 16)) & 0xff;
  676.  
  677.         k |= u & 0xff00;        /* undo step 1        */
  678.         *p = perm_tab1[k] ^ u;
  679.     }
  680.     write(ofd, buf, i);
  681.     }
  682. }
  683. !E!O!F!
  684. -- 
  685.    --  Andreas Nowatzyk  (DC5ZV)
  686.  
  687.    Carnegie-Mellon University         Arpa-net:   agn@unh.cs.cmu.edu
  688.    Computer Science Department         Usenet:   ...!seismo!unh.cs.cmu.edu!agn
  689.