Cryptography Reference
In-Depth Information
3
Sato-Araki Scheme
In this section, we summarize the two attacks described by Coppersmith against
Sato-Araki scheme. We will analyze these attacks in the extended HS scheme
later.
Sato-Araki scheme [20] uses quaternion algebra over
Z
/N
Z
.Let
R
be a
Z
/N
Z
-
analogue of Hamilton's quaternion algebra. Here,
R
is defined by
R
=
Z
/N
Z
·
1
⊕
Z
/N
Z
·
i
⊕
Z
/N
Z
·
j
⊕
Z
/N
Z
·
ij,
and
i
2
=
j
2
=
ji
.
R
is identified with a subring of a matrix ring by
the embedding homomorphism,
−
1
,ij
=
−
R
a
0
·
1+
a
1
·
i
+
a
2
·
j
+
a
3
·
ij
(5)
a
0
+
a
1
√
−
1
a
3
+
a
2
√
−
[
√
1
a
3
+
a
2
√
−
a
1
√
−
−→
∈
M
(2
,
Z
/N
Z
−
1])
.
−
1
a
0
−
1
Note that
R
is closed by the transpose operation. Sato-Araki scheme is described
as follows.
Key Generation
The secret key consists of the primes
p, q
and
u
R
×
. The public key consists
∈
(
u
T
)
−
1
u
−
1
of
N
and
h
:=
−
∈
R
.
Signature Generation
Let
M
=
M
T
R
×
randomly. We now compute
∈
R
be a message. Choose
ρ
∈
C
1
:=
ρ
−
1
M
+
ρ
T
,
C
2
:=
u
(
ρ
−
1
M
ρ
T
)
−
∈
R
.(
C
1
,
C
2
) is a signature.
Verificat ion
If
C
1
C
1
+
C
2
h
C
2
=4
M
, then the signature is accepted, otherwise it is rejected.
3.1
Attacks against Sato-Araki Scheme
The security of Sato-Araki scheme was based on the diculty of solving an
equation over
R
,
X
T
X
+
h
≡
0mod
N.
However, Coppersmith proposed two ecient attacks [4] by using a special prop-
erty of quaternion algebra, without factorizing
N
.
Coppersmith's first attack.
The first attack proposed by Coppersmith is a
chosen message attack. For
i
=1
,
2
,
3, let (
C
(
i
1
,
C
(
i
2
) be signatures for messages
M
i
. The key of the attack is as follows: For
i
=1
,
2
,
3,
(
C
(
i
1
)
T
u
C
(
i
)
are symmetric matrices
.
(6)
2
