Page 210 - Hardware Implementation of Finite-Field Arithmetic

190 Cha pte r Se v e n

m
The following bit-level algorithm for Montgomery squaring in GF(2 )
can be found in [KA98]:
Algorithm 7.13—Bit-level algorithm for Montgomery squaring

Input: a(x), f(x)
-m
2
Output: c(x) = a(x) x mod f(x)
m-1
ax
1. c(x) := ∑ i=0 i 2i
2. for i = 0 to m – 1 do
3. c(x) := c(x) + c f(x)
0
4. c(x) := c(x)/x
Assume that the following functions are available:
function m2xvv2(x: poly2_vector; y: poly_vector) return
poly2_vector
function lshift2(x: poly2_vector) return poly2_vector
where m2xvv2 computes the bit-wise XOR of 2-bit vectors x (with 2m – 1
bits) and y (with m bits) in the form (x XOR y , x XOR y , . . . , x
0 0 1 1 m − 1
XOR y , x , x , . . . , x ), and where lshift2 computes the left shift
m − 1 m m + 1 2m − 2
of a given bit vector x (with 2m – 1 bits). Therefore, the bit-level
m
Montgomery squaring over GF(2 ) can be rewritten in the following
algorithm:
Algorithm 7.14—Bit-level Montgomery squaring, version 2
for i in 0 .. 2*m-2 loop c(i) := 0; end loop;
for i in 0 .. m-1 loop c(2*i) := a(i); d(i) := 0;
end loop;
for i in 0 .. m-1 loop
if c(0) = 1 then
c := m2xvv2(c,f);
c(m) := m2xor(c(m),1);
end if;
c := lshift2(c);
end loop;

An executable Ada file bsquarer_montgomery_v2.adb, includ-
ing Algorithm 7.14, is available at www.arithmetic-circuits.org. The
assignment c(m) := m2xor(c(m),1) for c(0) = 1 is such that f(x) is a
polynomial with m + 1 coefficients; for the addition c(x) := c(x) +
c f(x), the above assignment represents the addition of the term x m
0
from f(x).
A VHDL model for the combinational implementation of the bit-
level Montgomery squaring (version 2, Algorithm 7.14) is given in
the file montg_comb_squarer.vhd, which is available at www.
arithmetic-circuits.org. This model includes the component montg_
sq_c_cell, with c and new_c as std_logic_vector(2*m − 2 downto 0) as
input and output, and includes the following architecture: