Correction parameter determination system

FIELD OF THE INVENTION

0001The invention is generally related to circuits and systems for performing modular exponentiations of large numbers, and more particularly, to circuits and systems for production of an error correction parameter associated with Montgomery modular multiplication.

BACKGROUND ART

0002The demand for secure information continues to drive improvements relating to cryptology. Modular exponentiation, and more particularly, the Montgomery algorithms, remains fundamental to the encryption and decryption of confidential, authenticated data used in Internet and electronic commerce. Montgomery modulation generally exploits properties and interrelations of very large numbers to avoid working with the numbers, themselves. Accordingly, dedicated programming and hardware for implementing Montgomery processes have been developed to achieve the repeated multiplications required for modular exponentiation in a faster and more efficient manner.

0003Calculation of an error correction parameter associated with Montgomery modulation is vital to the performance of exponentiation hardware and software. The error correction parameter is a constant that equals 2²ⁿmod N, where n is equivalent to the number of bits in the modulus, N, rounded up to the nearest multiple of the size of the multiplier core used in Montgomery modulation. As such, the parameter equals the remainder of a normal division operation where a bit string with a most significant bit of one, followed by 2n least significant zeros, is divided by the modulus.

0004In certain implementations, the error calculation parameter is pre-calculated using software configured to run the above described modulo operation on a computer with adequate processing. However, the size of the modulus, N, which can be on the order of thousands of bits in length, can burden even large processors. Alternatively, hardware circuit implementations that use dedicated gates to avoid the long delays of software are subject to their own timing issues. For instance, conventional hardware circuits must perform 2²ⁿprocessing loops during a modulo operation to arrive at the error correction parameter. Each iteration of the loop consists of a shift/compare operation, where a (n+1) bit accumulator is compared to the modulus, with the modulus subtracted therefrom if it is greater, or the accumulator multiplied by two (e.g. by shifting the contents of the accumulator one bit to the left) if it is less.

0005Moreover, to reduce the size of the subtraction circuitry, often each subtraction operation is performed using a series of partial subtraction operations that operate on a few bytes at a time (e.g., performing a 1024 bit subtraction using 64-bit subtraction circuitry that performs 16 partial subtraction operations). The tradeoff for the reduced size of subtraction circuitry is that each loop iteration requires multiple clock cycles to handle each subtraction operation.

0006For instance, a first iteration of a conventional loop may consist of initially setting a value in a working register to one, left shifting by one position, and attempting to subtract the modulus from the left-shifted result to determine if the value of the working register is larger than the modulus. Where so, the subtracted value in the working register is retained. Otherwise, the subtracted value of the working register is discarded, and the pre-subtracted value is again shifted and compared to the modulus in a subsequent iteration of the loop. A total of 2n iterations are performed in this manner, with the resulting value in the working register being the desired error correction parameter. Given that the value of 2n can be in the thousands, it will be appreciated that such repetitious iterations represent some of the most time intensive operations of a Montgomery application.

0007Consequently and despite the advances in implementing modular multiplications, a continuing need exists for further improvements in the field to reduce the overhead associated with performing modular multiplication operations.

SUMMARY OF THE INVENTION

0008The invention addresses these and other problems associated with the prior art by in one aspect providing a circuit arrangement and method that performs a plurality of shift/compare operations on a working register that has an initial value greater than a modulus value. For instance, the initial input may be selected to be the smallest exponent of 2 that is greater than the modulus (i.e., in binary, a binary “1” value left shifted to one position past the most significant bit of the modulus). Such an initial setting can reduce the number of required loop iterations and accelerate the parameter's determination.

0009Moreover, consistent with another aspect of the invention, the working register may be shifted by more than one position in connection with a shift/compare operation in order to further reduce loop iterations. Further processing accelerations realized by the present invention include conducting subtraction and shifting operations in parallel. During each shift/compare operation, or loop iteration, the modulus value may be subtracted from the working register to yield a subtracted result, while the result of a shifting operation is conducted and stored separately from the subtracted result. As such, either of the two stored results may serve readily as input to the next iteration of the loop, following a comparison, without the delays that plague conventional processing.

0010In so doing, the concepts of the present invention individually and conjunctively reduce processing times associated with error correction parameter determination, while further reducing costs associated with purchase and assembly of logic gates and other hardware.

0011These and other advantages and features, which characterize the invention, are set forth in the claims annexed hereto and forming a further part hereof. However, for a better understanding of the invention, and of the advantages and objectives attained through its use, reference should be made to the Drawings, and to the accompanying descriptive matter, in which there is described exemplary embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWING

0012<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of an error calculation circuit consistent with the invention.

0013<figref idref="DRAWINGS">FIG. 2</figref> is a flowchart of exemplary process steps suited to determine an initial input used in a processing loop executed by the hardware of <figref idref="DRAWINGS">FIG. 1</figref>.

0014<figref idref="DRAWINGS">FIG. 3</figref> is a flowchart of exemplary process steps suited to variably shift a binary word used in a processing loop executed by the hardware of <figref idref="DRAWINGS">FIG. 1</figref>.

0015<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart illustrating the program flow of a state machine consistent with the invention.

DETAILED EMBODIMENTS

0016Error correction determination for Montgomery modulation that is consistent with the invention may incorporate one or all of three concepts that provide substantial advantages over conventional parameter calculation techniques. The first concept applies to initializing an initial value for processing in a shift/compare operation, or loop iteration of an error correction circuit. This contrasts with conventional parameter calculation operations that shift the working register from a small initial value, e.g. “1,” which typically requires approximately n iterations of a loop to be performed before the modulus is ever subtracted from a working value.

0017As an example, consider an exemplary operation where the modulus is a number with a most significant bit of 945. A conventional operation, beginning with “1” and shifting/comparing by one register place for each iteration, would require 945 loop iterations before the working register has a most significant bit that is greater than 945 and thus a value that will result in a positive value being returned by a subtraction operation. For each iteration prior to that which results in a positive value being returned, the subtraction result will be negative, and thus discarded. Thus, it has been found that many of the initial shift operations in a conventional algorithm are essentially unnecessary in that the results of these operations are already known.

0018According to the first concept of the present invention, the initial value of a working register may be set to a value approximately equal to the most significant bit of the modulus, shifted one position to the left. In so doing, processes of the present invention recognize that no subtraction is typically necessary until the value of the working register has been shifted to a point that it is comparable to that of the modulus. Where desired, the initial value may be determined as the modulus is being loaded. Such initialization may nearly halve processing loop requirements of the comparable applications that begin with a minimal initial input.

0019The second concept consistent with the invention also reduces loop iterations by shifting the contents of the working register multiple positions within a single loop iteration. This concept facilitates error parameter calculation when compared to conventional shifting functions that shift in singular register increments, i.e., one register position per loop iteration, and require multiple processing loops to arrive at a useful register value. For example, as a result of a previous shift/compare operation the position of the most significant bit of a word of the modulus may occupy a register position that is four relative register positions greater than the register position occupied by the most significant bit of a corresponding word of the working register. As such, a conventional operation will require four, single shifts and respective loop iterations prior to arriving at a value in the working register that is greater than the modulus, contrasting an embodiment of the present invention in which the four individual shifts may be replaced by a single, four-position shift.

0020Still greater efficiency may be achieved by a third concept consistent with the invention that allows a subtracted result to be shifted and compared to the modulus at substantially the same time. This feature differs from conventional shifting operations, which are accomplished during a separate step than the modular comparison. These separate, deliberate steps of conventional practices translate into wasted processing cycles.

0021Each of these concepts will be described in greater detail in connection with a description of processes comprising each feature. Prior to discussing these specific embodiments, however, an exemplary hardware and software environment is described in greater detail below. More particularly, <figref idref="DRAWINGS">FIG. 1</figref> shows an exemplary parameter determination circuit <b>10</b> in accordance with the principles of the present invention. The circuit <b>10</b> includes a multiplexer <b>12</b> having multiple inputs from a register file <b>14</b>, as well as a zero and an initial input <b>22</b>, <b>24</b>, respectively. An exemplary multiplexer <b>12</b> consistent with the invention may comprise any device configured to selectively output a designated input.

0022As shown in <figref idref="DRAWINGS">FIG. 1</figref>, the register file <b>14</b> includes three logical files, or registers <b>16</b>-<b>20</b>. An exemplary register file <b>14</b> may include any digital storage or other memory. The size of each register <b>16</b>-<b>20</b> may be predetermined according to specific application requirements. For instance, each register <b>16</b>-<b>20</b> may accommodate 16, 64 bit values (i.e. 1024 bits). For purposes of this specification, “register” is used synonymously with the contained bit values or contents of an associated register. While having three registers <b>16</b>-<b>20</b> as shown in <figref idref="DRAWINGS">FIG. 1</figref> may present certain advantages in one scenario, one of skill in the art will recognize that more or fewer registers could be used in accordance with the principles of the present invention. Moreover, programmable and other types of memory storage may alternatively or additionally be utilized.

0023In operation, the multiplexer <b>12</b> routes one of the inputs <b>14</b>-<b>24</b> to an adder <b>26</b>, which also receives input from a memory <b>28</b>. As with the zero and initial inputs <b>22</b>, <b>24</b>, memory <b>18</b> may comprise hard or programmable storage, as well as a signal containing binary data elements. For instance, suitable memory <b>18</b> may comprise random access memory (RAM) containing the 16, 64 bit words that define a 1024 bit modulus. As discussed in greater detail below, the adder <b>26</b> may include a device configured to subtract the contents of the memory <b>18</b> from the multiplexer output. For instance, the adder <b>26</b> of the embodiment shown in <figref idref="DRAWINGS">FIG. 1</figref> accomplishes binary, bit-by-bit subtraction by adding one plus the inverse of the modulus to the multiplexer output.

0024A state machine <b>30</b> may couple to the multiplexer <b>12</b> and send instructions as to which input to send to the adder <b>26</b>. An exemplary state machine <b>30</b> may dictate and maintain register and other hardware addresses, as well as clock counts. A suitable state machine <b>30</b> may include and/or comprise one or more controllers, and one of skill in the art will appreciate that the placement and configuration of the state machine <b>30</b> may vary per application in accordance with the principles of the present invention. The state machine <b>30</b> typically also communicates with the register file <b>14</b>, adder <b>26</b> and memory <b>28</b>, as well as with a variable shifter <b>32</b>. Certain embodiments consistent with the invention include a variable shifter <b>32</b> configured to shift a register <b>16</b>-<b>18</b> output a plurality of bits in a single shift operation.

0025Those skilled in the art will recognize that the exemplary environment illustrated in <figref idref="DRAWINGS">FIG. 1</figref> is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative hardware and/or software environments may be used without departing from the scope of the invention. For example, while no clocking controls are shown in <figref idref="DRAWINGS">FIG. 1</figref>, it will be appreciated by one of skill in the art that clocks may be supplied by the state machine <b>30</b> whenever data must either emanate from or be fed into any of the above mentioned serially loaded/unloaded registers <b>16</b>-<b>20</b>. One of skill in the art will further appreciate that while other controls are also unspecified, i.e., multiplexer addresses, latch transfer signals, etc., they may readily be implemented in accordance with the principles of the present invention.

0026<figref idref="DRAWINGS">FIG. 2</figref> is a flowchart of exemplary process steps suited to determine the initial input <b>24</b> used in a processing loop executed by the hardware of <figref idref="DRAWINGS">FIG. 1</figref>. The flowchart of <figref idref="DRAWINGS">FIG. 2</figref> further outlines sequenced steps consistent with describing processes that apply to the aforementioned processing loops, and ultimately, determination of the error correction parameter.

0027More particularly, the circuit <b>10</b> of <figref idref="DRAWINGS">FIG. 1</figref> may load the modulus at block <b>40</b> of <figref idref="DRAWINGS">FIG. 2</figref> as part of an initialization process that includes blocks <b>40</b>-<b>48</b>. For instance, the modulus may be loaded into memory <b>18</b>. The modulus value, N, is typically large and advantageously broken into a sequence of words of predetermined length. Continuing with the example discussed in conjunction with <figref idref="DRAWINGS">FIG. 1</figref> for illustrative purposes, an exemplary modulus, or modulus value (as is herein used interchangeably with modulus), comprises 16 words of 64 bits each.

0028The state machine <b>30</b> operates on the modulus at block <b>42</b> as it is written to determine the most significant bit (and word) of the modulus. The most significant word of the modulus is the word containing its most significant bit. In operation, the state machine <b>30</b> may determine and store a most significant bit for a first loaded word at blocks <b>42</b> and <b>44</b>. If the words of the modulus are loaded from least to most significant, the most significant word of the modulus will be the last word having an “on” data element. Thus, the state machine <b>30</b> repeats the determination processes of blocks <b>42</b> and <b>44</b>, replacing the stored bit of block <b>44</b> with the most significant bit of a subsequently loaded word until no additional words at block <b>46</b> remain to be loaded. As is discussed below, zero inputs will be presented to the adder <b>26</b> at the occurrence of each word count that precedes the word count coinciding with the most significant word of the modulus as determined at blocks <b>42</b> and <b>44</b>.

0029According to one embodiment that is consistent with the principles of the present invention, program code or dedicated logic circuitry associated with the state machine <b>30</b> and/or circuit <b>10</b> at block <b>44</b> of <figref idref="DRAWINGS">FIG. 2</figref> stores the data as the initial input <b>24</b> of <figref idref="DRAWINGS">FIG. 1</figref>. Initial input <b>24</b> may comprise a signal conveying binary data information. The initial input <b>24</b> is typically the same size as a word of the modulus and corresponds to an integer greater than zero. More particularly, the circuit <b>10</b> may generate the initial input <b>24</b> by setting the bit of the initial input <b>24</b> to a value corresponding to the most significant bit of the most significant word of the modulus as determined at block <b>42</b>, shifted once to the left. A left shift functions to multiply the integer value of the modulus by two. Accordingly, the value of the initial input may be updated as the modulus loads, until the final word of the modulus has been loaded at block <b>46</b>.

0030The initialization processes at block <b>48</b> may include initialization of clock and word counts at the state machine <b>30</b>. For example, the clock count may set to an increment between zero and n. As discussed herein, the state machine <b>30</b> may set and update the respective counts at blocks <b>60</b>, <b>65</b> and <b>71</b> to determine, for instance, whether additional processing loops are necessary at block <b>82</b>, and whether the most significant word of the modulus is presented at the adder <b>26</b> at block <b>54</b>. While such a configuration lends particular advantages to certain embodiments of the present invention, one of skill in the art will recognize that the word and clock counts may alternatively or additionally be modified at other points in a processing loop per application requirements. Moreover, other positive settings of the initial value additionally accord with the principles of the present invention. Of note, “initial input” and “initial value” are used interchangeably throughout the specification.

0031Subsequent to establishing the initial input and clock settings at blocks <b>40</b>-<b>48</b>, the system may perform an initial loop at blocks <b>54</b>-<b>64</b>. The initial loop <b>54</b>-<b>64</b> may include determining at block <b>54</b> if the word count corresponds to the most significant word of the modulus as determined at block <b>42</b>. Where such a condition does not exist, a zero input may be presented to the adder <b>26</b> at block <b>55</b>. The circuit <b>10</b> shown in the embodiment of <figref idref="DRAWINGS">FIG. 2</figref> may still subtract an appropriate word of the modulus at block <b>59</b> as determined by the word count.

0032Thus, for each word of the modulus that precedes (i.e., is less significant, if words are loaded from least to most significant) the most significant word of the modulus as determined at block <b>54</b>, the multiplexer <b>12</b> presents a zero input <b>22</b> to the adder <b>26</b>. For instance, if the eighth word of the modulus contains its most significant bit, then the circuit <b>10</b> will provide seven zero inputs to the adder <b>26</b> at block <b>55</b> coinciding with the arrival of the seven words of the modulus, inverted, that precede the word of the working register containing the most significant bit. Because binary subtraction is equivalent to adding the inverse of a value plus one, the carry-in of the adder <b>26</b> is set for the least significant word addition so it may add an additional one. As shown in <figref idref="DRAWINGS">FIG. 2</figref>, the clock and word counts may be updated at block <b>60</b> to reflect the subtraction(s) of the initial loop.

0033The state machine <b>30</b> may instruct the multiplexer <b>12</b> at block <b>56</b> to output the initial input <b>24</b> to the adder <b>26</b>. The adder <b>26</b> of the embodiment of <figref idref="DRAWINGS">FIG. 1</figref> adds the inverse of the most significant word of the modulus, plus the carry out of the previous addition operation, to the initial input <b>24</b> at block <b>58</b>. This process effectively subtracts the modulus from a number consisting of the initial input <b>24</b>, followed by all zeros.

0034Upon ensuring (via the word count) that each word of the modulus and initial value have been processed, the state machine <b>30</b> knows that the initial result output from the adder <b>26</b> must be positive, and initiates storage of the initial result at block <b>64</b>. For instance, logic executed by the state machine <b>30</b> may cause the subtracted value to be stored in a register <b>18</b>. For reasons that will become apparent after a complete reading of the specification, the state machine <b>30</b> may designate the address of the register <b>18</b> as being the working register. In (main) processing loops subsequent to the initial loop of blocks <b>54</b>-<b>64</b>, the working register may selectively hold a shifted or another subtracted result. The clock and word counts may be incremented at block <b>65</b> to reflect the subtract/compare operation of the initial loop.

0035The contents of the working register <b>18</b> may be input to the variable shifter <b>32</b>. In some embodiments, the state machine <b>30</b> may determine at block <b>66</b> how many positions the working register <b>18</b> will be shifted in the span of a single loop. As discussed in greater detail below, the variable shifter <b>32</b> may selectively shift the initial result by multiple bit positions in a single shift. For instance, the variable shifter <b>32</b> may shift the initial result to the left a number of places correlated to the difference between the most significant bit of the working register and the most significant bit of the modulus. Put another way, the number of places shifted may be determined by the number of leading zeros that occupy binary placeholders of less value than the most significant bit of the modulus.

0036As such, if the 32^ndbit of the eighth word of the modulus is most significant, the variable shifter <b>32</b> may left shift the working register at block <b>68</b> up to 32 places in one loop iteration. In operation, if the most significant bit of the eighth word of the working register is the 27^thbit, then the variable shifter <b>32</b> may left shift the subtracted result five places in a single loop iteration. Shifting en masse further reduces loop requirements by avoiding loop iterations where no subtraction will occur. However, it should be appreciated by one of skill in the art that it may be desirable to shift the working register only once under certain conditions. In any case, the state machine <b>30</b> may initiate storage of this shifted result at block <b>70</b> in a second register <b>16</b>. The state machine <b>30</b> may additionally increment the clock count by five at block <b>71</b> to reflect the variable shift operation.

0037As per instructions from the state machine <b>30</b>, the multiplexer <b>12</b> outputs the subtracted result from variable shifter <b>32</b> and block <b>68</b> to the adder <b>26</b>. As such, the appropriate word of the modulus is subtracted from the shifted result at block <b>72</b>. In one embodiment consistent with the invention, such action may comprise a single shift/compare operation. That is, each shift/compare operation may include a register shift, effectively multiplying the register contents by two, as well as a comparison to determine whether the word of the working register is larger than a corresponding word of the modulus. In Montgomery calculations, such shift/compare operations are accomplished in every loop iteration of the calculation.

0038The subtracted result may be subsequently stored at block <b>73</b>. More particularly, the subtracted result may be stored in a third register <b>20</b> selected by the state machine <b>30</b>. The tandem storage of the subtracted and shifted results in separate registers <b>16</b>, <b>20</b> streamlines processing subsequent to the comparison at block <b>76</b>.

0039As such, the subtracted result is compared to a reference value at block <b>76</b>. For instance, the comparison at block <b>76</b> may determine whether the subtracted result is negative. Depending on the outcome of the determination, either the subtracted result or the shifted result will be used as the working register as designated by the state machine <b>30</b>. More particularly, if the subtracted result is determined to be negative at block <b>76</b>, then the state machine <b>30</b> may designate the register <b>20</b> containing the shifted value as the new working register. Alternatively, should the subtracted result be positive, then the register <b>16</b> containing the subtracted result becomes the new working register.

0040Assuming the clock count is not already equal to 2n at block <b>82</b>, the contents of the working register (working value) is input into the variable shifter <b>32</b> at block <b>80</b>, completing another processing loop. Should the clock count alternatively equal 2n at block <b>82</b> as required for the Montgomery method, then the binary data elements of the working register are output and stored as the error correction parameter at block <b>84</b>.

0041While the exemplary steps shown in <figref idref="DRAWINGS">FIG. 2</figref> are particularly advantageous under certain conditions, one of skill in the art will recognize that the sequence of these steps, as with all of the steps of the flowcharts of <figref idref="DRAWINGS">FIGS. 2-4</figref>, may be altered, with steps added or deleted in accordance with the principles of the present invention.

0042<figref idref="DRAWINGS">FIG. 3</figref> is a flowchart having exemplary process steps suited to variably shift a binary word used in a processing loop as discussed briefly in the text describing blocks <b>66</b> and <b>68</b> of <figref idref="DRAWINGS">FIG. 2</figref>. The flowchart of <figref idref="DRAWINGS">FIG. 3</figref> further illustrates typical interactions between the state machine <b>30</b> and the variable shifter <b>32</b>. For example, the flowchart illustrates the state machine's <b>30</b> monitoring of the modulus loading at block <b>90</b>. The state machine <b>30</b> reads the modulus to determine its most significant bit and word at block <b>92</b>, as well as the corresponding most significant bit of the initial input or working value, as discussed above.

0043The state machine <b>30</b> further determines a number correlated to the difference between the most significant bits of the working register and the modulus at block <b>94</b>, i.e., the number of consecutive leading zeros of the working register that are less than the most significant bit of the modulus. Referencing the ongoing example, the 32^ndbit is the most significant bit of the modulus' most significant word. Assuming that the most significant bit of the current value in the working register is 27^thbit, then the variable shifter <b>32</b> may shift the working register five units, or the difference between 32 and 27, in the next loop. As such, the state machine <b>30</b> may store this data and/or send an instruction to the variable shifter <b>32</b> at block <b>95</b> that relates to the data. For instance, the variable shifter <b>32</b> may receive an instruction at block <b>96</b> commanding it to shift its contents 5 bits to the left. As discussed herein, all 5 of the bits are left shifted in a single operation. The variable shifter <b>32</b> then outputs the shifted result to an appropriate register as described above. For synchronization considerations, the clock count may be updated to reflect the variable shift. For instance, if 5 bits are left shifted in a single operation, the clock count may be incremented in parallel by 5.

0044<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart illustrating the program flow of a state machine <b>30</b> consistent with the invention. Exemplary steps include initialization processes at blocks <b>100</b> and <b>102</b>, where the state machine <b>30</b> may reset memory and read the loading modulus. Reading of the modulus at block <b>102</b> may include a determination of whether the most significant bit of the modulus is located within the first word and/or within the capacity of a register of the system <b>10</b>. If so, the state machine <b>30</b> may ignore further words of the modulus, if any, and store the first word of the modulus in an appropriate register at block <b>110</b>.

0045In either case, the state machine <b>30</b> continues to execute processing loops at blocks <b>106</b> and <b>110</b> until the system clock count equals 2n, per Montgomery modulation specifications. At such time, the state machine <b>30</b> may save and output the working register at block <b>114</b>, the contents of which comprise the error correction parameter.

0046While the invention has and hereinafter will be described in the context of circuit arrangements and data processing systems utilizing the same, those skilled in the art will appreciate that circuit arrangements consistent with the invention are also capable of being distributed as program products in a variety of forms, and that the invention applies equally regardless of the particular type of signal bearing media used to actually carry out the distribution. Examples of signal bearing media include, but are not limited to recordable type media such as volatile and non-volatile memory devices, floppy and other removable disks, hard disk drives, magnetic tape, optical disks (e.g., CD-ROMs, DVDs, etc.), among others, and transmission type media such as digital and analog communication links.

0047Moreover, additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative apparatus and method, and illustrative examples shown and described. Accordingly, departures may be made from such details without departing from the spirit and scope of applicants' general inventive concept. For example, one of skill in the art will appreciate that the functionality of the exemplary circuit <b>10</b> may be accomplished programmably with less hardware in accordance with the principles of the present invention. Additionally, one of skill in the art will recognize that circuits consistent with the present inventions may be realized in a number of ways based on the specification and in accordance with the underlying principles of the invention. Therefore, the invention lies in the claims hereinafter appended.