Page 81 - ISCI’2017

1 Random substitution as a model for the cyclic keys formation

Let us consider the definition and basic properties of a random substitution (permutation) [13, 14],

that will be used further to assess the probability properties of round key sequences.
In combinatorics, a permutation is an ordered set of numbers 1,2, ,n , that is a bijection on the

set {1,2, , } n , which puts the i-th elements of the set in correspondence to the i number. The number

n in this case is called the order (degree) of permutation [13, 14].
The substitution s of arbitrary set Y = { ,yy 2 ,..., }y is a rule that each element y of set Y puts
1
n
i
in correspondence some other element ()sy [13, 14]:
i
 y y ... y 
s =  1 2 n  .
( ) sy
( )
 sy 1 ( ) ... sy n 
2
In group theory the substitution is a bijection of this set into itself, i.e. substitution s degrees n is
y
considered as a permutation of the elements of the set Y = { , yy 2 ,..., } and for all i = 1,2,...,n
1
n
corresponding ()sy ∈ .
Y
i
The function ()sy value for a specific element y ∈ Y will be called the implementation of
i
i
substitution s in i-th point.
The composition of substitutions s and s degree n is defined as the consistent fulfillment of
w
u
the set Y elements permutation [13, 14]:

 y y ... y 
ss y
s  s =  1 2 n  , ( ( )) Y∈ .
u
w
( ( )) ss y
( ( ))
w
i
u
 ss y 1 u ( ( )) ... ss y n 
2
u
w
w
w
u
Concerning operations of sequential substitutions execution the set of all !n permutations degree
n forms a group, called the symmetric group and denoted as S = { , ,..., }ss 2 s ! n .
1
n
By definition [13, 14], random substitution (permutation) s is the random vector
x
{ ( ), ( ),..., ( )}s y s y 2 s y n , where all elements take values from the Y set and the probability of a
x
1
x
x
match of any two elements is equal to 0. In other words, a random substitution is randomly chosen
permutation from the set S
n
 y y ... y 
s =  1 2 n  , s ∈ S , x∈ {1,2,..., !}n ,
 x s x ( )y 1 s x ( ) ...y 2 s x ( )y n  x n
defined by a set (vector) of random values { ( ), ( ),..., ( )}s y s y 2 s y n , that match probabilities satisfy
x
x
1
x
the following condition:
j
∀ i ≠ ∈ {1,2,..., }: (n P s x ( )y = s x (y j )) = .
0
i
81