Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
9.6 Generalized Algorithms 375
s
∗
0
= v(−1,h),w(0,n+1),z(−1,τ + k)
of M
∗
and any z
0
,z
1
,...∈ Z,if
v
0
v
1
...= λ
∗
(s
∗
0
,z
0
z
1
...),
then
z
0
z
1
...= λ(s
τ
,v
τ
v
τ+1
...),
where
s
τ
= z(−1,k),w(τ,n +1),v(τ − 1,h),
w
i+1
= ψ(z(i − τ − 1,k),w(i, n +1),v(i, h +1)),
i =0, 1,...,τ − 1.
For any i,0 i n,letX
i
be the column vector space over GF (q)of
dimension l
i
.LetY be the column vector space over GF (q) of dimension m,
and X = X
n
.
For any i,1 i n,letM
i
= X
i
,X
i−1
,U
p
i
+1
i
× X
r
i
i
,δ
i
,λ
i
be an
(r
i
, 0,p
i
)-order pseudo-memory finite automaton determined by f
i
and g
i
,
where
λ
i
(u
(i)
(0,p
i
+1),x
(i)
(−1,r
i
),x
(i)
0
)=x
(i−1)
0
,
δ
i
(u
(i)
(0,p
i
+1),x
(i)
(−1,r
i
),x
(i)
0
)=u
(i)
(1,p
i
+1),x
(i)
(0,r
i
), (9.28)
x
(i−1)
0
= f
i
(u
(i)
(0,p
i
+1),x
(i)
(0,r
i
+1)),
u
(i)
1
= g
i
(u
(i)
(0,p
i
+1),x
(i)
(0,r
i
+1)),
and let M
∗
i
= X
i−1
,X
i
,X
r
i
i
× U
p
i
+1
i
× X
τ
i
i−1
,δ
∗
i
,λ
∗
i
be a (τ
i
,r
i
,p
i
)-order
pseudo-memory finite automaton determined by f
∗
i
and g
i
,where
λ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(−1,τ
i
),x
(i−1)
0
)=x
(i)
0
,
δ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(−1,τ
i
),x
(i−1)
0
)
= x
(i)
(0,r
i
),u
(i)
(1,p
i
+1),x
(i−1)
(0,τ
i
), (9.29)
x
(i)
0
= f
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(0,τ
i
+1)),
u
(i)
1
= g
i
(u
(i)
(0,p
i
+1),x
(i)
(0,r
i
+1)).
Assume that τ
i
r
i
for 1 i n.
Let M
0
= X
0
,Y,Y
t
0
×U
p
0
+1
0
×X
r
0
0
,δ
0
,λ
0
be an (r
0
,t
0
,p
0
)-order pseudo-
memory finite automaton determined by f
0
and g
0
,where
λ
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),x
(0)
(−1,r
0
),x
(0)
0
)=y
0
,
δ
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),x
(0)
(−1,r
0
),x
(0)
0
)
376 9. Finite Automaton Public Key Cryptosystems
= y(0,t
0
),u
(0)
(1,p
0
+1),x
(0)
(0,r
0
), (9.30)
y
0
= f
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),x
(0)
(0,r
0
+1)),
u
(0)
1
= g
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),x
(0)
(0,r
0
+1)).
Let M
∗
0
= Y, X
0
,X
r
0
0
× U
p
0
+1
0
× Y
τ
0
+t
0
,δ
∗
0
,λ
∗
0
be a (τ
0
+ t
0
,r
0
,p
0
)-order
pseudo-memory finite automaton determined by f
∗
0
and g
0
where
λ
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(−1,τ
0
+ t
0
),y
0
)=x
(0)
0
,
δ
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(−1,τ
0
+ t
0
),y
0
)
= x
(0)
(0,r
0
),u
(0)
(1,p
0
+1),y(0,τ
0
+ t
0
), (9.31)
x
(0)
0
= f
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(0,τ
0
+ t
0
+1)),
u
(0)
1
= g
0
(y(−τ
0
− 1,t
0
),u
(0)
(0,p
0
+1),x
(0)
(0,r
0
+1)).
Assume that τ
0
r
0
.
Abbreviate τ
i,j
= τ
i
+ τ
i+1
+ ···+ τ
j
, r
i,j
= r
i
+ r
i+1
+ ···+ r
j
and
p
i,j
= r
i
+r
i+1
+···+ r
j−1
+p
j
for any integer i and j with i j.Letτ
i,j
=0
inthecaseofi>j.Thusp
j,j
= p
j
, τ
j,j
= τ
j
and r
j,j
= r
j
.Letf
n,n
= f
n
and g
n,n
= g
n
. For any i,1 i n − 1, let
f
i,n
(u
(i)
(0,p
i,i
+1),u
(i+1)
(0,p
i,i+1
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(0,r
i,n
+1))
= f
i
(u
(i)
(0,p
i
+1),
f
i+1,n
(u
(i+1)
(0,p
i+1,i+1
+1),u
(i+2)
(0,p
i+1,i+2
+1),...,
u
(n)
(0,p
i+1,n
+1),x
(n)
(0,r
i+1,n
+1)),
......,
f
i+1,n
(u
(i+1)
(−r
i
,p
i+1,i+1
+1),u
(i+2)
(−r
i
,p
i+1,i+2
+1),...,
u
(n)
(−r
i
,p
i+1,n
+1),x
(n)
(−r
i
,r
i+1,n
+ 1)))
and
g
i,n
(u
(i)
(0,p
i,i
+1),u
(i+1)
(0,p
i,i+1
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(0,r
i,n
+1))
= g
i
(u
(i)
(0,p
i
+1),
f
i+1,n
(u
(i+1)
(0,p
i+1,i+1
+1),u
(i+2)
(0,p
i+1,i+2
+1),...,
u
(n)
(0,p
i+1,n
+1),x
(n)
(0,r
i+1,n
+1)),
......,
f
i+1,n
(u
(i+1)
(−r
i
,p
i+1,i+1
+1),u
(i+2)
(−r
i
,p
i+1,i+2
+1),...,
u
(n)
(−r
i
,p
i+1,n
+1),x
(n)
(−r
i
,r
i+1,n
+ 1))).
Let
f
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1))
9.6 Generalized Algorithms 377
= f
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),
f
1,n
(u
(1)
(0,p
1,1
+1),u
(2)
(0,p
1,2
+1),...,
u
(n)
(0,p
1,n
+1),x
(n)
(0,r
1,n
+1)),
......,
f
1,n
(u
(1)
(−r
0
,p
1,1
+1),u
(2)
(−r
0
,p
1,2
+1),...,
u
(n)
(−r
0
,p
1,n
+1),x
(n)
(−r
0
,r
1,n
+ 1)))
and
g
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1))
= g
0
(y(−1,t
0
),u
(0)
(0,p
0
+1),
f
1,n
(u
(1)
(0,p
1,1
+1),u
(2)
(0,p
1,2
+1),...,
u
(n)
(0,p
1,n
+1),x
(n)
(0,r
1,n
+1)),
......,
f
1,n
(u
(1)
(−r
0
,p
1,1
+1),u
(2)
(−r
0
,p
1,2
+1),...,
u
(n)
(−r
0
,p
1,n
+1),x
(n)
(−r
0
,r
1,n
+ 1))).
Let M
n,n
= M
n
and M
i,n
= C
(M
i+1,n
,M
i
) for 0 i n − 1. From the
definition of compound finite automata, for any i,1 i n,wehave
M
i,n
= X
n
,X
i−1
,U
p
i,i
+1
i
× U
p
i,i+1
+1
i+1
×···×U
p
i,n
+1
n
× X
r
i,n
n
,δ
i,n
,λ
i,n
,
where
λ
i,n
(u
(i)
(0,p
i,i
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(−1,r
i,n
),x
(n)
0
)=x
(i−1)
0
,
δ
i,n
(u
(i)
(0,p
i,i
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(−1,r
i,n
),x
(n)
0
)
= u
(i)
(1,p
i,i
+1),...,u
(n)
(1,p
i,n
+1),x
(n)
(0,r
i,n
),
and
x
(i−1)
0
= f
i,n
(u
(i)
(0,p
i,i
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(0,r
i,n
+1)),
u
(c)
1
= g
c,n
(u
(c)
(0,p
c,c
+1),...,u
(n)
(0,p
c,n
+1),x
(n)
(0,r
c,n
+1)),
c = i,...,n.
And we have
M
0,n
= X
n
,Y,Y
t
0
× U
p
0,0
+1
0
× U
p
0,1
+1
1
×···×U
p
0,n
+1
n
× X
r
0,n
n
,δ
0,n
,λ
0,n
,
where
λ
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),...,u
(n)
(0,p
0,n
+1),x
(n)
(−1,r
0,n
),x
(n)
0
)= y
0
,
δ
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),...,u
(n)
(0,p
0,n
+1),x
(n)
(−1,r
0,n
),x
(n)
0
)
= y(0,t
0
),u
(0)
(1,p
0,0
+1),...,u
(n)
(1,p
0,n
+1),x
(n)
(0,r
0,n
),
378 9. Finite Automaton Public Key Cryptosystems
and
y
0
= f
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1)),
u
(0)
1
= g
0,n
(y(−1,t
0
),u
(0)
(0,p
0,0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1)),
u
(c)
1
= g
c,n
(u
(c)
(0,p
c,c
+1),u
(c+1)
(0,p
c,c+1
+1),...,
u
(n)
(0,p
c,n
+1),x
(n)
(0,r
c,n
+1)),
c =1,...,n.
Theorem 9.6.2. Assume that M
∗
i
, M
i
and τ
i
satisfy PI
2
(M
∗
i
,M
i
,τ
i
), i =
0, 1,...,n.Lets
(i)∗
−b
i−1
= x
(i)
(−b
i−1
−1,r
i
), u
(i)
(−b
i−1
,p
i
+1), ¯x
(i−1)
(−b
i−1
−
1,τ
i
) be a state of M
∗
i
, i =1,...,n.Letx
(0)
−b
0
,...,x
(0)
−1
∈ X
0
,
x
(i)
−b
i−1
...x
(i)
−1
= λ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
),
s
(i)∗
0
= δ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
), (9.32)
i =1,...,n,
and
u
(i)
j+1
= g
i
(u
(i)
(j, p
i
+1),x
(i)
(j, r
i
+ 1)) (9.33)
for i =1,...,n and j = −b
i−1
,...,−1,whereb
−1
=max{τ
0
, −
i−1
j=0
r
j
+
i
j=0
τ
j
, i =1,...,n},andb
i
= b
i−1
+ r
i
− τ
i
for 0 i n.Lets
(0)∗
0
=
x
(0)
(−1,r
0
), u
(0)
(0,p
0
+1), y(−1,τ
0
+ t
0
) be a state of M
∗
0
.If
x
(0)
0
x
(0)
1
...= λ
∗
0
(s
(0)∗
0
,y
0
y
1
...),
x
(i)
0
x
(i)
1
...= λ
∗
i
(s
(i)∗
0
,x
(i−1)
0
x
(i−1)
1
...), (9.34)
i =1,...,n,
then
y
0
y
1
...= λ
0,n
(s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...),
where s = y(−1,t
0
), u
(0)
(τ
0,0
,p
0,0
+1), u
(1)
(τ
0,1
,p
0,1
+1), ..., u
(n)
(τ
0,n
,
p
0,n
+1), x
(n)
(τ
0,n
− 1,r
0,n
),andu
(i)
j
in s for 0 <j τ
0,i
are computed out
according to the following formulae
u
(i)
j+1
= g
i,n
(u
(i)
(j, p
i,i
+1),u
(i+1)
(j + τ
i+1,i+1
,p
i,i+1
+1),...,
u
(n)
(j + τ
i+1,n
,p
i,n
+1),x
(n)
(j + τ
i+1,n
,r
i,n
+1)),
j =0, 1,...,τ
0,i
− 1,
i = n, n − 1,...,1, (9.35)
9.6 Generalized Algorithms 379
u
(0)
j+1
= g
0,n
(y(j − τ
0
− 1,t
0
),u
(0)
(j, p
0,0
+1),u
(1)
(j + τ
1,1
,p
0,1
+1),...,
u
(n)
(j + τ
1,n
,p
0,n
+1),x
(n)
(j + τ
1,n
,r
0,n
+1)),
j =0, 1,...,τ
0,0
− 1.
Proof. Suppose that (9.34) holds. From (9.32) and the part on M
∗
i
in
(9.34), it is easy to obtain that
x
(i)
−b
i−1
...x
(i)
−1
x
(i)
0
x
(i)
1
...= λ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
x
(i−1)
0
x
(i−1)
1
...),
i =1,...,n.Sinceb
i−1
τ
i
and (9.33) holds for i =1,...,n and j =
−b
i−1
,...,−1, from PI
2
(M
∗
i
,M
i
,τ
i
), it follows that
x
(i−1)
−b
i−1
...x
(i−1)
−1
x
(i−1)
0
x
(i−1)
1
...= λ
i
(s
(i)
,x
(i)
−b
i−1
+τ
i
x
(i)
−b
i−1
+τ
i
+1
...), (9.36)
i =1,...,n,wheres
(i)
= u
(i)
(−b
i−1
+ τ
i
,p
i
+1),x
(i)
(−b
i−1
+ τ
i
− 1,r
i
),
i =1,...,n. For any i, 1 i n, letting (9.33) for j =0, 1,..., since (9.33)
holds for j = −b
i−1
,...,−1, we have
u
(i)
j+1
= g
i
(u
(i)
(j, p
i
+1),x
(i)
(j, r
i
+1)), (9.37)
j = −b
i−1
, −b
i−1
+1,...
For such u
(i)
’s which satisfy (9.37), from the definition of M
i
and (9.36), we
obtain
x
(i−1)
j
= f
i
(u
(i)
(j + τ
i
,p
i
+1),x
(i)
(j + τ
i
,r
i
+1)), (9.38)
j = −b
i−1
, −b
i−1
+1,...,
i =1,...,n.SincePI
2
(M
∗
0
,M
0
,τ
0
) holds, from the part on M
∗
0
in (9.34), we
have
y
0
y
1
...= λ
0
(s
(0)
,x
(0)
τ
0
x
(0)
τ
0
+1
...), (9.39)
where s
(0)
= y(−1,t
0
),u
(0)
(τ
0
,p
0
+1),x
(0)
(τ
0
− 1,r
0
),and
u
(0)
j+1
= g
0
(y(j − τ
0
− 1,t
0
),u
(0)
(j, p
0
+1),x
(0)
(j, r
0
+ 1)) (9.40)
for j =0,...,τ
0
− 1.
We prove by induction on i that for any i,1 i n,wehave
x
(i−1)
−b
i−1
x
(i−1)
−b
i−1
+1
...
= λ
i,n
(u
(i)
(−b
i−1
+ τ
i,i
,p
i,i
+1),u
(i+1)
(−b
i−1
+ τ
i,i+1
,p
i,i+1
+1),...,
u
(n)
(−b
i−1
+ τ
i,n
,p
i,n
+1),x
(n)
(−b
i−1
+ τ
i,n
− 1,r
i,n
), (9.41)
x
(n)
−b
i−1
+τ
i,n
x
(n)
−b
i−1
+τ
i,n
+1
...)
and
380 9. Finite Automaton Public Key Cryptosystems
x
(i−1)
j
= f
i,n
(u
(i)
(j + τ
i,i
,p
i,i
+1),u
(i+1)
(j + τ
i,i+1
,p
i,i+1
+1),...,
u
(n)
(j + τ
i,n
,p
i,n
+1),x
(n)
(j + τ
i,n
,r
i,n
+1)), (9.42)
u
(c)
j+τ
i,c
+1
= g
c,n
(u
(c)
(j + τ
i,c
,p
c,c
+1),u
(c+1)
(j + τ
i,c+1
,p
c,c+1
+1),...,
u
(n)
(j + τ
i,n
,p
c,n
+1),x
(n)
(j + τ
i,n
,r
c,n
+1)),
c = i,...,n, j = −b
i−1
, −b
i−1
+1,...
Basis : i = n. The formula (9.41) is
x
(n−1)
−b
n−1
x
(n−1)
−b
n−1
+1
...
= λ
n,n
(u
(n)
(−b
n−1
+ τ
n,n
,p
n,n
+1),x
(n)
(−b
n−1
+ τ
n,n
− 1,r
n,n
),
x
(n)
−b
n−1
+τ
n,n
x
(n)
−b
n−1
+τ
n,n
+1
...)
which is deduced by (9.36), using λ
n,n
= λ
n
, r
n,n
= r
n
, p
n,n
= p
n
and
τ
n,n
= τ
n
. Similarly, the formula (9.42) is
x
(n−1)
j
= f
n,n
(u
(n)
(j + τ
n,n
,p
n,n
+1),x
(n)
(j + τ
n,n
,r
n,n
+1)),
u
(n)
j+τ
n,n
+1
= g
n,n
(u
(n)
(j + τ
n,n
,p
n,n
+1),x
(n)
(j + τ
n,n
,r
n,n
+1)),
j = −b
n−1
, −b
n−1
+1,...
which is deduced by (9.37) and (9.38), using f
n,n
= f
n
, g
n,n
= g
n
, r
n,n
= r
n
,
p
n,n
= p
n
,andτ
n,n
= τ
n
. Induction step : Suppose that for i 1wehave
proven that
x
(i)
−b
i
x
(i)
−b
i
+1
...
= λ
i+1,n
(u
(i+1)
(−b
i
+ τ
i+1,i+1
,p
i+1,i+1
+1),
u
(i+2)
(−b
i
+ τ
i+1,i+2
,p
i+1,i+2
+1), ..., (9.43)
u
(n)
(−b
i
+ τ
i+1,n
,p
i+1,n
+1),x
(n)
(−b
i
+ τ
i+1,n
− 1,r
i+1,n
),
x
(n)
−b
i
+τ
i+1,n
x
(n)
−b
i
+τ
i+1,n
+1
...)
and
x
(c−1)
j
= f
c,n
(u
(c)
(j + τ
c,c
,p
c,c
+1),u
(c+1)
(j + τ
c,c+1
,p
c,c+1
+1),...,
u
(n)
(j + τ
c,n
,p
c,n
+1),x
(n)
(j + τ
c,n
,r
c,n
+ 1)) (9.44)
for c = i +1andj = −b
i
, −b
i
+1,...,
u
(c)
j+τ
i+1,c
+1
= g
c,n
(u
(c)
(j+τ
i+1,c
,p
c,c
+1),u
(c+1)
(j+τ
i+1,c+1
,p
c,c+1
+1),...,
u
(n)
(j + τ
i+1,n
,p
c,n
+1),x
(n)
(j + τ
i+1,n
,r
c,n
+ 1))(9.45)
for c = i +1,...,n and j = −b
i
, −b
i
+1,... We prove (9.41) and (9.42) hold.
Since −b
i
= −b
i−1
+ τ
i
− r
i
, (9.44) holds for c = i +1and−b
i−1
+ τ
i
− r
i
9.6 Generalized Algorithms 381
j<−b
i−1
+ τ
i
. From (9.43) and (9.36), noticing −b
i
−b
i
+ r
i
= −b
i−1
+ τ
i
,
applying Theorem 9.6.1, (9.41) holds. Since (9.37) holds and (9.44) holds for
c = i +1andj −b
i
= −b
i−1
+ τ
i
− r
i
, from the definition of g
c,n
,wehave
u
(c)
j+τ
i,c
+1
= g
c,n
(u
(c)
(j + τ
i,c
,p
c,c
+1),u
(c+1)
(j + τ
i,c+1
,p
c,c+1
+1),...,
u
(n)
(j + τ
i,n
,p
c,n
+1),x
(n)
(j + τ
i,n
,r
c,n
+ 1)) (9.46)
for c = i and j −b
i−1
.From−b
i
= −b
i−1
− r
i
+ τ
i
−b
i−1
+ τ
i
, (9.45)
holds for c = i +1,...,n and j −b
i−1
+ τ
i
. Replacing j in (9.45) by j + τ
i
,
it follows immediately that (9.46) holds for c = i +1,...,n and j −b
i−1
.
Therefore, (9.46) holds for c = i,...,n and j −b
i−1
. From (9.41), (9.44)
holds for c = i and j −b
i−1
; therefore, (9.44) holds for c = i,...,n and
j −b
i−1
. We conclude that (9.42) holds.
Especially, equation (9.41) and (9.42) hold for the case of i =1,thatis,
x
(0)
−b
0
x
(0)
−b
0
+1
...
= λ
1,n
(u
(1)
(−b
0
+ τ
1,1
,p
1,1
+1),u
(2)
(−b
0
+ τ
1,2
,p
1,2
+1),...,
u
(n)
(−b
0
+ τ
1,n
,p
1,n
+1),x
(n)
(−b
0
+ τ
1,n
− 1,r
1,n
), (9.47)
x
(n)
−b
0
+τ
1,n
x
(n)
−b
0
+τ
1,n
+1
...)
and
x
(0)
j
= f
1,n
(u
(1)
(j + τ
1,1
,p
1,1
+1),u
(2)
(j + τ
1,2
,p
1,2
+1),...,
u
(n)
(j + τ
1,n
,p
1,n
+1),x
(n)
(j + τ
1,n
,r
1,n
+1)), (9.48)
u
(c)
j+τ
1,c
+1
= g
c,n
(u
(c)
(j + τ
1,c
,p
c,c
+1),u
(c+1)
(j + τ
1,c+1
,p
c,c+1
+1),...,
u
(n)
(j + τ
1,n
,p
c,n
+1),x
(n)
(j + τ
1,n
,r
c,n
+1)),
c =1,...,n, j = −b
0
, −b
0
+1,...
Using Theorem 9.6.1, from (9.47), (9.39) and (9.48), we obtain
y
0
y
1
...= λ
0,n
(¯s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...),
where ¯s = y(−1,t
0
), u
(0)
(τ
0,0
,p
0,0
+1), u
(1)
(τ
0,1
,p
0,1
+1), ..., u
(n)
(τ
0,n
,p
0,n
+
1), x
(n)
(τ
0,n
− 1,r
0,n
).
To prove s =¯s, letting (9.40) for j τ
0
, since (9.40) holds for 0 j<τ
0
,
(9.40) holds for j 0. From (9.48) and the definition of g
0,n
, noticing b
−1
τ
0
, this yields that
u
(0)
j+τ
0
+1
= g
0,n
(y(j − 1,t
0
),u
(0)
(j + τ
0,0
,p
0,0
+1),u
(1)
(j + τ
0,1
,p
0,1
+1),
...,u
(n)
(j + τ
0,n
,p
0,n
+1),x
(n)
(j + τ
0,n
,r
0,n
+ 1)) (9.49)
382 9. Finite Automaton Public Key Cryptosystems
holds for j −τ
0
. Notice that for any i, 1 i n, (9.46) holds for c = i
and j −b
i−1
. The condition j −b
i−1
is equivalent to the condition
j + τ
i
−b
i−1
+ τ
i
which can be deduced by the condition j + τ
i
0 because
of −b
i−1
+ τ
i
0. Thus for any i, 1 i n, (9.46) holds for c = i and
j + τ
i
0, that is,
u
(i)
j+τ
i
+1
= g
i,n
(u
(i)
(j + τ
i,i
,p
i,i
+1),u
(i+1)
(j + τ
i,i+1
,p
i,i+1
+1),...,
u
(n)
(j + τ
i,n
,p
i,n
+1),x
(n)
(j + τ
i,n
,r
i,n
+1))
holds for j + τ
i
0. From (9.49), it follows that (9.35) holds. Therefore,
s =¯s.
Let r
0,j
= τ
0
+ t
0
+ r
1
+ ···+ r
j
and p
0,j
= τ
0
+ t
0
+ r
1
+ ···+ r
j−1
+ p
j
,
for j>0. Let
f
0,n
(y(−1,r
0
),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1))
= f
∗
0
(y(−1,r
0
),u
(i)
(0,p
0
+1),
f
1,n
(u
(1)
(0,p
1,1
+1),u
(2)
(0,p
1,2
+1),...,
u
(n)
(0,p
1,n
+1),x
(n)
(0,r
1,n
+1)),
......,
f
1,n
(u
(1)
(−τ
0
− t
0
,p
1,1
+1),u
(2)
(−τ
0
− t
0
,p
1,2
+1),...,
u
(n)
(−τ
0
− t
0
,p
1,n
+1),x
(n)
(−τ
0
− t
0
,r
1,n
+ 1)))
and
g
0,n
(y(0,r
0
+1),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1))
= g
0
(f
1,n
(u
(1)
(−τ
0
− 1,p
1,1
+1),u
(2)
(−τ
0
− 1,p
1,2
+1),...,
u
(n)
(−τ
0
− 1,p
1,n
+1),x
(n)
(−τ
0
− 1,r
1,n
+1)),
......,
f
1,n
(u
(1)
(−τ
0
− t
0
,p
1,1
+1),u
(2)
(−τ
0
− t
0
,p
1,2
+1),...,
u
(n)
(−τ
0
− t
0
,p
1,n
+1),x
(n)
(−τ
0
− t
0
,r
1,n
+1)),
u
(0)
(0,p
0
+1),y(0,r
0
+1)).
We use M
0,n
to denote C
(M
1,n
,M
∗
0
), where symbols of the input alphabet
and the output alphabet of M
∗
0
are interchanged. Then we have
M
0,n
= X
n
,Y,Y
r
0
× U
p
0
+1
0
× U
p
0,1
+1
1
× ...× U
p
0,n
+1
n
× X
r
0,n
n
,δ
0,n
,λ
0,n
,
where
9.6 Generalized Algorithms 383
λ
0,n
(y(−1,r
0
),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(−1,r
0,n
),x
(n)
0
)
= y
0
,
δ
0,n
(y(−1,r
0
),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(−1,r
0,n
),x
(n)
0
)
= y(0,r
0
),u
(0)
(1,p
0
+1),u
(1)
(1,p
0,1
+1),...,
u
(n)
(1,p
0,n
+1),x
(n)
(0,r
0,n
),
and
y
0
= f
0,n
(y(−1,r
0
),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1)),
u
(0)
1
= g
0,n
(y(0,r
0
+1),u
(0)
(0,p
0
+1),u
(1)
(0,p
0,1
+1),...,
u
(n)
(0,p
0,n
+1),x
(n)
(0,r
0,n
+1)),
u
(i)
1
= g
i,n
(u
(i)
(0,p
i,i
+1),...,u
(n)
(0,p
i,n
+1),x
(n)
(0,r
i,n
+1)),
i =1,...,n.
Theorem 9.6.3. Assume that M
∗
i
, M
i
and τ
i
satisfy PI
2
(M
∗
i
,M
i
,τ
i
),
i =1,...,n and that M
∗
0
, M
0
and τ
0
satisfy PI
1
(M
0
,M
∗
0
,τ
0
).Lets
(i)∗
−b
i−1
=
x
(i)
(−b
i−1
−1,r
i
), u
(i)
(−b
i−1
,p
i
+1), ¯x
(i−1)
(−b
i−1
−1,τ
i
) be a state of M
∗
i
,
i =1,...,n.Letx
(0)
−b
0
,...,x
(0)
−1
∈ X
0
,
x
(i)
−b
i−1
...x
(i)
−1
= λ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
),
s
(i)∗
0
= δ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
),
i =1,...,n,
and
u
(i)
j+1
= g
i
(u
(i)
(j, p
i
+1),x
(i)
(j, r
i
+1))
for i =1,...,n and j = −b
i−1
,...,−1,whereb
−1
=max{0, −
i−1
j=1
r
j
+
i
j=1
τ
j
, i =1,...,n}, b
0
= b
−1
+ t
0
,andb
i
= b
i−1
+ r
i
− τ
i
for 1 i n.
Let s
(0)
0
= x
(0)
(−1,t
0
), u
(0)
(0,p
0
+1), y(−1,r
0
) be a state of M
0
.If
x
(0)
0
x
(0)
1
...= λ
0
(s
(0)
0
,y
0
y
1
...),
x
(i)
0
x
(i)
1
...= λ
∗
i
(s
(i)∗
0
,x
(i−1)
0
x
(i−1)
1
...), (9.50)
i =1,...,n,
then
384 9. Finite Automaton Public Key Cryptosystems
y
0
y
1
...= λ
0,n
(s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...),
where s = y(−1,r
0
), u
(0)
(0,p
0
+1), u
(1)
(τ
0,1
,p
0,1
+1), ..., u
(n)
(τ
0,n
,p
0,n
+1),
x
(n)
(τ
0,n
− 1,r
0,n
),andu
(i)
j
in s for 0 <j τ
0,i
are computed out according
to the following formulae
u
(i)
j+1
= g
i,n
(u
(i)
(j, p
i,i
+1),u
(i+1)
(j + τ
i+1,i+1
,p
i,i+1
+1),...,
u
(n)
(j + τ
i+1,n
,p
i,n
+1),x
(n)
(j + τ
i+1,n
,r
i,n
+1)),
i = n, n − 1,...,1,j=0, 1,...,τ
0,i
− 1.
Proof. The proof of this theorem is similar to Theorem 9.6.2. Suppose
that (9.50) holds. From the proof of Theorem 9.6.2, (9.47) and (9.48) hold.
Since PI
1
(M
0
,M
∗
0
,τ
0
) holds, from the part on M
0
in (9.50), we have
y
0
y
1
...= λ
∗
0
(s
(0)∗
,x
(0)
τ
0
x
(0)
τ
0
+1
...), (9.51)
where s
(0)∗
= y(−1,r
0
),u
(0)
(0,p
0
+1),x
(0)
(τ
0
− 1,τ
0
+ t
0
). Using Theo-
rem 9.6.1, from (9.47), (9.51) and (9.48), we obtain
y
0
y
1
...= λ
0,n
(¯s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...),
where ¯s = y(−1,r
0
), u
(0)
(0,p
0
+1), u
(1)
(τ
0,1
,p
0,1
+1), ..., u
(n)
(τ
0,n
,p
0,n
+1),
x
(n)
(τ
0,n
− 1,r
0,n
). From the proof of Theorem 9.6.2 (neglecting (9.49)), ¯s
coincides with s.
Lemma 9.6.1. Assume that PI
1
(M
i
,M
∗
i
,τ
i
) holds for any i, 1 i n.
Let
s = u
(1)
(0,p
1
+1),u
(2)
(0,p
1,2
+1),...,u
(n)
(0,p
1,n
+1),x
(n)
(−1,r
1,n
)
be a state of C
(M
n
,...,M
1
).Let
x
(c−1)
j
= f
c,n
(u
(c)
(j, p
c,c
+1),...,u
(n)
(j, p
c,n
+1),x
(n)
(j, r
c,n
+1)),
j = −r
c−1
,...,−1 (9.52)
for c =2,...,n.If
x
(0)
0
x
(0)
1
...= λ
1,n
(s, x
(n)
0
x
(n)
1
...), (9.53)
then
x
(n)
0
x
(n)
1
... (9.54)
= λ
∗
n
(x
(n)
(−1,r
n
),u
(n)
(0,p
n
+1),x
(n−1)
(τ
n
− 1,τ
n
),x
(n−1)
τ
n
x
(n−1)
τ
n
+1
...),
where