Random Bit Generator

That's there in case some random glitch inserts or removes a bit, accidentally leading to the stuck state.

Cheers! Rich

XOR some of Sloman's messages. ;-)

--
Politicians should only get paid if the budget is balanced, and there is
enough left over to pay them.

Aaargh!

Sorry about that...

Normally the counter jumps over the all-zeroes lockup state and runs at a length of 2^n - 1.

The error here (egg on face) was that by forcing the counter into the all-zeroes state, once every cycle, a lot (all?) of the states which would have existed on the other side of the jump are killed off.

The right way, if starting up in (or accidentally falling into) the all zeroes state is a concern, is to NOR all the Q's and feed the NOR output to the XOR, as shown.

That way, the counter runs at maximal length normally, but forces a 1 into the shift register's serial input if its outputs all go to 0, for whatever reason.

--
JF

What I have now...

Newsgroups: alt.binaries.schematics.electronic Subject: Random Bit Generator (from SED) - DevelopRandomBits.pdf Date: Fri, 22 Oct 2010 11:20:37 -0700 Message-ID: ...Jim Thompson

--
| James E.Thompson, CTO                            |    mens     |
| Analog Innovations, Inc.                         |     et      |
| Analog/Mixed-Signal ASIC's and Discrete Systems  |    manus    |
| Phoenix, Arizona  85048    Skype: Contacts Only  |             |
| Voice:(480)460-2350  Fax: Available upon request |  Brass Rat  |
| E-mail Icon at http://www.analog-innovations.com |    1962     |

               I can see November from my house :-)

So everybody is suggesting the LSFR. LSFRs are trivial; zero state problem has to be dealt with. I try doing something different just for the sake ot it.

Take two binary counters. One counts to 2^N, the other one counts to some odd number. Compute parity function of both counters. Here you go.

Take a binary adder and a register. Add some odd number at every cycle. Tale a bit somewhere from the middle of the register.

Take a binary adder and a register. Multiply by (2^N - 1), i.e. leftshift and subtract. Set the LSB to 1 to avoid all zero state.

There is approximately a zillion of ways of making quazi random (or true random) generator from whatever stuff you got in the drawers. BTW, some

25 years ago I made random generator from relays. However, that was LSFR :-)

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

I was wondering what that was trying to do. My first guess was that it was breaking out of the stuck-at state, but I didn't take the time to verify that.

I would normally avoid that wide input gate by using the system reset signal.

LFSRs with a good polynomial go through 2^N-1 states. It's normally not worth the effort to try to get that one extra possible state. If you want more states, it's much simpler to use a slightly larger polynomial. Each extra FF adds 2^N more states.

If you really want all 2^N states, I think it takes 2 clouds of gates or one cloud with an extra FF. The first cloud of gates detects a particular state and forces it into the otherwise missing state. The second cloud detects the missing state and forces it into the state it would have gone to if you hadn't done anything fancy. You can trade that second cloud of gates for a FF that remembers that the previous step was the special case.

Again, if you want more states, it's much simpler to use a bigger LFSR.

--
These are my opinions, not necessarily my employer's.  I hate spam.

One CANNOT compute (or generate from logic) a truly random number. Now, quasi-random number generators are a dime a dozen, like you imply.

Those aren't very random. He keeps saying the same stuff, over and over.

John

If you XOR enough of them, the typos add up into a random mess. :)

--
Politicians should only get paid if the budget is balanced, and there is
enough left over to pay them.

y

Even more off the wall if you throw in Mike Terrell's imagined "facts" about my life.

-- Bill Sloman, Nijmegen

Not exactly true. John Larkin does find a wide variety of different ways to get things wrong.

Today's special was his posting the URL a two-page version of Fairchild's eleven-page datasheet for the FSA3157

I certainly didn't expect that.

-- Bill Sloman, Nijmegen

Sure you can. Just make a long enough daisy chain of logic gates and compute a logic function from the input and the output of the chain. Now apply a clock to the input. As pulse propagates through the chain, the RMS jitter will add up and the output of the function will be truly random. Ring Oscillators are the other example, but they are asynchronous.

Oh, I forgot to mention the whole class of PRNGs where one counter acts as a source of the clock for the other counter. That is simple and allows generation of the variety of random looking sequencies.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

There are lots of digital chips, including some Intel processors, that have cryptographic-grade random number generators on-chip. One common technique is to use a bunch of asynchronous ring oscillators to scramble pseudo-random shift registers. Lots of references on the web.

I have a technique that uses an i/o pin as a noisy/chaotic RC ramp generator. Fun, but essentially useless.

John

Good point.

John

One of the main features of the cryptography grade RNG is the self test subsystem that continuously monitors that 1) RNG is in the good health

2) RNG had not been tampered with. If there is no such subsystem, the RNG is consumer or amateur grade, not cryptography grade.

Just to remember that a deterministic function over the random number don't add to the randomness. So the output hash should not generate more of the scrambled bits then the true entropy of the random source.

I used to measure the timing of self charge/discharge of the uncommited MCU input to set up the seed for the PRNG for the rolling code.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

I went to the web site, went to the analog switches table, found a part, clicked "datasheet." What I got was the official Fairchild 2010 data sheet, from the Fairchild web site. Well, one of the official datasheets.

I note that you got your datasheet from a non-Fairchild web site, and it's the 2003 version. So Fairchild deliberately stripped the data sheet.

Fairchild seems to have multiple 3157 datasheets on their own web site, and the links from various places to various datasheets are tangled and sometimes wrong.

Sloppy work, Bill, on their part and on yours.

And why are the chips with stunning, industry-best by 10:1 charge injections, obsolete?

They do make some nice silicon. This little critter switches like crazy:

Of course, the datasheet has no dimensions, and the package has multiple names, so one can spend a little time, as we did on Friday, trying to figure that out.

John

Post-hashing can remove any 1/0 (DC) bias and remove other autocorrelations as a physical source tends to have. Do all that a dozen times, as you can in an FPGA, and things get pretty good.

Things are more interesting if you XOR *into* a pseudo-random shift register, instead of merely with the output of one.

Similar idea, but I would keep using it. Hanging a cap on the pin helps. If the discharge time is short and is itself a function of random values, the combination of discharge time feedback, threshold uncertainty, dielectric absorption, and cap TC (use a really bad cap) add to the fun.

John

Yes, the post processing obfuscates the obvious dependencies, but it can't generate more of the entropy then the entropy of the source.

Again, you can't make more randomness by mixing random states with deterministic states. Although this procedure adds some "salt" to the common PRNG.

VLV

I wouldn't be so sure about deliberately. Never attribute to malice what can be explained by stupidity, or something close to that.

--
These are my opinions, not necessarily my employer's.  I hate spam.