CN1985460B - Communication Valid Realtime Credentials for OCSP and Distributed OCSP - Google Patents

Abstract

Facilitating a transaction between a first party and a second party includes: prior to initiating a transaction, one of the parties to the transaction obtains an artificially pre-computed OCSP response for the particular digital certificate, wherein the artificially pre-computed OCSP response was generated by an entity other than the first party and the second party; one of the transaction parties initiates a transaction; at the time of a transaction, the first party provides a specific digital certificate to the second party; and the second party verifies the particular digital certificate using the artificially pre-computed OCSP response. The second party may obtain a manually pre-computed OCSP response before the transaction begins. The second party may cache the artificially pre-computed OCSP responses for future transactions. The first party may obtain a manually pre-computed OCSP response before the transaction begins. The first party may cache the artificially pre-computed OCSP responses for future transactions.

Description

Communication Valid Realtime Credentials for OCSP and Distributed OCSP

Related Application Cross Reference

This application claims priority to US Provisional Application 60/535,666, filed January 9, 2004, and US Provisional Application 60/536,817, filed January 15, 2004, both of which are incorporated herein by reference.

Background of the invention

1. Technical field

This application relates to the field of digital certificates, and in particular to the field of verifying and validating digital certificates and other information.

2. Background technology

Digital signatures provide an efficient form of Internet authentication. Unlike traditional passwords and PINs, digital signatures authenticate transactions in a ubiquitously verifiable manner. Therefore, negating a transaction that has been digitally signed is difficult, but not impossible. The digital signature is generated by the signing key SK and verified by the matching verification key PK. User U keeps his own SK secret so that only U can sign on U's behalf. Fortunately, the key PK does not "betray" the matching key SK; ie knowledge of PK does not provide any real advantage in computing SK. Therefore, user U can make his own PK as public as possible, so that everyone can verify U's signature. For this purpose, the PK is called a public key.

A digital certificate is an alphanumeric string that enables digital signatures by guaranteeing that a given key PK is really the user U's public key. A certification authority (CA) generates and issues certificates to users, but usually only after the user's identity has been established. Thus, the certificate proves that the CA has verified the identity and other attributes of the holder. Certificates expire after a specified time, usually one year in the case of public CAs.

In general, a digital certificate C consists of a CA digital signature that securely binds together several numbers: the serial number SN unique to the certificate, the user's public key PK, the user name U, and the date of issue D ₁ , expiration date D ₂ , and other data. Expressed as symbols:

C=SIG _CA (SN, PK, U, D ₁ , D ₂ ,...)

It would be useful to be able to determine the status of a digital certificate, including determining whether a particular certificate was validly issued and/or determining whether a certificate was revoked before it expired. There are many techniques that can be used to determine the status of an individual digital certificate. For example, US Patents 5,666,416 and 5,717,758 describe techniques for providing a single certificate status. Other techniques for distributing and determining the status of a certificate are also well known, including the Certificate Revocation List (CRL), which is a digitally signed list of revoked certificates, and the Online Certificate Status Protocol (OCSP), which provides for querying the status of a particular certificate. mechanism.

CRLs work by having each CA periodically issue an appropriately dated and digitally signed list (CRL) containing the serial numbers of revoked certificates. In some practices, a CRL contains all revoked certificates for a given certificate group. Thus, the digital certificate can be presented with the electronic transaction compared to the most recent CRL. If a given certificate has not expired but is on the list of revoked certificates, it is known from the CRL that the certificate is invalid and the certificate holder is no longer authorized to perform transactions enabled by the digital certificate. On the other hand, a certificate is considered valid if it does not appear in the CRL. Alternatively, the CRL may be archived with other records of each transaction to be able to prove the validity of the transaction in the future, or to justify a denial of service in the case of a revoked certificate.

Assuming that the revocation rate is 10%, on average 1 out of 10 digital certificates will be revoked before its expiration. With such a revocation rate, a system with 10 million certificates will generate a CRL containing 1 million sequence numbers, which can make the CRL difficult to handle. Although this problem can be mitigated by the recent emergence of CRL partitioning techniques, the basic strategy of bundling together revocation information for many certificates can still be inconvenient and costly. If the sequence number is 24 bits long (to handle several million certificates), a child CRL for 1000 certificates will be 24000 bits (3000 bytes) long. In some deployments, due to overhead, each certificate's CRL entry is 22 bits long, so a sub-CRL for 1000 certificates is 22000 bits long. But in some cases this is unacceptable, for example in the case of wireless transactions it is impractical to have to transmit so many bits (protecting future disputes and possible legal claims).

CRLs grow larger because they provide proof of revocation (and thus indirectly proof of validity) of many certificates grouped together. By comparison, OCSP can provide proof of the validity of each certificate. Traditional OCSP services use an OCSP responder that can receive a question from a client (i.e. a relying party) about the validity of a given certificate issued by a given CA, in response to which OCSP can provide a digitally signed answer specifying The status of the certificate and time information about the answer.

To be able to provide OCSP services, conventional OCSP responders are provided with information about the status of all certificates of the CA. Since normally a CA can determine the status of its own certificate, if the OCSP responder is the CA itself, the OCSP responder/CA already has information about the revocation status of the certificate. On the other hand, if the OCSP responder is not a CA, the OCSP responder may be held to renew the CA's certificate status. See, eg, US Patent 5,717,758: Evidence-Based Certificate Revocation System.

The CA can update the OCSP responder by sending the most recent CRL. An OCSP responder can consult this CRL to infer whether a particular certificate of interest is currently valid or has been revoked, so that the OCSP responder can provide a signed response to the relying party indicating the time of the current CRL, the time of its next update, and the actual processing time.

Of course, a malicious/compromised OCSP responder could provide arbitrarily signed answers on a given CA's certificate, with or without any CRLs. Thus, to enable relying parties to safely rely on answers digitally signed by an OCSP responder about a given CA's certificate, OCSP includes mechanisms for the CA to provide the OCSP responder with the responder's certificate, a special digital certificate signed by the CA that essentially provides other The party vouches that the CA trusts the OCSP responder to provide accurate proof of the CA's certificate. It should be noted that for this process to work properly, each OCSP responder (and each CA) must have a privately signed key, and this key must be protected (such as by placing the server implementing the responder in a safe protected in the library).

Referring to FIG. 1, a schematic diagram 40 shows information flow in a traditional OCSP environment. Diagram 40 includes CA 42 , legacy OCSP responder 44 , and relying party 46 . The bold lines for CA 42 and OCSP responders 44 indicate that there are keys that must be protected for the system to function reliably. CA 42 provides validity information 48 (eg, CRL) to OCSP responder 44 . The relying party 46 makes other OCSP requests 52 to the OCSP responder 44 . OCSP responder 44 checks the validity information provided by CA 42 (eg in the form of a CRL) and determines the validity status of the certificate involved. OCSP responder 44 then prepares a corresponding response, which is digitally signed and provided to relying party 46 as a result of OCSP responder 54 . In some cases, OCSP responder 44 may also provide responder certificate 56 to relying party 46 , which indicates that OCSP responder 44 is authorized and trusted by CA 42 .

But OCSP has a big flaw. First, a digital signature is an operation in a computational set. The digital signature established on each OCSP response by a conventional OCSP responder is generated on request and is possibly the most computationally intensive part of the validation operation. For example, generating a digital signature can add 50 milliseconds to 1 second to transaction time. Even if a conventional OCSP responder caches the digital signature on C after the digital certificate C is first challenged, and sends the cached signature when C is challenged later, since the initial digital signature is generated, the first user's answer to the challenge C will still be greatly delayed.

Furthermore, if there is only one OCSP responder, all certificate validity queries are actually sent to that single OCSP responder, after which it becomes a major network bottleneck and causes considerable congestion and delay. If a large number of honest users suddenly query the OCSP responder, an outage-denial-of-service situation will ensue.

On the other hand, to prevent problems with centralized OCSP implementations, organizations may consider distributing the request load (with respect to the validity of their certificates) across several properly certified, legacy OCSP responders. In general, distributing the load of a single server across several (eg, 100) servers strategically distributed around the world (to avoid transmission bottlenecks) reduces network congestion. However, with OCSP, load distribution can cause additional problems because, to provide signed responses to certificate validity queries, each of the 100 distributed legacy OCSP responders has its own privately signed key. Thus, compromising any one of the 100 servers can effectively compromise the entire few. In fact, if a legacy OCSP responder is compromised, an attacker can use a discovered secret signing key to falsely sign a response indicating that (1) a valid certificate has been revoked, or (2) a revoked certificate is still valid. This latter type of false positive response may allow an employee who has been fired to regain access to the system.

One way to prevent transponders from being compromised is to run the transponders from a secure vault, which has 24/7 monitoring. Unfortunately, this is a very expensive option. A truly safe vault, such as a vault that meets all the requirements of a financial CA, requires more than $1 million to establish, and the annual operating cost is also around $1 million. Furthermore, even if institutions were willing to pay for such expenditures, vaults cannot be built overnight. So if a CA needs several vaults to offload its current legacy OCSP responders, there will be a delay of several months before new properly secured OCSP responders can be built.

Also, incurring the cost of several vaults does not solve the OCSP security problem. This is because the OCSP mechanism requires a conventional OCSP responder to receive a request from an untrusted source (relying party) and to service the request using the responder's privately signed key. Therefore, a malicious relying party (or a malicious agent masquerading as a relying party) would prefer to expose the OCSP responder-signed key by finding a possible weakness in the base operating system.

Furthermore, there are several difficulties associated with OCSP when servicing certificate validity requests originating from different security domains. For example, a traditional OCSP responder run by organization A can easily provide a response about the certificate status of organization A's CA, but an OCSP responder run by another organization does not have enough information to provide information about the "foreign" certificate. response.

This problem, which stems from a lack of specific knowledge, can be dealt with in one of two ways. First, a relying party from organization B can obtain the certificate status of organization A's CA from organization A's responder. However, this limits performance because the OCSP responder from Agency A may be geographically far from the relying party of Agency B, so that network time can significantly slow down the entire validation process. The second way is to allow a responder from organization B to respond with respect to organization A's certificate by having the CA from organization A forward organization A's CRL to the foreign responder. In fact, the CRL is digitally signed and thus need not be kept secret, and the CA of organization A should reasonably wish to inform as many audiences as possible of the validity status of organization A's certificate. This second way provides enough information to Authority B's OCSP responder to answer a request from a relying party regarding Authority A's certificate. Were it not for the relying party to value digitally signed answers from organization B's OCSP responder, organization A's CA should also certify that the foreign responder is trustworthy in answering queries about the validity of organization A's certificate.

Referring to FIG. 2 , schematic diagram 60 shows CA 42 , legacy OCSP responder 44 , and relying party 46 shown in schematic diagram 40 of FIG. 1 . However, in the situation shown in diagram 60 , relying party 46 provides an OCSP request 62 for a certificate not managed by CA 42 but issued and managed by a different CA 64 . In this case, OCSP responder 44 may not provide an OCSP response to OCSP responder 44 based solely on information within CRL 48 provided by CA 42 . Instead, the CA 64 provides a different CRL 66 and a different responder certificate to the OCSP responder 44 . The OCSP responder 44 then formulates an OCSP response 72 for the foreign certificate using a different CRL 66 . In some cases, OCSP responder 44 may also provide responder certificate 68 to relying party 46 .

This second approach may provide better scalability and performance, but it messes up the security and trust flow between the two organizations. In diagram 60, OCSP responder 44 is giving the relying party an authoritative response that the certificate of CA 64 is still valid. If the OCSP responder 44 gives an incorrect response for any reason (misconfiguration, hostile attack, or outright dishonesty), the OCSP responder 44 may negatively affect the CA 64's authority. By allowing OCSP responder 44 to make an authority statement about CA 64's certificate, CA 64's authority relinquishes some of the trust it previously held.

As an example, assume the institution is a credit card issuer. The bank from Institution A revokes the user's certificate, and the bank ensures that Institution A's legacy OCSP responder is safe and secure. Assuming that Agency B's OCSP responder is misconfigured, when Agency B's Merchant Relying Party asks for the user's validity, Agency B's responder incorrectly replies: User is valid. The merchant accepts the answer and allows the void user's transaction to proceed. This type of trust delegation between agencies is acceptable in some circumstances, but is of little use for any large-scale disparate deployment of traditional OCSP.

It is therefore desirable to provide a system that addresses the above difficulties.

Contents of the invention

According to the invention, providing information about the validity of digital certificates includes determining a digital certificate validity status for each of a plurality of digital certificates in a set of digital certificates, generating information about at least a subset of the set of digital certificates of the plurality of digital certificates a plurality of artificially precomputed messages of validity status, at least one of which indicates the validity status of more than one digital certificate, and digitally signing the artificially precomputed messages to provide an OCSP formatted response that responds to a specific number in the set of digital certificates OCSP query for certificates where at least one digital signature is used with OCSP formatted responses for more than one digital certificate. Generation and digital signing can be done before any OCSP query is answered by any OCSP formatted response. Determining the validity status of the digital certificate includes obtaining authenticated information about the digital certificate. Authenticated information about the digital certificate may be generated by the entity revoking the certificate. The authenticated information about the digital certificate may be a CRL. Generating a plurality of manually pre-computed responses may include generating responses for at least all non-revoked digital certificates in the set of digital certificates. Providing information about the validity of digital certificates may also include, after digitally signing a manually pre-computed message, forwarding its results to a plurality of responders servicing requests from relying parties interrogating digital certificates in the set of digital certificates validity status. Providing information about the validity of the digital certificate may also include making available to the responder a special digital certificate containing a public verification key used to verify a digital signature provided when digitally signing a manually pre-computed response. An entity that issues a particular digital certificate may also issue a certificate for a set of digital certificates. Generating a plurality of artificially precomputed responses and digitally signing the artificially precomputed responses may be performed periodically. The artificially precomputed response may include temporal information corresponding to when the artificially precomputed response was generated.

According to the present invention, computer software stored on a computer-readable medium that provides information about the validity of digital certificates includes executable code for determining the validity status of digital certificates for each of a plurality of digital certificates in a set of digital certificates, generating Executable code for a plurality of artificially precomputed messages regarding the validity status of at least a subset of a set of digital certificates of a plurality of digital certificates, wherein at least one message indicates the validity status of more than one digital certificate, and digitally signs the artificial precomputed The computed message is executable code providing an OCSP formatted response in response to an OCSP query regarding a particular digital certificate in the set of digital certificates, wherein at least one digital signature is used for more than one digital certificate along with the OCSP formatted response. The executable code that determines the validity status of the digital certificate includes obtaining authenticated information about the digital certificate. Authenticated information about the digital certificate may be generated by the entity revoking the certificate. The authenticated information about the digital certificate may be a CRL. The executable code generating the plurality of manually pre-computed responses may include generating responses for at least all non-revoked digital certificates in the set of digital certificates. The computer software may also include executable code that forwards the digitally signed, manually pre-computed message to a plurality of responders servicing requests from relying parties that inquire about the validity status of digital certificates in the set of digital certificates. The computer software may also include executable code that makes available to the responder a special digital certificate containing a public verification key used to verify the digital signature provided when digitally signing a manually pre-computed response. An entity that issues a particular digital certificate may also issue a certificate for a set of digital certificates. The executable code that generates the plurality of artificially precomputed responses and digitally signs the artificially precomputed responses may periodically generate and sign the responses.

According to the invention, providing information about the validity of a digital certificate includes obtaining a plurality of signing key/verification key pairs, where each signing key provides a digital signature and a corresponding verification key to verify the digital signature, wherein the signing key is used to Digitally signing multiple data elements together is more computationally efficient than digitally signing each data element individually, determining the digital certificate validity status for each certificate in a set of digital certificates, producing at least one subclass of the digital certificate set Multiple manually precomputed messages that set the validity state of the set and digitally sign the manually precomputed messages together using the signing key from the key pair. Determining the digital certificate validity status may include obtaining authenticated information about the digital certificate. Authenticated information about the digital certificate may be generated by the entity revoking the certificate. The authenticated information about the digital certificate may be a CRL. The manually precomputed response may be an OCSP format response. Generating a plurality of manually precomputed responses includes generating responses for at least all non-revoked digital certificates in the set of digital certificates. Providing information about the validity of digital certificates may also include, after digitally signing a manually pre-computed message, forwarding its results to a plurality of responders servicing requests from relying parties interrogating digital certificates in the set of digital certificates validity status. Generating a plurality of artificially precomputed responses and digitally signing the artificially precomputed responses may be performed periodically. The artificially precomputed response may include temporal information corresponding to when the artificially precomputed response was generated. Providing information about the validity of the digital certificate may include authenticating a verification key. Authenticating the verification key includes providing the verification key in a single digital certificate. Authenticating the verification keys may include providing each verification key in a separate digital certificate.

In accordance with the present invention, computer software stored on a computer-readable medium that provides information about the validity of a digital certificate includes executable code that obtains a plurality of signing key/verification key pairs, where each signing key provides a digital signature and The digital signature is verified by a corresponding verification key, where digitally signing multiple data elements together using the signing key is computationally more efficient than digitally signing each data element individually, determined for each certificate in a set of digital certificates executable code for generating a plurality of manually precomputed messages about the validity status of at least a subset of the set of digital certificates, and digitally signing them together using a signing key from the key pair Executable code for manually precomputed messages. The executable code that determines the validity status of the digital certificate may include executable code that obtains authenticated information about the digital certificate. Authenticated information about the digital certificate may be generated by the entity revoking the certificate. The authenticated information about the digital certificate may be a CRL. The manually precomputed response may be an OCSP format response. The executable code that generates the plurality of manually pre-computed responses includes executable code that generates responses for at least all of the digital certificates in the set of digital certificates that are not revoked. The computer may include executable code that authenticates the verification key. The executable code authenticating the verification keys may provide the verification keys in a single digital certificate or provide each verification key in separate digital certificates.

According to the invention, facilitating a transaction between a first party and a second party includes, prior to initiating the transaction, one of the transacting parties obtaining a manually pre-computed OCSP response for a particular digital certificate, wherein the manually pre-computed OCSP response is determined by a different The entities of the first party and the second party are generated, and one of the transaction parties starts the transaction. During the transaction, the first party provides a specific digital certificate to the second party, and the second party uses the artificially pre-calculated OCSP response to verify the specific digital certificate. The second party can obtain a manually precomputed OCSP response before the transaction begins. The second party may cache the manually precomputed OCSP responses for future transactions. The first party can get a manually precomputed OCSP response before the transaction starts. The first party may cache manually precomputed OCSP responses for future transactions. Facilitating the transaction between the first party and the second party may also include the first party providing a manually precomputed OCSP response to the second party after the transaction is initiated.

According to the present invention, determining the validity of the digital certificate includes checking a digitally signed message about the validity of the digital certificate, wherein the message is digitally signed by a special entity other than the entity that issued the digital certificate, and further includes using information from at least one of Information authentication Digitally signed messages: a digital certificate and a certificate authenticating the entity that issued the digital certificate. The information may be a public key corresponding to the secret key used to digitally sign the message. The information may correspond to a particular digital certificate authenticating the particular entity that digitally signed the message.

According to the present invention, determining the digital certificate validity status for each certificate in the digital certificate set includes periodically generating a plurality of digitally signed manually pre-calculated messages about the validity status of at least a subset of the digital certificate set, and periodically converting the digitally signed A manually precomputed message of , is forwarded to multiple responders serving requests from relying parties that inquire about the validity status of digital certificates in the set of digital certificates, where messages about some certificates are written differently from messages about other certificates frequency for forwarding. Messages about revoked certificates may be forwarded less frequently than messages about valid certificates.

In accordance with the present invention, computer software stored on a computer-readable medium for determining the validity of a digital certificate includes executable code that checks a digitally signed message regarding the validity of the digital certificate, where the message is issued by a special entity other than the entity that issued the digital certificate. The entity digitally signs, and further includes executable code that verifies the digitally signed message using information from at least one of: a digital certificate and a certificate authenticating the entity that issued the digital certificate. The information may be a public key corresponding to the secret key used to digitally sign the message. The information may correspond to a special digital certificate authenticating the particular entity that digitally signed the message.

According to the invention, computer software stored on a computer readable medium that provides information about the validity of digital certificates includes executable code that determines the validity status of the digital certificates for each certificate in the set of digital certificates, periodically generates a plurality of digitally signed executable code for manually precomputed messages regarding the validity status of at least a subset of the set of digital certificates, and executable code for periodically forwarding digitally signed manually precomputed messages to a plurality of responders serving requests from relying parties Code that the relying party queries the validity status of digital certificates in a set of digital certificates, wherein messages about some certificates are forwarded with a different frequency than messages about other certificates. Messages about revoked certificates may be forwarded less frequently than messages about valid certificates.

The system described here is a cost-effective, secure, scalable, and overall efficient validation system that greatly improves upon conventional methods. The system described here has significant advantages over traditional OCSP, even while maintaining compatibility with the OCSP standard, thereby providing superior security and scalability in quality.

The system described here is a general, stand-alone system that works independently of traditional OCSP. However, in some embodiments, the system may be OCSP compliant, wherein each proof of validity according to the system described herein is constructed as a syntactically correct digitally signed OCSP response such that a relying party requests and then OCSP format verification certificate validity information, etc. Digital signatures are computationally intensive operations, but the system described here concentrates this difficulty on a single dedicated server, or, in other embodiments, on a small number of dedicated servers. Therefore, it is very easy and relatively cheap to provision a single dedicated server (or a small number of servers) with enough computing power to process all the necessary digital signatures on each update. Responders used in the system described here need only perform ordinary read-and-forward operations, and thus can service incoming relying party queries more quickly than traditional OCSP responders, which must perform complex digital signatures .

Since the transponders used in the system described herein can be implemented with common hardware and require no protection, transponders can be purchased and operated relatively cheaply. Thus, a relatively large number of transponders can be deployed with relatively low overhead. Thus, even if a large number of certificate validity status requests are generated in a short period of time, the load can be distributed to many responders, thereby eliminating congestion and the risk of benign denial of service without too much overhead. It should be noted that the number of digital signatures used in the system described here depends on the number of certificates and is relatively independent of the number of validity status requests. Thus, a single server can be used to provide digitally signed responses even if a considerable number of validation requests are expected.

In the system described here, only one dedicated server (or a small number of dedicated servers) and the CA (if other than a single dedicated server) need to be protected/vaulted. In fact, the transponders of the system described here do not hold any secret keys: they only hold digital signatures of the pre-computed responses provided to the transponders, which, once computed, cannot be maliciously modified and thus do not need to be kept secret. In contrast, all conventional OCSP responders need protection because each of them has a secret signing key, the compromise of one of which will compromise the entire system. Therefore, the system described here is more secure than OCSP because it is preferable and easier to protect one site (or a small number of sites) than many equally important sites.

Furthermore, unlike the OCSP case, relying parties cannot easily install software exploits on the systems described herein. Even if the relying party succeeds in embedding some type of Trojan horse in its query, it cannot make any secrets public, because the responders of the system described here do not hold any secrets: the responders only save and return the Precomputed digital signatures. Therefore, any malicious relying party wishes to disclose a full, accurate, and digitally signed account, including which certificates are valid and which have been revoked for a given time interval. However, not only is this not secret information, but in fact it is information that the CA wishes to make widely known in order to prevent relying parties from incorrectly relying on a revoked certificate issued by the CA.

Also, it should be noted that software exploits cannot be easily installed against a single dedicated server (or a small number of dedicated servers) that digitally signs precomputed responses. In some embodiments, a single dedicated server (or a small number of dedicated servers) does not process requests from untrusted sources, but simply receives information from the CA and provides digitally signed information to the responder. Therefore, it is not possible to insert a Trojan horse in the system described here.

In addition to these advantages, the system described herein enables great flexibility in heterogeneous deployments involving multiple institutions. A responder from one institution can forward a manually pre-computed response to another without distributing any trust to the other institution. A first authority can cause another authority's responder to provide the first authority with trusted proof of validity without relinquishing any amount of control over the validity status of the first authority's certificate. That is, in the systems described herein, trust can flow from one institution to another without any loss of security or control. In some embodiments, responders may be treated as transparent network infrastructure rather than hardened trust points. This is similar to the cloud of services provided by the Internet's DNS infrastructure in that it allows for a heterogeneous collection of name servers that operate transparently with each other to discover and cache valid responses to queries.

Secure heterogeneity is the main advantage of the system described here over traditional OCSP. The secure heterogeneity allows multiple organizations to operate cooperatively, so that relying parties from different organizations can cross-confirm certificates from other organizations in a safe, reliable, and effective manner.

The system described here provides all validation trust in a single authority (or a small number of authorities), while distributing the query load across any number of unprotected responders. The system described here does not compromise security, even if the distributed implementation relies on a substantial number of transponders, even if unprotected. The system described herein improves response time to queries. The system described here does not authorize trust to foreign transponders in a heterogeneous environment.

Description of drawings

Figure 1 shows a prior art system for providing OCSP responses to relying parties.

Figure 2 shows a prior art system for providing OCSP responses in a heterogeneous environment.

Figure 3 illustrates an RTC system according to an embodiment of the system described herein.

Figure 4 is a flowchart for initializing RTCA according to an embodiment of the system described herein.

Figure 5 is a flow diagram of communication between a CA and RTCA according to an embodiment of the system described herein.

Figure 6 is a flow diagram for pushing data from an RTCA to an RTC transponder according to an embodiment of the system described herein.

7 is a flow diagram of an RTC transponder acquiring data from an RTCA according to an embodiment of the system described herein.

8 is a flow diagram of an RTC responder providing information to a relying party according to an embodiment of the system described herein.

FIG. 9 is a flowchart of an RTC responder obtaining validity information according to an embodiment of the system described herein.

FIG. 10 is a flow chart of obtaining validity information by an RTC responder according to another embodiment of the system described herein.

Figure 11 is a flowchart of steps performed in facilitating a transaction between two parties according to an embodiment of the system described herein.

Figure 12 is a schematic diagram of a digital certificate according to an embodiment of the system described herein.

Figure 13 is a schematic diagram of data flow between CA, RTCA, RTC responder and relying party according to an embodiment of the system described herein.

14 is a schematic diagram of data flow between the CA, RTCA, RTC responder and relying party of the first system and the CA, RTCA, RTC responder and relying party of the second system, according to an embodiment of the system described herein.

15 is a schematic diagram of a heterogeneous cloud of RTC transponders according to an embodiment of the system described herein.

Figure 16 is a flow diagram for optimization according to an embodiment of the system described herein.

Figure 17 is a schematic diagram of a licensing authority according to an embodiment of the system described herein.

18 is a schematic diagram of data flow between a CA, SERTCA, RTC responder, and a relying party, according to an embodiment of the system described herein.

19 is a flow diagram for providing information to RTCA/SERTCA/OCSP responders for batch OCSP processing, according to an embodiment of the system described herein.

20 is a flow diagram for providing information to RTC responders for batch OCSP processing, according to an embodiment of the system described herein.

Detailed ways

The system described herein uses Real Time Credentials (RTC), also known as Distributed OCSP (DOCSP), and uses an entity known as the RTC Authority (RTCA). The RTCA may or may not coincide with a given enterprise's CA. In some embodiments, each CA presents its own RTCA with a special certificate, the RTCA certificate. The CA can digitally sign the RTCA certificate to show that the CA trusts and authorizes the RTCA to provide information about the validity of the certificate issued by the CA. The RTCA certificate can pass the RTCA status to a given entity (such as an entity determined by a given identifier, OID number, etc.) and can assign a specific verification key PK (a specific entity has a corresponding secret signed key) to a specific entity .

In cases where the CA and RTCA agree, it is advantageous for the RTCA to have a different signing key than the CA. Thus, if the CA and RTCA are the same entity, the CA part of the entity actually only issues certificates and the RTCA part of the entity manages certificates only by certifying whether a particular certificate is valid or revoked. Therefore, even if CA and RTCA overlap, RTCA certificates can still be used.

In some embodiments, each CA is associated with only one RTCA. In other embodiments, it is also possible that each CA is associated with more than one RTCA, where each RTCA has a different signing key, or that some or all RTCAs share a signing key. Associating multiple RTCAs with a CA is beneficial for redundancy purposes. In other embodiments, it is also possible to associate one or more RTCAs with multiple CAs.

Just as a CA protects its signing key, an RTCA protects its signing key, for example by means of a vault, secure facility, or secure hardware. In some embodiments, RTCA can be placed in a protected facility that includes more than one server with a secret signing key. The facility securely keeps a copy of the secret signing key. An RTCA may include more than one server, each with a secret signing key properly certified by the CA.

The CA may maintain a state that the RTCA is aware of the validity of the CA's certificate, for example by using a CRL or using any other mechanism. The CA may (1) notify the RTCA online of any change in certificate validity whenever a change occurs; and/or (2) send the CRL to the RTCA at regular intervals and/or when the CA generates a new CRL. A CA may provide individual certificate status information using any one or more of a number of techniques (alone or in combination). See, for example, the content provided in US Patent Nos. 5,420,927, 5,604,804, 5,610,982, 6,097,811, 6,301,659, 5,793,868, 5,717,758, 5,717,757, 6,487,658, and 5,717,759, all of which are incorporated herein by reference. The systems described herein may use the techniques disclosed in one or more of these patents, or may be combined with one or more other suitable techniques. Techniques that can be used alone or in combination include full CRLs, split CRLs, CRL increments, OCSP responses (individually or in groups), mini-CRLs (bitwise compressed CRLs), VTokens (one-way hash chains), and various Plant a Merkle tree or other tree shapes.

At any date Di in the sequence of dates D1, D2, ..., the RTCA, based on knowledge of its current validity state (eg, based on the latest CRL of the CA) and independently of any relying party requests, may process each outstanding certificates and digitally sign a statement describing the status of each certificate. For example, the status of each certificate may be considered valid, revoked, or suspended (and possibly "unknown"). A signed statement may specify a time interval T. In some embodiments, each signed statement specifies the same time interval T at each update, while in some embodiments the overall time interval is consecutive. For example, at each update date Di, the time interval may be T=D _i+1 -D _i , where it is possible that only one of Di and Di+1 is part of T, while the other dates are part of adjacent time intervals. In some embodiments, if the RTCA's current knowledge of certificate status is based on CRLs, each Di may coincide with the date of one CRL, and Di+1 with the date of the next CRL, and so on. It should be appreciated that such strict time dependence is not required. For example, the date on which the RTCA processes or begins processing its statement may be D1, D2, etc., while the time intervals specified within the statement may be D1', D2', etc., where Di and Di' may be different and/or independent of each other. For example, Di may be earlier than Di', in which case the RTCA may start processing the claim before the declared time interval begins - for example, because the RTCA expects to complete its processing before the interval T begins.

In some embodiments, the claim time and CRL time may also be different if the CRL is used for RTCA updates from the CA. A possible lack of synchronization between processing time, CRL time, and declaration time is not critical to the same as described here. In practice, "real time" is an abstraction, since some extra time is required to notify and react appropriately to events. First, it should be noted that while advancing the RTCA process, the CRL may not be generated in real time. Also, the process of revoking certificates may not be real-time. For example, a user may realize that their secret key has been compromised -- and thus request that their own certificate be revoked -- only within a day of the compromise actually occurring. Therefore, there is a 1-day delay in the revocation of user certificates, and the deviation from real time due to RTCA calculations is negligible in comparison.

RTCA precomputes digital signatures that indicate the status of each certificate during a certain time interval T. Such precomputation may be performed independently of any party's request for certificate validity. In some embodiments, the RTCA pre-computes the signed statement of the state of certificate C in a particular time interval before any state queries about C are made, possibly even before the time interval begins.

In some embodiments, the RTCA-signed certificate status statement may be in standard OCSP format. This is useful where OCSP software is already in place, so that the RTC system can be easily utilized without modifying any existing relying party OCSP software. In some embodiments, OCSP conformance may be achieved by particular selection of relevant quantities, digital signature algorithms, OIDs, and the like.

In many cases, an RTCA needs to generate a response for every certificate issued, not just for revoked certificates. To determine the existence of a serial number for each certificate issued, the RTCA may be given a copy of each certificate by the CA or another entity for internal tracking, or the RTCA may be given a serial number issued by another mechanism that does not involve the transmission of individual certificates . In some embodiments, in the special case where certificate serial numbers are issued in sequential order, the issued certificate information may not be explicitly provided to the RTCA. When using consecutive serial numbers, the RTCA may choose to use only the current CRL to infer the existence of each certificate serial number. This can be done by determining the lowest and highest sequence numbers in the CRL. Any intermediate numbers in the range between the high and low sequence numbers are issued by the CA. If a number in the range appears in the CRL, its status is known to be obsolete. If the intermediate number in the range does not appear, it can be determined that the corresponding certificate has not been revoked, which is defined as "valid" in the OCSP standard.

The techniques described above can handle the majority of issued certificates, although there are still a small number of issued certificates with sequence numbers at or below the lowest CRL entry or above the highest CRL entry. RTCA can include these additional sequence numbers via a configurable parameter that assumes a fixed number of valid sequence numbers before the first entry and after the last entry in the CRL. For example, an RTCA may specify that 100 sequence numbers before the lowest CRL entry and 500 sequence numbers after the highest CRL entry represent valid certificates. This optimization allows RTCA to retrieve one data element (CRL) rather than a large number of data elements (individual certificates). Where certificates are issued in sequential order from low to high, the higher numbers used at the high end can be used to accommodate newly issued certificates. In other embodiments, the lowest and highest serial numbers of issued certificates may be explicitly provided to the RTCA, and in some embodiments, this information may be digitally signed.

It should be noted that precomputed syntactically correct OCSP responses may not technically be considered OCSP responses, since these responses were not computed in response to any original/initial request. In effect, RTCA precomputes OCSP-compliant responses to OCSP requests that have not yet been generated and may never be generated. Therefore, RTCA responses can be viewed as artificially precomputed responses. It is also possible to use the term artificially precomputed response to refer to any digitally signed RTCA statement, even in cases where OCSP is not compliant.

After generating the manually pre-computed responses, the RTCA can give responses that can be used by other parties. Specifically, the RTCA may return a response to the relying party in response to a validity status query. However, in other embodiments, the RTCA may give artificially pre-computed responses that may be used by RTC responders. RTC responders do not have to be secured, since in practice RTCA-signed messages (artificially pre-computed responses) cannot be fraudulently modified or tampered with in an undetectable manner. Thus, RTCA can send artificially pre-computed responses to foreign transponders (responders belonging to other agencies) without compromising security.

In some embodiments, RTCA may facilitate processing by RTC responders by presenting artificially pre-computed responses to RTC responders in an appropriately organized manner. For example, RTCA may present manually precomputed responses sorted by certificate serial number or by length, etc. To ensure that all relevant precomputed responses have been received, the RTCA may provide an additional signature to the RTC responder at each update by signing and dating all precomputed responses. In some embodiments, a manually precomputed count of the number of responses or similar mechanism may be used, with or without digital signatures.

In addition, the RTCA may send the CA-generated RTCA certificate to the RTC responder to prove that the CA trusts and authorizes the RTCA to provide information about the validity of the CA-issued certificate. In some embodiments, this sending does not have to be done every update. In some cases, RTCA sends RTCA certificates to RTC responders only at the beginning or at some fixed period or based on request.

The RTC responder may store the received RTCA's artificially pre-calculated responses for a sufficiently long time. In some embodiments, if the RTCA's signature relates to a certain time interval T, the RTC responder may save the artificially precomputed response at least until the end of T. In some embodiments, at least some RTC responders, such as those belonging to the same agency as the RTCA, may periodically take steps to ensure that the information is correct and up to date. For example, an RTC responder may verify that a manually precomputed response for a time interval T was received before the start of T or other appropriate time relative to T, verify all received RTCA signatures (and possibly verify the appropriate RTCA certificate), verify that the RTC Whether the responder has received all signatures (e.g. not less than the expected number of signatures, not less than the signature of the last transmission of the issued certificate), verify that the RTC responder has received a message indicating the validity of a certificate that has previously been declared invalid Information, verify whether the RTCA certificate itself has been revoked (for example, due to security leaks), etc. If any problems are detected, the RTC responder may notify the RTCA or other appropriate entity.

The relying party may query the RTC responder for the validity status of the certificate. In some embodiments, the request is in OCSP format. When queried for the validity of a particular certificate, the RTC responder may retrieve from memory the RTCA-generated artificially pre-computed response for the particular certificate and return it to the relying party. In some embodiments, the RTC responder may also forward the RTCA certificate that signed the manually pre-computed response. In some embodiments, the relying party may signal that it is not interested in receiving the RTCA certificate (eg, because the relying party already has a copy), or the RTC responder may know or assume that the relying party already has a copy of the certificate. The relying party may process the received response to determine the validity status of the certificate of interest. In some embodiments, if the manually precomputed response is in OCSP format, the Relying Party may use OCSP software for such processing. In some embodiments, the relying party may verify the appropriate RTCA certificate. In the case of OCSP compliance, the relying party may verify the RTCA certificate as the OCSP responder certificate. In some embodiments, RTCA certificates may be syntactically structured as OCSP responder certificates.

There are various optimizations that can be performed. For example, assume U is the party with certificate Cu. As part of a transaction with party V, U may send Cu to V (unless V already has Cu), and may perform additional tasks (such as displaying a digital signature associated with a public verification key attested to belong to U in Cu, or by The decryption is identified by V using a random puzzle encrypted in Cu with the public encryption key attested to belong to U). To secure the transaction, V can determine the current validity of Cu and make a validity query to the RTC responder. The responder can answer the query by retrieving and returning the latest RTCA-signed statement on Cu (a human precomputed response). However, querying the RTC transponder adds a third party to what would otherwise be a two-party transaction, adding time and complexity to the transaction.

One solution is to have the U party receive at the beginning of each time interval T, or at least during each time interval T, an RTCA-signed statement Du (an artificially precomputed response) indicating that Cu is valid throughout T . U may receive Du in response to a request to the RTC responder (eg, by making a general relying party request). Alternatively, Du may be pushed to U and possibly other parties, eg by RTC responder or RTCA at each update and/or on an automatic basis. In any case, when transacting with V during the interval T, U may forward Du to V, in addition to all other steps or tasks necessary for the transaction. Thus, transactions between U-V can be greatly sped up, since V does not need to visit any third party (such as an RTC transponder) to determine the current validity of U's certificate.

It should be noted that even if the overall time including U's acquisition of Du is not speeded up, the transactions between U-V are speeded up. However, it should also be noted that it is still useful and efficient to merely speed up transactions between U-Vs without saving overall time. For example, if it is assumed that the RTCA statement (manually precomputed response) is calculated at midnight and specifies a full day as the time interval, then U can obtain Du early in the morning (when transactions are relatively few) and then execute the time-sensitive U-V transaction During the period, Du is forwarded to V, and there are quite a lot of transactions at this time, so saving time is useful. It should also be noted that after Du has been obtained and cached, additional efficiencies can also be gained by having U forward Du while transacting with other parties throughout the day. Thus, for example, a single relying party query (U's own query, possibly made at a relatively less busy time) can successfully replace a large number of relying party requests (possibly at a busier time).

The above optimization can also be done by the V party. After obtaining Du returned from the RTC responder for a validity query on U-party's certificate Cu, V-party can give Du to U, or make Du available to other parties.

It should be noted that the optimizations discussed herein apply to OCSP-compliant embodiments of the systems described herein. It should be noted that it is also possible to apply similar optimizations to traditional OCSP implementations. For such an implementation, the user requests and obtains an OCSP response for its own certificate, and then forwards the OCSP response as part of its transaction to the other parties to the transaction at appropriate intervals. Alternatively, when the relying party first queries the validity of U's certificate Cu, the OCSP responder can compute a response Ru, return Ru to the relying party that issued the query, and also forward Ru to U so that U can cache Ru , cached at least temporarily (until the next update), and can forward Ru as part of a Cu-based transaction.

In some embodiments, the system described herein may be implemented using the data found in each certificate, saving additional certificate and/or response length. As noted above, CAs may issue RTCA certificates that authorize a particular RTCA to provide authoritative answers about the validity of CA-issued certificates. Such an RTCA certificate may specify a public key used to verify RTCA-signed responses (manually pre-computed responses). However, in some embodiments, the CA may embed the RTCA public key within the certificate issued by the CA or this information may be embedded within the CA certificate itself. That is, the CA (with the appropriate format, OID, etc.) can include the public key PK in the certificate Cu, which can be used to verify the digitally signed response regarding the validity of Cu. For these embodiments, the relying party does not have to receive a separate RTCA certificate. When an RTC responder is queried for an up-to-date proof of the validity of Cu, the relying party can only obtain (as it queried) an RTCA-signed response (manually pre-computed response). In effect, Cu may specify a public verification key that relying parties may use to verify Cu's proof of validity. In other embodiments, the entire RTCA certificate (or a pointer to it) may be embedded in the user certificate and/or the CA certificate. These embodiments can result in considerable transmission savings (since the RTC responder does not have to send a separate RTCA certificate, which can be much longer than the RTCA response) and memory savings (since the relying party does not have to store the RTCA certificate with the RTCA response).

Similarly, a certificate Cu may specify a time interval. For these embodiments, the RTCA response does not necessarily specify the start and end of the time interval T. In some embodiments, the start of T alone (or other simpler convention) may specify T appropriately. For example, if Cu specifies a daily update, any time within a particular day is sufficient to specify the full day to which the response refers. Alternatively, if it is known (eg from the general policy of the CA) that the certificate has a validity interval consisting of full days, it is not necessary to indicate such information within the certificate, thus saving RTCA responses.

It should be noted that while the RTCA certification of the validity or suspend decision of a particular certificate C may specify the time intervals to which the certification relates, the revocation certification need not specify any time interval. Rather, for such proofs, specifying a single point in time (such as the time of annulment) is usually sufficient because, unlike validity and stay decisions, annulment is usually an irrevocable process. Therefore, the revocation time rt alone is sufficient to prove that the certificate is revoked. It should be noted that rt does not have to be the start of any time interval T, but may refer to any time. Therefore, in the case of certificate C being permanently invalidated, RTCA does not have to send certificates of C's revocation on all renewal dates (such as D1, D2, etc.). Instead, the revocation proof may be sent only once (or several times for redundancy) and cached by the RTC responder to be returned to the relying party when it makes a query about C.

It should also be noted that RTCA can be immediately notified that Certificate C has been revoked. For example, a message that C has been revoked may be forwarded in the middle of time interval T, when the RTCA has generated and forwarded proof of C's validity to the RTC responder. In this case, no proof of validity will be computed for C until the next update. However, at that point (ie until T ends), the incorrect, but apparently valid, proof of validity of C is held by the RTC responder. Possible countermeasures include prioritizing proofs of revocation over proofs of validity. In this case, an honest relying party that sees both C's validity proof for some time interval T and C's revocation proof (at any time t) should treat C as revoked (after time t).

In some cases, some relying parties will never see the revocation certificate, so even though C has been revoked, C can be considered by these relying parties to still be valid until the end of T. This problem can be mitigated by having the RTCA calculate and send a proof of C's revocation to all RTC responders (independent of the scheduled date D1, D2, etc. or D1', D2', etc.). Thereafter, all properly functioning RTC responders may delete any validity certificates for C from memory and replace them with newly received revocation certificates. In this case, the RTC responder is more likely to provide the relying party with accurate proof of the validity of C.

Referring to FIG. 3 , a schematic diagram 80 shows an architecture implementing the system described herein. CA82 connects to RTCA84 and provides confirmation information (such as CRL) to it. The RTCA 84 is connected to a plurality of RTC responders 86-88 which receive manually precomputed responses from the RTCA. Each of CA82 and RTCA84 uses a privately signed key, as described elsewhere in this specification. In some embodiments, CA 82 and RTCA 84 may be the same entity, as indicated at block 85 .

RTCA 84 provides artificially precomputed responses to RTC responders 86-88. As noted elsewhere in this specification, RTC responders do not need their own privately signed keys and need not be secured because any information provided to a relying party by one of the RTC responders 86-88 is digitally signed by RTCA 84 and is public information.

In other embodiments, more than one RTCA may be used, as shown by RTCA92 and RTCA94, which represent multiple additional RTCAs. Each additional RTCA 92, 94 may be connected to a transponder 86-88 serviced by the RTCA 84. Alternatively, one or more of the additional RTCAs 92, 94 may be connected to additional, different plurality of transponders 96-98.

Referring to FIG. 4, a flowchart 100 shows the steps performed by a CA when RTCA is initialized. The steps of flowchart 100 may be performed when a new RTCA is added to the system or when a previous RTCA is issued a new certificate, either because the old RTCA certificate has expired or because the RTCA's key has been compromised.

Processing starts in a first step 102 where the CA verifies the RTCA. Verifying the RTCA at step 102 depends on the topology and security requirements of the system, and may require an administrator to physically inspect the RTCA and verify that the RTCA is in place and secure. Of course, other appropriate processing may also be performed in step 102 to verify that the RTCA is safe. After step 102 is step 104, the CA generates a key for RTCA. In step 104, the CA generates both a secret key and a public key for the RTCA.

Following step 104 is step 106 where the CA generates a certificate for the RTCA based on the key generated at step 104 . The certificate generated at step 106 is an RTCA certificate. Following step 106 is step 108 where the secret key is provided to the RTCA. In some embodiments, it is useful for security purposes to have the secret key provided to the RTCA in an off-line fashion (eg, the user writes the secret key on a piece of paper and then enters the secret key at the RTCA).

Following step 108 is step 112, the certificate generated at step 106 is provided to the RTCA. In step 112, it is possible to provide the certificate to the RTCA in an online (even insecure) manner, since the RTCA certificate will be public, and in fact, there is no knowledge, which cannot be altered. Following step 112 is step 114, initial certificate data regarding certificates managed by the CA is provided from the CA to the RTCA. The initial data provided at step 114 may include an initial CRL. Additionally, as described elsewhere in this specification, the initial data provided at step 114 may also include information about valid, non-expired certificates so that the RTCA may provide an appropriate response for valid, non-expired certificates. After step 114, the process ends.

In some embodiments, step 104 is performed by the RTCA such that the RTCA is the only entity with knowledge of the secret key. In this case, the RTCA presents the corresponding public key to the CA (either online or offline), so that the CA can generate a certificate at step 106 . Of course, in such a case, it is not necessary to perform step 108 as described above. This is illustrated by another flow 116 from step 106 to step 112 shown in flowchart 100 .

It should be noted that the steps of flowchart 100 can be performed even in the case where the CA and RTCA are the same entity. Of course, in such a case, verifying the RTCA at step 102 is of no value. Also, for embodiments where the RTCA/CA will use the same public and secret key pair for both the CA run and the RTCA run, steps 104, 106, 108 and 112 need not be performed because the RTCA certificate will simply be the CA's certificate . However, in cases where it is useful to have the RTCA certificate format different from the CA certificate format (such as the OCSP responder certificate format), step 106 may be performed when generating a certificate in a different format for the RTCA certificate.

Referring to FIG. 5, a flowchart 120 shows the steps performed in periodically transmitting certificate validity data from the CA to the RTCA. The steps of flowchart 120 may be performed on a regular basis, or may be performed based on a dedicated request of the RTCA. Processing begins with a first test step 122, where it is determined whether any certificates have been revoked recently (ie since the last iteration). If so, control passes from test step 122 to step 124, where a revocation message is sent to the responder. As described elsewhere in this specification, in some embodiments, revocation information is sent immediately (as close as possible) from the CA to the RTCA. In some embodiments, the revocation information sent from the CA to the RTCA at step 124 is digitally signed or authenticated.

Following step 124 or after test step 122 (if no certificate has been recently revoked) is a test step 126 of determining whether the current time corresponds to a new time interval for updating certificate information. As described elsewhere in this specification, in some embodiments the CA pushes new acknowledgments to the RTCA at periodic intervals. Thus, if at test step 126 it is determined that the current time does not correspond to the new interval, then control passes from test step 126 back to step 122 previously described. Otherwise, if the current time corresponds to a new interval, control passes from test step 126 to step 128 where new confirmation information is generated by the CA, which in some embodiments includes digitally signing or authenticating the information. As described elsewhere in this specification, the new confirmation information can be in any of a variety of forms, including CRLs.

Step 128 is followed by step 132 where the new confirmation information generated in step 128 is provided to the RTCA. Following step 132 is a test step 134 which determines whether the RTCA has acknowledged receipt of the information sent at step 132 . If not, control transfers from step 134 to step 136 where error handling is performed. The error handling performed at step 136 may include notifying a system administrator. It should be noted that determining whether the RTCA has received new information at step 134 is useful because a malicious attacker may deactivate the RTCA as a means of preventing information about recently revoked certificates from being disseminated. After step 136, processing ends.

If at test step 134 it is determined that the RTCA has acknowledged receipt of the information sent at step 132, then control passes from step 134 back to step 122 to process the next iteration. In some embodiments, data is periodically provided from the CA to the RTCA, whether or not the RTCA acknowledges receipt of the data. This is illustrated by another path 137 .

In some embodiments, the steps of flowchart 120 are not performed periodically, but are only performed in response to specific requests for RTCA request data. This is illustrated by an additional path 138 which passes control from step 122 or step 124 directly to step 128 . It should also be noted that an additional path 142 corresponds to the receipt of an acknowledgment at step 134 . Thus, in embodiments where the steps of flowchart 120 are performed sporadically, when it is determined at test step 134 that the RTCA has acknowledged receipt of the message sent at step 132, then path 142 indicates the end of processing. Of course, there are also possible embodiments where the RTCA does not acknowledge receipt of the information from the CA. This is illustrated by another path 144 .

Referring to FIG. 6, a flowchart 150 shows the processing performed by the RTCA in an embodiment where data is periodically pushed from the RTCA to the RTC transponder. Processing begins in a first step 152 where the RTCA determines whether new data has been received since the previous push. If not, control passes back to step 152 to continue looping and polling until new data is received. Once it is determined at test step 152 that new data has been received, control passes from step 152 to step 154 where data is passed from the RTCA to the RTC responder. After step 154, control passes back to step 152 to continue polling for new data.

Referring to FIG. 7, a flowchart 160 shows steps performed by the RTCA in an embodiment in which data is provided from the RTCA to the RTC responder in response to a request by the RTC responder. As described elsewhere in this specification, the RTC responder may itself periodically request data from the RTCA, rather than relying on having data automatically pushed periodically from the RTCA to the RTC responder.

Processing begins in a first step 162 where the RTCA receives a query (request data) from an RTC responder. Following step 162 is a test step 164 which determines whether the RTC responder requests an RTCA certificate. As described elsewhere in this specification, RTCA certificates are used to state that the CA trusts and authorizes the RTCA to provide confirmation information. In some embodiments, each RTC responder may cache the RTCA certificate (to be provided if required by the requesting and/or relying party), in which case the RTCA certificate need only be requested once. In other embodiments, the RTC responder may periodically request RTCA certificates, or in some cases, request RTCA certificates all the time.

If at test step 164 it is determined that the RTC responder has requested an RTCA certificate, then control passes from test step 164 to step 166 where the RTCA provides the RTCA certificate to the RTC responder. After step 166 or after test step 164 (if the RTC responder has not requested an RTCA certificate) is a test step 168 which determines whether other information (ie, a manually precomputed response) has been requested. If not, processing ends. Otherwise, control passes from test step 168 to test step 172, which determines whether another information is available at the RTCA. In some cases, another information requested by the RTC responder is not available at the RTCA. For example, if an RTC responder requests information about a foreign certificate, a manually precomputed response is not available at the RTCA.

If at test step 172 it is determined that the requested information is not available, then control passes from test step 172 to step 174 where the RTCA provides data to the RTC responder indicating that the requested information is not available. After step 174, processing ends. If at test step 172 it is determined that the requested additional information is available, then control passes from test step 172 to step 176 where the requested information is provided by the RTCA to the RTC responder. After step 176, processing ends.

Referring to FIG. 8, a flowchart 190 shows the steps performed by an RTC responder when receiving a request from a relying party requesting an artificially precomputed response (OCSP response). Processing starts in a first step 192, a request is received. Following step 192 is step 194 where the RTC responder obtains RTCA data appropriate for the request. Obtaining RTCA data at step 194 is described in detail elsewhere in this specification. Following step 194 is a test step 196 in which it is determined whether the requested data is available. If not, control passes from test step 196 to step 198 where the RTC responder provides a response to the relying party indicating that the status of the particular certificate is not known. After step 198, processing ends.

If at test step 196 it is determined that the latest validity data is available for the certificate of interest, then control passes from test step 196 to step 202 where a check is performed on the data. As described elsewhere in this specification, the checks performed at step 202 may include any or more of the following: determining the currentness of the data, determining that the RTCA certificate has not been tampered with and is still valid, and any one or more of which may be used in step 194. Additional checks performed on the acquired data.

Following step 202 is a test step 204 which determines whether the results of the check performed at step 202 indicate that everything is OK. If not, control passes from step 204 to step 206, where an indication is provided to the relying party that the validity data cannot be accepted. Other appropriate processing may be performed at step 206, including, for example, notifying a system administrator of the error. After step 206, the process ends.

If at test step 204 it is determined that the validity data is acceptable, then control passes from test step 204 to test step 208 where it is determined whether the relying party requests an RTCA certificate. If not, control passes from test step 208 to step 212, where the validity data (manually precomputed response) is provided to the relying party. After step 212, the process ends. Otherwise, if at test step 208 it is determined that an RTCA certificate is requested along with validity data, then control passes from test step 208 to step 214 where the validity data (manually precomputed response) and the RTCA certificate are provided to the relying party. After step 214, the process ends.

For some embodiments, the relying party may perform its own validity data check, in which case the check of step 202 or the corresponding test of step 204 need not be performed. This is illustrated by another flow path 216 from step 196 to step 208 .

Referring to FIG. 9 , a flowchart 230 shows in more detail the steps performed by the RTC transponder in acquiring RTCA data at step 194 of flowchart 190 of FIG. 8 . Flowchart 230 corresponds to an embodiment in which RTCA data is automatically pushed from the RTCA to the RTC responder, and the RTC responder does not have to explicitly request the data. For these embodiments, the transponder always automatically has the latest (or close to the latest) RTCA data.

Processing begins with a first test step 232 where the RTC responder determines whether the requested data is available at the RTC responder. If so, control transfers from test step 232 to test step 234, which determines whether the requested data at the RTC responder is the latest data. As described elsewhere in this specification, artificially precomputed responses may include a time interval during which artificially precomputed responses are valid, after which a new artificially precomputed response needs to be retrieved. Regardless of the particular mechanism used to determine the time interval for artificially precomputed responses, it is determined at test step 234 whether the particular artificially precomputed response requested by the relying party is up to date by comparing the current time with the time interval associated with the artificially precomputed response. determined by the time interval.

If the data is the latest, then control passes from test step 234 to step 236, which determines whether the RTCA certificate is valid. It is also possible that the RTCA certificate will be revoked (or will expire) in some cases and thus the data provided by the RTCA may not be reliable. For example, if the RTCA's secret key is compromised, the RTCA certificate may become invalid. Determining the validity of the RTCA certificate at step 236 may be performed using any of a variety of known techniques, including those described herein. If at test step 236 it is determined that the RTCA certificate is valid, control passes from the test step to step 238 where the requested artificially precomputed response is provided for further processing, as described in connection with flowchart 190 of FIG. 8 . After step 238, processing ends.

If it is determined at test step 232 that the data cannot be obtained, or if at test step 234 it is determined that the requested data is not up-to-date, or if at test step 236 it is determined that the RTCA certificate is not valid, then control goes to step 242, which is shown in FIG. Data cannot be obtained after processing the steps of flowchart 190. In some embodiments, the information provided at step 242 may include a reason why the requested information is not available. After step 242, the process ends.

In some embodiments, it may not be desirable to check the validity of the RTCA certificate at every iteration. For these embodiments, step 236 may be omitted, which is illustrated by another path 244 .

It should also be noted that it is also possible to use the process shown in flowchart 230 for embodiments where the RTC responder periodically requests new data from the RTCA. In such a case, the data may not be available or up to date because it has not been requested from the RTCA by the RTC responder.

Referring to FIG. 10 , flowchart 260 shows in more detail the steps performed in obtaining RTCA data at step 194 of flowchart 190 of FIG. 8 , which is used in an embodiment where the RTC responder requests data from the RTCA. Processing begins at a first step 262, where it is determined whether the relying party has requested an RTCA certificate. If so, control passes from step 262 to step 264, where it is determined whether the RTCA certificate is cached by the RTC responder. If not, control passes from test step 264 to step 266 where the RTC responder requests the RTCA certificate from the RTCA.

After step 266, or after step 262 (if the RTCA certificate is not requested), or after step 264 (if the requested certificate is not available) is a test step 268, determining whether a manual pre-computed response has been requested. If so, control passes from test step 268 to test step 272, which determines whether the requested artificially precomputed response is cached (up to date, of course) at the RTC responder. If not, control passes from test step 272 to test step 274 where the RTC responder requests a manually precomputed response from the RTCA. After step 274, or after step 268 (if no artificially precomputed response was requested), or after step 272 (if the requested artificially precomputed response was cached) is step 276, the result of fetching the requested information is provided To continue the processing of the steps of the flowchart 190 of FIG. 8 . After step 276, processing ends.

Referring to FIG. 11 , a flowchart 300 illustrates steps performed by a user or a relying party with whom a user transacts, in an embodiment of establishing a two-party transaction to avoid the additional steps and processing of a third-party transaction. Processing begins with a first test step 302, where it is determined whether the user and/or relying party has cached information (artificially precomputed responses) that is up to date (or exists locally at all). If so, control passes back to test step 302 to continue polling until the information is not up to date. Once it is determined at test step 302 that the cached information is not up to date, control passes from test step 302 to step 304 where the entity (user and/or relying party) obtains the latest information as described elsewhere in this specification. Step 304 is followed by step 306, the information obtained in step 304 is saved (cached) locally. After step 306, control passes back to step 302 to continue polling until the time when the cached information is no longer current.

Referring to FIG. 12 , certificate 320 is shown including conventional certificate information 322 and RTCA certificate information 324 . Certificate 320 may be a user certificate or a CA certificate. As noted above, in some embodiments, the public key attested by the RTCA certificate 324 may be embedded in the certificate. When the relying party views the certificate 320 (or user certificate or CA certificate), it is not necessary to obtain the RTCA certificate separately. In other embodiments, RTCA certificate information 324 includes the entire RTCA certificate or a pointer to it.

Referring to FIG. 13 , a diagram 400 shows information flow between CA 402 , RTCA 404 , RTC responder 406 , and relying party 408 . CA 402 provides confirmation information (eg, CRL) 412 to RTCA 404 as described elsewhere in this specification. The RTCA 404 generates a number of artificially precomputed responses 416 , which are provided to the RTC responder 406 . In some cases, RTCA 404 may also provide RTCA certificate 414 to RTC responder 406 . However, as described elsewhere in this specification, the RTCA certificate 414 may be provided only once or periodically independently of the RTCA 404 which provides the artificially precomputed response 416 to the RTC responder 406 .

Relying party 408 generates an OCSP request 418 (or some other type of request requesting validity information) that relying party 408 provides to RTC responder 406 . The RTC responder 406 services the OCSP request 418 by providing an artificially precomputed OCSP response 422 , which is one of the artificially precomputed OCSP responses 422 previously provided to the RTC responder 406 from the RTCA 404 . The relying party can then use the manually precomputed response 422 to take appropriate further action based on the validity status of the certificate involved. As described elsewhere herein, in some cases, RTC responder 406 may provide RTCA certificate 414 to relying party 408 .

Referring to FIG. 14, a schematic diagram 430 illustrates the transfer of confirmation information between two otherwise independent digital certificate systems. Diagram 430 shows CA 402 , RTCA 404 , RTC responder 406 , and relying party 408 of diagram 400 of FIG. 13 . Diagram 430 also shows confirmation information 412 provided by CA 402 to RTCA 404 and shows RTCA certificate 414 and artificially pre-computed response 416 passed from RTCA 404 to RTC responder 406 .

The diagram 430 also shows a second CA 432 , a second RTCA 434 , a second RTC responder 436 , and a second relying party 438 . The second CA 432 provides confirmation information 442 to the second RTCA 434 . The second RTCA 434 provides an artificially precomputed response 446 to the second RTC responder 436 . However, assuming CA 402 and second CA 432 manage separate sets of digital certificates, CRL 412 contains information about certificates other than CRL 442 , and artificially precomputed response 416 contains information about certificates other than artificially precomputed response 446 . Thus, when the second relying party 438 provides the OCSP request 448 to the second responder 436 regarding the certificate managed by the CA 402 , none of the artificially precomputed responses 446 provided by the second RTCA 434 may be suitable to satisfy the OCSP request 448 .

If the RTCA 404 has provided a manually precomputed response 416 to the second RTC responder 436 and if the RTCA 404 has previously provided the RTCA certificate 414 to the second RTC responder 436, then the above difficulty can be resolved, and the second RTC responder 436 can pass the RTCA The certificate 414 and the manually precomputed response 422 generated by the RTCA 404 are provided to the second relying party 438 to satisfy the OCSP request. It should be noted that the transmission from the RTCA 404 to the second RTC responder 436 is not necessarily secure, as the RTCA certificate 414 and the artificially pre-computed response 436 have been digitally sign.

Referring to FIG. 15 , schematic diagram 460 shows the system for generating the system shown in schematic diagram 430 of FIG. 14 . In diagram 460 , RTCA 404 provides artificially precomputed responses 416 to heterogeneous cloud 462 of RTC responders. Similarly, a second RTCA 434 provides an artificially precomputed response 446 to a heterogeneous cloud 462 of RTC responders. The RTCAs 404, 434 may also provide their respective RTCA certificates (not shown) to the heterogeneous cloud 462 of RTC responders. It should be noted that any number of RTCAs may provide artificially precomputed responses and/or RTCA certificates to the heterogeneous cloud 462 of RTC responders. Accordingly, Relying Party 408, Second Relying Party 438, or some other Relying Party may receive an appropriate one of the manually precomputed responses, and optionally, an RTCA request in response to an OCSP request (or some other type of request). Credentials, the request is for any credentials whose human precomputed responses are provided to the heterogeneous cloud 462 .

While the techniques described herein address many of the drawbacks of traditional OCSP, such as expensive computation, high communication volume, and costly secure server replication, additional optimizations can reduce even more computational and communication costs. In particular, the traffic between RTCA and RTC transponders can be reduced by appropriate compression, as described below. The savings resulting from the combination of techniques described below are significant, especially when standard OCSP syntax is used.

As mentioned above, RTCA sends artificially pre-calculated responses to each RTC responder. Each artificially pre-calculated response can consist of multiple data elements, such as response type, time to calculate the response, digital signature algorithm identifier, RTCA id, certificate number, whether the certificate is valid or invalid, and the digital signature itself. Many of these items are the same, or similar, across multiple responses. For example, the time to calculate the response and the id of the RTCA are the same for all responses. When all responses are sent collectively from the RTCA to the RTC responder, common data elements may only be transmitted once. When answering a relying party request, the RTC responder may also reconstruct an appropriate response. Furthermore, when data items are similar but not identical, appropriate compression algorithms can be used to exploit the similarities and transmit only the differences.

Furthermore, to further reduce the cost of computing responses and communicating them to responders, it may be advantageous to update responders based on the validity status of some rather than all certificates. For example, the validity status of all certificates may be updated hourly, while some high priority (such as high security) certificates may have their status updated every minute. Alternatively (or in addition), a newly revoked certificate may have its validity status updated immediately to the responder to reduce the risk of inappropriate use. Alternatively, the RTCA may provide the responder with every-minute updates of certificates whose status has changed, while also providing daily (or hourly) validity status information for all certificates signed.

Communication costs can be further reduced using standard common compression techniques such as Lempel-Ziv. Compression techniques may be applied after the above optimizations have reduced traffic.

The above optimizations reduce the computational load on the RTCA and the communication cost between the RTCA and the transponder, since, in many cases, a smaller number of signatures need to be computed. In fact, this approach increases security by reducing the latency caused by computation and communication: if the RTCA had to process and send the validity status of all digital certificates all the time, the responder has more current information than it should .

Referring to FIG. 16, a flowchart 470 shows the steps of compressing data communicated between the RTCA and the RTC transponder. Processing begins at a first step 472 where unscheduled items are removed without transmission. As mentioned above, one of the possible optimizations is to update information about certificates at different frequencies, the more important certificates being updated more frequently. Therefore, information about less important, unscheduled certificates is removed from the information to be sent from the RTCA to the RTC responder at each update cycle.

Following step 472 is step 474 in which redundant items are deleted from the remaining data. As mentioned above, redundant items include items that are identical to the information being transmitted. For example, the identity and update time of the RTCA are the same for all messages passed from the RTCA to the RTC responder. Following step 474 is step 476 where a compression algorithm is applied to the remaining information. Various possible compression algorithms are described above. After step 476, processing ends.

Attesting to the validity of a certificate is valuable in proving a claimed identity. In some cases, however, proving a claimed identity is often associated with privileged access to a specific physical location, logical entity, or service. The association of identities and privileges may be implicit and may not accommodate the need to control multiple independent privileges for the same user. A different approach would employ separate privilege states for each individual privilege. RTCA can be extended to provide privilege status for multiple privileges in addition to credential status.

Privileges can be granted by one or more authorities. This can be an implicit process where the authority and the CA are the same entity. In such a situation, a user proving their identity may establish user rights to access a particular location, logical entity, or service. However, a drawback of this approach is that the privilege status may be the same as the credential or identity validity status, thus resulting in a pure yes/no answer for all implied privileges. As described below, this can be addressed by extending RTCA to provide individual, independent privilege states for each user.

In the beginning, CA certifies RTCA as the privilege management authority. For example, this could be performed as part of the general CA attestation process described elsewhere in this specification. CAs may digitally sign certificates that indicate that the CA trusts and authorizes the RTCA to provide several independent privilege states in addition to the certificate validity state. Authorization can either be implied or explicitly stated in the RTCA certificate.

After certification, the authority can notify the RTCA of the current status of the respective privilege status. The authority may keep the RTCA informed of the validity status of the privileges granted to each user over which the authority has control. For example, the authority may (1) notify the RTCA online of any privilege status changes whenever a change occurs, or (2) send a digitally signed message to the RTCA indicating the change.

Determining an entity as an authorized authority can be done by using a digitally signed certificate issued by an appropriately trusted and authorized CA. The privileges controlled by each authority can be tied to the authority within the certificate itself (ie by the CA) or in a database located at the RTCA or by some other suitable means.

When an RTCA generates a separately signed certificate validity status message, the RTCA may include the status of each privilege associated with a particular certificate. As part of the process of providing the validity status of a credential, the RTCA may include an identifier and current status of each privilege associated with the credential in question. The time interval associated with the privileged state may be the same as that applied to the certificate validity state. In this regard, precomputing individual privilege states may occur concurrently with the same techniques described above for credential status validation. The privilege status can be included in the same digitally signed message as the certificate status confirmation.

RTCA can send precomputed privilege validity status to unprotected RTC responders. The process of distributing the various privilege states may be the same and concurrent with that used for credential status validation as described above. The responder may then save the RTCA pre-computed privileged state. When the privilege status confirmation information is included as part of the credential status confirmation information, the privilege status information may be stored as a single response by the responder as described above and/or may be stored with the credential confirmation information.

As described above, when a Reliance Responder is queried for credential validity status information, the RTC Responder may provide an RTCA precomputed response that includes the credential validity status and all associated privilege status. The relying party may then verify the precomputed response (and, if appropriate, the RTCA certificate). The relying party's processing of the received response is similar to that described above, except now any relevant privileged state is also available. The privilege status can be read and used to determine whether the requested access is authorized. An RTC system extended to provide multiple distinct privilege statuses may be similar to the system described elsewhere in this specification for providing credential status, except that precomputed OCSP responses may now be known to contain privilege validity status and credential validity status information outside.

Referring to FIG. 17, a diagram 480 shows an authority implementation. Schematic 480 shows CA482 connected to RTCA484. As described elsewhere in this specification, CA482 provides information to RTCA484. RTCA 484 is connected to a plurality of RTC transponders 486-488 to provide information thereto, as described elsewhere in this specification.

Diagram 480 also shows authority 492 providing authorization information to RTCA 484 . Alternatively, CA 482 may connect directly to authority 492 to provide initial authorization information, authority certificates, and any other appropriate information. As noted elsewhere in this specification, CA 482 and authority 492 may be the same entity, illustrated by box 496 surrounding CA 482 and authority 492 . Although not shown in schematic diagram 480, the system described here with authority 492 may include additional RTCAs, transponders, etc., as described elsewhere in this specification (see, eg, FIG. 3 and corresponding description).

It should be noted that instead of providing a certificate from CA 482 to authority 492 , CA 482 may provide authority certificates directly to RTCA 484 in some embodiments. It should also be noted that the authority certificate (or other evidence of authorization) may be provided in a certificate issued by CA 482 (similar to that shown in FIG. 12 above) or other information provided by CA 482 to RTCA 484.

While the RTC system addresses many of the OCSP deficiencies, further optimizations are possible. Specifically, the computational cost of RTCA can be reduced by processing multiple digital signatures at once. For the above system, RTCA signs the status of each digital certificate. Even if this is done ahead of time, possibly even before state queries are made, it may be desirable to reduce the computational cost of the process, especially since the generation of digital signatures is a computationally intensive operation.

As will be detailed below, an improvement is provided by making Signature Valid RTCA (SERTCA) combine the states of multiple certificates into a single statement and then sign and date that statement so that multiple certificates can be authenticated using a single signature state at a specific point in time. The number of certificates whose status is thus authenticated may be fixed (each statement always contains status information for the same number of certificates), or it may vary. Credentials identified in a single statement can also be identified in other statements. For example, one statement may represent the validity status of all certificates belonging to a particular individual, and another statement may represent the validity of all certificates with serial numbers within some integer interval. It is possible for the same certificate to belong to two collections and thus to two separate authentication statements.

After authenticating all claims for a particular time interval, SERTCA may send the claims to one or more RTC responders, which store the claims to serve relying party queries. Upon receiving a query for certificate X, the RTC responder may retrieve a SERTCA-signed statement containing X's validity status and return the statement to the relying party. A relying party can verify the SERTCA signature and search for information about X in the statement, thus knowing the state of X in an authenticated manner.

Of course, a SERTCA can also issue statements about the status of a single certificate, so if a SERTCA issues a statement about only a single certificate, the SERTCA can provide the same information as an RTCA. A particular SERTCA may be available as an RTCA at some times and not at other times (eg, according to computing constraints and needs at a particular time). The system can combine RTCA and SERTCA.

In the beginning, the CA proves SERTCA in a manner similar to the way RTCA was proved above, as described above. Like RTCAs, SERTCAs are entities that may or may not correspond to a particular institution's CA. Each CA provides its own one or more SERTCAs, where each SERTCA has a special certificate, the SERTCA certificate. A CA may digitally sign a SERTCA certificate to indicate that the CA trusts and authorizes SERTCA to provide information about the validity of the CA's certificate. Such a certificate conveys the SERTCA state to a specific entity (such as an entity identified by a specific identifier, OID number, etc.), and can bind a specific verification key PK (a specific entity has its corresponding secret signing key) to a specific entity. Certainly.

Just like RTCA, even if the CA and SERTCA agree, it is advantageous for the CA and SERTCA to have different signing keys. Therefore, regardless of whether the CA and SERTCA represent the same entity, the CA issues certificates and SERTCA manages certificates (such as certifying that the certificate is valid/revoked/suspended). This way, even if the CA and SERTCA are identical, a separate SERTCA certificate may still be used. In some embodiments, there is only one SERTCA per CA, although for redundancy or other purposes it is advantageous to have more than one, whether or not the same signing key is used. If there are multiple SERTCAs, some of them can simply be used as RTCAs.

It should be noted that, just like RTCA, SERTCA protects its signing key. For example by means of a vault, secure facility, or secure hardware. The CA keeps informed of the validity status of its certificates to SERTCA. For example, the CA may (1) notify SERTCA online of any change in certificate validity whenever a change occurs, or (2) send its CRL to SERTCA when generated. On any date Di in the sequence of dates D1, D2, ..., SERTCA performs an update based on its current knowledge of validation status (eg, based on the latest CRL of the CA) and independently of any relying party requests, by processing each outstanding This is achieved by (preferably non-expired) certificates, combining information about the validity status of the certificates into sets, and digitally signing for each set a statement indicating the status of each certificate in the set (artificially precomputed responses). For example, such a status may be active, obsolete, or deferred decision (or possibly "don't know," or "not issued," or another status indication). A signed statement may specify a time interval T. In some embodiments, each signed statement may specify the same time interval T at each update, and the sum of these time intervals may cover the entire "timeline". For example, at each update date Di, time interval T=D _i+1 -D _i - where it is possible that only one of Di and Di+1 is part of T while the other date is part of the adjacent time interval.

As an example, a statement example may have the form SIG-SERTCA("X: Active; Y: Obsolete; Z: Suspended decision; Date: Di; Next date: Di+1"), where X, Y, and Z represent the determination of a specific The information of the certificate (such as serial number), and "valid", "invalid", and "revoked" are indicators of the status of the corresponding certificate. If SERTCA's current knowledge of certificate status is based on the CA's CRL, then each Di may coincide with the date of one CRL, Di+1 with the date of the next CRL. It will be appreciated that such strict time dependence is not required. For example, the date at which SERTCA processes or starts processing its claims can be D1, D2, etc., while the time intervals specified within the claims can be D1’, D2’, etc., where Di and Di’ can be different. For example, Di may be earlier than Di', in which case RTCA may start processing claims before the time interval in which they were started - e.g. because SERTCA wants to finish its processing before interval T starts. Similarly, the claim time and CRL time can also be different if the CRL is used at SERTCA update time.

So, in effect, SERTCA pre-computed digital signatures indicate the status of all certificates at a certain time interval T. Such precomputation can be performed independently of any relying party requests regarding certificate validity. SERTCA may precompute signed statements for a particular time interval before any state queries are made in the time interval, even before that time interval begins. The SERTCA-signed statement of certificate status (a human-precomputed response) can be in standard OCSP format or in a format compatible with existing relying party software. This is useful to minimize or eliminate modifications to existing relying party software when OCSP software is already in place. For example, to ensure compliance with all relevant quantities of OCSP, digital signature algorithms, OIDs, etc. may be chosen appropriately.

It should be noted, however, that a syntactically correct OCSP response to SERTCA does not have to be a traditional OCSP response, since SERTCA responses are not computed in response to any request. In effect, SERTCA precomputes OCSP-compliant responses to OCSP requests that have not yet been generated and may never be generated. SERTCA responses, whether in OCSP format or not, are manually precomputed responses.

After precomputing the response, SERTCA can make the response available to other parties. While the SERTCA may return a response to the relying party in response to a validity status query, in other embodiments, the SERTCA may provide a precomputed response to the RTC responder similar to the RTC responder used in connection with the RTCA described above.

SERTCA can help the RTC responder to process the signature by presenting the signature to the RTC responder in a properly organized manner. To ensure that all relevant precomputed responses have been received, at each update SERTCA may provide an additional signature to the RTC responder by signing and dating the population of artificially precomputed responses received by the RTC responder . Additionally, SERTCA may send SERTCA certificates to RTC responders. This transfer does not have to happen every update, it can only be performed at the beginning or periodically.

The RTC responder may store the received artificially pre-computed responses of SERTCA for a sufficiently long time. In some embodiments, if the signature relates to a certain time interval T, the RTC responder may save the artificially precomputed response at least until the end of T. In some embodiments, RTC responders (especially those belonging to the same organization as SERTCA) may check to have the correct information. For example, an RTC responder may verify artificially precomputed responses received for time interval T before the start of T (or other appropriate time relative to T), verify all received SERTCA signatures (possibly and appropriate SERTCA certificates), verify Whether the RTC responder has received information about all certificates (e.g. not less than the expected number of certificates, not less than the certificates issued by the previous transmission), verify whether the RTC responder has received the validity of the certificates that were previously declared invalid Statement signed by DERTCA, etc. If any problems are detected, the RTC responder notifies SERTCA or another appropriate entity.

The relying party may query the RTC responder for the validity status of the certificate. In some embodiments, the relying party uses the OCSP format for the request. If information on the same certificate status appears in more than one statement, the relying party may indicate to the RTC responder which statement is the relying party's preference. For example, if SERTCA provides a statement representing the validity status of all certificates belonging to a particular individual, and provides a statement representing the validity status of all certificates with serial numbers within a certain integer interval, and the relying party mainly has interested in the validity status of certificates with serial numbers X, the relying party may provide an indicator indicating preference to receive (a) a SERTCA-signed statement that includes information about certificates with serial numbers close to X, or (b) a SERTCA-signed A statement for X that includes information about I's other certificate, or (c) a very short SERTCA-signed statement, or (d) a SERTCA-signed statement that includes information about X's state (ie, no preference). There are advantages to choosing one of these depending on the situation.

When queried for the validity of a particular certificate, the RTC responder may retrieve a SERTCA artificially pre-computed response from memory that includes information for that certificate. RTC responders may return manually precomputed responses. The RTC responder can also forward the appropriate certificate for SERTCA that has signed the human precomputed response. It should be noted that the relying party may provide an indication to receive the SERTCA certificate, or the RTC responder may know or assume that the relying party already has a copy of the SERTCA certificate. If there are multiple pre-computed answers containing information about the same certificate, the RTC responder may choose which answer to return based on the relying party's preference or some specified algorithm or according to some other rule.

The relying party processes the received response to determine the validity of the certificate of interest. In some embodiments, if the response is in OCSP format, the RTC responder uses OCSP software for such processing. The RTC responder verifies the appropriate SERTCA certificate. In an OCSP compliant embodiment, the RTC responder may verify the SERTCA certificate as the OCSP responder certificate. In some embodiments, SERTCA certificates may be syntactically structured as OCSP responder certificates.

Referring to FIG. 18 , a diagram 500 shows data flow between CA 502 , SERT CA 504 , RTC responder 506 and relying party 508 . CA502 provides confirmation information (such as CRL) to SERTCA504. SERTCA 504 generates multiple multi-certificate artificially pre-computed responses 516 using the validation information. SERTCA 504 also has its own certificate 514, which may be provided to SERTCA 504 by CA 502.

The relying party 508 generates an OCSP request 518 that the relying party 508 provides to the RTC responder 506 . In response thereto, RTC responder 506 provides multi-certificate artificially pre-computed response 522 , which is one of multi-certificate artificially pre-computed responses 516 originally provided to responder 506 by SERTCA 504 . In addition, responder 506 provides SERTCA certificate 514 to relying party 508 in some cases, as described elsewhere herein.

It should be noted that the processing of the RTCA system described above may also be adapted for use with SERTCA systems and/or hybrid systems, including the use of authorities, as described above, and providing the compression optimization described above in connection with FIG. 16 . Similarly, the processing of the SERTCA system described above is equally suitable for use with RTCA systems and/or hybrid systems.

Another technique, batch OCSP, can be used to reduce RTCA or SERTCA computation costs. Batch OCSP can be used alone or in combination with one or more of the other mechanisms described herein.

Batch OCSP can be used when the special digital signature used in the response is an RSA digital signature. While SERTCA improves signature efficiency by identifying the status of multiple certificates in a single signature, batch OCSP can generate multiple single-certificate OCSP responses with a single calculation to improve efficiency, making the cost per response much lower than that of a single OCSP response . For example, if 10 single-certificate OCSP responses are generated individually, the cost is roughly the cost of 10 RSA signatures for RTCA (or traditional OCSP responders). As mentioned above, the SERTCA mechanism reduces the cost to that of one RSA signature by combining the information on 10 certificates in a single statement. However, the drawback of using SERTCA is that the corresponding statements become longer. Batch OCSP can produce 10 different single-certificate, individually signed OCSP responses at a total cost of less than the cost of 10 RSA signatures (in some cases, about the cost of 2 RSA signatures).

Batch OCSP is based on Fiat's batch RSA computation, as described below. The public key PK of RSA consists of two integers, ie (N, e), which are respectively the well-known modulus and verification exponent. The modulus is the product of two large secret primes p and q, and the security of RSA depends on the difficulty of discovering its constituent primes from the modulus N. The corresponding secret key SK consists of (N,d), where d has the following properties: for all positive integers b less than N, if s is equal to the multiplication of b and d modulo N, then b is equal to s and The self-multiplication of e modulo N. In other words, the operation of multiplying an integer by e modulo N is exactly the opposite of the operation of multiplying an integer by d modulo N.

Computation of an RSA digital signature involves (possibly randomly) formatting a hash of a message m to obtain b, followed by computation of the signature by multiplying b by d, and then obtaining the result modulo N. The corresponding verification procedure computes b from s by multiplying s by e modulo N, and checks that b actually results correctly from m. Comments on Fiat batching RSA signatures are mentioned below. If there are multiple values b1, ..., bi, multiple authentication indices e1, ..., ei, and corresponding signing indices d1, ..., di. Then, by using number theory algorithms (not described here, but well known in the art), s1 pairs modulo N d1, s2 modulo N modulo N d2, ..., si pairs modulo N Computation of m di can be performed more efficiently than i separate individual computations (assuming e1, . . . , ei are different and certain other conditions are met).

As mentioned above, SERTCA (and RTCA) have a digital certificate issued by the CA attesting to the public key used by SERTCA to sign the precomputed OCSP response specifying the validity information of the digital certificate. Also as mentioned above, a SERTCA digital certificate consists of a CA that securely binds together several numbers such as SN, serial number unique to the certificate, PK, SERTCA's public key, identifier, issue date, expiration date, and other data. of digital signatures. Expressed notationally: C = SIG _CA (SERTCA, SN, PK, ID, D ₁ , D ₂ , . . . ). In the case of RSA digital signatures used by SERTCA, SERTCA's public key PK takes the form (n, e), where n is the modulus, e is the verification exponent, and the certificate takes the form:

C = SIG _CA (SERTCA, SN, (n, e), ID, D ₁ , D ₂ , . . . )

RTC responders and relying parties can learn the SERTCA public key from the SERTCA certificate in an authenticated manner. However, since conventional certificates contain only a single exponent e, conventional certificates are not suitable for use with batch RSA that uses multiple different exponents. Unless the verifier (RTC responder and/or relying party) knows the verification exponent used in the particular signature to verify the validity information of the digital certificate, the verifier will not be able to verify the signature. The problem is overcome below using batched RSA inside batched OCSP.

In one approach, SERTCA first generates the modulus n as in traditional RSA signatures, and presents n to the CA for verification as SERTCA's public key. SERTCA protects its secret key, which consists of prime numbers p and q. Afterwards, the CA issues a digital certificate for the public key consisting only of n to SERTCA. For example, a SERTCA certificate may take the form of C=SIG _CA (SN, n, ID, D ₁ , D ₂ , . . . ). Afterwards, the CA notifies SERTCA of the status of the user certificate of SERTCA. Next, SERTCA generates i signature indices d1, ..., di and corresponding verification indices e1, ..., ei. Independently of any relying party request, SERTCA produces statements about the validity status of one or more certificates at specified time intervals, and combines these statements into batches of size i, and within each batch with indices d1,… di uses batch RSA to generate a digital signature for each statement. Next, SERTCA sends a precomputed signature of the validity state to the unsecured responder, additionally including information allowing the responder and/or relying party to determine the exponent ej used to verify each claim. Afterwards, the responder saves the response precomputed manually by SERTCA.

When the Reliance Direction responder is asked for availability status information, the RTC responder answers the query with a manually precomputed response. Each response includes the authentication index ej and SERTCA certificate (if required) needed to authenticate the response. The relying party can then verify the manually precomputed response using RSA verification with the modulus n obtained from the SERTCA certificate and the verification exponent ej obtained from the RTC responder.

Variations on this method are also possible. For example, if the exponent is arbitrary (and no special message format is used before issuing the RSA signature), an adversary who already knows the SERTCA modulus n from the SERTCA certificate can look for an RSA signature that enables the adversary to generate false claims with respect to n and e The exponent e. To improve security, the SERTCA indices e1,...,ei can be fixed in advance (not necessarily obtainable by the transponder every time). Specifically, the exponent can be specified as part of the SERTCA certificate signed by the CA. Next, a SERTCA certificate can take the form:

C = SIG _CA (SERTCA, SN, (n, e1, ..., ei), ID, _D1 , _D2 , ...)

The relying party may also obtain the verification index from the SERTCA certificate or another source instead of the responder.

It would be advantageous to enable a responder and/or a relying party to infer which index ej was used for a particular statement rather than specifying this information explicitly. Such an inference can be made, for example, if the jth certificate validated in each batch always has a sequence number suitable for j modulo i. Next, the responder and/or relying party can simply derive the index's index from the serial number of the certificate whose validity is being verified.

It should be noted that in this approach, the relying party verification implementation may not follow the standard RSA signature verification paradigm, since the SERTCA's public key may not be presented to the relying party as a pair (n, e). The cost of modifying an existing relying party RSA implementation is not allowed in some applications. This can be solved by another method described below.

For the second method, SERTCA initially generates the same modulus n as in conventional RSA signatures, and i verification exponents e1,...,ei, which SERTCA presents to the CA for proof. For SERTCA, it is advantageous to protect the prime factorization of n. Afterwards, the CA can issue i digital certificates for the public key consisting of PK1=(n, e1), PK2=(n, e2), . . . PKi=(n, ei). For example, i SERTCA certificates may take the form: C1 = SIG _CA (SERTCA, SN, (n, e1), ID, _D1 , _D2 , ...), ..., Ci = SIG _CA (SERTCA, SN, (n, ei), ID, D ₁ , D ₂ , . . . ). The CA may then notify SERTCA of the status of its user certificates. After that, and independently of any relying party requests, SERTCA produces statements about the validity status of one or more certificates at specified time intervals, combines these statements into batches of size i, and within each batch Generate a digital signature for each statement using batch RSA with indices d1,...di. Next, SERTCA sends the precomputed signature of the validity state to the unsecured responder, additionally including information allowing the responder and/or relying party to determine the exponent ej used to verify the signing of each statement. Responders save SERTCA precomputed responses.

When the Dependency Responder queries the Responder for validity status information, the RTC Responder answers the query with a precomputed response. Each response signed with exponent ej includes the jth SERTCA certificate Cj (if required or requested). The relying party verifies the precomputed answer using RSA verification with the public key (n, ej) obtained from the SERTCA certificate. It should be noted that relying party authentication is syntactically the same as standard RSA authentication, since the standard form of the RSA public key is obtained from the SERTCA certificate. Therefore, no modification of the standard RSA implementation is required on the part of the relying party. In fact, the relying party may be completely unaware that SERTCA is using batch OCSP.

Variations on the methods described above are also possible. For example, instead of selecting the indices el,...,ej and presenting them to the CA - such indices can be inferred or known in advance by the CA - eg because these indices are fixed parameters of the system. Alternatively, it may be advantageous for the responder and/or relying party to be able to infer which index ej was used for a particular statement rather than specifying this information explicitly. Such an inference can be made, for example, if the jth certificate validated in each batch always has a sequence number suitable for j modulo i. Next, the responder and/or relying party can simply derive the index's index from the serial number of the certificate whose validity is being verified.

Referring to FIG. 19, a flowchart 600 shows the steps performed in initializing SERTCA (or an appropriate RTCA or OCSP responder) to perform batch OCSP. Processing begins below step 602 where the CA certifies modulo n. Step 604 follows step 602, generating i index pairs (authentication index and signing index). In the embodiments herein, the exponent pair is generated by SERTCA using a pair of secret primes whose product is equal to n. However, it is also possible for other embodiments to have other entities generate the index pairs of step 604 and use other algorithms to generate these pairs.

For some embodiments, processing may end after step 604 . However, other embodiments may include additional attestation by the CA, as described above, including having the CA attest to the verification indices el, e2, . . . , ei. In one embodiment, as shown in step 606, the CA certifies i verification indices in a single certificate, as described above. In another embodiment, as shown in step 608, the CA certifies i separate certificates representing RSA-style public keys of n, ek, where ek is one of the i verification exponents.

Referring to FIG. 20, a flowchart 620 shows the steps performed by SERTCA (or an appropriate RTCA or OCSP responder) in generating a manually precomputed response. Processing begins at a first step 622 where the CA provides confirmation information to the SERTCA as described elsewhere in this specification. Following step 622 is step 624, where SERTCA generates artificially precomputed responses using the signature indices d1, d2, . . . , di. Following step 624 is step 626 where the SERTCA provides the artificially precomputed response to the RTC responder in a manner similar to that described elsewhere in this specification.

In some embodiments, SERTCA may provide additional index information to the RTC responder. This is illustrated by the optional steps shown in flowchart 620 of FIG. 20 . The additional index information may consist of one or more proofs of the specific indices being used and/or information indicating which specific indices were used for which artificially pre-computed responses. Of course, as described elsewhere in this specification, there may also be other mechanisms for determining which indices are used for which artificially precomputed responses, so that for SERTCA, that information need not be provided separately. Similarly, there may be a mechanism for communicating the exponent information to the RTC responder (and ultimately to the relying party) so that no further proof has to be provided for the exponent alone.

It should be noted that the batch OCSP technique described above can be used with RTCA instead of SERTCA, and can also be used with traditional OCSP frameworks, where OCSP responders compute digitally signed certificate status information based on queries received from relying parties. Specifically, if an OCSP responder receives isolated queries, the OCSP responder can produce a single RSA-signed response, but if the OCSP responder receives many queries in a short period of time, the OCSP can answer all or some of the queries in the batch manner described above . This will be explained below.

Initially, the CA notifies the OCSP responder of the status of its user certificates in an OCSP-compliant manner. Upon receipt of multiple certificate status queries, the responder may use batch RSA to compute independent single-certificate, conventional OCSP responses to the i-th query, each associated with an exponent ej. The OCSP responder may also specify an index of agreement and/or include a CA-signed responder certificate whose authentication ej (and appropriate RSA modulus n) can be used to verify the responder signature. The CA may provide the OCSP responder with a single OCSP responder certificate, which states that only the RSA modulus n is used by the responder for its batch RSA signatures. For example, expressed as a symbol:

C=SIG _CA (responder, SN, n, ID, D ₁ , D ₂ ,...)

It should be noted that this is particularly accurate and safe if the exponent used by the OCSP responder is fixed. Alternatively, the CA may provide the OCSP responder with a responder certificate specifying that the responder can be used to batch multiple RSA-signed indices. For example, expressed as a symbol:

C=SIG _CA (responder, SN, (n, e1, ... ek), ID, D ₁ , D ₂ , ...)

Alternatively, for a particular OCSP responder, the CA may issue k different responder certificates, one certificate available for each index of the batch RSA signing for the responder. For example, expressed as a symbol:

C1 = SIG _CA (responder, SN, (n, e1), ID, D ₁ , D ₂ , ...), ..., Ck = SIG _CA (responder, SN, (n, ek), ID, D ₁ , _D2 ,...)

Throughout the description herein, CA, RTCA, transponder, transacting party, user may be any entity (eg, person, institution, server, device, computer program, computer file) or collection of entities. Credentials should be understood to include all kinds of certificates, specifically, graded certificates and flat certificates. See, eg, US Patent 5,420,927, which is incorporated herein by reference. The validity status and proof of validity status may include the validity status and proof of validity status of hierarchical certificates (eg, the validity status and proof of validity status of all certificates in a series of certificates). Verifying the validity of certificate C may include verifying the validity of the CA certificate of the CA that issued C and the validity of the RTCA/SERTCA certificate of the RTCA/SERTCA that provided a signed response regarding C's validity status.

Digital signatures and digital signatures are to be understood herein to include any suitable authentication of information, where appropriate.

Although a certificate describes a digitally signed document that binds a particular key to a particular user, following US Patent 5,666,416 (incorporated herein by reference), a certificate should also be understood to include all types of digitally signed documents. For example, a vendor acting as a CA can certify that the price list is under its control by digitally signing the price list (possibly along with date information). It is useful to know the validity status of such certificates. For example, a seller may want to demonstrate the current validity of a price list (and reject a particular price in the price list unless proof of its current validity is shown). Therefore, a customer may wish to determine the current validity of a price list document. The system described here can be used for this. The system described herein can be used to prove the current validity of web pages. In some embodiments, the RTCA/SERTCA generated proof of current validity may be stored with (or associated with) the web page itself. In such cases, the transacting parties may be considered computer files.

Sending a piece of data D (to party X) should be understood to include making D available (or making X receive D).

It should be noted that the systems described herein may be implemented using hardware, software, or some combination thereof, including but not limited to general purpose computer programming, in combination with specialized hardware, such as digital signal processing hardware, to provide the functionality described herein.

While this invention has been disclosed in conjunction with several embodiments, modifications thereof will become apparent to those skilled in the art. Accordingly, the spirit and scope of the present invention are indicated by the following claims.

Claims (11)

1. help the transaction method between first party and the second party, comprising:

Before beginning transaction; One of parties obtains and preserves the online certificate status protocol OCSP response about the artificial precomputation of particular digital certificate; Wherein the OCSP of artificial precomputation response is produced by the entity that is different from first party and second party, and the OCSP of wherein artificial precomputation response is independent of either party the request generation about the validity of particular digital certificate;

The transaction at the beginning of parties;

When transaction, first party provides particular digital certificate to second party; And

Second party is used this particular digital certificate of OCSP response verification of artificial precomputation, and the OCSP response of said artificial precomputation was before preserved before beginning transaction, and used the validity of the said particular digital certificate of OCSP response verification of said artificial precomputation.

2. according to the process of claim 1 wherein that second party obtained the OCSP response of artificial precomputation before the transaction beginning.

3. according to the method for claim 2, wherein the OCSP response of the artificial precomputation of second party buffer memory is to be used for transaction in the future.

4. according to the process of claim 1 wherein that first party obtained the OCSP response of artificial precomputation before the transaction beginning.

5. according to the method for claim 4, wherein the OCSP response of the artificial precomputation of first party buffer memory is to be used for transaction in the future.

6. according to the method for claim 4, also comprise:

First party provides the OCSP of artificial precomputation to respond to second party after the transaction beginning.

7. confirm the method for the validity of digital certificate, comprising:

Generation is about the response of the artificial precomputation of the digital signing of the state of validity of digital certificate;

Inspection is about the response of the artificial precomputation of the said digital signing of digital certificate the state of validity; Wherein the response of artificial precomputation is by the special entity digital signing that is different from the entity that sends digital certificate; Wherein be independent of the request of enquiring digital certificate validity and produce, and the request that wherein is independent of the enquiring digital certificate validity about the response of the artificial precomputation of the said digital signing of digital certificate the state of validity is obtained and preserved about the response of the artificial precomputation of the said digital signing of digital certificate the state of validity; And

Use is from the response of the artificial precomputation of one of the following at least said digital signing of Information Authentication: digital certificate and the certificate of identifying the entity that sends digital certificate.

8. according to the method for claim 7, wherein information is the PKI corresponding to the privacy key of the response of the artificial precomputation that is used for said digital signing.

9. according to the method for claim 7, wherein information is corresponding to the particular digital certificate of the special entity of the artificial precomputation response of identifying digital signing.

10. the method about the information of digital certificate validity is provided, comprises:

For each certificate that digital certificate is concentrated is confirmed the digital certificate the state of validity;

Regularly produce the artificial precomputation message about the state of validity of at least one subclass of digital certificate collection of a plurality of digital signings; And

Regularly give a plurality of transponders of serving the request of dependence side with the artificial precomputation forwards of digital signing; The state of validity of the digital certificate that said dependence side inquiry digital certificate is concentrated is wherein transmitted to be different from about the frequency of the message of other certificate about the message of some certificates.

11., wherein compare about the message of valid certificate and do not transmitted continually relatively about the message of calcellation certificate according to the method for claim 10.

Images