[Back] A Lagged Fibonacci generator creates pseudorandom numbers. It uses a generalisation of the Fibonacci sequence.

## Lagged Fibonacci Generator |

## Theory

A Fibonacci sequence is defined by:

\(S_n = S_{n-1}+ S_{n-2}\)

and where the current term is the sum of the two previous values. For example if we start at zero and one, we end up with the sequence of:

0,1,1,2,3,5,8,13,21,34,55...

The problem we have in computer security is to generate random numbers that cannot be predicted, as we will often generate encryption keys for our tunnelled connections and for encrypted data. We thus need to create a random seed value - typically generated from a truly random event - and then use this to generate a sequence of random values.

We can then generalise the sequence by selecting offset values of j and k, and then defining an operator:

\(S_n \equiv S_{n-j} \star S_{n-k} \pmod{m}, 0 < j < k\)

The operator \( \star \) can be either addition (\(+\)), subtraction (\(-\)), multiplication (×) or X-OR (⊕).

There are various safe pairs of values for j and k, including 3 and 7. So let's generate with an additional and with a seed value of 6421893 and use a mod of 10.

In this case we will start with the sequence of 6,4,2,1,8,9,3, and where we take the 3rd and 7th element and add them together and take (mod 10). In the first step, we have 2 + 3 (mod 10) which gives 5. This will then become a new random number. Let's now generate a few other ones:

j= 3 k= 7 Seed: 6421893 6 4 [ 2] 1 8 9 [ 3] --> 5 4 2 [ 1] 8 9 3 [ 5] --> 6 2 1 [ 8] 9 3 5 [ 6] --> 4 1 8 [ 9] 3 5 6 [ 4] --> 3 8 9 [ 3] 5 6 4 [ 3] --> 6 9 3 [ 5] 6 4 3 [ 6] --> 1 3 5 [ 6] 4 3 6 [ 1] --> 7 5 6 [ 4] 3 6 1 [ 7] --> 1 6 4 [ 3] 6 1 7 [ 1] --> 4 4 3 [ 6] 1 7 1 [ 4] --> 0 3 6 [ 1] 7 1 4 [ 0] --> 1 6 1 [ 7] 1 4 0 [ 1] --> 8 1 7 [ 1] 4 0 1 [ 8] --> 9 7 1 [ 4] 0 1 8 [ 9] --> 3 1 4 [ 0] 1 8 9 [ 3] --> 3 4 0 [ 1] 8 9 3 [ 3] --> 4 0 1 [ 8] 9 3 3 [ 4] --> 2 1 8 [ 9] 3 3 4 [ 2] --> 1 8 9 [ 3] 3 4 2 [ 1] --> 4 9 3 [ 3] 4 2 1 [ 4] --> 7 3 3 [ 4] 2 1 4 [ 7] --> 7

The random number then becomes:

5, 6, 4, 3, 6, 1, 7, 1, 4, 0, 1, 8, 9, 3, 3, 4, 2, 1, 4, 7

A simple program to generate this is given next:

import array import sys j = 3 k = 7 modval = 10 val = "8675309" def conv(val): arr = [] for i in xrange(len(val)): arr.append(int(val[i])) return arr def showvals(val,j,k): for i in xrange(len(val)): if (i==j-1): print "[%3d]"%val[i], elif (i==k-1): print "[%3d]"%val[i], else: print "%3d"%val[i], s=conv(val) print "j=",j," k=",k print "Seed:\t",val if (len(s)<k): print "Value needs to be larger than 7" exit() showvals(s,j,k) for n in xrange(20): out = (s[j-1] + s[k-1]) % modval for i in xrange(len(s)-1): s[i] = s[i+1] s[len(s)-1] = out print "-->",out showvals(s,j,k) print "-->",out

If we select a value of 100 for the mod value, we get:

j= 3 k= 7 Seed: 6421893 Mod: 100 6 4 [ 2] 1 8 9 [ 3] --> 5 4 2 [ 1] 8 9 3 [ 5] --> 6 2 1 [ 8] 9 3 5 [ 6] --> 14 1 8 [ 9] 3 5 6 [ 14] --> 23 8 9 [ 3] 5 6 14 [ 23] --> 26 9 3 [ 5] 6 14 23 [ 26] --> 31 3 5 [ 6] 14 23 26 [ 31] --> 37 5 6 [ 14] 23 26 31 [ 37] --> 51 6 14 [ 23] 26 31 37 [ 51] --> 74 14 23 [ 26] 31 37 51 [ 74] --> 0 23 26 [ 31] 37 51 74 [ 0] --> 31 26 31 [ 37] 51 74 0 [ 31] --> 68 31 37 [ 51] 74 0 31 [ 68] --> 19 37 51 [ 74] 0 31 68 [ 19] --> 93 51 74 [ 0] 31 68 19 [ 93] --> 93 74 0 [ 31] 68 19 93 [ 93] --> 24 0 31 [ 68] 19 93 93 [ 24] --> 92 31 68 [ 19] 93 93 24 [ 92] --> 11 68 19 [ 93] 93 24 92 [ 11] --> 4 19 93 [ 93] 24 92 11 [ 4] --> 97 93 93 [ 24] 92 11 4 [ 97] --> 97 Random [5, 6, 14, 23, 26, 31, 37, 51, 74, 0, 31, 68, 19, 93, 93, 24, 92, 11, 4,97]

Our values will thus be in the range of 0 to the mod value minus one. In normal circumstances we use a mod value (m) which is a power of 2, such as \(2^{32}\), and which will generate 32-bit random values. The seed value used is obviously important, in order for the values not to be predictable. It is a lagged method as we must remember a given number of values from the past generation.

The Lagged Fibonacci Generator is used in Freeciv - an empire-building strategy game - and use the values of {j = 24, k = 55}.