Secure processing device, secure processing method, encrypted confidential information embedding method, program, storage medium, and integrated circuit
When performing secure processing using confidential information that needs to be confidential, the secure processing device according to the present invention prevents the confidential information from being exposed by an unauthorized analysis such as a memory dump. A signature generation device that provides a message M with a signature by using a signature key comprises: a split key storage unit that stores split secret keys obtained by splitting the signature key d into at least two, a signature key generation equation F for calculating the split secret keys to obtain the signature key d, and a signature generation equation; a signature key generation identical equation generation unit that generates a signature key generation identical equation G for obtaining the same result as the signature generation equation F, with use of an associative law, a distributive law, and a commutative law; a combined split key generation unit that generates a plurality of combined split keys that are each a result of calculating the split secret keys, and that are to be arguments for the signature key generation identical equation G; and a signature generation unit that provides the message with the signature, based on the signature key generation identical equation G and the split secret keys.
1. A secure processing device that performs an operation equivalent to a secure operation performed on a message using a secret key, and that obtains a same operation result as the secure operation, the secure processing device comprising:
a microprocessor; and
a non-transitory memory storing thereon executable instructions, which when executed by the microprocessor, cause the secure processing device to function as:
a storage unit that stores (i) a plurality of split keys obtained by splitting the secret key, and (ii) a first secret key generation equation for calculating the secret key with use of the plurality of split keys as arguments input to the first secret key generation equation, the first secret key generation equation including an operation including at least one arithmetic operation;
a combined key generation unit operable to generate a plurality of combined keys, each of which is obtained by performing an operation on at least one of the split keys;
a generation unit operable to generate a second secret key generation equation (i) that is equivalent to the first secret key generation equation, (ii) that takes the plurality of combined keys as arguments, and (iii) that is for performing a secure operation on the message with use of the plurality of combined keys, the second secret key generation equation including an operation including at least one arithmetic operation; and
an executing unit operable to perform the secure operation on the message with use of the plurality of combined keys based on the second secret key generation equation, wherein the plurality of combined keys and the second secret key generation equation are dynamically generated before the secure operation is performed on the message, so that the plurality of combined keys and the second secret key generation equation are not always the same,
wherein the storage unit stores the plurality of split keys as groups of split keys, and
wherein the generation unit generates the second secret key generation equation by (i) randomly shuffling each of the groups of split keys stored in the storage unit using a commutative law, (ii) randomly splitting of the split keys included in each of the groups of split keys that have been randomly shuffled using an associative law, and (iii) transforming each of the groups of split keys that have been randomly split into a data structure, randomly selecting parts of the data structure to be combined, and combining the selected parts to generate the second secret key generation equation that is equivalent to the first secret key generation equation using a distributive law.
2. The secure processing device of claim 1 ,
wherein the first secret key generation equation includes one or more operations,
wherein each of the one or more operations, included in the first secret key generation equation, includes (i) a plurality of operands and (ii) an operator indicating a type of an operation between the operands,
wherein the storage unit stores attribute information for each of the operations included in the first secret key generation equation, the attribute information indicating a relationship between the plurality of operands and the operator, and
wherein the generation unit generates the second secret key generation equation with use of the attribute information.
3. The secure processing device of claim 2 ,
wherein, in the first secret key generation equation, values of the arguments are input as the operands, each of the values corresponding to a different one of the plurality of split keys,
wherein the attribute information indicates an operator that corresponds to a plurality of operands capable of being combined, and
wherein the combined key generation unit is operable to generate the combined keys by combining split keys corresponding to the combined operands.
4. The secure processing device of claim 1 , wherein the second secret key generation equation includes one or more operations, each of the one or more operations including (i) a plurality of operands and (ii) an operator indicating a type of an operation between the operands, and
wherein the storage unit stores attribute information for each of the one or more operations included in the second secret key generation equation, the attribute information indicating a relationship between the plurality of operands and the operator.
5. The secure processing device of claim 1 ,
wherein the generation unit further generates random number information, and thereby generates the second secret key generation equation including the random number information, and
wherein the executing unit perform the secure operation on the message using the plurality of combined keys and the random number information.
6. The secure processing device of claim 1 ,
wherein the generation unit further generates, with use of the secret key, redundant information that does not affect a result of the secure operation processing, and thereby generates the second secret key generation equation using the redundant information.
7. The secure processing device of claim 1 ,
wherein the storage unit stores dummy information, which is not used by the executing unit, together with the plurality of split keys.
8. The secure processing device of claim 1 ,
wherein the secret key is a signature key for generating a digital signature, and
wherein the secure operation is a signature generation operation for providing a digital signature on the message.
9. The secure processing device of claim 8 ,
wherein the signature generation processing is RSA (Rivest Shamir Adleman) signature generation processing.
10. The secure processing device of claim 8 ,
wherein the signature generation processing is performed using an elliptic curve digital signature method.
11. The secure processing device of claim 10 , wherein the executed executable instructions further cause the secure processing device to function as
a random number information generation unit operable to generate random number information,
wherein the executing unit performs (i) processing for calculating a random value k scalar multiplication point of a base point P that is an order q of an elliptic curve on a field of definition GF(p) in the elliptic curve digital signature method, and (ii) processing that uses a value of an inverse of k on the field of definition GF(q), without directly using the random number k, but using at least two pieces of random number information.
12. The secure processing device of claim 1 , wherein the secret key is a secret key for public key encryption, and
wherein the executing unit performs, as the secure operation, processing of a public key encryption system using a public key and the secret key.
13. The secure processing device of claim 12 ,
wherein the public key encryption is RSA encryption.
14. The secure processing device of claim 12 ,
wherein the public key encryption is elliptic curve encryption.
15. The secure processing device of claim 1 , wherein the executed executable instructions further cause the secure processing device to function as:
an acquiring unit operable to acquire, from outside, data for updating the generation unit; and
an updating unit operable to update the generation unit with use of the data for updating.
16. The secure processing device of claim 1 , wherein the executed executable instructions further cause the secure processing device to function as:
an acquiring unit operable to acquire, from outside, at least one split key for updating;
an updating unit operable to update at least one of the plurality of split keys stored in the storage unit using the at least one split key for updating acquired by the acquiring unit.
17. A secure processing method used in a secure processing device that performs an operation equivalent to a secure operation performed on a message using a secret key, and that obtains a same operation result as the secure operation, wherein the secure processing device includes a storage unit that stores (i) a plurality of split keys obtained by splitting the secret key, and (ii) a first secret key generation equation for calculating the secret key with use of the plurality of split keys as arguments input to the first secret key generation equation, the first secret key generation equation including an operation including at least one arithmetic operation, the secure processing method comprising:
generating a plurality of combined keys, each of which is obtained by performing an operation on at least one of the split keys;
generating a second secret key generation equation (i) that is equivalent to the first secret key generation equation, (ii) that takes the plurality of combined keys as arguments, and (iii) that is for performing a secure operation on the message with use of the plurality of combined keys, the second secret key generation equation including an operation including at least one arithmetic operation; and
performing the secure operation on the message with use of the plurality of combined keys based on the second secret key generation equation,
wherein the plurality of combined keys and the second secret key generation equations are dynamically generated before the secrete operation is performed on the message, so that the plurality of combined keys and the second secret key generation equation are not always the same,
wherein the storage unit stores the plurality of split keys as groups of split keys, and
wherein the second secret key generation equation is generated by (i) randomly shuffling each of the groups of split keys stored in the storage unit using the commutative law, (ii) randomly splitting of the split keys included in each of the groups of split keys that have been randomly shuffled using the associative law, and (iii) transforming each of the groups of split keys that have been randomly split into a data structure, randomly selecting parts of the data structure to be combined, and combining the selected parts to generate the second secret key generation equation that is equivalent to the first secret key generation equation using the distributive law.
18. A non-transitory computer readable recording medium having stored thereon a computer program used in a secure processing device that performs an operation equivalent to a secure operation performed on a message using a secret key, and that obtains a same operation result as the secure operation, the secure processing device comprising, wherein the secure processing device includes a storage unit that stores (i) a plurality of split keys obtained by splitting the secret key, and (ii) a first secret key generation equation for calculating the secret key with use of the plurality of split keys as arguments input to the first secret key generation equation, the first secret key generation equation including an operation including at least one arithmetic operation, and wherein, when executed, the computer program causes the secure processing device to perform a method comprising:
generating a plurality of combined keys, each of which is obtained by performing an operation on at least one of the split keys;
generating a second secret key generation equation (i) that is equivalent to the first secret key generation equation, (ii) that takes the plurality of combined keys as arguments, and (iii) that is for performing a secure operation on the message with use of the plurality of combined keys, the second secret key generation equation including an operation including at least one arithmetic operation; and
performing the secure operation on the message with use of the plurality of combined keys based on the second secret key generating equation,
wherein the plurality of combined keys and the second secret key generation equation are dynamically generated before the secure operation is performed on the message, so that the plurality of combined keys and the second secret key generation equation are not always the same,
wherein the storage unit stores the plurality of split keys as groups of split keys, and wherein the second secret key generation equation is generated by (i) randomly shuffling each of the groups of split keys stored in the storage unit using the commutative law, (ii) randomly splitting of the split keys included in each of the groups of split keys that have been randomly shuffled using the associative law, and (iii) transforming each of the groups of split keys that have been randomly split into a data structure, randomly selecting parts of the data structure to be combined, and combining the selected parts to generate the second secret key generation equation that is equivalent to the first secret key generation equation using the distributive law.
19. An integrated circuit that performs an operation equivalent to a secure operation performed on a message using a secret key, and that obtains a same operation result as the secure operation, the integrated circuit comprising:
a microprocessor; and
a non-transitory memory storing thereon executable instructions, which when executed by the microprocessor, cause the integrated circuit to function as:
a storage unit that stores (i) a plurality of split keys obtained by splitting the secret key, and (ii) a first secret key generation equation for calculating the secret key with use of the plurality of split keys as arguments input to the first secret key generation equation, the first secret key generation equation including an operation including at least one arithmetic operation;
a combined key generation unit operable to generate a plurality of combined keys, each of which is obtained by performing an operation on at least one of the split keys;
a generation unit operable to generate a second secret key generation equation (i) that is equivalent to the first secret key generation equation, (ii) that takes the plurality of combined keys as arguments, and (iii) that is for performing a secure operation on the message with use of the plurality of combined keys, the second secret key generation equation including an operation including at least one arithmetic operation; and
an executing unit operable to perform the second secure operation procedure on the message with use of the plurality of combined keys based on the second secret key generation equation,
wherein the plurality of combined keys and the second secret key generation equation are dynamically generated before the secure operation is performed on the message, so that the plurality of combined keys and the second secret key generation equation are not always the same,
wherein the storage unit stores the plurality of split keys as groups of split keys, and wherein the generation unit generates the second secret key generation equation by (i) randomly shuffling each of the groups of split keys stored in the storage unit using the commutative law, (ii) randomly splitting of the split keys included in each of the groups of split keys that have been randomly shuffled using the associative law, and (iii) transforming each of the groups of split keys that have been randomly split into a data structure, randomly selecting parts of the data structure to be combined, and combining the selected parts to generate the second secret key generation equation that is equivalent to the first secret key generation equation using the distributive law.