Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1999-07-15
2004-02-24
Sheikh, Ayaz (Department: 2131)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C380S028000, C380S030000, C380S044000, C380S046000
Reexamination Certificate
active
06697946
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an apparatus for performing secret communications and digital signatures by a public key cryptosystem, and especially relates to a message recovery signature apparatus whose security is based on the discrete logarithm problem.
DESCRIPTION OF THE PRIOR ART
Nyberg-Rueppel proposes a message recovery signature scheme which is carried out by a public key cryptosystem using the discrete logarithm problem as a basis for security (see Nyberg & Rueppel “A New Signature Scheme Based on the DSA Giving Message Recovery” 1
st ACM Conference on Computer and Communications Security
(1993)).
“Discrete logarithm” is a logarithm over a finite field.
“Discrete logarithm problem” is as follows. Let p be a prime number or a prime number raised to a given power, g be a primitive root of a finite field GF(p), and y, p, and g be any elements of GF(p) aside from zero. The problem is to find an integer x that satisfies
y=g
x
(Equation 1.1)
where 0≦x≦p−1.
“Using the discrete logarithm problem as a basis for security” is due to the following reason. Though the exponential calculation is easy, the above logarithmic calculation is extremely difficult for a large finite field GF(p), such as GF(2
127
) Such a logarithmic calculation corresponds to the calculation of the inverse of a one-way function and thus assists in the security of encryption.
“Public key cryptosystem” is a cryptosystem that uses different keys for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Public key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communications with a large number of users.
“Message recovery signature” is a signature for certifying the validity of the signer, with the message being embedded within the signature. With this technique, the message and the signature do not have to be sent separately, so that the traffic for transmission can be reduced.
FIG. 11
is a sequential view showing the processing of the above conventional signature scheme.
A user A
610
, a management center
620
, and a user B
630
are connected with each other via a network. Here, the user A
610
signs a message m and sends it to the user B
630
under management of the management center
620
.
<Public Key Generation>
A prime number is set as p, an element of GF(p) is set as g, and the order of g is set as q as the system conditions. Which is to say, q is the smallest integer that satisfies
g
q
=1(mod
p
) (Equation 1.2)
First, the management center
620
generates a public key y
A
for the user A
610
using the user A's secret key x
A
which has been informed beforehand, according to
y
A
=g
xA
(Equation 1.3)
(S
640
~S
641
).
The management center
620
then reveals the system parameters p, q, and g together with the public key y
A
of the user A
610
to the user B
630
(S
643
)
<Signature and Transmission>
The user A
610
generates a random number k (S
644
), calculates
r
1
=g
k
(mod
p
) (Equation 1.4)
r
2
=m/r
1
(mod
p
) (Equation 1.5)
r
2
′=r
2
(mod
q
) (Equation 1.6)
s=k−r
2
′x
A
(mod
q
) (Equation 1.7)
in sequence (S
645
~S
648
), and sends s and r
2
to the user B
630
as a ciphertext (r
2
,s) (S
649
).
Here, r
1
is referred to as a commitment, Equation 1.5 as a message-mask equation, and Equation 1.7 as a signature equation. Equation 1.7 leads to the following six types of
ak=b+cx
A
(mod
q
) (Equation 1.8)
where (a,b,c) is a permutation of (
1
,r
2
′,s), that is,
a=1, b=r
2
′, c=s
a=1, b=s, c=r
2
′
a=r
2
′, b=1, c=s
a=r
2
′, b=s, c=1
a=s, b=r
2
′, c=1
a=s, b=1, c=r
2
′
Note that (mod p) and (mod q) denote operations modulo p and q, respectively.
<Message Recovery>
The user B
630
receives the ciphertext (r
2
,s) and recovers the message m by computing
g
s
y
A
r2′
r
2
=m
(mod
p
) (Equation 1.9)
with the revealed public key y
A
and system parameters p, q, g, a, b, and c (S
650
). Equation 1.9 is derived from
&AutoLeftMatch;
m
=
r
1
r
2
=
g
k
r
2
=
g
s
+
r2
′
xA
r
2
=
g
s
g
xAr2
′
r
2
=
g
s
y
A
r2
′
r
2
(Equation 1.10)
Thus, the above conventional scheme is a breakthrough in the sense that message recovery signatures by a public key cryptosystem based on the discrete logarithm problem are made possible for the first time.
Nevertheless, this conventional scheme is vulnerable to four types of attack given below.
(Signature-equation Attack)
The signature-equation attack is as follows.
If a forger acquires the message m and its signature (r
2
,s), the forger can forge a new message mg
d
(d is any element of GF(p)), sign the message mg
d
, and send it to the user B.
Which is to say, the forger sends a ciphertext (r
2
,s+d) to the user B. The user B then calculates
&AutoLeftMatch;
g
s
+
d
y
A
r2
′
r
2
=
g
s
y
A
r2
′
r
2
g
d
=
m
g
d
(Equation 1.11)
If the recovered message mg
d
is intelligible, the user B will think that the message is from the user A. Hence the forger can successfully sign the new message mg
d
without knowledge of the secret key x
A
.
(Homomorphism Attack)
The homomorphism attack is as follows.
If a forger chooses a message mm, has the user A sign the message mm, and acquires the signature, the forger can impersonate the user A and sign a desired message mmg
d
.
This attack is possible for the same reason as the signature-equation attack. The difference with the signature-equation attack is that the forger can sign the desired message mmg
d
.
(Redundancy Attack)
The redundancy attack is as follows.
If a forger acquires the message m and its signature (r
2
,s), the forger can sign a new message mm that satisfies
rr
2
=r
2
′+nq
(≠
r
2
) (Equation 1.12)
mm=rr
2
×(m/r
2
) (Equation 1.13)
Which is to say, the forger sends a ciphertext (rr
2
,s) to the user B. Then the user B computes
&AutoLeftMatch;
g
s
y
A
rr2
′
rr
2
=
g
s
y
A
r2
′
rr
2
=
(
m
/
r
2
)
rr
2
=
m
m
(Equation 1.14)
If the recovered message mm is intelligible, the user A will think that the message is from the user A.
This attack is based on redundancy between r
2
′ used in Equation 1.7 and r
2
calculated in Equation 1.6.
(Recovery-equation Attack)
The recovery-equation attack is as follows.
Without performing communications beforehand, a forger can sign a message My
A
e
(e is an element of GF(p)) using any new M (M is an element of GF(p)).
Specifically, the forger determines rr
2
and ss that satisfy
rr
2
=My
u
g
v
(where
u
and
v
are elements of
GF
(
p
)) (Equation 1.15)
ss=−v
(Equation 1.16)
e=rr
2
′+u
(Equation 1.17)
and sends a ciphertext (rr
2
,ss) to the user B. The user B then calculates
&AutoLeftMatch;
g
ss
y
A
rr2
′
rr
2
=
y
A
e
My
=
My
A
e
(Equation 1.18)
If the recovered message My
A
e
makes sense, the user B will think that the message is from the user A.
This attack is based on that, for the elements u and v of GF(p), there are solutions that satisfy
rr
2
=My
A
u
g
v
(Equation 1.19)
v=−b/a
(where
a
and
b
are elements of {1
,r
2
′,s
}) (Equation 1.20)
The above four attacks are detailed in Atsuko Miyaji
Weakness in Message Recovery Signature Schemes
1 Institute of Electronics, Information, and Communication Engineers, Information Security Workshop (July 1995), Nyberg & Rueppel “A New Signature Scheme Based on the DSA Gi
Matsushita Electric - Industrial Co., Ltd.
Sheikh Ayaz
Song Hosuk
LandOfFree
Message recovery signature apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Message recovery signature apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message recovery signature apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326864