JP2000041035A - Authentication system, authentication method, and recording medium - Google Patents

Abstract

(57) [Summary] [Problem] To enable a user to judge that signatures of a plurality of signers are valid without increasing the signature information no matter how many times the signature is issued. SOLUTION: A key manager unit 1 generates secret keys e1 to ei and decryption keys d1 to di and distributes them to each signer as predetermined. The first signer unit 2 is operated by a drafter having a secret key e1 and a decryption key d1, and encrypts, for example, a target document created by the drafter with a signature using the secret key e1, and then executes the subsequent signer unit. Transfer to The signer units 3 to 5 are operated by a j-th signer having a secret key ej, a decryption key d (j-1) and dj, and use the decryption key d (j-1) to execute the signer unit in the preceding stage. Decrypts and confirms the ciphertext C (j-1) of the preceding stage transferred from, and encrypts the ciphertext C (j-1) with a signature using the secret key ei.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technology for realizing electronic authentication by performing a signature of target data such as document data and a restoration confirmation of the signed data. The present invention relates to an authentication system and an authentication method suitable for an authentication work based on confirmation and signature by an approver.

[0002]

2. Description of the Related Art As business procedures in companies, government offices, and the like, business processes that require approval by a plurality of certifiers for a single document, such as a so-called approval document, are often used. . For example, the draft decision document is:
A decision is made by obtaining approval from at least one predetermined approver, and processing is performed according to the decision result. When drafting and approving, by signing or sealing the relevant document, the person in charge and the person in charge certify that the contents are genuine or legitimate. In recent years, such an operation of performing an authentication decision such as a decision is made, for example, by a LAN (Loca
(1) An electronic approval technology for performing electronic processing using electronic mail or the like in a network such as an area network has been proposed and developed.

In such an electronic decision, an electronic signature, that is, an operation for electronically proving that the contents of a certain document or file are genuine or legitimate is indispensable. As a digital signature technology, there is a technology of encrypting a target document or file using a public key algorithm, and virtually attaching its own certificate.

For example, as shown in FIG. 11, information of an original document is compressed and a hash is taken to obtain information of the original document + hash. This hash is encrypted using a predetermined encryption key to obtain information of the original document + signature. This original document + signature information,
This is a signature document encrypted by the signature.

[0005] In a public key cryptosystem using a public key algorithm, an encryption key composed of a pair of one secret key and one public key is generally used. Only one encryption process is performed.
That is, as shown in FIG. 12, at the time of signature, a plaintext such as an original document is signed by encryption using a secret key to obtain a ciphertext. The cipher text is decrypted using the public key, thereby returning to plain text and confirming the content.

When a plurality of signers sign using such a conventional signature authentication system, signature information is added each time a signature is issued. That is, the amount of signature information attached each time a signature for approval or the like is added.
Therefore, when approval by a large number of approvers is required, the data amount of a document or the like transferred between the signers gradually increases.

For example, as shown in FIG. 13, when the drafter signs the original document, the original document + signature is obtained, and this file is transferred to the first approver. When the first approver approves (signs) this file, the original document + signature + authorization 1 is obtained, and this file is transferred to the second approver. When the second approver approves this file, the original document + signature + authorization 1 + authorization 2 is obtained, and this file is transferred to the third approver. When a third approver approves this file, the original document +
Signature + Approval 1 + Approval 2 + Approval 3, and this file is transferred to the next approver. In this way, the file size increases each time a signature is sequentially issued for approval.

[0008]

As described above, in the existing authentication system, signature information is sequentially and cumulatively added to an original document every time a signature is signed. For this reason, there has been a problem that the information amount is accumulated and increased each time a signature is repeated. In particular, when signatures are made by many signers, such as in decisions requiring many approvers,
The transfer data size of the decision document or the like to be transferred is significantly increased after the decision route.

On the other hand, in business processing and the like, in order to facilitate various processes, it is desired to standardize files and the like to be transferred and make the sizes uniform. In particular, in the case of a decision document or the like, it may be necessary that a document file or the like that requires a signature has a fixed format. When a fixed format is required as described above, a file or the like increases every time a signature is issued, the format is broken, and a system in which the fixed format cannot be maintained cannot be used. For example, EDI (Electronic Commerce)
In the case of Data Interchange (electronic data exchange), a signature in a fixed format is desirable.

[0010] The present invention has been made in view of the above circumstances, and it is possible to determine that the signature information of a plurality of signers is valid without increasing the signature information no matter how many times the signature is performed. An object of the present invention is to provide an authentication system and an authentication method that can perform the authentication.

[0011]

In order to achieve the above object, an authentication system according to a first aspect of the present invention provides a public key corresponding to a secret key for each signer and a signature at each stage according to a predetermined authentication order. A key is generated, and for the first signer, information including the private key and the public key of the first signer is transmitted to the second signer.
For the third and subsequent signers, key management means for distributing information including the private key and public key of the signer and the public key of the immediately preceding signer to each signing means, and authentication target data,
Encryption means for signing and encrypting using the private key of the first signer, confirmation means for confirming the encrypted data using the public key of the first signer, and encryption by the encrypting means First signing means for a first signer having transfer means for transferring the obtained data to the next-stage signing means, and transferring the transfer data transferred from the signing means corresponding to the immediately preceding signer to the immediately preceding signer. Confirmation means for confirming using the signer's public key in the step, encryption means for signing and encrypting the transfer data using the signer's secret key in the step, and encryption by the encryption means. A second signer and a second signer, each of which has a confirmation unit for confirming the encrypted data using the public key of the signer of the relevant stage, and a transfer unit for transferring the data encrypted by the encrypting unit to the signature unit of the next stage. And second signing means for It is.

[0012] The key management means is means for publishing a public key for confirming data encrypted by the signature at each stage only to a signer of the corresponding signature and a signer immediately after the signer. There may be.

[0013] An authentication system according to a second aspect of the present invention generates a private key and a public key for each signer, and for the first signer, the corresponding private key and the second and subsequent signatures. A key managing means for distributing the relevant private key and the public key of the immediately preceding signer to each signing means, a signing means for signing the data to be authenticated using the private key of the signer, First signing means for a first signer having transfer means for transferring data signed by the signing means to the next-stage signing means; and transfer data transferred from the immediately preceding signing means to the immediately preceding signing means. Confirmation means for confirming using the signer's public key at the stage, signature means for signing the transfer data transferred from the signature unit at the immediately preceding stage using the signer's private key at the stage, and the signature means By Comprising a second signature means for second and subsequent signer having a transfer means for transferring the signed data to the signature means of the following steps.

An authentication system according to a third aspect of the present invention comprises: means for generating a private key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order; For the signer, a key comprising means for notifying the private key of the first signer, and means for notifying the private key of the signer and the public key of the immediately preceding signer for the second and subsequent signers. It is characterized by comprising a management means, confirming the signature using the notified public key, and performing the signature using the notified private key.

[0015] The key management means may be means for disclosing a public key for confirming data encrypted by the signature at each stage only to a signer immediately after the signer of the corresponding signature. .

[0016] The key management means may be means for generating a public key for confirming only data encrypted by signatures in all stages before the corresponding stage.

An authentication method according to a fourth aspect of the present invention comprises:
A key generation step of generating a private key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order;
For the second signer, information including the corresponding private key and the public key corresponding to the signature by the secret key is used. For the second and subsequent signers, the relevant private key, the secret key and the immediately preceding signer are used. A key management step including a distribution step of distributing information including a public key corresponding to the signature of the private key to each signer, and signing and encrypting the data to be authenticated using the secret key corresponding to the signer. Encrypting the encrypted data, confirming the encrypted data using the public key corresponding to the signature, and transferring the data encrypted in the encrypting step to the next signer A signature step for the first signer having a signature and a first authentication step for confirming the transfer data transferred from the signer at the immediately preceding stage using a public key corresponding to the signature by the signer at the previous stage. Step, an encryption step of signing and encrypting the transfer data using the secret key corresponding to the signer of the stage, and encrypting the encrypted data using a public key corresponding to the signature in the encryption step. A second confirming step for confirming, and a signing step by a second or subsequent signer having a transfer step of transferring the data encrypted by the encrypting step to a signer at the next stage.

An authentication method according to a fifth aspect of the present invention comprises:
A key generation step of generating a private key for each signer and a public key corresponding to the signature at each stage according to a predetermined authentication order; and, for the first signer, information including the corresponding private key; For the second and subsequent signers, a key management step including a distribution step of distributing information including a corresponding private key and a public key corresponding to a signature with the immediately preceding signer's private key to each signer; An encryption step of signing and encrypting the data to be authenticated using the secret key corresponding to the signer, and a transfer step of transferring the data encrypted in the encryption step to the next signer. A signature step for drafting by the first signer and a confirmation to confirm the transfer data transferred from the signer in the immediately preceding stage using the public key corresponding to the signature by the signer in the previous stage. Step, an encrypting step of signing and encrypting the transfer data using the secret key corresponding to the signer of the current stage, and transferring the data encrypted by the encrypting step to a signer of the next stage One or more approval signature steps for the second and subsequent signers having a transfer step.

An authentication method according to a sixth aspect of the present invention comprises:
A key management step of notifying the first signer of the secret key and notifying the second and subsequent signers of the corresponding private key and the public key of the immediately preceding signer; Determining the validity of the signature up to the immediately preceding signer using the received public key, and signing the received signature target data using the notified private key.

In the key management step, a public key for confirming data encrypted by the signature in each of the steps is provided by:
It may be made public only to the signer immediately after the signer of the relevant signature.

In the key management step, the secret key of each signer may be made public only to the signer concerned.

In the key management step, a public key for confirming only data encrypted by signatures of all stages before the corresponding stage may be generated.

An authentication method according to a seventh aspect of the present invention comprises:
An n determining step of determining any two different prime numbers p and q and obtaining a product nn = p * q of the prime numbers p and q; (p-1) and (q-1)
L = LCM ((p-1), (q-1)) An arbitrary integer e1 which is relatively prime to L and smaller than L is selected, and GCD (e1, L) = 1 (1 < e1 <L) e1 determining step as the first secret key, and e1 and L
(I-1) primes (i is a natural number of 2 or more) prime ej
Is determined arbitrarily, and an ej determining step of setting i j-th private keys ej (j is a natural number and 1 ≦ j ≦ i), and e1, e2, e3,. A di determining step for obtaining the i-th decryption key di from di 1 (mod L), and conditions e1, e2,... E (i-1) d (i-1) 1 (mod L) (1 <Dj <L), a dj determining step for finding a j-th decryption key dj (j = 1 to (i-1)), and confirmation of a secret key ej and a j-th signature used for the signature of the j-th signer Key dj used for
A key distribution step in which the j-th signer has information of ej, d (j-1) and dj, and n and a secret key e
1 to sign and encrypt the plaintext M, which is the original data,
A first signature step including a first encryption step for obtaining a first ciphertext C1 C1 = E1 (M) = M ^ e1 mod n, and a jth ciphertext Cj using n and a decryption key dj M = Dj (Cj) = Cj ^ dj mod n, a confirmation step of restoring plaintext M, and signing and encrypting the (j-1) th ciphertext C (j-1) using n and secret key ej One or more including a second encryption step to obtain the j-th ciphertext Cj Cj = Ej (C (j-1)) = C (j-1) ^ ej mod n (1 <j <i) Signing step for approval.

An authentication system and an authentication method according to the present invention generate a secret key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order. Information containing the relevant private key and the second
For the third and subsequent signers, the relevant private key and information including the public key corresponding to the signature by the immediately preceding signer's private key are distributed to each signer, and the data to be authenticated falls under the relevant signer. Signing and encrypting using the secret key, and transferring the encrypted data to the next signer to make a draft signature by the first signer;
Confirm the transfer data transferred from the signer of the previous stage using the public key corresponding to the signature by the signer of the previous stage,
Signing and encrypting the transfer data using the secret key corresponding to the signer of the relevant stage, and transferring the encrypted data to the signer of the next stage to perform at least one signing by the second and subsequent signers. Sign the approval of. Also, if necessary, at the time of encryption with the signature at each stage, the encrypted data is confirmed using the public key corresponding to the signature in the encryption. In this authentication system and authentication method, the public key corresponding to the signature at each stage is supplied only to the corresponding signer as a value reflecting the secret key at the previous stage, and the signature information is obtained no matter how many times the signature is performed. Is not increased, and the signatures of a plurality of signers can be determined to be valid.

Further, the recording medium of the present invention generates a first secret key for each signer and a first public key corresponding to a signature at each stage according to a predetermined authentication order.
For the second signer, information including the private key and public key of the first signer, and for the second and subsequent signers, the private key and public key of the signer and the public key of the immediately preceding signer. Key management means for distributing information including
Encryption means for signing and encrypting the data to be authenticated using the private key of the first signer, confirmation means for confirming the encrypted data using the public key of the first signer, and the cipher First signing means for the first signer having a transfer means for transferring the data encrypted by the encrypting means to the next signing means, and transferred from the signing means corresponding to the immediately preceding signer. Confirmation means for confirming the transfer data using the signer's public key in the immediately preceding step, encryption means for signing and encrypting the transfer data using the signer's private key in the corresponding step, and encryption means And a transfer means for transferring the data encrypted by the encrypting means to the signing means of the next stage. Second signing hand for the signer of the second , A program to function as is characterized in that it is recorded.

[0026]

Embodiments of the present invention will be described below with reference to the drawings. First, prior to the description of the embodiment, an authentication method according to the present invention will be described. Here, (a) a commonly used RSA algorithm,
(b) The authentication algorithm used in the present invention, (c) a signature and a verification method using the authentication algorithm, and (d) restrictions on the application of the algorithm will be sequentially described.

<(A) General RSA Algorithm> (1) An arbitrary two different prime numbers p and q and their product n are determined. n = p * q (2) Calculate the least common multiple L of (p-1) and (q-1), that is, L = LCM ((p-1), (q-1)), and calculate And an arbitrary integer e smaller than L is selected from GCD (e, L) = 1 (where 1 <e <L) and set as an encryption key.

(3) On the basis of e and L obtained in the above (2), a decryption key d is obtained from ed 1 (mod L). Note that x1 (mody) is x
Is 1 and the remainder is 1; ed 1 (mod
L) indicates that the remainder obtained by dividing the product of the secret key e and the decryption key d by L is 1. Therefore, for example, a1a2b (mod
c) indicates that the remainder becomes b by multiplying a1 by a2 and dividing by c. In addition, x = zmody indicates that the remainder obtained by dividing z by y is x. For example, a = b1 · b2 mod
c indicates that the remainder becomes a by multiplying b1 and b2 and dividing by c.

(4) The encryption key e is a secret key used for the signature of the signer, and the decryption key d is a public key used for confirming the signature. Using the encryption key e, which is a secret key, the plaintext M is signed and encrypted to obtain a ciphertext C. C = E (M) = M ^ e mod n Here, E (x) means encryption of x. Also, x ＾
y means to process x by y, and C = M ^ e mod n is C
Means that n is equal to the result of encrypting M with e. The original plaintext M can be obtained by decrypting the ciphertext C using the decryption key d that is a public key. M = D (C) = C ^ d mod n That is, E indicates signature encryption using the encryption key e,
Indicates decryption confirmation using the decryption key d. Here, D (x) means decoding of x. M = C = d mod n means that the remainder of dividing M by n is equal to the result of decoding C by d.

<(B) New Authentication Algorithm According to the Present Invention> (1) An arbitrary two different large prime numbers p and q and their product n are determined. n = p * q (2) Calculate the least common multiple L of (p-1) and (q-1), that is, L = LCM ((p-1), (q-1)), and calculate And an arbitrary integer e1 smaller than L is selected from GCD (e1, L) = 1 (where 1 <e1 <L) and set as an encryption key.

(3) (3-1) (i-1) prime numbers which are prime to the encryption keys e1 and L are arbitrarily determined, and a total of i prime numbers are determined by the first to i-th encryption keys. .. Ei are set as the activation keys e1, e2, e3,. (3-2) Based on the encryption keys e1 to ei and L, an i-th decryption key di is obtained from e1, e2, e3,... Ei, di1 (mod L). (3-3) First to (i-1) th decryption keys d1 satisfying the following conditions:
To d (i-1). e1 ・ d1 1 (mod L) e1 ・ e2 ・ d2 1 (mod L) e1 ・ e2 ・ e3 ・ d3 1 (mod L)… e1 ・ e2 ・ ・ ・ ・ ・ e (i-1) ・ d (i-1) 1 (mod L) (where 1 ≦ j ≦ i; 1 <dj <L)

(4) If 1 ≦ j ≦ i, the encryption key ej
Is the secret key used for the signature of the j-th signer, and the decryption key dj is the public key used for confirming the j-th signature. The j-th signer has a secret key, an encryption key ej,
It has information on decryption keys d (j-1) and dj which are public keys. The first signer signs and encrypts the plaintext M using the first encryption key e1 to obtain the first ciphertext C1. C1 = E1 (M) = M ^ e1 mod n The j-th (1 <j ≦ i) signer obtains the j-th encryption key e
Using j, the (j-1) -th ciphertext C (j-1) is signed and encrypted to obtain the j-th ciphertext Cj. Cj = Ej (C (j-1)) = C (j-1) ^ ej mod n (1 <j ≦ i) By decrypting the j-th ciphertext Cj using the j-th decryption key dj, , The original plaintext M can be obtained. M = Dj (Cj) = Cj ^ dj mod n That is, Ej indicates signature encryption using the encryption key ej,
Dj indicates decryption confirmation using the decryption key dj.

<(C) Signature and Confirmation> Signature and confirmation by each signer are performed as follows.

(C-1) Signature method: (1) Create document M. (2) The drafter, that is, the first signer U1, signs the document M using his / her own private key e1 to obtain a ciphertext C1. C1 = E1 (M) = M ^ e1 mod n

(3) The second signer U2 signs the ciphertext C1 using his / her own private key e2 to form a ciphertext C2. C2 = E2 (C1) = C1 ^ e2 mod n = M ^ e1 ・ e2 mod n (4) The third signer U3 signs the ciphertext C2 using his / her own secret key e3 and encrypts the ciphertext. C3. C3 = E3 (C2) = C2 ^ e3 mod n = M ^ e1 · e2 · e3 mod n (5) Similarly, the j-th signer Uj uses the private key ej of himself to encrypt the ciphertext C. (j-1) is signed and the ciphertext C
j.

(C-2) Signature Confirmation Method: (1) The ciphertext C1 signed by the first signer U1 is confirmed using the decryption key d1. That is, since D1 (C1) = C1dd1 mod n = M ^ e1 · d1 mod n = M, it is possible to return to the plaintext M and confirm.

(2) C2 signed by the second signer U2
Is confirmed using the decryption key d2. That is, since D2 (C2) = C2 ^ d2 mod n = M ^ e1 ・ e2 ・ d2 mod n = M, it is possible to return to the plaintext M for confirmation.

(3) Similarly, Cj signed by the j-th signer Uj is confirmed using the decryption key dj. That is, since Dj (Cj) = Cj ^ dj mod n = M ^ e1 · e2 ··· ej · dj mod n = M, it can be returned to the plaintext M and confirmed.

(C-3) Specific procedure: (1) The first signer U1 creates a plaintext M and signs it with the secret key e1 known only to the signer U1. The signed plaintext M becomes the ciphertext C1. (2) The first signer U1 confirms that the signature is correct with the decryption key d1 known only to the signer U1 and the next signer U2, and then transmits the ciphertext C1 to the next signer U2. send.

(3) The second signer U2 converts the received ciphertext C1 into the original document and the first document using the decryption key d1.
After confirming that the signature of the second signer U1 is correct, the ciphertext C1 is signed with the secret key e2 known only to the signer U2 to obtain a ciphertext C2. (4) The second signer U2 confirms that his / her signature is correct with the decryption key d2 known only to the signer U2 and the next signer U3, and then changes the ciphertext C2 to the next signer U2. Send to U3.

(5) Similarly, the j-th signer Uj
Is to use the decryption key d (j-1) to verify that the original document and the previous signature are correct, and then to encrypt the ciphertext C (j-1) received by only the signer Uj. Cryptographic text C with key ej
(j-1) is signed to be a ciphertext Cj. Further, the signer Uj confirms that his / her signature is correct with the decryption key dj known only to the signer Uj and the next signer U (j + 1), and then adds the ciphertext Cj to the next signature. Person U (j + 1). In this way, signature and confirmation are repeated as many times as necessary.

<(D) Restriction of Algorithm>-Generally,
The decryption key, which is a public key for confirmation, may be literally disclosed to the outside. However, in this algorithm, if all the decryption keys are made public due to the common value of modulo n, The secret key is guessed. Therefore, the rules for public and private keys are restricted as follows. (1) Naturally, all private keys can be known only by the person himself / herself. The signer cannot know the private key of another signer. (2) As for the decryption key, each signer can know only the decryption key of the immediately preceding signer and the decryption key of the principal.

Next, an authentication system according to an embodiment of the present invention based on the above-described algorithm will be described with reference to FIGS. FIG. 1 schematically shows a configuration of an authentication system according to an embodiment of the present invention.

The authentication system shown in FIG. 1 includes a key manager section 1, a first signer section 2, a second signer section 3, a third signer section 4, and a final (i) th signer section 5. ing. The key manager unit 1 is operated by a key manager that manages a secret key and a public key related to signature / encryption, and generates secret keys e1 to ei and decryption keys d1 to di for distribution to each signer. ,
Distribute to each signer. The key manager unit 1 includes a first secret key operation unit 11, a subsequent secret key operation unit 12, a decryption key operation unit 13, and a key distribution processing unit 14.

The first secret key operation unit 11 determines any two different large prime numbers p and q and their product n n = p * q by the operation of the key manager, and calculates (p−1) The least common multiple L of (q−1), that is, L = LCM ((p−1), (q−1)) is calculated, and any integer e1 that is relatively prime to L and smaller than L is calculated as GCD (e1, L) = 1 (where 1 <e1 <L), and set as the first secret key that is an encryption key.

The subsequent secret key operation unit 12 arbitrarily assigns (i-1) prime numbers prime to the encryption keys e1 and L, which are the first secret keys, by the operation of the key manager. Determined as
Are set as the second to i-th secret keys e2, e3,. Therefore, the first secret key calculation unit 11 and the subsequent secret key calculation unit 12 use a total of i encryption keys e.
1 to ei are determined as secret keys.

The decryption key operation unit 13 includes encryption keys e1 to ei.
, And L, the i-th decryption key di is obtained from e1, e2, e3,... Ei.di1 (mod L), and the first to (i-1) th keys satisfying the following conditions are further obtained. Of the decryption keys d1 to d (i-1). e1 ・ d1 1 (mod L) e1 ・ e2 ・ d2 1 (mod L) e1 ・ e2 ・ e3 ・ d3 1 (mod L)… e1 ・ e2 ・ ・ ・ ・ ・ e (i-1) ・ d (i-1) 1 (mod L) (where 1 ≦ j ≦ i; 1 <dj <L) When 1 ≦ j ≦ i, the encryption key ej is used as the secret key used for the signature of the j-th signer, and the decryption key is used. Let dj be the public key used to confirm the j-th signature.

The key distribution processing unit 14 provides the j-th signer with an encryption key ej as a secret key and a decryption key d as a public key.
(j-1) and dj are distributed.

The first signer unit 2 has a secret key (encryption key) e
1 and a first signer having the decryption key d1, operated by, for example, the drafter, encrypts, for example, the target document created by the drafter with a signature using the secret key e1, and transfers the document to the subsequent signer unit I do.

The first signer unit 2 has a signature processing unit 21, a signature confirmation unit 22, and a document transfer unit 23. Signature processing unit 2
1 is the first private key e by the operation of the first signer.
1, a plaintext M as a target document is signed and encrypted to obtain a first ciphertext C1 C1 = E1 (M) = M ^ e1 mod n. The signature confirmation unit 22 decrypts the first cipher text C1 using the first decryption key d1, and obtains the following equation from D1 (C1) = C1 ^ d1 mod n = M ^ e1 · d1 mod n = M. The first signer confirms that the plaintext M is The document transfer unit 23 transfers the first ciphertext C1 to the next second signer unit 3.

The second signer unit 3 includes a secret key e2, a decryption key d
Operated by a second signer with 1 and d2,
Using the decryption key d1, the first ciphertext C1 transferred from the first signer unit 2 is decrypted and confirmed, and the first ciphertext C1 is encrypted with a signature using the secret key e2. And forwards it to the subsequent signer section.

The second signer section 3 has a signature processing section 31, a signature confirmation section 32, and a document transfer section 33. Signature processing unit 3
1 is a second secret key e by the operation of the second signer.
2, the first ciphertext C1 transferred from the first signer unit 2 is signed and encrypted, and the second ciphertext C2 C2 = E2 (C1) = C1 ^ e2 mod n = M ^ e1・ E2 mod n is obtained. Prior to the signature of the signature processing unit 31, the signature confirmation unit 32 decrypts the first cipher text C1 using the first decryption key d1, and D1 (C1) = C1 ^ d1 mod n = M ^ e1 · The second signer confirms the original plaintext M from d1 mod n = M. Further, the signature confirmation unit 32 decrypts the second cipher text C2 generated by the signature processing of the signature processing unit 31 with the second decryption key d2, and D2 (C2) = C2 ^ d2 mod n = M ^ e1 The second signer confirms that the original plaintext M is obtained from e2 · d2 mod n = M. The document transfer unit 33 transfers the second ciphertext C2 to the next third signer unit 4.

The third signer unit 4 includes a secret key e3, a decryption key d
Operated by a third signer with 2 and d3,
Using the decryption key d2, the second ciphertext C2 transferred from the second signer unit 3 is decrypted and confirmed, and the second ciphertext C2 is encrypted with a signature using the secret key e3. And forwards it to the subsequent signer section.

The third signer unit 4 includes a signature processing unit 41, a signature confirmation unit 42, and a document transfer unit 43. Signature processing unit 4
1 is the third secret key e by the operation of the third signer.
3, the second ciphertext C2 transferred from the second signer unit 3 is signed and encrypted, and the third ciphertext C3 C3 = E3 (C2) = C2 ^ e3 mod n = M ^ e1・ E2 ・ e3 mod n is obtained. Prior to the signature of the signature processing unit 41, the signature confirmation unit 42 uses the second decryption key d2 to generate the second ciphertext C2.
, And the third signer confirms the original plaintext M according to D2 (C2) = C22d2 mod n = M ・ e12e22d2 mod n = M. Further, the signature confirmation unit 42 decrypts the third ciphertext C3 generated by the signature processing of the signature processing unit 41 with the third decryption key d3, and D3 (C3) = C3 ^ d3 mod n = M ^ e1 The third signer confirms that the original plaintext M is obtained from e2 · e3 · d3 mod n = M. The document transfer unit 43 transfers the third ciphertext C3 to the next signer unit.

The final signer section 5 includes a secret key ei and a decryption key d.
It is operated by the final signer having (i-1) and di, and decrypts the preceding cipher text C (i-1) transferred from the preceding signer part using the decryption key d (i-1). And encrypts the ciphertext C (i-1) using a signature using the secret key ei.

The final signer unit 5 has a signature processing unit 51, a signature confirmation unit 52, and a document transfer unit 53. Signature processing unit 5
1 signs and encrypts the (i-1) -th ciphertext C (i-1) transferred from the signer part at the preceding stage using the i-th private key ei by the operation of the last signer. , I-th ciphertext Ci Ci = Ei (C (i-1)) = C (i-1) ^ ei mod n = M ^ e1... Ei mod n. Prior to the signature of the signature processing unit 51, the signature confirmation unit 52 uses the (i-1) th decryption key d (i-1) to generate the (i-1) th ciphertext C (i-1). D (i-1) (C (i-1)) = C (i-1) ^ d (i-1) mod n = M ^ e1 ... e (i-1) di mod n = M, the final signer confirms the original plaintext M. Further, the signature confirmation unit 52 decrypts the i-th cipher text Ci generated by the signature processing of the signature processing unit 51 with the i-th decryption key di, and Di (Ci) = Ci ^ di mod n = M ^ e1 ····················································································································· · The document transfer unit 53 transfers the i-th ciphertext Ci to a predetermined transfer destination (for example, the next processing section or the approved document storage unit).
Transfer to

The key manager 1, the first signer 2, the second signer 3, the third signer 4, and the final signer 5 are connected to each other by a network or the like. Each is constituted by a computer system or the like.

Next, the operation of the authentication system configured as described above will be described with reference to the flowcharts shown in FIGS. The key manager performs key management by the key manager unit 1 in a procedure as shown in FIG. First, large prime numbers p and q are set (step S1), and a product n is calculated from n = p * q (step S2). Next, the prime number p
And q, the least common multiple L of (p-1) and (q-1), that is, L = LCM ((p-1), (q-1)) is calculated (step S3). Disjoint and L
An arbitrary smaller integer e1 is obtained, and GCD (e1, L) = 1 (where 1 <e1 <L) The first secret key e1, which is an encryption key, is selected (step S1).
4). The above is the processing in the first secret key operation unit 11.

Then, based on the operation of the key manager, the subsequent secret key operation unit 12 causes the encryption key e, which is the first secret key, to be transmitted.
(I-1) prime numbers that are prime to 1 and L are arbitrarily determined as encryption keys and set as second to i-th secret keys e2, e3,... Ei (step S5). In this way, a total of i encryption keys e1 to ei are determined as secret keys.

Next, in the decryption key operation unit 13, based on the above-mentioned encryption keys e1 to ei and L, the i-th decryption is performed from e1, e2, e3,. The key di is obtained (step S6), and e1 · d11 (mod L) e1 · e2 · d2 1 (mod L) e1 · e2 · e3 · d3 1 (mod L)… e1 · e2 ···· e (i -1) · d (i-1) 1 (mod L) (where 1 ≦ j ≦ i; 1 <dj <L), the first to (i-1) th decryption keys d1 to d satisfying the following conditions: (i-1)
Is obtained (step S7). Here, if 1 ≦ j ≦ i, the encryption key ej is the secret key used for the signature of the j-th signer, and the decryption key dj is the public key used for confirming the j-th signature. .

The key distribution processing unit 14 sends the first signer U
1, an encryption key e1 that is a secret key and a decryption key d1 that is a public key are distributed, and an encryption key ej that is a secret key and a decryption key d (j -1) and dj
Is distributed (step S8).

The first signer U1, who is the drafter, performs the drafting process in the first signer section 2 according to the procedure shown in FIG. The first signer U1 creates a document B, for example, a decision document, and obtains a hash M based on information of the created document B (step S11).

By the operation of the first signer U1, the signature processing unit 21 uses the first secret key e1 to sign and encrypt the plaintext M of the hash which is the target document.
Then, the ciphertext C1 C1 = E1 (M) = M ^ e1 mod n is obtained (step S12).

At this time, the first signer U1 uses the first decryption key d1 by the signature confirmation unit 22 to obtain D1 (C1) = C1Md1 mod n = M ^ e1 · d1 mod n = Based on M, the first ciphertext C1 is decrypted and confirmed to be the original plaintext M (step S13).

Then, the first ciphertext C1 is sent to the next second signer unit 3 together with the original document B by the document transfer unit 23.
(Step S14), and the process ends.

The j-th signer Uj (j = 2 to i) is
The signature processing is performed in the j-th signer sections 3 to 5 according to the procedure shown in FIG.

By the operation of the j-th signer Uj, the signature confirmation unit (32, etc.) uses the (j-1) -th decryption key d (j-1) to execute the immediately preceding (j-1) -th Decrypt the ciphertext C (j-1), and D (j-1) (C (j-1)) = C (j-1) ^ d (j-1) mod n = M ^ e (j-1 ) .D (j-1) mod n = M, the j-th signer confirms the original plaintext M (step S21).

Then, by the operation of the j-th signer Uj, the signature processing unit (31 etc.) causes the j-th private key ej
Using the (j-1) th signer part transmitted from the immediately preceding (j-1) th signer part,
The ciphertext C (j-1) of (1) is signed and encrypted, and the j-th ciphertext Cj Cj = Ej (C (j-1)) = C (j-1) ^ ej mod n = M ^ e1 ... Ej mod n is obtained (step S22). At this time, the j-th signer Uj uses the j-th decryption key dj to obtain Dj (Cj) = Cj ^ dj mod n = M ^ e1. Based on mod n = M, the j-th ciphertext Cj is decrypted and confirmed to be the original plaintext M (step S23).

Then, it is determined whether or not there remains an unsigned signer to be approved next (step S24). If the next signer exists, the j-th cipher text Cj is Along with the document B, the document transfer unit (33, etc.)
(j + 1) Transferred to the signer section (step S25), and the process ends.

If it is determined in step S24 that the next signer does not exist, a predetermined authentication such as storing the signed document in a specific storage location or transferring the signed document to a processing destination after approval is performed. An end process is performed (step S26), and the process ends.

Regarding the operation of the authentication system described above,
This will be described more specifically with reference to FIGS. In this case, the subject is the decision document B, the signer U1 is the drafter of the decision, the signer U2 is the manager, the signer U3 is the director, and the signer U4.
Is the general affairs officer and signatory U5 is the accounting officer. Therefore, the number i of signers is 5.

First, the key manager performs the following processing. (1) Set large prime numbers p and q and find their product n. n = p * q (2) Next, based on the prime numbers p and q, (p−1) and (q
-1) is calculated, and an arbitrary integer e1 which is relatively prime to this L and smaller than L is calculated, and the first secret key e1
Is selected. L = LCM ((p-1), (q-1)) GCD (e1, L) = 1 (However, 1 <e1 <L)

(3-1) The encryption key e1 which is the first secret key and L
Are arbitrarily determined as the second to fifth secret keys, and a total of five secret keys are obtained. e1, e2, e3, e4, e5 (3-2) A fifth decryption key d5 is obtained based on the encryption keys e1 to e5 and L. e1, e2, e3, e4, e5, d5 1 (mod L) (3-3) Further, first to fourth decryption keys d1 to d4 satisfying the following conditions are obtained. e1, d1 1 (mod L) e1, e2, d2 1 (mod L) e1, e2, e3, d3 1 (mod L) e1, e2, e3, e4, d4 1 (mod L) (where 1 ≦ j ≤ i; 1 <dj <L)

(4) Distribute n to each of the signers U1 to U5, and distribute an encryption key e1 as a secret key and a decryption key d1 as a public key to the first signer U1. An encryption key ej which is a secret key and decryption keys d (j-1) and dj which are public keys are distributed to the signer Uj.

Thus, the signer U1 receives the secret key e1, the decryption keys d1 and n, and the signer U2 receives the secret key e1.
2. Receiving decryption keys d1, d2 and n, and signer U3
Receives the secret key e3, the decryption keys d2, d3 and n,
Signer U4 receives private key e4, decryption keys d3, d4, and n, and signer U5 receives private key e5, decryption key d
4, d5 and n are received.

The first signer U1 who is the drafter performs the following processing. (1) A document B which is a decision document is created, and a hash M based on information of the created document B is obtained. (2) Using the first secret key e1, the plaintext M of the hash which is the target document is signed and encrypted to obtain the first ciphertext C1. C1 = E1 (M) = M ^ e1 mod n

(3) The first ciphertext C1 is decrypted using the first decryption key d1, and it is confirmed that the original plaintext M is obtained. D1 (C1) = C1 ^ d1 mod n = M ^ e1 ・ d1 mod n = M

(4) The original document B and the first ciphertext C1 are transferred to the manager who is the next signer U2.

The manager who is the second signer U2 performs the following processing. (1) The first ciphertext C1 immediately before using the first decryption key d1
And the original plaintext M is confirmed. D1 (C1) = C1 ^ d1 mod n = M ^ e1 ・ d1 mod n = M

(2) Using the second secret key e2, the first cipher text C1 is signed and encrypted to obtain a second cipher text C2. C2 = E2 (C1) = C1 ^ e2 mod n = M ^ e1 ・ e2 mod n (3) The second ciphertext C2 is decrypted using the second decryption key d2 to become the original plaintext M. Make sure that D2 (C2) = C2 ^ d2 mod n = M ^ e1 · e2 · d2 mod n = M (4) The original document B and the second ciphertext C2 are transferred to the director who is the next signer U3. .

The director who is the third signer U3 performs the following processing. (1) The second ciphertext C2 immediately before using the second decryption key d2
And the original plaintext M is confirmed. D2 (C2) = C2 ^ d2 mod n = M ^ e1 ・ e2 ・ d2 mod n = M

(2) Using the third secret key e3, the second cipher text C2 is signed and encrypted to obtain a third cipher text C3. C3 = E3 (C2) = C2 ^ e3 mod n = M ^ e1 ・ e2 ・ e3 mod n (3) The third plaintext C3 is decrypted using the third decryption key d3, and the original plaintext M is decrypted. Make sure that D3 (C3) = C3 ^ d3 mod n = M ^ e1 ・ e2 ・ e3 ・ d3 mod n = M (4) The next signer U4, the general affairs officer, sends the original document B
And the third ciphertext C3.

The general affairs clerk who is the fourth signer U4 performs the following processing. (1) The third ciphertext C3 immediately before using the third decryption key d3
And the original plaintext M is confirmed. D3 (C3) = C3 ^ d3 mod n = M ^ e1 · e2 · e3 · d3 mod n = M (2) Using the fourth secret key e4, sign and encrypt the third ciphertext C3, The fourth ciphertext 4 is obtained. C4 = E4 (C3) = C3 ^ e4 mod n = M ^ e1 ・ e2 ・ e3 ・ e4 mod n

(3) The fourth ciphertext C4 is decrypted using the fourth decryption key d4, and it is confirmed that the fourth plaintext C4 becomes the original plaintext M. D4 (C4) = C4 ^ d4 mod n = M ^ e1 ・ e2 ・ e3 ・ e4 ・ d4 mod n = M (4) The next signer U5, the accounting officer, sends the original document B
And the fourth ciphertext C4.

The accounting person who is the fifth signer U5 performs the following processing. (1) Using the fourth decryption key d4, the immediately preceding fourth ciphertext C4
And the original plaintext M is confirmed. D4 (C4) = C4 ^ d4 mod n = M ^ e1 ・ e2 ・ e3 ・ e4 ・ d4 mod n = M

(2) Using the fifth secret key e5, the fourth ciphertext C4 is signed and encrypted to obtain the fifth ciphertext 5. C5 = E5 (C4) = C4 ^ e5 mod n = M ^ e1 ・ e2 ・ e3 ・ e4 ・ e5 mod n (3) The fifth ciphertext C5 is decrypted using the fifth decryption key d5, Is confirmed to be plaintext M. D5 (C5) = C5 ^ d5 mod n = M ^ e1 ・ e2 ・ e3 ・ e4 ・ e5 ・ d5 mod n = M

(4) Check whether there is a next signer, that is, whether or not all the authentications have been completed. If there is no next signer, the signed document, that is, the original document B and the fifth Authentication termination processing such as transfer or storage is performed on the ciphertext C5.

According to the above-described authentication system, FIG.
As shown in, by creating an encryption key for signing by the number of signers and a decryption key for confirmation by the number of signers,
The signature information, that is, the ciphertext is rewritten for each signature. That is, from the encrypted text 1 obtained by encrypting the plain text with the signature 1 using the encryption key 1, the plain text can be obtained by the confirmation 1 using the decryption key 1. From ciphertext 2 obtained by encrypting ciphertext 1 with signature 2 using encryption key 2, plaintext can be obtained by confirmation 2 using decryption key 2. From ciphertext 3 obtained by encrypting ciphertext 2 with signature 3 using encryption key 3, plaintext can be obtained by confirmation 3 with decryption key 3. In this manner, by sequentially and cumulatively sign-encrypting the ciphertext, it is possible to transfer the encrypted information reflecting the previous signature information without cumulatively adding the certification information itself, and The plaintext can be obtained from any stage by performing confirmation using a decryption key suitable for that stage.

Accordingly, as shown in FIG. 10, the new signature rewrites the signature information reflecting the previous signature information. That is, each time a signature / approval is made,
Even if the approval operation is repeated without accumulating the approval information, a plurality of approvals can be performed without changing the file size. In this way, it is possible to determine that the signatures of a plurality of signers are valid without increasing the signature information, no matter how many times the signature is performed.

Note that the authentication system of the present invention can be realized by using a normal computer system without configuring as a dedicated system. For example, a medium (floppy disk, CD-RO) storing a program for executing the above-described operation in a computer system.
M) can install an authentication system that executes the above-described processing. By installation, the program
The authentication system is stored in a medium such as a hard disk in the computer system, and is provided for execution.

The medium for supplying the program to the computer is not limited to a storage medium in a narrow sense, but may be a communication line,
Like a communication network and a communication system, it may be a storage medium in a broad sense including a communication medium that temporarily and fluidly stores information such as a program.

For example, the program may be registered in an FTP (File Transfer Protocol) server provided on a communication network such as the Internet, and distributed to an FTP client via the network. An electronic bulletin board (BBS: Bulletin) of the communication network may be used. The program may be registered in a board system or the like and distributed via a network. Then start this program and run the OS
The above processing can be achieved by executing under the control of the (Operating System). Furthermore, the above-described processing can also be achieved by starting and executing the program while transferring the program via the communication network.

[0093]

As described above, according to the present invention, the public key corresponding to the signature at each stage is supplied only to the corresponding signer as a value reflecting the secret key at the previous stage, and the signature is obtained. No matter how many times is performed, it is possible to provide an authentication system and an authentication method capable of determining that signatures of a plurality of signers are valid without increasing the signature information.

[Brief description of the drawings]

FIG. 1 is a block diagram schematically showing a configuration of an authentication system according to an embodiment of the present invention.

FIG. 2 is a flowchart illustrating an operation of a key management process in the authentication system of FIG. 1;

FIG. 3 is a flowchart illustrating an operation of a drafting process in the authentication system of FIG. 1;

FIG. 4 is a flowchart illustrating an operation of a signature process in the authentication system of FIG. 1;

FIG. 5 is a diagram for explaining a more specific operation in the authentication system of FIG. 1;

FIG. 6 is a diagram for explaining a more specific operation in the authentication system of FIG. 1;

FIG. 7 is a diagram for explaining a more specific operation in the authentication system of FIG. 1;

FIG. 8 is a diagram for explaining a more specific operation in the authentication system of FIG. 1;

FIG. 9 is a schematic diagram for explaining the concept of authentication in the authentication system of FIG. 1;

FIG. 10 is a schematic diagram for explaining the concept of file transfer in the authentication system of FIG. 1;

FIG. 11 is a schematic diagram for explaining the concept of a signature in a conventional system.

FIG. 12 is a schematic diagram for explaining the concept of a signature by a conventional public key cryptosystem.

FIG. 13 is a schematic diagram for explaining the concept of file transfer in a conventional system.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Key manager part 2-5 Signer part 11 1st secret key calculation part 12 Subsequent secret key calculation part 13 Decryption key calculation part 14 Key distribution processing part 21, 31, 41, 51 Signature processing part 22, 32, 42, 52 Signature Confirmation Unit 23, 33, 43, 53 Document Transfer Unit

Claims (12)

[Claims] 1. A private key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order are generated, and for a first signer, a private key of the first signer is generated. Key management means for distributing the information including the public key to the second and subsequent signers, to the respective signing means, the information including the private key and public key of the signer and the public key of the immediately preceding signer; Encryption means for signing and encrypting the data to be authenticated using the private key of the first signer, confirmation means for confirming the encrypted data using the public key of the first signer, and the cipher First signing means for a first signer having transfer means for transferring data encrypted by the encrypting means to the next-stage signing means, and transferring from the signing means corresponding to the immediately preceding signer. The transferred data using the public key of the signer in the previous stage Verification means, encryption means for signing and encrypting the transfer data using the private key of the signer at this stage, and encrypting the data encrypted by the encryption means with the public key of the signer at this stage. And a second signing means for second and subsequent signers having a transferring means for transferring the data encrypted by the encrypting means to the next signing means. An authentication system, characterized in that: 2. A private key and a public key are generated for each signer, and the corresponding private key is used for the first signer, and the corresponding private key and the last private key are used for the second and subsequent signers. Key management means for distributing the signer's public key to each signing means, signature means for signing the data to be authenticated using the signer's private key, and data signed by the signing means in the next step. First signing means for a first signer having transfer means for transferring the data to the signing means, and using the public key of the signer at the immediately preceding stage for the transfer data transferred from the signing device at the immediately preceding stage. A signature unit for signing the transfer data transferred from the signature unit at the immediately preceding stage using the private key of the signer at the stage, and a signature at the next stage for the data signed by the signature unit. Turn to means Authentication system characterized by comprising a second signature means for second and subsequent signer having a transfer means for the. 3. A means for generating a private key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order, and a first signer for the first signer. Means for notifying the private key of the second and subsequent signers, and means for notifying the private key of the signer and the public key of the previous signer for the second and subsequent signers. An authentication system comprising: verifying a signature by using a secret key; and performing a signature by using the notified private key. 4. The key management means is means for disclosing a public key for confirming data encrypted by the signature at each stage only to a signer immediately after the signer of the corresponding signature. The authentication system according to claim 1, 2 or 3, wherein: 5. The key management means according to claim 1, wherein said key management means is means for generating a public key for confirming data encrypted by signatures of all stages before said stage. The authentication system according to claim 3 or 4. 6. A key generation step of generating a secret key for each signer and a public key corresponding to each stage of a signature in accordance with a predetermined authentication order. For the second and subsequent signers, information including the public key corresponding to the signature by the private key, and for the second and subsequent signers, information including the public key corresponding to the secret key and the signature by the private key of the immediately preceding signer. A key management step including a distribution step of distributing the data to each signer, an encryption step of signing and encrypting the data to be authenticated using the secret key corresponding to the signer, and a public key corresponding to the signature. A signature step for a first signer, comprising: a confirmation step of confirming the encrypted data by using the above; and a transfer step of transferring the data encrypted in the encryption step to a next signer. A first confirmation step of confirming the transfer data transferred from the signer of the immediately preceding stage using a public key corresponding to the signature by the signer of the previous stage, the transfer data corresponding to the signer of the corresponding stage An encryption step of signing and encrypting using the secret key, and confirming the encrypted data using a public key corresponding to the signature in the encryption step.
And a signing step by a second or subsequent signer having a transfer step of transferring data encrypted by the encryption step to a signer at the next stage. 7. A key generating step for generating a secret key for each signer and a public key corresponding to each stage of a signature in accordance with a predetermined authentication order. A distribution step of distributing, to each of the signers, the information including the information, and, for the second and subsequent signers, the corresponding private key and information including the public key corresponding to the signature with the immediately preceding signer's private key. A key management step; an encryption step of signing and encrypting the data to be authenticated using the secret key corresponding to the signer; and transmitting the data encrypted in the encryption step to a signer in the next step. A signature step for drafting by a first signer having a transfer step of transferring, and using a public key corresponding to the signature by the signer of the previous stage, using the transfer data transferred from the signer of the immediately preceding stage. A confirming step for confirming, an encrypting step of signing and encrypting the transfer data using the secret key corresponding to the signer of the current stage, and a signer of the next stage for encrypting the data encrypted by the encrypting step. At least one signing step for approval for the second and subsequent signers having a transfer step of transferring to an authentication method. 8. A key management step for notifying the first signer of the secret key and notifying the second and subsequent signers of the corresponding private key and the public key of the immediately preceding signer; Receiving the public key, determining the validity of the signature up to the immediately preceding signer using the notified public key, and signing the received signature target data using the notified private key. Authentication method. 9. The method according to claim 9, wherein the key management step includes: a public key for confirming data encrypted by the signature of each of the steps;
9. The authentication method according to claim 6, wherein the information is disclosed only to a signer immediately after the signer of the signature. 10. The method according to claim 6, wherein the key management step generates a public key for confirming data encrypted by signatures of all stages before the corresponding stage. The authentication method according to claim 1. 11. An n determining step of determining any two different prime numbers p and q and obtaining a product nn = p * q of the prime numbers p and q; (p-1) and (q-1) ) Is calculated. L = LCM ((p−1), (q−1)) An arbitrary integer e1 which is relatively prime to L and smaller than L is selected, and GCD (e1, L) = 1 (1 <E1 <L) An e1 determining step as a first secret key, and (i-1) primes (i is a natural number of 2 or more) that are prime to e1 and L
Is determined arbitrarily, and i j-th secret keys ej
(J is a natural number and 1 ≦ j ≦ i), and an ith decryption key from e1, e2, e3,... Ei.di 1 (mod L) based on ej and L di determining step for obtaining di, and a j-th decryption key dj (1 <dj <L) that satisfies the condition e1 · e2 ···· e (i-1) · d (i-1) 1 (mod L) (1 <dj <L) j = 1 to (i-1)), a secret key ej used for the signature of the j-th signer, and a decryption key dj used for confirming the j-th signature
A key distribution step of distributing the j-th signer so that the j-th signer has the information of ej, d (j-1) and dj, and signing and encrypting the plaintext M as the original data using n and the secret key e1. And a signature step for drafting including a first encryption step to obtain a first ciphertext C1 C1 = E1 (M) = M ^ e1 mod n, and a j-th ciphertext using n and the decryption key dj A verification step of restoring plaintext M from Cj by M = Dj (Cj) = Cj ^ dj mod n, and signing the (j-1) th ciphertext C (j-1) using n and secret key ej Including a second encryption step to obtain the j-th ciphertext Cj Cj = Ej (C (j-1)) = C (j-1) ^ ej mod n (1 <j <i) An authentication method, comprising the above-mentioned signature step for approval. 12. The computer system generates a private key for each signer and a public key corresponding to a signature at each stage according to a predetermined authentication order. Information, including the private and public keys of
For the second and subsequent signers, key management means for distributing information including the signer's private key and public key and the immediately preceding signer's public key to each signing means. Encrypting means for signing and encrypting using the private key of the signer, confirming means for confirming the encrypted data using the public key of the first signer, and data encrypted by the encrypting means First signing means for a first signer having transfer means for transferring the data to the next-stage signing means, and transferring the transfer data transferred from the signing means corresponding to the immediately preceding signer to the immediately preceding signer. Confirmation means for confirming using the public key of the signer, encryption means for signing and encrypting the transfer data using the private key of the signer at this stage, and data encrypted by the encryption means. Confirm using the public key of the signer of the stage. And a second signing means for second and subsequent signers having a transferring means for transferring the data encrypted by the encrypting means to the next signing means. A computer-readable recording medium that has been recorded.