tailieunhanh - Efficient Software-Implementation of Finite Fields with Applications to Cryptography

In this work, we present a survey of efficient techniques for software implementation of finite field arithmetic especially suitable for cryptographic applications. | Acta Appl Math DOI S10440-006-9046-1 Efficient Software-Implementation of Finite Fields with Applications to Cryptography Jorge Guajardo Sandeep S. Kumar Christof Paar Jan Pelzl Springer Science Business Media . 2006 Abstract In this work we present a survey of efficient techniques for software implementation of finite field arithmetic especially suitable for cryptographic applications. We discuss different algorithms for three types of finite fields and their special versions popularly used in cryptography Binary fields prime fields and extension fields. Implementation details of the algorithms for field addition subtraction field multiplication field reduction and field inversion for each of these fields are discussed in detail. The efficiency of these different algorithms depends largely on the underlying micro-processor architecture. Therefore a careful choice of the appropriate set of algorithms has to be made for a software implementation depending on the performance requirements and available resources. Mathematics Subject Classifications 12-02 12E30 12E10 Key words field arithmetic cryptography efficient implementation binary field arithmetic prime field arithmetic extension field arithmetic optimal extension fields J. Guajardo B Information and System Security Department Philips Research Eindhoven The Netherlands e-mail S. S. Kumar C. Paar J. Pelzl Horst-Gortz Institute for IT-Security Ruhr-University Bochum Bochum Germany S. S. Kumar e-mail kumar@ C. Paar e-mail cpaar@ J. Pelzl e-mail pelzl@ Q Springer Acta Appl Math 1. Introduction Finite field or Galois field and finite ring arithmetic are an integral part of many cryptographic algorithms. The main application domain is asymmetric algorithms also known as public-key algorithms for instance algorithms based on the Discrete Logarithm DL problem the Diffie-Hellman DH key exchange protocol 16 and the Digital Signature Algorithm DSA