A technique for computing the quotient (⌊ ab/n ⌋) of Euclidean divisions from the difference of two remainders (ab (mod n) - ab (mod n+1)) was proposed by Fischer and Seifert. The technique allows a 2-bit modular multiplication to work on most -bit modular multipliers. However, the cost of the quotient computation rises sharply when computing modular multiplications larger than 2 bits with a recursive approach. This paper addresses the computation cost and improves on previous 2-bit modular multiplication algorithms to return not only the remainder but also the quotient, resulting in an higher performance in the recursive approach, which becomes twice faster in the quadrupling case and four times faster in the octupling case. In addition to Euclidean multiplication, this paper proposes a new 2-bit Montgomery multiplication algorithm to return both of the remainder and the quotient.

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.

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.

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.

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.

We show that a randomized addition-sub-traction chains countermeasure against side channel attacks is vulnerable to an SPA attack, which is a kind of side channel attack, under distinguishability between addition and doubling. The side channel attack takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure was proposed by Oswald-Aigner, and is based on a random decision inserted into computations. However, the question of its immunity to side channel attacks is still controversial. The randomized addition-subtraction chains countermeasure has security flaw in timing attacks, another kind of side channel attack. We have implemented the proposed attack algorithm, whose input is a set of AD sequences, which consist of the characters "A" and "D" to indicate addition and doubling, respectively. Our program has clarified the effectiveness of the attack. The attack algorithm could actually detect secret scalars for given AD sequences. The average time to detect a 160-bit scalar was about 6 milliseconds, and only 30 AD sequences were enough to detect such a scalar. Compared with other countermeasures against side channel attacks, the randomized addition-subtraction chains countermeasure is much slower.

We present a novel approach for computing 2n-bit Montgomery multiplications with n-bit hardware Montgomery multipliers. Smartcards are usually equipped with such hardware Montgomery multipliers; however, due to progresses in factoring algorithms, the recommended bit length of public-key schemes such as RSA is steadily increasing, making the hardware quickly obsolete. Thanks to our double-size technique, one can re-use the existing hardware while keeping pace with the latest security requirements. Unlike the other double-size techniques which rely on classical n-bit modular multipliers, our idea is tailored to take advantage of n-bit Montgomery multipliers. Thus, our technique increases the perenniality of existing products without compromises in terms of security.

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.

HMAC is one of the most famous keyed hash functions, and widely utilized. In order to design secure hash functions, we often use PGV construction consisting of 64 schemes, each of which utilizes a block cipher. If the underlying block cipher is ideal, 12 schemes are proven to be secure. In this paper, we evaluate the security of these schemes in view of side channel attacks. As it turns out, HMACs based on 11 out of 12 secure PGV schemes are vulnerable to side channel attacks, even if the underlying block cipher is secure against side channel attacks. These schemes are classified into two groups based on their vulnerabilities. For the first group which contains 8 schemes, we show that the attacker can reveal the whole key of HMAC, and selectively forge in consequence. For the other group which contains 3 schemes, we specify the importance of the execution sequence for the inner operations of the scheme, and refine it. If wrong orders of operations are used, the attacker can reveal a portion of the key of HMAC. Hence, the use of HMACs based on such PGV schemes as they are is not recommended when the resistance against side channel attacks is necessary.

We develop efficient precomputation methods of multi-scalar multiplication on ECC. We should recall that multi-scalar multiplication is required in some elliptic curve cryptosystems including the signature verification of ECDSA signature scheme. One of the known fast computation methods of multi-scalar multiplication is a simultaneous method. A simultaneous method consists of two stages; precomputation stage and evaluation stage. Precomputation stage computes points of precomputation, which are used at evaluation stage. Evaluation stage computes multi-scalar multiplication using precomputed points. In the evaluation stage of simultaneous methods, we can compute the multi-scalar multiplied point quickly because the number of additions is small. However, if we take a large window width, we have to compute an enormous number of points in precomputation stage. Hence, we have to compute an abundance of inversions, which have large computational amount. As a result, precomputation stage requires much time, as well known. Our proposed method reduces from O(22w) inversions to O(w) inversions for a window width w, using Montgomery trick. In addition, our proposed method computes uP and vQ first, then compute uP+vQ, where P,Q are elliptic points. This procedure enables us to remove unused points of precomputation. Compared with the method without Montgomery trick, our proposed method is 3.6 times faster in the case of the precomputation stage for simultaneous sliding window NAF method with window width w=3 and 160-bit scalars under the assumption that I/M=30, S/M=0.8, where I,M,S respectively denote computational amounts of inversion, multiplication and squaring on a finite field.

SFLASH was chosen as one of the final selection of the NESSIE project in 2003. It is one of the most efficient digital signature scheme and is suitable for implementation on memory-constrained devices such as smartcards. Side channel attacks (SCA) are a serious threat to memory-constrained devices. If the implementation on them is careless, the secret key may be revealed. In this paper, we experimentally analyze the effectiveness of a side channel attack on SFLASH. There are two different secret keys for SFLASH, namely the proper secret key (s,t) and the random seed Δ used for the hash function SHA-1. Whereas many papers discussed the security of (s,t), little is known about that of Δ. Steinwandt et al. proposed a theoretical DPA for finding Δ by observing the XOR operations. We propose another DPA on Δ using the addition operation modulo 232, and present an experimental result of the DPA. After obtaining the secret key Δ, the underlying problem of SFLASH can be reduced to the C* problem broken by Patarin. From our simulation, about 1408 pairs of messages and signatures are needed to break SFLASH. Consequently, SHA-1 must be carefully implemented in order to resist SCA on SFLASH.

This paper proposes novel algorithms for computing double-size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e=216+1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications.

We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve over any non-binary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods on the Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementation with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curve in constrained environments such as mobile devices and smart cards.

The side channel attack (SCA) is a serious attack on wearable devices that have scarce computational resources. Cryptographic algorithms on them should be efficient using small memory--we have to make efforts to optimize the trade-off between efficiency and memory. In this paper we present efficient SCA-resistant scalar multiplications based on window method. Moller proposed an SPA-resistant window method based on 2w-ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive and it requires 2w points of table (or 2w-1 + 1 points if the signed 2w-ary is used). The most efficient window method with small memory is the width-w NAF, which requires 2w-2 points of table. In this paper we convert the width-w NAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. |00x|00x||00x|, where x is positive odd points < 2w. Thus the size of the table is 2w-1, which is optimal in the construction of the SPA-resistant chain based on width-w NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Moller's scheme for w = 2,3,4,5, which are relevant choices in the sense of efficiency for 160-bit 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.