Cryptography Reference
In-Depth Information
9.8.2.3 Square Root Computation
Applications have recently emerged in which it is important to calculate the square
roots of field elements. Efficient square rooting is especially important in the case of
pairing-based cryptography over binary fields (Barreto et al. 2007). Fast calculation of
square roots in 2 F requires that all exponents in the irreducible polynomial ( a , b and
c ) be odd (Fong et al. 2004). Such irreducible polynomials are easy to find, but unfor-
tunately most of the standard polynomials (e.g: irreducible polynomials recommended
by NIST) are not of this form.
As pointed out by Fong et al. (2004), if using an irreducible polynomial with all
odd exponents, for example, the trinomial z m + z a + 1, the field square root can be
expressed as
+ +
=+ +
(
m
)/2
(
a
)/2
az
()
A
(
z
z
).
A
(9.4)
even
odd
where A even and A odd are the even and odd indexed bits of a ( z ) concatenated into half-
sized bit arrays. Multiplication by the term z ( m +1) / 2 is simple and is performed by storing
A odd as the higher order bits of the final result. Multiplication of A odd by the rest of the
terms in f ( z ) can be performed with some xor operations and shifts, when necessary.
The amount of calculations required for this step depends on the particular irreduci-
ble polynomial. The resulting polynomial =
cz
()
az is of a degree less than m- 1;
()
therefore, the reduction step is not necessary.
9.9 Summary
Finite field arithmetic is one of the main building blocks of every IBC protocol. Finite
fields are very important constructs because they have special properties that can be
exploited for the purpose of cryptography. They serve as elementary blocks in ECC
because elliptic curves used in cryptography are always defined over finite fields. The
efficient implementation of finite field arithmetic is an important prerequisite in ellip-
tic curve systems because curve operations are performed using arithmetic operations
in the underlying field. Operations on field elements, such as addition, subtraction,
multiplication, squaring, and inversion operate on numbers that are usually hundreds
of bits long.
The two main types of finite fields that are suitable for implementation of elliptic
curve systems are prime fields F p and binary fields F 2 m . Arithmetic in finite fields is the
fundamental building block in every ECC implementation. The performance of the
whole system depends in large degree on the efficiency of the arithmetic operations. The
most important operation in the prime field is the multiprecision integer multiplication.
This chapter reviewed methods for calculating multiplication on low-end proces-
sors. Most of the arithmetic implementations on embedded devices are focused on
prime finite fields. The choice of the field is dictated by the fact that basic arithmetic
operations can be effectively optimized if pseudo-Mersenne primes are used in F p .
Search WWH ::




Custom Search