Page 221 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 201

A VHDL file exponentiation_montgomery.vhd, modeling a sequen-
tial implementation of Algorithm 7.18, is available at www.
arithmetic-circuits.org. The corresponding circuit is shown in
Fig. 7.7.
The entity declaration of the bit-level Montgomery exponen-
tiation circuit given in the VHDL file exponentiation_montgomery.
vhd is

entity exponentiation_montgomery is
port (
A: in std_logic_vector (M-1 downto 0);
E: in std_logic_vector (N-1 downto 0);
clk, reset, start: in std_logic;
B: out std_logic_vector (M-1 downto 0);
done: out std_logic
);
end exponentiation_montgomery;

E (n – 1 : 0) A (m – 1 : 0) one (constant)
r mod f (constant) r x r mod f (constant) new_b (m – 1 : 0)
new_c (m – 1 : 0)

01 2 . control 1 01 23 control 2

m-bit register m-bit register
b (m – 1 : 0) c (m – 1 : 0)

start_mul start_sq
Montgomery Montgomery
multiplier done_mul squarer done_sq

new_b (m – 1 : 0) new_c (m – 1 : 0)

start start_mul
start_sq
inic
n-bitshift register State machine
shift_right ce_c = shift_right
(control)
control 1
E (0) control 2
done
FIGURE 7.7 Montgomery exponentiation.