Summation generator

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search

The summation generator, created in 1985, by Rainer Rueppel, was a cryptography and security front-runner in the late 1980s. It operates by taking the output of two LFSRs through an adder with carry. The operation's strength is that it is nonlinear. However, through the early 1990s various attacks against the summation generator eventually led to its fall to a correlation attack. In 1995 Klapper and Goresky were able to determine the summation generator's sequence in only 219 bits.

An improved summation generator with 2-bit memory was then proposed by cryptographers Lee and Moon. In the new generator scheme an extra bit of memory is added to the nonlinear combining function. The objective in the modification was to make the summation generator immune to correlation attack.

An attack against the improved summation generator was reported by Mex-Perera and Shepherd in 2002 by exploiting linear relations. Besides, in June 2005 an algebraic attack was developed. Using this attack a PC can calculate the initial state of the summation generator within 3 minutes even with 256 bit LFSRs.


See Also on BitcoinWiki[edit]