A cryptanalytic observation concerning systems based on language theory
type: Item
instance of: scholarly article
title: A cryptanalytic observation concerning systems based on language theory
zbMATH Open document ID: 0664.94013
DOI: 10.1016/0166-218X(88)90073-X
author: Jarkko Kari
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4087590
zbMATH Keywords: public-key cryptosystems
zbMATH Keywords: formal languages
zbMATH Keywords: regular language
zbMATH Keywords: finite automaton
zbMATH Keywords: iterated morphisms
zbMATH Keywords: finite substitutions
MaRDI profile type: Publication
Wikidata QID: Q62046001
cites work: Q4140407
cites work: On a public-key cryptosystem based on iterated morphisms and substitutions
description: scientific article; zbMATH DE number 4087590