A Method of Constructing
Quasigroup Field-Based Random Number Generators
Czeslaw Koscielny 2003
Academy of Management in Legnica, Poland
Faculty of Computer Science
e mail: c.koscielny@wsm.edu.pl
(Classic Worksheet Maple 9)
Introduction
The skill to produce satisfactory sequences of random numbers is one of the crucial tasks of cryptography. For this reason a lot of types of random number generators in the literature [4, 5, 6 ] are described. Many of known and generally used random number generators are not excellent enough for modern cryptographic applications, so it's worth trying to develop new generators, because, as wrote George Marsaglia, "...random number generator is much like sex: when it's good it's wonderful, and when it's bad it's still pretty good" ([4], keynote in the documentation of DIEHARD) . Thus, taking into account that there is never too much of a good thing, in the contribution a method of designing a new familly of random number generators based on the concept of quasigroup fields, has been presented. A notion of a very simple algebraic system, originated with quasigroups [1, 2] and permutations, called quasigroup field and denoted by , for the first time in [3 ] has been mentioned, but for the reader's convenience, its definition in Appendix is repeated. A random nature of quasigroup field predestine this means in a natural manner to be used for producing random numbers.
In principle, discussed generators may deliver random and non-predictable, periodic sequences of elements of of an arbitrary order . These sequences QFFSR sequences are called (abbreviation of Quasigroup Field Feedback Shift-Register), since they are created using feedback shift-registers over . It has been experimentally shown that there exist a lot of QFFSR sequences generators of diverse structure, many of them giving sequences of elements with a good randomness. Therefore, the hard problem of optimizing QFFSR sequences generators has been indicated.
In the contribution a particular attention mainly to generating random bytes has been paid, since it is currently the most interesting problem for application researchers. However, it is not difficult to observe that the method may be used in designing any random number generator.
QFFSR Sequences Generators
A feedback shift-register over an arbitrary quasigroup field , shortly called QFFSR, can be built using the circuit elements shown in Fig. 1.
Fig. 1. Circuit elements used in a feedback shift-register over :
element storage device, an additive inverter, a multiplicative inverter, an adder and a multiplier, all for performing operations in
A general arrangement of QFFSR of length in Fig. 2. is presented. It consists of stages (or storage elements) numbered , each capable of storing one element and having one input and one output; and also non-shown clock input which controls the movement of data contained in memory cells. The register will properly work if its first stage output and at least one output of other stages is connected to the feedback network.
Fig. 2. QFFSR of length : a general arrangement
As it is known, during each unit of time the following operations are performed:
The output of the feedback network in the -th time unit depends on the content of storage elements in the previous time unit. Thus, QFFSR considered as a generator of random elements may work. It uses an initial set of elements from
as a seed and generates successive elements by the recursion equations
where denotes the required number of elements of the output sequence. This is a periodical sequence and it will be named QFFSR sequence. The term length of a QFFSR sequence will denote the length of its period. Thus, the length of a QFFSR sequence ends with the elements of seed. In general, any value of a seed is possible. However, since the length of the generated sequence depends on the seed, some values of seed giving short sequences may be less useful. Function can be composed of any number of expressions involving an arbitrary number of variables (but at least and yet another one , ), and any number of operations in . For example, the work of QFFSR sequences generator shown in Fig. 3.
Fig. 3. An example of QFFSR sequences generator
can be described by means of equations
Fig. 4. Another example of a QFFSR sequences generator
The other example of generator, shown in Fig. 4., produces output sequence according to relations:
One may also consider the tables of operations in to be a second component of a seed. In this case, using QFFSR sequences generator as a keystream generator for a stream cipher over , we have to our disposal a very huge keyspace, indeed. But often in many systems the tables of operations in are made public. In this instance, if we need to augment the keyspace, we can make the function additonally dependent on some number of constants , and consider these constants together with the initial state of all stages of the register as a generator seed. Such an approach allows to design many diverse families of QFFSR sequences generators. One member of such family in Fig. 4. is given.
Fig. 5. QFFSR sequences generator with iterated feedback network connections
The generator consists of the -stage feedback shift-register in which the feedback network is formed by means of identical elements and one a little different element . It is assumed here that any feedback network element has two inputs in the form of a constant and of the output ot of -th stage of the register, and that it computes the same expression. Because of its modularity the generator of such structure for a hardware implementation is convenient. A detailed example of a generator of the above structure in Fig. 6. is shown.
Fig. 6. A detailed QFFSR sequences generator with iterated feedback network connections (it follows form the states of switches that only the outputs of the first and -th stages form inputs to the feedback network)
Any element of a feedback network connection is equipped with two switches and . If we want to connect the feedback network with the output of th stage of the register, the switch must be closed (on) while the switch must be open (off), otherwise inversely, ought to be closed with open. Suppose that the output of the first stage and some number of outputs of stages th, th, th are connected with the feedback network, In this case the following recurrence relations generate the output sequence:
From this short introduction to QFFSR sequences generators it follows that the presented method makes it possible to design practically an unlimited number of generators of diverse structures. The problem is how to find the simplest structure which will give the best generator. It is not easy because this task cannot be analitycally solved: the behaviour of QFFSR sequences is unpredictable. However, it should ensure a good randomness of QFFSR sequences.
A software implementation of QFFSR sequences generators is very flexible because in a given structure an additive inverter can be easily exchanged for a multiplicative inverter. The same concerns an adder and a multiplier. In this way, a procedure simulating, for example, the generator from Fig. 3., may generate 16 diverse sequences using the same seed. The number of sequences generated by a procedure simulating specific QFFSR may be considerably increased by taking into consideration that binary operations in quasigroup fields are ordinarily non-associative and non-commutative. Since all sequences generated in this way have usually diverse lengths, they may be concatenated together to form one long QFFSR sequence.
Using Maple one only may easily generate QFFSR sequence and examine the frequency of the occurence of elements of in it. But to study its randomness, a special tool should be used. According to the author, a good tool for it is freely available very stringent DIEHARD battery of tests [4].
This worksheet can suppy the reader with plenty of data for studying the statistical properties of QFFSR sequences.
Maple Implementation of QFFSR Sequences Generators
To equip the reader with the tool enabling him to experiment on QFFSR sequence s, the following procedures have been implemented in Maple 9 interpreter and written into the file qfrngpl.m :
In the output sequence the actual value of the seed t times is repeated. While computing the sequence this value and the number of the last element of the seed in the output sequence are printed out. It allows to see that the seed is irregularly placed in the output sequence.
Procedures qfrng1 , qfrng1l , qfrng2 and qfrng2l are rather suited for generating and testing shorter sequences. If one has a need to generate and examine sequences of an arbitrary length he may use procedures qfrng1lf and qfrng2lf .
Experimenting with QFFSR Sequences Generators
To experiment with QFFSR sequences generator s presented in this contribution the file qfrngpl.m ought to be read first. Then, the order of must be established and operations on elements of enabled. For example, let us invoke the procedure qfrng1 :
You may also write more general procedures which will comment results of computations:
We see that the sequence no. 15 is useless.
Similarly, you can invoke the other procedures:
Finally, using the files previously computed, we may, in many ways, produce new files containing random bytes in the following manner:
Conclusions
It has been experimentally proved that there exist periodic shift-register sequences over and that these sequences, named QFFSR sequences can be easily generated both using an appropriate software and a dedicated hardware as well. The QFFSR sequence is strongly non-linear and very hard to study since its period cannot be analytically determined and it bears a strong resemblance to truly random sequence. For this reason QFFSR sequences may find broad application in cryptography and statistics.
Using the software developed in this contribution, several 15 MByte disk files containing mainly pieces of QFFSR sequences over have been computed by the author. These files by means of the program DIEHARD have been tested, and result of the tests have been stored in the directory diehard.tst . Looking through these tests, the reader can form his opinion on the quality of the presented generators.
The author hopes that this report will provide inspiration for later work on quasigroup field-based random number generators.
Appendix
Consider an algebraic system , consisting of a finite set of elements in which two internal binary operations, called addition and multiplication, respectively, are defined. Let where denotes an arbitrary positive integer . The -element quasigroup field, denoted by , is the above system, satisfying the axioms:
This means that multiplication is distributive under addition, and that there exist in formal additive and multiplicative inverses, which can be functions many-to-one as well as one-to-one, both having nothing to do with addition and multiplication. From the last but one axiom it follows that the division by 0 is possible. For practical purposes, it is also assumed, that . Since , and are quasigroups, addition and multiplication need be neither commutative nor associative.
References
[1] Dnes, J., Keedwell, A.D.: Latin Squares and their Applications , Budapest, Akademiai Kiad, 1974
[2] Dnes, J., Keedwell, A.D.: Latin Squares - New Developments in the Theory and Applications , Annals Disc. Math., Vol. 46, Amsterdam, North-Holland, 1991 [3] Koscielny, C.: The Application of Quasigroup Fields in Designing Efficient Hash Functions, http://www.mapleapps.com
[4] DIEHARD: a battery of tests of randomness, http://stat.fsu.edu/~geo/
[5] Menezes, A. J., van Oorschot P., Vanstone S.: Handbook of Applied Cryptography , CRC Press, 1996
[6] Schneier, B.: Applied Cryptography Second Edition : Protocols, Algorithms, and Source Code in C , John Wiley & Sons, Inc., 1996
