The generation of nonlinear substitutions (S-boxes) is an important task in the design of modern symmetric cryptoalgorithms. (nonlinearity, balance, delta-uniformity, correlation and algebraic immunity, etc.) characterize their resistance to linear, differential, algebraic and other cryptanalysis methods. This article explores a computational particle swarm optimization (PSO) method as applied to the problem of generating nonlinear substitutions. Having a set of possible solutions (particles) and moving these particles in the search space, the PSO tries to improve the possible solution in terms of some quality indicator. We use nonlinearity, balance, delta uniformity, algebraic immunity and linear redundancy as the main indicators, and randomly generated S-boxes are used as a set of particles. This article shows several PSO modifications for generating nonlinear substitutions. At first, we reproduce the previously known PSO modification for generating S-boxes and show its low efficiency. At second, we propose our own PSO implementation and show that this method can actually generate substitutions with high cryptographic properties. The experimental results allow us to establish the influence of the size of the population of particles and the number of iterations of the outer loop on the efficiency of the heuristic generation of nonlinear substitutions. In addition, we explore the similarity of the generated substitution tables with the AES cipher S-box. Nonlinear substitutions, s-boxes, particle swarm optimization, computational search.
and other properties characterize resistance of
S-boxes to linear, differential, algebraic and other
cryptanalysis methods. Therefore, the problem of generating substitutions with the required properties
is an important and urgent scientific problem [
Various methods are used to generate cryptographically strong substitutions, see for example
[
2022 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Particle swarm optimization - heuristic method of global optimization, which is implemented on the basis of populations, which is proposed in [14]. PSO is based on "swarm" intelligence, which is a natural behavior of birds, fishes, insects and others. Swarm particles either fly away or fly together in search of food before they find a good place, where the food is located. While searching for food, there is always one bird that feels and seeks food better than others, so such bird is more likely to find a place where food can be found, which means that it will have better information about the source of food than others. Since birds constantly share such "good" information in the search process, the flock will eventually move to a "better" place where food is more likely to be found. In PSO, the movement of "birds" begins from one location to another, equivalent to a flock, good information is equivalent to the most optimistic solution, and the expected food is equivalent to the most optimistic solution for the entire operation of the algorithm.
This method helps to find the most optimistic solution due to the cooperation of each element of the population, the “bird.” Quite complex optimization problems can be solved using PSO algorithm. The advantages allow it to be applied to many areas of optimization alone and in combination with other existing algorithms. The algorithm is used in such areas as neural network training, optimization of certain functions, machine learning, signal processing, etc., [15–18].
In the basic PSO algorithm, the population consists of «N» particles, and the location of each of the particles corresponds to a potential solution in d -dimensional space. The position of each particle in the swarm is influenced by both the most optimistic position during its movement (individual experience, called personal best - pBest of the particle), and the position of the most optimal particle in its vicinity (experience that is called the best of all - gBest ).
Flock particles fly into search space due to their exploration and exploitation capabilities and use pBest and gBest , to find the best solution in PSO. In addition, each particle is characterized by velocity. The velocity and position of each particle are reviewed after each subsequent iteration of the algorithm.
The velocity and position of each particle are determined at each step as: vk 1 vikd c1r1( pBestikd xikd ) c2r2 (gBestikd xikd ) id xk1 xikd vikd1 id (1) (2) where: vikd and xikd is velocity and position of the particle « i » at its « k » times and the d-dimension quantity of its position; pBestikd is d -dimension quantity of the individual « i » element at its most optimist position;
gBestikd is d -dimension quantity of the most optimistic position of the whole «swarm»;
parameters c1, c2 , r1, r2 are randomly generated within [
In abstract [12] proposed interpretation of PSO for the generation of highly nonlinear S-boxes that implement bijective mappings S :{0,1}8 {0,1}8 . Although, the authors of this research made mistakes in calculating the nonlinearity of S-boxes (in particular, see our commentary [13]), we reproduced their proposed algorithm for computational search of nonlinear substitutions and made our own researches of the efficiency of PSO. 2.1.
According to the description from [12] the generation of S-boxes occurs using the following algorithm.
1. Population initialization
For S-box optimization problem, each individual 8 8 S-box is considered as the particle. The Sbox population is generated randomly so that the S-Boxes remain bijective. Generation is repeated until the N -sized population is filled.
Next, nonlinearity is calculated for each block. According to this nonlinearity, the population of blocks is sorted (in descending order of nonlinearity).
3. PSO vector initialization
The velocity vector is filled with zeros and updated at each successful iteration. Each position vector is initialized using the appropriate S-Box in the population. The velocity vector is updated by formula (1), and the location vector is updated by formula (2). The vector of the most optimistic positions during the iteration ( pBest ) is updated for each generated population if the nonlinearity values of the new blocks are better than the previous ones. The most optimal of all is the particle with the highest nonlinearity in the population.
4. Initialization of PSO parameters
PSO parameters, such as c1 , c2 , r1 and r2 are randomly selected using a Renyi map. During the optimization phase of the algorithm, these parameters randomly change at each iteration. Another parameter is the coefficient of inertia (inertial weight), which is given by the formula: wcurIter w1 (curIter 1)( mwa2хItwe1r ) (3) where w1 and w2 is the initial and final value of the coefficient, respectively.
The velocity and location vectors are updated according to the laws in formulas (1) and (2) respectively. The process of such improvement generates certain values that are repeated or negative. To prevent this, the authors use certain processing methods, replacing repeated values with values that are lacking to preserve the bijectivity. An algorithm for such improvements is not provided in [12]. 6. The final step of the iteration
Next, the nonlinearity value is also calculated for all newly generated blocks, and all S-Boxes, including those already in the population, are sorted again in descending of nonlinearity. N best blocks according to the nonlinearity remain in the population, all other blocks are discarding. Vectors pBest and gBest are updated as above.
The pseudocode of the algorithm presented in the article [12], is shown in Fig. 1.
In [13] we showed that the calculation of the nonlinearity of S-Boxes in [12] was incorrect. According to Fig. 1 nonlinearity is chosen as the main target of optimization. Therefore, the effectiveness of the use of PSO to generate substitutions can’t be established by publication [12].
In this article, we reproduced the algorithm shown in Fig. 1 and made some experimental researches with correct calculation of nonlinearity. Unfortunately, we were unable to form a single S-Box with a nonlinearity greater than 98, even after numerous experiments. This is a very poor result, which indicates an unsuccessful PSO interpretation. But this does not mean that the PSO method cannot be efficiency applied in another interpretation. 2.2.
In this work, we propose a new implementation of PSO. The PSO method modified by us almost completely repeats algorithm from [12]. The main difference is in the first iteration of the while loop when forming the first block in the new population, as well as when filling the vectors of the most optimal blocks. Additionally, we estimate other properties of S-Boxes (algebraic immunity, delta uniformity, and linear redundancy).
The essence of the modified algorithm is given below. 1. Population initialization
As in the algorithm discussed earlier, each 8 8 S-box is considered as the particle. The S-box population is generated randomly so that the S-Boxes remain bijective. Generation is repeated until the N -sized population is filled.
2. Calculation of nonlinearity
Next, nonlinearity is calculated for each block. According to this nonlinearity, the population of
blocks is sorted (in descending order of nonlinearity).
__________________________________________________
Input arguments:
N ← number of blocks in the population
max_itr ← maximum number of iterations
xr ← initial value of Renyi chaotic map
c ← parameter of Renyi map
__________________________________________________
Generation of the initial population of S-boxes:
xr ← renyi_map(xr, c, 100)
population ← zeros(2 × N, 256) // 256 for 8 × 8 S-boxes
for i ← 1 to N
[sboxi, xr] ← gen_sbox(xr, c)
population[i] ← sboxi
end for
population[
Vel[i][j] ←
ceil(w∗Vel[i][j] + c1∗r1∗(pBest[i][j] - population[i][j]) + c2∗r2∗(gBest[j]-population[i][j])) if (Vel[i][j] < 0)
Vel[i][j] ← (Vel[i][j] + 256)mod(256)
The velocity vector is filled with zeros and updated at each successful iteration. Each position vector is initialized using the appropriate S-Box in the population. The velocity vector is updated by formula (1), and the location vector is updated by formula (2). The difference in our algorithm is that when forming a new population, the first block of the new population is formed due to the interaction of the first block of the initial population with itself and changing a small number of values. This gives an almost zero velocity vector on the first iteration, which allows to gradually deteriorate on subsequent iterations. In subsequent iterations, if after applying this method the nonlinearity of S-box is higher than 98, the block is further mixed randomly to improve other parameters such as linear redundancy, delta uniformity and algebraic immunity.
This is done in order to reach a compromise, so that there are no situations where one parameter is very good and the others are bad. It is possible to ensure that all parameters are sufficient and satisfy most conditions using this method.
The vector of the most optimistic positions during the iteration ( pBest ) is updated for each generated population if the nonlinearity values of the new blocks are better than the previous ones.
The most optimal particle in our method is also updated at each iteration and equated to the best block in the vector of the most optimistic positions pBest .
PSO parameters such as c1 , c2 , r1 and r2 are randomly selected. During the optimization phase of the algorithm, these parameters randomly change at each iteration. Inertial weight is also (3). 5. Improvement and adjustment
The following algorithm was developed to preserve the objectivity of S-Boxes (Fig. 2). After forming a block, each of its elements is checked for coincidence with another element in this block. If when checking a certain element such an element already exists in this block, then the variable contains becomes 1, and the value is updated by adding a random value to it, and taking it by modulo 256. This is repeated as long as only unique values from 0 to 255 remain in the S-Box. The pseudocode of the algorithm is given below.
__________________________________________________ for (int i = 0; i < N; ++i) for (int j = 0; j < size;)
Updating values by (1) and (2) int contains; if (contains == 0)
tempSbox[j] = X; end if else
tempSbox[j] = myModulusDec((tempSbox[j] + rand()), 256); end else; contains = 0; for (int k = 0; k < j; ++k) if (tempSbox[k] == tempSbox[j]) contains = 1; break; end if end for if (!contains)
j++; end if end for ...... end for __________________________________________________ Figure 2: Algorithm for preserving the bijectivity of population particles
Next, the nonlinearity value is also calculated for all newly generated blocks, and all S-Boxes, including those already in the population, are sorted again in descending of nonlinearity. N best blocks according to the nonlinearity remain in the population, all other blocks are discarding. Vectors pBest and gBest are updated as above.
The pseudocode of the modified algorithm is shown in Fig. 3.
Our proposed new modification of PSO allows to form S-boxes with nonlinearity 104, delta uniformity 8, linear redundancy 0 and algebraic immunity 3 in a relatively short time. As an example, we give one of the following S-boxes (8-bit output vectors are given in decimal format): {99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 180, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 29, 146, 52, 165, 229, 241, 113, 216, 49, 88, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 51, 207, 208, 239, 170, 251, 67, 77, 166, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 221, 28, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 187, 232, 72, 198, 85, 247, 116, 31, 191, 189, 139, 138, 112, 62, 181, 102, 204, 3, 75, 17, 97, 53, 87, 185, 134, 193, 148, 158, 225, 248, 152, 223, 105, 217, 142, 176, 155, 30, 135, 233, 206, 40, 45, 22, 140, 161, 137, 13, 153, 230, 66, 104, 65, 246, 15, 21, 84, 157, 14, 118}
The next step in our research was examination of the effect of particle population size and the number of iterations of the external cycle on the efficiency of heuristic generation of nonlinear substitutions.
__________________________________________________ Input arguments: N ← number of blocks in the population max_itr ← maximum number of iterations mode ← mode (0 – algorithm from [12], 1 – modified algorithm) __________________________________________________ Generation of the initial population of S-boxes: srand(time(NULL)); int flag = rand()%size; population ← zeros(2 × N, 256) // 256 for 8 × 8 S-boxes for i ← 1 to N [sboxi, xr] ← gen_sbox(i+flag)
Generation occurs using rand () and Fisher-Yates mixing
population[i] ← sboxi
end for
population[
NL[i] ← nonlinearity(population[i])
end for
NL_sorted ← sort(NL) // sorting in descending order
gBest ← population[
Using (3) for w
c1 ← 2∗rand() [
Vel[i][j] ← ceil(w∗Vel[i][j] + c1∗r1∗(gBest[i][j] - population[i][j]) + c2∗r2∗(gBest[j]-population[i][j])) end if if (mode == 0)
Vel[i][j] ← ceil(w∗Vel[i][j] + c1∗r1∗(pBest[i][j] - population[i][j]) + c2∗r2∗(gBest[j]-population[i][j])) end if if (Vel[i][j] < 0)
Vel[i][j] ← (Vel[i][j] + 256)mod(256)
A new modification of PSO was examined in detail during the experiments. The results of test runs to search for blocks with the required parameters are given in Tables 1-13.
Nd, % – – – – – – – – 0.8828 – – – 0.8828
– 0.8710 – – – – 0.8789 Nd, % – – – – – – – 0.8671 – – – – – – – – – – – 0.8750
M not found not found not found not found
16 not found not found
45 not found not found not found not found not found not found not found not found not found 60 12 122
Nd, % – – – – 0.8632 – – 0.8710 – – – – – – – – – 0.8750 0.8710 0.8789 Nd, % – – – 0.8593 – – – – – – – – – – – – – – – –
Nd, % – – – – – – – 0.8828 – – – – – – – – 0.8750 – – 0.8789 Nd, %
– 0.8710 – – – – – 0.8828
– 0.8789 – – – – – – – – – 0.8789 The Tables 1-13 indicate: N is number of blocks in the population. MaxIter is specified number of iterations. M is number of iterations to find the required block (or not found). T is work time. Nd is the number of positions differs from AES. Nd, % is coefficient of similarity (in percent) with AES S-Box.
Below is a summary of the information presented in the form of a histogram (see Fig. 4).
In Fig. 4 on the x -axis indicates the number of iterations, on the y -axis is the number of blocks in the population, on z - the number of blocks (with the required parameters) found (as required set: nonlinearity = 104, algebraic immunity = 3, linear redundancy = 0). As you can see, the larger N and MaxIter , the more blocks found.
Additionally, the last two columns in Tables 1-13 should be commented on. These columns contain
parameters of difference (absolute and relative) from the values of the algebraic S-box of the AES
cipher [19,20]. This S-box is used as the initial filling of one of the particles of the swarm (see the line
«population[
As you can see, the generated substitution tables are very similar to the AES cipher S-box (almost 90% similarity). S-boxes generated by the algorithm from [21] are also close by this property. Therefore, it is promising to compare these two generation algorithms for the efficiency of computational search.
This work was supported in part by the National Research Foundation of Ukraine under Grant 2020.01/0351.
[11]L.D. Burnett, Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography, phd, Queensland University of Technology, 2005. https://eprints.qut.edu.au/16023/ (accessed May 19, 2021). [12]M. Ahmad, I.A. Khaja, A. Baz, H. Alhakami, W. Alhakami, Particle Swarm Optimization Based Highly Nonlinear Substitution-Boxes Generation for Security Applications, IEEE Access. 8 (2020) 116132–116147. https://doi.org/10.1109/ACCESS.2020.3004449. [13]A. Kuznetsov, K. Kuznetsova, Comment on “Particle Swarm Optimization Based Highly Nonlinear Substitution-Boxes Generation for Security Applications,” in: 2021 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), Cracow, Poland, September 22-25. http://www.idaacs.net (accessed October 15, 2021). [14]J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings of ICNN’95 - International Conference on Neural Networks, 1995: pp. 1942–1948 vol.4. https://doi.org/10.1109/ICNN.1995.488968. [15]M.E.H. Pedersen, A.J. Chipperfield, Simplifying Particle Swarm Optimization, Applied Soft
Computing. 10 (2010) 618–628. https://doi.org/10.1016/j.asoc.2009.08.029. [16]Y. Xiaojing, J. Qingju, L. Xinke, Center Particle Swarm Optimization Algorithm, in: 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), 2019: pp. 2084–2087. https://doi.org/10.1109/ITNEC.2019.8729510. [17]Z. Yimin, S. Guojun, Y. Xiaoguang, Cloud service selection optimization method based on parallel discrete particle swarm optimization, in: 2018 Chinese Control And Decision Conference (CCDC), 2018: pp. 2103–2107. https://doi.org/10.1109/CCDC.2018.8407473. [18]M.E.H. Pedersen, Tuning & simplifying heuristical optimization, phd, University of
Southampton, 2010. https://eprints.soton.ac.uk/342792/ (accessed August 5, 2021). [19]J. Daemen, V. Rijmen, Rijndael/AES, in: H.C.A. van Tilborg (Ed.), Encyclopedia of Cryptography and Security, Springer US, Boston, MA, 2005: pp. 520–524. https://doi.org/10.1007/0-387-234837_358. [20]J. Daemen, V. Rijmen, Specification of Rijndael, in: J. Daemen, V. Rijmen (Eds.), The Design of Rijndael: The Advanced Encryption Standard (AES), Springer, Berlin, Heidelberg, 2020: pp. 31– 51. https://doi.org/10.1007/978-3-662-60769-5_3. [21]O. Kazymyrov, V. Kazymyrova, R. Oliynykov, A Method For Generation Of High-Nonlinear SBoxes Based On Gradient Descent, 2013. https://eprint.iacr.org/2013/578 (accessed August 16, 2020).