System and method for generating a digital certificate

Technical field

This invention relates to the creation and renewal of digital certificates. More specifically, the invention relates to a secure system and method for generating a digital certificate.

Background of the invention

Digital electronic records are increasingly used to confirm events. Historically, seals, special paper signatures and other tools were used to prove the authenticity of documents and other records. In addition to proving the authenticity of documents and records, these and other tools were used to authenticate that the document was received or created in a certain order. These ways of proving authenticity and order are useful in a variety of areas including banking, negotiation and filing

- 2 legal documentation and public administration. Currently, such services are usually offered by notaries, auditors, etc.

Similar authentication and order checking services are needed in the market for digitized electronic content. In many different areas of this market, companies that provide electronic services receive digital records. For example, the electronic banking system receives a digital record for a certain purchase made by the recipient. Such service providers register the order in which digital records are received and give each record a "sequential value". When the records are received and registered by the service provider, a digital certificate is usually issued for the party providing the record. Later, you may need to check the order in which the records were registered for either the service provider or another site. To meet this need for checking, subsequent values ​​may be associated with the digital records in such a way as to subsequently prove that the subsequent value reflects the order of registration in a correct and authentic manner.

Usually, serial numbers are linked to digital records by asymmetric cryptography or by publishing, which is an alternative method. Checkable binding

- 3 is called the order certificate. Without verifiable bindings, service providers could deny the validity of anything presented as a certificate.

When asymmetric cryptography is used to make a verifiable binding, the service provider usually signs a digital record (containing the appropriate sequential value) with a digital signature or encryption algorithm such as RSA. Public key cryptography is fast enough to allow almost instant certificate generation. asymmetric cryptography

However, the use of creating digital signatures has an inherent disadvantage: the cryptographic signature keys can be corrupted. If the key has been corrupted, certificates created with that key are no longer verifiable. Because the probability of key corruption increases over time, certificates created using key cryptography are only suitable for short-term use.

If publications are used to perform a verifiable binding, the service provider usually publishes the digital record with the subsequent value to the public, for example in the press. If the service provider complies with certain publication regulations, then on published content

- 4 you can rely on it as if it were certified by the service provider. Since no cryptographic keys are used with the publishing method, there is no problem with key corruption. However, the method of using publications is slow and therefore inefficient. Publishing is possible once a day or once a week, but immediate creation of a certificate, although required by the modern electronic market, is impossible.

In order to be able to check the authenticity of the certificate in the long term and do it efficiently, you can use combined publication-based bindings and / or multi-key signatures. However, because this combination has the disadvantages of both systems, certificates need to be updated regularly, with the additional cost of maintaining binding validity.

There is another basic problem with the properties of the subsequent values ​​themselves, usually represented by integers. To some extent, verifiable links between digital records and integers can be seen by the checking parties as evidence that the records have actually received these successive values.

Often, however, subsequent values ​​assigned to digital records do not accurately reflect the actual one

- 5 time order in which the records were received. Malicious service providers can assign values ​​to subsequent records in any order they want. It is therefore necessary to be able to detect the misleading behavior of the service provider. The idea of ​​numbering records may be too abstract to reflect the registration process. For example, ensuring that three records were recorded before any particular record does not provide any information about how those records were recorded. One way to overcome this problem is to define the next record value for the specified record as a set of all records preceding the specified record in the warehouse. These "sequential values" represent the order of registration, but because they also record the history of the warehouse, the service provider cannot refuse them. However, if each subsequent value reflects the entire history of the warehouse, such values ​​can be so large that their calculation and transmission becomes impractical.

One way to confirm the service provider's history is to include a cryptographic summary of all previously registered records in the digital certificate issued to the record delivery party. For example, linear chain hashing can be created by using a function

- 6 cryptographic hashes against the concatenation of a freshly received record and the record received immediately before it. Such a method is disclosed in US Patent No. 5,136,646 (Haber et al.). Cryptographic summaries that are included in the order certificates create a causal, one-way relationship between confirmations, and therefore can be used to check their order without fear of misleading behavior on the part of the service provider, because any erroneous confirmation is detected by the verifier who examines one-way causal hashing chain. Successive values ​​created by such processes are shorter due to the use of the cryptographic hash function. However, checking such values ​​still requires calculating all records in the warehouse, and therefore may require significant processing resources. This process is also disadvantageous because it cannot be carried out without the interaction with the service provider.

In "Improving the availability of time standing services" Ame Ansper, Ahto Buldas, Mart Saarepera, Jan Willemson. ACISP 2001, [Online] 11 July 2001, pages 1-16, Sydney, Australia, describes a method of digital time stamping used to preserve the evidential value of electronic documents, time stamping protocols and time stamping

- 7 bindings are asymmetrical.

created

However, hash. This publication describes a joining approach, especially on specific linear joining schemes and weft tree joining schemes to provide digital time sealing services.

At present, effective, cryptography-proofing for many applications requires long-term verifiable bindings that can preferably be checked without using cryptographic keys. Therefore, we need a digital system for recording electronic records with procedures that allow customers to replace short-term digitally signed certificates (asymmetric cryptographic methods) with evidence based on long-term certificates that are based on cryptographic summaries and publishing methods.

The present invention aims to solve these and other problems.

The essence of the invention

The system and method of generating a digital certificate were described, in which customers submit records to the service provider for registration. These records are saved and customers receive a digitally signed certificate that confirms the registration (and registration number) of the record.

- 8 These digitally signed certificates can then be replaced by a certificate proof, which is generated by applying a cryptographic hash function to the store of all records.

In one embodiment of the present invention, a system and method for generating a digital certificate is described in which the customer presents the service provider with a digital record for registration. A complex digital value is produced that represents at least one subset of the entire history of previously received records, wherein this composite digital value is generated by applying a deterministic algorithm to items stored in the warehouse. A confirmation certificate is then generated and sent to the customer, with the certificate containing at least a digital record, a sequence number assigned to that record, and a composite digital value. This certificate is digitally signed using an asymmetric cryptographic scheme. Then the digital record or its representation is added to the magazine.

In another embodiment of the present invention, a system and method of publishing a cryptographic summary of a digital record magazine is described. A composite digital value is generated that represents at least one subset of the whole

- 9 histories of received records, where this complex digital value is generated by applying a deterministic algorithm to the elements stored in the warehouse. A complex serial number is also generated and set as equal to the current warehouse serial number. This composite digital value and the composite serial number of the magazine are then widely published.

In another embodiment of the present invention, a system and method of creating a certificate proof for a digital record is described in which the digital value of the interval for the record is generated in relation to the published composite digital value. A certificate proof is then generated, with the certificate proof containing at least a digital interval value and record sequence number, and may also include a subset of the digital record itself, a composite digital value, and a composite sequence number.

Other features and advantages of the invention will appear from the following description in connection with the following drawings.

Short description of the drawings

For the purpose of understanding the present invention, the accompanying drawings will now be exemplified, in which:

Fig. 1 is a general block diagram of the system operation and method of generating a digital certificate, showing generally the steps of registering a digital record in a warehouse, cryptographic publishing of the summary of the warehouse and generating a certificate proof for the digital record.

Fig. 2 a block diagram of the system operation and method of generating a digital certificate, detailing the procedure for registering a digital record in a warehouse and generating a digital certificate in a warehouse, and generating a digital certificate that checks record registration.

Fig. 3 is a block diagram of the operation of a system part and method of generating a digital certificate, illustrating in detail the procedure for generating the certificate proof for a digital record.

Fig. 4 is a block diagram of the operation of one system application and method of generating a digital certificate illustrating the procedure for using the certificate proof to verify receipt and the number of the next digital record.

Fig. 5 is a block diagram of the operation of one system application and method of generating a digital certificate, illustrating the procedure for using certificate evidence to verify receipt and serial numbers of more than one digital record.

Fig. 6 is a diagram of the state change of a system part and the method of generating a digital certificate, illustrating the states and transitions between them during the generation of the first digital certificate.

Fig. 7 is a diagram of the state change of a system part and the method of generating a digital certificate, illustrating the states and transitions between them during the generation of the second digital certificate and renewal of the first digital certificate.

Fig. 8 is a data structure for use with the system and method of generating a digital certificate illustrating a forest of binary hashing trees.

Fig. 9 is a data structure for use with the system and method for generating a digital certificate, illustrating a forest of binary hashing trees represented as an indexed area.

Fig. 10 is a data structure for use with a system and method for generating a digital certificate, illustrating a forest of binary trees arranged in a layered data structure.

Fig. 11 is a table for use with the system and method of generating a digital certificate, illustrating a course of operation of the algorithm for registering a digital record.

Fig. 12 shows a table for use with the system and method of generating a digital certificate,

- 12 illustrating the course of the algorithm for generating the digital interval value.

Fig. 13 is a table for use with the system and method of generating a digital certificate, further illustrating the operation of the algorithm for generating the digital interval value.

Detailed description

Although this invention is applicable in many different forms, the drawings show and describe in detail preferred embodiments, it being understood that the present description is intended to be taken as an example of the principles of the invention, and not to limit the broad aspect of the invention to the embodiments shown. .

Referring in detail to the drawings, and first to Figure 1, the system and method of generating a digital certificate are shown here. This system and method briefly includes three main functionalities. The first main functionality is the registration of a new digital record. In step 101, a new digital record is created or received. A digital record is a representation of a data element, and the data element can represent any type of digital information. For example, the data element may be an electronic document, order information, identification information or

- 13 any other type of information presented digitally. As a representation of a data element, the digital record may contain the data element in its entirety, it may contain part of that data element, or it may contain some other representation of the data element. In a preferred embodiment, the new digital record is received at step 101. In another preferred embodiment, a new digital record is created in step 101 based on the received data element, and then stored in the digital record store.

In step 102, the first deterministic function is applied to at least a subset of the digital records stored in the warehouse, thereby generating the first composite digital value. In a preferred embodiment, this first deterministic function is applied to all digital records stored in the warehouse, thereby ensuring that the first composite digital value is a representation of the entire warehouse history and thereby reduces the possibility that the warehouse owner may later falsify the contents of the warehouse.

In addition, in step 102, a new digital record is assigned a serial number. In a preferred embodiment, the sequence number represents the order in which the new digital record was received. For example, if there are ten digital records

- 14 stored in a warehouse when a new digital record is received, it will be assigned a sequential number 11. However, the sequential number can be any representation of the time or order in which the new digital record is received.

At step 103, a first certificate is generated so that the certificate confirms the receipt of a new digital record. This first certificate shall contain at least the sequence number assigned to the new digital record and the first composite digital value. In a preferred embodiment, such a first certificate may be used to check the sequence number because the sequence number indicates the time or order of receipt of the new digital record, and the first composite digital value represents the history of the warehouse, indicating when the new digital record was received.

In step 104, additional information may optionally be added to the first certificate. For example, in the preferred embodiment, the first certificate additionally contains a new digital record or part thereof. This is useful for confirming that the content of a digital record has been correctly received by the magazine. In another preferred embodiment, the additional information may be a time stamp

- the exact time when the new digital record was received.

In step 105, a digital signature is added to the first certificate. The digital signature may be any type of signature such that the signature confirms the identity of the warehouse owner. For example, a digital signature may be based on a private / public key encryption scheme such as RSA. In a preferred embodiment, the first certificate is digitally signed using the private key of the storage owner. Preferably, the first certificate is sent to the creator or provider of the digital record.

In step 106, a new digital record or its representation is added to the magazine. Step 106 of adding a new digital record to the warehouse can be performed before or after generating the first composite digital value in step 102. In a preferred embodiment, a new digital record is added to the storage after the first digital certificate has been generated in step 103, so as to reduce the time it takes to receive the first digital certificate for the provider of the new digital record. After adding a new digital record to the warehouse in step 106, you can create or receive additional digital records. In other words, the system can return to step 101.

- 16 The second main functionality of the system and how to generate a digital certificate is publishing information related to the magazine. In step 107, a second composite digital value is generated by applying a second deterministic function to at least one subset of digital records stored in the warehouse. Like the first composite digital value, the second composite digital value represents the history of the magazine at a given time. In a preferred embodiment, the first and second deterministic functions are not the same functions. Preferably, the second deterministic function is applied to all digital records stored in the warehouse, and therefore the second composite digital value represents the entire history of the warehouse, thereby reducing the risk that the warehouse owner may falsify the warehouse.

At step 108, a composite sequence number is generated, wherein this sequence number corresponds to the order in which the second composite digital value is generated. The composite sequence number is therefore a sign of the temporal quality of the second composite digital value. In step 108, the second composite digital value and composite sequence number are published, i.e., sent to the public. A public forum can be any source of information that is available to

- 17 ordinary audiences. For example, a public forum can be a newspaper, magazine, website or email.

The third main functionality of the system and how to generate a digital certificate is the creation of a second certificate, which testifies to the authenticity of the number of the next new digital certificate. At step 109, a digital interval value is generated, wherein the digital interval value is based on the first and second composite digital values. In a preferred embodiment, the digital interval value is the result of applying a third deterministic function to the digital records stored in the warehouse between receiving a new digital record and generating a second composite digital value. The value of the digital interval may therefore reflect the history of the magazine between receiving a new digital record and publishing the second composite digital value. However, the digital interval value can also be the result of a deterministic function used for all digital records stored in the warehouse, thereby reflecting the entire warehouse history.

At step 110, a second certificate is generated, wherein the second certificate includes at least a digital interval value and a new sequence number

- 18 digital records. Because this digital interval value reflects the warehouse history since the new digital record was added to the warehouse or earlier, the digital interval value can be used to confirm the accuracy of the sequence number. The digital interval value can also be used to refresh, i.e. extend the authenticity of a new digital record. Since the generation of the digital interval value is not based on the use of encryption keys, the security of the second digital certificate is not a compromise as is the case with the encryption key.

Fig. 2 shows in detail the steps of the method for generating a digital certificate. In step 106, a new digital record 200 is added to storage 210. In step 205, the first deterministic function is applied to at least a subset of the digital records stored in the storage, so as to produce the first composite digital value 204. The step of adding a new digital record 200 to the magazine 106 may be carried out either before or after the step of applying the first deterministic function 205 to the magazine 210. The next number 202 is assigned to the new digital record 200, this sequence number representing the time value of the new digital

- 19 record 200, i.e. the order in which the new digital record 200 was received.

In step 103, the first certificate 201 is generated. The first certificate 201 contains at least the first composite digital value 204 and the subsequent number 202 of the new digital certificate 200. In addition, the first certificate 201 may contain the new digital record 200 alone and other additional data 207. In step 208 the first certificate 201 is signed with digital signature 209, the digital signature 209 is preferably based on a public key encryption scheme.

In step 213, a second deterministic function is applied to the digital records stored in storage 210 to generate a second composite digital value 212. A composite sequential number 217 is generated and is preferably set to be equal to the currently next available sequential number in storage 210. At step 109, an interval 214 digital value is generated, wherein this interval 214 digital value reflects the time difference between receiving a new digital record 200 and generating a second composite digital value 212. Finally, at 110, a second certificate 215 is generated, with the second certificate 215 contains at least the next number 202 of the new digital record 200 and a digital value

- 20 212 interval. In addition, as indicated in step 110, the second certificate 215 may include all or part of the first certificate 201 and the subsequent filed number 217.

Fig. 3 details the verification steps of the second certificate 215 in detail. The first certificate 201 is received from server 302 by client 301, the first certificate 201 being preferably signed by digital signature 209. Optionally, after receiving the first certificate 201, a signature verification procedure 308 is performed, to initially confirm the authenticity of the first 201 certificate. Preferably, the signature checking procedure 308 involves using a key-based encryption scheme.

The first certificate 201 is received by the second client 303, and a signature verification procedure 308 is performed to confirm the authenticity of the first certificate 201. In the preferred embodiment, after determining in step 308 that the digital signature 209 of the first certificate 201 is invalid, the second client 303 will be unable to confirm or recognize the validity of the first certificate 201. After confirming that the digital signature 209 of the first certificate 201 is valid, the first certificate is sent to the second server

304, where the first certificate is renewed,

- 21 extended and recognized as valid by applying the method described here for generating the second certificate 215. The second certificate 215 is then sent to the second server 304. The published second digital composite value 212 and the composite sequence number 217 are publicly available to the second customer 303. Based on these value, the second certificate 215 and the first certificate 201, the second customer 303 can verify the validity of the next number 202 through the verification process 307. After confirming that the first certificate 201 and the second certificate 215 are compatible, the second client 303 may rely on the authenticity of the next number 202 and the digital record 200 provided by the first customer 301.

Fig. 4 shows in detail another embodiment of the system and method of checking the digital record 200. The digital record 200 is sent from the client 402 to the checking server 401. A second certificate 215 is received from the extension server 403, where the process of generating the second certificate 215 was carried out. The second composite digital value 212 and the composite sequential number 217, together referred to as public values ​​212, are published on public server 404 and are received by checking server 401. So, checking

- 22 server 401 may be based on the validity of digital record 200 provided by client 402.

Fig. 5 shows in detail an example of system implementation and method of recording digital records, where the checking server 501 can check the order of sequential values ​​202 of competing digital records 200 provided by first and second clients 502 and 504, respectively. First client 502 sends the first digital record 503 to the checker. server 501 with a second 509 certificate corresponding to the first 503 digital record. Second client 504 sends a second digital record 510 to the checking server 501 along with a second certificate 511 corresponding to the second digital record 510. Thus, the checking server 501 can use the system and method described herein to determine which of the competing digital records 200 was previously stored.

Public values ​​512, published on public server 506, are received by check server 501. Using the check process 507 described here, check server 501 can rely on the first and second digital records 200 and accompanying second certificates to determine which of the 200 digital records are authentic. In addition, because the next 202 numbers of 200 digital records are reflected in

- 23 second certificates 215, checking server 501 can also determine the authentic order of receiving 200 digital records.

Fig. 6 is a state change diagram further illustrating the states and transitions between them in the process of registering a new digital record and generating the first digital certificate. At step 603, a recording system is initialized. The next value is set to zero, the magazine is cleared of digital records and complex digital values ​​are deleted. At step 602, the system is waiting to receive the digital record. After receiving the digital record in step 604, the first composite digital value is generated. In step 506, a sequential value is assigned to the new digital record and the first digital certificate is generated according to the procedures described herein. This first digital certificate is digitally signed. Finally, a new digital record is added to the magazine. After the registration is completed in step 605, the system returns to the standby state 602 to receive another new digital record.

Fig. 7 is a state change diagram further illustrating the states and transitions between them in the process of extending the first digital certificate. The system starts in step 701 and in step 703 the system is initialized. The second composite digital value is

- 24 generated by applying a second deterministic function to the warehouse and a second complex subsequent value is generated. Then the system goes to state 702 waiting for the second certificate to be received. If no certificate is received, the system may indirectly return to step 703 to reinitialize and re-generate composite values. When the digital certificate is received, at 704 a digital interval value is generated according to the process described herein. After generating the digital interval value, the system generates a second digital certificate in step 705. Finally, the system returns to the state 702 waiting to receive another digital certificate. In a preferred embodiment, since the generation of the second digital certificate is dependent on the content of the first digital certificate, the system can be used to renew or extend the authenticity of the first digital certificate. The system can also be used to check the authenticity of the first digital certificate and can also be used to check the authenticity of the digital record corresponding to the first digital certificate.

Fig. 8 is a diagram illustrating a data structure for use with the system and method of generating a digital certificate. In favorable

- An embodiment is a data structure forest of binary hash trees in which each parent vertex of a binary tree is cryptographically hashed with child vertices. The construction of such a binary hashing tree is implemented on the fly based on receiving new digital records. New digital records are represented by hash values ​​of a specific size and are saved as 802 binary hash tree lists. Due to the use of the data structure with binary trees, the number of digital records stored in the warehouse does not have to be known, and the topological parameters of the warehouse, such as height and width, do not need to be specified. Fig. 8 thus shows the storage data structure with binary hash trees after receiving six digital records.

The tops of 802 leaves of such a forest are naturally organized. The next number n of the leaf defines its location in the forest. If a new xn data record is received, it is first stored as a leaf with a subsequent value of n, and then the tree is updated. The upgrade process is organized to ensure that only the main forest vertices 801 will participate in future generations of complex digital values. The list of main vertices provides a hash for use in generation

- 26 complex digital composite value generation. During the digital value process, every vertex of the structure that can be calculated is calculated and immediately saved. All 802 leaves are stored in their order of calculation, preferably corresponding to the subsequent tree arrangement. Because the major vertices 801 already represent the hash values ​​of the 802 leaf vertices, these 802 leaf vertices do not need to be considered when generating a composite digital value. The data forest with binary hash trees therefore ensures very fast processing of complex digital values.

Fig. 9 is a diagram of a data structure for use with a system and method for generating a digital certificate in which a data structure forest with binary hashing trees is further depicted as an indexed array. The elements of this array representing the forest are saved in the order they are calculated. In other words, the elements calculated earlier in time have smaller indicators than the elements calculated later. The process of building a forest data structure preferably depends on the use of a stack containing the main hashing values ​​h1 ... hs, where hs is located at the top of the stack. If (x0 ... xn-1) are forest leaves, the number of elements in the stack is equal

- 27 number of bits set in the binary representation of n. Each added leaf changes some values ​​at the top of the stack, and the number of changed values ​​equals the number of rightmost bits of the one in the binary representation of n. For example, if n = 23, the nth addition changes three elements stack because 23 = 101112.

Fig. 10 is a schematic diagram of a data structure for use with a system and method for generating a data certificate, wherein this data structure is further depicted as a layered forest of binary hashing trees. It is beneficial to organize the binary tree in layers to efficiently calculate the digital interval value. The nth layer 1001 is defined as the minimum subset of vertices that meet two assumptions. First, these layers meet the assumption that for all n, leaf xn belongs to the nth layer. Secondly, the layers satisfy the assumption that if one of the child vertices of vertex belongs to the n-th layer, and the other child vertex belongs to the layer (nk) -th (where ke {0 ... n}, then vertex also belongs to the nth layer Fig. 10 shows an example of a binary hashing tree with six nodes organized in layers.

Fig. 11 is a table illustrating the operation of the algorithm for use with the system and method

- 28 digital certificate generation. In the preferred embodiment, the algorithm for recording the digital record, where n represents the serial number in the warehouse, and x represents the new digital record, is as follows:

Composite_va] ue = [], Repository = [] n: = 0 rcpeat

Receive_Record (x)

Reply (λ, Compostte_value, Jt)

Append (Repository. X)

Update (Repository, Composiie_va1ue, n, x) n η + 1 where "Composite_value" is a composite value, "Repository" is a magazine, and "Record" is a record.

Fig. 11 is a flowchart of the algorithm with the digital records being entered [x0, x1, x2, x3, x4]. Update function (Repository,

Composite_value, n, x) can also be defined as follows:

an while Odd (a) do jc Hash (Pop (Composiie_value), jc) Append (Repository, jf) aa »1

Push (Composite_vaJue, x)

Fig. 12 is a table illustrating the course of the algorithm for use with the system and method of generating a digital certificate. In favorable

- 29 example implementation, the algorithm for generating the digital interval value, where n is the sequence number in the warehouse, and N is the composite sequence value, is as follows:

head U, weight: = (U: = JMi + l, i: = 1 while /: = [(n © &) or (£> - 1)] <N do if ά & / 1 = fc

Append (head_t Rcpository [2f ~ j + 2]) else

Append (lail, Repository b: = b «\

Fig. 12 shows the operation of this algorithm, where n = 4 and N = 7. Fig. 13 shows the operation of the algorithm, where n = 3 and N = 7.

It should be understood that the invention may be implemented in other specific forms without departing from its spirit or its main characteristics. Current embodiments should therefore be considered in all respects as illustrative rather than limiting and the invention should not be limited to the details set forth herein.