2
$\begingroup$

We want an algorithm for the following task:

We are given $n$ and $i$ and we want to check if an $n$-bit LFSR with the sub-register exactly $n/2$ and an interval of $i$ "works". We say an interval of $i$ "works" when each string $x\in \{0,1\}^n$ that is not the all-zero string appears exactly $i+1$ times before the LFSR loops.

One way of solving the problem is brute-force simulation. Is there a better way of solving this problem?


Background

So, first a quick refresher on what an LFSR is. A Linear Feedback Shift Register uses particular bits of the current state to help determine what the next state is. By XORing together particular bits (called taps), then shifting the result of the XOR into the register, every value for that size register is achieved once and only once with the only exception being the zero state (where all bits are zero) in which no matter which bits you XOR, you'll shift in another zero. For example, an LFSR with 8 bits will go through all 255 unique states before landing on the original state.

enter image description here

More detailed definitions and examples of LFSRs can be found on Wikipedia.

Now assume that we have two LFSRs, one inside the other, e.g. in the picture above assume that the 2 bits on the right hand side are themselves a smaller LFSR. We alternate between performing shift operation on the larger LFSR and on the smaller one. We call the number of times that we shift the larger LFSR before shifting the smaller one the interval.


Motivation

I began looking for ways to expand on LFSRs, ways to use it or ways to manipulate the process in the name of cryptography. Soon enough I found this interesting reaction. The best way I can think to explain it is through example. P.S. If I say "every state," assume that I do mean with the exception of the all zero state unless otherwise mentioned.

If you have an 8 bit LFSR, you'll land on every state exactly once before you land on the original starting state. Inspired by how A5/1 uses multiple LFSRs, I wondered if there was a way I could have 2 LFSRs overlap each other somehow. I began looking into what would happen if an LFSR "contained" another LFSR. Imagine having an 8 bit LFSR as such:

XXXXYYYY

Imagine the front half, the 4 Ys, is a second 4 bit LFSR. I started by shifting the entire register (all Xs and Ys above) as an 8 bit LFSR, then shifting the 4 bits (the Ys) before shifting the 8 bits again. It would alternate between shifting all 8, the first 4, all 8, the first 4, etc... I'm inventing terminology here, let's call shifting all 8 bits a "shift" and shifting the first 4 bits as a "subshift." Note that both shifting and subshifting shift towards the least significant bit to the right. Also, during a subshift, the Xs above are unaffected, the carry bit from the subshift goes in the most significant bit of the sub-register which is the left most Y above.

I wrote a little app with 255 labels to print how often that particular state was landed on. I.e. the 5th label showed how many times the full register held the value 5. The zero label was of course always zero. This yielded nothing initially. Eventually I thought that I was subshifting too often. So I tried shifting twice before subshifting. Then three times... Four... Five... Finally I tried doing 11 shifts between each subshift. That's when the magic happened! I watched as my app slowly totaled up every state to 12. I ran it again, I debugged and stepped through it to make sure I wasn't doing something wrong. If you shift an 8 bit register 11 times, then 1 subshift, then 11 more subshifts, etc. you eventually land on every state 12 times.

My first thought was will 12 land on every value 13 times? And I began testing... Most numbers went on way too long. I generally stopped looking when a state happened more than +1 of the interval I was using (if I had an interval of 40, and a value hit 42, I knew that wouldn't produce the same results as 11 did) and slowly a list formed:

8 bit register with 4 bit sub-register working intervals:
11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
225, 237, 253

If you shift X number of times, every state will be landed on X + 1 times, BUT only if X (the interval) is one of those values. The only exception to the "+1" trend was 254 which landed on every state 21 times. There's no need to test values larger than 255 (for an 8 bit register), because if you shift 255 times, you'll be back where you started. Remember, these are my findings for 8 bit registers in which the front 4 bits are subshifted.

I looked into doing a 16 bit register with an 8 bit sub-register and began finding equal results (just different values), this is not a complete list because it generally took 6-8 hours to test an interval:

16 bit register with 8 bit sub-register working intervals:
7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630, 655,
721, 725, 808, 860, 867, 893

All of these numbers also follow the "+1" rule of each state being landed on interval + 1 times. I understand where the +1 is coming from: if you subshift to a number, you land on that number then shift interval times to interval other numbers.

I've been studying this phenomenon for over a year. My goal is to accurately predict what intervals "work" and which ones don't. Currently my best bet is to brute force (although I know a few things that can indicate early on if an interval DOESN'T work, such as if you land on the initial state it indicates you've made a full cycle.)

Has anybody seen anything like this? Know what kinds of math I can use to analyze and test this with? I've tried using previous working values to predict future values, but they appear to be random, i.e. 29 to 63 is a huge gap where 176 and 177 both work. I've looked into there being a correlation between 8 bit and 16 bit numbers, but since both sets are increasing, they look highly correlated but have a huge standard error. I need to abstractly find what intervals work with 100% accuracy because my encryption requires we finding a working interval for a 4096 bit register... 16 bit took 6 to 8 hours to test a number, 4096 would take billions of billions of years to test a single interval value by brute force.

P.S. I have no clue how to tag this question... Any help would be appreciated there, too.

EDIT: Many comments have pointed out I should do smaller register sizes. Here's some of that data in as close to a table as I can get:

 4 bit: 1, 7, 11, 13

 8 bit: 11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
        225, 237, 253

16 bit: 7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630,
        655, 721, 725, 808, 860, 867, 893

Because this is more collaborative than Stack Exchange questions usually allow, I'm breaking my rule and putting out my email:

my email

$\endgroup$
  • $\begingroup$ No, the cycling length of an n-bit LFSR with the sub register being exactly n/2 and an interval of i is ((2^n)-1)*(i+1). I'm asking for how to determine, without brute force, what intervals work. Intervals that "don't work" exhibit very non-uniform behavior. $\endgroup$ – Corey Ogburn Aug 10 '11 at 22:49
  • 3
    $\begingroup$ have you solved this for the obvious simpler cases? I.e. 4 bits with the first 2 being subshifted, or even 3 bits with the first 2 being subshifted? Also... your question has a lot of extra text and requires a lot of reading to get at your question. It might be a good idea to follow Dijkstra's advice: "if you can spend 10 minutes to save each of your readers 1 minute, then it is polite to do so if you expect at least 10 readers". At least introduce some headings and clearly mark your question. $\endgroup$ – Artem Kaznatcheev Aug 10 '11 at 22:54
  • $\begingroup$ I haven't looked into 4 bit LFSRs with 2 bit sub registers. As for 3 bit LFSRs, I'm not sure whether to round up or down when cutting that in half, I've stuck with 8 and 16 with half size internal registers. $\endgroup$ – Corey Ogburn Aug 10 '11 at 22:56
  • $\begingroup$ you can't round down for 3, since shifting 1 bit is pointless. I strongly suggest solving these simpler 3-2 and 4-2 cases, it will be a good exercise. $\endgroup$ – Artem Kaznatcheev Aug 10 '11 at 22:59
  • 2
    $\begingroup$ @Kaveh I think by "works" he means each string $x \in \{0,1\}^n$ that is not the all-zero string appears exactly $i + 1$ times before the LFSR loops. $\endgroup$ – Artem Kaznatcheev Aug 10 '11 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.