A cryptanalytic observation concerning systems based on language theory (Q1115843)

This note discusses a cryptanalytic method applicable to some public-key cryptosystems based on the theory of formal languages. Essentially, the method uses the fact that the image of a regular language under an inverse finite substitution is accepted by a finite automaton of the same size as the automaton accepting the original regular language. In particular, systems based on iterated morphisms and repeated finite substitutions, [\textit{A. Salomaa} and \textit{S. Yu}, Theor. Comput. Sci. 48, 283-296 (1986; Zbl 0636.94007)], will be discussed.