Galois LFSRs in PIC18 ASM.

[()blivion]

(-_-) ummm. . .

So, trying to make a building block for a PRNG in PICASM for PIC18 instruction set, and I'm having the worst time making it work. If you don't already know, more information on exactly what I'm doing can be found *HERE*. The second or third code box has what I'm doing, only in C. My PIC18ASM source that has worked the best so far is below. I get sequence repetition after only 21081 iterations though, which isn't right.

PRNG             RRCF	LFSR_B_H, F		;  Shift the 16+1 bit register
                 RRCF	LFSR_B_L, F		; (Shifts through the CARRY bit)

                 BTFSS	STATUS, 0		; Test the output bit.
	   RETURN

                 MOVLW	b'10010000'		; XOR bits 17 and 14 if bit 0 is set 
                 XORWF	LFSR_B_H, F		; store in LFSR high byte.
	   RETURN

I'm not getting maximum sequence length out of the register no matter what bit mask I use for the polynomial/taps. I have tried all sorts of different combinations I could think of with all different lengths for the shift register. Maybe I'm not following the algo correctly? The bit mask above is for a 17 bit Galois LFSR as laid out on the wiki article. I use two RRCFs to pass bits through CARRY, which should make it effectively a 17 bit LFSR. I'm doing nByte + 1bit LFSRs because (in theory) it conveniently allows one to do most things with byte oriented instructions while almost entirely avoiding single bit manipulations. Which is the point of implementing a Galois LFSR.

I know the fix is going to be something really stupid too, I just think I've been looking at it to long or something. If I can get it to work with about the same number of instructions as above it will be a really good building block for PIC PRNGs.

Thanks for any assistance.
-()b

 

[Mr RB]

First, i would use the Fibonnaci example not the Galois one, same maximal iterations but more logical to implement even though it is a bit longer in code.

There's a couple of things wrong with your code!
1. your RRF leaves an unknown bit in bit15, it would be better to be zero at that point. You could CLRC before the 2 RRCFs.
2. if the output bit is 1 you need to XOR bits 10, 12, 13 and then insert (not xor) the output bit into 15.

 

[()blivion]

Hello again Mr RB.

First, i would use the Fibonnaci example not the Galois one, same maximal iterations but more logical to implement even though it is a bit longer in code.

Thought about it, and working example code exists for the Fibonnaci version. I chose the Galois version because it is (supposed to be) significantly more efficient to implement in software. The Fibonnaci version takes, at a minimum, one instruction for each byte shifted, then takes one extra instruction for each and every XORed bit. (Edit: Which, admittedly, is only ever going to be 2 or 4) The Galois version takes one instruction per shift, then just one single instruction does ALL the rest... In theory.

Otherwise, yeah, there is no point in using anything other than the Fibonnaci version. And having beat my head against the problem for a while now, it is starting to look like I will have to use more instructions to make it work compared with what I already have. Which is going to be a shame. Removing even a single instruction in tight loops like these gives great speed gains.

1. your RRF leaves an unknown bit in bit15, it would be better to be zero at that point. You could CLRC before the 2 RRCFs.

Sorry for the vagueness, I do actually have the unknown bit cleared before jumping into the LFSR part. I don't know the full extent of how exactly I'm going to use the LFSR part yet. But I probably will move the BCF STATUS, 0 down to the PRNG label so that it can't be shifted without the unknown bit. I just hadn't done it yet. Here is the rest of the routine...

PRNG_int		movlw	0xAB			; Load arbitrary numbers to LFSR
                        movwf	LFSR_B_H		; 
                        movlw	0xCD			; 
                        movwf	LFSR_B_L		; 

                        CLRF	WREG			; Clear relevant registers
                        BCF     STATUS, 0		;
PRNG
SHIFT_H			RRCF	LFSR_B_H, F		;  Shift the 16+1 bit register
SHIFT_L			RRCF	LFSR_B_L, F		; (Shifts through the CARRY bit)

                        BTFSS	STATUS, 0		; Test the output bit (bit 0).
	RETURN

                        MOVLW	b'10010000'		; XOR bits 17 and 14 if bit 0 is set 
                        XORWF	LFSR_B_H, F		; store in LFSR high byte.
	RETURN

[SUB]Note: The labels "SHIFT_H" and "SHIFT_L" are just there so I can easily find and collect the register values in the trace with a batch file.[/SUB]

2. if the output bit is 1 you need to XOR bits 10, 12, 13 and then insert (not xor) the output bit into 15.

This may actually be the problem, then again, it may not.

You are 100% correct that one XORs the "taps" into just the input bit... with the Fibonnaci version. I don't think that is the case for the Galois version though. It looks like each tap bit is independently inverted (XOR) if and only if the output bit was set. It can be best understood by examining the image in for the 16-bit Galois LFSR. Or alternately, you could read it as is worded in the article...

1: Bits that are not taps are shifted one position to the right, unchanged.
2: The taps, are XOR'd with the output bit before they are stored in the next position.


Edit: Thanks for the reply.

 

[()blivion]

Here is a quick thought, could you (or anyone) maybe possibly compile the two/three code boxes in the article and post the disassembly listing? That would probably give me a clue as to what needs to be done. I don't have a PIC18 compiler, so I can't do it myself.

 

[Mr RB]

Why are you only XORing two bits when the diagram shows 3 bits are XORed and one bit is stored?

And you are still not storing the new bit into bit15, you are just doing XORs?

I just typed in what I believ is the the correct code based on the wiki diagram;
**broken link removed**

PRNG
	BCF     STATUS, 0;    clear carry before shifting (will make a 0 in bit15)
	RRCF  	LFSR_B_H, F;  Shift the 16+1 bit register
	RRCF	LFSR_B_L, F; (Shifts through the CARRY bit)
        BTFSS   STATUS, 0; Test the output bit (bit 0, is now in carry).
RETURN
 
	MOVLW	b'00110100'; mask to XOR bits 13, 12 and 10 (re Wiki diagram) if bit 0 is set 
	XORWF	LFSR_B_H, F; complete the XOR operation on the LFSR high byte.
	BSF     LFSR_B_H, 7; insert a 1 into bit15 of the LFSR
RETURN

 

[()blivion]

Why are you only XORing two bits when the diagram shows 3 bits are XORed and one bit is stored?

The diagram in question is for a 16 bit Galois LFSR, But I was attempting to use the carry bit as the 17th bit (0 bit actually). I plan on implementing an LFSR for every number of bits from 0 up to some arbitrary number. Then use an extra byte to store all the odd bits for any LFSR that is not an even number of bytes, but that is for a later stage after I get the LFSR process in ASM down pat. Anyway, to implement a 17 bit LFSR it would have to have different tap points in accordance with the polly table. Which should be bit 17 and bit 14, so that's what I was trying for. Hope this clears that up

You are still not storing the new bit into bit15, you are just doing XORs?

The new bit comes out of the carry, the looping point is at PRNG not PRNG_int. (I fully realize the negative implications of this and will explain.)

"PRNG_int" is the first part and is only called once during boot to load the starting values. Every call to this routine thereafter would be to the lower part only, just to service the LFSR's. Really it is a bit sloppy and incorrect since leaving the routine and coming back will mess with the carry bit and inject unknown data into the LFSR. Bad bad juju of course. My excuse is I have been doing so much code shuffling in that area trying to get *something* to work that it has gotten conceptually a little untidy. I fully intend to do it the right way after I get accurate LFSR emulation in ASM figured out.

But keeping in mind that this is slapped together for now, you would note that the beginning of the smaller loop should actually be getting get the bit it needs mathematically. It comes out of the carry at the start of each loop, which as I said above would be the 17th/0 bit. The RETURN instructions really should be unconditional branches back to PRNG during testing, and the routine should only be run independently for now. Just to reiterate, I planed to use a dedicated register as the other bits instead of the carry, and will move clearing the carry down into that loop when the whole routine has some more meat.

I actually did have a dedicated register for the extra bits at first. It just wasn't working at all, so I was grasping at straws to try and understand what was wrong. I really suspected the carry bit was to blame, so I wanted to make sure it was a useful part of the LFSR and not at all hurtful. And that is what lead to what had thus far been the best working code I could come up with, the code I posted above. I also tried to cut carry entirely out by using the rotate without carry instructions, but that created other problems.

Many apologies for my sloppiness on this one.

:code box:

Thanks for your help Mr Rb, your code does in fact quite perfectly implement a 16 bit LFSR. Which is great (^.^). I would happily attach the output for you to confirm, but it is over ETO's upload size limit. Maybe I will put it in paste bin or email it to you or something. In any case, the sequence repeats exactly at line 131072 (2^16 x 2) which is, of course, maximal permutations for a 16 bit number, accounting for every two lines/bytes of output being one complete loop.

Now if I could just figure out how to do what you did, just with an arbitrary nBit shift register, then I think I would be all set.

Thanks again. -()b

 

[Mr RB]

Thank you for explaining in detail what you are doing. I'm sure you can understand my confusion when you talked about a specific Wiki diagram but I saw your code was failing to match that diagram.

OK, I have done LFSRs in the past with any arbitrary number of bits, it is not hard at all and all you need is enough bytes to store all the required bits.

I really dislike your idea of keeping vital data in the carry bit, it's only an extra instruction or two to have the data always safe in the main buffer.

For your proposed new LFSR using bit 17 and bit 14, it would be done just the same, like this;

PRNG
BCF     STATUS, 0;    clear carry before shifting, will make a 0 in top bit(s)
RRCF  LFSR_B_U, F;  Shift the 17 bit register (requires 3 bytes; U,H,L)
RRCF  LFSR_B_H, F; 
RRCF   LFSR_B_L, F; 
        BTFSS   STATUS, 0; Test the output bit (bit 0, is now in carry).
RETURN
 
MOVLW  b'00100000'; mask to XOR bit 13 if bit 0 is set 
XORWF  LFSR_B_H, F; complete the XOR operation on the correct byte.
BSF    LFSR_B_U, 0; insert a 1 into bit16 of the LFSR
RETURN

Also you probably saw I prefer to use the correct software bit names 0-16 for a 17 bit shift register. For some reason Wiki use the numbers 1-17 probably because they are more focused on a math polynomial discussion rather than a software implementation.

For large shift registers you can use better register byte names like;
LFSR_00
LFSR_01
etc, and doing that a while back I did a 60 or 80 fibonacci style LFSR (can't remember the exact size) as an output scrambler for another RNG process.

I'm curious to learn more about why you want to do LFSRs with lots of different sizes, is this just a thought experiment or for some actual real world use?

 

[()blivion]

Got around to uploading the first LFSR output file. **broken link removed** is a link to the download. Unfortunately the download page is plastered with annoying ads. The actual button is the medium sized gray button on the lower mid section of the page. And you have to pass a minor captcha.

Edit: The time on the file has expired.

I really dislike your idea of keeping vital data in the carry bit, it's only an extra instruction or two to have the data always safe in the main buffer.

I didn't like it either. I was just grasping at straws at the time. For sure, I won't be doing it that way anymore.

Code:

Thanks again, I will probably be testing that today. One question, at a glance it looks like I may have to use one extra byte per LFSR? Is there no relatively simple way to use one byte to store the bits for multiple LFSRs? That would certainly save some memory if I make many LFSRs.

Also you probably saw I prefer to use the correct software bit names 0-16 for a 17 bit shift register. For some reason Wiki use the numbers 1-17 probably because they are more focused on a math polynomial discussion rather than a software implementation.

Yes, I saw and was thinking about that. I don't agree with the wiki's way of doing it either. I was only using that designation as it is exactly what the Wiki was saying and I wasn't sure I should deviate from that. It would be nice to set a better common ground though. So from now on (if the thread goes on much longer) we can just use the microchip designations. It makes more sense to me anyway.

For large shift registers you can use better register byte names like;
LFSR_00
LFSR_01

Yeah, I'm on top of that. The naming scheme I was planning on using for some of my larger LFSRs goes something like. "LFSR_<letter>_<number>". The letter tells you which LSFR it actually is, and the number indicates what byte in that particular LFSR. I figure with this scheme it would be OK to do say "LFSR_A_03" and at the same time "LFSR_B_03", and there won't be any confusion as to what each label was referring to. It could just as easily be "LFSR_<number>_<number> though I suppose.

I'm curious to learn more about why you want to do LFSRs with lots of different sizes, is this just a thought experiment or for some actual real world use?

I'm happy to share

So far this is mostly thought experiment really. Such things could lead to real world use, but it isn't really "needed" for anything right now. I have some ideas I want to play with and see where it goes. Otherwise it is just for "edutainment". As you know, more bits means longer periods, however single LFSRs have predictable patterns, and are thus not really random. The same number of bits, as smaller LFSRs has potential for more complex patterns with the same amount of memory. As for why LFSRs. I believe it was you that said "I think every one should build their own [pseudo] random number generator". It seemed like good advice. And LFSRs seem like good starts. LFSRs make good building blocks for quite a few things actually.


Ideas
First I'll tell you, I came up with something interesting while doing this project. I was thinking about how to save more memory, And I started to wonder if we couldn't simply overlap all the registers with each other? That is, an nBit LFSR can be broken down into smaller LFSRs, then operations are done on each, leaving the data there and allowing it to bleed over into and alter the other "virtual LFSRs". This should save memory while creating even more chaos in that memory. Even if the operations on one virtual LFSR accidentally create all 0/1 for any other virtual LFSR, there should be no problems with lock up because future operations will shift in an opposing bit, allowing that virtual LFSR to function again. I think the chaos should be really high with this configuration.

Another idea I wanted to play with was an encryption algo that uses the key to not only load the starting LFSR values, but to also decide how they are all shuffled and combined. Basically, a cipher that preforms a varying transformation on the plain text, based on the key you use. In theory it strengthens the encryption by adding another layer of uncertainty. And I was going to realize this with different sized LFSRs that can be chosen from and combined in different ways, based on the key. But I have no idea how usable this actually is, I think it may already be being done. That's how most things seem to go in this study.

Yet another thing I want to do is play with DSSS/FHSS + encryption someday. But that is going to require a whole lot more radio R&D on my part, radio is one of my weak points. I really like that such technology lowers interference, and is hard to jam, AND is hard to spy in on. I was thinking of taking it farther and making some kind of "stealth radio". I.E. some devices that can talk to each other, maybe even long distanced, but otherwise are not reasonably detectable.

Just fun thought that will, in all reality, probably never get off the ground.

 

[Mr RB]

... One question, at a glance it looks like I may have to use one extra byte per LFSR? Is there no relatively simple way to use one byte to store the bits for multiple LFSRs? That would certainly save some memory if I make many LFSRs.

I believe every LFSR must have its own separate buffer, and the buffer size must have enough bytes to hold all the bits. The number of bits wasted is from 0-7 on every LFSR. I don't think you would save much RAM trying to manually handle all the top bits and at first glance it looks like a coding nightmare.

...
Yes, I saw and was thinking about that. I don't agree with the wiki's way of doing it either. I was only using that designation as it is exactly what the Wiki was saying and I wasn't sure I should deviate from that. It would be nice to set a better common ground though. So from now on (if the thread goes on much longer) we can just use the microchip designations. It makes more sense to me anyway.

I used to have a PDF white paper on these type of RNGs and they used numbers starting at 1 also, but again the focus was on the polynomial math. Once the initial math is done (and you know the bits to XOR) doing the software implementation it comes back to standard bits and bytes numbering, at least in my code.

...
... As you know, more bits means longer periods, however single LFSRs have predictable patterns, and are thus not really random. The same number of bits, as smaller LFSRs has potential for more complex patterns with the same amount of memory. As for why LFSRs. I believe it was you that said "I think every one should build their own [pseudo] random number generator". It seemed like good advice. And LFSRs seem like good starts. LFSRs make good building blocks for quite a few things actually.

Yeah, agreed, they can be handy and thanks for the quote! What I meant with "build their own RNG" was really to build YOUR own one, and test the output and see what is needed to get it to that point where it becomes "good enough". LFSR is a good building block as part of a process, like using the LFSR bit to XOR the output bit of your own process, especially if your process has good entropy but has issues with bias or frequency.

...
Ideas
First I'll tell you, I came up with something interesting while doing this project. I was thinking about how to save more memory, And I started to wonder if we couldn't simply overlap all the registers with each other? That is, an nBit LFSR can be broken down into smaller LFSRs, then operations are done on each, leaving the data there and allowing it to bleed over into and alter the other "virtual LFSRs". This should save memory while creating even more chaos in that memory. Even if the operations on one virtual LFSR accidentally create all 0/1 for any other virtual LFSR, there should be no problems with lock up because future operations will shift in an opposing bit, allowing that virtual LFSR to function again. I think the chaos should be really high with this configuration.

That's interesting and would be a cool experiment. Generally modifying the data within a LFSR is considered bad form as the LFSR is a single maximal length repeating pattern, so to change any bit when it is working just skips it to a different part of the pattern, which in most cases gives a shortened repeat.

If you want to try that I would suggest XORing a bit from LFSR A with LFSR B, that gives better entropy than just eliminating and replacing a bit. Also it might be good to only do that process infrequently, not do it every bit. That gives time to build more entropy in the individual LFSRs before they "mash" a bit and affect each other, giving longer and more complex patterns in their interaction and disallowing short pattern locks. Building on that, if you can "randomly" select a time to mash the bits that is generally better than doing it at a fixed time, provided there is little predictability to when you randomly do the event.

And obviously, the old technique of generating the output bit by XORing a number of non-polynomial bits from different LFSRs will give a much better output than just outputting the last bit from the last LFSR in the line.

It's fun seeing someone making RNGs in software and hopefully someone else might speak up who has experience. My understanding is pretty rudimentary and I'm mainly a brute force kind of guy, ie big buffers and lots of data mashing based on unrelated things. LFSRs are more mathematical in nature and (to me) are best used as a single part of a RNG process, not form the entire process.

 

[()blivion]

Sorry I didn't respond to you right away RB. Been busy-ish, and this thread is a bit technical to just pop in and drop a few lines. I wrote quite a lot here for you, but feel free to skip all you want. No obligation to read any of it.

I don't think you would save much RAM trying to manually handle all the top bits and at first glance it looks like a coding nightmare.

That's pretty much exactly what I figured. I just wanted to point out the possibility. But yeah, not worth it really.

[Your idea is] interesting and would be a cool experiment.

Sure. Though we may need to choose a different platform if we want to really test this. It's hard to get data out of the sim, at least it is for me. I have to put markers in my source, output the trace to a text file, then process that file with a batch script to extract useful data. It's fairly tedious.

Really we're entering the realm of statistics anyway, not PIC programming. The firmware realization should probably come after the math is down pat. But such things would be out of my sphere of knowledge. This probably needs the attention of some real "mathmagicians".

Generally modifying the data within a LFSR is considered bad form as the LFSR is a single maximal length repeating pattern, so to change any bit when it is working just skips it to a different part of the pattern, which in most cases gives a shortened repeat.

Hummm... I don't really know myself, but the way I figure it is as follows...

In all their pattern complexity and glory, LFSRs are really just an odd form of binary counter[SUP][1][/SUP]. So, we should be able to statistically simplify them to a basic nBit counter, as they both cover the same space in the same number of iterations. LFSRs just use a different pattern to get to the same destination. We will conveniently overlook the all zero state, which should only have a very small bias on the statistics of all this (I hope).

Now, analyzing a standard counter we find that clearing any one bit that was previously set will always jump back in the sequence, and setting any bit that was previously clear jumps forward. It follows from this that if we toggle any randomly chosen bit, at any random time, we would have a 50/50 chance of going back or forward, since such random choice should have a 50/50 chance of hitting a 1 or 0, in accordance with the expected value theory[SUP][2][/SUP].

Truthfully, an LFSR isn't exactly the same as a simple counter in the above regard. For example you could see an instance where clearing a bit would actually go forward, or setting one ends up sending you back, the opposite behavior of a typical counter. But in reality this doesn't actually matter, because the distribution of these "opposite behaving instances" should also be 50/50, canceling any bias out.

So because the expected value for a single binary bit in an LFSR is 0.5=1/2=50/50, and an LFSR should more or less behave just like an ordinary counter when any randomly chosen bit is flipped. It follows that any random LFSR bit being toggled really should also statistically have 50/50 chances of either skipping ahead, *OR* skipping back, just like a counter does.

Q: OK, assuming you are correct, what does this really mean?

A: The biggest advantages of LFSRs is that they are reasonably fast, and they cover maximum space for a given amount of memory. The biggest problem of LFSRs, as with any maximal length counters with simple feedback system, is that they are 100% deterministic. For example, the Berlekamp–Massey algorithm can "crack" any single LFSR working with just it's output stream[SUP][3][/SUP]. LFSRs however have the distinct advantage over standard counters of being quite statistically random, and that is just the ticket out of their easy to define deterministic nature. Using one LFSR to change another, whether directly or just affecting it's output stream, breaks up patterns. So, the above theory may or may not short change the space that a given LFSR would have covered if left alone, like you are more or less suggesting. But even so it still doesn't do it in a deterministic way. It may short change it a whole lot for one or two iterations, then another modification does something else altogether, "un-short changing it's self" so to speak.



Another way to examine the problem, one that is significantly easier to explain, is to point out that the transition from all 1s to the next state is in fact a perfectly valid and acceptable number that one may find in a truly random sequence. It has the same exact weight as any other LFSR transition you could come across in a truly random sequence in fact. And even before you see it like this, you may realize that an LFSR is a loop with no real beginning or end. Thus there is really nothing to get short changed as debated. Yes, if you alter bits in an LFSR outside of it's feedback function, you will be making big leaps from one point in the circle to another that wouldn't have happened otherwise. But there is absolutely no way for an attacker to know, when you are doing this, where you started, where you will end up, how big the jump was, or how big it will be. This remains true even if the jump brings you really close to or over the all 1s boundary. Mashing bits of multiple LFSRs with each other before using them intrinsically obscures any particular transitions that would scream LFSR sequence. Which is generally how you are going to use LFSRs anyway.

So, bad form or not, I still want to believe that using any well designed "exo-LFSR feedback function" to change an LFSRs current state can generate good entropy. And I feel another LFSR is a decent way to do this. But feel perfectly comfortable to object with a better explanation of your own point of view, because I may be totally wrong. It wouldn't be the first time the other shoe has dropped on one of my crazy ideas.

If you want to try that I would suggest XORing a bit from LFSR A with LFSR B, that gives better entropy than just eliminating and replacing a bit. Also it might be good to only do that process infrequently, not do it every bit. That gives time to build more entropy in the individual LFSRs before they "mash" a bit and affect each other, giving longer and more complex patterns in their interaction and disallowing short pattern locks. Building on that, if you can "randomly" select a time to mash the bits that is generally better than doing it at a fixed time, provided there is little predictability to when you randomly do the event.

You are pretty much describing the shrinking generator. It's a little different because one ANDs the output of LFSR A with the output of LFSR B, rather than XOR. But the exact logic function doesn't really matter I don't think, two LFSRs properly interacting generate entropy. The second part of what your saying is describing the alternating step generator, which is the other major LFSR based PRNG.

There is nothing really wrong with either of these implementations. The only thing is they are well known and relatively inflexible. Also note that if implemented wrong they both will fail miserably, but the same is true for just about anything. That being said, the other side of the coin is that "custom" and "secret" PRNG algos tend to have more flaws than what has been well established. That's why the general conciseness is keep such things open. Then again, if you know what you're doing, and you thoroughly check your work, you could have your cake and eat it too. So the reward o'ta be there.

And obviously, the old technique of generating the output bit by XORing a number of non-polynomial bits from different LFSRs will give a much better output than just outputting the last bit from the last LFSR in the line.

This is another technique mentioned in the Wiki article for solving the deterministic problem of LFSRs. It doesn't go into detail though and there are no references to go by. But it seems pretty strait forward. So, not much to say about this really.

It's fun seeing someone making RNGs in software and hopefully someone else might speak up who has experience. My understanding is pretty rudimentary and I'm mainly a brute force kind of guy, ie big buffers and lots of data mashing based on unrelated things. LFSRs are more mathematical in nature and (to me) are best used as a single part of a RNG process, not form the entire process.

It's fun making them... when I can get the code to behave properly.

It should be obvious that my understanding is also fairly rudimentary. Though I like to use the less harsh word "intuitive". This highlights the contrast to some kind of hard science and mathematics without implying one has absolutely no idea of what they are doing. And although LFSRs are quite mathematical, I do think they can be used with a intuitive mindset well enough to be the core of a good PRNG, though I can't exactly prove this. And of course, even if LFSRs are not 100% usable this way by themselves, there will always remain the opportunity to add other methods to supplement their weaknesses. Your brute force methods wouldn't be bad for this.

Anyway, that's all I got right now. Thanks for your help RB, I couldn't have done it with you. Honestly, you solved my original reason for creating this thread, so the case is pretty much closed as far as I am concerned. I'll still probably get back on this sooner or later, just maybe not in this thread. Now that I have Galois LFSRs, I need to play with them and see what I can come up with.

 

[Mr RB]

Hi Oblivion, and of course I read your entire post as it would be bad manners not to read a post where someone took the effort replying to me.

Re the point about it being "bad form" (my words) to modify data in a running LFSR, I agree with the bulk of what you have said. The main reason for it being "bad" is that the LFSR makes a maximal length string. So if one LFSR is used to generate a random number string, it can be relied upon to NOT repeat itself until X bits are generated.

Now if that was being used to randimise a process, or encrypt data, the process or encryption could be relied on to have no repeat (assuming it was not run to exceeed maximal length). If any bit in the LFSR was modified when running, there is a possibility of a previous state being revisited and then an exact copy of the sequence continued from that point onward, which makes an exact repeat of the "random" data, being very bad for both "random" requirement and catastrophic for encryption.

In your case the situation is a bit different as you are discussing using multiple LFSRs in a larger more complex process, so if one LFSR repeats a sequence of data the result is much easier tolerated and may not compromise the whole process. If all LFSRs were modified, I worry that it would settle into a single repeating pattern, which could even be worse problem than one LFSR that might just repeat some data occasionally. But if you keep one or more LFSRs free running and XOR into the LFSRs that are modified, it reduces the problem as the modified LFSRs cannot settle into a single short term pattern.

As a good "intuitive" approach I would have one RNG that is quite erratic but may have short term patterns, and XOR it's output with the output from a very long free running LFSR, which has very stable good entropy that can be relied on not to repeat. (Something like a 80bit LFSR running at microcontroller speed has a repeat period "longer than the end of the universe" according to one research paper I read.)

So that looks like this;
1. one or more free running LFSRs are used to insert/XOR bits into a number of other LFSRs. This is the "erratic" RNG that can have circular data paths. It will generate some short term repeat patters at times but the overall operation is extremely erratic or chaotic.
2. a reliable long term free-running LFSR making a good datastream that will not repeat for the life of the device.
3. XOR the outputs of process 1 and 2 together, this is the final output.

 

[()blivion]

Hummm... yeah... you pretty much convinced me it might be a big mistake after all, your argument is solid. I hadn't recognized that after multiple jumps we might end up back to a spot on the circle that we already used. Even a small repeat of a large LFSR would probably degrade the encryption a significant amount.

My thinking was that there is a whole lot of space in a large LFSR that is not being used, and the conventional method has an obvious liner sequence. So if one could use "random" parts of that space, rather than pick a starting point and go, the key/starting data would be harder to figure out. In the former way, if an attacker does somehow figure out where you are at in the LFSRs sequence, they have entirely cracked a large LFSR and reduced the complexity by several orders of magnitude. If the latter were done instead, and parts of the LFSR sequence were "picked randomly", then it would (in theory) be much more difficult to get the state of that one large register, even if the attacker had a way of getting through some layers of LFSR obfuscation.

It's that "picked randomly" part that appears to be the real problem. If it is truly random, then it can't be made to not use places already used. Otherwise, it's not random, it's deterministic, which kinda defeats the purpose. Looks like a catch-22. The only way I see out of this is if there was some cleaver way to do it randomly AND not use the same space ever again. But that would almost certainly require large amounts of memory. A working mathematical model is most likely not possible for this.


*** OFF TOPIC ***
By the way, I happened to be checking out Shift1 the other day and I realized that you can most likely get a significant speed up by putting a diode in parallel with each resistor. The idea is to shorten the wait time before sending the next command (charge time for CS and CT). You may also have to add a third resistor to lower charging current at least a little, but that is easy and probably won't be a problem anyway. It's a fairly straightforward mod and should give a significant performance boost. Over all it should bring the 15μs, 30μs, and 300μs charging times all down to 1~5μs instead.

 

[Mr RB]

...
*** OFF TOPIC ***
By the way, I happened to be checking out Shift1 the other day and I realized that you can most likely get a significant speed up by putting a diode in parallel with each resistor. The idea is to shorten the wait time before sending the next command (charge time for CS and CT). You may also have to add a third resistor to lower charging current at least a little, but that is easy and probably won't be a problem anyway. It's a fairly straightforward mod and should give a significant performance boost. Over all it should bring the 15μs, 30μs, and 300μs charging times all down to 1~5μs instead.

Thanks for that, and you are totally correct that would improve speed considerably.

It has already been suggested by a number of people, and I should probably make a note of that possible improvement on my web page. The reason it was not implemented on the kit is that it's just extra complexity, extra parts and construction work etc.

The system even with the extra slow timings I used will write to all characters on the LCD in "the blink of an eye" anyway. As I used large safety margins the periods shown in my diagram can be reduced quite a bit is speed is an issue, and also the cap values can be reduced to say half the size and the periods halved as well, doubling the speed.

And for the same reason I don't think anyone has bothered doing that, because... if it works and works quick enough that there is no problem, then people won't bother changing it.