8 Bit Random Numbers

On Tue, 03 Feb 2009 18:04:32 -0600, John Fields
<jfields@austininstruments.com> wrote:

On Mon, 02 Feb 2009 22:05:13 +0000, Nobody <nobody@nowhere.com> wrote:

On Mon, 02 Feb 2009 07:58:02 -0600, John Fields wrote:

Well, we could argue forever about what constitutes "[E]XOR-based", but
it's not an LFSR, and I thought it was clear that's what "nospam" was
referring to by "XOR-based PRNG".
---
He was, and you're both wrong.

What you're saying, in effect, is that if an 8 cylinder ICE fitted with
a 7 cylinder ignition system was fitted with a system winch allowed all
8 cylinders to work it would no longer be an ICE, which is total
nonsense.

No, I'm saying that if you modify an LFSR so that its input is no longer
an N-input XOR of (some of) its outputs, it's no longer an LFSR.

---
Well, I can't argue with that since it's the _feedback_ that's linear,
so I concede.
---

I don't think that anone would contest that there exist *other* circuits
which will cycle through all 256 8-bit values, or at least don't have the
lock-up state.

---
Your point being???

There are circuits which don't have the lockup state, but an LFSR isn't
one of them.

---
And yet the LFSR lives within whatever it's called if it's EXOR feedback
based...

I suggest, since the non-linear portion of the counters' sequence is so
small, that they be dubbed Mostly Linear Feedback Shift Registers;
MLFSRs.

Got a problem with that?

JF
Click to expand...
There is an extensive literature on LFSR's, dating back decades, with
lots of formal theory. There's plenty of stuff on the web.

John
 
On 04 Feb 2009 04:00:00 GMT, nospam@nospam.com wrote:

John Fields wrote:

you pompous little cocksucker.

Fuck you _and_ the horse you rode in on

If you had logic or evidence supporting your arguments, you would have posted
them.
Click to expand...
---
Since you must have read the post from which you got the excerpt, the
logic and evidence supporting my position was what you refused to
comment on, so I assume you had/have no refutation.
---

Not having either and having clearly lost the argument, you now resort
to personal attacks.
Click to expand...
---
Having both, having posted them, and then having received no refutation
from you, you're clearly posturing from an untenable position.

The personal attacks are just the icing on the cake.
---

Plonk.
Click to expand...
Coward.

JF
 
On Wed, 04 Feb 2009 08:17:13 -0800, John Larkin
<jjlarkin@highNOTlandTHIStechnologyPART.com> wrote:


There is an extensive literature on LFSR's, dating back decades, with
lots of formal theory. There's plenty of stuff on the web.
Click to expand...
---
Yup, and here's something cute from 34 years ago:

9tijo4dvaqpkb507vq63nrceaq9nl9kcc4@4ax.com

JF
 
On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?
Click to expand...
It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.

BTW, since we're talking about shift registers employing feedback (i.e.
"feedback shift registers") and mine has a linear output, I'd say that
qualifies it as a linear feedback shift register, so I rescind my
earlier concession.
Click to expand...
LFSR = (linear feedback) (shift register), not (linear) (feedback shift
register).
 
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.
Click to expand...

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
 
On Feb 4, 6:55 am, nos...@nospam.com wrote:
Bill Bowden wrote:

John Fields wrote:

Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...

Yes, I know how these people operate. They can't appreciate anything
new and unique that conflicts with existing ideas. Some won't even
take the time to look over new stuff, because they already know it
won't work. They can't see the beauty in something simple and original
that negates old ideas.

I strongly disagree. I certainly do appreciate new and unique
ideas. It's calling the new and unique idea by the exact same
name as an existing tried and true idea that I object to. Such
lack of rigor leads to things like JF writing "you are wrong"
concerning a correct statement about a PRNG that uses only XOR
feedback (AKA a LFSR) and pointing to an alleged counterexample
that uses other (nonlinear) logic elements in the feedback.

His decision to resort to personal attacks rather that arguing
his case on the merits is suggestive that he himself knows that
his "you are both wrong" was and still is incorrect.

His idea has a lot going for it (no lockup state, balanced 1s
and 0s...) and at least one disadvantage (slower than a Galois
LFSR) and is a worthy addition to any list of easy-to-impiment
PRNGs as long as it is properly classified rather than misnamed.
I certainly have not seen anyone here claim that it won't work
or refuse to look at it. I don't know where you got that.
Click to expand...
I got it from other people I know in real life. No reflection on
people here in cyberspace.

-Bill

More info on the existing "tried and true" approach:

http://www.newwaveinstruments.com/resources/articles/m_sequence_linea...
(Scroll down to "Galois Field Mathematics and M-Sequences")

http://www.edacafe.com/books/ASIC/Book/CH14/CH14.7.php
(Using a LFSR for Built-in Self-test in an ASIC)

http://www.yikes.com/~ptolemy/lfsr_web/index.htm
(LFSRs for Engineers)

http://en.wikipedia.org/wiki/Linear_feedback_shift_register
(Scroll down to "Polynomials for Maximal LFSRs")

http://www.physics.otago.ac.nz/px/research/electronics/papers/technic...
(Table of maximum-cycle LFSR taps)

http://homepage.mac.com/afj/taplist.html
(Another table of maximum-cycle LFSR taps)

http://home1.gte.net/res0658s/electronics/LFSRtaps.html
(Yet another table of LFSR taps)
Click to expand...
 
On Feb 4, 2:14 am, Nobody <nob...@nowhere.com> wrote:

For your original sequence of 3,4,5,7, use 0xB8 or 0x1D, depending upon
the shift direction. The following C code generates the same bit sequence
using both Fibonacci and Galois implementations.

Note that the two versions generate the same bit sequences, but the
sequence of 8-bit states differs.

#include <stdio.h

typedef unsigned char byte;

byte f_taps = 0x1D; /* 0001 1101 */
byte g_taps = 0xB8; /* 1011 1000 */

byte xor(byte x)
{
x = (x & 0x0F) ^ (x >> 4);
x = (x & 0x03) ^ (x >> 2);
x = (x & 0x01) ^ (x >> 1);
return x;

}

byte f(byte *x)
{
byte t = xor(*x & f_taps);
*x >>= 1;
*x |= t << 7;
return t;

}

byte g(byte *x)
{
byte t = *x & 1;
byte k = (-t) & g_taps;
*x >>= 1;
*x ^= k;
return t;

}

int main(void)
{
byte x = 1, y = 1;
int i;

for (i = 0; i < 0x100; i++) {
byte tx = f(&x);
byte ty = g(&y);
printf("%d %d\n", tx, ty);
}

return 0;

}
Click to expand...

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
 
On Feb 4, 5:03 am, John Fields <jfie...@austininstruments.com> wrote:
On Tue, 3 Feb 2009 23:18:56 -0800 (PST), Bill Bowden



wrongaddr...@att.net> wrote:
On Feb 3, 1:59 pm, John Fields <jfie...@austininstruments.com> wrote:

Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...
---

Yes, I know how these people operate. They can't appreciate anything
new and unique that conflicts with existing ideas. Some won't even
take the time to look over new stuff, because they already know it
won't work. They can't see the beauty in something simple and original
that negates old ideas.

-Bill

---
Thinking about it a little more, it occurred to me that my circuit (it's
not really mine, I came across it in the late 60's when I worked for
Racal-Milgo in Miami) is in a class of devices called "feedback shift
registers" and, since its output has as many ones as it has zeroes, it's
a linear device.

Consequently, it's truly a linear feedback shift register and the ones
with lockout states aren't. ;)

JF
Click to expand...
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
 
In article <gakko4l94j0q9titng72efp94t1veqn824@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...>
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.


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.
Click to expand...
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.
 
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.
Click to expand...
---
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.
---

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.
Click to expand...
---
If you _want_, for some reason, a lockup state to exist, then I agree
with you.

However, in those applications where the lockup state can be entered
into involuntarily, the LFSR with no lockup state is the better choice.
---

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.
Click to expand...
---
A _combination_ of linear and nonlinear feedback is used, I believe.
---

BTW, since we're talking about shift registers employing feedback (i.e.
"feedback shift registers") and mine has a linear output, I'd say that
qualifies it as a linear feedback shift register, so I rescind my
earlier concession.

LFSR = (linear feedback) (shift register), not (linear) (feedback shift
register).
Click to expand...
---
Actually, "LFSR with no lockup state" is what's commonly used.

JF
 
On Wed, 4 Feb 2009 19:59:22 -0800 (PST), Bill
Bowden <wrongaddress@att.net> wrote:

On Feb 4, 2:14 am, Nobody <nob...@nowhere.com> wrote:

For your original sequence of 3,4,5,7, use 0xB8 or 0x1D, depending upon
the shift direction. The following C code generates the same bit sequence
using both Fibonacci and Galois implementations.

Note that the two versions generate the same bit sequences, but the
sequence of 8-bit states differs.

#include <stdio.h

typedef unsigned char byte;

byte f_taps = 0x1D; /* 0001 1101 */
byte g_taps = 0xB8; /* 1011 1000 */

byte xor(byte x)
{
x = (x & 0x0F) ^ (x >> 4);
x = (x & 0x03) ^ (x >> 2);
x = (x & 0x01) ^ (x >> 1);
return x;

}

byte f(byte *x)
{
byte t = xor(*x & f_taps);
*x >>= 1;
*x |= t << 7;
return t;

}

byte g(byte *x)
{
byte t = *x & 1;
byte k = (-t) & g_taps;
*x >>= 1;
*x ^= k;
return t;

}

int main(void)
{
byte x = 1, y = 1;
int i;

for (i = 0; i < 0x100; i++) {
byte tx = f(&x);
byte ty = g(&y);
printf("%d %d\n", tx, ty);
}

return 0;

}


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
Click to expand...
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
www.daqarta.com
Scope, Spectrum, Spectrogram, Sound Level Meter
FREE Signal Generator
Science with your sound card!
 
On Thu, 5 Feb 2009 06:34:24 -0600, krw <krw@att.zzzzzzzzz> wrote:

In article <gakko4l94j0q9titng72efp94t1veqn824@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.


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.

How can you have branches?
Click to expand...

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

John
 
Bill Bowden says...

I located a program to generate 255 pseudo-random
numbers in some fixed sequence which repeats after 255
counts. 4 bits of the random register (bits 3,4,5,7)
are used as feedback to determine the next "1" or "0" to
clock into the shift register. Bits 4 and 5 are xored,
and that result is xored with bit 3. The result of that
is xored with the last bit 7 to yield a "1" or "0" to
shift into the register. This operation produces 255
non-repeating numbers in some scrambled order.

The question is, can this operation be done using fewer
bits. Is it possible to produce 255 pseudo-random
numbers from an 8 bit shift register using less than 4
bits as feedback?
Click to expand...
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.
 
In article <vc4mo411tu1i75d4vba07p3r2qjgidgg3a@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...>
On Thu, 5 Feb 2009 06:34:24 -0600, krw <krw@att.zzzzzzzzz> wrote:

In article <gakko4l94j0q9titng72efp94t1veqn824@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.


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.

How can you have branches?


Branches in the reverse direction, where two different states point to
one state in the forward direction. An OR gate can do that.
Click to expand...
Then one of the states source states can never be reached again;
bad for crypto.
 
On Thu, 5 Feb 2009 11:13:42 -0600, krw <krw@att.zzzzzzzzz> wrote:

In article <vc4mo411tu1i75d4vba07p3r2qjgidgg3a@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...
On Thu, 5 Feb 2009 06:34:24 -0600, krw <krw@att.zzzzzzzzz> wrote:

In article <gakko4l94j0q9titng72efp94t1veqn824@4ax.com>,
jjlarkin@highNOTlandTHIStechnologyPART.com says...
On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

On Wed, 04 Feb 2009 07:36:43 -0600, John Fields wrote:

The mathematical notion of linearity implies that the transformation has
a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this
matters. It may even be undesirable, as it effectively mandates a lock-up
state.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.

Why would that be undesirable?

It isn't about whether it's (un)desirable, it's whether it's an LFSR.

If you are relying upon some aspect of the (substantial) theory behind
LFSRs, then using something other than an LFSR would be undesirable.

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.


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.

How can you have branches?


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

Then one of the states source states can never be reached again;
bad for crypto.
Click to expand...
Of course. I was commenting on the appearance of the entire state
diagram.

John
 
On Wed, 04 Feb 2009 19:59:22 -0800, Bill Bowden wrote:

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?
Click to expand...
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
 
On Thu, 05 Feb 2009 11:03:52 -0600, George wrote:

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.
Click to expand...
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.
 
On 2009-02-05, John Fields <jfields@austininstruments.com> wrote:

On Thu, 05 Feb 2009 01:42:28 +0000, Nobody <nobody@nowhere.com> wrote:

OTOH, there are plenty of situations where the linearity is undesirable
(e.g. it makes an LFSR useless as a cryptographic PRNG), so non-linear
feedback is used instead.

---
A _combination_ of linear and nonlinear feedback is used, I believe.
---
Click to expand...
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.
 
On 2009-02-06, Nobody <nobody@nowhere.com> wrote:
On Thu, 05 Feb 2009 11:03:52 -0600, George wrote:

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.

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();
Click to expand...
this one?

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

it fails if x == y.
Click to expand...
works here.

// x y

// 1 1
x^=y;
// 0 1
y^=x;
// 0 1
x^=y;
// 1 1
 
Nobody wrote:

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):
Click to expand...
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: http://en.wikipedia.org/wiki/RC4
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top