Geodesic
S-boxes algorithmic realization based on modified additive generators
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 102-104.

Voir la notice de l'article provenant de la source Math-Net.Ru

$S$-boxes give the properties of non-linearity and diffusion to cryptosystems and are essential parts of symmetric iterative block ciphers. Usually, they are described as vector Boolean functions and are represented by a memory-consuming tables limiting the practical size of them ($6\times4$ bits in DES cypher, $4\times4$ bits in GOST cypher, $8\times8$ bits in Kuznyechik cypher). In this paper, we present an algorithm for constructing $s$-boxes (including large ones) using modified additive generators (MAG). The required cryptographic properties of the created substitutions follow from algebraic and mixing properties of MAG and are determined in experiments with a software implementation of the algorithm. Each created substitution $s$ on $V_n$ is tested to determine whether it has the following desirable properties: 1) essential dependence of coordinate functions of $s$ on all their variables; 2) non-linearity of all the non-zero combinations of the coordinate functions of $s$; 3) nearness of the difference characteristics $p_s$ to a random value, where $p_s=\max_{\alpha,\beta\in V_8}|\{x\in V_8\colon s(x)\oplus s(x\oplus\alpha)=\beta\}|$. As a result of the research, $2^{19}$ $s$-boxes $8\times8$ were created using MAG with several selected $s$-boxes $4\times4$. Almost all of them satisfy requirements 1 and 2. For a large number (several thousands) of constructed $s$-boxes $8\times8$, $p_s=10/256$, and four $s$-boxes have $p_s=8/256$. The results show that the presented method is capable of constructing large and cryptographically strong $s$-boxes.
Keywords: modified additive generator, s-box, shift register.
Mots-clés : MAG 
@article{PDMA_2017_10_a40,
     author = {V. M. Fomichev and D. M. Lolich and A. V. Yuzbashev},
     title = {S-boxes algorithmic realization based on modified additive generators},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {102--104},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a40/}
}
TY  - JOUR
AU  - V. M. Fomichev
AU  - D. M. Lolich
AU  - A. V. Yuzbashev
TI  - S-boxes algorithmic realization based on modified additive generators
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 102
EP  - 104
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a40/
LA  - ru
ID  - PDMA_2017_10_a40
ER  - 
%0 Journal Article
%A V. M. Fomichev
%A D. M. Lolich
%A A. V. Yuzbashev
%T S-boxes algorithmic realization based on modified additive generators
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 102-104
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a40/
%G ru
%F PDMA_2017_10_a40
V. M. Fomichev; D. M. Lolich; A. V. Yuzbashev. S-boxes algorithmic realization based on modified additive generators. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 102-104. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a40/

[1] Koreneva A. M., Fomichev V. M., “Peremeshivayuschie svoistva modifitsirovannykh additivnykh generatorov”, Diskret. analiz i issled. operatsii, 24:2 (2017), 32–52

[2] Rekomendatsii po standartizatsii, Zadanie uzlov zameny bloka podstanovki algoritma shifrovaniya GOST 28147-89, M., 2013

[3] Anderson R., Biham E., Knudsen L. R., Serpent: A Proposal for the Advanced Encryption Standard, NIST AES Proposal, 1998

[4] Fomichev V. M., Kyazhin S. N., “Lokalnaya primitivnost matrits i grafov”, Diskret. analiz i issled. operatsii, 24:1 (2017), 97–119 | MR | Zbl

[5] Menyachikhin A., “Spectral-linear and spectral-difference methods for generating cryptographically strong S-boxes”, CTCrypt Preproceedings, Yaroslavl, 2016, 232–252