Efficient Characteristic 3 Galois Field Operations for Elliptic Curve Cryptographic Applications
My research project was about developing more efficient polynomial arithmetic algorithms for Galois fields of characteristic 3. These mathematical groups are commonly used particularly for elliptic curve cryptography, and efficient polynomial arithmetic algorithms are crucial. Through my research, I was able to develop a new method for this arithmetic that was orders of magnitude faster than the best algorithms previously presented. Furthermore, I was able to show my method's applicability toward elliptic curve cryptography. In conclusion, my research presents a significantly improved algorithm for characteristic 3 Galois field arithmetic, and has the potential to make encryption significantly faster and safer.
Galois fields are a fundamental concept in abstract algebra and have a wide variety of applications in applied mathematics and computer science. Galois fields of characteristic 3, where the number of field elements is a power of 3, have a distinctive application in building high-security elliptic curve cryptosystems. However, they are not typically used because of their relative inefficiency in computing polynomial operations when compared to conventional prime or binary Galois fields. The purpose of this research was to design and implement characteristic 3 Galois field arithmetic algorithms with greater overall efficiency than those presented in current literature, and to evaluate their applicability to elliptic curve cryptography. The algorithms designed were tested in a C++ program and using a mapping of field element logarithms, were able to simplify the operations of polynomial multiplication, division, cubing, and modular reduction to that of basic integer operations. In exchange for the initial precomputation and storage costs, the algorithms designed significantly outperformed the best characteristic 3 algorithms presented in literature. Furthermore, they performed elliptic curve scalar multiplication with an efficiency comparable to prime Galois fields and showed a distinct applicability to elliptic curve cryptosystems with constrained environments or large-scale storage potential. In conclusion, this research presents a novel method of optimizing the performance of characteristic 3 Galois fields and has major implications for the field of elliptic curve cryptography.
Hello! My name is Vinay Iyengar and I am a Junior at the Oregon Episcopal School in Portland, Oregon. In free time, I love playing and listening to music and am an oboist in the Portland Youth Philharmonic. I also am a member of my school's Varsity tennis team and lead my school's Intercultural Student Association. I am extremely passionate about mathematics and cryptography, and the concept of using math to encrypt secret messages is both fascinating and inspiring to me. Dr. Neal Koblitz, the inventor of elliptic curve cryptography, Professor of Mathematics at the University of Washington and my mentor, is the biggest inspiration in my life. He has taught me to always be humble and to make learning my most important priority. In the future, I hope to attend a top-notch school and pursue a degree is either pure mathematics or applied math. Afterwards, I either want to pursue research as a career or go into industry, though I am undecided at this point. Winning the Google Science Fair would be a dream come true for me. It would help me pay for college tuition and allow me to attend a school I otherwise would be unable to attend. Most importantly, it would bring greater publicity to my research which I think is truly special and has the ability to make a difference in the world.
I had two goals I wanted to achieve in this research project.
1. To develop characteristic 3 Galois field arithmetic algorithms more efficient than the best algorithms previously presented in literature. I measured efficiency of my algorithms in terms of whether they computed the right answer, and the speed they were able to compute it within.
2. To evaluate the applicability of my methods towards elliptic curve cryptography.
Galois fields are one of the most important concepts in abstract algebra and have a wide variety of applications towards public-key encryption algorithms. In essence, a Galois field is an algebraic structure with established operations for addition, subtraction, multiplication, and division that satisfy the requirements for an Abelian group. This means that operations follow the five axioms of an Abelian group: closure, associativity, commutativity, having an identity element and an inverse element. Most importantly, Galois fields have a finite number of elements in them (Lidl & Niederreiter, 1997).
The most efficient and secure cryptographic system in use today is known as elliptic curve cryptography (ECC) and is based on the concept of elliptic curves built over Galois fields (Koblitz, 1987). This project in particular investigates elliptic curves built over Galois fields of characteristic 3. This essentially means that the number of elements in the field is a power of 3, allowing the Galois field to be notated as GF(3k), where k represents the degree of the field. In Galois fields of characteristic 3, elements of the field are represented as polynomials modulo a primitive polynomial p(x), where coefficients are either 0, 1, or 2 (Lidl & Niederreiter, 1994). This research looks into characteristic 3 Galois fields for elliptic curve cryptographic applications because after the research of Galbraith (2001), it is well accepted that characteristic 3 curves provide more security and bandwidth efficiency than conventional binary or prime curves. In addition, they are highly applicable towards building pairing-based cryptosystems, an attractive option for identity-based cryptographic algorithms (Boneh & Franklin, 2001). However, according to the canonical research of Harrison, Page, & Smart (2002), they are not efficient enough despite their potential. This is mainly because characteristic 3 polynomial arithmetic operations rely on base 3 arithmetic and are much slower compared to prime and binary Galois fields, which utilize the computer’s inherent hardware arithmetic.
Elliptic curves are a type of cubic equation of the form y2 = x3 + ax + b (Weierstrass form), where a and b represent coefficients. When elliptic curves are built over a Galois field, the points on the curve themselves form an Abelian group making it possible for operations to be done on points on the curve such as addition of two points, or the doubling of a point. Another form of elliptic curves that is popular is the Edwards equation of the form x2 + y2 = 1 + dx2y2, where d represents a coefficient. This research works primarily with the Edwards form of elliptic curves due to the lack of characteristic 3 Edwards research in the past. Another important operation on elliptic curves is scalar multiplication which refers to multiplying a Point P by an integer k, resulting in the Point P*k. Scalar multiplication not only dominates the execution time of ECC algorithms, but is also essential to the security of these systems.
Conventional characteristic 3 Galois field arithmetic algorithms. These were the algorithms to which the algorithms designed in this experiment were compared.
The key idea of this research was to map the polynomials to a simpler representation more conducive to efficient arithmetic. The algorithms designed were inspired by the concept of Zech’s logarithms presented in the work of Lidl & Neiderreiter, 1997. The algorithms designed include the following: logarithm table generation, polynomial multiplication, polynomial division, and polynomial cubing.
This research designed and developed a new and highly efficient way of doing characteristic 3 Galois field operations using a logarithm-table approach. Furthermore, this research explored and analyzed Edwards curves over characteristic 3 fields. Finally, scalar multiplication was implemented using binary, ternary, and balanced-ternary algorithms, and analyzed against state-of-the-art prime fields.
The logarithm table generation algorithm aims to create a table of field element logarithms, mapped from a power representation. This is done by repeatedly multiplying successive terms in the table by the value x, and then reducing these values modulo the primitive polynomial of the system. This algorithm also utilizes the concept of substitution reduction to simplify polynomial modular reduction. Substitution reduction basically substitutes, during the computation phase, an identity previously computed in the table, in order to simplify modular reduction. To better illustrate this concept, I have created a small example of logarithm table generation.
The main instrument used in this research was a Windows 7 computer with a 2.10 GHz Intel Core i3 processor installed with a Microsoft Visual Studio compiler. The main program was written in C++. An open source implementation for a Galois Field of characteristic 2 (Partow, 2006) was used as the starting point for the programming part of the research. The algorithms for the Galois Field of characteristic 3 were designed independently and then implemented into the program for testing.
This document provides detailed results of this project with graphs, tables, observations, as well as conclusions that can be drawn from the data. This sheet thus serves as sections 7 and 8.
My teacher and sponsor Peter Langley for all his help and encouragement. My mentor Dr. Neal Koblitz at the University of Washington for his guidance and support. Dr. Jiangtao Li of Intel Corporation for reviewing my research paper and supporting my research. My parents for their endearing support and belief.
- Ahmadi, O., Hankerson, D., & Menezes, A. (2007). Software implementation of arithmetic in. Arithmetic of Finite Fields, 85-102.
- Barreto, P., Kim, H., Lynn, B., & Scott, M. (2002). Efficient algorithms for pairing-based cryptosystems. Advances in Cryptology—CRYPTO 2002, 354-369.
- Bernstein, D., & Lange, T. (2007). Faster addition and doubling on elliptic curves. Advances in Cryptology, 13, 29-50. Retrieved from http://cr.yp.to/newelliptic/newelliptic-20070906.pdf
- Blake, I., Seroussi, G., & Smart, N. (1999). Elliptic curves in cryptography. (1st ed.). London: Cambridge University Press.
- Boneh, D., & Franklin, M. (2001). Identity-based encryption from the Weil pairing. In Advances in Cryptology—CRYPTO 2001 (pp. 213-229). Springer Berlin/Heidelberg.
- Das, A., & Madhavan, C. E. V. (2009). Public-key cryptography: theory and practice. (1st ed.). New Delhi: Dorling Kindersley.
- Galbraith, S. (2001). Supersingular curves in cryptography. Advances in Cryptology—ASIACRYPT 2001, 495-513.
- Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to elliptic curve cryptography. (1st ed.). Springer.
- Harrison, K., Page, D., & Smart, N. P. (2002). Software implementation of finite fields of characteristic three, for use in pairing-based cryptosystems.LMS Journal of Computation and Mathematics, 5(1), 181-193.
- Iyengar, V. S. (2012). Novel elliptic curve scalar multiplication algorithms for faster and safer public-key cryptosystems. International Journal on Cryptography and Information Security, 2(3), 57-66. doi: 10.5121/ijcis.2012.2305
- Koblitz, N. (1994). A course in number theory and cryptography. (2 ed.). New York, NY: Springer
- Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177). 203–209. Retrieved from http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf
- Lawson, N. (2009). Side-channel attacks. IEEE, 7(6), 65-68. Retrieved from http://rootlabs.com/articles/IEEE_SideChannelAttacks.pdf
- Lenstra, H. (1987). Factoring integers with elliptic curves. Annals of Mathematics, 126(6), Retrieved from http://www.jstor.org/pss/1971363
- Lidl, R. and Niederreiter, H. Introduction to Finite Fields and Their Applications, rev. ed. Cambridge, England: Cambridge University Press, 1994.
- Lidl, R. and Niederreiter, H. (Eds.). Finite Fields, 2nd ed. Cambridge, England: Cambridge University Press, 1997.
- Nation Security Agency, Certicom Corp. (n.d.). Recommended elliptic curve domain parameters. Retrieved from www.secg.org/collateral/sec2_final.pdf
- Partow, A. (2006) Galois Field Arithmetic Library (Version 5.0) [Computer Software] Available from: http://www.partow.net/projects/galois/#GFALLice nse
- Public-key cryptography. (n.d.). Retrieved from http://gdp.globus.org/gt4-tutorial/multiplehtml/ch09s03.html
- Silverman, J. H. (2006). A friendly introduction to number theory. (3rd ed., Vol. 3). Pearson Prentice Hall.
- Silverman, J. (2000). The arithmetic of elliptic curves. New York: Springer-Verlag. Retrieved from http://books.google.com/books?hl=en&lr=&id=Z90CA_EUCCkC&oi=fnd&pg=PR5&dq
- Smart, N. P., & Westwood, E. J. (2003). Point multiplication on ordinary elliptic curves over fields of characteristic three. Applicable Algebra In Engineering, Communication And Computing, 13(6), 485-497. doi: 10.1007/s00200-002-0114-0
- What is diffie-hellman (n.d.). RSA Labs: PKCS, 7, Retrieved from http://www.rsa.com/rsalabs/node.asp?id=2248
- (2012). Edwards Curve. Wikipedia, the free encyclopedia, Retrieved from http://en.wikipedia.org/wiki/File:Edward-curves.svg