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.
The shrinking generator uses two linear feedback shift registers. 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 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.
Read more about Shrinking Generator: An Implementation of A Shrinking Generator in Python
Famous quotes containing the words shrinking and/or generator:
“And my spirit is grown to a lordly great compass within,
That the length and the breadth and the sweep of the marshes of
Glynn
Will work me no fear like the fear they have wrought me of yore
When length was failure, and when breadth was but bitterness sore,
And when terror and shrinking and dreary unnamable pain
Drew over me out of the merciless miles of the plain,—
Oh, now, unafraid, I am fain to face
The vast sweet visage of space.”
—Sidney Lanier (1842–1881)
“He admired the terrible recreative power of his memory. It was only with the weakening of this generator whose fecundity diminishes with age that he could hope for his torture to be appeased. But it appeared that the power to make him suffer of one of Odette’s statements seemed exhausted, then one of these statements on which Swann’s spirit had until then not dwelled, an almost new word relayed the others and struck him with new vigor.”
—Marcel Proust (1871–1922)