Information security device, exponentiation device, modular exponentiation device, and elliptic curve exponentiation device
First Claim
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, andthe 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 B2;
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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 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, andthe 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 B2; 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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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; andan output unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
- A based on the intractability of the discrete logarithm problem in a group,
-
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, andthe 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 B2; 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, whereinthe 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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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.
- A based on the intractability of the discrete logarithm problem in a group,
-
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, andthe 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 B2; 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, whereinthe 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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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; andthe output unit outputs the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.
- A,
-
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 Ak over a natural number field, the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=Ak 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 B2; 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 Ak, the result of the exponentiation Ak 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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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; andan output unit for outputting, the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.
- A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;
-
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 Ak 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 Ak 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=Ak 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 B2; 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 Ak, the result of the exponentiation Ak 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 B2, 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 B1, 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 B2 for the operand in the variable B1, 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; andoutput unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.
- A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;
-
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 B2; 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 B2, 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 B1, 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 B2 for the operand in the variable B1 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; andoutput unit for outputting the encrypted information, the decrypted information, the digital signature, a result of the verification or the shared key.
- A based on the intractability of the discrete logarithm problem in a group, the improvement comprising;
Specification