8 Bit Random Numbers

If you have an n-bit register, draw 2^n circles, and number each to represent a state, "0" to "255" in the 8-bit case.

Clock the register to determine the state progressions, and draw an arrow from each state bubble to the next. If it's a maximal-length linear sequence, 255 state bubbles can be arranged in a circle, each pointing to one other, and the poor "0" state will be all by its lonesome away from the circle, off to the side, pointing to nothing (well, to itself if you want.)

Given any state, it's obvious what all the other states are, going forwards or backwards. Bad for crypto.

But add some nonlinear gates, or use a non-maximal sequence, and the bubble diagram may fragment into all sorts of loops, branches, strings feeding loops, isolated circles, much cool stuff. If it's nonlinear, more than two arrows can feed into one bubble, so there's no single way to trace the sequence backwards... it branches.

John

Thanks for the C code, but my knowledge of C is limited, and it may be a little slow to implement.

I found an assembly program for a PIC processor on the web which requires 10 lines of code, or maybe 44 clock cycles.

The idea is to shift the random register left and obtain the result in the working register (w) and then shift the register again which rolls around the carry bit to the first bit, again in (w). Then the three feedback bits are tested to determine the new input bit and the result fed to the lowest bit.

Looks pretty speedy, but I was thinking the parallel approach might reduce the 44 clocks to a lower number.

What I'm not understanding with the parallel approach is how the 8 bit result from xoring a constant 8 bits is converted to a single bit to be shifted into the register. In other words, if I xor B8 with the contents of the random register, I get some new 8 bit number. What can I do with that? How does the new 8 bit result resolve to a single bit?

Main:

RLF RANDOM,0 RLF RANDOM,0 BTFSC RANDOM,3 XORLW 1 BTFSC RANDOM,4 XORLW 1 BTFSC RANDOM,5 XORLW 1 MOVWF RANDOM GOTO Main

-Bill

I got it from other people I know in real life. No reflection on people here in cyberspace.

-Bill

I worked for Racal-Dana in Irvine California in the 80s as a associate engineer. Earlier, I worked as a technician for many years, never finished school, and learned electronics in the military schools in San Diego in 67. Never made it to Viet Nam. I got lucky and did some time in Hawaii.

-Bill

How can you have branches? This digital stuff is supposed to be deterministic. Also, if a bubble can be gotten to by two routes it's very bad for (de-)crypto. Crypto rather relies on a 1:1 mapping of plain text to cypher text. Two routes to a single node implies two plain text values encrypt into one cypher value (very bad).

Crypto relies on the path being secret, but unique.

--
Whether it\'s an LFSR or not has already been established, and since my
response was to your: "It may even be undesirable, as it effectively
mandates a lock-up state.", it _is_ about desirability.

The parallel approach is what I was trying to explain (perhaps not well enough) at the end of my post of 1-28-09. You need to think of the whole operation as a set of completely independent parallel shift registers. The number of shift registers is the number of bits in a register (byte, word, or dword). The number of bits in a single shift register is the number of memory locations you dedicate to this.

Keeping that in mind, the overall operation uses the same logic as a simple single-register LFSR, but it's much easier. The Nth memory location is now the Nth bit, so you XOR memory locations directly. There are no rotate or shift instructions... instead, you manipulate the index into the memory array. The new 8-bit result (assuming you use byte-sized memory) is 8 independent single-bit LFSR outputs at once.

Note that the LFSRs never actually do any "shifting"... only your memory pointer changes so that you regard different locations as different LFSR bits after each crank of the machine.

The memory pointer math requires careful thought to optimize for speed. A circular buffer topology is essentially what you want here, but the problem is that LFSRs are typically *not* powers of 2 (at least, the efficient single-XOR types). That makes it hard to wrap the pointer around at the ends... you can't use a simple mask on the pointer as you can with power-of-2, you need specific test-and-branch comparisons.

A way around this is to use a larger power-of-2 mask, and adjust your thinking so that the memory locations representing the LFSR are a subset that "walks" around the larger memory array. This will take a fair amount of pencil-and-paper chicken tracks to work out, but the code will be faster.

Best regards,

Bob Masta DAQARTA v4.51 Data AcQuisition And Real-Time Analysis

Scope, Spectrum, Spectrogram, Sound Level Meter FREE Signal Generator Science with your sound card!

Branches in the reverse direction, where two different states point to one state in the forward direction. An OR gate can do that.

John

Others have answered your question, but I just wanted to comment that if you look at the entire 8-bit value, the sequence of values produced isn't really random or even pseudo-random. If the most recent value happened to have the high bit cleared, then the next value will be exactly double the previous value, or double that value, plus one, and that's not very random. And if the high bit was set, then in a way the new value is still double the previous value if you ignore the high bit. Bascially, the new value is just the old value shifted one bit to the left.

And since the sequence is non-repeating, it's impossible to get the same value twice, or more times, in a row, which would certainly happen from time to time if the bytes were randomly selected.

But if you look at just the individual "new" bit produced on each interation, the sequence of those bits may indeed appear to be quite random.

So if randomness (rather than just non-repeating) is important to whatever you're doing, one solution might be to run a much larger shift register - 30 bits or more - and do

8 iterations to produce the next "random" byte for your use. All 8 bits will have been replaced by new ones with no obvious relationship to each other or to what was there before.

Of course the 30-bit register is still deterministic, but the non-repeating sequence is still quite lengthy: 2^30 - 1. You would have to shift four bytes instead of one, and do that and the XORs eight times instead of one, but, you know, processors are pretty fast now.

Then one of the states source states can never be reached again; bad for crypto.

lock-up

Of course. I was commenting on the appearance of the entire state diagram.

John

It doesn't. That's why the parallel version is preferred for use on a microprocessor, as XOR-ing two words together for a one-word result is faster than XOR-ing the bits of a word together for a one-bit result.

Any serial (Fibonacci) implementation has an equivalent parallel (Galois) implementation which produces the same sequence of bits, but not the same sequence of 8-bit states. The tap sequence used for one is a mirror image of the tap sequence for the other.

In the serial version, the state is shifted one place, with the incoming bit calculated as an XOR of the tap bits.

In the parallel version, the state is shifted one place, with the incoming bit zero; if the outgoing bit is set, the state is then XOR-ed with the tap word.

In the C version, the xor() function XORs the bits of an 8-bit word together to produce a 1-bit result. This is required by the serial version, f(), but not the parallel version, g(). As xor() uses 3 shifts, 3 ANDs, and 3 XORs, eliminating it provides a significant saving; moreso for larger states (you need N steps for a (2^N)-bit state).

Hmm; actually, it's probably more clear to write g() as:

byte g(byte *x) { byte t = *x & 1; // t = LSB of state (outgoing bit) *x >>= 1; // shift state right one bit, incoming bit is zero if (t) // if outgoing bit is set ... *x ^= g_taps; // ... XOR state with tap word return t; // return outgoing bit }

Which version is preferred depends largely upon whether you want to use a branch (new version) or a negate and an AND (old version).

In either case, an assembler version would typically test the carry flag after the shift, rather than testing the LSB before the shift (C itself doesn't provide a mechanism to set/test flags).

Roughly (ARM assembler):

MOV r0,#1 ; start in state 1 .loop MOVS r0,r0,LSR #1 ; shift right one place, 0->in, out->Carry EORCS r0,r0,#&B8 ; XOR with tap word (B8h) if carry set ; carry contains next output bit ; use it here B loop ; next iteration

If you want highly-random bytes, and can spare 258 bytes of RAM, I would echo nospam's suggestion to use RC4 (aka ArcFour, as RC4 is a trademark):

byte x, y byte a[256] ; a[] is a permuation, i.e. each of the values 0-255 ; occurrs exactly once.

proc next_byte() byte t

x = x + 1 y = y + a[x] swap(a[x], a[y]) t = a[x] + a[y] return a[t] end

A word of caution: do not use the XOR trick for the swap(); it fails if x == y.

certainly for DES (and by implication 3DES) that is the case.

RSA is AIUI linear (being based on multiplications)

I've not looked closely at any of the other encryprion schemes.

this one?

x^=y; y^=x; x^=y;

works here.

// x y // 1 1 x^=y; // 0 1 y^=x; // 0 1 x^=y; // 1 1

A description of ARCFOUR (Alleged RC4), written by Neil Bawd in 1997 and updated in 2000:

In 1987 Ron Rivest developed the RC4 cipher-system for RSA Data Security, Inc. It used a well-guarded proprietary trade secret. The system was popular and is used in several hundred commercial cryptography products, including Lotus Notes, Apple Computer's AOCE, and Oracle Secure SQL. It is part of the Cellular Digital Packet Data Specification, and is used by Internet Explorer, Netscape, and Adobe Acrobat.

Seven years later, source code alleged to be equivalent to RC4 was published anonymously on the Cypherpunks mailing list. Users with legal copies of RC4 confirmed compatibility.

The code is extremely simple and can be written by most programmers from the description.

We have an array of 256 bytes, all different.

Every time the array is used it changes - by swapping two bytes.

The swaps are controlled by counters i and j, each initially 0.

To get a new i, add 1.

To get a new j, add the array byte at the new i.

Exchange the array bytes at i and j.

The code is the array byte at the sum of the array bytes at i and j.

This is XORed with a byte of the plaintext to encrypt, or the ciphertext to decrypt.

The array is initialized by first setting it to 0 through 255.

Then step through it using i and j, getting the new j by adding to it the array byte at i and a key byte, and swapping the array bytes at i and j. Finally, i and j are set to 0.

All additions are modulo 256.

The cipher key to be used when initializing can be up to 256 bytes, i.e., 2048 bits. It works best when it's shorter so the randomizing done at initialization can thoroughly shuffle the array. At most 64 bytes are recommended for the key.

The name "RC4" is trademarked by RSA Data Security, Inc. So anyone who writes his own code has to call it something else. In 1997 I called it ARCIPHER. ARCFOUR has been since widely accepted as the name of the alleged RC4.

It is popular because it is small, fast, and believed to be secure.

It's a rare example of Cheap, Fast, and Good.

Also see:

Yes, that clears things up a bit, but the incoming bit occasionally needs to be set, otherwise it's always going to be the same.

With PIC assembly, looks like only 3 lines are needed. But the sequence length is 2^n-2 for some reason. It loops around every 254 counts. Not sure what's missing.

The first line (RLF) shifts the register left one place with the incomming bit "0" if the carry flag is clear, or "1" if the flag is set.

The second line tests the carry bit and jumps over the XOR if the bit is clear "0".

The 3rd line does the XOR and leaves the result in the random register. The working register (w) contains the constant word B8, so a couple extra lines are needed to load the B8 into w. But that's only done once.

Starting at hex 01, the sequence goes.... 01,02,04,08,10,20,40,80, B8,C9,2B,57,AE,E4,71,E3,7E,FD,42, etc.

Loop:

RLF RANDOM,f ; Shift Left BTFSC STATUS,0 ; Test carry flag XORWF RANDOM,f ; XOR w and random GOTO Loop

-Bill

It doesn't matter. With the parallel version, all of the tap bits get flipped whenever the outgoing bit is set, equivalent to having XOR gates between some of the stages.

It isn't like the serial version, where the tap bits determine the initial value, and the bit then travels through the shift register unchanged.

The value of B8 assumes a right shift; it should be 1D (the mirror image) for a left shift.

The incoming bit should always be zero; i.e. use a (logical) shift rather than a rotate. If there isn't a distinct shift operation, clear the carry first.

[snip]

But we're not swapping x and y, we're swapping a[x] and a[y], i.e.:

a[x]^=a[y]; a[y]^=a[x]; a[x]^=a[y];

This fails if x == y, i.e. if a[x] and a[y] are the same array element; the new value will always be zero.

The above code might make it obvious, but consider:

#define SWAP(x,y) do { x^=y; y^=x; x^=y; } while (0) ... SWAP(a[x], a[y]);

This particular flaw was a runner-up in the 2007 Underhanded C Contest: