https://doi.org/10.31449/inf.v43i2.2687 Informatica 43 (2019) 199–207 199
Some Remarks and Tests on the DH1 Cryptosystem Based on Automata
Compositions
Pál Dömösi
Institute of Mathematics and Informatics, University of Nyíregyháza
H-4400 Nyíregyháza, Sóstói út 31/B, Hungary
Faculty of Informatics, University of Debrecen
H-4028 Debrecen, Kassai út 26, Hungary
E-mail: domosi@unideb.hu
József Gáll, Géza Horváth
Faculty of Informatics, University of Debrecen
H-4028 Debrecen, Kassai út 26, Hungary
E-mail: gall.jozsef@inf.unideb.hu, horvath.geza@inf.unideb.hu
Norbert Tihanyi
Faculty of Informatics, Eötvös Loránd University
H-1117 Budapest, Pázmány Péter sétány 1/C, Hungary
E-mail: tihanyi.pgp@gmail.com
Keywords: automata network, NIST test, block cipher, statistics
Received: February 17, 2019
In this paper we discuss NIST test results of a previously introduced cryptosystem based on automata
compositions. We conclude that the requirements of NIST test are all fulﬁlled by the cryptosystem.
Povzetek: Analiziran je kriptirni sistem DH1 na osnovi konˇ cnih avtomatov s testom NIST.
1 Introduction and problem
statement
Dömösi and Horváth in their previous
works (see [Dömösi and Horváth, 2015a] and
[Dömösi and Horváth, 2015b]) introduced new block
ciphers based on Gluškov-type product of automata.
In what follows we will refer to the cipher in
[Dömösi and Horváth, 2015a] as the ﬁrst Dömösi-
Horváth cryptosystem, or in short, DH1-cipher, whereas to
the cipher in [Dömösi and Horváth, 2015b] as the second
Dömösi-Horváth cryptosystem, or in short, DH2-cipher.
In this paper we investigate some properties of the DH1-
cipher. However, we do not discuss all details of deﬁnition
and motivation regarding DH1-chipers in this paper.
Both systems use the following simple idea: consider
a giant-size permutation automaton such that the set of
states and the set of inputs consisting of all given length
of strings over a non-trivial alphabet as all possible plain-
text/ciphertext blocks. Moreover consider a cryptograph-
ically secure pseudo random number generator with large
periodicity having the property that, getting its really ran-
dom kernel, it serves a sequence of pseudo random strings
as inputs for the automaton. For each plaintext block the
system calculates the new state into which the actual pseu-
dorandom string takes the automaton from the state which
is identiﬁed as the actual plaintext block. The string –
identiﬁed as the new state– will be the ciphertext block
ordered to the considered plaintext block. Of course, the
ciphertext will be the concatenation of the generated ci-
phertext blocks. The giant size of the automaton makes
it infeasible to break the system by brute-force method.
For all notions and notations not deﬁned in this paper
we refer to the monographs [Dömösi and Nehaniv, 2005,
Mezenes and Vanstone, 1996]. The cryptosystem dis-
cussed here is a block cipher. Since the key automaton is
a permutation automaton, for every ciphertext there exists
exactly one plaintext making the encryption and decryption
unambiguous. Moreover, there is a huge number of corre-
sponding encoded messages to each plaintext so that sev-
eral encryptions of the same plaintext yield several distinct
ciphertexts.
Given the cryptosystem DH1-cipher described above a
natural question is the investigation of the statistical prop-
erties of the system from many perspectives. For in-
stance, the avalanche effect of the system –as a natu-
ral property required in the profession– may be tested by
several classical hypothesis tests. Some early results are
given in [Dömösi et al., 2017] where they conﬁrm that the
avalanche effect is fulﬁlled. However, further tests can and
should also be used, in particular the ones used for testing
whether the output of it can be distinguished from ’true’
random sources. That is why we turned to the well known
200 Informatica 43 (2019) 199–207 P. Dömösi et al.
NIST package of statistical tests in this paper, which can be
considered as a ’standard’ in the profession for such pur-
poses. Our main aim is to give the results of the NIST test
regarding the cryptosystem at issue (Section 5). For this
we describe the system (Section 3) together with some the-
oretical background (Section 2), as well as the necessary
details, of course, of our experimental analysis done for the
tests (Section 4). We show in this paper that the system we
discuss has passed all statistical tests in the NIST package.
2 Theoretical background
The automata are systems that can be used for the transmis-
sion of information of certain type. In wider sense, every
system that accepts signals from its environment and, as a
result, changes its internal state, can be considered as an au-
tomaton. By an automaton we mean a deterministic ﬁnite
automaton without outputs. The automatonA = (A;   ;  )
consists of the ﬁnite set of states A, the ﬁnite set of in-
put signals   , and the transition function  , which is often
written in a matrix form. The transition matrix of the au-
tomatonA = (A;   ;  ) consists of its states such that it
has as many rows as input signals, and there are as many
columns as states of the automaton. For the sake of sim-
plicity we assume thatA and   are ordered sets. Thej-th
element of thei-th row of the transition matrix will be the
state which is assigned by the transition function to the pair
consisting ofj-th state andi-th input signal. We say about
this elementa of thei-th row andj-th column of the tran-
sition matrix that thei-th input signal takes the automaton
from itsj-th state to statea. (In fact, in this case it is also
usual to say that the automaton goes from itsj-th state to
statea by the effect of thei-th input signal.) The rows of
the transition matrix can be identiﬁed with the input signals
of the automaton, and its columns with its states, while the
transition matrix itself with the transition.
If all the rows of the transition matrix are permutations
of the state set then we have a permutation automaton.
Lemma 1. An automatonA = (A;   ;  ) is a permutation
automaton if and only if for anya;b2A;x2   ,  (a;x) =
  (b;x) impliesa =b.
Proof. Suppose thatA is a permutation automaton. Then
all rows in its transition matrix are permutations of the state
set. But then none of the rows of the transition matrix has a
repetition. Therefore, for any states a;b 2 A and input
x 2   ;   (a;x) =   (b;x) implies a = b. Conversely,
assume that for any states a;b 2 A and input x 2   ;
  (a;x) =   (b;x) implies a = b. Then none of the rows
of the transition matrix has a repetition. Therefore all of its
rows are permutations of the state set. This completes the
proof.
The Gluškov-type product of the automata A
i
with respect to the feedback functions ’
i
(i 2
f1;:::;ng) is deﬁned to be the automaton
A = A
1
     A
n
(  ; (’
1
;:::;’
n
)) with state set
Figure 1: Gluškov-type product.
A =A
1
      A
n
; input set   ; transition function  given
by   ((a
1
;:::;a
n
);x) = (  1
(a
1
;’
1
(a
1
;:::;a
n
;x));:::;
  n
(a
n
;’
n
(a
1
;:::;a
n
;x))) for all (a
1
;:::;a
n
)2 A and
x2   (see also Figure 1). In particular, ifA
1
=::: =A
n
then we say thatA is a Gluškov-type power.
We shall use the feedback functions’
i
;i = 1;:::;n in
an extended sense as mappings’
  i
:A
1
      A
n
      ;
where ’
  i
(a
1
;:::;a
n
;  ) =   and ’
  i
(a
1
;:::;a
n
;px) =
’
  i
(a
1
;:::;a
n
;p)’
i
(  1
(a
1
;’
  1
(a
1
;:::;a
n
;p));:::;
  n
(a
n
;’
  n
(a
1
;:::;a
n
;p));x),a
i
2 A
i
;i = 1;:::;n;p2
    ;x2   : In the sequel,’
  i
;i2f1;:::;ng will also be
denoted by’
i
:
Next we deﬁne the concept of temporal product of au-
tomata. It is a model for multichannel automata networks
where the network may cyclically change its internal struc-
ture during its work on each channel.
LetA
t
= (A;   t
;  t
);t = 1; 2 be automata having
a common state set A: Take a ﬁnite nonvoid set   and
a mapping ’ of   into   1
    2
: Then the automaton
A = (A;   ;  ) is a temporal product (t-product) ofA
1
by
A
2
with respect to   and’ if for anya2 A andx2   ;
  (a;x) =   2
(  1
(a;x
1
);x
2
); where (x
1
;x
2
) = ’(x) (see
also Figure 2). The concept of temporal product is gener-
alized in the natural way to an arbitrary ﬁnite family of
n > 0 automataA
t
(t = 1;:::;n), all with the same
state set A, for any mapping ’ :   !
Q
n
t=1
  t
, by
deﬁning  (a;x) =  n
(      2
(  1
(a;x
1
);x
2
);    ;x
n
) when
’(x) = (x
1
;:::;x
n
). In particular, a temporal product of
automata with a single factor is just a (one-to-many) rela-
beling of the input letters of some input-subautomaton of
its factor.
Lemma 2. Every temporal product of permutation au-
tomata is a permutation automaton.
Proof. It is clear from the above mentioned remark that
every temporal product of permutation automata with a
single factor is a permutation automaton. Now letA
t
=
(A;   t
;  t
);t = 1; 2 be permutation automata with the
same state setA. Consider a temporal product ofA
1
and
A
2
with respect to an arbitrary input set   and mapping
’ :   !   1
    2
: Prove that for anya;b2A;z2   with
’(z) = (x;y);   2
(  1
(a;x);y) =   2
(  1
(b;x);y) implies
a =b:
Some Remarks and Tests on the DH1. . . Informatica 43 (2019) 199–207 201
Figure 2: Temporal product.
Indeed, let   1
(a;x) = c and   1
(b;x) = d: Recall that
A
2
is a permutation automaton. Therefore, by Lemma 1,
  2
(c;y) =   2
(d;y) impliesc = d: On the other hand,A
1
is also a permutation automaton. Thus, by Lemma 1,c =d
with  1
(a;x) = c and  1
(b;x) = d implya = b: Apply-
ing Lemma 1 again, we receive that the temporal product
ofA
1
andA
2
with respect to   and ’ is a permutation
automaton. Therefore our statement holds for all temporal
products having two factors. Now we consider a temporal
product of permutation automataA
1
;:::;A
n
;n > 2 with
respect to a given set   and mapping’:
Deﬁne the mappings ’
1
:   !   1
    2
; ’
2
:   ! ( 
1
    2
)     3
;:::;
’
n  1
:   ! (:::( 
1
    2
)   :::     n  1
)     n
with ’
1
(x) = (x
1
;x
2
);
’
2
(x) = ((x
1
;x
2
);x
3
);:::;’
n  1
(x) =
((:::((x
1
;x
2
);x
3
):::);x
n
) whenever
’(x) = (x
1
;:::;x
n
): Let B
1
denote the temporal
product ofA
1
andA
2
with respect to   and’
1
;B
2
denote
the temporal product ofB
1
andA
3
with respect to   and
’
2
;:::;B
n  1
denote the temporal product ofB
n  2
and
A
n
with respect to   and’
n
, respectively.
Then using the fact that our statement holds for all
temporal products with two factors we obtain that all of
B
1
;:::;B
n  1
are permutation automata. On the other
hand, it is clear thatB
n  1
is equal to the temporal prod-
uct of permutation automataA
1
;:::;A
n
with respect to   and’: Thus the proof is complete.
Given a functionf : X
1
      X
n
! Y; we say that
f is really independent of its i-th variable if for every
pair (x
1
;:::;x
n
); (x
1
;:::;x
i  1
;x
0
i
;x
i+1
;:::;x
n
)
2 X
1
        X
n
; f(x
1
;:::;x
n
) =
f(x
1
;:::;x
i  1
;x
0
i
;x
i+1
;:::;x
n
): Otherwise we say
thatf really depends on itsi-th variable.
A (ﬁnite) directed graph (or, in short, a digraph)D =
(V;E) (of ordern > 0) is a pair consisting of sets of ver-
ticesV =fv
1
;:::;v
n
g and edgesE  V  V: Elements
of V are sometimes called nodes. An edge (v;v
0
)2 E
is said to have a source v and a target v
0
. Moreover, we
say that v2 V is a source if there exists a v
0
2 V hav-
ing (v;v
0
)2 E, and v
0
2 V is a target if there exists a
v 2 V with (v;v
0
) 2 E . The pair (v;v
0
); (v
00
;v
000
) is
called a branch ifv =v
00
andv
0
6=v
000
. In addition,the pair
(v;v
0
); (v
00
;v
000
) is called a collapse ifv6=v
00
andv
0
=v
000
.
IfjVj =n then we also say thatD is a digraph of ordern:
IfV can be decomposed into two disjoint (nonempty) sub-
setsV
1
;V
2
such thatV
1
is the set of all targets andV
2
is the
set of all sources then we say thatD is a bipartite digraph.
If the bipartite graphD has neither branches nor collapses
then we say thatD is a simple bipartite digraph.
Let   be the set of all binary strings with a given
length ‘ > 0 and let n be a positive integer power of 2,
letA
1
= (  ;       ;  A1
) be a permutation automaton
such that for every a;x;x
0
;y;y
0
2   ;  A1
(a; (x;y)) 6=
  A1
(a(x
0
;y));  A1
(a; (x;y)) 6=   A1
(a(x;y
0
)); and let
A
i
= (  ;       ;  Ai
);i = 2;:::;n be state-isomorphic
copies ofA
1
such thatA
1
;:::;A
n
are not necessarily pair-
wise distinct, and letn be a power of 2. Consider the fol-
lowing simple bipartite digraphs:
D
1
= (f1;:::;ng;f(n=2 + 1; 1); (n=2 +
2; 2);:::; (n;n=2)g),
D
2
= (f1;:::;ng;f(n=4 + 1; 1); (n=4 +
2; 2);:::; (n=2;n=4);
(3n=4 + 1;n=2 + 1); (3n=4 + 2;n=2 +
2);:::; (n; 3n=4)g),
:::,
D
log2n  1
= (f1;:::;ng;f(3; 1); (4; 2); (7; 5);:::;
(8; 6); (n  1;n  3); (n;n  2)g),
D
log2n
= (f1;:::;ng;f(2; 1); (4; 3);:::; (n;n  1)g);
D
log2n+1
=D
1
;
:::;
D
2log2n
=D
log2n
.
For every digraph D = (V;E) with D 2
fD
1
;:::;D
2log2n
g let us deﬁne the Gluškov-
type product, called two-phase D-product,
A
D
= A
1
        A
n
( 
n
; (’
1
;:::;’
n
)) of
A
1
;:::;A
n
so that for every (a
1
;:::;a
n
); (x
1
;:::;x
n
)
2   n
;i 2 f1;:::;ng; ’
i
(a
1
;:::;a
n
; (x
1
;:::;x
n
)) =
(a
j
  x
j
;x
i
); if (j;i)2E, anda
j
  x
j
is the bitwise addi-
tion modulo 2 ofa
j
andx
j
,’
j
(a
1
;:::;a
n
; (x
1
;:::;x
n
))
= (a
0
i
  x
i
;x
j
); if (j;i)2E,a
0
i
denotes the state into which
’
i
(a
1
;:::;a
n
; (x
1
;:::;x
n
)) takes the automatonA
i
from
its statea
j
; anda
0
i
  x
i
is the bitwise addition modulo 2 of
a
0
i
andx
i
.
1
LetB = ( 
n
; ( 
n
)
2log2n
;  B
) be the temporal prod-
uct ofA
D1
;:::;A
D
2log
2
n
with respect to ( 
n
)
2log2n
and
the identity map ’ : ( 
n
)
2log2n
! ( 
n
)
2log2n
. We say
thatB is a key-automaton with respect toA
1
;:::;A
n
.
2
Obviously,B is unambigously deﬁned by the transition
matrix of A
1
and the bijective mappings   1
:   !
  ;:::;  n
:   !   which represent the state isomor-
phisms ofA
1
;:::;A
n
toA:
An important property of key-automata is explained in
the following result.
Theorem 1. Every key-automaton is a permutation au-
tomaton.
Proof. Let B = ( 
n
; ( 
n
)
2log2n
;  B
) be a key-
automaton. By deﬁnition, it is a temporal product of au-
tomataA
D1
;:::;A
D
2log
2
n
with respect to ( 
n
)
2log2n
and
1
We remark, that for everyj2 V
2
there exists exactly onei2 V
1
with(j;i)2E; and conversely, for everyi2V
1
there exists exactly one
j2V
2
with(j;i)2E. Therefore, all of’
1
;:::;’n are well-deﬁned.
2
Recall thatn should be a positive integer power of2.
202 Informatica 43 (2019) 199–207 P. Dömösi et al.
the identity map’ : ( 
n
)
2log2n
! ( 
n
)
2log2n
as deﬁned
above. By Lemma 2, it is enough to prove that each of
A
D1
;:::;A
D
2log
2
n
is a permutation automaton.
Consider an automatonA
D
= ( 
n
;   n
;  D
) withA
D
2
fA
D1
;:::;A
D
2log
2
n
g and the simple bipartite digraphD =
(V;E) assigned toA
D
: LetV
1
denote the set of targets and
V
2
denote the set of sources ofD as before.
By Lemma 1 it is enough to prove that
for any states (a
1
;:::;a
n
); (a
0
1
;:::;a
0
n
)
2   n
and input (x
1
;:::;x
n
) 2
  n
,   D
((a
1
;:::;a
n
); (x
1
;:::;x
n
))
=   D
((a
0
1
;:::;a
0
n
); (x
1
;:::;x
n
)) implies (a
1
;:::;a
n
) =
(a
0
1
;:::;a
0
n
).
Suppose   D
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  D
((a
0
1
;:::;a
0
n
); (x
1
;:::;x
n
)) = (b
1
;:::;b
n
) for
some state (b
1
;:::;b
n
) ofA
D
and let (i;j)2E. Observe
that for everyi2 V
1
there exists exactly onej2 V
2
with
(j;i)2 E; and vice versa, for every j 2 V
2
there exists
exactly one i2 V
1
with (j;i)2 E: This means that the
transitions in thei-th andj-th component automata depend
only on thei-th andj-th state and input components.
Then, by the effect of its input (a
j
  x
j
;x
i
) thei-th com-
ponent ofA
D
goes from its statea
i
into stateb
i
; and sim-
ilarly, by the effect of its input (b
i
  x
i
;x
j
) thej-th com-
ponent ofA
D
goes from its statea
j
into stateb
j
:
But then by the effect of its input (a
0
j
  x
j
;x
i
), thei-th
component ofA
D
goes from its statea
0
i
into stateb
i
; and
similarly, by the effect of its input (b
i
  x
i
;x
j
), the j-th
component ofA
D
goes from its statea
0
j
into stateb
j
:
Recall thatA
j
is a permutation automaton. Therefore,
applying Lemma 1,a
j
=a
0
j
: Therefore, using our previous
assumptions we can derive that by the effect of its input
(a
j
  x
j
;x
i
) thei-th component ofA
D
goes from its state
a
0
i
into stateb
i
: On the other hand, we assumed that by the
effect of its input (a
j
  x
j
;x
i
), thei-th component ofA
D
goes from its statea
i
into stateb
i
: Applying Lemma 1 again
we obtain thata
i
=a
0
i
:
Applying the above treatment to ev-
ery (i;j) 2 E; we receive (a
1
;:::;a
n
)
= (a
0
1
;:::;a
0
n
). This completes the proof.
The basic idea of DH1 cryptosystem is to use a ﬁ-
nite automaton and a pseudo random generator. The set
of states of the automaton consists of all possible plain-
text/cyphertext blocks and the input set of the automaton
contains all possible pseudo random blocks. The size of the
pseudo random blocks are the same as the size of the plain-
text/cyphertext blocks. For each plaintext block the pseudo
random generator generates the next pseudo random block
and the automaton transforms the plaintext block into a
cyphertext block by the effect of the pseudo random block.
The key is the transformation matrix of the automaton.
It is easy to see that the key must be a permutation au-
tomaton, since this property grants an unambiguous de-
cryption. This condition is satisﬁed by Theorem 1.
On the other hand we can have more than one cor-
responding ciphertext for each plaintext even if we use
the same key-automaton. The reason for this is that we
can change the pseudo random numbers generated by the
pseudo random generator. We can save a secret numbern
–as a part of the key– and before encryption we can choose
a (public) random numberm. This numberm will be the
ﬁrst block of the ciphertext, and before encryption and de-
cryption, the seed of the pseudo random number generator
can be calculated with an XOR operation from n and m
(n  m). This way each encryption process uses different
pseudo random numbers and results different ciphertext for
the same plaintext.
The problem with this idea is the following. Modern
block ciphers operate on ﬁxed-length groups of bits called
blocks. The size of the blocks is at least 128 bits (16 bytes),
so the size of the transition matrix of the automaton is huge,
namely 2
128
  2
128
  16 bytes, which is impossible to be
stored in the memory or on a hard disk. The solution is
to use an automata network. Gluškov-type product of au-
tomata consists of smaller component automata and it is
able to simulate the operation of a huge automaton. In this
case we should store only the transition matrix of the iso-
morphic component-automata, the structure of the compo-
sition and the secret numbern to calculate the seed of the
pseudo random number generator.
3 Encryption and decryption
A symmetric cryptosystem consists of the following:
– a set of plaintextsP,
– a set of ciphertextsC,
– a key spaceK,
– an encryption functione :P K!C , and
– a decryption functiond :C K!P .
Furthermore, the following property must hold for each
x2P andk2K:d((e(x;k);k) =x. Moreover, the cryp-
tosystem is called approved block cipher if and only if the
elements of the set of plaintexts and the set of ciphertexts
are at least 128 bit long (jPj  2
128
andjCj  2
128
).
Our cryptosystem is a block cipher one. Both of the en-
cryption and decryption apparatus have a pseudo random
generator and a key-automaton.
The encryption procedure is the following. Before the
encryption procedure, the pseudo random generator gets its
initialization vector as a true random stringr
1
:::r
n
2   n
,
where the pseudo random alphabet   is also the plaintext
and the ciphertext alphabet simultaneously. This initializa-
tion vector will also be the ﬁrst block of the ciphertext.
Then the apparatus reads the plaintext block-by-block
and, after reading the next plaintext blocka
1
    a
n
2   n
(the ﬁrst block ﬁrst), it generates the second, third, and the
further blocks of the ciphertext in the following way.
The apparatus takes the key-automaton B =
( 
n
; ( 
n
)
2log2n
;  B
) into the state a
1
    a
n
2   n
Some Remarks and Tests on the DH1. . . Informatica 43 (2019) 199–207 203
which coincides with the actual one, i.e. the last received
plaintext block.
Next the pseudo random number generator gener-
ates a 2log
2
n long number of pseudo random se-
quences w
1
;:::;w
2log2n
2   n
such that each of them
takes the next temporal component (the ﬁrst one ﬁrst)
A
D
= ( 
n
;   n
;  D
) (A
D
2 fA
D1
;:::;A
D
2log
2
n
g)
of the key automaton into the state a
k;1
    a
k;n
=   D
(a
k  1;1
    a
k  1;n
;w
k
);k = 1;:::; 2log
2
n; where
a
0;1
    a
0;n
denotes the actual plaintext block.
The last statea
2log2n;1
    a
2log2n;n
will be the generated
ciphertext block of the plaintext blocka
1
    a
n
.
The i-th transition a
i;1
    a
i;n
=
  D
(a
i  1;1
    a
i  1;n
;w
i
) will be performed in the
following way.
Recall that D is a Gluškov product A
D
= A
1
      A
n
( 
n
; (’
1
;:::;’
n
)) of appropriate permutation au-
tomataA
m
= (  ;   2
;  m
);m = 1;:::;n that are state
isomorphic to each other so that for an appropriate bipar-
tite digraphD = (V;E) with the setV
1
of targets andV
2
of sources we have as follows:
  i
(a
k  1;i
;’
i
(a
k  1;1
;    ;a
k  1;n
; (x
1
;:::;x
n
)) =
a
k;i
; where a
k;i
=   i
(a
k  1;i
; (a
k  1;j
  x
j
;x
i
)); if
(j;i) 2 E; and a
k;i
=   i
(a
k  1;i
; (a
k;j
  x
j
;x
i
)); if
(i;j)2E, anda
k;j
=  i
(a
k  1;i
; (a
k  1;j
  x
j
;x
i
));
(1)
where w
m
= x
1
    x
n
2   n
is the actual pseudo ran-
dom string. Obviously, using the transition matrix ofA
i
;
from a
k  1;i
;a
k  1;j
;x
i
;x
j
we can determine a
k;i
for ev-
ery i 2 V
1
; (j;i) 2 E. Moreover, after calculating
the values a
i
(i 2 V
1
), using the transition table ofA
i
,
from a
k  1;j
;a
k;i
;x
i
;x
j
we can determine a
k;j
for every
i2V
2
; (i;j)2E.
Then, concatenating the calculated blocks, we will get
the ciphertext.
The decryption procedure is the following. Similarly as
before, before the decryption procedure the pseudo random
generator gets the ﬁrst ciphertext block as its initialization
vectorr
1
:::r
n
2   n
.
Then the apparatus reads the ciphertext block-by-block
and, after reading the next ciphertext blockc
1
    c
n
2   n
(the ﬁrst block ﬁrst), it generates the second, third and the
further blocks of the plaintext in the following way.
The apparatus determines the state
a
1
    a
n
2   n
of key-automaton
B = ( 
n
; ( 
n
)
2log2n
;  B
) into which the automaton
B is taken from the state a
1
    a
n
2   n
by the effect of
2log
2
n consecutive strings in   n
generated by the pseudo
random generator.
Thus the pseudo random generator should generate
a 2log
2
n -long number of pseudo random sequences
w
1
;:::;w
2log2n
2   n
and going back from the last mem-
berw
2log2n
to the ﬁrst onew
1
the following procedure is
performed.
Each of them takes the next temporal com-
ponent (in opposite direction, i.e., the last one
ﬁrst and the ﬁrst one last) A
D
= ( 
n
;   n
;  D
)
(A
D
2 fA
D1
;:::;A
D
2log
2
n
g) of the key automa-
ton into the state a
k  1;1
    a
k  1;n
back from the
state a
k;1
    a
k;n
=   D
(a
k  1;1
    a
k  1;n
;w
k
);k =
1;:::; 2log
2
n; where a
2log2n;1
    a
2log2n;n
denotes the
actual ciphertext blockc
1
    c
n
.
The last statea
0;1
    a
0;n
will be the generated plaintext
block of the ciphertext blockc
1
    c
n
.
The state a
i  1;1
    a
i  1;n
obtained
from the i-th state transition a
i;1
    a
i;n
=   D
(a
i  1;1
    a
i  1;n
;w
i
) will be performed in the
following way.
Recall again that D is a Gluškov product
A
D
= A
1
     A
n
( 
n
; (’
1
;:::;’
n
)) of appro-
priate permutation automataA
m
= ( 
2
;   ;  m
);m =
1;:::;n that are state isomorphic to each other
so that for an appropriate bipartite digraph
D = (V;E) with the set V
1
of targets and V
2
of
sources, we conclude as in (1).
Recall also that all of A
1
;:::;A
n
are permutation
automata. Therefore, for every a
k;i
;a
k;j
;x
i
;x
j
; j 2
V
2
; (j;i)2 E, there exists only one a
k  1;j
with a
k;j
=
  i
(a
k  1;j
; (a
k;i
  x
i
;x
j
)). Thus, using the transition
table we can unambiguously determine a
k  1;j
for ev-
ery j 2 V
2
. Moreover, for every a
k;i
;a
k  1;j
;x
i
;x
j
;
i2V
1
; (j;i)2E, there exists exactly onea
k  1;i
witha
k;i
=  i
(a
k  1;i
; (a
k  1;j
  x
j
;x
i
)). Therefore, using the tran-
sition table again we can unambiguously determinea
k  1;i
as well for everyi2V
1
.
Then by concatenating the determined plaintext blocks
we will get the plaintext back.
To sum up, the discussed cryptosys-
tem is a block cipher. Because of
Theorem 1, for every ciphertext there exists exactly
one plaintext making the encryption and decryption
unambiguous. Moreover, there is a huge number of
corresponding encoded messages to each plaintext so that
several encryptions of the same plaintext yield several
distinct ciphertexts.
4 Experimental results
The practical test was done using 16 byte (128 bit) long in-
put blocks, output blocks and pseudo random blocks. First
we present the size of the keyspace, then we continue our
investigation with the test results of the the speed of the
algorithm, and ﬁnally the effectiveness of the avalanche ef-
fect.
Using the above mentioned parameters with 256 possi-
ble states (1 byte long states) we need 16 automata having
a transition matrix of 2
16
= 65536 lines and 2
8
= 256
columns. Each cell of the automaton contains 1 byte long
data (One state). The size of the matrix is 16 megabytes
and the number of possible matrices is 256!
65536
, where the
exclamation mark means the factorial operation. This pro-
tection is much more than good enough against brute-force
204 Informatica 43 (2019) 199–207 P. Dömösi et al.
attacks. When we use isomorphic automata this huge num-
ber should be further increased to have 256!
65536
  256!
15
=
256!
65551
possible keys. Using the above mentioned pa-
rameters with half byte (4bits) long states, we need 32 au-
tomata having a transition matrix of 2
8
= 256 lines and
2
4
= 16 columns and each cell of the automaton contains
half byte long data. In this case the size of the matrix is
only 2 kilobytes and the number of possible matrices is
16!
256
. Using permutation automata this can be increased
to 16!
287
possible keys, which is still more than enough
against brute-force attacks. However, we recommend the 8
bit version, because the number of calculations during the
encoding and decoding process is less and the effectiveness
of the avalanche effect is better.
The practical test of the encoding and decoding algo-
rithm was done on an average desktop PC, (3,1 GHz Intel
Core I3-2100 processor, 4 Gigabyte RAM). The program
we used was a well written C# implementation. The results
of the speed tests of the 8 bit version can be seen in Table
1.
The results of the speed tests show that using an average
PC the encoding time is more than 4 megabytes per second,
and decoding time is about the same.
The avalanche effect is a very important property of
block ciphers. The block cipher is said to have avalanche
effect when a small change in the plaintext block results in
a signiﬁcant change in the corresponding ciphertext block,
further, a small change in the ciphertext block results in a
signiﬁcant change in the corresponding plaintext block. We
tested the avalanche effect in the following way. We chose
1000000 random plaintext blocks, encoded them and then
we changed 1 bit in each plaintext block, encoded again,
then we calculated the number of different bytes in the ci-
phertext blocks pair-wise. We also tested the opposite case,
namely, we chose 1000000 random ciphertext blocks, de-
coded them and then we changed 1 bit in each ciphertext
block, decoded again and calculated the number of differ-
ent bytes in each plaintext block pair-wise. During the ﬁrst
test we used just the ﬁrst two rounds of encoding and de-
coding. The results can be seen in Table 2. When we
change only one bit in the plaintext block the difference
between the corresponding ciphertext blocks will be really
huge in the majority of cases. The same effect can be seen
in the opposite case: changing one bit in the ciphertext
block results in a huge difference in the plaintext block as
well. Although it was a good result, we also made a fur-
ther test with the full 4-round algorithm. The results can be
seen in Table 3.
Furthermore, we calculated the optimal avalanche effect.
For this, we chose 2  1000000 completely random blocks
and then calculated the difference between them pair-wise.
The results are in Table 4
We can assume that using the 8-bit version of the algo-
rithm with 128 bit long blocks and 4 rounds the algorithm
has the maximal avalanche effect and an appropriate speed
(4 megabyte/s). Of course the speed of the algorithm de-
pends on the hardware, the programming language and the
actual program code as well.
5 The NIST test
The National Institute of Standards and Technology (NIST)
published a statistical package consisting of 15 statistical
tests that were developed to test the randomness of arbi-
trarily long binary sequences produced by either hardware
or software based cryptographic random or pseudo random
number generators. In case of each statistical test a set of
P-values was produced. Given a signiﬁcance level  , if the
P-value is less than or equal to   then test suggests that
the observed data is inconsistent with our null hypothesis,
i.e. the ’hypothesis of randomness’, so we reject it. We
used  = 0:01 as it is common in such problems in cryp-
tography. An   of 0.01 indicates that one would expect
1 sequence in 100 sequences to be rejected under the null
hypothesis. Hence a P-value exceeding 0.01 would mean
that the sequence would be considered to be random, and
P-value less than or equal to 0:01 would lead to the conclu-
sion that the sequence is non-random.
One of the criteria used to evaluate the AES candidate
algorithms was their demonstrated suitability as random
number generators. That is, the evaluation of their out-
put utilizing statistical tests should not provide any means
by which to distinguish them computationally from a truly
random source. Randomness testing was performed using
the same parameters as for the AES candidates in order
to achieve the most reliable and comparable results. First
the input parameters –such as the sequence length, sample
size, and signiﬁcance level– were ﬁxed. Namely, these pa-
rameters were set at 2
20
bits, 300 binary sequences, and
  = 0:01, respectively. Furthermore, Table 5 shows the
length parameters we used.
In order to analyze the output of the algorithm
we encrypted the Rockyou database, which contains
more than 32 millions of cleartext passwords (see e.g:
[Tihanyi et al., 2015]). Applying the NIST test for the en-
crypted ﬁle it has turned out that the output of the algo-
rithm can not be distinguished in polynomial time from
true random sources by statistical tests. The exact p-values
of the evaluation of the ciphertext are shown in Table (6).
We also tested the uniformity of the distribution of thep-
values obtained by the statistical tests included in NIST,
which is a usual requirement in the literature (see e.g.
[Rukhin et al., 2010]). The uniformity of p-values provide
no additional information about the type of the cryptosys-
tem. We have also shown that the proportions of binary
sequences which passed the 0:01 level lie in the required
conﬁdence interval (see e.g. [Rukhin et al., 2010]).
6 Conclusions
The output of our crypto algorithm has passed all statisti-
cal tests of the NIST suite we performed and we were not
Some Remarks and Tests on the DH1. . . Informatica 43 (2019) 199–207 205
Table 1: Encoding and decoding spped test.
Type of the plaintext Size Encoding time Decoding time Encoded bytes per second
Image:JPG 205216 00:00.0470960 00:00.0456500 4357397.6558519
Document:PDF 204768 00:00.0459240 00:00.0454752 4458845.0483407
Text:TXT 204848 00:00.0467470 00:00.0461294 4382056.6025627
Compressed:RAR 204848 00:00.0471470 00:00.0454830 4344878.7833796
Compressed:RAR 104883392 00:25.9539778 00:27.2784568 4041129.7569962
Compressed:RAR 524613552 02:10.6843636 02:08.6140492 4014355.9454882
Compressed:RAR 1102971104 04:28.121944 04:08.2624464 4442762.5683785
Table 2: Character differences after 2 rounds of encoding.
different characters in one block encoding decoding
0 0 0
1 0 0
2 1 1
3 0 0
4 36 40
5 3 1
6 72 89
7 125 136
8 5574 5594
9 11 4
10 179 225
11 410 396
12 11050 11064
13 880 921
14 22670 22397
15 43064 42710
16 915924 916422
Table 3: Character differences after 4 rounds of encoding.
different characters in one block encoding decoding
0-12 0 0
13 37 28
14 1717 1746
15 59403 59145
16 938842 939081
Table 4: Optimal avalanche effect.
different characters in one block
0-12 0
13 32
14 1693
15 58681
16 939594
206 Informatica 43 (2019) 199–207 P. Dömösi et al.
Table 5: Parameters used for NIST Test Suite.
Test Name Block length
Block Frequency 128
Non-overlapping Template 9
Overlapping Template 9
Approximate Entropy 10
Serial 16
Linear Complexity 500
able to distinguish it from true random sources by sta-
tistical methods. Statistical analyses of a cryptosystem is a
must-have requirement, and these test results are good in-
dicators that further analyses can and should be done in or-
der to check further properties. Cryptanalysis methods like
chosen-plaintext, known-plaintext and related-key attack
techniques will be used to prove or disprove the strength
of the cryptosystem. These problems are the subject of our
future research.
Many information systems such as computers and com-
puter networks may be simulated by means of a queue-
ing system. In general, queueing systems model is de-
veloped assuming the arrival rate and service intensity to
be in the equilibrium state. The well-known methods of
the queueing system investigation are based on the station-
ary behaviour of the input ﬂow and service duration. Tak-
ing into account these characteristics as well as technical-
economical criteria, the optimal system performance pa-
rameters are determined.
In real conditions the input ﬂow arrival rate is affected by
the step-by-step inﬂuence and the system state can essen-
tially differ from the desired one. Here we come across the
problem of compensating these differences with the pur-
pose of equalizing the real value of output of customers’
ﬂow to the desirable one.
The main idea of this work lies in the identiﬁcation of
the queueing system as the control object with further con-
struction of discrete control closed scheme.
7 Acknowledgments
This work was supported by the National Research, Devel-
opment and Innovation Ofﬁce of Hungary under Grant No.
TÉT 16-1-2016-0193.
References
[Dömösi and Horváth, 2015a] Dömösi, P. and Horváth, G.
(2015). A novel cryptosystem based on abstract au-
tomata and Latin cubes. Studia Scientiarum Math-
ematicarum Hungarica, 52(2):221–232. https://
doi.org/10.1556/012.2015.52.2.1309
[Dömösi and Horváth, 2015b] Dömösi, P. and Horváth, G.
(2015). A novel cryptosystem based on Gluškov
product of automata. Acta Cybernetica, 22:359–371.
https://doi.org/10.14232/actacyb.
22.2.2015.8
[Dömösi et al., 2017] Dömösi, P., Gáll, J., Horváth, G
and Tihanyi, N. (2017). Statistical Analysis of
DH1 Cryptosystem. Acta Cybrnetica, 23:371–378.
https://doi.org/10.14232/actacyb.
23.1.2017.20
[Dömösi and Nehaniv, 2005] Dömösi, P. and Ne-
haniv,C.L. (2005). Algebraic theory of automata
networks: An introduction. ser. SIAM monographs
on Discrete Mathematics and Applications, vol.
11, Society for Industrial and Applied Math-
ematics (SIAM), Philadelphia, PA. https:
//doi.org/10.1137/1.9780898718492
[Mezenes and Vanstone, 1996] Menezes, P. C. O. A. J.
and Vanstone, S. A. (1996). Handbook of Applied
Cryptography ser. Discrete Mathematics and Its Ap-
plications. CRC Press. https://doi.org/10.
1201/9781439821916
[Rukhin et al., 2010] Rukhin, A., Soto, J., Nechvatal, J.,
Smid, M., Barker, E., Leigh, S., Levenson, M., Van-
gel, M., Banks, D., Heckert, A., Dray, J., V o, S.
(2010). NIST Special Publication 800-22: A Sta-
tistical Test Suite for Random and Pseudo Ran-
dom Number Generators for Cryptographic Applica-
tions. National Institute of Standards and Technology,
https://nvlpubs.nist.gov/nistpubs/legacy/sp/
nistspecialpublication800-22r1a.pdf, downloaded in
August 2016. https://doi.org/10.6028/
nist.sp.800-22
[Tihanyi et al., 2015] Tihanyi, N., Kovács, A., Vargha, G.,
Lénárt, Á. Unrevealed Patterns in Password
Databases Part One: Analyses of Cleartext Pass-
words. Technology and Practice of Passwords.
PASSWORDS 2014. Lecture Notes in Computer
Science, vol 9393. https://doi.org/10.
1007/978-3-319-24192-0_6
Some Remarks and Tests on the DH1. . . Informatica 43 (2019) 199–207 207
Table 6: Results for the uniformity of p-values and the proportion of passing sequences.
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-value PRO- STATISTICAL TEST
PORTION
28 35 23 33 43 34 32 23 26 23 0:162606 296=300 Frequency
25 29 35 38 27 23 26 27 31 39 0:407091 298=300 BlockFrequency
28 37 26 37 32 28 25 36 25 26 0:574903 297=300 CumulativeSums
26 30 31 30 33 27 24 38 28 33 0:840081 295=300 CumulativeSums
33 20 33 26 32 28 44 25 30 29 0:205897 297=300 Runs
23 33 40 24 31 22 31 29 38 29 0:284959 297=300 LongestRun
24 28 40 32 24 30 30 27 37 28 0:527442 297=300 Rank
34 35 23 33 30 35 27 34 23 26 0:623240 298=300 FFT
35 31 30 29 30 29 32 28 23 33 0:958773 295=300 NonOverlapping  Template
: : : : : : : : : : : : :
                                                    25 27 25 29 40 39 29 33 26 27 0:419021 299=300 OverlappingTemplate
32 29 21 20 29 37 34 28 30 40 0:220931 298=300 Universal
35 33 28 34 26 26 27 30 33 28 0:935716 299=300 ApproximateEntropy
21 17 24 23 15 15 18 12 15 17 0:516465 171=177 RandomExcursions
: : : : : : : : : : : : :
                                                    23 16 15 16 14 26 12 18 18 19 0:384836 172=177 RandomExcursions  Variant
: : : : : : : : : : : : :
                                                    23 27 38 25 27 43 41 24 24 28 0:042808 298=300 Serial
28 28 25 24 45 32 32 33 28 25 0:253551 296=300 Serial
32 25 33 34 40 20 31 35 15 35 0:039244 295=300 LinearComplexity
208 Informatica 43 (2019) 199–207 P. Dömösi et al.