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

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
10Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. An information security device for securely and reliably managing predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
 A, 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 comprising;
initializing means for storing the identity element as an initial value in a variable X and a variable B_{2};
repetition control means for controlling calculation means, storage means, and exchange means 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;
the calculation means for performing 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_{2}, and storing the further binary operation result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
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 highspeed 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 multiplelength 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.
11 Citations
View as Search Results
Information security device, exponentiation device, modular exponentiation device, and elliptic curve exponentiation device  
Patent #
US 7,167,559 B2
Filed 03/25/2002

Current Assignee
Matsushita Electric Industrial Company Limited

Sponsoring Entity
Matsushita Electric Industrial Company Limited

Server apparatus  
Patent #
US 20060179297A1
Filed 01/13/2006

Current Assignee
Sanyo Electric Company Limited

Sponsoring Entity
Sanyo Electric Company Limited

RSAANALOGOUS XZELLIPTIC CURVE CRYPTOGRAPHY SYSTEM AND METHOD  
Patent #
US 20120140921A1
Filed 12/01/2010

Current Assignee
King Fahd University of Petroleum and Mineral

Sponsoring Entity
King Fahd University of Petroleum and Mineral

Accelerated Verification of Digital Signatures and Public Keys  
Patent #
US 20140344579A1
Filed 06/27/2014

Current Assignee
Blackberry Limited

Sponsoring Entity
Blackberry Limited

Method For Validating A Cryptographic Parameter And Corresponding Device  
Patent #
US 20140369493A1
Filed 04/30/2014

Current Assignee
IDEMIA France

Sponsoring Entity
Oberthur Technologies SA

Using a secret generator in an elliptic curve cryptography (ECC) digital signature scheme  
Patent #
US 9,800,411 B1
Filed 05/05/2016

Current Assignee
ISARA Corporation

Sponsoring Entity
ISARA Corporation

METHOD FOR ONBOARD PRIME NUMBER GENERATION  
Patent #
US 20170346632A1
Filed 11/25/2015

Current Assignee
Thales DIS France SA

Sponsoring Entity
Thales DIS France SA

Method for validating a cryptographic parameter and corresponding device  
Patent #
US 10,038,560 B2
Filed 04/30/2014

Current Assignee
IDEMIA France

Sponsoring Entity
IDEMIA France

Accelerated verification of digital signatures and public keys  
Patent #
US 10,284,370 B2
Filed 06/27/2014

Current Assignee
Blackberry Limited

Sponsoring Entity
Blackberry Limited

Method for onboard prime number generation  
Patent #
US 10,447,477 B2
Filed 11/25/2015

Current Assignee
Thales DIS France SA

Sponsoring Entity
Thales DIS France SA

Method and apparatus for integrated ciphering and hashing  
Patent #
US 6,021,201 A
Filed 01/07/1997

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

19 Claims
 1. An information security device for securely and reliably managing predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
 A,
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 comprising;
initializing means for storing the identity element as an initial value in a variable X and a variable B_{2};
repetition control means for controlling calculation means, storage means, and exchange means 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;
the calculation means for performing 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_{2}, and storing the further binary operation result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
 A,
 14. An information security method 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 means, repetition control means, calculation means, storage means, and exchange means, 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 comprising;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B_{2; and } a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means 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 means 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_{2}, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 A,
 15. 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 means, repetition control means, calculation means, storage means, and exchange means, 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;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B_{2}; and
a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means 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 means 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_{2}, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 A,
 16. A computerreadable 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 means, repetition control means, calculation means, storage means, and exchange means, 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;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B_{2}; and
a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means 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 means 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_{2}, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 A,
 17. 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:
initializing means for storing an integer value 1 as an initial value in a variable X and a variable B_{2};
repetition control means for controlling calculation means, storage means, and exchange means 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;
the calculation, means 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_{2}, and storing the further multiplication result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 18. 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: initializing means for storing the integer 1 as an initial value in a variable X and a variable B_{2};
repetition control means for controlling calculation means, storage means, and exchange means 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;
the calculation means 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_{2}, and storing the further multiplication result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 19. 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;
initializing means for storing the zero element as an initial value in a variable X and a variable B_{2};
repetition control means for controlling calculation means, storage means, and exchange means 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 means 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_{2}, and storing the further addition result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
 A on an elliptic curve,
1 Specification
[0001] This application is based on unexamined patent application publication 2001092482 filed in Japan, the content of which is hereby incorporated by reference.
[0002] 1. Field of the Invention
[0003] The present invention relates to information security technology for performing exponentiation operations, modular exponentiation operations, and elliptic curve exponentiation operations.
[0004] 2. Related Art
[0005] The widespread use of electronic data transmission resulting from developments in computer and communications technology has led to the increasing application of such technology as secret communications and digital signatures.
[0006] A secret communication system allows communications to be conducted between related parties without the communicated content being revealed to third parties. A digital signature system enables the receiver to authenticate the communicated content and verify the sender.
[0007] Both of these systems employ a cryptosystem known as public key cryptography. Public key cryptography provides a convenient method for managing a large number of separate encryption keys and is considered indispensable for communications involving many users. According to this system different keys are used for encryption and decryption, the encryption key being public and the decryption key remaining secret.
[0008] The Discrete Logarithm Problem
[0009] The security in public key cryptography is based on the intractability of the discrete logarithm problem. Commonly used discrete logarithms included those over finite fields and elliptic curves.
[0010] The discrete logarithm problem over a finite field assumes that GF is a finite field, and b and y are elements of GF. The discrete logarithm problem for GF is then to determine a value x such that:
b^{x}=y
[0011] where x is an integer (when it exists).
[0012] The discrete logarithm problem over an elliptic curve assumes that E is an elliptic curve defined over GF, G is a base point lying on E, and Y is a new point lying on E.
[0013] The discrete logarithm problem for GF is then to determine a value x such that:
Y=x*G
[0014] where x is an integer (when it exists).
[0015] The symbol “*” represents the multiple addition of the base point lying on the elliptic curve. For example, x*G represents the addition of a base point G to itself x times, or:
x*G=G+G+G+G+. . . +G
[0016] The discrete logarithm problem is employed in the security of public key cryptosystems because of the computational difficulties involved in determining the value of x with respect to a finite field GF(p) having a large number of bases. Related issues are discussed in detail in Neal Koblitz, A Course in Number Theory and Cryptography, SpringerVerlag, 1987.
[0017] Exponentiation and Elliptic Curve Exponentiation
[0018] When the discrete logarithm problem is used as the basis for security in public key cryptography, two types of arithmetic operations are employed, those being exponentiation and elliptic curve exponentiation.
[0019] A well known method of performing exponentiation and elliptic curve exponentiation is the binary method described by D. E. Knuth in Seminumerical Algorithms: The Art of Computer Programming, Volume Two (3^{rd }ed., Reading, Mass.: AddisonWesley, 1997, c.1969).
[0020] Known refinements to the standard binary algorithm include the small window method (also described in Knuth above) and the signed binary method (see F. Morain, J. Olivos, “Speeding up the computations on an elliptic curve using additionsubtraction chains,” in Theoretical Informatics and Applications, vol.24, no.6, 1990).
[0021] Further refinements to the signed binary method are disclosed in unexamined patent application publications 749769 and 2000330470 filed in Japan.
[0022] Binary Method
[0023] The following is a description of the prior art binary method, using modular exponentiation as an example.
[0024] In order to calculate A^{k }using the binary method, a modular exponentiation result is obtained by performing (i) n−1 modular squarings and (ii) modular multiplications such that k_{i}=1. In this calculation exponent k is represented in binary, giving k_{n−1 }k_{n−2 }. . . k_{i }. . . k_{1 }k_{0 }where n>i≧0 and k_{i}=0 or 1.
[0025] According to the binary method, the variable i, which is an index showing which bits to investigate, is initially assigned a value n−1 where k is represented in binary. Also, a variable X, which will ultimately store the modular exponentiation result, is assigned an initial value of 1. Modulus n represents the bit size when k is represented in binary.
[0026] The following steps are then repeatedly performed while subtracting 1 from the value of variable i per repetition until i=0 (i=n−1, n−2, . . . , 1, 0).
[0027] Step 1: X=X^{2 }(modular square X and assign the result to X)
[0028] Step 2: X=X×A only when k_{i}=1 (modular multiply X by A and assign the result to X)
[0029] When the repetitions have been completed, the resulting value A^{k }is stored in X.
[0030] Small Window Method
[0031] The following description relates to another prior art method, the small window method.
[0032] The first step in calculating A^{k }using this method is the same as the binary method: the variables X and i are assigned initial values of 1 and n−1, respectively. The equation m=2^{w−1 }is then calculated where W is a window size, and a table based on A is formulated that includes A_{0}, A_{1}, . . . , A_{m1}. Here, A_{0}, A_{1}, . . . , A_{m1 }are calculated as follows.
[0033] A_{0}=A
[0034] A_{1}=A^{3 }
[0035] . . .
[0036] A_{m−1}=A^{2m−1 }
[0037] Next, the binary expression k_{i }of the exponent k is converted to k′_{i}. Here, k_{i }has a value of 0 or 1, and k′_{1 }has a value of 0, 1, . . . m−1.
[0038] Taking a threebit sequence k_{t+2}, k_{t+1}, k_{t }(the value of k_{t+2}, k_{t+1}, k_{t }each being 0 or 1) in the binary expression . . . k_{i }k_{i−1 }. . . k_{1 }k_{0 }of exponent k as an example, the three bits are expressed collectively as k′_{t}. Thus, k′_{t}=011=3 when k_{t+2}=0, k_{t+1}=1, k_{t}=1. Although this example is described in terms of being a conversion process using a threebit sequence, it is actually window size that is used to conduct the conversion.
[0039] Next, the following steps are performed while subtracting 1 from variable i per repetition until i=0 (i=n−1, n−2, . . . , 1, 0)
[0040] Step 1: X=X^{2 }(modular square X and assign the result to X) Step 2: X=X×Ak′_{i }only when k′_{i }≠0 (modular multiply X by Ak′_{i }and assign the result to X)
[0041] When the repetitions have been completed, the resulting value A^{k }is stored in X.
[0042] The small window method is a wellknown means of performing highspeed modular exponentiation because it allows for a reduction in the number of modular multiplications in comparison to the binary method.
[0043] Other prior art methods will not be discussed here due to their similarity with the two methods given above; namely, they also determine the exponent and perform modular multiplication and modular squaring on the determined value of the exponent.
[0044] Exemplary Structure of a Modular Exponentiation Device
[0045] The following description relates to a known modular exponentiation device for performing modular exponentiation using the above prior art arithmetic operation methods.
[0046] The modular exponentiation device is composed of a generalpurpose microprocessor CPU, a RAM, and other elements.
[0047] The CPU, in addition to executing controls, performs modular multiplication and modular squaring. The RAM stores computer programs, table data, and calculation results. The computer programs are for executing the above binary method or small window method, and the CPU performs the binary method or the small window method in accordance with the computer programs.
[0048] In this extremely simple structure the CPU performs all of the arithmetic operations. The processing speeds of this simple structure are slow as a result of there being no specialized control circuits or calculation circuits.
[0049] A Variation of the Modular Exponentiation Device
[0050] The structure of this variation is different from the known modular exponentiation device discussed above. Instead of a generalpurpose CPU, the device described here employs a coprocessor to perform the modular exponentiation, the coprocessor being capable of executing a number of dedicated operations at high speed. Thus, in addition to the generalpurpose microprocessor CPU, this modular exponentiation device is characterized by including a coprocessor for conducting dedicated arithmetic operations.
[0051] In this device the CPU notifies the coprocessor to commence the operations. The coprocessor includes a control unit for controlling the other element of the device, a calculation unit for performing the modular exponentiation, a table data storage unit of storing the various table data, and a calculation result storage unit for storing the calculation results.
[0052] The control unit selects from the table data storage unit the data to be used for calculations in the calculation unit and transfers the selected data to the calculation unit. The calculation unit performs modular squarings and modular multiplications using the table data selected by the control unit and the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit.
[0053] As described above, the coprocessor includes elements for storing the table data and the calculation results. This structure is adopted because the internal memory of the coprocessor is able to access the data faster than the external RAM when the control unit requires the data.
[0054] The separation of the control unit and the calculation unit in this structure allows for the operations to be performed at high speed. However, it is necessary to provide a table data storage unit accessible by the calculation unit, thus requiring the coprocessor to have a large internal memory.
[0055] Also, since the coprocessor is responsible for all the computation processing, the function of the CPU is limited to notifying the coprocessor to initiate the operations. The CPU, therefore, plays no part in the modular exponentiation operations performed by the coprocessor.
[0056] A Further Variation of the Modular Exponentiation Device
[0057] The following description relates to a further variation of the modular exponentiation device. This device is composed of a generalpurpose microprocessor CPU and a coprocessor for performing dedicated arithmetic operations. The coprocessor includes a control unit, two calculation units (first and second calculation units), a table data storage unit for storing table data, and a calculation result storage unit for storing calculation results. The coprocessor operates the two calculation units in parallel.
[0058] The control unit selects data to be used in the calculations performed in the first calculation unit from the table data storage unit, and transfers the data to the first calculation unit. The first calculation unit performs modular multiplications using the table data selected by the control unit and the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit. The second calculation unit performs modular squarings on the calculation results stored in the calculation result storage unit, and stores the results of the calculations in the calculation result storage unit.
[0059] By separating the calculation unit into first and second calculation units and having the two calculation units operate in parallel, it is possible for this device to perform the operations even faster than the above modular exponentiation device. As in the above device, the coprocessor in this structure is responsible for all the computation processing, and the CPU is only required to notify the coprocessor to initiate the operations. Thus the CPU plays no part in the modular exponentiation operations performed by the coprocessor. Naturally, the fact of there being two calculation units necessitates an increase in coprocessor circuitry.
[0060] As demonstrated above, a modular exponentiation device that relies on the CPU to perform all the arithmetic operations is unable to achieve an adequate operating frequency, resulting in the slow performance of the modular exponentiation calculations. The operating frequency can be improved by introducing a coprocessor to perform dedicated operations, although the coprocessor then requires a large internal memory.
[0061] Using the binary method, which only requires a small memory capacity, instead of the small window method, which needs a voluminous table, helps to reduce the memory requirements. The problem now is the relative computational slowness of the binary method in comparison to the small window method.
[0062] The speed at which modular exponentiation is performed according to the binary method can be improved by operating two coprocessors in parallel, although this problematically requires a doubling of the coprocessor circuitry.
[0063] In view of the issues discussed above, an objective of the present invention is to provide (i) an information security device, (ii) devices, methods, and computer programs for performing exponentiation, modular exponentiation, and elliptic curve exponentiation, and (iii) a storage medium for storing the computer programs. Provision of the above allows for the execution of highspeed power operation methods such as the small window method, and does not require increases in either coprocessor circuitry or memory capacity.
[0064] The above objective can be achieved 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. In this device, the group is formed from a predetermined set and a binary operation performed using elements of the set, the power operation k & A involves 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 is to determine the element k, when k exists, such that an element Y=k & A in the group.
[0065] Furthermore, the device includes (i) an initializing unit for storing the identity element as an initial value in a variable X and a variable B_{2}, (ii) a 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 power operation k & A, the result of the power operation k & A being stored in the variable X at the completion of the repetitions, (iii) the calculation unit for performing 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_{2}, and storing the further binary operation result in the variable X, (iv) the storage unit for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B_{1}, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and (v) the exchange unit for exchanging the operand in the variable B_{2 }for the operand in the variable B_{1 }when the operations conducted by the calculation means and the storage means have been completed.
[0066] This structure of the invention allows for the operation conducted by the storage unit to be carried out in parallel with the operation conducted by the calculation unit, while at the same time executing the highspeed power operation method. Highspeed power operations can be achieved as a result.
[0067] Furthermore, the storage unit can include (i) a selection subunit for preventing the selection of the operand when a section of the bit sequence of k conforms to a predetermined bit sequence pattern, and (ii) a data storage subunit for preventing the storage of a selected operand in the variable B_{1 }when the selection subunit has prevented the selection of the operand. Then in the following step when the data storage subunit has prevented the storage of an operand in the variable B_{1}, the calculation unit can perform the binary operation using the variable X and the same variable X, perform the binary operation again using the initial binary operation result and the identity element, and store the further binary operation result in the variable X.
[0068] This structure of the invention allows for the binary operation performed by the coprocessor to be conducted in parallel with the data transfer between the CPU and the coprocessor, while at the same time reducing the access capacity of the coprocessor. Highspeed power operations can be achieved as a result.
[0069] These and other objects, advantages, and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings that illustrate specific embodiments of the present invention.
[0070] In the drawings:
[0071]FIG. 1 is a block diagram showing a structure of a digital signature system 1 according to a first embodiment of the present invention;
[0072]FIG. 2 is a flowchart showing the digital signature operations conducted by digital signature system 1;
[0073]FIG. 3 is a block diagram showing a structure of a user A device 10;
[0074]FIG. 4 is a flowchart showing the operations when elliptic curve exponentiation is performed by a CPU, a DMA control unit, and a coprocessor included in user A device 10;
[0075]FIG. 5 is a flowchart showing the operations when elliptic exponentiation is performed by user A device 10;
[0076]FIG. 6 is a flowchart showing in detail the conversion of k_{i }to k′_{i};
[0077]FIG. 7 is a timechart showing the timing of calculation processing carried out by a prior art CPU and coprocessor;
[0078]FIG. 8 is a timechart showing the timing of calculation processing carried out by the CPU, the DMA control unit, and the coprocessor included in user A device 10;
[0079]FIG. 9 is a block diagram showing a structure of a key sharing system 1b according to a further embodiment of the present invention;
[0080]FIG. 10 is a flowchart showing the key sharing operations conducted by key sharing system 1b;
[0081]FIG. 11 is a flowchart showing the operations when modular exponentiation is performed in key sharing system 1b;
[0082]FIG. 12 is a flowchart showing the exponentiation operations performed by a device according to yet another embodiment of the present invention;
[0083]FIG. 13 is a flowchart showing the exponentiation operations performed by a device according to still yet another embodiment of the present invention (continued in FIG. 13); and
[0084]FIG. 14 is a continuation of the flowchart shown in FIG. 13.
[0085] 1. First Embodiment
[0086] The following description relates to a digital signature system 1 as a first embodiment of the present invention.
[0087] 1.1 Structure of Digital Signature System 1
[0088] Digital signature system 1 employs the DSA signature scheme, the security of which is based on the intractability of the elliptic curve discrete logarithm problem.
[0089] As shown in FIG. 1, system 1 is composed of a user A device 10, a management center device 20, and a user B device 30. Devices 10, 20, and 30 are connected to each other via the Internet 2.
[0090] Management center device 20 stores the secret key of user A device 10, uses the stored secret key of device 10 to generate a public key, and makes the generated public key available to user B device 30.
[0091] In order to transmit a message to device 30 via the Internet 2, device 10 generates a signature using its secret key. The signature is then sent together with the message to device 30 via the Internet 2. Device 30 receives the message and signature from device 10, and uses the public key to verify that the message was sent from device 10.
[0092] (1) Structure of Management Center Device 20
[0093] As shown in FIG. 1, device 20 is composed of an information storage unit 21, a public key generation unit 22, and a transmitterreceiver unit 23. An elliptic curve exponentiation unit 24 is included in unit 22.
[0094] Information Storage Unit 21
[0095] For the purposes of this specification, p is a prime, E is an elliptic curve defined over a finite field GF(p), G is a base point lying on E, and q is an order of E. As such, q is the smallest positive integer that satisfies the equation:
q*G=0
[0096] where 0 is the point at infinity and has x,y coordinates of (∞, ∞). “0” functions as the zero element in addition operations when the elliptic curve is determined to be a group.
[0097] Unit 21 stores the secret key X_{A }Of user A (having previously received notification of the secret key X_{A }from user A), prime p, the parameters of elliptic curve E, base point G, and order q.
[0098] Public Key Generation Unit 22
[0099] Unit 22 reads secret key X_{A}, prime p, elliptic curve E parameters, base point G, and order q from information storage unit 21.
[0100] Elliptic curve exponentiation unit 24 included in unit 22 uses the read secret key X_{A }to generate a public key Y_{A }of user A such that:
Y _{A} =X _{A} *G
[0101] The operation performed is an elliptic curve exponentiation on elliptic curve E defined over finite field GF(p).
[0102] Unit 22 then outputs the generated public key Y_{A }to transmitterreceiver unit 23.
[0103] Transmitterreceiver Unit 23
[0104] Unit 23 reads prime p, elliptic curve E parameters, base point G, and order q from information storage unit 21, and transmits them to devices 10 and 30 via the Internet 2. Management center device 20 thereby makes public prime p, elliptic curve E parameters, base point G, and order q.
[0105] Also, unit 23 receives public key Y_{A }from public key generation unit 22 and transmits the received public key to user B device 30 via the Internet 2.
[0106] (2) Structure of User A Device 10
[0107] As shown in FIG. 1, device 10 is composed of a message storage unit 11, a signature unit 12, and a transmitterreceiver unit 13. An elliptic curve exponentiation unit 14 is included in unit 12.
[0108] Message Storage Unit 11
[0109] Unit 11 stores a message m_{e }to be sent to user B device 30.
[0110] Signature Unit 12
[0111] Unit 12 receives output of prime p, elliptic curve E parameters, base point G, and order q from transmitterreceiver unit 13.
[0112] Unit 12 then reads message m_{e }from message storage unit 11, and also generates a random number r_{0}.
[0113] Next, unit 12 calculates:
R_{1}=(r_{x}, r_{y})=r_{0}*G
[0114] The operation here involves an elliptic curve exponentiation on the elliptic curve E defined over finite field GF(p).
[0115] Unit 12 then determines s such that:
×r_{0}=m_{e}+r_{X}×X_{A }(mod q)
[0116] Unit 12 then outputs the calculated values of R_{1 }and s to transmitterreceiver unit 13.
[0117] Transmitterreceiver Unit 13
[0118] Unit 13 receives transmission of prime p, elliptic curve E parameters, base point G, and order q from management center device 20, and outputs them to signature unit 12.
[0119] Unit 13 receives output of R_{1 }and s from signature unit 12, and reads message me from message storage unit 11.
[0120] Unit 13 also transmits message m_{e }and (R_{1}, s) as a signature to user B device 30 via the Internet 2.
[0121] (3) Structure of User B Device 30
[0122] As shown in FIG. 1, device 30 is composed of a message storage unit 31, a verification unit 32, and a transmitterreceiver unit 33. An elliptic curve exponentiation unit 34 is included in unit 32.
[0123] Message Storage Unit 31
[0124] Unit 31 has an area for storing message m_{e}.
[0125] TransmitterReceiver Unit 33
[0126] Unit 33 receives transmission of prime p, elliptic curve E parameters, base point G, order q, and public key Y_{A }from management center device 20 via the Internet 2, and outputs them to verification unit 32.
[0127] Unit 33 also receives transmission of message m_{e }and signature (R_{1}, s) from user A device 10 via the Internet 2. Unit 33 then writes message m_{e }into message storage unit 31 and outputs signature (R_{1}, s) to verification unit 32.
[0128] Verification Unit 32
[0129] Unit 32 receives output of prime p, elliptic curve E parameters, base point G, order q, public key Y_{A}, and signature (R_{1}, s) from transmitterreceiver unit 33.
[0130] Unit 32 then judges whether the following equation holds true:
s*R _{1} =m _{e} *G+r _{x} *Y _{A}
[0131] This operation includes an elliptic curve exponentiation on the elliptic curve E defined over finite field GF(p). Elliptic curve exponentiation unit 34 included in unit 32 performs the elliptic curve exponentiation.
[0132] If this equation holds true, then user A device 10 is verified as being the transmitter of message m_{e}. If the equation does not hold true, then user A device 10 is not verified as the transmitter of message m_{e}.
[0133] The above equation is derived as follows:
[0134] 1.2 Operation of Digital Signature System 1
[0135] The operation of digital signature system 1 is described with reference to the flowchart in FIG. 2.
[0136] Elliptic curve exponentiation unit 24 in public key generation unit 22 of management center device 20 uses secret key X_{A }to generate public key Y_{A }of user A (step S101). Transmitterreceiver unit 23 in device 20, makes prime p, elliptic curve E parameters, base point G, and order q public by transmitting them to devices 10 and 30 via the Internet 2 (step 102). Unit 23 also makes public key Y_{A }of device 10 public by transmitting it to user B device 30 via the Internet 2 (step S103).
[0137] Next, signature unit 12 in user A device 10 generates a random number r_{0 }(step S104), calculates R_{1}=(r_{x}, r_{y})=r_{0}*G, (step S105), and determine s such that s×_{r0}=m_{e}+r_{x}×x_{A }mod q (step S106) Transmitterreceiver unit 13 in device 10 then transmits message m_{e }and signature (R_{1}, s) to user B device 30 via the Internet 2 (step S107).
[0138] Next, transmitterreceiver unit 33 in device 30 receives transmission of message m_{e }and signature (R_{1}, s) from device 10 via the Internet 2 (step S107). Then in order to verify whether the transmitter of message m_{e }was in fact user A device 10, verification unit 32 in device 30 judges whether the equation s*R_{1}=m_{e}*G+r_{x}*Y_{A }holds true (step S108)
[0139] 1.3 Detailed Structure of User A device 10
[0140] The following detailed description relates to user A device 10, and focuses particularly on the structure of elliptic curve exponentiation unit 14.
[0141] Unit 14 as described below performs an elliptic curve exponentiation k*A, and assigns the result of the operation to variable X.
[0142] Also, since elliptic curve exponentiation units 24 and 34 in devices 20 and 30, respectively, are structurally related to unit 14, a description of units 24 and 34 has been omitted.
[0143] As shown in FIG. 3, user A device 10 is composed of a a CPU 101, a RAM 102, a display unit 103, an input unit 104, a transmitterreceiver unit 105, a direct memory access (DMA) control unit 106, a coprocessor 40, a data bus 111, and an address bus 112. CPU 101, RAM 102, and units 103, 104, 105, 106 and 40, are connected to each other via data bus 111 and address bus 112.
[0144] Coprocessor 40 includes a control unit 401, a memory unit 402, a RAM 403, a calculation unit 404, a data bus 411, and an address bus 412. Units 401, 402 and 404, and RAM 403, are connected to each other via data bus 411 and address bus 412.
[0145] In addition, control unit 401, memory unit 402, and RAM 403 are also connected to data bus 111 and address bus 112.
[0146] Elliptic curve exponentiation unit 14 is composed of CPU 101, RAM 102, DMA control unit 106, coprocessor 40, data bus 111, and address bus 112. Unit 14 functions by means of CPU 101 and coprocessor 40 operating in accordance with a computer program.
[0147] (1) RAM 102
[0148] RAM 102 is composed of a readable/writable semiconductor memory.
[0149] RAM 102 stores elliptic curve exponentiation value k and calculation value A used in the elliptic curve exponentiation X=k*A. Take, for example, bit lengths of 160 and 480 bits, respectively, for k and A. A 480bit length is determined for A because it is possible to improved the efficiency of the calculation on the elliptic curve by using an expanded threedimensional coordinate system for A.
[0150] Areas are allocated in RAM 102 by CPU 101, and these allocated areas are used by CPU 101.
[0151] (2) CPU 101
[0152] CPU 101 is a generalpurpose microprocessor and operates in accordance with a computer program stored in RAM 102. The following description relates to the operations of CPU 101.
[0153] In order to perform the elliptic curve exponentiation k*A, CPU 101 initially executes the following initialization procedures (i) to (iii).
[0154] (i) CPU 101 outputs an initialization instruction to coprocessor 40 via data bus 111 and address bus 112.
[0155] (ii) CPU 101 assigns a value n−1 to variable i. Variable i is an index used to control the repetitions of elliptic curve exponentiation k*A. CPU 101 allocates a storage area for variable i in RAM 102. Alternatively, it is possible to allocate a storage area for variable i in one of the resistors included in CPU 101.
[0156] The value n is a bit number showing the length of the area needed to store k.
[0157] Also, a zero value is assigned to the variables k_{n+1}, k_{n}, k_{−1}, k_{−2}.
[0158] (iii) CPU 101 allocates an area in RAM 102 for storing variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}. Each of variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1 }has a 480bit length.
[0159] CPU 101 calculates m=2^{w−1 }and 3*A, 5*A, . . . , (2m−1) *A where W is a window size. CPU 101 then assigns the results of A, 3*A, 5*A, . . . , (2m−1) *A respectively to variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, stored in RAM 102.
[0160] Next, CPU 101 repeats the following steps (i) to (iv) while subtracting 1 from variable i per repetition until i =n−1 becomes i=0.
[0161] (i) CPU 101 converts k_{i }to k′_{i }(note: conversion process described in greater detail below)
[0162] Here, as described in relation to the prior art, k_{i }takes the value of the i^{th }bit from the bottom of the bit sequence of k where k is represented in binary, and k′_{i }represents a collective plurality of k_{i }values. In other words, the value of k_{i }is 0 or 1, and the value of k′_{i }is one of 0, 1, . . . , m−1. Also, m=2^{w−1 }where w is a window size.
[0163] (ii) CPU 101 outputs a DMA transfer instruction to DMA control unit 106 via data bus 111 and address bus 112.
[0164] (iii) CPU 101 outputs a calculation instruction to coprocessor 40 via data bus 111 and address bus 112.
[0165] (iv) CPU 101 receives output of a calculation completion notification from coprocessor 40 via data bus 111 and address bus 112.
[0166] When the repetitions have been completed, CPU 101 reads, as the result of the elliptic curve exponentiation k*A, variable X stored in RAM 403, and writes this result into a specified area in RAM 102.
[0167] (3) DMA Control Unit 106
[0168] Unit 106 receives output of the transfer instruction from CPU 101 via data bus 111 and address bus 112.
[0169] On receipt of the transfer instruction, unit 106 transfers Ak′_{i }stored in RAM 102 to memory unit 402 of coprocessor 40 in order to set the value of variable B_{1 }stored in memory unit 402 such that:
B_{1}=Ak′_{i}
[0170] However, if k′_{i}=0 then B_{1}=0.
[0171] When B_{1 }has been set, unit 106 outputs a transfer completion notification to coprocessor 40.
[0172] (4) RAM 403
[0173] RAM 403 is composed of a readable/writable semiconductor memory. RAM 403 includes an area for storing variable X. This area has a 480bit length.
[0174] (5) Control Unit 401
[0175] Unit 401 receives output of the initialization instruction and the calculation instruction from CPU 101. Unit 401 also receives output of the transfer completion notification from DMA control unit 106.
[0176] On receipt of the initialization instruction, unit 401 sets the value of variable X stored in RAM 403 to 0, and the value of variable B_{2 }stored in memory unit 402 to 0.
[0177] On receipt of the calculation instruction, unit 401 outputs a calculation instruction to calculation unit 404. Unit 401 also receives the calculation completion notification outputted from calculation unit 404.
[0178] On receipt of the calculation completion notification and the transfer completion notification, unit 401 outputs a memory switch instruction to memory unit 402, and then outputs a calculation completion notification to CPU 101.
[0179] (6) Memory Unit 402
[0180] Unit 402 is composed of a first memory area 402a and a second memory area 402b.
[0181] Area 402a is connected to either buses 111 and 112 or buses 411 and 412. Area 402b is also connected to either buses 111 and 112 or buses 411 and 412.
[0182] If area 402a is connected to buses 111 and 112, then area 402b is connected to buses 411 and 412. This is referred to as “connection condition 1.”
[0183] Conversely, if area 402a is connected to buses 411 and 412, then area 402b is connected to buses 111 and 112. This is referred to as “connection condition 2.”
[0184] Unit 402 receives output of the memory switch instruction from control unit 401.
[0185] If unit 402 is in connection condition 1 when the memory switch instruction is received, then unit 402 switches from connection condition 1 to connection condition 2.
[0186] On the other hand, if unit 402 is in connection condition 2 when the memory switch instruction is received, then unit 402 switches from connection condition 2 to connection condition 1.
[0187] One of variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1 }is stored in a variable storage area in first memory area 402a, this area being indicated by a specific address. One of the variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}is also stored in a variable storage area in second memory area 402b, this area being indicated by the same address as used to store the variable in first memory unit 402a.
[0188] When unit 402 is in connection conditions 1 or 2, the variable stored in the variable storage area of the memory area connected to buses 111 and 112 is referred to as B_{1}, and the variable stored in the variable storage area of the memory area connected to buses 411 and 412 is referred to as B_{2}.
[0189] (7) Calculation Unit 404
[0190] Unit 404 receives output of the calculation instruction from control unit 401.
[0191] On receipt of the calculation instruction, unit 404 reads variable X from RAM 403, calculates 2*X, and overwrites variable X with the result. Next, unit 404 reads variable X from RAM 403, calculates X+B_{2}, and overwrites variable X with the result.
[0192] When this calculation has been completed, unit 404 outputs a calculation completion notification to control unit 401.
[0193] 1.4 Detailed Operation of User A Device 10
[0194] The following detailed description relates the operation of user A device 10, and focuses in particular on the operation of elliptic curve exponentiation unit 14, with reference to the flowcharts in FIGS. 4 and 5.
[0195] The flowchart in FIG. 4 shows the operations of the individual elements included in unit 14, and the flowchart in FIG. 5 shows the overall operation of unit 14.
[0196] CPU 101 outputs an initialization instruction to coprocessor 40 via data bus 111 and address bus 112 (step S201).
[0197] On receipt of the initialization instruction, control unit 401 in coprocessor 40 sets the value of variable X stored in RAM 403 to 0 and the value of variable B_{2 }stored in memory unit 402 to 0 (step S202).
[0198] CPU 101 assigns a value of n−1 to variable i and a value of 0 to variables k_{n+1}, k_{n}, k_{−1}, k_{−2 }(step S203) . Next, CPU 101 allocates an area in RAM 102 for storing variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, calculates m=2^{w−1 }and 3*A, 5*A, . . . , (2m−1)* A, and assigns the results of A, 3*A, 5*A, . . . , (2m−1)*A, respectively to A_{0}, A_{1}, A_{2}, . . . , A_{m−1 }stored in RAM 102, (step S204).
[0199] CPU 101 then outputs a calculation instruction to coprocessor 40 via data bus 111 and address bus 112 (step S208).
[0200] Next, CPU 101 judges whether i ≧0, and if “yes” (step S205), then CPU 101 converts k_{i }to k′_{i }(step S206) and outputs a DMA transfer instruction to DMA control unit 106 via data bus 111 and address bus 112 (step S207).
[0201] On receipt of the DMA transfer instruction from CPU 101 (step S207), DMA control unit 106 sets the value of variable B_{1 }stored in memory unit 402 of coprocessor 40 by transferring Ak′_{i }stored in RAM 102 to memory unit 402 via data bus 111 and address bus 112. However, if k′_{i}=0, then B_{1}=0 (step S209). When B_{1 }has been set, unit 106 outputs a transfer completion notification to control unit 401 in coprocessor 40 (step S212).
[0202] On receipt of the calculation instruction from CPU 101 (step S208), control unit 401 outputs a calculation instruction to calculation unit 404 (step S221). Calculation unit 404 then calculates X=2*X (step S210) and X=X+B_{2 }(step S211), and outputs a calculation completion notification to control unit 401 when the calculations have been completed (step S222).
[0203] On receipt of the transfer completion notification and calculation completion notification (steps S212 and S222), control unit 401 outputs a memory switch instruction to memory unit 402, and memory unit 402 switches to connection condition 2 when the current condition is connection condition 1, and to connection condition 1 when the current condition is connection condition 2 (step S213). Next, control unit 401 outputs a calculation completion notification to CPU 101 (step S214).
[0204] CPU 101 then subtracts 1 from value of variable i (step S215), and returns to step S205 to repeat the process.
[0205] On the other hand, if CPU 101 judges that i<0 (step S205), then CPU 101 receives a calculation completion notification (step S214), reads the value of variable X stored in RAM 403 as the result of the exponentiation k*A, writes the read result into a specified area of RAM 102 (step S216), and ends the calculation process.
[0206] The following detailed description relates to the conversion of k_{i }to k′_{i }in step S206, with reference to the flowchart in FIG. 6.
[0207] Here, k=[k_{n−1}k_{n−2 }. . . k_{1 }k_{0}] is converted to k′=[k′_{n−1 }k′_{n−2 }. . . k′_{1 }k′_{0}]. k′_{n−1}, k_{n−2}, . . . , k′_{1}, k′_{0 }each have 3bit length.
[0208] Furthermore, the values k_{n−1}, k_{n−2}, . . . , k_{1}, and k_{0 }are each either 0 or 1, and k=2_{n−1}×k_{n−1}+2_{n−2}×k_{n−2}+. . . +2_{1}×k_{1}+k_{0}. The values of k′_{n−1}, k′_{n−2}, . . . , k′_{1}, k′_{0 }are 0, 1, 3, . . . , 7, respectively.
[0209] If k_{i+2}=1 (step S401), then CPU 101 calculates k′_{i}=4×k_{i+2}+2×k_{i+1}+k_{i }(step S402) and ends the conversion process.
[0210] If k_{i+2}≠1 (step S401), and [k_{i+2 }k_{i+1 }k_{i }k_{i−1}]=[0110] (step S403), then CPU 101 determines that k′_{i}=3 (step S404), and ends the conversion process.
[0211] If k_{i+2}≠1 (step S401), [k_{i+2 }k_{i+1 }k_{i }k_{i−1}] ≠[0110] (step S403), and [k_{i+2 }k_{i+1 }k_{i }k_{i−1 }k_{i−2}]=[00100] (step S405), then CPU 101 determines that k′_{i}=1 (step S406), and ends the conversion process.
[0212] If k_{i+2}≠1 (step S401), [k_{i+2 }k_{i+1 }k_{i }k_{i−1 }]≠, [0110] (step S 403), and [k_{i+2 }k_{i+1 }k_{i }k_{i−1 }k_{i−2}]≠[00100] (step S405), then CPU 101 determines that k′_{i}=0 (step S407), and ends the conversion process.
[0213] 1.5 Evaluation of Calculations Preformed by Elliptic Curve Exponentiation Unit 14
[0214] As shown in FIG. 7, in a prior art elliptic curve exponentiation device, the CPU transfers the operand to a memory area in the coprocessor (C01). The coprocessor then converts k_{i }to k′_{1 }(C11) and performs an addition operation on the elliptic curve (C12). The conversion of k_{i }to k′_{i }and the addition operation are then repeated.
[0215] As shown in FIG. 8 in comparison, in elliptic curve exponentiation unit 14 of the present invention, CPU 101 converts k_{i }to k′_{i }(C31) and DMA control unit 106 transfers the operand a variable B_{1 }stored in a memory area of coprocessor 40 (C32).
[0216] Next, CPU 101 converts k_{i }to k′_{i }(C33) and DMA control unit 106 transfers the operand to variable B_{1 }stored in a memory area of coprocessor 40 (C34), while at the same time coprocessor 40 performs an addition operation on the elliptic curve using variable B_{2 }in the memory area (C41)
[0217] The transfer of the operand to B_{1 }by unit 106 and the addition operation using B_{2 }by coprocessor 40 are performed in parallel from then on.
[0218] Because the transfer and addition operations are performed in parallel, elliptic curve exponentiation unit 14 of the present invention allows the total calculation time to be reduced in comparison to the prior art elliptic curve exponentiation device.
[0219] 2. Second Embodiment
[0220] The following description relates to a key sharing system 1b as a further embodiment of the present invention.
[0221] 2.1 Structure of Key Sharing System 1b
[0222] As shown in FIG. 9, key sharing system 1b, the security of which is based on the intractability of the discrete logarithm problem for a finite field, is composed of a user A device 10b and a user B device 30b. Device 10b and 30b are connected to each other via the Internet 2.
[0223] Device 10b and 30b each store their own secret key. Public keys for each of device 10b and 30b are generated using the respective secret keys, and the respective public keys i are sent to the other device (that is, device 10b public key to device 30b and vice versa). Then, using the public key of the other device, devices 10b and 30b each generate a single shared key.
[0224] Secret communication of messages between devices 10b and 30b can thereafter be conducted using the shared key.
[0225] (1) Structure of User A Device 10b
[0226] As shown in FIG. 9, device 10b is composed of a key generation unit 11b, a transmitterreceiver unit 12b, a key storage unit 13b, an encryption unit 14b, and a message storage unit 15b.
[0227] Key Storage Unit 13b
[0228] Unit 13b stores a secret key X_{A }of user A device 10b. Unit 13b further includes areas for storing public key Y_{A }of user A device 10b and a shared key F of devices 10b and 30b.
[0229] Key Generation Unit 11b
[0230] Unit 11b includes a modular exponentiation unit 16b.
[0231] Unit 11b reads secret key X_{A }from key storage unit 13b and generates public key Y_{A }using secret key X_{A }such that:
Y_{A}=α**X_{A }mod p
[0232] where α and p are predetermined integers. The operator ** indicates an exponentiation operation. For example, A **k represents A^{k}.
[0233] The calculation of the above equation is performed by unit 16b.
[0234] Next, unit 11b sends the generated public key Y_{A }to device 30b via transmitterreceiver unit 12b and the Internet 2.
[0235] Unit 11b also receives transmission of public key Y_{B }from user B device 30b via the Internet 2 and unit 12b. Unit 11b then uses the transmitted public key Y_{B }to generate shared key F such that:
[0236] The calculation of the above equation is performed by unit 16b.
[0237] Next, unit 11b writes the generated shared key F into key storage unit 13b.
[0238] Message Storage Unit 15b
[0239] Unit 15b stores a message to be sent to device 30b.
[0240] Encryption Unit 14b
[0241] Unit 14b reads the message from message storage unit 15b and shared key F from key storage unit 13b.
[0242] Then, unit 14b generates an encrypted message derived from shared key F by implementing an encryption algorithm with respect to the message, and transmits the encrypted message to device 30b via transmitterreceiver unit 12b and the Internet 2.
[0243] (2) Structure of User B Device 30b
[0244] As shown in FIG. 9, device 30b is composed of a transmitterreceiver unit 31b, a key generation unit 32b, a decryption unit 33b, a key storage unit 34b, and a message storage unit 35b.
[0245] Key Storage Unit 34b
[0246] Unit 34b stores a secret key X_{B }of device 30b. Unit 34b further includes areas for storing public key Y_{B }of device 30b and shared key F of devices 10b and 30b.
[0247] Key Generation Unit 32b
[0248] Unit 32b includes a modular exponentiation unit 36b.
[0249] Unit 32b reads secret key X_{B }from key storage unit 34b and uses the read secret key X_{B }to generate public key Y_{B }such that:
Y_{B}=α**X_{B }mod p
[0250] where α and p are predetermined integers. The operator **indicates an exponentiation operation.
[0251] The calculation of the, above equation is performed by unit 36b.
[0252] Next, unit 32b sends the generated public key Y_{B }to user A device 10b via transmitterreceiver unit 31b and the Internet 2.
[0253] Unit 32b also receives transmission of public key Y_{A }from device 10b via the Internet 2 and unit 31b. Unit 32b then uses the transmitted public key Y_{A }to generate shared key F such that:
[0254] The calculation of the above equation is performed by unit 36b.
[0255] Next, unit 32b writes the generated shared key F into key storage unit 34b.
[0256] Message Storage Unit 35b
[0257] Unit 35b stores the encrypted message sent from device 10b.
[0258] Decryption Unit 33b
[0259] Unit 33b receives transmission of the encrypted message from device 10b via the Internet 2 and transmitterreceiver unit 31b. Unit 33b also reads shared key F from key storage unit 34b.
[0260] Then, unit 33b generates a decrypted message derived from shared key F by implementing a decryption algorithm with respect to the encrypted message.
[0261] The decryption algorithm referred to here is an algorithm for performing an inversion of the encryption algorithm.
[0262] Unit 33b then writes the decrypted message into message storage unit 35b.
[0263] 2.2 Operation of Key Sharing System 1b
[0264] The operation of system 1b is described with reference to the flowchart in FIG. 10.
[0265] Key generation unit 11b reads secret key X_{A }from key storage unit 13b and uses the read secret key X_{A }to generate public key Y_{A }such that:
Y_{A}α=α**X_{A }mod p (step S301)
[0266] Unit 11b then sends the generated public key Y_{A }to user B device 30b via transmitterreceiver unit 12b and the Internet 2 (step S302).
[0267] Key generation unit 32b reads secret key X_{B }from key storage unit 34b and uses the read secret key X_{B }to generate public key Y_{B }such that:
Y_{B}=α**X_{B }mod p (step S311)
[0268] Unit 32b then sends the generated public key Y_{B }to user A device 10b via transmitterreceiver unit 31b and the Internet 2 (step S312).
[0269] Next, key generation unit 11b receives transmission of public key Y_{B }from device 30b via the Internet 2 and transmitterreceiver unit 12b, and uses the received public key Y_{B }to generate shared key F such that:
F=Y_{B}**X_{A }mod p
[0270] Unit 11b then writes the generated shared key F into key storage unit 13b (step S303).
[0271] Next, key generation unit 32b receives transmission of public key Y_{A }from device 10b via the Internet 2 and transmitterreceiver unit 31b, and uses the received public key Y_{A }to generate shared key F such that:
F=Y_{A}**X_{B }mod p
[0272] Unit 32b then writes the generated shared key F into key storage unit 34b (step S313).
[0273] Next, encryption unit 14b reads the message from message storage unit 15b and shared key F from key storage unit 13b, generates the encrypted message derived from shared key F by implementing the encryption algorithm (step S304), and then transmits the encrypted message to device 30b via transmitterreceiver unit 12b and the Internet 2 (step S305).
[0274] Next, decryption unit 33b receives transmission of the encrypted message from device 10b via the Internet 2 and transmitterreceiver unit 31b, reads shared key F from key storage unit 34b, and generates the decrypted message derived from shared key F by implementing the decryption algorithm with respect to the encrypted message (step S314).
[0275] 2.3 Detailed Structure of User A Device 10b
[0276] The following detailed description relates to user A device 10b, and focuses particularly on the structure of modular exponentiation unit 16b.
[0277] Unit 16b as described below performs a modular exponentiation A**k mod p, and assigns the result of the operation to variable X.
[0278] Since unit 16b is similar in structure to elliptic curve exponentiation unit 14 in user A device 10, the description will focus on the differences between the two units.
[0279] Also, since modular exponentiation unit 36b in device 30b is structurally related to unit 16b in device 10b, a description of unit 36b has been omitted. CPU 101
[0280] In order to perform the modular exponentiation A**k mod p, CPU 101 executes the following initial procedure.
[0281] CPU 101 calculates A**3, A**5, . . . , A**(2m−1) mod p, and assigns the results of A, A**3, A**5, . . . , A**(2m−1) mod p to A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, respectively.
[0282] DMA Control Unit 106
[0283] Unit 106 sets the value of variable B_{1 }such that B_{1}=1 if k′_{i}=0.
[0284] Control Unit 401
[0285] On receipt of the initialization instruction, unit 401 sets the value of variable X stored in RAM 403 to 1, and the value of variable B_{2 }stored in memory unit 402 to 1.
[0286] Calculation Unit 404 On receipt of the calculation instruction, unit 404 reads variable X from RAM 403, calculates X**2 mod p, and overwrites variable X with the result. Unit 404 then reads variable X from RAM 403, calculates X×B_{2 }mod p, and overwrites variable X with the result.
[0287] 2.4 Detailed Operation of User A Device 10b
[0288] The following detailed description relates the operation of user A device 10b, and focuses in particular the operation of modular exponentiation unit 16b, with reference to the flowchart in FIG. 11.
[0289] Since the FIG. 11 flowchart is similar to the FIG. 5 flowchart the description will focus on the differences between the two flowcharts.
[0290] On receipt of the initialization instruction, control unit 401 sets the value of variable X stored in RAM 403 to 1 and the value of variable B_{2 }stored in memory unit 402 to 1 (step S202b ) CPU 101 allocates an area in RAM 102 for storing variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, calculates m=2^{w−1 }and A**3, A**5, . . . , A*(2m−1) mod p, and assigns the results of A, A**3, A**5, . . . , A**(2m−1) mod p respectively to A_{0}, A_{1}, A_{2}, . . . , A_{m−1 }stored in RAM 102 (step S204b )
[0291] DMA control unit 106 sets the value of variable B_{1 }stored in memory unit 402 of coprocessor 40 by transferring A k′_{i }stored in RAM 102 to memory unit 402 via data bus 111 and address bus 112. However, if k′_{i}=0, then B_{1}=1 (step S209b).
[0292] Calculation unit 404 calculates X=X**2 mod p (step S210b ) and X=X×B_{2 }mod p (step S211b ).
[0293]3. Summary
[0294] As described above in relation to the present invention per the embodiments, a relatively large table as required by the small window method is generated outside of the coprocessor, and the selection and transfer of data included in the table is conducted in parallel with the calculations performed in the coprocessor. Furthermore, so as to prevent bottlenecks from occurring in the data transfer between the CPU and the coprocessor, two banks are included in the coprocessor for use in the calculations.
[0295] The modular exponentiation device of the present invention calculates A^{k }mod p where p and k are specified positive integers and A is a positive integer less than p.
[0296] Furthermore, the device includes the following units: an operand parameter storage unit for storing one or more operand parameters that are based on A and p; first and second operand storage units for storing operands; an intermediate value storage unit for storing an intermediate value; an intermediate value initialization unit for setting the intermediate value as an initial value; an operand selection unit for scanning k in descending order and selecting as an operand from the operand parameter storage unit an operand parameter corresponding to a section of the bit pattern of k; an operand transfer unit for (i) reading the selected operand from the operand parameter storage unit, and (ii) transferring the read operand to one of the two operand storage units; an intermediate value renewal unit for (i) reading an operand from the operand storage unit that did not receive transfer of the operand from the operand transfer unit, (ii) reading the intermediate value from the intermediate value storage unit, and (iii) writing into the intermediate value storage unit the result of a predetermined arithmetic operation on p and the read intermediate value; an operand switching unit for switching the functions of the two operand storage units; a parallel processing control unit for controlling the operand selection unit and the operand transfer unit to transfer, in parallel with the arithmetic operation performed by the intermediate value renewal unit, the operand to be used in the following arithmetic operation; and a calculation result output unit for outputting as the calculation result the value stored in the intermediate value storage unit when all the calculations involving k have been completed.
[0297] In this construction, it is desirable for access to the table to be limited to the operand selection unit and the operand transfer unit. Further, it is desirable for the intermediate value renewal unit to only have access to a restricted amount of the memory of the first and second operand storage units and the intermediate value storage unit.
[0298] According to the present invention, it is possible to perform highspeed exponentiation operations while at the same time reducing the access capacity of the coprocessor. A highspeed operating frequency is achieved by providing two calculation result storage units in the coprocessor and interchanging their functions. This effectively allows data transfer between the CPU and the coprocessor to be conducted in parallel with the execution of the arithmetic operation by the coprocessor.
[0299] When the bit width used in the calculations is increased in order to improve the security of the system, the data volume requirements in the coprocessor need only increase by an amount equal to the memory taken to store the additional bit width in the operand storage units and the intermediate value storage unit, since any increase in table size is accommodated by the CPU. This structure thus enables highspeed modular exponentiation to be conducted by a coprocessor having minimal circuitry.
[0300] 4. Variations of the Embodiments
[0301] Although described in terms of the above embodiments, the present invention is not limited to these embodiments, and the following variations are therefore applicable.
[0302] (1) In addition to modular exponentiation operations, it is also possible to perform nonmodular exponentiation operations in modular exponentiation unit 16b in user A device 10.
[0303] This variation is described below with reference to the flowchart in FIG. 12. As FIG. 12 is similar to FIG. 11, the description will focus on the differences.
[0304] CPU 101 allocates an area in RAM 102 for storing variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, calculates m=2^{w−1 }and A**3, A**5, . . . , A**(2m−1), and assigns the results of A, A**3, A**5, . . . , A**(2m−1) respectively to A_{0}, A_{1}, A_{2}, . . . , ) A_{m−1}, stored in RAM 102 (step S204c).
[0305] Calculation unit 404 calculates X=X**2 (step S210c) and X=X×B_{2 }(step S211c)
[0306] (2) According the embodiments of the present invention, the exponentiation A^{k }is performed by the coprocessor in a descending order of k. However, as shown below, it is possible for CPU 101 to perform the operation A^{k }in an ascending of k in parallel with the descending order operation performed by the coprocessor. This variation is carried out as follows.
[0307] Here, k=[k_{n−1 }k_{n−2 }k_{n−3 }. . . k_{0}] (where k_{n−1}, k_{n−2}, k_{n−3}, . . . , k_{0}are each either 0 or 1).
[0308] Exponent k is divided into (n−x) higher order bits and x lower order bits. Generated as a result is k_{H }and k_{L}, where k_{H }is formed from the (n−x) higher order bits and x number of zeros, and k_{L }is formed from (n−x) number of zeros and the x lower order bits. k_{H }and k_{L }are thus represented as follows.
k_{H}=[k_{n−1 }k_{n−2 }k_{n−3 }. . . k_{x }0 0 . . . 0]
k_{L}=[0 0 . . . 0 k_{x−1 }. . . k_{0}]
[0309] A**k_{H }is calculated according to the above embodiments. On the other hand, A**k_{L }is calculated by CPU 101 during a non−use period of the CPU. CPU 101 also calculates A**k=A**k_{H}×_{A}**k_{L}.
[0310] Alternatively, it is possible to conduct the parallel processing in descending and ascending order of k without the initial division of k. In this case, the final calculation is performed when the same bit of k is reached during descending and ascending order calculations. This variation is described below with reference to the flowcharts in FIGS. 13 and 14.
[0311] CPU 101 outputs an initialization instruction to coprocessor 40 via data bus 111 and address bus 112 (step S201).
[0312] On receipt of the initialization instruction, control unit 401 sets the value of variable X stored in RAM 403 to 1, and the value of variable B_{2 }stored in memory unit 402 to 1 (step S202d).
[0313] CPU 101 assigns value n−1 to variable i and 0 to variables k_{n+1}, k_{n}, k_{−1}, k_{−2 }(step S203). CPU 101 also assigns 1 to variable Y, value A to a variable C, and 0 to a variable j (step S301). CPU 101 then allocates an area in RAM 102 for storing variables A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, calculates m=2^{w−1 }and A**3, A**5, . . . , A**(2m−1), and assigns the results of A, A**3, A**5, . . . , A**(2m−1) respectively to A_{0}, A_{1}, A_{2}, . . . , A_{m−1}, stored in RAM 102 (step S204c)
[0314] CPU 101 then outputs a calculation instruction to coprocessor 40 via data bus 111 and address bus 112 (step S208).
[0315] Next, CPU 101 judges whether i≧j, and if “yes” (step S205d), then CPU 101 converts k_{i }to k′_{1 }(step S206) and outputs a DMA transfer instruction to DMA control unit 106 via data bus 111 and address bus 112 (step S207).
[0316] On receipt of the DMA transfer instruction from CPU 101 (step S207), DMA control unit 106 sets the value of variable B_{1 }stored in memory unit 402 of coprocessor 40 by transferring A k′_{i }stored in RAM 102 to memory unit 402 via data bus 111 and address bus 112 (step S209d). When B_{1 }has been set, unit 106 outputs a transfer completion notification to control unit 401 in coprocessor 40 (step S212)
[0317] On receipt of the calculation instruction (step S208), control unit 401 outputs a calculation instruction to calculation unit 404 (step S221). Calculation unit 404 then calculates X=X**2 (step S210d) and X=X×B_{2 }(step S211d), and outputs a calculation completion notification to control unit 401 when the calculations have been completed (step S222).
[0318] On receipt of the calculation completion notification and the transfer completion notification (steps S212 and S222), control unit 401 outputs a memory switch instruction to memory unit 402, and memory unit 402 switches to connection condition 2 if the current condition is connection condition 1, and to connection condition 1 if the current condition is connection condition 2 (step S213). Next, control unit 401 outputs a calculation completion notification to CPU 101 (step S214).
[0319] CPU 101 then subtracts 1 from variable i (step S215), and return to step S205d to repeat the process.
[0320] Again, if CPU 101 judges that i≧j (step S205d), then CPU 101 also calculates C=C**2 (step S311), and if k_{j}=1 (step S312), then CPU 101 calculates Y=Y×C (step S313), adds 1 to variable j (step 314), and returns to step S205d.
[0321] On the other hand, if CPU 101 judges that i<j (step S205d), then CPU 101 reads variable X stored in RAM 403 and assigns variable Z to variable X (step S321). If i≧0 (step S322), CPU 101 calculates Z=Z**2 (step S323), subtracts 1 from variable i (step S324), and returns to step S322 to repeat the process.
[0322] If i<0 (step S322), then CPU 101 receives a calculation completion notification from control unit 401 (step S214), calculates Z=Z×Y (step S325), writes variable Z into a specified area of RAM 102 as the result of the exponentiation k*A (step S326), and ends the calculation process.
[0323] (3) In digital signature system 1 as described in the above embodiments, CPU 101 calculates 3*A, 5*A, . . . , (2m−1)*A. It is, however, possible for this calculation to have been completed beforehand and stored in RAM 102. This variation is also applicable to key sharing system 1b.
[0324] (4) It is possible for elliptic curve exponentiation and modular exponentiation to be applied in such systems using encryption technology as secret communication systems, authorization systems, key exchange systems, and the like.
[0325] A secret communication system allows for the transmission of a message without the content of the message being revealed to third parties.
[0326] An authorization system allows for (i) the verification of the sender, (ii) the authentication of the message, (iii) the verification of the receiver'"'"'s access rights, (iv) the verification of the receiver, (v) and the validation of any agreements that might have been reached between parties concerned.
[0327] A key exchange system allows for the exchange of secret keys used in a secret key encryption system without the secret keys being revealed to third parties.
[0328] The security of these systems is based on the intractability of the discrete logarithm problem over finite fields and elliptic curves.
[0329] (5) As shown in the flowchart in FIG. 5, the conversion of k_{i }to k′_{i }according to the above embodiments is conducted prior to the arithmetic operations and DMA transfer performed in parallel by the coprocessor. However, it is possible for the conversion to be conducted after the arithmetic operations and DMA transfer performed by the coprocessor.
[0330] Also, as described in the above embodiments, the examination of the bits is conducted one bit at a time, although with the small window method bit patterns consisting of contiguous 0value bits are bound to occur. In this case, it is possible to skip over the contiguous 0value bits and perform a modular squaring operation on the number of bits skipped over.
[0331] Although according to the above embodiments it is necessary to conduct a DMA transfer of the operand, the transfer of the converted value of the exponent need not be conducted, which also means that the modular multiplication need not be performed.
[0332] Although the small window method was used in the examples given for the above embodiments, it is possible to use other methods such as the binary method or the comb method.
[0333] (6) It is possible to structure digital signature system 1 as described below.
[0334] According to the above embodiments as shown in FIG. 6, the value of A k′_{i }as determined by k′_{i}, which results from the conversion of k_{i }to k′_{i }performed in CPU 101, is 0. Referring to the FIG. 6 flowchart, however, if “no” is the outcome of step S405 (i.e., a judgment involving a section of the bit sequence of k), then instead of outputting a DMA transfer instruction to DMA control unit 106, it is possible for CPU 101 to instruct coprocessor 40 to perform the following steps.
[0335] Specifically, instead of X=2*X (step S210) and X=X+B_{2 }(step S211), it is possible for CPU 101 to instructs coprocessor 40 to calculate X=2*X and X=X+0, and then on receipt of the calculation instruction, coprocessor 40 can performs the instructed calculations.
[0336] This variation is also applicable to key sharing system 1b.
[0337] (7) Although the structure of the present invention as described above includes a CPU, a RAM, and a coprocessor, the present invention is not limited to this structure and can be composed of any elements that perform a similar function. For example, a HD can replace the RAM, and a hardware accelerator can replace the coprocessor.
[0338] (8) A relatively large table can be generated outside of the coprocessor so as to enable highspeed exponentiation to be performed using the small window method. The selection of data from the table and transfer of data to the coprocessor can then be conducted in parallel with a multiplelength arithmetic operation performed in the coprocessor. So as to avoid bottlenecks occurring in the data transfer between the CPU and the coprocessor, two data banks can be 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 can be switched, and the arithmetic operation then repeated using the newly transferred data while at the same time conducting data transfer in readiness for the following operation.
[0339] (9) The exponentiation A^{k}, the modular exponentiation A^{k }over a finite field, and the elliptic curve exponentiation k*A described above can be generalized as a power operation k & A. Also, the modular exponentiation operation over a finite field is one form of a modular exponentiation operation over a residue field.
[0340] The exponentiation A^{k }and the modular exponentiation A^{k }over a finite field are each formed from k repetitions of a multiplication operation using element A and the identity element value 1. The elliptic curve exponentiation k*A is formed from k repetitions of an addition operation using element A and a zero element value 0. The multiplication and addition operations are both binary operations.
[0341] (10) It is possible for the present invention to be the method described above in the embodiments. It is also possible for the method to be a computer program executed by a computer. Alternatively, the method can be a digital signal composed of a computer program.
[0342] It is furthermore possible for the present invention to store a computer program or a digital signal on a computer readable storage medium, examples of which include a flexible disc, a hard disc, a CDROM, an MO, a DVD, a DVDROM, a DVDRAM, and a semiconductor memory. Alternatively, the present invention can be the computer program or digital signal stored on the storage medium.
[0343] Also, it is possible for the present invention to transmit the computer program or the digital signal via a network such as a telecommunications circuit, a wireless communications circuit, a cable communications circuit, or the Internet.
[0344] It is further possible for the present invention to be a computer system that includes a memory and a microprocessor. In this variation, the memory can store the computer program, and the microprocessor can perform operations in accordance with the computer program.
[0345] Alternatively, it is possible for the present invention to be implemented by another computer system, this being achieved by sending the computer program or digital signal stored on the storage medium to the other computer system, or by sending the computer program or digital signal to the other computer system via the network.
[0346] (11) Furthermore, it is possible to provide a combination of any of the embodiments and variations described above.
[0347] Although the present invention has been fully described by way of examples with reference to the accompanying drawings, it is to be noted that various changes and modifications will be apparent to those skilled in the art. Therefore, unless such changes and modifications depart from the scope of the present invention, they should be construed as being included therein.