Having learned about chaos theory at university some years ago, I've been curious ever since to know whether it has found any practical use in computing.
Let me explain where I imagine it could be used...
Chaos, in the mathematical sense, is stochastic ("random") behaviour in a deterministic ("non-random") system. Chaotic systems have three key properties:
- they are bounded
- they are non-repeating
- they are sensitive to initial conditions
For example, take the chaotic iterative map function f(x) = 2x2 - 1. For inputs between -1 and +1 (excluding -1, -0.5, 0, 0.5 and 1), iterating this function yields chaotic results. For example:
x | f(x) ----------+----------- 0.700000 | -0.020000 -0.020000 | -0.999200 -0.999200 | 0.996801 0.996801 | 0.987226 0.987226 | 0.949229 0.949229 | 0.802070 0.802070 | 0.286633 0.286633 | -0.835683 -0.835683 | 0.396731
The results are bounded (output is always greater than -1.0, less than 1.0) and non-repeating (try iterating over it a few thousand times – you won't see any emerging pattern). If you vary the first value of x by even a tiny amount (e.g. use 0.700001) you'll start to see the results diverging considerably from those above after just a few iterations. In other words, this function is also sensitive to initial conditions.
I could imagine this having a number of applications in computing as a predictable pseudo-random number generator. For example, you could use something like the above function as the basis for one of those secure key fobs used for "something you have with you" authentication. Imagine using f(x) = 2x2 - 1 in such a device. Provided the device and the server were seeded with exactly the same initial input, they'll continue to remain in sync forever (allowing for timing issues), since the function is completely deterministic. Let's say you used the first six digits after the decimal point as the key displayed to the user and validated by the server. If someone looked over your shoulder, saw the current value and fed it into the same function, they still couldn't predict future values of the device thanks to the function's sensitivity to initial conditions: only having the input to six decimal places is worthless.
So, is my intuition correct? Has chaos found such a use in computer security?