Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > power(a,b) mod m as state machine

Reply
Thread Tools

power(a,b) mod m as state machine

 
 
HansWernerMarschke@web.de
Guest
Posts: n/a
 
      06-28-2008
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;
 
Reply With Quote
 
 
 
 
HansWernerMarschke@web.de
Guest
Posts: n/a
 
      06-29-2008
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
 
Reply With Quote
 
 
 
 
HansWernerMarschke@web.de
Guest
Posts: n/a
 
      06-29-2008
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.
 
Reply With Quote
 
MikeWhy
Guest
Posts: n/a
 
      06-29-2008
<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
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.




 
Reply With Quote
 
HansWernerMarschke@web.de
Guest
Posts: n/a
 
      06-30-2008
On 30 Jun., 13:36, Brian Drummond <(E-Mail Removed)>
wrote:
> On Sun, 29 Jun 2008 07:30:58 -0700 (PDT), (E-Mail Removed)
> wrote:
>
> >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 ?

>
> http://toolbox.xilinx.com/docsan/xil...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)
>
> >I will try to change it into a one process state machine.
> >I hope this will help.

>
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
State machine - Vending machine - strange behaviour fenster VHDL 3 12-23-2011 09:53 AM
Why doesn't `from pkg import mod' work after `del pkg.mod'? ryles Python 3 07-26-2009 04:13 PM
difference between import from mod.func() and x=mod.func() Hari Sekhon Python 0 06-20-2006 08:07 AM
append_features(mod) -- mod.kind_of? makes absolutely no sense T. Onoma Ruby 9 12-15-2003 03:34 AM



Advertisments