JP2002132144A - Authentication method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable an additional message to be sent in a cyclic signature and to specify a verifier. A public key is distributed by a public means 101. First
The signer (user) 102 generates the first signature information and the encrypted message, and transmits them to the second signer (YAS) 103. Second
The signer (YAS) 103 confirms the legitimacy of the user by decrypting the received encrypted message. Furthermore, YGS
Is created as a signature verifier, and a second signature information is created and sent to the user.
The user creates third signature information from the received second signature information and sends it to the signature verifier (YGS) 104. The YGS receives the third signature information and verifies the signature.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

TECHNICAL FIELD The present invention relates to an authentication system,
In particular, the present invention relates to an authentication system for cyclically signing a message and restoring the message in a cryptographic communication system.

[0002]

In the same way as signing a paper document to reveal the responsibility of the creator of the document, digital data is digitally signed to identify the creator of the digital data. In addition, there is a cyclic signature that performs a plurality of signatures on digital data such that a plurality of approver's settlement stamps are stamped on a request for approval in a paper document. Among the digital signatures, the message restoration type signature is a signature whose original message is restored when the signature is verified.

Referring to FIGS. 3 and 4, Ny of the first conventional example is shown.
The berg-Rueppel message restoration type signature will be described. FIG.
FIG. 1 is a functional block diagram of a first conventional Nyberg-Rueppel message restoration type signature scheme. In FIG. 3, a publishing unit 301 is a unit that distributes a public key necessary for creating and confirming a signature. The signer 302 is a means for sending a message with a signature attached. The recipient 303 is a means for receiving the signature and confirming the creator of the message. The message generation unit 304 is a unit that generates a message to be transmitted. The signature information creation unit 305 is a unit that creates signature information for a message. Transmission means 306 is means for transmitting the signature information to the recipient. The receiving unit 307 is a unit that receives the signature information from the signer. The message calculation means 308 is means for calculating and confirming a message from the signature information.

FIG. 4 is a flowchart showing an operation procedure of the first conventional Nyberg-Rueppel message restoration type signature scheme. In FIG. 4, step 1 is a procedure in which the publishing unit publishes the public key. Step 2 is a procedure in which the signer creates a signature and sends it to the recipient. Step 3 is a procedure in which the recipient verifies the signature.

[0005] The first conventional example of Ny constructed as described above
Explain the operation of the berg-Rueppel message restoration type signature scheme
You. In step 1, the public means sets the public key (p, q,
g, y). Let p be a sufficiently large prime number. q
Let (p-1) be a large prime factor. g is an integer ring Z_p ^*In
Of the order q. Let the signer's private key be x (integer ring Z_p
^*And the public key is y. The private key x is the signer's
And the public keys y, p, q, and g are
Published by Dan. That is, Z_p ^*= {1,2, ..., p-1} g^q modp = 1 g^{q '} modp ≠ 1 (0 <q ′ <q) y = g^x modp.

In step 2, the signer determines a random number k for the message m, creates a signature (r, s), and sends it to the recipient. That is, r = m × g ^k mod x s = k + m × g ^k × x mod q is sent.

In step 3, the recipient who has received the digital signature (r, s) for the message m calculates the message m using the signer's public key y. That is, r × g ^−s × y ^r modp = (m × g ^k ) × g ^ (− k−r × x) × g ^ (xx × r) modp = m × g ^ (k−kr × Only when the signer is correct, as in (x + xxr) modp = m, the message m can be restored.

Referring to FIGS. 5 and 6, a second conventional example of a Nyberg-Rueppel message restoration type signature having two messages will be described. This signature is a message M having the same resilience as the Nyberg-Rueppel message recovery type signature.
And the message m used for the exponent part at the time of verification, similar to the ElGamal signature. This signature is described in Document 1 [Shunsuke Araki, Satoshi Uehara, and Yuki Imamura, “Application of Nyberg-Rueppel Message Restoring Signature with Restricted Confirmers”, The 2000 Symposium on Cryptograph an
d Information Security SCIS-2000, C26, Okinawa, Jap
an, Jan. 26-28, 2000].

FIG. 5 is a functional block diagram of a second conventional Nyberg-Rueppel message restoration type signature system. FIG.
, Public means 501 is a means for distributing a public key necessary for creating and confirming a signature. The signer 502 is a means for sending a message with a signature. The recipient 503,
This is a means for receiving the signature and confirming the creator of the message. The first message generation means 504 is a means for generating a first message to be transmitted. Second message generating means
A unit 505 generates a second message to be transmitted. The signature information creation unit 506 is a unit that creates signature information for a message. Transmission means 507 is means for transmitting the signature information to the recipient. The receiving means 508 is means for receiving the signature information from the signer. The message calculation means 509 is a means for calculating and confirming a message from signature information.

FIG. 6 is a flowchart showing the operation of the second conventional Nyberg-Rueppel message restoration type signature scheme. In FIG. 6, step 1 is a procedure in which the publishing unit publishes the public key. Step 2 is a procedure in which the signer creates a signature and sends it to the recipient. Step 3 is a procedure in which the recipient verifies the signature.

The Ny of the second conventional example configured as described above
The operation of the berg-Rueppel message restoration type signature scheme will be described. In step 1, the publishing means sets the public key (p, q,
g, y). Let p be a sufficiently large prime number. Let q be a large prime factor of (p-1). g of the original of order q in the ring of integers Z _p ^*. Let the private key of the signer be x (integer ring Z _p
^* ) And the public key is y. The private key x is securely managed under the signer, and the public keys y, p, q, and g are made public. That is, ^{_{Z p * = {1,2, ···}} , p-1} g q modp = 1 g q 'modp ≠ 1 (0 <q'<q) y = g x modp.

In step 2, the signer selects a random number k, and uses the random number k, the messages M and m, and the secret key x,
Generate a digital signature (m, r, s) and send it to the recipient. That is, r = M × g ^ (k × m) modp s = k + r × x modq is sent.

In step 3, the digital signature (m,
The receiver receiving (r, s) calculates the message M using the signer's public key y. That is, r × m × g ^ (− s × m) × y ^ (r × m) modp = (M × g ^ (k × m)) × g ^ (− k × m−r × x × m) × g ^ (x × r × m) modp = M × g ^ (k × m−k × m−r × x × m + x × r × m) modp = M, and only when the signer is correct, the message M Can be restored.

Referring to FIGS. 7 and 8, a third conventional example of El
Explain the Gamal cooperation signature (circular signature). This signature is
This is a method of creating one signature by two persons (a plurality of persons). Reference 2 [Shingo Miyazaki, Seki Ishimoto, Jun Shinbo, Koichi Sakurai, "ElG
Configuration of amal-type cooperative signature and its application to key management and key escrow system, IPSJ Transactions pp.2074-2082, Vol.38, no.10,
Oct. 1997].

FIG. 7 is a functional block diagram of a third conventional example of an ElGamal cooperative signature system. In FIG.
Reference numeral 701 denotes a means for distributing a public key required for creating and confirming a signature. The first signer 702 is a means for adding a signature to the first message and transmitting it. The second signer 703 is a means for adding a signature to the second message and transmitting it. The signature verifier 704 is a means for receiving the signature and confirming the creator of the message. The first message generation means 705 is a means for generating a first message to be transmitted. The encrypted message creating means 706 is means for encrypting the first message. The first signature information creation unit 707 is a unit that creates signature information for the first message. Transmission means 708
Is means for transmitting the first signature information to the second signer.
The receiving unit 709 is a unit that receives the first signature information from the first signer. The first message calculation means 710 is a means for calculating and confirming the first message from the first signature information. The second signature information creation unit 711 is a unit that creates signature information for the second message. Transmission means 712
This is means for transmitting the second signature information to the first signer. The receiving means 713 is means for receiving the second signature information from the second signer. The second message calculation means 714 is means for calculating and confirming the second message from the second signature information.
The third signature information creation unit 715 is a unit that creates signature information for a message. Transmission means 716 is means for transmitting the third signature information to the signature verifier. Receiving means 717
Is means for receiving the third signature information from the first signer. The signature verification unit 718 is a unit that calculates and confirms a message from the third signature information.

FIG. 8 is a flowchart showing the operation of the third conventional ElGamal cooperative signature scheme. In FIG. 8, step 1 is a procedure in which the publishing unit publishes the public key. Step 2 is a procedure in which the first signer creates a signature and sends it to the second signer. Step 3 is a procedure in which the second signer creates a signature and sends it to the first signer. Step 4 is the first
This is a procedure in which the signer creates a signature and sends it to the verifier. Step 5 is a procedure in which the verifier verifies the signature.

[0017] The third conventional example of the above-described configuration of El
The operation of the Gamal cooperative signature scheme will be described. In step 1, the publishing means publishes the public key (p, g, y). p
Is a sufficiently large prime number. the g is an integer ring Z _p ^* of primitive roots. The first signer has a secret key x ₁ (an element of the integer ring Z _p ^* ),
The second signer has a secret key x ₂ (an element of the integer ring Z _p ^* ). The secret key x ₁ is securely managed under the first signer, and the secret key x ₂
Is securely managed under the second signer. The public key common to both is y. The public keys y, p and g are made public. ^{_{That, Z p * = {1,2,}} ···, p-1} g p-1 modp = 1 g q modp ≠ 1 (0 <q <p-1) y = g ^ (x 1 + x 2) modp.

In this conventional example, there are three possible combinations of a signature key and a verification key, depending on how to select a key to be signed.
In other words, the confirmation of the signature by the only private key x _1, there is a need for secret key x ₂ and the public key (p, g, y). The confirmation of the signature by the only private key x _2, secret key x ₁ and the public key (p, g,
y) is required. The public key (p, g, y) is required for confirming the cooperation signature of the private keys x ₁ and x ₂ . These are used properly in each situation.

In step 2, the first signer creates and sends a signature. The random numbers k ₁ and K are prepared, and r ₁ = g ^ (− k ₁ ) modp is created, and the random number K and a key (y × g ^) corresponding to the secret key x ₂ are obtained.
Using (−x ₁ )), the message (C ₁ , C ₂ ) obtained by encrypting the message M is sent to S ₂ together with r ₁ . That is, C ₁ = g ^K modp C ₂ = M × (y × g ^ (− x ₁ )) ^K modp is sent.

[0020] In Step 3, the second signer from the received message (C _1, C _2), decrypts the message M using the secret key x _2. That is, M = C ₂ / C ₁ ^ x ₂ modp is obtained. From the extracted message M, r ₁ and random number k ₂ , a signature (r ₁₂ , s ₂ ) is created and sent to the first signer. _{That, r 12 = M × r 1} × g ^ (- k 2) modp s 2 = k 2 -x 2 × r 12 mod (p-1) a letter.

In step 4, the first signer obtains a message M from the received (r ₁₂ , s ₂ ). That is, s ₁ = k ₁ −x ₁ × r ₁₂ mod (p−1) s ₁₂ = s ₁ + s ₂ mod (p−1) is created, and g ^ s ₁₂ × y ^ r ₁₂ × r ₁₂ modp = g ^ (k ₁ −x ₁ × r ₁₂ + k ₂ −x ₂ × r ₁₂ ) × g ^ {(x ₁ + x ₂ ) × r ₁₂ } × (M × g ^ (− k ₁ ) × g ^ (− k ₂ )) Find M by setting modp = M and confirm the signature. Further, (r ₁₂ ,
s ₁₂ ) to the verifier requesting verification.

In step 5, anyone can verify the signature by using (r ₁₂ , s ₁₂ ) and the public key (p, g, y).

Since anyone can ultimately verify these signatures, it is inconvenient if only a specific person wants to verify them. In other words, if the key escrow system authenticates that it is a legitimate investigator with the permission of a court or the like, anyone can authenticate that it is a legitimate investigator and restore the message. Information about who is being investigated is available to anyone and there is a risk of privacy infringement. In the case of a key escrow system, only the key management server or the investigating agency needs to be able to verify.

In order that only a specific person can verify, a digital signature in which discriminating information is added and a confirming person is limited will be briefly described. Let m be a message describing the signature type. Let M be a message signed with the signature type indicated by m. The public key of the sender is y _A (= g ^ x _A ), the public key of the receiver is y _B (= g ^ x _B ), and the public key of the third party to be confirmed is y _C (= g ^ x _C ). Sender, decide to sign any type, and a Select y _A or y _B or y _C. Using the random number k, the message M
From and transmits to calculate the ^{r = M × a k s =} k + r × m × x A. The calculation is performed according to the finite field used. The verifier uses the received r, s, its own secret key x, the sender's public key y _A, and the message m to obtain M = r × a− ^s × y _A ^ (r × m × x ) To verify the message M. In other words, use the public key y _A of the sender to a when the undeniable signature, when the prover limit signature use the y _B to a, when the confirmation's specified signature using the y _C to a. x is made to x _A when the undeniable signature, becomes x _B when the prover restriction signature, become x _C when the confirmation's specified signature.

A fourth conventional Kerberos system will be described with reference to FIGS. 9 and 10. FIG. Kerberos is an authentication method that proves the identity of a user to a service. FIG. 9 is a functional block diagram of a conventional Kerberos (Kerberos) system. In FIG. 9, a user 91 is a user of the Kerberos system. AS92 is
Authentication server. TGS93 is a ticket issuing server. The service institution 94 is a system that provides a user with a predetermined service.

FIG. 10 is a flowchart showing the operation of the conventional Kerberos (Kerberos) system. In FIG. 10, TGS
The ticket request 1001 is sent from the user to the authentication server AS92.
This is a procedure for requesting the issuance of a TGS ticket. TGS ticket delivery 1002 from the authentication server AS92 to the user
This is a procedure for delivering TGS tickets. The service ticket request 1003 is transmitted from the user to the ticket issuing server TGS9.
This is the procedure for requesting the issuance of a service ticket in 3.
Service ticket delivery 1004 is ticket issuing server TG
This is the procedure for delivering the service ticket from S93 to the user. The service ticket transmission 1005 is a procedure for transmitting a service ticket from a user to a service organization. The service provision 1006 is a procedure in which a service organization provides a service to a user.

The operation of the third conventional Kerberos system configured as described above will be described. Authentication is performed using encrypted information called a ticket.
In the TGS ticket request 1001 shown in FIG. 10, a user requests the authentication server AS92 to issue a TGS ticket. T
In the GS ticket delivery 1002, the TGS ticket is delivered from the authentication server AS92 to the user. In the service ticket request 1003, the user requests the ticket issuing server TGS93 to issue a service ticket. In the service ticket delivery 1004, the service ticket is delivered from the ticket issuing server TGS93 to the user. In the service ticket transmission 1005, the service ticket is transmitted from the user to the service organization. In service provision 1006, a service organization provides a service to a user.

The Kerberos system has a drawback in that the authentication between a user and various service organizations is emphasized, so that when used for communication between users, a ciphertext creator cannot sign. In other words, there is a drawback that authentication against the user can be denied. In addition, since the secret key between the user and the authentication server AS is stored for a long period of time, it has a disadvantage that it is easily exposed to malicious attacks.

Referring to FIGS. 11 and 12, a fifth prior art Yaksha system will be described. Yaksha
The system is an authentication system that allows a ciphertext creator to sign using a public key. FIG. 11 shows the system of Yaksha. In FIG. 11, the user
1101 is a user of the Yaksha system. YA
S1102 is a Yaksha authentication server. YGS11
03 is a Yaksha ticket issuing server.
The service organization 1104 is a system that provides a predetermined service to a user.

FIG. 12 is a flowchart showing the operation of the conventional Yaksha system. In FIG. 12, an initial ticket (tgt = ticket granting ticket) request 1201 is a procedure for requesting the YAS to issue an initial ticket from the user. The initial ticket delivery 1202 is a procedure for delivering an initial ticket from YAS to a user. The service ticket (s-ticket) request 1203 is a procedure in which the user requests the YGS to issue a service ticket. The service ticket (s-ticket) delivery 1204 is a procedure for delivering a service ticket from the YGS to the user. The service ticket transmission 1205 is a procedure for transmitting a service ticket from a user to a service organization. The service provision 1206 is a procedure in which a service organization provides a service to a user.

The operation of the fourth prior art Yaksha system configured as described above will be described. In the initial ticket request protocol (as_req) 1201 shown in FIG.
Send D, tgs, time-exp, [[TEMP-CERT] ^ Dc, n] ^ Dc. C1ID
Is the ID of the user. tgs is the ID of the YGS that issues the service ticket. time-exp is the expiration date of the ticket. TEMP-CERT is a temporary certificate, C1,
Includes E_c-temp, N_c-temp, and expiry-time. E_c-temp, N_c-
temp is the temporary user's public key pair, signed with the user's long-term private key Dc. In order to avoid a TEMP-CERT dictionary attack, a random number n is concatenated and further signed with a cyclic signature (JS1 processing) using the user's private key. A dictionary attack is basically a method of estimating a password by applying a password or the like from one end to words in the dictionary. Here, [TEMP-CERT] ^ guess = [TEMP-CERT] ^ Dc And trying to guess the value of Dc.

By the way, in Yaksha, RSA is added to [TEMP-CERT].
It cyclically signs and mutually authenticates the user and the YAS server. Ask the YAS server to authenticate that the user is a legitimate user, and verify the verification result (evidence) with YGS
The purpose is to show to the server. Also, R for the tgt ticket
The SA certificate is used to mutually authenticate the YAS server and the YGS server. The YAS server has a fake
It indicates that this is a valid ticket issued by a legitimate server that is not a YAS server, and also tells the user that they have mutually authenticated.

Upon receiving a key request for key sharing from the user, YAS encrypts (signs) and distributes the common key K used between the user and the service organization. YAS decrypts the TEMP-CERT with the user's public key Ec, confirms the contents,
Thereafter, a cyclic signature (JS2 process) is performed using the YAS secret key Dcy. [[T
EMP-CERT] ^ Dc] ^ Dcy is obtained. This is returned to the user in the initial ticket delivery (as_rep) 1202.

The user sends this to the YGS in a service ticket request (tgs_req) 1203. YGS received
[[TEMP-CERT] ^ Dc] ^ Dcy is cyclically signed (JS3 processing) and TEM
Retrieve the P-CERT and verify that the message has already been authenticated by the user and YAS.

The procedure for an investigating agency to recover a key for wiretapping during law enforcement is exactly the same. That is, the server YAS decrypts the TEMP-CERT with the public key Ei of the investigating institution I, confirms the contents R (such as a warrant of a court), and then performs a cyclic signature (JS2 processing) with the secret key Dcy of the server YAS. [[TEM
Since P-CERT, R] ^ Dc] ^ Dcy is obtained, this is returned to the investigating agency I by protocol 2 (also called as_rep).

The investigating agency I receives the [[TEMP-CERT, R]
^ Dc] ^ Dcy is cyclically signed (JS3 processing) and TEMP-CERT, R is extracted. This is sent to the YGS server using protocol 3 (also called tgs_req). YGS confirms from the authenticators r ₁₂ and s ₁₂ that the message has already been authenticated by Investigator I and YAS. In other words, in Kerberos and Yaksha, the basic protocol does not change even in the investigation mode during law enforcement. At the time of law enforcement, the investigating agency presents a search warrant etc. of the court to the server on behalf of the user and has the key recovered. Will be.

[0037]

However, the conventional Yaksha
In the cyclic signature method, there is a problem that it is impossible to send another message in addition to the message to be signed, and it is not possible to designate a verifier.

Although the final verification can be confirmed by anyone, this is sometimes inconvenient. In other words, anyone who has obtained the signature identifiers r ₁₂ and s ₁₂ can verify the signature and read the message, and privacy may be violated because anyone is communicating with whom.

In the protocol 3, if the authenticator r ₁₂ , s ₁₂ is eavesdropped during the transmission of the authenticator r ₁₂ , s ₁₂ from the investigating institution I to the YGS server at the time of key recovery, there is a possibility that information about who is being searched is leaked. However, in the case of Kerberos or Yaksha, it is not preferable that anyone can verify the message and recover the message, because the user only needs to authenticate the key server firmly.

An object of the present invention is to solve the above-mentioned conventional problem and realize a signature which can send an additional message by a cyclic signature and can designate a verifier. In particular,
By using the signature specified by the confirmer, the mutual authentication between the user and the YAS server by the cyclic signature in Yaksha is improved, and the YAS server authenticates the user as a valid user, and the verification result (evidence) is verified. YGS
The purpose is to prevent privacy from being violated when shown to the server.

[0041]

In order to solve the above-mentioned problems, the present invention provides an authentication method in which a primitive root of an integer ring modulo a sufficiently large prime number is used as a base of signature information under an integer ring. A first signature unit for secretly holding a certain first secret key, a second signature unit for secretly holding a second secret key that is an element of an integer ring, and a third signature key that is a source of an integer ring. Holding means for publishing a signature, a prime number, a base, a first common public key, a second common public key, and a verifier public key as public keys, wherein the first signature means generates a first message Means for generating a first random number and a second random number; means for generating first signature information from the first random number and the public key; and generating an encrypted message from the first message, the second random number and the public key. Means for transmitting the encrypted message and the first signature information to the second signature means Wherein the second signature means comprises: means for receiving the encrypted message and the first signature information; means for calculating the first message from the encrypted message and the second secret key; means for generating the second message; Means for generating a third random number, a first message, a second message,
Means for generating second signature information from the signature information, the third random number, and the public key; and means for transmitting the second signature information to the first signature means, wherein the first signature means further receives the second signature information. Means for generating third signature information from the second signature information, the first random number, the second message, and the first secret key;
Means for transmitting the signature information to the signature confirmation means, wherein the signature confirmation means restores the first message using the means for receiving the third signature information, and the third signature information, the public key, and the third secret key. And means for verifying the signature.

With this configuration, only the designated signature confirmation means can verify the cyclic signature, and the privacy protection function can be enhanced.

[0043]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below in detail with reference to FIGS.

(Embodiment) In an embodiment of the present invention, a message specified by a user by designating a verifier is verified by a YAS server, a cyclic signature is attached with an additional message, and further a YGS server is used. This is an authentication method for verification.

FIG. 1 is a functional block diagram of the authentication system according to the embodiment of the present invention. In FIG. 1, the publishing means
101 is a means for distributing a public key necessary for creating and confirming a signature. The first signer 102 is a means for the user to sign and transmit the first message. Second signer 103
Is a YAS server that signs and sends the second message. The signature verification unit 104 is a YGS server that receives and verifies the signature information.

The first message generating means 105 is a means for generating a first message to be transmitted. The encrypted message creation means 106 is means for encrypting the first message. The first signature information creating means 107 is means for creating first signature information for the first message. The first transmitting means 108 is means for transmitting the first signature information to the second signer.

The first receiving means 109 transmits the first signature information to the first
This is the means to receive from the signer. The first message calculation means 110 is a means for calculating and confirming the first message from the first signature information. The second message generation means 111
This is a means for generating a second message to be transmitted. The second signature information creation unit 112 is a unit that creates second signature information for the second message. The second transmitting means 113 is means for transmitting the second signature information to the first signer.

The second receiving means 114 transmits the second signature information to the second
This is the means to receive from the signer. Third signature information creation means
Reference numeral 115 denotes a unit that creates third signature information for the message. The third transmitting means 116 is means for transmitting the third signature information to the second signer. The third receiving means 117 includes a third
This is a means for receiving the signature information from the first signer. The signature verification means 118 is a means for calculating and confirming a message from the third signature information.

FIG. 2 is a flowchart showing the operation of the authentication method according to the embodiment of the present invention. In FIG. 2, step 1 is a public key publishing procedure by the publishing means. Step 2 is a procedure for generating the first signature information by the first signer. Step 3 is a procedure for generating the second signature information by the second signer. Step 4 is the third signing by the first signer.
This is a procedure for generating signature information. Step 5 is a signature verification procedure by the signature verifier.

The operation of the authentication system according to the embodiment of the present invention configured as described above will be described. In this example, a Nyberg-Rueppel message restoration type signature for signing two messages is used as a cyclic signature, and further transformed into a signature specified by a confirmer.

In step 1, the publishing means generates and publishes a public key (p, g, y, _yy , y ₂ ) using a known method. For example, The disclosure means is
And the base g are sent to the first signer, the second signer, and the signature verifier. The modulus p is a sufficiently large prime number. A sufficiently large prime number is a large prime number that does not allow the discrete logarithm problem to be practically solved. The base g is a primitive root of an integer ring Z _p ^* modulo _p . That is, ^{_{Z p * = {1,2, ···}} , p-1} g p-1 modp = 1 g q modp ≠ 1 (0 <q <p-1).

The first signer generates a secret key x ₁ (an element of the integer ring Z _p ^* ) and keeps it secret. The first signer first public key y ₁ (= g ^ x ₁ modp) is generated and sent to the public means. The second signer generates a secret key x ₂ (an element of the integer ring Z _p ^* ) and keeps it secret. Second signer first public key y ₂ (= g ^ x ₂ mo
dp) and send it to the publishing means. The signature verifier generates a secret key x ₃ (an element of the integer ring Z _p ^* ) and keeps it secret. A signature verifier public key y ₃ (= g ^ x ₁ modp) is generated and sent to the public means.

The public means uses the first signer's first public key y ₁ and the second signer's first public key y ₂ to obtain a first common public key y _y (common to the first signer and the second signer). = G ^ (x ₁ + x ₂ ) mod
p) is generated and sent to the first signer, the second signer, and the signature verifier. The signature verification public key y _3, and sends it to the first signer and the second signer.

The first signer is the first signer second public key y₁₂
(= Y_Three^ x₁ modp) and send it to the publishing means. Second
The signer is the second signer second public key y_{twenty two}(= Y_Three^ x_Two mod
p) and send it to the publishing means. First signer second public key
y₁₂And the second signer second public key y_{twenty two}From the first signer and the
2 The common second common public key y (= y_Three^ (x₁+ X _Two)
 modp) to generate a signature verification
Send to witness.

In step 2, the first signer (user) generates a message M. The message M is encrypted by generating random numbers k ₁ and k ₂ . First, the signature information, r
_{= Y 3 ^ (- k 1} ) to create a modp. Using a key (y × y ₃ ^ (− x ₁ )) corresponding to the secret key x ₂ of the second signer (YAS),
The message M is encrypted to generate a message (C ₁ , C ₂ ). That is, C ₁ = y ₃ ^ k ₂ modp = g ^ (x ₃ × k ₂ ) modp C ₂ = M × (y × y ₃ ^ (-x ₁ )) ^ k ₂ modp = M × (y ₃ ^ (x ₁ + x ₂ ) × y ₃ ^ (− x ₁ )) ^ k ₂ modp = M × g ^ (k ₂ × x ₂ × x ₃ ) modp is calculated. The message (C ₁ , C ₂ ) is sent to the second signer (YAS) together with r.

In step 3, the second signer (YAS)
Is expressed as follows: C ₂ / C ₁ ^ x ₂ modp = M × g ^ (k ₂ × x ₂ × x ₃ ) / g ^ (x ₃ × k ₂ × x ₂ ) modp = M ) To check the legitimacy of the user by decrypting the ciphertext sent from the user. The second signer (YAS) generates a second message m, and writes that YGS is a signature limited as a signature verifier. From the extracted message M, the generated second message m, the received r, and the generated random number k ₃ , r ₁₂ = M × r × y ₃ ^ (− k ₃ ) modps ₂ = k ₃ −m × x ₂ × r ₁₂ mod (p-1) is created, and (m, r ₁₂ , s ₂ ) is the first signer (user)
Send to

In step 4, the first signer (user) obtains s ₁ = k ₁ −m × x ₁ × r ₁₂ mod (p−1) s ₁₂ from the received m, r ₁₂ and s _2. = S ₁ + s ₂ mod (p−1), and sends (r ₁₂ , s ₁₂ , m) to the signature verifier (YGS).

In step 5, the signature verifier (YGS)
Can verify the signature by using (r ₁₂ , s ₁₂ ), the public key (p, g, y, _yy , y ₃ ), the second message m, and the secret key x ₃ . That is, r ₁₂ × y ₃ ^ s ₁₂ × y _y (r ₁₂ × m × x ₃ ) modp = M × r
× y ₃ ^ (− k ₃ ) × y ₃ ^ (k ₁ −m × x ₁ × r ₁₂ + k ₃ −m × x ₂ × r ₁₂ ) × y
₃ ^ ((r ₁₂ × m) × (x ₁ + x ₂ )) modp = M × y ₃ ^ (− k ₁ −
k ₃ ) × y ₃ ^ (k ₁ −m × x ₁ × r ₁₂ + k ₃ −m × x ₂ × r ₁₂ ) × y
₃ ^ ((r ₁₂ × m) × (x ₁ + x ₂ )) modp = M In the actual calculation, the exponent part is (p−
By calculating the remainder in 1), the amount of calculation can be reduced.

In this example, the first signer is the user. However, if the first signer is the investigator, the procedure for recovering the key by the investigator during law enforcement is exactly the same. That is, the YAS verifies the legitimacy of the investigating agency by decrypting the cipher text sent from the investigating agency, such as a court warrant. After that, a signature is specified by the confirmer using the YAS private key and the YGS public key, and the signature is returned to the investigating agency.

The investigating agency sends a circular signature to YGS. YGS
Confirms that the message has already been authenticated by law enforcement and YAS. In other words, the basic protocol does not change even in the search mode at the time of law enforcement, and at the time of law enforcement, an investigating agency presents a search warrant of the court to the server on behalf of the user to have the key recovered.

With the cyclic signature, additional messages can be sent and the verifier can be specified. In particular, by using the signature specified by the confirmer, YAS authenticates the user as a valid user, and verifies the verification result (evidence) to Y.
In the case of indicating to the GS, even if it is eavesdropped, it cannot be decrypted to prevent privacy from being violated.

As described above, in the embodiment of the present invention,
The authentication method is configured to verify the message signed by the user by designating the verifier on the YAS server, cyclically sign with an additional message, and then verify it on the YGS server. The cyclic signature can be verified, and the privacy protection function can be enhanced.

[0063]

As is apparent from the above description, in the present invention, the authentication method using the primitive root of the integer ring modulo a sufficiently large prime number as the base of the signature information is the first secret which is the element of the integer ring. First signature means for secretly holding a key, second signature means for secretly holding a second secret key that is an element of an integer ring, and signature confirmation for secretly holding a third secret key that is an element of an integer ring Means,
Means for publishing a prime number, a base, a first common public key, a second common public key, and a verifier public key as public keys, wherein the first signature means includes: means for generating a first message; Means for generating a first random number and a second random number;
Means for creating signature information, means for creating an encrypted message from the first message, the second random number and the public key, means for transmitting the encrypted message and the first signature information to the second signature means, 2 signature means, means for receiving the encrypted message and the first signature information, and means for receiving the encrypted message and the second signature information.
Means for calculating a first message from a secret key, means for generating a second message, means for generating a third random number,
First message, second message, first signature information, and third message
Means for generating second signature information from a random number and a public key;
Means for transmitting the signature information to the first signature means.
The signature means further includes means for receiving the second signature information, means for generating third signature information from the second signature information, the first random number, the second message, and the first secret key, and signature verification of the third signature information. Means for transmitting the signature to the means, means for receiving the third signature information, means for restoring the first message with the third signature information, the public key and the third secret key to verify the signature. And the user, 2
The effect is obtained that signature verification can be performed by associating two key servers and the privacy protection function can be enhanced.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of an authentication method according to an embodiment of the present invention;

FIG. 2 is a flowchart showing the operation of the authentication method according to the embodiment of the present invention;

FIG. 3 is a functional block diagram of a conventional Nyberg-Rueppel message restoration type signature scheme,

FIG. 4 is a flowchart showing the operation of a conventional Nyberg-Rueppel message restoration type signature scheme,

Fig. 5 Conventional Nyberg-Rueppel with two messages
Functional block diagram of message restoration type signature method,

FIG. 6: Conventional Nyberg-Rueppel with two messages
Flow chart showing the operation of the message restoration type signature scheme,

FIG. 7 is a functional block diagram of a conventional cyclic signature scheme;

FIG. 8 is a flowchart showing the operation of a conventional cyclic signature scheme;

FIG. 9 is a functional block diagram of a conventional Kerberos (Kerberos) system,

FIG. 10 is a flowchart showing the operation of a conventional Kerberos (Kerberos) system;

FIG. 11 is a functional block diagram of a conventional Yaksha system,

FIG. 12 is a flowchart showing the operation of a conventional Yaksha system.

[Explanation of symbols]

 101 publishing means 102 first signer 103 second signer 104 signature verification means 105 first message generation means 106 encrypted message creation means 107 first signature information creation means 108 first transmission means 109 first reception means 110 first message Calculation means 111 second message generation means 112 second signature information creation means 113 second transmission means 114 second reception means 115 third signature information creation means 116 third transmission means 117 third reception means 118 signature verification means 301 publication means 302 Signer 303 Receiver 304 Message generation means 305 Signature information creation means 306 Transmission means 307 Receiving means 308 Message calculation means 501 Publishing means 502 Signer 503 Receiver 504 First message generation means 505 Second message generation means 506 Signature information creation means 507 transmitting means 508 receiving means 509 message calculating means 701 publishing means 702 first signer 703 second signer 704 signature verifier 705 first message generator Step 706 Encrypted message creating means 707 First signature information creating means 708 Transmitting means 709 Receiving means 710 First message calculating means 711 Second signature information creating means 712 Transmitting means 713 Receiving means 714 Second message calculating means 715 Third signature information Creation means 716 Transmission means 717 Receiving means 718 Signature verification means 91 User 92 Authentication server 93 Ticket issuing server 94 Service organization 1001 TGS ticket request 1002 TGS ticket delivery 1003 Service ticket request 1004 Service ticket delivery 1005 Service ticket transmission 1006 Service provision 1101 User 1102 YAS 1103 YGS 1104 Service Agency 1201 Initial Ticket Request 1202 Initial Ticket Delivery 1203 Service Ticket Request 1204 Service Ticket Delivery 1205 Service Ticket Transmission 1206 Service Provision

Claims (3)

[Claims] 1. An authentication system in which a primitive root of an integer ring modulo a sufficiently large prime number is used as a base of signature information, wherein a first signature means for secretly holding a first secret key as an element of the integer ring is provided.
(User), a second signature means (YAS) for secretly holding the second secret key that is the element of the integer ring, and a signature confirmation means (Secretally holding the third secret key that is the element of the integer ring) YGS)
Means for publishing the prime number, the base, the first common public key, the second common public key, and the verifier public key as public keys, wherein the first signature means generates a first message Means for generating a first random number and a second random number;
Means for generating first signature information from a random number and the public key;
Means for generating an encrypted message from the first message, the second random number, and the public key; and means for transmitting the encrypted message and the first signature information to the second signature means. Means for receiving the encrypted message and the first signature information; means for calculating the first message from the encrypted message and the second secret key; means for generating a second message; Third
Means for generating a random number, the first message and the second
Means for generating second signature information from a message, the first signature information, the third random number, and the public key; and means for transmitting the second signature information to the first signature means, wherein the first signature Means for receiving the second signature information; means for generating third signature information from the second signature information, the first random number, the second message, and the first secret key; Means for transmitting signature information to the signature confirmation means, the signature confirmation means comprising: means for receiving the third signature information; and the third signature information, the public key, and the third secret key. Means for restoring the first message and verifying the signature. 2. The method according to claim 1, wherein the first message is a message to be subjected to signature verification, and the second message is a message indicating that the third signature information is a signature in which the signature confirmation means is limited to a confirmer. The authentication method according to claim 1, wherein: 3. The authentication method according to claim 1, wherein said first signature means is an investigative institution.