A noniterative reconstruction algorithm for lfsr prng

LSBs	action of state1
action of state2
(00,00),(00,10) (10,00),(10,10)	state1>>1	state2>>1
(11,11)	((state1>>1)^tap1)>>1	(((state2>>1)^tap2)>>1)^tap2
(00,01),(00,11)	state1>>2	(state2>>1)^tap2
(01,00),(11,00)	(state1>>1)^tap1	state2>>2
(10,01),(10,11)	(state1>>2)^tap1	(state>>1)^tap2
(01,10),(11,10)	(state1>>1)^tap1	(state2>>2)^tap2
(01,01)	(((state1>>1)^tap1)>>1)^tap1	((state2>>1)^tap2)>>1
(01,11)	(((state1>>1)^tap1)>>1)^tap1	(((state2>>1)^tap2)>>1)^tap2
(11,01)	((state1>>1)^tap1)>>1	((state2>>1)^tap2)>>1

TABLE I. LSBS AND ACTIONS OF EACH STATE

TABLEⅠshows all the 16 combinations of the least two bits of the two states. As long as the state transition table is known, and if the states corresponding to a certain id are also known, all the states can be easily calculated reversely.

3. 
   REVERSE RECONSTRUCTION ALGORITHM
   

1. 
   Algorithm Description
   

The algorithm assumes a sequence of consecutive IDs is known. In practice, CNAME chaining technique or NS chaining technique [12] can be used to obtain a sequence of consecutive IDs.
It’s important to observe that the inner states of the two LFSRs are always shifting to the right as they advancing. Therefore, if the states of the later IDs are known in some way, it’s easy to reversely reconstruct the previous IDs’ states.
Reverse reconstruction algorithm reconstructs the full state of the two LFSRs after the first ID of the sequence is generated from the bottom of the ID sequence. Here it goes:

• 
  Reverse Reconstruction Algorithm:
  

Step 1. Calculate 16-bit states for some IDs. Such IDs have two conditions: ending up with 1 as its LSB and following by at least one ID ending up with 1 as its LSB;
Step 2. Reversely reconstruct the states from the bottom of the ID sequence if the ID’s state is already figured out all to the first ID of the sequence;
Step 3. Check if the states of the first ID are fully reconstructed. We can achieve this by predict whether using current ID sequence be able to reconstruct full states and at least how many IDs should be used can we get full state;
Step 4. Start from the last ID with known states, predict the next ID’s states and verify the states;
Step 5. If we get more states, reversely reconstruct the states from the bottom of the ID sequence again, otherwise stop.

2. 
   Algorithm Analysis
   

There are three key points in the reverse reconstruction algorithm. First, how to calculate some IDs’ states and what’s the prerequisite? Second, How to calculate the former using later states? Third, How to predict how many ID is needed to get the full states?
First, as described above, if two consecutive IDs with 1 as their LSB are known, we can calculate the 16-bit states for the first ID, take LSB(state2) = 00, LSB(state1) = *1 (* means both 0 and 1 are acceptable) for example (state1 stands for state of LFSR1, state1’ for next state of LFSR1, curid for current ID, nxtid for next ID, tap1 for a constant and so on):

• 
  LSB(state2) = 00, LSB(state1) = *1: