Page 219 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 199

when 1 => if start = ‘1’ then current_state <= 2;
end if;
when 2 => current_state <= 3; --capture operands
when 3 => current_state <= 4; --start operations
when 4 => if (done_sq =’1’ and (ee(0) = ‘0’ or done_
mult =’1’)) then current_state <= 5; end if;
when 5 => if count = N-1 then current_state <= 0;
else current_state <= 3; end if;
end case;
end if;
end process control_unit;

It must be noted that Algorithm 7.16 is the binary version of
the square-and-multiply exponentiation mod f(x) given in Algo-
rithm 5.8. Furthermore, for multiplication and squaring operations
given in Algorithm 7.16, any of the algorithms given in Secs. 7.1
and 7.2 could be used. Therefore, if Montgomery multiplication
and squaring algorithms are used, a Montgomery exponentiation
method can be given [ KA97]. This approach is based on binary
method where standard multiplication and squaring operations in
m
GF(2 ) are simply replaced by Montgomery multiplication and
squaring operations. The method also requires a small amount of
pre- and postprocessing.
Let r(x) and a(x) be a fixed element and an arbitrary element,
m
respectively, of GF(2 ). The Montgomery image of a(x) under r(x) is
represented as ˆ()ax , and is defined as ˆ()ax = ax ⋅ r x
() () , where “⋅”
denotes standard multiplication modulo f(x). Given two Montgom-
ˆ
ery images ˆ()ax and ()bx , their Montgomery product “×” is defi-
ned as
ˆ() bx×
ax
ax ˆ () = ˆ() () ()bx r x⋅ ˆ ⋅ −1 (7.46)

ˆ
The Montgomery product of ˆ()ax and ()bx is equal to the
Montgomery image of the product a(x)⋅b(x), which is easily
ˆ
ˆ
proved as ˆ c = ˆ a b× = ˆ a br⋅ ⋅ −1 = (ar⋅⋅ ⋅⋅ −1 = a br = ⋅r . Let the
⋅
⋅
)
c
) (br r
r
exponent e be presented in its binary representation as an m-bit
e
vector e = (e , e , . . . , e ). In order to compute b = a for a given
0 1 m − 1
field element a ∈ GF(2 ), the Montgomery images of 1 and a using
m
standard multiplications must be first computed. The Montgom-
ery exponentiation algorithm based on the binary square and
multiply method then computes b = a using only Montgomery
e
multiplication and squaring operations as follows [KA97]:
Algorithm 7.17 —Montgomery exponentiation algorithm
Input: a, r, e
Output: b = a e