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

• US 6,275,936 B1
• Filed: 10/15/1998
• Issued: 08/14/2001
• Est. Priority Date: 10/17/1997
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Kakehi, Rumiko, Takeda, Koji, Terao, Taro, Kyojima, Masaki
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/173,186
• Time in Patent Office: 1,034 Days
• Field of Search: 713/161, 713/166, 713/168, 713/169, 713/170, 713/176, 713/182
• US Class Current: 713/182
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 2221/2103 Challenge-response
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A decryption method and device, an access right authentication method and apparatus for securely transmitting specific information to the decryption device while retaining blindness of data that is assigned to be decrypted. An input unit of the decryption device receives a cipher text C′ generated by providing a blind effect to a cipher text C and second decryption information d₂ from a user and transmits them to a decryption unit. The decryption unit takes a modulus n and first decryption information d₁ from a modulus storage unit and a first decryption information storage unit, respectively. The decryption unit then calculates the expression R=C′^d1d2 mod n and outputs R through an output unit. If a combination of a cipher text C and the second decryption information d₂ is correct, a correct decryption result is available.

Claims

1. A decryption device that decrypts a cipher text encrypted by RSA method, comprising:

a first storage unit that stores a modulus n of a modulus exponentiation operation;

a second storage unit that stores first decryption information d₁;

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs second decryption information d₂; and

an operation unit that performs the modulus exponentiation operation in which C is raised to a power, a product of d₁ and d₂, modulo n and outputs a result of the operation.

2. The decryption device as set forth in claim 1, further comprising:

a confirmation unit that confirms a value of d₂, wherein the operation unit does not perform the exponentiation operation when d₂ is 1.

3. The decryption device as set forth in claim 1, further comprising:

a confirmation unit that confirms whether d₂ includes predetermined redundancy, wherein the operation unit does not perform the exponentiation operation when d₂ does not include the predetermined redundancy.

4. A decryption device that decrypts a cipher text encrypted by RSA method, comprising:

a first storage unit that stores a modulus n of a modulus exponentiation operation;

a second storage unit that stores first decryption information d₁;

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs second decryption information d₂; and

an operation unit that performs the modulus exponentiation operation in which C is raised to a power, a product of d₁ and a result of a predetermined operation on d₂, modulo n and outputs a result of the operation.

5. A decryption device that decrypts a cipher text encrypted by RSA method, comprising:

a first storage unit that stores a modulus n of a modulus exponentiation operation;

a second storage unit that stores an Euler number of n (φ

(n));

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs decryption information d;

a first operation unit that calculates an inverse number of d modulo φ

(n); and

a second operation unit that performs the modulus exponentiation operation in which C is raised to a power, a result of operation by the first operation unit, modulo n and outputs a result of the operation.

6. A decryption device that decrypts a cipher text encrypted by RSA method, comprising:

a first storage unit that stores a modulus n of a modulus exponentiation operation;

a first operation unit that calculates an Euler number of n (φ

(n));

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs decryption information d;

a second operation unit that calculates an inverse number of d modulo φ

(n); and

a third operation unit that performs the modulus exponentiation operation in which C is raised to a power, a result of operation by the second operation unit, modulo n and outputs a result of the operation.

7. A decryption device that decrypts a cipher text encrypted by RSA method, comprising:

a first storage unit that stores a modulus n of a modulus exponentiation operation;

a second storage unit that stores an Euler number of n (φ

(n));

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs decryption information d;

a first operation unit that calculates an inverse number of a result of a predetermined operation on d modulo φ

(n); and

a second operation unit that performs the modulus exponentiation operation in which C is raised to a power, a result of the operation by the first operation unit, modulo n and outputs a result of the operation.

8. A decryption device comprising:

a storage unit that stores at least a piece of secret decryption information kept secret to the decryption device;

a cipher text input unit that inputs a cipher text C;

an information input unit that inputs at least a piece of open decryption information disclosed to the decryption device; and

a decryption unit that decrypts C based on the secret decryption information and the open decryption information.

9. A decryption method comprising the steps of:

storing at least a piece of secret decryption information kept secret to a decryption device;

inputting a cipher text C;

inputting at least a piece of open decryption information disclosed to the decryption device; and

decrypting C based on the secret decryption information and the open decryption information.

10. A key generation device for an encryption method adopting a modulus exponentiation operation using an integer as a modulus, comprising:

an operation unit that operates a non collision function;

a composite number generation unit that generates a composite number; and

a key generation unit that generates keys I, D and E used in the encryption method so that a product of D, E and a result of operation of the non collision function on I is congruent with 1 modulo an Euler number of the composite number.

11. A key generation device for an encryption method adopting a modulus exponentiation operation using an integer as a modulus, comprising:

a key generation unit that generates keys I, D and E used in the encryption method; and

a composite number generation unit that generates a composite number, wherein I is a prime number and a product of I, D and E is congruent with 1 modulo an Euler number of the composite number.

12. A key generation device for an encryption method adopting a modulus exponentiation operation using an integer as a modulus, comprising:

a redundancy providing unit that provides predetermined redundancy to a specific piece of information;

a composite number generation unit that generates a composite number; and

a key generation unit that generates keys I, D and E used in the encryption method, wherein I is generated by providing the predetermined redundancy to the specific piece of information by the redundancy providing unit and a product of I, D and E is congruent with 1 modulo an Euler number of the composite number.

13. 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, comprising:

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 security characteristic information and the user identifying information;

a fourth storage unit that stores security required information;

a response generation unit that generates a response by performing 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.

14. The access right authentication apparatus as set forth in claim 13, wherein the response generation unit comprises a first operation unit that performs a predetermined operation on the user identifying information, the proof support information and the security required information, and a second operation unit that performs a predetermined operation on the challenging data and the result of the operation performed by the first operation unit to generate the response.

15. The access right authentication apparatus as set forth in claim 13, wherein the response generation unit comprises a first operation unit that performs a predetermined operation on the challenging data , the user identifying information and the security required information, and a second operation unit that performs a predetermined operation on the result of the operation by the first operation unit and the proof support information to generate the response.

16. The access right authentication apparatus as set forth in claim 13, wherein the response generation unit comprises a first operation unit performs a predetermined operation on the challenging data, the user identifying information and the security required information, a second operation unit that performs a predetermined operation on challenging data, the proof support information and the security required information and a third operation unit performs a predetermined operation on the results of the operations performed by the first operation unit and the second operation unit to generate the response.

17. The access right authentication apparatus as set forth in claim 13, wherein the security characteristic information is a first decryption key, the security required information is a second decryption key, the challenging data is a result of encryption of arbitrary data with an encryption key corresponding to the first and second decryption keys, and the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

18. The access right authentication apparatus as set forth in claim 13, wherein the security characteristic information is a first decryption key, a result of a predetermined operation on the security required information is a second decryption key, the challenging data is a result of encryption of arbitrary data with an encryption key corresponding to the first and second decryption keys, and the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

19. The access right authentication apparatus as set forth in claim 13, wherein a function used for encryption/decryption is a modulus exponentiation operation using an integer n as a modulus, the security characteristic information is an Euler number of the integer n, the security required information is an encryption key, the challenging data is a result of encryption of arbitrary data with the encryption key, and the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

20. The access right authentication apparatus as set forth in claim 13, wherein a function used for encryption/decryption is a modulus exponentiation operation using an integer n as a modulus, the security characteristic information is an Euler number of the integer n, a result of a predetermined operation on the security required information is an encryption key, the challenging data is arbitrary data encrypted with the encryption key, and the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

21. The access right authentication apparatus as set forth in claim 14, further comprising:

a secure unit that holds the second storage unit, first operation unit and the second operation unit to make it difficult to observe them from the outside of the secure unit.

22. The access right authentication apparatus as set forth in claim 15, further comprising:

a secure unit that holds the second storage unit and the first operation unit to make it difficult to observe them from the outside of the secure unit.

23. The access right authentication apparatus as set forth in claim 16, further comprising:

a secure unit that holds the second storage unit and the first operation unit to make it difficult to observe them from the outside of the secure unit.

24. The access right authentication apparatus as set forth in claim 17, wherein a function used for encryption/decryption is a modulus exponentiation operation using an integer n as a modulus, and a product of the first decryption key, the second decryption key and the encryption key is congruent with 1 modulo an Euler number of n.

25. The access right authentication apparatus as set forth in claim 17, further comprising:

a random number generation unit that generates a random number; and

a random number storage unit that stores the random number, wherein the challenging data is generated by providing a random number effect using the random number to data encrypted with the encryption key, and the response verification unit verifies that a result of removing the random number effect from the response is correct decryption of the data that was encrypted with the encryption key.

26. The access right authentication apparatus as set forth in claim 18, wherein a function used for encryption/decryption is a modulus exponentiation operation using an integer n as a modulus, and a product of the first decryption key, the second decryption key and the encryption key is congruent with 1 modulo an Euler number of n.

27. The access right authentication apparatus as set forth in claim 24, wherein the proof support information has a value obtained by subtracting a value generated by performing a predetermined operation on the user identifying information from a value of the first decryption key, and the response generation unit generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, a product of the first decryption key and the second decryption key, modulo n based on the proof support information, the user identifying information, the security required information and the challenging data.

28. The access right authentication apparatus as set forth in claim 24, wherein the response generation unit has a first operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the second decryption key and a result of a predetermined operation on the user identifying information, modulo n, a second operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the proof support information and the second decryption key, modulo n and a third operation unit that calculates a product of results of the operations by the first operation unit and the second operation unit modulo n, and wherein the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

29. The access right authentication apparatus as set forth in claim 24, wherein the proof support information stored in the third storage unit has a value obtained by dividing the first decryption key by a value generated by performing a predetermined operation on the user identifying information modulo the Euler number of n, and the response generation unit generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, a product of the first decryption key and the second decryption key, modulo n based on the proof support information, the user identifying information, the security required information and the challenging data.

30. The access right authentication apparatus as set forth in claim 24, wherein the response generation unit has a first operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the second decryption key and a result of a predetermined operation on the user identifying information, modulo n, and a second operation unit that performs the modulus exponentiation operation in which a result of the operation by the first operation unit is raised to a power, the proof support information, modulo n, and wherein the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

31. The access right authentication apparatus as set forth in claim 26, wherein the proof support information has a value obtained by subtracting a value generated by performing a predetermined operation on the user identifying information from a value of the first decryption key, and the response generation unit generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, a product of the first decryption key and the second decryption key, modulo n based on the proof support information, the user identifying information, the security required information and the challenging data.

32. The access right authentication apparatus as set forth in claim 26, wherein the response generation unit has a first operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the second decryption key and a result of a predetermined operation on the user identifying information, modulo n, a second operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the proof support information and the second decryption key, modulo n and a third operation unit that calculates a product of results of the operations by the first operation unit and the second operation unit modulo n, and wherein the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

33. The access right authentication apparatus as set forth in claim 26, wherein the proof support information stored in the third storage unit has a value obtained by dividing the first decryption key by a value generated by performing a predetermined operation on the user identifying information modulo the Euler number of n, and the response generation unit generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, a product of the first decryption key and the second decryption key, modulo n based on the proof support information, the user identifying information, the security required information and the challenging data.

34. The access right authentication apparatus as set forth in claim 26, wherein the response generation unit has a first operation unit that performs the modulus exponentiation operation in which the challenging data is raised to a power, a product of the second decryption key and a result of a predetermined operation on the user identifying information, modulo n, and a second operation unit that performs the modulus exponentiation operation in which a result of the operation by the first operation unit is raised to a power, the proof support information, modulo n, and wherein the response verification unit verifies that the response generated by the response generation unit is the correctly decrypted challenging data.

35. The access right authentication apparatus as set forth in claim 19, wherein the proof support information is generated by performing a predetermined operation on the Euler number and the user identifying information, and wherein the response generation unit calculates a decryption key corresponding to the encryption key based on the proof support information, the user identifying information and the security required information and generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, the decryption key, modulo n.

36. The access right authentication apparatus as set forth in claim 20, wherein the proof support information is generated by performing a predetermined operation on the Euler number and the user identifying information, and wherein the response generation unit calculates a decryption key corresponding to the encryption key based on the proof support information, the user identifying information and the security required information and generates the response by performing the modulus exponentiation operation in which the challenging data is raised to a power, the decryption key, modulo n.

37. 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, comprising:

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 generated by performing a first predetermined operation on security characteristic information and the user identifying information;

a fourth storage unit that stores security required information;

a fifth storage unit that stores security examination information;

an examination unit that examines whether the security examination information has a specific relationship with a result of a second predetermined operation on the challenging data and the security required information;

a response generation unit, when the examination unit determines that the security examination information has the specific relationship with the result of the second predetermined operation, that generates a response by performing a third predetermined operation on the challenging data, the user identifying information and the proof support information; and

a response verification unit that verifies the response is generated based on the security characteristic information.

38. An access right authentication method for authenticating a user'"'"'s access right by verifying legitimacy of a response generated for proving the user'"'"'s access right, comprising the steps of:

storing challenging data,

storing user identifying information;

storing proof support information generated by performing a predetermined operation on security characteristic information and the user identifying information;

storing security required information;

generating a response by performing a predetermined operation on the challenging data, the user identifying information, the proof support information and the security required information; and

verifying that the response is generated based on the security characteristic information and the security required information.

39. An access right authentication method for authenticating a user'"'"'s access right by verifying legitimacy of a response generated for proving the user'"'"'s access right, comprising the steps of:

storing challenging data,

storing user identifying information;

storing proof support information generated by performing a first predetermined operation on security characteristic information and the user identifying information;

storing security required information;

storing security examination information;

examining whether the security examination information has a specific relationship with a result of a second predetermined operation on the challenging data and the security required information;

when it is determined that the security examination information has the specific relationship with the result of the second predetermined operation in the examining step, generating a response by performing a third predetermined operation on the challenging data, the user identifying information and the proof support information; and

verifying that the response is generated based on the security characteristic information.