Decryption method and device, and access right authentication method and apparatus

[0002] 1. Field of the Invention

[0003] The present invention relates to encryption and decryption of digital data and authentication of access rights to digital data or services, which applies the encryption and decryption of the digital data.

[0004] 2. Discussion of the Related Art

[0005] To protect the data security by encryption and decryption, there are the following two types of relationships between a user of encrypted data and an owner of a decryption key that is necessary to decrypt the data.

[0006] 1) The user of the data and the owner of the decryption key are the same person.

[0007] 2) The user of the data and the owner of the decryption key are not the same person.

[0008] As an example of 1), personal confidential communication is a typical case. In this case, the recipient holds a decryption key for the data in secret. The sender encrypts the data with an encryption key corresponding to the decryption key of the recipient. The recipient's leakage of the decryption key to the third party leads to an intrusion into the recipient's privacy, which is a great disadvantage to the recipient. Therefore, if the recipient obtains the decryption key, no problem is expected.

[0009] As an example of 2), a simultaneous multi-address transmission of the digital data is mentioned. The charged digital data simultaneously transmitted to multi-addresses is encrypted and cannot be used without being decrypted. Although the decryption key is known to a third party, it will not be any disadvantage to a recipient of the data. Therefore, if the recipient obtains the decryption key for decrypting the encrypted digital data, there occurs a possibility that the recipient leaks the decryption key to the third party to get good value for it. In other words, the user of the data has a positive reason to leak the decryption key. Accordingly, it is necessary to separate the user of the data from the owner of the decryption key.

[0010] The satellite broadcast now solves the problem by storing the decryption key in an area in a hardware that is inaccessible from the outside and assigning the decryption of the data to the hardware (referred to as delegated decryption). The user of the digital data cannot obtain the decryption key, and therefore the problem that the decryption key is leaked by the user of the digital data does not arise.

[0011] Not only in the satellite broadcast, the same method is also used in the case where the decryption is performed on the data transmitted simultaneously to many and unspecified addresses, such as the simultaneous multi-address transmission through the World Wide Web (WWW) of the Internet or the cable television broadcast (CATV). There are many kinds of assignee, for example, a built-in decryption device of a satellite broadcast tuner, an IC card with a decryption function, a computer connected to a network and so forth. Any of them performs the delegated decryption.

[0012] If the delegated decryption is performed in an easy manner that the encrypted data is directly transmitted to the decryption device and the decryption result is received from the decryption device, the following problems arise.

[0013] (1) The decryption device can learn what is decrypted and what is a result of the decryption.

[0014] The decryption device can be created so that a history of the delegated decryption is generated. If such decryption device has been created, there occurs a possibility that a privacy of a recipient of data as to what kind of data he/she would like to decrypt is recorded by the decryption device and later used illegitimately. Such decryption device is also a disadvantage to a sender of the data because the sender cannot delegate the decryption of the data undesirable to be known to the decryption device. In the example of the satellite broadcast, if data of a movie is encrypted and sent, the decryption device stores the decrypted plain data of the movie. The data of the movie may be illegitimately used by the creator of the decryption device.

[0015] (2) If there is an intruder intercepting a communication with the decryption device, the intruder can learn what is decrypted and what is a result of decryption.

[0016] The seriousness of the problem can be understood by considering the example in which the recipient of delegation of the decryption is a computer connected to a network. Without any countermeasure, a third party intercepting the network can easily learn what is decrypted and what is a result of the delegated decryption.

[0017] A blind decryption is a technique of delegated decryption that clears up the above two problems. A blind decryption method based on the RSA (Rivest-Shamir-Adleman) is disclosed by “Fair Public Key Cryptosystem”, Proc. Crypto 92, pp. 113-138 (1993). The outline is described as follows.

[0018] It is assumed that a person delegating the decryption is “Alice” and a decryption device that performs decryption on delegation is “Bob”. It is further assumed that a decryption key held by Bob is D, an RSA modulus is n and an encryption key is E. Since this is the RSA cryptosystem, the following expression is established:

[0019] ED≡1 mod φ(n)

[0020] wherein φ(n) is an Euler number of n.

[0021] It is then assumed that the result of encryption of a plain text M with n and E is expressed as C=M^Emod n.

[0022] 1) Alice generates a random number r and calculates the expression C′=r^EC mod n, and transmits C′ to Bob.

[0023] 2) Bob calculates the expression R=C′^Dmod n and transmits R to Alice.

[0024] 3) Alice obtains r⁻¹which satisfies the expression r⁻¹r≡1 mod n, and calculates the expression M′=r⁻¹R mod n.

[0025] With the following expression, it is possible to confirm that Alice can obtain a correct decryption result according to the above procedures:

[0026] M′≡r⁻¹R≡r⁻¹C′^D≡r⁻¹(r^EC)^D≡r⁻¹(r^EM^E)^D≡r⁻¹rM≡M mod n  (1)

[0027] In this method, Bob and a third party intercepting the communication between Bob and Alice can only know C′=r^EC mod n and R=C′^−D≡rM mod n. The encrypted text C that Alice wanted to decrypt and its decryption result M cannot be known to Bob and the intruder intercepting the communication. This method thus resolves the above two problems of the assigned decryption.

[0028] Japanese Patent Application Laid-Open No. 10-247905 suggests a device for controlling the access to the digital data, which employs the blind decryption.

[0029] The device for access controlling disclosed by the above application consists of a proving device for proving an ownership of the access right to the data and a verification device for verifying the proof by the proving device. The verification device stores encrypted digital data and another piece of data generated by encrypting a key for decrypting the digital data with an RSA public key (the another piece of data is referred to as an encrypted key). The proving device is an RSA decryption device. The verification device delegates the decryption of the encrypted key by using the blind decryption to the proving device and then decrypts the digital data with a result of the delegated decryption. If the digital data is correctly decrypted, it is considered that the proving device succeeded in proving the ownership of the access right.

[0030] Owing to the use of the blind decryption, the content of the delegated encrypted key and the decryption key of the digital data cannot be known to the proving device or an intruder intercepting the communication between the verification device and the proving device.

[0031] The technique of the Japanese Patent Application Laid Open No. 10-247905 is particularly characterized by the configuration of the proving device which is of the RSA type. The Japanese Patent Application Laid Open No. 10-247905 suggests embedding of the RSA decryption key in changeable data called an access ticket for enabling the decryption of multiple RSA public keys with a single proving device. To prevent stealing the RSA decryption key from the access ticket, the access ticket is created by masking the RSA decryption key. Thereby it is possible to open the access ticket. The proving device disclosed by the Japanese Patent Application No. 10-247905 contains tamper resisting hardware such as an IC card. The masking effect of the access ticket is removed only by the tamper-resisting the hardware.

[0032] The access controlling disclosed by the above application is now described in detail.

[0033] The verification device holds encrypted data and an encrypted key K* generated by encrypting a key K for decrypting the encrypted data with the RSA modulus n and an encryption key E. The proving device has an IC card with a function for operating a modulus exponentiation and calculating a one-way hash function f(x, y). The IC card further stores secret data d. If the decryption key for the RSA modulus n and the encryption key E is D, the access ticket is t=D−f (d, n).

[0034] The proof and verification of ownership of the access rights are executed according to the following procedures.

[0035] 1. The verification device generates a random number r.

[0036] 2. The verification device calculates C=r^EK* mod n and transmits n and C to the proving device, provided that K* is K^E.

[0037] 3. The proving device calculates R₁=C^f(^{d, n}) mod n in the IC card.

[0038] 4. The proving device calculates R₂=C^tmod n.

[0039] 5. The proving device calculates R=R₁R₂mod n and transmits the result to the verification device.

[0040] 6. The verification device obtains r⁻¹that satisfies r⁻¹r≡1 mod n and then calculates K′=r⁻¹R mod n.

[0041] If the above procedures are correctly executed, K≡K′ mod n is obtained. Therefore, ownership of the access rights can be proved according to the following expression.

[0042] K′≡r⁻¹R≡r⁻¹R₁R₂≡r⁻¹C^f(d,n)+1C^t≡r⁻¹C^f(d,n)+1≡r¹C^D≡r⁻¹(r^EK*)^D≡r⁻¹(r^EK^E)^D≡r⁻¹rK≡K mod n  (2)

[0043] In this method, if a user possesses an IC card having d different for each user, an access ticket for decrypting an encrypted key of the digital data is also different for each user. Although a user copies and uses an access ticket of another person, it is impossible to prove the ownership of the access right. Therefore, an access right of each user can be controlled by limiting issuance of the access ticket to each user. Moreover, if the RSA modulus n and the encryption key E are changed for each piece of the digital data, an access ticket for a certain piece of data cannot be used for other pieces of data. Thus, it is possible to control the access to each piece of the digital data.

[0044] The problem of the blind decryption originates in its strong blindness. According to the blind decryption, the decryption device can obtain information only about reception of delegation of decryption for a certain piece of data when the decryption is delegated. No information about the data assigned to be decrypted is transmitted to the decryption device. However, there are many requests for transmitting a specific type of information about the data to the decryption device when the decryption is assigned. Examples of the requests are as follows:

[0045] 1) If a fee is charged for the delegated decryption service, and if the decryption fee is different for each piece of data, the decryption fee should be informed to the decryption device together with the transmission of the encrypted data.

[0046] 2) If a term of the use is fixed for each piece of data, the term of the use should be informed to the decryption device together with the transmission of the encrypted data, and it should be checked by the decryption device.

[0047] 3) If users of each piece of the data are limited, a list of users of the data should be transmitted with the encrypted data and it is checked by the decryption device whether the person delegating the decryption is a qualified user of the data.

[0048] 4) If the delegated decryption of a confidential document is executed, an identifier of encrypted data should be transmitted to the decryption device with the encrypted data and the decryption device must store them for a later inspection.

[0049] However, suppose that these pieces of information are transmitted to the decryption device together with the encrypted data without any contrivance. It is then possible for the person who delegates the decryption to replace a piece of information to be attached to the data with another one at his/her own convenience if he/she has a malicious intent. Several types of illegitimate actions become possible, for example, to transmit information including a fee for delegated decryption of a piece of data lower than the actual fee, to transmit information including a term of use prescribed to be longer than the actual term, to transmit a list of accessible persons or an identifier that is different from the reality, or the like.

[0050] The same is true with the technique of the Japanese Patent Application Laid Open No. 10-247905 that controls the access to the digital data applying the conventional blind decryption. The invention disclosed by the above application includes a tamper-resisting IC card. It is hardly possible to change the process executed in the IC card or to tamper with the information stored in the IC card. Therefore, if the information is correctly transmitted to the IC card, the security in the IC card can be guaranteed. It is desirable to store the fee for accessing the data or to check the term of the access to the data within the IC card. However, in the Japanese Patent Application No. 9-418, there is no means to securely transmit those pieces of information to the IC card because the application utilizes the conventional blind decryption without any changes.

[0051] The present invention has been made in view of the above circumstances and has an aspect to provide a blind decryption that can securely transmit a specific piece of information to a decryption device while keeping the blindness of data delegated to be decrypted.

[0052] Another aspect of the present invention is to control the access to the digital data by applying the above-described blind decryption method.

[0053] Additional aspects and advantages of the invention will be set forth in part in the description which follows and in part will be obvious from the description, or may be learned by practice of the invention.

[0054] To achieve the former aspect of the present invention, a decryption device that decrypts a cipher text encrypted by RSA method comprises a first storage unit that stores a modulus n of a modulus exponentiation operation and a second storage unit that stores first decryption information. The device also comprises a cipher text input unit that inputs the cipher text and an information input unit that inputs second decryption information. The device further comprises an operation unit that performs the modulus exponentiation operation by raising the cipher text to a power, a product of the first decryption information and the second decryption information, modulo n and outputs a result of the operation.

[0055] With this configuration, two pieces of decryption information, the first and the second are required when a decryption device decrypts the encrypted data.

[0056] Encryption is to raise a piece of data to a power, an encryption key, modulo n. Decryption is correctly performed if a product of the encryption key, the first decryption information and the second decryption information is 1 modulo an Euler number of n (φ(n)).

[0057] It is assumed that the second decryption information is input to the decryption device from the outside. Therefore, the correct decryption result is unavailable unless the encrypted data and the second decryption information are correctly input.

[0058] The device may be configured so that the information that must not be substituted, such as a decryption fee of each data, is input to the device as the second decryption information. Then a penalty of unsuccessful decryption is imposed for illegitimate substitution of information.

[0059] As another configuration of the decryption device that requires the first decryption information and the second decryption information for decrypting the encrypted data, the decryption device may raise the encrypted data to a power, an inverse number of the second decryption information modulo the first decryption information, modulo n and may output it as a decryption result.

[0060] With this configuration, if the first decryption information is an Euler number of the modulus n and the second decryption information is an encryption key, the decryption is correctly performed.

[0061] In this configuration, also, the second decryption information is input to the decryption device from the outside. Therefore, unless the encrypted data and the second decryption information are correctly input, the correct decryption result cannot be obtained.

[0062] With this configuration, it is also assumed that the information that must not be substituted, such as a decryption fee of data, is input to the decryption device as the second decryption information. Then a penalty of unsuccessful decryption is imposed for illegitimate substitution of information.

[0063] To achieve the latter aspect of the present invention, an access right authentication apparatus that authenticates an access right of a user by verifying legitimacy of a response generated for proving the access right of the user, comprises a first storage unit that stores challenging data, a second storage unit that stores user identifying information, a third storage unit that stores proof support information that is a result of a predetermined operation on the user identifying information and security characteristic information and a fourth storage unit that stores security required information. The apparatus also comprises a response generation unit that generates a response by executing a predetermined operation on the challenging data, the user identifying information, the proof support information and the security required information, and a response verification unit that verifies the response is generated based on the security characteristic information and the security required information.

[0064] With this configuration, a legitimate combination of the response, the user identifying information, the proof support information and the security required information indispensable for correct authentication of the access right.

[0065] The information that must not be substituted, such as an access fee, should be included in the security required information. Then a penalty of access rejection is imposed for illegitimate substitution of information.

[0066] With another configuration of the latter aspect of the present invention, an access right authentication apparatus that authenticates a user's access right by verifying legitimacy of a response generated for proving the user's access right, comprises a first storage unit that stores challenging data, a second storage unit that stores user identifying information and a third storage unit that stores proof support information that is a result of a first predetermined operation on the user identifying information and security characteristic information. The apparatus also comprises a fourth storage unit that stores security required information, a fifth storage unit that stores security examination information, and an examination unit that examines whether the security examination information stored in the fifth storage unit has a specific relationship with a result of a second predetermined operation on the challenging data stored in the first storage unit and the security required information stored in the fourth storage unit. The apparatus further comprises a response generation unit, when the examination unit finds that the security examination information has the specific relationship with the result of the second predetermined operation, that generates a response by executing a third predetermined operation on the challenging data stored in the first storage unit, the user identifying information stored in the second storage unit and the proof support information stored in the third storage unit, and a response verification unit that verifies the response is generated based on the security characteristic information and the security required information.

[0067] With this configuration, a legitimate combination of the response, the user identifying information, the proof support information and the security required information indispensable for correct authentication of the access right.

[0068] The information that must not be substituted, such as an access fee, should be included in the security required information. Then a penalty of access rejection is imposed for illegitimate substitution of information.

[0069] The accompanying drawings, which are incorporated in and constitute a part of this specification illustrate embodiment of the invention and, together with the description, serve to explain the objects, advantages and principles of the invention. In the drawings:

[0070] FIG. 1 is a block diagram showing a decryption device in a first embodiment according to the present invention;

[0071] FIG. 2 is a block diagram showing a decryption device in a second embodiment according to the present invention;

[0072] FIG. 3 is a block diagram showing a basic configuration of an access right authentication apparatus in third to sixth embodiments according to the present invention;

[0073] FIG. 4 is a block diagram showing a configuration of a proving device of the access right authentication apparatus in the third embodiment according to the present invention;

[0074] FIG. 5 is a block diagram showing a configuration of a proving device of the access right authentication apparatus in the fourth embodiment according to the present invention;

[0075] FIG. 6 is a block diagram showing a configuration of a proving device of the access right authentication apparatus in the fifth embodiment according to the present invention;

[0076] FIG. 7 is a block diagram showing a configuration of a proving device of the access right authentication apparatus in the sixth embodiment according to the present invention;

[0077] FIG. 8 is a block diagram showing a configuration of a verification device of the access right authentication apparatus in the third, fourth and sixth embodiments according to the present invention;

[0078] FIG. 9 is a block diagram showing a configuration of a verification device of the access right authentication apparatus in the fifth embodiment according to the present invention;

[0079] FIG. 10 illustrates operations of the proving device of the access right authentication apparatus in the third embodiment according to the present invention;

[0080] FIG. 11 illustrates operations of the verification device of the access right authentication apparatus in the third embodiment according to the present invention;

[0081] FIG. 12 illustrates operations of the proving device of the access right authentication apparatus in the fourth embodiment according to the present invention;

[0082] FIG. 13 illustrates operations of the verification device of the access right authentication apparatus in the fourth embodiment according to the present invention;

[0083] FIG. 14 illustrates operations of the proving device of the access right authentication apparatus in the fifth embodiment according to the present invention;

[0084] FIG. 15 illustrates operations of the verification device of the access right authentication apparatus in the fifth embodiment according to the present invention;

[0085] FIG. 16 illustrates operations of the proving device of the access right authentication apparatus in the sixth embodiment according to the present invention; and

[0086] FIG. 17 illustrates operations of the verification device of the access right authentication apparatus in the sixth embodiment according to the present invention.

[0087] Preferred embodiments of decryption method and device, and access right authentication method and apparatus according to the present invention are now described in detail based on the drawings.

[0088] First Embodiment

[0089] The first embodiment of the present invention is a blind decryption device. The configuration of the device is shown in FIG. 1. The present embodiment adopts a modulus exponentiation operation using a composite number n as a modulus, in which X is raised to a power Y modulo n (both X and Y are integers), for an encryption/decryption method. The decryption device of the present embodiment requires a modulus n and two pieces of decryption information d₁and d₂for decryption. An encryption key E, d₁and d₂are generated to satisfy the following expression (1):

[0090] Ed₁d₂≡1 mod φ(n)  (1)

[0091] wherein φ(n) is an Euler number of n.

[0092] A cipher text C corresponding to a piece of data M is generated according to the following expression (2):

[0093] C=M^Emod n  (2)

[0094] A user of the blind decryption device of the present embodiment possesses the cipher text C, a modulus n, the encryption key E and the second decryption information d₂. When the user delegates decryption of C to the decryption device of the present embodiment, he/she generates C′ by providing a blind effect to C, and inputs C′ and d₂to the decryption device. The user then receives an output R from the decryption device. Finally, the user removes the blind effect from R to obtain a decryption result.

[0095] Specific procedures executed by a user who uses the decryption device are as follows.

[0096] 1. The user generates a random number r (1<r<n).

[0097] 2. The user calculates the following expression (3) to provide the blind effect to the cipher text C.

[0098] C′=r^EC mod n  (3)

[0099] 3. The user transmits C′ and d₂to the blind decryption device and receives an output R from the device.

[0100] 4. The user calculates the following expression (4) to obtain a decryption result M′.

[0101] M′=r−1R mod n  (4)

[0102] The blind decryption device of the present embodiment comprises the following sub units: an input unit 11 that inputs a blind-effected cipher text C′ and second decryption information d₂; an output unit 12 that outputs a decryption result R; a modulus storage unit 13 that stores a modulus n; a first decryption information storage unit 14 that stores the first decryption information d₁; and a decryption unit 15 that calculates the decryption result R based on n, C′, d₁and d₂.

[0103] Procedures executed by the blind decryption device of the present embodiment are as follows.

[0104] 1. The input unit 11 receives the blind-effected cipher text C′ and the second decryption information d₂from the user and transmits them to the decryption unit 15.

[0105] 2. The decryption unit 15 obtains the modulus n from the modulus storage unit 13 and the first decryption information d₁from the first decryption information storage unit 14 and then calculates the following expression (5).

[0106] R=C′^ddmod n  (5)

[0107] 3. The output unit 12 outputs R.

[0108] The following expression (6) shows that the correct decryption is performed when the combination of the cipher text C and the second decryption information d₂is legitimate.

[0109] M≡r⁻¹R≡r⁻¹C′^dd≡r⁻¹(r^EC)^dd≡r⁻¹rM≡M mod n  (6)

[0110] If a piece of information different from the second decryption information d₂is transmitted instead of d₂to the blind decryption device, the user cannot obtain a correct decryption result. Therefore, it is possible to prevent transmission of a false decryption fee to the decryption device by including the decryption fee in the second decryption information d₂.

[0111] However, if the second decryption information d₂is not a prime number, a problem arises. When the factorization d₂=a*b is possible, though C′^amod n and b are transmitted to the decryption device instead of C′ and d₂, the same output can be obtained from the decryption device. Accordingly, it is possible to obtain a correct decryption result by transmitting false decryption information b instead of d₂.

[0112] To prevent the occurrence of the problem, the combination of E, d₁and d₂should be determined so that d₂becomes a prime number.

[0113] Although d₂is a prime number, the same output can be obtained by transmitting C^d2; mod n and 1 to the decryption device instead of C′ and d₂. To prevent this problem, the decryption device should have means for confirming that the transmitted second decryption information is a value excepting for 1. The decryption is performed only when the second decryption information is a value excepting for 1.

[0114] If d₂is not a prime number, it is effective to determine the combination of E, d₁and d₂so that d₂has a redundancy, for example, repetition of a specific value, and to dispose means for confirming the redundancy in the transmitted second decryption information in the decryption device. If a probability that a nontrivial divisor of d₂has the redundancy known to the decryption device is sufficiently low, the attack of transmitting the divisor to the decryption device instead of d₂can be avoided by this method.

[0115] It is also possible to add a hash function operation unit that performs a one-way hash function V(x) to the blind decryption device and to calculate the following expression (7) instead of the expression (5).

[0116] R=C′^dV()mod n  (7)

[0117] The one-way hash function has a characteristic that it is very difficult to calculate x and y that satisfy h(x)=h(y) which are different from each other. As the examples of the one-way hash function, MD2, MD4 and MD5 by RSA Data Securities Inc., the Secure Hash Standard by the U.S. Federal Government and so forth are known.

[0118] In this case, the encryption key E, d₁and d₂are generated to satisfy the following expression (8).

[0119] Ed₁V(d₂)≡1 mod φ(n)  (8)

[0120] With this configuration, it is possible to keep V(x) secret to the user, and therefore the security is improved. Moreover, d₂larger than the modulus n is available.

[0121] If the decryption fee information is included in the second decryption information, the decryption device is configured to store the transmitted decryption fee information and the decryption fee is charged to the person who delegated the decryption based on the stored fee information, a delegated decryption system able to impose decryption fees without falsehood can be realized.

[0122] In another configuration, information about the term of the use of the encrypted data is included in the second decryption information. The decryption device is configured to have a clock. Thereby the transmitted term of the use and the time indicated by the clock are compared to determine whether the decryption should be performed. Thus, a delegated decryption system that can limit the term of the use of data is available.

[0123] In the other configuration, information about attributes of the encrypted data is included in the second decryption information. The decryption device is configured to store the transmitted attribute information. Thereby a delegated decryption system that stores the data which can be used in a statistical work, an inspection or the like is available.

[0124] Second Embodiment

[0125] The second embodiment is also a blind decryption device. A configuration of the device is shown in FIG. 2.

[0126] The present embodiment adopts the modulus exponentiation using a composite number n as a modulus for an encryption/decryption method. The decryption device uses the modulus n, two pieces of decryption information d₁and d₂for decryption. The decryption information d₁is an Euler number of the modulus n and the decryption information d₂is the encryption key E. The encryption key E and the decryption information d₁are generated to be relatively prime.

[0127] The cipher text C for a piece of data M is generated according to the above expression (2).

[0128] The user of the blind decryption device of the present embodiment has the cipher text C, the modulus n and the encryption key E (the second decryption information d₂). When the user assigns the decryption of C to the decryption device of the present embodiment, he/she generates C′ by providing a blind effect to C, and inputs C′ and E to the decryption device. The user then receives an output R from the decryption device and removes the blind effect of R to obtain a decryption result.

[0129] The specific procedures for the user to use the decryption device of the present embodiment are the same as those of the first embodiment.

[0130] The blind decryption device of the present embodiment comprises the following sub-units: an input unit 11 that inputs a cipher text C′ that is blind-effected and an encryption key E; an output unit 12 that outputs a decryption result R; a modulus storage unit 13 that stores a modulus n; an Euler number storage unit 16 that stores an Euler number φ(n); an inverse number generation unit 17 that inputs a modulus and an integer and calculates an inverse number of the integer with the modulus; and a decryption unit 15 that obtains the decryption result R based on n, C′ and the result of calculation of the inverse number generation unit 17.

[0131] Procedures of the blind decryption device of the present embodiment are as follows.

[0132] 1. Through the input unit 11, the decryption device receives the blind-effected cipher text C′ and second decryption information d₂from the user. C′ and d₂are transmitted to the decryption unit 15 and the inverse number generation unit 17, respectively.

[0133] 2. The inverse number generation unit 17 takes an Euler number φ(n) out of the Euler number storage unit 16. The inverse number of d₂modulo the Euler number φ(n), d₂⁻¹modulo φ(n), is calculated. The result is transmitted to the decryption unit 15.

[0134] 3. The decryption unit 15 takes the modulus n out of the modulus storage unit 13 and calculates the following expression (9).

[0135] R=C′^(d)mod n  (9)

[0136] 4. R is output through the output unit 12.

[0137] If the combination of the cipher text C′ and the second decryption information d₂is legitimate, it is confirmed according to the following expression (10) that the decryption has been correctly executed.

[0138] M′≡r⁻¹R≡r⁻¹C′^(d)≡r⁻¹(r^EC)^(d)≡r⁻¹(r^EM^E)^(d)≡r⁻¹rM≡M mod n  (10)

[0139] If the user transmits information different from the second decryption information to the blind decryption device of the present embodiment, he/she cannot obtain the correct decryption result. Therefore, it is possible to prevent transmission of false decryption fee to the decryption device by including the decryption fee in the second decryption information.

[0140] It is also possible to add a hash function operation unit that performs a one-way hash function V(x) to the blind decryption device and to calculate an inverse number of V(d₂), V(d₂)⁻¹instead of calculating the inverse number of d₂by the inverse number generation unit 16. The following expression (11) may be calculated by the decryption unit 15.

[0141] R=C′(^V(d)mod n   (11)

[0142] In this case, the encryption key E is V(d₂). With this configuration, it is possible to use d₂larger than the modulus.

[0143] It is also possible to store prime factors of the modulus n instead of storing the Euler number of the modulus n and to calculate the Euler number when the decryption is executed.

[0144] Further, it is possible to store prime factors of the modulus n instead of storing the Euler number of the modulus n, to perform the modulus exponentiation operation with each prime factor as a modulus and then obtain a result with the modulus n based on the Chinese remainder theorem.

[0145] Specifically, if n is a product of two prime numbers p and q, the following expressions are calculated:

[0146] R₁=C′^{dmod (p−1)}mod p

[0147] R₂=C′^{dmod (q−1)}mod q.

[0148] It is possible to calculate R from R₁and R₂based on the Chinese remainder theorem.

[0149] Third, fourth, fifth and sixth embodiments of the present invention are access right authentication apparatuses. A basic configuration common to these embodiments is shown in FIG. 3.

[0150] In the figure, each of these access right authentication apparatuses has a verification device 100 and a proving device 200. The proving device 200 generates a response utilizing an access ticket generated by an access ticket generation device 300. The verification device 100 is annexed to services or digital data that require authentication of access right to use, which verifies ownership of a legitimate access right of a user of the services or digital data. The proving device 200 is possessed by the user of the services or digital data, which proves to the verification device 100 that the user has a legitimate access right.

[0151] For authentication of an access right, the verification device 100 transmits challenging data to the proving device 200 that generates a response corresponding to the challenging data and returns it to the verification device 100. In the third, fourth, fifth and sixth embodiments, the challenging data transmitted by the verification device 100 is generated by encrypting arbitrary data. The proving device 200 decrypts the challenging data to generate the response. The verification device 100 examines whether the response returned by the proving device is a result of correct decryption of the challenging data. Thus, the response is verified.

[0152] For generation of the response, the challenging data, the user identifying information, an access ticket and security required information are required.

[0153] The user identifying information is a piece of digital data corresponding to each user of the services or digital data, which is different from user to user. The user identifying information is stored in the proving device 200 in a format that the user cannot access.

[0154] The access ticket is a piece of digital data generated from security characteristic information and the user identifying information.

[0155] The security required information is possessed by the verification device 100. The information is transmitted to the proving device with the challenging data.

[0156] In the third, fourth, fifth and sixth embodiments, the challenging data cannot be decrypted until both security characteristic information and security required information are available. Accordingly, if an intruder intercepting the communication between the verification device 100 and the proving device 200 takes an illegitimate action such as substitution of the security required information transmitted to the proving device 200 with the challenging data, the intruder cannot obtain a correct response. Thereby it is possible to prevent substitution of the security required information with something else.

[0157] In the third, fourth, fifth and sixth embodiments, the access right authentication apparatus can be configured so that information about the fees for using the services or digital data is embedded in the security required information. The transmitted information about the fees is then stored in the proving device 200 in a form that user cannot change. If the using fee is charged to the user based on the information about fees, it is possible to charge fees to the user without deceit.

[0158] In another configuration of the third, fourth, fifth and sixth embodiments, information about the term of the use of the services or digital data can be included in the security required information. The proving device 200 is configured to have a clock. Thereby the transmitted term of the use and the time indicated by the clock are compared to determine whether the response can be generated. Thus, an access right authentication apparatus that can limit the term of the use of services or digital data is available.

[0159] In the other configuration of the third, fourth, fifth and sixth embodiments, information about attributes of the services or digital data may be included in the security required information. The proving device 200 can be configured to store the transmitted attribute information in a form that any user cannot change. Thereby an access right authentication apparatus that stores the data, which can be used in a statistical work, an inspection or the like, is available.

[0160] Third Embodiment

[0161] Configurations of a proving device and a verification device of the third embodiment are shown in FIGS. 4 and 8, respectively. Operations of the proving device and the verification device are shown in FIGS. 10 and 11, respectively.

[0162] As shown in FIG. 4, the proving device 200 includes a received data storage unit 202, an access ticket storage unit 203, a user identifying information storage unit 204, a power generation unit 205, a first operation unit 206, a second operation unit 207 and a response generation unit 208.

[0163] As shown in FIG. 8, the verification device 100 includes a verification unit 101, an access ticket public key storage unit 103, a random number generation unit 104, a random number storage unit 105, a random number effect removal unit 106, a random number effect providing unit 107, a challenging plain data storage unit 108, a security required information storage unit 109, a received data storage unit 110 and a verification operation unit 111.

[0164] In the third embodiment of the present invention, the security characteristic information D, public information E and n corresponding to D and the security required information I are defined as follows.

[0165] n is an RSA modulus, a product of two prime numbers p and q which are sufficiently large, satisfying the following expression (12).

[0166] n=pq  (12)

[0167] φ(n) is an Euler number of n calculated by the following expression (13).

[0168] φ(n)=(p−1)(q−1)  (13)

[0169] The security characteristic information D is an RSA private key modulo n and satisfies the following expression (14).

[0170] gcd(D, φ(n))=1  (14)

[0171] Here, gcd(x, y) represents the greatest common divisor of x and y. I is a prime number that satisfies the following expression (15).

[0172] gcd(I, φ(n))=1  (15)

[0173] The public information E is generated to satisfy the following expression (16).

[0174] EID mod φ(n)=1  (16)

[0175] D and E are also referred to as access ticket private key and access ticket public key, respectively. The access ticket t is generated using the access ticket private key D, the user identifying information e and the modulus n based on the following expression (17).

[0176] t=D−F(e, n)  (17)

[0177] The user identifying information e is different for each user, which is used to identify each user. The function F is a function in which function values hardly collide with each other. For example, it is defined using the one-way hash function as the following expression (18) or (19).

[0178] F(x, y)=h(x|y)  (18)

[0179] F(x, y, z, u, w)=h(x|y|z|u|w)  (19)

[0180] Here, x|y denotes the concatenation of two bit-string representations of x and y.

[0181] It is possible to open t, E, n and I to the public. On the contrary, D, e, p, q, φ(n) and the function F are required to be kept secret to everybody but those who have the right to generate the ticket.

[0182] Hereinafter, data K that is to be encrypted is referred to as verification data. Data R generated by the proving device is referred to as a response. Data that the proving device 200 receives from the verification device 100 for generating the response is referred to as challenging data.

[0183] Operations of the third embodiment are as follows.

[0184] 1. When a user accesses digital contents that require authentication by the access right authentication apparatus, the verification device 100 is invoked. If the verification device 100 is implemented as a part of an application program running on a PC or workstation of the user, it is activated by the user with a normal method of starting an application program using an instruction device such as a keyboard or mouse. When execution of the application program reaches the program constituting the verification device 100, it is activated.

[0185] If the verification device 100 is implemented on the other PC or workstation (referred to as server) connected through a network, the user activates a communication program on his/her own PC or workstation. Then the communication program transmits a channel open request to the server in accordance with predetermined procedures, and the verification device 100 on the server is invoked. For example, suppose that the communication program of the user follows procedures called TCP/IP for communicating with the server. The verification device is associated with a specific port of the server in advance and the communication program of the user is set to designate the port and transmit a TCP connection request to the server. It is then possible that a daemon (inetd) on the server activates the verification device in reply to the TCP connection request. This method of implementation is widely used in the network such as the Internet.

[0186] It is possible to implement the verification device 100 as an exclusive-purpose device. For example, the verification device 100 can be implemented as a program written in a ROM in an IC card reader/writer and the proving device 200 can be a program implemented in a microcontroller of an IC card. In this case, when a user inserts the IC card into the reader-writer, the verification device 100 is invoked.

[0187] 2. The challenging data C, the modulus n stored in the access ticket public key storage unit 103 and the security required information I stored in the security required information storage unit 109 are transmitted from the verification device 100 to the proving device 200. They are written in the received data storage unit 202. In the challenging plain data storage unit 108, C′ is stored as the challenging plain data. If arbitrary data K is assumed to be the verification data, the challenging plain data C′ and the verification data K satisfy the following expression (20).

[0188] C′=K^Emod n  (20)

[0189] In the verification device 100, the-random number generation unit 104 generates a random number r. The challenging data C is generated by calculating the following expression (21) in the random number effect providing unit 107 using r, E and n obtained from the access ticket public key storage unit 103 and C′ obtained from the challenging plain data storage unit 108.

[0190] C=r^EC′ mod n  (21)

[0191] Thus, the challenging data C is generated and written in the received data storage unit 202 in the proving device 200. The generated random number r is stored in the random number storage unit 105.

[0192] In this manner, a random number effect is provided to the challenging data and the effect is removed when the response is generated by the proving device 200. In other words, blindness is provided to the challenging data. Thereby the challenging plain data or its decryption result can be concealed from an intruder intercepting the communication between the verification device 100 and the proving device 200 or the proving device 200 itself. A replay attack is also disabled by changing the random number used for the random number effect each time. The following embodiments have the same features as this embodiment. If the verification device is configured so that it does not hold the data K, but holds only C′, which is an encryption result of K, and if the verification device has means that verifies coincidence between K and a result of removing the random number effect from the response transmitted from the proving device 200, a risk of leaking the data K from the verification device 100 can be avoided.

[0193] 3. A power generation unit 205 in the proving device 200 obtains the user identifying information e stored in the user identifying information storage unit 204 and the modulus n stored in the received data storage unit 202 and calculates the following expression (22).

[0194] F(e, n)  (22)

[0195] 4. The first operation unit 206 in the proving device 200 obtains the security required information I and the modulus n stored in the received data storage unit 202 and calculates the following expression (23) using I, n and the data generated by the power generation unit 205 to obtain R′.

[0196] R′=C^{If(e, n)}mod n  (23)

[0197] 5. The second operation unit 207 in the proving device 200 obtains the access ticket t stored in the access ticket storage unit 203 and calculates the following expression (24) to obtain R″.

[0198] R″=C^Itmod n  (24)

[0199] 6. The response generation unit 208 in the proving device 200 obtains R′ and R″ from the first operation unit 206 and the second operation unit 207, respectively, and calculates the following expression (25) to obtain R.

[0200] R=R′R″ mod n  (25)

[0201] 7. The proving device 200 writes R in the received data storage unit 110 in the verification device 100.

[0202] 8. The random number effect removal unit 106 in the verification device 100 takes the random number r previously generated out of the random number storage unit 105 and calculates the following expression (26)

[0203] K′=r⁻¹R mod n  (26)

[0204] 9. Only when the combination of the access ticket t, the user identifying information e and the security required information I used in the proving device 200 is legitimate, the data K′ obtained by calculation and the verification data K coincide with each other. Thus, the verification is correctly performed.

[0205] 10.The calculated K′ is transmitted to the verification unit 101 in the verification device 100. The execution unit 102 performs normal processes only when K′=K is established.

[0206] If the above procedures are correctly preformed, it is understood that K and K′ coincide with each other according to the following expressions (27).

[0207] K′≡r⁻¹R≡r⁻¹R′R″≡r⁻¹C^{IF(e, n)}C^It≡r⁻¹C^ID≡r⁻¹(r^EC′)^ID≡r⁻¹(r^EK^E)ID≡r⁻¹rK≡K mod n  (27)

[0208] If an intruder intercepting the communication between the verification device 100 and the proving device 200 substitutes false information I′ for the security required information I, K does not coincide with K′. Therefore, the intruder cannot access the services or digital data.

[0209] However, if the security required information I is not a prime number, a problem occurs. If factorization I=a*b is possible, though C^amod n and b are transmitted to the decryption device instead of C and I, the decryption device provides the same output. Accordingly, normal access is available by transmitting the false information b instead of the security required information I. To avoid this problem, the combination of E, D and I should be determined so that I is a prime number.

[0210] However, though I is set to a prime number, if C^Imod n and 1 are transmitted to the decryption device instead of C and I, the same output can be obtained from the decryption device. To avoid this problem, the proving device 200 should have means that confirm whether the transmitted information is 1. The proving device 200 is configured to perform exponentiation operation on C only when the information is not 1.

[0211] When I is not a prime number, it is effective to determine the combination of E, D and I so that I has a redundancy, for example, repetition of a specific value, and to dispose means that confirms the redundancy in the transmitted security required information in the proving device 200. If a probability that a nontrivial divisor of I has the redundancy known to the proving device 200 is sufficiently low, the attack of transmitting the divisor to the decryption device instead of the security required information can be avoided by this method.

[0212] In this embodiment, the user identifying information storage unit 204, the power generation unit 205 and the first operation unit 206 are disposed in the inside of the IC card or the like, which any user cannot access or tamper with. It is then possible to guard the embodiment from illegitimate action enabled by leakage of the user identifying information or tampering with the power generation unit 205 or the first operation unit 206.

[0213] It may be possible to add an operation means that performs the one-way hash function V(x, y) to the proving device 200 of the present embodiment and to calculate the following expressions (28) and (29) instead of the expressions (23) and (24).

[0214] R′=C^{V(I, n)F(e, n)}mod n  (28)

[0215] R″=C^{V(I, n)t}mod n  (29)

[0216] In this case, the encryption key E, the security required information I and the security characteristic information D are set to satisfy the following expression (30).

[0217] EV(I, n)D≡1 mod φ(n)  (30)

[0218] With this configuration, the security required information larger than the modulus is available.

[0219] If the configuration of the proving device 200 is changed to calculate the security characteristic information from the access ticket and the output of the power generation unit 205, and to perform the modulus exponentiation operation on the challenging data using the result of calculation, the same effect as this embodiment is obtained.

[0220] Some examples for the method of verifying coincidence of K and K′ in the verification device 100 are now described. These examples are applicable to the fourth, fifth and sixth embodiments.

[0221] [1] Direct comparison of verification data and decryption result

[0222] The verification unit 101 stores the verification data K in advance.

[0223] A comparison part in the verification unit 101 directly compares the verification data K with the data K′ generated by decrypting the challenging data. Only when K′=K is established, a normal process is conducted. Otherwise, an error handling process such as a halt of the process is conducted. This example has a weakness of security that the verification data K, which is an object of verification, appears by itself in the verification device. For instance, if the verification device 100 is implemented as a program running on a PC or workstation of a user, it is possible to analyze the program and steal K, though it is difficult. If the value of K is known to a user, he/she can make a device that copies operations of the proving device 200. An illegitimate access by impersonation is then possible.

[0224] [2] Use of one-way function

[0225] To overcome the above weakness, the data to be an object of verification stored in the verification unit 101 is changed from the verification data K itself to data h(K) obtained by operating the one-way hash function h on the data K. According to the characteristic of the one-way hash function, it is extremely difficult to calculate x that satisfies an expression y=h(x) from the data y stored in the response storage unit. The verification unit 101 has a transformation part that outputs a result of operation of the one-way hash function on input data. The comparison part compares the output h(K′) obtained by operation of the hash function on the data K′ generated by decrypting the challenging data with the stored data, namely, h(K). In this example, the verification data K does not appear in the program. Moreover, it is extremely difficult to calculate K from h(K) stored in the response storage unit. Therefore, this example is more secure than example [1]. However, the comparison part is implemented as conditional statements in a program. If the verification device is implemented as a program having a configuration easily analyzed or tampered with, it is possible to tamper with the program to skip the conditional statements. Thus, a weakness still remains.

[0226] [3] Decrypted value used as decryption key for decrypting specific data

[0227] The data stored for verification is encrypted data. The data K′ generated by decrypting the challenging data is a key for decrypting the encrypted data. The verification unit 101 decrypts the encrypted data stored for verification using the value of the data K′ as a decryption key. If the encrypted data is decrypted, the program can be executed. With this configuration, the decryption key itself does not appear in the verification device 100. Therefore, high security is available.

[0228] [4] Confirmation whether decrypted value satisfies specific redundancy

[0229] The verification device 100 has redundancy confirmation unit.

[0230] The verification unit 101 transmits the value of data K′ generated by decrypting the challenging data to the redundancy confirmation unit. If it is confirmed by the unit that the data has specific redundancy, the program can be executed. Examples of the redundancy are, a specific pattern repeated in decrypted data, a specific condition satisfied by data in a specific position, a meaning held by data as a specific language, and so forth.

[0231] [5] Encryption of program code itself

[0232] Data generated by encrypting a part or all of program code held by the verification device 100 is stored as challenging plain data in the challenging plain data storage unit. That is, the data K′ generated by decrypting the challenging data is a part or all of the program code. The execution unit embeds the data K′ in a predetermined position of the program and then executes the program. If the proving device returns correct data, in other words, the data K′ is a result of correct decryption of the code, the program can be executed. It is also possible to generate an executable file by embedding the decrypted code in the original program and activate the file. However, it is desirable from the viewpoint of security to embed the decrypted code in the program on a memory and then activate it on the condition that the program is only stored in the memory. In this example, a part or all of the code indispensable for executing the program is encrypted. Therefore, even in the case of relatively low security, such that the program to be executed is implemented as an application program running on a PC or workstation of a user, illegitimate execution of the program can be prevented.

[0233] [6] Decrypted value used as decryption key of program

[0234] The verification device 100 holds data generated by encryption of part or all of the code of the program. Data K′ generated by decrypting the challenging data is a decryption key necessary for decrypting the encrypted program code. With this configuration, it is possible to control the size of the data K′ to a predetermined small amount regardless of the size of the code to be encrypted. Thereby an overhead in communication is reduced. The verification unit 101 decrypts the encrypted program code stored by the verification device 100 using the data K′. The decrypted code is embedded in a predetermined position of the program and the program is then executed. The program can be executed only when the proving device returns the correct data, that is, the code is correctly decrypted by the data K′.

[0235] Fourth Embodiment

[0236] The fourth embodiment differs from the third embodiment in the method of calculation of the access ticket t. FIGS. 8 and 5 show the configurations of the verification device and the proving device, respectively, of the fourth embodiment. FIGS. 13 and 12 show the operations of the verification device and the proving device, respectively. The characteristics of security characteristic information D, public information E, n and security required information I and methods of generation of challenging plain data C′ and challenging data C are the same as those of the first embodiment. In FIG. 5, devices or units corresponding to those in FIG. 4 have the same reference numbers as those in FIG. 4.

[0237] An access ticket t of the fourth embodiment is generated according to the following expression (31).

[0238] t=D/F(e, n) mod φ(n)  (31)

[0239] The operations of the fourth embodiment are now described.

[0240] 1. When a user accesses a verification device 100, it is invoked. Similar to the case of the third embodiment, the verification device 100 can be implemented as an application program running on a PC or workstation of a user, a server program running on a server connected to a PC or workstation of a user through a network or an exclusive device such as an IC card reader-writer. The same is true of the following embodiments.

[0241] 2. The verification device 100 transmits challenging data C, a modulus n stored in an access ticket public key storage unit 103 and security required information I stored in a security required information storage unit 109. They are written in a received data storage unit 202 in a proving device 200.

[0242] 3. A power generation unit 205 obtains user identifying information e stored in a user identifying information storage unit 204 and the modulus n stored in the access ticket public key storage unit 203 and calculates the following expression (32).

[0243] F(e, n)  (32)

[0244] 4. A proof operation unit 209 in the proving device 200 obtains the security required information I and the modulus n stored in the received data storage unit 202. The proof operation unit 209 calculates the following expression (33) using the security required information I, the modulus n and the data generated by the power generation unit 205 to obtain R′.

[0245] R′=C^{IF(e, n)}mod n  (33)

[0246] 5. A response generation unit 208 in the proving device 200 obtains an access ticket t stored in the access ticket storage unit 203, the modulus stored in the received data storage unit 202 and R′ from the proof operation unit 209 and calculates the following expression (34) based thereon to obtain R.

[0247] R=R′^tmod n  (34)

[0248] 6. The proving device 200 writes R in the received data storage unit 110 in the verification device 100.

[0249] 7. A random number effect removal unit 106 in the verification device 100 takes a random number r previously generated out of a random number storage unit 105 and calculates the following expression (35).

[0250] K′=r⁻¹R mod n  (35)

[0251] 8. Only when the combination of the access ticket t used in the proving device 200, the user identifying information e and the security required information I is legitimate, K′ obtained as a result of calculation and the challenging data K are coincident with each other. Thus, the verification is correctly conducted. In other words, if the above procedures are correctly conducted, it is confirmed that K and K′ are coincide with each other according to the following expression (36).

[0252] K′≡r⁻¹R≡r⁻¹Rⁿ≡r⁻¹C^{IF(e n)t}≡r⁻¹C^{IF(e, n)D/F(e, n)}≡r⁻¹C^ID≡r⁻¹(r^EC′)^ID≡r⁻¹(r^EK^E)^ID≡r⁻¹rK≡K mod n  (36)

[0253] If an intruder intercepting the communication between the verification device 100 and the proving device 200 substitutes the security required information I for I′, K and K′ do not coincide with each other. Therefore, it is impossible for the intruder to access the services or digital data.

[0254] However, if the security required information I is not a prime number, a problem occurs. If factorization I=a*b is possible, though C^amod n and b are transmitted to the decryption device instead of C and I, the decryption device provides the same output. Accordingly, normal access is available by transmitting false information b instead of the security required information I. To avoid this problem, the combination of E, D and I should be determined so that I is a prime number.

[0255] However, though I is a prime number, if C^Imod n and 1 are transmitted to the decryption device instead of C and I, the same output can be obtained from the decryption device. To avoid this problem, the proving device 200 should have means that confirm whether the transmitted information is 1. The proving device 200 is configured to perform exponentiation operation on C only when the information is not 1.

[0256] When I is not a prime number, it is effective to determine the combination of E, D and I so that I has a redundancy, for example, repetition of a specific value, and to dispose means that confirms the redundancy in the transmitted security required information in the proving device 200. If a probability that a nontrivial divisor of I has redundancy known to the proving device 200 is sufficiently low, the attack of transmitting the divisor to the decryption device instead of the security required information can be avoided by this method.

[0257] To compare K′ with the verification data K, the method same as that used in the third embodiment is available.

[0258] In this embodiment, the user identifying information storage unit 204, the power generation unit 205 and the proof operation unit 209 are disposed in the inside of the IC card or the like, which any user cannot access or tamper with. It is then possible to guard the embodiment from illegitimate use enabled by leaking the user identifying information or tampering with the power generation unit 205 or the proof operation unit 209.

[0259] It may be possible to add an operation unit that performs the one-way hash function V(x, y) to the proving device 200 of the present embodiment and to calculate the following expression (37) instead of the expression (33).

[0260] R′=C^{v(I, n)F(e, n)}mod n  (37)

[0261] In this case, the encryption key E, the security required information I and the security characteristic information D are set to satisfy the following expression (38).

[0262] EV(I, n)D≡1 mod φ(n)  (38)

[0263] With this configuration, the one-way hash function V(x, y) can be kept secret from the user and the security required information larger than the modulus is available.

[0264] If the configuration of the proving device 200 is changed to calculate the security characteristic information based on the access ticket and the output of the power generation unit 205 and to perform the exponentiation operation on the challenging data using the result of calculation, the same effect as this embodiment is available.

[0265] Fifth Embodiment

[0266] In the third and fourth embodiments, the proving device 200 cannot confirm the legitimacy of the security required information. In the fifth embodiment, a proving device 200 confirms the legitimacy of security required information. If the information is illegitimate, the proving device 200 does not generate a response. FIGS. 9 and 6 show configurations of a verification device 100 and the proving device 200, respectively, of the fifth embodiment. FIGS. 15 and 14 show operations of the verification device 100 and the proving device 200, respectively.

[0267] In this embodiment, characteristics of security characteristic information D, an RSA modulus n and φ(n), an Euler number of n, are same as those of the third embodiment. Challenging plain data C′ and challenging data C are generated in the same way as the third embodiment. Public information E is generated to satisfy the following expression (39).

[0268] ED mod φ(n)=1  (39)

[0269] Similar to the first embodiment, an access ticket t is generated based on an access ticket private key D, user identifying information e, a modulus n and a function F according to the following expression (40).

[0270] t=D−F(e, n)  (40)

[0271] Operations of this embodiment are now described.

[0272] 1. When a user accesses a verification device 100, it is invoked.

[0273] 2. An examination information generation unit 112 in the verification device 100 obtains the challenging data C and security required information I stored in the security required information storage unit 109 and calculates the following expression (41) based thereon to generate examination information M.

[0274] M=V(C, I)  (41)

[0275] The function V has the same characteristics as the function F. It is necessary to keep it secret from everything but the verification device 100 and the proving device 200.

[0276] 3. The verification device 100 transmits the challenging data C, the modulus n stored in the access ticket public key storage unit 103, the security required information I stored in the security required information storage unit 109 and the examination information M to the proving device 200. They are written in the received data storage unit 202 of the proving device 200.

[0277] 4. A security required information verification unit 210 of the proving device 200 obtains the challenging data C, the security required information I and the examination information M written in the received data storage unit 202 and verifies whether the values satisfy the following expression (42).

[0278] M=V(C, I)  (42)

[0279] If the values satisfy the expression (42), the following process is executed.

[0280] 5. A power generation unit 205 of the proving device 200 obtains the user identifying information e stored in the user identifying information storage unit 204 and the modulus n stored in the received data storage unit 202 and calculates the following expression (43).

[0281] F(e, n)  (43)

[0282] 6. A first operation unit 206 of the proving device 200 calculates the following expression (44) to obtain R′ using the challenging data C and the modulus n written in the received data storage unit 202 and the data generated by the power generation unit 205.

[0283] R′=C^{F(e, n)}mod n  (44)

[0284] 7. A second operation unit 207 of the proving device 200 obtains the access ticket t stored in the access ticket storage unit 203, the challenging data C and the modulus n stored in the received data storage unit 202 and calculates the following expression (45) to obtain R″.

[0285] R″=C^tmod n  (45)

[0286] 8. A response generation unit 208 of the proving device 200 obtains R′ and R″ from the first operation unit 206 and the second operation unit 207, respectively, and calculates the following expression (46) to obtain R.

[0287] R=R′R″ mod n  (46)

[0288] 9. The proving device transmits R to the verification device 100 and it is written in the received data storage unit 110.

[0289] 10. A random number effect removal unit 106 of the verification device 100 takes a random number r previously generated out of the random number storage unit 105 and calculates the following expression (47).

[0290] K′=r⁻¹R mod n  (47)

[0291] 11. If the combination of the access ticket t, user identifying information e and the security required information I is correct, the data K′ obtained as a result of calculation coincide with the verification data K. Thus, the verification is correctly executed.

[0292] If the above procedures are correctly executed, K′ and K coincide with each other as shown by the following expression (48).

[0293] R′≡r⁻¹R≡r⁻¹R′R″≡r⁻¹C^{f(e, n)}C^t≡r⁻¹C^D≡r⁻¹(r^EC′)D≡r⁻¹(r^EK^E)D≡r⁻¹rK≡K mod n  (48)

[0294] If an intruder intercepting the communication between the verification device 100 and the proving device 200 substitutes the security required information I for I′, it is detected by the examination in step 4. The proving device 200 then halts generation of the response and informs the verification device 100 of the halt. Several ways of informing the halt are available. For example, halt code can be written in the received data storage unit 110. An alternative is to determine the time necessary to generate the response in advance and to halt the process if no response is written by the predetermined time.

[0295] To compare K′ and the verification data K, the method same as that of the third embodiment can be applied.

[0296] In this embodiment, the user identifying information storage unit 204, the security required information verification unit 210, the power generation unit 205 and the first operation unit 206 can be disposed in the inside of the IC card or the like, which any user cannot access or tamper with. It is then possible to guard the embodiment from an illegitimate use enabled by leaking the user identifying information or tampering with the power generation unit 205 or the first operation unit 206.

[0297] Sixth Embodiment

[0298] Configurations of a verification device 100 and a proving device 200 of the sixth embodiment are shown in FIGS. 8 and 7, respectively. Operations of the verification device 100 and the proving device 200 are shown in FIGS. 17 and 16, respectively. In this embodiment, public information (RSA modulus) n and φ(n), an Euler number of n, satisfy the same characteristics as those of the first embodiment. Security required information I is an integer that satisfies the following expression (49).

[0299] gcd(I, φ(n))=1  (49)

[0300] An access ticket t is generated according to the following expression (50) using the Euler number φ(n), user identifying information e, the modulus n and a function F.

[0301] t=φ(n)−F(e, n)  (50)

[0302] Operations of this embodiment are now described.

[0303] 1. A user accesses the verification device 100 and it is invoked.

[0304] 2. The verification device 100 transmits challenging data C, the modulus n stored in the access ticket public key storage unit 103 and the security required information I stored in the security required information storage unit 109 to the proving device 200. They are written in the received data storage unit 202. A challenging plain data storing unit 108 stores C′ as challenging plain data. If arbitrary data K is assumed to be verification data, the challenging plain data C′ and the data K satisfy the following expression (51).

[0305] C′=K^Imod n  (51)

[0306] A random number generation unit 104 of the verification device 100 generates a random number r. A random number effect providing unit 107 calculates the following expression (52) using r, n obtained from the access ticket public key storage unit 103, I obtained from the security required information storage unit 108 and C′ obtained from the challenging plain data storage unit 108 to generate the challenging data C. The generated challenging data C is written in the received data storage unit 202 of the proving device 200. The generated random number r is stored in a random number storage unit 105.

[0307] C=r^IC′mod n  (52)

[0308] 3. The power generation unit 205 of the proving device 200 obtains the user identifying information e stored in the user identifying information storage unit 204 and the modulus n stored in the received data storage unit 202 and calculates the following expression (53).

[0309] F(e, n)  (53)

[0310] 4. The proof operation unit 209 of the proving device 200 obtains the security required information I stored in the received data storage unit 202 and the access ticket t stored in the access ticket storage unit 203. The proof operation unit 209 then calculates the following expression (54) using the security required information I, the access ticket t and the data generated by the power generation unit 205.

[0311] φ=t+F(e, n)  (54)

[0312] After that, the proof operation unit 209 calculates D that satisfies the following expression (55).

[0313] DI≡1 mod φ  (55)

[0314] 5. A response generation unit 208 of the proving device 200 obtains D from the proof operation unit 209, C and n from the received data storage unit 202 and calculates the following expression (56) to obtain R.

[0315] R=C^Dmod n  (56)

[0316] 6. The random number effect removal unit 106 of the verification device 100 obtains a random number r that was previously generated from the random number storage unit 105 and calculates the following expression (57).

[0317] K′=r⁻¹R mod n  (57)

[0318] 7. Only when the combination of the access ticket t, the user identifying information e and the security required information I used in the proving device 200 is legitimate, K′ obtained as a result of calculation and the verification data K coincide with each other. Thus, the verification is correctly performed.

[0319] If the above procedures are correctly executed, coincidence between K and K′ can be confirmed according to the following expression (58).

[0320] K′≡r⁻¹R≡r⁻¹C^D≡r⁻¹(r^IC′)^D≡r⁻¹(r^IK^I)^D≡r⁻¹rk (∵φ(n)=t+F(e, n)) ≡K mod n  (58)

[0321] If an intruder who intercepts the communication between the verification device 100 and the proving device 200 substitutes the security required information I for I′, calculation cannot be succeeded.

[0322] I′D≢1 mod φ(n)

[0323] In this case, K and K′ do not coincide with each other. Therefore, the services or digital data cannot be accessed. To compare K′ and the verification data K, the method same as that of the third embodiment can be used.

[0324] In this embodiment, the user identifying information storage unit 204, the power generation unit 205, the proof operation unit 209 and the response generation unit 208 can be disposed in the inside of the IC card or the like, which any user cannot access or tamper with. It is then possible to guard the embodiment from an illegitimate use enabled by leaking the user identifying information or tampering with the power generation unit 205 or the proof operation unit 209.

[0325] It may be possible to add an operation unit that performs the one-way hash function V(x, y) to the proving device 200 of the present embodiment and to calculate the following expression (59) instead of the expression (55).

[0326] DV(I, n)≡1 mod n  (59)

[0327] If arbitrary data K is assumed to be verification data, the challenging plain data C′ and the data K satisfy the following expression (60).

[0328] C′=K^{I(I, n)}mod n  (60)

[0329] With this configuration, the security required information larger than the modulus is available.