WO2005015526A1 - 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体 - Google Patents

楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体 Download PDF

Info

Publication number
WO2005015526A1
WO2005015526A1 PCT/JP2003/010003 JP0310003W WO2005015526A1 WO 2005015526 A1 WO2005015526 A1 WO 2005015526A1 JP 0310003 W JP0310003 W JP 0310003W WO 2005015526 A1 WO2005015526 A1 WO 2005015526A1
Authority
WO
WIPO (PCT)
Prior art keywords
elliptic curve
scalar multiplication
program
scalar
computer
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2003/010003
Other languages
English (en)
French (fr)
Inventor
Tetsuya Izu
Kouichi Itoh
Masahiko Takenaka
Naoya Torii
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to EP03817985A priority Critical patent/EP1653428B1/en
Priority to PCT/JP2003/010003 priority patent/WO2005015526A1/ja
Priority to JP2005507578A priority patent/JP4284320B2/ja
Publication of WO2005015526A1 publication Critical patent/WO2005015526A1/ja
Priority to US11/311,590 priority patent/US7639808B2/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
    • H04L9/003—Countermeasures against attacks on cryptographic mechanisms for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G06F2207/7228—Random curve mapping, e.g. mapping to an isomorphous or projective curve
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/08—Randomization, e.g. dummy operations or using noise

Definitions

  • Elliptic curve encryption device Elliptic curve encryption device, elliptic curve encryption method, elliptic curve encryption program, and computer-readable recording medium storing the program
  • the present invention relates to an elliptic curve cryptosystem, and more particularly to an elliptic curve cryptosystem, an elliptic curve cryptographic method, and an elliptic curve cryptographic program suitable for use in preventing a power analysis attack in a processor performing the elliptic curve cryptosystem.
  • the present invention relates to a readable recording medium.
  • the encryption method includes a public key encryption method and a common key encryption method.
  • Public key cryptography uses different keys for encryption and decryption.
  • a key (public key) for performing encryption is made public, and a plaintext is encrypted using this public key and transmitted to a receiver.
  • the key (secret key) for decrypting the ciphertext is held as secret information known only to the recipient, and the recipient can obtain the plaintext by decrypting the ciphertext using this secret key. it can.
  • Elliptic Curve Cryptography has attracted attention as a public key cryptosystem.
  • Various types of encryption / decryption algorithms are known for this elliptic curve cryptosystem, but most encryption / decryption processes use a scalar multiplication operation.
  • d XP the point P on the elliptic curve
  • P + P + .. + P the sum of d pieces
  • sender A has a secret key s (s is an integer) and receiver B has a secret key t (t is an integer)
  • the elliptic curve E and the base point P (X, y)) and public Open key s XP (scalar multiple of sender A's secret key s and base point P) and public key t XP (scalar multiple of recipient B's private key t and base point P) It has already been released.
  • the sender A calculates a scalar multiplication S X (t XP) between the secret key s of the sender A and the public key t XP of the receiver B, obtains a bit representation of the X coordinate, and obtains the bit table
  • a bit-wise EOR Exclusive OR
  • Receiver B calculates a scalar multiplication t X (s XP) of its own private key t and sender A's public key s XP, and obtains a bit representation of the X coordinate.
  • the ciphertext C is decrypted and the message m is decrypted by performing a bit-wise E ⁇ R operation between the bit representation and the bit representation of the ciphertext C. obtain.
  • ECES ⁇ encryption and decryption processing is performed using scalar multiplication.
  • the decryption technology is a technology for estimating secret information such as a secret key from available information such as ciphertext, and there are various methods. Among them, a technique that has recently attracted attention is a technique called side channel attack.
  • the side channel attack is a method devised by Paul Kocher in 1989.
  • side channel information power consumption
  • This method estimates key information inside the cryptographic processor by collecting and analyzing time data and electromagnetic wave data. It has been pointed out that there is a possibility that a secret key can be estimated from a cryptographic processor by using a side channel attack for both public key cryptography and secret key cryptography.
  • SPA Single Power Analysis
  • DPA Differential Power Analysis
  • SPA uses the characteristics of a single power consumption data in a cryptographic processor to DPA is a method for estimating the secret key by analyzing the difference between a large number of power consumption data.
  • Scalar multiplication of points on the elliptic curve is mainly performed.
  • Scalar multiplication The simplest implementation method of dXP is the binary method, which calculates the most significant bit (MSB) from the most significant bit (MSB) and the least significant bit (MSB).
  • MSB most significant bit
  • MSB most significant bit
  • MSB least significant bit
  • LSB Significant Bit
  • Algorithm 1 shows an example of the algorithm of the binary method (MS B)
  • Algorithm 2 shows an example of the algorithm of the binary method (LSB).
  • lowercase letters (d, etc.) represent scalar values
  • uppercase letters ( ⁇ , ⁇ , etc.) represent points on elliptic curves.
  • elliptic addition is denoted as ECADD
  • elliptic doubling is denoted as ECDB L.
  • the sign """ represents power multiplication
  • sequence enclosed by"("and") 2 "represents a digit represented by a binary number.
  • the number with S indicates the number of steps in the example program representing the algorithm.
  • T is a temporary variable
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d.
  • step S1 For example Consider the case of calculating scalar multiplication d XP for.
  • ECDBL (T) is set to the variable T in step S3, and the value of the variable T after processing is 2XP.
  • XP is output.
  • MSB binary method
  • T [0] and T [1] are both temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d.
  • step S1 For example Consider the case of calculating scalar multiplication dXP for.
  • step S2 a point is set to the variable T [l] and a point is set to the variable ⁇ [ ⁇ ].
  • step S7 ECDBL (T [1]) is set to the variable T [l], and the value of the variable T [l] after processing becomes 2 XP.
  • step S4 to S6 ECDBL (T [1]) is set in variable T [l], and the value of variable T [l] after processing is 4
  • step S5 ECADD (T [0], T [1]) is set to the variable T [0] in step S5
  • the variable T [ 0] is 5 XP.
  • step S7 the ECDBL (T [1]) force S is set to the variable T [l], and the value of the variable T [l] after processing is 8 ⁇ ⁇ .
  • step S7 ECDBL (T [1]) is set to the variable T [l], and the value of the variable T [l] after processing is 16 XP.
  • step S5 ECDBL (T [1]) is set to variable T [l], and the value of variable T [l] after processing is 32 mm.
  • step S5 marked with * is executed according to the bit value d [i] of d.
  • SP A uses this property to analyze the secret key d.
  • Many experiments show that the power waveforms of ECDBL and ECADD are characteristic and easily distinguishable. Therefore, by measuring the power waveforms generated in Algorithm 1 and Algorithm 2 calculations in the processor, the order and the number of ECDBL and ECADD calculations can be determined from the waveforms, and the secret key d can be determined by analysis. .
  • T [0] and T [l] are both temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the lower ith bit of d.
  • T [0], T [l], and T [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the lower ith bit of d.
  • T [0] T [0]
  • T [l] T [l]
  • T [2] are all temporary variables
  • d is a scalar value of ⁇ bits
  • d [i] is the value of the i-th lower bit of d.
  • Coron99 also describes DPA for these algorithms.
  • the secret key is analyzed by DPA. It is shown that it can be obtained.
  • the document Coron99 introduces a representation of points on an elliptic curve using random numbers called Randomized Projective Coordinates (RPC). Measures have been proposed.
  • RPC Randomized Projective Coordinates
  • Algorithm 3 ' an example of an algorithm in which RPC is performed on Algorithm 3
  • Algorithm 4' an example of an algorithm in which RPC is performed on Algorithm 4
  • Algorithm 5 ' an example of algorithm 5 is shown in Algorithm 5 '. respectively those subjected to RPC as Algorithm 5 1.
  • points on the elliptic curve represented by RPC are indicated by variables with dashes a or).
  • T, [0], T '[l], T, and [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the lower ith bit of d. is there.
  • invRPC indicates the inverse conversion from the RPC expression.
  • T, [0], T, [l], T, [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d .
  • invRPC indicates an inverse conversion from the RPC expression.
  • T '[0], T, [l], and T' [2] are temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d .
  • invRPC indicates an inverse conversion from the RPC expression.
  • ⁇ RC is a DPA countermeasure method using point expressions using point expressions using random numbers in the same way as RPC.
  • the method of applying R C is the same as that of R PC.
  • T "[0], T” [l], T “[2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the lower ith bit of d.
  • invRC indicates the inverse transformation from RC representation.
  • T "[0], T” [l], T “[2] are all temporary variables
  • d is an n-bit scalar value
  • • d [i] is the value of the i-th lower bit of d.
  • invRC indicates the inverse conversion from RC representation.
  • T "[0], T ,, [l], T” [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d is there.
  • InvHC indicates the reverse conversion from the RC expression.
  • a window method as a method of realizing the scalar multiplication d XP.
  • the window method with a width of 4 bits calculates 0 to 15 times P as the initial processing, stores the result as a table, and then divides the scalar value into 4-bit units (windows). Handles scalar multiplication.
  • the following shows an example of the window method (4 bits wide) as Algorithm 6.
  • d is a scalar value of n bits and n is a multiple of 4.
  • d [i, i-3] is a 4-bit value from the i-th lower bit of d to (i_3) bits.
  • W [i] is a table used in the window method.
  • d 5 bits and not a multiple of 4, so for convenience, 0 is inserted in the upper 3 bits and it is regarded as 8 bits.
  • n 8.
  • W [i] ECADD (W [il], P) is set in step S04.
  • the value set in W [i] is iXP.
  • step S09 ECDBL (T) is processed, and 4 X ⁇ is registered in the variable ⁇ .
  • step S10 ECDBL (T) is processed, and 8 XP is registered in the variable T.
  • step S11 T: 2 ECDBL (T) is processed, and 16 XP is registered in the variable T.
  • d is an 11-bit scalar value and n is a multiple of 4.
  • D [i, i-3] is a 4-bit value from the i-th lower bit of d to (i-3) bits.
  • T ' is one
  • the time variable, W '[i] is the table used in the window method, and invRPC is the inverse transformation from the RPC representation.
  • D [i, i-3] is a 4-bit value from the i-th lower bit of d to (i-3) bits.
  • T is a temporary variable
  • W [i] is a table used in the window method
  • invRC is the inverse transformation from the RC representation.
  • Algorithm 7 shows an example of the ES algorithm.
  • randomO is a function that generates an n-bit random number.
  • scalar (d, P) is a function for calculating the scalar multiplication d XP, and is specifically calculated using Algorithm 3 ′ to 6 ′ and Algorithm 3 "” described above.
  • the variables r, T, Tl, and T2 are all temporary variables.
  • ES can be said to be safe against SPA, DPA, and special point attacks, but the scalar multiplication used in ES is only for SPA and DPA countermeasures. There is a lot of waste to apply to ' ⁇ ra' and Algorithm 3 " ⁇ ra". In particular, when these methods are applied, the addition and doubling of points on the elliptic curve must be processed extra as compared with before the application, and there is a drawback that the processing overhead increases. .
  • the present invention has been made in view of such problems, and has an elliptic curve cryptographic device and an elliptic curve cryptosystem that can make it difficult to estimate secret information against a specific point attack and can increase the security of cryptographic processing. It is an object of the present invention to provide a method, an elliptic curve encryption program, and a computer-readable recording medium recording the program.
  • Non-Patent Document 1 (Reference Coron99)
  • Non-patent document 2 (Reference Izu-Takagi02)
  • Non-Patent Document 3 Reference Joye-TymenOl
  • Non-Patent Document 4 (Reference Goubin03)
  • Non-Patent Document 5 Reference Clavier- JoyeOl
  • an elliptic curve cryptographic device is an elliptic curve cryptographic device for performing elliptic curve cryptographic processing, wherein a point P on an elliptic curve on a finite field GF (p "m) is provided.
  • Coordinate conversion unit that converts the coordinates (X: Y: Z) into coordinates (r1X (X-s1): r2X (Y-s2): r3X (Z-s3)) , P is a prime number, m is an integer of 1 or more, rl, r 2, and r 3 are each an integer of 1 or more and (p — 1) or less, si, s 2, and s 3 are all 0 or more and (p _ l) The following integers, and the sign-represents a power.) and a scalar multiplication operation unit that performs scalar multiplication of the points on the elliptic curve transformed by the coordinate transformation unit.
  • the parameters s 1 and s 2, and at least one of s 3 has a value other than 0.
  • the scalar multiplication unit may perform scalar multiplication by a binary method using add 'and' double always, or may perform scalar multiplication by Montgomery Lada method. , Scalar multiplication may be performed in the window 'method.
  • the scalar multiplication unit may perform scalar multiplication by the X coordinate method, or may perform scalar multiplication by using continuous ellipse doubling.
  • the elliptic curve cryptography method of the present invention provides an elliptic curve encryption
  • the coordinates of the point P on the elliptic curve (X: Y: Z) on the finite field GF (p "m) are represented by the coordinates (r1X (X-s1): r2X (Y— s 2): coordinate transformation step for transforming into r 3 X (Z—s 3)) (where P is a prime number, m is an integer of 1 or more, r 1, r 2, r 3 are 1 or more and (p — 1) An integer less than or equal to, sl, s2, and s3 are each an integer greater than or equal to 0 and less than or equal to (p_l), and the sign “represents a power.”
  • the ellipse transformed in this coordinate transformation step It is characterized by having a scalar multiplication operation step for performing scalar multiplication of points on a curve, and at least one of the parameters s 1, s 2 and s
  • scalar multiplication may be performed by a binary method using add-and-double-all-AIDS.
  • scalar multiplication may be performed by Montgomery-ladder method.
  • scalar multiplication may be performed by the window method.
  • scalar multiplication may be performed by the X coordinate method, and in the scalar multiplication operation step, scalar multiplication may be performed using continuous ellipse doubling.
  • the elliptic curve cryptographic program of the present invention is an elliptic curve cryptographic program for performing elliptic curve cryptographic processing, wherein the coordinates (X: Y: Z) of a point P on the elliptic curve on a finite field GF (p "m) To a coordinate (rl X (X-si): r 2 X (Y-s 2): r 3 X (Z-s 3)) (where p is a prime number and m is an integer of 1 or more) , R 1, r 2, and r 3 are each an integer of 1 or more and (p ⁇ 1) or less, sl, s 2, and s 3 are each an integer of 0 or more and (p ⁇ 1) or less, and At least one of s 1, s 2, and s 3 has a value other than 0.
  • the sign represents a power.
  • the scalar multiplication of the point on the elliptic curve transformed by the coordinate transformation unit is performed.
  • the computer functions as a scalar multiplication operation unit that performs the operation.
  • Scalar multiplication may be performed by a binary method using do-double-always, or scalar multiplication may be performed by the Montgomery's ladder method when a computer functions as a scalar multiplication operation unit.
  • a scalar multiplication unit When you make your computer work as a window, you can do scalar multiplication in the window 'method.
  • scalar multiplication may be performed by the X coordinate method.
  • continuous ellipse doubling may be used.
  • Scalar multiplication may be performed.
  • the computer-readable recording medium of the present invention records the above-described elliptic curve encryption program.
  • the elliptic curve encryption device As described above, according to the elliptic curve encryption device, the elliptic curve encryption method, the elliptic curve encryption program, and the computer-readable recording medium storing the program according to the present invention, the following effects and advantages are obtained.
  • the coordinates (X: Y: Z) of the point P on the elliptic curve on the finite field GF are coordinates (r 1 X (X-s 1): r 2 X (Y—s 2) : R 3 X (Z—s 3)) (where P is a prime number, m is an integer of 1 or more, and rl, r2, and r 3 are random integers of 1 or more and (p-1) or less) , Si, s2, s3 are all random integers greater than or equal to 0 and less than or equal to (p-1), and at least one of these sl, s2, s3 has a value other than 0 In addition, the sign 'represents a power.) Since the scalar multiplication of the points on the converted elliptic curve is performed, the scalar multiplication in the elliptic curve cryptography is calculated with resistance to a side channel attack. It becomes possible.
  • FIG. 1 is a diagram for explaining elliptic addition.
  • FIG. 2 is a diagram for explaining elliptic doubling.
  • FIG. 3 is a diagram showing a configuration of a main part of the elliptic curve symbol device according to the present invention.
  • FIG. 4 is a block diagram showing a functional configuration of the elliptic curve encryption device as one embodiment of the present invention.
  • FIG. 5 is a diagram showing an example of a hardware configuration of an elliptic curve encryption device that executes the elliptic curve encryption program of the present invention.
  • the elliptic curve encryption device includes, for example, an information processing device dedicated to elliptic curve encryption, a personal computer, an IC chip built in an IC card (smart card), a mobile phone, and a portable information terminal. It is realized as a device (PDA (Personal Data Assistant), etc.), DVD player, etc., and has a processor that performs calculations.
  • an information processing device dedicated to elliptic curve encryption
  • a personal computer an IC chip built in an IC card (smart card), a mobile phone, and a portable information terminal. It is realized as a device (PDA (Personal Data Assistant), etc.), DVD player, etc., and has a processor that performs calculations.
  • PDA Personal Data Assistant
  • the elliptic curve E on GF (p "m) is a set of points (X, y) satisfying the following equation, plus a point ⁇ called the point at infinity (hereinafter sometimes referred to as the zero point). Note that the point at infinity ⁇ may be expressed as 0.
  • x 3 ⁇ "2 + a l X A,-a 2-x l -x 2,
  • the finite field GF (p) is called a prime field.
  • the elliptic curve E over the prime field GF (p) is given by the equation
  • the point at infinity ⁇ may be represented as 0.
  • A, b, x, and y are elements of GF (P).
  • a point on the elliptic curve can be represented in a coordinate format such as (x, y).
  • the point at infinity ⁇ is the only point that cannot be represented in a coordinate format such as (X, y).
  • FIG. 1 is a diagram for explaining elliptic addition
  • FIG. 2 is a diagram for explaining elliptic doubling.
  • the computation time for elliptic addition, elliptic doubling, and scalar multiplication is often estimated by the sum of the computation times for multiplication, square computation, and inverse computation in a finite field. This is because the actual calculation of elliptic addition, elliptic doubling, and scalar multiplication is performed by a combination of addition and subtraction in a finite field, multiplication-squaring, and inverse calculation, and in many cases, the calculation time of addition and subtraction is This is because it is negligibly short compared to the calculation time.
  • the point of the elliptic curve on GF (p "m) is represented by a combination of three elements such as (X: Y: Z), where GF (p" m) elements r 1 ⁇ 0, r 2 ⁇ 0, r 3 ⁇ 0, sl, s 2, s 3
  • the linear transformation coordinates are represented by the coordinates (X: Y: Z) of the point P on the elliptic curve on the finite field and the coordinates (r 1 X (X-si): r 2 X (Y-s 2): r 3 X (Z-s 3)), where r 1, r 2, and r 3 are any integers other than 0, and s 1, At least one of s 2 and s 3 is an integer other than 0.
  • these r1, r2, r3, si, s2, and s3 may be referred to as parameters of the linear transformation coordinates.
  • the elliptic curve E on GF (p) can be expressed by the following equation.
  • FIG. 3 is a diagram showing a configuration of a main part of the elliptic curve encryption device 11 according to the present invention.
  • the elliptic curve encryption device 11 includes an operation unit (processor) 12 and a storage 16.
  • the storage unit 15 stores operation programs such as elliptic addition, ellipse doubling, and ellipse 2 "k multiplication of elliptic curve cryptography, which will be described later.
  • the operation unit 12 includes an operation unit 13 and a register. Group 14 and operation result output register group 1
  • the arithmetic unit 13 executes the elliptic curve encryption program stored in the storage unit 16 using the register group 14, and outputs the operation result to the operation result output register group 15. I have.
  • Each of the register group 14 and the operation result output register group 15 is composed of a plurality of registers. These registers store numerical values for performing the operation, results of the operation, and memory of the code currently being executed. The address, the state of the CPU, and the like are stored.
  • the operation result output register group 15 stores, in particular, the operation result by the operation unit 13.
  • FIG. 4 is a block diagram showing a functional configuration of the elliptic curve encryption device 11 as one embodiment of the present invention.
  • the elliptic curve cryptosystem 11 includes a zero point determination unit 21, a scalar multiplication unit 22, a linear coordinate conversion unit (coordinate conversion unit) 23, and a random number generation unit 24. ing.
  • the random number generation unit 24 generates random numbers r 1, r 2, and r 3, and passes the generated random numbers r 1, r 2, and r 3 to the scalar multiplication unit 22 and the linear coordinate conversion unit 23. It's swelling.
  • the zero point determination unit 21 determines whether or not the result of the scalar multiplication is a zero point (infinity point).
  • the linear coordinate transformation unit 23 converts the coordinates (X: Y: Z) of the point P on the elliptic curve on the finite field GF (p) into the coordinates (r1X (X-s1): r2X (Y—s 2): Convert to r 3 X (Z—s 3)) (linear coordinate conversion), and pass the converted coordinates (hereinafter, also referred to as linear conversion coordinates) to the scalar multiplication unit 22. It has become.
  • the scalar multiplication processing unit 22 calculates the scalar multiplication d XP of the points on the elliptic curve transformed by the linear coordinate transformation unit 23. Elliptic addition and elliptical doubling are performed using various algorithms described later. Calculation, elliptic 2-k multiplication, etc. Scalar multiplication is performed.
  • the arithmetic unit 12 executes a program stored in the storage unit 16, thereby executing a zero-point determination unit 21, a scalar multiplication unit 22, It functions as a linear coordinate converter 23 and a random number generator 24.
  • LCECADD elliptic addition
  • LCECDBL elliptic doubling
  • T24 T23-T21 / * 2 * R A 2-3 * T * W A 2 + 2 * s
  • T10 T3 + T8 / * a * Zl 8 4 + 3 * ⁇ 1 ⁇ 2 * /
  • T20 T17 + s / * M A 2 + s * /
  • T24 T22 + s / * 4 * Xl * Yl A 2 + s * /
  • T25 T24-X4 / * 4 * Xl * Yl A 2 + s-X4 * /
  • the scalar multiplication unit 22 calculates the scalar multiplication d XP, the binary method (LSB, add / double. Always).
  • Algorithm 10 an algorithm example used by the scalar multiplication processing unit 22 for scalar multiplication is shown as Algorithm 10.
  • the linear coordinate conversion unit 23 converts the coordinates (X: Y: Z) of the point P on the elliptic curve into the coordinates (r 22 X (X—s): r "3 XY: r XZ) (linear Coordinate transformation)
  • T [2]: LCECDBL (T [2])
  • LC stands for transformation to linear mapping coordinates (linear coordinate transformation)
  • invLC stands for the inverse transformation
  • T [0], T [l], and ⁇ [2] are all temporary variables
  • d is a scalar value of ⁇ bits
  • d [i] is the value of the i-th lower bit of d. That is, in the elliptic curve cryptographic device 11 of the first embodiment, the calculation unit 12 functions as the linear coordinate conversion unit 23 by executing steps SI and S2 of Algorithm 10 described above, and executes steps S3 to S7. By doing so, it functions as the scalar processing unit 22.
  • the algorithm 10 used by the scalar multiplication processing unit 22 uses the add / double 'always method, it is safe for SPA and DPA.
  • the linear coordinate transformation unit 23 calculates For the elliptic curve E on the prime field GF (p), the coordinates (X: Y: Z) of the point P on the elliptic curve are represented by the coordinates (r1X (X-s1): r2X (Y—s 2): r 3 X (Z—s 3)), and the scalar multiplication processing unit 22 calculates the elliptic addition and the elliptic doubling at the linearly converted coordinates after the conversion, so that the RPC in the Jacobian coordinates is calculated. Similar random effects can be expected, and it is safe against DP A.
  • the value stored in the variable T [2] is irrelevant to d, and the value is different from step S5 except for step S5. It will not change. Therefore, as a modification of the binary method (LSB, add-and-double-always), a modified add-and-double-all-size algorithm represented by the following algorithm example 11 is applied. You can also.
  • a modified quadratic algorithm such as that shown in Algorithm 11 is used instead of add-and-double-always. AND'double alwayss is used, and the rest of the configuration is almost the same as the elliptic curve encryption device 11 of the first embodiment described above.
  • Algorithm 11 an algorithm example used by the scalar multiplication processing unit 22 for scalar multiplication is shown as Algorithm 11.
  • LC represents the transformation to linear mapping coordinates
  • invLC represents the inverse transformation
  • T [0], T [l], and ⁇ [2] are all temporary variables
  • d is a scalar value of ⁇ bits
  • d [i] is the value of the i-th lower bit of d.
  • the temporary variables used in step S06 and step S10 are shared.
  • the operation unit 12 functions as the linear coordinate conversion unit 23 by executing steps S01 and S02 of Algorithm 11 described above, and performs steps S03 to S12. By executing the above, it functions as a scalar processing unit 22.
  • the algorithm 11 used by the scalar multiplication processing unit 22 uses the modified add-and-double-all-phase, so that the SPA Safe for you.
  • the coordinates (X: Y: Z) of the point P on the elliptic curve are represented by the coordinates (r1X (X-s1): r2X (Y-s2): r3 'X (Z—s 3)), and the scalar multiplication processing unit 22 calculates elliptic addition and elliptic doubling at the linearly transformed coordinates after the conversion, so that randomness similar to RPC in Jacobian coordinates is used. Effective and safe against DP A.
  • the scalar multiplication processing unit 22 since the scalar multiplication processing unit 22 performs the scalar multiplication by the X coordinate method, it is safe for SPA and DPA and can shorten the calculation time.
  • the parameters (rl, r2, r3, sl, s2, s3) (r, r, r, s, 0, 0) are used as described above.
  • the calculation time can be reduced.
  • the X coordinate method is an algorithm that calculates elliptic addition / ellipse doubling without using the y coordinate.
  • Algorithms 12m, 12a, 13, 14m, and 14a expressed in projective coordinates on the prime field Algorithm examples of the x-coordinate method disclosed in the document Izu-Takagi02 for elliptic curves are shown below as Algorithms 12m, 12a, 13, 14m, and 14a, respectively.
  • the symbol m added to the end of the algorithm number indicates that a multiplicative EC ADD is used, and the symbol a indicates that an additive E CADD is used.
  • X3 Z3 'X [(XlXX2-aXZlXZ2) A 2-4XbXZlXZ2X (XlXZ2 + 2XZl)
  • X4 (Xl A 2-aXZl A ) A 2-8XbXXlXZl A 3
  • the linear coordinate transformation unit 2 According to the elliptic curve encryption device 11 of the third embodiment of the present invention, the linear coordinate transformation unit 2
  • the scalar multiplication processing unit 22 calculates elliptic addition and elliptic doubling at the linearly converted coordinates after the conversion, so that the RPC in the Jacobian coordinate is used. The same random effect can be expected, and it is safe against DPA.
  • addition and doubling are performed by one function by using xECADDDBLni and xECADDDBLa.
  • the number of function calls can be reduced, and processing can be accelerated.
  • the operation result can be shared between addition and doubling, the amount of calculation can be reduced.
  • the elliptic curve encryption device 11 is designed such that the scalar multiplication processing unit 22 in the elliptic curve decoding device 11 of the third embodiment calculates the scalar multiplication d XP in Montgomery. 'Ladder is used, and other parts are The configuration is almost the same as that of the elliptic curve cryptosystem 11 of the third embodiment.
  • Algorithm 15 an algorithm example used by the scalar multiplication processing unit 22 for scalar multiplication is shown as Algorithm 15.
  • T [l]: xECADD (T [0], T [l], LC (P))
  • xLC is the transformation of the linear mapping coordinates to the coordinates used in the X coordinate method
  • invLC represents the inverse transformation
  • T [0], T [l], and ⁇ [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d.
  • the same operation and effect as those of the above-described fourth embodiment can be obtained, and the algorithm 15 used by the scalar multiplication processing unit 22 can be obtained. Because it uses Montgomery's ladder, it is safe for SPA and DPA.
  • the scalar multiplication unit 22 uses the improved Montgomery's ladder when calculating the scalar multiplication d XP. Is substantially the same as the elliptic curve encryption device 11 of the fourth embodiment.
  • the improved Montgomery ladder reduces the number of function calls by performing addition and doubling with one function by using xECADDDBL, similar to Algorithms 14m and 14a described above. It can speed up processing, In addition, the amount of calculation can be reduced by sharing the operation result between addition and doubling.
  • Algorithm 15 ′ an example of an algorithm used by the scalar multiplication processing unit 22 for scalar multiplication is shown as Algorithm 15 ′.
  • xLC is the transformation of the linear mapping coordinates to the coordinates used in the X coordinate method
  • invLC represents the inverse transformation
  • T [0], T [l], and ⁇ [2] are all temporary variables
  • d is an n-bit scalar value
  • d [i] is the value of the i-th lower bit of d.
  • the same operation and effect as those of the fourth embodiment described above can be obtained, and the algorithm 15 used by the scalar multiplication processing unit 22 can be obtained.
  • XECADDDBL is used, so by performing addition and doubling with one function, the number of function calls can be reduced and the processing speed can be increased.
  • the operation result can be calculated by addition and doubling. The amount of calculation can be reduced by sharing.
  • scalar multiplication in elliptic curve cryptography can be calculated with resistance to side channel attacks.
  • An elliptic curve encryption device 11 includes a scalar multiplication unit
  • the elliptic 2 k multiplication means to calculate 2 k times 2 k XP of a given point.
  • Elliptical 2 k multiplication is susceptible calculated by there use elliptic doubling consecutively k times, when treated as one function, the intermediate values cutting The reduction may allow for more efficient calculations than being applied continuously.
  • Algorithm 1 6 described above was applied elliptical 2 k multiplication relative Jacobian coordinates While those, can also apply the ellipse 2 k multiplication for linear conversion coordinates performed by the linear coordinate transforming unit 23 of the present invention in place of the Jacobian coordinates, This ensures that the improved calculation speed Can be done.
  • a conversion may be performed.
  • the elliptical encryption device can be realized by, for example, an information processing device such as a personal computer.
  • a CPU (Central Processing Unit) 31 executes elliptic curve cryptography elliptic addition, elliptic doubling, and the like.
  • the memory 32 is used as various registers used for operations.
  • the external storage device 33 stores OS, an elliptic curve encryption program, and the like.
  • the medium driving device 34 is a device that reads or writes a portable recording medium 35 such as a CDROM, a DVD, a flexible disk, and an IC card.
  • the input device 36 is a device for inputting data such as a keyboard.
  • the output device 37 is a device such as a display and a printer.
  • the network connection device 38 is a device for connecting to a network such as the Internet, and can download a program from a server on the network via this device.
  • the CPU 31, the memory 32, the external storage device 33, the input device 36, and the like are connected by a bus 39.
  • the CPU 31 of the information processing device executes the elliptic curve cryptographic program, thereby executing the above-described zero point determination unit 21, scalar multiplication unit 22, linear coordinate conversion unit (coordinate conversion unit) 23, and random number generation. It functions as part 24.
  • the programs (elliptic curve cryptographic programs) for realizing the functions of the zero point determination unit 21, the scalar multiplication unit 22, the linear coordinate conversion unit (coordinate conversion unit) 23, and the random number generation unit 24 are as follows.
  • flexible disk CD-ROM, CD-R, CD-R / W, DVD-R, DVD-R, DVD-R / W, magnetic disk It is provided in a form recorded on a computer-readable recording medium such as a disk, an optical disk, and a magneto-optical disk.
  • a computer-readable recording medium such as a disk, an optical disk, and a magneto-optical disk.
  • the computer reads the program from the recording medium, transfers the program to an internal storage device or an external storage device, and stores and uses the program.
  • the program may be recorded on a storage device (recording medium) such as a magnetic disk, an optical disk, or a magneto-optical disk, and provided to the computer from the storage device via a communication path.
  • a computer is a concept including hardware and an operating system, and means hardware that operates under the control of an operating system.
  • the hardware is operated by the application program alone without the need for the operating system, the hardware itself corresponds to the computer.
  • the hardware includes at least a microprocessor such as a CPU and means for reading a computer program recorded on a recording medium.
  • the elliptic curve encryption device 11 has a function as a computer. They have.
  • the above-mentioned flexible disk CD-ROM, CD-R, CD-R / W, DVD, DVD-R, DVD-R / W, magnetic disk, optical disk, magneto-optical
  • computers such as IC cards, ROM cartridges, magnetic tapes, punch cards, internal storage devices (memory such as RAM and ROM), external storage devices, and printed materials on which codes such as bar codes are printed
  • Various readable media can be used.
  • the present invention can be applied to various products such as an IC card, a DVD device, a mobile phone, and a personal computer, as well as a device dedicated to encryption and decryption of elliptic curve cryptography.
  • the zero point determination unit 21, the scalar multiplication unit 22, the linear coordinate conversion unit 23, and the random number generation unit 24 are executed.
  • the function is not limited to this.
  • some of the zero point determination unit 21, the scalar multiplication unit 22, the linear coordinate conversion unit 23, and the random number generation unit 24 The function may be processed by an external device. For example, only the scalar multiplication processing unit 22 may be executed.
  • the elliptic curve cryptosystem 11 may be realized by, for example, a smart card having a processor, or storing a secret key or a secret key only in a memory of a smart card, and The elliptic curve cryptographic process may be performed by an external device (elliptic curve No. ⁇ device) communicably connected.
  • an external device elliptic curve No. ⁇ device
  • the parameter (rl, r2, r3) is As in the third to fifth embodiments, (r, r, r) may be used, and some or all of r 1, r 2, and r 3 may be different from each other. Les ,.
  • the parameters (r 1, r 2, r 3) are replaced by the first embodiment and As in the second embodiment, (r2, r "3, r) may be used, and some or all of r1, r2, and r3 may be different from each other. Les ,.
  • the parameters in the parameters (r 1, r 2, r 3, sl, s 2, s 3) used by the linear coordinate conversion unit 23 for the linear coordinate conversion is not limited to (s, 0, 0).
  • the part of the parameter (si, s2, s3) is not limited to (s, 0, 0).
  • si, s2, and s3 each have a value other than 0.
  • only 3 1 and 5 3 are 0, only s 1 and s 2 are 0, only s 3 is 0, only s 2 is 0, and only s 1 is 0.
  • these Some or all of s 1, s 2, and s 3 may be different from each other.
  • a special point whose y coordinate is 0 is represented as a point of s in the Y coordinate of the linear transformation coordinate, and a scalar And it is safe against special point attacks on the y-coordinate.
  • a non-zero numerical value s to the parameter s 3
  • a special point whose z coordinate is 0 is represented as a point whose z coordinate in linear transformation coordinates is s, and the scalar multiplication It does not appear on the way and is safe against special point attacks on the z coordinate.
  • the scalar multiplication processing unit 22 calculates the scalar multiplication unit 22 using the window method (see Algorithm 6, 6 ′, 6 6). The calculation may be performed so that it is secure against special point attacks and also secure against SPA.
  • an elliptic curve encryption device an elliptic curve encryption method, an elliptic curve No. program, and a computer-readable recording medium on which the program is recorded by a person skilled in the art. It is possible to implement 'manufacture'. Industrial applicability
  • the elliptic curve encryption device As described above, the elliptic curve encryption device, the elliptic curve encryption method, the elliptic curve encryption program, and the computer-readable recording medium storing the program according to the present invention are useful for performing the elliptic curve encryption process. Effective against channel attacks.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Signal Processing (AREA)
  • Mathematical Physics (AREA)
  • Computational Mathematics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Algebra (AREA)
  • Complex Calculations (AREA)
  • Facsimile Image Signal Circuits (AREA)
  • Storage Device Security (AREA)
  • Image Processing (AREA)

Abstract

楕円曲線暗号処理を行なう楕円曲線暗号装置である。　有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）とをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有するように構成することにより、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することができる。

Description

楕円曲線暗号装置， 楕円曲線暗号方法， 楕円曲線暗号プログラムおよび同プログ ラムを記録したコンピュータ読取可能な記録媒体 技術分野
本発明は、 楕円曲線暗号処理に関し、 特に、 楕円曲線暗号処理を行なうプロセ ッサにおける電力解析攻撃の防止に用いて好適な、 楕円曲線暗号装置， 楕円曲線 喑号方法， 楕円曲線暗号プログラムおょぴ同プログラムを記録したコンピュータ 明
読取可能な記録媒体に関する。 書
背景技術
暗号方式には公開鍵暗号方式と共通鍵暗号方式とが含まれる。 公開鍵暗号方式 は、 暗号化と復号化とで異なる鍵 （キー） を用いる方式である。 典型的な公開鍵 暗号方式では、 暗号化を行なうための鍵 （公開鍵） を公開しておき、 この公開鍵 を用いて平文を暗号化して受信者に送信する。 暗号文を復号化するための鍵 （秘 密鍵） は受信者のみが知る秘密情報として保持されており、 受信者がこの秘密鍵 を用いて暗号文を復号化することにより平文を得ることができる。
また、 近年では、 公開鍵暗号と して楕円曲線喑号 （Elliptic Curve Cryptography)が注目を集めている。 この楕円曲線暗号にはさまざまな種類の暗 号化 ·復号化アルゴリズムが知られているが、 ほとんどの暗号化 ·復号化処理で スカラー倍算という演算が用いられる。 ここでスカラー倍算とは、 楕円曲線上の ベースポィントと呼ばれる点 Pとスカラーと呼ばれる整数 dと力ゝら、 d X P = .P + P + ..+ P ( d個の和） を計算することである。 なお、 楕円曲線暗号において は、 ベースポイント Pとスカラー倍点 d X Pとから、 スカラー d (秘密鍵） を求 めることは困難であることが知られている。
ここで、 楕円曲線暗号の例として、 E C E S暗号方式を説明する。 送信者 Aが 秘密鍵 s (sは整数） を持ち、 受信者 Bが秘密鍵 t ( tは整数） を持つ場合に、 楕 円曲線 Eと、 楕円曲線 E上に設定されるベースポイント P ( = ( X , y ) ) と、 公 開鍵 s X P (送信者 Aの秘密鍵 sとベースポイント Pとのスカラー倍点） と、 公 開鍵 t X P (受信者 Bの秘密鍵 tとベースポイント Pとのスカラー倍点） とがあ らかじめ公開されている。
このとき送信者 Aは、 自分の秘密鍵 sと、 受信者 Bの公開鍵 t X Pとのスカラ 一倍算 S X ( t X P) を計算し、 その X座標のビット表現を求め、 このビット表 現とメッセージのビット表現との間でビット対応の E O R (Exclusive OR：排他 的論理和） 演算を施すことで、 メッセージ mに対する暗号文 Cを生成し、 それを 受信者 Bに送信する。 受信者 Bは、 自分の秘密鍵 tと、 送信者 Aの公開鍵 s X P とのスカラー倍算 t X ( s X P) を計算し、 その X座標のビット表現を求める。 そして、
s X ( t X P) = t X ( s XP)
という関係式が成立することを考慮して、 そのビット表現と暗号文 Cのビット表 現との間でビット対応の E〇 R演算を施すことで、 暗号文 Cを復号してメッセー ジ mを得る。 このようにして EC E S喑号と呼ばれる喑号方式では、 スカラー倍 を用いて暗号化 ·複号化処理を行なう。
また、 暗号の分野における技術の一つに、 解読技術と呼ばれるものがある。 解 読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のこ とであり、 様々な手法が存在する。 その中で最近注目されている技術に、 サイド チヤネル攻撃と呼ばれる手法がある。
サイドチャネル攻撃は、 1 9 9 8年に Paul Kocherによって考案された手法で あって、 スマートカード等に搭載された暗号プロセッサに様々な入力データを与 えた時のサイドチャネル情報 （消費電力データ ·消費時間データ ·電磁波データ 等） を収集 ·解析することにより、 暗号プロセッサ内部の鍵情報を推定する手法 である。 サイドチャネル攻撃を用いると、 公開鍵暗号、 共通鍵暗号共に暗号プロ セッサから秘密鍵を推定できる可能性があることが指摘されている。
このサイドチャネル攻撃の中で、 電力解析攻撃は強力な攻撃法である。 この電 力解析攻撃として、 単純電力解析 （S PA； Single PowerAnalysis) と、 差分電 力解析 （D P A； Differential Power Analysis) との 2種類の手法が知られてい る。 S PAは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の 推定を行なう方式であり、 D P Aは多数の電力消費データの差分を解析すること で秘密鍵の推定を行なう方式である。
そして、 楕円曲線暗号に対しても、 上述した S PAや DPAを適用することが 可能である。 この場合、 スカラー倍算が攻擊対象となることが多い。 詳細な推定 法こつレヽて fま、 Jean-Sebastem Coron "Resistance against Difrerential Power Analysis for Elliptic Curve Cry tosy stems", Cryptographic Hardware and Embedded Systems 1999 (CHES1999), Lecture Notes in Computer Science vol.1717, Springer-Verlag, pp.292-302, 1999 (以下、 文献 Coron99という） 等 の文献にて述べられている。
さて、 楕円曲線暗号の暗号化 ·復号化処理では、 楕円曲線上の点のスカラー倍 算が中心となる。 スカラー倍算 dXPの最も単純な実現手法としてバイナリ法 （ Binary method) があり、 最上位ビット （Most Significant Bit； M S B ) から計 算する方法 （バイナリ法 （MSB)) と、 最下位ビッ ト （Least Significant Bit； L SB) から計算する方法 （バイナリ法 （L SB)) とが知られている。
ここで、 バイナリ法 (MS B) のアルゴリズム例を (1) Algorithm 1に、 又、 バイナリ法 （L S B) のアルゴリズム例を （2) Algorithm 2に示す。 なお、 以 下、 特に断りの無い限り、 小文字 （d等） はスカラー値を表わし、 大文字 （Ρ,Τ 等） は楕円曲線上の点を表わすものとする。 又、 楕円加算を ECADD、 楕円 2 倍算を ECDB Lと表わす。 更に、 符号 " " " はべき乗算を表わすものとし、 " （ " と "） 2" とによって囲まれた数列は 2進数で表現された数字を表わす。 又、 " S1： "等のように、 Sを付した数字はァルゴリズムを表わすプログラム例におけ るステツプ数を示すものとする。
(1) Algorithm 1 [バイナリ法 （MSB)]
Si: T :=P
S2: for i = n_2 downto 0 {
S3： T：= ECDBL( T )
S4: if ( d[{| 1 ) {
S5: T：= ECADD( T, P) ※
S6: } ST- }
S8: return( T )
ここで、 Tは一時変数、 dは nビットのスカラー値で、 d[i] は dの下位 i番目 のビットの値である。 ，
例えば
Figure imgf000006_0001
についてスカラー倍算 d X Pを計算す る場合を考える。 ステップ S1においては変数 Tに点 Pが設定され、 その次のス テツプ S2〜S7において、 i=3,2，l，0に対応する各処理が行なわれる。
i=3のとき、 ステップ S3では変数 Tに ECDBL(T)が設定され、 処理後の変数 T の値は 2XP となる。 また、 i=3 のときには、 d[i]=d[3]=0なので、 ステップ S4〜S6はスキップされる。
i=2 のとき、 ステップ S3では変数 Tに ECDBL(T)が設定され、 処理後の変数 Tの値は 4XP となる。 又、 i=2のときには、 d[i]=d[2]=lなので、 ステップ S5 では変数 Tに ECDBL(T，P)が設定され、 処理後の変数 Tの値は 5XPとなる。 i=lのとき、 ステップ S3では変数 Tに ECDBL(T)が設定され、 処理後の変数 Tの値は 10XPとなる。 又、 i=lのときには、 d[i]=d[l]=0なので、 ステップ S4 〜S6はスキップされる。
i=0とき、 ステップ S3では変数 Tに ECDBL(T)が設定され、 処理後の変数 T の値は 20XPとなる。 又、 i=0のときには、 d[i]=d[0]=lなので、 ステップ S5で は変数 Tに ECDBL(T，P)が設定され、 処理後の変数 Tの値は 21 XPとなる。 以上でステップ S2〜S7の処理が終了し、 最後のステップ S8で変数 Tの値 21
XPが出力される。 このようにバイナリ法 （MSB) では、 スカラ値の最上位ビ ットから処理が行なわれるのである。
(2) Algorithm 2 レ イナリ法 （LSB)]
Si: T[l] := Ρ
S2: T[0]：= O
S3： for i = 0 up to n-1 {
S4: if (d[i] = 1) {
S5: T[0]：= ECADD( T[0]， T[l] ) ― ※
S6: } S7: T[l〗：= ECDBL( T[l] )
S8: }
S9: return( Τ[θ] )
ここで T[0],T[1] はいずれも一時変数、 dは nビットのスカラー値で、 d[i]は dの下位 i番目のビッ トの値である。
例えば
Figure imgf000007_0001
についてスカラー倍算 dXPを計算する 場合を考える。 ステップ S1においては変数 T[l] に点 Ρ力 又、 変数 τ[ο]に点 Οが設定される。次のステップ S3〜S8において i=0,l,2，3,4に対応する各処理が 行なわれる。
i=0 のときには、 d[i]=d[0]=l なので、 ステップ S5 では変数 T[0]に
ECADD(T[0]，T[1])が設定され、 処理後の変数 T[0]の値は Pとなる。 ステップ S7 では変数 T[l]に ECDBL(T[1])が設定され、処理後の変数 T[l]の値は 2 X Pとなる i=lのときには、 d[i]=d[l]=0なので、 ステップ S4〜S6はスキップされ'る。 ス テツプ S7では変数 T[l]に ECDBL(T[1])が設定され、 処理後の変数 T[l]の値は 4
ΧΡとなる。
i=2 のときには、 d[i]=d[2]=l なので、 ステップ S5 では変数 T[0]に ECADD(T[0],T[1])が設定され、 処理後の変数 T[0]の値は 5 XPとなる。 ステップ S7では変数 T[l]に ECDBL(T[1])力 S設定され、 処理後の変数 T[l]の値は 8 Χ Ρと なる。
i=3のときには、 d[i]=d[3]=0なので、 ステップ S4〜S6はスキップされる。 ス テツプ S7では変数 T[l]に ECDBL(T[1])が設定され、 処理後の変数 T[l]の値は 16 X Pとなる。
i=4 のと きには、 d[i]二 d[0]=l なので、 ステップ S5 では変数 T[0]に ECADD(T[0]，T[1])が設定され、 処理後の変数 T[0]の値は 21 XPとなる。 ステツ プ S7では変数 T[l]に ECDBL(T[1])が設定され、処理後の変数 T[l]の値は 32 ΧΡ となる。
以上でステップ S3〜S8の処理が終了し、 最後のステップ S9で変数 T[0]の値 21 X P が出力される。 このようにバイナリ法 (L S B )では、 スカラ値の最下位ビ ットから処理が行なわれるのである。
さて、 上述した Algorithm 1および Algorithm 2を点のスカラ一倍算に使用し た場合には、 いずれも※印を付したステップ S5の処理は、 dのビット値 d[i]に応 じて実行されたりされなかったりする。 S P Aではこの性質を利用して秘密鍵 d を解析する。 多くの実験から、 ECDBLと ECADDの電力波形は特徴的で容易に 区別可能であることが知られている。 従って、 プロセッサにおける Algorithm 1 およぴ Algorithm 2の演算において発生する電力波形を測定することによって、 その波形から ECDBLと ECADDの演算の順序と回数がわかり、秘密鍵 dを解析 して求めることができる。
この S P Aへの対策として、 ア ド · アンド ' ダブル ·オールウェイズ ( add-and-double-always) と呼ばれる、 加算と 2倍算とを常に行なう方法が 文献 Coron99で提案されている。 この方法では、常に ECDBL演算と ECADD演算と が交互に行なわれるので S P Aに対して安全である。以下に、先述した Algorithm 1および Algorithm 2に対してァド ·アンド ·ダブル ·オールウェイズを施した アルゴリズム例を Algorithm 3および Algorithm 4として示す。
( 3 ) Algorithm 3 [バイナリ法 （M S B , アド ·アンド .ダブル ·オールゥ エイズ)]
Si: T[0]：= Ρ
S2: for l = n-2 downto 0 \
S3： T[0]：= ECDBL(T[0] )
S4: T[l]：= ECADD( T[0], P )
S5: T[0]：= T[d[i]]
S6: }
S7: return( T[0] )
ここで、 T[0], T[l] はいずれも一時変数、 dは nビットのスカラー値で、 d[i] は dの下位 i ビット目の値である。
( 4 ) Algorithm 4 [バイナリ法 （L S B， アド .アンド .ダブル 'オールゥ エイズ)]
Si: T[0]：= Ο S2: T[2]：= P
S3： for i = 0 upto n-1 {
S4: T[l]：= ECADD( T[0]， T[2] )
S5: T[2]：= ECDBL( T[2] )
S6: T[0]：= T[d[i]]
S7: }
S8: return( T[0])
ここで、 T[0], T[l], T[2]はいずれも一時変数、 dは nビットのスカラー値で、 d[i]は dの下位 i ビット目の値である。
上述した Algorithm 3および Algorithm 4を用レ、ることにより S P Aを防止す ることができる。 又、 同様の効果をもつ方式として、 モンゴメリ ' ラダー （ Montgomery-Ladder j を用レヽ 7こ方法力、、 T. Izu, and T. Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks", Public -Key Cryptography 2002 (PKC2002), Lecture Notes in Computer Science vol. 2274, pp.280.296, Springer- Verlag, 2002. (以下、文献 Iz -Takagi02 という） にて提案されている。
スカラー倍算 d X Pにおいて、モンゴメリ 'ラダーでは常に ECDBLと ECADD を交互に計算するので、 S P Aに対して安全である。 モンゴメ リ · ラダーのアル ゴリズム例を Algorithm 5に示す。
( 5 ) Algorithm 5 [モンゴメリ · ラダー]
S1 T[0]：= Ρ
S2 T[l]：= ECDBL( T[0] )
S3 for i = n-2 downto 0 {
S4 T[2] := ECDBL( T[d[i]] )
S5 T[l] := ECADD( T[0], T[l] )
S6 T[0] := T[2-d[i]]
S7 T[l]：= T[l+d[i]]
S8 }
S9 return ( T[0] ) ここで T[0]， T[l]， T[2]はいずれも一時変数、 dは ηビットのスカラー値で、 d[i] は dの下位 iビット目の値である。
上述した Algorithm 3〜Algorithm 5を用いることにより SPAを防止するこ とができる力 文献 Coron99にはこれらのアルゴリズムに対する D P Aについて も述べられており、 Algorithm 3〜 Algorithm 5では D P Aで秘密鍵を解析して求 めることができることが示されている。 そして、 文献 Coron99には、 ランダム化 射影座標 （Randomized Projective Coordinates； R P C ) と呼ばれる、 乱数を使 用した楕円曲線上の点の表現を導入することによって、 Algorithm 3〜 Algorithm 5に対する DP Aへの各対策が提案されている。
以下に、 Algorithm3に対して RP Cを施したアルゴリズム例を Algorithm3 ' と して示す他、 Algorithm 4に対して R P Cを施したアルゴリ ズム例を Algorithm 4 ' と して、 又、 Algorithm 5に対して R P Cを施したものを Algorithm 51 としてそれぞれ示す。 なお、 以下、 R P Cで表現された楕円曲線 上の点をダッシュ aもしくは，） 付の変数で示す。
( 6 ) Algorithm 3 ' [バイナリ法 (MSB, アド 'アンド ·ダブル ·オール ウェイズ， RPC)]
Si: T'[2]：= RPC(P)
S2: T，[0]：= T，[2]
S3: for i = n-2 downto 0 {
S4: T'[0] :=ECDBL(T'[0])
S5: T'[l]：= ECADD( T'[0]， T'[2] )
S6: T'[0]：= T'[d[i]]
S7: }
S8: return( invEPC(T'[0]) )
ここで、 T，[0]， T'[l], T，[2]はいずれも一時変数、 dは nビッ トのスカラー値で、 d[i]は dの下位 iビット目の値である。又、 invRPCは RPC表現からの逆変換を 示す。
( 7 ) Algorithm 4 ' [パイナリ法 （L S B， アド ·アンド 'ダブル ·オール ウェイズ， RPC)] Si: T'[0] := 0
S2: T，[2] := RPC(P)
S3： for i = 0 upto n-1 {
S4: T'[l]：= ECADD( T'[0]， T，[2] )
S5: T'[2]：= ECDBL( T'[2] )
S6: T，[0]：= T，[欄
S7: }
S8: return( invRPC(T'[0]) )
ここで、 T，[0]， T，[l], T，[2]はいずれも一時変数、 dは nビットのスカラー値で、 d[i]は dの下位 iビット目の値である。又、 invRPCは R P C表現からの逆変換を 示す。
( 8 ) Algorithm 5 ' [モンゴメリ 'ラダー， R P C ]
Si: T'[0] := RPC(P)
S2: T，[l] := ECDBL(T'[0])
S3: for i二 n-2 downto 0 {
S4: T'[2]：= ECDBL( T'[d[i]] )
S5: T'[l] := ECADD( T'[0], T，[l] )
S6: T，[0] := T，[2-d[i]]
S7: T'[l]：= T'[l+d[i]]
S8: }
S9: return( invEPC(T'[0]) )
ここで、 T'[0], T，[l], T'[2]はいずれも一時変数、 dは nビットのスカラー値で、 d[i]は dの下位 iビット目の値である。又、 invRPCは R P C表現からの逆変換を 示す。
また、 D P Aに対する対策として、 R P Cと同様の効果を持つ方式として、 M.
Joye, and C. Tymen, "Protections against aifierential analysis for elliptic curve cryptography", Cryptographic Hardware and Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science vol. 2162, pp. 377-390, Springer- Verlag, 2001. (文献 Joye'TymenOlという） で提案された ランダム化 曲線 （Randomized Curve ； RC) 法がある。
■ RCは、 R P Cと同様に乱数を用いた点の表現を用いた点の表現を用いた点の 表現を用いることによる D P A対策法である。 R Cの適用方法は R P Cと同様で ある。 I I
Algorith 〇m 3に対して RCを施したアルゴリズム例を Algorithm 3 とし て示し、同様に、 A IIlgorithm 4に対して R Cを施したアルゴリズム例を Algorithm A" , Algorithm5に対して RCを施したアルゴリズム例を Algorithm5 " とし ョ
てそれぞれ示す。 なお、 以下、 RCで表現された楕円曲線上の点はダブルダッシ ュ （〃 もしくは"） 付の変数で示す。
( 9 ) Algorithm 3 " レ ィナリ法 （MS B, アド .アンド 'ダブル ·オール ウェイズ， RC)]
S1 T" [2]：= RC(P)
S2 T"[0]：= Τ"[2]
S3 for i = n-2 downto 0 ι
S4 T，，[0] := ECDBL( T"[0] )
S5 T"[l]：= ECADD( T"[0], T"[2] )
S6 T"[0]：= T"[d[i]]
S7 }
S8 return( invRC(T"[0]) )
ここで、 T"[0]， T"[l], T"[2] はいずれも一時変数、 dは nビッ トのスカラー値で 、 d[i] は dの下位 i ビット目の値である。 又、 invRCは R C表現からの逆変換を 示す。
( 1 0) Algorithm 4 " [バイナリ法 （ L S B， アド 'アンド 'ダブル ·ォー ルウェイズ， R C)
S1
S2 T"[2] := RC(P)
S3 for l = 0 up to n-1 {
S4 T"[l] := ECADD( T"[0], T"[2] )
S5 T"[2] :=ECDBL( T"[2] )
S6 S7: }
S8: return( invRC(T"[0]) )
ここで、 T"[0]， T"[l], T"[2]はいずれも一時変数、 dは nビットのスカラー値で、 • d[i] は dの下位 iビット目の値である。 又、 invRCは R C表現からの逆変換を示 す。
( 1 1 ) Algorithm 5 " [モンゴメリ ·ラダー， R C ]
Si: T"[0]：= RC(P)
S2: T"[l]：= ECDBL(T"[0])
S3： for i = n-2 downto 0 {
S4: T，，[2]：= ECDBL( T"[d[i]] )
S5: T"[l]：= ECADD( T"[0]， T，，[l] )
S6: T"[0] := T"[2-d[i]]
S7: T"[l]：= T"[l+d[i]]
S8: }
S9: return( invRC(T"[0]) )
ここで、 T"[0], T，，[l]， T"[2]はいずれも一時変数、 dは nビットのスカラー値で、 d[i] は dの下位 iビット目の値である。 又、 invHCは R C表現からの逆変換を示 す。
また、 スカラー倍算 d X Pの実現手法としては、 前述したバイナリ法 （ Algorithm 1 , 2 ) やモンゴメリ 'ラダー （Algorithm 5 ) の他に、 ウィンドウ法 (window method) と呼ばれる方法もある。 例えば、 幅 4ビッ トのウィンドウ法 は、 初期処理として Pの 0〜 1 5倍を計算し、 その結果をテーブルとして持って おき、 次にスカラー値を 4ビット単位（ウインドゥ）に分割することにより、 スカ ラー倍算を処理する。 以下に、 Algorithm 6としてウィンドウ法 （幅 4ビット） のアルゴリズム例を示す。
( 1 2 ) Algorithm 6 [ウィンドウ法 （幅 4ビット）]
S01: W[0] = 0
S02: W[l] = P
S03: for i = 2 upto 15 { S04 W[i] = ECADD(W[i-l], P)
S05 ： }
S06 ： T:: = W[d[n-l,n-4]]
S07 ： for i = n-5 downto 3 step -4 {
S08 T = ECDBL( T )
S09 T 二 ECDBL( T )
S10 T = ECDBL( T )
Sll T = ECDBL( T )
S12 T = ECADD( T, W[d[i,i-3]] )
S13 }
S14 return( T )
ここで、 dは nビットのスカラ一値で、 nは 4の倍数と仮定する。 又、 d[i,i-3] は dの下位 iビット目から （ i _3) ビットまでの 4ビット値とする。 W[i]はゥ ィンドウ法で使用するテーブルである。
例えば、 d=21=2A4+2A2+2A0=(10101)2=(00010101)2に対するスカラー倍算を 考える。 このとき dは 5ビットで 4の倍数ではないので、 便宜上、 その上位 3ビ ットに 0を挿入して 8ビットとみなす。 このとき n = 8である。 先ず、 初期値と してステップ S01で W[0]=Oが、 ステップ S02で W[1]=Pが設定される。 次に i=2,3,..., 15に対し、ステップ S03〜S05が実行される。各 iに対し、ステップ S04 で W[i] = ECADD(W[i-l]， P)が設定される。 このとき、 W[i]に設定されている値 は iXPとなっている。 ステップ S03〜S05の処理の終了後、 ステップ S06で変 数 Tに W[d[n-l,n-4]] = W[d[7,4]] = W[d[000l]] = 1XP が設定される。
次に、 i=3に対してステップ S07〜S13が処理される。 ステップ S08では T:= ECDBL( T ) が処理され、 変数 Τには 2 X Ρが登録される。 ステップ S09では T:=ECDBL(T)が処理され、変数 Τには 4 X Ρが登録される。 ステップ S10では T :=ECDBL(T)が処理され、 変数 Tには 8 X Pが登録される。 ステップ S11で は T:二 ECDBL(T)が処理され、変数 Tには 16 X Pが登録される。ステップ S12 では T = ECADD( T, W[d[i,i-3]] ) = ECADD( T, W[010l] ) = ECADD( 16XP, 5 XP) = 21XPが処理され、 変数 Tに 21 ΧΡが登録される。 以上でステップ S07〜S13の処理が終了する。最後にステップ S14において変 数 Tの値 2 1 X Pが出力される。 このようにウィンドウ法では、 あらかじめ作成 したテーブルを用いてスカラー倍算 d X Pを計算するのである。
さて、点のスカラー倍算に Algorithm 6 (ウィンドウ法）を使用する場合には、 dのビット値に応じて行なわれたり行なわれなかったりするような処理が無いの で、 バイナリ法と比較して一般に S P Aに対して安全であるといわれている。 し かし、 ウィンドウ法は、 バイナリ法と同様に、 D P Aに対しては安全ではなく、 文献 Coron99に開示された手法で解析可能であるが、 かかる D P Aに対しては、 バイナリ法やモンゴメリ ·ラダーと同様に、 R P Cや R Cが有効であることが知 られている。 以下に、 Algorithm 6に対して R P Cを施したアルゴリズム例を Algorithmら' に、又、 Algorithm 6に R Cを施したァルゴリズム例を Algorithm ら" に示す。
( 1 3 ) Algorithm 6 ' [ウィンドウ法 （幅 4ビット）， R P C]
S01 ： W'[0] = 0
S02 • W，[l] = RPC(P)
S03 ： for i = 2 up to 15 {
S04 ： W'[i] = ECADD( W，[i-1]， W'[l] )
S05 ： }
S06 ： T'：= W'[d[n-l,n-4]]
S07 for i = n-5 downto 0 step -4 {
S08 T， ：= ECDBL( T' )
S09 T， = ECDBL( T， )
S10 T' ：= ECDBL( T' )
S11 T， = ECDBL( T' )
S12 T' = ECADD( T', W'[d[i,i-3]] )
S13 }
S14 return( invRPC(T') )
ここで、 dは 11ビットのスカラー値で、 nは 4の倍数と仮定する。 また d[i,i-3] は dの下位 i ビット目から （i— 3 ) ビットまでの 4ビット値とする。 T' は一 時変数、 W'[i]はウィンドウ法で使用するテーブル、 invRPCは R P C表現からの 逆変換を示す。
( 1 4 ) Algorithm 6 " [ウィンドウ法 （幅 4ビット）， R C ] .
S01: II
〇
S02: W"[l] = RC(P)
S03: ior l = 2 upto 15 \
S04: W"[i] = ECADD( W"[i-1], W"[l] )
S05: }
S06: T" := W"[d[n-l,n-4]]
S07: for i二 n-5 downto 3 step -4 {
S08: T，，：= ECDBL( T，， )
S09: T" := ECDBL( T" )
S10: T"： = ECDBL( T" )
S11: T"：= ECDBL( T" )
S12: T"：= ECADD( T"， W"[d[i,i-3]] )
S13: }
S14: return( invRC(T") )
ここで、 dは nビットのスカラー値で、 nは 4の倍数と仮定する。 また d[i，i-3] は dの下位 iビット目から （ i— 3 ) ビットまでの 4ビット値とする。 T " は一 時変数、 W"[i] はウィンドウ法で使用するテーブル、 invRCは R C表現からの逆 変換を示す。
さて、 S P Aと D P Aとの双方に対しては、 従来、 前述した Algorithm s ' 〜 6 ' や Algorithm 3 " 〜 " を用いれば安全であるとされていた。しかしながら、 最近、 JU. Goubm, "A Renned Power-Analysis Attack on Elliptic Curve Cryptosystem", Public-Key Cryptography 2003 (PKC2003), Lecture Notes in Computer Science vol. 2567, Springer-Verlag, pp.199-210, 2003. (文献 Goubin03とレ、う） において、 これらを解析する手法が開示された。
楕円曲線上の点のうち、 X座標または y座標が 0であるような点を特殊点とレ、 う。スカラー倍算の途中に特殊点が出現した場合には、 S P Aや D P Aによって、 このような点が中間値として現れたことを容易に検出することができる。 文献
Goubin03 に開示された解析手法においては、 あるビット d[i]に対応する計算の 終了時に特殊点が現れるようなベースボイントを人工的に生成し、 実際に特殊点 が検出されるかどうかによって d[i]の値を推定するようになっている。 以下、 便 宜上、 この文献 Goubin03の解析手法を用いた攻擊を特殊点攻撃と呼ぶ。
この特殊点攻撃に対し、 バイナリ法やモンゴメリ 'ラダーは安全でない。 又、 R P Cや R Cを用いたとしても、 座標値が 0になるという性質は保持されてしま うので、 Algorithm 3 ' 〜 6 ' や Algorithm 3 〜ら" も特殊点攻撃に対して安 全であるとはいえない。
なお、 Algorithm 3〜 6についての D P Aに対する他の対策として、 C. Clavier, and M. Jo e, "Universal exponentiation algorithm "A nrst ster> towards provable SPA-resistance - -" , Cryptographic Hardware and Embedded Systems 2001 (CHES2001), Lecture Notes in Computer Science vol. 2162, Springer-Verlag, pp.300-308, 2001. (文献 Clavier -Joye 01 とレヽう） tこて提案され ているェクスポーネント .スプリ ツティング (exponent-splitting； E S ) がある 。この E Sはスカラー値をランダムに変化させる手法であって、乱数 rによって、 スカラー dを d = r + ( d— r ) に分割して、 2つのスカラー倍算 r X Pと （d - r ) X Pとを別々に計算し、
r X P + ( d - r ) X P = d X P
が成り立つという性質を利用して、 2つのスカラー倍算の結果を足しあわせるこ とで d X Pを計算するものである。
ここで、 2つのスカラー倍算 r X Pおよび （d— r ) X Pには、 他の S P A/ D P Aに耐性を有するアルゴリズムを用いる。 特殊点攻擊に対しては、 スカラー 値がランダムに変化するために防御が可能となる。 E Sのアルゴリズム例を Algorithm 7に示す。
( 1 5 ) Algorithm 7 [ェクスポーネント ' スプリ ツティング]
SI: r := randomO
S2: Tl：= scalar( r, P )
S3： T2： = scalar( d-r, P ) S4: T := ECADD( Tl， T2 )
S5: return( T )
ここで randomOは nビットの乱数を生成する関数である。 又、 scalar( d, P ) はスカラー倍算 d X Pを計算する関数であって、具体的には、前述した Algorithm 3 ' 〜6 ' や Algorithm 3 〜ら" 等を用いて計算される。また変数 r， T, Tl, T2 はいずれも一時変数である。
E Sは、 S P A, D P Aおよび特殊点攻撃に対して安全といえるが、 E Sで使 用するスカラー倍算はその手法単独で S P A対策， D P A対策であるので、既に S P A対策と D P A対策済の Algorithm 3 ' 〜ら' や Algorithm 3 " 〜ら" に適 用するには無駄が多い。 特に、 これらの手法を適用すると、 楕円曲線上の点の加 算および 2倍算を、 適用前と比較して余分に処理しなければならず、 処理オーバ 一へッドが大きくなる欠点がある。
本発明は、 このような課題に鑑み創案されたもので、 特定点攻撃に対して秘密 情報の推定を困難にし、 暗号処理の安全性を高めることが可能な楕円曲線暗号装 置， 楕円曲線暗号方法， 楕円曲線暗号プログラムおよび同プログラムを記録した コンピュータ読取可能な記録媒体を提供することを目的とする。
非特許文献 1 (文献 Coron99)
dean-Sebastem Uoron "Resistance against Differential Power Analysis for Elliptic Curve Crytosystems", Cryptographic Hardware and Embedded Systems 1999 (CHES1999), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.292-302, 1999
非特許文献 2 (文献 Izu-Takagi02)
T. Izu, and T. Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks", Public-Key Cryptography 2002 (PKC2002), Lecture Notes in Computer Science vol. 2274, pp.280-296, Springer-Verlag, 2002.
非特許文献 3 (文献 Joye-TymenOl)
M. Jo ye, and C. Tymen, "Protections against differential analysis for elliptic curve cryptography", urypto graphic Hardware and. Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science vol. 2162, pp. 377-390, Springer-Verlag, 2001.
非特許文献 4 (文献 Goubin03)
L. Goubin, "A Refined Power-Analysis Attack on Elliptic Curve Cryptosystem", Public -Key Cryptography 2003 (PKC2003), Lecture Notes in Computer Science vol. 2567, Springer-Verlag, pp.199-210, 2003.
非特許文献 5 (文献 Clavier- JoyeOl)
C. Clavier, and M. Joye, "Universal exponentiation algorithm --A first step towards provable SPA-resistance - -" , Cryptographic Hardware and Embedded Systems 2001 (CHES2001), Lecture Notes in Computer Science vol. 2162， Springer-Verlag, pp.300-308, 2001. 発明の開示
上記の目的を達成するために、 本発明の楕円曲線暗号装置は、 楕円曲線暗号処 理を行なう楕円曲線喑号装置であって、 有限体 G F ( p " m) 上における楕円曲 線上の点 Pの座標 (X： Y： Z ) を座標 （r 1 X ( X - s 1 ) ： r 2 X (Y— s 2 ) ： r 3 X ( Z - s 3 ) ) に変換する座標変換部 （ただし、 pは素数、 mは 1以上 の整数、 r l， r 2 , r 3はいずれも 1以上且つ （p _ 1 ) 以下の整数、 s i , s 2 , s 3はいずれも 0以上且つ （p _ l ) 以下の整数、 又、 符号-はべき乗を 表わす） と、 この座標変換部によって変換された楕円曲線上の点のスカラー倍算 を行なうスカラー倍算演算部とをそなえ、 パラメーター s 1 , s 2 , s 3のうち 少なくとも 1つが 0以外の値を有することを特徴としている。
なお、 スカラー倍算演算部が、 アド 'アンド 'ダブル ·オールウェイズを用い たバイナリメソッドで、 スカラー倍算を行なってもよく、 又、 モンゴメリ ·ラダ 一法でスカラー倍算を行なってもよく、 更に、 ウィンドウ 'メソッドでスカラー 倍算を行なってもよい。
また、 スカラー倍算演算部が、 X座標法でスカラー倍算を行なってもよく、 連 続楕円 2倍算を用いてスカラー倍算を行なってもよい。
さらに、 本発明の楕円曲線暗号方法は、 楕円曲線暗号処理を行なう楕円曲線暗 号方法であって、 有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X ： Y： Z) を座標 ( r 1 X (X- s 1) ： r 2 X (Y— s 2) ： r 3 X (Z— s 3 )) に変換する座標変換ステップ （ただし、 Pは素数、 mは 1以上の整数、 r 1， r 2, r 3はいずれも 1以上且つ （p— 1) 以下の整数、 s l， s 2, s 3はい ずれも 0以上且つ （p _ l) 以下の整数、 又、 符号"はべき乗を表わす） と、 こ の座標変換ステップにおいて変換された楕円曲線上の点のス力ラ一倍算を行なう スカラー倍算演算ステップとをそなえ、 パラメーター s 1， s 2, s 3のうち少 なくとも 1つが 0以外の値を有することを特徴としている。
なお、 スカラー倍算演算ステップにおいて、 アド 'アンド 'ダブル ·オールゥ エイズを用いたバイナリメソッドでスカラー倍箅を行なってもよく、 又、 スカラ 一倍算演算ステップにおいてモンゴメリ ·ラダー法でスカラー倍算を行なっても よく、 更に、 スカラー倍算演算ステップにおいて、 ウィンドウ 'メソッドでスカ ラ一倍算を行なつてもよい。
また、 スカラー倍算演算ステップにおいて、 X座標法でスカラー倍算を^なつ てもよく、 又、 スカラー倍算演算ステップにおいて、 連続楕円 2倍算を用いてス カラー倍算を行なってもよい。
さらに、 本発明の楕円曲線暗号プログラムは、 楕円曲線暗号処理を行なう楕円 曲線暗号プログラムであって、 有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X： Y： Z ) を座標 （r l X (X- s i) : r 2 X (Y- s 2) : r 3 X (Z- s 3)) に変換する座標変換部 （ただし、 pは素数、 mは 1以上の整数、 r 1 , r 2, r 3はいずれも 1以上且つ （p— 1) 以下の整数、 s l， s 2， s 3はいずれも 0以上且つ （p— 1) 以下の整数であり、 且つ、 これらの s 1， s 2, s 3のうち少なくとも 1つが 0以外の値を有する。 又、 符号 はべき乗を表 わす） と、 座標変換部によって変換された楕円曲線上の点のスカラー倍算を行な うスカラー倍算演算部としてコンピュータを機能させることを特徴としている。 なお、 スカラー倍算演算部としてコンピュータを機能させる際に、 アド 'アン ド ·ダブル ·オールウェイズを用いたバイナリメソッドでスカラー倍算を行なつ てもよく、 又、 スカラー倍算演算部としてコンピュータを機能させる際に、 モン ゴメリ 'ラダー法でスカラー倍算を行なってもよく、 更に、 スカラー倍算演算部 としてコンピュータを機能させる際に、 ウィンドウ 'メソッドでスカラー倍算を 行なってもよレ、。
また、 スカラー倍算演算部としてコンピュータを機能させる際に、 X座標法で スカラー倍算を行なってもよく、 又、 スカラー倍算演算部としてコンピュータを 機能させる際に、 連続楕円 2倍算を用いてスカラー倍算を行なってもよい。 そして、 本発明のコンピュータ読取可能な記録媒体は、 上述した楕円曲線暗号 プログラムを記録したものである。
このように、 本発明の楕円曲線暗号装置， 楕円曲線暗号方法， 楕円曲線暗号プ ログラムおよぴ同プログラムを記録したコンピュータ読取可能な記録媒体によれ ば、 以下の効果ないし利点がある。
(1) 有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X： Y： Z) を座標 (r 1 X (X- s 1)： r 2 X (Y— s 2) ： r 3 X (Z— s 3)) に 変換 （ただし、 Pは素数、 mは 1以上の整数、 r l, r 2, r 3はいずれも 1 以上且つ （p— 1) 以下のランダムな整数、 s i, s 2, s 3はいずれも 0以 上且つ （p— 1) 以下のランダムな整数であり、 且つ、 これらの s l， s 2, s 3のうち少なくとも 1つが 0以外の値を有する。 又、 符号'はべき乗を表わ す） し、 この変換された楕円曲線上の点のスカラー倍算を行なうので、 楕円曲 線暗号におけるスカラー倍算を、 サイドチャネル攻撃に対する耐性をもって計 算することが可能となる。 .
(2) 特に、 s l， s 2, s 3のうち少なくとも 1つが 0以外の値を有する ので、 特殊点の線型変換座標での座標が 0以外の値となり、 スカラー倍算の途 中で出現することがなく、 これにより特殊点攻擊に対して安全である。
(3) アド ·アンド 'ダブル ·オールウェイズを用いたバイナリメソッドで、 スカラー倍算を行なうことにより、 S P Aおよび DP Aに対して安全である。
(4) ヤコビアン座標における R PCと同様のランダム効果が期待でき、 D
P Aに対しても安全である。
(5) モンゴメリ 'ラダー法で前記スカラー倍算を行なうことにより、 SP Aおよび DP Aに対して安全である。
(6) X座標法で前記スカラー倍算を行なうことにより、 SPAおよび DP Aに対して安全であり、 さらに計算時間を短縮することができる。
( 7 ) ウィンドウ 'メソッドで前記スカラー倍算を行なうことにより、 S P Aおよび D P Aに対して安全である。
( 8 ) 連続楕円 2倍算を用いて前記スカラー倍算を行なうことにより、 高速 に演算を行なうことができる。 図面の簡単な説明
図 1は楕円加算を説明するための図である。
図 2は楕円 2倍算を説明するための図である。
図 3は本発明に係る楕円曲線喑号装置の要部の構成を示す図である。
図 4は本発明の一実施形態としての楕円曲線暗号装置の機能構成を示すプロッ ク図である。
図 5は本発明の楕円曲線暗号プログラムを実行する楕円曲線暗号装置のハード ウェア構成の一例を示す図である。 発明を実施するための最良の形態
以下、 図面を参照して本発明の実施の形態を説明する。
( a ) 基本説明
本発明の一実施形態としての楕円曲線暗号装置は、 例えば、 楕円曲線暗号の専 用の情報処理装置， パーソナルコンピュータ， I Cカード （スマートカード） 等 に内蔵された I Cチップ，携帯電話機，携帯情報端末装置（P D A (Personal data assistant) 等）， D V Dプレーヤ等として実現されるものであり、 演算を行なう プロセッサを有して構成されるものである。
以下の説明では、 本発明にかかる楕円曲線暗号演算方法を、 pを素数、 mを 1 以上の整数とし、 要素数 p の有限体 G F ( p " m) 上の楕円曲線に適用した 場合について説明する。 なお、 以下、 特に断りの無い限り、 小文字 （d等） はス カラー値を表わし、 大文字 （P， T等） は楕円曲線上の点を表わすものとする。 又、 楕円加算を E C AD D、 楕円 2倍算を E C D B Lと表わす。 更に、 符号 " はべき乗算を表わすものとし、 " （" と "） 2" とによって囲まれた数列は 2進 数で表現された数字を表わす。 又、 "S01： "等のように、 Sを付した数字はアル ゴリズムを表わすプ口グラム例におけるステツプ数を示すものとする。
GF (p " m) 上の楕円曲線 Eは、 以下の方程式を満たす点 （X , y) の集合 に、 無限遠点 （以下、 ゼロ点という場合もある） と呼ばれる点∞を加えた集合で ある。 なお、 無限遠点∞を 0と表すこともある。
E： y " 2+ a l X x X y + a 3 X y = x " 3 + a 2 X x " 2 + a 4 X x + a 6 ここで a l， a 2, a 3 , a 4, a 6 , x, yはそれぞれ GF ( p " m) の要素 である。 楕円曲線上の点は （X , y) のような座標形式で表現できるが、 無限遠 点∞は （x， y) のような座標形式で表現することができない唯一の点である。
Pを GF (p " m) 上の楕円曲線 E上の点とし、 以下のように Pの逆元一 Pを 疋 5
( 1 ) P =∞ならば、 一 p =∞
(2) P≠∞ならば、 P= (x, y) としたときに、
— P = (X , — y— a l X x— a 3
また、 P I , P 2を GF (p " m) 上の楕円曲線 E上の 2点とし、 以下に示す ように P 1と P 2との和 P 3 = P 1 +P 2を定義する。
( 1 ) P 1 =∞ならば、 P 3 = P 2
(2) P 2 =∞ならば、 P 3 = P 1
(3) P 1 = _ P 2ならば、 P 3 =∞
(4) P l≠— P 2ならば P l = (x 1 , y 1 ), P 2 = (x 2, y 2), P 3 =
(x 3, y 3) としたときに、
x 3 = λ " 2 + a l X A, - a 2 - x l -x 2,
y 3 =- (λ + a 1 ) X x 3 - v - a 3,
ただし、
P 1≠P 2のとき
λ = (y 2 - y 1 ) / (x 2 - 1 )
v = (y l X x 2 -y 2 X x l) / (x 2 - 1 )
P 1 =P 2のとき
λ = (3 X 1 " 2 + 2 X a 2 X x + a 4- a l X y l) / (2 X y 1 + a 1 X x 1 + a 3)
v = (- x 1 3 + a 4 Xx l + 2 X a 6- a 3 Xy l) / (2 X y 1 + a 1 X x 1 + a 3)
と定める。
P 1≠P 2のときに、 P 1 +P 2を計算することを楕円加算 （ECADD)、 P I
=P 2のときに P 1 +P 2 = 2 X P 1を計算することを楕円 2倍算 （ECDBL) という。 楕円加算 ·楕円 2倍算は、 有限体 GF (p - m) での加減算 ·乗算 ·平 方算 ·逆元計算の組み合わせによって計算される。
pを素数とするとき、 有限体 GF (p) を素体という。 特に、 pが 5以上の素 数の場合には、 素体 GF (p) 上の楕円曲線 Eは、 方程式
E : y " 2=x " 3+a X x+b
を満たす点（x， y) の集合上に、無限遠点と呼ばれる点∞を加えた集合である。 なお、 無限遠点∞を 0と表すこともある。 又、 a， b, x, yはそれぞれ GF ( P) の要素である。 楕円曲線上の点は （x， y) のような座標形式で表現できる 力 無限遠点∞は （X , y) のような座標形式で表現することができない唯一の 点である。
Pを GF (p) 上の楕円曲線 E上の点とし、 以下に示すように Pの逆元一 Pを 疋 。
(1) p=∞ならば、 _p=∞
(2) P≠∞ならば、 P= (x, y ) としたときに、 一 P= (x, - y) また、 P l， P 2を GF (p) 上の楕円曲線 E上の 2点とし、 以下に示すよう にして P 1と P 2との和 P 3 =P 1 +P 2を定義する。
( 1 ) P 1 =∞ならば、 P 3 = P 2
(2) P 2=∞ならば、 P 3 = P 1
(3) P 1 =— P 2ならば、 P 3 =∞
(4) P l≠— P 2ならば、 P l = (x 1 , y 1 ), P 2 = (x 2, y 2), P 3 = (x 3, y 3) としたときに、
x 3 = λ " 2— 1— x 2
y 3 = — λ X x 3— v ただし
P 1≠P 2のとき
λ = (y 2 - y 1 ) / (x 2 - x 1 )
v = (y l X x 2 -y 2 X x l) / (x 2 - x 1 )
P 1 =P 2のとき
X = ( 3 X x 1 " 2 + a ) / (2 X y 1 )
v = (- x l " 3 + a X x l + 2 X b) / (2 X y 1 )
と定める。
P 1≠P 2のときに、 P 1 +P 2を計算することを楕円加算 （ECADD)、 P 1 =P 2のときに P 1 +P 2 = 2 X P 1を計算することを楕円 2倍算 （ECDBL) という。 楕円加算 ·楕円 2倍算は、 有限体 GF (p) での加減算 ·乗算 .平方算
•逆元計算の組み合わせによって計算される。
図 1は楕円加算を説明するための図、 図 2は楕円 2倍算を説明するための図で ある。 楕円加算は、 図 1に示すように、 楕円曲線上の点 P l = (x 1 , y 1 ) と P 2 = (x 2, y 2) とを結ぶ直線と楕円曲線との交点を、 x軸で折り返した点
P 3 = P 1 +P 2 - (x 3, y 3) として定義される。 楕円 2倍算は、 図 2に示 されるように、 楕円曲線上の点 P l = (x 1 , y 1) の接線と楕円曲線との交点 を、 X軸で折り返した点 P 4 = P 1 +P 1 = 2 X P 1 = (x 4, y 4) として定 義される。
有限体上の楕円曲線 Eと、 ベースポイントと呼ばれる曲線上の点 Pと、 スカラ 一と呼ばれる整数 dとに対して、 点 d X P = P + P+…十 P (d個の和） を計算 することをスカラー倍算という。 スカラー倍算は、 楕円加算、 楕円 2倍算の組み 合わせによって実現される。
楕円加算、 楕円 2倍算、 スカラー倍算の計算時間は、 有限体における乗算、 平 方算、 逆元計算の計算時間の和によって見積もられることが多い。 これは実際の 楕円加算、 楕円 2倍算、 スカラー倍算の計算が、 有限体における加減算 ·乗算 - 平方算 ·逆元計算の組み合わせで計算され、 多くの場合、 加減算の計算時間はそ の他の計算時間に比べて無視できるほど短レ、からである。
一般に有限体 GF (p ~ m) での逆元計算の計算時間は、 乗算 ·平方算の計算 時間に比べて非常に大きくなる。 このため、 本発明の楕円曲線暗号装置において は、 楕円曲線の点を表現する上で線形座標を使用するようになっている。
本発明で使用する線型変換座標においては、 GF (p " m) 上の楕円曲線の点 は (X ： Y ： Z) のような 3つの要素の組み合わせで表される。 ただし、 GF ( p " m) の要素 r 1≠0、 r 2≠0、 r 3≠0、 s l、 s 2、 s 3に対して、
(X : Y : Ζ) と ( r 1 X (X— s 1) ： r 2 X (Y s 2) : r 3 X (Z— s 3 ) ) とが同じ点と考える。 .
そして、 本楕円曲線暗号装置 1 1においては、 線形変換座標は、 有限体上にお ける楕円曲線上の点 Pの座標 (X： Y： Z) を座標 (r 1 X (X- s i) : r 2 X (Y- s 2) : r 3 X (Z - s 3)) に変換するものであって、 r 1 , r 2, r 3 はそれぞれ 0以外の任意の整数であり、 s 1， s 2， s 3の少なくともいずれか 1つが 0以外の整数である。 なお、 以下、 これらの r l， r 2, r 3, s i, s 2, s 3を線型変換座標のパラメータという場合もある。
線型変換座標を用いると、 楕円曲線上の全ての点は （X： Y： Z) のような座 標形式で表現することができる。 又、 無限遠点は∞= (0 : 1 : 0) となる。 なお、 線型変換座標のパラメータを （r 1， r 2, r 3, s 1 , s 2, s 3) と表わす場合に、
( r 1 , r 2, r 3 , s 1 , s 2 , s 3) = ( r， r , r， 0， 0， 0) とした場合に、 射影座標として用いることができ、 又、
( r 1 , r 2, r 3, s i, s 2, s 3) = (r " 2, r 3， r , 0, 0, 0
)
とした場合に、 ヤコビアン座標として用いることができる。
以下、 本発明に係る楕円曲線暗号演算方法を、 pを 5以上の素数とし、 要素数 pの有限体 GF (p) (pは 5以上の素数）上の楕円曲線に適用した場合について 説明する。
GF (p) 上の楕円曲線 Eは、 以下の式で表わすことができる。
E : y " 2=x " 3+a Xx+b
ここで a, b， x, yは GF (p) の要素で、 4 X a " 3 + 27 X b " 2≠0を 満たす。 図 3は本発明に係る楕円曲線暗号装置 1 1の要部の構成を示す図である。 本楕 円曲線暗号装置 1 1は、 図 3に示すように、 演算部 （プロセッサ） 1 2と記憶 1 6とをそなえて構成されている。 記憶部 1 5は、 後述する楕円曲線暗号の楕円加 算， 楕円 2倍算， 楕円 2 " k倍算等の演算プログラムを記憶するものである。 演算部 1 2は、 演算器 1 3， レジスタ群 14および演算結果出力レジスタ群 1
5をそなえて構成されている。 演算器 1 3は、 記憶部 1 6に格納された楕円曲線 暗号プログラムをレジスタ群 14を用いて実行するものであって、 その演算結果 を演算結果出力レジスタ群 1 5に出力するようになっている。
レジスタ群 14および演算結果出力レジスタ群 1 5は、 いずれも複数のレジス タからなり、 これらのレジスタに、 演算を行なうための数値や、 演算実行後の結 果， 現在実行しているコードのメモリアドレス、 CPUの状態などを格納するも のであり、 演算結果出力レジスタ群 1 5には、 特に演算器 1 3による演算結果が 格納されるようになっている。
図 4は本発明の一実施形態としての楕円曲線暗号装置 1 1の機能構成を示すブ ロック図である。 本楕円曲線暗号装置 1 1は、 図 4に示すように、 ゼロ点判定部 2 1, スカラー倍算処理部 22, 線形座標変換部 （座標変換部） 23および乱数 生成部 24をそなえて構成されている。
乱数生成部 24は、 乱数 r 1， r 2, r 3を生成するものであり、 生成した乱 数 r 1， r 2, r 3をスカラ倍算処理部 22および線形座標変換部 23に渡すよ うになつている。
ゼロ点判定部 21は、 スカラー倍算の結果がゼロ点 （無限遠点） であるか否か を判定するものである。
線形座標変換部 23は、 有限体 GF (p) 上における楕円曲線上の点 Pの座標 (X： Y： Z) を座標 ( r 1 X (X- s 1) ： r 2 X (Y— s 2) ： r 3 X (Z— s 3)) に変換 （線形座標変換） するものであり、 変換後の座標 （以下、 線形変換 座標という場合もある） をスカラー倍算処理部 22に渡すようになつている。 ス カラー倍算処理部 22は、 線形座標変換部 23によって変換された楕円曲線上の 点のスカラー倍算 d XPを演算するものであり、 後述する種々のアルゴリズムを 用いて楕円加算，楕円 2倍算，楕円 2 - k倍算等の演算処理を行なうことにより、 スカラー倍算を行なうようになっている。
なお、 本楕円曲線暗号装置 1 1においては、 例えば、 演算部 1 2が、 記憶部 1 6に記憶されたプログラムを実行することにより、 ゼロ点判定部 2 1 , スカラー 倍算処理部 2 2 , 線形座標変換部 2 3および乱数生成部 2 4として機能するよう になっている。
そして、 スカラー倍算処理部 2 2力 スカラー倍算 d X Pを計算する際に、 こ の変換後の線型変換座標における楕円加算と楕円 2倍算を計算するようになって いる。 すなわち、 スカラー倍算処理部 2 2は、 素体 G F ( p ) 上の楕円曲線 Eに 対して、 パラメーター （r 1， r 2 , r 3， s 1， s 2 , s 3 ) = ( r " 2 , r " 3， r , s , 0 , 0 ) の線型変換座標における楕円加算 (以下、 LCECADD と いう）と楕円 2倍算 （以下、 LCECDBL という） を計算するようになっているの である。
このときの楕円加算の計算アルゴリズムを Algorithm sに示すとともに、 楕円 2倍算の計算アルゴリズムを Algorithm 9に示す。
( a - 1 ) Algorithm 8 [LCECADD (パラメーター （rA2，rA3，r，s,0,0) ) ]
Input: Pl=(Xi:Yi:Zl), P2=(X2:Y2:Z2), s
Output: Ρ3=(Χ3:Υ3:Ζ3)=(Χ1:Υ1:Ζ1)+(Χ2,Υ2,Ζ2)
S01: if ( Zl ~0 ) then return( P2 )
S02: if ( Z2==0 ) then ret画（ PI )
S03: Tl = Z1A2 /* Ζ1Λ2 */
Figure imgf000028_0001
S05: T3 = Ζ2Λ2 /* Ζ2Λ2 */
S06: T4 = Z2*T3 /* Z2A3 */
S07: T5 = X1*T3 /* X1*Z2A2 */
S08: T6 二 s*T3 /* s*Z2A2 */
S09: T7 = X2*T1 /* X2*Z1A2 */
S10: T8 = s*Tl /* s*ZlA2 */
Sli: T9 = Y1*T4 /* S1=Y1*Z2八 3
S12: T10 = Y2*T2 /* S2=Y2*Z1A3 S13: Til = Τ7-Τ5 /* Χ2*Ζ1Λ2-Χ1*Ζ2Λ2 *
S14: T12 = T11-T8 /* U2-X1*Z2A2 */
S15: T13 = T12+T6 /* U2-U1=W */
S16: T14 = Τ7+Τ5 /* Χ2*Ζ1Λ2+Χ1*Ζ2Λ2 *
S17: T15 = T14-T8 /* U2+X1*Z2A2 */
S18: T16 = T15-T6 /* U2+U1=T */
S19: T17 = T10-T9 /* S2-S1=R */
S20: T18 = T10+T9 /* S2+S1=M */
S2i: T19 = Τ17Α2 /* RA2 */
S22: T20 = Τ13Α2 /* WA2 */
S23: T21： = Τ16*Τ20 /* T*WA2 */
S24: T22 = T19+S /* ； R八 2+s */
S25: X3 二 T22-T21 /* EA2-T*WA2+s */
S26: T23二 2*Χ3 /* 2*RA2-2*T*WA2+2*s
S27: T24 = T23-T21 /* 2*RA2-3*T*WA2+2*s
S28: T25 = 2*s /* 2*s */
S29: Τ26 = Τ25-Τ24 /*
S30: Τ27 = Τ25*Τ17 /* V*R */
S3i: Τ28 = Τ18*Τ13 /* M*W */
S32: Τ29 = Τ28*Τ20 /* M*WA 3 */
S33: Υ3 = (Τ27-Τ29)/2 /* (V*R-M*WA3)/2 */
S34: Τ30 = Ζ1*Ζ2 /* Z1*Z2 */
S35: Ζ3 = Τ30*Τ13 /* Z1*Z2*W */
S36: ret画 ( (Χ3:Υ3:Ζ3) )
( a— 2 ) Algorithm 9の計算例 [LCECDBL (パラメーター （r八 3,rA 3，r,s,0,0
) ) ]
Input: P1=(X1:Y1:Z1), s， a
Output: P4=(X4: Y4:Z4)=2 (XI :Y1 :Z l)
SOI: if ( Z1==0 ) then returnC PI ) S02: Tl = Z1A2 /* Zl八 2 */
S03: T2 = Τ1Λ2 /* Ζ1Λ4 */
S04: T3 = a*T2 . /* a*ZlA4 */
S05: T4 = Χ1Λ2 /* X1A2 */
S06: T5 = 2*X1 /* 2*X1 */
S07: T6 = s-T5 /* s-2*Xl */
S08: T7 = s*T6 /* s*(s-2*Xl) */
S09: T8 = 3*T4 /* 3*X1A2 */
S10: T9 = 3*T7 /* 3*s*(s-2*Xl) */
Sli: T10 = T3+T8 /* a*Zl八 4+3*Χ1Λ2 */
S12: Til = T10+T9 /* W+3*(Xl-s)A2=M *
SI 3： T12 = Y1A2 /* Y1A2 */
S14: T13 = X1*T12 /* X1*Y1A2 */
S15: T14 = s*T12 /* s*YlA2 */
S16: T15 = T12A2 /* Y1A4 */
S17: T16 = 8*T15 /* 8*s*M */
S18: T17 = T11A2 /* MA2 */
S19: T18 = 8*T13 /* 8*X1*Y1A2 */
S20: T19 = 8*T14 /* 8*s*YlA2 */
S2i: T20 = T17 + s /* MA2+s */
S22: T21 = T20-T18 /* MA2-8*Xl*YlA2+s
S23: X4 = T20+T19 /* MA2-2*S+s */
S24: T22 = 4*T13 /* 4*X1*Y1A2 */
S25: T23 = 4* 14 /* s*YlA2 */
S26: T24 = T22+s /* 4*Xl*YlA2+s */
S27: T25 = T24-X4 /* 4*Xl*YlA2+s-X4 */
S28: T26 = T25-T23 /* S-X4+S */
S29: T27 = T11*T26 /* M*(S-X4+s) */
S30: Y4 = T27-T16 /* M*(S-X4+s)-T */ S31: T28 = Y1*Z1 /* Y1*Z1 */
S32: Ζ4 = 2*Τ28 /* 2*Υ1*Ζ1 *Ι
S33: return( (Χ4:Υ4:Ζ4) )
(b) 第 1実施形態の説明
本発明の第 1の実施形態としての楕円曲線暗号装置 1 1は、 スカラー倍算処理 部 2 2が、 スカラー倍算 d XPを計算する際に、 バイナリ法 （L S B, アド .ァ ンド ·ダブル .オールウェイズ） を用いるようになつている。 以下に、 スカラー 倍算処理部 2 2がスカラ一倍算に用いるアルゴリズム例を Algorithm 1 0として 示す。
なお、 本第 1実施形態の楕円曲線喑号装置 1 1においては、 線形座標変換部 2
3は、 ノ ラメーター （r l， r 2 , r 3, s i , s 2, s 3) = (r " 2, r "
3， r， s， 0， 0) に基づいて、 素体 GF (p) 上の楕円曲線 Eに対して、 楕 円曲線上の点 Pの座標 （X： Y： Z) を座標 （r l X (X- s i) : r 2 X (Y_ s 2) : r 3 X (Ζ- s 3)) に変換するようになっている。 すなわち、 線形座標 変換部 2 3は、 楕円曲線上の点 Pの座標 （X： Y： Z) を座標 （r ~ 2 X (X— s) ： r " 3 XY： r XZ) に変換 （線形座標変換） するようになつている
( b— 1 ) Algorithm 1 0 [バイナリ法 （ L S B , アド 'アンド 'ダブル ·ォ 一ノレウェイズ， パラメーター (rA2,rA3,r,s,0,0))]
Si: T[0]：= LC(O)
S2: T[2] := LC(P)
S3： for i = 0 upto n-1 {
S4: T[l] := LCECADD( T[0], T[2] )
S5: T[2] := LCECDBL( T[2] )
S6: T[0]：= T [删
S7: }
S8: return( invLC(T[0]) )
ここで、 LCは線型写像座標への変換 （線形座標変換)、 invLCはその逆変換を 表す。 また T[0]， T[l]， Τ[2]はいずれも一時変数であり、 dは ηビットのスカラ 一値で、 d[i]は dの下位 iビット目の値である。 すなわち、 本第 1実施形態の楕円曲線暗号装置 11においては、 演算部 12が 上述した Algorithm 10のステップ SIおよび S2を実行することにより線形座標 変換部 23として機能し、 ステップ S3〜ステップ S7を実行することにより、 ス カラー処理部 22として機能するようになっているのである。
本発明の第 1実施形態としての楕円曲線暗号装置 1 1によれば、 線形座標変換 部 23が、 パラメーター （r l， r 2, r 3, s l， s 2, s 3) = (r ~ 2， r " 3, r , s , 0, 0) に基づいて、 素体 G F (p) 上の楕円曲線 Eに対して、 楕円曲線上の点 Pの座標 （X： Y： Z) を座標 （r 1 X (X- s 1) ： r 2 X (Y - s 2) ： r 3 X (Z- s 3)) に変換し、 スカラー倍算処理部 22が、 この変換 後の線型変換座標における楕円加算と楕円 2倍算を計算するので、 s≠0とする ことにより、 X座標が 0であるような特殊点は、 線型変換座標での X座標が sの 点として表され、 スカラー倍算の途中で出現することがない。 これにより特殊点 攻撃に対して安全である。
また、 スカラー倍算処理部 22が用いる Algorithm 10において、 アド .ァ ンド ·ダブル'オールウェイズを用いているので、 S PAおよび DP Aに対し て安全である。
さらに、 線形座標変換部 23が、 パラメーター （r 1， r 2, r 3, s i, s 2, s 3) = (r " 2, r " 3, r, s， 0, 0) に基づいて、 素体 GF ( p) 上の楕円曲線 Eに対して、 楕円曲線上の点 Pの座標 (X： Y： Z) を座標 ( r 1 X (X - s 1 ) ： r 2 X (Y— s 2) ： r 3 X (Z— s 3)) に変換し、 ス カラー倍算処理部 22が、 この変換後の線型変換座標における楕円加算と楕円 2倍算を計算するので、 ヤコビアン座標における R P Cと同様のランダム効果 が期待でき、 DP Aに対しても安全である。
(c) 第 2実施形態の説明
前述した第 1実施形態の楕円曲線喑号装置 1 1で用いられる Algorithm 10に おいては、 変数 T[2]に保管される値は dとは無関係であり、 そのステップ S5以 外では値が変更されることはない。 そこでバイナリ法 （LSB， アド ·アンド - ダブル ·オールウェイズ) の変形として、 以下の Algorithm 1 1に示すアルゴリ ズム例によって表わされる変形ァド .アンド .ダブル .オールゥヱイズを適用す ることもできる。
本発明の第 2実施形態としての楕円曲線暗号装置 1 1においては、 スカラー倍 算 d X Pを計算する際に、 アド .アンド 'ダブル ·オールウェイズに代えて Algorithm 1 1に示すような変形ァド .アンド 'ダブル ·オールウェイズを用い るようになっており、 それ以外の部分については前述した第 1実施形態の楕円曲 線暗号装置 1 1とほぼ同様に構成されている。 以下に、 スカラー倍算処理部 2 2 がスカラー倍算に用いるアルゴリズム例を Algorithm 1 1として示す。
( c _ 1 ) Algorithm 1 1 レ ィナリ法 （ L S B， 変形ァド ·アンド 'ダブル 'オールウェイズ， パラメーター （rA2，rA3，r,s，0,0) ) ]
SOI: T[0]：= LC(O)
S02: T[2]：= LC(P)
S03: T[l]： = Τ[2]
S04: Χ0 = Χ(Τ[2]); Υ0 = Υ(Τ[2]) ； Ζ0 = Ζ(Τ[2])
S05: Τ[2] := LCECDB (ΧΟ:Υ0:Ζ0) )
S06: Τ[0] = T[d[0]];
S07: for( i=i; i<=n-l; i++ ){
S08: T[l]：= LCECADDC T[0]， T[2] )
S09: T[2]：ニ LCiECDBL( T[2]，（X0:Y0:Z0) )
S10: T[0] = T[d[i]];
Sll: }
S12: return( invLC(T[0]) )
ここで、 L Cは線型写像座標への変換、 invLCはその逆変換を表す。又、 T[0], T[l]， Τ[2]はいずれも一時変数、 dは ηビットのスカラー値で、 d[i]は dの下位 i ビット目の値である。なお、ステップ S06とステップ S10とで使用される一時変 数は共用されるものとする。
本第 2実施形態の楕円曲線暗号装置 1 1においては、 演算部 1 2が上述した Algorithm 1 1のステップ S01および S02を実行することにより線形座標変換部 2 3として機能し、 ステップ S03〜ステップ S12を実行することにより、 スカラ 一処理部 2 2として機能するようになっているのである。 本発明の第 2実施形態の楕円曲線暗号装置 1 1によれば、 スカラー倍算処理部 22が用いる Algorithm 1 1において、 変形ァド ·アンド .ダブル ·オールゥェ ィズを用いているので、 S P Aに対して安全である。
また、 線形座標変換部 23が、 パラメーター （r 1, r 2, r 3, s l， s 2, s 3) = (r " 2, r " 3, r , s , 0, 0) に基づいて、 素体 GF (p
) 上の楕円曲線 Eに対して、 楕円曲線上の点 Pの座標 （X： Y： Z) を座標 ( r 1 X (X- s 1 ) ： r 2 X (Y- s 2) ： r 3'X (Z— s 3)) に変換し、 スカ ラー倍算処理部 22が、 この変換後の線型変換座標における楕円加算と楕円 2 倍算を計算するので、 ヤコビアン座標における RPCと同様のランダム効果が 期待でき、 DP Aに対しても安全である。
さらに、 上記パラメータにおいて s ≠ 0であるので、 X座標が 0であるよう な特殊点は、 線型変換座標での X座標が sとなり、 スカラー倍算の途中で出現 しない。 これにより特殊点攻撃に対しても安全である。
(d) 第 3実施形態の説明
本発明の第 3実施形態としての楕円曲線暗号装置 1 1は、 線形座標変換部 23 力 パラメーター （r 1, r 2, r 3， s 1， s 2, s 3) = ( r , r, r, s , 0， 0) に基づいて、 素体 GF (p) 上の楕円曲線 Eに対して、 楕円曲線上の点 Pの座標 （X： Y： Z) を座標 （r l X (X- s i) : r 2 X (Y- s 2) : r 3 X (Z— s 3)) に変換する線形座標変換を行なうようになっており、 更に、 スカ ラー倍算処理部 22が、 X座標法を用いて楕円加算と楕円 2倍算と楕円加算 2倍 算とを計算するようになっている。
本第 3実施形態においては、 スカラー倍算処理部 22が X座標法で前記スカラ 一倍算を行なうので、 S PAおよび DPAに対して安全である他、 計算時間を短 縮することができる。
また、 本実施形態においては、 上述の如くパラメーター （r l， r 2, r 3, s l， s 2, s 3) = (r， r, r , s， 0, 0) を用いるようになつており、 これにより、 計算時間を短縮することができる。
ここで、 X座標法とは、 楕円加算 ·楕円 2倍算 '楕円加算 2倍算を y座標を用 いずに計算するアルゴリズムである。 参考までに、 素体上の射影座標で表された 楕円曲線に対する、 文献 Izu-Takagi02 に開示された x座標法のアルゴリズム例 を、 以下に Algorithm 1 2 m， 1 2 a, 1 3， 14 m, 14 aとしてそれぞれ示 す。 なお、 アルゴリズムの番号の末尾に付した符号 mは乗法的 （multiplicative ) な EC ADDを用いることを示すものであり、 符号 aは加算的 （additive) な E CADDを用いることを示す。
( d— 1 ) Algorithm 1 2m [xECADDm (射影座標） ]
Input: P1=(X1:Z1), P2=(X2:Z2)， P3'=(X3':Z3')=P1-P2, a, b
Output: P3=(X3:Z3)=P1+P2
X3 = Z3' X [(XI X X2- a X Z 1 X Z2)A2- 4 X b X Zl X Z2 X (XI X Z2+2 X Zl) Z3 = X3' X(X1XZ2-X2XZ1)A2
(d— 2) Algorithm 1 2 a [xECADDa (射影座標）]
Input: P1=(X1:Z1)， P2=(X2:Z2), P3'=(X3':Z3')=P1-P2, a， b
Output: P3=(X3:Z3)=P1+P2
S = 2X(XlXZ2 + X2XZl)x(XlXX2 + aXZlXZ2) + 4XbXZlA2XZ2A2
T = (X1XZ2-X2XZ1)A2
X3 = Z3' XS+X3' XT
Z3 = Z3'xT
(d- 3) Algorithm 1 3 [xECDBL (射影座標） ]
Input: Pl=(Xi:Zl), a, b
Output: P4=(X4:Z4)=2xPl
X4 = (XlA2-aXZlA2)A2-8XbXXlXZlA3
Z4 = 4X(XlXZlX(XlA2+aXZlA2) + bXZlA4)
(d-4) Algorithm 14m [xECADDDBLm (射影座標） ]
Input: P1=(X1:Z1), P2=(X2:Z2)， P3'=(X3':Z3')=P1-P2, a, b
Output: P3=(X3:Z3)=P1+P2, P4=(X4:Z4)=2xPl
X3 = Z3' X[(XlXX2-aXZlXZ2)A2-4XbXZlXZ2X(XlXZ2+2XZl)
Z3 = X3' X(X1XZ2-X2XZ1)A2
X4 = (XlA2-aXZlA2)A2-8XbXXlXZlA3
Z4 = 4X(XlXZlX(XlA2+aXZlA2) + bXZlA4) (d- 5) Algorithm 1 4 a [xECADDDBLa (射影座標）]
Input: Pl=(Xl:Zl), P2=(X2:Z2)， P3'=(X3':Z3')=P1"P2, a, b
Output: Ρ3=(Χ3··Ζ3)=Ρ1+Ρ2, P4=(X4:Z4)=2xPl
S = 2X(XlXZ2+X2XZl)x(XlXX2 + aXZlXZ2) + 4XbXZlA2XZ2A2.
T = (X1XZ2-X2XZ1)A2
X3二 Z3， XS+X3' XT
Z3 = Z3'xT
X4 = (XlA2-aXZlA)A2-8XbXXlXZlA3
Z4 = 4X(XlXZlx(XlA2+aXZlA2) + bXZlA4)
本発明の第 3実施形態の楕円曲線暗号装置 1 1によれば、 線形座標変換部 2
3力 ノ ラメーター （r l， r 2, r 3, s i, s 2, s 3) = (r， r, r, s， 0， 0) に基づいて、 素体 GF (p) 上の楕円曲線 Eに対して、 楕円曲線 上の点 Pの座標 （X ： Y ： Z) を座標 （r l X (X_ s l) : r 2 X (Y— s
2) ： r 3 X (Z— s 3)) に変換し、 スカラー倍算処理部 22が、 この変換後 の線型変換座標における楕円加算と楕円 2倍算を計算するので、 ヤコビアン座 標における RPCと同様のランダム効果が期待でき、 DP Aに対しても安全で ある。
また、 上記パラメータにおいて s ≠ 0であるので、 X座標が 0であるような特 殊点は、線型変換座標での X座標が sとなり、スカラー倍算の途中で出現しない。 これにより特殊点攻撃に対しても安全である。
さらに、 上述した Algorithm 1 4m, 1 4 aによれば、 xECADDDBLni や xECADDDBLaを用いることにより、 1つの関数で加算と 2倍算とを行なうよう になっている。 これにより、 関数の呼び出し回数を低減することができ、 処理を 高速化することができる。 又、 加算と 2倍算とで演算結果を共有することができ るので、 計算量も低減することもできる。
(e) 第 4実施形態の説明
本発明の第 4実施形態としての楕円曲線暗号装置 1 1は、 第 3実施形態の楕円 曲線喑号装置 1 1におけるスカラー倍算処理部 22が、 スカラー倍算 d XPを計 算する際にモンゴメリ 'ラダーを用いるようになつており、 その他の部分につい ては第 3実施形態の楕円曲線暗号装置 1 1とほぼ同様に構成されている。以下に、 スカラー倍算処理部 2 2がスカラー倍算に用いるアルゴリズム例を Algorithm 1 5として示す。
( e - 1 ) Algorithm 1 5 [モンゴメリ 'ラダー， x座標法， パラメーター （ r,r,r,s,0,0) ]
Si: T[0]■= xLC(P)
S2: T[l]： = xECDBL( T[0] )
S3: for i = n-2 downto 0 {
S4: T[2]：= xECDBL( T随]] )
S5: T[l]： = xECADD( T[0]， T[l], LC(P) )
S6: T[0] := T[2-d[i]]
S7: T[l]：= T[l+d[i]]
S8: }
S9: return ( invxLC(T[0]) )
ここで、 xLC は線型写像座標における X座標法で用いる座標への変換であり、 invLCはその逆変換を表す。 又、 T[0], T[l]および Τ[2]はいずれも一時変数、 d は nビットのスカラー値で、 d[i]は dの下位 iビット目の値である。
本発明の第 4実施形態としての楕円曲線暗号装置 1 1によれば、 上述した第 4 実施形態と同様の作用効果を得ることができる他、 スカラー倍算処理部 2 2が用 いる Algorithm 1 5において、 モンゴメリ 'ラダーを用いているので、 S P Aお よび D P Aに対して安全である。
( f ) 第 5実施形態の説明
本発明の第 5実施形態としての楕円曲線暗号装置 1 1は、 スカラー倍算処理部 2 2が、 スカラー倍算 d X Pを計算する際に改良モンゴメリ 'ラダーを用いるよ うになつており、 それ以外の部分は第 4実施形態の楕円曲線暗号装置 1 1とほぼ 同様に構成されている。
改良モンゴメ リ ·ラダーは、 上述した Algorithm 1 4 m, 1 4 aと同様に、 xECADDDBL を用いることにより、 1つの関数で加算と 2倍算を行なうことに より、関数の呼び出し回数を低減して処理を高速化することができるものであり、 又、 加算と 2倍算とで演算結果を共有することにより計算量を低減することもで きるものである。 以下に、 スカラー倍算処理部 2 2がスカラー倍算に用いるアル ゴリズム例を Algorithm 1 5 ' として示す。
( f - 1 ) Algorithm 1 5 ' [改良モンゴメリ ' ラダー， x座標法， パラメ一 ター ， r，r，r，s,0,0) ]
SI: T[0]：= xLC(P)
S2: T[l]：= xECDBL( T[0] )
S3： for i = n-2 downto 0 {
S4: ( T[l-d[i]], T[d[i]] )：= xECADDDBL( T[d[i]], T[l_d[i]]， xLC(P) ) S5: }
S6: return ( invxLC(T[0]) )
ここで、 xLC は線型写像座標における X座標法で用いる座標への変換であり、 invLCはその逆変換を表す。 又、 T[0]， T[l]および Τ[2]はいずれも一時変数、 d は nビットのスカラー値で、 d[i]は dの下位 i ビット目の値である。
本発明の第 5実施形態としての楕円曲線暗号装置 1 1によれば、 上述した第 4 実施形態と同様の作用効果を得ることができる他、 スカラー倍算処理部 2 2が用 いる Algorithm 1 5 ' において、 xECADDDBL を用いるので、 1つの関数で加 算と 2倍算を行なうことにより、 関数の呼び出し回数を低減して処理を高速化す ることができる他、 加算と 2倍算とで演算結果を共有することにより計算量を低 減することができる。
上述の如く、 本発明の各実施形態にかかる楕円曲線喑号装置 1 1によれば、 楕 円曲線暗号におけるスカラー倍算を、 サイドチャネル攻擊に対する耐性をもって 計算することが可能となる。
( g ) 第 6実施形態
本発明の第 6実施形態としての楕円曲線暗号装置 1 1は、 スカラー倍算処理部
2 2が、 スカラー倍算 d X Pを計算する際に、楕円 2 k ( 2 ~ k )倍算 （iECDBL) を用いるようになつている。 ここで、 楕円 2 k倍算とは、 与えられた点の 2 k倍 点 2 k X Pを計算することである。 楕円 2 k倍算は、 楕円 2倍算を k回連続して用 いることで計算可能であるが、 1つの関数として処理した場合には、 中間値の削 減によって連続に適用するよりも効率的な計算が可能なことがある。
例えば、 K. Itoh, M. Takenaka, N. Torii, S. Temma, and Y. Kurihara,„Fast Implementation of Public-key Cryptography on DSP TMS320C6201", Cryptographic Hardware and Embedded Systems 1999 (CHES1999), Lecture Notes in Computer Science vol. 1717, pp.61-72, Springer-Verlag, 1999. (文献 Itoh+99という） には、 以下の Algorithm 1 6に示すような、楕円 2 k倍算を実現 するためのアルゴリズムが開示されている。 なお、 この楕円 2 k倍算は、 素体上 でヤコビアン座標で表現された楕円曲線に対して適用可能である。
( g — 1 ) Algorithm 1 6 [iECDBL (ヤコビアン座標） ]
Input: Ρ[0]=(Χ[0]:Υ[0]:Ζ[0]), k， a
Output: P[k]=(X[k]:Y[k]:Z[k])=2AkxP[0]
SOI: W[0]：= axZOM
S02: M[0]：= 3 XX[0]A2 + W[0]
S03: S[0] := 4xX[0]xY[0]A2
S04: T[0] = 8xY[0]A4
S05: X[l]：= M[0]A2-2 X S[0]
S06: Y[l]：= M[0] X (S[0] -X[1])-T[0]
S07: Z[l] := 2xY[0]xZ[0]
S08: for 0=1； i<k; i++){
S09: W[i]：= 2xT[i-l]xW[i-l]
S10: M[i]：= 3 XX[iJA2+W[i]
Sll: S[iJ：= 4xX[i]xY[i]八 2
S12: T[i] 8xY[i]A4
S13: X[i+1] := M[i]A2-2 X S[i]
S14: Y[i+1] := M[i] X (S[i]-X[i+1])-T[i]
S15: Z[i+1]：= 2xY[i]xZ[i]
S16: }
S17: return( (X[k]:Y[k]:Z[k]) )
上述した Algorithm 1 6は、 ヤコビアン座標に対して楕円 2 k倍算を適用した ものであるが、 このヤコビアン座標に代えて本発明の線形座標変換部 23により 行なわれた線形変換座標に対して楕円 2 k倍算を適用することもでき、 これによ り、 演算速度を向上させることができる。
なお、線形座標変換部 23は、パラメーター （r l， r 2, r 3, s 1, s 2， s 3) = (r " 2, r " 3, r , s， 0, 0) に基づいて線形座標変換を行なつ てもよく、 又、 パラメーター （r 1, r 2, r 3 , s 1 , s 2, s 3) = (r , r, r， s , 0， 0) に基づいて線形座標変換を行なってもよい。
(h) その他
次に、 上述した本発明の楕円曲線暗号プログラムを実行する楕円曲線喑号装置 のハードウエア構成の一例を図 5を参照して説明する。楕円暗号装置は、例えば、 パーソナルコンピュータ等の情報処理装置により実現できる。
CPU (Central Processing Unit) 3 1は、 楕円曲線暗号の楕円加算、 楕円 2 倍算等を実行する。 メモリ 32は、 演算に使用される各種のレジスタとして使用 される。外部記憶装置 33は、 O Sや、楕円曲線暗号プログラム等が格納される。 媒体駆動装置 34は、 CDROM、 DVD, フレキシブルディスク、 I Cカー ド等の可搬記録媒体 35の読み取り、 あるいは書き込みを行なう装置である。 入力装置 3 6は、 キーボード等のデータを入力する装置である。 出力装置 37 は、 ディスプレイ、 プリンタ等の装置である。 ネットワーク接続装置 38は、 ィ ンターネット等のネットワークに接続するための装置であり、 この装置を介して ネットワーク上のサーバからプログラムをダウンロードすることができる。なお、 CPU31, メモリ 32， 外部記憶装置 33, 入力装置 36等はバス 39により 接続されている。
そして、 情報処理装置の CPU 3 1が、 楕円曲線暗号プログラムを実行するこ とにより、 上述したゼロ点判定部 21, スカラー倍算処理部 22， 線形座標変換 部 （座標変換部） 23および乱数生成部 24として機能するようになっている。 なお、 これらのゼロ点判定部 21， スカラ一倍算処理部 22 , 線形座標変換部 (座標変換部） 23および乱数生成部 24としての機能を実現するためのプログ ラム （楕円曲線暗号プログラム） は、 例えばフレキシブルディスク， CD— RO M, CD-R, CD-R/W, D VD, DVD-R, D VD-R/W, 磁気ディ スク， 光ディスク， 光磁気ディスク等の、 コンピュータ読取可能な記録媒体に記 録された形態で提供される。 そして、 コンピュータはその記録媒体からプロダラ ムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。 又、 そのプログラムを、 例えば磁気ディスク， 光ディスク, 光磁気ディスク等の記憶 装置 （記録媒体） に記録しておき、 その記憶装置から通信経路を介してコンビュ ータに提供するようにしてもよい。
ゼロ点判定部 21， スカラー倍算処理部 22， 線形座標変換部 （座標変換部） 23および乱数生成部 24としての機能を実現する際には、 内部記憶装置 （記憶 部 1 6, メモリ 32) に格納されたプログラムがコンピュータのマイクロプロセ ッサ （演算部 12, CPU 31) によって実行される。 このとき、 記録媒体に記 録されたプログラムをコンピュータが読み取つて実行するようにしてもよレ、。 なお、 本実施形態において、 コンピュータとは、 ハードウェアとオペレーティ ングシステムとを含む概念であり、 オペレーティングシステムの制御の下で動作 するハードウェアを意味している。 又、 オペレーティングシステムが不要でァプ リケーシヨンプログラム単独でハードウェアを動作させるような場合には、 その ハードウェア自体がコンピュータに相当する。 ハードウェアは、 少なくとも、 C PU等のマイクロプロセッサと、 記録媒体に記録されたコンピュータプログラム を読み取るための手段とをそなえており、 本実施形態においては、 楕円曲線暗号 装置 11がコンピュータとしての機能を有しているのである。
さらに、 本実施形態における記録媒体としては、 上述したフレキシブルデイス ク， CD— ROM, CD-R, CD-R/W, DVD, DVD-R, DVD-R /W, 磁気ディスク， 光ディスク， 光磁気ディスクのほか、 I Cカード， ROM カートリッジ， 磁気テープ， パンチカード， コンピュータの内部記憶装置 （RA Mや ROMなどのメモリ），外部記憶装置等や、バーコードなどの符号が印刷され た印刷物等のコンピュータ読取可能な種々の媒体を利用することができる。 そして、 本発明は、 楕円曲線暗号の暗号化及び解読を行なう専用の装置に限ら ず、 I Cカード、 DVD装置、 携帯電話機、 パーソナルコンピュータ等の種々の 製品に適用できる。
そして、 本発明は上述した各実施形態に限定されるものではなく、 本発明の趣 旨を逸脱しなレ、範囲で種々変形して実施することができる。
例えば、 演算部 1 2力 S、 記憶部 1 6に記憶されたプログラムを実行することに より、 ゼロ点判定部 21， スカラ一倍算処理部 22 , 線形座標変換部 23および 乱数生成部 24として機能するようになっているが、 これに限定されるものでは なく、 例えば、 ゼロ点判定部 21, スカラー倍算処理部 22, 線形座標変換部 2 3および乱数生成部 24のうちの一部の機能を外部装置が処理してもよく、 例え ば、 スカラー倍算処理部 22のみを実行してもよい。
また、 本楕円曲線暗号装置 1 1は、 例えば、 プロセッサをそなえたスマート力 ードによって実現されてもよく、 又、 スマートカードのメモリに秘密鍵や秘密鍵 のみを格納しておき、 このスマートと通信可能に接続された外部装置 （楕円曲線 喑号装置） によつて楕円曲線暗号処理を行なつてもよい。
さらに、 上述した第 1実施形態および第 2実施形態では、 線形座標変換部 23 、 パラメーター （r 1， r 2， r 3, s 1， s 2, s 3) = (r " 2, r " 3， r , s , 0， 0) に基づいて線形座標変換を行なう例について説明しているが、 これに限定されるものではなく、 例えば、 パラメータ （r l, r 2, r 3) の部 分が第 3〜第 5実施形態と同様に （r, r , r ) であってもよく、 又、 これらの r 1 , r 2, r 3のうち一部もしくは全てが互いに異なる数値であってもよレ、。 また、 上述した第 3〜第 5実施形態では、 線形座標変換部 23が、 パラメータ 一 （r l, r 2, r 3, s l， s 2, s 3) = ( r , r , r , s , 0， 0) に基 づいて線形座標変換を行なう例について説明しているが、 これに限定されるもの ではなく、 例えば、 パラメータ （r 1 , r 2, r 3) の部分が第 1実施形態や第 2実施形態と同様に（r 2， r " 3, r ) であってもよく、又、 これらの r 1, r 2, r 3のうち一部もしくは全てが互いに異なる数値であってもよレ、。
さらに、 上述した各実施形態について、 線形座標変換部 23が線形座標変換に 用いるパラメーター （r 1 , r 2, r 3, s l， s 2, s 3 ) における、 ノヽ。ラメ ータ （s i, s 2， s 3) の部分は、 （s、 0， 0) に限定されるものではなく、 例えば、 s i, s 2, s 3のいずれも 0以外の値であってもよく、 又、 3 1と 5 3とだけがそれぞれ 0, s 1と s 2とだけがそれぞれ 0， s 3だけが 0, s 2だ けが 0， s 1だけが 0等、 種々変形して実施することができる。 更に、 これらの s 1 , s 2 , s 3のうち一部もしくは全てが互いに異なる数値であってもよレ、。 ここで、 パラメータ s 1に 0ではない数値 sを適用することにより、 X座標が 0であるような特殊点は、 線型変換座標での X座標が sの点として表され、 スカ ラー倍算の途中で出現することがない。 これにより X座標に関する特殊点攻撃に 対して安全となる。
また、 パラメータ s 2に 0ではない数値 sを適用することにより、 y座標が 0 であるような特殊点は、 線型変換座標での Y座標が sの点として表され、 スカラ 一倍算の途中で出現することがなく、 y座標に関する特殊点攻撃に対して安全と なる。 同様に、 パラメータ s 3に 0ではない数値 sを適用することにより、 z座 標が 0であるような特殊点は、 線型変換座標での Z座標が sの点として表され、 スカラー倍算の途中で出現することがなく、 z座標に関する特殊点攻撃に対して 安全となる。
さらに、 上述した線形座標変換部 2 3によって線形座標変換を行なった変換後 の座標を、 スカラー倍算処理部 2 2が、 ウィンドウ法 （Algorithm 6， 6 ' , 6 〃 参照） を用いてスカラー倍算を行なってもよく、 これにより、 特殊点攻撃に対 して安全であるとともに S P Aに対しても安全である。
また、 上述した各実施形態においては、 pを 5以上の素数とし、 要素数 pの有 限体 G F ( p ) ( pは 5以上の素数）上の楕円曲線に適用した場合について説明し ているが、 これに限定されるものではなく、 本発明の趣旨を逸脱しない範囲で種 々変形して実施することができる。
なお、 本発明の各実施形態が開示されていれば、 本発明の楕円曲線暗号装置， 楕円曲線暗号方法， 楕円曲線喑号プログラムおよび同プログラムを記録したコン ピュータ読取可能な記録媒体を当業者によって実施'製造することが可能である。 産業上の利用可能性
以上のように、 本発明の楕円曲線暗号装置， 楕円曲線暗号方法， 楕円曲線暗号 プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体は、 楕円曲線暗号処理を行なうのに有用であり、 特にサイドチャネル攻撃に対して有 効である。

Claims

請 求 の 範 囲
1. 楕円曲線暗号処理を行なう楕円曲線暗号装置であって、
有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X ： Y ： Z) を座 標 （r l X (X - s i) : r 2 X (Y_ s 2) ： r 3 X (Z— s 3)) に変換する座 標変換部 （23) (ただし、 pは素数、 mは 1以上の整数、 r 1, r 2， r 3はそ れぞれ 1以上且つ （p_ 1) 以下の整数、 s l， s 2, s 3はそれぞれ 0以上且 つ （p— 1) 以下の整数、 又、 符号"はべき乗を表わす） と、
該座標変換部 （23) によって変換された楕円曲線上の点のスカラー倍算を行 なうスカラー倍算演算部 （22) とをそなえ、
該パラメーター s l， s 2， s 3のうち少なくとも 1つが 0以外の値を有する ことを特徴とする、 楕円曲線暗号装置。
2. 該スカラー倍算演算部 （22) が、'アド 'アンド 'ダブル'オールウェイズ を用いたバイ: リメソッドで、 該スカラー倍算を行なうことを特徴とする、 請求 の範囲第 1項に記載の楕円曲線暗号装置。
3. 該スカラー倍算演算部 （22) 1S モンゴメリ 'ラダー法で前記スカラー倍 算を行なうことを特徴とする、 請求の範囲第 1項に記載の楕円曲線暗号装置。
4. 該スカラー倍算演算部 （22) 力 ウィンドウ ·メソッドで前記スカラー倍 算を行なうことを特徴とする、 請求の範囲第 1項に記載の楕円曲線暗号装置。
5. 該スカラー倍算演算部 （22) 、 X座標法で前記スカラー倍算を行なうこ とを特徴とする、 請求の範囲第 1項に記載の楕円曲線暗号装置。
6. 該スカラー倍算演算部 （22) 、 連続楕円 2倍算を用いて前記スカラー倍 算を行なうことを特徴とする、 請求の範囲第 1項に記載の楕円曲線暗号装置。
7. 楕円曲線喑号処理を行なう楕円曲線暗号方法であって、 有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X： Y ： Z) を座 標 （r 1 X (X- s i) : r 2 X (Y— s 2) : r 3 X (Z- s 3)) に変換する座 標変換ステップ （ただし、 pは素数、 mは 1以上の整数、 r l， r 2, r 3はそ れぞれ 1以上且つ （p _ 1) 以下の整数、 s 1， s 2, s 3はそれぞれ 0以上且 5 つ （p— 1) 以下の整数、 又、 符号'はべき乗を表わす） と、
該座標変換ステップにおいて変換された楕円曲線上の点のス力ラ一倍算を行な うスカラー倍算演算ステップとをそなえ、
該パラメーター s i, s 2， s 3のうち少なくとも 1つが 0以外の値を有する \ー - ことを特徴とする、 楕円曲線暗号方法。
10
8. 該スカラー倍算演算ステップにおいて、 アド 'アンド 'ダブル'オールゥェ ィズを用いたバイナリメソッドで、 該スカラ一倍算を行なうことを特徴とする、 請求の範囲第 7項に記載の楕円曲線暗号方法。
15 9. 該スカラー倍算演算ステップにおいて、 モンゴメリ 'ラダー法で前記スカラ 一倍算を行なうことを特徴とする、請求の範囲第 7項に記載の楕円曲線暗号方法。
1 0. 該スカラー倍算演算ステップにおいて、 ウィンドウ 'メソッドで前記スカ ラー倍算を行なうことを特徴とする、 請求の範囲第 7項に記載の楕円曲線暗号方
20 法。
1 1. 該スカラー倍算演算ステップにおいて、 X座標法で前記スカラー倍算を行 なうことを特徴とする、 請求の範囲第 7項に記載の楕円曲線暗号方法。
25 1 2. 該スカラー倍算演算ステップにおいて、 連続楕円 2倍算を用いて前記スカ ラー倍算を行なうことを特徴とする、 請求の範囲第 7項に記載の楕円曲線暗号装 置。
1 3. 楕円曲線暗号処理を行なう楕円曲線暗号プログラムであって、 有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X ： Y ： Z) を座 標 （r l X (X- s i) : r 2 X (Y- s 2) : r 3 X (Z— s 3)) に変換する座 標変換部 （23) (ただし、 pは素数、 mは 1以上の整数、 r 1, r 2， r 3はそ れぞれ 1以上且つ （p— 1) 以下の整数、 s i, s 2, s 3はそれぞれ 0以上且 つ （p— 1) 以下の整数であり、 且つ、 これらの s 1， s 2, s 3のうち少なく とも 1つが 0以外の値を有する。 又、 符号 ~はべき乗を表わす） と、
該座標変換部 （23) によって変換された楕円曲線上の点のスカラー倍算を行 なうスカラー倍算演算部 （22) としてコンピュータを機能させることを特徴と する、 楕円曲線暗号プログラム。
-
1 4. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 アド ·アンド .ダブル .オールウェイズを用いたバイナリメソッドで、 該スカラ 一倍算を行なうことを特徴とする、 請求の範囲第 1 3項に記載の楕円曲線暗号プ 口グラム。
1 5. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 モンゴメリ ·ラダー法で前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 3項に記載の楕円曲線暗号プログラム。
1 6. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 ウィンドウ ·メソッドで前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 3項に記載の楕円曲線暗号プログラム。
1 7. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 X座標法で前記スカラー倍算を行なうことを特徴とする、 請求の範囲第 1 3項に 記載の楕円曲線暗号プログラム。
1 8. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 連続楕円 2倍算を用いて前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 3項に記載の楕円曲線暗号プログラム。
1 9. 楕円曲線暗号処理を行なう楕円曲線暗号プログラムを記録したコンビユー タ読取可能な記録媒体であって、
該楕円曲線暗号プログラムが、
有限体 GF (p " m) 上における楕円曲線上の点 Pの座標 （X： Y： Z) を座 標 (r 1 X (X- s 1) ： r 2 X (Y— s 2) ： r 3 X (Z - s 3)) に変換する座 標変換部 （23) (ただし、 pは素数、 mは 1以上の整数、 r 1, r 2， r 3はそ れぞれ 1以上且つ （p _ 1) 以下の整数、 s l， s 2, s 3はそれぞれ 0以上且 つ （p— 1 ) 以下の整数であり、 且つ、 これらの s 1， s 2, s 3のうち少なく とも 1つが 0以外の値を有する。 又、 符号 ~はべき乗を表わす） と、
該座標変換部 （23) によって変換された楕円曲線上の点のスカラー倍算を行 なうスカラー倍算演算部 （22) としてコンピュータを機能させることを特徴と する、 楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
20. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 ァド ·アンド ·ダブル ·オールウェイズを用いたバイナリメソッドで、 該スカラ 一倍算を行なうことを特徴とする、 請求の範囲第 1 9項に記載の楕円曲線暗号プ ログラムを記録したコンピュータ読取可能な記録媒体。
2 1. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 モンゴメリ ·ラダー法で前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 9項に記載の楕円曲線喑号プログラムを記録したコンピュータ読取可能な 記録媒体。
22. 該スカラー倍算演算部 （22) として該コンピュータを機能させる際に、 ウィンドウ ·メソッドで前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 9項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な 記録媒体。
2 3 . 該スカラー倍算演算部 （2 2 ) として該コンピュータを機能させる際に、 X座標法で前記スカラー倍算を行なうことを特徴とする、 請求の範囲第 1 9項に 記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
2 4 . 該スカラー倍算演算部 （2 2 ) として該コンピュータを機能させる際に、 連続楕円 2倍算を用いて前記スカラー倍算を行なうことを特徴とする、 請求の範 囲第 1 9項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な 記録媒体。
PCT/JP2003/010003 2003-08-06 2003-08-06 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体 Ceased WO2005015526A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
EP03817985A EP1653428B1 (en) 2003-08-06 2003-08-06 Elliptic curve encrypting device, elliptic curve encrypting method, elliptic curve encrypting program and computer-readable recording medium recording that program
PCT/JP2003/010003 WO2005015526A1 (ja) 2003-08-06 2003-08-06 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体
JP2005507578A JP4284320B2 (ja) 2003-08-06 2003-08-06 楕円曲線暗号装置，楕円曲線暗号方法および楕円曲線暗号プログラム
US11/311,590 US7639808B2 (en) 2003-08-06 2005-12-16 Elliptic curve cryptosystem apparatus, elliptic curve cryptosystem method, elliptic curve cryptosystem program and computer readable recording medium storing the elliptic curve cryptosystem program

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2003/010003 WO2005015526A1 (ja) 2003-08-06 2003-08-06 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US11/311,590 Continuation US7639808B2 (en) 2003-08-06 2005-12-16 Elliptic curve cryptosystem apparatus, elliptic curve cryptosystem method, elliptic curve cryptosystem program and computer readable recording medium storing the elliptic curve cryptosystem program

Publications (1)

Publication Number Publication Date
WO2005015526A1 true WO2005015526A1 (ja) 2005-02-17

Family

ID=34131269

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2003/010003 Ceased WO2005015526A1 (ja) 2003-08-06 2003-08-06 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体

Country Status (4)

Country Link
US (1) US7639808B2 (ja)
EP (1) EP1653428B1 (ja)
JP (1) JP4284320B2 (ja)
WO (1) WO2005015526A1 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008042908A (ja) * 2006-08-04 2008-02-21 Samsung Electronics Co Ltd 高速モンゴメリパワーラダーアルゴリズムを利用する欠陥検出動作を具現するための二進有限領域におけるポイント加算方法及び加算演算装置
JP2010068293A (ja) * 2008-09-11 2010-03-25 Toshiba Corp 秘密情報を用いて演算する装置、方法およびプログラム
US8369514B2 (en) 2006-03-28 2013-02-05 Seimens Aktiengesellschaft Method for the secure determination of data
JP2017067859A (ja) * 2015-09-28 2017-04-06 株式会社メガチップス スカラー倍算装置及びスカラー倍算方法
CN111966324A (zh) * 2020-08-19 2020-11-20 哈尔滨理工大学 面向多椭圆曲线标量乘法器的实现方法、装置及存储介质

Families Citing this family (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE602005020991D1 (de) * 2005-10-28 2010-06-10 Telecom Italia Spa Verfahren zur skalarmultiplikation in gruppen ellir nebenkanalattacken-beständige kryptosysteme
KR100874909B1 (ko) * 2006-01-14 2008-12-19 삼성전자주식회사 Ｄｆａ에 대항하는 몽고메리 전력 래더 알고리즘을 사용하는 암호화 방법
DE102006002891B4 (de) * 2006-01-20 2009-06-04 Siemens Ag Verfahren, Vorrichtung und System zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten
KR100850202B1 (ko) * 2006-03-04 2008-08-04 삼성전자주식회사 Ｅｃｃ 패스트 몽고매리 전력 래더 알고리즘을 이용하여ｄｆａ 에 대응하는 암호화 방법
EP1840732A1 (en) * 2006-03-31 2007-10-03 Axalto SA Protection against side channel attacks
US8311214B2 (en) * 2006-04-24 2012-11-13 Motorola Mobility Llc Method for elliptic curve public key cryptographic validation
CN101079203B (zh) * 2006-05-22 2010-07-28 北京华大信安科技有限公司 椭圆曲线密码系统和方法
US7864951B2 (en) * 2006-07-10 2011-01-04 King Fahd University Of Petroleum And Minerals Scalar multiplication method with inherent countermeasures
DE102006060760A1 (de) * 2006-09-29 2008-04-10 Siemens Ag Authentifikationsverfahren und Kommunikationssystem zur Authentifikation
US7856101B2 (en) * 2007-02-07 2010-12-21 King Fahd University Of Petroleum And Minerals Method for elliptic curve scalar multiplication
US8102998B2 (en) * 2007-05-02 2012-01-24 King Fahd University Of Petroleum And Minerals Method for elliptic curve scalar multiplication using parameterized projective coordinates
US8559625B2 (en) * 2007-08-07 2013-10-15 Inside Secure Elliptic curve point transformations
US8670557B2 (en) * 2007-09-10 2014-03-11 Spansion Llc Cryptographic system with modular randomization of exponentiation
US8233615B2 (en) 2008-01-15 2012-07-31 Inside Secure Modular reduction using a special form of the modulus
US8619977B2 (en) * 2008-01-15 2013-12-31 Inside Secure Representation change of a point on an elliptic curve
EP2090978A1 (en) * 2008-02-15 2009-08-19 Thomson Licensing An apparatus and a method for calculating a multiple of a point on an elliptic curve
US20090214023A1 (en) * 2008-02-26 2009-08-27 Al-Somani Turki F Method for elliptic curve scalar multiplication
US8422685B2 (en) 2008-02-26 2013-04-16 King Fahd University Of Petroleum And Minerals Method for elliptic curve scalar multiplication
US7991154B2 (en) * 2008-05-14 2011-08-02 Univeristy of Castilla-La Mancha Exponentiation method using multibase number representation
JP2010164904A (ja) * 2009-01-19 2010-07-29 Fujitsu Ltd 楕円曲線演算処理装置、楕円曲線演算処理プログラム及び方法
US8542820B2 (en) * 2009-02-05 2013-09-24 Infineon Technologies Ag Apparatus for calculating a result of a scalar multiplication
US8699701B2 (en) * 2010-12-01 2014-04-15 King Fahd University Method of performing XZ-elliptic curve cryptography for use with network security protocols
US20130336479A1 (en) * 2012-06-15 2013-12-19 Kabushiki Kaisha Toshiba Information recording device
DE102012210354B3 (de) * 2012-06-20 2013-11-07 Siemens Aktiengesellschaft Verfahren und Recheneinheit zur Erzeugung kryptographischer Daten
FR3016987B1 (fr) * 2014-01-29 2017-07-21 Morpho Echelle de montgomery desequilibree
CN104184578B (zh) * 2014-07-30 2017-07-07 山东大学 一种基于fpga的椭圆曲线标量乘法加速电路及其算法
US9645794B2 (en) * 2014-09-23 2017-05-09 Texas Instruments Incorporated Homogeneous atomic pattern for double, add, and subtract operations for digital authentication using elliptic curve cryptography
US9590805B1 (en) * 2014-12-23 2017-03-07 EMC IP Holding Company LLC Ladder-based cryptographic techniques using pre-computed points
US11146397B2 (en) * 2017-10-31 2021-10-12 Micro Focus Llc Encoding abelian variety-based ciphertext with metadata
CN108875416B (zh) * 2018-06-22 2020-05-19 北京智芯微电子科技有限公司 椭圆曲线多倍点运算方法和装置
CN114527956B (zh) * 2022-01-25 2024-05-10 北京航空航天大学 抗spa攻击的sm2算法中非定点标量乘法的计算方法
CN115344525B (zh) * 2022-08-16 2023-04-18 江南信安（北京）科技有限公司 一种椭圆曲线点加硬件加速方法及装置

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002540483A (ja) * 1999-03-26 2002-11-26 ジェムプリュス 楕円曲線型公開鍵暗号化アルゴリズムを用いる電子構成部品内の対抗措置方法

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5854759A (en) * 1997-05-05 1998-12-29 Rsa Data Security, Inc. Methods and apparatus for efficient finite field basis conversion
US6212279B1 (en) * 1998-06-26 2001-04-03 The United States Of America As Represented By The United States National Security Agency Method of elliptic curve cryptographic key exchange using reduced base tau expansion in non-adjacent form

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002540483A (ja) * 1999-03-26 2002-11-26 ジェムプリュス 楕円曲線型公開鍵暗号化アルゴリズムを用いる電子構成部品内の対抗措置方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
OKEYA K. ET AL.: "Jisso kogeki ni okeru katei no kyojaku to jitsugen kanosei ni tsuite", 2003 NEN ANGO TO JOHO SECURITY SYMPOSIUM YOKOSHU, vol. 1, 26 January 2003 (2003-01-26), pages 539 - 544, XP002984915 *
See also references of EP1653428A4 *

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8369514B2 (en) 2006-03-28 2013-02-05 Seimens Aktiengesellschaft Method for the secure determination of data
JP2008042908A (ja) * 2006-08-04 2008-02-21 Samsung Electronics Co Ltd 高速モンゴメリパワーラダーアルゴリズムを利用する欠陥検出動作を具現するための二進有限領域におけるポイント加算方法及び加算演算装置
JP2010068293A (ja) * 2008-09-11 2010-03-25 Toshiba Corp 秘密情報を用いて演算する装置、方法およびプログラム
JP2017067859A (ja) * 2015-09-28 2017-04-06 株式会社メガチップス スカラー倍算装置及びスカラー倍算方法
CN111966324A (zh) * 2020-08-19 2020-11-20 哈尔滨理工大学 面向多椭圆曲线标量乘法器的实现方法、装置及存储介质
CN111966324B (zh) * 2020-08-19 2024-01-30 哈尔滨理工大学 面向多椭圆曲线标量乘法器的实现方法、装置及存储介质

Also Published As

Publication number Publication date
US7639808B2 (en) 2009-12-29
JP4284320B2 (ja) 2009-06-24
EP1653428A4 (en) 2008-04-09
JPWO2005015526A1 (ja) 2006-10-05
EP1653428A1 (en) 2006-05-03
EP1653428B1 (en) 2012-08-15
US20060093137A1 (en) 2006-05-04

Similar Documents

Publication Publication Date Title
WO2005015526A1 (ja) 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体
JP4789468B2 (ja) 秘密鍵を用いた耐タンパ楕円曲線暗号処理
JP5412274B2 (ja) サイドチャネル攻撃からの保護
JP3821631B2 (ja) 楕円曲線暗号におけるスカラー倍計算方法及び装置、並びに記憶媒体
EP1320027B1 (en) Elliptic curve cryptosystem apparatus, method and program
US8391477B2 (en) Cryptographic device having tamper resistance to power analysis attack
CN106464483B (zh) 用于电子部件实现椭圆曲线密码算法的应对方法、电子电路和电子系统
WO2001024439A1 (en) Device, program or system for processing secret information
Hutter et al. NaCl’s crypto_box in hardware
US8300810B2 (en) Method for securely encrypting or decrypting a message
WO2012086076A1 (ja) 署名生成装置及び署名生成方法及び記録媒体
WO2012090289A1 (ja) 暗号処理装置および方法
JP4513752B2 (ja) 暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラム
KR101440680B1 (ko) 중국인 나머지 정리에 기반한 준동형 암복호화 방법 및 이를 이용한 장치
JP2004163687A (ja) 楕円曲線暗号装置、楕円曲線暗号プログラム
KR102253211B1 (ko) 소수체와 이진체 상의 타원곡선을 지원하는 공개키 암호 시스템의 하드웨어 구현을 위한 연산장치 및 방법
KR100564599B1 (ko) 역원 계산 회로, 역원계산 방법 및 상기 역원계산 방법을실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수있는 기록매체
JP4502817B2 (ja) 楕円曲線スカラー倍計算方法および装置
JP2010008883A (ja) 暗号用演算装置、暗号用演算方法及びプログラム
JP4772081B2 (ja) 秘密鍵を用いた耐タンパ楕円曲線暗号処理
JP4692022B2 (ja) 楕円曲線暗号におけるスカラー倍計算装置、及び、そのプログラム
Dąbrowski et al. Generation and Implementation of Cryptographically Strong Elliptic Curves
JP2006072336A (ja) 素因数分解装置、素因数分解プログラム、安全性評価装置、安全性評価プログラム及び素因数分解方法
JP2007212768A (ja) 楕円曲線暗号における事前計算テーブル作成装置
JP4243179B2 (ja) 演算装置

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2005507578

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 11311590

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 2003817985

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2003817985

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 11311590

Country of ref document: US