Editing Shrinking generator

{{Short description|Form of pseudorandom number generator}}
In [[cryptography]], the '''shrinking generator''' is a form of [[pseudorandom number generator]] intended to be used in a [[stream cipher]]. It was published in Crypto 1993 by [[Don Coppersmith]], [[Hugo Krawczyk]] and [[Yishay Mansour]].<ref>D. Coppersmith, H. Krawczyk, and Y. Mansour, “[https://link.springer.com/chapter/10.1007/3-540-48329-2_3 The shrinking generator],” in CRYPTO  ’93:  Proceedings  of  the  13th  annual  international cryptology  conference  on  Advances  in  cryptology, (New York, NY, USA), pp. 22–39, Springer-Verlag New York, Inc., 1994</ref>

The shrinking generator uses two [[linear-feedback shift register]]s. One, called the {{var|A}} sequence, generates output bits, while the other, called the {{var|S}} sequence, controls their output. Both {{var|A}} and {{var|S}} are clocked; if the {{var|S}} [[bit]] is 1, then the {{var|A}} bit is output; if the {{var|S}} bit is 0, the {{var|A}} bit is discarded, nothing is output, and the registers are clocked again. This has the disadvantage that the generator's output rate varies irregularly, and in a way that [[Timing attack|hints at the state of S]]; this problem can be overcome by buffering the output. The random sequence generated by LFSR can not guarantee the unpredictability in secure system and various methods have been proposed to improve its randomness <ref>Poorghanad, A. et al. [https://ieeexplore.ieee.org/abstract/document/4724668 Generating High Quality Pseudo Random Number Using Evolutionary methods] ''IEEE'', DOI: 10.1109/CIS.2008.220.</ref>

Despite this simplicity, there are currently no known attacks better than exhaustive search when the feedback polynomials are secret. If the feedback polynomials are known, however, the best known attack requires less than {{var|A}} • {{var|S}} bits of output.<ref>Caballero-Gil, P. et al. [https://arxiv.org/abs/1005.0087 New Attack Strategy for the Shrinking Generator] ''Journal of Research and Practice in Information Technology'', Vol. 1, pages 331–335, Dec 2008.</ref>

A variant is the [[self-shrinking generator]].

==An implementation in Python==
This example uses two Galois LFRSs to produce the output pseudorandom bitstream. The Python code can be used to encrypt and decrypt a file or any bytestream.

<syntaxhighlight lang="python">
#!/usr/bin/env python3

import sys

# ----------------------------------------------------------------------------
# Crypto4o functions start here
# ----------------------------------------------------------------------------


class GLFSR:
    """Galois linear-feedback shift register."""

    def __init__(self, polynom, initial_value):
        print "Using polynom 0x%X, initial value: 0x%X." % (polynom, initial_value)

        self.polynom = polynom | 1
        self.data = initial_value
        tmp = polynom
        self.mask = 1

        while tmp != 0:
            if tmp & self.mask != 0:
                tmp ^= self.mask

            if tmp == 0:
                break

            self.mask <<= 1

    def next_state(self):
        self.data <<= 1

        retval = 0

        if self.data & self.mask != 0:
            retval = 1
            self.data ^= self.polynom

        return retval


class SPRNG:
    def __init__(self, polynom_d, init_value_d, polynom_c, init_value_c):
        print "GLFSR D0: ",
        self.glfsr_d = GLFSR(polynom_d, init_value_d)
        print "GLFSR C0: ",
        self.glfsr_c = GLFSR(polynom_c, init_value_c)

    def next_byte(self):
        byte = 0
        bitpos = 7

        while True:
            bit_d = self.glfsr_d.next_state()
            bit_c = self.glfsr_c.next_state()

            if bit_c != 0:
                bit_r = bit_d
                byte |= bit_r << bitpos

                bitpos -= 1

                if bitpos < 0:
                    break

        return byte


# ----------------------------------------------------------------------------
# Crypto4o functions end here
# ----------------------------------------------------------------------------


def main():
    prng = SPRNG(
        int(sys.argv[3], 16),
        int(sys.argv[4], 16),
        int(sys.argv[5], 16),
        int(sys.argv[6], 16),
    )

    with open(sys.argv[1], "rb") as f, open(sys.argv[2], "wb") as g:
        while True:
            input_ch = f.read(1)

            if input_ch == "":
                break

            random_ch = prng.next_byte() & 0xFF
            g.write(chr(ord(input_ch) ^ random_ch))


if __name__ == "__main__":
    main()
</syntaxhighlight>

==See also==
* [[FISH (cipher)|FISH]], an (insecure) [[stream cipher]] based on the shrinking generator principle
* [[Alternating step generator]], a similar [[stream cipher]]

==References==
{{reflist}}

{{Cryptography stream}}

[[Category:Articles with example Python (programming language) code]]
[[Category:Stream ciphers]]
[[Category:Pseudorandom number generators]]