Implementation of Elliptic Curve Cryptography in Wireless Sensor Networks - Security for Wireless Sensor Networks Using Identity-Based Cryptography - page 191

700

600

500

400

Atmega
128
MSP430

300

200

100

0

Modular addition
(assembly)

Modular addition
(C language)

Modular
subtraction
(assembly)

Modular
subtraction (C)

Figure 9.2. Timings in Instruction Cycles for Modular Addition and Subtraction of
160-Bit Integers on Standard WSN Processors

platform. They represent an average value over 100 operations because the reduction
step is not always executed.

9.8.1.2 Multiprecision Integer Multiplication

There are two main methods to implement multiprecision integer multiplication
in software. The first group uses the Karatsuba-Ofman technique, which divides
the operands into smaller integers and thus reduces the number of multiplications.
Unfortunately, this approach has a large overhead in addition operations and is not
efficient in finite fields of practical interest. The second group of techniques is more
practical and uses different variations of basic schoolbook multiplication. When doing
multiplication using the schoolbook algorithm, the multiplication is divided into sev-
eral partial products that are accumulated to get the final result. The partial products
can be calculated in any order before they are added together. They can be arranged
in rows from right-to-left or in columns by bit length. Figures 9.3 and 9.4 show a 4×4
multiplication using both methods.
The column-wise technique (also known as the product scanning method) is not as
straightforward to program since the columns are of different lengths, although this is
not a concern if the code is unrolled. The alternative row-wise method (also known as
the operand scanning method) is much easier to implement as a short looped program.
The word-by-word multiplication can be carried out using a simple pair of nested “for”
loops. The row-wise algorithm requires more memory writes, but less memory reads,