qfrng.mws
A Method of Constructing
Quasigroup FieldBased 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 nonpredictable, periodic sequences of elements of
of an arbitrary order
. These sequences
QFFSR sequences
are called (abbreviation of Quasigroup Field Feedback ShiftRegister), since they are created using feedback shiftregisters 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 shiftregister 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 shiftregister 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 nonshown 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 content of stage
is moved to stage
for
,

the output of the feedback network forms an element of the output sequence and a new content of the
th stage.
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 shiftregister 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 nonassociative and noncommutative. 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
:

S := proc(a, b::nonnegint) ... end proc:
returns a sum of two arbitrary elements
.

P := proc(a, b::nonnegint) ... end proc:
returns
a product of two arbitrary elements
.

Ai := proc(a::nonnegint) ... end proc:
returns
an
additive inverse
of an arbitrary element
.

Mi := proc(a::nonnegint) ... end proc:
returns
a
multiplicative inverse
of an arbitrary element
.

qfinit := proc(q::posint) ... end proc:
initializes computations in
, using the files
s5
,
p5
,
mi5
,
ai5
,
s16
,
p16
,
mi16
,
ai16 and s256
,
p256
,
mi256
,
ai256
, containing suitable operation tables and allowing to perform operations in
for
. Thus, the actual value of a parameter
can be 5, 16 or 256. If the reader wants to compute in a quasigroup field of other order, he can make his own similar files, in which the tables of operations in a quasigroup field of required order are stored.

qfrng1 := proc(s0::list, F1, F2, G1, G2::procedure, k, n, v::posint)
simulates, in a more general manner, the operation of
QFFSR sequences generator
shown in Fig. 3. The parameter
s0
represents the initial state of shiftregister, parameters
F1, G1

operation of
additive or multiplicative inversion,
F2, G2
 operation of addition or multiplication, respectively. The procedure takes advantage of the fact that the multiplication and addition in
are not commutative, and that the operation of multiplicative (additive) inversion for the operation of additive (multiplicative) inversion can be exchanged, similarly as addition and multiplication. Thus, many possible feedback network connections determining the work of the generator can be made. The procedure uses only 16 of such possibilities, and the parameter
v
,
the actual value of which can be equal to
selects the feedback function. The parameter
k
(
) decides that outputs of
k
th and
k
+1th stages are inputed to the feedback network. The procedure returns:

a sequence of elements of length, determined either by the actual value of the a parameter
n
, or equal to the period of
QFFSR sequence, if this period is
less than the value of actual parameter
n
,

a length of the output sequence,

a frequency of elements in the output sequence.

qfrng1l := proc(s0::list, F1, F2, G1, G2::procedure, k, n, t::posint)
a procedure with the same formal parameters as the procedure
qfrng1
, with the exception of the parameter
t
. The procedure concatenates together the sequences obtained using the procedure
qfrng1
with
v
= 1, 2, ...,
t
,
and returns:

a sequence equal to the concatenations of
t
sequences,

a length of the output sequence,

a frequency of elements in the output sequence.
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.

qfrng1lf := proc(s0::list, F1, F2, G1, G2::procedure, k, n, t::posint, fn::string)
operates exactly as the procedure
qfrng1l
, but it writes the output sequence to the disk file named
fn
, and returns the frequency of elements in this sequence.

qfrng2 := proc(s0, h, sh::list, F1, F2, G1, G2::procedure, n, v::posint)
works similarly as the procedure
qfrng1
and emulates the operation of
QFFSR sequences generator
shown in Fig. 6. The formal parameters
s0, F1, F2, G1, G2, n, v
have the same meaning as in the procedure
qfrng1
, and the actual value ot the parameter
v
can be equal to
since the procedure
qfrng2
uses also 16 different feedback functions. The parameter
s0
together with the parameter
h
, both having the same number of elements, form the seed of the generator, while
sh
decides which elements of feedback network are active. Therefore,
sh
is a list containing at least one or up to
numbers from the set
. Similarly as the procedure
qfrng1
, this procedure returns:

a sequence of elements of length, determined either by the actual value of the a parameter
n
, or equal to the period of
QFFSR sequence, if this period is
less than the value of actual parameter
n
,

a length of the output sequence,

a frequency of elements in the output sequence.

qfrng2l := proc(s0, h, sh::list, F1, F2, G1, G2::procedure, n, t::posint)
operates in a similar manner as the procedure
qfrng1l
and returns the same quantities.

qfrng2lf := proc(s0, h, sh::list, F1, F2, G1, G2::procedure, n, t::posint, fn::string)
operates similarly as the procedure
qfrng1lf
and returns the same quantities.
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
:
> 
restart; read "qfrngpl.m";

> 
qfrng1([1, 2, 3], Mi, S, Ai, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, S, Ai, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, S, Mi, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, P, Ai, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, P, Mi, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, P, Mi, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Mi, P, Ai, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, S, Ai, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, S, Ai, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, S, Mi, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, S, Mi, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, P, Ai, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, P, Ai, S, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, P, Mi, P, 2, 10000, 5);

> 
qfrng1([1, 2, 3], Ai, P, Mi, S, 2, 10000, 5);

> 
qfrng1([0, 0, 0, 0], Ai, P, Ai, P, 3, 100000, 1);

You may also write more general procedures which will comment results of computations:
> 
qfg1 := proc(q, v::posint, s0::list)
local x, y, i, pn, n;
n := 0;
qfinit(q);
for x to 16 do
y := qfrng1(s0, Ai, S, Mi, P, v, q^nops(s0), x);
if y[2] < 30 then pn := [seq(0, i = 1 .. y[2])]
else pn := [seq(0, i = 1 .. 30)]
end if;
n := n + y[2];
if y[2] < 31 then
for i to y[2] do pn[i] := y[1][i] end do
else for i to 30 do pn[i] := y[1][i] end do
end if;
printf("\n%d%s%d", nops(pn),
" elements of the sequence no. ", x);
printf("\n%s", convert(pn, string));
printf("\n%s%d%s%s", "length of the sequence = ", y[2],
", frequency of elements: ",
convert(y[3], string))
end do;
printf("\n%s%d%s", "total length of all sequences = ", n, "\n")
end proc:

> 
qfg1(16, 2, [0, 1, 0]);

> 
qfg1(5, 4, [0, 0 ,0 ,0, 0]);

We see that the sequence no. 15 is useless.
Similarly, you can invoke the other procedures:
> 
qfinit(5): s0 := [0, 1, 0, 1]: qfrng1l(s0, Ai, S, Mi, P, 3, 10240, 3);

> 
qfinit(16); s0 := [13, 0, 1]:

> 
qfrng1l(s0, Ai, S, Mi, P, 2, 100000, 16);

> 
for i to 16 do x := qfrng2([1, 2, 4], [3, 4, 1],[2, 3], Ai, S, Mi, P, 10000, i): print(x[2], x[3]) end do:

> 
qfinit(256):
s0 := [0, 100, 50]:
t := time(): qfrng1lf(s0, Ai, S, Mi, P, 2, 15000000, 5,"qfsg1s3");
print(time()  t);
s0 := [0,10,100,200]:
t := time(): qfrng1lf(s0, Ai, S, Mi, P, 2, 15000000, 5,"qfsg1s4");
print(time()  t);
s0 := [0, 10, 100, 200, 128]:
t:=time():
qfrng1lf(s0, Ai, S, Mi, P, 2, 15000000, 5,"qfsg1s5");
print(time()  t);
s0 := [0, 10, 100, 200, 128, 16]:
t := time(): qfrng1lf(s0, Ai, S, Mi, P, 2, 15000000, 5,"qfsg1s6");
print(time()  t);
s0 := [0, 10, 100]:
t := time(): qfrng2lf(s0, [3, 0, 2], [2, 3], Ai, S, Mi, P, 15000000, 16, "qfsg2s3");
print(time()  t);
s0 := [0, 10, 100, 200]:
t :=time(): qfrng2lf(s0, [3, 0, 2, 200], [2, 4],Ai, S, Mi, P, 15000000,16,"qfsg2s4");
print(time()  t);
s0 := [0, 0, 0, 0, 0]:
t := time(): qfrng2lf(s0, [0, 1, 2, 3, 4], [2, 3, 5], Ai, S, Mi, P, 15000000, 16, "qfsg2s5");
print(time()  t);
pnf := fopen("maple", WRITE, BINARY): elf := array(0 .. q  1):
for i to q do elf[i  1] := 0 end do:
t := time():
for i to 15000000 do x := rand(256)(): elf[x] := elf[x]+1: writebytes(pnf,[x]) end do:
convert(elf, list); fclose(pnf): print(time()  t);

Finally, using the files previously computed, we may, in many ways, produce new files containing random bytes in the following manner:
> 
t := time():
ef1 := array(0 .. q  1):
ef2 := array(0 .. q  1):
for i to q do ef1[i  1] := 0; ef2[i  1] := 0 end do:
fi1 := fopen("qfsg2s4", READ, BINARY):
fi2 := fopen("qfsg2s5", READ, BINARY):
fo1 := fopen("qfsg2s45", WRITE, BINARY):
fo2 := fopen("qfsg2s54", WRITE, BINARY):
fs := filepos(fi1, infinity); filepos(fi1, 0);
for i to fs do b1 := readbytes(fi1): b2 := readbytes(fi2):
c1 := S(b2[1], b1[1]); writebytes(fo1,[c1]);
c2 := S(b1[1], b2[1]): writebytes(fo2, [c2]);
ef1[c1] := ef1[c1] + 1: ef2[c2] := ef2[c2] + 1:
end do:
fclose(fi1): fclose(fi2): fclose(fo1): fclose(fo2):

Conclusions
It has been experimentally proved that there exist periodic shiftregister 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 nonlinear 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 fieldbased 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 manytoone as well as onetoone, 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, NorthHolland, 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