Cryptography Reference
In-Depth Information
9.8.1 Prime Field Arithmetic on Resource-Constraint Processors
Typical prime field arithmetic operations include addition, subtraction, squaring,
multiplication, and reduction operations. Field inversion is also required for some oper-
ations, but in many cases it can be replaced with a larger number of cheaper operations.
For example, using Montgomery's method, the modular reduction can be carried out
without using division, and, hence, it is the modular multiplication and squaring that
are significant (Montgomery 1985). Multiprecision multiplication is the time-critical
requirement in a great majority of number-theoretic-based methods for PKC. It is
required for the RSA algorithm, for methods based on elliptic curves, and also for new
mechanisms that are based on cryptographic pairings. Elliptic curve systems are usu-
ally defined over finite fields F p of large characteristic (Section 3.2.3), where p has at
least 160 bits (for security reasons). Since the modulus is of a fixed size in bits, the code
for addition, multiplication, squaring, and modular reduction can be written in assem-
bly language. The loops can be completely unrolled to achieve maximum performance
at the cost of some additional storage.
The implementation of prime field arithmetic requires that each field element is
represented using multiple machine words. In the case of F p , where p is a large prime, the
field element a can be implemented as a series of W - bit u n s i g n e d i nt e g e r s 0 < a i < 2 W , where
W is the word size on the target machine (e.g., W = 8, 16, 32) and
-
= å 1
0
t
W
a
a
2
. The
i
i
é ù
=ê ú
ê
log
p
=
i
2
number of required words t to hold a field element can be calculated from
t
.
ú
W
ê
ú
The binary representation of a field element a can be stored in an array A = ( A [ t- 1] , . . . ,
A [2] , A [1] , A [0]), where the rightmost bit of A [0] is the Least Significant Bit (LSB).
9.8.1.1 Modular Addition and Subtraction
Multiprecision integer addition and subtraction is a straightforward operation on stan-
dard general-purpose processors. It requires t additions (or subtractions) of word-size
integers. On processors that have the add-with-carry (and subtract-with-carry) instruc-
tion, there is no need for an explicit check for carry. Arithmetic in the field F p requires
modular additions c = ( a + b ) mod p and subtractions c = (a - b) mod p . These opera-
tions require an additional step, which performs reduction modulo p . In the case of
modular subtraction, after calculating t word-size subtractions, the borrow bit is tested.
If the borrow is equal to 1 then the modulus p is added to the result c . Similarly, in
modular addition, the carry bit decides if a reduction is needed. When the carry bit
is equal to 1, then the modulus p needs to be subtracted from c . The reduction is also
needed if carry is equal to 0 and c p .
Figure 9.2 presents the timings for modular addition and subtraction operations
on 160-bit integers in F p . All the timings are given in clock cycles of a given hardware
Search WWH ::




Custom Search