近年來研究指出密碼系統可經由實作攻擊法(Side Channel Attack, SCA)而被破解，尤以可攜式裝置(Wearable Device)等資源有限之設備愈為容易遭受該攻擊。這類設備上的密碼系統往往也需兼顧運算效率與記憶體使用率，所以通常會採用橢圓曲線系統。其中Okeya及Takagi提出的方法可用來抵擋能量消耗攻擊(Simple Power Attack)，然而該方法需要大小為n．2^(w-1)的記憶體空間，而本文提出的方法僅需大小為n．2^(w-2)的記憶體空間，n代表金鑰長度，w代表編碼時的視窗大小(Window Size)。同時，隨著w的不同，本文提出的方法在大多數情況下皆能以一半的記憶體空間達到優於前者的運算效率。本文設計的概念在於利用微型區塊(Atomic Block)來抵擋能量消耗攻擊(Simple Power Attack, SPA)，同時採用了wNAF編碼來提升運算效率。

In recent years, it is discovered that cryptosystems suffer from so-called side channel attacks (SCAs). When implementing cryptosystems in resources-limited portable devices, the situation becomes more severe. We usually need to carefully consider both the computation efficiency and memory requirement for these portable devices. Therefore, one of the ways to accomplish these demands is to use elliptic curve cryptosystems. In previous works, Okeya and Takagi try to defend against simple power attack by modifying the wNAF recoding method. Their method, however, sacrifices memory space to satisfy the resistance. The memory space of n．2^(w-1) is required. Our scheme reduce the memory space used in scalar multiplication and only needs memory space of n．2^(w-2), where n is the key length and w is the window size. The conception of our scheme is to use the atomic blocks to resist simple power attack and adopt the wNAF recoding method to improve the computation efficiency.

[1] ANSI X9.62-1998, “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” American Bankers Association, 1999.
[2] S. Atay, A. Koltuksuz, H. Hışıl, Ş. Eren, “Computational Cost Analysis of Elliptic Curve Arithmetic,” IEEE International Conference on Hybrid Information Technology (ICHIT'06), 2006.
[3] A.O. Atkin and F. Morain, “Building Cyclic Elliptic Curves Modulo Large Primes,” Advances in Cryptology-Eurocypto’91, LNCS 547, Springer-Verlag, pp. 328-336, 1991.
[4] O. Acıiçmez, J.-P. Seifert, and Ç.K. Koç, "Micro-Architectural Cryptanalysis," IEEE Trans. Security and Privacy, Vol. 5, No. 4, pp. 62-64, July-Aug. 2007.
[5] S. Arno and F.S. Wheeler, “Signed Digit Representations of Minimal Hamming Weight,” IEEE Trans. Computers, Vol. 42, No. 8, pp. 1007-1010, Aug. 1993.
[6] D. Boneh and D. Brumley, “Remote Timing Attacks are Practical,” In proceedings of the 12th Usenix Security Symposium, 2003.
[7] D. Boneh, R.A. DeMillo, and R.J. Lipton, “On the Importance of Checking Cryptographic Protocols for Faults,” Proc. Conf. Advances in Cryptology—EUROCRYPT ’97, LNCS 1233, pp. 37-51, 1997.
[8] Certicom Corporation, URL: http://www.certicom.com.
[9] J. Coron, “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystem,” CHES’99, Lecture Notes in Computer Science, Vol. 1717, pp.292-302, 1999.
[10] B. Chevallier-Mames, M. Ciet, and M. Joye, “Low-Cost Solutions for Preventing Simple Side-Channel Analysis：Side-Channel Atomicity,” IEEE Trans. Computers, Vol. 53, No. 6, pp. 760-768, June 2004.
[11] Y.-J. Choi, M.-S. Kim, H.-R. Lee and H.-W. Kim, "Implementation and Analysis of Elliptic Curve Cryptosystems over Polynomial basis and ONB," Proceedings of World Academy of Science, Engineering and Technology, Vol. 10, Dev. 2005.
[12] H. Cohen, A. Miyaji and T. Ono, “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates,” Advance in Cryptology-ASIACRYPT’98, LNCS 1514, Springer-Verlag, pp. 51-65, 1997.
[13] W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Trans. On Information Theory, Vol. IT-22, pp. 638-654, Nov. 1976.
[14] T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Trans. Information Theory, Vol. 31, No. 4, pp. 469-472, July 1985.
[15] FIPS 186-2, “Digital Signature Standard,” Federal Information Processing Standards Publication 180-2, 2000. Available from: http://csrc.nist.gov/
[16] D.M. Gordon, “A Survey of Fast Exponentiation Methods,” J. Algorithms, Vol. 27, pp. 129-146, 1998.
[17] C. Giraud, “An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis,” IEEE Trans. Computers, Vol. 55, No. 9, pp. 1116-1120, Sep. 2006.
[18] P. Gaudry, F. Hess, N.P. Smart, “Constructive and Destructive Facts of Weil Descent on Elliptic Curves,” Hewlett Packard Laboratories Technical Report, 2000.
[19] S.D. Galbraith and N.P. Smart, “A Cryptographic Application of the Weil Descent,” Cryptography and Coding, pp. 191-200, 1999.
[20] IEEE P1363, “Standard Specifications for Public-Key Cryptography,” IEEE Working Group, Nov. 1999.
[21] IEEE P1363A, “Standard Specifications for Public-Key Cryptography: Additional Techniques,” IEEE Working Group, May. 2000.
[22] ISO/IEC 14888-3, Information Technology – Security Techniques – Digital Signature with Appendix – Part 3: Certificate-based Mechanisms.
[23] ISO/IEC 15946 series, Information Technology – Security Techniques – Cryptographic Techniques Based on Elliptic Curves, 1998.
[24] ISO/IEC 9796-4 Information Technology – Security Techniques – Digital Signature with Message Recovery – Part 4: Discrete Logarithm-based Mechanisms.
[25] M. Joye, “Fault Attacks An Algorithmic Perspective,” Summer school on cryptographic hardwar, side-channel and fault attacks, June 2006. http://www.dice.ucl.ac.be/crypto/sumschool-slides.htm.
[26] A. Jursic and A. Menezes, “Elliptic Curves and Cryptography” Dr. Dobb’s Journal, Apr. 1997.
[27] M. Joye and F. Olivier, “Side-Channel Analysis,” In H. van Tilborg, Ed., Encyclopedia of Cryptography and Security, pp. 571-576, Kluwer Academic Publishers, 2005.
[28] M. Joye and S.M. Yen, “Optimal Left-to-Right Binary Signed-Digit Recoding,” IEEE Trans. Computers, Vol. 49, No. 7, pp. 740-748, July 2000.
[29] N. Koblitz, “Elliptic Curve Cryptosystems,” Math. Computat., Vol. 48, pp. 203-209, 1987.
[30] Ç.K. Koç, “High-Speed RSA Implementations,” Tech. Rep. TR 201, RSA Laboratories, Nov. 1994.
[31] P.C. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” Proc. Conf. Advances in Cryptology—CRYPTO ’96, Vol. 1109, pp. 104-113, 1996.
[32] Ç.K. Koç and T. Acar, “Fast Software Exponentiation in GF(2k),” 13th IEEE Symposium on Computer Arithmetic (ARITH-13, ‘97’), pp. 225, 1997.
[33] P.C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis,” Proc. Conf. Advances in Cryptology—CRYPTO ’99, Vol. 1666, pp. 388-397, 1999.
[34] C.S. Laih, F.K. Tu and Y.C. Lee, “On the Implementation of Public Key Cryptosystems Against Fault-Based Attacks,” IEICE Transactions on Fundamentals of Electronic Communications and Computer Science, Vol. E82-A, No.6, pp. 1082-1089, June 1999.
[35] P.L. Montgomery, “Modular Multiplication without Trial Division,” Mathematics of Computations, Vol. 44, pp. 519-512, Apr. 1985.
[36] V.S. Miller, “Use of Elliptic Curves in Cryptography,” Advances in Cryptology-Crypto’85, LNCS 218, Springer-Verlag, pp. 417-426, 1986.
[37] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve Methods for Factorization," Mathematics of Computation, Vol. 48, pp. 243-264, 1987.
[38] A. Menezes, “Elliptic Curve Public Key Cryptosystems,” Kluwer Academic Publishers, Boston, 1993.
[39] T.S. Messerges, E.A. Dabbish, and R.H. Sloan, “Examining Smart-Card Security under the Threat of Power Analysis Attacks,” IEEE Trans. on Computers, Vol. 51, No. 5, pp. 541-552, May 2002.
[40] A.J. Menezes, T. Okamoto, and S.A. Vanstone, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field,” IEEE Trans. On Information Theory, Vol. 39, No. 5, pp. 1639-1646, Sep. 1993.
[41] NIST, “Digital Signature Standard,” U.S. Department of Commerce, Aug. 1991.
[42] K. Okeya, K. Schmidt-Samoa, C. Spahn, T. Takagi, “Signed Binary Representations Revisit,” Proceedings of CRYPTO'04, pp. 123-139, 2004.
[43] K. Okeya and T. Takagi, “The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks,” Proc. CT-RSA'03, Vol. 2612 of LNCS, pp.328–342, April 2003.
[44] X. Ruan and R.S. Katti, “Left-to-Right Optimal Signed-Binary Representation of a Pair of Integers,” IEEE Trans. Computers, Vol. 54, No. 2, pp. 124-131, Feb. 2005.
[45] R. Rivest, A. Shamir and L.M. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems,” Communications of the ACM, Vol. 21, pp. 120-126, 1978.
[46] J.A. Solinas, "Efficient Arithmetic on Koblitz Curves," Design, Codes and Cryptography, pp. 195-249, 2000.
[47] SEC 1. Elliptic Curve Cryptography. Standards for Efficient Cryptography Group, Sep. 2000. Available from: http://www.secg.org/
[48] SEC 2. Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography Group, Sep. 2000. Available from: http://www.secg.org/
[49] E.D. Win, S. Mister, B. Preneel and M. Wiener, "On the Performance of Signature Schemes based on Elliptic Curves," Lecture Notes in Computer Science, 1998.
[50] W.C. Yang, D.J. Guan, and C.S. Laih, “Fast Multi-Computations with Integer Similarity Strategy,” Proc. Int’l Workshop Practice and Theory in Public Key Cryptography (PKC ‘05), LNCS 3386, pp. 139-153, Jan. 2005.
[51] W.C. Yang, D.J. Guan, and C.S. Laih, “Fast Multicomputation with Asynchronous Strategy,” IEEE Trans. Computers, Vol. 56, No. 2, Feb. 2007.
[52] W.C. Yang, P.Y. Hseih, and C.S. Laih, “Efficient Squaring of Large Integers,” IEICE Trans. Fundamentals, Vol. E87-A, No. 5, May 2004.
[53] S.M. Yen and M. Joye, “Checking before Output May Not Be Enough against Fault-Based Cryptanalysis,” IEEE Trans. Computers, Vol. 49, No. 9, pp. 967-970, June 2000.
[54] Y. Zheng and T. Matsumoto, “Breaking Smart Card Implementations of ElGamal Signature and Its Variants,” Presented at the rump session of Asiacrypt '96, available at http://www.sis.uncc.edu/~yzheng/publications/files/a96-rump-hw-fa ult.pdf.