A self-shrinking generator is a PRNG that is a variant of the shrinking generator concept.
Algorithm
A self-shrinking generator wraps another pseudorandom bit generator and attempts to make it more difficult to guess the internal state from the output.
- Generate two bits.
- If the first bit you generated is a
1, output the second bit. - Otherwise, output nothing.
- Go to step 1.
In [2]:
def self_shrinking(generator): while True: first = next(generator) second = next(generator) if first: yield second
Application to LFSRs
In [3]:
def lfsr(key): state = lfsr_key_deriv(key) while True: b = state[0] b ^= state[2] b ^= state[6] b ^= state[7] state.pop(0) state.append(b) yield b
In [4]:
gen_output(lfsr(b"Hello world")) gen_output(lfsr(b"Hello World"))
Out [4]:
'0111101100110011100111100110110011000010110101010100101010001110'
Out [4]:
'0010101111100110001001010100000110001110111001010100000011100011'
In [5]:
gen_output(self_shrinking(lfsr(b"Hello world"))) gen_output(self_shrinking(lfsr(b"Hello World")))
Out [5]:
'1011101001101000100110101000000001000111101010101111100010110000'
Out [5]:
'0011000010101011100001000100001000110011111011100001100001011110'
References and useful links
- Self-shrinking generator on Wikipedia
- Shrinking generator on Wikipedia