SpudFiles

I have been attempting to create a random number generator for the past few days using clock drift between the system time ticks (accurate to 1 millisecond in the language I'm writing in ((QBASIC)) ), and the CPU clock cycles available to the application I wrote per second.

While I was able to obtain reasonably good results (see my website at http://www.markfh11q.net/generate.php?id=0&file=math ), I'm thinking I need to go in another direction. Here are the reasons.

1.) The cycles/second don't vary as much as I like. While I am using the modulus 26 to generate numbers 0-25, there is a fair amount of bias that must be corrected (using the Von Neumann method).

2.) When the application is run under Windows, the CPU cycles tend to level out at a constant, halting the output of the program (because of the bias control method).


So, I figured: why not try the same thing with a 556 timer chip?

Basically, I would connect the two outputs to two individual port addresses on the computer. Then, QBASIC would read off the binary from their ouput (0 for 0V and 1 for the voltage allowed that port).

One half of the timer will run fairly slow, but not slow enough to make generation of the random numbers too slow. The other half would run extremely fast, so that small variations are more detectable. Variations, I think, are inevitable, due to noise and variations of the chips. The two independent circuits could also be separated physically to different areas of the CPU case to produce more variation.

The program starts a loop on a tick (bit 1) of the slow timer. During this loop, it counts the ticks on the fast timer. When the loop is finished, it takes this count MOD 2 and assigns that to a binary output in a pair. The process is repeated to obtain the second bit in the pair. If the bits are equal, the pair is discarded. If they differ, the first bit in the pair is stored in the final binary sequence.

This continues until a certain number of bits is received, preferably user-defined. The bits are then translated into a long integer which is then fed as a seed to QBASICS random number generator, which is used to generate two large blum primes.

The process repeats until another binary number of the specified length is reached. This number is fed as the seed value into the Blum Blum Shub pseudorandom-number generator, which then outputs the final values.


All of this counts on the two 556 timers being able to generate enough randomness for the process. Does anybody see any problems with this? I was going to use crystals for the oscillation, but they seemed too precise to work well.

That's it. Comments? Suggestions? Thanks for reading. All of this is going to be used for a small cryptography suite I'm building, which handles plaintext messages using a onetime-pad cipher.

markfh11q wrote:The program starts a loop on a tick (bit 1) of the slow timer. During this loop, it counts the ticks on the fast timer. When the loop is finished, it takes this count MOD 2 and assigns that to a binary output in a pair. The process is repeated to obtain the second bit in the pair. If the bits are equal, the pair is discarded. If they differ, the first bit in the pair is stored in the final binary sequence.

This continues until a certain number of bits is received, preferably user-defined. The bits are then translated into a long integer which is then fed as a seed to QBASICS random number generator, which is used to generate two large blum primes.

I don't see why you omit a pair that have the same MOD2 bit. Shouldn't you keep any pair which have different raw counts (before the MOD 2)?

I would think that over a short time frame (a couple seconds) the second timer's counts will be a gaussian distribution about an average. You are taking the LSb (least significant bit) which will be the difference between the average and the current count MOD2. So, if the current count matches the average (which is never actually calculated or measured) then the LSb is 0. If the current count is off of the average by +/- 1 count then the LSb is 1. If the count is off the average by +/- 2 then the LSb is back to zero etc. If the distribution is wide enough, and you take enough samples, then the average LSb will tend towards zero. If the distribution is narrow, then the 1/0 probabilites might not be the same?

There may also be some cross-talk between the 555's and the system clock, 60Hz noise from the power supply, the video card, etc. A lot of that can be blocked by shielding the 555's but there will still be crosstalk via the power supply. I think the cross talk may tend synchronize the two 555s to a certain extent.

Aren't there other hardware methods for generating random numbers? Particularly for generating random bits? A high gain amplifier and a single bit AD converter (comparator) for example?

I've always wondered if you couldn't use Google as a random number generator.

Sounds like it should be fine. You could write yourself a little dot plotter program that will print an X,Y coordinate dot in say a 640 x 480 window that is directly relative in some way to your "random numbers"...truncate LSBs, MOD, do whatever you have to do to get them to in fit in the window array.

As the dots fill the window, you should be able to see patternizing tendencies show up as thicker bands or groupings. An ideal random generator should produce no significant banding or grouping of dots.

There are several motherboard and CPU registers, a sound card sample. etc. that could offer reasonably random number seeds especially when calculating with a time factor and each other. Do you have any particular reason to use an external hardware source?

starman wrote:As the dots fill the window, you should be able to see patternizing tendencies show up as thicker bands or groupings. An ideal random generator should produce no significant banding or grouping of dots.

That's an easy way to look for non-randomness in a random number generator. It's easy to do in QBASIC, just take pairs of "random" numbers, scale to the screen dimensions and POKEm (PSETm?) to a graphics window. The generator in the older versions of Windows Basic was pretty non-random and gave a distinct banding pattern.

What about just measuring Electromagnetic radiation around your machine and use that as a seed...it's pretty random.

I could do that. I would just take more time to do right.

Jimmy, a lot of the bias correction occurs taking it two bits at a time and removing pairs of the same. The frequencies of the two states are still skewed, but they're closer to 0.5 than without the "whitening" process.

I just implemented this method today in a Blackjack program. I'm not done with the program yet (all you do is play against yourself for now), but I used pretty much the same method as I already did, with a small change. I generated a binary byte with the method described above using the CPU clock and system timer as oscillators, and then converted the byte to a decimal (0-255). I then used this to seed QBASIC's RNG, and then used that to "shuffle" the cards (assign a random permutation to a 52 value array of with numbers 1-52). So far, I think it's pretty fair enough for a game, but it'd be nice to have better methods for cryptography.

TurboSuper wrote:What about just measuring Electromagnetic radiation around your machine and use that as a seed...it's pretty random.

The challenge with that approach is the the radiation is not random. The PC will generate a fair amount of RF and EM all by itself. That radiation will not be random, it'll have high frequencies from the system clock and various other clocks in the 'puter. It'll have high frequecnies from the monitor scan circuitry. Your house will have non-random RF from motors, TVs, etc. If you recorded the EM radiation it'll look random but to ensure that it actually is random will be a challenge.

Why does it has to be a hardware random number generator?
C++ does quite a good job at generating random numbers.
And it does it with math, it's a very simple formula actually, just google it.
The random numbers are predictable though, so you have to deliver a seed to the algorithm.
The current time in milliseconds is good enough
Unless you're trying to create a blackjack program that other people will use too...
Because you then can just hook the random number generator, and return your own values so you know the outcome...
But that's something you can't avoid. You will experience this problem with almost any algorithm.
The only solution then is a good working anti-cheat, and that's quite hard.

SpoT^
EDIT: Oh yeah this formula favors the low numbers by a TINY (VERY TINY) amount

spot wrote:Why does it has to be a hardware random number generator?
C++ does quite a good job at generating random numbers.
And it does it with math, it's a very simple formula actually, just google it.
The random numbers are predictable though, so you have to deliver a seed to the algorithm.
The current time in milliseconds is good enough

If you read Mark's original post you'll find that what he is trying to generate is the seed.

spot, this RNG will be used for cryptography.

Let's say we have a fairly large message. If the key is perfectly random, and consists of the letters A-B, then the total possible keys would be 26ⁿ, where n is the length of the message and key.

Even if they could test every key with a computer, they would also get every conceivable message of the same length in the process.

If I simply RANDOMIZE'd the RNG in QBASIC (or any other language) with the time in seconds past midnight (accurate to milliseconds, but any seed passed to the RNG is INT'd, I believe), then the number of key possibilities is reduced to 86,400 , of which the key I actually used may produce a distinct output from the other possible sequences. If an attacker knew I just seeded a RNG with the time in seconds past midnight, his job would be a fair bit easier. I'm also probably going to be using the BBS algorithm instead of the built-in RNG just for it's reputation in cryptography.

BTW, in the meantime while I am waiting for a free weekend back home to try some of this, I've been toying with the idea of running multiple processes doing the same loop, which may or may not cause a more variable CPU "slice" available to each program, and a more spread output from the processes which could be whitened further. We'll see how that goes once I look up how to do it in QBASIC. The good thing about the language is that it's fairly easy to run DOS shell commands, which will aid in doing the whole thing automated.