JP2004336702A - Data originality securing method and system, and program for securing data originality - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a data originality securing method and system, in which data can be preserved while more easily securing its originality and a program for securing data originality. <P>SOLUTION: A data originality securing system 1 for preserving source data B while securing its originality includes a divided data generating part 13 which uses a secret dispersion method to divide the source data B into a plurality of divided data D(1)-D(4) with which the source data B can be restored, and a plurality of preservation servers 3a1-3a4 which are independent in a hardware manner, for respectively storing the divided plurality of data D(1)-D(4). <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to a data originality securing method and system for securing and storing data originality, and a data originality securing program.

  With the development of IT, opportunities to connect one's own terminal to a communication network such as the Internet and to communicate data to another terminal connected to this communication network via the communication network have been greatly increased.

  At this time, since the terminal is connected to the communication network, a malicious third party (such as a hacker) accesses the terminal via the terminal of the third party connected to the communication network, and is stored in the terminal. There is a risk that the data may be falsified, and it is necessary to ensure the originality of the falsified data (the contents must be complete without any falsification by intention or negligence).

  In this regard, conventionally, a technique has been introduced in which falsification of data can be detected using an electronic signature to ensure originality (for example, see Non-Patent Document 1).

  That is, according to the originality securing method using the digital signature technology, Mr. A of the data transmission source receives an electronic certificate containing a public key that has been previously guaranteed by a certification authority (CA).

  Then, Mr. A creates an electronic signature for the data to be transmitted (also referred to as the data body), and transmits data including the created electronic signature (data body + electronic signature + electronic certificate) to Mr. B.

Mr. B compares the hash value generated from the data itself in the received data with the value obtained by decrypting the electronic signature with the public key included in Mr. A's digital certificate received from Mr. A It is determined whether or not the data has been falsified.
"PKI-Related Technology Description", [online], December 12, 2002, Information Processing Promotion Agency of Japan, [Search April 11, 2003], Internet <URL: http: //www.ipa.go. jp / security / pki / index.html>

  However, according to the originality securing method using the digital signature technology, when the data received by Mr. B is stored for a long period of time, the data may be falsified due to the compromise of the secret key or the like.

  Therefore, in the method of securing originality using the digital signature technology, the expiration date is set in advance for the electronic certificate issued by the certificate authority, and Mr. A renews the secret key and public key before the expiration date. It is necessary to generate an electronic certificate for the public key from a certificate authority, and to create data with an electronic signature again using a new private key.

  However, the process of re-issuing a digital certificate from a certificate authority based on the expiration date of the above-described digital certificate and the process of creating data with a digital signature using a new private key take a lot of trouble and time. The above-described process of re-issuing the electronic certificate and the process of creating data with an electronic signature must be repeated each time, and there has been a long-awaited need for a method of storing data while ensuring its originality more easily.

  The present invention has been made in view of the above-described circumstances, and provides a data originality securing method and system, and a data originality securing program capable of easily securing and storing the originality of data. Its purpose is to provide.

  In order to achieve the above-mentioned object, the present invention provides a data originality securing system for storing data while securing its originality, as described in claim 1, wherein the data is stored using a secret sharing method. And a plurality of hardware-independent storage units for respectively storing the plurality of divided data, the plurality of divided data being capable of restoring the divided data. .

  In the invention described in claim 2, the data division unit includes an identification data generation unit that generates, from the data main body whose originality is to be secured, identification data capable of uniquely identifying the data main body; A dividing unit for dividing the data combined with the data body by using a secret sharing method.

  According to a third aspect of the present invention, the identification data generation unit includes a generation unit that generates a hash value of the data body using a predetermined hash function as the identification data.

  According to a fourth aspect of the present invention, the data division unit generates division identification data capable of uniquely identifying the entire data from the entire data obtained by adding management information relating to the data division to each divided data. The gist is that the plurality of storage units store the divided data, management information on the data division, and the division identification data, respectively.

  The invention according to claim 5, wherein the plurality of divided data are respectively read from the plurality of storage units, and a data restoration unit that respectively restores the data body and the identification data from the read plurality of divided data by a secret sharing method. And a confirmation unit for regenerating the identification data from the restored data body and confirming whether or not the regenerated identification data matches the restored identification data. .

  In the invention described in claim 6, the divided data, the management information relating to the data division, and the division identification data are respectively read from the plurality of storage units, and the data body and the divided data are read out from the read plurality of divided data by a secret sharing method. A data restoration unit for restoring the identification data, and a step of regenerating the identification data from the restored data body, and confirming whether the regenerated identification data matches the restored identification data. (1) regenerating the division identification data from the entire data obtained by combining the read division data and the management information relating to the data division with respect to each of the plurality of division data; And a second confirmation unit that confirms whether the read division identification data matches. .

  In the invention described in claim 7, the plurality of divided data are read from the plurality of storage units, and the read plurality of divided data are combined in different combinations to restore a plurality of data. The gist of the present invention is that a restoration confirmation unit for confirming whether or not they match each other is further provided.

  The invention according to claim 8 is a data originality securing method for storing data while securing its originality, wherein the data is divided into a plurality of divided data which can be restored using a secret sharing method. The gist of the present invention is to include a step of dividing and a step of storing the plurality of divided data in a plurality of storage devices independent of hardware.

  In the invention described in claim 9, the dividing step includes a step of generating, from the data main body whose originality is to be secured, identification data capable of uniquely identifying the data main body, a step of generating the identification data and the data main body. And dividing the data obtained by combining the data by using a secret sharing method.

  An invention according to claim 10 is a computer-readable program for securing data originality for securing and storing the originality of data, wherein the computer uses the secret sharing method to store the data. And a storage process of storing the divided data in a plurality of hardware-independent storage devices communicable with the computer. Are executed.

  The invention according to claim 11, wherein the division processing includes: identification data generation processing for generating identification data that can uniquely identify the data main body from the data main body for which originality is to be secured; And a division process for dividing the data combined with the data body by using a secret sharing method.

  The gist of the invention described in claim 12 is that the identification data generation processing generates a hash value of the data body as the identification data using a predetermined hash function.

  According to a thirteenth aspect of the present invention, in the data division processing, division identification data capable of uniquely identifying the entire data is generated from the entire data obtained by adding management information relating to the data division to each divided data. The gist of the storage process is to store the divided data, the management information on the data division, and the division identification data in the plurality of storage devices.

  The invention according to claim 14, wherein the plurality of divided data are respectively read from the plurality of storage devices, and the data main body and the identification data are respectively restored from the read plurality of divided data by a secret sharing method. Regenerating the identification data from the restored data body, and confirming whether the regenerated identification data matches the restored identification data. Make a summary.

  The invention according to claim 15 is characterized in that the divided data, the management information relating to the data division, and the division identification data are respectively read from the plurality of storage devices, and the data body and the divided data are read from the read plurality of divided data by a secret sharing method. A data restoration process for restoring the identification data, and a step of regenerating the identification data from the restored data body and checking whether the regenerated identification data matches the restored identification data. (1) re-generating the division identification data from the entire data obtained by combining the read division data and the management information relating to the data division with respect to each of the plurality of division data; And a second confirmation process for confirming whether or not the read division identification data matches. And summarized in that to execute the over data.

  In the invention described in claim 16, the plurality of divided data are read from the plurality of storage devices, and the read plurality of divided data are combined in different combinations to restore a plurality of data. The gist of the present invention is to cause the computer to further execute a restoration confirmation process for confirming whether or not they match.

  According to the data originality securing method and system and the data originality securing program according to the present invention, data is divided into a plurality of divided data by using a secret sharing method, and a plurality of storage units independent of hardware are provided. Since each of the data is stored in the (storage device), even if at least a part of the data is tampered with, it is possible to easily confirm whether the divided data has been tampered with from the divided data including the tampered data. .

  As a result, even if the data is stored for a long period of time, the data can be easily stored without repeating the process of re-issuing the digital certificate and the process of creating the data with the digital signature as in the case of the digital signature. can do.

  An embodiment of a data originality securing method and system and a data originality securing program according to the present invention will be described with reference to the accompanying drawings.

(First Embodiment)
FIG. 1 is a block diagram showing a schematic configuration of a data originality securing system 1 according to the first embodiment of the present invention.

  As shown in FIG. 1, a data originality assurance system 1 can communicate with a client computer (hereinafter, simply referred to as a client) 2 that can connect to and communicate with a communication network N such as the Internet. And a plurality of (in this embodiment, four) data storage server computers (hereinafter simply referred to as storage servers) 3a1 to 3a4 that are hardware independent of each other.

  The client 2 includes a CPU as an arithmetic processing unit, an interface connected to the CPU and enabling communication between the CPU and the network N, an input unit for data input connected to the CPU, and a memory 10 connected to the CPU. Each has it.

  The memory 10 stores data to be stored while maintaining originality {for example, M (M is a natural number) bytes of digital data; hereinafter, also referred to as original data} B. The memory 10 is readable by the client 2 (its CPU), and is a data for causing the client 2 (its CPU) to execute an originality securing process (data storage process) shown in FIGS. 2 and 3 described later. An originality securing program P is installed.

  Note that the data originality securing program P is mounted on various recording media such as a magnetic memory and a semiconductor memory, and is read from the recording medium by the client 2 and loaded into the memory 10 as necessary. It is also possible.

  The client 2 includes, as functions implemented by the data originality securing program P, a hash value generation unit 11 that generates, for example, a hash value that can uniquely identify the original data B from the original data B stored in the memory 10. , The original data B and the data including the hash value H are divided using a secret sharing scheme to generate divided data D (1) to D (4) (the number of divisions is 4 in the present embodiment). A generation unit 13, an original data restoration unit 15 that generates original data B and a hash value H from the divided data D (1) to D (4), and the divided data D (1) to D (4) via a network N And a communication unit 17 for performing communication.

  Each of the storage servers 3a1-3a4 includes a CPU serving as an arithmetic processing unit, an interface connected to the CPU and enabling communication between the CPU and the network N, an input unit for data input connected to the CPU, and connected to the CPU. And a storage device such as a hard disk.

  Next, the overall processing of the data originality securing system 1 according to the present embodiment will be described.

  As shown in FIGS. 2 and 3, the client 2 operates in accordance with the data originality securing program P, and as a function of the hash value generating unit 11, the client 2 who wants to secure the originality stored in the memory 10 and store it. The data B is read from the memory 10, and the read original data B is generated as a hash value H of the original data B using a predetermined hash function (step S1).

  The hash value H has such a property that if the original data B is changed even by one bit, the hash value H shows a completely different value, that is, the original data B can be uniquely identified.

  Next, the client 2 divides the original data B including the generated hash value H into four data (divided data) D (1) to D (4) by using a secret sharing method as a function of the divided data generation unit 13. (Step S2).

  Hereinafter, the process of generating the divided data D (1) to D (4) based on the secret sharing scheme in step S2 will be described in detail.

For example, Shamir's secret sharing method ｛(k, n) threshold method based on a second-order polynomial F (x) = ax ² + bx + B (mod p; representing the remainder when divided by p); Let n be 4 and let k be 3 representing the number that can be restored. Here, B is original data, and F (x) is divided data. a, b, and p are arbitrarily determined when dividing the original data B. Here, p is a prime number larger than a, b, and B.

  At this time, the divided data F (1) to F (4) {corresponding to the divided data D (1) to D (4)} obtained by the divided data generation processing of the client 2 are represented by the following equations (1) to (4). It is created as follows.

F (1) = a + b + B (mod p) (1)
F (2) = 4a + 2b + B (mod p) (2)
F (3) = 9a + 3b + B (mod p) (3)
F (4) = 16a + 4b + B (mod p) (4)
If k = 3 or more divided data {for example, F (1), F (2), F (4)} among the divided data F (1) to F (4) is collected, the divided data F (1) ) = A + b + B (mod p) (1)
F (2) = 4a + 2b + B (mod p) (2)
F (4) = 16a + 4b + B (mod p) (4)
And the original data B can be obtained.

  And even if the divided data of k-1 or less are collected, the original data B cannot be restored.

  When the original data B is a long data string, the client 2 sequentially creates F (1) to F (4) for each byte from the head of the original data B, for example, and creates the divided data D (1). (F (1)) to D (4) (F (4)) are created.

  Then, as a function of the communication unit 17, the client 2 transmits the created divided data D (1) to D (4) to the storage servers 3a1 to 3a4 via the network N (step S3).

  Each of the storage servers 3a1 to 3a4 stores the divided data D (1) to D (4) transmitted via the network N in a storage device such as a hard disk (step S5).

  In this way, the original data B can be stored in the storage servers 3a1 to 3a4 as the divided data D (1) to D (4) including the hash value H.

  Next, when checking whether or not the divided data D (1) to D (4) stored in the storage servers 3a1 to 3a4 have been falsified, the client 2 sets the divided data D (1) to D (4). Are transmitted to the storage servers 3a1-3a4 (step S10).

  Each of the storage servers 3a1 to 3a4 reads out the divided data D (1) to D (4) stored in the storage device such as the hard disk from the storage device in response to the transmitted download request. The divided data D (1) to D (4) are transmitted to the client 2 via the network N (step S11).

  The client 2 operates according to the data originality securing program P, receives and receives the divided data D (1) to D (4) transmitted via the network N as a function of the original data restoring unit 15. The original data B1 and the hash value H1 are respectively restored by the secret sharing method based on the divided data D (1) to D (4) (step S12).

  Next, the client 2 regenerates the hash value H2 from the restored original data B1 and compares the regenerated hash value H2 with the restored hash value H1 as a function of the original data restoration unit 15 to determine whether or not they match. Is confirmed (step S13).

  The processing of steps S12 and S13 will be specifically described.

  For example, among the divided data F (1), F (2), F (3), and F (4), some of the divided data is falsified. For example, F (2) to F (4) are Fa (2). ) To Fa (4).

At this time, the client 2 obtains the following equation: F (1) = a + b + B (mod p) (1)
Fa (2) = 4a + 2b + B (mod p) (2)
Fa (3) = 9a + 3b + B (mod p) (3)
Fa (4) = 16a + 4b + B (mod p) (4)
, The original data B including the hash value H is restored by combining at least three expressions.

  However, since the divided data F (2) to F (4) have been falsified into the divided data Fa (2) to Fa (4), even if the divided data Fa (2) to Fa (4) are simultaneously Since the restored original data B1 is different from the original data B whose originality is to be secured, the hash value H2 regenerated from the original data B1 is also different from the restored hash value H1. As a result, the client 2 can confirm that at least a part of the divided data D (1) to D (4) stored in the storage servers 3a1 to 3a4 has been falsified.

  As described above, according to the present embodiment, the original data B is divided into a plurality of divided data D (1) to D (4) using the secret sharing method and stored in the storage servers 3a1 to 3a4, respectively. Therefore, even if at least a part of the divided data D (1) to D (4) is falsified, the divided data D (1) to D (4) including the falsified data is converted from the divided data D (1) to D (4). It is possible to easily check whether (1) to D (4) have been tampered with.

  As a result, for example, even when the original data B is stored for a long period of time, the original data B can be easily saved without repeating the process of reissuing the electronic certificate and the process of creating the data with the electronic signature as in the case of the electronic signature. Data B can be stored.

  According to the present embodiment, since the original data B is divided into divided data D (1) to D (4) and stored in the storage servers 3a1 to 3a4, for example, the divided data D (1) to D (4) are stored. Even if one of the divided data in (4) is falsified, the original data B can be restored using the remaining divided data.

  As a result, the originality of the original data B can be secured more reliably.

(Second embodiment)
FIG. 4 is a schematic flowchart showing an example of the originality securing process based on the data originality securing program in the data originality securing system according to the second embodiment of the present invention. Note that the configuration of the data originality securing system in the present embodiment is different from the content of the data originality securing program and the processing of the client, and the other configurations are substantially the same as those shown in FIG. , And the description is omitted.

  In the present embodiment, as a function of the divided data generation unit 13, the client 2 reads, from the memory 10, the original data B stored in the memory 10 and whose originality is desired to be stored, and keeps the read original data B secret. The data is divided into four data (divided data) D (1) to D (4) using the distribution method (step S21).

  Note that the processing in step S21 is substantially equivalent to the processing in step S2.

  Next, as a function of the communication unit 17, the client 2 transmits the created divided data D (1) to D (4) to the storage servers 3a1 to 3a4 via the network N (step S22).

  Each of the storage servers 3a1-3a4 stores the divided data D (1) -D (4) transmitted via the network N in a storage device such as a hard disk (step S23).

  In this way, the original data B can be stored in the storage servers 3a1-3a4 as the divided data D (1) to D (4).

  Next, when checking whether or not the divided data D (1) to D (4) stored in the storage servers 3a1 to 3a4 have been falsified, the client 2 sets the divided data D (1) to D (4). Are transmitted to the storage servers 3a1-3a4, respectively (step S30).

  Each of the storage servers 3a1 to 3a4 reads out the divided data D (1) to D (4) stored in a storage device such as a hard disk from the storage device in response to the transmitted download request. The divided data D (1) to D (4) are transmitted to the client 2 via the network N (step S31).

  The client 2 receives the divided data D (1) to D (4) transmitted via the network N as a function of the original data restoration unit 15, and receives the received divided data D (1) to D (4). Are combined in different combinations by the secret sharing method to restore a plurality of original data B1 to Bm (m = 2 in the present embodiment), and confirm whether or not the restored original data B1 to B2 match each other ( Step S32).

  The processing in step S32 will be specifically described.

  The client 2 uses, for example, a predetermined combination, for example, the divided data F (1) to F (3) among the divided data F (1), F (2), F (3), and F (4). The original data B1 is restored by the secret sharing method, and then the original data B2 is restored by the secret sharing method using a combination different from the above combination, for example, the divided data F (2) to F (4).

  At this time, if a part of the divided data F (1) to F (4) is tampered with, as described above, the restored original data B1 and B2 are the original data for which the originality is to be secured. Unlike B, the original data B1 and B2 combine the divided data F (1) to F (4) in different combinations, so that the restored original data B1 and B2 are different from each other.

  Therefore, in the client 2, at least a part of the divided data D (1) to D (4) stored in the storage servers 3a1 to 3a4 has been falsified due to a mismatch between the restored original data B1 and the original data B2. This can be confirmed on the client 2 side.

  Note that, in the present embodiment, the divided data F (1) to F (3) and the divided data F (2) to F (4) are different combinations from among the divided data F (1) to F (4). However, the present invention is not limited to this combination, and it is sufficient to select a plurality of combinations in which each of the four divided data D (1) to D (4) is used at least once for restoration. It can be confirmed whether or not the original data restored based on the combination of each other matches.

(Third embodiment)
FIG. 5 is a block diagram showing a schematic configuration of the data originality securing system 4 according to the third embodiment of the present invention.

  As shown in FIG. 5, the data originality assurance system 4 is communicably connected to a network 5 such as a terminal 5 and a dividing device 6 which can connect to and communicate with a communication network N such as the Internet. And a plurality of (three in the present embodiment) data storage server computers (hereinafter simply referred to as storage servers) 3a1 to 3a3 which are hardware independent from each other. With the above system configuration, the dividing device 6 divides the data into a plurality of divided data in response to a data storage request from the terminal 5 via the network N, and divides the divided plurality of divided data via the network N It is stored in a plurality of storage servers 3a1-3a3. The communication between the terminal 5 and the dividing device 6 and the communication between the dividing device 6 and each of the storage servers 3a1 to 3a3 are performed using SSL (Secure Socket Layer), IP- Communication data is encrypted by a VPN (Virtual Private Network) or the like.

  The terminal 5 and the dividing device 6 are connected to a CPU as an arithmetic processing unit, an interface connected to the CPU to enable communication between the CPU and the network N, an input unit for data input connected to the CPU, and the CPU. Each has its own memory.

  The terminal 5 transmits data stored by the user to the division device 6 while the user secures the originality and stores the data {for example, digital data of M (M is a natural number) bytes; hereinafter, also referred to as original data} And a data transmitting / receiving unit 31 that receives the data from the dividing device 6.

  The original data B transmitted from the terminal 5 is stored in the memory 10 of the dividing device 6. Further, the memory 10 is readable by the dividing device 6 (its CPU), and the data originality for causing the dividing device 6 (its CPU) to execute the data originality securing process shown in FIGS. 6 and 7 described below. The security program P3 is installed.

  The data originality securing program P3 is mounted on various recording media such as a magnetic memory and a semiconductor memory, and is read from the recording medium by the dividing device 6 and loaded into the memory as necessary. It is also possible.

  As a function realized by the data originality securing program P3, the dividing device 6 generates, for example, a hash value H that can uniquely identify the original data B from the original data B stored in the memory 10 and will be described later. A hash value generation unit 32 that generates hash values h1 to h3 and a secret sharing method S (secret sharing method different from those of the first and second embodiments) described below are used for data including the original data B and the hash value H. To generate divided data (hereinafter also referred to as a divided data body) D (1) to D (3) (in the present embodiment, the number of divisions is set to 3), and to generate the divided data body D (1 ) To D (3), header information, and divided data composed of hash values h1 to h3 generated from the divided data body and the entire contents of the header information (hereinafter, also referred to as transmission divided data). (B) a divided data generation unit 33 that generates DD (1) to DD (3); a random number generation unit 34 that generates random number data used when generating the divided data bodies D (1) to D (3); The hash values h1 to h3 are regenerated from the divided data bodies D (1) to D (3) obtained from the storage servers 3a1 to 3a3 and the header information thereof, and the hash value H is regenerated from the restored original data B. A hash value checking unit 35 for checking the authenticity of the data; and an original data restoring unit for generating the original data B and the hash value H from the divided data bodies D (1) to D (3) using the secret sharing method S. 36, and a data transmitting / receiving unit 37 for transmitting / receiving the original data B and the transmission division data DD (1) to DD (3) via the network N.

  Each of the storage servers 3a1-3a3 is connected to a CPU serving as an arithmetic processing unit, an interface connected to the CPU and enabling communication between the CPU and the network N, an input unit for data input connected to the CPU, and the CPU. And a storage device such as a hard disk.

  Next, the overall processing of the data originality securing system 4 according to the present embodiment will be described with reference to FIGS. Here, FIG. 6 is a flowchart showing the data originality securing process based on the data originality securing program P3 in the present embodiment, and FIG. 7 is a data sequence of the data originality securing process shown in FIG. .

  As shown in FIG. 6 and FIG. 7, when the user specifies the original data B to be stored and transmits the original data B from the terminal 5 to the dividing device 6, the dividing device 6 divides the original data B in accordance with the data originality securing program P3. As a function of the hash value generation unit 32, the original data B stored in the memory 10 and whose originality is desired to be kept and stored is read from the memory 10, and the read original data B is read using a predetermined hash function. A hash value H of the original data B is generated (steps S101 and S102).

  The hash value H has such a property that if the original data B is changed even by one bit, the hash value H shows a completely different value, that is, the original data B can be uniquely identified.

  Next, as a function of the divided data generating unit 33, the dividing device 6 converts the original data B including the generated hash value H into three data (divided data) D (1) to D (3) using the secret sharing method S. (Step S103). Then, for each of the divided data D (i) (i = 1, 2, 3), data of a format shown in FIG. 8, that is, a hash value hi (i = 1, 2, 3), and management information on data division are included. The transmission division data DD (i) including the header information Ai (i = 1, 2, 3) and the division data D (i) (i = 1, 2, 3) is generated (steps S104, S105).

  Here, as a function of the hash value generation unit 32, the hash value hi is generated from the entire contents of the header information Ai and the divided data D (i) by using a predetermined hash function. The data identifier Ai1 of the header information Ai includes information indicating that the data is divided by the secret sharing scheme S of the present embodiment, the version information Ai2 includes information for identifying the version of the data format, and a header. In the size Ai3, information indicating the total data length of the area from the original data size to the divided data size is stored. The original data size Ai4 is information indicating the length of the original data (original data B including the hash value H), the division number Ai5 is information indicating the number of data divisions (3 in the present embodiment), In the processing unit bit length Ai6, information indicating a processing unit bit length, which will be described later, used in the division processing based on the secret sharing scheme S is stored. In addition, the random number data size Ai7 includes information indicating the length of random number data used in the division processing by the secret sharing method S, and the division data type Ai8 includes information indicating the number of division data (for example, 3 In the case of division, information indicating whether the divided data is D (1), D (2), or D (3)) and the divided data size Ai9 include the length of the divided data D (i). Is stored.

  Then, as a function of the data transmitting / receiving unit 37, the dividing device 6 transmits the created transmission divided data DD (1) to DD (3) to the storage servers 3a1 to 3a3 via the network N (step S106).

  Each of the storage servers 3a1 to 3a3 stores the transmission division data DD (1) to DD (3) transmitted via the network N in a storage device such as a hard disk (step S107).

  In this way, the divided data D (1) to D (3) obtained by dividing the original data B including the hash value H, the header information A1 to A3, and the transmission divided data DD composed of the hash values h1 to h3 (1) to DD (3) can be stored in the storage servers 3a1 to 3a3, respectively.

  Next, when retrieving the transmission division data DD (1) to DD (3) stored in the storage servers 3a1 to 3a3, the user specifies the original data B to be retrieved and retrieves it from the terminal 5 to the dividing device 6. Upon transmitting the instruction, the dividing device 6 transmits download requests for the transmission divided data DD (1) to DD (3) to the storage servers 3a1 to 3a3, respectively (steps S108 and S109).

  Each of the storage servers 3a1-3a3 reads out the transmission divided data DD (1) -DD (3) stored in the storage device such as a hard disk from each storage device in response to the transmitted download request, and reads out. The transmitted divided data DD (1) to DD (3) are transmitted to the dividing device 6 via the network N (step S110).

  The division device 6 operates in accordance with the data originality securing program P3, and receives the transmission division data DD (1) to DD (3) transmitted via the network N as a function of the hash value confirmation unit 35, The hash values h1 ′ to h3 ′ are regenerated from the divided data bodies D (1) to D (3) of the received transmission divided data DD (1) to DD (3) and the header information A1 to A3 (step S111). Then, the regenerated hash values h1 ′ to h3 ′ are compared with the hash values h1 to h3 of the received transmission divided data DD (1) to DD (3) to check whether they match (step S112). ). Thereby, it is possible to confirm that the contents of the data acquired from the storage servers 3a1 to 3a3 are not missing or falsified.

  Next, in step S112, when there are at least two or more transmission divided data DD (1) to DD (3) having the same hash value, the divided data D (1) to D ( 3) Based on the header information A1 to A3 and the secret sharing method S, the original data B1 and the hash value H1 are restored (step S113). This is because even if the divided data cannot be obtained from the storage servers 3a1 to 3a3 or the hash value cannot be confirmed, the data can be acquired and the hash value can be confirmed to be necessary for data restoration. If the number is equal to or more than the number (in the present embodiment, two or more as described later), the subsequent processing (data restoration processing) is performed.

  Next, as a function of the hash value checking unit 35, the dividing device 6 regenerates the hash value H2 from the restored original data B1, compares the regenerated hash value H2 with the restored hash value H1, and determines whether or not they match. It is confirmed whether or not it is (steps S114, S115). Thereby, it is possible to confirm that the contents of the restored original data B and hash value H are not missing or falsified. Further, even if the contents of the header information A1 to A3 and the divided data bodies D (1) to D (3) are falsified, the hash values h1 to h3 are calculated in accordance with the falsified contents and rewritten. , The hash values match in step S112), and tampering can be detected.

  Then, the dividing device 6 transmits the restored original data B to the terminal 5 via the network N, whereby the terminal 5 acquires the original data B (Steps S116 and S117).

  Here, the secret sharing scheme S in the present embodiment will be described in detail. In the following description, the original data refers to the original data to be divided, that is, the original data B including the hash value H generated by the hash value generation unit 33 in the present embodiment.

  In the division and restoration of the original data in the present embodiment, the original data is divided into a desired number of division data based on a desired processing unit bit length. In this case, the processing unit bit length is set to an arbitrary value. Since the original data is divided for each processing unit bit length, and the divided partial data is generated from the original partial data by a number smaller by one than the number of divisions, the bit length of the original data is equal to the processing unit bit length. If the value does not match the integral multiple of (number-1) times, the bit length of the original data is adjusted to an integral multiple of (the number of divisions-1) times the processing unit bit length by padding the trailing part of the original data with zeros. Thus, the present embodiment can be applied.

  Further, the above-described random numbers are also generated from the random number generation unit 34 as (number of divisions-1) random number partial data having a bit length of the processing unit bit length corresponding to each of the (number of divisions-1) original partial data. Is done. That is, the random number is divided for each processing unit bit length, and is generated as (partition number-1) random number partial data having a bit length of the processing unit bit length. Further, the original data is divided into a desired number of divided data based on the processing unit bit length, and each of the divided data also corresponds to the processing unit corresponding to each of the (number of divided -1) original partial data. It is generated as (partition number-1) divided partial data having the bit length of the bit length. That is, each of the divided data is divided for each processing unit bit length, and is generated as (partition number -1) divided partial data having a bit length of the processing unit bit length.

  In the following description, the above-described original data, random numbers, divided data, the number of divisions, and the processing unit bit length are represented by B, R, D, n, and b, respectively. Using i (= 1 to n) and j (= 1 to n-1) as variables representing one, (n-1) original partial data, and (n-1) random number partial data , And one of each of the n pieces of divided data D are represented by B (j), R (j) and D (i), respectively, and furthermore, a plurality of divided data D (i) It is assumed that the divided partial data of (n-1) is denoted by D (i, j). That is, B (j) represents the j-th original partial data when the original data B is divided from the top of the original data B by the processing unit bit length and numbered in order from the first.

  Using this notation, the original data, the random number data, and the divided data, and the original partial data, the random number partial data, and the divided partial data that configure them, respectively, are represented as follows.

Original data B = (n-1) original partial data B (j)
= B (1), B (2),…, B (n-1)
Random number R = (n-1) random number partial data R (j)
= R (1), R (2),…, R (n-1)
n pieces of divided data D (i) = D (1), D (2), ..., D (n)
Each divided partial data D (i, j)
= D (1,1), D (1,2),…, D (1, n-1)
D (2,1), D (2,2),…, D (2, n-1)
………
D (n, 1), D (n, 2),…, D (n, n-1)
(i = 1 ~ n), (j = 1 ~ n-1)
The present embodiment performs an exclusive OR operation (XOR) of the original partial data and the random number partial data on a plurality of partial data divided according to the processing unit bit length as described above. The method is characterized in that the original data is divided using a definition expression consisting of exclusive OR operation (XOR) of data and random number partial data, and a method using a polynomial or remainder operation in the data division processing described above. Compared with (the method in the first and second embodiments), the use of an exclusive OR (XOR) operation, which is a bit operation suitable for computer processing, requires high-speed and high-performance operation processing capability. In addition to this, it is possible to generate divided data by repeating simple arithmetic processing even for large amounts of data, and the storage capacity required for storing the divided data is a multiple of the number proportional to the number of divisions. It can be made smaller than that. Further, the divided data is generated by a stream process in which the arithmetic processing is sequentially performed from the beginning of the data for each arbitrarily determined constant length.

  In the following description, the exclusive OR operation (XOR) used in the present embodiment will be represented by an operation symbol “*”. The results of each operation are as follows.

0 * 0 results in 0
Operation result of 0 * 1 is 1
The operation result of 1 * 0 is 1
1 * 1 operation result is 0
In addition, the XOR operation satisfies the exchange rule and the combination rule. That is,
a * b = b * a
It is mathematically proved that (a * b) * c = a * (b * c) holds.

  Further, a * a = 0 and a * 0 = 0 * a = a hold.

Here, a, b, and c represent bit strings of the same length, and 0 represents a bit string of the same length and composed of all “0”.

  Next, the operation of the secret sharing scheme S in the present embodiment will be described with reference to the drawings such as flowcharts. Before this description, the definitions of the symbols shown in the flowcharts of FIGS. 9 to 12 will be described.

(1) Π _{i = 1} ⁿ A (i) means A (1) * A (2) *... A (n).

  (2) c (j, i, k) is a [n-1) × (n-1) matrix U [n-1, n-1] × (P [n-1, n-1]) ＾ It is defined as the value of the i-th row and the k-th column of (j-1).

  At this time, Q (j, i, k) is defined as follows.

（４）P[n,n]とは、n×n行列であって、i行j列の値をp(i,j)で表すと、
j=i+1 のとき p(i,j)=1
i=1,j=n のとき p(i,j)=1
上記以外のとき p(i,j)=0
である行列を意味するものとし、「回転行列」ということとする。具体的には下記のような行列であり、他の行列の右側からかけると当該他の行列の１列目を２列目へ、２列目を３列目へ、…,n-1列目をn列目へ、n列目を１列目へ移動させる作用がある。つまり、行列Pを他の行列に右側から複数回かけると、その回数分だけ各列を右方向へ回転させるように移動させることができる。

（５）A,Bをn×n行列とすると、A×Bとは行列AとBの積を意味するものとする。行列の成分同士の計算規則は通常の数学で用いるものと同じである。 When c (j, i, k) = 1 Q (j, i, k) = R ((n-1) × m + k)
Q (j, i, k) = 0 when c (j, i, k) = 0
(3) U [n, n] is an n × n matrix, and the value of the i-th row and the j-th column is represented by u (i, j).
u (i, j) = 1 when i + j <= n + 1
u (i, j) = 0 when i + j> n + 1
And is referred to as an “upper triangular matrix”. Specifically, the matrix is as follows.

(4) P [n, n] is an n × n matrix, and when the value of i row and j column is represented by p (i, j),
When j = i + 1, p (i, j) = 1
When i = 1, j = n p (i, j) = 1
Other than above p (i, j) = 0
And a “rotation matrix”. Specifically, the following matrix is obtained. When multiplied from the right side of another matrix, the first column of the other matrix becomes the second column, the second column becomes the third column,. To the n-th column and the n-th column to the first column. That is, when the matrix P is applied to another matrix a plurality of times from the right side, each column can be moved so as to rotate to the right by the number of times.

(5) If A and B are n × n matrices, A × B means the product of matrices A and B. The calculation rules for the matrix elements are the same as those used in ordinary mathematics.

  (6) Assuming that A is an n × n matrix and i is an integer, A ＾ i means i products of the matrix A. A ＾ 0 means the unit matrix E.

次に、図９に示すフローチャートおよび図１０および図１１に示す具体的データなどを参照して、まず元データBの分割処理について説明する。 (7) The unit matrix E [n, n] is an n × n matrix, and the value of the i-th row and the j-th column is represented by e (i, j).
e (i, j) = 1 when i = j
Other than above e (i, j) = 0
Let be a matrix. Specifically, the matrix is as follows. Let A be any n × n matrix
A × E = E × A = A
There is a property that.

Next, the dividing process of the original data B will be described first with reference to the flowchart shown in FIG. 9 and the specific data shown in FIGS.

  First, the original data B is supplied to the dividing device 6 (Step S201 in FIG. 9). In this example, the original data B is 16-bit “10110010 00110111”.

  Next, the user instructs the dividing device 6 from the terminal 5 as the number of divisions n (step S203). As the number of divisions n, a value predetermined in the division device 6 may be used. The three divided data generated by the dividing device 6 according to the division number n = 3 are D (1), D (2), and D (3). The divided data D (1), D (2), D (3) are all 16-bit data having the same bit length as the original data.

  Then, the processing unit bit length b used to divide the original data B is determined to be 8 bits, and a 16-bit random number R having the same bit length as the original data is obtained from the random number generation unit 34 and generated. (Step S205). The processing unit bit length b may be specified by the user from the terminal 5 to the dividing device 6, or a value predetermined in the dividing device 6 may be used. Note that the processing unit bit length b may be an arbitrary number of bits, but is 8 bits that can divide the original data B here. Therefore, the original data B of 16 bits "10110010 00110111" is divided into 8 units of processing unit bit length, and the two original divided data B (1) and B (2) are "10110010" And "00110111".

  In the next step S207, it is determined whether or not the bit length of the original data B is an integral multiple of 8 × 2, and if not, the end of the original data B is padded with 0, and the 8 × 2 Adjust to an integral multiple. Note that the division processing when the processing unit bit length b is set to 8 bits and the division number n is set to 3 as in this example is not limited to 16 bits as the bit length of the original data B. This is effective for original data B having an integer multiple of length b × (number of divisions n−1) = 8 × 2.

  Next, in step S209, the variable m, that is, the variable m meaning the integral multiple described above, is set to 0. When the original data B has a processing unit bit length b × (number of divisions n−1) = 8 × 2 = 16 bits as in this example, the variable m is 0, but it is twice as large as 32 bits. In this case, the variable m becomes 1, and in the case of three times 48 bits, the variable m becomes 2.

  Next, it is determined whether or not data of 8 × 2 bits from the 8 × 2 × m + 1th bit of the original data B exists (step S211). This is because the division processing shown in step S211 and subsequent steps is performed on the processing unit bit length b × (number of divisions n−1) = 8 × 2 = 16 bits specified by the variable m of the original data B, and then It is determined whether there is the next 16 bits as data B. In the case where the original data B is 16 bits as in this example, if the division processing from step S211 is performed once on the 16-bit original data B, the variable m is incremented by 1 in step S219 described later. However, in the original data B of this example, since there is no data of 17 bits or less corresponding to the case where the variable m is m + 1, the process proceeds from step S211 to step S221. In this case, the variable m is Since it is 0, the 8 × 2 × m + 1-th bit of the original data B becomes 8 × 2 × 0 + 1 = 1, and data is stored in 8 × 2 bits from the first 16 bits of the original data B. Since it exists, the process proceeds to step S213.

  In step S213, the variable j is changed from 1 to 2 (= the number of divisions n−1), and 8 bits from the 8 × (2 × m + j−1) +1 bit of the original data B (= processing unit bit) (Length) is set to the original partial data B (2 × m + j), whereby the original data B is divided by the processing unit bit length into 2 (division number n-1) original partial data B (1) , B (2) are generated as follows.

Original data B = B (1), B (2)
First original partial data B (1) = “10110010”
Second original partial data B (2) = “00110111”
Next, the variable j is changed from 1 to 2 (= the number of divisions n-1), and an 8-bit random number generated from the random number generation unit 34 is set in the random number partial data R (2 × m + j). Thereby, two (partition number n-1) pieces of random number partial data R (1) and R (2) obtained by dividing the random number R by the processing unit bit length are generated as follows (step S215).

Random number R = R (1), R (2)
First random number partial data R (1) = “10110001”
Second random number partial data R (2) = “00110101”
Next, in step S217, while changing the variable i from 1 to 3 (= the number of divisions n), and further changing the variable j in each variable i from 1 to 2 (= the number of divisions n-1), the process proceeds to step S217. Each of the divided partial data D (i, 2 × m + j) that constitutes each of the plurality of divided data D (i) by a definition formula consisting of exclusive OR of the original partial data and the random number partial data for generating the divided data ) Is generated. As a result, the following divided data D is generated.

Division data D
= 3 divided data D (i) = D (1), D (2), D (3)
First divided data D (1)
= 2 divided partial data D (1, j) = D (1,1), D (1,2)
= “00110110”, “10110011”
Second divided data D (2)
= 2 divided partial data D (2, j) = D (2,1), D (2,2)
= "00000011", "00000010"
Third divided data D (3)
= 2 divided partial data D (3, j) = D (3,1), D (3,2)
= `` 10110001 '', `` 00110101 ''
Note that the definition expression in step S217 for generating each divided partial data (i, j) is specifically described in the table shown in FIG. 11 when the division number n = 3 as in this example. It is what is being done. From the table shown in FIG. 11, the definition formula for generating the divided partial data D (1,1) is B (1) * R (1) * R (2), and the definition formula of D (1,2) Is B (2) * R (1) * R (2), the definition of D (2,1) is B (1) * R (1), and the definition of D (2,2) is B (2) * R (2), the defining formula of D (3,1) is R (1), and the defining formula of D (3,2) is R (2). The table shown in FIG. 11 also describes a general definition formula for an arbitrary integer when m> 0.

  After the division data D is generated for the case where the variable m = 0, which means an integer multiple, the variable m is incremented by 1 (step S219), and the process returns to step S211 to return to the original data B corresponding to the variable m + 1. In the present example, the same division processing is to be performed for the 17th and subsequent bits. However, since the original data B in this example is 16 bits and there is no data after the 17th bit, the process proceeds from step S211 to step S221, where The divided data D (1), D (2), and D (3) thus obtained are temporarily stored in the memory 10 of the dividing device 6, and the dividing process ends. The divided data D (1), D (2), and D (3) stored in this manner cannot independently estimate the original data.

  Here, the generation processing of the divided data based on the definition formula in step S217 of the flowchart of FIG. 9 described above, specifically, the generation processing of the divided data when the number of divisions n = 3, will be described in detail.

  First, when the variable m = 0, which means an integer multiple, the divided data D (i) = D (1) to D (3) constituting each of the divided partial data (i, 2 × m + j) = D (i, j) (i = 1 to 3, j = 1 to 2) is as follows.

D (1,1) = B (1) * Q (1,1,1) * Q (1,1,2)
D (1,2) = B (2) * Q (2,1,1) * Q (2,1,2)
D (2,1) = B (1) * Q (1,2,1) * Q (1,2,2)
D (2,2) = B (2) * Q (2,2,1) * Q (2,2,2)
D (3,1) = R (1)
D (3,2) = R (2)
Q (j, i, k) included in the four equations from the top among the above six equations is specifically determined.

This is the following when c (j, i, k) is the value of the i × k matrix of U [2,2] × (P [2,2]) ＾ (j−1) which is a 2 × 2 matrix. Is defined as

j=2のときは

これを用いると、各分割部分データD(i,j)は次のような定義式により生成される。 When c (j, i, k) = 1 Q (j, i, k) = R (k)
Q (j, i, k) = 0 when c (j, i, k) = 0
here,
When j = 1

When j = 2

When this is used, each divided partial data D (i, j) is generated by the following defining formula.

D (1,1) = B (1) * Q (1,1,1) * Q (1,1,2) = B (1) * R (1) * R (2)
D (1,2) = B (2) * Q (2,1,1) * Q (2,1,2) = B (2) * R (1) * R (2)
D (2,1) = B (1) * Q (1,2,1) * Q (1,2,2) = B (1) * R (1) * 0 = B (1) * R (1 )
D (2,2) = B (2) * Q (2,2,1) * Q (2,2,2) = B (2) * 0 * R (2) = B (2) * R (2 )
The definition formula for generating each of the above-described divided partial data D (i, j) is also illustrated in FIG.

  FIG. 10 shows the case where the original data B is divided from each data, the definition formula, and each divided partial data when the original data B of 16 bits is divided into three by the division number n = 3 based on the processing unit bit length of 8 bits as described above. It is a table | surface which shows the calculation formula at the time of restoration.

  Here, the divided data D (1), D (2), D (3) and the divided partial data D (1,1), D (1,2), D (2,1), The process of generating D (2,2), D (3,1), D (3,2) and the general form of the definition formula will be described.

  First, for the first divided data D (1), the first divided partial data D (1,1) is defined by the above-described definition formula B (1) * R (1) * R (2) Then, the second divided partial data D (1, 2) is defined by the definition formula B (2) * R (1) * R (2). Note that the general form of this definition formula is B (j) * R (j) * R (j + 1) for D (1, j), and for D (1, j + 1) B (j + 1) * R (j) * R (j + 1) (j is an odd number). When calculated according to the definition formula, D (1,1) becomes 00110110 and D (1,2) becomes 10110011, so that D (1) becomes 00110110 10110011. The general form of the definition formula is shown in FIG.

  For the second divided data D (2), D (2,1) is defined as B (1) * R (1), and D (2,2) is B (2) * R ( Defined in 2). The general form of this definition is B (j) * R (j) for D (2, j) and B (j + 1) * R for D (2, j + 1) (j + 1) (j is an odd number). When calculated according to the definition formula, D (2,1) becomes 00000011 and D (2,2) becomes 00000010, so that D (2) is 00000011 00000010.

  Further, for the third divided data D (3), D (3,1) is defined by R (1), and D (3,2) is defined by R (2). The general form of this definition is R (j) for D (3, j) and R (3, j + 1) for D (3, j + 1) (where j is Odd number). When calculated according to the definition formula, D (3,1) becomes 10110001, D (3,2) becomes 00110101, and thus D (3) becomes 10110001 00110101.

  In the above description, the lengths of B, R, D (1), D (2), and D (3) are set to 16 bits. The divided data D (1), D (2), D (3) can be generated even from the original data B. Also, the processing unit bit length b can be arbitrarily set, and by repeating the above-described division processing for each length of b × 2 in order from the beginning of the original data B, the original data of an arbitrary length, specifically the processing It can be applied to original data having a length that is an integral multiple of the unit bit length b × 2. If the length of the original data B is not an integral multiple of the processing unit bit length b × 2, the length of the original data B is set to the processing unit bit length b × 2, for example, by padding the end of the data with 0. The above-described division processing according to the present embodiment can be applied by adjusting to the integral multiple of.

  Next, a process of restoring original data from divided data will be described with reference to a table shown on the right side of FIG.

  First, it requests the dividing device 6 to restore the original data B. Upon receiving the restoration request for the original data B, the dividing device 6 stores the divided data D (1), D (2), and D (3) corresponding to the original data B in the storage servers 3a1, 3a2, and 3a3. The divided data D (1), D (2), and D (3) are acquired from the storage servers 3a1, 3a2, and 3a3 via the network N, and the acquired divided data D ( The original data B is restored from 1), D (2), and D (3) as shown below.

  First, first original partial data B (1) can be generated from the divided partial data D (2,1), D (3,1) as follows.

D (2,1) * D (3,1) = (B (1) * R (1)) * R (1)
= B (1) * (R (1) * R (1))
= B (1) * 0
= B (1)
Specifically, since D (2, 1) is 00000011 and D (3, 1) is 10110001, B (1) is 10110010.

  Further, second original partial data B (2) can be generated from another divided partial data as follows.

D (2,2) * D (3,2) = (B (2) * R (2)) * R (2)
= B (2) * (R (2) * R (2))
= B (2) * 0
= B (2)
Specifically, since D (2, 2) is 00000010 and D (3, 2) is 00110101, B (2) is 00110111.

In general, if j is odd,
D (2, j) * D (3, j) = (B (j) * R (j)) * R (j)
= B (j) * (R (j) * R (j))
= B (j) * 0
= B (j)
Therefore, if D (2, j) * D (3, j) is calculated, B (j) can be obtained.

Also, in general, j is an odd number,
D (2, j + 1) * D (3, j + 1) = (B (j + 1) * R (j + 1)) * R (j + 1)
= B (j + 1) * (R (j + 1) * R (j + 1))
= B (j + 1) * 0
= B (j + 1)
Therefore, if D (2, j + 1) * D (3, j + 1) is calculated, B (j + 1) is obtained.

  Next, when D (1) and D (3) are acquired and B is restored, the following is performed.

D (1,1) * D (3,1) * D (3,2) = (B (1) * R (1) * R (2)) * R (1) * R (2) = B ( 1) * (R (1) * R (1)) * (R (2) * R (2))
= B (1) * 0 * 0
= B (1)
Therefore, if D (1,1) * D (3,1) * D (3,2) is calculated, B (1) can be obtained. When specifically calculated, B (1) becomes 10110010 because D (1,1) is 00110110, D (3,1) is 10110001, and D (3,2) is 00110101.

Similarly,
D (1,2) * D (3,1) * D (3,2) = (B (2) * R (1) * R (2)) * R (1) * R (2)
= B (2) * (R (1) * R (1)) * (R (2) * R (2))
= B (2) * 0 * 0
= B (2)
Therefore, if D (1,2) * D (3,1) * D (3,2) is calculated, B (2) can be obtained. When specifically calculated, D (1,2) is 10110011, D (3,1) is 10110001, D (3,2) is 00110101, and B (2) is 00110111.

In general, if j is odd,
D (1, j) * D (3, j) * D (3, j + 1) = (B (j) * R (j) * R (j + 1)) * R (j) * R (j +1)
= B (j) * (R (j) * R (j)) * (R (j + 1) * R (j + 1))
= B (j) * 0 * 0
= B (j)
Therefore, by calculating D (1, j) * D (3, j) * D (3, j + 1), B (j) can be obtained.

Also, in general, j is an odd number,
D (1, j + 1) * D (3, j) * D (3, j + 1) = (B (j + 1) * R (j) * R (j + 1)) * R (j) * R (j + 1)
= B (j + 1) * (R (j) * R (j)) * (R (j + 1) * R (j + 1))
= B (j + 1) * 0 * 0
= B (j + 1)
Therefore, if D (1, j + 1) * D (3, j) * D (3, j + 1) is calculated, B (j + 1) is obtained.

  Next, when D (1) and D (2) are acquired and B is restored, the following is performed.

D (1,1) * D (2,1) = (B (1) * R (1) * R (2)) * (B (1) * R (1))
= (B (1) * B (1)) * (R (1) * R (1)) * R (2)
= 0 * 0 * R (2)
= R (2)
Therefore, if D (1,1) * D (2,1) is calculated, R (2) can be obtained. When specifically calculated, since D (1,1) is 00110110 and D (2,1) is 00000011, R (2) is 00110101.

Similarly,
D (1,2) * D (2,2) = (B (2) * R (1) * R (2)) * (B (2) * R (2))
= (B (2) * B (2)) * R (1) * (R (2) * R (2))
= 0 * R (1) * 0
= R (1)
Therefore, if D (1,2) * D (2,2) is calculated, R (1) can be obtained. Specifically, since D (1, 2) is 10110011 and D (2, 2) is 00000010, R (1) is 10110001.

  Using these R (1) and R (2), B (1) and B (2) are obtained.

D (2,1) * R (1) = (B (1) * R (1)) * R (1)
= B (1) * (R (1) * R (1))
= B (1) * 0
= B (1)
Therefore, if D (2,1) * R (1) is calculated, B (1) is obtained. Specifically, since D (2, 1) is 00000011 and R (1) is 10110001, B (1) is 10110010.

Similarly,
D (2,2) * R (2) = (B (2) * R (2)) * R (2)
= B (2) * (R (2) * R (2))
= B (2) * 0
= B (2)
Therefore, if D (2,2) * R (2) is calculated, B (2) can be obtained. Specifically, since D (2, 2) is 00000010 and R (2) is 00110101, B (2) is 00110111.

In general, if j is odd,
D (1, j) * D (2, j) = (B (j) * R (j) * R (j + 1)) * (B (j) * R (j))
= (B (j) * B (j)) * (R (j) * R (j)) * R (j + 1)
= 0 * 0 * R (j + 1)
= R (j + 1)
Then, if D (1, j) * D (2, j) is calculated, R (j + 1) can be obtained.

Similarly,
D (1, j + 1) * D (2, j + 1) = (B (j + 1) * R (j) * R (j + 1)) * (B (j + 1) * R (j +1))
= (B (j + 1) * B (j + 1)) * R (j) * (R (j + 1) * R (j + 1))
= 0 * R (j) * 0
= R (j)
Therefore, if D (1, j + 1) * D (2, j + 1) is calculated, R (j) can be obtained.

  Using these R (j) and R (j + 1), B (j) and B (j + 1) are obtained.

D (2, j) * R (j) = (B (j) * R (j)) * R (j)
= B (j) * (R (j) * R (j))
= B (j) * 0
= B (j)
Therefore, B (j) can be obtained by calculating D (2, j) * R (j).

Similarly,
D (2, j + 1) * R (j + 1) = (B (j + 1) * R (j + 1)) * R (j + 1)
= B (j + 1) * (R (j + 1) * R (j + 1))
= B (j + 1) * 0
= B (j + 1)
Therefore, if D (2, j + 1) * R (j + 1) is calculated, B (j + 1) can be obtained.

  As described above, when divided processing is repeatedly performed based on the processing unit bit length b from the beginning of the original data to generate divided data, three divided data D (1), D (2), D ( Even without using all of 3), as described above, the original data can be restored using two of the three divided data.

  As another method of the present invention, the original data can be divided by using a bit length of the random number R shorter than that of the original data B.

  That is, although the random number R described above is data having the same bit length as B, D (1), D (2), and D (3), the random number R is shorter than the bit length of the original data B, and the divided data D (1), D (2), and D (3) are generated by repeatedly using this short bit length random number R.

  Since the divided data D (3) is generated only from the random number R, it is not necessary to store the divided data D (3) by repeating the random number R. For example, when the bit length of the original data B is 1600 bits (200 bytes), the random number R is a repetition of arbitrarily taken 160 bits (20 bytes) of data. That is, R (1) to R (20) are randomly generated, and R (21) to R (200) are R (21) = R (1), R (22) = R (2),. (40) = R (20), R (41) = R (1), R (42) = R (2), ..., R (60) = R (20), R (61) = R (1) , R (62) = R (2),…, R (80) = R (20), ………, R (181) = R (1), R (182) = R (2),…, R (200) = R (20).

  In the above description, D (3) is generated by defining the divided partial data D (3, j) as random number partial data R (j), but it is sufficient to store up to D (3, 20) . That is, the length of D (3) is 1/10 of D (1) and D (2). Therefore, the total amount of data to be stored is three times that of the original data B in the previous embodiment, but can be 2.1 times in this embodiment.

If the length of the data of the repetition part in the random number R is too short, R may be decrypted only from D (1) or D (2), so it is desirable to select an appropriate length.

  Next, with reference to the flowchart shown in FIG. 12, a general division process when the number of divisions is n and the processing unit bit length is b will be described.

  First, the original data B is supplied to the dividing device 6 (step S401). In addition, the user instructs the number of divisions n (an arbitrary integer satisfying n ≧ 3) to the division device 6 from the terminal 5 (step S403). As the number of divisions n, a value predetermined in the division device 6 may be used. The processing unit bit length b is determined (step S405). Note that b is any integer greater than 0. Next, it is determined whether or not the bit length of the original data B is an integer multiple of b × (n−1). If not, the end of the original data B is padded with 0 (step S407). Also, a variable m indicating an integral multiple is set to 0 (step S409).

  Next, it is determined whether there is data of b × (n−1) bits from the b × (n−1) × m + 1th bit of the original data B (step S411). If the result of this determination is that there is no data, the process proceeds to step S421. In this case, however, since the variable m has been set to 0 in step S409, there is data, so step S413 Proceed to.

  In step S413, the variable j is changed from 1 to n−1, and data of b bits from the (b × (n−1) × m + j−1) +1 bit of the original data B is converted to the original partial data B ( (n-1) × m + j) is repeated, whereby (n-1) original partial data B (1) and B (2) are obtained by dividing the original data B by the processing unit bit length b. ,... B (n-1) are generated.

  Next, the variable j is changed from 1 to n−1, and a random number having a processing unit bit length b generated from the random number generation unit 34 is set in the random number partial data R ((n−1) × m + j). Then, n-1 random number partial data R (1), R (2),... R (n-1) are generated by dividing the random number R by the processing unit bit length b (step S415).

  Next, in step S417, while changing the variable i from 1 to n, and further changing the variable j from 1 to n-1 in each variable i, a plurality of definitions are made according to the definition formula for generating the divided data shown in step S417. Each divided partial data D (i, (n−1) × m + j) constituting each of the divided data D (i) is generated. As a result, the following divided data D is generated.

Division data D
= n pieces of divided data D (i) = D (1), D (2), ... D (n)
First divided data D (1)
= n-1 divided partial data D (1, j) = D (1,1), D (1,2), ... D (1, n-1)
Second divided data D (2)
= n-1 divided partial data D (2, j) = D (2,1), D (2,2), ... D (2, n-1)
………
………
N-th divided data D (n)
= n-1 divided partial data D (n, j) = D (n, 1), D (n, 2), ... D (n, n-1)
After the divided data D is generated for the case where the variable m = 0, the variable m is incremented by 1 (step S419), and the process returns to step S411, where b × (n) of the original data B corresponding to the variable m = 1 -1) The same division processing is performed for the bits and thereafter. Finally, as a result of the determination in step S411, when there is no more data in the original data B, the process proceeds from step S411 to step S421, where the divided data D (1),. Is temporarily stored in the memory 10, and the division process is terminated.

  As described above, according to the present embodiment, the original data B is divided into a plurality of divided data D (1) to D (3) by the secret sharing method S including the hash value H of the original data B, Further, it is composed of divided data D (1) to D (3), header information A1 to A3, and hash values h1 to h3 calculated from divided data D (1) to D (3) and header information A1 to A3. The transmission division data DD (1) to DD (3) are generated and the transmission division data DD (1) to DD (3) are stored in the storage servers 3a1 to 3a3, respectively. Even if at least a part of 1) to DD (3) has been tampered with, the transmission division data DD (1) to DD (3) are obtained from the transmission division data DD (1) to DD (3) including the falsified data. ) Can be easily checked for tampering. Can.

  As a result, for example, even when the original data B is stored for a long period of time, the original data B can be easily saved without repeating the process of reissuing the electronic certificate and the process of creating the data with the electronic signature as in the case of the electronic signature. Data B can be stored.

  Further, according to the present embodiment, since the original data B is divided into transmission divided data DD (1) to DD (3) and stored in the storage servers 3a1 to 3a3, for example, the transmission divided data DD (1) Even if one of the divided data of DD (3) is falsified, the original data B can be restored using the remaining divided data.

As a result, the originality of the original data B can be more reliably ensured. The secret sharing method in the first and second embodiments is used for division management of a secret key of a public key cryptosystem. Although this is a practical method for data having a relatively small data capacity, the secret sharing scheme S according to the present embodiment does not require multiple long integer arithmetic processing including polynomial arithmetic and remainder arithmetic. Therefore, it is possible to obtain an effect that the data can be easily and quickly divided and restored even when a large amount of large data is processed.

  In the first and second embodiments, the divided data D (1) to D (4) obtained by dividing the original data B are stored in the storage servers 3a1 to 3a4 connected to the client 2 via the network N. In the third embodiment, the transmission division data DD (1) to DD (3) obtained by dividing the original data B are stored in the storage servers 3a1 to 3a1 connected to the division device 6 via the network N. Although it was configured to be stored in 3a3, the present invention is not limited to this configuration.

  For example, a modification of the data originality securing system 1 is shown in FIG.

  As shown in FIG. 13, the data originality securing system 1A according to the modified example is configured as a client system 25 solely on the client side, and the client system 25 includes a client 2 and a LAN for the client 2. And a plurality of storage storage devices 20a1 to 20a4 which are connected to each other via hardware and independent of each other in terms of hardware.

  Even if the data originality assurance system 1A is configured as shown in FIG. 13, the original data B can be stored as the divided data D (1) to D (4) in the plurality of storage storage devices 20a1 to 20a4, The original data B can be stored while ensuring the originality thereof simply and reliably.

  Similarly, as a modified example of the data originality securing system 4, the terminal 5, the dividing device 6, and the storage servers 3a1 to 3a3 may be configured as a client system solely on the client side.

  Furthermore, each system configuration described in the above embodiment is merely a preferred specific example, and if the functions are the same, other system configurations, for example, the data originality securing system 1 May be a system configuration as shown in the data originality securing system 4. This is a system configuration in which the function of the client 2 of the data originality securing system 1 is distributed to the terminal 5 and the dividing device 6. Similarly, for example, the system configuration of the data originality securing system 4 may be a system configuration as shown in the data originality securing system 1. This is to integrate the functions of the terminal 5 and the dividing device 6 of the data originality securing system 4 and make the functions of the client 2.

  Further, according to the above-described embodiment and its modification, as a secret sharing method, Shamir's secret sharing method ｛(k, n) threshold method; provided that n representing the number of divisions is 4, k representing the number that can be restored Is set to 3, and the secret sharing scheme S is used. However, the present invention is not limited to this configuration, and other secret sharing schemes other than the secret sharing scheme described in the above embodiment may be used. It is possible.

  Furthermore, according to the above-described embodiment and its modifications, the hash value is used as the identification data that can uniquely identify the original data. However, the identification data other than the hash value, for example, parity, checksum (the original data is It may be a value obtained by dividing all the blocks and treating the divided blocks as numerical values).

FIG. 1 is a block diagram showing a schematic configuration of a data originality securing system according to a first embodiment of the present invention. 4 is a schematic flowchart showing an example of a data originality securing process based on a data originality securing program in the data originality securing system according to the first embodiment of the present invention. FIG. 3 is a diagram schematically showing a data sequence in the data originality securing process shown in FIG. 2. FIG. 9 is a block diagram showing a schematic configuration of a data originality securing system according to a second embodiment of the present invention. FIG. 13 is a block diagram showing a schematic configuration of a data originality securing system according to a third embodiment of the present invention. 13 is a schematic flowchart showing an example of a data originality securing process based on a data originality securing program in the data originality securing system according to the third embodiment of the present invention. FIG. 7 is a diagram schematically showing a data sequence in the data originality securing process shown in FIG. 6. FIG. 13 is a diagram illustrating a configuration of divided data according to a third embodiment of the present invention. 15 is a flowchart illustrating a division process when the number of divisions is n = 3 in the third embodiment of the present invention. In the third embodiment of the present invention, the original data of 16 bits is divided from the data, the definition formula and each divided partial data when the original data of 16 bits is divided into three by the division number n = 3 based on the processing unit bit length of 8 bits. Table showing calculation formulas etc. when restoring data. 14 is a table showing definition data for generating divided data, divided partial data, and each divided partial data when the number of divisions is n = 3 in the third embodiment of the present invention. 15 is a flowchart illustrating a general division process when the number of divisions is n and the unit bit length is b according to the third embodiment of the present invention. FIG. 9 is a block diagram showing a schematic configuration of a data originality securing system according to a modification of the present invention.

Explanation of reference numerals

1, 1A, 4 ... Data originality securing system 2 ... Clients 3a1-3a4 ... Storage server 5 ... Terminal 6 ... Division device 10 ... Memory 11 ... Hash value generation unit 13 ... Division data generation unit 15 ... Original data restoration unit 17 ... Communication units 20a1 to 20a4 Storage storage device 25 Client system 31, 37 Data transmission / reception unit 32 Hash value generation unit 33 Divided data generation unit 34 Random number generation unit 35 Hash value confirmation unit 36 Original data restoration unit 37 ... Data transmission / reception unit

Claims (16)

A data originality securing system that secures the originality of data and stores the data,
A data dividing unit that divides the data into a plurality of divided data that can be restored using the secret sharing method,
A plurality of hardware-independent storage units for storing a plurality of divided data,
A data originality assurance system comprising: The data dividing unit is an identification data generation unit that generates identification data that can uniquely identify the data main body from the data main body whose originality is to be secured,
2. The data originality assurance system according to claim 1, further comprising a dividing unit for dividing the data obtained by combining the generated identification data and the data body by using a secret sharing method.   3. The data originality securing system according to claim 2, wherein the identification data generation unit includes a generation unit that generates a hash value of the data body using a predetermined hash function as the identification data. The data division unit generates division identification data that can uniquely identify the entire data, from the entire data obtained by adding management information on data division to each divided data,
4. The data originality assurance system according to claim 2, wherein the plurality of storage units store the divided data, management information on the data division, and the division identification data, respectively. A data restoration unit that respectively reads the plurality of divided data from the plurality of storage units and restores the data body and the identification data by a secret sharing scheme from the read plurality of divided data,
A confirmation unit that regenerates the identification data from the restored data body, and checks whether the regenerated identification data matches the restored identification data.
The data originality securing system according to claim 2 or 3, further comprising: Data restoration for reading the divided data, the management information relating to the data division, and the division identification data from the plurality of storage units, respectively, and restoring the data body and the identification data from the read plural division data by a secret sharing method, respectively. Department and
A first confirmation unit that regenerates the identification data from the restored data body, and confirms whether the regenerated identification data matches the restored identification data;
For each of the plurality of divided data, the divided identification data is regenerated from the entire data obtained by combining the read divided data and the management information relating to the data division. A second confirmation unit for confirming whether or not the identification data matches;
The data originality securing system according to claim 4, further comprising:   The plurality of divided data are respectively read from the plurality of storage units, the read plurality of divided data are combined in different combinations to restore a plurality of data, and it is confirmed whether the restored plurality of data match each other. The data originality securing system according to claim 1, further comprising a restoration confirmation unit. A data originality securing method for storing data while securing its originality,
Dividing the data into a plurality of divided data that can be restored using a secret sharing method,
Storing each of the plurality of divided data in a plurality of storage devices independent of hardware,
A data originality securing method characterized by comprising: The dividing step is a step of generating identification data that can uniquely identify the data main body from the data main body whose originality is to be secured,
Dividing the data obtained by combining the generated identification data and the data body using a secret sharing method,
9. The data originality securing method according to claim 8, comprising: A computer-readable data originality securing program for securing data and storing the originality thereof,
In the computer, a data dividing process of dividing the data into a plurality of divided data that can be restored using the secret sharing method,
A storage process of storing a plurality of divided data in a plurality of hardware-independent storage devices capable of communicating with the computer,
A program for ensuring originality of data. The division process is an identification data generation process of generating identification data that can uniquely identify the data main body from the data main body whose originality is to be secured,
A division process of dividing the data obtained by combining the generated identification data and the data body using a secret sharing method,
The data originality assurance program according to claim 10, further comprising:   12. The data originality assurance program according to claim 11, wherein the identification data generating process generates a hash value of the data body using a predetermined hash function as the identification data. The data division processing generates division identification data that can uniquely identify the entire data, from the entire data obtained by adding management information on data division to each divided data,
13. The data originality assurance program according to claim 11, wherein the storage processing stores the divided data, the management information on the data division, and the division identification data in the plurality of storage devices. . A data restoration process of respectively reading the plurality of divided data from the plurality of storage devices and restoring the data body and the identification data from the read plurality of divided data by a secret sharing method,
Confirmation processing for regenerating the identification data from the restored data body, and confirming whether the regenerated identification data matches the restored identification data,
13. The data originality assurance program according to claim 11, wherein the program is executed by the computer. Data restoration for reading the divided data, the management information relating to the data division, and the division identification data from the plurality of storage devices, respectively, and restoring the data body and the identification data from the read plurality of division data by a secret sharing method. Processing,
A first confirmation process for regenerating the identification data from the restored data body and confirming whether the regenerated identification data matches the restored identification data;
For each of the plurality of divided data, the divided identification data is regenerated from the entire data obtained by combining the read divided data and the management information relating to the data division. A second confirmation process for confirming whether or not the identification data matches;
14. The data originality assurance program according to claim 13, wherein the program is executed by the computer.   The plurality of divided data are respectively read from the plurality of storage devices, the read plurality of divided data are combined in different combinations to restore a plurality of data, and it is confirmed whether or not the restored plurality of data respectively match. 11. The data originality securing program according to claim 10, further causing the computer to execute restoration confirmation processing.

Images