[Back to Results | New Search]

Student Number 92522085 Author Lee-Chun Ko(¬_¤O¸s) Author's Email Address brentko@giga.net.tw Statistics This thesis had been viewed 2018 times. Download 605 times. Department Computer Science and Information Engineering Year 2004 Semester 2 Degree Master Type of Document Master's Thesis Language English Title Physical Cryptanalysis of RSA Implementations Date of Defense 2005-05-12 Page Count 79 Keyword physical attack smart card Abstract 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.Table of Content 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 . . . . . . . . . . . . . . . . . 62Reference [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¡Pgecio¡Pglu 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.Advisor Sung-Ming Yen(ÃC·C»Ê)

Files approve in 1 year

92522085.pdf Date of Submission 2005-07-04

Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.