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.

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.

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 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.