Power analysis can be used to attack many implementations of cryptosystems, e.g., RSA and ECC, and the doubling attack is a collision based power analysis performed on two chosen ciphertexts. In this paper, we introduced a modified doubling attack to threaten RSA and ECC implementations by exploiting only one chosen ciphertext of small order. To attack the RSA implementations we selected an input of order two while to attack the ECC implementations we exploited one chosen invalid point of small order on a cryptographically weak curve rather than on the original curve. We showed that several existing power analysis countermeasures for RSA and ECC implementations are still vulnerable to the proposed attack. To prevent the proposed attack, we suggested countermeasures for RSA as well as for ECC.

This paper presents a new approach to precompute points [3]P, [5]P,..., [2k-1]P, for some k ≥ 2 on an elliptic curve over Fp. Those points are required for the efficient evaluation of a scalar multiplication, the most important operation in elliptic curve cryptography. The proposed method precomputes the points in affine coordinates and needs only one single field inversion for the computation. The new method is superior to all known methods that also use one field inversion, if the required memory is taken into consideration. Compared to methods that require several field inversions for the precomputation, the proposed method is faster for a broad range of ratios of field inversions and field multiplications. The proposed method benefits especially from ratios as they occur on smart cards.

Recently, the result of TinyECCK (Tiny Elliptic Curve Cryptosystem with Koblitz curve) shows that both field multiplication and reduction over GF(2m) are related to a heavy amount of duplicated memory accesses and that reducing the number of these duplications noticeably improves the performance of elliptic curve operations such as scalar multiplications, signing and verification. However, in case that the underlying word size is extended from 8-bit to 16-bit or 32-bit, the efficiency of the techniques proposed in TinyECCK is decreased because the number of memory accesses to load or store an element in GF(2m) is significantly reduced. Therefore, in this paper, we propose a technique which makes left-to-right (ltr) comb method which is widely used as an efficient multiplication algorithm over GF(2m) suitable for extended word sizes and present TinyECCK16 (Tiny Elliptic Curve Cryptosystem with Koblitz curve on 16-bit word) which is implemented with the proposed multiplication algorithm on 16-bit Tmote Sky mote. The proposed algorithm is faster than typical ltr comb method by 15.06% and the 16-bit version of the algorithm proposed in TinyECCK by 5.12% over GF(2163).

Scalar multiplication methods using the Frobenius maps are known for efficient methods to speed up (hyper)elliptic curve cryptosystems. However, those methods are not efficient for the cryptosystems constructed on fields of small extension degrees due to costs of the field operations. Iijima et al. showed that one can use certain automorphisms on the quadratic twists of elliptic curves for fast scalar multiplications without the drawback of the Frobenius maps. This paper shows an extension of the automorphisms on the Jacobians of hyperelliptic curves of arbitrary genus.

In this paper, we revisit a generally accepted opinion: implementing Elliptic Curve Cryptosystem (ECC) over GF(2m) on sensor motes using small word size is not appropriate because XOR multiplication over GF(2m) is not efficiently supported by current low-powered microprocessors. Although there are some implementations over GF(2m) on sensor motes, their performances are not satisfactory enough to be used for wireless sensor networks (WSNs). We have found that a field multiplication over GF(2m) are involved in a number of redundant memory accesses and its inefficiency is originated from this problem. Moreover, the field reduction process also requires many redundant memory accesses. Therefore, we propose some techniques for reducing unnecessary memory accesses. With the proposed strategies, the running time of field multiplication and reduction over GF(2163) can be decreased by 21.1% and 24.7%, respectively. These savings noticeably decrease execution times spent in Elliptic Curve Digital Signature Algorithm (ECDSA) operations (signing and verification) by around 15-19%. We present TinyECCK (Tiny Elliptic Curve Cryptosystem with Koblitz curve - a kind of TinyOS package supporting elliptic curve operations) which is the first implementation of Koblitz curve on sensor motes as far as we know. Through comparisons with existing software implementations of ECC built in C or hybrid of C and inline assembly on sensor motes, we show that TinyECCK outperforms them in terms of running time, code size and supporting services. Furthermore, we show that a field multiplication over GF(2m) can be faster than that over GF(p) on 8-bit Atmega128 processor by comparing TinyECCK with TinyECC, a well-known ECC implementation over GF(p). TinyECCK with sect163k1 can generate a signature and verify it in 1.37 and 2.32 secs on a Micaz mote with 13,748-byte of ROM and 1,004-byte of RAM.

In this letter, we provide a simple proof of bilinearity for the eta pairing. Based on it, we show an efficient method to compute the powered Tate pairing as well. Although efficiency of our method is equivalent to that of the Tate pairing on the eta pairing approach, but ours is more general in principle.

This study employs secret codes and secret keys based on the elliptic curve to construct an elliptic curve cryptosystem with a dynamic access control system. Consequently, the storage space needed for the secret key generated by an elliptic curve dynamic access control system is smaller than that needed for the secret key generated by exponential operation built on the secure filter (SF) dynamic access control system. Using the elliptic curve to encrypt/decrypt on the secure filter improves the efficiency and security of using exponential operation on the secure filter in the dynamic access control system. With the proposed dynamic elliptic curve access control system, the trusted central authority (CA) can add/delete classes and relationships and change the secret keys at any time to achieve an efficient control and management. Furthermore, different possible attacks are used to analyze the security risks. Since attackers can only obtain the general equations for the elliptic curve dynamic access control system, they are unable to effectively perform an elliptic curve polynomial (ECP) conversion, or to solve the elliptic curve discrete logarithm problem (ECDLP). Thus, the proposed elliptic curve dynamic access control system is secure.

The most time consuming operation to verify a signature with the Elliptic Curve Digital Signature Algorithm is a multi-scalar multiplication with two scalars. Efficient methods for its computation are the Shamir method and the Interleave method, whereas the performance of those methods can be improved by using general base-2 representations of the scalars. In exchange for the speed-up, those representations require the precomputation of several points that must be stored. In the case of two precomputed points, the Interleave method and the Shamir method provide the same, optimal efficiency. In the case of more precomputed points, only the Interleave method can be sped-up in an optimal way and is currently more efficient than the Shamir method. This paper proposes a new general base-2 representation of the scalars that can be used to speed up the Shamir method. It requires the precomputation of ten points and is more efficient than any other representation that also requires ten precomputed points. Therefore, the proposed method is the first to improve the Shamir method such that it is faster than the Interleave method.

This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a Cab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the Cab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.

We propose a new analysis technique against a class of countermeasure using randomized binary signed digit (BSD) representations. We also introduce some invariant properties between BSD representations. The proposed analysis technique can directly recover the secret key from power measurements without information for algorithm because of the invariant properties of BSD representation. Thus the proposed attack is applicable to all countermeasures using BSD representations. Finally, we give the simulation results against some countermeasures using BSD representation such as Ha-Moon method, Ebeid-Hasan method, and the method of Agagliate et al. The results show that the proposed attack is practical analysis method.

Koblitz curves belong to a special class of binary curves on which the scalar multiplication can be computed very efficiently. For this reason, they are suitable candidates for implementations on low-end processors. However, such devices are often vulnerable to side channel attacks. In this paper, we propose a new countermeasure against side channel attacks on Koblitz curves, which utilizes a fixed-pattern recoding to defeat simple power analysis. We show that in practical cases, the recoding can be performed from left to right, and can be easily stored or even randomly generated.

Elliptic curve cryptosystems are expected to be a next standard of public-key cryptosystems. A security level of elliptic curve cryptosystems depends on a difficulty of a discrete logarithm problem on elliptic curves. The security level of a elliptic curve cryptosystem which has a public-key of 160-bit is equivalent to that of a RSA system which has a public-key of 1024-bit. We propose an elliptic curve cryptosystem LSI architecture embedding word-based Montgomery multipliers. A Montgomery multiplication is an efficient method for a finite field multiplication. We can design a scalable architecture for an elliptic curve cryptosystem by selecting structure of word-based Montgomery multipliers. Experimental results demonstrate effectiveness and efficiency of the proposed architecture. In the hardware evaluation using 0.18 µm CMOS library, the high-speed design using 126 Kgates with 208-bit multipliers achieved operation times of 3.6 ms for a 160-bit point multiplication.

Elliptic curves offer interesting possibilities for alternative cryptosystems, especially in constrained environments like smartcards. However, cryptographic routines running on such lightweight devices can be attacked with the help of "side channel information"; power consumption, for instance. Elliptic curve cryptosystems are not an exception: if no precaution is taken, power traces can help attackers to reveal secret information stored in tamper-resistant devices. Okeya-Takagi scheme (OT scheme) is an efficient countermeasure against such attacks on elliptic curve cryptosystems, which has the unique feature to allow any size for the pre-computed table: depending on how much memory is available, users can flexibly change the table size to fit their needs. Since the nature of OT scheme is different from other side-channel attack countermeasures, it is necessary to deeply investigate its security. In this paper, we present a comprehensive security analysis of OT scheme, and show that based on information leaked by power consumption traces, attackers can slightly enhance standard attacks. Then, we explain how to prevent such information leakage with simple and efficient modifications.

We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). Concerning the security of HECC, the theta divisors play an important role. The scalar multiplication using a random base point is vulnerable to an exceptional procedure attack, which is a kind of side-channel attacks, using theta divisors. In the case of cryptographic protocols of the scalar multiplication using fixed base point, however, the exceptional procedure attack is not applicable. First, we present novel efficient scalar multiplication using theta divisors, which is the positive application of theta divisors on HECC. Second, we develop a window-based method using theta divisors that is secure against side-channel attacks. It is not obvious how to construct a base point D such that all pre-computed points are theta divisors. We present an explicit algorithm for generating such divisors.

This paper presents new algorithms for the Tate pairing on a prime field. Recently, many pairing-based cryptographic schemes have been proposed. However, computing pairings incurs a high computational cost and represents the bottleneck to using pairings in actual protocols. This paper shows that the proposed algorithms reduce the cost of multiplication and inversion on an extension field, and reduce the number of calculations of the extended finite field. This paper also discusses the optimal algorithm to be used for each pairing parameter and shows that the total computational cost is reduced by 50% if k = 6 and 57% if k = 8.

Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r-2)(r+1)/2 and its average density of non-zero digit is asymptotically (r-1)/(2r-1). For r=3, the non-trivial digits are {2, 4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF--we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF.

Side channel attacks (SCA) are serious attacks on mobile devices. In SCA, the attacker can observe the side channel information while the device performs the cryptographic operations, and he/she can detect the secret stored in the device using such side channel information. Ha-Moon proposed a novel countermeasure against side channel attacks in elliptic curve cryptosystems (ECC). The countermeasure is based on the signed scalar multiplication with randomized concept, and does not pay the penalty of speed. Ha-Moon proved that the countermeasure is secure against side channel attack theoretically, and confirmed its immunity experimentally. Thus Ha-Moon's countermeasure seems to be very attractive. In this paper we propose a novel attack against Ha-Moon's countermeasure, and show that the countermeasure is vulnerable to the proposed attack. The proposed attack utilizes a Markov chain for detecting the secret. The attacker determines the transitions in the Markov chain using side channel information, then detects the relation between consecutive two bits of the secret key, instead of bits of the secret key as they are. The use of such relations drastically reduces the search space for the secret key, and the attacker can easily reveal the secret. In fact, around twenty observations of execution of the countermeasure are sufficient to detect the secret in the case of the standard sizes of ECC. Therefore, the single use of Ha-Moon's countermeasure is not recommended for cryptographic use.

Genus 3 hyperelliptic curve cryptosystems are capable of fast-encryption on a 64-bit CPU, because a 56-bit field is enough for their definition fields. Recently, Kuroki et al. proposed an extension of the Harley algorithm, which had been known as the fastest addition algorithm of divisor classes on genus 2 hyperelliptic curves, on genus 3 hyperelliptic curves and Pelzl et al. improved the algorithm. This paper shows an improvement of the Harley algorithm on genus 3 hyperelliptic curves using Toom's multiplication. The proposed algorithm takes only I + 70M for an addition and I + 71M for a doubling instead of I + 76M and I + 74M respectively, which are the best possible of the previous works, where I and M denote the required time for an inversion and a multiplication over the definition field respectively. This paper also shows 2 variations of the proposed algorithm in order to adapt the algorithm to various platforms. Moreover this paper discusses finite field arithmetic suitable for genus 3 hyperelliptic curve cryptosystems and shows implementation results of the proposed algorithms on a 64-bit CPU. The implementation results show a 160-bit scalar multiplication can be done within 172 µs on a 64-bit CPU Alpha EV68 1.25 GHz.

In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.