Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
9.2 Basic Algorithm 355
2τ
0
+2τ
1
if τ
0
= r
0
, and the freedom for encryption is 0. In FAPKC4, a special
case of FAPKC with n =1,r
0
= t
∗
0
+ τ
0
,andt
0
= r
∗
0
(cf. [122]), the freedom
for signature is 0 if τ
0
<r
0
,2τ
1
if τ
0
= r
0
, and the freedom for encryption is
2τ
0
.
We point out that finite automata M
i
and M
∗
i
satisfying conditions
PI(M
∗
i
, M
i
,τ
i
)andPI(M
i
,M
∗
i
,τ
i
) do exist. Recall some results in Chap. 3.
Taking p = −1, let M be an (r, t)-order memory finite automaton M
f
defined
by
y
i
= f(y
i−1
,...,y
i−t
,x
i
,...,x
i−r
),i=0, 1,... (9.14)
Assume that eq
0
(i) is the equation
−y
i
+ f(y
i−1
,...,y
i−t
,x
i
,...,x
i−r
) = 0 (9.15)
and that
eq
k
(i)
R
a
[ϕ
k
]
−→ eq
k
(i),eq
k
(i)
R
b
[r
k+1
]
−→ eq
k+1
(i),k=0, 1,...,τ − 1 (9.16)
is an R
a
R
b
transformation sequence. Let f
∗
τ
be a single-valued mapping from
X
r
×Y
τ+t+1
to X,andM
∗
= Y,X,X
r
×Y
τ+t
,δ
∗
,λ
∗
be a finite automaton
M
f
∗
τ
defined by
x
i
= f
∗
τ
(x
i−1
,...,x
i−r
,y
i
,...,y
i−τ−t
),i=0, 1,...
If eq
τ
(i) has a solution f
∗
τ
, i.e., for any parameters x
i−1
, ..., x
i−r
, y
i+τ
, ...,
y
i−t
, eq
τ
(i) has a solution x
i
x
i
= f
∗
τ
(x
i−1
,...,x
i−r
,y
i+τ
,...,y
i−t
),
then from Lemma 3.1.1 we have PI(M
∗
,M,τ). If eq
τ
(i) has at most one
solution f
∗
τ
, i.e., for any x
i
, ..., x
i−r
, y
i+τ
, ..., y
i−t
, eq
τ
(i) implies x
i
=
f
∗
τ
(x
i−1
,...,x
i−r
, y
i+τ
, ..., y
i−t
), then from Lemma 3.1.2 we have PI(M, M
∗
,τ).
Thus if eq
τ
(i) determines a single-valued function f
∗
τ
,thenwehavePI(M
∗
,M,
τ)andPI(M, M
∗
,τ). Using R
−1
a
R
−1
b
transformation, in Sect. 3.2 of Chap. 3
a generation procedure of such a finite automaton M andsuchanR
a
R
b
transformation sequence are given. For example, choose an m×l(τ +1) (l, τ)-
echelon matrix G
τ
(i)overGF (q)andanR
−1
a
R
−1
b
transformation sequence
G
k+1
(i)
R
−1
b
[r
k+1
]
−→ G
k
(i),G
k
(i)
R
−1
a
[P
k
]
−→ G
k
(i),k= τ − 1,...,1, 0 (9.17)
such that for any parameters x
i−1
, ..., x
i−ν
,
G
0τ
ψ
l
−1,ν
(x
i
,...,x
i−ν
)
as a function of the variable x
i
is a bijection. Take
356 9. Finite Automaton Public Key Cryptosystems
f(y
i−1
,...,y
i−t
,x
i
,...,x
i−r
)
= f
(y
i−1
,...,y
i−t
)+
r
j=0
G
j0
ψ
l
−1,ν
(x
i−j
,...,x
i−j−ν
),
where f
and G
j0
, j = τ +1,...,r are arbitrarily chosen such that the right
side of the equation does not depend on x
i−r−1
,...,x
i−r−ν
. Taking M as
M
f
and the R
a
R
b
transformation sequence corresponding to the reverse
transformation sequence of (9.17), then the finite automaton and the R
a
R
b
transformation sequence satisfy the conditions mentioned above.
9.3 An Example of FAPKC
We give a pedagogical example with q =2,m =8,n =1andc =0.Thusthe
alphabets X and Y are the column vector spaces over GF (2) of dimension 8.
M
0
is an (r
0
,t
0
)-order nonlinear finite automaton, defined by
y
i
=
t
0
j=1
A
j
y
i−j
⊕
r
0
j=0
B
j
x
i−j
⊕
r
0
−1
j=0
B
j
t
(x
i−j
,x
i−j−1
),
i =0, 1,...,
and M
∗
0
is a nonlinear (t
0
+ τ
0
,r
0
)-order memory finite automaton, defined
by
x
i
=
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−j
,
i =0, 1,...,
where t
is a nonlinear function from X
2
to X,
t
(x
0
,x
−1
)=β
3+j
,
j =2
3
j
3
+2
2
j
2
+2j
1
+ j
0
,
j
3
= p
8
(β
20
& x
0
),
j
2
= p
8
(β
21
& x
0
)),
j
1
= p
8
(β
20
& x
−1
),
j
0
= p
8
(β
21
& x
−1
),
p
8
([b
7
,b
6
,...,b
0
]
T
)=b
7
⊕ b
6
⊕···⊕b
0
,
[a
7
,a
6
,...,a
0
]
T
&[b
7
,b
6
,...,b
0
]
T
=[a
7
& b
7
,a
6
& b
6
,...,a
0
& b
0
]
T
,
x
0
,x
−1
∈ X, a
i
,b
i
∈ GF (2),i=0,...,7.
9.3 An Example of FAPKC 357
M
1
is a nonlinear r
1
-order input-memory finite automaton, defined by
x
i
=
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
),
i =0, 1,...,
and M
∗
1
is a nonlinear (τ
1
,r
1
)-order memory finite automaton, defined by
x
i
=
r
1
j=1
F
∗
j
x
i−j
⊕
r
1
−2
j=1
F
∗∗
j
t(x
i−j
,x
i−j−1
,x
i−j−2
) ⊕
τ
1
j=0
D
∗
j
x
i−j
,
i =0, 1,...,
where t is a nonlinear function from X
3
to X,
t(x
0
,x
−1
,x
−2
)=β
3+j
⊕ (β
19
& ψ(x
0
)&ψ(x
−1
)&ψ(x
−2
)),
j =2
3
j
3
+2
2
j
2
+2j
1
+ j
0
,
j
3
= p
8
((β
0
& x
0
) ⊕ (β
2
& x
−1
)),
j
2
= p
8
(β
1
& x
−1
),
j
1
= p
8
((β
0
& x
−1
) ⊕ (β
2
& x
−2
)),
j
0
= p
8
(β
1
& x
−2
),
x
0
,x
−1
,x
−2
∈ X.
β
0
,...,β
21
are in X,andψ is a single-valued mapping from X to X.Inthis
example, β
0
, β
1
, ..., β
21
are f1, a2, 57, 00, 00, 00, 00, 01, 01, 01, 01, 00, 20,
40, 64, 80, a8, d0, fe, 04, 79, 39, respectively, and ψ([0, 0, 0, 0, 0, 0, 0, 0]
T
)
ψ([0, 0, 0, 0, 0, 0, 0, 1]
T
) ... ψ([1, 1, 1, 1, 1, 1, 1, 1]
T
)are
30 31 33 34 35 36 37 38 05 06 07 08 09 0a 0b 0c
0d 0e 0f 02 00 01 03 04 10 11 13 14 15 16 17 18
19 1a 1b 1c 1d 1e 1f 12 29 2a 2b 2c 20 21 23 24
25 26 27 28 2d 2e 2f 22 39 3a 3b 3c 3d 3e 3f 32
70 71 73 74 75 76 77 78 45 46 47 48 49 4a 4b 4c
4d 4e 4f 42 40 41 43 44 50 51 53 54 55 56 57 58
59 5a 5b 5c 5d 5e 5f 52 69 6a 6b 6c 60 61 63 64
65 66 67 68 6d 6e 6f 62 79 7a 7b 7c 7d 7e 7f 72
b0 b1 b3 b4 b5 b6 b7 b8 85 86 87 88 89 8a 8b 8c
8d 8e 8f 82 80 81 83 84 90 91 93 94 95 96 97 98
99 9a 9b 9c 9d 9e 9f 92 a9 aa ab ac a0 a1 a3 a4
a5 a6 a7 a8 ad ae af a2 b9 ba bb bc bd be bf b2
358 9. Finite Automaton Public Key Cryptosystems
f0 f1 f3 f4 f5 f6 f7 f8 c5 c6 c7 c8 c9 ca cb cc
cd ce cf c2 c0 c1 c3 c4 d0 d1 d3 d4 d5 d6 d7 d8
d9 da db dc dd de df d2 e9 ea eb ec e0 e1 e3 e4
e5 e6 e7 e8 ed ee ef e2 f9 fa fb fc fd fe ff f2
respectively. In this example, to save space, we use symbols 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, a, b, c, d, e, f to denote 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001 1010, 1011 1100, 1101 1110, 1111 in matrices, and to denote
column vectors [0, 0, 0, 0]
T
,[0, 0, 0, 1]
T
,[0, 0, 1, 0]
T
,[0, 0, 1, 1]
T
,[0, 1, 0, 0]
T
,
[0, 1, 0, 1]
T
,[0, 1, 1, 0]
T
,[0, 1, 1, 1]
T
,[1, 0, 0, 0]
T
,[1, 0, 0, 1]
T
,[1, 0, 1, 0]
T
,
[1, 0, 1, 1]
T
,[1, 1, 0, 0]
T
,[1, 1, 0, 1]
T
,[1, 1, 1, 0]
T
,[1, 1, 1, 1]
T
in states and se-
quences (words), respectively. The concatenation of two such symbols, say
s
1
s
2
, denotes t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
when s
1
denotes t
1
t
2
t
3
t
4
and s
2
denotes t
5
t
6
t
7
t
8
,
or denotes [t
1
,t
2
,t
3
,t
4
,t
5
,t
6
,t
7
,t
8
]
T
when s
1
denotes [t
1
,t
2
,t
3
,t
4
]
T
and s
2
de-
notes [t
5
,t
6
,t
7
,t
8
]
T
,wheret
i
∈ GF (2), i =1, 2,...,8.
C
(M
1
,M
0
) is a nonlinear (r
0
+ r
1
,t
0
)-order memory finite automaton.
In this example, take τ
0
=4,τ
1
=6,r
0
=5,t
0
=3,r
1
=8,and
C
(M
1
,M
0
) in the public key can be expressed as
y
i
=
t
0
j=1
A
j
y
i−j
⊕
r
0
+r
1
j=0
C
j
x
i−j
⊕
r
0
+r
1
−2
j=0
C
j
t(x
i−j
,x
i−j−1
,x
i−j−2
),
i =0, 1,...,
where
[C
0
... C
13
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
00 00 a2 00 db dd 21 3c 91 d3 bc cd 7d 69
00 00 a2 00 92 6a 42 8a a6 d8 6b 47 9e 25
00 f1 a6 1e 5c 52 39 1e bd ef 3c 85 18 01
00 00 00 f1 6c e0 d8 b7 ab d1 c3 8a 2f ff
00 f1 57 00 d0 73 76 ba 05 2e d6 cb 52 41
00 00 00 a2 42 ed f8 c9 00 70 7f c5 26 25
00 00 53 57 1a c1 97 99 b1 26 3b a2 a6 90
00 00 a2 00 68 6c e0 30 85 0b dc f2 51 b3
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
[C
0
... C
11
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
00 b8 b2 10 c1 b8 f3 6a a6 38 9e 67
00 b8 b2 69 d0 65 22 25 1b 5f 90 64
00 81 ca 23 2c 0c e2 b9 88 97 39 4d
00 39 8b a0 b2 77 a7 b8 9b 89 d2 d4
00 b8 38 8a 19 aa 8b 97 7e b4 41 e6
00 00 00 90 aa 4e fe 72 38 5e bc 64
00 81 b8 78 d1 dd fa 6e 98 eb 25 ad
00 b8 33 b9 70 77 9e 52 e4 fd 15 d7
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
9.3 An Example of FAPKC 359
[A
1
A
2
A
3
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
00 43 80
00 21 c0
00 10 e0
00 08 70
00 04 38
00 02 1c
00 01 0e
00 00 87
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
In the public key,
s
out
v
= s
out
e
= 74, d1, 4a,
s
in
v
= 17, 06, d2,
s
in
e
= 17, 06, d2, ef, 52, a5, 0c, de, 58, 37, 9b, 80, 4d.
In the private key, M
∗
0
is a nonlinear (7, 5)-order memory finite automa-
ton, defined by
x
i
=
5
j=1
A
∗
j
x
i−j
⊕
4
j=1
A
∗∗
j
t
(x
i−j
,x
i−j−1
), ⊕
7
j=0
B
∗
j
y
i−j
,
i =0, 1,...,
where
[B
∗
0
... B
∗
7
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
00 c2 df 82 23 ef 27 00
c0 29 2b 1d 7a 5a 7f 00
c0 eb 62 c2 11 78 4b 00
00 00 d5 14 68 a1 6c 00
c0 6e f4 ca 0b bf 11 7f
00 47 49 8a 70 28 58 00
00 47 0a 9e 50 6b 34 00
00 00 00 a8 00 57 58 00
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
[A
∗
1
... A
∗
5
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
41 5e 1a 6e 00
89 80 1d 81 00
8a 92 52 7a 00
2f 67 09 14 00
01 f0 4e 67 81
8f 3d e1 ef 00
da 2d 8f fb 00
58 86 60 ef 00
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
360 9. Finite Automaton Public Key Cryptosystems
[A
∗∗
1
... A
∗∗
4
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
ba d3 11 00
7b 62 38 00
ab d3 09 00
7b c8 18 00
68 38 6b 38
40 81 29 00
63 41 31 00
40 b9 29 00
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
M
∗
1
is a nonlinear (6, 8)-order, (6, 6)-order in essential, memory finite au-
tomaton, defined by
x
i
=
6
j=1
F
∗
j
x
i−j
⊕
4
j=1
F
∗∗
j
t(x
i−j
,x
i−j−1
,x
i−j−2
) ⊕
6
j=0
D
∗
j
x
i−j
,
i =0, 1,...,
where
[D
∗
0
... D
∗
6
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
c2 eb 04 59 59 40 79
c2 58 59 42 1b 00 00
00 b3 5d 1b 22 00 00
00 b3 42 59 22 39 00
c2 eb 1b 1b 42 39 00
00 b3 eb 00 39 79 79
c2 58 59 42 7b 79 79
00 b3 42 59 42 79 00
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
[F
∗
1
... F
∗
6
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
26 b5 6e 99 e1 be
23 b6 ff 29 aa 4b
bb 0b 4a 6d b6 4b
00 26 05 3d 43 4b
df 34 a4 5e e9 f5
ea 69 2c 90 00 00
9d be 24 f4 57 f5
e9 2e 7c 42 1c f5
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
[F
∗∗
1
... F
∗∗
4
]=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
b9 ba 96 32
2f 28 0d d1
d8 6c be 50
bd 96 dc 50
01 91 1a 62
25 2c 00 00
61 d6 28 62
f3 e9 78 62
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
In the private key,
9.3 An Example of FAPKC 361
s
(0),in
s
= 74, d1, 4a,
s
(0),out
s
= 69,
s
(1)
s
= 17, 06, d2, 70, 7f, a1, 65, 75; 69, ec, bf, cc, c9, 3e,
s
(0),in
d
= 74, d1, 4a,
s
(0),out
d
= 59, c2, 37, 81, b6,
s
(1),out
d
= 17, 06, d2, ef, 52, a5, 0c, de.
Let α be the sequence
4e 6f 20 70 61 69 6e 73 2c 6e 6f 20 67 61 69 6e 73 2e
over X, which is the ASCII code of the sentence “No pains,no gains.”.
For encryption, taking randomly α
10
= 89 b4 70 2a 92 07 ce cd 2a 4c,
then
λ(s
e
,αα
10
)=6f df a8 59 94 99 80 d7 91 d8 7f 65 ff 39 6d
a6 36 fe a6 7b 8b fc 08 78 03 75 13 e5
is a ciphertext of α,whereλ is the output function of C
(M
1
,M
0
), and
s
e
= s
out
e
,s
in
e
= 74, d1, 4a; 17, 06, d2, ef, 52, a5, 0c, de, 58, 37, 9b, 80, 4d.
For decryption, first compute
λ
0
(s
(0)
d
,β
1
)=14 d9 c2 26 af 38 fe 74 c2 2b 3b 74 1f 49 a0
69 c0 d7 15 43 58 a4 6a 55,
where β
1
= 94 99 80 d7 91 d8 7f 65 ff 39 6d a6 36 fe a6 7b 8b fc 08 78
03 75 13 e5, s
(0)
d
= 59, c2, 37, 81, b6; 59, a8, df, 6f, 74, d1, 4a. Then compute
λ
1
(s
(1)
d
,β
2
)=4e 6f 20 70 61 69 6e 73 2c 6e 6f 20 67 61 69 6e 73 2e
which is equal to the plaintext α,whereβ
2
= fe 74 c2 2b 3b 74 1f 49 a0 69
c0 d7 15 43 58 a4 6a 55, s
(1)
d
= 17, 06, d2, ef, 52, a5, 0c, de; 38, af, 26, c2,
d9, 14.
For signing, taking randomly c9, c8, 02, 95, 2e, 76, b0, 8d and α
10
= 2d 49
df fb 14 69 63 d7 e6 8d, first compute
λ
0
(s
(0)
s
,αα
10
)=35 2e 1a 75 74 92 9e 1c b0 14 4c a4 b0 3c 60
02 25 7d 9b 70 fb 62 11 88 c2 ec 76 b3
where s
(0)
s
= 69, c9, c8, 02, 95; 74, d1, 4a, 2e, 76, b0, 8d. Then compute
λ
1
(s
(1)
s
,λ
0
(s
(0)
s
,αα
10
)) = 33 bb bc 7b 95 95 87 2a 9d ec 1e 54 7a 18 fb
31 1f 4c 9c d8 4d a1 82 17 7a ce 25 2b
362 9. Finite Automaton Public Key Cryptosystems
which is a digital signature of α.
For verifying, compute
λ(s
v
,β
3
)=4e 6f 20 70 61 69 6e 73 2c 6e 6f 20 67 61 69 6e 73 2e
which is equal to α,where
β
3
= 1e 54 7a 18 fb 31 1f 4c 9c d8 4d a1 82 17 7a ce 25 2b,
s
v
= 74, d1, 4a; ec, 9d, 2a, 87, 95, 95, 7b, bc, bb, 33, 17, 06, d2.
9.4 On Weak Keys
9.4.1 Linear R
a
R
b
Transformation Test
Notice that C
(M
n
,...,M
0
) in the public key of FAPKC is an (r
0
+···+r
n
,t
0
)-
order memory finite automaton. Let C
(M
n
,...,M
0
)beM
f
defined by (9.14),
where r = r
0
+···+r
n
,andt = t
0
. Let (9.16) be a linear R
a
R
b
transformation
sequence, where τ = τ
0
+ ···+ τ
n
,andeq
0
(i) is defined by (9.15). If for any
parameters x
i−1
, ..., x
i−r
, y
i+τ
, ..., y
i−t
, the equation eq
τ
(i) has a (or at
most one) solution x
i
, then from results in Sect. 3.1 of Chap. 3 a (τ+t, r)-order
memory finite automaton
¯
M can be feasibly constructed from eq
τ
(i) such that
C
(M
n
,...,M
0
) is a weak inverse (or an original weak inverse) with delay
τ of
¯
M. Therefore, a check process should be included in a key-generator of
FAPKC to sieve out such a C
(M
n
,...,M
0
), of which an original weak inverse
(or a weak inverse) can be obtained by linear R
a
R
b
transformation method.
IfthereisalinearR
a
R
b
transformation satisfying the condition mentioned
above, then C
(M
n
,...,M
0
) is sieved out. Although the number of those
linear R
a
R
b
transformations is huge, only one linear R
a
R
b
transformation
sequence is enough to check due to the following results in Sect. 4.1 of Chap. 4:
if for a linear R
a
R
b
transformation sequence (9.16) the condition holds, then
for any linear R
a
R
b
transformation sequence (9.16) the condition holds too.
The key of FAPKC of which C
(M
n
,...,M
0
) is sieved out by linear R
a
R
b
transformation method is called a weak key.Forn = 1, from results in
Sect. 4.2 of Chap. 4, the following cases are weak key: linear M
0
, 0 step delay
M
1
; linear M
0
, quasi-linear M
1
; linear M
0
, nonlinear M
1
of which a weak
inverse can be obtained by linear R
a
R
b
transformation method. The latter
is a more general case.
9.4.2 On Attack by Reduced Echelon Matrix
In Sect. 4.3 of Chap. 4, a method by reduced echelon matrix to construct
a weak inverse of a finite automaton is discussed, and it is shown that if
9.4 On Weak Keys 363
some inversion method by reduced echelon matrix based on injectiveness or
surjectiveness of D
22
ψ
l
ν
(x(i, ν+1)) is applicable to a finite automaton M,sois
the linear R
a
R
b
transformation method, where M = X, Y, Y
k
× X
h+ν
,δ,λ
is defined by
y
i
= ϕ
out
(y(i − 1,k)) + [C
0
,...,C
h
]ψ
lh
ν
(x, i), (9.18)
i =0, 1,...,
D
22
is described in Theorem 4.3.1. From this result, it is not necessary to
include a check process based inversion method by reduced echelon matrix in
a key-generator of FAPKC. Only weak keys of FAPKC can be broken using
the method by reduced echelon matrix!
9.4.3 On Attack by Canonical Diagonal Matrix Polynomial
Let M = X, Y, Y
k
× X
h+ν
,δ,λ be a finite automaton defined by (9.18). Let
C(z)=
h
j=0
C
j
z
j
.
Formally, we use z
j
ψ
l
ν
(x
i
,...,x
i−ν
) to denote ψ
l
ν
(x
i−j
,...,x
i−j−ν
), and z
j
x
i
to denote x
i−j
.Then
[C
0
,...,C
h
]ψ
lh
ν
(x, i)=
h
j=0
C
j
ψ
l
ν
(x
i−j
,...,x
i−j−ν
)
=
h
j=0
C
j
(z
j
ψ
l
ν
(x
i
,...,x
i−ν
)) = C(z)ψ
l
ν
(x
i
,...,x
i−ν
).
Suppose that C(z)=D(z)F (z). Let M
1
be a finite automaton defined by
x
i
= F (z)ψ
l
ν
(x
i
,...,x
i−ν
),
i =0, 1,...,
and M
0
a finite automaton defined by
y
i
= ϕ
out
(y(i − 1,k)) + D(z)x
i
,
i =0, 1,...
It is easy to see that M = C
(M
1
,M
0
). Since M
0
is quasi-linear, its weak
inverse can be easily constructed whenever it exists. Thus there is a feasible
inversion method for M whenever there is a feasible inversion method for
M
1
. Therefore, if for any parameters x
−1
, ..., x
−ν
, F (0)ψ
l
ν
(x
0
,...,x
−ν
)asa
364 9. Finite Automaton Public Key Cryptosystems
function of the variable x
0
is an injection, then M
1
is weakly invertible with
delay 0 and a weak inverse with delay 0 of M
1
can be feasibly constructed.
It is well known that the process of reducing canonical diagonal form for
matrix polynomials is feasible. We can feasibly find 0 a
1
··· a
r
, f
j
(z),
j =1,...,r, and two invertible matrix polynomials P(z)andQ(z) such that
C(z)=P (z)DIA
m,m
(z
a
1
f
1
(z),...,z
a
r
f
r
(z), 0,...,0)Q(z),
f
j
(z) | f
j+1
(z)forj =1,...,r−1andf
j
(0) =0forj =1,...,r. Take D(z)=
P (z)DIA
m,r
(z
a
1
,...,z
a
r
)andF (z)=DIA
r,m
(f
1
(z),...,f
r
(z))Q(z). Then
C(z)=D(z)F(z) is referred to as the derived factorization of type 2 by
canonical diagonal matrix polynomial. Similar, C(z)=D
(z)F
(z)isreferred
to as the derived factorization of type 1 by canonical diagonal matrix poly-
nomial, where D
(z)=P (z)DIA
m,r
(z
a
1
f
1
(z), ..., z
a
r
f
r
(z)) and F (z)=
DIA
r,m
(1,...,1)Q(z). If C(z)=D(z)F(z) is a derived factorization of type
1 or 2 by canonical diagonal matrix polynomial and F (0)ψ
l
ν
(x
0
,...,x
−ν
)as
a function of the variable x
0
is an injection for any parameters x
−1
, ..., x
−ν
,
then a weak inverse of M can be feasibly constructed as mentioned in the
preceding paragraph. On the other hand, from Theorem 4.4.5, there exists a
terminating and elementary R
a
R
b
transformation sequence
C
k
(z)
R
a
[P
k
]
−→ C
k
(z),C
k
(z)
R
b
[r
k+1
]
−→ C
k+1
(z),k=0, 1,...,τ
− 1,
where C
0
(z)=C(z). Let
¯
Q(z) be the submatrix of the first r rows of
C
τ
(z). From Corollaries 4.4.4 and 4.4.5, if F (0)ψ
l
ν
(x
0
,...,x
−ν
) as a func-
tion of the variable x
0
is an injection for any parameters x
−1
, ..., x
−ν
,then
¯
Q(0)ψ
l
ν
(x
0
,...,x
−ν
) as a function of the variable x
0
is an injection for any
parameters x
−1
, ..., x
−ν
. It follows that a weak inverse of M can be feasibly
constructed by linear R
a
R
b
transformation method. We conclude that keys
of FAPKC which can be broken by canonical diagonal matrix polynomial
method are weak keys. Thus it is not necessary to include a check process
based on reducing canonical diagonal matrix polynomial in a key-generator
of FAPKC.
9.5 Security
Since no theory exists to prove whether a public key system is secure or not,
the only approach is to evaluate all ways to break it that one can think.
We first consider ways that a cryptanalyst tries to deduce the private key
from the public key, and then ways of deducing the plaintext (respectively
signature) from the ciphertext (respectively message).