Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
8.3 Linearly Independent Latin Arrays 345
10, 5, 4, 3, 6, 11, 8, 1, 9, 2, 7;
10, 5, 4, 3, 6, 11, 8, 1, 9, 7, 2;
10, 5, 7, 3, 6, 11, 8, 1, 9, 2, 4;
10, 5, 7, 3, 6, 11, 8, 1, 9, 4, 2;
10, 5, 4, 3, 8, 11, 6, 1, 9
, 2, 7;
10, 5, 4, 3, 8, 11, 6, 1, 9, 7, 2;
10, 5, 7, 3, 8, 11, 6, 1, 9, 2, 4;
10, 5, 7, 3, 8, 11, 6, 1, 9, 4, 2.
For any solution π in the example, let
V
0
=
0000
,V
1
=
⎡
⎢
⎢
⎣
1000
0100
0010
1100
⎤
⎥
⎥
⎦
,
and P
R
be the 11 × 11 permutation matrix of which the element at row i
column π(i) is 1. From Theorem 8.3.5,
⎡
⎣
V
0
V
1
WV
1
⊕ P
R
(I
V
0
⊕ U
−
)
⎤
⎦
is in S(V
0
,V
1
), where WV
1
= A, U
−
= B,androwsofW
i
in W are arranged
in increasing order, that is,
W =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0011
0101
0110
1001
1010
1100
0111
1011
1101
1110
1111
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Therefore,
P
−1
⎡
⎣
V
0
V
1
WV
1
⊕ P
R
(I
V
0
⊕ U
−
)
⎤
⎦
=
⎡
⎣
0
V
1
P
R
B
⎤
⎦
gives the last 4 columns of the truth table of a permutation ϕ on R
4
2
with
c
ϕ
> 1.
346 8. One Key Cryptosystems and Latin Arrays
Historical Notes
Finite automata are regarded as mathematical models of ciphers in [91, 88, 33]
for example. Based on [99, 100], a one key cryptosystem is proposed in [101]
to model the ciphers which can be realized by finite automata and possess
features of bounded error propagation and no plaintext expansion. Section 8.1
is based on [101]. This model consists of four part: a segment of recent ci-
phertext history, an autonomous finite automaton, a discrete function, and
a permutational family. In [115], the concept of Latin array is introduced for
studying permutational families, which is a generalization of Latin square.
Section 8.2 is based on [115, 116, 43] and an unpublished manuscript [114];
the omitted parts in the proofs of Lemmas 8.2.7 and 8.2.9 and Theorem 8.2.15
can be found in [114]. And Sect. 8.3 is based on [119].
9. Finite Automaton Public Key
Cryptosystems
Renji Tao
Institute of Software, Chinese Academy of Sciences
Beijing 100080, China trj@ios.ac.cn
Summary.
Since the introduction of the concept of public key cryptosystems by
Diffie and Hellman
[32]
, many concrete cryptosystems had been proposed
and found applications in the area of information security; almost all are
block. In this chapter, we present a sequential one, the so-called finite
automaton public key cryptosystem; it can be used for encryption as well
as for implementing digital signatures. The public key is a compound finite
automaton of n +1( 2 ) finite automata and states, the private key is
the n + 1 weak inverse finite automata of them and states; no feasible
inversion algorithm for the compound finite automaton is known unless
its decomposition is known. Chapter 3 gives implicitly a feasible method
to construct the 2n + 2 finite automata. We restrict the 2n + 2 finite
automata to memory finite automata in the first five sections; in the last
section, we use pseudo-memory finite automata to construct generalized
cryptosystems.
Security of finite automaton public key cryptosystems is discussed in
Sects. 9.4 and 9.5, which is heavily dependent on Chap. 4 and Sect. 2.3.
Key words: public key cryptosystem, FAPKC, finite automata
Since the introduction of the concept of public key cryptosystems by Diffie
and Hellman
[32]
, many concrete cryptosystems had been proposed and found
applications in the area of information security; almost all are block. In this
chapter, we present a sequential one, the so-called finite automaton public
key cryptosystem; it can be used for encryption as well as for implement-
ing digital signatures. The public key is a compound finite automaton of
n +1( 2) finite automata and states, the private key is the n +1weak in-
verse finite automata of them and states; no feasible inversion algorithm for
the compound finite automaton is known unless its decomposition is known.
348 9. Finite Automaton Public Key Cryptosystems
Chapter 3 gives implicitly a feasible method to construct the 2n + 2 finite
automata. We restrict the 2n + 2 finite automata to memory finite automata
in the first five sections; in the last section, we use pseudo-memory finite
automata to construct generalized cryptosystems.
Security of finite automaton public key cryptosystems is discussed in
Sects. 9.4 and 9.5, which is heavily depend on Chap. 4 and Sect. 2.3.
9.1 Theoretical Fundamentals
Throughout this chapter, for any integer i, any positive integer k and any
symbol string z, we still use z(i, k) to denote the symbol string z
i
,z
i−1
,...,
z
i−k+1
. For any (r, t)-order memory finite automaton M = X, Y, S, δ, λ,
any (r
,t
)-order memory finite automaton M
= Y,X,S
,δ
,λ
,andany
nonnegative integer τ ,weusePI(M, M
,τ) to denote the following condition:
For any state s = y(−1,t),x(−1,r) of M and any state s
=
x(−1,t
), y(τ − 1,r
) of M
,andanyx
0
,x
1
,...∈ X, y
τ
,y
τ+1
,...∈
Y ,ify
0
y
1
...= λ(s, x
0
x
1
...), then x
0
x
1
...= λ
(s
,y
τ
y
τ+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
,X
r
i
i
,δ
i
,λ
i
be an r
i
-order input-
memory finite automaton, M
∗
i
= X
i−1
,X
i
,X
r
i
i
×X
τ
i
i−1
,δ
∗
i
,λ
∗
i
a(τ
i
,r
i
)-order
memory finite automaton, and τ
i
r
i
.
Let M
0
= X
0
,Y,Y
t
0
× X
r
0
0
,δ
0
,λ
0
be an (r
0
,t
0
)-order memory finite
automaton, M
∗
0
= Y,X
0
,X
t
∗
0
0
× Y
r
∗
0
,δ
∗
0
,λ
∗
0
an (r
∗
0
,t
∗
0
)-order memory finite
automaton, and τ
0
r
0
.
Theorem 9.1.1. Assume that M
∗
i
, M
i
and τ
i
satisfy PI(M
∗
i
,M
i
,τ
i
), i =0,
1,...,n.Lets
(i)∗
−b
i−1
= x
(i)
(−b
i−1
− 1,r
i
), ¯x
(i−1)
(−b
i−1
− 1,τ
i
) be a state of
M
∗
i
, i =1,...,n,andletx
(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.1)
i =1,...,n,
where b
0
= r
0
− τ
0
, b
i
= b
i−1
+ r
i
− τ
i
, i =1,...,n.Lets
(0)∗
0
= x
(0)
(−1,t
∗
0
),
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.2)
i =1,...,n,
9.1 Theoretical Fundamentals 349
then
y
0
y
1
...= λ
(s
,x
(n)
τ
x
(n)
τ+1
...), (9.3)
where λ
is the output function of C
(M
n
,...,M
1
,M
0
), s
= y(−1,t
0
),
x
(n)
(τ − 1, r), r = r
0
+ ···+ r
n
,andτ = τ
0
+ ···+ τ
n
.
Proof. Suppose that (9.2) holds. From (9.1) and (9.2), 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.SincePI(M
∗
i
,M
i
,τ
i
) holds, this yields 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.4)
i =1,...,n,wheres
(i)
= x
(i)
(−b
i−1
+ τ
i
− 1,r
i
).SincePI(M
∗
0
,M
0
,τ
0
)
holds, from the part on M
∗
0
in (9.2), we have
y
0
y
1
...= λ
0
(s
(0)
,x
(0)
τ
0
x
(0)
τ
0
+1
...), (9.5)
where s
(0)
= y(−1,t
0
),x
(0)
(τ
0
− 1,r
0
).
For 1 i n − 1, let λ
i
be the output function of C
(M
n
,...,M
i
). From
(9.4) for i = n − 1,n, by Theorem 1.2.1 we have
x
(n−2)
−b
n−2
x
(n−2)
−b
n−2
+1
...= λ
n−1
(x
(n)
(−b
n−2
+ τ
n−1
+ τ
n
− 1,r
n−1
+ r
n
),
x
(n)
−b
n−2
+τ
n−1
+τ
n
x
(n)
−b
n−2
+τ
n−1
+τ
n
+1
...).
Suppose that we have proven that
x
(i)
−b
i
x
(i)
−b
i
+1
...= λ
i+1
(x
(n)
(−b
i
+ τ
i+1
+ ···+ τ
n
− 1,r
i+1
+ ···+ r
n
),
x
(n)
−b
i
+τ
i+1
+···+τ
n
x
(n)
−b
i
+τ
i+1
+···+τ
n
+1
...)
for i 1, we prove the case of λ
i
. From the above equation and (9.4), noticing
−b
i
= −b
i−1
+ τ
i
− r
i
, applying Theorem 1.2.1, we obtain
x
(i−1)
−b
i−1
x
(i−1)
−b
i−1
+1
...= λ
i
(x
(n)
(−b
i−1
+ τ
i
+ ···+ τ
n
− 1,r
i
+ ···+ r
n
),
x
(n)
−b
i−1
+τ
i
+···+τ
n
x
(n)
−b
i−1
+τ
i
+···+τ
n
+1
...).
Thus the above equation holds for the case of i =1,thatis,
x
(0)
−b
0
x
(0)
−b
0
+1
...= λ
1
(x
(n)
(−b
0
+ τ
1
+ ···+ τ
n
− 1,r
1
+ ···+ r
n
),
x
(n)
−b
0
+τ
1
+···+τ
n
x
(n)
−b
0
+τ
1
+···+τ
n
+1
...).
Since (9.5) holds, from Theorem 1.2.1 it immediately follows that
y
0
y
1
...= λ
(s
,x
(n)
τ
x
(n)
τ+1
...),
that is, (9.3) holds.
350 9. Finite Automaton Public Key Cryptosystems
Theorem 9.1.2. Assume that PI(M
i
,M
∗
i
,τ
i
), i =0, 1, ..., n hold. Let
s
= y(−1,t
0
),x
(n)
(−1,r) be a state of C
(M
n
,...,M
1
,M
0
) with output
function λ
,wherer = r
0
+ ···+ r
n
.Let
x
(i−1)
−r
0
−···−r
i−1
...x
(i−1)
−1
= λ
i
(x
(i)
(−r
0
−···−r
i−1
− 1,r
i
),x
(i)
−r
0
−···−r
i−1
...x
(i)
−1
) (9.6)
for i = n, n − 1,...,1,and
y
0
y
1
...= λ
(s
,x
(n)
0
x
(n)
1
...). (9.7)
If
x
(0)
0
x
(0)
1
...= λ
∗
0
(x
(0)
(−1,t
∗
0
),y(τ
0
− 1,r
∗
0
),y
τ
0
y
τ
0
+1
...), (9.8)
and
x
(i)
0
x
(i)
1
...= λ
∗
i
(x
(i)
(−1,r
i
),x
(i−1)
(τ
i
− 1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...) (9.9)
for i =1,...,n− 1,then
x
(n)
0
x
(n)
1
...= λ
∗
n
(x
(n)
(−1,r
n
),x
(n−1)
(τ
n
− 1,τ
n
),x
(n−1)
τ
n
x
(n−1)
τ
n
+1
...). (9.10)
Proof.Lets
i
= x
(i)
(−1,r
i
) for 1 i n, s
n
= s
and s
i
= y(−1,
t
0
), x
(i)
(−1,r
0
+ ···+ r
i
) for 0 i n − 1. For any i,0<i n,since
(9.6) holds, from Theorem 1.2.1, the state s
i
of C
(M
i
,..., M
1
, M
0
)and
the state s
i
,s
i−1
of C(M
i
,C
(M
i−1
,..., M
1
, M
0
)) are equivalent. Thus,
the state s
(= s
n
)ofC
(M
n
, ..., M
1
, M
0
) and the state s
n
,...,s
1
,s
0
of
C(M
n
,...,M
1
,M
0
)areequivalent.
Suppose that (9.7) holds. Let
¯x
(n−1)
0
¯x
(n−1)
1
...= λ
n
(s
n
,x
(n)
0
x
(n)
1
...), (9.11)
and
¯x
(i−1)
0
¯x
(i−1)
1
...= λ
i
(s
i
, ¯x
(i)
0
¯x
(i)
1
...) (9.12)
for i = n − 1,n− 2,...,1. Since s
and s
n
,...,s
1
,s
0
are equivalent, (9.7)
yields
y
0
y
1
...= λ
0
(s
0
, ¯x
(0)
0
¯x
(0)
1
...). (9.13)
To show x
(n−1)
0
x
(n−1)
1
... =¯x
(n−1)
0
¯x
(n−1)
1
..., we now prove by simple in-
duction that x
(i)
0
x
(i)
1
...=¯x
(i)
0
¯x
(i)
1
... for 0 i n − 1. Since PI(M
0
,M
∗
0
,τ
0
)
holds, by (9.13) we have
¯x
(0)
0
¯x
(0)
1
...= λ
∗
0
(x
(0)
(−1,t
∗
0
),y(τ
0
− 1,r
∗
0
),y
τ
0
y
τ
0
+1
...).
From (9.8) it follows that x
(0)
0
x
(0)
1
... =¯x
(0)
0
¯x
(0)
1
... Suppose that
x
(i−1)
0
x
(i−1)
1
... =¯x
(i−1)
0
¯x
(i−1)
1
... is true and i n − 1. We prove that
9.2 Basic Algorithm 351
x
(i)
0
x
(i)
1
...=¯x
(i)
0
¯x
(i)
1
... Since PI(M
i
,M
∗
i
,τ
i
) holds, noticing x
(i−1)
j
=¯x
(i−1)
j
,
(9.12) yields
¯x
(i)
0
¯x
(i)
1
...= λ
∗
i
(x
(i)
(−1,r
i
),x
(i−1)
(τ
i
− 1,τ
i
),x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...).
From (9.9), we have x
(i)
0
x
(i)
1
...=¯x
(i)
0
¯x
(i)
1
...
Since PI(M
n
,M
∗
n
,τ
n
) holds, noticing x
(n−1)
j
=¯x
(n−1)
j
, (9.11) yields
x
(n)
0
x
(n)
1
...= λ
∗
n
(x
(n)
(−1,r
n
),x
(n−1)
(τ
n
− 1,τ
n
),x
(n−1)
τ
n
x
(n−1)
τ
n
+1
...),
that is, (9.10) holds.
Corollary 9.1.1. If condition (9.6) is replaced by
x
(i−1)
−r
0
−r
1
−···−r
i−1
...x
(i−1)
−1
= λ
i
(x
(i)
(−r
0
− r
1
−···−r
i−1
− 1,r
i
),x
(i)
−r
0
−r
1
−···−r
i−1
...x
(i)
−1
),
where r
0
=min(r
0
,t
∗
0
), −r
0
− r
1
−···−r
i−1
means −r
0
in the case of i =1,
then Theorem 9.1.2 still holds.
Proof.SinceM
i
, i =1,...,nare input-memory finite automata, x
(0)
−1
,...,
x
(0)
−t
∗
0
in (9.8), x
(i)
−1
,...,x
(i)
−r
i
, i =1,...,n in (9.9) and (9.10) are independent
of x
(n)
−r
, x
(n)
−r+1
, ..., x
(n)
−r+r
0
−r
0
−1
.
9.2 Basic Algorithm
A conventional cryptosystem, namely, a one key cryptosystem, is a family of
pairs of encryption algorithms and decryption algorithms, each algorithm in
any pair is indexed by its key. The key of an encryption algorithm and the
key of its corresponding decryption algorithm are the same, or the latter can
be easily derived from the former. Conventional cryptosystems require the
sender and the receiver to share a key in secret.
According to Diffie and Hellman
[32]
, a public key cryptosystem is a family
of pairs of algorithms, say {(E
k
,D
k
),k ∈ K}, satisfying conditions: (a) for
any k ∈ K, D
k
is an inverse of E
k
(for confidence application), and/or E
k
is
an inverse of D
k
(for authenticity application), (b) for any k ∈ K, E
k
and D
k
are easy to compute, (c) for almost every k ∈ K, it is infeasible to derive an
easily computed algorithm equivalent to D
k
from E
k
, and (d) for any k ∈ K,
it is feasible to compute the pair of E
k
and D
k
. In applications of a public
key cryptosystem, each user chooses a pair of E
k
, the user’s public key, and
D
k
, the user’s private key, the user makes E
k
public and keeps D
k
secret.
352 9. Finite Automaton Public Key Cryptosystems
Based on the results of the preceding section, a public key cryptosys-
tem for both confidence and authenticity applications can be proposed. It is
required that m = l
0
= ···= l
n
.
1
We denote X
i
by X for short.
Choose a common q and m for all users. Let both the alphabets X and Y
be the same column vector space over GF(q) of dimension m. The plaintext
space X
∗
and the ciphertext space Y
∗
are the same.
A user, say A, choose his/her own public key and private key as follows.
(a) Construct an (r
∗
0
,t
∗
0
)-order memory finite automaton M
∗
0
= Y , X, S
∗
0
,
δ
∗
0
, λ
∗
0
andan(r
0
,t
0
)-order memory finite automaton M
0
= X, Y, S
0
,δ
0
,
λ
0
satisfying conditions PI(M
∗
0
,M
0
,τ
0
)andPI(M
0
,M
∗
0
,τ
0
).
(b) For each i,1 i n, construct an r
i
-order input-memory finite
automaton M
i
= X, X, S
i
,δ
i
,λ
i
and a (τ
i
,r
i
)-order memory finite au-
tomaton M
∗
i
= X, X, S
∗
i
,δ
∗
i
,λ
∗
i
satisfying conditions PI(M
∗
i
,M
i
,τ
i
)and
PI(M
i
,M
∗
i
,τ
i
).
(c) Construct the finite automaton C
(M
n
,...,M
1
,M
0
)=X, Y, S, δ, λ
from M
0
, ..., M
n
.
(d) Let b
0
= r
0
−τ
0
, b
i
= b
i−1
+r
i
−τ
i
, i =1,...,n. Assume that b
0
= ...=
b
c−1
= 0, i.e., r
j
= τ
j
, j =0,...,c−1, for some c,0 c n. Choose arbitrary
y
−1
,...,y
−t
0
∈ Y , x
(c)
−1
,...,x
(c)
−b
c
∈ X.Foreachi, c +1 i n,choosean
arbitrary state s
(i)∗
−b
i−1
= x
(i)
−b
i−1
−1
,...,x
(i)
−b
i−1
−r
i
,¯x
(i−1)
−b
i−1
−1
,...,¯x
(i−1)
−b
i−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
)
and
s
(i)∗
0
= δ
∗
i
(s
(i)∗
−b
i−1
,x
(i−1)
−b
i−1
...x
(i−1)
−1
),
for i = c +1,...,n. Take s
(0),in
s
= y
−1
,...,y
− min(t
0
,r
∗
0
)
, s
(c),out
s
= x
(c)
−1
,...,
x
(c)
−b
c
, s
(i)
s
=s
(i)∗
0
, i= c+1,...,n, s
out
v
=y
−1
,...,y
−t
0
, s
in
v
= x
(n)
−1
,...,x
(n)
−b
n
.
(e) Choose arbitrarily y
−1
,...,y
−r
∗
0
+τ
0
∈ Y ,andx
(n)
−1
,...,x
(n)
−r
∈ X,
where r
= r
0
+ r
1
+ ···+ r
n
, r
0
=min(r
0
,t
∗
0
). Compute
x
(i−1)
−r
0
−r
1
−···−r
i−1
...x
(i−1)
−1
= λ
i
(x
(i)
−r
0
−r
1
−···−r
i−1
−1
,...,x
(i)
−r
0
−r
1
−···−r
i
,x
(i)
−r
0
−r
1
−···−r
i−1
...x
(i)
−1
),
i = n, n − 1,...,1.
1
If the public key system is only for the confidence application, l
n
··· l
0
m
is enough. If it is only for the authenticity application, l
n
··· l
0
m suffices.
9.2 Basic Algorithm 353
Take s
out
e
= y
−1
,...,y
− min(r
∗
0
−τ
0
,t
0
)
, s
in
e
= x
(n)
−1
, ..., x
(n)
−r
, s
(0),out
d
=
x
(0)
−1
, ..., x
(0)
− min(r
0
,t
∗
0
)
, s
(0),in
d
= y
−1
,...,y
−r
∗
0
+τ
0
, s
(i),out
d
= x
(i)
−1
,...,x
(i)
−r
i
,
i =1,...,n.
1
(f) The public key of the user A is
C
(M
n
,...,M
1
,M
0
),s
out
v
,s
in
v
,s
out
e
,s
in
e
,τ
0
+ ···+ τ
n
.
The private key of the user A is
M
∗
0
,...,M
∗
n
,s
(0),in
s
,s
(c),out
s
,s
(c+1)
s
,...,s
(n)
s
,
s
(0),out
d
,s
(0),in
d
,s
(1),out
d
,...,s
(n),out
d
,τ
0
,...,τ
n
.
Encryption
Any user, say B, wants to send a plaintext x
0
...x
l
to a user A. B first suffixes
any τ
0
+ ···+ τ
n
digits, say x
l+1
... x
l+τ
0
+···+τ
n
, to the plaintext. Then
using A’s public key C
(M
n
,...,M
1
,M
0
), s
out
e
= y
−1
,...,y
− min(r
∗
0
−τ
0
,t
0
)
and s
in
e
= x
(n)
−1
,...,x
(n)
−r
, B computes the ciphertext y
0
...y
n+τ
0
+···+τ
n
as
follows:
y
0
...y
l+τ
0
+···+τ
n
= λ
(s
,x
0
...x
l+τ
0
+···+τ
n
),
where
s
= y
−1
,...,y
−t
0
,x
(n)
−1
,...,x
(n)
−r
,
x
(n)
−r+r
0
−t
∗
0
−1
,...,x
(n)
−r
are arbitrarily chosen from X when t
∗
0
<r
0
,and
y
−r
∗
0
+τ
0
−1
, ..., y
−t
0
are arbitrarily chosen from Y when r
∗
0
− τ
0
<t
0
.
Decryption
From the ciphertext y
0
...y
l+τ
0
+···+τ
n
, A can retrieve the plaintext as fol-
lows. Using M
∗
0
,...,M
∗
n
, s
(0),out
d
= x
(0)
−1
,...,x
(0)
− min(r
0
,t
∗
0
)
, s
(0),in
d
= y
−1
,...,
y
−r
∗
0
+τ
0
, s
(i),out
d
= x
(i)
−1
,...,x
(i)
−r
i
, i =1,...,n in his/her private key, A
computes
x
(0)
0
x
(0)
1
...x
(0)
l+τ
1
+···+τ
n
= λ
∗
0
(x
(0)
−1
,...,x
(0)
−t
∗
0
,y
τ
0
−1
,...,y
τ
0
−r
∗
0
,y
τ
0
y
τ
0
+1
...y
l+τ
0
+···+τ
n
),
x
(i)
0
x
(i)
1
...x
(i)
l+τ
i+1
+···+τ
n
= λ
∗
i
(x
(i)
−1
,...,x
(i)
−r
i
,x
(i−1)
τ
i
−1
,...,x
(i−1)
0
,x
(i−1)
τ
i
x
(i−1)
τ
i
+1
...x
(i−1)
l+τ
i
+···+τ
n
),
i =1,...,n,
where x
(0)
−r
0
−1
,...,x
(0)
−t
∗
0
may be arbitrarily chosen when r
0
<t
∗
0
. From Corol-
lary 9.1.1, the plaintext x
0
...x
l
is equal to x
(n)
0
x
(n)
1
...x
(n)
l
.
1
For the simplicity of symbolization, we use the same symbols y
−j
and x
(i)
−j
in (d)
and in (e), but their intentions are different.
354 9. Finite Automaton Public Key Cryptosystems
Signature
To sign a message y
0
...y
l
, the user A first suffixes any τ
0
+ ···+ τ
n
digits,
say y
l+1
... y
l+τ
0
+···+τ
n
, to the message. Then using his/her private key
M
∗
0
,..., M
∗
n
, s
(0),in
s
= y
−1
, ..., y
− min(t
0
,r
∗
0
)
, s
(c),out
s
= x
(c)
−1
,...,x
(c)
−b
c
, s
(i)
s
,
i = c +1,...,n, 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,
where
s
(0)
s
= x
(0)
−1
,...,x
(0)
−t
∗
0
,y
−1
,...,y
−r
∗
0
,
s
(i)
s
= x
(i)
−1
,...,x
(i)
−r
i
, ¯x
(i−1)
−1
,...,¯x
(i−1)
−τ
i
,
i =1,...,c,
x
(0)
−b
0
−1
,...,x
(0)
−t
∗
0
are arbitrarily chosen from X inthecaseofc =0,
x
(0)
−1
,...,x
(0)
−t
∗
0
, x
(i)
−1
,...,x
(i)
−r
i
, i =1,...,c−1, x
(c)
−b
c
−1
,...,x
(c)
−r
c
,and¯x
(i−1)
−1
,...,
¯x
(i−1)
−τ
i
, i =1,...,c, are arbitrarily chosen from X inthecaseofc>0, and
y
−t
0
−1
,...,y
−r
∗
0
are arbitrarily chosen from Y inthecaseoft
0
<r
∗
0
.Then
x
(n)
0
x
(n)
1
...x
(n)
l+τ
0
+···+τ
n
is a signature of the message y
0
...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
= y
−1
,...,y
−t
0
, s
in
v
= x
(n)
−1
,...,
x
(n)
−r+τ
in A’s public key, B computes
λ
(s
,x
(n)
τ
x
(n)
τ+1
...x
(n)
l+τ
),
which would coincide with the message y
0
...y
l
from Theorem 9.1.1, where
s
= y
−1
,...,y
−t
0
, x
(n)
τ−1
, ..., x
(n)
τ−r
, r = r
0
+ ···+ r
n
,andτ = τ
0
+ ···+ τ
n
.
The public key cryptosystem based on finite automata mentioned above is
abbreviated to FAPKC. Notice that a plaintext may have many ciphertexts
and that a message may have many signatures. In encryption or signing,
some digits of the initial state(s) may take arbitrary values. The number of
such digits is referred to as the freedom, which depends on the choice of
parameters. For example, in FAPKC3, a special case of FAPKC with n =1,
r
∗
0
= t
0
+τ
0
,andt
∗
0
= r
0
(cf. [131]), the freedom for signature is 2τ
0
if τ
0
<r
0
,