Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
9.6 Generalized Algorithms 385
x
(i)
0
x
(i)
1
... (9.55)
= λ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(τ
i
− 1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...)
for i =1,...,n− 1.
Proof.Lets
i
= u
(i)
(0,p
i
+1),x
(i)
(−1,r
i
) for i =1,...,n − 1, and
s
i
= u
(i+1)
(0,p
i+1
+1), u
(i+2)
(0,p
i+1,i+2
+1), ..., u
(n)
(0,p
i+1,n
+1),
x
(n)
(−1,r
i+1,n
) for i =0, 1,...,n− 1. Suppose that (9.53) holds. We prove
by induction on i that
x
(i−1)
0
x
(i−1)
1
...= λ
i,n
(s
i−1
,x
(n)
0
x
(n)
1
...) (9.56)
holds for any i,1 i n. The case of i = 1 is trivial because of s = s
0
.
Suppose that (9.56) holds for i and i n − 1. We prove (9.56) holds for i +1,
that is,
x
(i)
0
x
(i)
1
...= λ
i+1,n
(s
i
,x
(n)
0
x
(n)
1
...). (9.57)
Since (9.52) holds for c = i + 1, applying Theorem 9.6.1, the state s
i−1
of C
(M
n
, ..., M
i
) and the state s
i
,s
i
of C(C
(M
n
,...,M
i+1
),M
i
)are
equivalent. Letting
¯x
(i)
0
¯x
(i)
1
...= λ
i+1,n
(s
i
,x
(n)
0
x
(n)
1
...), (9.58)
from (9.56), we have
x
(i−1)
0
x
(i−1)
1
...= λ
i
(s
i
, ¯x
(i)
0
¯x
(i)
1
...).
Since PI
1
(M
i
,M
∗
i
,τ
i
) holds, the above equation deduces
¯x
(i)
0
¯x
(i)
1
...= λ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(τ
i
−1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...).
From (9.55), it follows immediately that ¯x
(i)
0
¯x
(i)
1
... = x
(i)
0
x
(i)
1
... Therefore,
(9.58) implies (9.57).
Since PI
1
(M
n
,M
∗
n
,τ
n
) holds, from the case i = n of (9.56), (9.54) holds.
Theorem 9.6.4. Assume that PI
1
(M
i
,M
∗
i
,τ
i
) holds for any i, 0 i n.
Let s = y(−1,t
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
) be a state of C
(M
n
, ..., M
1
, M
0
). Assume that (9.52) holds
for c =1,...,n and
y
0
y
1
...= λ
0,n
(s, x
(n)
0
x
(n)
1
...). (9.59)
If
x
(0)
0
x
(0)
1
... (9.60)
= λ
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(τ
0
− 1,τ
0
+ t
0
),y
τ
0
y
τ
0
+1
...)
holds and (9.55) holds for i =1,...,n− 1,then(9.54) holds.
386 9. Finite Automaton Public Key Cryptosystems
Proof.Lets
0
= y(−1,t
0
), u
(0)
(0, p
0
+1), x
(0)
(−1,r
0
) and s
0
=
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
).Since
(9.52) holds for c =1,thestates of C
(M
n
,...,M
1
,M
0
) and the state s
0
,s
0
of C(C
(M
n
,..., M
1
), M
0
) are equivalent. Letting
¯x
(0)
0
¯x
(0)
1
...= λ
1,n
(s
0
,x
(n)
0
x
(n)
1
...), (9.61)
since (9.59) holds, we have
y
0
y
1
...= λ
0
(s
0
, ¯x
(0)
0
¯x
(0)
1
...).
From PI
1
(M
0
,M
∗
0
,τ
0
), it follows immediately that
¯x
(0)
0
¯x
(0)
1
...= λ
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(τ
0
− 1,τ
0
+ t
0
),y
τ
0
y
τ
0
+1
...).
Using (9.60), this yields ¯x
(0)
0
¯x
(0)
1
...= x
(0)
0
x
(0)
1
... From (9.61), we obtain
x
(0)
0
x
(0)
1
...= λ
1,n
(s
0
,x
(n)
0
x
(n)
1
...).
From Lemma 9.6.1, we obtain (9.54).
Theorem 9.6.5. Assume that PI
2
(M
∗
0
,M
0
,τ
0
) holds and PI
1
(M
i
,M
∗
i
,τ
i
)
holds for any i, 1 i n.Lets = 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
) be a state of C
(M
n
,...,M
1
,M
∗
0
).
Assume that
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.62)
for c =1,...,n and
y
0
y
1
...= λ
0,n
(s, x
(n)
0
x
(n)
1
...), (9.63)
where r
0
= τ
0
+ t
0
, r
i
= r
i
, i =1,...,n.If
x
(0)
0
x
(0)
1
...= λ
0
(x
(0)
(−1,t
0
),u
(0)
(τ
0
,p
0
+1),y(τ
0
− 1,r
0
),y
τ
0
y
τ
0
+1
...),
u
(0)
j+1
= g
0
(x
(0)
(j − τ
0
− 1,t
0
),u
(0)
(j, p
0
+1),y(j, r
0
+1)), (9.64)
j =0, 1,...,τ
0
− 1
hold and (9.55) holds for i =1,...,n− 1,then(9.54) holds.
Proof.Lets
0
= y(−1,r
0
), u
(0)
(0,p
0
+1), x
(0)
(−1,τ
0
+ t
0
) and s
0
=
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
).Since
(9.62) holds for c =1,thestates of C
(M
n
,...,M
1
,M
∗
0
) and the state s
0
,s
0
9.6 Generalized Algorithms 387
of C(C
(M
n
,..., M
1
), M
∗
0
) are equivalent. Letting (9.61), from (9.63), we
have
y
0
y
1
...= λ
∗
0
(s
0
, ¯x
(0)
0
¯x
(0)
1
...).
Since PI
2
(M
∗
0
,M
0
,τ
0
) holds, it follows immediately that
¯x
(0)
0
¯x
(0)
1
...= λ
0
(x
(0)
(−1,t
0
),u
(0)
(τ
0
,p
0
+1),y(τ
0
− 1,r
0
),y
τ
0
y
τ
0
+1
...).
From (9.64), this yields ¯x
(0)
0
¯x
(0)
1
...= x
(0)
0
x
(0)
1
... Therefore, (9.61) implies
x
(0)
0
x
(0)
1
...= λ
1,n
(s
0
,x
(n)
0
x
(n)
1
...).
From Lemma 9.6.1, we obtain (9.54).
9.6.2 Two Algorithms
FA P KC 3 x- n
Using the results of the preceding subsection, we now generalize the so-called
basic algorithm of the public key cryptosysytem based on finite automata in
Sect. 9.2 to two public key cryptosystems so that component finite automata
of the compound finite automata in public keys are finite automata with
auxiliary state discussed in the preceding subsection. The two cryptosystems
are designed for both encryption and signature. Therefore, we require that
all input alphabets and all output alphabets have the same dimension, say
m.
We first propose a cryptosystem relied upon Theorem 9.6.2 and Theo-
rem 9.6.4. Let n 1. Choose a common q and m for all users. Let all the
alphabets X
0
,...,X
n
and Y be the same column vector space over GF (q)of
dimension m.
A user, say A, choose his/her own public key and private key as follows.
(a) Construct pseudo-memory finite automata M
i
, M
∗
i
, i =0, 1,...,nde-
fined by (9.30), (9.28), (9.31) and (9.29), respectively, which satisfy conditions
PI
1
(M
i
,M
∗
i
,τ
i
)andPI
2
(M
∗
i
,M
i
,τ
i
)forsomeτ
i
r
i
, i =0, 1,...,n.
(b) Construct the finite automaton C
(M
n
,...,M
1
,M
0
)=X, Y , S, δ
0,n
,
λ
0,n
from M
0
, M
1
, ..., M
n
.
(c) Let b
−1
=max{τ
0
, −
i−1
j=0
r
j
+
i
j=0
τ
j
,i=1,...,n},andb
i
= b
i−1
+
r
i
− τ
i
, i =0, 1,...,n. Choose arbitrary x
(0)
−b
0
,...,x
(0)
−1
∈ X
0
.Foreachi,
1 i n, choose an arbitrary state
s
(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
)
of M
∗
i
. Compute
388 9. Finite Automaton Public Key Cryptosystems
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)),
i =1,...,n, j = −b
i−1
,...,−1.
Choose an arbitrary state s
(0)∗
0
= x
(0)
(−1,r
0
), u
(0)
(0,p
0
+1), y(−1,τ
0
+ t
0
)
of M
∗
0
. Take s
(i)
s
= s
(i)∗
0
, i =0, 1,...,n, s
out
v
= y
−1
,...,y
−τ
0
−t
0
, s
aux,i
v
=
u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
(i)
, i =0, 1,...,n, s
in
v
= x
(n)
−1
,...,x
(n)
−r
(n)
,where
r
(n)
=max(r
n
,r
n−1,n
− τ
n,n
,...,r
1,n
− τ
2,n
,r
0,n
− τ
1,n
),
p
(0)
= p
0
,
p
(i)
=max(p
i
,p
i−1,i
− τ
i,i
,...,p
1,i
− τ
2,i
,p
0,i
− τ
1,i
),i=1,...,n.
(d) Choose an arbitrary state s
e
= y(−1,t
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
) of C
(M
n
,...,M
1
,M
0
). Compute
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)),
c =1, 2,...,n, j = −r
c−1
,...,−1.
Take s
(0),in
d
= y
−1
,...,y
−t
0
, s
(i),aux
d
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
i
and s
(i),out
d
=
x
(i)
−1
,..., x
(i)
−r
i
, i =0, 1,...,n.
1
(e) The public key of the user A is
C
(M
n
,...,M
1
,M
0
),s
out
v
,s
in
v
,s
aux,0
v
,...,s
aux,n
v
,s
e
,τ
0,n
.
The private key of the user A is
M
∗
0
,...,M
∗
n
,s
(0)
s
,...,s
(n)
s
,s
(0),in
d
,s
(0),aux
d
,...,s
(n),aux
d
,
s
(0),out
d
,...,s
(n),out
d
,τ
0
,...,τ
n
.
Encryption Anyuser,sayB, wants to send a plaintext x
(n)
0
x
(n)
1
...x
(n)
l
to
a user A. B first suffixes any τ
0,n
digits, say x
(n)
l+1
...x
(n)
l+τ
0,n
, to the plaintext.
Then using C
(M
n
,...,M
1
,M
0
)ands
e
in A’s public key, B computes the
ciphertext y
0
y
1
... y
l+τ
0,n
as follows:
y
0
y
1
...y
l+τ
0,n
= λ
0,n
(s
e
,x
(n)
0
x
(n)
1
...x
(n)
l+τ
0,n
).
1
For the simplicity of symbolization, we use the same symbols y
−j
, u
(i)
j
, x
(i)
−j
in
(c) and in (d), but their intentions are different.
9.6 Generalized Algorithms 389
Decryption From the ciphertext y
0
y
1
...y
l+τ
0,n
, according to Theorem 9.6.4,
A can retrieve the plaintext x
(n)
0
x
(n)
1
...x
(n)
l
as follows. Using M
∗
0
,...,M
∗
n
,
s
(0),in
d
s
(i),aux
d
, s
(i),out
d
, i =0, 1,...,n in his/her private key, A computes
x
(0)
0
x
(0)
1
...x
(0)
l+τ
1,n
= λ
∗
0
(x
(0)
(−1,r
0
),u
(0)
(0,p
0
+1),y(τ
0
− 1,τ
0
+ t
0
),y
τ
0
y
τ
0
+1
...y
l+τ
0,n
)
and
x
(i)
0
x
(i)
1
...x
(i)
l+τ
i+1,n
= λ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(τ
i
−1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...x
(i−1)
l+τ
i,n
),
i =1,...,n,
where s
(0),in
d
= y
−1
,...,y
−t
0
, s
(i),aux
d
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
i
and s
(i),out
d
=
x
(i)
−1
, ..., x
(i)
−r
i
, i =0, 1,...,n.
Signature To sign a message y
0
y
1
...y
l
, the user A first suffixes any τ
0,n
dig-
its, say y
l+1
...y
l+τ
0,n
, to the message. Then using M
∗
0
, ..., M
∗
n
, s
(0)
s
,...,s
(n)
s
in his/her private key, A computes
x
(0)
0
x
(0)
1
...x
(0)
l+τ
0,n
= λ
∗
0
(s
(0)
s
,y
0
y
1
...y
l+τ
0,n
),
x
(i)
0
x
(i)
1
...x
(i)
l+τ
0,n
= λ
∗
i
(s
(i)
s
,x
(i−1)
0
x
(i−1)
1
...x
(i−1)
l+τ
0,n
),
i =1,...,n.
Then x
(n)
0
x
(n)
1
...x
(n)
l+τ
0,n
is a signature of y
0
y
1
...y
l
.
Validation Any user, say B, can verify the validity of the signature
x
(n)
0
x
(n)
1
... x
(n)
l+τ
0,n
as follows. Using C
(M
n
,...,M
1
,M
0
), s
out
v
,s
in
v
,s
aux,i
v
,
i =0, 1,...,n in A’s public key, B first computes
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,
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,
where s
out
v
= y
−1
,...,y
−τ
0
−t
0
, s
aux,i
v
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
(i)
, i =0, 1,...,n,
s
in
v
= x
(n)
−1
,...,x
(n)
−r
(n)
. Letting 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
), A then computes
390 9. Finite Automaton Public Key Cryptosystems
λ
0,n
(s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...x
(n)
l+τ
0,n
)
which would coincide with the message y
0
y
1
...y
l
from Theorem 9.6.2.
The special case of n = 1 of the above cryptosystem may be regarded
as a generation of the cryptsystem FAPKC3 (cf. [123]). The cryptosystem is
referred to as FAPKC3x-n.
FA P KC 4 x- n
Similar to FAPKC3x-n, we propose a cryptosystem relied upon Theorem 9.6.3
and Theorem 9.6.5. Let n 1. Choose a common q and m for all users. Let
all the alphabets X
0
,...,X
n
and Y be the same column vector space over
GF (q) of dimension m.
A user, say A, choose his/her own public key and private key as follows.
(a) Construct pseudo-memory finite automata M
i
, M
∗
i
, i =0, 1,...,nde-
fined by (9.30), (9.28), (9.31) and (9.29), respectively, which satisfy conditions
PI
1
(M
i
,M
∗
i
,τ
i
)andPI
2
(M
∗
i
,M
i
,τ
i
)forsomeτ
i
r
i
, i =0, 1,...,n.
(b) Construct the finite automaton C
(M
n
,...,M
1
,M
∗
0
)=X, Y, S
,δ
0,n
,
λ
0,n
from M
∗
0
, M
1
, ..., M
n
.
(c) Let b
−1
=max{0, −
i−1
j=0
r
j
+
i
j=0
τ
j
,i =1,...,n}, b
0
= b
−1
+ t
0
,
and b
i
= b
i−1
+ r
i
− τ
i
, i =1,...,n. Choose arbitrary x
(0)
−b
0
,...,x
(0)
−1
∈ X
0
.
For each i,1 i n, choose an arbitrary state s
(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
) of M
∗
i
. Compute
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))
i =1,...,n, j = −b
i−1
,...,−1.
Choose an arbitrary state s
(0)
0
= x
(0)
(−1,t
0
), u
(0)
(0,p
0
+1), y(−1,r
0
) of
M
0
. Take s
(0)
s
= s
(0)
0
, s
(i)
s
= s
(i)∗
0
, i =1,...,n, s
out
v
= y
−1
,...,y
−r
0
, s
aux,i
v
=
u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
(i)
, i =0, 1,...,n, s
in
v
= x
(n)
−1
,...,x
(n)
−r
(n)
,where
r
(n)
=max(r
n
,r
n−1,n
− τ
n,n
,...,r
1,n
− τ
2,n
,r
0,n
− τ
0,n
),
p
(0)
= p
0
,
p
(i)
=max(p
i
,p
i−1,i
− τ
i,i
,...,p
1,i
− τ
2,i
,p
0,i
− τ
0,i
),i=1,...,n.
9.6 Generalized Algorithms 391
(d) Choose an arbitrary state s
e
= 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
) of C
(M
n
,...,M
1
,M
∗
0
). Compute
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)),
c =1, 2,...,n, j = −r
c−1
,...,−1,
where r
0
= τ
0
+ t
0
, r
i
= r
i
, i =1,...,n. Take s
(0),in
d
= y
−1
,...,y
−r
0
,
s
(i),aux
d
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
i
, i =0, 1,...,n, s
(0),out
d
= x
(0)
−1
, ..., x
(0)
−τ
0
−t
0
,
and s
(i),out
d
= x
(i)
−1
, ..., x
(i)
−r
i
, i =1,...,n.
1
(e) The public key of the user A is
C
(M
n
,...,M
1
,M
∗
0
),s
out
v
,s
in
v
,s
aux,0
v
,...,s
aux,n
v
,s
e
,τ
0,n
.
The private key of the user A is
M
0
,M
∗
1
,...,M
∗
n
,s
(0)
s
,...,s
(n)
s
,s
(0),in
d
,s
(0),aux
d
,...,s
(n),aux
d
,
s
(0),out
d
,...,s
(n),out
d
,τ
0
,...,τ
n
.
Encryption Anyuser,sayB, wants to send a plaintext x
(n)
0
x
(n)
1
...x
(n)
l
to
a user A. B first suffixes any τ
0,n
digits, say x
(n)
l+1
...x
(n)
l+τ
0,n
, to the plaintext.
Then using C
(M
n
,...,M
1
,M
∗
0
)ands
e
in A’s public key, B computes the
ciphertext y
0
y
1
... y
l+τ
0,n
as follows:
y
0
y
1
...y
l+τ
0,n
= λ
0,n
(s
e
,x
(n)
0
x
(n)
1
...x
(n)
l+τ
0,n
).
Decryption From the ciphertext y
0
y
1
...y
l+τ
0,n
, according to Theorem 9.6.5,
A can retrieve the plaintext x
(n)
0
x
(n)
1
...x
(n)
l
as follows. Using M
0
, M
∗
1
,...,M
∗
n
,
s
(0),in
d
s
(i),aux
d
, s
(i),out
d
, i =0, 1,...,n in his/her private key, A computes
u
(0)
j+1
= g
0
(x
(0)
(j − τ
0
− 1,t
0
),u
(0)
(j, p
0
+1),y(j, r
0
+1)),j=0,...,τ
0
− 1,
x
(0)
0
x
(0)
1
...x
(0)
l+τ
1,n
= λ
0
(x
(0)
(−1,t
0
),u
(0)
(τ
0
,p
0
+1),y(τ
0
− 1,r
0
),y
τ
0
y
τ
0
+1
...y
l+τ
0,n
)
and
x
(i)
0
x
(i)
1
...x
(i)
l+τ
i+1,n
= λ
∗
i
(x
(i)
(−1,r
i
),u
(i)
(0,p
i
+1),x
(i−1)
(τ
i
−1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...x
(i−1)
l+τ
i,n
),
i =1,...,n,
where s
(0),in
d
= y
−1
,...,y
−r
0
, s
(i),aux
d
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
i
, i =0, 1,...,n,
s
(0),out
d
= x
(0)
−1
, ..., x
(0)
−τ
0
−t
0
and s
(i),out
d
= x
(i)
−1
, ..., x
(i)
−r
i
, i =1,...,n.
1
For the simplicity of symbolization, we use the same symbols y
−j
, u
(i)
j
, x
(i)
−j
in
(c) and in (d), but their intentions are different.
392 9. Finite Automaton Public Key Cryptosystems
Signature To sign a message y
0
y
1
...y
l
, the user A first suffixes any τ
0,n
digits, say y
l+1
... y
l+τ
0,n
, to the message. Then using M
0
, M
∗
1
, ..., M
∗
n
,
s
(0)
s
,...,s
(n)
s
in his/her private key, A computes
x
(0)
0
x
(0)
1
...x
(0)
l+τ
0,n
= λ
0
(s
(0)
s
,y
0
y
1
...y
l+τ
0,n
),
x
(i)
0
x
(i)
1
...x
(i)
l+τ
0,n
= λ
∗
i
(s
(i)
s
,x
(i−1)
0
x
(i−1)
1
...x
(i−1)
l+τ
0,n
),
i =1,...,n.
Then x
(n)
0
x
(n)
1
...x
(n)
l+τ
0,n
is a signature of y
0
y
1
...y
l
.
Validation Any user, say B, can verify the validity of the signature
x
(n)
0
x
(n)
1
... x
(n)
l+τ
0,n
as follows. Using C
(M
n
,...,M
1
,M
∗
0
), s
out
v
,s
in
v
,s
aux,i
v
,
i =0, 1,...,n in A’s public key, B first computes
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,
where s
aux,i
v
= u
(i)
0
,u
(i)
−1
,...,u
(i)
−p
(i)
, i =0, 1,...,n, s
in
v
= x
(n)
−1
,...,x
(n)
−r
(n)
.
Letting 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
), A then computes
λ
0,n
(s, x
(n)
τ
0,n
x
(n)
τ
0,n
+1
...x
(n)
l+τ
0,n
)
which would coincide with the message y
0
y
1
...y
l
from Theorem 9.6.3, where
s
out
v
= y
−1
,...,y
−r
0
.
The special case of n = 1 of the above cryptosystem may be regarded
as a generation of the cryptsystem FAPKC4 (cf. [125]). The cryptosystem is
referred to as FAPKC4x-n.
Historical Notes
Since introducing the concept of public key cryptosystems by Diffie and Hell-
man [32], many concrete block cryptosystems are proposed in [89, 74, 72,
34, 50, 76, 63, 90, 93, 1]. A sequential public key cryptosystem based on fi-
nite automata, referred to as FAPKC0, is given in [112] of which a public
key contains a compound finite automaton of an invertible linear (τ,τ)-order
memory finite automaton with delay τ and a weakly invertible nonlinear
input-memory finite automaton with delay 0. Two other schemes, referred to
as FAPKC1 and FAPKC2, are given in [113], where a public key for FAPKC1
Historical Notes 393
contains a compound finite automaton of an linear inverse τ-order input-
memory finite automaton with delay τ and a weakly invertible nonlinear
input-memory finite automaton with delay 0. Reference [26] first proves that
FAPKC0 is insecure in encryption. Reference [11] proves that FAPKC1 is
insecure in encryption, and proposes a modification using quasi-linear finite
automata, which is shown to be insecure in both encryption and signature
in [108]. From [107], FAPKC0 and FAPKC1 are insecure in both encryption
and signature. In [118] a method for generating a kind of nonlinear weakly in-
vertible finite automata is developed; then two schemes, called FAPKC3 and
FAPKC4, are proposed in [131, 122]. References [123, 125, 126] give some
generalization of FAPKC3 and FAPKC4. In [45, 22], some schemes of pub-
lic key cryptosystems based on finite automata are also proposed. Further
works on security of public key cryptosystems based on finite automata can
be found in [83, 108, 135, 137, 28, 132, 121, 109, 30, 110, 8, 82, 128]. In this
chapter, Sects. 9.1 and 9.2 are based on [126]. Section 9.4 is in part based
on [108, 83, 137, 28, 132, 121]. Section 9.5 is in part based on [45, 128]. And
Sect. 9.6 is a further generalization of [123, 125] in respect of the total number
of component automata.
References
1. M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-
case equivalence, in Proceedings of the T wenty-ninth Annual ACM Symposium
on the Theory of Computing, Association for Computing Machinery, 1997,
284–293.
2. S. V. Aleshin, Finite automata and the Burnside problem for torsion groups,
Mathematical Notes, 29(1972), 319–328. (in Russian)
3. D. D. Aufenkamp, Analysis of sequential machines II, IRE Transactions on
Electronic Computers, 7(1958), 299–306.
4. F. Bao, On the Structure of n-ary Feedforward Inverses with Delay 1, MA
Thesis, Institute of Software, Chinese Academy of Sciences, Beijing, 1986. (in
Chinese)
5. F. Bao, Limited error-propagation, self-synchronization and finite input-
memory FSMs as weak inverses, in Advances in Chinese Computer Science,
Vol. 3, World Scientific, Singapore, 1991, 1–24.
6. F. Bao, Composition and decomposition of weakly invertible finite automata,
Science in China,Ser.A,23 (1993), 759–765. (in Chinese)
7. F. Bao, Two results about the decomposition of delay step of weakly invertible
finite automata, Chinese Jounrnal of Computers, 16(1993), 629–632. (in
Chinese)
8. F. Bao, Increasing ranks of linear finite automata and complexity of FA public
key cryptosystem, Science in China,Ser.A,37(1994), 504–512.
9. F. Bao, R. H. Deng, X. Gao, and Y. Igarashi, Modified finite automata
public key cryptosystem, in Proceedings of the First International Workshop
on Information Security, Lecture Notes in Computer Science 1396, Springer-
Verlag, Berlin, 1997, 82–95.
10. F. Bao and Y. Igarashi, A randomized algorithm to finite automata pub-
lic key cryptosystem, in Proceedings of the Fifth International Symposium
on Algorithms and Computation, Lecture Notes in Computer Science 834,
Springer-Verlag, Berlin, 1994, 678–686.
11. F. Bao and Y. Igarashi, Break finite automata public key cryptosystem, in
Automata, Languages and Programming, Lecture Notes in Computer Science
944, Springer-Verlag, Berlin, 1995, 147–158.
12. F. Bao, Y. Igarashi, and X. Yu, Some results on decomposition of weakly
invertible finite automata, IEICE Transactions on Information and systems,
E79-D(1996), 1–7.
13. C. Berge, Th´eorie des Graphes et ses Applications, Dunod, Paris, 1958.
14. E. Berlecamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York,
1968.
15. E. Berlecamp, Factoring polynomial over large finite fields, Mathematics of
Computation, 24(1970), 713–735.