Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1997-10-30
2002-01-22
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C380S028000, C380S030000
Reexamination Certificate
active
06341349
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and a system for generating and/or verifying a digital signature by using a public key encryption method for securing the security in a computer network.
The digital signature technology for imparting electric documents or the like for electronic comments or transactions with a function equivalent to that of a conventional seal (hanko in Japanese) promises high efficiency utilization of computer-network system. However, with the conventional electronic mail encryption technology (also known as Privacy Enhanced Mail or PEM in abbreviation), it is impossible to process more than one digital signature for a single enhanced mail. In this conjunction, in the electronic commerce fields, it is expected in the not-so-distant future that the electronic document such as message and the like affixed with a number of digital signatures including not only the digital signature of a purchaser but also those of a distributor, salesman and/or monetary business-man will be handled. Under the circumstances, there arises a demand for the multiple digital signature technology which allows the electronic documents affixed with a plurality of digital signatures to be processed. In this conjunction, it is noted that a person receiving an electronic document affixed with a plurality of digital signatures will be forced to verify the authenticity of plural or N digital signatures written by other persons before writing or generating his or her own single digital signature. Thus, in order to enhance the availability of the digital signature facility in the computer network system, it will be required to increase the speed for verification of the plural (N) digital signatures. Besides, it is conceivable that in the electronic commerces, there is a possibility that comments may be added by a plurality of persons in the course of processing the electronic document.
For having better understanding of the invention, description will first be made in some detail of the technical background of the invention. As a typical one of the digital signature techniques known heretofore, there may be mentioned the public-key cryptography elliptic curve system disclosed in J. Koeller, A. J. Menezes, M. Qu and S. A. Vanstone: “Standard for RSA, Diffie-Hellman and Related Public-Key Cryptography Elliptic Curve Systems (Draft 8)” in “IEEE P1363 Standard” published by the IEEE, May 3, 1996 and May 14, 1996, respectively.
FIG. 9
is a schematic diagram showing generally a configuration of a computer network system in which the techniques disclosed in the above-mentioned literatures are adopted.
Referring to
FIG. 9
, there are connected to a network
1001
a system manager's computer
1002
, a user A's computer
1003
and a user B's computer
1004
for mutual communication.
Operations of the individual units shown in
FIG. 9
will be described below.
System Setup
The system manager's computer
1002
is in charge of generating an elliptic curve (E)
1006
. Subsequently, a base point (also referred to as the system key) (P)
1007
of the order (n)
1008
is generated and registered in a public file
1005
.
Key Generation
A key generating function module
1011
incorporated in the user A's computer
1003
is designed to execute the processing steps which will be mentioned below.
Step
1
: In an interval [2, n−2], an integer d
A
is selected at random as a private key.
Step
2
: A key Q
A
is computed in accordance with Q
A
=d
A
P.
Step
3
: The key (Q
A
)
1015
is opened to the public as the public key. More specifically, the public key (Q
A
)
1015
is transmitted together with the identifier name of the user A to the system manager's computer
1002
via the network
1001
, whereon the identifier name of the user A is written in the public file
1005
at a column
1009
for the user A's name with the value of the public key (Q
A
)
1015
being written in a column
1010
for the public key Q
A
.
Step
4
: In the user A's computer
1003
, the value of the private key (d
A
)
1014
is held as the private key of the user A.
Digital Signature Generation Process
A digital signature generating function module
1033
incorporated in the user A's computer
1003
is designed to execute the processing steps mentioned below.
Step
1
: Message (M)
1016
is received.
Step
2
: Hash value e=H(M) is computed by using a hash function (H)
1028
.
Step
3
: Random number
k
is selected from the interval [2, n−2] by using a random number generation function
1029
.
Step
4
: Point kP=(x, y) is computed by a so-called “scalar multiplication on elliptic curve (E)”
1030
.
Step
5
: A first tally
r
given by r=x+e (mod n) is determined in accordance with the modular computation “r=x+e (mod n)”
1031
.
Step
6
: A private key (d
A
)
1017
is inputted to modular computation process “s=k−d
A
r (mod n)”
1032
for thereby determining a second tally
s
(=k−d
A
r (mod n)).
Step
7
: A message M
1016
and the digital signature (r, s)
1019
are sent to the user B's computer
1004
via the network
1001
.
As the parameters required for the computations performed by the digital signature generating function module
1033
, the elliptic curve (E)
1006
, the base point which may also be referred to system key (P)
1007
and the order (n)
1008
registered in the public file
1005
held by the system manager's computer
1002
are referenced.
Digital Signature Verification Process
A digital signature verifying function module
1023
incorporated in the user B's computer
1004
is designed to execute the processing steps mentioned below.
Step
1
: The user A's public key (Q
A
)
1010
is fetched from the public file
1005
held by the system manager's computer
1002
to be set as a public key (Q
A
)
1020
. Additionally, the base point (system key) (P)
1007
is fetched from the public file
1005
held by the system manager's computer
1002
to be set as the base point (P)
1007
B. Furthermore, the digital signature (r, s)
1019
sent from the user A's computer
1003
is received to be set as a digital signature (r, s)
1021
. Besides, the message (M)
1016
sent from the user A's computer
1003
is received to be set as a message (M)
1022
.
Step
2
: The base point or system key (P)
1007
B, the public key (Q
A
)
1020
, the digital signature (r, s)
1021
are inputted to the process “scalar multiplication on elliptic curve (E)” and “addition”
1024
to thereby carry out the calculation “(x, y)=sP+rQ
A
”.
Step
3
: The message M
1022
is inputted into the hash function H
1025
to thereby compute the hash value e=H(M).
Step
4
: Through the computation process “r′=x+e (mod n)”
1026
, a first tally “r′=x+e (mod n)” is determined.
Step
5
: When the decision “r=r′?”
1027
results in r=r′ or YES, data “authenticated” is outputted, and if otherwise, “not authenticated” is outputted.
As the parameters required for the computations performed by the digital signature verifying function module
1023
, the elliptic curve (E)
1006
, the base point or system key (P)
1007
and the order (n)
1008
as registered in the public file
1005
held by the system manager's computer
1002
are referenced.
Through the processes described above, the digital signature (r, s) functions as an electronic seal (i.e., seal or “hanko” impressed electronically by the user A for the message M). To say in another way, the user B can hold the set of the message M and the digital signature (r, s) as the evidence indicating that the message M is issued by the user A. Further, although the user B can recognize the authenticity of the set of the message M and the digital signature (r, s), the user B can not originally generate the set of the message M and the digital signature (r, s). For this reason, the user A can not negate later on the fa
Kurumatani Hiroyuki
Takaragi Kazuo
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Peeso Thomas R.
LandOfFree
Digital signature generating/verifying method and system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signature generating/verifying method and system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signature generating/verifying method and system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874280