Geodesic
The mixing properties of modified additive generators
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 32-52.

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

We develop a matrix-graph approach to estimating the mixing properties of bijective shift registers over a set of binary vectors. Such shift registers generalize, on the one hand, the class of ciphers based on the Feistel network and, on the other hand, the class of transformations of additive generators (the additive generators are the base for the Fish, Pike, and Mush algorithms). It is worth noting that the original schemes of additive generators are found insecure due to their weak mixing properties. The article contains the results of investigations for the mixing properties of modified additive generators. For the mixing directed graph of a modified additive generator, we define the sets of arcs and cycles, obtain primitivity conditions, and give a bound for the exponent. We show that the determination of parameters for the modified additive generator allows us to achieve a full mixing in a number of iterations that is substantially less than the number of vertices in the mixing digraph. Tab. 1, illustr. 1, bibliogr. 13.
Keywords: additive generator, modified additive generator, mixing digraph, primitive digraph, shift register, exponent of digraph. 
@article{DA_2017_24_2_a2,
     author = {A. M. Koreneva and V. M. Fomichev},
     title = {The mixing properties of modified additive generators},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {32--52},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_2_a2/}
}
TY  - JOUR
AU  - A. M. Koreneva
AU  - V. M. Fomichev
TI  - The mixing properties of modified additive generators
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 32
EP  - 52
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_2_a2/
LA  - ru
ID  - DA_2017_24_2_a2
ER  - 
%0 Journal Article
%A A. M. Koreneva
%A V. M. Fomichev
%T The mixing properties of modified additive generators
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 32-52
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_2_a2/
%G ru
%F DA_2017_24_2_a2
A. M. Koreneva; V. M. Fomichev. The mixing properties of modified additive generators. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 32-52. http://geodesic.mathdoc.fr/item/DA_2017_24_2_a2/

[1] A. M. Dorokhova, V. M. Fomichev, “Revised values of exponents for mixing graphs of bijective shift registers over a set of binary vectors”, Prikl. Diskretn. Mat., no. 1, 77–83 (Russian)

[2] K. G. Kogos, V. M. Fomichev, “Positive properties of nonnegative matrices”, Prikl. Diskretn. Mat., 2012, no. 4, 5–13 (Russian)

[3] A. M. Koreneva, V. M. Fomichev, “On a Feistel block cipher generalization”, Prikl. Diskretn. Mat., 2012, no. 3, 34–40 (Russian)

[4] S. N. Kyazhin, V. M. Fomichev, “Local primitiveness of graphs and nonnegative matrices”, Prikl. Diskretn. Mat., 2014, no. 3, 68–80 (Russian)

[5] V. N. Sachkov, V. E. Tarakanov, Combinatorics of nonnegative matrices, Transl. Math. Monogr., 213, AMS, Providence, 2002 | MR | MR | Zbl

[6] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology, Dialog-MIFI, Moscow, 2010 (Russian)

[7] V. M. Fomichev, “Properties of paths in graphs and multigraphs”, Prikl. Diskretn. Mat., 2010, no. 1, 118–124 (Russian)

[8] V. M. Fomichev, “The estimates for exponents of primitive graphs”, Prikl. Diskretn. Mat., 2011, no. 2, 101–112 (Russian)

[9] V. M. Fomichev, “Estimates for exponent of some graphs by means of Frobenius's numbers of three arguments”, Prikladn. Diskretn. Matem., 24:2 (2014), 88–96 (Russian)

[10] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, Wiley, New York, 1996 | MR | Zbl

[11] Kim B. M., Song B. C., Hwang W., “Nonnegative primitive matrices with exponent 2”, Linear Algebra Appl., 407 (2005), 162–168 | DOI | MR | Zbl

[12] Shader B. L., Suwilo S., “Exponents of nonnegative matrix pairs”, Linear Algebra Appl., 363 (2003), 275–293 | DOI | MR | Zbl

[13] Wielandt H., “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648 | DOI | MR | Zbl