---------------------------------------------------------------------------- -- Fermat's little theorem algorithm for modular divison (Fermat_divider.vhd) -- -- Computes Z = X/Y mod P using Fermatīs little theorem. -- i.e. X*(Y**(P-2)) mod P. Since Y**(P-2) mod P = Y**(-1) mod P -- -- uses the montgomery multiplier ---------------------------------------------------------------------------- library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_arith.all; use IEEE.std_logic_unsigned.all; package Fermat_divider_parameters is constant K: integer := 8; constant LOGK: integer := 3; constant int_p: integer := 239; constant P: std_logic_vector(K-1 downto 0) := conv_std_logic_vector(int_p, K); constant EXP_2K: std_logic_vector(K-1 downto 0) := conv_std_logic_vector((2**(2*K)) mod int_p, K); -- constant K: integer := 192; -- constant LOGK: integer := 8; -- constant P: std_logic_vector(K-1 downto 0) := X"fffffffffffffffffffffffffffffffeffffffffffffffff"; ---- constant MINUS_P: std_logic_vector(K downto 0) := '0'&X"000000000000000000000000000000010000000000000001"; ---- constant P_MINUS_2: std_logic_vector(K-1 downto 0) := X"fffffffffffffffffffffffffffffffefffffffffffffffd"; ---- constant EXP_K: std_logic_vector(K-1 downto 0) := X"000000000000000000000000000000010000000000000001"; -- --EXP_2K = 2**(2*K) mod p -- constant EXP_2K: std_logic_vector(K-1 downto 0) := X"000000000000000100000000000000020000000000000001"; -- constant K: integer := 256; -- constant LOGK: integer := 8; -- constant P: std_logic_vector(K-1 downto 0) := (223 downto 193 => '0',191 downto 96 => '0',others =>'1'); ------EXP_2K = 2**(2*K) mod p -- constant EXP_2K: std_logic_vector(K-1 downto 0) := (226 => '1',223 downto 194 => '1', 192 downto 129 => '1', -- 127 downto 99 => '1', 97 downto 64 => '1', 1 downto 0 => '1',others =>'0'); constant MINUS_P: std_logic_vector(K downto 0) := ('0' & not(P)) + '1'; constant P_MINUS_2: std_logic_vector(K-1 downto 0) := P - "10"; -- --EXP_K = 2**k mod p = 2**K - p = MINUS_P constant EXP_K: std_logic_vector(K-1 downto 0) := MINUS_P(K-1 downto 0); constant ZERO: std_logic_vector(LOGK-1 downto 0) := (others => '0'); constant ONE: std_logic_vector(K-1 downto 0) := conv_std_logic_vector(1, K); constant MONTG_DELAY: std_logic_vector(LOGK-1 downto 0) := conv_std_logic_vector(K/2, LOGK); end Fermat_divider_parameters; library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; use work.Fermat_divider_parameters.all; entity Fermat_divider is port ( x, y: in std_logic_vector(K-1 downto 0); clk, reset, start: in std_logic; z: out std_logic_vector(K-1 downto 0); done: out std_logic ); end Fermat_divider; architecture rtl of Fermat_divider is signal operand1, operand2, result, e, xy, txy, int_P_MINUS_2: std_logic_vector(K-1 downto 0); signal start_mp, mp_done, ce_e, ce_txy, load, update, ser_out, equal_ZERO: std_logic; signal cont1: std_logic_vector(1 downto 0); signal cont2: std_logic; type states is range 0 to 22; signal current_state: states; signal count: std_logic_vector(LOGK-1 downto 0); component Montgomery_multiplier is port ( x, y: in std_logic_vector(K-1 downto 0); clk, reset, start: in std_logic; z: out std_logic_vector(K-1 downto 0); done: out std_logic ); end component; begin with cont1 select operand1 <= xy when "00", e when others; with cont1 select operand2 <= EXP_2K when "00", e when "01", txy when "10", ONE when others; with cont2 select xy <= x when '0', y when others; main_component: Montgomery_multiplier port map(operand1, operand2, clk, reset, start_mp, result, mp_done); z <= result; register_e: process(clk) begin if clk'event and clk = '1' then if load = '1' then e <= EXP_K; elsif ce_e = '1' then e <= result; end if; end if; end process register_e; register_txy: process(clk) begin if clk'event and clk = '1' then if ce_txy = '1' then txy <= result; end if; end if; end process register_txy; equal_ZERO <= '1' when count = ZERO else '0'; shift_register: process(clk) begin if clk'event and clk = '1' then if load = '1' then int_P_MINUS_2 <= P_MINUS_2; elsif update = '1' then for i in 1 to k-1 loop int_P_MINUS_2(K-i) <= int_P_MINUS_2(K-i-1); end loop; int_P_MINUS_2(0) <= '0'; end if; end if; end process shift_register; ser_out <= int_P_MINUS_2(K-1); counter: process(clk) begin if clk'event and clk = '1' then if load = '1' then count <= conv_std_logic_vector(K, LOGK); elsif update= '1' then count <= count - 1; end if; end if; end process; control_unit: process(clk, reset, current_state) begin case current_state is when 0 to 1 => ce_e <= '0'; ce_txy <='0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '1'; when 2 => ce_e <= '0'; ce_txy <= '0'; load <= '1'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 3 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "00"; cont2 <= '1'; done <= '0'; when 4 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '1'; done <= '0'; when 5 => ce_e <= '0'; ce_txy <= '1'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '1'; done <= '0'; when 6 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "01"; cont2 <= '0'; done <= '0'; when 7 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "01"; cont2 <= '0'; done <= '0'; when 8 => ce_e <= '1'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "01"; cont2 <= '0'; done <= '0'; when 9 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 10 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 11 => ce_e <= '1'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 12 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '1'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 13 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 14 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 15 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 16 => ce_e <= '0'; ce_txy <= '1'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "00"; cont2 <= '0'; done <= '0'; when 17 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 18 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 19 => ce_e <= '1'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "10"; cont2 <= '0'; done <= '0'; when 20 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '1'; cont1 <= "11"; cont2 <= '0'; done <= '0'; when 21 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "11"; cont2 <= '0'; done <= '0'; when 22 => ce_e <= '0'; ce_txy <= '0'; load <= '0'; update <= '0'; start_mp <= '0'; cont1 <= "11"; cont2 <= '0'; done <= '0'; end case; if reset = '1' then current_state <= 0; elsif clk'event and clk = '1' then case current_state is when 0 => if start = '0' then current_state <= 1; end if; when 1 => if start = '1' then current_state <= 2; end if; when 2 => current_state <= 3; when 3 => current_state <= 4; when 4 => if mp_done= '1' then current_state <= 5; end if; when 5 => current_state <= 6; when 6 => current_state <= 7; when 7 => if mp_done= '1' then current_state <= 8; end if; when 8 => if ser_out = '1' then current_state <= 9; else current_state <= 12; end if; when 9 => current_state <= 10; when 10 => if mp_done= '1' then current_state <= 11; end if; when 11 => current_state <= 12; when 12 => current_state <= 13; when 13 => if equal_ZERO = '1' then current_state <= 14; else current_state <= 6; end if; when 14 => current_state <= 15; when 15 => if mp_done= '1' then current_state <= 16; end if; when 16 => current_state <= 17; when 17 => current_state <= 18; when 18 => if mp_done= '1' then current_state <= 19; end if; when 19 => current_state <= 20; when 20 => current_state <= 21; when 21 => if mp_done= '1' then current_state <= 22; end if; when 22 => current_state <= 0; end case; end if; end process; end rtl; ---------------------------------------------------------------------------- -- Montgomery_multiplier ---------------------------------------------------------------------------- library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; --use work.Montgomery_multiplier_parameters.all; use work.Fermat_divider_parameters.all; entity Montgomery_multiplier is port ( x, y: in std_logic_vector(K-1 downto 0); clk, reset, start: in std_logic; z: out std_logic_vector(K-1 downto 0); done: out std_logic ); end Montgomery_multiplier; architecture rtl of Montgomery_multiplier is signal pp, pc, ps, y_by_xi, next_pc, next_ps, half_ac, half_as, half_bc, half_bs, pp_minus_p: std_logic_vector(K downto 0); signal ac, as, bc, bs, long_p: std_logic_vector(K+1 downto 0); signal int_x: std_logic_vector(K-1 downto 0); signal xi, load, ce_p, equal_zero, load_timer, time_out: std_logic; type states is range 0 to 4; signal current_state: states; signal count, timer_state: std_logic_vector(logk-1 downto 0); begin and_gates: for i in 0 to k-1 generate y_by_xi(i) <= y(i) and xi; end generate; y_by_xi(K) <= '0'; first_csa: for i in 0 to k generate as(i) <= pc(i) xor ps(i) xor y_by_xi(i); ac(i+1) <= (pc(i) and ps(i)) or (pc(i) and y_by_xi(i)) or (ps(i) and y_by_xi(i)); end generate; ac(0) <= '0'; as(K+1) <= '0'; long_p <= "00" & P; second_csa: for i in 0 to k generate bs(i) <= ac(i) xor as(i) xor long_p(i); bc(i+1) <= (ac(i) and as(i)) or (ac(i) and long_p(i)) or (as(i) and long_p(i)); end generate; bc(0) <= '0'; bs(K+1) <= ac(K+1); half_as <= as(K+1 downto 1); half_ac <= ac(K+1 downto 1); half_bs <= bs(K+1 downto 1); half_bc <= bc(K+1 downto 1); with as(0) select next_pc <= half_ac when '0', half_bc when others; with as(0) select next_ps <= half_as when '0', half_bs when others; parallel_register: process(clk) begin if clk'event and clk = '1' then if load = '1' then pc <= (others => '0'); ps <= (others => '0'); elsif ce_p = '1' then pc <= next_pc; ps <= next_ps; end if; end if; end process parallel_register; equal_zero <= '1' when count = zero else '0'; pp <= ps + pc; pp_minus_p <= pp + minus_p; with pp_minus_p(K) select z <= pp(K-1 downto 0) when '0', pp_minus_p(K-1 downto 0) when others; shift_register: process(clk) begin if clk'event and clk = '1' then if load = '1' then int_x <= x; elsif ce_p = '1' then for i in 0 to k-2 loop int_x(i) <= int_x(i+1); end loop; int_x(K-1) <= '0'; end if; end if; end process shift_register; xi <= int_x(0); counter: process(clk) begin if clk'event and clk = '1' then if load = '1' then count <= conv_std_logic_vector(K-1, logk); elsif ce_p= '1' then count <= count - 1; end if; end if; end process; control_unit: process(clk, reset, current_state) begin case current_state is when 0 to 1 => ce_p <= '0'; load <= '0'; load_timer <= '1'; done <= '1'; when 2 => ce_p <= '0'; load <= '1'; load_timer <= '1'; done <= '0'; when 3 => ce_p <= '1'; load <= '0'; load_timer <= '1'; done <= '0'; when 4 => ce_p <= '0'; load <= '0'; load_timer <= '0'; done <= '0'; end case; if reset = '1' then current_state <= 0; elsif clk'event and clk = '1' then case current_state is when 0 => if start = '0' then current_state <= 1; end if; when 1 => if start = '1' then current_state <= 2; end if; when 2 => current_state <= 3; when 3 => if equal_zero = '1' then current_state <= 4; end if; when 4 => if time_out = '1' then current_state <= 0; end if; end case; end if; end process; timer:process(clk) begin if clk'event and clk = '1' then if load_timer = '1' then timer_state <= MONTG_DELAY; else timer_state <= timer_state - 1; end if; end if; end process timer; time_out <= '1' when timer_state = zero else '0'; end rtl;