Information security device, exponentiation device, modular exponentiation device, and elliptic curve exponentiation device

• US 7,167,559 B2
• Filed: 03/25/2002
• Issued: 01/23/2007
• Est. Priority Date: 03/28/2001
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Nakano, Toshihisa, Matsuzaki, Natsume, Ono, Takatoshi
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): Pan; Joseph
• Application Number:
  US10/105,480
• Publication Number:
  US 20020172356A1
• Time in Patent Office: 1,765 Days
• Field of Search: 380/28, 380/30, 380/44, 380/200, 380/201, 380/255, 380/277, 726/2, 713/1, 713/2, 713/188, 713/194, 713/174
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7285 using the window method, i.e. left-to-right k-ary exponentiation
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

In an exponentiation device, a relatively large table is generated outside of a coprocessor so as to enable high-speed exponentiation to be performed using the small window method. The selection of data from the table and transfer of data to the coprocessor are conducted in parallel with a multiple-length arithmetic operation performed in the coprocessor. So as to avoid bottlenecks occurring in the data transfer between a CPU and the coprocessor, two data banks are provided in the coprocessor for storing the data to be used in the arithmetic operation. By providing two banks in the coprocessor, it is possible to use one for transferring data while data stored in the other is being used in the arithmetic operation. When the operation using the stored data has been completed, the banks are switched, and the arithmetic operation is then repeated using the newly transferred data while at the same time conducting data transfer in readiness for the following operation.

Claims

1. A computerized implemented information security device for encrypting information, decrypting the encrypted information, generating a digital signature, and verifying the digital signature or sharing a key by performing a power operation k &

A based on the intractability of the discrete logarithm problem in a group,

the group being formed from a predetermined set and a binary operation performed using elements of the set,

the power operation k &

A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, and

the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &

A in the group, the device operating on bits of data comprising;

input unit for receiving inputs of the element k and the element A;

initializing unit for storing the identity element as an initial value in a variable X and a variable B₂;

repetition control unit for controlling a calculation unit, a storage unit, and an exchange unit to repeat, for the number of bits in a bit sequence of data resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &

A, the result of the power operation k &

A being stored in the variable X at the completion of the repetitions;

the calculation unit performs the binary operation using the variable X and the same variable X, performing the binary operation again using the initial binary operation result and an operand stored in the variable B₂, and storing the further binary operation result in the variable X;

the storage unit selects an operand to be used by the calculation unit in the following step and stores the selected operand in a variable B₁, the operation conducted by the storage unit being completed during a duration of the operation conducted by the calculation unit;

the exchange unit exchanges the operand in the variable B₂ for the operand in the variable B₁, when the operations conducted by the calculation unit and the storage unit have been complete;

a security unit for using, after the completion of the repetitions, the result of the power operation k &

A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

an output unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.

2. The device of claim 1, wherein the storage means includes

a candidate value storage unit for storing one or more candidate values that are smaller than a predetermined value,

a selection unit for selecting one of the one or more stored candidate values as the operand to be used by the calculation unit in the following step, the selection being conducted using a section of the bit sequence of k, and

a data storage unit for storing the selected operand in the variable B₁, the operation conducted by the data storage unit being completed during the duration of the operation conducted by the calculation unit.

3. The device according to claim 2, wherein

the one or more candidate values stored by the candidate value storage unit result from a power operation h &

A where h is smaller than a predetermined value.

4. The device according to claim 3, wherein

the repetition control unit controls the step to be repeated in a descending order of the bit sequence of k.

5. The device according to claim 4, wherein

the selection unit prevents the selection of the operand when the section of the bit sequence of k conforms to a predetermined bit sequence pattern,

the data storage unit prevents the storage of a selected operand in the variable B₁, when the selection unit has prevented the selection of the operand, and

the calculation unit performs, in the following step when the data storage unit has prevented the storage of an operand in the variable B₁, the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and the identity element, and stores the further binary operation result in the variable K.

6. The device according to claim 4 being a computer system composed of a general-purpose processor, a specialized processor, a first memory, a bus, and a DMA control unit, wherein

the general-purpose processor, the specialized processor, the first memory, and the DMA control unit are connected to each other via the bus,

the first memory includes a region for storing a computer program, the element k, the element A, and an operand,

the specialized processor includes the calculation unit, the exchange unit, and a second memory for storing the variables X₁, B₁, and B₂,

the initializing unit initializes, via the bus, the variables X and B₂ stored in the second memory,

the repetition control unit controls the step to be repeated,

the storage unit transfers, via the bus and under the control of the DMA control unit, the operand stored in the first memory to the variable B₁, stored in the second memory, and

the operations conducted by the initializing unit, the repetition control unit, and the storage unit are executed by the general-purpose processor in accordance with the computer program.

7. The device according to claim 6, wherein

the repetition control unit controls the step to be repeated for the higher order bits of the bit sequence of k, and

the device further comprises:

a binary method calculation unit for applying a binary method to perform, in ascending order of the bit sequence of k, a lower order power operation using the lower order bits of the bit sequence, the result of the lower order power operation being stored in a variable Z in the first memory; and

a binary operation unit for calculating the result of the power operation k &

A by performing a binary operation using the variables X and Z,

the operations conducted by the binary method calculation unit and the binary operation unit being executed by the general-purpose processor in accordance with the computer program.

8. The device according to claim 4, wherein the group is an elliptic curve,

the identity element is a zero element, being a point at infinity above the elliptic curve,

the power operation k &

A is a multiplication k×

A on the elliptic curve,

the binary operation is an addition on the elliptic curve,

the discrete logarithm problem is to determine k, when k exists, such that Y=k×

A on the elliptic curve,

the initializing unit stores the zero element in the variables X and B₂,

the repetition control unit controls the step to be repeated for the bit number of k so as to perform the multiplication k×

A, the result of the multiplication k×

A being stored in the variable X at the completion of the repetitions, and

the calculation unit performs the addition using the variable X and the same variable X, performs the addition again using the initial addition result and the operand stored in the variable B₂, and stores the further addition result in the variable X.

9. The device according to claim 4, wherein

the group is a residue field,

the identity element is an integer having a value of 1,

the power operation k &

A is an exponentiation A^k over the residue field,

the binary operation is a multiplication over the residue field,

the discrete logarithm problem is to determine k, when k exists, such that Y=A^k over the residue field,

the initializing unit stores the integer 1 in the variables X and B₂,

the repetition control unit controls the step to be repeated for the bit number of k so as to perform the exponentiation A^k, the result of the exponentiation A^k being stored in the variable X at the completion of the repetitions, and,

the calculation unit performs the multiplication using the variable X and the same variable X, performs the multiplication again using the initial multiplication result and the operand stored in the variable B₂, and stores the further multiplication result in the variable X.

10. The device according to claim 4, wherein

the group is a natural number field,

the identity element is an integer having a value of 1,

the power operation k &

A is an exponentiation A^k over the natural number field,

the binary operation is a multiplication over the natural number field,

the discrete logarithm problem is to determine k, when k exists, such that Y=A^k over the natural number field,

the initializing unit stores the integer 1 in the variables X and B₂,

the repetition control unit controls the step to be repeated for the bit number of k so as to perform the exponentiation A^k, the result of the exponentiation A^k being stored in the variable X at the completion of the repetitions, and

the calculation unit performs the multiplication using the variable X and the same variable X, performs the multiplication again using the initial multiplication result and the operand stored in the variable B₂, and stores the further multiplication result in the variable X.

11. The device according to claim 4 performing the power operation k &

A in order to encrypt or decrypt the predetermined information.

12. The device according to claim 4 performing the power operation k &

A in order to generate or verify at digital signature in the predetermined information.

13. The device according to claim 4 performing the power operation k &

A in order to safely share a key with another device.

14. A computerized implemented information security method used by an information security device for encrypting information, decrypting the encrypted information, generating a digital signature, and verifying the digital signature or sharing a key by performing a power operation k &

A based on the intractability of the discrete logarithm problem in a group,

the device including initializing unit, repetition control unit, calculation unit storage unit, and exchange unit,

the group being formed from a predetermined set and a binary operation performed using elements of the set,

the power operation k &

A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, and

the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &

A in the group, the method operating upon bits of data comprising;

inputting values for the element k and the element A;

an initializing step for having the initializing unit store the identity element as an initial value in a variable X and a variable B₂;

a repetition control step for having the repetition control means control the calculation unit, the storage unit, and the exchange unit to repeat, for the number of bits in a bit sequence of data resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &

A, the result of the power operation k &

A being stored in the variable X at the completion of the repetitions, wherein

the calculation unit performs the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and an operand stored in the variable B₂, and stores the further binary operation result in the variable X,

the storage unit selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B₁, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and

the exchange unit exchanges the operand in the variable B₂ for the operand in the variable B₁, when the operations conducted by the calculation unit and the storage unit have been completed;

using, after the completion of the repetitions, the result of the power operation k and A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.

15. A computer-readable storage medium storing an information security program used by an information security device that securely and reliably manages predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &

A,

the device including initializing unit, repetition control unit, calculation unit, storage unit, exchange unit, security unit and an output unit,

the group being formed from a predetermined set and a binary operation performed using elements of the set,

the power operation k &

A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, and

the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &

A in the group, the program comprising;

a storing step for storing inputted values for the element k and the element A;

an initializing step for having the initializing unit store the identity element as an initial value in a variable X and a variable B₂; and

a repetition control step for having the repetition control unit control the calculation unit, the storage unit, and the exchange unit to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &

A, the result of the power operation k &

A being stored in the variable X at the completion of the repetitions, wherein

the calculation unit performs the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and an operand stored in the variable B₂, and stores the further binary operation result in the variable AX,

the storage unit selects an operand to be used by the calculation unit in the following step and stores the selected operand in a variable B₁, the operation conducted by the storage unit being completed during a duration of the operation conducted by the calculation unit,

the exchange unit exchanges the operand in the variable B₂ for the operand in the variable B₁, when the operations conducted by the calculation unit and the storage unit have been completed;

the security unit for after the completion of the repetitions, uses the result of the power operation k &

A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

the output unit outputs the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.

16. In a computerized implemented information security device for encrypting information, decrypting the encrypted information, generating a digital signature, and verifying the digital signature or sharing a key by performing a power operation k &

A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;

an exponentiation device for exponentiating A^k over a natural number field, the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=A^k over the natural number field, the device comprising;

an input unit for receiving inputs of the element k and the element A;

an initializing unit for storing an integer value 1 as an initial value in a variable X and a variable B₂;

a repetition control unit for controlling calculation unit, storage unit, and exchange unit to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the exponentiation A^k, the result of the exponentiation A^k being stored in the variable X at the completion of the repetitions;

a calculation unit for performing the multiplication using the variable X and the same variable X, performing the multiplication again using the initial multiplication result and an operand stored in the variable B₂, and storing the further multiplication result in the variable X;

a storage unit for selecting an operand to be used by the calculation unit in the following step and storing the selected operand in a variable B₁, the operation conducted by the storage unit being completed during a duration of the operation conducted by the calculation unit;

the exchange unit for exchanging the operand in the variable B₂ for the operand in the variable B₁, when the operations conducted by the calculation unit and the storage unit have been completed;

a security unit for using, after the completion of the repetitions, the result of the power operation k &

A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

an output unit for outputting, the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.

17. In a computerized implemented information security device for encrypting information, decrypting the encrypted information, generating a digital signature, and verifying the digital signature or sharing a key by performing a power operation k &

A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;

a modular exponentiation device for exponentiating A^k over a residue field,

the residue field being formed from a predetermined set and a multiplication over the residue field performed using elements of the set,

the exponentiation A^k involving k number of repetitions of the multiplication performed using the element A of the residue field and an integer value 1, and

the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=A^k over the residue field, the device comprising;

input unit for receiving inputs of the element k and the element A;

initializing unit for storing the integer 1 as an initial value in a variable X and a variable B₂;

repetition control unit for controlling a calculation unit, a storage unit, and an exchange unit to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as k to perform the exponentiation A^k, the result of the exponentiation A^k being stored in the variable X at the completion of the repetitions;

the calculation unit performs the multiplication using the variable X and the same variable X, performing the multiplication again using the initial multiplication result and an operand stored in the variable B₂, and storing the further multiplication result in the variable X;

the storage unit provides an operand to be used by the calculation unit in the following step and storing the selected operand in a variable B₁, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation unit;

the exchange unit exchanges the operand in the variable B₂ for the operand in the variable B₁, when the operations conducted by the calculation unit and the storage unit have been completed;

security unit for using, after the completion of the repetitions, the result of the power operation k &

A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

output unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.

18. In a computerized implemented information security device for encrypting information, decrypting the encrypted information, generating a digital signature, and verifying the digital signature or sharing a key by performing a power operation k &

A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;

an elliptic curve exponentiation device for multiplying k×

A on an elliptic curve,

the elliptic curve being formed from a predetermined set and an addition on the elliptic curve performed using elements of the set,

the multiplication k×

A on the elliptic curve involving k number of repetitions of the addition performed using the element A of the elliptic curve and a zero element, being a point at infinity above the elliptic curve, and,

the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k×

A on the elliptic curve, the device comprising;

input unit for receiving inputs of the element k and the element A;

initializing unit for storing the zero element as an initial value in a variable X and a variable B₂;

repetition control unit for controlling a calculation unit, a storage unit, and an exchange unit to repeat, for the number of bits in a bit sequence resulting when the element k;

is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the multiplication k×

A, the result of the multiplication k×

A being stored in the variable X at the completion of the repetitions;

the calculation unit for performing the addition using the variable X and the same variable X, performing the addition again using the initial addition result and an operand stored in the variable B₂, and storing the further addition result in the variable X;

the storage unit for selecting an operand to be used by the calculation unit in the following step and storing the selected operand in a variable B₁, the operation conducted by the storage unit being completed during a duration of the operation conducted by the calculation unit; and

the exchange unit for exchanging the operand in the variable B₂ for the operand in the variable B₁ when the operations conducted by the calculation unit and the storage unit have been completed;

security unit for using, after the completion of the repetitions, the result of the power operation k &

A being stored in the variable X to encrypt the information, decrypt the encrypted information, generate the digital signature, and verify the digital signature or share the key; and

output unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.