Source Code 1992 March

home *** CD-ROM | disk | FTP | other *** search

/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / misc / volume02 / xrand < prev next >

Wrap

Internet Message Format | 1991-08-27 | 20.8 KB

From mipos3!intelca!oliveb!ames!necntc!ncoast!allbery Fri Apr 15 12:42:45 PDT 1988 Article 349 of comp.sources.misc: Path: td2cad!mipos3!intelca!oliveb!ames!necntc!ncoast!allbery From: agn@UNH.CS.CMU.EDU (Andreas Nowatzyk) Newsgroups: comp.sources.misc Subject: v02i096: xrand, xcrypt -- a random number generator & application Keywords: pseudo random numbers, rand, random, encryption, cipher Message-ID: <8804131846.AA29500@rutgers.edu> Date: 13 Apr 88 17:19:34 GMT Sender: allbery@ncoast.UUCP Reply-To: agn@UNH.CS.CMU.EDU (Andreas Nowatzyk) Organization: Carnegie-Mellon University, CS/RI Lines: 681 Approved: allbery@ncoast.UUCP comp.sources.misc: Volume 2, Issue 96 Submitted-By: "Andreas Nowatzyk" <agn@UNH.CS.CMU.EDU> Archive-Name: xrand The attached random-number generator was writen because of a need for a good source of random numbers for a research project that involved systems without such facility (for example a research prototype with only a C-compiler and minimal libraries). Since the results are critical to my work, a serious attempt was made to write a 'really good' RNG: that is several CPU weeks on assorted machines were spend to try out (and discard) various approaches. The generator below is based on 2 well known methods: Linear Congruential (LCGs) and Additive Congruential generators (ACGs). The LCG produces the longest possible sequence of 32 bit 'random' numbers, each being unique in that sequence (it has only 32 bits of state). It suffers from 2 problems: a) Independence isn't great, that is the (n+1)th number is somewhat related to the preceding one, unlike flipping a coin where knowing the past outcomes don't help to predict the next result. b) Taking parts of a LCG generated number can be quite non-random: for example, looking at only the least significant byte gives a permuted 8-bit counter (that has a period length of only 256). The advantage of an LCA is that it is perfectly uniform when run for the entire period length (and very uniform for smaller sequences too, if the parameters are chosen carefully). ACG's have extremly long period lengths and provide good independence. Unfortunately, uniformity isn't not too great. Furthermore, I didn't find any theoretically analysis of ACG's that addresses uniformity. The RNG given below will return numbers generated by an LCA that are permuted under control of a ACG. 2 permutations take place: the 4 bytes of one LCG generated number are subjected to one of 16 permutations selected by 4 bits of the ACG. The permutation a such that byte of the result may come from each byte of the LCG number. This effectively destroys the structure within a word. Finally, the sequence of such numbers is permuted within a range of 256 numbers. This greatly improves independence. xcrypt is a recreational application (as I have little need for secrecy) of this random number generator to en/decrypt files. However, I do believe that this byproduct is quite strong and a challenge ($50) to this effect has been posted to sci.crypt. Breaking xcrypt would probably reveal a flaw in xrand and I'm highly interested in any such problem. Cheers -- Andreas -------------------- Cut here -------------------- # # type sh /usru0/agn/x.shar to unpack this archive. # echo extracting xrand.1... cat >xrand.1 <<'!E!O!F!' .TH XRAND 3 4/13/88 .CM 4 .SH NAME xrand \- pseudo random number generators .SH SYNOPSIS void rnd_init(seed) unsigned seed; long rnd_i() unsigned long rnd_u() long rnd_ri(range) long range; double rnd_01d() double rnd_ned(lamda) double lamda; .SH DESCRIPTION xrand is a collection of pseudo-random number generators that were carefully tested for uniform distribution and independence. These tests included testing parts of the generated numbers (say a byte or a bit) for the same properties. .B rnd_init must be called before any random numbers are drawn. Different seeds will yield different, but deterministic sequences of random numbers with like statistical properties. .B rnd_i returns positive integers, .B rnd_u returns unsigned integers (all 32 bit are .I random ), .B rnd_ri returns integers in the range [0..range-1], .B rnd_01d returns doubles in the range of [0.0..1.0), .B rnd_ned returns negative-exponential distributed doubles in the range [0.0..+infinity). .SH ENVIRONMENT .B rnd_ned requires .B log() from the math library. .SH "SEE ALSO" .I rand(3C), which produces pseudo-random numbers which are not very random and .I random(3), which is about 45% faster than xrand but has inferior uniformity. .SH BUGS .B xrand assumes that long words have 32 bits and that 2's complement arithmetic is used. .SH HISTORY .TP 13-Apr-88 Andreas Nowatzyk (agn) at Carnegie-Mellon University Created. !E!O!F! # # type sh /usru0/agn/x.shar to unpack this archive. # echo extracting xrand.c... cat >xrand.c <<'!E!O!F!' #include <math.h> /* Random number generators: * * rnd_init (unsigned seed) * : initializes the generator * * rnd_i () : returns positive integers [0,0x7fffffff] * rnd_u () : returns unsigned's [0,0xffffffff] * rnd_ri (long n) : returns positive integers [0,n-1] * rnd_01d () : returns doubles [0.0,1.0) * Note: ")" is no typo - rnd_01d will not return a 1.0, * but can return the next smaller FP number. * rnd_ned (double lam): returns neg. exponential distributed doubles [0.0,+inf) * * Algorithm M as describes in Knuth's "Art of Computer Programming", Vol 2. 1969 * is used with a linear congruential generator (to get a good uniform * distribution) that is permuted with a Fibonacci additive congruential * generator to get good independence. * * Bit, byte, and word distributions were extensively tested and pass * Chi-squared test near perfect scores (>7E8 numbers tested, Uniformity * assumption holds with probability > 0.999) * * Run-up tests for on 7E8 numbers confirm independence with * probability > 0.97. * * Plotting random points in 2d reveals no apparent structure. * * Autocorrelation on sequences of 5E5 numbers (A(i) = SUM X(n)*X(n-i), i=1..512) * results in no obvious structure (A(i) ~ const). * * On a SUN 3/60, rnd_u() takes about 19.4 usec per call, which is about 44% * slower than Berkeley's random() (13.5 usec/call). * * Except for speed and memory requirements, this generator outperforms * random() for all tests. (random() scored rather low on uniformity tests, * while independence test differences were less dramatic). * * Thanks to M.Mauldin, H.Walker, J.Saxe and M.Molloy for inspiration & help. * * (c) Copyright 1988 by A. Nowatzyk * */ /* LC-parameter selection follows recommendations in * "Handbook of Mathematical Functions" by Abramowitz & Stegun 10th, edi. */ #define LC_A 66049 /* = 251^2, ~= sqrt(2^32) */ #define LC_C 3907864577 /* result of a long trial & error series */ #define Xrnd(x) (x * LC_A + LC_C) /* the LC polynomial */ static unsigned long Fib[55]; /* will use X(n) = X(n-55) - X(n-24) */ static int Fib_ind; /* current index in circular buffer */ static unsigned long Xrnd_var; /* LCA - recurrence variable */ static unsigned long auxtab[256]; /* temporal permutation table */ static unsigned long prmtab[64] = { /* spatial permutation table */ 0xffffffff, 0x00000000, 0x00000000, 0x00000000, /* 3210 */ 0x0000ffff, 0x00ff0000, 0x00000000, 0xff000000, /* 2310 */ 0xff0000ff, 0x0000ff00, 0x00000000, 0x00ff0000, /* 3120 */ 0x00ff00ff, 0x00000000, 0xff00ff00, 0x00000000, /* 1230 */ 0xffff0000, 0x000000ff, 0x00000000, 0x0000ff00, /* 3201 */ 0x00000000, 0x00ff00ff, 0x00000000, 0xff00ff00, /* 2301 */ 0xff000000, 0x00000000, 0x000000ff, 0x00ffff00, /* 3102 */ 0x00000000, 0x00000000, 0x00000000, 0xffffffff, /* 2103 */ 0xff00ff00, 0x00000000, 0x00ff00ff, 0x00000000, /* 3012 */ 0x0000ff00, 0x00000000, 0x00ff0000, 0xff0000ff, /* 2013 */ 0x00000000, 0x00000000, 0xffffffff, 0x00000000, /* 1032 */ 0x00000000, 0x0000ff00, 0xffff0000, 0x000000ff, /* 1023 */ 0x00000000, 0xffffffff, 0x00000000, 0x00000000, /* 0321 */ 0x00ffff00, 0xff000000, 0x00000000, 0x000000ff, /* 0213 */ 0x00000000, 0xff000000, 0x0000ffff, 0x00ff0000, /* 0132 */ 0x00000000, 0xff00ff00, 0x00000000, 0x00ff00ff /* 0123 */ }; union hack { /* used to access doubles as unsigneds */ double d; unsigned long u[2]; }; static union hack man; /* mantissa bit vector */ rnd_init (seed) /* modified: seed 0-31 use precomputed stuff */ unsigned seed; { register unsigned long u; register int i; double x, y; union hack t; static unsigned seed_tab[32] = { 0xbdcc47e5, 0x54aea45d, 0xec0df859, 0xda84637b, 0xc8c6cb4f, 0x35574b01, 0x28260b7d, 0x0d07fdbf, 0x9faaeeb0, 0x613dd169, 0x5ce2d818, 0x85b9e706, 0xab2469db, 0xda02b0dc, 0x45c60d6e, 0xffe49d10, 0x7224fea3, 0xf9684fc9, 0xfc7ee074, 0x326ce92a, 0x366d13b5, 0x17aaa731, 0xeb83a675, 0x7781cb32, 0x4ec7c92d, 0x7f187521, 0x2cf346b4, 0xad13310f, 0xb89cff2b, 0x12164de1, 0xa865168d, 0x32b56cdf }; if (seed < 32) u = seed_tab[seed]; else u = seed ^ seed_tab[seed & 31]; for (i = 55; i--;) /* set up Fibonacci additive congruential */ Fib[i] = u = Xrnd(u); for (i = 256; i--;) auxtab[i] = u = Xrnd(u); Fib_ind = u % 55; /* select a starting point */ Xrnd_var = u; if (sizeof(x) != 2 * sizeof(unsigned long)) { x = 0.0; y = 1.0; y /= x; /*** intentional divide by 0: rnd_01d will not work because a double doesn't fit in 2 unsigned longs on your machine! ***/ }; x = 1.0; y = 0.5; do { /* find largest fp-number < 2.0 */ t.d = x; x += y; y *= 0.5; } while (x != t.d && x < 2.0); man.d = 1.0; man.u[0] ^= t.u[0]; man.u[1] ^= t.u[1]; /* man is now 1 for each mantissa bit */ } long rnd_i () /* * returns a positive, uniformly distributed random number in [0,0x7fffffff] */ { register unsigned long i, j, *t = Fib; i = Fib_ind; j = t[i]; /* = X(n-55) */ j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */ t[i] = j; if (++i >= 55) i = 0; Fib_ind = i; t = &auxtab[(j >> 24) & 0xff]; i = *t; Xrnd_var = *t = Xrnd(Xrnd_var); t = &prmtab[j & 0x3c]; j = *t++ & i; j |= *t++ & ((i << 24) | ((i >> 8) & 0x00ffffff)); j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff)); j |= *t & ((i << 8) | ((i >> 24) & 0x000000ff)); return j & 0x7fffff; } unsigned long rnd_u () /* * same as rnd_i, but gives full 32 bit range */ { register unsigned long i, j, *t = Fib; i = Fib_ind; j = t[i]; /* = X(n-55) */ j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */ t[i] = j; if (++i >= 55) i = 0; Fib_ind = i; t = &auxtab[(j >> 24) & 0xff]; i = *t; Xrnd_var = *t = Xrnd(Xrnd_var); t = &prmtab[j & 0x3c]; j = *t++ & i; j |= *t++ & ((i << 24) | ((i >> 8) & 0x00ffffff)); j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff)); j |= *t & ((i << 8) | ((i >> 24) & 0x000000ff)); return j; } long rnd_ri (rng) long rng; /* * randint: Return a random integer in a given Range [0..rng-1] * Note: 0 < rng */ { register unsigned long r, a; do { r = rnd_i(); a = (r / rng) + 1; a *= rng; } while (a >= 0x7ffffff); a--; return a - r; } double rnd_01d () /* * returns a uniformly distributed double in the range of [0..1) * or 0.0 <= rnd_01d() < 1.0 to be precise * * Note: this code assumes that 2 'unsigned long's can hold a 'double' * (works on SUN-3's, SUN-4's, MIPS, VAXen, IBM RT's) */ { union hack t; t.d = 1.0; t.u[0] |= rnd_u() & man.u[0]; /* munch in 1st part */ t.u[1] |= rnd_u() & man.u[1]; /* munch in 2nd part */ return t.d - 1.0; } double rnd_ned (lam) double lam; /* * returns a neg. exponential distributed double in the range of [0..+infinity) * or 0.0 <= rnd_neg() < +infinity to be precise * * Note: this code assumes that 2 'unsigned long's can hold a 'double' * it also assumes that 'log()' behaves as advertised. * */ { union hack t; t.d = 1.0; t.u[0] |= rnd_u() & man.u[0]; /* munch in 1st part */ t.u[1] |= rnd_u() & man.u[1]; /* munch in 2nd part */ return -log(2.0 - t.d) / lam; } !E!O!F! # # type sh /usru0/agn/x.shar to unpack this archive. # echo extracting xcrypt.1... cat >xcrypt.1 <<'!E!O!F!' .TH XCRYPT 1 4/13/88 .CM 4 .SH NAME xcrypt \- data encryption/decryption program .SH SYNOPSIS encrypt <plain-text file> <cipher-text file> decrypt <cipher-text file> <plain-text file> .SH DESCRIPTION .B xcrypt uses the observation that a good pseudo-random number generator can be used to generate a strong encryption. .B xcrypt is based on .B xrand(3) that was extensively tested for randomness (some CPU-week were devoted to this effort). .B xcrypt invoked with a name starting with either 'e' or 'E' will write an encrypted version of the plain-text file to the cipher text file. Any other invocation will cause an decryption. Both files are treated as binary files. ASCII-text files will become binary files upon encryption. The key string will be prompted from <stdin>. .B xcrypt will compute for a few seconds before starting the translation, which is essentially I/O limited. This initialization phase is indispensable and was designed to thwart brute force key guessing attempts. Key lengths of 10-1000 characters are meaningful. .SH ENVIRONMENT .B xcrypt requires .B xrand(3) .SH HISTORY .TP 13-Apr-88 Andreas Nowatzyk (agn) at Carnegie-Mellon University Created. !E!O!F! # # type sh /usru0/agn/x.shar to unpack this archive. # echo extracting xcrypt.c... cat >xcrypt.c <<'!E!O!F!' /* * xcrypt: a Encryption / Decryption program. * * xcrypt is loosely based on an idea that was proposed by M.Mauldin @ CMU * (and potentially many other): use a pseudo-random number generator (RNG) * to produce one-time pads. * * So, the basic approach is simply to initialize the RNG with the * encryption key and then decide what part of the RNG output is * used to encrypt the message. In xcrypt, a high quality RNG is * employed that was extensively tested for uniform distribution * and independence. This is expected to yield a rather strong encryption. * * Selecting the starting point of the random number sequence is based on a * seed that is derived from the unix time()-call and the process ID. * This seed (4 bytes) is prefixed to the ciphertext (similar to the typical * unix password encoding scheme). You may consider transmitting the seed * by an other channel. * * Actually, both the seed and the key are used to determine the initial * state of the RNG, which is less computationally expensive than letting * the RNG run for value-of(seed) iterations. * * This particular RNG has 9990bits of state (yes, more than 1Kbyte!), so * so keys of 1000 char are still meaningful (albeit cumbersome). * * In order to thwart a key-guessing, brute force attack, the RNG is * run for 60000 to 120000 iterations before the output is used for * encryption. The RNG output of this initialization phase is used to * construct 2 sets of 256 permutations of [0,1,...,255], that will * be used later. Thus, any shortcut of these iterations (the actual * number depends on the key and is not known to the attacker) would * also have to produce all the intermediate results. Given the low * complexity of an iteration, it's non-linearity and the intermediate * result requirement, it appears to me that it is provable that no * dramatic shortcut exists. * * The RNG delivers 32bit random numbers. All 32 bits are * used to encrypt an 8bit character: * 1. use 8bit to XOR the plaintext character * 2. use 8bit to select a random permutation (from set 1, see above) * 3. use 8bit to XOR the result of step 2 * 4. use 8bit to select a random permutation (set 2) * Every bit of the RNG output will change the plain-to-cipher text * character mapping, but unlike the simple XOR case, it is not possible * to reconstruct the RNG output from a plain/cipher text pair (you * would have to guess about 24bits!). * * The strength of xcrypt is based on: * 1. a high quality RNG with plenty of state information. * 2. a computation intensive initialization phase * 3. 'information loss' in the encryption phase that * prevents the reconstruction of the 'PAD' even in the * known plain text case. * * Note: 'xcrypt' is a small just-for-fun program, but the underlying * RNG was written and extensively tested as part of a serious * research project. * * April, 1988 A. Nowatzyk * */ #include <stdio.h> #include <sys/file.h> char perm_tab1[0x10000]; /* permutation tables */ char perm_tab2[0x10000]; #include "xrand.c" main(argc, argv) int argc; char *argv[]; { unsigned seed; char buf[4]; int ifd, ofd; if (argc != 3 || 0 > (ifd = open(argv[1], O_RDONLY)) || 0 > (ofd = open(argv[2], O_WRONLY | O_CREAT, 0600))) { fprintf(stderr, "en/decrypt <input-file> <output-file>\n"); exit(1); } if (*argv[0] == 'e' || *argv[0] == 'E') { /** encryption **/ seed = time(0l); /* get an arbitrary seed */ seed ^= getpid(); get_key(seed); /* get the key */ buf[0] = seed; /* write out the seed */ buf[1] = seed >> 8; buf[2] = seed >> 16; buf[3] = seed >> 24; write(ofd, buf, 4); encrypt(ifd, ofd); } else { /** decryption ******************/ if (4 != read(ifd, buf, 4)) { /* retrieve seed */ fprintf(stderr, "Can't read '%s'\n", argv[1]); exit(1); } seed = buf[0] & 0x000000ff; seed |= (buf[1] << 8) & 0x0000ff00; seed |= (buf[2] << 16) & 0x00ff0000; seed |= (buf[3] << 24) & 0xff000000; get_key(seed); /* get the key */ inv_tab(perm_tab1); /* invert permutation tables */ inv_tab(perm_tab2); decrypt(ifd, ofd); } close(ifd); close(ofd); exit(0); } get_key(seed) unsigned seed; { char buf[1024]; register int i, j, k; static char *key_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; register char t; rnd_init(seed); printf("Key:"); /* I know, there are better ways */ gets(buf); for (i = 0, j = 0; buf[i] && i < 1024; i++) for (k = 0; key_chars[k]; k++) if (buf[i] == key_chars[k]) { j++; Fib[(7 * k) % 55] ^= 625111 * k + rnd_u(); buf[i] = '?'; /* munch key over */ break; } if (j < 10) fprintf(stderr, "Warning: your key is rather short\n"); i = rnd_u(); /* initial permutation table 1 */ for (j = 0; j < 256; j++) { for (k = 0; k < 256; k++) perm_tab1[j * 256 + k] = i + k; i++; } for (j = 30000 + rnd_ri(30000l); j--;) { /* shuffle pt 1 */ i = rnd_u(); k = (i & 0xff00) | ((i >> 24) & 0xff); i &= 0xffff; /* the random number is broken into * 3 parts, n1, n2, n3 of 1 byte each. * the n1-th and n2-th elements of * the n3-th permutation are transposed. */ t = perm_tab1[k]; perm_tab1[k] = perm_tab1[i]; perm_tab1[i] = t; } i = rnd_u(); /* initial permutation table 2 */ for (j = 0; j < 256; j++) { for (k = 0; k < 256; k++) perm_tab2[j * 256 + k] = i + k; i++; } for (j = 30000 + rnd_ri(30000l); j--;) { /* shuffle pt 2 */ i = rnd_u(); k = (i & 0xff00) | ((i >> 24) & 0xff); i &= 0xffff; t = perm_tab2[k]; perm_tab2[k] = perm_tab2[i]; perm_tab2[i] = t; } } inv_tab(pt) /* compute inverse permutations */ char *pt; { register int i, j; char t[256]; for (i = 0; i < 256; i++) { for (j = 0; j < 256; j++) t[pt[i * 256 + j] & 0xff] = j; for (j = 0; j < 256; j++) pt[i * 256 + j] = t[j]; } } encrypt (ifd, ofd) /* encrypt stuff */ int ifd, ofd; { register int i, j, k; register unsigned long u; register char *p; char buf[1024]; while (0 < (i = read(ifd, buf, 1024))) { for (p = buf, j = i; j--; p++) { u = rnd_u(); /* draw a random number */ k = *p & 0xff; /* get char to encrypt */ k ^= u & 0xffff; /* step 1 */ k = perm_tab1[k] & 0xff; k ^= (u >> 16) & 0xffff; /* step 2 */ *p = perm_tab2[k]; } write(ofd, buf, i); } } decrypt (ifd, ofd) /* decrypt stuff */ int ifd, ofd; { register int i, j, k; register unsigned long u; register char *p; char buf[1024]; while (0 < (i = read(ifd, buf, 1024))) { for (p = buf, j = i; j--; p++) { u = rnd_u(); /* draw a random number */ k = *p & 0xff; /* get char to decrypt */ k |= (u >> 16) & 0xff00; /* undo step 2 */ k = (perm_tab2[k] ^ (u >> 16)) & 0xff; k |= u & 0xff00; /* undo step 1 */ *p = perm_tab1[k] ^ u; } write(ofd, buf, i); } } !E!O!F! -- -- Andreas Nowatzyk (DC5ZV) Carnegie-Mellon University Arpa-net: agn@unh.cs.cmu.edu Computer Science Department Usenet: ...!seismo!unh.cs.cmu.edu!agn