Simple method of selecting totalistic rules for pseudorandom number generator based on nonuniform cellular automaton

The entropy \(E_{h}\) task is to specify the statistical quality of each pseudorandom number sequences (PNS). We used Shannon’s equation of even distribution as an entropy function. To calculate the entropy’s value, each PNS is divided into subsequences of size h \((h=4)\). Let k be the number of values, which can construct a single element of a sequence (for binary values \(k=2\)) and \(k^{h}\) a number of possible states of each sequence of length h (if \(h=4\) than \(k^{h}=16\)). \(E_{h}\) can be calculated in the following way:where \(p_{h_{j}}\) is a probability of occurrence of a sequence \(h_{j}\) in a PNS.

The entropy achieves its maximum \(E_{h}=h\), when the probabilities of the \(h_{j}\) (possible sequences of the length h) are equal to \(\frac{1}{k^{h}}\).

The starting point is an analysis of a nonuniform CA with all totalistic rules. The research cover TCA rules with neighborhood radius \(r=1\), and an examination of all subsets of these 16 rules (i.e., \(\{t0,...,t15\}\)). In the next stage also all subsets of TCA rules with \(r=2\) are examined. This whole set consists of 64 TCA rules. However, the number of subsets to analyze is the sum of each of combinations \(C(n,k)=\frac{n!}{k!*(n-k)!}\), where n is the number of rules in the whole set, and k is a number of rules in the subset. In the nonuniform, TCA the cooperation of rules is essential. So, if one rule cooperates with each of the other rules in a two-element subset, then probably they could cooperate with rules in a subset larger than two numbers of rules. Cooperation of rules means that such rules applied in nonuniform TCA will generate high-quality bitstreams. Therefore, in the next experiments a two-element subset of nonuniform TCA rules will be analyzed.

In all performed experiments, CA size was equal to 100, and CA was working in 4096-time steps (a value suitable for Entropy test), which examine the distribution of subsequences consisted of 4 elements in the whole bit sequence. From one CA run one-bit sequence obtained from states of randomly selected CA cell was selected. Each rule test was repeated 10000 times with random initial configuration of CA state, and the average Entropy of each rule was calculated.

During the experiments each of 120 subsets containing 2 rules with \(r=1\) was analyzed, and only 5 subsets of rules were selected, because average entropies of other subsets are lower than 3,8. Table 1 presents values of minimal, average, and maximal entropy for each best two-element subsets and one the worst subset of rules with \(r=1\) for TCA. We can see that only five from all subsets of TCA rules have a good quality, and obtained entropy values are near to maximal equal to 4. The best subsets of rules are: \(\{t5, t10\}\), \(\{t5, t2\}\), \(\{t5, t11\}\), \(\{t10, t2\}\), \(\{t10, t11\}\), among them the highest average entropy equal to 3,999860445 has the subset \(\{t5, t10\}\). Other rules are characterized by not enough high value of entropy. As we can see in Table 1, we have four rules ({t2, t5, t10, t11}) which joined in pairs are characterized by a high value of entropy, except the couple \(\{t11, t2\}\), for which the minimal entropy is almost equal to 0. It means that stable or cyclic bit sequence was generated. We can conclude that rules t2 and t11 do not cooperate with each other like other rules mentioned above.

In Table 2 we can see presented value of entropy for nonuniform TCA for subsets of rules selected from set of cooperating rules. Table 2 holds results for subsets composed of four \(\{t5, t10, t2, t11\}\), or three \(\{t5, t10, t2\}\) and \(\{t5, t10, t11\}\) cooperating with each other TCA rules. Despite the higher number of rules in these subsets, the values of entropy are higher for subset composed of two rules \(\{t5, t10\}\) (see, Table 1).

The next stage of experiments was performing the entropy test on two-element subsets from the whole set of TCA rules with \(r=2\). During the experiments, each of 2016 subsets containing 2 rules with \(r=2\) was analyzed. The 125 subsets of rules, with average entropy not lower than 3,9 were selected. In this subset of 125 couples of rules, the best average value of entropy and best minimal entropy are characterized by the couples presented in Table 3. As we can observe, the rules composed of pairs crate set of the strongest rules \(\{t10, t11, t20, t21, t42, t43, t52\) and \(t53\}\), except the pairs \(\{(t20, t52), (t52, t53)\}\) with very low entropy values. Each couple from this set is presented in Table 3. Moreover, we can see that the best values of entropy (minimal, average, and maximal) present the pair \(\{t21, t42\}\). Also, in the subset of 125 pairs of rules occasionally rules: \(\{t5, t12, t13, t18, t19, t22, t23, t25, t26, t28, t30, t33, t35, t36, t37,\) t38, t44, t50 and \(t51\}\) have appeared.

Figure 1 presents the graphical representation of TCA work. We can see states of TCA during the time steps. We can observe each of the single cells and their states during the time steps. In the cases (a) and (b) on the diagrams we can’t see stable or cyclic bit sequences. This fact confirms corresponding entropy values near to maximal (equal to 4), see Table 3. In the opposite cases (c) and (d), diagrams are showing us vanishing randomness and stable and also cyclic bit sequences. As was mentioned above, TCA rules from these pairs do not cooperate with each other, so low values characterize entropies of such generated sequences (see, last rows of Table 3).

Table 4 presents values of entropy for maximal set of rules for nonuniform TCA, selected from set of cooperating rules. We can see high entropy values, average, and minimal and maximal obtained during the executed experimental tests. Figure 2 presents the space-time diagram of nonuniform TCA with rules applied from this set. As we can see, there are no stable or periodic sequences of bits, 0’s are represented by white, and 1’s by black squares.

To be sure that the TCA rules did not generate stable or cyclic sequences of bits, let us look at them from the perspective of one of the most crucial cryptographic criteria—a balance of the TCA. This approach analyzes the behavior of rules in the sense of balance in TCA rules structure.

Balance (regularity) is one of the important criteria which should be fulfilled by a Boolean function used in ciphering (see, [22]). This criterion says that each output bit (0 or 1) of a Boolean function should appear an equal number of times for all possible input values. For the CA-based generator, it means that independently on the initial configuration (except consisted of only 0s or only 1s), CA should achieve the state where the number of 0s and 1s in a CA state is equal to \(\frac{N}{2}\), and should maintain this state in the next time steps. The balance of the CA could be satisfied by using the balanced rules of CA. CA rule as a Boolean function \(f: Z_{2}^{n}\rightarrow Z_{2}\) maps \(n\) binary inputs (neighborhood state of CA) to a single binary output. So, the balance of a Boolean function is measured using its Hamming Weight and is defined as:A Boolean function is balanced when its Hamming Weight is equal to \(2^{n-1}\). In means that balanced rule has in binary form an equal number of 0s and 1s. As we can see the rules described in [9, 11, 15‐17, 20] are balanced for both \(r=1\) and \(r=2\). For a single rule as rule of CA-based PRNG, a balance is necessary criterion except formal tests, but for a set of rules it is insufficient.

Rules for TCA-based PRNG selected during the tests, despite passing the appropriate tests, sometimes generated bit sequences with low randomness. Since the tests are examining only bit sequences chosen randomly from thousands generated by the generator, sometimes, incidental cyclic bit sequence was not considered or averaged results from many tests do not reflect its proper characteristic. So occasionally, even a good rule applied in TCA can create cyclic or partially stable bit sequences. In the paper [14] we presented a method of selection of Elementary CA rules based on a cryptographic criterion known as a balance. The proposed method selects a maximal size set of available CA rules for a given neighborhood radius and suitable for PRNG. This technique guarantees to avoid wrong assignments of rules resulting in the creation of unwanted stable bit sequences and provides cryptographically strong bit sequences and huge keyspace. This method introduces a relationship for good bit mixing. A rule for CA-based PRNG should perform the same number of the subsequent cell state transitions: \(0s \rightarrow 0s\), \(0s \rightarrow 1s\), \(1s \rightarrow 0s\) and \(1s \rightarrow 1s\). Therefore, for Elementary CA, the outputs 0s and 1s should be selected in a special configuration, resulting in CA rule. This method cannot be identically transferred to creating the TCA rules, because in TCA, does not exist a direct relationship between neighborhood structure and effect of work. Elementary CA rule from a strict neighborhood structure creates an adequate state of CA cell. In TCA the neighborhood structure is not essential; instead, the sum of elements in the neighborhood plays a vital role. From here, for different neighborhood structures with the same sum of 0s and 1s, the TCA rule gives the same effect and generates identical states of TCA cells.

Let’s analyze a TCA rule with \(r=1\) as a Boolean function. In Table 5 the letters \(a,...,d \in \{0, 1\}\) correspond to outputs of a Boolean function. When \(a+...+d=2\), then the Elementary CA rule is balanced, but for TCA, the balance means \(a*1+b*3+b*3+d*1=(1+3+3+1)/2=4\), because the totalistic rule creates the same CA state for few different neighborhood structures. For a good mixing of bits, a rule for TCA-based PRNG should perform the same number of the following cell state transitions: \(0s \rightarrow 0s\), \(0s \rightarrow 1s\), \(1s \rightarrow 0s\) and \(1s \rightarrow 1s\). The totalistic rule for few neighborhood structures creates the same CA state; therefore, for these output 0s and 1s should be selected in a, ..., d in a special configuration. A bad schedule might cause that rule will produce stable sequences during an interaction with other rules (see, Fig. 1 (c), (d)). Elementary CA for a single neighborhood state generates one output (see, the paper [14]). However, in the TCA case, one single output is created by the neighboring states.

TCA rules to be balanced should have two 0s and two 1s in binary form. Moreover, the same number of 1s generating 1s, 1s generating 0s, 0s generating 1s, and 0s generating 0s, which determine the situation where the same number of neighborhood states generate 1s and 0s. So, to satisfy the above requirements, a rule should fulfill the following logical sentence, based on designation Table 5:Let {0, 1, X} be the binary alphabet, where X is the mask, and means X masking each value in the alphabet. From above, when we have a situation, where the part of TCA state is, e.g., {..0111..} and neighborhood configuration is {..X11X..} (from {X11} and {11X}), then two middle cells of TCA will produce sequences of 1s during the TCA work, etc. So, in formula 4: \((a\ne b)\) protects rule against input configurations of neighborhood: {11X} and {X11} translates in TCA \(1s \rightarrow 1s\), and leads to generation of unwanted stable sequence of 1s; \((c\ne d)\) protects against input configurations {00X} and {X00} translates \(0s \rightarrow 0s\), leading to generation of unwanted stable sequence of 0s. Also in binary alphabet, from formula 4 we receive relationship \((b\ne c)\), which protects rule against input configurations of neighborhood: {10X} and {X01} translating \(0s \rightarrow 0s\), leading to generation of unwanted stable sequence of 0s, and configurations {01X} and {X10} translating \(1s \rightarrow 1s\), leading to generation of unwanted stable sequence of 1s. Formula 4 could be simplified to the following logical sentence:Let us solve the formula 5.

Let \(a=0\) then \(c=0\) and \(b=d=1\), and this way we obtain the binary TCA rule \((0101)_{2}\), i.e., a decimal rule \(t5_{10}\).

Let \(a=1\) then \(c=1\) and \(b=d=0\), and this way we obtain the binary TCA rule \((1010)_{2}\), i.e., a decimal rule \(t10_{10}\).

As we can see, analyzed rules have a neighborhood radius equal to 1. To summarize, only two of these rules are free from a wrong configuration in nonuniform TCA-based PRNG, leading to generating stable or cyclic sequences of bits. We can obtain the same result by analyzing, e.g., the entropy of generated bit sequences, see Table 1 (first row of data), where we can see high values of entropies for this set of rules. Entropies for these rules far exceed values for other presented in the same table. Nevertheless, experimental surveys need much more time than the method of analysis with applying balance criterion, which gives a possibility to easily select rules.

Analogously, applying the above method, we can create a suitable logical formula for TCA rules with neighborhood \(r=2\). Table 6 presents a TCA rule with \(r=2\) as Boolean function.

On the base of Eqs. 4 and 5 for CA rules with \(r=1\), we can create the suitable logical formula for CA rules with \(r=2\). The dependencies between outputs of the TCA rule with \(r=2\), which during cooperation with other rules do not create stable sequences present following logical sentence:The letters \(a, b, c, d, e, f \in \{0, 1\}\) correspond to outputs of a Boolean function. When \(a*1+b*5+c*10+d*10+e*5+f*1=32/2=16\) then the rule is balanced. The dependencies between outputs of the TCA rule with \(r=2\) such that its interaction with other rules do not generate stable sequences was achieved in two selected TCA rules: t21, t42. But, when we give a possibility not to satisfy the balance a little bit, i.e., to be not 16 but for example \(17=16+1\) or \(15=16-1\), with a specific degree of freedom equal to 1. Then, constructed this way rules will be not balanced but quasi-balanced, resulting in making the changes for Boolean function outputs in \(a,\; f \in \{0, 1\}\). Therefore, Eq. 6 is changing to the following form:by reducing the relationship \((a\ne f)\wedge (a\ne b)\).

The solutions of these logic sentences leads to set of TCA rules: \(\{t10, t11,\) t20, t21, t42, t43, t52 and \(t53\}\) corresponding to set presented in Table 4 discovered during the time-consuming experiments. This set of rules was obtained automatically based on test results (see the previous section) and confirmed by analyzing TCA’s structure with applied rules. Selected rules could be applied to BitStream Generator as a seed of TCA-based PRNG. The session keys number for a selected set of TCA rules is equal \(8^{N}*2^{N}\), where the N is the number of TCA cells, while the number of session keys for every single rule, is only equal to \(1^{N}*2^{N}\). We could conclude that nonuniform TCA with a large session keyspace could increase the protected information’s safety.

In this same easy way, everyone can select the best sets of TCA rules free from the creation of cyclic or stable sequences for various TCA neighborhood radius.