Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
9.5 Security 365
9.5.1 Inversion by a General Method
If one can find a finite automaton M
∗
which is a weak inverse of C
(M
n
,...,
M
0
)withdelayτ
0
+···+τ
n
, then one can retrieve plaintexts from ciphertexts.
For general nonlinear finite automata, the proof of Theorem 1.4.4 provides
an inversion algorithm which requires computing each output for each state
and for each input of length τ
0
+ ···+ τ
n
+ 1. For a state, the computing
amount is O(q
m(τ
0
+···+τ
n
)
)(O(2
160
)forn =1,q =2,m =8,τ
0
+ τ
1
= 20).
Therefore, this method is impractical for moderate τ
0
+ ···+ τ
n
.
Similarly, if one can find a finite automaton M
∗
of which C
(M
n
,...,M
0
)
is a weak inverse with delay τ
0
+ ···+ τ
n
, then one can forge signatures for
messages. For general nonlinear finite automata, in Sect. 6.5 of Chap. 6 an
inversion algorithm is provided, which requires computing an input-tree with
level τ
0
+···+τ
n
for each state and each output of length τ
0
+···+τ
n
+1. So this
method spends more computing time and storage amount than the method
mentioned in the preceding paragraph. We prefer to construct an original
weak inverse of a finite automaton by means of constructing a weak inverse
of the finite automaton based on mutual invertibility, see Theorem 2.2.1.
9.5.2 Inversion by Decomposing Finite Automata
From the finite automaton C
(M
n
,...,M
0
)inapublickeyofFAPKC,ifone
can feasibly find finite automata
¯
M
n
, ...,
¯
M
0
so that C
(M
n
, ..., M
0
)=
C
(
¯
M
n
, ...,
¯
M
0
) and a weak inverse finite automaton of
¯
M
i
can be feasibly
constructed for each j,0 j n, then a weak inverse finite automaton
of C
(M
n
,...,M
0
) can be feasibly constructed. No feasible decomposition
method is known.
In some special cases, for example, in the example of FAPKC mentioned
in Sect. 9.3, if M
0
is linear (i.e., B
j
=0forj =0, 1,...,r
0
− 1), then
decomposing C
(M
1
,M
0
) is reduced to factorizing the matrix polynomial
¯
C(z)=
r
0
+r
1
j=0
[ C
j
,C
j
] z
j
,
where C
r
0
+r
1
−1
= C
r
0
+r
1
=0.If
¯
C(z)=
¯
B(z)
¯
F (z), then C
(M
1
, M
0
)=
C
(
¯
M
1
,
¯
M
0
), where
¯
M
0
is defined by
y
i
=
t
0
j=1
A
j
y
i−j
⊕
¯r
0
j=0
¯
B
j
x
i−j
,
i =0, 1,...,
¯
M
1
is defined by
366 9. Finite Automaton Public Key Cryptosystems
x
i
=
¯r
1
j=0
¯
F
j
x
i−j
⊕
¯r
1
j=0
¯
F
j
t(x
i−j
,x
i−j−1
,x
i−j−2
),
i =0, 1,...,
¯
B(z)=
¯r
0
j=0
¯
B
j
z
j
,and
¯
F (z)=
¯r
1
j=0
[
¯
F
j
,
¯
F
j
]z
j
.Thusaweakinversefinite
automaton of C
(M
1
,M
0
) can be feasibly found whenever a weak inverse
finite automaton of
¯
M
1
can be feasibly constructed.
Although polynomial time algorithms for factorization of polynomials over
GF (q) are existent, no feasible algorithm is known for factorizing matrix
polynomials over GF (q). Some specific factorizing algorithms of matrix poly-
nomials over GF (q) are known, such as factorization by linear R
a
R
b
trans-
formation and factorization by reducing canonical diagonal form for matrix
polynomials. But those specific factorizations never lead to breaking the key
except the weak key.
Let F be a finite field. H(z)inM
m,n
(F [z]) is said to be linearly primitive,
if for any H
1
(z)inM
m,m
(F [z]) with rank m and any H
2
(z)inM
m,n
(F [z]),
H(z)=H
1
(z)H
2
(z) implies H
1
(z) ∈ GL
m
(F [z]).
H(z)inM
m,n
(F [z]) is said to be left-primitive, if for any positive integer
r,anyH
1
(z)inM
m,r
(F [z]) with rank r and any H
2
(z)inM
r,n
(F [z]), H(z)=
H
1
(z)H
2
(z) implies that the rank of H
1
(0) is r.
Two factorizations A(z)=G(z)H(z)andA(z)=G
(z)H
(z)areequiv-
alent, if there is an invertible matrix polynomial R(z) such that G
(z)=
G(z)R(z)
−1
and H
(z)=R(z)H(z).
It is known that the linearly primitive factorizations of A(z)andthe
derived factorizations of type 1 by canonical diagonal matrix polynomial of
A(z) are coincided with each other and unique under equivalence and that
the left-primitive factorizations of A(z), the derived factorizations by linear
R
a
R
b
transformations of A(z) and the derived factorizations of type 2 by
canonical diagonal matrix polynomial of A(z) are coincided with each other
and unique under equivalence. No other algorithm to give linearly primitive
factorization or left-primitive factorization is known except ones by reducing
canonical diagonal form and by linear R
a
R
b
transformation.
9.5.3 Chosen Plaintext Attack
A chosen plaintext attack for FAPKC is reduced to the problem of solving
a nonlinear system of equations over GF (q). We explain the claim for the
example in Sect. 9.3.
Since the public key is available for anyone, one can encrypt any plain-
text x
0
x
1
...x
n
and obtain corresponding ciphertext y
0
y
1
...y
n+τ
0
+τ
1
using
C
(M
1
,M
0
) and its initial state s
e
. Suppose that s
e
is equivalent to the state
9.5 Security 367
s
1
,s
0
of C(M
1
,M
0
). Let x
0
x
1
...x
n
be the output of M
1
for the input
x
0
x
1
...x
n
on the state s
1
.Thenwehave
x
0
...x
n−τ
0
= λ
∗
0
(x
−1
,...,x
−r
0
,y
τ
0
−1
,...,y
−t
0
,y
τ
0
...y
n
)
for some x
−1
,...,x
−r
0
and y
−1
,...,y
−t
0
. It follows that
r
1
j=0
F
j
x
i−j
⊕
r
1
−2
j=0
F
j
t(x
i−j
,x
i−j−1
,x
i−j−2
)
=
r
0
j=1
A
∗
j
x
i−j
⊕
r
0
−1
j=1
A
∗∗
j
t
(x
i−j
,x
i−j−1
) ⊕
t
0
+τ
0
j=0
B
∗
j
y
i+τ
0
−j
, (9.19)
i =0, 1,...,n− τ
0
,
where s
1
= x
−1
,...,x
−r
1
. In (9.19), values of x
i
and y
i
are known, and
unknown variables are F
j
’s, F
j
’s, A
∗
j
’s, A
∗∗
j
’s, B
∗
j
’s, and x
j
’s. In the case of
r
0
> 0, (9.19) is nonlinear in essential. Finding out M
1
and M
∗
0
by solving
the system of equations seems difficult, even if M
∗
0
is linear.
9.5.4 Exhausting Search and Stochastic Search
Exhausting Search Attack
Since the encryption algorithm is known for anyone, one may guess possible
plaintexts and can encrypt them. When the result of encrypting some guessed
plaintext coincides with the ciphertext, the guessed plaintext is the virtual
plaintext. Notice that the public key cryptosystem based finite automata is
sequential. Its block length m is small in order to provide a small key size.
But small block length causes the cryptosystem fragile for the divide and
conquer attack. In fact, the guess process can be reduced to guessing a piece
of plaintext of length τ
0
+ ···+ τ
n
+ 1 and deciding its first digit. That is,
guess a value of the first τ
0
+ ···+ τ
n
+ 1 digits of the plaintext first, and
then encrypt it using the public key and compare the result with the first
τ
0
+···+ τ
n
+1 digits of the virtual ciphertext. If they coincide, then the first
digit of the guessed plaintext is indeed the first digit of the virtual plaintext.
Repeat this process for guessing next digit of the plaintext, and so on. In
Sect. 2.3 of Chap. 2, Algorithm 1 is such an exhausting search algorithm for
encryption, where M is the finite automaton C
(M
n
,...,M
1
,M
0
) in a user’s
public key, and s is a state of M of which part of components is given by
s
out
e
and s
in
e
in the public key. In the case of the example in Sect. 9.3, s is
s
out
e
,s
in
e
.
Formulae of the search amounts in average case and in worse case are
deduced in Sect. 2.3 of Chap. 2 for a finite automaton M, which is equivalent
368 9. Finite Automaton Public Key Cryptosystems
to C(
¯
M
0
, D
X,r
1
,
¯
M
1
, D
X,r
2
,
¯
M
2
, ...,
¯
M
τ−1
, D
X,r
τ
,
¯
M
τ
), where 0 r
1
r
2
··· r
τ
m,
¯
M
i
is a weakly invertible finite automaton with delay 0
for i =0, 1,...,τ,and
¯
M
i
is (m−r
i+1
)-preservable, i =1,...,τ−1. We point
out that a finite automaton M = C
(M
1
,M
0
) satisfies the above condition,
where M
0
is a weakly invertible finite automaton with delay 0, and M
1
is
generated by linear R
a
R
b
transformation method. A formula of the lower
bound for the search amounts in average case is also given there, that is,
(l +1− τ)
1+
τ
j=2
q
r
j
+···+r
τ
/2.
According to the formula, in the case of the example, (l+1−τ)(2
r
2
+···+r
τ
−1
+
2
r
3
+···+r
τ
−1
) is a lower bound for the search amounts in average case, taking
l = τ = 15, which is equal to 2
58
+2
56
whenever r
1
, ..., r
15
are1,2,2,3,3,
3, 4, 4, 4, 5, 5, 5, 6, 6, 7, respectively, or 2
67
+2
65
whenever r
1
, ..., r
15
are
1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, respectively.
Similarly, to forge a signature of a given message, one may guess a pos-
sible signature first, and then computes using the public key for verification
and checks whether the computing result coincides with the message or not.
Repeat this process until a coincident one is met. An attacker may adopt
an exhausting search attack to forge a signature for a given message using a
search algorithm like the following.
Algorithm 3
Input : a message y
0
y
1
...y
l
.
Output : the signature x
0
x
1
...x
τ+l
which satisfies
y
0
y
1
...y
l
= λ(s
x
0
,...,x
τ −1
,x
τ
...x
τ+l
),
where s
x
0
,...,x
τ −1
is a state y
−1
,...,y
−t
0
, x
τ−1
, ..., x
τ−r
determined
by s
out
v
= y
−1
,...,y
−t
0
and s
in
v
= x
−1
,..., x
−r+τ
in the public
key and x
0
,...,x
τ−1
.
Procedure :
1. Guess the prefix of length τ of the signature.
1.1. Take X
τ
= X
τ
.
1.2. If X
τ
= ∅, then choose an element in it as x
0
,...,x
τ−1
, delete
this element from it and go to Step 2.1; otherwise (impossibly
occurs) stop.
2. Guess the main part of the signature.
2.1. Set i =0ands
= s
x
0
,...,x
τ −1
.
2.2. Set X
s
,x
τ
x
τ +1
...x
τ +i−1
= {x|x ∈ X, y
i
= λ(δ(s
, x
τ
x
τ+1
...
x
τ+i−1
), x)} in the case of i>0, or {x|x ∈ X, y
i
= λ(s
,x)}
otherwise.
9.5 Security 369
2.3. If X
s
,x
τ
x
τ +1
...x
τ +i−1
= ∅, then choose an element in it as x
τ+i
,
delete this element from it, increase i by 1 and go to Step 2.4;
otherwise, decrease i by 1 and go to Step 2.5.
2.4. If i>l, then output x
0
...x
τ+l
as a signature x
0
...x
τ+l
and
stop; otherwise, go to Step 2.2.
2.5. If i 0, go to Step 2.3; otherwise, go to Step 1.2.
An execution of Algorithm 3 consists of two phases. The first phase is
to search several such initial states, say s
= s
x
0
...x
τ −1
, for some values of
x
0
,...,x
τ−1
∈ X with y
0
y
1
...y
l
∈ W
M
l+1,s
. The second phase is to search an
initial state s
= s
x
0
...x
τ −1
with y
0
y
1
...y
l
∈ W
M
l+1,s
.Weevaluatethesearch
amount for the second phase. We point out that the phase 2 and Algorithm 1
in Sect. 2.3 of Chap. 2 are the same except the subscripts of x
i
in Algorithm 3
with offset τ . Thus for a valid x
0
...x
τ−1
, we can evaluate the search amount
of the phase 2 in Algorithm 3 as well as to evaluate the search amount of
Algorithm 1. Taking account of the search amount of the first phase of an
execution of Algorithm 3, the complexity for signature is a little more than
the complexity for encryption.
By the way, the initial state for encryption may be variable, whenever
M
0
= X, Y, S
0
,δ
0
,λ
0
is defined by
y
i
=
t
0
j=1
A
j
y
i−j
+ f
0
(x
i
,...,x
i−r
0
),
i =0, 1,...
and M
∗
0
= Y,X,S
∗
0
,δ
∗
0
,λ
∗
0
is defined by
x
i
= f
∗
0
(x
i−1
,...,x
i−r
0
)+
t
0
+τ
0
j=0
B
∗
j
y
i−j
,
i =0, 1,...,
where f
0
(0,...,0) = f
∗
0
(0,...,0) = 0. Suppose that ¯y
−1
, ...,¯y
−t
0
satisfy the
condition
λ
∗
0
(0,...,0, 0,...,0, ¯y
−1
,...,¯y
−t
0
, 00 ...)=00... (9.20)
Let
λ
0
(¯y
−1
,...,¯y
−t
0
, 0,...,0, , 00 ...)=¯y
0
¯y
1
... (9.21)
From PI(M
0
,M
∗
0
,τ
0
), this yields
λ
∗
0
(0,...,0, ¯y
τ
0
−1
,...,¯y
0
, ¯y
−1
,...,¯y
−t
0
, ¯y
τ
0
¯y
τ
0
+1
...)=00...
370 9. Finite Automaton Public Key Cryptosystems
Subtracting two sides of (9.20) from two sides of the above equation, from
the definition of M
∗
0
,wehave
λ
∗
0
(0,...,0, ¯y
τ
0
−1
,...,¯y
0
, 0,...,0, ¯y
τ
0
¯y
τ
0
+1
...)=00... (9.22)
Let
λ
0
(y
−1
,...,y
−t
0
,x
−1
,...,x
−r
0
,x
0
x
1
...)=y
0
y
1
..., (9.23)
and y
i
= y
i
+¯y
i
, i =0, 1,... Adding two sides of (9.21) to two sides of (9.23),
from the definition of M
0
,wehave
λ
0
(y
−1
+¯y
−1
,...,y
−t
0
+¯y
−t
0
,x
−1
,...,x
−r
0
,x
0
x
1
...)=y
0
y
1
...
On the other hand, from PI(M
0
,M
∗
0
,τ
0
), (9.23) yields
λ
∗
0
(x
−1
,...,x
−r
0
,y
τ
0
−1
,...,y
0
,y
−1
,...,y
−t
0
,y
τ
0
y
τ
0
+1
...)=x
0
x
1
...
Adding two sides of (9.22) to two sides of the above equation, from the
definition of M
∗
0
,wehave
λ
∗
0
(x
−1
,...,x
−r
0
,y
τ
0
−1
,...,y
0
,y
−1
,...,y
−t
0
,y
τ
0
y
τ
0
+1
...)=x
0
x
1
...
We conclude that an offset ¯y
−1
,...,¯y
−t
0
which satisfies (9.20) may be added
to the output part of the initial state for encryption.
The equation (9.20) is equivalent to
⎡
⎢
⎢
⎢
⎢
⎣
B
∗
τ
0
+1
B
∗
τ
0
+2
... B
∗
τ
0
+t
0
−1
B
∗
τ
0
+t
0
B
∗
τ
0
+2
B
∗
τ
0
+3
... B
∗
τ
0
+t
0
0
... ... ... ... ...
B
∗
τ
0
+t
0
−1
B
∗
τ
0
+t
0
... 00
B
∗
τ
0
+t
0
0 ... 00
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
¯y
−1
¯y
−2
.
.
.
¯y
−t
0
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
(9.24)
which can be further reduced by row transformation. For example, in the
example of FAPKC given in Sect. 9.3, the equation (9.24) can be further
reduced to
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
01101011 00010001 01111111
00010001 01111111 00000000
10111111 00110100 00000000
01010000 00010011 00000000
01111111 00000000 00000000
00110100 00000000 00000000
00010011 00000000 00000000
00000010 00000000 00000000
10001100 00000000 00000000
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎣
¯y
−1
¯y
−2
¯y
−3
⎤
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
0
0
0
0
0
0
0
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
There are 2
24−1−3−5
=2
15
different solutions of [¯y
−1
, ¯y
−2
, ¯y
−3
]. This increases
the complexity of the exhause search for encryption, because the virtual initial
state for encryption is unknown.
9.5 Security 371
Stochastic search attack
The above attack by exhausting search is a deterministic algorithm. It can be
modified to a stochastic one. Algorithm 2 in Sect. 2.3 of Chap. 2 is a stochastic
search algorithm to retrieve a plaintext x
0
x
1
...x
l
from a ciphertext y
0
y
1
...y
l
(= λ(s, x
0
x
1
...x
l
)), where M is the finite automaton C
(M
n
, ..., M
1
, M
0
)
in a user’s public key, and s is a state of M in which partial components are
given by s
out
e
and s
in
e
in the public key. In the case of the example in Sect. 9.3,
s is s
out
e
,s
in
e
.
A formula of the successful probability is deduced in Sect. 2.3 of Chap. 2
for a finite automaton M which is equivalent to C(
¯
M
0
, D
X,r
1
,
¯
M
1
, D
X,r
2
,
¯
M
2
, ...,
¯
M
τ−1
, D
X,r
τ
,
¯
M
τ
), where 0 r
1
r
2
··· r
τ
m,
¯
M
i
is a
weakly invertible finite automaton with delay 0 for i =0, 1,...,τ,and
¯
M
i
is (m − r
i+1
)-preservable for i =1,...,τ − 1. According to the formula, in
the case of the example, the probability of successfully choosing x
0
,...,x
l
of
Algorithm 2 is 2
min(l,τ −1)
i=0
r
τ −i
−(l+1)r
τ
. Taking l = τ = 15, the probability
is 2
−52
whenever r
1
, ..., r
15
are1,2,2,3,3,3,4,4,4,5,5,5,6,6,7,
respectively, or 2
−43
whenever r
1
, ..., r
15
are1,2,3,4,4,4,5,5,5,5,6,6,
6, 6, 7, respectively.
Similar to Algorithm 2, an attacker may adopt a stochastic search attack
to forge a signature for a given message using a stochastic search algorithm
like the following.
Algorithm 4
Input : a message y
0
y
1
...y
l
.
Output : the signature x
0
x
1
...x
τ+l
which satisfies
y
0
y
1
...y
l
= λ(s
x
0
,...,x
τ −1
,x
τ
...x
τ+l
),
where s
x
0
,...,x
τ −1
is a state y
−1
,...,y
−t
0
, x
τ−1
, ..., x
τ−r
determined
by s
out
v
= y
−1
,...,y
−t
0
and s
in
v
= x
−1
,..., x
−r+τ
in the public
key and x
0
,...,x
τ−1
.
Procedure :
1. Guess the prefix of length τ of the signature.
Choose randomly x
0
,...,x
τ−1
∈ X.
2. Guess the main part of the signature.
2.1. Set i =0ands
= s
x
0
,...,x
τ −1
.
2.2. Set X
s
,x
τ
x
τ +1
...x
τ +i−1
= {x|x ∈ X, y
i
= λ(δ(s
,x
τ
x
τ+1
...
x
τ+i−1
), x)} inthecaseofi>0, or {x|x ∈ X, y
i
= λ(s
,x)}
otherwise.
2.3. If X
s
,x
τ
x
τ +1
...x
τ +i−1
= ∅, then choose randomly an element in
it as x
τ+i
,increasei by 1 and go to Step 2.4; otherwise, prompt
a failure information and stop.
372 9. Finite Automaton Public Key Cryptosystems
2.4. If i>l, then output x
0
...x
τ+l
as a signature x
0
...x
τ+l
and
stop; otherwise, go to Step 2.2.
Let p
y
0
...y
l
ix
be the probability of successfully choosing an initial part
x
0
...x
τ−1
in Step 1 of Algorithm 4. Let X
y
0
...y
l
valid
= {x
0
...x
τ−1
|
I
M
y
0
y
1
...y
l
,s
x
0
,...,x
τ −1
= ∅}.Thenp
y
0
...y
l
ix
= |X
y
0
...y
l
valid
|/q
mτ
.
We point out that the phase 2 and Algorithm 2 in Sect. 2.3 of Chap. 2
are the same except the subscripts of x
i
in Algorithm 4 with offset τ and
replacing s by s
. From Theorem 2.3.8, the probability of successfully execut-
ing Algorithm 4 is p
y
0
...y
l
ix
q
min(l,τ −1)
i=0
r
τ −i
−(l+1)r
τ
, for a finite automaton M
which is equivalent to C(
¯
M
0
,D
X,r
1
,
¯
M
1
,D
X,r
2
,
¯
M
2
,...,
¯
M
τ−1
,D
X,r
τ
,
¯
M
τ
),
where 0 r
1
r
2
··· r
τ
m,
¯
M
i
is weakly invertible finite au-
tomata with delay 0 for i =0, 1,...,τ,and
¯
M
i
is (m − r
i+1
)-preservable for
i =1,...,τ − 1.
9.6 Generalized Algorithms
9.6.1 Some Theoretical Results
In this section, we deal with pseudo-memory finite automata instead of mem-
ory finite automata. Notice that a generation method of pseudo-memory finite
automata with invertibility is discussed in Chap. 3.
Let M = X, Y, (U
(1)
)
p
1
+1
×···×(U
(c)
)
p
c
+1
× X
r
,δ,λ be a finite au-
tomaton defined by
y
i
= f(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)),
u
(j)
i+1
= g
j
(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)),
j =1,...,c, i=0, 1,...
Let M
= Y,Z, Z
k
× (W
(1)
)
n
1
+1
×···×(W
(d)
)
n
d
+1
× Y
h
,δ
,λ
be a finite
automaton defined by
z
i
= ϕ(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),y(i, h +1)),
w
(j)
i+1
= ψ
j
(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),y(i, h +1)),
j =1,...,d, i=0, 1,...
From M and M
, a finite automaton X, Z, Z
k
× (W
(1)
)
n
1
+1
×···×
(W
(d)
)
n
d
+1
× (U
(1)
)
h+p
1
+1
×···×(U
(c)
)
h+p
c
+1
× X
h+r
,δ
,λ
is defined
by
9.6 Generalized Algorithms 373
z
i
= ϕ(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),
f(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)), ...,
f(u
(1)
(i − h, p
1
+1),...,u
(c)
(i − h, p
c
+1),x(i − h, r + 1))),
w
(j)
i+1
= ψ
j
(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),
f(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)), ..., (9.25)
f(u
(1)
(i − h, p
1
+1),...,u
(c)
(i − h, p
c
+1),x(i − h, r + 1))),
j =1,...,d,
u
(j)
i+1
= g
j
(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)),
j =1,...,c,
i =0, 1,...
We still use C
(M,M
) to denote this finite automaton in this section.
Theorem 9.6.1. For any state
s
= z(−1,k),w
(1)
(0,n
1
+1),...,w
(d)
(0,n
d
+1),
u
(1)
(0,h+ p
1
+1),...,u
(c)
(0,h+ p
c
+1),x(−1,h+ r)
of C
(M,M
),let
s = u
(1)
(0,p
1
+1),...,u
(c)
(0,p
c
+1),x(−1,r),
s
= z(−1,k),w
(1)
(0,n
1
+1),...,w
(d)
(0,n
d
+1),y(−1,h),
where
y
i
= f(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)), (9.26)
i = −h,...,−1.
Then the state s, s
of C(M, M
) and s
are equivalent.
Proof. Taking arbitrary x
0
,x
1
,...∈ X,let
z
0
z
1
...= λ
(s
,x
0
x
1
...).
Then there exist w
(1)
(i), ..., w
(d)
(i), u
(1)
(i), ..., u
(c)
(i), i =1, 2,... such
that (9.25) holds. Denoting
y
i
= f(u
(1)
(i, p
1
+1),...,u
(c)
(i, p
c
+1),x(i, r +1)),i=0, 1,... (9.27)
and using (9.26), (9.25) yields
z
i
= ϕ(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),y(i, h +1)),
w
(j)
i+1
= ψ
j
(z(i − 1,k),w
(1)
(i, n
1
+1),...,w
(d)
(i, n
d
+1),y(i, h +1)),
j =1,...,d, i=0, 1,...
374 9. Finite Automaton Public Key Cryptosystems
From the definition of M
,wehave
z
0
z
1
...= λ
(s
,y
0
y
1
...).
Using (9.25) and (9.27), from the definition of M,weobtain
y
0
y
1
...= λ(s, x
0
x
1
...).
Thus
λ
(s
,x
0
x
1
...)=z
0
z
1
...= λ
(s
,λ(s, x
0
x
1
...)) = λ
(s, s
,x
0
x
1
...),
where λ
is the output function of C(M,M
). Therefore, s, s
and s
are
equivalent.
Let M = V,Z,Z
k
× W
n+1
× V
h
,δ,λ be a finite automaton, where
λ(z(−1,k),w(0,n+1),v(−1,h),v
0
)=z
0
,
δ(z(−1,k),w(0,n+1),v(−1,h),v
0
)=z(0,k),w(1,n+1),v(0,h),
z
0
= ϕ(z(−1,k),w(0,n+1),v(0,h+1)),
w
1
= ψ(z(−1,k),w(0,n+1),v(0,h+1)).
Let M
∗
= Z, V, V
h
× W
n+1
× Z
τ+k
,δ
∗
,λ
∗
be a finite automaton, where
λ
∗
(v(−1,h),w(0,n+1),z(−1,τ + k),z
0
)=v
0
,
δ
∗
(v(−1,h),w(0,n+1),z(−1,τ + k),z
0
)
= v(0,h),w(1,n+1),z(0,τ + k),
v
0
= ϕ
∗
τ
(v(−1,h),w(0,n+1),z(0,τ + k +1)),
w
1
= ψ(z(−τ − 1,k),w(0,n+1),v(0,h+1)).
We use PI
1
(M,M
∗
,τ) to denote the following condition: for any state
s
0
= z(−1,k),w(0,n+1),v(−1,h)
of M and any v
0
,v
1
,...∈ V ,if
z
0
z
1
...= λ(s
0
,v
0
v
1
...),
then
v
0
v
1
...= λ
∗
(s
∗
τ
,z
τ
z
τ+1
...),
where
s
∗
τ
= v(−1,h),w(0,n+1),z(τ − 1,τ + k).
We use PI
2
(M
∗
,M,τ) to denote the following condition: for any state