Cyber Security and Fibonacci: Random Numbers and Hashing
Cyber Security and Fibonacci: Random Numbers and Hashing
The Fibonacci sequence — also known as the Golden Ratio — is one of the most fundamental characteristics of the Universe. It is created by starting at 0 and 1, and where the next value in the sequence is the addition of the previous two values. Thus we get 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on. Leonardo Fibonacci came up with the sequence when he observed the growth of a rabbit population over the period of a year, but can be seen within many things in nature, including flower petals, pine cones, tree branches, shells, and the shape of galaxies:
In general, a Fibonacci sequence is defined by:
Sₙ=Sₙ₋₁+Sₙ₋₂
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...
Fibonacci and Random Numbers: Lagged Fibonacci Generator
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ₙ≡Sₙ₋ⱼ★Sₙ₋ₖ (mod m), 0<j<k
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 case, we will start with the sequence of 6,4,2,1,8,9,3, and where we take the 3rd and 7th elements 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 [here]:
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 sysj = 3
k = 7
modval = 10
val = "8675309"
def conv(val):
arr = []
for i in xrange(len(val)):
arr.append(int(val[i]))
return arrdef 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",valif (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³², 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 here.
Fibonacci Hashes
We can use the Fibonacci series for a random number generator, and if these random numbers are well distributed, we can then use it to create a hash function. For this, we could have a 64-bit range, and where we can divide by the golden rule value to determine a multiplier for an input data value:
fib = 2^64 / Φ ≈ 11400714819323198485
and where Φis the golden ratio and where:
Φ= ( 1 + sqrt (5) ) / 2 = 1.618033989…..
The values are then:
2⁸ = 158
2¹⁶ = 40503
2³² = 2654435769
2⁶⁴ = 11400714819323198485
2¹²⁸ = 210306068529402873165736369884012333108
We can then multiply the required value with the current hash, and add on the data byte value:
for (int i = 0; i < len / 8; i++) {
h = h * fib + data[i];
}The code becomes:
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <intrin.h>
#include <algorithm>
#include <array>
#include <iostream>
#include <random>
#include <string>
void fib_hash64(const void* key, int len, uint32_t seed, void* out);
void fib_hash32(const void* key, int len, uint32_t seed, void* out);
using namespace std;
using std::cout;
using std::cin;
typedef uint64_t uint64;
typedef uint32_t uint32;
int main(int argc, char* argv[])
{
string str = "abc";
char buff[128];
uint32 u32;
uint64 u64;
int seed = 0;
strcpy_s(buff, str.c_str());
if (argc >= 2) {
if (strlen(argv[1]) > BUFFSIZE - 1) return(0);
strcpy_s(buff, argv[1]);
}
if (argc >= 3) seed = atoi(argv[2]);
strcpy_s(hexdata, argv[3]);
printf("Key: %s\n",hexdata);
}printf("String: %s\n", buff);
printf("Seed: %d\n\n", seed);uint32_t u32f;
fib_hash32((void*)buff, strlen(buff), seed, &u32f);
printf("\nFib 32\t\t%lu Hex: %lx\n", u32f, u32f);uint64_t u64f;
fib_hash64((void*)buff, strlen(buff), seed, &u64f);
printf("\nFib 64\t\t%llu Hex: %llx\n", u64f, u64f);
}The program is here:
https://asecuritysite.com/encryption/smh_fib
Conclusions
And there you go, there is beauty in cybersecurity.
Subscribe: https://billatnapier.medium.com/membership