Geodesic
Estimates for exponents of mixing graphs relating to some modifications of additive generators
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 60-64.

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

One of the positive properties of a key generator is a complete mixing of input vector sequence. It means that the all bits in output sequence $\gamma_1\gamma_2\ldots\gamma_i\ldots$ depend on the all bits of the initial state. Complete mixing occurs for bits in the sequence $\gamma_i$ when $i\ge\exp G(\varphi)$, where $\varphi$ is the transformation of internal states of the generator, $G(\varphi)$ is the mixing digraph of transformation $\varphi$ and $\exp G(\varphi)$ is the exponent of digraph $G(\varphi)$. The criterion of complete mixing is the primitiveness of digraph $G(\varphi)$, the necessary condition is the strong connectivity of digraph $G(\varphi)$. This paper is devoted to some modifications of additive generators. Well known algorithms such as Fish, Pike and Mush are based on additive generators. Native schemes of additive generators do not reach complete mixing. In order to achieve the strong connectivity of digraph $G(\varphi)$, the scheme of additive generator is modified by involutive permutation of vectors coordinates. The complete mixing conditions are researched for this modification of additive generator. Some sufficient conditions for primitiveness of mixing graph $G(\varphi)$ and some estimates for $\exp G(\varphi)$ are proved. The obtained estimates show that complete mixing of the generator output sequence can be achieved after a number of cycles, which is significantly smaller than the dimension (in bites) of the generator state.
Keywords: additive generator, mixing graph of transformation, exponent of graph. 
@article{PDMA_2014_7_a26,
     author = {A. M. Dorokhova},
     title = {Estimates for exponents of mixing graphs relating to some modifications of additive generators},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {60--64},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a26/}
}
TY  - JOUR
AU  - A. M. Dorokhova
TI  - Estimates for exponents of mixing graphs relating to some modifications of additive generators
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 60
EP  - 64
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a26/
LA  - ru
ID  - PDMA_2014_7_a26
ER  - 
%0 Journal Article
%A A. M. Dorokhova
%T Estimates for exponents of mixing graphs relating to some modifications of additive generators
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 60-64
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a26/
%G ru
%F PDMA_2014_7_a26
A. M. Dorokhova. Estimates for exponents of mixing graphs relating to some modifications of additive generators. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 60-64. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a26/

[1] Shnaier B., Prikladnaya kriptografiya. Protokoly, algoritmy, iskhodnye teksty na yazyke Si, Triumf, M., 2002

[2] Kogos K. G., Fomichev V. M., “Polozhitelnye svoistva neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2012, no. 4(18), 5–13

[3] Koreneva A. M., Fomichev V. M., “Ob odnom obobschenii blochnykh shifrov Feistelya”, Prikladnaya diskretnaya matematika, 2012, no. 3(17), 34–40

[4] Dorokhova A. M., Fomichev V. M., “Utochnënnye otsenki eksponentov peremeshivayuschikh grafov biektivnykh registrov sdviga nad mnozhestvom dvoichnykh vektorov”, Prikladnaya diskretnaya matematika, 2014, no. 1(23), 77–83

[5] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010

[6] Fomichev V. M., “Otsenki eksponentov primitivnykh grafov”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 101–112

[7] Fomichev V. M., “Svoistva putei v grafakh i v multigrafakh”, Prikladnaya diskretnaya matematika, 2010, no. 1(7), 118–124