由於網路的使用率增加，目前大多數的通訊傳遞皆經由電子通道傳送。一些隨著網路興起的應用，例如小額電子付費、線上購物和其他交易型的應用仰賴一種防篡改的設備 (例如智慧卡)。這些智慧卡嵌入了密碼的運算功能以致於提供高度的安全性，並且通常了包含了擁有者的身份資訊以及一些關於擁有者的秘密訊息。

自從公開金鑰密碼系統的發明以來，使多數位簽章方法相繼的被提出。在這些方法當中，RSA公開金鑰密碼系統是被認為最普遍方法由於其高度的安全性以及容易的實作。因此，藉由實作RSA或其他數位簽章方法到智慧卡內，這些智慧卡就能夠提供身份認證的功能。

自從Kocher提出了能量攻擊法來對抗智慧卡及其他密碼硬體設備的實作，許多密碼系統的設計者不只關心於密碼系統在數學上的安全性並且也關心於實作方面。相對於先前的主動式攻擊，例如錯誤攻擊法，能量攻擊法是一種被動式攻擊並且更容易實作。因此，許多的研究人員一直致力於發展一種安全並且有效率的防禦法來對抗能量攻擊法以及其他實體攻擊法。

在相關的文獻當中，有些防禦法仍然是具有爭議的並且無法對抗更進階的實體攻擊法。在本篇論文當中，我們將提出三種新的實體攻擊法來指出目前存在的一些防禦法並不安全。首先，藉由結合錯誤攻擊法以及簡單能量攻擊法，我們提出了一種攻擊於Montgomery的指數演算法，其原本是用來防禦簡單能量攻擊法以及一些錯誤攻擊法。第二，我們提出了一種更有力的能量攻擊法來攻擊一種以隨機編碼的方式來對抗差分能量攻擊法的防禦法。第三，我們擴展了目前一種存在的攻擊法來攻擊Montgomery的指數演算法。所提出的三種攻擊法皆以實際的實驗來證明攻擊法的可行性。

The recent communications are mostly through the electronic
channel due to the increasingly usage of the Internet. Some
applications such as micro-payment systems, on-line shopping, and
other transaction applications employ temper-proof devices such as
smart cards. These cards are embedded a cryptographic computation
function so as to providing highly security, and they usually
contain owner's identification and some secret information related
to the owner.

Since the introduction of the public-key cryptography, plenty of
digital signature schemes are then proposed. Among these schemes,
the RSA public-key cryptosystem is considered as the most popular
scheme due to its highly security and easily implementation.
Therefore, by deploying RSA or other signature schemes into smart
cards, these temper-proof devices can be used to providing
authentication and identification.

Since Kocher proposed the power analysis attacks against the
implementation of smart cards or other cryptographic hardware
devices, many of cryptosystem designers concern not only the
mathematic security of cryptography but also the implementation of
smart cards. Contrary to the previously active attack such as the
fault attack, power analysis attacks are passive attacks and more
easier to mount. Therefore, many researchers have focusing on
developing a secure and efficient countermeasure against power
analysis attacks and some other physical attacks.

In the related literatures, some of the countermeasures are still
controversial and insecure in advanced physical attacks. In this
thesis, we pointed out some of the existent countermeasures are
insecure by the proposed three new physical attacks. First of all,
by combining fault attack and simple power analysis, we proposed
an attack on Montgomery ladder which was originally proposed to
defeat simple power analysis and some fault-based attacks. Second,
we proposed a more powerful power analysis attack against a
countermeasure which was based on a randomized binary sign digit
representation to defeat differential power analysis. Third, we
extended the existent attack to develop a new type of attack
against Montgomery ladder. Three attacks are then confirmed either
by experimental result or by simulation result.

1 Introduction 1
1.1 Motivation of the Research . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Review of RSA Cryptosystem and Its Implementations 6
2.1 Brief Historical Review of Public-Key Cryptography . . . . . . . . . . 6
2.2 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Modular Exponentiation Algorithms . . . . . . . . . . . . . . . . . . 9
3 Review of Physical Cryptanalysis against RSA 12
3.1 Simple Power Analysis { SPA . . . . . . . . . . . . . . . . . . . . . . 12
3.1.1 Some countermeasures . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Di®erential Power Analysis { DPA . . . . . . . . . . . . . . . . . . . 15
3.2.1 Some countermeasures . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Fault Attack { FA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.1 CRT-based fault attack . . . . . . . . . . . . . . . . . . . . . . 20
3.3.2 Computational safe-error attack . . . . . . . . . . . . . . . . . 22
3.3.3 Memory safe-error attack . . . . . . . . . . . . . . . . . . . . . 22
3.3.4 Some countermeasures . . . . . . . . . . . . . . . . . . . . . . 23
4 Side-Channel Security of Montgomery Ladder Revisited 27
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Proposed Di®erential Simple Power Analysis { DSPA . . . . . . . . . 27
4.2.1 The ‾rst attack on Montgomery ladder . . . . . . . . . . . . . 28
4.2.2 The second attack on Montgomery ladder . . . . . . . . . . . 29
4.2.3 Extended attacks to other algorithms . . . . . . . . . . . . . . 30
4.3 Analysis of the DSPA . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.1 Feasibility of the proposed attack . . . . . . . . . . . . . . . . 31
4.3.2 Attack scenario analysis . . . . . . . . . . . . . . . . . . . . . 32
4.4 Experimental Result . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5 A More Powerful Attack against Ha-Moon's Countermeasure Based
on Randomized BSD 38
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Review of Ha-Moon's DPA Countermeasure . . . . . . . . . . . . . . 39
5.3 Proposed Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3.1 Attack model and notations . . . . . . . . . . . . . . . . . . . 40
5.3.2 Main idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.3 Description of the attack . . . . . . . . . . . . . . . . . . . . . 42
5.3.4 Key ‾nding step . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.5 Attacking algorithm . . . . . . . . . . . . . . . . . . . . . . . 44
5.4 Experimental Result and Example . . . . . . . . . . . . . . . . . . . . 44
5.4.1 Experimental result . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6 Di®erential Doubling Attack on Montgomery Ladder 51
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2 Fouque-Valette's Doubling Attack on SMA Algorithm . . . . . . . . . 52
6.2.1 Attack model . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.2.2 Description of the doubling attack . . . . . . . . . . . . . . . . 52
6.3 Proposed Di®erential Doubling Attack { DDA . . . . . . . . . . . . . 54
6.3.1 Description of the di®erential doubling attack . . . . . . . . . 54
6.3.2 Attacking algorithm . . . . . . . . . . . . . . . . . . . . . . . 56
6.4 Experimental Result . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7 Conclusions 61
7.1 Brief Review of Main Contributions . . . . . . . . . . . . . . . . . . . 61
7.2 Further Research Topics and Directions . . . . . . . . . . . . . . . . . 62

[1] C. AumÄuller, P. Bier, W. Fischer, P. Hofreiter, and J.-P. Seifert, Fault At-
tacks on RSA with CRT: Concrete Results and Practical Countermeasures,"
In Cryptographic Hardware and Embedded Systems { CHES '02, LNCS 2523,
pp. 260{275, Springer-Verlag, 2003.
[2] M. K. Ahn, J.C. Ha, H. J. Lee, and S. J. Moon, Random M-ary Method Based
Countermeasure against Side Channel Attacks," In International Conference on
Computational Science and Its Applications { ICCSA '03, LNCS 2668, pp. 338{
347, Springer-Verlag, 2003.
[3] T. Akishita and T. Takagi, ero-Value Point Attacks on Elliptic Curve Cryp-
tosystem," In Information Security Conference { ISC '03, LNCS 2851, pp. 218{
233, Springer-Verlag, 2003.
[4] E. Brier, C. Clavier, and F. Olivier, Correlation Power Analysis with a Leak-
age Model," In Cryptographic Hardware and Embedded Systems { CHES '04,
LNCS 3156, pp. 16{29, Springer-Verlag, 2004.
[5] D. Boneh, R. A. DeMillo, and R. J. Lipton, On the Importance of Check-
ing Cryptographic Protocols for Faults," In Advances in Cryptology { EURO-
CRYPT'97, LNCS 1233, pp. 37{51, Springer-Verlag, 1997.
[6] D. Boneh, R. A. DeMillo, and R. J. Lipton, On the Importance of Eliminating
Errors in Cryptographic Computations," In Journal of Cryptology, Vol. 14,
No. 2, pp. 101{119, Springer-Verlag, 2001.
[7] R. Bevan and E. Knudsen, Ways to Enhance Di®erential Power Analysis," In
International Conference on Information Security and Cryptology { ICISC '02,
LNCS 2587, pp. 327{342, Springer-Verlag, 2003.
[8] M. Bellare and P. Rogaway, Optimal Asymetric Encryption - How to Encrpt
with RSA," In Advances in Cryptology { EUROCRYPT'94, LNCS 950, pp. 92{
111, Springer-Verlag, 1994.
[9] E. Biham and A. Shamir, Di®erential Fault Analysis of Secret Key Cryptosys-
tems," In Advances in Cryptology { CRYPTO'97, LNCS 1294, pp. 513{525,
Springer-Verlag, 1997.
[10] C. Clavier, J.-S. Coron, and N. Dabbous, Di®erential Power Analysis in the
Presence of Hardware Countermeasures," In Cryptographic Hardware and Em-
bedded Systems { CHES '00, LNCS 1965, pp. 252{263, Springer-Verlag, 2000.
[11] B. Chevallier-Mames, M. Ciet, and M. Joye, Low-Cost Solutions for Preventing
Simple Side-Channel Analysis: Side-Channel Atomicity," In IEEE Transaction
on Computers, Vol. 53, No. 6, pp. 760{768, 2004.
[12] C. Clavier and M. Joye, Universal Exponentiation Algorithm: A First Step
towards Provable SPA-resistance," In Cryptographic Hardware and Embedded
Systems { CHES '01, LNCS 2162, pp. 300{308, Springer-Verlag, 2001.
[13] S. Chari, C. Jutla, J. R. Rao, and P. Rohatgi, A Cautionary Note Regarding
Evaluation of AES Candidates on Smart Cards," In Second Advanced Encryp-
tion Standard Candidate Conference, pp. 135{150, 1999.
[14] B. Chevallier-Mames, Self-Randomized Exponentiation Algorithms," In Cryp-
tographer's Track RSA Conference - CT-RSA '04, LNCS 2964, pp. 236{249,
Springer-Verlag, 2004.
[15] J.-S. Coron, Resistance against Di®erential Power Analysis for Elliptic
Curve Cryptosystems," In Cryptographic Hardware and Embedded Systems {
CHES '99, LNCS 1717, pp. 292{302, Springer-Verlag, 1999.
[16] National Bureau of Standards, Data Encryption Standard,"U.S. Department
of Commerce, FIPS Pub. 46, January 1997.
[17] W. Di±e and M. E. Hellman, Multiuser Cryptographic Techniques," In AFIPS
National Computer Conference, Vol. 45, pp. 109{112, 1976.
[18] W. Di±e and M. E. Hellman, New Directions in Cryptography," In IEEE
Transactions on Information Theory, Vol. 22, No. 6, pp. 644{654, 1976.
[19] J. F. Dhem, F. Koeune, P. A. Leroux, P. Mestre, J.-J. Quisquater, and J. L.
Willems, A Practical Implementation of the Timing Attack," In Smart Card
Research and Advanced Application Conference { CARDIS '98, LNCS 1820,
pp. 167{182, Springer-Verlag, 2000.
[20] ÄO E·gecio·glu and C. K. Koc, Exponentiation Using Canonical Recoding," In
Theoretical computer science, Vol. 129, pp. 407{417, 1994.
[21] T. ElGamal, A Public-Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms," In Advances in Cryptology { CRYPTO'84, LNCS 196,
pp. 10{18, Springer-Verlag, 1985.
[22] U. Feige, A. Fiat, and A. Shamir, ero Knowledge Proofs of Identity," In
Journal of Cryptology, Vol. 1, No. 2, pp. 77{94, 1988.
[23] P.-A. Fouque, G. Martinet, and G. Poupard, Attacking Unbalanced RSA-CRT
Using SPA," In Cryptographic Hardware and Embedded Systems - CHES '03,
LNCS 2779, pp. 254{268 , Springer-Verlag, 2003.
[24] P.-A. Fouque, F. Muller, G. Poupard, and F. Valette, Defeating Countermea-
sure Based on Randomized BSD Representations," In Cryptographic Hardware
and Embedded Systems - CHES '04, LNCS 3156, pp. 312{327, Springer-Verlag,
2004.
[25] P.-A. Fouque and F. Valette, The Doubling Attack - Why Upwards is Bet-
ter than Downwards," In Cryptographic Hardware and Embedded Systems -
CHES '03, LNCS 2779, pp. 269{280, Springer-Verlag, 2003.
[26] D. M. Gordon, A Survey of Fast Exponentiation Methods," In Journal of
Algorithms, Vol. 27, pp. 129{146, 1998.
[27] L. Goubin, A Re‾ned Power-Analysis Attack on Elliptic Curve Cryptosys-
tems," In Public Key Cryptography { PKC'03, LNCS 2567, pp. 199{210,
Springer-Verlag, 2003.
[28] G. Hachze, F. Koeune, and J.-J. Quisquater, Timing Attack: What can be
Achieved by a Powerful Adversary?," In 20th Symposium on Information The-
ory in the Benelux, pp. 63{70, 1999.
[29] J. C. Ha and S. J. Moon, Randomized Signed-Scalar Multiplication of ECC
to Resist Power Attacks," In Cryptographic Hardware and Embedded Systems
{ CHES '02, LNCS 2523, pp. 551{563, Springer-Verlag, 2003.
[30] D.-G. Han, K. Okeya, T. H. Kim, Y. S. Hwang, Y.-H. Park, and S. Jung,
Cryptanalysis of the Countermeasures Using Randomized Binary Signed Dig-
its," In Applied Cryptography and Network Security { ACNS '04, LNCS 3089,
pp. 398{413, Springer-Verlag, 2004.
[31] H. Handschuh, P. Paillier, and J. Stern, Probing Attacks on Temper-Resistant
Devices," In Cryptographic Hardware and Embedded Systems { CHES '99,
LNCS 1717, pp. 303{315, Springer-Verlag, 1999.
[32] K. Itoh, T. Izu, and M. Takennake Address-Bit Di®erential Power Analysis of
Cryptographic Schemes OK-ECDH and OK-ECDSA," In Cryptographic Hard-
ware and Embedded Systems { CHES '02, LNCS 2523, pp. 129{143, Springer-
Verlag, 2003.
[33] K. Itoh, T. Izu, and M. Takennake A Practical Countermeasure against
Address-Bit Di®erential Power Analysis," In Cryptographic Hardware and Em-
bedded Systems { CHES '03, LNCS 2779, pp. 382{396, Springer-Verlag, 2003.
[34] K. Itoh, J. Yajima, T. Takenaka, and N. Torii, DPA Countermeasure by Im-
proving the Window Method," In Cryptographic Hardware and Embedded Sys-
tems { CHES '02, LNCS 2523, pp. 303{317, Springer-Verlag, 2002.
[35] M. Joye, A. K. Lenstra, and J.-J. Quisquater, Chinese Remaindering Based
Cryptosystems in the Presence of Faults," In Journal of Cryptology, Vol. 12,
No. 4, pp. 241-245, 1999.
[36] M. Joye and S. M. Yen, The Montgomery Powering Ladder," In Crypto-
graphic Hardware and Embedded Systems { CHES '02, LNCS 2523, pp. 291{302,
Springer-Verlag, 2003.
[37] N. Koblitz, Elliptic Curve Cryptosystems," In Mathematics of Computation,
Vol. 48, pp. 203{209, 1987.
[38] P. Kocher, Timing Attacks on Implementations of Di±e-Hellman, RSA, DSS,
and Other Systems," In Advances in Cryptology { CRYPTO'96, LNCS 1109,
pp. 104{113, Springer-Verlag, 1996.
[39] P. Kocher, J. Ja®e, and B. Jun, Di®erential Power Analysis," In Advances in
Cryptology { CRYPTO'99, LNCS 1666, pp. 388{397, Springer-Verlag, 1999.
[40] F. Koeune and J.-J. Quisquater, A Timing Attack against Rijndael," In Tech-
nical Report CG-1999/1, Universit¶e catholique de Louvain, June 1999.
[41] D. E. Kunth, Seminumerical Algorithm," In The Art of Computer Program-
ming, Vol. 2, Addison-Wesley, 1981.
[42] A. K. Lenstra, Memo on RSA Signature Generation in the Presence of Faults,"
manuscript, Sept. 28, 1996.
[43] S. Moore, R. Anderson, P. Cunningham, R. Mullins, and G. Taylor, Improving
Smart Card Security using Self-timed Circuits," In IEEE International Sym-
posium on Asynchronous Circuits and Systems { ASYNC'02 , pp. 211{218,
2002.
[32] K. Itoh, T. Izu, and M. Takennake Address-Bit Di®erential Power Analysis of
Cryptographic Schemes OK-ECDH and OK-ECDSA," In Cryptographic Hard-
ware and Embedded Systems { CHES '02, LNCS 2523, pp. 129{143, Springer-
Verlag, 2003.
[33] K. Itoh, T. Izu, and M. Takennake A Practical Countermeasure against
Address-Bit Di®erential Power Analysis," In Cryptographic Hardware and Em-
bedded Systems { CHES '03, LNCS 2779, pp. 382{396, Springer-Verlag, 2003.
[34] K. Itoh, J. Yajima, T. Takenaka, and N. Torii, DPA Countermeasure by Im-
proving the Window Method," In Cryptographic Hardware and Embedded Sys-
tems { CHES '02, LNCS 2523, pp. 303{317, Springer-Verlag, 2002.
[35] M. Joye, A. K. Lenstra, and J.-J. Quisquater, Chinese Remaindering Based
Cryptosystems in the Presence of Faults," In Journal of Cryptology, Vol. 12,
No. 4, pp. 241-245, 1999.
[36] M. Joye and S. M. Yen, The Montgomery Powering Ladder," In Crypto-
graphic Hardware and Embedded Systems { CHES '02, LNCS 2523, pp. 291{302,
Springer-Verlag, 2003.
[37] N. Koblitz, Elliptic Curve Cryptosystems," In Mathematics of Computation,
Vol. 48, pp. 203{209, 1987.
[38] P. Kocher, Timing Attacks on Implementations of Di±e-Hellman, RSA, DSS,
and Other Systems," In Advances in Cryptology { CRYPTO'96, LNCS 1109,
pp. 104{113, Springer-Verlag, 1996.
[39] P. Kocher, J. Ja®e, and B. Jun, Di®erential Power Analysis," In Advances in
Cryptology { CRYPTO'99, LNCS 1666, pp. 388{397, Springer-Verlag, 1999.
[40] F. Koeune and J.-J. Quisquater, A Timing Attack against Rijndael," In Tech-
nical Report CG-1999/1, Universit¶e catholique de Louvain, June 1999.
[41] D. E. Kunth, Seminumerical Algorithm," In The Art of Computer Program-
ming, Vol. 2, Addison-Wesley, 1981.
[42] A. K. Lenstra, Memo on RSA Signature Generation in the Presence of Faults,"
manuscript, Sept. 28, 1996.
[43] S. Moore, R. Anderson, P. Cunningham, R. Mullins, and G. Taylor, Improving
Smart Card Security using Self-timed Circuits," In IEEE International Sym-
posium on Asynchronous Circuits and Systems { ASYNC'02 , pp. 211{218,
2002.
[44] S. Moore, R. Anderson, R. Mullins, G. Taylor, and J. Fournier, Balanced
Self-Checking Asynchronous Logic for Smart Card Application," In Journal of
Microprocessors and Microsystems, Vol. 27, No. 9, pp. 421{430, 2003.
[45] S. Mangard, A Simple Power-Analysis (SPA) Attack on Implementations of
the AES Key Expansion," In International Conference on Information Security
and Cryptology { ICISC '02, LNCS 2587, pp. 343{358, Springer-Verlag, 2003.
[46] R. Mayer-Sommer,Smartly Analyzing the Simplicity and the Power of Sim-
ple Power Analysis on Smartcards," In Cryptographic Hardware and Embedded
Systems { CHES '00, LNCS 1965, pp. 78{92, Springer-Verlag, 2000.
[47] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, Power Analysis Attacks of
Modular Exponentiation in Smartcards," In Cryptographic Hardware and Em-
bedded Systems { CHES '99, LNCS 1717, pp. 144{157, Springer-Verlag, 1999.
[48] T. S. Messerges, Using Second-Order Power Analysis to Attack DPA Resis-
tant Software," In Cryptographic Hardware and Embedded Systems { CHES '00,
LNCS 1965, pp. 238{251, Springer-Verlag, 2000.
[49] H. Mamiya, A. Miyaji, and H. Morimoto, E±cient Countermeasures against
RPA, DPA, and SPA," In Cryptographic Hardware and Embedded Systems {
CHES '04, LNCS 3156, pp. 343{356, Springer-Verlag, 2004.
[50] D. May, H. L. Muller, and N. P. Smart, Non-deterministic Processors," In
Australasian Conference on Information Security and Privacy { ACISP '01,
LNCS 2119, pp. 115{129, Springer-Verlag, 2001.
[51] D. May, H. L. Muller, and N. P. Smart, Random Register Renaming to
Foil DPA," In Cryptographic Hardware and Embedded Systems { CHES '01,
LNCS 2162, pp. 28{38, Springer-Verlag, 2001.
[52] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied
cryptography," CRC Press, 1997.
[53] R. Novak, Sign-Based Di®erential Power Analysis," In Workshop on Infor-
mation Security Applications { WISA '03, LNCS 2908, pp. 203{216, Springer-
Verlag, 2003.
[54] E. Oswald, Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryp-
tosystems," In Cryptographic Hardware and Embedded Systems { CHES '02,
LNCS 2523, pp. 82{97, Springer-Verlag, 2003.
[55] E. Oswald and K. Aigner, Randomized Addition-Subtraction Chain as a Coun-
termeasure against Power Attacks," In Cryptographic Hardware and Embedded
Systems { CHES '01, LNCS 2162, pp. 39{50, Springer-Verlag, 2001.
[56] K. Okeya and D.-G. Han, Side Channel Attack on Ha-Moon's Countermeasure
of Randomized Signed Scalar Multiplication," In International Conference on
Cryptology in India { INDOCRYPT'03, LNCS 2904, pp. 334{348, Springer-
Verlag, 2003.
[57] K. Okeya and K. Sakuria, On Insecurity of the Side Channel Attack Counter-
measure Using Addition-Subtraction Chains under Distinguishability between
Addition and Doubling," In Australasian Conference on Information Security
and Privacy { ACISP '02, LNCS 2384, pp. 420{435, Springer-Verlag, 2002.
[58] K. Okeya and K. Sakuria, A Second-Order DPA Attack Breaks a Window-
Method Based Countermeasure against Side Channel Attacks," In Information
Security Conference { ISC '02, LNCS 2433, pp. 389{401, Springer-Verlag, 2002.
[59] K. Okeya and K. Sakuria, A Multiple Power Analysis Breaks the Ad-
vanced Version of the Randomized Addition-Subtraction Chains Countermea-
sure against Side Channel Attacks," In IEEE Information Theory Workshop {
ITW'03, pp. 175{178, 2003.
[60] P. L. Montgomery, Speeding the Pollard and Elliptic Curve Methods of Fac-
torization," Mathematics of Computation, Vol. 48, pp. 243{264, 1987.
[61] J.-J. Quisquater and C. Couvreur, Fast Decipherment Algorithm for RSA
Public-key Cryptosystem," In Electronics Letters, Vol. 18, No. 21, pp. 905{907,
1982.
[62] M. O. Rabin, Digital Signatures and Public-Key Functions as Intractable as
Factorization," In MIT Laboratory for Computer Science, Technical Report,
MIT/LCS/TR-212, Jan 1979.
[63] G. W. Reitwiesner, Binary Arithmetic," In Advances in Computers, Vol. 1,
pp. 231{308, 1960.
[64] C. Rechberger and E. Oswald, Security of IEEE 802.11 Considering Power and
EM Side-Channel Information," In Computing, Communications and Control
Technologies { CCCT'04, Vol. 7, pp. 129{133, 2004.
[65] J. R. Rao, P. Rohatgi, H. Scherzer, and S. Tinguely, Partitioning Attacks: Or
How to Rapidly Clone Some GSM Cards," In IEEE Symposium on Security
and Privacy, pp. 31{44, 2002.
[66] R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital
Signatures and Public-key Cryptosystem," In Communication of ACM, Vol. 21,
No. 2, pp. 120{126, 1978.
[67] W. Schindler, A Timing Attack against RSA with the Chinese Remainder
Theorem," In Cryptographic Hardware and Embedded Systems { CHES '00,
LNCS 1965, pp. 109{124, Springer-Verlag, 2000.
[68] C. Schnorr, E±cient Signature Generation by Smart Cards," In Journal of
Cryptology, Vol. 4, No. 3, pp. 161{174, 1991.
[69] A. Shamir, Method and Apparatus for Protecting Public Key Schemes from
Timing and Fault Attacks," In United States Patent 5991415, November 23,
1999.
[70] S. G. Sim, D. J. Park, and P. J. Lee, New Power Analysis on the Ha-Moon
Algorithm and MIST Algorithm," In International Conference on Information
and Communications Security { ICICS '04, LNCS 3269, pp. 291{304, Springer-
Verlag, 2004.
[71] C. D. Walter, Sliding Windows Succumbs to Big Mac Attack," In Crypto-
graphic Hardware and Embedded Systems { CHES '01, LNCS 2162, pp. 286{299,
Springer-Verlag, 2001.
[72] C. D. Walter, MIST: An E±cint, Randomized Exponentiation Algorithm for
Resisting Power Analysis," In Cryptographer's Track RSA Conference { CT-
RSA '02, LNCS 2271, pp. 53{66, Springer-Verlag, 2002.
[73] C. D. Walter, Simple Power Analysis of Uni‾ed Code for ECC Double
and Add," In Cryptographic Hardware and Embedded Systems { CHES '04,
LNCS 3156, pp. 191{204, Springer-Verlag, 2004.
[74] J. Waddle and D. Wagner, Towards E±cient Second-Order Power Analysis,"
In Cryptographic Hardware and Embedded Systems { CHES '04, LNCS 3156,
pp. 1{15, Springer-Verlag, 2004.
[75] S. M. Yen and M. Joye, Checking before Output may not be Enough against
Fault-based Cryptanalysis," In IEEE Transaction on Computers, Vol. 49, No. 9,
pp. 967{970, 2000.
[76] S. M. Yen, S. J. Kim, S. G. Lim, and S. J. Moon, A Countermeasure against
One Physical Cryptanalysis may Bene‾t Another Attack," In International
Conference on Information Security and Cryptology { ICISC '01, LNCS 2288,
pp. 414{427, Springer-Verlag, 2002.
[77] S. M. Yen, S. J. Kim, S. G. Lim, and S. J. Moon, RSA Speedup with
Residue Number System Immune against Hardware Fault Cryptanalysis," In
International Conference on Information Security and Cryptology { ICISC '01,
LNCS 2288, pp. 397{413, Springer-Verlag, 2002.
[78] S. M. Yen, S. J. Kim, S. G. Lim, and S. J. Moon, RSA Speedup with Chinese
Remainder Theorem Immune against Hardware Fault Cryptanalysis," In IEEE
Transaction on Computers, Vol. 52, No. 4, pp. 461{472, 2003.
[79] S. M. Yen and C. S. Laih, Fast Algorithm for the LUC Digital Signature Com-
putation," In IEE proceedings: Computers and Digital Techniques, Vol. 142,
No. 2, pp. 165{169, 1995.
[80] S. M. Yen, S. J. Moon, and J. C. Ha, Hardware Fault Attack on RSA with CRT
Revisited," In International Conference on Information Security and Cryptol-
ogy { ICISC '02, LNCS 2587, pp. 374{388, Springer-Verlag, 2003.
[81] S. M. Yen, S. J. Moon, and J. C. Ha, Permanent Fault Attack on RSA
with CRT," In Australasian Conference on Information Security and Privacy
{ ACISP '03, LNCS 2727, pp. 285{296, Springer-Verlag, 2003.