APPARATUS AND METHOD FOR HASH GENERATION

Abstract

A disclosed hash generation method includes: calculating a hash matrix for identifying original data, which corresponds to a product multiplied by a partial hash matrix of a last block of plural blocks divided from the original data, from a product for each of blocks other than the last block, which is calculated by multiplying from a partial hash matrix of a first block of the plural blocks up to a partial hash matrix of the block; and calculating a hash matrix for identifying changed data, by multiplying a product of a product multiplied lastly by a partial hash matrix of a block immediately before a changed block and a partial hash matrix of the changed block by an inverse matrix of a product multiplied lastly by a partial hash matrix of an unchanged original block and a product multiplied lastly by a partial hash matrix of the last block.

Claims

1. An information processing apparatus, comprising: a memory; and a processor coupled to the memory and configured to: calculate a first hash matrix for identifying original data, which corresponds to a first product multiplied by a partial hash matrix that is based on a last block of a plurality of blocks divided from the original data, from a second product for each of blocks other than the last block, wherein the second product for each of blocks other than the last block is stored in the memory and has been calculated by multiplying from a partial hash matrix that is based on a first block of the plurality of blocks up to a partial hash matrix that is based on the block; and calculate a second hash matrix for identifying changed data, by multiplying a third product of a fourth product multiplied lastly by a partial hash matrix that is based on a block immediately before a changed block and a partial hash matrix that is based on the changed block by an inverse matrix of a fifth product multiplied lastly by a partial hash matrix that is based on an unchanged original block and a sixth product multiplied lastly by a partial hash matrix that is based on the last block, upon detecting that a part of the original data has been changed.

2. The information processing apparatus as set forth in claim′, wherein the processor configured to: calculate the second hash matrix by multiplying, for each of changed blocks and in order from a head of changed blocks, the third product by the inverse matrix of the fifth product and the sixth product, upon detecting that a number of the changed blocks is more than 1.

3. The information processing apparatus as set forth in claim′, wherein the processor is further configured to update the fifth product by the third product to increment a block number for specifying the changed block, and the processor is configured to set a block specified by the block number as the changed block.

4. The information processing apparatus as set forth in claim′, wherein the processor is further configured to output a hash value based on the second hash matrix.

5. A hash generation method, comprising: calculating, by using a computer, a first hash matrix for identifying original data, which corresponds to a first product multiplied by a partial hash matrix that is based on a last block of a plurality of blocks divided from the original data, from a second product for each of blocks other than the last block, wherein the second product for each of blocks other than the last block is stored in the memory and has been calculated by multiplying from a partial hash matrix that is based on a first block of the plurality of blocks up to a partial hash matrix that is based on the block; and calculating, by using the computer, a second hash matrix for identifying changed data, by multiplying a third product of a fourth product multiplied lastly by a partial hash matrix that is based on a block immediately before a changed block and a partial hash matrix that is based on the changed block by an inverse matrix of a fifth product multiplied lastly by a partial hash matrix that is based on an unchanged original block and a sixth product multiplied lastly by a partial hash matrix that is based on the last block, upon detecting that a part of the original data has been changed.

6. Anon-transitory computer-readable storage medium storing a program that causes a computer to execute a process, the process comprising: calculating a first hash matrix for identifying original data, which corresponds to a first product multiplied by a partial hash matrix that is based on a last block of a plurality of blocks divided from the original data, from a second product for each of blocks other than the last block, wherein the second product for each of blocks other than the last block is stored in the memory and has been calculated by multiplying from a partial hash matrix that is based on a first block of the plurality of blocks up to a partial hash matrix that is based on the block; and calculating a second hash matrix for identifying changed data, by multiplying a third product of a fourth product multiplied lastly by a partial hash matrix that is based on a block immediately before a changed block and a partial hash matrix that is based on the changed block by an inverse matrix of a fifth product multiplied lastly by a partial hash matrix that is based on an unchanged original block and a sixth product multiplied lastly by a partial hash matrix that is based on the last block, upon detecting that a part of the original data has been changed.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0012] FIG. 1 is a diagram depicting a process of calculating a hash value;

[0013] FIG. 2 is a diagram depicting the process of calculating the hash value;

[0014] FIG. 3 is a diagram depicting the process of calculating the hash value;

[0015] FIG. 4 is a diagram depicting the process of calculating the hash value;

[0016] FIG. 5 is a diagram depicting first expressions and second expressions related to matrices;

[0017] FIG. 6 is a diagram depicting a process of calculating a hash value when a block is changed;

[0018] FIG. 7 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0019] FIG. 8 is a diagram depicting a process of calculating a hash value when a block is changed;

[0020] FIG. 9 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0021] FIG. 10 is a diagram depicting a process of calculating a hash value when a block is changed;

[0022] FIG. 11 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0023] FIG. 12 is a diagram depicting a process of calculating a hash value when a block is changed;

[0024] FIG. 13 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0025] FIG. 14 is a diagram depicting a process of calculating a hash value when a block is added;

[0026] FIG. 15 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0027] FIG. 16 is a diagram depicting a process of modifying a first product;

[0028] FIG. 17 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0029] FIG. 18 is a diagram depicting the process of modifying the first product;

[0030] FIG. 19 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0031] FIG. 20 is a diagram depicting the process of modifying the first product;

[0032] FIG. 21 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0033] FIG. 22 is a diagram depicting the process of modifying the first product;

[0034] FIG. 23 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0035] FIG. 24 is a diagram depicting the process of modifying the first product;

[0036] FIG. 25 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0037] FIG. 26 is a diagram depicting the process of modifying the first product;

[0038] FIG. 27 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0039] FIG. 28 is a diagram depicting the process of modifying the first product;

[0040] FIG. 29 is a diagram depicting the first expressions and the second expressions related to the matrices;

[0041] FIG. 30 is a diagram depicting an example of module configuration of a hash generation apparatus;

[0042] FIG. 31 is a diagram depicting a main processing flow;

[0043] FIG. 32 is a diagram depicting a main processing flow;

[0044] FIG. 33 is a diagram depicting an example of module configuration of an initial calculation unit;

[0045] FIG. 34 is a processing flow of an initial processing;

[0046] FIG. 35 is a diagram depicting an example of module configuration of a change unit;

[0047] FIG. 36 is a processing flow of a change processing;

[0048] FIG. 37 is a diagram depicting an example of module configuration of an addition unit;

[0049] FIG. 38 is a processing flow of an addition processing;

[0050] FIG. 39 is a processing flow of a calculation processing;

[0051] FIG. 40 is a diagram depicting an example of module configuration of a modification unit;

[0052] FIG. 41 is a processing flow of a modification processing;

[0053] FIG. 42 is a processing flow of a modification processing; and

[0054] FIG. 43 is a functional block diagram of a computer.

DESCRIPTION OF EMBODIMENTS

[0055] In this embodiment, part of internal data that is generated in a process of calculating a hash value for the original data is stored. Then, when the original data is changed, a new hash value is calculated with less computation using the internal data. The original data may be about 1 terabyte, for example.

[0056] Firstly FIG. 1 to FIG. 4 illustrates a process of calculating a hash value. Furthermore, FIG. 5 illustrates expressions related to matrices that are used in that process. The first expressions in this example are expressions that define matrices that are illustrated on the left side. Similarly, the second expressions are expressions for calculating matrices that are illustrated on the left side.

[0057] First, FIG. 1 will be explained. The original data for which a hash value is generated is divided into blocks having a predetermined length (for example, 64 kibibytes). In this example, the original data is divided into N blocks. The block number i is a natural number from 1 to N. In this example, a block is written as X.sub.i. In other words, the original data is divided into block X.sub.1, block X.sub.2, block X.sub.3, . . . block X.sub.n.

[0058] First, the hash value H.sub.1 is generated from block X.sub.1. In the following, the hash value obtained from each block X.sub.i is called a first hash value. Moreover, a hash value is written as H.sub.i. Since the first hash value is based on part of the original data, the first hash value is a partial hash value. The size of the hash value in this example is 256 bits. A hash function for finding a hash value is based on a conventional technique.

[0059] The first hash value H.sub.1 is converted to a hash matrix A.sub.1. In the following, the hash matrix that is obtained from each of the first hash values H.sub.i is called first hash matrix. Moreover, a first hash matrix is written as A.sub.i. Since the first hash matrix A.sub.i is based on part of the original data, the first hash matrix is a partial hash matrix. In this example, the hash matrix A.sub.i is a square matrix of 4 rows*4 columns.

[0060] The hash value H.sub.i is divided into 16-bit codes. For example, a hash value is divided every 16 bits starting from the least significant bit. Then, the first to the fourth codes that are obtained by division are assigned to the element of the first column to the element of the fourth column of the first row of hash matrix A.sub.i. Similarly, the fifth to the eighth codes are assigned to the element of the first column to the element of the fourth column of the second row of hash matrix A.sub.i. Similarly, the ninth to the twelfth codes are assigned to the element of the first column to the element of the fourth column of the third row of hash matrix A.sub.i. Similarly, the thirteenth to the sixteenth codes are assigned to the element of the first column to the element of the fourth column of the fourth row of hash matrix A.sub.i.

[0061] In this embodiment, a product in which hash matrices A.sub.i are sequentially multiplied is stored as internal data. The product that is generated from the initial original data is called the first product. Moreover, a first product is written as C.sub.i. The first first product is defined by the first expression “C.sub.1=A.sub.1” that is illustrated in FIG. 5, and is similarly found by the second expression “C.sub.1=A.sub.1”. In this example, the internally stored data is represented by bold lines. In other words, the blocks X.sub.i and the first products C.sub.i are internally stored.

[0062] Next, calculation for the second block X.sub.2 will be explained using FIG. 2. The second first hash value H.sub.2 is calculated based on the second block X.sub.2. The second first hash value H.sub.2 is converted to a second first hash matrix A.sub.2.

[0063] The second first product C.sub.2 is defined by the first expression “C.sub.2=A.sub.1A.sub.2” that is illustrated in FIG. 5, and is similarly introduced by the second expression “C.sub.2=C.sub.1A.sub.2”. In other words, the second first product C.sub.2 is found by multiplying the first first product C.sub.1 by the second first hash matrix A.sub.2.

[0064] Next, calculation for the third block X.sub.3 will be explained using FIG. 3. The third first hash value H.sub.3 is calculated based on the third block X.sub.3. The third first hash value H.sub.3 is converted to a third first hash matrix A.sub.3.

[0065] The third first product C.sub.3 is defined by the first expression “C.sub.3=A.sub.1A.sub.2A.sub.3” that is illustrated in FIG. 5, and is similarly found by the second expression “C.sub.3=C.sub.2A.sub.3”. In other words, the third first product C.sub.3 is found by multiplying the second first product C.sub.2 by the third first hash matrix A.sub.3.

[0066] Similar processing is repeated up until the Nth block. FIG. 4 illustrates the processing for the Nth block. The Nth first hash value H.sub.N is calculated based on the Nth block X.sub.N. The Nth first hash value H.sub.N is converted to an Nth first hash matrix A.sub.N.

[0067] The Nth first product C.sub.N is defined by the first expression “C.sub.N=A.sub.1A.sub.2A.sub.3 . . . A.sub.N” that is illustrated in FIG. 5, and is similarly found by the second expression “C.sub.N=C.sub.N−1A.sub.N”.

[0068] In other words, the Nth first product C.sub.N is found by multiplying the (N−1) th first product C.sub.N−1 by the Nth first hash matrix A.sub.N.

[0069] A second hash matrix B for specifying the original data is defined by the first expression “B=A.sub.1A.sub.2A.sub.3 . . . A.sub.N” that is illustrated in FIG. 5, and is similarly found by the second expression “B=C.sub.N”. In other words, the first product C.sub.N becomes the second hash matrix B for specifying the original data.

[0070] Furthermore, the second hash matrix B is converted to a second hash value H.sub.t for specifying the original data. In this example, the element in the first column to the element in the fourth column of the first line of the second hash matrix B are first to fourth codes. The element in the first column to the element in the fourth column of the second line of the second hash matrix B are fifth to eighth codes. The element in the first column to the element in the fourth column of the third line of the second hash matrix B are ninth to twelfth codes. The element in the first column to the element in the fourth column of the fourth line of the second hash matrix B are thirteenth to sixteenth codes. The second hash value H.sub.t is generated by combining the first to the sixteenth codes. The size of the second hash value H.sub.t in this example is 256 bits.

[0071] In the following, the case in which part of the blocks is changed will be explained. FIG. 6 illustrates a process of calculating a hash value when the third block is changed. The changed third block is written as X*.sub.3. In this example, “*” is attached to a changed block. The first expressions and second expressions for the matrices related to this process of calculation are illustrated in FIG. 7.

[0072] The third new first hash value H*.sub.3 is calculated from the third changed block X*.sub.3. In this example, an asterisk * is attached to a changed first hash value.

[0073] Furthermore, the third new first hash value H*.sub.3 is converted to a new first hash matrix A*.sub.3. In this example, an asterisk * is attached to a changed first hash matrix.

[0074] Then, a second product C*.sub.3 up to the new first hash value H*.sub.3 is calculated. The second product C*.sub.3 that corresponds to the third changed block X*.sub.3 is defined by the first expression “C*.sub.3=A.sub.1A.sub.2A*.sub.3” that is illustrated in FIG. 7. In this way, a product that includes a changed first hash matrix is called a second product. Moreover, a second product is written as C*.sub.i. A second product C*.sub.i is stored internally unless it becomes unnecessary.

[0075] The second product C*.sub.3 is found by the second expression “C*.sub.3=C.sub.2A*.sub.3” that is illustrated in FIG. 7.

[0076] In other words, the third second product C*.sub.3 is found by multiplying the second first product C.sub.2 by the third new first hash matrix A*.sub.3.

[0077] In this embodiment, an inverse matrix D.sub.i of a first product C.sub.i that corresponds to a changed block X*.sub.j is found. In this example, the inverse matrix D.sub.3 that corresponds to the third changed block X*.sub.3 is defined by the first expression “D.sub.3=(A.sub.1A.sub.2A.sub.3).sup.−1” that is illustrated in FIG. 7, and similarly is found by the second expression “D.sub.3=C.sub.3.sup.−1” An inverse matrix D.sub.i is stored internally except unless it becomes unnecessary.

[0078] Processing to find the second hash value H.sub.t in this state will be explained. The second hash matrix B in this state is defined by the first expression “B=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A.sub.8” that is illustrated in FIG. 7, and similarly is found by the second expression “B=C*.sub.3D.sub.3C.sub.8”.

[0079] In other words, the second hash matrix B in this state is found by multiplying the third second product C*.sub.3 by the third inverse matrix D.sub.3, and then multiplying by the eighth first product C.sub.8 that corresponds to the last block. The second hash matrix B is then converted to the second hash value H.sub.t.

[0080] A process of calculating a hash value when the sixth block X.sub.6 is further changed will be explained using FIG. 8. The first expressions and second expressions related to this process of calculation are illustrated in FIG. 9.

[0081] A sixth new first hash value H*.sub.6 is calculated from the sixth changed block X*.sub.6. The sixth new first hash value H*.sub.6 is further converted to a new first hash matrix A*.sub.6.

[0082] The second product C*.sub.6 up to the new first hash value H*.sub.6 is then calculated. The second product C*.sub.6 that corresponds to the sixth changed block X*.sub.6 is defined by the first expression “C*.sub.6=A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A*.sub.6” that is illustrated in FIG. 9, and similarly is found by the second expression “C*.sub.6=C.sub.5A*.sub.6”.

[0083] In other words, the sixth second product C*.sub.6 is found by multiplying the fifth first product C.sub.5 by the new first hash matrix A*.sub.6.

[0084] Moreover, an inverse matrix D.sub.6 that corresponds to the sixth changed block X*.sub.6 is defined by the first expression “D.sub.6=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6).sup.−1” that is illustrated in FIG. 9, and similarly is found by the second expression “D.sub.6=C.sub.6.sup.−1”.

[0085] Processing for finding the second hash value H.sub.t in this state will be explained. The second hash matrix B in this state is defined by the first expression “B=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6A.sub.7A.sub.8” that is illustrated in FIG. 9, and similarly is found by the second expression “B=C*.sub.3D.sub.3C*.sub.6D.sub.6C.sub.8”.

[0086] In other words, the second hash matrix B in this state is found by multiplying the third second product C*.sub.3 by the third inverse matrix D.sub.3, the sixth second product C*.sub.6, the sixth inverse matrix D.sub.6, and the eighth first product C.sub.8 that corresponds to the last block. Then, the second hash matrix B is converted to the second hash value H.sub.t.

[0087] Process of calculating a hash value when the second block X.sub.2 is changed will be explained. The first expressions and the second expressions that are related to this process of calculating are illustrated in FIG. 11.

[0088] A second new first hash value H*.sub.2 is calculated from the second changed block X*.sub.2 Then, the second new first hash value H*.sub.2 is further converted to a new first hash matrix A*.sub.2.

[0089] A second product C*.sub.2 is then calculated up to the new first hash value H*.sub.2 The second product C*.sub.2 that corresponds to the second changed block X*.sub.2 is defined by the first expression “C*.sub.2=A.sub.1A*.sub.2” that is illustrated in FIG. 11, and is similarly found by the second expression “C*.sub.2=C.sub.1A*.sub.2”. In other words, the second second product C*.sub.2 is found by multiplying the first first product C.sub.1 by the second new first hash matrix A*.sub.2.

[0090] Moreover, an inverse matrix D.sub.2 that corresponds to the second changed block X*.sub.2 is defined by the first expression “D.sub.2=(A.sub.1A.sub.2).sup.−1” that is illustrated in FIG. 11, and similarly is found by the second expression “D.sub.2=C.sub.2.sup.−1”.

[0091] Processing for finding the second hash value H.sub.t in this state will be explained. The second hash matrix B in this state is defined by the first expression “B=A.sub.1A*.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6A.sub.7A.sub.8” that is illustrated in FIG. 11, and is similarly found by the second expression “B=C*.sub.2D.sub.2C*.sub.3D.sub.3C*.sub.6D.sub.6C.sub.8”.

[0092] In other words, the second hash matrix B in this state is found by multiplying the second second product C*.sub.2 by the second inverse matrix D.sub.2, the third second product C*.sub.3, the third inverse matrix D.sub.3, the sixth second product C*.sub.6, the sixth inverse matrix D.sub.6, and the eighth first product C.sub.8 that corresponds to the last block. The second hash matrix B is then converted to the second hash value H.sub.t.

[0093] Next, a process of calculating a hash value when the last block is changed will be explained using FIG. 12. The first expressions and second expressions that are related to this process of calculating are illustrated in FIG. 13.

[0094] An eighth new first hash value H*.sub.8 is calculated from an eighth changed block X*.sub.8. Furthermore, the eighth new first hash value H*.sub.8 is converted to a new first hash matrix A*.sub.8.

[0095] A second product C*.sub.8 is calculated up to the new first hash value H*.sub.8 The second product C*.sub.8 that corresponds to the eighth changed block X*.sub.8 is defined by the expression “C*.sub.8=A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A*.sub.8” that is illustrated in FIG. 13, and similarly is found by the second expression “C*.sub.8=C.sub.7A*.sub.8”.

[0096] In other words, the eighth second product C*.sub.8 is found by multiplying the seventh first product C.sub.7 by the eighth new first hash matrix A*.sub.8.

[0097] Moreover, an inverse matrix D.sub.8 that corresponds to the eighth changed block X*.sub.8 is defined by the first expression “D.sub.8=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A.sub.8).sup.−1” that is illustrated in FIG. 13, and similarly is found by the second expression “D.sub.8=C.sub.8.sup.−1”.

[0098] Processing for finding the second hash value H.sub.t in this state will be explained. A second hash matrix B in this state is defined by the first expression “B=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A*.sub.8” that is illustrated in FIG. 13, and similarly is found by the second expression “B=C*.sub.3D.sub.3C*.sub.8”.

[0099] In other words, a second hash matrix B in this state is found by multiplying the third second product C*.sub.3 by a third inverse matrix D.sub.3 and the eighth second product C*.sub.8 that corresponds to the changed block X*.sub.8. Here, the inverse matrix D.sub.8 is not used. However, the inverse matrix D.sub.8 may be used in the case of calculating the second hash matrix B later.

[0100] Next, a process of calculating a hash value in the case in which a block is added after the last block will be explained using FIG. 14. The first expressions and second expressions that are related to this process of calculating are illustrated in FIG. 15.

[0101] A first hash value H.sub.9 is calculated from the added ninth block X.sub.9. Furthermore, the first hash value H.sub.9 is converted to a first hash matrix A.sub.9.

[0102] A first product C.sub.9 is then calculated up to the first hash value H.sub.9. The first product C.sub.9 that corresponds to the ninth block X.sub.9 is defined by the first expression “C.sub.9=A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A.sub.8A.sub.9” that is illustrated in FIG. 15, and is similarly found by the second expression “C.sub.9=C.sub.8A.sub.9”. In other words, the ninth first product C.sub.9 is found by multiplying the eighth first product C.sub.8 by the first hash matrix A.sub.9.

[0103] Processing for finding the second hash value H.sub.t in this state will be explained. A second hash matrix B in this state is defined by the first expression “B=A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A.sub.8A.sub.9” that is illustrated in FIG. 15, and similarly is found by the second expression “B=C.sub.9”. In other words, the first product C.sub.9 becomes the second hash matrix B. The second hash matrix B is then converted to the second hash value H.sub.t.

[0104] As described above, as the number of changed blocks X*.sub.i increases, the number of terms of an expression for calculating the second hash matrix B increases. Therefore, the amount of computation for calculating the second hash matrix B increases. Moreover, the number of second products C*.sub.i and inverse matrices D.sub.i that are stored internally also increases. As a result, the amount of storage increases. In order to eliminate these problems, in this embodiment, the number of second products C*.sub.i and inverse matrices D.sub.i are reduced and the amount of computation is also reduced by modifying the first products C.sub.i.

[0105] FIG. 16 illustrates a process of modifying the third first product C.sub.3 in a state in which the third and sixth blocks have been changed. The first expressions and second expressions for matrices related to this process of modifying are illustrated in FIG. 17.

[0106] First, the first block of the blocks that have already been changed is specified. In this example, changed block X*.sub.3 is specified.

[0107] Then, the second product C*.sub.3 that corresponds to the changed block X*.sub.3 is copied to the first product C.sub.[3] that corresponds to the changed block X*.sub.3. In this example, brackets are attached to a number of an updated first product.

[0108] Next, the second product C*.sub.4 that corresponds to the next block X.sub.4 after the changed block X*.sub.3 is calculated based on the updated first product C.sub.[3].

[0109] Therefore, a first hash value H.sub.4 is calculated from the fourth block X.sub.4 Furthermore, the first hash value H.sub.4 is converted to a first hash matrix A.sub.4.

[0110] A second product C*.sub.4 that corresponds to the block X.sub.4 is calculated. In this example, an asterisk * is attached to the updated second product. The second product C*.sub.4 is defined by the first expression “C*.sub.4=A.sub.1A.sub.2A*.sub.3A.sub.4” that is illustrated in FIG. 17, and is similarly found by the second expression “C*.sub.4=C.sub.[3]A.sub.4”. In other words, the second product C*.sub.4 is found by multiplying the third updated first product C.sub.[3] by the first hash matrix A.sub.4.

[0111] Furthermore, an inverse matrix D.sub.4 that corresponds to the block X.sub.4 is generated. The inverse matrix D.sub.4 is defined by the first expression “D.sub.4=(A.sub.1A.sub.2A.sub.3A.sub.4).sup.−1” that is illustrated in FIG. 17, and is similarly found by the second expression “D.sub.4=C.sub.4.sup.−1”.

[0112] The second product C*.sub.3 and inverse matrix D.sub.3 that correspond to the changed block X*.sub.3 are then deleted.

[0113] The process for finding a second hash value H.sub.t in this state will be explained. A second hash matrix B in this state is defined by the first expression “B=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6A.sub.7A.sub.8” that is illustrated in FIG. 17, and similarly is found by the second expression “B=C*.sub.4D.sub.4C*.sub.6D.sub.6C.sub.8”.

[0114] In other words, the second hash matrix B in this state is found by multiplying the fourth second product C*.sub.4 by the fourth inverse matrix D.sub.4, the sixth second product C*.sub.6, the sixth inverse matrix D.sub.6, and the eighth first product C.sub.8 that corresponds to the last block. The second hash matrix B is then converted to a second hash value H.sub.t.

[0115] After that, the changed block X*.sub.3 is regarded as equivalent to an unchanged block, and the next block X.sub.4 is regarded as equivalent to a changed block. The number of changed blocks or blocks that are regarded as changed blocks are registered in an update list that will be described later. Then, the first block of the changed blocks or blocks that are regarded as changed blocks is specified and the processing for modifying the first products C.sub.i is repeated.

[0116] FIG. 18 illustrates processing for modifying the fourth first product C.sub.4 after the state illustrated in FIG. 16. The first expressions and second expressions of matrices that are related to this process of modifying are illustrated in FIG. 19.

[0117] First, the block X.sub.4 that is regarded as the changed block is specified. Then, the second product C*.sub.4 that corresponds to the block X.sub.4 is copied to the first product C.sub.[4].

[0118] Next, a second product C*.sub.5 that corresponds to the next block X.sub.5 is calculated based on the updated first product C.sub.[4]. Therefore, the first hash value H.sub.5 is calculated from the fifth block X.sub.5. Furthermore, the first hash value H.sub.5 is converted to the first hash matrix A.sub.5.

[0119] Then, a second product C*.sub.5 that corresponds to the block X.sub.5 is calculated. The second product C*.sub.5 is defined by the first expression “C*.sub.5=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5” that is illustrated in FIG. 19, and is similarly found by the second expression “C*.sub.5=C.sub.[4]A.sub.5”. In other words, the second product C*.sub.5 is found by multiplying the fourth updated first product C.sub.[4] by the first hash matrix A.sub.5.

[0120] Furthermore, an inverse matrix D.sub.5 that corresponds to the block X.sub.5 is generated. The inverse matrix D.sub.5 is defined by the first expression “D.sub.5=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5).sup.−1” that is illustrated in FIG. 19, and similarly is found by the second expression “D.sub.5=C.sub.5.sup.−1”.

[0121] The second product C*.sub.4 and the inverse matrix D.sub.4 that correspond to the block X.sub.4 are then deleted. An explanation of the process for finding a second hash value H.sub.t in this state is omitted.

[0122] FIG. 20 illustrates a process of modifying the fifth first product C.sub.5 after the state illustrated in FIG. 18. The first expressions and the second expressions for the matrices that are related to this process of modifying are illustrated in FIG. 21.

[0123] First, block X.sub.5 that is regarded as the changed block is specified. Then, a second product C*.sub.5 that corresponds to block X.sub.5 is copied to the first product C.sub.[5].

[0124] Next, a second product C*.sub.6 that corresponds to the next changed block X*.sub.6 is modified based on the updated first product C.sub.[5]. Therefore, a first hash value H*.sub.6 is calculated from the sixth block X*.sub.6. Furthermore, the first hash value H*.sub.6 is converted to a first hash matrix P′.sub.6.

[0125] A second product C**.sub.6 that corresponds to the block X*.sub.6 is then calculated. In this example, an asterisk * is further attached to updated second products. The second product C**.sub.6 is defined by the first expression “C**.sub.6=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6” that is illustrated in FIG. 21, and similarly is found by the second expression “C**.sub.6=C.sub.[5]A*.sub.6”. In other words, the second product C**.sub.6 is found by multiplying the fifth updated first product C.sub.[5] by the first hash matrix A*.sub.6.

[0126] Furthermore, an inverse matrix D.sub.6 that corresponds to the block X*.sub.6 is generated. The inverse matrix D.sub.6 is defined by the first expression “D.sub.6=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6).sup.−1” that is illustrated in FIG. 21, and is similarly found by the second expression “D.sub.6=C.sub.6.sup.−1”.

[0127] The second product C*.sub.5 and inverse matrix D.sub.5 that correspond to the block X.sub.5 are then deleted. An explanation of processing for finding a second hash value H.sub.t in this state is omitted.

[0128] FIG. 22 illustrates a process of modifying the sixth first product C.sub.6 after the state illustrated in FIG. 20. The first expressions and the second expressions that are related to this process of modifying are illustrated in FIG. 23.

[0129] First, the changed block X*.sub.6 is specified. Then, the second product C**.sub.6 that corresponds to the changed block X*.sub.6 is copied to the first product C.sub.[6].

[0130] Next, a second product C**.sub.7 that corresponds to the next block X.sub.7 is generated based on the updated first product C.sub.[6]. Therefore, a first hash value H.sub.7 is calculated from the seventh block X.sub.7. Furthermore, the first hash value H.sub.7 is converted to a first hash matrix A.sub.7.

[0131] A second product C**.sub.7 that corresponds to the block X.sub.7 is then calculated. In this example, as well as the second product C**.sub.6, two asterisks * are attached. The second product C**.sub.7 is defined by the first expression “C**.sub.7=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6A.sub.7” that is illustrated in FIG. 23, and is similarly found by the second expression “C**.sub.7=C.sub.[6]A.sub.7”. In other words, the second product C**.sub.7 is found by multiplying the sixth updated first product C.sub.[6] by the first hash matrix A.sub.7.

[0132] Furthermore, an inverse matrix D.sub.7 that corresponds to the block X.sub.7 is generated. The inverse matrix D.sub.7 is defined by the first expression “D.sub.7=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7).sup.−1” that is illustrated in FIG. 23, and is similarly found by the second expression “D.sub.7=C.sub.7.sup.−1”.

[0133] The second product C**.sub.6 and inverse matrix D.sub.6 that correspond to the block X*.sub.6 are then deleted. An explanation of the process for finding a second hash value H.sub.t in this state is omitted.

[0134] FIG. 24 illustrates a process of modifying the seventh first product C.sub.7 after the state illustrated in FIG. 22. The first expressions and the second expressions of the matrices that are related to this process of modifying are illustrated in FIG. 25.

[0135] First, the block X.sub.7 that is regarded as the changed block is specified. Then, a second product C**.sub.7 that corresponds to the block X.sub.7 is copied to the first product C.sub.[7].

[0136] Next, a second product C**.sub.8 that corresponds to the next block X.sub.8 is generated based on the updated first product C.sub.[7]. Therefore, a first hash value H.sub.8 is calculated from the eighth block X.sub.8. Furthermore, the first hash value H.sub.8 is converted to a first hash matrix A.sub.8.

[0137] A second product C**.sub.8 that corresponds to the block X.sub.8 is then calculated. The second product C**.sub.8 is defined by the first expression “C**.sub.8=A.sub.1A.sub.2A*.sub.3A.sub.4A.sub.5A*.sub.6A.sub.7A.sub.8” that is illustrated in FIG. 25, and is similarly found by the second expression “C**.sub.8=C.sub.[7]A.sub.8”. In other words, the second product C**.sub.8 is found by multiplying the seventh updated first product C.sub.[7] by the first hash matrix A.sub.8.

[0138] Furthermore, an inverse matrix D.sub.8 that corresponds to the block X.sub.8 is generated. The inverse matrix D.sub.8 is defined by the first expression “D.sub.8=(A.sub.1A.sub.2A.sub.3A.sub.4A.sub.5A.sub.6A.sub.7A.sub.8).sup.−1” that is illustrated in FIG. 25, and similarly is found by the second expression “D.sub.8=C.sub.8.sup.−1”.

[0139] The second product C**.sub.7 and inverse matrix D.sub.7 that correspond to the block X.sub.7 are then deleted. An explanation of the process for finding a second hash value H.sub.t in this state is omitted.

[0140] Next, a case where a first product is modified in a state where change blocks are in succession will be explained. FIG. 26 illustrates a process of modifying the second first product C.sub.2 in a state in which the second, third and sixth blocks have been changed. The first expressions and the second expressions of the matrices that are related to this process of modifying are illustrated in FIG. 27.

[0141] First, the first block of the blocks that have already been changed is specified. In this example, the changed block X*.sub.2 is specified.

[0142] Then, the second product C*.sub.2 that corresponds to the changed block X*.sub.2 is copied to the first product C.sub.[2] that corresponds to the changed block X*.sub.2. In this example, brackets are attached to a number of an updated first product.

[0143] Next, the second product C*.sub.3 that corresponds to the next changed block X*.sub.3 after the changed block X*.sub.2 is modified based on the updated first product C.sub.[2].

[0144] Therefore, a first hash value H*.sub.3 is calculated from the third changed block X*.sub.3. Furthermore, the first hash value H*.sub.3 is converted to a first hash matrix A*.sub.3.

[0145] A second product C**.sub.3 that corresponds to the changed block X*.sub.3 is then calculated. The second product C**.sub.3 is defined by the first expression “C**.sub.3=A.sub.1A*.sub.2A*.sub.3” that is illustrated in FIG. 27, and is similarly found by the second expression “C**.sub.3=C.sub.[2]A*.sub.3”. In other words, the second product C**.sub.3 is found by multiplying the second updated first product C.sub.[2] by the first hash matrix A*.sub.3.

[0146] Furthermore, an inverse matrix D.sub.3 that corresponds to the block X*.sub.3 is generated. The inverse matrix D.sub.3 is defined by the first expression “D.sub.3=(A.sub.1A.sub.2A.sub.3).sup.−1” that is illustrated in FIG. 27, and is similarly found by the second expression “D.sub.3=C.sub.3.sup.−1”.

[0147] The second product C*.sub.2 and the inverse matrix D.sub.2 that correspond to the changed block X*.sub.2 are then deleted. An explanation of the process for finding a second hash value H.sub.t in this state is omitted.

[0148] FIG. 28 illustrates a process of modifying the third first product C.sub.3 after the state illustrated in FIG. 26. FIG. 29 illustrates the first expressions and the second expressions for matrices related to this process of modifying.

[0149] First, the changed block X*.sub.3 is specified. The second product C**.sub.3 that corresponds to the changed block X*.sub.3 is copied to the first product C.sub.[3].

[0150] Next, a second product C**.sub.4 that corresponds to the next block X.sub.4 is generated based on the updated first product C.sub.[3]. Therefore, a first hash value H.sub.4 is calculated from the fourth block X.sub.4. Furthermore, the first hash value H.sub.4 is converted to a first hash matrix A.sub.4.

[0151] A second product C**.sub.4 that corresponds to the block X.sub.4 is then calculated. The second product C**.sub.4 is defined by the first expression “C**.sub.4=A.sub.1A*.sub.2A*.sub.3A.sub.4” that is illustrated in FIG. 29, and is similarly found by the second expression “C**.sub.4=C.sub.[3]A.sub.4”. In other words, the second product C**.sub.4 is found by multiplying the third updated first product C.sub.[3] by the first hash matrix A.sub.4.

[0152] Furthermore, an inverse matrix D.sub.4 that corresponds to the block X.sub.4 is generated. The inverse matrix D.sub.4 is defined by the first expression “D.sub.4=(A.sub.1A.sub.2A.sub.3A.sub.4).sup.−1” that is illustrated in FIG. 29, and is similarly found by the second expression “D.sub.4=C.sub.4.sup.−1”.

[0153] The second product C**.sub.3 and the inverse matrix D.sub.3 that correspond to the block X*.sub.3 are then deleted. An explanation of processing for finding a second hash value H.sub.t in this state is omitted. This completes an explanation of an outline of processing related to this embodiment.

[0154] FIG. 30 illustrates an example of module configuration of a hash generation apparatus. The hash generation apparatus has a block storage unit 3001, a total number storage unit 3003, a first hash value storage unit 3005, a first hash matrix storage unit 3007, a first product storage unit 3009, a second product storage unit 3011, an inverse matrix storage unit 3013, a second hash matrix storage unit 3015, a second hash value storage unit 3017, an update list storage unit 3019, and a calculation expression storage unit 3021.

[0155] In the following, variable symbols are omitted. The block storage unit 3001 stores each of the blocks. The total number storage unit 3003 stores the number of blocks. The first hash value storage unit 3005 stores first hash values based on each of the blocks. The first hash matrix storage unit 3007 stores first hash matrices based on the first hash values. The first product storage unit 3009 stores first products that correspond to each of the blocks. The second product storage unit 3011 stores second products that correspond to changed blocks. The inverse matrix storage unit 3013 stores inverse matrices of the first products that correspond to the changed blocks. The second hash matrix storage unit 3015 stores a second hash matrix. The second hash value storage unit 3017 stores a second hash value. The update list storage unit 3019 stores an update list in which numbers of changed blocks and numbers of blocks that are regarded as changed blocks are set. Hereinafter, changed blocks and blocks that are regarded as changed blocks will be referred to as updated blocks, and the numbers of changed blocks and the numbers of blocks that are regarded as changed blocks will be called numbers of updated blocks. The calculation expression storage unit 3021 stores matrices that correspond to terms that are included in a calculation expression in order of multiplication.

[0156] The block storage unit 3001, the total number storage unit 3003, the first hash value storage unit 3005, the first hash matrix storage unit 3007, the first product storage unit 3009, the second product storage unit 3011, the inverse matrix storage unit 3013, the second hash matrix storage unit 3015, the second hash value storage unit 3017, the update list storage unit 3019 and the calculation expression storage unit 3021 are realized using hardware resources (for example, refer to FIG. 43).

[0157] The hash generation apparatus further has an acceptance unit 3031, a division unit 3033, an initial calculation unit 3035, a change unit 3039, an addition unit 3041, a modification unit 3043, a first calculation unit 3045 and an output unit 3047.

[0158] The acceptance unit 3031 receives initial data and various instructions. The division unit 3033 divides the initial data into blocks. The initial calculation unit 3035 executes initial processing. The initial processing will be described later. The change unit 3039 executes change processing. The change processing will be described later. The addition unit 3041 executes addition processing. The addition processing will be described later. The modification unit 3043 executes modification processing. The modification processing will be described later. The first calculation unit 3045 executes calculation processing. The calculation processing will be described later. The output unit 3047 outputs a second hash value.

[0159] The aforementioned acceptance unit 3031, division unit 3033, initial calculation unit 3035, change unit 3039, addition unit 3041, modification unit 3043, first calculation unit 3045 and output unit 3047 are realized using hardware resources (for example, refer to FIG. 43) and programs that cause a processor to execute the processing that will be described below.

[0160] FIG. 31 illustrates a main processing flow. The acceptance unit 3031 accepts initial data (S3101). The initial data is an object for which a hash value is found, that is, the original data.

[0161] The division unit 3033 divides the initial data into blocks having a predetermined length (S3103). For example, the division unit 3033 divides the initial data into 64-kibibyte blocks. The divided blocks are stored in the block storage unit 3001. The division unit 3033 stores the number of blocks in the total number storage unit 3003 (S3105).

[0162] The initial calculation unit 3035 executes initial processing (S3107). In the initial processing, a second hash value is calculated based on the initial data.

[0163] FIG. 33 illustrates an example of the module construction of the initial calculation unit 3035. The initial calculation unit 3035 has a second calculation unit 3301, a first conversion unit 3303, a third calculation unit 3305 and a second conversion unit 3307.

[0164] The second calculation unit 3301 calculates first hash values based on each block. The first conversion unit 3303 converts the first hash values to first hash matrices. The third calculation unit 3305 calculates first products. The second conversion unit 3307 converts a second hash matrix to a second hash value.

[0165] The aforementioned second calculation unit 3301, first conversion unit 3303, third calculation unit 3305 and second conversion unit 3307 are realized using hardware resources (for example, refer to FIG. 43) and programs that cause a processor to execute the processing that will be described below.

[0166] FIG. 34 illustrates a processing flow of the initial processing. The initial calculation unit 3035 specifies one block in order (S3401). First, the first block X.sub.1 is specified. After that the next blocks are specified in order from X.sub.2 to X.sub.N. In the following, the block specified in S3401 is written as X.sub.i. Here, i represents a block number.

[0167] The second calculation unit 3301 calculates a first hash value H.sub.i based on the block X.sub.i (S3403). The method for calculating a hash value is based on a conventional technique.

[0168] The first conversion unit 3303 converts the first hash value H.sub.i to a first hash matrix A.sub.i (S3405). For example, the first hash value H.sub.i is divided into plural codes, and a first hash matrix A.sub.i is generated by assigning each of these codes to a predetermined element.

[0169] The third calculation unit 3305 calculates a first product C.sub.i up to that first hash matrix (S3407). More specifically, the first product C.sub.i is calculated by multiplying the first product C.sub.i-1 that corresponds to the block X.sub.i-1 before the block X.sub.i that was specified in S3401 by the first hash matrix A.sub.i. When the first block X.sub.1 is specified, the first hash matrix A.sub.1 becomes the first product C.sub.1 as it is. The third calculation unit 3305 then stores that first product C.sub.i in the first product storage unit 3009 (S3409).

[0170] The initial calculation unit 3035 determines whether or not there is an unspecified block (S3411). More specifically, when all of the blocks up to the last block X.sub.N have already been specified, then it is determined that there is not an unspecified block. When it is determined that there is an unspecified block, the processing returns to the processing illustrated in S3401, and the processing described above is repeated.

[0171] On the other hand, when it is determined that there is not an unspecified block, the second conversion unit 3307 specifies a second hash matrix B (S3413). More specifically, the first product C.sub.N that corresponds to the last block is the second hash matrix B. The second hash matrix B is stored in the second hash matrix storage unit 3015.

[0172] The second conversion unit 3307 converts the second hash matrix B to a second hash value H.sub.t (S3415). For example, the second hash value H.sub.t is generated by combining values as codes, which are represented by the elements in the second hash matrix B. The second hash value H.sub.t is stored in the second hash value storage unit 3017. After the initial processing is finished, the processing returns to the main processing of the calling source.

[0173] Here, the explanation will return to the explanation of FIG. 31. The acceptance unit 3031 determines whether or not an update instruction has been accepted (S3109). An update instruction may be an instruction resulting from user operation, or may be an instruction from another program. In this example, it is presumed that an instruction to change one block or to add one block is accepted.

[0174] When it is determined that an update instruction has been accepted, the acceptance unit 3031 determines whether or not the instruction is an instruction to change a block (S3111). When the instruction is determined to be an instruction to change a block, the change unit 3039 executes change processing (S3113). In the change processing, internal data is updated according to the block change.

[0175] FIG. 35 illustrates an example of module construction of the change unit 3039. The change unit 3039 has a fourth calculation unit 3501, a third conversion unit 3503, a fifth calculation unit 3505 and a sixth calculation unit 3507.

[0176] The fourth calculation unit 3501 calculates a first hash value based on an updated block. The third conversion unit 3503 converts the first hash value to a first hash matrix. The fifth calculation unit 3505 calculates a second product. The sixth calculation unit 3507 calculates an inverse matrix of the first product.

[0177] The aforementioned fourth calculation unit 3501, third conversion unit 3503, fifth calculation unit 3505 and sixth calculation unit 3507 are realized by using hardware resources (for example, refer to FIG. 43) and programs for causing a processor to execute the processing described below.

[0178] FIG. 36 illustrates a processing flow of the change processing. The change unit 3039 changes an existing block (S3601). Here, the original block before being changed is represented as X.sub.M, and the updated block after being changed is represented as X*.sub.M.

[0179] The fourth calculation unit 3501 calculates a first hash value H*.sub.M based on the updated block X*.sub.M (S3603). The method for calculating the hash value is based on a conventional technique.

[0180] The third conversion unit 3503 converts the first hash value H*.sub.M to a first hash matrix A*.sub.M (S3605). For example, the first hash matrix A*.sub.M is generated by dividing the first hash value H*.sub.M into plural codes and assigning each of those codes to a predetermined elements.

[0181] The fifth calculation unit 3505 calculates a second product C*.sub.M up to the first hash matrix A*.sub.M (S3607). The second product C*.sub.M is found by multiplying the first product C.sub.M−1, which was obtained by being lastly multiplied the hash matrix A.sub.M−1 that is based on the block X.sub.M−1 just before the updated block X*.sub.M, by the first hash matrix A*.sub.M. Then, the fifth calculation unit 3505 stores that second product C*.sub.M in the second product storage unit 3011 (S3609).

[0182] The sixth calculation unit 3507 calculates an inverse matrix D.sub.M of the first product C.sub.M up to the original first hash matrix A.sub.M that is based on the original block X.sub.M (S3611). Then, the sixth calculation unit 3507 stores that inverse matrix D.sub.M in the inverse matrix storage unit 3013 (S3613).

[0183] The change unit 3039 adds the number M of the updated block to the update list (S3615). After the change processing has ended, the processing returns to the main processing of the calling source.

[0184] Here, the explanation will return to the explanation of FIG. 31. When it is determined in S3111 that the instruction is not an instruction to change a block, or in other words, when the instruction is an instruction to add a block, the addition unit 3041 executes addition processing (S3115). In the addition processing, internal data is updated according to the addition of a block.

[0185] FIG. 37 illustrates an example of module configuration of the addition unit 3041. The addition unit 3041 has a seventh calculation unit 3701, a fourth conversion unit 3703 and an eighth calculation unit 3705.

[0186] The seventh calculation unit 3701 calculates a first hash value based on a newly added block. The fourth conversion unit 3703 converts the first hash value to a first hash matrix. The eighth calculation unit 3705 calculates a first product.

[0187] The aforementioned seventh calculation unit 3701, fourth conversion unit 3703 and eighth calculation unit 3705 are realized by hardware resources (for example, refer to FIG. 43), and programs that cause a processor to execute the processing described below.

[0188] FIG. 38 illustrates a processing flow of the addition processing. The addition unit 3041 adds a new block X.sub.N+1 after the last block X.sub.N (S3801).

[0189] The seventh calculation unit 3701 calculates a first hash value H.sub.N+1 based on the new block X.sub.N+1 (S3803). The method for calculating the hash value is based on a conventional technique.

[0190] The fourth conversion unit 3703 converts that first hash value H.sub.N+1 to a first hash matrix A.sub.N+1 (S3805).

[0191] The eighth calculation unit 3705 calculates a first product C.sub.N+1 up to the first hash matrix A.sub.N+1 (S3807). The first product C.sub.N+1 is found by multiplying the first product C.sub.N, which was obtained by being lastly multiplied with the hash matrix A.sub.N that is based on the last block X.sub.N, by the first hash matrix A.sub.N+1. Then the eighth calculation unit 3705 stores that first product C.sub.N+1 in the first product storage unit 3009 (S3809).

[0192] The addition unit 3041 updates the number of blocks (S3811). More specifically, 1 is added to the number of blocks. After the addition processing has ended, the processing returns to the main processing of the calling source.

[0193] Here, the explanation returns to the explanation of FIG. 31. After the change processing or addition processing has ended, the first calculation unit 3045 executes calculation processing (S3116).

[0194] FIG. 39 illustrates a processing flow of the calculation processing. The first calculation unit 3045 determines whether or not numbers of updated blocks (hereinafter, referred to as update block numbers) are set in the update list (S3901). When it is determined that update block numbers are not set in the update list, the calculation processing ends, and the processing returns to the main processing of the calling source.

[0195] However, when it is determined that update block numbers are set in the update list, the first calculation unit 3045 specifies, in the update list, an update block number in order from the smallest (S3903). Here, the specified update block number is written as j.

[0196] The first calculation unit 3045 adds a second product C*.sub.j that corresponds to the update block number j to a term in the calculation expression (S3905). That term is then stored in the calculation expression storage unit 3021.

[0197] The first calculation unit 3045 determines whether or not the update block number j is the last block number N (S3907). When it is determined that the update block number j is the last block number N, the first calculation unit 3045 calculates a second hash matrix B according to the calculation expression (S3909). The second hash matrix B is stored in the second hash matrix storage unit 3015.

[0198] The first calculation unit 3045 converts the second hash matrix B to a second hash value H.sub.t (S3911). For example, the second hash value H.sub.t is generated by combining values as codes, which are represented by the elements of the second hash matrix B. The second hash value H.sub.t is stored in the second hash value storage unit 3017. The calculation processing then ends, and the processing returns to the main processing of the calling source.

[0199] In S3907, when it is determined that the update block number j that was specified in S3903 is not the number N of the last block, the first calculation unit 3045 adds the inverse matrix D.sub.j that corresponds to the update block number j to a term of the calculation expression (S3913).

[0200] The first calculation unit 3045 determines whether or not there is an unspecified update block numbers in the update list (S3915). When it is determined that there is an unspecified update block number in the update list, the processing returns to the processing of S3903, and the processing described above is repeated.

[0201] However, when it is determined that there are no unspecified update block numbers in the update list, the first calculation unit 3045 adds the first product C.sub.N that corresponds to the number N of the last block to the terms of the calculation expression (S3917).

[0202] The first calculation unit 3045 calculates a second hash matrix B according to the calculation expression (S3919). The second hash matrix B is stored in the second hash matrix storage unit 3015.

[0203] The first calculation unit 3045 converts the second hash matrix B to a second hash value H.sub.t (S3921). The second hash value H.sub.t is stored in the second hash value storage unit 3017. After the calculation processing ends, the processing returns to the main processing of the calling source.

[0204] Here, the explanation will return to the explanation of FIG. 31. In S3109, when it is determined that an update instruction has not been accepted, the acceptance unit 3031 determines whether or not a modification instruction has been received (S3117). A modification instruction may be an instruction according to user operation, or may be an instruction from another program. When it is determined that a modification instruction has been accepted, the modification unit 3043 executes modification processing (S3119). In the modification processing, the first product of an updated block is modified.

[0205] FIG. 40 illustrates an example of the module configuration of the modification unit 3043. The modification unit 3043 has an update unit 4001, a deletion unit 4003, a ninth calculation unit 4005, a fifth conversion unit 4007, a tenth calculation unit 4009 and an eleventh calculation unit 4011.

[0206] The update unit 4001 updates a first product. The deletion unit 4003 deletes update block numbers from the update list. The ninth calculation unit 4005 calculates a first hash value. The fifth conversion unit 4007 converts the first hash value to a first hash matrix. The tenth calculation unit 4009 calculates a second product. The eleventh calculation unit 4011 calculates an inverse matrix of the first product.

[0207] The aforementioned update unit 4001, deletion unit 4003, ninth calculation unit 4005, fifth conversion unit 4007, tenth calculation unit 4009 and eleventh calculation unit 4011 are realized by hardware resources (for example, refer to FIG. 43) and programs that cause a processor to execute the processing described below.

[0208] FIG. 41 illustrates a processing flow of the modification processing. The modification unit 3043 specifies the smallest update block number in the update list (S4101). Here, the specified update block number is represented as j.

[0209] The update unit 4001 updates the first product C.sub.j that corresponds to the update block number j (S4103). More specifically the second product C*.sub.j that corresponds to the update block number j is copied to the first product. Here, an updated first product is written as C.sub.[j].

[0210] The deletion unit 4003 determines whether or not the update block number j is the number N of the last block (S4105).

[0211] When it is determined that the update block number j is the number N of the last block, the deletion unit 4003 deletes that update block number j from the update list (S4107). Then, the modification processing ends and the processing returns to the main processing of the calling source.

[0212] However, when it is determined that the update block number j is not the number N of the last block, the ninth calculation unit 4005 specifies the block X.sub.j+1 (in the case that the block has been changed, the changed block X*.sub.j+1) using the next number j+1 subsequent to the update block number j (S4109).

[0213] The ninth calculation unit 4005 calculates a first hash value H.sub.j+1 (or first hash value H*.sub.j+1) based on the block X.sub.j+1 (or changed block X*.sub.j+1) that was specified in S4109 (S4111). The method for calculating the hash value is based on a conventional technique.

[0214] The fifth conversion unit 4007 converts the first hash value H.sub.j+1 (or first hash value H*.sub.j+1) to a first hash matrix A.sub.j+1 (or first hash matrix A*.sub.j+1) (S4113).

[0215] The tenth calculation unit 4009 calculates a second product C*.sub.j+1 (or second product C**.sub.j+1) up to the first hash matrix A.sub.j+1 (or first hash matrix A*.sub.j+1) (S4115). The second product C*.sub.j+1 (or second product C**.sub.j+1) is found by multiplying the first product C*.sub.j that corresponds to the update block number j that was specified in S4101 by the first hash matrix A.sub.j+1 (or first hash matrix A*.sub.j+1).

[0216] The tenth calculation unit 4009 stores the calculated second product C*.sub.j+1 (or second product C**.sub.j+1) in the second product storage unit 3011 (S4117). Then processing shifts to the processing of S4201 illustrated in FIG. 42 by way of terminal C.

[0217] The eleventh calculation unit 4011 calculates an inverse matrix D.sub.j+1 of the first product C.sub.j+1 up to the original first hash matrix A.sub.j+1 based on the original block X.sub.j+1 that corresponds to the next number j+1 of the smallest update block number j that was specified in S4101 (S4201). The eleventh calculation unit 4011 then stores that inverse matrix D.sub.j+1 in the inverse matrix storage unit 3013 (S4203).

[0218] The deletion unit 4003 deletes the second product and the inverse matrix D.sub.j that correspond to the smallest update block number j (S4205). The modification unit 3043 adds 1 to the update block number j in the update list (S4207). In other words, the smallest update block number j in the update list is changed into update block number j+1.

[0219] The modification unit 3043 determines whether or not to interrupt the modification processing (S4209). For example, the modification processing may be interrupted when the smallest update block number j reaches a predetermined number. The modification unit 3043 may also determine whether or not to interrupt the modification processing based on the processing load of the hash generation apparatus. It may also be possible to interrupt the modification processing when an interrupt instruction according to user operation is accepted. Moreover, it is also possible to interrupt the modification processing when an interrupt instruction is accepted from another program. When it is determined to interrupt the modification processing, the modification processing ends and the processing returns to the main processing of the calling source.

[0220] However, when it is determined not to interrupt the modification processing, the processing returns to the processing of S4101 illustrated in FIG. 41 by way of terminal D.

[0221] Here, the explanation will return to the explanation of FIG. 31. After the modification processing ends, the processing returns to the processing illustrated in S3109, and the processing described above is repeated.

[0222] When it is determined in S3117 that a modification instruction was not accepted, the processing shifts to the processing of S3201 illustrated in FIG. 32 by way of terminal A. The acceptance unit 3031 determines whether or not an output instruction has been accepted (S3201). An output instruction may be an instruction that is according to user operation, or may be an instruction from a program.

[0223] When it is determined that an output instruction was accepted, the output unit 3047 outputs the second hash value H.sub.t that is stored in the second hash value storage unit 3017 (S3203). Then, the processing returns to the processing of S3109 illustrated in FIG. 31 by way of terminal B.

[0224] However, when it is determined that an output instruction has not been accepted, the acceptance unit 3031 determines whether or not an end instruction has been received (S3205). An end instruction may be an instruction according to user operation, or may also be an instruction from a program. When it is determined that an end instruction has not been accepted, the processing returns to the processing of S3109 illustrated in FIG. 31 by way of terminal B. However, when it is determined that an end instruction has been accepted, the main processing ends.

[0225] It may also be possible to omit the calculation processing that is illustrated in S3116 in FIG. 31, and execute the calculation processing before S3203 in FIG. 32.

[0226] In the following, an additional explanation about calculation will be given. It may also be possible to convert the codes that were divided from the hash value H.sub.i to a predetermined remainder. For example, the divided code is divided by 65521 and a remainder is found. The number 65521 is the largest prime number that is less than or equal to 65535. In this way, it is possible to apply the value of the code to a predetermined bit width.

[0227] Division for finding an inverse matrix is defined as described below, for example. Here, the value ‘m’ is a prime number (for example, 65521). Let ‘a’ be an integer that is equal to or greater than 0 and less than m. Let ‘b’ be an integer that is equal to or greater than 1 and less than m. Under these conditions, of the integers ‘c’ that satisfy a=b*c, those which are greater than or equal to 0 and smaller than m are taken as quotients.

[0228] When all of the elements that are included in a matrix are 0, the inverse matrix of that matrix is not determined. Therefore, when finding the hash matrix A.sub.i, in a case when all of the elements that are included in the matrix obtained by converting the hash value H.sub.i are 0, it may also be possible to find the hash matrix A.sub.i by adding a predetermined matrix (for example, a unit matrix) to that matrix.

[0229] In this embodiment, the products of matrices are found as described above. When finding products of matrices, expressions in which order of terms are different are not always equivalent. Therefore, in the expressions for finding products described above, not only the terms themselves, but also order of the terms are significant. For example, when the order of a block X.sub.i is changed, the hash value H.sub.t will be different.

[0230] In the example described above, an inverse matrix D is stored. In this way, an amount of calculation in the calculation processing is reduced. However, it is also possible not to store the inverse matrix D. In that case, the inverse matrix storage unit 3013 does not need to be provided. In the change processing, the processing of S3611 and S3613 depicted in FIG. 36 may be omitted. In the modification processing, it may also be possible to omit the processing of S4201 and S4203 illustrated in FIG. 42. Similarly, it may also be possible to omit the deletion processing for deleting the inverse matrix D.sub.j in S4205. Moreover, in the calculation processing, in S3913 illustrated in FIG. 39, it may also be possible to calculate the inverse matrix D.sub.j of the first product C.sub.j that corresponds to the update block number. In this way, the amount of data that is stored may be reduced.

[0231] According to the present embodiment, it is possible to further reduce an amount of computation required for recalculating the hash matrix and the hash value.

[0232] Moreover, even though plural portions in the original data have been changed, it is possible to further reduce an amount of computation that is required for recalculating the hash matrix and the hash value.

[0233] Furthermore, even in a case in which many portions in the original data have been changed, it may also be possible to further reduce an amount of calculation that is required for recalculating the hash matrix and the hash value. There is also a good aspect in that an amount of internal data that is stored is reduced.

[0234] Although the embodiment of this invention was explained above, this invention is not limited to those. For example, aforementioned functional block configuration does not always correspond to actual program module configuration.

[0235] Moreover, the aforementioned configuration of each storage area is a mere example, and may be changed. Furthermore, as for the processing flow, as long as the processing results do not change, the turns of the steps may be exchanged or the steps may be executed in parallel.

[0236] In addition, the aforementioned hash generation apparatus is a computer apparatus as illustrated in FIG. 43. That is, a memory 2501, a CPU 2503 (central processing unit), a HDD (hard disk drive) 2505, a display controller 2507 connected to a display device 2509, a drive device 2513 for a removable disk 2511, an input unit 2515, and a communication controller 2517 for connection with a network are connected through a bus 2519 as illustrated in FIG. 43. An operating system (OS) and an application program for carrying out the foregoing processing in the embodiment, are stored in the HDD 2505, and when executed by the CPU 2503, they are read out from the HDD 2505 to the memory 2501. As the need arises, the CPU 2503 controls the display controller 2507, the communication controller 2517, and the drive device 2513, and causes them to perform predetermined operations. Moreover, intermediate processing data is stored in the memory 2501, and if necessary, it is stored in the HDD 2505. In those embodiments of this invention, the application program to realize the aforementioned processing is stored in the computer-readable, non-transitory removable disk 2511 and distributed, and then it is installed into the HDD 2505 from the drive device 2513. It may be installed into the HDD 2505 via the network such as the Internet and the communication controller 2517. In the computer apparatus as stated above, the hardware such as the CPU 2503 and the memory 2501, the OS and the application programs systematically cooperate with each other, so that various functions as described above in details are realized.

[0237] The aforementioned embodiment is summarized as follows:

[0238] An information processing apparatus relating to this embodiment includes: a memory and a processor coupled to the memory. And the processor is configured to: (A) calculate a first hash matrix for identifying original data, which corresponds to a first product multiplied by a partial hash matrix that is based on a last block of plural blocks divided from the original data, from a second product for each of blocks other than the last block, the second product for each of blocks other than the last block being stored in the memory and being calculated by multiplying from a partial hash matrix that is based on a first block of the plural blocks up to a partial hash matrix that is based on the block; and (B) calculate a second hash matrix for identifying changed data, by multiplying a third product of a fourth product multiplied lastly by a partial hash matrix that is based on a block immediately before a changed block and a partial hash matrix that is based on the changed block by an inverse matrix of a fifth product multiplied lastly by a partial hash matrix that is based on an unchanged original block and a sixth product multiplied lastly by a partial hash matrix that is based on the last block, upon detecting that a part of the original data has been changed.

[0239] In this way, it becomes possible to reduce an amount of computation required for recalculating hash data.

[0240] The processor may be configured to calculate the second hash matrix by multiplying, for each of changed blocks and in order from a head of changed blocks, the third product by the inverse matrix of the fifth product and the sixth product, upon detecting that a number of the changed blocks is more than 1.

[0241] In this way, even when plural portions of the original data are changed, it becomes possible to further reduce the amount of computation required for recalculating the hash data.

[0242] Furthermore, the processor may further be configured to update the fifth product by the third product to increment a block number for specifying the changed block, and the processor may be configured to set a block specified by the block number as the changed block.

[0243] In this way, even when many parts of the original data are changed, it is possible to further reduce the amount of computation required for recalculating the hash data. There is also a good aspect in that an amount of internal data that is stored is reduced.

[0244] Incidentally, it is possible to create a program causing a computer to execute the aforementioned processing, and such a program is stored in a computer readable storage medium or storage device such as a flexible disk, CD-ROM, DVD-ROM, magneto-optic disk, a semiconductor memory, and hard disk. In addition, the intermediate processing result is temporarily stored in a storage device such as a main memory or the like.

[0245] All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present inventions have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.