leo.blog();

Self Shrinking Generator

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.

  1. Generate two bits.
  2. If the first bit you generated is a 1, output the second bit.
  3. Otherwise, output nothing.
  4. 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

Leave a Comment