power(a,b) mod m as state machine

Discussion in 'VHDL' started by HansWernerMarschke@web.de, Jun 28, 2008.

  1. 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;
     
    , Jun 28, 2008
    #1
    1. Advertising

  2. Guest

    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
     
    , Jun 29, 2008
    #2
    1. Advertising

  3. Guest

    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.
     
    , Jun 29, 2008
    #3
  4. MikeWhy Guest

    <> wrote in message
    news:...
    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.
     
    MikeWhy, Jun 29, 2008
    #4
  5. Guest

    On 30 Jun., 13:36, Brian Drummond <>
    wrote:
    > On Sun, 29 Jun 2008 07:30:58 -0700 (PDT),
    > 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/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)
    >
    > >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
     
    , Jun 30, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Weng Tianxiang
    Replies:
    7
    Views:
    1,144
    Mike Treseler
    Nov 25, 2003
  2. Andrew FPGA
    Replies:
    8
    Views:
    3,982
  3. Hari Sekhon
    Replies:
    0
    Views:
    538
    Hari Sekhon
    Jun 20, 2006
  4. ryles
    Replies:
    3
    Views:
    562
    Piet van Oostrum
    Jul 26, 2009
  5. T. Onoma
    Replies:
    9
    Views:
    377
    Dave Thomas
    Dec 15, 2003
Loading...

Share This Page