JP3779479B2 - IC card - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an IC card that processes encryption.
[0002]
[Prior art]
The basic principle of the RSA cryptosystem, which is a public key cryptosystem and was invented in 1978 by three people, Rivest, Shamir, and Adlman.
[0003]
[Basic principle of RSA encryption] When the secret key is (d, n), the public key is (e, n), the plaintext is M, and the ciphertext is C, encryption and decryption are expressed by the following formulas: Can do.
[0004]
Encryption: C≡M^e(Modn)
Decryption: M≡C^d(Modn)
Where n = p · q (p and q are large prime numbers), λ (n) = LCM {(p−1), (q−1)} (LCM: least common multiple), GCD {e, λ (n) } = 1 (GCD: greatest common divisor), d = e^-1mod λ (n) is satisfied.
[0005]
The security of RSA encryption is based on the difficulty of factoring n, and it is recommended to use large integers of about 1024 bits for parameters such as e, d, n, and M. At this time, one encryption formula M^eThe processing in modn uses a binary arithmetic method (DE Knuth, “Seminumeral algorithms (arithmetic)”, The Art of Computer Programming, Volume 2, Addison-Wesley, 1969, 15 in average). Five modular multiplication operations are required.
[0006]
Also, the basic principle of elliptic curve cryptography, which is a public key cryptosystem and was independently proposed in 1985 by Koblitz and Miller.
[0007]
[Principle of Elliptic Curve Cryptography] An outline of the elliptic curve will be described. A set obtained by adding a virtual infinity point O to a set of points satisfying the following expression with respect to parameters (a, b) that determine the order of a finite field as a prime number p and an elliptic curve is defined as an elliptic curve E_pCall it. Here, for convenience, it is expressed in a two-dimensional affine coordinate system.
[0008]
E_p: Y²≡x³+ Ax + b (modp)
On the elliptic curve, the addition on the elliptic curve is defined between two points on the curve,
P₃= P₁+ P₂(However, P_i= (X_i, Y_i)) Is defined as follows:
[0009]
[(P₁≠ P₂In the following case, this case is referred to as an ellipse addition operation.
[0010]
Ellipse addition operation: 0 additions, 6 subtractions, 2 multiplications, 1 division
λ = (y₂-Y₁) / (X₂-X₁), X₃= Λ²-X₁-X₂,
y₃= Λ (x₁-X₃-Y₁
[(P₁= P₂)] This case is hereinafter referred to as elliptical doubling.
[0011]
Ellipse doubling: 1 addition, 3 subtractions, 3 multiplications, 1 division
λ = (3x₁ ²+ A) / 2y₁, X₃= Λ²-2x₁,
y₃= Λ (x₁-X₃-Y₁
However, all the above operations are performed in a residue system modulo p.
[0012]
The security of the elliptic curve cryptography is as follows. When the point A on the elliptic curve is x times (ie, A is added x times) is B (= x · A), the values of the points A and B are known. Is based on the fact that it is very difficult to obtain x from the value. This property is called a discrete logarithm problem on an elliptic curve, and in order to ensure the same level of security as the 1024 bits of the RSA cipher, p, a, x_i, Y_iFor such parameters, an integer of about 160 bits is recommended.
[0013]
The calculation of the k-fold point (k · P) of the point P, which is the basic calculation of the elliptic curve cryptography, is performed by using the above addition on the elliptic curve. It is necessary to perform a remainder division operation. The remainder division operation is generally processed using an algorithm such as the extended Euclidean algorithm, but requires a lot of processing time. Therefore, a method is widely used in which a point on an elliptic curve is processed by converting a point in the two-dimensional affine coordinate system into a point in the three-dimensional coordinate system without performing the remainder division calculation. For details, see D.C. V. Chudnovsky and G.C. V. Chudnovsky, "Sequences of Numbers Generated by Addition in Formal Groups and New Primitives and Factories Tests, Advanced Measures in App." 385-434, 1986. As an example, an elliptic curve E in a two-dimensional affine coordinate system_pThe above addition operation is expressed as x≡X / Z²(Modp),
y≡Y / Z³When converted to a three-dimensional projective coordinate system satisfying (modp), the following definition is made.
[0014]
Ellipse addition operation: 2 additions, 5 subtractions, 16 multiplications, 0 divisions
X₃= R²-TW², 2Y₃= VR-MW³, Z₃= Z₁Z₂W
However, W = X₁Z₂ ²-X₂Z₁ ², R = Y₁Z₂ ³-Y₂Z₁ ³,
T = X₁Z₂ ²+ X₂Z₁ ², M = Y₁Z₂ ³-Y₂Z₁ ³,
V = TW²-2X₃
Ellipse doubling: 1 addition, 3 subtractions, 10 multiplications, 0 divisions
X₃= M²-2S, Y₃= M (SX₃) -T, Z₃= 2Y₁Z₁
However, M = 3X₁ ²+ AZ₁ ⁴, S = 4X₁Y₁ ², T = 8Y₁ ⁴
However, all the above operations are performed in a residue system modulo p.
[0015]
Other examples of coordinate transformation include x≡X / Z (modp),
There is a conversion method to a three-dimensional homogeneous coordinate system that satisfies y≡Y / Z (modp).
[0016]
However, a remainder division operation is required once when converting from the three-dimensional coordinate system to the two-dimensional coordinate system again.
[0017]
If the 160-bit elliptic curve cryptosystem is converted into a three-dimensional projective coordinate system and the k · P operation is processed using the above-described binary operation method, an average of 2862 times of modular multiplication is required.
[0018]
As described above, public key cryptography such as RSA cryptography and elliptic curve cryptography requires a lot of modular multiplication operations as its basic computation. For this reason, a method has been devised that uses a high-speed algorithm for the remainder multiplication operation to speed up the remainder multiplication operation and speed up the entire cryptographic processing.
[0019]
In particular, since most of the operations of RSA cryptography are modular multiplication operations, hardware that executes a high-speed algorithm of modular multiplication operations and an IC card that executes RSA cryptographic processing at high speed by using it are IC This is realized based on ISO7816 which is a standard of the card.
[0020]
[Problems to be solved by the invention]
In contrast, public key cryptography and digital signatures other than RSA may require a remainder division operation. Among the remainder four arithmetic operations, the remainder division operation particularly requires a computation time, which is a big problem in speeding up the encryption processing and signature generation processing. One of the public key cryptosystems that uses the remainder division operation is elliptic curve cryptography. A method for reducing the number of remainder division operations in this elliptic curve cryptography and a method for calculating the remainder division computation at high speed are described by Shinbo, “Applying Montgomery Arithmetic to Elliptic Curve Ciphers” SCIS '97 (The 1997 Symposium on Cryptography and Information Security).
[0021]
However, when the method in this document is applied to an apparatus such as an IC card defined by the ISO7816 standard, there is a limit to the computing power of the CPU due to the standard and the limitations of the current semiconductor technology. Therefore, the inverse operation in the remainder division operation takes time, and it is difficult to increase the processing speed.
[0022]
SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide a method capable of executing elliptic curve cryptographic processing at high speed in a cryptographic processing device having hardware for executing a high-speed algorithm for modular multiplication, and a device using the same, for example, an IC card. It is to be.
[0023]
Another object of the present invention is to provide a device having hardware for executing a high-speed algorithm for modular multiplication, for example, a method for executing digital signature processing at high speed in an IC card, and a device for realizing the method. It is to be.
[0024]
Another object of the present invention is to provide a method capable of speeding up the inverse operation in remainder division and a program or apparatus using the same in elliptic curve cryptography.
[0025]
Another object of the present invention is to use a method capable of executing various processes such as a DSA signature and a Schnorr signature at high speed in a cryptographic processing apparatus having hardware for executing a high-speed algorithm for modular multiplication, and the same. To provide a device, for example an IC card.
[0026]
Another object of the present invention is a method capable of speeding up inverse operation in remainder division in various public key schemes and digital signature schemes that require remainder division operations such as DSA signature and Schnorr signature processing, and an apparatus using the same Is to provide.
[0027]
[Means for Solving the Problems]
In order to achieve the above object, according to the present invention, the following modes are provided.
First, according to one aspect of the present invention, in a device including a device (hereinafter referred to as a residue multiplier) in which a high-speed algorithm for residue multiplication is implemented (for example, an IC card), the remainder multiplier is effectively used. As described above, an elliptic curve encryption processing method is provided in which operations in elliptic curve cryptography are composed of operations centered on remainder multiplication.
Specifically, the remainder calculation after the random number generation necessary for the elliptic curve encryption process and the remainder calculation in the signature creation process can be calculated using a remainder multiplier. Further, in order to effectively use the remainder multiplier also in the computation on the elliptic curve, the remainder in the addition computation on the elliptic curve is obtained by converting the points on the elliptic curve from the two-dimensional affine coordinate system to the three-dimensional coordinate system. The division operation is converted into a remainder multiplication operation, and processing is performed so that the remainder multiplier can be used for the remainder multiplication operation.
[0028]
In another aspect of the present invention, in order to speed up the inverse operation described in the above problem, it is necessary when converting from a three-dimensional coordinate system to a two-dimensional affine coordinate system and when obtaining signature data. The inverse operation is also calculated using a remainder multiplication operation. The inverse operation in the residue system is generally obtained using an algorithm such as the extended Euclidean algorithm, but when the modulus of the remainder is a prime number, without using an algorithm such as the extended Euclidean algorithm, It can be obtained using only a modular multiplication operation. The method is shown below.
According to Fermat's little theorem, for prime β and prime integer α that is relatively prime,
α^β-1≡1 (modβ)
Is established. Using this theorem, the inverse operation α^-1mod β can be expressed as follows.
α^-1≡α^β-2(Modβ)
In the present invention, in order to maintain the security of elliptic curve cryptography, the values of the order p and the base point order n of the finite field are large prime numbers. The conditions in the Fermat's small theorem, the prime number β and the positive integer α Always satisfy that they are disjoint. Therefore,
α^-1The value of mod β is α^β-2If it is equal to mod β and the remainder multiplication operation is performed using the binary operation method, the average ((| β−2 | −1) × 3/2)
(Where | β-2 | represents the number of bits of (β-2)), and the inverse operation α^-1It is possible to determine the value of mod β. When this method is used, it is not necessary to create an algorithm such as the Euclidean mutual division method as a program, so that the program size is also reduced.
[0029]
This inverse element calculation method is not limited to elliptic curve cryptography, but can also be used for processing of various other public key schemes and digital signature schemes that require inverse element calculations, such as DSA signatures and Schnorr signatures.
[0030]
Also, parameters that are frequently used in computations that can be calculated in advance can be calculated in advance on a personal computer, etc., and stored in a rewritable non-volatile memory in the IC card as one piece of system information. , Can reduce the amount of calculation. The data as system information stored in advance includes a finite body number p, aRmodp obtained by converting the elliptic curve parameter a, and the two-dimensional affine coordinates (x, y) of the point P (base point) on the elliptic curve. The point P (X, Y, Z) converted to the coordinates of the three-dimensional projective coordinate system, and further converted for the remainder multiplier, the order n of the base point, the secret key d, and the calculation on the elliptic curve are used. 2Rmodp, 3Rmodp, 4Rmodp, 8Rmodp and 2 converted constants^-1Rmodp, Rmodp, Rmodn, and R for use in remainder calculation²modp and R²Let it be modn. However, R used here is a positive integer satisfying R> p, R> n with respect to the finite field order p and the base point order n, for example, the numbers of bits of p and n are | p | and | n | When expressing
The smallest positive integer having a bit length equal to the larger of | p | +1 or | n | +1.
[0031]
Further, in order to reduce the total number of calculations in the addition calculation on the elliptic curve in the IC card and reduce the total amount of calculation, a point that is a constant multiple of the base point is stored as a table in a rewritable nonvolatile memory in the IC card. I decided to leave. However, the amount of calculation decreases as the number of tables increases, but the data size stored in the memory increases. For this reason, in the present invention, the table has a point that is a power of 4 times the base point. At this time, the number of points held as a table, that is, the number of tables is represented by | p |
(| P | / 2) pieces, and the values of the table are converted into the coordinates of the three-dimensional projective coordinate system, and further converted into the calculation area of the remainder multiplication device, the point P_i= (X_i, Y_i, Z_i)
(I is an integer of 0 ≦ i <| p | / 2).
[0032]
In addition, when the memory size is larger, it is possible to configure the operation on the elliptic curve by only the elliptic addition operation by having a point that is a power of 2 of the base point as a table. The number of times can be reduced.
[0033]
In general, in the case where the table has a value of a point that is a power of 2 times the base point (n is a natural number) as a table, the number of tables is represented by | p | (| P | / n), and can be determined by a trade-off between the calculation performance of the CPU and the memory capacity for storing the table.
[0034]
DETAILED DESCRIPTION OF THE INVENTION
An embodiment of the present invention will be described with reference to the drawings.
[0035]
FIG. 1 is a schematic configuration diagram when a digital signature system execution apparatus using an addition operation in an elliptic curve on a finite field according to the present invention is realized in an IC card based on, for example, a Hitachi H8 / 3111 microcomputer. Show. This type of IC card 101 includes a CPU 102, a ROM 103 including operation instructions for implementing the present invention, an EEPROM 104 as a rewritable nonvolatile memory for storing system information data such as a finite body number and an elliptic curve parameter, An I / O port 105 that controls input / output to the IC card 101, a RAM 106, a remainder multiplier 107 that can perform a remainder multiplication operation, a power supply terminal Vcc110, a ground terminal Vss111, a clock terminal CLK112, and a reset A terminal RES1113 and an I / O terminal I / O114 are included. Each terminal of the IC card 101 is connected to a necessary part in the IC card 101. The remainder multiplier can be constituted by, for example, a coprocessor of a microcomputer H8 / 3111 manufactured by Hitachi with a high-speed calculation function. Other equivalent coprocessors can also be used.
[0036]
The remainder multiplier 107 includes a CPU / residue multiplier common RAM 109 that can be used in common with the CPU 102, and the RAM 109 includes at least three data registers CDA, CDB, and CDN. When the arithmetic operation of the remainder multiplier 107 is executed by storing the input data in the registers CDA, CDB, CDN, the operation result is stored by rewriting the value of the CDA. Further, the CDB and CDN values do not change after the calculation. The remainder multiplier 107 is a device capable of executing the following three types of operations by designating an operation type.
[0037]
CDA ← (CDA / CDB) R^-1mod (CDN): hereinafter referred to as remainder operation 1.
CDA ← (CDA²) R^-1mod (CDN): hereinafter referred to as remainder operation 2.
CDA ← (CDA) R^-1mod (CDN): hereinafter referred to as remainder operation 3.
Each element in the IC card 101 is interconnected by a bus 108.
In addition, the elliptic curve E used in the present invention_pThe order of the finite field is a prime number p, and a set of virtual infinity points O is added to a set of points satisfying the following formulas for parameters (a, b) for determining an elliptic curve. Here, for the sake of convenience, the affine coordinate system is used.
E_p: Y²≡x³+ Ax + b (modp)
Furthermore, the base point is P (x, y), and the base point has a prime number n.
[0038]
(1) Storage of system information
A finite body number p, an elliptic curve parameter aRmodp, and a point P that is a constant multiple of the coordinates of a point P (base point) on the elliptic curve._i(X_i, Y_i, Z_i)
(I is an integer of 0 ≦ i <| p | / 2, | p | represents the number of bits of the finite order p), the base point order n, the secret key d, and the operation on the elliptic curve 2Rmodp, 3Rmodp, 4Rmodp, 8Rmodp and 2 converted constants used^-1Rmodp, Rmodp, Rmodn, and R for use in remainder calculation²modp and R²“modn” is stored in the EEPROM 104. However, R used here is a positive integer satisfying R> p, R> n. For example, when the numbers of bits of p and n are expressed as | p | and | n |, respectively, | p | +1 or | n | The smallest positive integer having a bit length equal to the larger of +1.
[0039]
It is assumed that the storage of these system information is performed before the following cryptographic processing is executed. Here, R is a numerical value given as a constant, and is a parameter that is determined depending on, for example, the computing performance of the coprocessor that constitutes the multiple length arithmetic means.
[0040]
(2) Signature creation
2 to 7 show flowcharts for creating a digital signature performed by the elliptic curve cryptographic processing apparatus according to this embodiment. Hereinafter, an outline procedure for creating a digital signature will be described with reference to FIG.
The following flowcharts show the contents of the CPU 102 executing the program stored in the ROM 103 while using the data stored in the RAM 106 and the EEPROM 104 and causing the remainder calculator 107 to execute the process as necessary. ing.
[0041]
Step 201: Start
Step 202: A random number k is generated, the random number k is stored in the register CDA of the remainder multiplier 107, and the Rmodn stored in the EEPROM 104 is stored in the register CDB. Let it run. The execution result stored in the CDA is again set as a random number k.
Step 203: The random number k generated in Step 202 and the system information p, aRmodp, P (X, Y, Z) stored in the EEPROM 104 are input, and an elliptic curve E_pIn the above, an operation k · P that is a random number k times the base point P is calculated. In this calculation, the CPU 102 performs an addition operation on an elliptic curve on a finite field in a three-dimensional projective coordinate system, that is, a scalar multiplication operation, and the remainder multiplication in the computation is calculated using a remainder multiplier 107 which is a coprocessor.
[0042]
Step 204: Since the execution result (X, Y, Z) of step 203 is a point in the three-dimensional projected coordinate system, it is converted to a point (x, y) in the affine coordinate system. The operation for this conversion is x≡X / Z²(Modp), but instead, the operation x≡X · Z^p-3(Modp) may be performed. Because x≡X · Z by applying Fermat's little theorem^p-3This is because (modp) holds. Therefore x≡X / Z²X / Z without using (modp)^p-3By using (modp), coordinate conversion can be performed only by remainder multiplication without using remainder division operation.
Step 205: The random number k generated in Step 202, the hash value (digest value) H (M) for the message M input from the I / O terminal 114 via the I / O port 105, and the EEPROM 104 are stored. Using the secret key d, the base point order n, and xmodp calculated in step 204, the following calculation is performed.
[0043]
Generation of signature r: r≡x (modn)
Generation of signature s: s≡k^-1・ (H (M) + d ・ r) (modn)
An inverse element operation is required when calculating the signature s in the above operation. This operation is also performed by the same method as in step 204.^-1The value of modn is k^n-2The remainder is replaced with a modular remainder multiplication, and the remainder multiplication is calculated using the remainder multiplier 107. This calculation result is set as a signature (r, s), and is output from the I / O terminal 114 via the I / O port 105 as a digital signature for the message M.
Step 206: End
Next, the procedure for creating a digital signature in this embodiment will be described in more detail with reference to FIGS.
FIG. 3 is a detailed flowchart of the process in step 203 of FIG.
Step 301: Start
Step 302: k = (k) in which the binary notation of the random number k generated in Step 202 is paired by 2 bits._i, K_i-1, ..., k₁, K₀)₂, And scan the bit string from the bottom to k_i= (11), the higher order bit string k_{i + 1}In addition, (01) is added to rewrite up to the most significant bit. In the conversion example, if the original bit string is (10, 11, 10, 11), the converted bit string is (01, 11, 00, 11, 11). This conversion is performed up to the most significant bit, and the bit string is changed again.
k = (k_l, K_l-1, ..., k₁, K₀)₂(However, k_l≠ (00)).
The value of l obtained at this time is stored as (l + 1) in a variable i (hereinafter referred to as a loop counter) as the number of times the computation on the elliptic curve is repeated.
[0044]
Step 303: Points converted for the remainder multiplier after the three-dimensional coordinate conversion of the base point on the elliptic curve which is the table value stored in the EEPROM 104 as described above
P_i(X_i, Y_i, Z_i) To store the initial value in the RAM 106 and P_iK corresponding to_iRewrite the value of.
Step 304: Count down the loop counter i by 1.
Step 305: The loop counter i is determined. If i is smaller than 0, the process proceeds to step 307. Otherwise, go to step 306.
Step 306: k_iIf the value of (00) is (00), the process returns to step 304. k_iIf the value of (01) is the table value P_iThe ellipse addition operation is performed to add and the process returns to step 304. k_iIf the value of (10) is, the table value P_iThe ellipse doubling operation for doubling is performed, and the ellipse addition operation for adding the results is performed, and the process returns to step 304. k_iIf the value of (11) is, the table value P_iFor the value of Y coordinate of, find the inverse element for the addition with the modulus p, and change the value to the table value P_iThe ellipse addition operation is performed to add the points, and the process returns to step 304.
Step 307: End
FIG. 4 is a detailed flowchart of the ellipse addition operation in the process of FIG.
Step 401: Start. In step 303, since p is stored in the CDN of the remainder multiplier 107, remainder multiplication using p as a modulus is performed.
[0045]
Step 402: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 403: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 404: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 405: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 406: The CPU 102 performs a remainder subtraction operation to obtain an intermediate value W.
Step 407: The CPU 102 performs a remainder addition operation to obtain an intermediate value T.
Step 408: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 409: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 410: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 411: The residue calculation 1 is executed using the residue multiplier 107.
Step 412: The CPU 102 performs a remainder subtraction operation to obtain an intermediate value R.
Step 413: The CPU 102 performs a remainder addition operation to obtain an intermediate value M.
[0046]
Step 414: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 415: The remainder calculation 1 is executed using the remainder multiplier 107, and the Z coordinate of the point after the ellipse addition calculation is obtained.
Step 416: Residue calculation 2 is executed using the remainder multiplier 107.
Step 417: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 418: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 419: The CPU 102 performs a remainder subtraction operation to obtain the X coordinate of the point after the ellipse addition operation.
Step 420: The CPU 102 performs a remainder subtraction operation to obtain an intermediate value V.
Step 421: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 422: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 423: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 424: The CPU 102 performs a remainder subtraction operation to obtain an intermediate value Y.
Step 425: 2 stored in the EEPROM 104^-1Rmodp and the intermediate value Y are input to the remainder multiplier 107 and the remainder calculation 1 is executed. Thereby, the Y coordinate of the point after the ellipse addition operation is obtained.
Step 426: End
FIG. 5 shows a detailed flowchart of the ellipse doubling operation in the process of FIG.
Step 501: Start. In step 303, since p is stored in the CDN of the remainder multiplier 107, remainder multiplication using p as a modulus is performed.
Step 502: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 503: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 504: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 505: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 506: 3Rmodp stored in the EEPROM 104 and X obtained in Step 502₁ ²Rmodp is input to the remainder multiplier 107 and the remainder calculation 1 is executed.
Step 507: The CPU 102 performs a remainder addition operation to obtain an intermediate value M.
Step 508: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 509: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 510: 4Rmodp stored in the EEPROM 104 and X obtained in Step 509₁Y₁ ²Rmodp is input to the remainder multiplier 107 and the remainder calculation 1 is executed. Thereby, the intermediate value S is obtained.
[0047]
Step 511: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 512: 8Rmodp stored in the EEPROM 104 and Y obtained in Step 511₁ ⁴Rmodp is input to the remainder multiplier 107 and the remainder calculation 1 is executed. Thereby, an intermediate value T is obtained.
Step 513: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 514: 2Rmodp stored in the EEPROM 104 and Y obtained in Step 513₁Z₁Rmodp is input to the remainder multiplier 107 and the remainder calculation 1 is executed. Thereby, the Z coordinate of the point after the ellipse doubling operation is obtained.
Step 515: The remainder calculation 2 is executed using the remainder multiplier 107.
Step 516: 2Rmodp and intermediate value S stored in the EEPROM 104 are input to the remainder multiplier 107, and a remainder calculation 1 is executed.
Step 517: The CPU 102 performs a remainder subtraction operation to obtain the X coordinate of the point after the ellipse doubling operation.
Step 518: The remainder calculation 1 is executed using the remainder multiplier 107.
Step 519: The CPU 102 performs a remainder subtraction operation to obtain the Y coordinate of the point after the ellipse doubling operation.
Step 520: End
FIG. 6 shows a detailed flowchart of the processing (inverse operation) in step 204 in FIG.
Step 601: Start
Step 602: (p-3) is calculated from the finite position number p stored in the EEPROM 104, and its binary notation
(P-3) = (j_l, J_l-1, ..., j₁, J₀)₂(However, j_l= 1) is stored in the loop counter i as the number of times the remainder multiplication operation is repeated.
Step 603: The Z coordinate of the point after the calculation in Step 203 is stored in the CDA and CDB of the remainder multiplier 107. Further, since the value of CDN does not change in step 303 while p is stored in the CDN of the remainder multiplier 107, the value of p is stored.
Step 604: Count down the loop counter i by 1.
Step 605: The loop counter i is determined. If i is smaller than 0, the process proceeds to step 609. Otherwise, go to step 606.
Step 606: The remainder calculation 2 is executed using the remainder multiplier 107.
[0048]
Step 607: Value j for loop counter i in (p-3)_iJudgment is made. j_iIf is not 1, the process returns to step 604. j_iIf is 1, the process proceeds to step 608.
Step 608: The remainder calculation 1 is executed using the remainder multiplier 107. Thereafter, the process returns to step 604.
Step 609: The X coordinate of the point after the calculation in step 203 is stored in the CDB of the remainder multiplier 107. At this time, the CDA has Z^p-3The value of Rmodp is stored.
Step 610: The remainder calculation 1 is executed using the remainder multiplier 107. As a result, CDA has XZ^p-3The value of Rmodp, that is, the converted value xR≡XZ of the x coordinate of the coordinate in the two-dimensional affine coordinate system resulting from the execution of step 203 into the operation area of the remainder multiplier^-2The value of R (modp) is stored.
Step 611: The remainder calculation 3 is executed using the remainder multiplier 107. As a result, CDA has XZ^-2The value of modp, that is, the x coordinate x≡XZ of the coordinates in the two-dimensional affine coordinate system that is the execution result of step 203^-2The value of (modp) is stored. In the above steps 604 to 608, X / Z²1 / Z of the operation to find²Z^p-3And the value is obtained by the remainder computing unit 107.
Step 612: End
As described above, in the present invention, it is not necessary to perform a multiple-precision residue multiplication operation using the CPU 102 by using the multiple-precision residue multiplication function of the remainder multiplier 107. For this reason, there are few calculation steps, and the processing speed can be increased.
[0049]
FIG. 7 is a detailed flowchart of the processing in step 205 in FIG.
Step 701: Start
Step 702: The xP value xmodp of kP calculated in Step 204 is stored in the CDA of the remainder multiplier 107.
Step 703: Rmodn stored in the EEPROM 104 is stored in the CDB of the remainder multiplier 107. R is a unique value of the coprocessor, and n is the order of P on the elliptic curve.
Step 704: The base point order n stored in the EEPROM 104 is stored in the CDN of the remainder multiplier 107.
Step 705: The remainder calculation 1 is executed using the remainder multiplier (coprocessor) 107. The value of xmodn, which is the result of this calculation, is stored in the CDA. This value is a signature
r≡x (modn). Next, the process proceeds to steps 706 to 713 for obtaining the signature s.
Step 706: R stored in the EEPROM 104 in the CDB of the remainder multiplier 107²Store modn.
Step 707: The remainder calculation 1 is executed using the remainder multiplier 107. The value of rRmodn, which is the calculation result, is held in the CDA.
Step 708: The secret key d stored in the EEPROM 104 is stored in the CDB of the remainder multiplier 107.
Step 709: The remainder calculation 1 is executed using the remainder multiplier 107. The value of d · rmodn, which is the calculation result, is stored in the CDA.
[0050]
Step 710: Using the CPU 102, calculate the sum of the hash value H (M) for the message M and d · rmodn obtained in the above step 709,
The value of (H (M) + d · r) modn is stored in the RAM 106.
Step 711: Inverse operation k^-1Rmodn is a residue multiplication k using a residue multiplier 107^n-2Calculate with Rmodn. For this calculation method, refer to the processing from step 601 to step 609 in FIG. The result of this operation
k^-1Rmodn is stored in the CDA of the remainder multiplier 107.
Step 712: The value of (H (M) + d · r) modn stored in the RAM 106 in Step 710 is stored in the CDB of the remainder multiplier 107.
Step 713: The remainder calculation 1 is executed using the remainder multiplier 107. K which is the result of this operation^-1The value of (H (M) + d · r) modn is stored in the CDA. This value is the signature s≡k^-1(H (M) + d · r) (modn).
Step 714: End
In order to confirm the effect of the present invention, a program according to the above embodiment was created, and the execution time when the number of operating clocks of the CPU was 5 MHz was measured.
Specifically, k · P calculation on an elliptic curve with a 160-bit key length is performed using 80 reference tables each indicating a value of a point that is a power of 4 of the base point in a three-dimensional projection coordinate system. In addition, the inverse element calculation is performed by combining Fermat's little theorem and binary arithmetic. As an execution environment, a microcomputer H8 / 3111 emulator for IC cards with a built-in multiple-precision modular multiplication coprocessor manufactured by Hitachi, Ltd. was used, and an assembler was used as a program language. As a result, the signature creation time (time taken from step 201 to step 206) by elliptic curve encryption with a 160-bit key length is 0.308 seconds / signature.
[0051]
As described above, according to the present invention, remainder multiplication and remainder division are performed using a remainder multiplier, other remainder addition and remainder subtraction are performed using a CPU, and reference is made to pre-calculated values. By doing so, elliptic curve cryptography can be processed at high speed.
In the above description, the digital signature creation process has been mainly described. However, the present invention is not limited to this, and the signature verification process using the elliptic curve cryptography and the cipher creation process can be performed at high speed by the same method.
In addition, as described in the above description, the method of processing the inverse element operation at a high speed using the remainder multiplier is a variety of public key cryptography using other inverse element operations, digital signature schemes such as a DSA signature, Schnorr signature, and the like. It is applicable to.
[0052]
Further, the present invention is not limited to the IC card as in the above-described embodiment, and can be applied to any similar device that has a limited processing capability of the CPU and includes a multiplier. For example, the present invention can be applied to a microcontroller that performs authentication processing, IEEE1394 LSI for encryption processing, or the like. These uses are also described in NIKKEI ELECTRONICS 1998. 12.14 (No. 732) pp27-28.
[0053]
In the present invention, the EEPROM is given as an example of the rewritable nonvolatile memory 104. However, the present invention is not limited to this, and a flash memory can also be used. The ROM 103 can also use a flash memory.
The module that realizes the inverse operation using the coprocessor 107 shown in FIG. 6 can be realized in any form, such as a single piece of hardware such as software or a semiconductor chip, or a combination thereof. It will be understood.
[0054]
【The invention's effect】
As described above, according to the present invention, the digital signature creation process based on the elliptic curve is configured by using a method that effectively uses the remainder multiplication operation, so that it can be processed at high speed in an apparatus including a remainder multiplier. Methods and apparatus can be provided.
[Brief description of the drawings]
FIG. 1 is a block diagram of an apparatus to which the present invention is applied.
FIG. 2 is a flowchart showing a signature creation procedure using elliptic curve cryptography according to an embodiment of the present invention.
FIG. 3 is a detailed flowchart of processing in step 203 of FIG. 2;
4 is a detailed flowchart of an ellipse addition operation in FIG. 3. FIG.
FIG. 5 is a detailed flowchart of the ellipse doubling operation in FIG. 3;
FIG. 6 is a detailed flowchart of processing in step 204 of FIG.
FIG. 7 is a flowchart of processing in step 206 of FIG.
[Explanation of symbols]
101 ... IC card,
102 ... CPU,
103 ... ROM,
104 ... EEPROM,
105 ... I / O port,
106 ... RAM,
107: Remainder multiplier,
108 ... Bus
109: CPU / residue multiplier common RAM,
110: power supply (Vcc) terminal,
111: Ground (Vss) terminal,
112 ... Clock (CLK) terminal,
113 ... reset (RES) terminal,
114: I / O terminal.

Claims (7)

Means for receiving a message from the input / output terminal via the input / output port;
Means for performing public key cryptography on the message;
Means for outputting the processing result of the public key cryptography process from an input / output terminal via an input / output port;
The public key cryptographic processing means is a positive integer A, B, N, R (where A, B are variables given as input variables or intermediate variables, and N is a variable given as an input variable, R is a numerical value given as a constant), and ABR ⁻¹ modN, A ² R ⁻¹ modN, and AR ⁻¹ modN representing the numerical values to be calculated in the intermediate arithmetic processing are multiplied by a multiple of multiples. Multiple length arithmetic means for calculating;
Using the multiple length arithmetic means, and calculating means for performing inverse element calculation by repeating the ABR ⁻¹ modN and the A ² R ⁻¹ modN which are multiplications on a finite group,
The calculation means uses a relational expression k ⁻¹ modn≡k ⁿ⁻² modn for an operation k ⁻¹ modn for a prime integer k that is relatively prime to the prime number n, and k ⁻¹ modn is the k ⁿ⁻ An IC card comprising an inverse element calculation unit that replaces ² modn and performs calculation of the k ⁿ⁻² modn by repeatedly using a modular multiplication operation of the ABR ⁻¹ modN and the A ² R ⁻¹ modN.   2. The IC card according to claim 1, wherein the multiple length arithmetic means is constituted by a coprocessor, and the R is a constant determined by the performance of the coprocessor. The public key cryptography is elliptic curve cryptography,
2Rmodp, 3Rmodp, 4Rmodp, 8Rmodp, 2 ⁻¹ Rmodp, aRmodp, Rmodp, R ² modp, Rmodn, R ² modn (however, an elliptic curve over a finite field E _p : y ² ≡x ³ + ax + bmod) In addition, at least one of numerical values of R> p and R> n satisfying R> p and R> n is stored in advance, and can be referred to from the multiple length arithmetic means. 3. The IC card according to claim 1, further comprising a non-volatile memory that can be used. A rewritable value in which a value of a positive integer multiple of the base point P on the elliptic curve is stored in advance, and a value of a positive integer multiple of the base point P can be referred to from the multiple length arithmetic means. 4. The IC card according to claim 1, further comprising a non-volatile memory. An encryption processing method using an IC card having a CPU and a coprocessor,
The CPU
Receiving a message from the input / output terminal via the input / output port;
Performing elliptic curve cryptography on the message;
Outputting the processing result of the elliptic curve encryption processing step from the input / output terminal via the input / output port;
Run
The elliptic curve encryption processing step includes:
Positive integers A, B, N, R (where A, B are variables given as input variables or intermediate variables, N is a variable given as an input variable, and R is a numerical value given as a constant) Calculating ABR ⁻¹ modN, A ² R ⁻¹ modN, and AR ⁻¹ modN representing the numerical value to be calculated that occurs in the intermediate arithmetic processing by a multiplication operation of a multiple of the remainder,
Using the coprocessor to iterate the ABR ⁻¹ modN and A ² R ⁻¹ modN, which are multiplications on a finite group, to perform inverse element calculations;
Including
In the inverse element calculation step, an operation k ⁻¹ modn for a positive integer k that is relatively prime to the prime number n is used as a relational expression k ⁻¹ modn≡k ⁿ⁻² modn, and k ⁻¹ modn is changed to the k ^It is replaced with ^n-2 modn, and includes a step of executing an inverse element calculation in which the calculation of k ^n-2 modn is performed by repeatedly using a modular multiplication operation of the ABR ⁻¹ modN and the A ² R ⁻¹ modN. Cryptographic processing method. A C PU, and a recording medium storing a program for causing execution of cryptographic processing to the IC card with a coprocessor,
The program is stored in the IC card .
Receiving a message from the input / output terminal via the input / output port;
Performing elliptic curve cryptography on the message;
Outputting the processing result of the elliptic curve encryption processing step from the input / output terminal via the input / output port;
Was executed,
The elliptic curve encryption processing step includes:
Positive integers A, B, N, R (where A, B are variables given as input variables or intermediate variables, N is a variable given as an input variable, and R is a numerical value given as a constant) Calculating ABR ⁻¹ modN, A ² R ⁻¹ modN, and AR ⁻¹ modN representing the numerical value to be calculated that occurs in the intermediate arithmetic processing by a multiplication operation of a multiple of the remainder,
Using the coprocessor to iterate the ABR ⁻¹ modN and A ² R ⁻¹ modN, which are multiplications on a finite group, to perform inverse element calculations;
Including
In the inverse element calculation step, an operation k ⁻¹ modn for a positive integer k that is relatively prime to the prime number n is used as a relational expression k ⁻¹ modn≡k ⁿ⁻² modn, and k ⁻¹ modn is changed to the k ^It is replaced with ^n-2 modn, and includes a step of executing an inverse element calculation in which the calculation of k ^n-2 modn is performed by repeatedly using a modular multiplication operation of the ABR ⁻¹ modN and the A ² R ⁻¹ modN. recording medium storing a program for causing execution of cryptographic processing to be. It is used in an electronic device equipped with a cryptographic processing device using a modular multiplication unit,
In cryptographic processing, the value k to be generated, the constant R determined by the performance of the remainder multiplier, and the operation k ⁻¹ modn for a positive integer k that is relatively prime to the prime number n is called k ⁻¹ modn≡k ⁿ⁻² modn. An inverse element calculation module that calculates using a relational expression,
A first means for calculating kRmodn by the remainder multiplier and storing the calculation result in a first register and a second register;
An A ² R ⁻¹ mod N computing unit that squares the value of the first register, multiplies it by R ⁻¹ , and stores the resulting modn in the first register;
An ABR ^-1 modN arithmetic unit that multiplies the values of the first register and the second register, multiplies them by R- ¹ , and stores the resulting modn in the first register;
Second means for repeating the processing by the A ² R ⁻¹ mod ^N computing unit and the ABR ⁻¹ mod ^N computing unit to obtain kn ⁻² modn;
An inverse element calculation module comprising:

Images