So What Do Sea Shells Have To Do With Computer Security?

A Fibonacci sequence is defined by:

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

This series was named after Fibonacci (and who also defined the concept of zero). If we plot the lengths in the spirals get the following:

This type of shape is seen in nature, such as:

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 Fibonacci sequence by selecting offset values of j and k, and then defining an operator:

The operator ⋆ 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 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 create with a mod value of 100 and a seed of:

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] --> 21
 93  24 [ 92]  11   4  97 [ 21] --> 13
 24  92 [ 11]   4  97  21 [ 13] --> 24
 92  11 [  4]  97  21  13 [ 24] --> 28
 11   4 [ 97]  21  13  24 [ 28] --> 25
  4  97 [ 21]  13  24  28 [ 25] --> 25
Random [5, 6, 14, 23, 26, 31, 37, 51, 74, 0, 31, 68, 19, 93, 93, 
24, 92, 11, 4, 97, 21, 13, 24, 28, 25]

Our values will thus be in the range of 0 to the mod value minus one. In normal 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.

Try your own example [link].