JP2003308012A - Decoding apparatus and method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To safely send specific information to a decoder without disordering blindness of data consigned to be decoded. <P>SOLUTION: A cipher sentence C' applied with a blind effect and a second decrypt key d2 are received from a user via an input part 11 and sent to a decoding part 15. The decoding part 15 extracts a modulus number (n) from a modulus number storage part 13, extracts first decoded information d1 from a first decoded information storage part 14, calculates R=C'<SP>d1d2</SP>modn and outputs R via an output part 12. When the combination of a cipher sentence C and second decoded information d2 is right, the right decoded result is obtained. <P>COPYRIGHT: (C)2004,JPO

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to encryption / decryption of digital data and authentication of access qualification to digital data or services by applying encryption / decryption.

[0002]

2. Description of the Related Art When attempting to protect the security of data by encryption / decryption, there are two types of relationships between the user of encrypted data and the holder of the decryption key for decrypting the data.

When the data user and the holder of the decryption key are the same When the user of the data and the holder of the decryption key are not the same As the former example, secret communication between individuals is typical. In the case of communication between individuals, the recipient keeps the decryption key of the data in secret. The sender encrypts the data with the encryption key corresponding to the decryption key of the receiver. Leaking the decryption key to the third party by the recipient leads to a loss of privacy of the recipient, which is a great disadvantage for the recipient. Therefore, even if the recipient has the decryption key, no problem occurs.

An example of the latter is simultaneous broadcasting of digital data carried out by satellite broadcasting or the like. The paid digital data that is broadcasted simultaneously is encrypted, and cannot be used unless this digital data is decrypted. However, if the recipient possesses the decryption key for decrypting the encrypted digital data, the recipient does not have any disadvantage even if the decryption key is known to a third party. By leaking the key to a third party, a profit such as consideration can be obtained from the third party. In other words, the data user has a positive reason for leaking the decryption key, so that the data user and the decryption key holder have to be separated.

At present, in satellite broadcasting, this problem is solved by incorporating a decryption key in an area inaccessible from the outside in the hardware and entrusting the decryption of the data to this hardware (contract decryption). . Since there is no way for the user of digital data to obtain the decryption key itself, the problem of leakage of the decryption key by the user of digital data does not occur.

Not only those using satellite broadcasting but also WWW (World Wide Web) and CATV of the Internet
(Cable television broadcasting) also uses the same means when decoding data that is broadcast to the unspecified large number, such as the broadcast of data via broadcast. There are various consignees, such as a decoder built in the satellite broadcast tuner, an IC card having a decoding function, and a destination computer via a network, but there is no difference in that all of them are consignment decoding.

When entrusted decryption is performed by the easy method of transmitting encrypted data as it is to the decryptor and receiving the decryption result from the decryptor, the following two problems occur.

The decoder reveals what was decoded and what was the decoding result.

The decoder creator can create the decoder so that the history of the commissioned decoding remains. If the decoder were made in this way, the privacy of the recipient of the data as to what data they tried to decrypt could be stored in the decoder and later abused.
Also, a similar configuration of the decoder is disadvantageous to the sender of the data. From the perspective of the sender of the data, the data that the decoder does not want to know can not be subjected to the consignment decryption. In the case of satellite broadcasting, when a movie is encrypted and sent, the decrypted plaintext movie is stored in the decryptor, and there is a risk that the data is misused by the creator of the decryptor.

When a person intercepts communication with the decoder, the interceptor reveals what was decrypted and what the decryption result was.

The seriousness of this problem can be understood by imagining a case where the decryption entrustee is a computer connected to the destination via the network. In this case, if no means is taken, the third party who is intercepting the net can easily know what was decrypted by the consignment decryption and what the decryption result was.

Blind decoding is a technique of consignment decoding that simultaneously solves the above two problems. Silbio
Micali, Fair public key
Cryptosystem, Proc. Crypto
92, pp. 113-138 (1993) RSA
A blind decoding scheme based on (Rivest-Shamir-Adleman) is disclosed. The contents of the disclosure are outlined below.

The decryption entrustor is Alice, and the decryption decoder that receives the entrustment is Bob. Bob has a decryption key D, an RSA modulus n, and an encryption key E. Since it is RSA, ED≡1 mod φ (n) holds. However, φ (n) is the Euler number of n.

A plaintext M encrypted with n and E C = M ^E
mod n. 1. Alice generates a random number r and C ′ = r ^E C
Calculate mod n and send C ′ to Bob. 2. Bob calculates R = C ′ ^D mod n, and A
send to lice. 3. Alice is r ⁻¹ r ≡ ¹ mod n
⁻¹ is calculated, and M ′ = r ⁻¹ R mod n is calculated.

It can be seen from the following equation that Alice obtains the correct decoding result by the above procedure.

[0016]

[Equation 1] According to this scheme, the decoders Bob and Alice and B
C '= r ^{E for a} third party intercepting communications between
C mod n, R = C ′ ^D ≡rM mod n is only visible, and Alice wanted to decrypt the ciphertext C
In addition, the decoding result M of C is not exposed to the decoder Bob or an interceptor of communication. This method solves the two problems of the above-mentioned entrusted decryption.

An apparatus for controlling access to digital data by applying blind decoding is proposed in Japanese Patent Application No. 9-418.

The access control device described in Japanese Patent Application No. 9-418 comprises a certifying device for certifying possession of access right to data, and a verifying device for verifying proof by the certifying device. The verification device stores encrypted digital data and data obtained by encrypting a key for decrypting the digital data with an RSA public key (encryption key). The proving device is an RSA decoder. The verification device entrusts the decryption of the encryption key to the certification device by using blind decryption, and uses the result to decrypt the digital data. If it is decrypted correctly, the certification device has succeeded in certifying possession of the access right.

Since the blind decryption is used, the contents of the entrusted encryption key and the decryption key of the digital data are known to the certifying device or a person who intercepts the communication between the verifying device and the certifying device. Never.

The technique of Japanese Patent Application No. 9-418 is particularly applicable to RSA.
It is characterized by the configuration of the proof device, which is a decryptor. Japanese Patent Application No. 9-
In the proposal of No. 418, in order to enable decryption of a plurality of RSA public keys with a single certifier, the RSA decryption key is embedded in changeable data called an access ticket. The access ticket is a masked version of the RSA decryption key so that the RSA decryption key cannot be taken out from the access ticket, whereby the access ticket is openable information. Japanese Patent Application No. 9-4
The certifying device of No. 18 has tamper-resistant hardware such as an IC card, and the effect of the mask of the access ticket can be removed only by that hardware.

The access control proposed in Japanese Patent Application No. 9-418 will be described in detail below.

The verification device has the encrypted data and the encryption key K obtained by encrypting the decryption key K of the encrypted data K with the RSA modulus n and the encryption key E. The proof device is an IC having a function of calculating a modular exponentiation and a function of calculating a one-way hash f (x, y).
I have a card. Further secret data d is stored in the IC card. RSA modulus n, encryption key E
Access ticket t if the decryption key for is D
Is data having a value of t = D−f (d, n).

The proof and verification of possession of the access right are performed in the following procedure. 1. The verification device generates a random number r. 2. The verifier calculates C = r ^E K ^* mod n,
Send n and C to the proving device. However, K ^* is K ^E. 3. The proof device uses R ₁ = C ^{f (d, n)} m in the IC card.
Calculate od n. 4. The proving device calculates R ₂ = C ^t mod n. 5. The proving device calculates R = R ₁ R ₂ mod n,
Send to the verification device. 6. Verification device, a r ^-1 r≡1 mod n r ^-1
And K ′ = r ⁻¹ Rmod n is calculated.

If the above procedure is carried out correctly, K≡K '
It can be seen from the following equation that the mod n is obtained and the possession of the access right is proved.

[0025]

[Equation 2] In this method, if a user has an IC card of different d for each user, the access ticket for decrypting the encryption key of certain digital data will be different for each user.
Even if you copy another person's access ticket, you cannot use it to prove possession of access rights. Therefore, the access right for each user can be controlled by issuing or not issuing the access ticket for each user. Further, if the RSA modulus n and the encryption key E are changed for each digital data, the access ticket of one data cannot be used for other data. Therefore, access control for each digital data is also possible.

[0026]

The problem of blind decoding lies in its strong blindness. According to blind decoding, the only information that the decoder can collect by entrusting the decoding is the information that some kind of decoding entrusted.
No information about the data entrusted to be decrypted can be conveyed to the decoder. However, there are many demands to convey some kind of information about the data to the decoder when performing the consignment decoding. Specifically, there are the following. In the case of obtaining a fee by the consignment decryption service, if the decryption fee differs for each data, the decryption fee for the data together with the encrypted data must be transmitted to the decoder. When the expiration date is determined for each data, the expiration date of the data must be sent to the decryption device together with the encrypted data, and the decryption device must check the expiration date. When the number of users is limited for each data, the encrypted data and the list of users who can use the data must be sent to the decoder, and the decoder must check whether the entrustor is the user. I have to. If a confidential document is outsourced for decryption, the encrypted data must be sent to the decryptor along with the encrypted data for later auditing, and the decryptor must remember this.

If these pieces of information are transmitted to the decoder together with the encrypted data without any contrivance, when the entrustor has malicious intent, the attached information is replaced with something convenient for the entrustor. Is possible. For example, it is possible to cheat by sending information that is cheaper than the data to be entrusted, sending a later expiration date, sending a list of accessible persons different from the actual one, sending an identifier different from the actual one, etc.

This problem is solved by applying the conventional blind decoding to control access to digital data.
The same applies to the technology of No. 418. The proposal of Japanese Patent Application No. 9-418 has an IC card having tamper resistance. Modify the processing performed in the IC card,
It is very difficult to falsify the information stored in the card, so if the information can be correctly transmitted to the IC card,
The safety inside the IC card is guaranteed. Therefore, the storage of the access charge for the data and the checking of the expiration date of the access are carried out in the IC card.
Japanese Patent Application No. Hei 9 using the conventional blind decoding as it is
No. 418 has no means for securely transmitting such information to the IC card.

In view of the above problems, the first object of the present invention is to realize blind decoding in which specific information can be safely sent to a decoder while maintaining the blindness of the data entrusted with the decoding. To do. A second object of the present invention is to realize access control of digital data by applying a blind decoding method that solves the above problems.

[0030]

In order to achieve the first object, according to the present invention, when the decoder decrypts the encrypted data, the first decryption information and the second decryption information are used. It is structured to require information. More specifically, under the modulus n, the decryptor multiplies the encrypted data by the product of the first decryption information and the second decryption information, and outputs it as the decryption result.

The encryption is a process in which data is raised to the power of the encryption key under the modulus n, and the product of the encryption key, the first decryption information, and the second decryption information is modulo the Euler number of n. If is congruent with 1, it can be correctly decoded.

Furthermore, the second decryption information is input from the outside to the decryptor, and the encrypted data and
The device is devised so that a correct decoding result cannot be obtained unless the second decoding information is correctly input.

If the system is configured so that information that cannot be replaced, such as the data decoding fee, is input to the decoder as the second decoding information, it will be said that the decoding failure will occur in response to an illegal act of replacing the information. Penalties can be imposed.

In addition, when the decryptor decrypts the encrypted data, the decryptor requires the first decryption information and the second decryption information. And with
In this example, the encrypted data is exponentiated by the reciprocal of the second decryption information when the first decryption information is modulo, and the exponent is output as the decryption result.

If the first decryption information is the Euler number of modulus n and the second decryption information is the encryption key, the decryption can be performed correctly.

Further, the second decryption information is input from the outside to the decryptor, and the encrypted data and
The device is devised so that a correct decoding result cannot be obtained unless the second decoding information is correctly input.

If the system is configured so that the information that should not be replaced, such as the data decoding fee, is input to the decoder as the second decoding information, it is said that the decoding failure is caused by the fraudulent act of the information replacement. Penalties can be imposed.

In order to achieve the second object, according to the present invention, the access qualification for authenticating the above-mentioned user's access qualification is verified by verifying the correctness of the certification data generated for certifying the user's access qualification. The authentication device has a predetermined storage unit for storing authentication data, second storage unit for storing user's unique information, the user's unique information, and access qualification authentication characteristic information. Is held in the first storage means, the third storage means for storing the proof auxiliary information which is the execution result of executing the calculation of, the fourth storage means for storing the essential information for the access qualification authentication, and the first storage means. The authentication data, the unique information of the user stored in the second storage unit, the certification auxiliary information stored in the third storage unit, and the fourth storage unit. Ak A proof data generating means for generating proof data by performing a predetermined operation on the required information for the qualification authentication, the proof data based on the characteristic information of the access qualification authentication and the essential information of the access qualification authentication. Proof data verification means for verifying that the data has been generated is provided.

In the present invention, in order to correctly recognize the access qualification, the certification data, the unique information of the user,
The combination of auxiliary information for certification and required information for access qualification must be correct.

Information that should not be replaced, such as access fees, should be included in the required information for access qualification authentication.
It is possible to impose a penalty of denying access to fraudulent acts of replacing information.

In another configuration of the present invention for achieving the second object, the above-mentioned user's access qualification is authenticated by verifying the correctness of the certification data generated to prove the user's access qualification. In the access qualification authentication device, the first storage means for storing the authentication data, the second storage means for storing the unique information of the user, the unique information of the user and the characteristic information of the access qualification authentication are provided. In contrast,
Third storage means for storing proof auxiliary information which is the execution result of executing a predetermined calculation, fourth storage means for storing essential information for access qualification authentication, and storage for inspection information for access qualification authentication 5, the result of performing a predetermined operation on the authentication data held in the first storage means and the essential information for access qualification authentication stored in the fourth storage means, When the inspection means for inspecting a predetermined relationship with the inspection information of the access qualification authentication stored in the fifth storage means and the result of the inspection by the inspection means are good, the first storage A predetermined operation is performed on the authentication data held in the means, the unique information of the user stored in the second storage means, and the certification auxiliary information stored in the third storage means. To generate proof data A proof data generation means that, the proof data has provided the feature information of the access right authentication, and a proof data verification means for verifying that it is generated based on the essential information of the access right authentication.

In the present invention, in order to properly obtain access qualification, proof data, user's unique information,
The combination of auxiliary information for certification and required information for access qualification must be correct.

Information that should not be replaced, such as access fees, should be included in the required information for access qualification authentication.
It is possible to impose a penalty of denying access to fraudulent acts of replacing information.

[0044]

BEST MODE FOR CARRYING OUT THE INVENTION The present invention will be described below with reference to Examples. [Embodiment of Partial Blind Decoder] [First Embodiment] The first embodiment is a blind decoder to which the present invention is applied. FIG. 1 shows the configuration of the blind decoding device according to this embodiment. In this embodiment, as the encryption / decoding method, a modular exponentiation modulo the composite number n is used. This decoder uses two pieces of decoding information d ₁ and d ₂ in addition to the modulus n for decoding. The encryption key E and d ₁ and d ₂ are created so as to satisfy the relationship of Expression 1.

[0045]

## EQU3 ## Ed ₁ d ₂ ≡1 mod φ (n) (1) where φ (n) is the Euler number of n.

The ciphertext C for the data M is generated by the equation 2.

[0047]

Equation 4] User ^{C = M E mod n (2} ) blind decoding apparatus of this embodiment, in possession ciphertext C and modulus n, the encryption key E and the second decryption information d _2.
When entrusting the decoding of C to the present embodiment, the user applies a blind effect to C to generate C ′, and inputs C ′ and d ₂ into the decoder of the present embodiment. Then, the output R from the decoder of this embodiment is received, the blind effect of R is removed, and the decoding result is obtained.

The specific procedure for the user to use the decoder of this embodiment is as follows. 1. The user generates a random number r within the range of 1 <r <n. 2. The user calculates Equation 3 and adds the blind effect to the ciphertext C.

[0049]

## EQU5 ## C '= r ^E C mod n (3) 3. The user sends C ′ and d ₂ to the blind decoder of this embodiment and receives the output R from the blind decoder. 4. The user calculates Equation 4 and obtains the decoding result M ′.

[0050]

(6) M ′ = r ⁻¹ R mod n (4) The blind decoder of this embodiment is composed of the following subunits. Input unit 11: a ciphertext C ′ with a blind effect,
The second decryption information d ₂ is input. Output unit 12: Outputs the decoding result R. Modulus storage unit 13: stores the modulus n. First decryption information storage unit 14: Stores the first decryption information d ₁ . Decoding unit 15: Calculates a decoding result R from n, C ′, d ₁ and d ₂ .

The processing procedure of the blind decoder of this embodiment is as follows. 1. The ciphertext C ′ with the blind effect and the second decryption key d ₂ are received from the user via the input unit 11 and sent to the decryption unit 15. 2. The decryption unit 15 retrieves the modulus n from the modulus storage unit 13 and the first decryption information d ₁ from the first decryption information storage unit 14 to calculate Equation 5.

[0052]

## ^EQU7 ## R = C ' ^d1d2 mod n (5) 3. R is output via the output unit 12.

If the combination of the ciphertext C and the second decryption information d ₂ is correct, equation 6 shows that the decryption is correct.

[0054]

[Equation 8] Also, if information different from the second decoding information d ₂ is sent to the blind decoder of this embodiment, the user cannot obtain a correct decoding result. Therefore, the second decryption information d ₂
If the decryption fee and the like are included in, it is possible to prevent a false decryption fee from being sent to the decoder.

However, the second decryption information d₂Is not a prime number
In some cases, problems will occur. d₂But d ₂= A * b and factor
If it can be solved, C, d₂Instead of sending
C^aThe output of the decoder does not change even if mod n, b is sent.
Yes. Therefore, d₂Instead of
It is possible to send and obtain the correct decoding result.

To prevent this, the combination of E, d ₁ and d ₂ should be determined so that d ₂ becomes a prime number.

Even if d ₂ is a prime number, C ^d2 modn, 1 is sent to the decoder instead of C and d ₂ .
You can get the same output. In order to prevent this, the decoder may have means for confirming that the transmitted second decoding information is not 1, and configured to perform decoding only when the second decoding information is not 1.

Even if d ₂ is not a prime number, it becomes a value with redundancy such as repetition of a specific value.
The combination of E, d ₁ and d ₂ may be determined, and the decoder may be provided with means for confirming the redundancy of the second information sent. If the nontrivial divisor of d ₂ is sufficiently low that the decoder has the redundancy known, then this method also gives the second
The attack that sends the divisor to the decoder instead of the information of

It is also possible to add a hash function calculation unit for calculating the one-way hash function V (x) to the blind decoder of this embodiment and calculate Equation 7 instead of Equation 5.

[0060]

R = C ′ ^{d1V (d2)} mod n (7) It is extremely difficult to calculate different x and y that satisfy h (x) = h (y), unlike the one-way hash function. It is a function with properties. As an example of the one-way hash function, RSA Data Security Inc. MD2, MD4, MD5 by the US Federal Government SHS (Secure Hash Standard)
It has been known.

In this case, the encryption key E and d ₁ and d ₂ are made so as to satisfy the relation of the equation (8).

[0062]

[Equation 10] Ed ₁ V (d ₂ ) ≡1 mod φ (n) (8) With this configuration, V (x) can be kept secret from the user, and the safety is improved. To do. Also,
A large d ₂ can also be used depending on the modulus.

The decryption fee information is embedded in the second decryption information in the present embodiment, the decoder is configured to accumulate the transmitted decryption fee information, and the entrustor is based on the later accumulated fee information. If the decryption fee is charged to (1), it is possible to make a consignment decryption system capable of charging a genuine decryption fee. This also applies to the second embodiment described later.

The expiration date information of the encrypted data is embedded in the second decryption information in the present embodiment, and the decryptor is
Create a consignment decryption system that can limit the expiration date of data by configuring it so that it has a built-in clock and compares the sent expiration date with the time of the internal clock to determine whether or not decryption is possible. You can This also applies to the second embodiment.

If attribute information of encrypted data is embedded in the second decryption information in the present embodiment and the decryption element is configured to store the attribute information sent, it is possible to perform statistical processing and auditing later. It is possible to create a consignment decryption system that can store data that can be used for. This also applies to the second embodiment.

[Second Embodiment] The second embodiment is also a blind decoder to which the present invention is applied. The configuration of the blind decoder of this embodiment is shown in FIG.

In the present embodiment, the modular exponentiation modulo the composite number n is used as the encryption / decoding method. This decoder uses two pieces of decoding information d ₁ and d ₂ in addition to the modulus n for decoding. The decryption information d ₁ is the Euler number of the modulus n, and the decryption information d ₂ is the encryption key E. Also, the encryption key E is created so as to be coprime to d.

The ciphertext C for the data M is the above-mentioned equation 2
Generated by.

The users of the blind decoder of this embodiment are
It has a ciphertext C, a modulus n, and an encryption key E (which is also the second decryption information d ₂ ). When entrusting the decoding of C to this embodiment, the user applies a blind effect to C to generate C ′, and inputs C ′ and E to this embodiment. Then, the output R from the present embodiment is received, the blind effect of R is removed, and the decoding result is obtained.

The specific procedure for the user to use this embodiment is the same as that of the first embodiment.

The blind decoder of this embodiment is composed of the following subunits. Input unit 11: Inputs a ciphertext C ′ having a blind effect and an encryption key E. Output part 1
2: Output the decoding result R. Modulus storage unit 13: stores the modulus n. Euler number storage unit 16: Euler number φ (n)
Memorize Reciprocal number generation unit 17: Inputs a modulus and an integer and calculates the reciprocal of the integer in the modulus. Decoding section 1
5: The decoding result R is calculated from the calculation result of the n, C ′ and the reciprocal number generation unit 17.

The processing procedure of the blind decoder of this embodiment is as follows. 1. The ciphertext C ′ with the blind effect and the second decryption information d ₂ are received from the user via the input unit 11, C ′ is sent to the decryption unit 15, and d ₂ is sent to the reciprocal number generation unit 17. 2. Reciprocal generator 17 from the Euler number storage unit 16 fetches the Euler number phi (n), Euler number phi (n) is the inverse d ₂ ^-1 of d ₂ calculated modulo decoder 1 and the results
Send to 5. 3. The decoding unit 15 retrieves the modulus n from the modulus storage unit 13 and calculates Equation 9.

[0073]

[Equation 11] 4. R is output via the output unit 12.

If the combination of the ciphertext C and the second decryption information d ₂ is correct, it can be seen from Expression 10 that the decryption is correct.

[0075]

[Equation 12] Also, if information different from the second decoding information is sent to the blind decoder of this embodiment, the user cannot obtain the correct decoding result. Therefore, by including the decoding fee and the like in the second decoding information, it is possible to prevent a false decoding fee from being sent to the decoder.

The blind decoder of the present embodiment is provided with a hash function calculation unit for calculating the one-way hash function V (x), and the reciprocal number generation unit 16 calculates the reciprocal of d ₂ instead of V ( d ₂₎ to calculate the inverse V (d ₂₎ ^-1 of the decoding section 1
Equation 11 may be calculated in step 5.

[0077]

[Equation 13] In this case, the encryption key E becomes V (d ₂ ). When configured in this way, a larger d ₂ can be used depending on the modulus.

Further, instead of storing the Euler number of the modulus n, the prime factor of the modulus n may be stored and the Euler number may be calculated at the time of decoding.

Further, instead of storing the Euler number of the modulus n, the prime factors of the modulus n are stored, and the modular exponentiation is performed for each individual prime factor using the prime factor as a modulus. The remainder theorem may be used to obtain the result when n is a modulus.

Specifically, when n is the product of two prime numbers p and q,

[0081]

[Equation 14] The same effect can be obtained by calculating R and calculating R from R ₁ and R ₂ using the Chinese Remainder Theorem.

[Example of access qualification authentication] Third, fourth,
The fifth and sixth embodiments are access qualification authentication devices to which the present invention is applied. FIG. 3 shows a rough structure of the third, fourth, fifth and sixth embodiments.

In FIG. 3, the access qualification authentication apparatus of these embodiments has a certification apparatus 100 and a verification apparatus 200. The proving apparatus 200 uses the access ticket generated by the access ticket generating apparatus 300 to generate proof data. The verification device 100 is a device associated with a service or digital data whose access qualification is authenticated, and verifies that a user of the service or digital data has a valid access right. The certification device 200 is a device held by a user of a service or digital data,
The verification device 100 proves that the user has a valid access right.

To authenticate the access qualification, the verification device 100 sends the authentication data to the certification device 200, and the certification device 200
Then, the proof data corresponding to the authentication data is generated and is sent to the verification data. In the third, fourth, fifth and sixth embodiments, the authentication data sent by the verification device 100 is some data encrypted, and the verification device 200
Generates authentication data by decrypting the authentication data. The verification device 100 verifies the proof data by inspecting whether the proof data sent from the proof device 200 is a correct decryption of the authentication data.

To generate the proof data, four pieces of authentication data, user-specific information, access ticket, and essential information for access qualification authentication are required.

The user-specific information is digital data that differs for each user of the service and digital data, and is stored in the certification device 200 in a form that cannot be accessed by the user.

The access ticket is digital data generated from the characteristic information of the access qualification authentication and the user unique information.

The essential information for the access qualification authentication is data held by the verification device 100 and is sent to the certification device 200 together with the authentication data.

In the third, fourth, fifth and sixth embodiments, the authentication data can be decrypted only when the characteristic information for access qualification authentication and the essential information for access qualification authentication are available. Therefore, an eavesdropper of the communication between the verification device 100 and the proving device 200 receives the authentication data together with the proving device 20.
If illicit acts such as replacing the required information for access qualification authentication sent to 0, correct proof data cannot be obtained. As a result, it is possible to prevent the essential information for access qualification authentication from being replaced.

Information on the service or digital data usage fee is embedded in the essential information for access qualification authentication in the third, fourth, fifth and sixth embodiments, and the sent usage fee information is
The certification device 20 so that the data is stored in a form that cannot be changed by the user.
If 0 is configured and the usage fee is charged to the user based on the charge information accumulated later, an access qualification authentication system capable of charging a genuine usage fee can be created.

The expiration date information of the service and digital data is embedded in the essential information of the access qualification authentication in the third, fourth, fifth and sixth embodiments, and the certification device 200 has a built-in clock and the expiration date sent. If it is configured to determine whether or not to generate the proving apparatus 200 by comparing it with the time of the built-in clock, it is possible to create an access qualification authentication system that can limit the expiration date of services and digital data.

The attribute information of services and digital data is embedded in the essential information for access qualification authentication in the third, fourth, fifth and sixth embodiments, and the transmitted attribute information is stored in a form that the user cannot change. By configuring the proving apparatus 200, it is possible to create an access qualification authentication system capable of accumulating data that can be used in subsequent statistical processing and auditing.

[Third Embodiment] FIG. 4 shows a method of constructing a proof device according to a third embodiment, and FIG. 8 shows a method of constructing a verification device. The operation of the proving apparatus of this embodiment is shown in FIG. 10, and the operation of the verification apparatus is shown in FIG.

As shown in FIG. 4, the proving apparatus 200 of this embodiment has a reception data storage unit 202, an access ticket storage unit 203, a user unique information storage unit 204, an index generation unit 205, a first calculation unit 206, and a first calculation unit 206. It is configured to include a two-operation unit 207 and a proof data generation unit 208.

Further, the verification apparatus 100 of this embodiment is similar to that of FIG.
As shown in, the verification means 101, the access ticket public key storage unit 103, the random number generation unit 104, and the random number storage unit 10
5, a random number effect removing unit 106, a random number effect applying unit 107, an authentication raw data storage unit 108, an essential information storage unit 109, a received data storage unit 110, and a verification calculation unit 111.

In the first embodiment of the present invention, the access qualification authentication characteristic information D, the public information E and n corresponding to D, and the access qualification authentication essential information I are defined as follows.

N is an RSA modulus, that is, a product of two sufficiently large prime numbers p and q, and satisfies the expression 12.

[0098]

N = pq (12) φ (n) is the Euler number of n and is calculated by equation 13.

[0099]

Φ (n) = (p−1) (q−1) (13) The characteristic information D of the access qualification authentication is R under the modulus n.
It is an SA private key and satisfies Expression 14.

[0100]

Gcd (D, φ (n)) = 1 (14) where gcd (x, y) represents the greatest common divisor of the two numbers x and y. Further, I is a prime number that satisfies Expression 15.

[0101]

(18) gcd (I, φ (n)) = 1 (15) The public information E is generated so as to satisfy Expression 16.

[0102]

EID mod φ (n) = 1 (16) D is called an access ticket secret key, and E is called an access ticket public key. The access ticket t is generated based on the following Expression 17 using the access ticket secret key D, the unique information e of the user, and the modulus n.

[0103]

(20) t = DF (e, n) (17) The unique information e of the user is a number different for each user and is used to identify the user. The function F is a function whose function values are less likely to collide, and for example, the one-way hash function h
Can be used to determine as in Equation 18 or Equation 19.

[0104]

F (x, y) = h (x | y) (18) F (x, y, z, u, w) = h (x | y | z | u | w) (19) where , X | y represents a concatenation of bits of x and y.

In the numbers appearing in the above description, t,
E, n, I can be published, and the remaining D, e, p, q,
φ (n) and the function F need to be secret except for those who have the right to create a ticket.

Further, hereinafter, the encrypted data K will be referred to as verification data, and the data R generated by the proving apparatus 200 for proving will be referred to as proving data. In addition, the certification device 200
The data received from the verification device 100 in order to generate the proof data is referred to as authentication data.

The operation of this embodiment will be described below. 1. The verification device 100 is activated by the user accessing digital content that requires authentication by the access qualification authentication device. When the verification device 100 is configured as a part of an application program that operates on the user's PC or workstation, the user activates the application program by a normal method using a pointing device such as a keyboard or a mouse. When the execution of the application program reaches the program configuring the verification device 100, the verification device 100 is activated.

Another PC or workstation (referred to as a server) whose verification device 100 is connected to the network.
In the above configuration, the user activates the communication program on his / her PC or workstation, and the communication program requests the server to establish communication according to a predetermined procedure. 100 is activated. For example, if the user's communication program follows a procedure called TCP / IP (Transmission Control Protocol / Internet Protocol) when communicating with the server, the verification device is associated with a specific port of the server in advance, and By setting the communication program to specify the port and request a TCP connection request from the server, a daemon (inetd) on the server can activate the verification device in response to the TCP connection request. . Such an implementation method is widely used in networks such as the Internet.

The verification device 100 may be a dedicated device. For example, the verification device 100 can be configured as a program burned in a ROM in an IC card reader / writer, and the certification device 200 can be a program installed in a microcontroller of an IC card. In this case, the verification device 100 is activated by the user inserting the IC card into the reader / writer.

2. The verification device 100 uses the authentication data C
And the modulus n stored in the access ticket public key storage unit 103 and the essential information I for access qualification authentication stored in the essential information storage unit 109,
It is written in the received data storage unit 202 therein. The authentication raw data storage unit 108 stores C ′ as the authentication raw data. Here, when the verification data is set to an appropriate data K, the authentication raw data C ′ is expressed by the formula 2 with respect to the data K.
Satisfies 0.

[0111]

[Equation 22] C ′ = K ^E mod n (20) For the authentication data C, the verification device 100 causes the random number generation unit 104 to generate a random number r, and r and E acquired from the access ticket public key storage unit 103. , N and C ′ acquired from the authentication raw data storage unit 108, the random number effect imparting unit 107 performs the calculation of Expression 21. The generated authentication data C is written in the received data storage unit 202 in the certification device 200. Also, the generated random number r
Are stored in the random number storage unit 105.

[0112]

C = r ^E C ′ mod n (21) In this way, the random number effect is added to the authentication data, and the random number effect is removed when verifying the proof data returned by the certifying device 200. Thus, blindness can be added to the authentication data. That is, the verification device 1
The authentication raw data itself or the decryption result can be hidden from an interceptor of the communication between 00 and the proof device 200 or the proof device itself. It also has the role of making the replay attack impossible by changing the random number used for the random number effect each time. This also applies to the following embodiments. Further, the verification device is configured not to hold the data K in the verification device, but instead holds only the encryption result C ′, and the random number effect is removed from the proof data sent from the proof device 200. If the verification device 100 is provided with a means for verifying that the data K and the K match, the risk of the data K leaking from the verification device 100 can be avoided.

3. Index generation unit 20 in proof device 200
5 acquires the user's unique information e stored in the user unique information storage unit 204 and the modulus n stored in the received data storage unit 202, and executes the calculation of Expression 22.

[0114]

(24) F (e, n) (22)

4. First operation unit 20 in proof device 200
6 obtains the essential information I and the modulus n stored in the received data storage unit 202, and uses this and the data generated by the exponent generation unit 205 to execute the calculation of Equation 23 to obtain R ′.
To get

[0116]

R ′ = C ^{IF (e, n)} mod n (23)

5. Second operation unit 20 in proof device 200
7 acquires the access ticket t stored in the access ticket storage unit 203, calculates Expression 24,
Get R ''.

[0118]

[Equation 26] R ″ = C ^It mod n (24)

6. The proof data generation unit 208 in the proof device 200 obtains R ′ and R ″ from the first and second calculation units 206 and 207, calculates equation 25, and obtains R.

[0120]

R = R′R ″ mod n (25)

7. The proving device 200 verifies R by the verification device 10
0 is written in the received data storage unit 110. 8. The random number effect removal unit 106 in the verification device 100 extracts the previously generated random number r from the random number storage unit 105,
Formula 26 is calculated.

[0122]

K ′ = r ⁻¹ R mod n (26) 9. Only when the combination of the access ticket t, the unique information e of the user, and the essential information I used in the proving apparatus 200 is correct, K ′ obtained as a result of the calculation matches the verification data K, and the verification is performed correctly. . 10. The calculated K ′ is delivered to the verification means 101 in the verification device 100, but the execution means 102 uses K ′ = K.
Regular processing is executed only when is satisfied.

If the above procedure is performed correctly, it can be seen from Equation 27 that K and K ′ match.

[0124]

[Equation 29] Further, if the interceptor of the communication between the verification device 100 and the certification device 200 replaces the essential information I for access qualification authentication with I ′, K and K ′ do not match, so that the service or digital data cannot be accessed. .

However, if the required information I for access qualification authentication is not a prime number, a problem occurs. I is I = a * b
If it can be factored into, the output of the decoder does not change even if C ^a mod n, b is sent instead of sending C and I to the decoder. Therefore, instead of the essential information of I, the essential information of b can be sent for normal access. To prevent this, the combination of E, D, and I may be determined so that I becomes a prime number.

Even if I is a prime number, C,
Instead of sending I, send C ^I modn, 1, it is possible to obtain the same output. To prevent this, the proof device 20
0 has means for confirming that the essential information sent is not 1, and may be configured to calculate the modular exponentiation of C only when the essential information is not 1.

Further, even if I is not a prime number, it becomes a value with redundancy such as repetition of a specific value.
The combination of E, D and I is decided, and the proof device 200
In addition, a means for confirming the redundancy of the sent essential information may be provided. If the non-trivial divisor of I is less likely to have the redundancy known to the proving device 200, this method also avoids the attack of sending that divisor instead of the essential information to the decoder.

In this embodiment, if the user unique information storage unit 204, the index generation unit 205, and the first operation unit 206 are configured inside an IC card or the like that cannot be accessed or modified by the user, the user unique information can be stored. Leakage and index generation unit 20
5. It is possible to protect the present embodiment from fraud caused by modification of the first calculation unit 206.

The proof device 200 of this embodiment is provided with an arithmetic means for arithmetically operating the one-way hash function V (x, y),
Expression 28 may be calculated instead of Expression 23, and Expression 29 may be calculated instead of Expression 24.

[0130]

R ′ = C ^{V (I, n) F (e, n)} mod n (28) R ′ = C ^{V (I, n) t} mod n (29) In this case, encryption key E and access qualification The essential information I and the access qualification characteristic information D are created so as to satisfy the relationship of Expression 30.

[0131]

[Equation 31] EV (I, n) D≡1 mod φ (n) (30) With this structure, essential information larger than the modulus can be used.

The proof device 200 of this embodiment is constructed so that the characteristic information of the access qualification is calculated from the access ticket and the output of the exponent generator 205, and the result is used as a power remainder. Even if it does, the same effect as this embodiment can be obtained.

Hereinafter, in the verification device 100, K and K '
Here are some examples of how to verify that they are the same. These examples are similarly applicable to the fourth, fifth and sixth embodiments.

[1] Configuration example for directly comparing the verification data with the decryption result The verification means 101 stores the verification data K in advance.
The comparison unit in the verification means 101 uses the verification data K and
Directly compare the authentication data with the decrypted data K ',
Regular processing is executed only when K ′ = K is satisfied, and error processing such as stopping the processing is executed when K ′ = K is not satisfied. This configuration example has a security weakness that the verification data K itself to be verified appears in the device. For example, when the verification device 100 is configured as a program that operates on the user's PC or workstation, it is difficult, but not always impossible, to analyze the program and steal K. When the value of K becomes known to the user, it becomes possible to configure a device that imitates the operation of the proving device 200, and unauthorized access by spoofing is possible.

[2] Configuration Example Using One-Way Function In order to improve the above-mentioned drawbacks, the verification data stored in the verification means 101 is not stored in the verification data K itself but in the above K. Data h (K) obtained by applying the one-way hash function h. From the property of the one-way hash function, from the data y stored in the proof data storage means,
It is extremely difficult to calculate x that satisfies y = h (x). The verification unit 101 has a conversion unit that returns the result of applying the one-way hash function to the input data. The comparison unit compares the output h (K ′) obtained by using the data K ′ obtained by decrypting the authentication data as the input of the hash function with the stored data (= h (K)). In this method example, the verification data K does not appear in the program, and it is extremely difficult to calculate K from h (K) stored in the proof data storage means. Is safer than the example. However,
The comparison unit is configured as a conditional statement in the program, and if the verification device is a program and has a configuration that is easy to analyze and tamper with, the program can be tampered with so as to skip the conditional statement. However, it still has a weak point.

[3] Decrypted value is decryption key for decrypting specific data Configuration example Data stored for verification is encrypted data, and authentication data is decrypted. The processed data K ′ is a key for decrypting this encrypted data. The verification means 101 uses the value of the data K ′ as a decryption key of the encryption used to encrypt the data stored for verification, and as a result, the encrypted data can be decrypted. The program can be executed only when Even with this configuration, since the decryption key itself does not appear in the verification device 100, the degree of security is high.

[4] Configuration example verifying device 100 for verifying that the decrypted value satisfies a specific redundancy The verification device 10 has a redundancy verifying means.
1 sends the value of the data K ′ obtained by decrypting the authentication data to the redundancy verification means. Only when the redundancy verification means confirms that the data satisfies the specific redundancy, the program can be executed. Examples of redundancy are that the decoded data repeats a certain pattern, that the data at a certain position meets a certain condition, or that the data is meaningful as a certain language, etc. Can be given.

[5] Configuration Example of Encrypting Program Code itself The data obtained by encrypting a part or all of the code of the program held by the verification device 100 is held in the authentication data storage means as the authentication data. That is, the data K ′ obtained by decrypting the authentication data becomes a part or all of the code of the program. The executing means embeds the data K'in a predetermined position in the program, and then executes the embedded program. The program can be executed only when the proving device returns correct data, that is, when K'correctly decrypts the code. After generating a file that embeds the decrypted code in the original program, you can start the file, but you can embed the decrypted code in the program in memory while the program is expanded in memory. The way to start later is
It is desirable for safety. In this configuration example, some or all of the code essential for executing the program is encrypted, so that the program to be executed is configured as an application program that operates on the user's PC or workstation. It is possible to prevent illegal execution even if the security is relatively low.

[6] Configuration example in which the decrypted value is the decryption key of the program The verification device 100 holds data obtained by encrypting a part or all of the code of the program, and the decrypted data of the authentication data. K'is a decryption key necessary for decrypting the encrypted program code. According to this configuration, regardless of the code size to be encrypted,
The size of the data K ′ can be suppressed to a certain small value, and the communication overhead can be reduced. The verification means 101 uses the data K ′ to decrypt the stored encrypted program code. Further, the decrypted code is embedded in a predetermined position in the program, and then the embedded program is executed. The program can be executed only when the proving device returns correct data, that is, when the code is correctly decoded by K '.

[Fourth Embodiment] The fourth embodiment is different from the third embodiment in the calculation of the access ticket t. FIG. 8 shows a method of constructing the verification apparatus of this embodiment, and FIG. 5 shows a method of constructing the proving apparatus. In addition, the operation of the verification device of the present embodiment is shown in FIG.
3 shows the operation of the proving device in FIG. In this embodiment, the characteristic information D of access qualification authentication, the public information E, n, the properties to be satisfied by the essential information I of access qualification authentication, and the method for generating the authentication raw data C ′ and the authentication data C are as described in the first embodiment.
Is the same as. In FIG. 5, the parts corresponding to those in FIG. 4 are designated by the corresponding reference numerals.

The access ticket t of this embodiment is expressed by the formula 28
It is generated based on.

[0142]

[Equation 32]       t = D / F (e, n) mod φ (n) (31) The operation of this embodiment will be described below.

1. The verification device 100 is activated by the user's access.

As a method of realizing the verification apparatus 100, an application program operating on a user's PC or workstation, a server program on a server connected to the user's PC or workstation via a network, or an IC card reader. The fact that any dedicated device such as a lighter is possible is no different from the case of the third embodiment. This is the same in the following examples.

2. The verification device 100 uses the authentication data C
, The modulus n stored in the access ticket public key storage unit 103, and the essential information I for the access qualification authentication stored in the essential information storage unit 109,
The data is written in the received data storage unit 202 which is 0.

3. Index generation unit 20 in proof device 200
Reference numeral 5 denotes the user unique information e stored in the user unique information storage unit 204 and the access ticket public key storage unit 2
The modulus n stored in 03 is obtained, and the calculation of Expression 32 is executed.

[0147]

F (e, n) (32)

4. Proving operation unit 2 in proving apparatus 200
09 acquires the essential information I and the modulus n stored in the received data storage unit 202, and using this and the data generated by the exponent generation unit 205, executes the calculation of Expression 33 to obtain R ′. To get

[0149]

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

5. The proof data generation unit 208 in the proof device 200 obtains the access ticket t stored in the access ticket storage unit 203 and the modulus n stored in the received data storage unit 202, and outputs R from the proof operation unit 209. 'Is obtained and Eq. 34 is calculated to obtain R.

[0151]

(35) R = R ′ ^t mod n (34)

6. The proving apparatus 200 uses the R as the verification apparatus 1
00 in the received data storage unit 110. 7. The random number effect removal unit 106 in the verification device 100 extracts the previously generated random number r from the random number storage unit 105,
Formula 35 is calculated.

[0153]

(36) K '= r ^-1 R mod n (35)

8. Only when the combination of the access ticket t, the unique information e of the user, and the essential information I used in the proving apparatus 200 is correct, K ′ obtained as a result of the calculation matches the verification data K, and the verification is performed correctly. . If the above procedure is done correctly, Equation 36
Thus, it can be seen that K and K ′ match.

[0155]

[Equation 37] Further, if the interceptor of the communication between the verification device 100 and the authentication device 200 replaces the essential information I for the access qualification authentication with I ′, K and K ′ do not match, so that the service and the digital data cannot be accessed. .

However, if the required information I for access qualification authentication is not a prime number, a problem occurs. I is I = a * b
If it can be factored into, the output of the decoder does not change even if C ^a mod n, b is sent instead of sending C and I to the decoder. Therefore, instead of the essential information of I, the essential information of b can be sent for normal access. To prevent this, the combination of E, D, and I may be determined so that I becomes a prime number.

Even if I is a prime number, C,
Instead of sending I, send C ^I modn, 1, it is possible to obtain the same output. To prevent this, the proof device 20
0 has means for confirming that the essential information sent is not 1, and may be configured to calculate the modular exponentiation of C only when the essential information is not 1.

Further, even if I is not a prime number, it becomes a value with redundancy such as repetition of a specific value.
The combination of E, D and I is decided, and the proof device 200
In addition, a means for confirming the redundancy of the sent essential information may be provided. If the nontrivial divisor of I is sufficiently unlikely to have the redundancy known to the proving device 200, this method also avoids the attack of sending the divisor instead of the essential information to the decoder.

As a method of comparing K ′ with the verification data K, the same method as in the third embodiment can be used.

In the present embodiment, if the user unique information storage unit 204, the index generation unit 205, and the proof operation unit 209 are configured inside an IC card or the like that cannot be accessed or modified by the user, the user unique information 204 will be stored. This embodiment can be protected from leakage and fraud caused by modification of the index generation unit 205 and the proof operation unit 209.

The proof device 200 of the present embodiment is provided with a calculation means for calculating the one-way hash function V (x, y),
Expression 37 may be calculated instead of Expression 33.

[0162]

R ′ = C ^{V (I, n) F (e, n)} mod n (37) In this case, the encryption key E, the access qualification essential information I, and the access qualification feature information D are It will be made to satisfy the relationship.

[0163]

[Equation 39] EV (I, n) D≡1 mod φ (n) (38) With this configuration, V (x, y) can be kept secret from the user, and the security can be improved. Is improved. Also, depending on the modulus, large required information can be used.

The proving apparatus 200 of this embodiment is configured to calculate the access qualification characteristic information from the access ticket and the output of the exponent generator 205, and use the result to multiplicand the authentication data. Even if it does, the same effect as this embodiment can be obtained.

[Fifth Embodiment] In the third and fourth embodiments, the validity of the essential information of the access qualification is not known to the proving device 200, whereas in the fifth embodiment the access qualification is used. The authenticity of the essential information is verified by the proving device 200, and if it is not authentic, the proof data is not generated. FIG. 9 shows a method of configuring the verification device 100 according to the present embodiment.
A method of constructing the proving apparatus 200 is shown in FIG. The operation of the verification device 100 of this embodiment is shown in FIG.
The operation of is shown in FIG.

The characteristics to be satisfied by the access qualification authentication characteristic information D, the RSA modulus n, and the Euler number φ (n) of n and the method for generating the authentication raw data C ′ and the authentication data C according to the present embodiment. Is the same as in the third embodiment. The public information E in this embodiment is generated so as to satisfy Expression 35.

[0167]

ED mod φ (n) = 1 (39) The access ticket t uses the access ticket secret key D, the user's unique information e, the modulus n, and the function F, as in the first embodiment, using the following formula. 40 based on 40.

[0168]

T = D−F (e, n) (40)

The operation of this embodiment will be described below. 1. The verification device 1 is accessed by the user.
00 is started.

2. The inspection information generation unit 112 in the verification device 100 acquires the authentication data C and the essential information I for the access qualification authentication stored in the essential information storage unit 109, executes the calculation of Expression 41, and performs the inspection information. Generate M.

[0171]

M = V (C, I) (41) The function V is a function having the same property as the function F, and must be secret except for the verification device 100 and the proof device 200.

3. The verification device 100 uses the certification data C
And the modulo n stored in the access ticket public key storage unit 103, the essential information I for access qualification authentication and the inspection information M stored in the essential information storage unit 109, the received data storage in the certification device 200. Write in the section 202.

4. The essential information verification unit 210 in the proving apparatus 200 acquires the authentication data C, the essential information I, and the inspection information M written in the received data storage unit 202, and verifies whether or not Expression 42 is satisfied.

[0174]

(43) M = V (C, I) (42) If Expression 42 is satisfied, the following calculation is continued.

5. Index generation unit 20 in proof device 200
5 acquires the user's unique information e stored in the user's unique information storage unit 204 and the modulus n stored in the received data storage unit 202, and executes the calculation of Expression 43.

[0176]

(44) F (e, n) (43)

6. First operation unit 206 in proof device 200
Uses the authentication data C and the modulus n written in the received data storage unit 202, and the data generated by the exponent generation unit 205 to execute the calculation of Expression 44 to obtain R ′.

[0178]

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

7. Second operation unit 20 in proof device 200
7 obtains the access ticket t stored in the access ticket storage unit 207, the authentication data C and the modulus n stored in the received data storage unit 202, calculates Equation 45, and obtains R ″. obtain.

[0180]

R ″ = C ^t mod n (45)

8. The proof data generation unit 208 in the proof device 200 obtains R ′ and R ″ from the first and second operation units 206 and 207, calculates equation 46, and obtains R.

[0182]

R = R'R '' mod n (46)

9. The proving device 200 verifies R by the verification device 10
0 is written in the received data storage unit 110. 10. The random effect removal unit 106 in the verification device 100
The previously generated random number r is extracted from the random number storage unit 105, and the calculation of Expression 47 is performed.

[0184]

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

11. Only when the combination of the access ticket t, the unique information e of the user, and the essential information I used in the proving apparatus 200 is correct, K ′ obtained as a result of the calculation matches the verification data K, and the verification is performed correctly. .

If the above procedure is carried out correctly, it can be seen from equation 48 that K and K ′ match.

[0187]

[Equation 49] When the interceptor of the communication between the verification device 100 and the authentication device 200 replaces the essential information I for access qualification authentication with I ′, the check at 4 is not passed, and the verification device 200 stops the generation of the proof data. Notifies the verification device 100 of the cancellation. The notification means may be, for example, a method of writing the cancellation code in the received data storage unit 110, or a predetermined time required to generate the proof data may be set in advance, and writing to the received data storage unit 110 even if the required time is exceeded. If it is not done, there is a method to stop it.

As a method of comparing K ′ with the verification data K, the same method as in the third embodiment can be used.

In the present embodiment, the user unique information storage unit 204, the essential information verification unit 210, the index generation unit 205, and the first calculation unit 206 may be configured inside an IC card or the like that cannot be accessed or modified by the user. For example, the present embodiment can be protected from leakage of user-specific information and fraud caused by modification of the essential information verification unit 210, the index generation unit 205, and the first calculation unit 206.

[Sixth Embodiment] FIG. 8 shows a method of constructing a verification apparatus 100 according to a sixth embodiment, and FIG. 7 shows a method of constructing a certification apparatus 200. The operation of the verification device 100 of this embodiment is shown in FIG. 17, and the operation of the proving device 200 is shown in FIG. In the fourth embodiment of the present invention, public information n and n
The property to be satisfied by the Euler number φ (n) of is similar to that of the first embodiment. The required information I for the access qualification authentication is the formula 49
Is an integer that satisfies.

[0191]

Gcd (I, φ (n)) = 1 (49) Further, the access ticket t uses the Euler number φ (n), the user's unique information e, the modulus n, and the function F, and the following formula 5
It is generated based on 0.

[0192]

T = φ (n) −F (e, n) (50)

The operation of this embodiment will be described below. 1. The verification device 1 is accessed by the user.
00 is started.

2. The verification device 100 uses the authentication data C
, The modulus n stored in the access ticket public key storage unit 103, and the essential information I for the access qualification authentication stored in the essential information storage unit 109,
The data is written in the received data storage unit 202 which is 0. The authentication raw data storage unit 108 stores C ′ as the authentication raw data. Here, the verification data is an appropriate data K
Then, the authentication raw data C ′ satisfies the equation 51 for the data K.

[0195]

C ′ = K ^I mod n (51) For the authentication data C, the verification device 100 generates a random number r in the random number generation unit 104, and r and n acquired from the access ticket public key storage unit 103. And the essential information storage unit 10
9 and I ′ obtained from the authentication raw data storage unit 108, the random number effect imparting unit 107 uses Equation 52
It is generated by performing the calculation of. The generated authentication data C is written in the received data storage unit 202 in the certification device 200. The generated random number r is stored in the random number storage unit 1
It is stored in 05.

[0196]

C = r ^I C ′ mod n (52)

3. Index generation unit 20 in proof device 200
5 acquires the user's unique information e stored in the user unique information storage unit 204 and the modulus n stored in the received data storage unit 202, and executes the calculation of Expression 53.

[0198]

F (e, n) (53)

4. Proving operation unit 2 in proving apparatus 200
09 acquires the essential information I stored in the received data storage unit 202 and the access ticket t stored in the access ticket storage unit 203, and uses this and the data generated by the index generation unit 205. Then, the calculation of Expression 54 is performed to obtain, and D that satisfies Expression 55 is calculated.

[0200]

Ψ = t + F (e, n) (54) DI ≡ 1 mod ψ (55)

5. The proof data generation unit 208 in the proof device 200 obtains D from the proof operation unit 209, obtains C and n from the received data storage unit 202, and calculates Equation 56 to obtain R.

[0202]

R = C ^D mod n (56)

6. The random number effect removal unit 106 in the verification device 100 uses the random number r generated in the random number storage unit 105 first.
Is taken out and the calculation of Expression 57 is performed.

[0204]

K '= r ^-1 R mod n (57)

7. Only when the combination of the access ticket t, the unique information e of the user, and the essential information I used in the proving apparatus 200 is correct, K ′ obtained as a result of the calculation matches the verification data K, and the verification is performed correctly. .

If the above procedure is performed correctly, it can be seen from equation 58 that K and K'match.

[0207]

Equation 58] ^{K'≡r -1 R ≡r -1 C D ≡r} -1 (r I C ') D ≡r -1 (r I K I) D ≡r -1 rK ( because phi (n) = T + F (e, n)) ≡K mod n (58) In addition, when the interceptor of the communication between the verification device 100 and the authentication device 200 replaces the essential information I of the access qualification authentication with I ′,

[0208]

[Equation 59] Since K and K'do not match, services and digital data cannot be accessed. K'and verification data K
The same method as in Example 3 can be used for the comparison method with.

In this embodiment, the user unique information storage unit 204, the index generation unit 205, the proof operation unit 209, and the proof data generation unit 208 may be configured inside an IC card or the like that cannot be accessed or modified by the user. For example, this embodiment can be protected from leakage of user-specific information and fraud caused by modification of the index generation unit 205 and the proof operation unit 209.

The proof device 200 of the present embodiment is provided with a calculation means for calculating the one-way hash function V (x, y),
Expression 59 may be calculated instead of Expression 55.

[0211]

[Equation 60] DV (I, n) ≡1 mod (59)
In this case, when the verification data is the appropriate data K, the authentication raw data C ′ is created so as to satisfy the equation 54 for the data K.

[0212]

C ′ = K ^{V (I, n)} mod n (60)
With this configuration, essential information larger than the modulus can be used.

[0213]

As described above, according to the present invention, the first decryption information and the second decryption information are required to decrypt the encrypted data. Is
It is assumed that the decryptor is externally input (the first decryption information may be externally input or internally generated), and the encrypted data and the second decryption information may be input. If you do not enter it correctly, you will not get the correct decryption result. Therefore, if the system is configured so that information that should not be replaced, such as the data decoding fee, is input to the decoder as the second decoding information, a penalty of failure of decoding will be given to fraudulent acts of information replacement. Can be imposed.

Further, by applying the above-mentioned decryption method to the access qualification authentication, by inputting the information which should not be replaced, such as the access charge, as the above-mentioned second decryption information, it is illegal to replace the information. You can impose a penalty of access denial on actions.

[Brief description of drawings]

FIG. 1 is a block diagram showing a decoding device according to a first embodiment of the present invention.

FIG. 2 is a block diagram showing a decoding device according to a second exemplary embodiment of the present invention.

FIG. 3 is a block diagram showing an access qualification authentication device of the third to sixth embodiments of the present invention as a whole.

FIG. 4 is a block diagram showing a configuration of a certification device of an access qualification authentication device according to a third embodiment of the present invention.

FIG. 5 is a block diagram showing a configuration of a certifying device of an access qualification authenticating device according to a fourth embodiment of the present invention.

FIG. 6 is a block diagram showing a configuration of a certification device of an access qualification authentication device according to a fifth exemplary embodiment of the present invention.

FIG. 7 is a block diagram showing a configuration of a certifying device of an access qualification authenticating device according to a sixth embodiment of the present invention.

FIG. 8 is a block diagram showing a configuration of a verification device of an access qualification authentication device according to third, fourth and sixth embodiments of the present invention.

FIG. 9 is a block diagram showing a configuration of a verification device of an access qualification authentication device according to a fifth exemplary embodiment of the present invention.

FIG. 10 is a diagram for explaining the operation of the certification device of the access qualification authentication device according to the third embodiment of the present invention.

FIG. 11 is a diagram illustrating an operation of the verification device of the access qualification authentication device according to the third embodiment of the present invention.

FIG. 12 is a diagram for explaining the operation of the proving device of the access qualification authenticating device according to the fourth embodiment of the present invention.

FIG. 13 is a diagram illustrating an operation of the verification device of the access qualification authentication device according to the fourth embodiment of the present invention.

FIG. 14 is a diagram for explaining the operation of the certification device of the access qualification authentication device according to the fifth embodiment of the present invention.

FIG. 15 is a diagram illustrating an operation of the verification device of the access qualification authentication device according to the fifth embodiment of the present invention.

FIG. 16 is a diagram for explaining the operation of the certification apparatus of the access qualification authentication apparatus according to the sixth embodiment of the present invention.

FIG. 17 is a diagram illustrating an operation of the verification device of the access qualification authentication device according to the sixth embodiment of the present invention.

[Explanation of symbols]

11 Input section 12 Output section 13 modulus storage 14 First Decryption Information Storage Unit 15 Decryption unit 16 Euler number storage 17 Inverse number generator 100 Verification device 101 Verification means 102 means of execution 103 access ticket public key storage unit 104 random number generator 105 random number storage 106 Random effect remover 107 Random effect adding unit 108 Authentication data storage unit 109 essential information storage unit 110 Received data storage unit 111 Verification operation unit 112 Inspection information generator 200 Proof device 201 means for generating proof data 202 Received data storage unit 203 access ticket storage unit 204 user unique information storage unit 205 Index generator 206 First Calculation Unit 207 Second operation unit 208 Proof data generator 209 Operation unit for proof 300 access ticket generation device

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Yukishi Takeda             430 Green, Sakai, Nakai-cho, Ashigaragami-gun, Kanagawa Prefecture             Inside of Fuji Xerox Co., Ltd. (72) Inventor Taro Terao             430 Green, Sakai, Nakai-cho, Ashigaragami-gun, Kanagawa Prefecture             Inside of Fuji Xerox Co., Ltd. F term (reference) 5J104 AA16 AA18 AA22 EA04 EA19                       EA22 EA28 EA32 JA28 NA02                       NA18 NA35 NA40 NA42

Claims (9)

[Claims] 1. An apparatus for decrypting a ciphertext encrypted by the RSA method, comprising: first storage means for storing a modulus n of a power-residue; and second storage means for storing first decryption information d ₁ . It has a storage means, an arithmetic means for calculating the modular exponentiation, a means for inputting the ciphertext C, and a means for inputting the second decryption information d ₂ , and the ciphertext C and the second decryption When the information d ₂ is input, the ciphertext C is raised to the product of the first decryption information d ₁ and the second decryption information d ₂ under the modulus n, and the result is output. A decoding device characterized by: 2. The decoding device according to claim 1, further comprising means for confirming that the second decoding information is not 1, and when the second decoding information is 1, decoding processing is not performed. 3. The decoding device according to claim 1, further comprising means for confirming that the second decoding information has a predetermined redundancy, and when the second decoding information does not have the predetermined redundancy, the decoding process is not performed. 4. An apparatus for decrypting a ciphertext encrypted by the RSA method, comprising: a first storage means for storing a modulus n of a power-residue; and a second storage means for storing a _first decryption information d ₁ . It has a storage means, a calculation means for calculating the modular exponentiation, a means for inputting the ciphertext C, and a means for inputting the second decryption information d ₂ , and the ciphertext C and the second decryption When the information d ₂ is input, the ciphertext C is multiplied by a predetermined operation on the _second decryption information d ₂ and the first decryption information d ₁ under the modulus n. A decoding device characterized in that the result is output to the power of. 5. An apparatus for decrypting a ciphertext encrypted by the RSA method, wherein a first storage means for storing a modulus n of a power-of-residue and a reciprocal calculation modulo the Euler number of n are performed. A first arithmetic means; a second arithmetic means for calculating a modular exponentiation; a second storage means for storing the Euler number of n; a means for inputting a ciphertext C; and a second decryption information d ₂ Means for inputting the ciphertext C and the second decryption information d ₂ , and the second decryption information modulo the Euler number of n by the first computing means. A decryption device, which calculates the reciprocal of d ₂ , multiplies the ciphertext C by the calculation result of the first arithmetic means under the modulus n, and outputs the result. 6. The decoding device according to claim 5, further comprising a third calculating means for calculating the n Euler number instead of the second storing means for storing the n Euler number. 7. An apparatus for decrypting a ciphertext encrypted by the RSA method, comprising: first storage means for storing a modulus n of a power-residue; and second storage means for storing an Euler number of n. , N the first arithmetic means for calculating the reciprocal modulo the Euler number, the second arithmetic means for calculating the modular exponentiation, the means for inputting the ciphertext C, and the second decryption information d ₂ . Means for inputting the ciphertext C and the second decryption information d ₂ , and the first arithmetic means performs a predetermined arithmetic operation on the _second decryption information d ₂ . The reciprocal of the Euler number of n modulo the one is calculated, and the ciphertext C is raised to the power of the calculation result of the first arithmetic means under the modulo n.
A decoding device which outputs the result. 8. A storage means for storing one or more pieces of non-disclosure decryption information not disclosed to the decryptor body side, a means for inputting a ciphertext C, and 1 disclosed as significant information to the decryptor body side. Alternatively, the decryption device includes a unit for inputting a plurality of pieces of disclosure decryption information, and a unit for decrypting the ciphertext based on the nondisclosure decryption information and the disclosure decryption information. 9. A step of storing one or more pieces of non-disclosure decryption information that is not disclosed to the decryptor body side, a step of inputting a ciphertext C, and one or more that is disclosed as significant information to the decryptor body side. A decryption method comprising: a step of inputting a plurality of disclosure decryption information; and a step of decrypting the ciphertext based on the non-disclosure decryption information and the disclosure decryption information.