Abstract:
An apparatus and method for computing a SHA-1 hash function value are provided. The apparatus includes a first register unit including a plurality of registers that store a first bit string of predetermined lengths for generation of a hash function value; a second register unit storing input data in units of second bit strings with predetermined lengths, and sequentially outputting the second bit strings; a third register unit performing an operation on the first bit string of the plurality of registers and the second bit strings output from the second register unit so as to generate and store a third bit string, and updating first-bit string of the plurality of registers based on the third bit string; and an adding unit combining the first bit string stored in the first register unit, the first bit string of the third bit string stored in the third register unit, and the original initial values stored in the first register unit so as to obtain a hash function value. Accordingly, it is possible to reduce the size of the apparatus and stably compute a hash function value at a high speed.

Description:
BACKGROUND OF THE INVENTION 
   This application claims the priority of Korean Patent Application No. 2003-97149, filed on Dec. 26, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference. 
   1. Field of the Invention 
   The present invention relates to an apparatus and method for computing a value of a hash function allowing compression of a message to increase the efficiency of digital signing that guarantees authentication and integrity of important information. 
   2. Description of the Related Art 
   Secure Hash Algorithms (SHAs) are algorithms developed by the National Institute of Standards and Technology (NIST), defined in the Federal Information Processing Standard (FIPS) 180-1. SHA-1, which is a type of SHA, divides an incoming message into units of 512-bit blocks using separation or zero padding, performs a rounding operation on the 512-bit blocks 80 times, and outputs a 160-bit compressed message. In particular, the SHA-1 hash algorithm generates a digital signature for the compressed message, thereby reducing the time required for digital signing. 
   The SHA is mainly used to increase the efficiency of digital signing. Thus, it is important to perform the algorithm quickly and reduce the size of an algorithm processor to minimize the load on a system due to addition of the processor. Most of the existing SHAs are embodied as software. Therefore, there is a growing need for development of an SHA-1 processor (or an SHA-1 hash operation unit) that can process data faster than SHAs embodied as software and serve power saving and safety of data. 
   SUMMARY OF THE INVENTION 
   According to one aspect of the present invention, there is provided an apparatus for computing a SHA-1 hash function, the apparatus including a first register unit including a plurality of registers that store a first bit string of predetermined lengths for generation of a hash function value; a second register unit storing input data in units of second bit strings with predetermined lengths, and sequentially outputting the second bit strings; a third register unit performing an operation on the first bit string of the plurality of registers and the second bit strings output from the second register unit so as to generate and store a third bit string, and updating first-bit string of the plurality of registers based on the third bit string; and an adding unit combining the first bit string stored in the first register unit, the first bit string of the third bit string stored in the third register unit, and the original initial values stored in the first register unit so as to obtain a hash function value. 
   According to another aspect of the present invention, there is provided a method of computing a SHA-1 hash function, the method including (a) storing initial values in registers A, B, C, D, and E; (b) dividing input data into bit strings of predetermined lengths, storing the bit strings in a register W, and outputting the stored bit strings; (c) performing a predetermined logic operation on the respective initial values stored in the registers A, B, C, D, and E, and the bit strings stored in the register W; (d) calculating intermediate values of the registers A, B, C, D, and E based on a result of the predetermined logic operation, updating the initial values of the registers A, B, C, D, and E with their intermediate values, and storing the updated initial values in the registers A, B, C, D, and E; (e) repeatedly performing (a) through (e) a predetermined number of times, and obtaining final values of the registers A, B, C, D, and E by combining the respective intermediate values stored in the registers A, B, C, D, and E with their original initial values. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other aspects and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which: 
       FIG. 1  is a schematic block diagram of an apparatus for computing a SHA-1 hash function value according to an embodiment of the present invention; 
       FIG. 2  is a schematic block diagram of a register A of  FIG. 1 ; 
       FIG. 3  is a schematic block diagram of a Register W of  FIG. 1 ; and 
       FIG. 4  is a flowchart illustrating a method of computing a SHA-1 hash function value according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Exemplary embodiments of the present invention will be described in detail with reference to the attached drawings. The same reference numerals represent the same elements throughout the drawings. 
     FIG. 1  is a schematic block diagram of an apparatus for computing a SHA-1 hash function value according to an embodiment of the present invention. The apparatus of  FIG. 1  includes a controller  100  that controls the execution of a rounding operation and the generation of a hash function value; registers A, B, C, D, E, and W  101 ,  102 ,  103 ,  104 ,  105 , and  106  that compute and store values A, B, C, D, E, and W required to generate the hash function value, respectively; and first through fifth 32-bit adders  107 ,  108 ,  109 ,  110 , and  111  that are activated or deactivated in response to an addition control signal Hash_ready input from the controller  100 . 
   When computing of the hash function value begins, initial values of the register B  102 , the register C  103 , the register D  104 , and the register E  105 , and a most significant 32-bit value output from the Register W  106  are input to the Register A  101 . Then, the register A  101  performs a rounding operation to compute a value A, and at the same time, the registers B, C, D, and E  102  through  105  perform a rounding operation to obtain values B, C, D, and E, respectively. 
   The obtained value A output from the register A  101  is input to both the register B  102  and the first 32-bit adder  107 . The value B, which is computed using the initial value of the register B  102  by the Register B  102 , is input to both the register C  103  and the second 32-bit adder  108 . The value C, which is computed using the initial value of the register C  103  by the Register C  103 , is input to both the register D  104  and the third 32-bit adder  109 . The value D, which is computed using the initial value of the register D  104  by the register D  104 , is input to both the register E  105  and the fifth 32-bit adder  110 . Then, a first rounding operation is completed. 
   A second rounding operation starts when a hash operation activation clock becomes a value of 1. In general, the hash operation activation clock is a system clock. The hash operation activation clock will be referred to as a clock hereinafter. Similarly to the first rounding operation, during the second rounding operation, the respective registers A through E  101  through  105  receive 32-bit values that are the result of the first rounding operation, perform the second rounding operation thereon, and output the results of the rounding operation to corresponding registers A through E  101  through  105  and 32-bit adders  107  through  111 . The adders  107  through  111  operate only when the addition control signal Hash_ready has a value of 1 and do not operate when it has a value of 0. A value of the addition control signal Hash_ready is initially adjusted to 0 and changed to 1 when a value of a counter (not shown) of the controller  100  reaches 79. Here, the counter value is increased by 1 from 0 to 79. The reason why the counter value is increased from 0 to 79 is that the SHA-1 hash algorithm performs a rounding operation 80 times as described above. 
   When the addition control signal Hash_ready has a value of 1, a 32-bit value output from the register A  101  and a 32-bit value H 0 , which is the initial value of the register A  101 , are input to the first adder  107 , and the first adder  107  combines the input values to generate a first most significant 32-bit value out_data [159:128]. Simultaneously, a 32-bit value output from the register B  102  and a 32-bit value H 1 , which is the initial value of the register B  102 , are input to the second adder  108 , and the second adder  108  combines the input values to generate a second most significant 32-bit value out_data [127:96]. 
   Next, a 32-bit value output from the register C  103  and a 32-bit value H 2 , which is the initial value of the register C  103 , are input to the third adder  109  and the third adder  109  combines these values to generate a third most significant 32-bit value out_data [95:64]. Next, a 32-bit value output from the register D  104  and a 32-bit value H 3 , which is the initial value of the register D  104 , are input to the fourth adder  110 , and the fourth adder  110  combines these values to generate a fourth most significant 32-bit value out_data [63:32]. Next, a 32-bit value output from the register E  105  and a 32-bit value H 4 , which is the initial value of the register E  105 , are input to the fifth adder  111 , and the fifth adder  111  combines these values to generate a least most significant 32-bit value out_data [31:0]. Then, a 160-bit hash function value is obtained. 
   Internal operations in the register A  101  and the register W  106  will be later described in detail with reference to  FIGS. 2 and 3 . First, internal operations in the registers B through E  102  through  105  will now be described. 
   While the register B  102 , the register D  104 , and the register E  105  only receive the input 32-bit values and output the 32-bit values, the register C  103  also rotates the input 32-bit value to the left by 30 bits when the clock has a value of 1 and outputs the value obtained by shifting. In other words, two least significant bit values input to the register C  103  are output as two most significant bit values, and a most significant bit value input thereto is output as a third most significant bit value. 
     FIG. 2  is a block diagram of the Register A  101  of  FIG. 1  according to an embodiment of the present invention. When 32-bit data A, B, C, D, E, and W and a signal sel are input to the Register A  101 , a rotation operator  201  rotates the 32-bit data A to the left by 5 bits (&lt;&lt;5). Also, an F-function operator  202  performs an F-function operation on the 32-bit data B, C, and D and 32-bit data is obtained as a result of the F-function operation. 
   The signal sel, output from the controller  100  of  FIG. 1 , is used to control the F function operator  202 . The value of the signal sel denotes the number of times that a rounding operation is to be performed. For instance, the values of the signal sel are 00, 01, 10, and 11, when values of the counter in the controller range from 0 to 19, from 20 to 39, from 40 to 59, and from 60 to 79, respectively. 
   A value of the F-function changes according to a value of the signal sel, as follows:
         F(B,C,D)=(B and C) or (not B and D) (sel=00)   F(B,C,D)=(B xor C xor D) (sel=01 or sel=11)   F(B,C,D)=(B and C) or (B and D) or (C and D) (sel=10)       

   A constant transformer  203  transforms a predetermined constant into different hexadecimal numbers according to a value of the signal sel. For instance, when the signal sel with a value of 00 is input to the constant transformer  203 , it outputs a value of 5A827999. When the signal sel with a value of 01 is input, the constant transformer  203  outputs a value of 6ED9EBA1. When the signal sel with a value of 10 is input, the constant transformer  203  outputs a value of 8F1BBCDC. When the signal sel with a value of 11 is input, the constant transformer  203  outputs a value of CA62C1 D6. 
   Outputs of the rotation operator  201  and the F-function operator  202  are input to and combined by a second adder  205 . The 32-bit data E and W input from the register A  101  are input to and combined by a first adder  204 . The result of combination output from the first adder  204  and a value output from the constant transformer  203  are input to and combined by a third adder  206 . Results of combination output from the second and third adders  205  and  206  are input to and combined by a fourth adder  207 , thus obtaining a value Out_data [31:0]. The value Out_data [31:0] is output from the Register A  101 . 
     FIG. 3  is a block diagram of the register W  106  of  FIG. 1  according to an embodiment of the present invention. When 512-bit data In_data [511:0] is input to the register W  106 , the register W  106  divides it into sixteen 32-bit data and sequentially stores the respective 32-bit data in w 0  through w 15  registers  301  through  316 . That is, the most significant 32 bits of the 512-bit data are stored in the w 0  register  301  and least significant 32 bits thereof are stored in the w 15  register  316 . When a clock has a value of 1, an output of the w 0  register  301  is output as an output of the Register W  106 , a first XOR operator  317  performs an XOR operation on the outputs of the w 0  register  301  and the w 2  register  303 , and a second XOR operator  319  performs an XOR operation on the outputs of the w 8  register  309  and the w 13  register  314 . Next, a third XOR operator  318  performs an XOR operation on results of the first and second XOR operations  317  and  319 . A rotation operator  320  rotates a result of the XOR operation to the left by 1 bit so as to shift the 32-bit data of the registers w 1  through w 15  to the registers w 0  through w 14 , respectively. Then, the rotation operator  320  stores the result of rotation. 
   That is, an output of the w 1  register  302  is moved to the w 0  register  301 , an output of the w 2  register  303  is moved to the w 1  register  302 , and an output of the rotation operator  320  is moved to the w 15  register  316 . When a subsequent clock has a value of 1, 32-bit data stored in the w 0  register is output as an output of the Register W  106 , and XOR operations are performed by the XOR operators  317 ,  318 , and  319 , and a rotation operation is performed by the rotation operator  320 . Next, outputs of the w 1  register  310  through the w 15  register  316  are shifted by 32 bits in the left direction, and the result of rotation is stored in the w  15  register  316 . The rotation operation is performed 80 times. 
     FIG. 4  is a flowchart illustrating a method of computing a SHA-1 hash function value, according to an embodiment of the present invention. Referring to  FIG. 4 , initial values are stored in the register A  101  through the register E  105  of  FIG. 1  (S 410 ). Next, when input data is stored in the Register W  106  (S 420 ), values A, B, C, D, E, and W stored in the respective register A  101  through the register W  106 , respectively, are processed to obtain new values A′, B′, C′, D′, E′, and W′, these new values are stored in the respective registers, and an intermediate value thereof is computed (S 430 ). Computation of the intermediate value was in detail described above using a rounding operation with reference to  FIG. 1 , and therefore, a description thereof will be omitted. 
   Next, it is determined whether computing of intermediate values has been repeatedly performed 80 times (S 440 ). If the number of times intermediate values has been computed is smaller than 80, it is determined whether the number of times intermediate values have been computed is a multiple of 20 (S 460 ). Whenever it is determined that the number of times is a multiple of 20, a function and a constant used by the register A  101  are transformed (S 470 ). After computing an intermediate value 80 times, the stored values A′, B′, C′, D′, and E′ are combined with the initial values to obtain final values (S 450 ). 
   As described above, a method and apparatus for computing a SHA-1 hash function value according to the present invention allow a hash function value to be quickly obtained by computing both a value of an output of a Register W and the hash function value. Also, a signal for controlling transformation of an F_function is generated using a value of a counter in a controller, and an operation required for computation of a hash function value is performed using the signal, thereby simplifying the operation. Further, since the register W shifts the value of the inner registers w 0  through w 15  by 32 bits in the left direction, an output of the register W is equivalent to that of a w 0  register, thereby allowing the Register W to be easily controlled. 
   While this invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.