INCREASING RANKS OF LINEAR FINITE AUTOMATA AND COMPLEXITY OF FA PUBLIC-KEY CRYPTOSYSTEM

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.