Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

1. Introduction

Renji Tao

Institute of Software, Chinese Academy of Sciences

Beijing 100080, China trj@ios.ac.cn

Summary.

Finite automata are a mathematical abstraction of discrete and digital

systems with ﬁnite “memory”. From a behavior viewpoint, such a system

is a transducer which transforms an input sequence to an output sequence

with the same length. Whenever the input sequence can be retrieved by the

output sequence (and initial internal state), the system is with invertibility

and may be used as an encoder in application to cipher or error correcting.

The invertibility theory of ﬁnite automata is dealt within the ﬁrst six

chapters of this book. In the ﬁrst chapter, the basic concepts on ﬁnite au-

tomata are introduced. The existence of (weak) inverse ﬁnite automata and

boundedness of delay for (weakly) invertible ﬁnite automata are proven

in Sect. 1.4, and the coincidence between feedforward invertibility and

bounded error propagation is presented in Sect. 1.5. In Sect. 1.7, we char-

acterize the structure of (weakly) invertible ﬁnite automata by means of

their state tree. In addition, there is a section that reviews some basic

results of linear ﬁnite automata, as an introduction to Chap. 7.

Key words: ﬁnite automata, invertible, weakly invertible, feedforward

invertible, inverse, weak inverse, feedforward inverse, error propagation,

state tree

Finite automata are a mathematical abstraction of discrete and digital sys-

tems with ﬁnite “memory”. From a structural viewpoint, such a system has

an input and an output as well as an “internal state”. Its time system is

discrete (say, moments 0, 1,...). Only ﬁnite possible values can be taken by

the input (output and internal state, respectively) at each moment. And, the

output at the current moment and the internal state at the next moment can

be uniquely determined by the input and the internal state at the current

moment. From a behavior viewpoint, such a system is a transducer which

transforms an input sequence to an output sequence with the same length.

2 1. Introduction

Whenever the input sequence can be retrieved by the output sequence (and

the initial internal state), the system is with invertibility and may be used

as an encoder in application to cipher or error correcting.

The invertibility theory of ﬁnite automata is dealt within the ﬁrst six

chapters. In the ﬁrst chapter, the basic concepts on ﬁnite automata are in-

troduced. The existence of (weak) inverse ﬁnite automata and boundedness

of delay for (weakly) invertible ﬁnite automata are proven in Sect. 1.4, and

the coincidence between feedforward invertibility and bounded error propa-

gation is presented in Sect. 1.5. In Sect. 1.6, we characterize the structure of

(weakly) invertible ﬁnite automata by means of their state tree. In addition,

there is a section that reviews some basic results of linear ﬁnite automata, as

an introduction to Chap. 7.

1.1 Preliminaries

We begin with a brief excursion through some fundamental concepts. A reader

acquainted with the notation used may skip this section. We will assume a

familiarity with the most basic notions of set theory, such as membership ∈,

set-builder notation {· · · | · ··} or {· · · : ···}, empty set ∅, subset ⊆, union ∪,

intersection ∩, diﬀerence \.

1.1.1 Relations and Functions

For any sets A

,...,A

,theCartesian product of A

,...,A

is the

set

{(a

,...,a

) | a

∈ A

,i=1, 2,...,n},

denoted by A

× A

×···×A

(sometimes (a

,...,a

) is replaced by

a

,...,a

). In the case of A

= A, i =1, 2,...,n, A

× A

×···×A

called the n-fold Cartesian product of A and is abbreviated to A

. For any

i, 1  i  n,thei-th component of an element (a

,...,a

)inA

× A

···×A

means a

Let A and B be two sets. A relation R from A to B is a subset R of A×B.

If (a, b)isintherelationR, it is written as aRb.If(a, b)isnotintherelation

R,itiswrittenasaR/b. In the case of A = B, R is also called a relation on

A relation R on a set A is an equivalence relation, if the following condi-

tions hold: (a) R is reﬂexive, i.e., (a, a) ∈ R for any a in A;(b)R is symmetric,

i.e., (a, b) ∈ R implies (b, a) ∈ R for any a and b in A;and(c)R is transitive,

i.e., (a, b) ∈ R and (b, c) ∈ R imply (a, c) ∈ R for any a,

b and c in A.

1.1 Preliminaries 3

Let R be an equivalence relation on A. For any a in A, the set [a]

{b | b ∈ A, (a, b) ∈ R} is called the equivalence class containing a. The set

{[a]

| a ∈ A} is called the equivalence classes of R.

Let A be a set and π = {H

| i ∈ I} be a family of subsets of A.If(a)

∪

i∈I

= A and (b) H

∩ H

= ∅ for any diﬀerent i and j in I, π is called a

partition of A,andH

, i ∈ I are called blocks of the partition π.

Clearly, the equivalence classes of an equivalence relation on A deﬁne a

partition. Conversely, a partition {H

| i ∈ I} of A determines an equivalence

relation R on A in the following way:

(a, b) ∈ R ⇔∃i ∈ I(a ∈ H

& b ∈ H

a, b ∈ A.

It is convenient to identify an equivalence relation with its partition.

Let R be a relation from A to B. The subset

{a ∈ A |∃b ∈ B((a, b) ∈ R)}

of A is called the domain of R, and the subset

{b ∈ B |∃a ∈ A((a, b) ∈ R)}

of B is called the range of R.

Suppose that R is a relation from A to B. Deﬁne a relation R

−1

from B

to A as follows:

(a, b) ∈ R

−1

⇔ (b, a) ∈ R,

a ∈ A, b ∈ B.

−1

is called the inverse relation of R. Clearly, the domain of R and the

range of R

−1

are the same; the domain of R

−1

and the range of R are the

same.

Let R be a relation from A to B. If, for any a in A,anyb and b



in B,

(a, b) ∈ R and (a, b



) ∈ R imply b = b



, R is called a partial function from A

to B.

A single-valued function (mapping)fromA to B is a partial function R

from A to B such that the domain of R is A. A single-valued function from

a set to itself is also called a function or a transformation on the set.

Let f be a single-valued mapping or partial function from A to B.For

any a in the domain of f, the unique element in B,sayb, satisfying (a, b) ∈ f

is written as f(a), and is called the value of f at (the point) a. For any a not

in the domain of f, we say that the value of f at (the point) a is undeﬁned.

For any relation R from A to B and any a in A,wealsouseR(a) to denote

the set {b ∈ B | (a, b) ∈ R

}. Clearly, R

−1

(b)={a ∈ A | (b, a) ∈ R

−1

} =

{a ∈ A | (a, b) ∈ R} for any b in B.

4 1. Introduction

Let f be a single-valued mapping from A to B. If the range of f is B, f

is called a surjection,ortobesurjective, or a single-valued mapping from A

onto B.Iff(a) = f(a



) holds for any diﬀerent elements a and a



in A, f is

called an injection,ortobeinjective,ortobeone-to-one.Iff is injective and

surjective, f is called a bijection,ortobebijective,oraone-to-one mapping

from A onto B. If there exists a one-to-one mapping from A onto B, A is

said to be one-to-one correspondent with B. A bijection from a ﬁnite set to

itself is also called a permutation on the set, or of its elements.

If f is a partial or single-valued function from A to B, the inverse relation

−1

is also called the inverse function of f.Thusf

−1

(b)={a ∈ A | (a, b) ∈

f} = {a ∈ A | f (a)=b}. For any b in B, whenever |f

−1

(b)| =1,wealsouse

−1

(b) to denote the unique element, say a,inf

−1

(b), where f(a)=b;from

the context, the reader can easily understand the meaning of the notation

withoutambiguity.Itiseasytoseethatiff is a bijection from A to B,

then f

−1

is a bijection from B to A and f

−1

(f(a)) = a for any a ∈ A,

f(f

−1

(b)) = b for any b ∈ B.

An injection f from A to B is also called an invertible function, or an

invertible transformation in the case of A = B; a partial or single-valued

function g from B to A is called an inverse function,oran inverse transfor-

mation inthecaseofA = B,off,ifg(f(a)) = a holds for any a ∈ A.For

any partial or single-valued function f

from A

to B

, i =1, 2, if A

⊆ A

⊆ B

and f

(a)=f

(a) for any a ∈ A

, f

is called a restriction of f

(on A

). We use f

to denote a restriction of f

on A

. Clearly, if g is an

inverse function of f, then the inverse function f

−1

of f is a restriction of

g.Wealsousef

−1

to denote an inverse function of f; from the context, the

reader can easily understand the meaning of the notation without ambiguity.

A vector function of dimension n in s variables over F means a single-

valued function from the s-fold Cartesian product of F (respectively an

s-dimensional vector space over F )tothen-fold Cartesian product of F (re-

spectively an n-dimensional vector space over F). For a vector function ϕ of

dimension n in s variables over F , its value at the point (x

,...,x

)isusually

expressed as ϕ(x

,...,x

); for any i,1 i  n,thei-th component function

of ϕ is a single-valued function from the s-fold Cartesian product of F (re-

spectively an s-dimensional vector space over F )toF of which the value at

each point (x

,...,x

)isthei-th component of ϕ(x

,...,x

). A vector func-

tion over {0, 1} is called a Boolean vector function. A Boolean function means

a Boolean vector function of dimension 1. A Boolean function ϕ(x

,...,x

)

in s variables can be expressed by a polynomial of x

,...,x

; if the degree

of the polynomial is greater than 1, ϕ is said to be nonlinear. The Boolean

function in s variables of which all values are 0 is called the zero Boolean

1.1 Preliminaries 5

function in s variables. The function on A of which the value at each a in A

equals a is called the identity function on A.

1.1.2 Graphs

We will discuss some fundamental concepts of graph. (V, Γ)iscalleda(di-

rected) graph,ifΓ ⊆ V × V for a nonempty set V . V is called the vertex

set, and elements in V are called vertices. Γ is called the arc set or the di-

rected edge set, and elements in Γ are called arcs or directed edges. For an arc

u =(a, b) ∈ Γ , a is called the initial vertex of u,andb the terminal vertex

of u.

Let w = u

...u

... be a ﬁnite or inﬁnite sequence of arcs, where u

∈

Γ , i =1, 2,... If the terminal vertex of u

is the initial vertex of u

i+1

for any

, u

i+1

in w, w is called a path of the graph (V,Γ).Thenumberofarcsinw

is called the length of the path w. The initial vertex of u

is called the initial

vertex of the path w;andtheterminalvertexofu

is called the terminal

vertex of the path w if the length of the path w is n.

If w = u

...u

is a path of the graph (V,Γ)andtheterminalvertexof

the arc u

is the initial vertex of the arc u

, the path w is called a circuit of

the graph (V,Γ). Evidently, if there exists a circuit, then there exists a path

of inﬁnite length.

For any vertex a, the set {b|(b, a) ∈ Γ, b ∈ V } is called the incoming vertex

set of a, and the set {b|(a, b) ∈ Γ, b ∈ V } is called the outgoing vertex set of

A vertex of which both the incoming vertex set and the outgoing vertex

set are empty is called an isolated vertex.

We deﬁne recurrently the levels of vertices as follows. For any vertex a in

V , if the incoming vertex set of a is empty, the level of a is deﬁned to be 0.

For any vertex a in V , if the levels of all vertices in the incoming vertex set

of a have been deﬁned and the maximum is h,thelevel of a is deﬁned to be

h +1.

For any arc u =(a, b), if levels of a and b have been deﬁned, the level of

the arc u is deﬁned to be the level of the vertex a.

If the level of each vertex of (V,Γ) is deﬁned and the maximum is h,we

say that the graph has level,andthelevel

of the graph is deﬁned to be h − 1.

Clearly, if each vertex of (V,Γ) is an isolated vertex, then the level of the

graph is −1.

If V is ﬁnite, the graph (V,Γ)issaidtobeﬁnite.

Notice that for a ﬁnite graph, it has no circuit if and only if it has level,

and the maximum of its path-lengths equals its level plus 1 if it has level.

6 1. Introduction

It is convenient for some applications to introduce the empty graph.The

vertex set and the arc set of the empty graph can be regarded as the empty

set. The level of the empty graph is deﬁned to be −2.

Two graphs (V, Γ)and(V



,Γ



)aresaidtobeisomorphic, if there exists

a one-to-one mapping ϕ from V onto V



such that (a, b)isanarcof(V, Γ)if

andonlyif(ϕ(a),ϕ(b)) is an arc of (V



,Γ



). Any such mapping ϕ is called an

isomorphism from (V,Γ)to(V



,Γ



). An isomorphism from a graph to itself

is called an automorphism of the graph.

Agraph(V



,Γ



)iscalledasubgraph of a graph (V,Γ), if V



⊆ V and



⊆ Γ .

Agraph(V,Γ) is called a tree with root v, if the following conditions

hold: (a) each vertex (= v)isaterminalvertexofauniquearc;(b)v is not

a terminal vertex of any arc; and (c) (V,Γ) has no circuit.

A vertex of a tree is called a leaf, if no arc emits from the vertex, i.e., the

outgoing vertex set of the vertex is empty.

Let (V, Γ)and(V



,Γ



) be two trees. If (V



,Γ



) is a subgraph of (V, Γ),



,Γ



) is called a subtree of (V,Γ).

Let G be a (directed) graph (respectively tree). If an element of some set

is assigned to each arc of G, or if an element of some set is assigned to each

arc of G and an element of some set is assigned to each vertex of G, G is

called a labelled graph (respectively labelled tree). The element assigned to an

arc (respectively a vertex) is referred to as the arc (respectively vertex) label

of the arc (respectively vertex).

1.2 Deﬁnitions of Finite Automata

1.2.1 Finite Automata as Transducers

For any set A, the concatenation of elements in A,saya

...a

l−1

, is called

a word (or a ﬁnite sequence)overA,andl its length,wherea

,...,a

l−1

are elements in A. In the case of l =0,a

...a

l−1

is a void sequence which

contains no element. The void sequence is called the empty word and its

length is 0. We use ε to denote the empty word (void sequence), and |α| the

length of a word α. The set of all the words over A including the empty word

is denoted by A

∗

.Ifa

,...,a

,... are elements in A, the concatenation

of the inﬁnite elements a

...a

... is called an inﬁnite-length word or an

ω-word (or an inﬁnite sequence)overA.WeuseA

to denote the set of all

inﬁnite-length words over A.WealsouseA

to denote the set of all words

over A of length n for any nonnegative integer n.

Let α = a

...a

m−1

and β = b

...b

n−1

be two words in A

∗

.The

concatenation of α and β is a

...a

m−1

...b

n−1

, which is also a word in

1.2 Deﬁnitions of Finite Automata 7

∗

of length m+n, and is denoted by α·β,orαβ for short. Clearly, α·ε = ε·α =

α. Similarly, if α = a

...a

m−1

is in A

∗

and β = b

...b

n−1

... in A

then the concatenation of α and β is the element a

...a

m−1

...b

n−1

...

in A

which is also denoted by α · β,orαβ for short. Clearly, ε · β = β. β is

called a preﬁx of α, if there exists γ such that α = βγ. β is called a suﬃx of

α, if there exists γ such that α = γβ. For any U, V ⊆ A

∗

, the concatenation

of U and V is the set {αβ | α ∈ U, β ∈ V }, denoted by UV.

A ﬁnite automaton is a quintuple X, Y, S, δ, λ,whereX, Y and S are

nonempty ﬁnite sets, δ is a single-valued mapping from S × X to S,andλ is

a single-valued mapping from S × X to Y . X, Y and S are called the input

alphabet,theoutput alphabet and the state alphabet of the ﬁnite automaton,

respectively; and δ and λ are called the next state function and the output

function of the ﬁnite automaton, respectively.

Expand the domain of δ to S × X

∗

as follows. For any state s

in S and

any l(> 0) input letters x

,...,x

l−1

in X, we compute recurrently states

,...,s

in S by

i+1

= δ(s

),i=0, 1,...,l− 1,

and deﬁne

δ(s

...x

l−1

)=s

In the case of l = 0, we deﬁne

δ(s

,ε)=s

Expand the domain of λ to S × (X

∗

∪ X

) and the range of λ to Y

∗

∪ Y

follows. For any state s

in S and any l(> 0) input letters x

,...,x

l−1

X, we deﬁne

λ(s

...x

l−1

)=y

...y

l−1

where

= λ(δ(s

...x

i−1

),x

),i=0, 1,...,l− 1.

In the case of l = 0, we deﬁne

λ(s

,ε)=ε.

For any state s

in S and any inﬁnite input letters x

,... in X, we deﬁne

λ(s

...)=y

...,

where

8 1. Introduction

= λ(δ(s

...x

i−1

),x

),i=0, 1,...

From the deﬁnitions, it is easy to see that

δ(s, αβ)=δ(δ(s, α),β),s∈ S, α, β ∈ X

∗

and

λ(s, αβ)=λ(s, α)λ(δ(s, α),β),s∈ S, α ∈ X

∗

,β∈ X

∗

∪ X

. (1.1)

Notice that each state s of the ﬁnite automaton determines a single-valued

mapping λ

from X

∗

∪ X

to Y

∗

∪ Y

,where

(α)=λ(s, α),α∈ X

∗

∪ X

is called the automaton mapping of s of which the restriction λ

∗

is a

single-valued mapping from X

∗

to Y

∗

and the restriction λ

is a single-

valued mapping from X

to Y

.From(1.1),itisevidentthatλ

∗

and

can be determined by each other. A single-valued mapping ϕ from X

∗

to Y

∗

is said to be sequential,if|ϕ(α)| = |α| for any α ∈ X

∗

and ϕ(β)isa

preﬁx of ϕ(α) for any α ∈ X

∗

and any preﬁx β of α. From the deﬁnition of

λ and (1.1), λ

∗

is sequential.

Example 1.2.1. Let X = Y = {0, 1} and S = {0, 1}

= {a

,...,a

|a

,...,

=0, 1}. Deﬁne

δ(a

,...,a

,x)=a

,...,a

,f(a

,...,a

,x),

λ(a

,...,a

,x)=g(a

,...,a

,x),

,...,a

,x=0, 1,

where f and g are two single-valued mappings from {0, 1}

n+1

to {0, 1}.Then

X, Y, S, δ, λ is a ﬁnite automaton. We use BSR

f,g

to denote the ﬁnite

automaton. The name is an abbreviation of the phrase “Binary Shift Register

with feedback function f and mixer g ”. Given s

= a

−n

,...,a

−1

∈S and

∈ X, i =0, 1,...,let

λ(s

...x

...)=y

...y

...

for some y

∈ Y , i =0, 1,... Then

= g(a

i−n

,...,a

i−1

),i=0, 1,...

and

δ(s

...x

i−1

)=a

i−n

,...,a

i−1

,i=0, 1,...,

where

1.2 Deﬁnitions of Finite Automata 9

= f(a

i−n

,...,a

i−1

),i=0, 1,...

A special case is of interest, where f(a

,...,a

,x) does not depend on

x,thatis,f is a single-valued mapping from {0, 1}

to {0, 1},andg can be

expressed as

g(a

,...,a

,x)=g



,...,a

) ⊕ x,

⊕ standing for the exclusive-or operation, that is, the addition modulo 2

operation. This automaton is called the binary steam cipher in cryptology

community. The key-sequence is generated by a shift register with feedback

function f and output logic g



; the mixer of the key and the input is the

addition modulo 2. Given s

= a

−n

,...,a

−1

∈S and x

∈ X, i =0, 1,...,

let

λ(s

...x

...)=y

...y

...

for some y

∈ Y , i =0, 1,... Then

= g



i−n

,...,a

i−1

) ⊕ x

,i=0, 1,...

and

δ(s

...x

i−1

)=a

i−n

,...,a

i−1

,i=0, 1,...,

where

= f(a

i−n

,...,a

i−1

),i=0, 1,...

Let M

= X

,δ

,λ

, i =1, 2 be two ﬁnite automata. For any

∈ S

, i =1, 2, s

and s

are said to be equivalent, denoted by s

∼ s

,if

= X

and for any α ∈ X

∗

, λ

,α)=λ

,α)holds.

Let λ

i,s

be the automaton mapping of s

, i =1, 2. Consider λ

i,s

∗

a mapping from X

∗

to (Y

∪ Y

)

∗

.Thens

∼ s

if and only if λ

1,s

∗

2,s

∗

. Consider λ

i,s

as a mapping from X

to (Y

∪Y

)

.Sinceλ

i,s

∗

and λ

i,s

are determined by each other, we have that s

∼ s

if and only

if λ

1,s

= λ

2,s

. Therefore, s

∼ s

if and only if λ

1,s

= λ

2,s

.Inother

words, s

∼ s

if and only if for any α ∈ X

(= X

), λ

,α)=λ

,α)

holds, if and only if for any α ∈ X

∗

∪ X

(= X

∗

∪ X

), λ

,α)=λ

,α)

holds.

From the deﬁnition, it is easy to show that the relation ∼ is reﬂexive,

symmetric and transitive.

If s

∼ s

and α ∈ X

∗

,thenδ(s

,α) ∼ δ(s

,α). In fact, since s

∼ s

for any β ∈ X

∗

,wehaveλ

,α)=λ

,α)andλ

,αβ)=λ

,αβ).

From

,αβ)=λ

,α)λ

(δ

,α),β),i=1, 2,

it follows that

10 1. Introduction

,α)λ

(δ

,α),β)=λ

,α)λ

(δ

,α),β).

Thus

(δ

,α),β)=λ

(δ

,α),β).

We conclude that δ(s

,α) ∼ δ(s

,α).

is said to be stronger than M

, denoted by M

≺ M

, if for any state

in S

, there exists a state s

in S

such that s

∼ s

. M

and M

are

said to be equivalent, denoted by M

∼ M

,ifM

≺ M

and M

≺ M

Clearly, the relation ≺ is reﬂexive and transitive, and the relation ∼ on ﬁnite

automata is reﬂexive, symmetric and transitive.

A ﬁnite automaton is said to be minimal, if any diﬀerent states of it are

not equivalent.

and M

are said to be isomorphic,ifX

= X

, Y

= Y

and there

exists a one-to-one mapping ϕ from S

onto S

such that

ϕ(δ

,x)) = δ

(ϕ(s

),x),λ

,x)=λ

(ϕ(s

),x),s

∈ S

,x∈ X

ϕ is called an isomorphism from M

to M

If M

and M

are isomorphic, then M

and M

are equivalent. In fact,

since M

and M

are isomorphic, there exists an isomorphism ϕ from M

. We prove by induction on the length of α that

(s, α)=λ

(ϕ(s),α) (1.2)

holds for any s in S

and any α in X

∗

. Basis : |α| = 0, i.e., α = ε.Since

(s, α)=ε = λ

(ϕ(s),α)

holds for any s in S

, (1.2) holds for any s in S

and α = ε. Induction step :

Suppose that we have proven that (1.2) holds for any s in S

and any α in

∗

of length n.Givenα ∈ X

∗

of length n +1, let α = xα



,wherex ∈ X

Then the length of α



is n.SinceM

and M

are isomorphic, we have

ϕ(δ

(s, x)) = δ

(ϕ(s),x)

and

(s, x)=λ

(ϕ(s),x).

From the induction hypothesis, we have

(δ

(s, x),α



)=λ

(ϕ(δ

(s, x)),α



Thus