| dc.description.abstract | Modular exponentiation and its analogy, scalar multiplication, are the central computations in public-key cryptosystems. Because the memory capacity and computation power are crucial to smart cards, designing efficient exponentiation algorithms is an important issue for smart-card related applications. Since smart cards may suffer from side-channel analysis (SCA) attacks, which target the implementation of cryptosystems, the implementation security of cryptosystems using smart cards is an issue as important as designing an efficient algorithm. This dissertation investigates efficient and secure methods to implement exponentiation algorithms.
Because its property of having minimal Hamming weight among binary signed-digit representations, the binary non-adjacent form (NAF) is the optimal method to speed up scalar multiplications. Randomized NAF recoding is a typical SCA countermeasure. This dissertation newly introduces the separated non-adjacent form (sNAF) as a generalization of the conventional NAF. We show that both of sNAF and NAF have the same average Hamming weight, and can speed up exponentiation algorithms with a rate about 11.11% when compared with using the conventional binary recoded scalar. This dissertation also proposes the randomized sNAF recoding scheme to increase the security strength of scalar multiplications against SCA attacks. Compared with the randomized NAF recoding and several previous recoding schemes, the randomized sNAF recoding is a superior countermeasure from the viewpoint of security.
Doubling attack is a powerful SCA attack on exponentiation algorithms by exploiting two related chosen messages. This dissertation proposes the small-order doubling attack on the RSA cryptosystem by exploiting only one single chosen message of small order. This attack can be extended to the attack using two related chosen messages, which are different from the used by the original doubling attack. We show that an efficient RSA implementation improved by Chinese remainder theorem (CRT) is also weak against the proposed attacks. To prevent RSA against the proposed doubling attacks, a low-cost countermeasure is newly developed. Basically, the small-order doubling attacks can not threaten the elliptic curve cryptosystems (ECC), whereas a cryptographic elliptic curve is usually suggested with a prime order and small-order points do not exist on this kind of curves. However, this dissertation shows that existing invalid points having small orders on other curves can be used to mount a further extended doubling attack on the target curve of prime order. Several previous SCA countermeasures for ECC are shown to be vulnerable against the proposed doubling attack. To prevent ECC against the doubling attack using invalid points, efficient countermeasures are suggested in this dissertation.
Montgomery reduction algorithms are often taken to cooperate with RSA-CRT methods to achieve a high performance of RSA modular exponentiations. This dissertation proposes a new DPA attack on the RSA-CRT implementation with Montgomery reduction algorithms. An experimental result is illustrated to verify the proposed DPA attacks. In order to prevent against the proposed DPA attacks, an CRT-based message blinding technique is proposed as a low-cost countermeasure. | en_US |