Application Center - Maplesoft

# A Method of Constructing Quasigroup Field-Based Random Number Generators

You can switch back to the summary page by clicking here.

qfrng.mws

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 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 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 :

• 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 shift-register, 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 +1-th 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";

 > qfinit(5);

 > 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);

 > qfinit(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 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:

•  and  are quasigroups,
• ,
• ,
•

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