F. Bao, INCREASING RANKS OF LINEAR FINITE AUTOMATA AND COMPLEXITY OF FA PUBLIC-KEY CRYPTOSYSTEM, Science in China. Series A, Mathematics, Physics, Astronomy & Technological Sciences, 37(4), 1994, pp. 504-512
The encryption algorithm of finite automata (FA) public key cryptosyst
em is implemented by a weakly invertible finite automata (WIFA) which
is composed of a nonlinear WIFA with delay 0 and a linear WIFA with de
lay tau. In this paper, we proved that such an automaton bears the sam
e properties as the linear WIFA and the increasing ranks of the latter
are key factors to affecting the former. A probabilistic algorithm is
given to realize a ciphertext attack, and its complexity is analysed
through the increasing ranks of the linear WIFA. The size of the param
eters for safe linear WIFA is estimated.