Cryptography Reference
In-Depth Information
One class of electronic devices that function similar
to rotors is the Fibonacci generator (also called the Koken
generator after its inventor), named for the Fibonacci
sequence of number theory. In the classical Fibonacci
sequence 1, 1, 2, 3, 5, 8, 13…each successive term, begin-
ning with 2, is the sum of the two terms to its left; i.e.,
F
i
=
F
i
− 1
+
F
i
− 2
. By loose analogy, any sequence in which each
term is the sum of a collection of earlier terms in fixed (rel-
ative) locations is called a Fibonacci sequence.
In an n-stage Fibonacci generator the contents of an
n-bit shift register are shifted right one position at each
step—the bit at the extreme right being shifted out and
lost—and the new left-hand bit is determined by the logi-
cal sum (1 + 1 = 1, 0 + 1 = 1 + 0 = 0 + 0 = 0; symbolized by
0
)
of bits occurring in prescribed locations in the shift regis-
ter before the shift was made. For example, for n = 5 and
x
i
=
x
i
− 1
0
x
i − 4
0
x
i − 5
one obtains the 31-bit cycle 01011101
10001111100110100100001, which is the maximal-length
sequence realizable with a five-stage generator. The rel-
evance of Fibonacci generators to cryptography is seen
if the sequence is read five bits at a time by successively
shifting one bit position to the left. This yields a scram-
bled ordering of the integers 1 through 31 that resembles
the scrambled ordering produced by rotors.
The cryptographic problem is that the combin-
ing operation used to determine successive states in the
sequence is linear and hence easily invertible, even though
the sequence can be 2
n
− 1 bits in length before repeating.
Another problem is how the key is to be used. The obvious
choice—i.e., simply to use the key to determine the num-
ber of steps in the cycle from the plaintext
n
-tuple to the
ciphertext
n
-tuple—is cryptographically insecure because
a known plaintext cryptanalysis would quickly reveal the
key. A frequently reinvented solution to this problem has
