CN1177872A - Method for realizing digital signing with information appendix and checking method thereof - Google Patents

Abstract

A method for implementing a digital signature with an appendix to a message and a method for verifying such a signature. The method comprises the steps of: sending a message M in response, multiplying a hash code H(M) by g ^k , wherein g ^k is calculated by a random number K generated each time a signature is executed, and the result of the multiplication is determined by a modulus P performs a modular multiplication, and obtains the beginning part R of a signature by truncating its result value to Lq bits, and obtains the ending part S of a signature using a signer's secret key X, whose random number K is executed each time It is generated when signing, and R is calculated by S=(K-RX) mod q, and then a signature verification key Y and a message M including R and S are sent to verify the digital signature.

Description

Method for implementing digital signature with message appendix and verification method thereof

The present invention relates to digital signatures, and more specifically, the present invention relates to a digital signature method with message appendix, which can provide signature function for electronic files or data.

In general, digital signatures in the electronic exchange of information are the counterparts of handwritten signatures in traditional mail. As society relies more on information, due to the development of computers and electronic communication, all documents have changed from traditional mail to electronic data. In this case, the possibility of alteration and falsification of contracts or documents between entities, that is, between individuals, between individuals and groups, and between companies becomes high. To adapt to this new situation, a technology that provides a signature function to electronic documents is required, similarly to that in conventional mail.

That is, to accommodate the above-mentioned circumstances, digital signatures with message appendixes are used to provide information protection services such as authentication and integrity of data in information processing systems and inter-network communication systems. There is a need for a cryptographic technique for the digital signature technique, by which theft, forgery and alteration of electronic documents can be prevented.

Systems using cryptography are generally divided into public key systems and secret key systems. A cryptographic system of the secret key approach is difficult to manage because two systems wanting to communicate must share the same secret key, and cannot provide signatures that would give adequate protection, and because it cannot provide such things as unauthorized access denial and Inhibition and other functions. In the cryptographic system of the public key method, the public key and the secret key are calculated using a one-way function, and this mathematical solution is very difficult. Anyone who has a public copy of the public key can use this copy to perform a private communication because the public key is made public for use by anyone, while the secret key is protected by the user.

In digital signatures using the public key method, a pair of keys, a secret key for signing a message and a public key for verifying the signature, are used. That is, the pair of keys used in the digital signature method includes a public key for authentication and a secret key for signature.

One type of message signing using the public key method is a digital signature that performs message recovery. This method restores the message during the process of verifying the signature. This digital signature method is provided by the International Organization for Standardization and the International Electrotechnical Commission (ISO/IEC9796), and it is a digital signature that implements message restoration. At this time, the RSA algorithm is adopted, and its confidentiality is based on the difficulty of prime factor decomposition. In the RSA algorithm, it is difficult to add a digital signature to a message of any length because it must receive a message of limited length.

A digital signature with an appendix to a message is not the same as a digital signature that performs message restoration. In the digital signature with message appendix, a hash function is used to obtain the message. Since the signature is implemented after the message is simplified using a hash function, the signature and verification can be completed in a short time. ELGamal digital signature is an example of digital signature with message appendix and public key digital signature, whose secrecy is based on computing a discrete logarithm. However, it has the disadvantage that the signature length will be doubled when generating the signature.

It is an object of the present invention to provide a method for implementing digital signatures with message appendices in which a hash function is used in order to reduce the signature length.

Another object of the present invention is to provide a method for verifying a digital signature with a message appendix.

In order to achieve the first purpose, a method for implementing a digital signature with message appendix is provided here, when L _p and L _q represent the bit lengths of prime factors p and q, and satisfy 1<a<p- 1 and a ^(p-1)/q mod p＞1 when g=a ^(p-1) /q mod p, the method comprises the steps of: responding to a message M sent, multiplying the hash code H by g ^k ( M), where g ^k is calculated by the random number K generated whenever a signature is executed; the previous multiplication result is performed by a modulus P, and a signature is obtained by truncating the result value to L _q bits The beginning part R of a signer's secret key X is used to obtain the end part S of a signature, whose random number K is generated every time a signature is executed, and R is calculated by S=(K-RX) mod q, and then A signature verification key Y for verifying the digital signature and a message M including R, S are transmitted.

In order to achieve the second purpose, a method for verifying a digital signature with a message appendix is provided here, when L _p and L _q represent the bit lengths of the prime factors p and q, and satisfy 1<a<p-1 and a ^(p-1)/q mod p>1 when g=a ^(p-1)/q mod p, the method comprises the steps of receiving the messages Y, M, S and R sent in claim 1, and Confirm 0<R<q and 0<s<q, calculate g ^s and Y ^R through the hash function value H(M) corresponding to the message M, received S and R, and perform modular multiplication according to the modulus P, Then, when the result value after truncating the modular multiplication result into L _q bits is equal to the received value R, a user with the public verification key Y can confirm the signed received message M.

The above objects and advantages of the present invention will become more apparent by describing in detail its preferred embodiments with reference to the accompanying drawings, in which:

Fig. 1 is a flow chart depicting a method for generating a digital signature according to the present invention.

Fig. 2 is a flowchart describing a method for verifying a generated digital signature.

Hereinafter, the present invention will be described in detail with reference to the accompanying drawings. Before explaining the present invention, reference symbols used in the present invention will be described as follows. M represents a send message. p and q represent prime factors. L _p and L _q denote the bit lengths of p and q, respectively. Define g=a ^(p-1)/q mod P when 1<a<p-1 and a ^(p-1)/q mod p>1 are satisfied. X represents a signer's secret signing key. Y represents a public signature verification key to verify the digital signature: Y=g ^x mod pK represents a random number, which is any element in {1, 2, . . . , q-1}. This digital signature Σ is obtained by concatenation of R and S. Both R and S are smaller than q.

X, Y, p, and q are all fixed variables, where p, q, and g are shared by all users, however, the random number K is reselected whenever a signature is generated. K and X used in the signature process should not be known by others, and their values are selected between 0 and the prime factor q. H is a collision-resistant hash function. h=H(M) is a hash code. It is the result of hashing the signed message. In addition, "‖" means juxtaposition.

According to the above definition and understanding, the digital signature with message appendix of the present invention can be generated as follows. Fig. 1 is a flowchart of a method for generating a digital signature according to the present invention.

First, a hash code H(M) of a message M is generated by using a hash function, wherein the hash function is a one-way function (step 100). Each time a signature is generated, an optional random number K is selected from {1, 2, . . . , q-1} (step 110). Compute g ^K using the generated random numbers (step 120). g ^k is a message-independent value and can be precomputed.

After the modulo-p multiplication of this hash code by the precomputed value (step 130), the result is truncated to be L _q bits long. Truncation means discarding all bits longer than L _q bits. The result is R, which corresponds to the beginning of the signature (step 140).

S=(K-RX) mod q is computed using the signer's secret signing key to generate the epilogue of the signature (step 150). The signature Σ=RIIS is output by concatenating R and S (step 160). This signature is added to the message and {Y, M, R and S} are transmitted along with the signature's verification key Y (step 170).

Fig. 2 is a flow chart of a method for verifying the generated digital signature, a verifier confirms 0<R<q and 0<S<q according to ∑=RIIS so as to verify the signature, where ∑ is received by the verifier One of the signed messages (step 200). In the case where the above two conditions are met, the signature is verified as shown in Figure 2. Compute g ^s , Y ^R and the hash function value H(M) from the received message M and the received S, R (step 210), and perform modulo p multiplication (step 220). _VR is generated by truncating the modular multiplication result to _Lq bits (step 230), and compared to the received value _R (step 240). When V _R equals R, this user, having the signer's public attestation key Y, can confirm that the signature Σ=RIIS of the received message M was signed with the signer's secret signing key X (step 250). The fact that _VR is not equal to R means that the message M was signed with an illegal signature or changed by an attacker. In this case, the message M is treated as invalid data (step 260).

According to the present invention, a signature function in a conventional mail can be provided to an electronic document and an original drafter capable of authenticating the electronic document.

When the content of the original file is changed by a third party, it can be known that the file has been changed by a third party and an electronic signature required for electronic money can be provided. In addition, this digital signature can be used in authorization systems and can increase the speed of verifying the signature.

Claims (2)

1, a kind ofly is used to realize that one has the method for the digital signature of information appendix, works as L _pAnd L _qThe bit length of expression prime p and q, and at satisfied 1＜a＜p-1 and a ^(p-1)/qMod p＞1 o'clock g=a ^(p-1)/qMod p comprises step:

The message M that response sends uses g ^kMultiply by hash code H (M), g wherein ^kCalculate by the random number K that when carrying out a signature, produces;

Described multiplication result is carried out mould by a modulus P take advantage of, and be L by its end value is blocked _qThe position and obtain one the signature beginning part R;

Adopt the privacy key X of a signer and obtain an ending S who signs, its random number K is producing when carrying out signature, and by S=(K-RX) mod q calculating R; And

Transmission one is used for the signature verification key Y of confirmer digital signature and comprises the message M of described R, S.

2, a kind of method that is used to confirm have the digital signature of information appendix is worked as L _pAnd L _qThe bit length of expression prime p and q, and at satisfied 1＜a＜p-1 and a ^(p-1)/qMod p＞1 o'clock g=a ^(p-1)/qMod p comprises step:

Be received in message Y, the M, S and the R that send in the claim 1, and confirm 0＜R＜q and 0＜S＜q;

Calculate g by S and R with the corresponding Hash functional value H of message M (M), described reception ^sAnd Y ^R, and carry out mould according to modulus P and take advantage of;

When taking advantage of the result to be truncated into L described mould _qDuring value R that the end value behind the position equals to be received, make a user with open verification key Y can confirm the reception message M that signs.

Images