power(a,b) mod m as state machine

[HansWernerMarschke]

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;

 

[HansWernerMarschke]

Thank´s for help, Brian.

This is of great value for me.
Do you have complete examples for the one process, two process and
three process state machine ?
I will try to change it into a one process state machine.
I hope this will help.

- Hans

 

[HansWernerMarschke]

I´ve changed some things (There was more then one mistake) and now it
´s running correctly.
My first, a little bit complicated, VHDL program, hurrah !
Now lets write the encryption program.

 

[MikeWhy]

I´ve changed some things (There was more then one mistake) and now it
´s running correctly.
My first, a little bit complicated, VHDL program, hurrah !
Now lets write the encryption program.

=========
You might also note that mod 2**N is simply the low N-bits of the value.
Makes me curious if there are similar optimizations you might try in the
power term.

 

[HansWernerMarschke]

http://toolbox.xilinx.com/docsan/xilinx4/data/docs/xst/hdlcode15.html

(Their 2-process SM is valid but unusual; it only separates the outputs
into a second process, rather than the state transitions. However you
can infer the usual form by working back from the 3-process example)


Sounds like it did... once this puzzle was solved, I hope the remaining
mistakes were easier to find.

How is the Enigma coming along?
Is it time to start writing Bombes in VHDL yet?

- Brian

Well Enigma is only an exercise which makes a lot of trouble.
It´s not really useful for secure encryption.
But there are also other encryption schemes which are a little bit
more state of the art like the ones from:
http://www.ecrypt.eu.org/stream/

Hans-Werner