From a315223f98fa6f1fdea2b1080c5f3e33352ebb13 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Joachim=20Stro=CC=88mbergson?= Date: Mon, 27 Apr 2015 11:17:08 +0200 Subject: Updating modexp core to v 0.50. This version contains a working core that can perform sign and verify with big keys/values. The core builds ok in Altera and Xilinx FPGA tools. This commit also includes a new testgenerator capable of generating testbench for modexp with autgenerated test data of different lengths. The README has been updated with status and implementation results in for different FPGA devices. --- src/rtl/modexp.v | 348 ++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 252 insertions(+), 96 deletions(-) (limited to 'src/rtl/modexp.v') diff --git a/src/rtl/modexp.v b/src/rtl/modexp.v index d64a556..9f3d4f0 100644 --- a/src/rtl/modexp.v +++ b/src/rtl/modexp.v @@ -71,35 +71,38 @@ module modexp( localparam ADDR_NAME0 = 8'h00; localparam ADDR_NAME1 = 8'h01; localparam ADDR_VERSION = 8'h02; - localparam ADDR_CTRL = 8'h03; + localparam ADDR_CTRL = 8'h08; localparam CTRL_INIT_BIT = 0; localparam CTRL_NEXT_BIT = 1; localparam ADDR_STATUS = 8'h09; + localparam STATUS_READY_BIT = 0; + + localparam ADDR_MODULUS_LENGTH = 8'h20; + localparam ADDR_EXPONENT_LENGTH = 8'h21; + localparam ADDR_LENGTH = 8'h22; // Should be deprecated. - localparam ADDR_MODSIZE = 8'h20; - localparam ADDR_LENGTH = 8'h21; - localparam ADDR_EXPONENT = 8'h22; localparam MODULUS_PREFIX = 4'h1; localparam ADDR_MODULUS_START = 8'h00; localparam ADDR_MODULUS_END = 8'hff; + localparam EXPONENT_PREFIX = 4'h2; localparam ADDR_EXPONENT_START = 8'h00; localparam ADDR_EXPONENT_END = 8'hff; + localparam MESSAGE_PREFIX = 4'h3; localparam MESSAGE_START = 8'h00; localparam MESSAGE_END = 8'hff; + localparam RESULT_PREFIX = 4'h4; localparam RESULT_START = 8'h00; localparam RESULT_END = 8'hff; - localparam LENGTH_PREFIX = 4'h5; - localparam DEFAULT_MODLENGTH = 8'h80; localparam DEFAULT_EXPLENGTH = 8'h80; @@ -107,7 +110,7 @@ module modexp( localparam MONTPROD_SELECT_X_NR = 3'h1; localparam MONTPROD_SELECT_Z_P = 3'h2; localparam MONTPROD_SELECT_P_P = 3'h3; - localparam MONTPROD_SELECT_ONE_Z = 3'h4; + localparam MONTPROD_SELECT_Z_ONE = 3'h4; localparam MONTPROD_DEST_Z = 2'b00; localparam MONTPROD_DEST_P = 2'b01; @@ -124,53 +127,36 @@ module modexp( localparam CTRL_CALCULATE_ZN = 4'h8; localparam CTRL_DONE = 4'h9; + localparam EXPONATION_MODE_SECRET_SECURE = 1'b0; + localparam EXPONATION_MODE_PUBLIC_FAST = 1'b1; //for rsa, c=M^65537 etc, there is no need to slow down to hide the exponent + + localparam CORE_NAME0 = 32'h6d6f6465; // "mode" localparam CORE_NAME1 = 32'h78702020; // "xp " - localparam CORE_VERSION = 32'h302e3031; // "0.01" + localparam CORE_VERSION = 32'h302e3530; // "0.50" //---------------------------------------------------------------- // Registers including update variables and write enable. //---------------------------------------------------------------- - reg [07 : 0] modulus_mem_int_rd_addr; - wire [31 : 0] modulus_mem_int_rd_data; - wire [31 : 0] modulus_mem_api_rd_data; - reg modulus_mem_api_we; - - reg [07 : 0] message_mem_int_rd_addr; - wire [31 : 0] message_mem_int_rd_data; - wire [31 : 0] message_mem_api_rd_data; - reg message_mem_api_we; - - reg [07 : 0] exponent_mem_int_rd_addr; - wire [31 : 0] exponent_mem_int_rd_data; - wire [31 : 0] exponent_mem_api_rd_data; - reg exponent_mem_api_we; + reg [07 : 0] exponent_length_reg; + reg [07 : 0] exponent_length_new; + reg exponent_length_we; - wire [31 : 0] result_mem_api_rd_data; - reg [07 : 0] result_mem_int_rd_addr; - wire [31 : 0] result_mem_int_rd_data; - reg [07 : 0] result_mem_int_wr_addr; - reg [31 : 0] result_mem_int_wr_data; - reg result_mem_int_we; - - reg [07 : 0] p_mem_rd0_addr; - wire [31 : 0] p_mem_rd0_data; - reg [07 : 0] p_mem_rd1_addr; - wire [31 : 0] p_mem_rd1_data; - reg [07 : 0] p_mem_wr_addr; - reg [31 : 0] p_mem_wr_data; - reg p_mem_we; + reg [07 : 0] modulus_length_reg; + reg [07 : 0] modulus_length_new; + reg modulus_length_we; reg [07 : 0] length_reg; + reg [07 : 0] length_new; reg [07 : 0] length_m1_reg; - reg [07 : 0] length_new; //TODO: API should write length!!! - reg [07 : 0] length_m1_new; //TODO: API should write length-1 when writing length!!! - reg length_we; //TODO: API should enable length_we!!! + reg [07 : 0] length_m1_new; + reg length_we; reg start_reg; - reg start_new; //TODO: API should start operations!!! - reg start_we; //TODO: API should start operations!!! + reg start_new; + reg start_we; + reg clear_start; reg ready_reg; reg ready_new; @@ -187,22 +173,61 @@ module modexp( reg [3 : 0] modexp_ctrl_new; reg modexp_ctrl_we; - reg [31 : 0] one; + reg [31 : 0] one_reg; reg [31 : 0] one_new; + reg [31 : 0] b_one_reg; + reg [31 : 0] b_one_new; reg [12 : 0] loop_counter_reg; reg [12 : 0] loop_counter_new; reg loop_counter_we; + reg [07 : 0] E_word_index; reg [04 : 0] E_bit_index; reg last_iteration; + reg ei_reg; reg ei_new; reg ei_we; + reg exponation_mode_reg; + reg exponation_mode_new; + reg exponation_mode_we; + + //---------------------------------------------------------------- // Wires. //---------------------------------------------------------------- + reg [07 : 0] modulus_mem_int_rd_addr; + wire [31 : 0] modulus_mem_int_rd_data; + wire [31 : 0] modulus_mem_api_rd_data; + reg modulus_mem_api_we; + + reg [07 : 0] message_mem_int_rd_addr; + wire [31 : 0] message_mem_int_rd_data; + wire [31 : 0] message_mem_api_rd_data; + reg message_mem_api_we; + + reg [07 : 0] exponent_mem_int_rd_addr; + wire [31 : 0] exponent_mem_int_rd_data; + wire [31 : 0] exponent_mem_api_rd_data; + reg exponent_mem_api_we; + + wire [31 : 0] result_mem_api_rd_data; + reg [07 : 0] result_mem_int_rd_addr; + wire [31 : 0] result_mem_int_rd_data; + reg [07 : 0] result_mem_int_wr_addr; + reg [31 : 0] result_mem_int_wr_data; + reg result_mem_int_we; + + reg [07 : 0] p_mem_rd0_addr; + wire [31 : 0] p_mem_rd0_data; + reg [07 : 0] p_mem_rd1_addr; + wire [31 : 0] p_mem_rd1_data; + reg [07 : 0] p_mem_wr_addr; + reg [31 : 0] p_mem_wr_data; + reg p_mem_we; + reg [31 : 0] tmp_read_data; //reg tmp_error; @@ -225,7 +250,7 @@ module modexp( reg residue_calculate; wire residue_ready; - reg [14 : 0] residue_nn; + reg [14 : 0] residue_nn; reg [07 : 0] residue_length; wire [07 : 0] residue_opa_rd_addr; wire [31 : 0] residue_opa_rd_data; @@ -238,6 +263,11 @@ module modexp( reg [07 : 0] residue_mem_montprod_read_addr; wire [31 : 0] residue_mem_montprod_read_data; + reg residue_valid_reg; + reg residue_valid_new; + reg invalidate_residue; + reg residue_valid_int_validated; + //---------------------------------------------------------------- // Concurrent connectivity for ports etc. //---------------------------------------------------------------- @@ -368,18 +398,37 @@ module modexp( begin if (!reset_n) begin + exponent_length_reg <= DEFAULT_EXPLENGTH; + modulus_length_reg <= DEFAULT_MODLENGTH; + start_reg <= 1'b0; ready_reg <= 1'b1; montprod_select_reg <= MONTPROD_SELECT_ONE_NR; montprod_dest_reg <= MONTPROD_DEST_NOWHERE; modexp_ctrl_reg <= CTRL_IDLE; - one <= 32'h0; + one_reg <= 32'h0; + b_one_reg <= 32'h0; length_reg <= 8'h0; length_m1_reg <= 8'h0; loop_counter_reg <= 13'b0; ei_reg <= 1'b0; + residue_valid_reg <= 1'b0; + exponation_mode_reg <= EXPONATION_MODE_SECRET_SECURE; end else begin + one_reg <= one_new; + b_one_reg <= b_one_new; + residue_valid_reg <= residue_valid_new; + + if (exponent_length_we) + exponent_length_reg <= exponent_length_new; + + if (modulus_length_we) + modulus_length_reg <= modulus_length_new; + + if (start_we) + start_reg <= start_new; + if (ready_we) ready_reg <= ready_new; @@ -394,8 +443,8 @@ module modexp( if (length_we) begin - length_reg <= write_data[7 : 0]; - length_m1_reg <= write_data[7 : 0] - 8'h1; + length_reg <= length_new; + length_m1_reg <= length_m1_new; end if (loop_counter_we) @@ -404,7 +453,8 @@ module modexp( if (ei_we) ei_reg <= ei_new; - one <= one_new; + if (exponation_mode_we) + exponation_mode_reg <= exponation_mode_new; end end // reg_update @@ -416,12 +466,35 @@ module modexp( //---------------------------------------------------------------- always @* begin : api + modulus_length_we = 1'b0; + exponent_length_we = 1'b0; + start_new = 1'b0; + start_we = 1'b0; modulus_mem_api_we = 1'b0; exponent_mem_api_we = 1'b0; message_mem_api_we = 1'b0; length_we = 1'b0; + invalidate_residue = 1'b0; + + //TODO: Add API code to enable fast exponation for working with public exponents. + exponation_mode_we = 1'b0; + + exponation_mode_new = EXPONATION_MODE_SECRET_SECURE; + modulus_length_new = write_data[7 : 0]; + exponent_length_new = write_data[7 : 0]; + length_new = write_data[7 : 0]; + length_m1_new = write_data[7 : 0] - 8'h1; + tmp_read_data = 32'h00000000; + // We need to be able to clear start bit after we have + // started a modexp operation. + if (clear_start) + begin + start_new = 1'b0; + start_we = 1'b1; + end + if (cs) begin case (address[11 : 8]) @@ -430,8 +503,26 @@ module modexp( if (we) begin case (address[7 : 0]) + ADDR_CTRL: + begin + start_new = write_data[0]; + start_we = 1'b1; + end + ADDR_LENGTH: - length_we = 1'b1; + begin + length_we = 1'b1; + end + + ADDR_MODULUS_LENGTH: + begin + modulus_length_we = 1'b1; + end + + ADDR_EXPONENT_LENGTH: + begin + exponent_length_we = 1'b1; + end default: begin @@ -451,10 +542,16 @@ module modexp( tmp_read_data = CORE_VERSION; ADDR_CTRL: - tmp_read_data = 32'h00000000; + tmp_read_data = {31'h00000000, start_reg}; ADDR_STATUS: - tmp_read_data = 32'h00000000; + tmp_read_data = {31'h00000000, ready_reg}; + + ADDR_MODULUS_LENGTH: + tmp_read_data = {24'h000000, modulus_length_reg}; + + ADDR_EXPONENT_LENGTH: + tmp_read_data = {24'h000000, exponent_length_reg}; ADDR_LENGTH: tmp_read_data = {24'h000000, length_reg}; @@ -471,6 +568,7 @@ module modexp( if (we) begin modulus_mem_api_we = 1'b1; + invalidate_residue = 1'b1; end else begin @@ -522,15 +620,19 @@ module modexp( // generates the big integer one ( 00... 01 ) //---------------------------------------------------------------- always @* - begin : one_process; + begin : one_process + one_new = 32'h00000000; + b_one_new = 32'h00000000; if (montprod_opa_addr == length_m1_reg) one_new = 32'h00000001; - else - one_new = 32'h00000000; + if (montprod_opb_addr == length_m1_reg) + b_one_new = 32'h00000001; end + //---------------------------------------------------------------- - // read mux for modulus, since it is being addressed by two sources + // Read mux for modulus. Needed since it is being + // addressed by two sources. //---------------------------------------------------------------- always @* begin : modulus_mem_reader_process @@ -540,21 +642,38 @@ module modexp( modulus_mem_int_rd_addr = montprod_opm_addr; end + //---------------------------------------------------------------- - // feeds residue calculator + // Feeds residue calculator. //---------------------------------------------------------------- always @* - begin : residue_process; - residue_nn = { 1'b0, length_reg, 6'h0 }; //N*2, N=length*32, *32 = shl5, *64 = shl6 + begin : residue_process + //N*2, N=length*32, *32 = shl5, *64 = shl6 + residue_nn = { 1'b0, length_reg, 6'h0 }; residue_length = length_reg; residue_opm_data = modulus_mem_int_rd_data; end + + //---------------------------------------------------------------- + // Sets the register that decides if residue is valid or not. + //---------------------------------------------------------------- + always @* + begin : residue_valid_process + if (invalidate_residue) + residue_valid_new = 1'b0; + else if ( residue_valid_int_validated == 1'b1) + residue_valid_new = 1'b1; + else + residue_valid_new = residue_valid_reg; + end + + //---------------------------------------------------------------- // montprod_op_select // // Select operands used during montprod calculations depending - // on what operation we want to do + // on what operation we want to do. //---------------------------------------------------------------- always @* begin : montprod_op_select @@ -572,7 +691,7 @@ module modexp( case (montprod_select_reg) MONTPROD_SELECT_ONE_NR: begin - montprod_opa_data = one; + montprod_opa_data = one_reg; montprod_opb_data = residue_mem_montprod_read_data; end @@ -594,10 +713,10 @@ module modexp( montprod_opb_data = p_mem_rd1_data; end - MONTPROD_SELECT_ONE_Z: + MONTPROD_SELECT_Z_ONE: begin - montprod_opa_data = one; - montprod_opb_data = result_mem_int_rd_data; + montprod_opa_data = result_mem_int_rd_data; + montprod_opb_data = b_one_reg; end default: @@ -612,7 +731,7 @@ module modexp( //---------------------------------------------------------------- // memory write mux // - // direct memory write signals to correct memory + // Direct memory write signals to correct memory. //---------------------------------------------------------------- always @* begin : memory_write_process @@ -643,11 +762,12 @@ module modexp( //---------------------------------------------------------------- // loop_counter // - // Calculate the loop counter and related variables + // Calculate the loop counter and related variables. //---------------------------------------------------------------- always @* begin : loop_counters_process - E_bit_index = loop_counter_reg[ 04 : 0 ]; + loop_counter_new = 13'b0; + loop_counter_we = 1'b0; if (loop_counter_reg == { length_m1_reg, 5'b11111 }) last_iteration = 1'b1; @@ -669,7 +789,7 @@ module modexp( default: begin - loop_counter_new = 13'b0; + loop_counter_new = loop_counter_reg; loop_counter_we = 1'b0; end @@ -680,12 +800,15 @@ module modexp( //---------------------------------------------------------------- // exponent // - // reads the exponent + // Reads the exponent. //---------------------------------------------------------------- always @* begin : exponent_process - // accessing new instead of reg - pick up update at CTRL_ITERATE_NEW to remove a pipeline stall - E_word_index = loop_counter_new[ 12 : 5 ]; + // Accessing new instead of reg - pick up update at + // CTRL_ITERATE_NEW to remove a pipeline stall. + E_word_index = length_m1_reg - loop_counter_new[ 12 : 5 ]; + + E_bit_index = loop_counter_reg[ 04 : 0 ]; exponent_mem_int_rd_addr = E_word_index; @@ -705,48 +828,70 @@ module modexp( //---------------------------------------------------------------- always @* begin - ready_new = 0; - ready_we = 0; + ready_new = 1'b0; + ready_we = 1'b0; montprod_select_new = MONTPROD_SELECT_ONE_NR; montprod_select_we = 0; montprod_dest_new = MONTPROD_DEST_NOWHERE; montprod_dest_we = 0; montprod_calc = 0; modexp_ctrl_new = CTRL_IDLE; - modexp_ctrl_we = 0; + modexp_ctrl_we = 1'b0; + clear_start = 1'b0; residue_calculate = 1'b0; + residue_valid_int_validated = 1'b0; + case (modexp_ctrl_reg) CTRL_IDLE: begin - ready_new = 0; - ready_we = 1; - if (start_reg == 1'b1) + if (start_reg) begin - modexp_ctrl_new = CTRL_RESIDUE; - modexp_ctrl_we = 1; - residue_calculate = 1'b1; + ready_new = 1'b0; + ready_we = 1'b1; + modexp_ctrl_new = CTRL_DONE; + modexp_ctrl_we = 1'b1; + + if (residue_valid_reg) + begin + //residue has alrady been calculated, start with MONTPROD( 1, Nr, MODULUS ) + montprod_select_new = MONTPROD_SELECT_ONE_NR; + montprod_select_we = 1; + montprod_dest_new = MONTPROD_DEST_Z; + montprod_dest_we = 1; + montprod_calc = 1; + modexp_ctrl_new = CTRL_CALCULATE_Z0; + modexp_ctrl_we = 1; + end + else + begin + //modulus has been written and residue (Nr) must be calculated + modexp_ctrl_new = CTRL_RESIDUE; + modexp_ctrl_we = 1; + residue_calculate = 1'b1; + end end end CTRL_RESIDUE: begin - if (residue_ready == 1'b1) + if (residue_ready) begin montprod_select_new = MONTPROD_SELECT_ONE_NR; montprod_select_we = 1; montprod_dest_new = MONTPROD_DEST_Z; montprod_dest_we = 1; montprod_calc = 1; - modexp_ctrl_new = CTRL_CALCULATE_Z0; - modexp_ctrl_we = 1; + modexp_ctrl_new = CTRL_CALCULATE_Z0; + modexp_ctrl_we = 1; + residue_valid_int_validated = 1'b1; //update registers telling residue is valid end end CTRL_CALCULATE_Z0: begin - if (montprod_ready == 1'b1) + if (montprod_ready) begin montprod_select_new = MONTPROD_SELECT_X_NR; montprod_select_we = 1; @@ -774,20 +919,28 @@ module modexp( montprod_dest_new = MONTPROD_DEST_Z; montprod_dest_we = 1; montprod_calc = 1; - modexp_ctrl_new = CTRL_ITERATE_Z_P; - modexp_ctrl_we = 1; + modexp_ctrl_new = CTRL_ITERATE_Z_P; + modexp_ctrl_we = 1; + + if (ei_new == 1'b0 && exponation_mode_reg == EXPONATION_MODE_PUBLIC_FAST) + begin + //Skip the fake montgomery calculation, exponation_mode_reg optimizing for speed not blinding. + montprod_select_new = MONTPROD_SELECT_P_P; + montprod_dest_new = MONTPROD_DEST_P; + modexp_ctrl_new = CTRL_ITERATE_P_P; + end end CTRL_ITERATE_Z_P: - if (montprod_ready == 1'b1) + if (montprod_ready) begin montprod_select_new = MONTPROD_SELECT_P_P; montprod_select_we = 1; montprod_dest_new = MONTPROD_DEST_P; montprod_dest_we = 1; montprod_calc = 1; - modexp_ctrl_new = CTRL_ITERATE_P_P; - modexp_ctrl_we = 1; + modexp_ctrl_new = CTRL_ITERATE_P_P; + modexp_ctrl_we = 1; end CTRL_ITERATE_P_P: @@ -799,24 +952,26 @@ module modexp( CTRL_ITERATE_END: begin - if (last_iteration == 1'b0) + if (!last_iteration) begin modexp_ctrl_new = CTRL_ITERATE; modexp_ctrl_we = 1; end else begin - montprod_select_new = MONTPROD_SELECT_ONE_Z; + montprod_select_new = MONTPROD_SELECT_Z_ONE; montprod_select_we = 1; + montprod_dest_new = MONTPROD_DEST_Z; + montprod_dest_we = 1; montprod_calc = 1; - modexp_ctrl_new = CTRL_CALCULATE_ZN; - modexp_ctrl_we = 1; + modexp_ctrl_new = CTRL_CALCULATE_ZN; + modexp_ctrl_we = 1; end end CTRL_CALCULATE_ZN: begin - if (montprod_ready == 1'b1) + if (montprod_ready) begin modexp_ctrl_new = CTRL_DONE; modexp_ctrl_we = 1; @@ -825,10 +980,11 @@ module modexp( CTRL_DONE: begin - ready_new = 1; - ready_we = 1; - modexp_ctrl_new = CTRL_IDLE; - modexp_ctrl_we = 1; + clear_start = 1'b1; + ready_new = 1'b1; + ready_we = 1'b1; + modexp_ctrl_new = CTRL_IDLE; + modexp_ctrl_we = 1; end default: -- cgit v1.2.3