Efficient software-implementation of finite fields with applications to cryptography
The paper presents a survey of the existing techniques for software implementation of finite field arithmetic with a view in cryptographic applications. So the introduction discusses the types and sizes of finite fields used in Cryptography (for example the authors point out the vulnerability of the Elliptic Curve Cryptography over composite field extensions). The three types of fields \(\mathbb{F}_{2^m}, \mathbb{F}_p\) and \(\mathbb{F}_{p^m}\)\, are treated separately and in each one of the cases algorithms for the arithmetic operations of Addition, Multiplication, Field Reduction and Inversion are described. In the case of a field extension the elements are represented in a polynomial basis \(\{1, \alpha,\dots, \alpha^{m-1}\}\). Section 3 studies the case of binary fields \(\mathbb{F}_{2^m}\). The authors pay attention to the word-length of the processor, for instance they detail the Comb method for polynomial multiplication (of two \(m-1\)\, degree polynomials) in a \(w\)-bit processor. For the field reduction (of a \(2m-2\) degree polynomial modulo the degree \(m\) irreducible polynomial \(F(x)\) of \(\alpha\)) they state the convenience of choosing as \(F(x)\)\, a trinomial or pentanomial. Finally the paper discusses different ways to compute the inverse of an element in \(\mathbb{F}_{2^m}\): Binary Euclidean Algorithm, Almost Inverse Algorithm, Fermat Little Theorem and Look-up Tables. Section 4 reviews the case of fields \(\mathbb{F}_p\)\,. Firstly the paper describes ``multi-precision arithmetic for integers in radix \(b\)\, representation (\(b\) is chosen related to the word-length of the processor). Then the arithmetic modulo \(p\)\, is considered and the paper describes algorithms for modular reduction, both in the case of general primes \(p\)\, (Barret, Quisquater and Montgomery algorithms) and in the case of primes of special form (Crandall and Generalized Mersenne Primes). Software implementation of arithmetic over \(\mathbb{F}_{p^m}\)\, is the subject of Section 6 (although in the Introduction it is said that this case will be treated in Section 5. In fact Section 5 treats the problem of Inversion in fields \(\mathbb{F}_p\)). The so called Optimal Extension Fields allow an efficient software implementation. The paper provides a wide list of references to the studied algorithms as well as to related cryptographic aspects.
- Efficient hardware implementation of finite fields with applications to cryptography
- Software Implementation of Finite Fields of Characteristic Three, for Use in Pairing-based Cryptosystems
- Software implementation of elliptic curve cryptography over binary fields
- Efficient software implementation for finite field multiplication in normal basis
- Efficient arithmetic in finite field extensions with application in elliptic curve cryptography.
- Efficient Finite Fields in the Maxima Computer Algebra System
- The computational efficacy of finite-field arithmetic
- scientific article; zbMATH DE number 2058638
- Fast algorithms for elliptic curve cryptosystems over binary finite field
- A Computer Algorithm for Calculating the Product AB Modulo M
- A cryptographic library for the Motorola DSP56000
- A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
- Constructive and destructive facets of Weil descent on elliptic curves
- Efficient arithmetic in finite field extensions with application in elliptic curve cryptography.
- Fast key exchange with elliptic curve systems
- Guide to elliptic curve cryptography.
- High-speed software multiplication in \(\mathbb{F}_{2^m}\)
- scientific article; zbMATH DE number 5296403 (Why is no real title available?)
- scientific article; zbMATH DE number 1349933 (Why is no real title available?)
- scientific article; zbMATH DE number 954401 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Itoh-Tsujii inversion in standard basis and its application in cryptography and codes
- Modular Multiplication Without Trial Division
- New directions in cryptography
- Optimal extension fields for fast arithmetic in public-key algorithms
- Software implementation of elliptic curve cryptography over binary fields
- Software implementation of the NIST elliptic curves over prime fields
- Software-implementable pseudoprobabilistic fast block ciphers
- Practical fast algorithm for finite field arithmetics using group rings
- Efficient arithmetic in (pseudo-)Mersenne prime order fields
- Binary fields on limited systems
- Arithmetic of binary finite fields
- Efficient Finite Fields in the Maxima Computer Algebra System
- Efficient software implementation of binary field arithmetic using vector instruction sets
- scientific article; zbMATH DE number 3961485 (Why is no real title available?)
- scientific article; zbMATH DE number 1221491 (Why is no real title available?)
- Dual-field arithmetic unit for GF(p) and GF(2ᵐ)
- Generic \(\text{GF}(2^m)\) arithmetic in software and its application to ECC
- Efficient software implementation for finite field multiplication in normal basis
- A fast software implementation for arithmetic operations in \(\text{GF}(2^n)\)
- Fast normal basis multiplication using general purpose processors
- A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. (Extended abstract)
- Efficient Rijndael encryption implementation with composite field arithmetic
- Efficient implementations of Gaussian elimination in finite fields on ASICs for MQ cryptographic systems
- Optimal software-implemented Itoh-Tsujii inversion for \(\mathbb{F}_{2^{m}}\)
- scientific article; zbMATH DE number 5066607 (Why is no real title available?)
- Effects of Optimizations for Software Implementations of Small Binary Field Arithmetic
- An alternative class of irreducible polynomials for optimal extension fields
- Information Security and Privacy
- Generic efficient arithmetic algorithms for PAFFs (Processor Adequate Finite Fields) and related algebraic structures
- Efficient arithmetic in finite field extensions with application in elliptic curve cryptography.
- Finite field arithmetic in large characteristic for classical and post-quantum cryptography
- Efficient hardware implementation of finite fields with applications to cryptography
This page was built for publication: Efficient software-implementation of finite fields with applications to cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850780)
