Guest
In cryptographic algorithmens there is often an operation a^b mod m.
I´ve tried to model this as a state machine in VHDL.
The algorithm for fast exponentiation is some times called square &
multiply.
There is an aspect which I don´t understand.
I can synthesize the code without errros or warnings but I don´t get
the right result.
Here is the code followed by the testbench.
As you can recognize in the testbench 3 is calculated to the power of
4 modulus 2**8.
So the result should be 81.
In the simulation res get´s the values 0 (Initial) 1, 3, 9, 81 and
161.
res is assigned to the result and to the output port.
But not 81 is assigned as result instead the last value 161 is used.
You can interpret this that the loop is done one time more as needed.
Where is my fault ?
I´m not able to find the error.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
library IEEE;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.math_real.all;
entity power is
generic
(
-- Input and output size is 8 bit
size : positive := 8
);
port
(
clock : in std_logic;
base : in std_logic_vector(size-1 downto 0);
exponent : in std_logic_vector(size-1 downto 0);
result : out std_logic_vector(size-1 downto 0)
);
end power;
-- The square & multiply algorithmen as a state machine
-- for calculation of a^b mod 2 ** m
architecture power_rtl of power is
-- The states for the state machine
type states is (first, second, third, forth);
-- The state machine starts at the first state
signal state : states := first;
signal next_state : states;
subtype long is natural range 0 to 2 ** size - 1;
signal res, exp : long;
signal res_temp, exp_temp : long;
subtype index is integer range size-1 downto 0;
signal i : index;
begin
clocking : process (clock)
begin
if rising_edge(clock)
then
state <= next_state;
end if;
end process;
square_and_multiply : process (clock)
begin
if rising_edge(clock)
then
case state is
when first => res <= 1;
exp <= to_integer(unsigned(base));
i <= exponent'high;
next_state <= second;
when second => if i >= exponent'low
then
if exponent(i) = '1'
then
res_temp <= (res * exp) mod 2 ** size;
else
res_temp <= exp;
end if;
exp_temp <= (exp * exp) mod 2 ** size;
end if;
next_state <= third;
when third => if i > exponent'low
then
res <= res_temp;
exp <= exp_temp;
i <= i - 1;
next_state <= second;
else
next_state <= forth;
end if;
when forth => result <std_logic_vector(to_unsigned(res,size));
end case;
end if; -- rising_edge
end process square_and_multiply;
end architecture power_rtl;
--------------------------------------------------------------------------------------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.ALL;
use ieee.numeric_std.ALL;
entity testbench is
generic(
size : positive := 8
);
end testbench;
architecture behavior of testbench is
component power
port(
clock : in std_logic;
base, exponent : in std_logic_vector(0 to size-1);
result : out std_logic_vector(0 to size-1)
);
end component;
signal signal_base : std_logic_vector(0 to size-1);
signal signal_exponent : std_logic_vector(0 to size-1);
signal signal_result : std_logic_vector(0 to size-1);
signal clock_internal : std_logic;
-- Clock period definitions
constant clock_period_testbench : time := 10ns;
signal stop_the_clock: boolean;
begin
uut: power port map
(
base => signal_base,
exponent => signal_exponent,
result => signal_result,
clock => clock_internal
);
clocking : process
begin
while not stop_the_clock loop
clock_internal <= '1', '0' after clock_period_testbench / 2;
wait for clock_period_testbench;
end loop;
wait;
end process;
tb : process
begin
-- wait until global set/reset completes
wait for 10 ns;
signal_base <= "00000011";
signal_exponent <= "00000100";
-- will wait forever
wait;
end process tb;
end;
I´ve tried to model this as a state machine in VHDL.
The algorithm for fast exponentiation is some times called square &
multiply.
There is an aspect which I don´t understand.
I can synthesize the code without errros or warnings but I don´t get
the right result.
Here is the code followed by the testbench.
As you can recognize in the testbench 3 is calculated to the power of
4 modulus 2**8.
So the result should be 81.
In the simulation res get´s the values 0 (Initial) 1, 3, 9, 81 and
161.
res is assigned to the result and to the output port.
But not 81 is assigned as result instead the last value 161 is used.
You can interpret this that the loop is done one time more as needed.
Where is my fault ?
I´m not able to find the error.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
library IEEE;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.math_real.all;
entity power is
generic
(
-- Input and output size is 8 bit
size : positive := 8
);
port
(
clock : in std_logic;
base : in std_logic_vector(size-1 downto 0);
exponent : in std_logic_vector(size-1 downto 0);
result : out std_logic_vector(size-1 downto 0)
);
end power;
-- The square & multiply algorithmen as a state machine
-- for calculation of a^b mod 2 ** m
architecture power_rtl of power is
-- The states for the state machine
type states is (first, second, third, forth);
-- The state machine starts at the first state
signal state : states := first;
signal next_state : states;
subtype long is natural range 0 to 2 ** size - 1;
signal res, exp : long;
signal res_temp, exp_temp : long;
subtype index is integer range size-1 downto 0;
signal i : index;
begin
clocking : process (clock)
begin
if rising_edge(clock)
then
state <= next_state;
end if;
end process;
square_and_multiply : process (clock)
begin
if rising_edge(clock)
then
case state is
when first => res <= 1;
exp <= to_integer(unsigned(base));
i <= exponent'high;
next_state <= second;
when second => if i >= exponent'low
then
if exponent(i) = '1'
then
res_temp <= (res * exp) mod 2 ** size;
else
res_temp <= exp;
end if;
exp_temp <= (exp * exp) mod 2 ** size;
end if;
next_state <= third;
when third => if i > exponent'low
then
res <= res_temp;
exp <= exp_temp;
i <= i - 1;
next_state <= second;
else
next_state <= forth;
end if;
when forth => result <std_logic_vector(to_unsigned(res,size));
end case;
end if; -- rising_edge
end process square_and_multiply;
end architecture power_rtl;
--------------------------------------------------------------------------------------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.ALL;
use ieee.numeric_std.ALL;
entity testbench is
generic(
size : positive := 8
);
end testbench;
architecture behavior of testbench is
component power
port(
clock : in std_logic;
base, exponent : in std_logic_vector(0 to size-1);
result : out std_logic_vector(0 to size-1)
);
end component;
signal signal_base : std_logic_vector(0 to size-1);
signal signal_exponent : std_logic_vector(0 to size-1);
signal signal_result : std_logic_vector(0 to size-1);
signal clock_internal : std_logic;
-- Clock period definitions
constant clock_period_testbench : time := 10ns;
signal stop_the_clock: boolean;
begin
uut: power port map
(
base => signal_base,
exponent => signal_exponent,
result => signal_result,
clock => clock_internal
);
clocking : process
begin
while not stop_the_clock loop
clock_internal <= '1', '0' after clock_period_testbench / 2;
wait for clock_period_testbench;
end loop;
wait;
end process;
tb : process
begin
-- wait until global set/reset completes
wait for 10 ns;
signal_base <= "00000011";
signal_exponent <= "00000100";
-- will wait forever
wait;
end process tb;
end;
