Truth tables of some nonlinear feedback functions
for 15-bit feedback shift registers
with the maximum length of state cycles

 

Izabela Janicka-Lipska

e-mail: janicka@sk-kari.put.poznan.pl

 

1. Introduction

The functions presented here could not be included, because of their size, in some papers where they are referred to. Each function f(x1, x2,, x15) is a 15-variable Boolean function with the following property: the 15-bit shift register (with f as its feedback function) has a state cycle of the maximum length 215. The functions have been selected by an algorithm presented in:

Janicka-Lipska I., Nonlinear feedback functions of maximal shift registers and their application to the design of a cryptographic hash function (in Polish), Ph. D. thesis, Poznan, 2001.

The feedback functions are used for constructing a family of cryptographic hash functions with a variable length of hash result, called the FSR-255 family.

 

2. Function files

            The functions are given in the following files:

bulletf01.txt
bulletf02.txt
bulletf03.txt
bulletf04.txt
bulletf05.txt
bulletf06.txt
bulletf07.txt
bulletf08.txt
bulletf09.txt
bulletf10.txt
bulletf11.txt
bulletf12.txt
bulletf13.txt
bulletf14.txt
bulletf15.txt
bulletf16.txt
bulletf17.txt
bullet all.zip

 

3. File format

Each function is given in an ASCII-type file containing a sequence of 8192 hex symbols (0−F) with no separating characters. The function truth table can be obtained by the following three-step procedure:

1.      Transforming the file original sequence to the reverse-word sequence

        Split the file original sequence of 8192 hex symbols into 1024 words consisting of 8 hex symbols.

        Reverse the order of hex symbols in each 8-symbol word (exchange symbol No 1 with symbol No 8, symbol No 2 with symbol No 7, etc.).

2.      Transforming the reverse-word sequence to the binary sequence of function values
Replace each hex symbol with its 4-bit binary representation (the leftmost bit is the most significant bit).

3.      Transforming the binary sequence of function values to the function truth table

        Form the sequence of all input words (binary sequences of length 15) in the order of increasing value of numbers represented by input words.

        Assign successive words from the above sequence (representing values of input variables) to successive elements from the binary sequence (representing function values) in such a way that:

        the first (leftmost) bit of the binary sequence is assigned the word (0,0,,0),

        the last (rightmost) bit of the binary sequence is assigned the word (1,1,,1).

 

To explain the file format, the above procedure is applied as an example to the initial part of the f01.txt file.

Example

Step 1. Transforming the file original sequence to the reverse-word sequence

The file original sequence: 3FE73EDD9ACFF4EEDBE9EFDCE782D96653F83779...

The reverse-word sequence:  DDE37EF3EE4FFCA9CDFE9EBD669D287E97738F35...

 Step 2. Transforming the reverse-word sequence to the binary sequence of function values

The reverse-word sequence:  D   D   E   3   7   E   F   3   E   E   ...

The binary sequence:        1101110111100011011111101111001111101110...

 Step 3. Transforming the binary sequence of function values to the function truth table

The binary sequence:f   1101110111100011011111101111001111101110...

The input variables:│x15 0101010101010101010101010101010101010101...

                    │x14 0011001100110011001100110011001100110011...

                    │x13 0000111100001111000011110000111100001111...

                    x12 0000000011111111000000001111111100000000...

                    │x11 0000000000000000111111111111111100000000...

                    │x10 0000000000000000000000000000000011111111...

                    │x9  0000000000000000000000000000000000000000...

                    x 0000000000000000000000000000000000000000...

                    │x 0000000000000000000000000000000000000000...

                    │x6  0000000000000000000000000000000000000000...

                    │x 0000000000000000000000000000000000000000...

                    x 0000000000000000000000000000000000000000...

                    │x3  0000000000000000000000000000000000000000...

                    │x2  0000000000000000000000000000000000000000...

                    x1  0000000000000000000000000000000000000000...