Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2000-09-05
2002-04-09
Hayes, Gail (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S037000, C380S042000, C708S203000, C708S209000, C708S503000
Reexamination Certificate
active
06370247
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a technique for ensuring security of digital signature, data encryption, etc. in a computer network, and particularly to a method of converting a message to a hash value which is difficult to inversely convert.
A public key cipher system has been known as an encryption system for data such as electronic mail which is sent and received through a network. The processing flow based on the public key cipher system is as follows:
(1) A user beforehand distributes to transmitters a public key for encrypting an electronic mail to be sent to the user.
(2) A transmitter who wishes to send the electronic mail to the user encrypts the electronic mail by using the public key which is distributed from the user who is the intended recipient of the electronic mail, and then transmits the encrypted electronic mail to the destination of the electronic mail.
(3) The user decrypts the encrypted electronic mail by using the user's own secret key (having a numeric value different from the public key) when receiving the encrypted electronic mail which is encrypted by the public key distributed by himself/herself.
This public key cipher system has been applied not only to a data encryption technique, but also to a digital signature technique which is a technique for electrically verifying legitimacy of a contract or the like in electronic commerce using a network.
However, a lot of time is needed if a digital signature for a long message is generated by using only the public key cipher in the digital signature technique. Therefore, there has been proposed a method of temporarily compressing a message to shortened data and then generating a digital signature for the compressed data.
Here, for this type of data compression, it is unnecessary to compress the data so that an original message can be restored from the compressed data unlike normal data compression, however, it is necessary to compress the data so that the compressed data has a kind of encryption characteristic. A hash function has been proposed to implement such compression.
A message for an electronic commerce document or the like, for example, Document A: “To Taro & Co. Esq., I will purchase a car (catalog No. 1443) at one million and forty thousand yen. Mar. 10, 1996 Yoshiura” is input data to the hash function. There is no upper limit to the length of the input data.
The hash function subjects the input data to processing like encryption conversion to compress the input data to data having a fixed short length. For example, hash value: 283AC9081 E83D5B28977 is an output of the hash function.
This hash value is called a message digest or a finger print, and ideally substantially only one hash value exists for one input data (message) in the world. In order to guarantee that “substantially only one exists in the world”, it is generally recognized that the length of the hash value must be set to at least about 128 bits. More specifically, the hash function must have the following characteristics.
(1) One-way Property
When an output value of a hash function is given, it must be computationally difficult to determine another message which brings the same output value as the above output value.
For example, it is assumed that the birthday of Kazuo is February 22nd. In order to search for another person whose birthday is coincident with Kazuo's birthday, it is statistically sufficient to investigate the birthdays of about 183 (365/2) persons.
The same is satisfied even when the person is replaced by a message and the birth day is replaced by a hash value. That is, if the length of the hash value is set to 160 bits, the hash value can have any one of 2
160
possible values (i.e., the total number of possible hash values is equal to 2
160
). In order to search another message having the same hash value as a message concerned, it is required to investigate messages of 2
160
/2 (=2159), and this is computationally difficult.
(2) Collision Free Property
The message and the hash value may be any values (i.e., no limitation is imposed on the message and the hash value). At any rate, it must be computationally difficult to find out two different messages which have the same hash value.
For example, when any two persons having the same birthday are required to be found out, the birthdays of about 24 persons (=365
½
) need to be investigated in probability.
This is also satisfied even when the person is replaced by the message and the birth day is replaced by the hash value. That is, if the length of the hash value is set to 160 bits, in order to find out two different messages (any messages are possible) having the same hash value, it is necessary to investigate a set of messages of about 2
160
/2=2
80
on average. This number is smaller that that in the case of the one-way property, but this value is still computationally difficult. Various methods have been proposed to implement the hash function which requires the above characteristics, and at present a method of repeating character-substitution and transposition to obtain hash values have mainly been used. The following paper
1
discloses the processing principle of the method:
ISO/IEC 10118-2, “Information technology—Security Techniques—Hash-functions: Part 2: Hash-functions using an n-bit block encryption algorithm” (1994)
The hash function as disclosed in the paper
1
will be described with reference to FIG.
27
.
The left side of
FIG. 27
is a diagram showing the processing flow of a general hash function, and the right side of
FIG. 27
is a diagram showing the processing flow when an encryption function such as DES (Data Encryption Standard) is used for character-substitution/transposition repeating processing
3005
shown in the left side of FIG.
27
.
As shown at the left side of
FIG. 27
, a message
3001
to be compressed is divided into a first section P
1
3002
, a second section P
2
3003
, . . . , for every predetermined length, and these sections are successively input to the hash function
3007
.
The hash function
3007
subjects the first section P
1
3002
to the character-substitution/transposition repeating processing
3005
by using an initial value
3004
as a parameter, thereby calculating a first intermediate output.
Subsequently, the hash function subjects the second section P
2
3003
to the character-substitution/transposition repeating processing
3005
by using the first intermediate output as a parameter (in place of the initial value
3004
), thereby calculating a second intermediate output.
The above processing is repeated until the data of the final section is input, and the finally calculated intermediate output is used as a hash value Hash
3006
.
Here, in the paper
1
, an encryption function (block encryption) such DES of USA encryption standard is used for the character-substitution/transposition repeating processing
3005
. Such a hash function is called a “hash function using block encryption”, and it has been standardized in ISO (International Organization for Standardization).
The “hash function using block encryption” will be described below.
As shown at the right side of
FIG. 27
, the first section P
1
3002
is input to the encryption function
3009
with a parameter which is obtained by converting the initial value
3004
with a conversion function
3008
. Exclusive OR
3010
is conducted between the encryption result based on the encryption function
3009
and the first section P
1
3002
bit by bit, thereby calculating the first intermediate output based on the character-substitution/transposition repeating processing
3005
.
Subsequently, the first intermediate output is fed back and then converted with the conversion function
3008
. Thereafter, by using the first intermediate output thus converted as a parameter, the second section P
2
3003
is input to the encryption function
3009
. The exclusive OR
3010
is conducted between the encryption result based on the encryption function
3009
and the second section P
2
3003
bit by bit, thereby calculat
Kurumatani Hiroyuki
Takaragi Kazuo
Darrow Justin T.
Hayes Gail
LandOfFree
Hash value generating method and device, data encryption... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hash value generating method and device, data encryption..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash value generating method and device, data encryption... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2834402