-One of the standard cryptographic transformations is the addition modulo two of an open binary text with a key binary sequence. In this paper, we have obtained a description of all Boolean functions from n arguments that are suitable for use in cryptographic transformations instead of the modulo-two addition function (we will call them component-by-component Boolean functions). An example of their use in the cryptographic conversion algorithm GOST R 34.12-2015 is also given. The article proposes an algorithm for generating component-bycomponent Boolean functions from n variables for different values of n and k, where k is the number of the variable whose value the function returns. For the case n=3 and k=1 or k=2, all Boolean functions that replace the addition function modulo 2 are represented. The paper proposes an encryption method based on component-by-component Boolean functions and a pseudo-random sequence generator of elements from the GF(2n-1) field. Using Boolean functions that return the value of one of the arguments when repeated, expands the variety of intermediate variants of round transformations, gives a new variable encryption method, ultimately significantly increasing the cryptographic strength of the cipher.
properties of Boolean functions, as well as the possibilities of their use in order to protect information. These issues are discussed both in scientific articles and in a number of textbooks for Universities, for example, [1, 2]. For the most complete overview of the cryptographic properties of
is a continuation of work [4], in which the authors proposed
various symmetric encryption algorithms is bitwise addition modulo two of a plaintext represented in binary form with a key binary sequence. For example, GOST R 34.12-2015 [6] is a symmetric cipher in which the beginning of the transformation sequence is the transformation X[k]:
X[k](a) = k ⊕ a, (
D X[k](a) = (k ⊕ a) ⊕ k = a. (
(
. . .
S(а) and L(а) 128-bit open data block D(a)
Nine rounds of cryptogra
phic transforma tions 128-bit encrypted text block cipEh(ear)text
F
k1 . . . kn k2 . .
. kn+1 k9 . .
. kn+ 8 k10 . . .
kn+9 F . . .
F F Fig. 1. Modification of the encryption algorithm from GOST R 34.122015 using component-wise functions.
Earlier in [4], we proposed 10 Boolean functions of three
variables to replace addition modulo 2. We introduced the
term component-wise functions for them. In general case, a
Boolean function of n variables, which returns the value of
the first argument, must satisfy the condition:
( ( 1, 2, … , ), 2, … , ) = 1. (
Modern studies of the GOST R 34.12-2015 cipher are presented in [7- 9] and others. They are mainly devoted to the study of the cryptographic strength of this encryption standard, as well as various options for its software implementation. This article describes all Boolean functions of n arguments that are suitable for use in symmetric cryptographic transformations instead of the modulo two addition function. We proposed an algorithm for their generation, an encryption method based on component-wise Boolean functions and a generator of a pseudo-random sequence of elements of the field GF(2n-1).
F(F(0, x2, … , xn), x2, … , xn) = 0
{ , (
variables satisfying condition (
length 2n. Since the second half of the value vector completely depends on the first (inverse to the first), you can set it by specifying the first half of the value vector in an arbitrary way. It has a length of 2n- 1, and the number of binary vectors of this length is 22 −1.
Let us prove the second statement of the theorem. The values of (0, 2, … , ) are in the first half of the vector ̃, and in the same order in the second half of the vector ̃ ̃ are the values of (1, 2, … , ). From the conditions obtained above, it follows that (0, 2, … , ) = ̅̅(̅̅1̅,̅̅̅̅,̅̅…̅̅,̅̅̅̅̅), that 2 is, the second half of the vector ̃ is inverse to the first.
Example 1. For n=2 we have 222−1=4 Boolean functions that return the first argument. We list their value vectors.
second is completed inversely with the first: 0011, 0110, 1001, 1100.
We got the following 4 functions: F(x, y)= x, F(x, y)= x+y, F(x, y)= xy and F(x, y)= ̅.
Example 2. For n=3 we have 223−1 =16 Boolean functions that return the first argument. They have value vectors: 00001111, 00011110, 00101101, 00111100, 01001011, 01011010, 01101001, 01111000, 10000111, 10010110, 10100101, 10110100, 11000011, 11010010, 11100001 and 11110000.
functions, we come to conclusions from examples 1 and 2.
each other. The second and penultimate functions are related in a similar way, and so on. Thus, if we are going to use several component-wise functions in the encryption algorithm, we will select them only one from each pair.
It is also obvious that some of the functions obtained
contain dummy variables, which is unacceptable for
cryptographic functions. Applying the algorithm for
determining the fictitiousness of the variables x2, ..., xn to the
selected functions, we obtain all Boolean functions that
satisfy condition (
1 k n, is a Boolean function ( 1, 2, … , ), that does not contain fictitious variables and returns the k-th argument when it is reused, i.e., satisfying the condition:
F(x1, x2, … , xk−1, F(x1, x2, … , xn), xk+1, … , xn) =
= xk (
component-wise functions ( 1, 2, … , ) , that substantially depend on n variables and return the variable xk when reused. The input of the algorithm: n is the number of variables, k is the number of the variable whose value the function returns.
after each part.
works for n=3, k=2.
23-1=4, so we generate all binary vectors of length 4: 0000, 0001, 0010, 0011, ..., 1111.
Let us show that we actually got functions that return the second component. Take, for example, F1(x1, x2, x3), ̃1=(00110110). We show that for arbitrary values x1 and x3 and for x2=a, the function F1 returns the value a.
If we take n=3 and k=1 in the algorithm, the first steps
of the algorithm will be the same as in example 3. In step 4,
we do not split the remaining 10 vectors, since 2k-1=20=1.
Add the inverse part to them and get the vectors of the
values of (
All component-wise (n, k) functions are balanced, that is, they take the values 0 and 1 equally often. However, they have a different probability of replacing or saving the plaintext character. So, the function from example 3 with the value vector ̃1 =(00110110) changes the value of the plaintext a only in 2 cases out of 8, that is, it has a 25% the probability of replacing the plaintext.
The best characteristics (50% to 50%) of transition probabilities are those Boolean functions that correspond to the balanced vectors that remain after step 3 of the above algorithm.
Example 4. When n=4 of the 256 vectors generated in
step 2, only 220 are checked for the absence of fictive
variables. Of these, 58 vectors are balanced. At n=4, it is
balanced and passes the check for the absence of fictive
variables, for example, the vector 11010100. This means
that (
Let r be a non-negative number less than . A Boolean function from n variables is called r-stable if any of its subfunctions obtained by fixing at most r variables are balanced.
Theorem 2. For any component-wise (n,k) function ( 1, 2, … , ) the following conditions are equivalent: ( 1, 2, … , ) has transition probabilities 50%; ( 1, 2, … , −1, 0, +1, … , ) is balanced; ( 1, 2, … , ) is 1-stable.
We prove 12. The length of the vector of values of the
function ( 1, 2, … , −1, 0, +1, … , ) is 2 −1 . Let the
vector of values of the function
( 1, 2, … , −1, 0, +1, … , ) have t units. It is necessary
to prove that = 2 −2 , i.e., that the number of units is
exactly half the length of the vector. Since (
Now we consider the function (0, 2, … , −1, , +1, … , ). It can be divided into two subfunctions: (0, 2, … , −1, 0, +1, … , ) and (0, 2, … , −1, 1, +1, … , ) , and the second will be inverse to the first. Therefore, the combined vector (0, 2, … , −1, , +1, … , ) has an equal number of zeros and ones. It is proved in a similar way that the vector of values of the function (1, 2, … , −1, , +1, … , ) is balanced. For the same reason, the vectors of subfunction values are balanced, which are obtained by fixing one of the variables 2, … , −1, +1, … , . Therefore, ( 1, 2, … , ) is 1-stable.
We prove 31. It follows from the condition that the function ( 1, 2, … , −1, 0, +1, … , ) is balanced, that is, takes 2 −2 times the value 1 and 2 −2 times the value 0. In addition, the function ( 1, 2, … , −1, 1, +1, … , ) is balanced, that is, takes 2 −2 times the value 1 and 2 −2 times the value 0. Then the number of substitutions is 2 −1, which means the probability of transitions is 50%. The theorem is proved.
FUNCTIONS
One of the encryption options using (
Let ( 1, 2, … , ) – be a component-wise (n,1) function, a –be binary plaintext, K be the key SRP of the elements of the field GF(2n-1). Then the encryption of the text a is performed elementwise according to the formula:
E(a)= ( , ). (
To decrypt, we use the same function ( 1, 2, … , ) and the key sequence K:
D(E(a))= ( ( , ), )=a. (
The organization of calculations largely depends on the representation of the elements of the field GF (2n- 1), therefore, we will consider this question in more detail. Operations on elements of a finite field GF (2m) are easily performed when they form an index table, where mdimensional binary vectors are associated with the powers of a primitive element. Such a representation is also convenient when dividing field elements into circular classes, used, for example, to find primitive polynomials or in algorithms for obtaining the number of noise-resistant codes [11].
Consider the algorithm for constructing the index table
of the field GF(2m), where m≤30. Input data: m is the degree
of expansion, f(x) is the primitive polynomial of degree m
over GF(
To optimize the speed of calculations, we will store each vector of coefficients in a 32-bit integer data type. At the position of the i-th bit in the binary notation of the number, the i-th coefficient of the vector will be stored. Due to this, the multiplication of the vector by will be carried out by a bitwise left shift. The search for the remainder of division by the primitive polynomial f(x) will be expressed through the operation of bitwise addition modulo 2. Thus, the storage of the index table GF(2m) requires about 4 ∙ 2m bytes of memory.
Note that the calculation of each subsequent coefficient vector is performed sequentially. Thus, lines 0, 1, 2, …, 2m3, 2m-2. are filled. In order to calculate the table using parallel technologies, we break all the rows into k consecutive blocks. To calculate the j-th block, you need to calculate the coefficient vector that is the first in this block. For this, there is no need to find all previous vectors. We use the binary exponentiation algorithm to significantly speed up the calculations.
We tested the work of the program for constructing the index table of the GF(2m), where m=26, 27, 28, 29 and 30. The calculations were performed on 4 cores on an NArFU cluster with 20 computing nodes, each of which had 2 10core Intel Xeon processors and 64 GB of RAM. The table contains data on the operating time for various m and for a different number of threads.
EXECUTION TIME OF SERIAL AND PARALLEL ALGORITHMS
(IN SECONDS)
Threads \ m Sequential algorithm 1 thread 2 threads 3 threads 4 threads 26 0.507 0.535 0.311 0.242 27 0.205 0.403 0.794 1.597 3.283
From the presented table we can conclude that the program shows an acceleration of about 2,5 times with parallel implementation of 4 threads.
Component-wise (n, k) functions extend the modes of standard cryptographic transformations, in particular, GOST R 34.12-2015. Using them instead of the modulo 2 addition operation increases the possibilities of choosing round transformations for symmetric ciphers. But a significant disadvantage of the functions under consideration is a large redundancy. We believe that consideration of K- digit component-wise functions will help overcome this disadvantage. Further research will be aimed at introducing the encryption method using component-wise functions in the hardware-software complex.