In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, the shrinking generator is a form of pseudorandom number generator

Pseudorandom number generator

A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...

 intended to be used in a stream cipher

Stream cipher

In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...

. It was published in Crypto 1993 by Don Coppersmith

Don Coppersmith

Don Coppersmith is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-boxes, strengthening them against differential cryptanalysis...

, Hugo Krawczyk, and Yishay Mansour.

The shrinking generator uses two linear feedback shift register

Linear feedback shift register

A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...

s. One, called the A sequence, generates output bits, while the other, called the S sequence, controls their output. Both A and S are clocked; if the S bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

 is 1, then the A bit is output; if the S bit is 0, the A bit is discarded, nothing is output, and we clock the registers again. This has the disadvantage that the generator's output rate varies irregularly, and in a way that hints at the state of S; this problem can be overcome by buffering the output.

Despite this simplicity, the shrinking generator has remained remarkably resistant to cryptanalysis: there are currently no known attacks better than exhaustive search when the feedback polynomials are secret.

An interesting variant is the self-shrinking generator

Self-shrinking generator

A self-shrinking generator is a pseudorandom generator, which is based on the shrinking generator concept. Various variants of the self-shrinking generator based on a linear feedback shift register are studied for use in cryptography.-Algorithm:...

.

An implementation of a shrinking generator 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.


#!/usr/bin/python

import sys

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

class glfsr:
def __init__(self, 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 = tmp ^ self.mask;

if tmp 0:
break

self.mask = self.mask << 1

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

retval = 0

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

return retval

class sprng:
def __init__(self, polynom_d, init_value_d, polynom_c, init_value_c):
self.glfsr_d = glfsr(polynom_d, init_value_d)
self.glfsr_c = glfsr(polynom_c, init_value_c)

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

while 1 1:
bit_d = self.glfsr_d.next_state
bit_c = self.glfsr_c.next_state

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

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))

print "GLFSR D0: using polynom 0x%X, initial value: 0x%X." % (int(sys.argv[3], 16), int(sys.argv[4], 16))
print "GLFSR C0: using polynom 0x%X, initial value: 0x%X." % (int(sys.argv[5], 16), int(sys.argv[6], 16))

f = open(sys.argv[1], "rb")
g = open(sys.argv[2], "wb")

while 1

1:
input_ch = f.read(1)

if input_ch

"":
break

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

f.close
g.close

main


The C code is also available, see External links.

See also

• FISH
  FISH (cipher)
  The FISH stream cipher is a fast software based stream cipher using Lagged Fibonacci generators, plus a concept from the shrinking generator cipher. It was published by Siemens in 1993. FISH is quite fast in software and has a huge key length...
  
  , an (insecure) stream cipher
  Stream cipher
  In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
  
  based on the shrinking generator principle

External links

• An implementation of a cryptographically secure shrinking pseudorandom number generator.