While dousing yet another "chaos encryption" rumor, Perry says-

...

All this "encryption with chaos" stuff just adds up to "look at my fancy PRNG"...

I think that's a very clear handle on chaos for people who know about PRNGs, or vice-versa. Chaos = PRNG. I wonder if there's any good cross-fertilization of the two fields beyond the obvious.

I am especially interested in the "strange attractors" aspect of chaos theory. A good article on strange attractors appeared in Scientific American in the early/mid '80s. (Mail/post me if you want me to look up the issue.) Douglas Hofstadter was the author (of Godel, Escher, Bach... an awesome book!). Strange attractors use feedback to "lock in". I have used strange attractors to find special points in n-dimensional spaces. It may be far-fetched, but strange attractors or some similar statistical/experimental method may be the means by which large numbers are factored some day.... Cort.

fnerd@smds.com (FutureNerd Steve Witham) writes: I think that's a very clear handle on chaos for people who know about PRNGs, or vice-versa. Chaos = PRNG. I wonder if there's any good cross-fertilization of the two fields beyond the obvious.

Here's an exchange from sci.crypt in 1991 that's relevant to chaos and cryptography. A guy was using the logistic function as his RNG. If you look at the output from my decryptions, that might explain why the Keno guy was getting only 19 out of 20 right instead of 20 out of 20. If the Keno RNG is based on some fractal-type function, then pieces are self-similar, which means you don't need to find the right piece of it... just a piece that's similar to the right seed, which need not be close at all. Total speculation, of course, without knowing what the RNG really was. Jim Gillogly Sterday, 29 Astron S.R. 1994, 20:12 ---------------------------------------------------------------------------- From: 2fmnsilly@kuhub.cc.ukans.edu (Otter) Newsgroups: sci.crypt Subject: Cryption system based on chaos mathmatics Message-Id: <1991Mar18.234703.29145@kuhub.cc.ukans.edu> Date: 19 Mar 91 05:47:03 GMT Organization: University of Kansas Academic Computing Services Lines: 50 Here is a simple (can you tell I just learned 'C') en/decryption algorithm based on the mathematics of chaos. It uses the magic number of the 'strange attractor' to produce the 'random' cipher characters for the data to be XOR'd with. It is written for Turbo C. Feedback is encouraged. /* crypt.c */ /* CHAOS encryption/decryption routine */ /*-------------------------------------*/ /* Written by Chris Raile 1989 */ /* 2fmnsilly@kuhub.cc.ukans.edu */ /* 2fmnsilly@ukanvax.bitnet */ /*-------------------------------------*/ /* Implementation: */ /* */ /* 'in' File to be en/decrypted */ /* 'out' Resulting en/decrypted file */ #include "stdio.h" main() { FILE *fptrin; FILE *fptrout; int i, ch; double r = 3.56994571869; double j, x=.31379412; /* <-- change numbers after 1st '3' */ fptrin = fopen("in","rb"); /* to alter encryption scheme (key) */ fptrout = fopen("out","wb"); while ( (ch=getc(fptrin)) != EOF) { x=(r*x)*(1-x); j=x*100; i=(int)j; ch=i^ch; putc(ch,fptrout); } fclose(fptrin); fclose(fptrout); } -- +------------------------------------+------------------------------+ | Reverend Chris "Otter" Raile from | 2fmnsilly@kuhub.cc.ukans.edu | | 'The Slackmeisters Of The Holy | 2fmnsilly@UKANVAX.BITNET | | Evaporated Milk' -- A division | | | of the Church of the SubGenius(TM) | "A CornNut could not drive | | | me to insanity--it's just | | *The best damned Amway salesman* | toasted corn." - Me | +------------------------------------+------------------------------+ ---------------------------------------------------------------------------- From: jim@rand.org (Jim Gillogly) Newsgroups: sci.crypt Subject: Re: Cryption system based on chaos mathmatics Summary: No good Keywords: chaos, index of coincidence Message-Id: <1991Mar19.172839.881@rand.org> Date: 19 Mar 91 17:28:39 GMT References: <1991Mar18.234703.29145@kuhub.cc.ukans.edu> Sender: news@rand.org Organization: Banzai Institute Lines: 99 Chris Raile suggests an encryption routine based on the logistic function. I won't state categorically that chaos isn't useful in cryptography, but this particular routine isn't cryptographically effective. If you use it to encrypt an input file of all a's, for example, you'll see some striking repetitions. As it happens, this implementation isn't particularly sensitive to initial conditions. The program below tests about 1000 key values in the given range (.3 to .4) and looks at the result. Here's a sample crypto file (hex dump from "od"): 0000000 0751 2746 3102 245d 3b49 2010 2c51 7043 0000020 3044 2711 2b43 3e5c 384b 7441 2c4f 3353 0000040 2a04 3557 3747 2259 234a 2143 7951 3858 0000060 2d49 3711 374d 2418 3543 744c 314d 2253 0000100 3604 3346 7950 3156 334a 3e01 5300 The analysis program is mildly instructive -- if you haven't used the Index of Coincidence to test for a successful decryption, you should. The I.C. for English is around 0.066, so the program prints out all the results it finds above .06 for our amusement. Here's the result: Key 0.3136: (IC 0.061) Knuuh tells us that random number generatoul shoumd#not be chosen at randoj. Key 0.3137: (IC 0.066) Knuth tells us that random number generatoul shoumd not be chosen at random1 Key 0.3138: (IC 0.066) Knuth tells us that random number generators should not be chosen at randoj. Key 0.3139: (IC 0.062) Knuth tellt?us th`t random number generators should not be chosen at randoj. Key 0.3169: (IC 0.061) Jotwh tellt?us th`t random number generators should not be chosen at randoj. Key 0.3170: (IC 0.061) Jotwh tellt?us th`t random number generators should not be chosen at randoj. Key 0.3171: (IC 0.065) Jotwh tells us that random number generatorl should not be chosen at random1 Key 0.3172: (IC 0.061) Jotwh tells us that random number generatoul shoumd#not be chosen at random1 None of these is perfect, but it certainly tells us where to try refining our key. It's interesting that the decryptions get back on track after initial derailments in some case... no butterfly effect here. Jim Gillogly Banzai Institute ------- program follows ----- /* CHAOS encryption analysis hack, Jim Gillogly, 19 Mar 91 */ /* Tries a spread of initial keys and sees what comes close. */ /* Addresses the following program: */ /* CHAOS encryption/decryption routine */ /* Written by Chris Raile 1989 */ #include <stdio.h> #include <ctype.h> double english_like(); main() { FILE *in; char ct[200], pt[200], *s, *t; /* Room for a line of ciphertext */ double r = 3.56994571869; double x, x0, e; int len, i; in = fopen("out","rb"); /* Read the ciphertext */ for (s = ct; (*s = getc(in)) != EOF; s++); len = s - ct; for (x0 = .3; x0 < .4; x0 += .0001) /* Try about a thousand keys */ { /* Decrypt using key x0 */ for (x = x0, i = 0, s = ct, t = pt; i < len; s++, t++, i++) { x *= r * (1 - x); if (! isprint(*t = ( (int) (100 * x)) ^ *s)) break; } *t = 0; if ((e = english_like(pt)) > .060) printf("Key %5.4f: (IC %5.3f)\n %s\n", x0, e, pt); } } double english_like(s) /* Do index of coincidence on a string */ char *s; /* 26-letter English comes out around .066 */ { int n, i; char freqs[256]; double sum; if ((n = strlen(s)) <= 1) return 0.; bzero(freqs, 256); /* Clear the counters */ while (*s) freqs[*s++]++; /* Frequency count */ for (i = sum = 0; i < 256; i++) sum += freqs[i] * (freqs[i] - 1); return sum / n / (n - 1); } -- Jim Gillogly jim@rand.org ----------------------------------------------------------------------------