USS Clueless Stardate 20010613.2051

  USS Clueless

             Voyages of a restless mind

Main:
normal
long
no graphics

Contact
Log archives
Best log entries
Other articles

Site Search

Stardate 20010613.2051 (On Screen via long range sensors): What is a "random number"? When I was in college, one of my fellow students pointed out that there is no such thing as a "random number": is 1 a random number? How about 3.1415926 or 2.718281828? His point was that there are no random numbers, only random sequences. Then someone else pointed out that there were also no random sequences, only sequences we did not fully understand.

Actually, though, there is a legitimate definition of a random number which stands alone, outside a sequence. That would be a number from within a choice space such that there is no particular reason to expect that number to be favored over any of the other numbers available in the choice space. So even if it is familiar it doesn't really matter if its familiarity is coincidence. If some other party elsewhere would not expect that particular number to have a better than average chance of being chosen, then it is "random".

Where this has practical significance is, of course, in cryptography. If you're trying to choose a session key then it needs to be "random" according to this definition. (According to the book Crypto, one implementation of Netscape Navigator which implemented a session key didn't use a good algorithm for choosing its number, such that certain choices in the choice space were much more likely to be selected -- and those could be predicted by someone else. Netscape quickly fixed this flaw when it was pointed out.)

Also, my college friends were wrong even about sequences: It is possible to create some sequences for which it is theoretically impossible to have enough knowledge to predict them. This article describes several approaches which have been used and they all come down to using certain physical effects which ultimately derive from quantum mechanics. Interestingly, they didn't mention the one which is actually easiest to implement and use: thermal noise. (The one which uses the jitter on the output of a video camera is based on thermal noise, but their solution is far more elaborate than it needs to be.) The most common place to encounter thermal noise is as background hiss on a stereo amplifier when the volume is turned up with no music playing. A good amplifier design will have very little of this, but it's impossible to eliminate it entirely. And if you really want a source of random numbers, a hissy amplifier with no input can serve quite nicely. I keep waiting for someone to build a small USB device containing a single-chip microcomputer and a bit of other circuitry, which will return a random number gotten from a physical source when asked. With modern technology such a device could be put into a package a quarter the size of a pack of cigarettes and be powered by the USB itself. But I guess the need isn't really there yet, because for most purposes it's possible to create a good-enough random number using things like "how many milliseconds has it been since the last time this computer booted" and "What is the exact pixel location of the mouse pointer right now" as seeds. The problem with those kinds of things is that they really aren't enough to fully smear a 512-bit choice space, which means that your 512-bit session key isn't really going to be 512 bits strong. (randomize)

Captured by MemoWeb from http://denbeste.nu/entries/00000095.shtml on 9/16/2004