臺灣博碩士論文加值系統

對於各種可攜式與資源受限設備，可能會需要借助密碼元件提供認證(Authentication)、完整性(Integrity)及機密性(Confidentiality)等功能。這些密碼元件(例如：RSA與ECC)常使用到模指數運算(Modular exponentiation)或純量乘法(Scalar multiplication)。實務上，若模指數運算與純量乘法未受保護，將可能遭受旁道攻擊法(Side-channel analysis, SCA)的威脅。旁道攻擊法包含了簡易能量攻擊法(Simple power analysis, SPA)與差分能量攻擊法(Differential power analysis, DPA)。設計一能抵擋旁道攻擊法之乘法演算法須兼顧效能與安全性間的平衡，極具挑戰性。本文發現到雖然文獻中有各種可抵擋簡易能量攻擊法之作法，然而該些方法中大多效能不佳且無法通用。為此，本文首先基於非對稱性策略，針對類DSA系統提出效率良好且可抵擋簡易能量攻擊法之模指數運算演算法。為了進一步提供更適用的乘法演算法，本文發展出旁道原子區塊技術之一般性架構，可保護幾乎所有的編碼系統。此一般性架構兼具安全性、通用性，且擁有最佳平均效能。此外，為抵擋因條件分支(Conditional branch)所造成之SN序列攻擊法(SN-sequence attack)，本文亦提供解決方法以避免此攻擊法及其變型之威脅。此解決法容易整合至乘法演算法中，且大多數情況下複雜度負擔低。藉由採用本文提出之多項技術，一可抵擋多種旁道攻擊法且具良好效能之乘法演算法架構將可建置完成。

For portable and resource-constrained devices, we may demand cryptographic primitives to provide functionality like authentication, integrity and secrecy. These cryptographic primitives (e.g., RSA and ECC) require basic operations such as modular exponentiation or point (scalar) multiplication. In practice, if modular exponentiation and point (scalar) multiplication are not protected with specific methods, they may be vulnerable to side-channel analysis (SCA), which typically includes simple power analysis (SPA) and differential power analysis (DPA). Designing a SCA-resistant multiplication algorithm requires balancing speed and security through challenging designs. We found though many SPA-resistant scalar multiplication algorithms have been proposed, most are inefficient and not interoperable with other recoding methods. Based on the concept of asynchronous strategy, we propose an efficient method to compute modular exponentiations against SPA for DSA-like schemes. To provide better multiplication algorithm, we develop a general framework based on the side-channel atomicity techniques to protect nearly all fast recoding methods/number systems. Our framework supplies security and flexibility, and has best average performance among previous works. Moreover, we give solutions to address the effects caused by conditional branches to prevent from the SN-sequence attack and its variants. Our solutions are easily incorporated to achieve more security resilience and incur low overhead in most cases. Using the proposed techniques, a comprehensive countermeasure against numerous SCAs can be accomplished while possessing competitive efficiency.

1. Introduction 1
1.1. Background and Motivations 1
1.2. Synopsis of the Dissertation 6
2. Background 9
2.1. Primitives and Operations for Public Key Cryptosystems 9
2.1.1. Modular Exponentiation 9
2.1.2. Elliptic Curve Cryptography 10
2.1.2.1.Arithmetic on Elliptic Curves 11
2.1.2.2.Scalar (Point) Multiplication 13
2.2. Side Channel Attacks and Countermeasures 15
2.2.1. Simple Power Analysis (SPA) 15
2.2.2. Countermeasures against SPA 17
2.2.3. Differential Power Analysis (DPA) 18
2.2.4. Countermeasures against DPA 18
3. Efficient Modular Exponentiation Resistant to SPA in DSA-like systems 21
3.1. Attacks and Countermeasures on DSA 22
3.2. SPA-resistance of DSA Based on Asynchronous Multi-computation 23
3.3. Security and Performance Analysis 26
4.A General Framework of Side-Channel Atomicity for Elliptic Curve Scalar Multiplication 35
4.1. Review of Side-channel Atomicity for Elliptic Curves over GF(p) 35
4.2. (tau-scalar, xi-base) Representation 37
4.3. General Framework of Side-channel Atomicity 41
4.4. Theoretical Performance Analysis 50
4.5. Implementation Results 54
5. Recoding Algorithm Protection Strategies against SN-Sequence Attack 59
5.1. SN-sequence Attack 60
5.2. Countermeasures for defending against SN-sequence Attack 62
5.2.1. Our Strategies 62
5.2.2. Examples of Applying Our Strategies 66
5.3. Implementation Results 67
6. Conclusions 71
References 73
Biography 79

[1]FIPS 140-3, “Security Requirements for Cryptographic Modules, which is available at http://csrc.nist.gov/publications/drafts/fips140-3/revised-draft-fips140-3_PDF-zip_document-annexA-to-annexG.zip/, 2011.
[2]MIRACL (Multiprecision Integer and Rational Arithmetic C/C++ Library), which is available at http://www.shamus.ie/, 2011.
[3]NSA Suite B Cryptography, which is available at http://www.nsa.gov/ia/programs/suiteb
_cryptography/index.shtml, 2011.
[4]P1363: Standard Specifications for Public Key Cryptography. IEEE, 2000.
[5]SEC 2, “Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography Group, Sep. 2000. Available at http://www.secg.org/, 2011.
[6]Arno, S. and Wheeler, F. S., “Signed Digit Representations of Minimal Hamming Weight, IEEE Trans. on Computers, Vol. 42, No. 8, pp. 1007-1010, Aug. 1993.
[7]Bernstein, D. J., Birkner, P., Lange, T. and Peters, C., “Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication, Progress in Cryptology, Proc. 8th Int’l Conf. on Cryptology in India (INDOCRYPT ’07), pp. 167-182, 2007.
[8]Boneh, D., DeMillo, R. A. and Lipton, R. J., “On the Importance of Checking Cryptographic Protocols for Faults, Advances in Cryptology — EUROCRYPT ’97, LNCS 1233, pp. 37-51, 1997.
[9]Brier, E. and Joye, M., “Weierstras Elliptic Curves and Side-Channel Attacks, Proc. 5th Int’l Workshop Practice and Theory in Public Key Cryptography (PKC ‘02), Vol. 2274 of LNCS, pp. 335-345, 2002.
[10]Billet, O. and Joye, M., “The Jacobi Model of an Elliptic Curve and Side-Channel Analysis, Proc. 15th Int’l Symp. on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC ‘03), pp. 34-42, 2003.
[11]Bernstein, D. J. and Lange, T., “Faster Addition and Doubling on Elliptic Curves, Advances in Cryptology — ASIACRYPT ‘07, Vol. 4833, pp. 29-50, 2007.
[12]Bernstein, D. J. and Lange, T., “Inverted Edwards Coordinates, Proc. 17th Int’l Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC ’07), Vol. 4851, pp. 20-27, 2007. http://cr.yp.to/newelliptic/.
[13]Barbosa, M. and Page, D., “On the Automatic Construction of Indistinguishable Operations, Cryptology ePrint Archive, Report 2005/174, 2005.
[14]Coron, J. S., “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, Proc. 1th Int’l Workshop Cryptographic Hardware and Embedded Systems (CHES ‘99), Vol. 1717, pp. 292-302, 1999.
[15]Chevallier-Mames, B., Ciet, M. and Joye, M., “Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity, IEEE Trans. on Computers, Vol. 53, No. 6, pp. 760-768, June 2004.
[16]Cohen, H., Miyaji, A. and Ono, T., “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, Advances in Cryptology — ASIACRYPT ’98, pp. 51-65, 1998.
[17]Ciet, M. and Joye, M., “(Virtually) Free Randomization Techniques for Elliptic Curve Cryptography, Proc. Information and Communications Security (ICICS ‘03), LNCS 2836, pp. 348-359, Springer-Verlag, 2003.
[18]Dimitrov, V., Imbert, L. and Mishra, P. K., “Efficient and Secure Elliptic Curve Point Multiplication using Double-Base Chains, Advances in Cryptology — ASIACRYPT ’05, Vol. 3788, pp. 59-78, 2005.
[19]Doche, C., Kohel, D. R. and Sica, F., “Double-Base Number System for Multi-Scalar Multiplications, Advances in Cryptology — EUROCRYPT ’09, pp. 502-517, 2009.
[20]ElGamal, T., “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. on Information Theory, Vol. 31, No. 4, pp. 469-472, July 1985.
[21]Gordon, D. M., “A Survey of Fast Exponentiation Methods, J. Algorithms, Vol. 27, pp. 129-146, 1998.
[22]Giraud, C., “An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis, IEEE Trans. on Computers, Vol. 55, No. 9, pp. 1116-1120, Sep. 2006.
[23]Galbraith, S. D., Lin, X. and Scott, M., “Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves, Advances in Cryptology — EUROCRYPT ’09, pp. 518-535, 2009.
[24]Giraud, C. and Verneuil, V., “Atomicity Improvement for Elliptic Curve Scalar Multiplication, The 9th Smart Card Research and Advanced Application IFIP Conf. (CARDIS ‘10), Vol. 6035 of LNCS, pp. 80-101, 2010.
[25]Hankerson, D., Karabina, K. and Menezes, A., “Analyzing the Galbraith-Lin-Scott Point Multiplication Method for Elliptic Curves over Binary Fields, IEEE Trans. On Computers, Vol. 58, No. 10, pp. 1411-1420, Oct. 2009.
[26]Joye, M., “Fault Attacks an Algorithmic Perspective, 2007 Information Security Summer School (ISSS 2007) on Cryptographic Hardware, Side-channel and Fault Attacks, 2007.
[27]Joye, M., “Highly Regular m-Ary Powering Ladders, Selected Areas in Cryptography (SAC ‘09), Vol. 5867 of LNCS, pp. 350-363, 2009.
[28]Joye, M. and Olivier, F., “Side-Channel Analysis, Encyclopedia of Cryptography and Security, pp. 571-576, Kluwer Academic Publishers, 2005.
[29]Joye, M. and Tymen, C., “Protections against Differential Analysis for Elliptic Curve Cryptography: An Algebraic Approach, Proc. 3th Int’l Workshop Cryptographic Hardware and Embedded Systems (CHES ‘01), Vol. 2162, pp. 377-390, 2001.
[30]Joye, M. and Tunstall, M., “Exponent Recoding and Regular Exponentiation Algorithms, Advances in Cryptology — AFRICACRYPT ’09, Vol. 5580 of LNCS, pp. 334-349, 2009.
[31]Joye, M. and Yen, S. M., “Optimal Left-to-Right Binary Signed-Digit Recoding, IEEE Trans. on Computers, Vol. 49, No. 7, pp. 740-748, July 2000.
[32]Joye, M. and Yen, S. M., “The Montgomery Powering Ladder, Proc. 4th Int’l Workshop Cryptographic Hardware and Embedded Systems (CHES ’02), pp. 291-302, 2002.
[33]Koc, C. K., “High-speed RSA Implementations, Tech. Rep. TR 201, RSA Laboratories, Nov. 1994.
[34]Kocher, P. C., “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Advances in Cryptology — CRYPTO ’96, pp. 104-113, 1996.
[35]Kocher, P. C., Jaffe, J. and Jun, B., “Differential Power Analysis, Advances in Cryptology — CRYPTO ’99, Vol. 1666, pp. 388-397, 1999.
[36]Kocher, P. C., Jaffe, J. and Jun, B., “Introduction to Differential Power Analysis and Related Attacks, Cryptography Research, 1998.
[37]Lee, M. K., “SPA-Resistant Simultaneous Scalar Multiplication, Proc. Int’l Conf. on Computational Science and Its Applications (ICCSA ‘05), LNCS, Vol. 3481, pp. 314-321, 2005.
[38]Longa, P., “Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields, Ph. D. dissertation, School of Information Technology and Engineering, Ottawa Univ., 2007.
[39]Longa, P. and Miri, A., “Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields, IEEE Trans. on Computers, Vol. 57, No. 3, pp. 289-302, Sept. 2008.
[40]Liu, D., Tan, Z. and Dai, Y., “New Elliptic Curve Multi-scalar Multiplication Algorithm for a Pair of Integers to Resist SPA, Proc. 4th China Int’l Conf. on Information Security and Cryptology (INSCRYPT ’08), LNCS 5487, pp. 253-264, 2009.
[41]Messerges, T. S., Dabbish, E. A. and Sloan, R. H., “Examining Smart-card Security Under the Threat of Power Analysis Attacks, IEEE Trans. on Computers, Vol. 51, No. 5, pp. 541-552, May 2002.
[42]Okeya, K., Schmidt-Samoa, K., Spahn, C. and Takagi, T., “Signed Binary Representations Revisit, Advances in Cryptology — CRYPTO ’04, pp. 123-139, 2004.
[43]Okeya, K. and Takagi, T., “The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks, Proc. The Cryptographers' Track (CT-RSA ’03), Vol. 2612 of LNCS, pp.328-342, Apr. 2003.
[44]Ruan, X. and Katti, R. S., “Left-to-Right Optimal Signed-Binary Representation of a Pair of Integers, IEEE Trans. on Computers, Vol. 54, No. 2, pp. 124-131, Feb. 2005.
[45]Solinas, J. A., “Efficient Arithmetic on Koblitz Curves, J. Design, Codes and Cryptography, pp. 195-249, 2000.
[46]Solinas, J. A., “Low-Weight Binary Representation for Pairs of Integers, Technical Report CORR 2001-41, Waterloo Univ., 2001.
[47]Sakai, Y., Sakurai, K., “A New Attack with Side Channel Leakage during Exponent Recoding Computations, Proc. 6th Int’l Workshop Cryptographic Hardware and Embedded Systems (CHES ’04), LNCS, Vol. 3156, pp. 298-311, Springer-Verlag, 2004.
[48]Yang, W. C., Guan, D. J. and Laih, C. S., “Fast Multicomputations with Integer Similarity Strategy, Proc. 8th Int’l Workshop Practice and Theory in Public Key Cryptography (PKC ‘05), LNCS 3386, pp. 139-153, Jan. 2005.
[49]Yang, W. C., Guan, D. J. and Laih, C. S., “Fast Multicomputation with Asynchronous Strategy, IEEE Trans. on Computers, Vol. 56, No. 2, pp. 234-242, Feb. 2007.
[50]Yang, W. C., Hseih, P. Y. and Laih, C. S., “Efficient Squaring of Large Integers, IEICE Trans. on Fundamentals, Vol. E87-A, No. 5, May 2004.
[51]Yen, S. M. and Joye, M., “Checking before Output May Not Be Enough against Fault-Based Cryptanalysis, IEEE Trans. on Computers, Vol. 49, No. 9, pp. 967-970, June 2000.
[52]Zheng, Y. and Matsumoto, T., “Breaking Smart Card Implementations of ElGamal Signature and Its Variants, Presented at the rump session of ASIACRYPT ’96, which is available at http://www.sis.uncc.edu/~yzheng/publications/files/a96-rump-hw-fault.pdf, 2011.