Cryptanalytical finite~automaton invertibility with finite delay
Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 27-37
Voir la notice de l'article provenant de la source Math-Net.Ru
The paper continues an investigation of the cryptanalytical invertibility concept with a finite delay introduced by the author for finite automata. Here, we expound an algorithmic test for an automaton $A$ to be cryptanalytically invertible with a finite delay, that is, to have a recovering function $f$ which allows to calculate a prefix of a length $m$ in an input sequence of the automaton $A$ by using its output sequence of a length $m+\tau$ and some additional information about $A$ defining a type of its invertibility and known to cryptanalysts. The test finds out whether the automaton $A$ has a recovering function $f$ or not and if it has, determines some or, may be, all of such functions. The test algorithm simulates a backtracking method for searching a possibility to transform a binary relation to a function by shortening its domain to a set corresponding to the invertibility type under consideration.
Keywords:
finite automata, information-lossless automata, automata invertibility, cryptanalytical invertibility, cryptanalytical invertibility test.
@article{PDM_2019_4_a2,
author = {G. P. Agibalov},
title = {Cryptanalytical finite~automaton invertibility with finite delay},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {27--37},
publisher = {mathdoc},
number = {4},
year = {2019},
language = {en},
url = {http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/}
}
G. P. Agibalov. Cryptanalytical finite~automaton invertibility with finite delay. Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 27-37. http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/