Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 215-226
Volume 24, No 2, 2017, P. 32-52
UDC 519.17
A. M. Koreneva and V. M. Fomichev
The mixing properties of modified additive generators
Abstract:
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 di?graph, primitive digraph, shift register, exponent of digraph.
DOI: 10.17377/daio.2017.24.528
Alisa M. Koreneva 1
Vladimir M. Fomichev 1,2,3
1. National Research Nuclear University MEPhI,
31 Kashirskoe Highway, 115409 Moscow, Russia
2.
Financial University under the Government of the Russian Federation,
49 Leningradsky Ave., 125993 Moscow, Russia
3. Institute of Problems of Informatics (Russian Academy of Sciences),
44-2 Vavilova St., 119333 Moscow, Russia
e-mail: alisa.koreneva@gmail.com, fomichev@nm.ru
Received 19 February 2016
Revised 25 July 2016
References
[1] A. M. Dorokhova and 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, 2014 [Russian].[2] K. G. Kogos and V. M. Fomichev, Positive properties of nonnegative matrices, Prikl. Diskretn. Mat., No. 4, 5–13, 2012 [Russian].
[3] A. M. Koreneva and V. M. Fomichev, On a Feistel block cipher generalization, Prikl. Diskretn. Mat., No. 3, 34–40, 2012 [Russian].
[4] S. N. Kyazhin and V. M. Fomichev, Local primitiveness of graphs and nonnegative matrices, Prikl. Diskretn. Mat., No. 3, 68–80, 2014 [Russian].
[5] V. N. Sachkov and V. E. Tarakanov, Kombinatorika neotritsatel’nykh matrits, TVP, Moscow, 2000 [Russian]. Translated under the title Combinatorics of nonnegative matrices, AMS, Providence, 2002 (Transl. Math. Monogr., Vol. 213).
[6] V. M. Fomichev, Metody diskretnoi matematiki v kriptologii (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., No. 1, 118–124, 2010 [Russian].
[8] V. M. Fomichev, The estimates for exponents of primitive graphs, Prikl. Diskretn. Mat., No. 2, 101–112, 2011 [Russian].
[9] V. M. Fomichev, Estimates for exponent of some graphs by means of Frobenius’s numbers of three arguments, Prikladn. Diskretn. Matem., 24, No. 2, 88–96, 2014 [Russian].
[10] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, Wiley, New York, 1996. Translated under the title Prikladnaya kriptografiya: Protokoly, algoritmy, iskhodnye teksty na yazyke Si, Triumf, Moscow, 2002 [Russian].
[11] B. M. Kim, B. C. Song, and W. Hwang, Nonnegative primitive matrices with exponent 2, Linear Algebra Appl., 407, 162–168, 2005.
[12] B. L. Shader and S. Suwilo, Exponents of nonnegative matrix pairs, Linear Algebra Appl., 363, 275–293, 2003.
[13] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z., 52, 642–648, 1950 [German].
