Miyaji Laboratory

In 1976, the concept of a public key cryptosystem was proposed by Diffie and Hellman. After this, various public key cryptosystems were researched e.g. RSA, ElGamal scheme. A public key cryptosystem (PKC) is different from a symmetric cryptosystem (which is often called "conventional crypto"). A "public" means that a key which is used for encryption is allowed to be OPEN in the system. On the others hand, a key which is used for decryption should be secret. PKC was expected for not only data encryption but also digital signature etc. , then nowadays we can see PKC in many information society scene. Recently, factoring problem and discrete logarithm problem (with short keys) which are security bases of PKC become vulnerable because computer performance is developed amazingly, so to make secure cryptosystem we must take long size key.

In such situation, Elliptic Curve Cryptosystem (ECC) and Hyper ECC (HECC) have been studied actively as a new cryptosystem in next generation. ECC is based on the points on an elliptic curve becoming a group, and elliptic curve discrete logarithm problem (ECDLP). It was proposed by Koblitz and Miller in 1985 independently. Encryption and decryption key size of ECC is short and compact compared with RSA etc. Therefore, ECC is used for the smart card whose resource is not rich with a small memory. The operation that becomes the center of ECC is an arithmetic calculation of scalar multiplication dP to point $P$ on an elliptic curve and secret key d regardless of decoding the cipher text or generating the signature. And the point addition is defined by ECADD where different point are added (P+Q) and ECDBL where a point is doubled (2P). Scalar multiplication can be divided to 2 kinds, one is called "Fixed point scalar multiplication" using a table where has pre-computed points, and the other is named "Arbitrary point scalar multiplication". As the first one, there are MOC-method which divides scalar and BGMW-method which treats only ECADD etc. Window-method and NAF-scalar-presentation with short memory belong to the second method. To make efficient ECC, we need a fast scalar multiplication algorithm which does not use many memories so that we can use ECC on a smartcard.
New attack method named Side Channel Attack (SCA) has become new threat to a smart card whose power is supplied from outside. SCA utilizes side channel information like power consumption, sound, timing etc. Among above all of side channel information, power consumption is easy to be used in SCA. In ECC, ECADD and ECDBL have a different calculation, so SCA makes use of this difference. The method which utilizes simple measurement is called Simple Power Analyze (SPA), the other method that analyzes many traces with statistical tools is called Different Power Analyze (DPA). DPA is stronger attack than SPA. Many countermeasures have been proposed against SPA and DPA. Side Channel Atomicity is the main current method as a countermeasure against SPA, which regards each of a calculation in a finite field as a block which contains a small set of arithmetic. As a DPA countermeasure, "adding" a random point on EC to a initial point and after scalar multiplication, "subtracting" the rand

In our research, we applied Montgomery's Trick (MT) for MOC-method as a fixed point scalar multiplication and proposed a fast algorithm. Usually a calculation for rational points on ECC needs inversion in a finite field arithmetic calculation (Affine coordinate). Inverse operation takes much cost compared with multiplication and squaring, so to avoid this costly procedure, Jacobian coodinate is often used where only one inverse is needed. Our proposed method in Affine coordinate improved how to make tables in MOC-method and applied MT, then we archived an efficient scalar multiplication with a few inversions. MT is that inversions of several field elements can be computed simultaneously by one inversion and some extra multiplication. When we need n inversions of filed elements, MT can reduce the cost to only one inversion and 3(n-1) multiplications. This proposed method can be extended to the curves with genus >= 2, so in HECC we succeed to reduce the cost of calculations.
About an arbitrary point scalar multiplication, we proposed new algorithm with triple bases without pre-computation. In many scalar multiplication algorithms, a base number 2 is used widely. So the operation 2P, 2P+Q are taken repeatedly. We added the operation 3P+Q proposed by Ciet et.al. and new formulae 5P +- Q, 5P +- 2Q, then we got a realization of a speedy scalar multiplication in Affine coordinate. Moreover in Jacobian coordinate, we applied 5P operation for DIM-method which uses two base numbers, and we archived an efficient scale multiplication.
These new methods can be combined with Side Channel Atomicity and RIP, so we can say they are efficient scalar multiplication with tolerance against SCA.