Patent Description:
Increasingly, documents are being signed digitally. Digital signatures employ systems that (a) authenticates a person signing the document is who they say they are when they sign and (b) validates that a signed document is authentic. In this manner, a person who is relying on the document can be certain that the document is authentic and the person who signed the document cannot deny that they signed it. These digital signature systems often use asymmetric cryptography which rely on a secret private key and a non-secret public key associated with an individual. To forge a signature, a malicious actor needs to obtain the secret key or spend the computational cost (if possible) of breaking the signature scheme (i.e. signing a message without having the private key). Attack tolerance to a digital signature system can be classified into mathematical tolerance (e.g., the ability to forge a digital signature by breaking the signature mathematically) or physical tolerance (e.g., tampering with a physical device to forge a signature, etc.). The growth of digital signatures is accompanied by the growth of public keys that need to be tracked and signature requests that need to be processed. As mathematical tolerance and physical tolerance increases, the need for reliable and scalable digital signature infrastructure will increase.

The appended claims define this application. The present disclosure summarizes aspects of the embodiments and should not be used to limit the claims. Other implementations are contemplated in accordance with the techniques described herein, as will be apparent to one having ordinary skill in the art upon examination of the following drawings and detailed description, and these implementations are intended to be within the scope of this application.

An example system for generating a digital signature includes a first backend server, a second backend server, and a frontend server. The frontend server receives a signature request from a remote application server. The signature request includes a first total public key with a cryptographically embedded first server identifier and a second total public key with a cryptographically embedded second server identifier. The frontend server extracts the cryptographically embedded first server identifier from the first total public key. The frontend server then forwards the signature request to first backend server that corresponds to the first server identifier. In response to determining that the first backend server is unavailable, the frontend server extracts the cryptographically embedded second server identifier from the second total public key, and forward the signature request to the second backend server that corresponds to the second server identifier. The responding backend server forwards the signature request to a plurality of remote security devices associated with the total public key. The backend server then receives a first signature from each of the plurality of remote security devices and generates a combined signature based on the first signatures. The backend server then generates the second signature based on the combined signature and a finalizing key. The finalizing key is cryptographically generated based on the server identifier of the backend server. The backend server forwards the second signature to the frontend server. The frontend server then forwards the second signature to the remote application server.

For a better understanding of the invention, reference may be made to embodiments shown in the following drawings. The components in the drawings are not necessarily to scale and related elements may be omitted, or in some instances proportions may have been exaggerated, so as to emphasize and clearly illustrate the novel features described herein. In addition, system components can be variously arranged, as known in the art. Further, in the drawings, like reference numerals designate corresponding parts throughout the several views.

While the invention may be embodied in various forms, there are shown in the drawings, and will hereinafter be described, some exemplary and non-limiting embodiments, with the understanding that the present disclosure is to be considered an exemplification of the invention and is not intended to limit the invention to the specific embodiments illustrated.

With the rise of digital signatures, computer infrastructure is needed to robustly handle the task of generating large number of signatures daily. Signatures are often requested by third party application servers. For example, a signature may be required to acknowledge that a customer has read a website's privacy and personal data policy, or a signature may be required when a customer signs government documents, such as tax documents, or commercial contracts (e.g., mortgage applications, etc.). However, the third party application servers are independent from the digital signature scheme and are not equipped to handle the actual signature process. The signature generation process becomes more complicated when one or more physical security devices are used in the signature generating process. It is not practical for third party application servers to know how to contact the physical security devices. Additionally, as the role of digital signatures become ubiquitous, an infrastructure scheme is needed to add security devices and handle signature generation in a reliable manner. Additionally, a reliable system should be configured such that: (a) private keys are never transferred from the device on which they are created; and (b) when one server in the system is offline, a digital signature can still be created without disruption.

As described below, a Signature Authority (SA) includes backend servers and frontend servers. The backend servers perform signature functions and communicate with specific security devices and/or security tokens. Each backend server has a unique identifier (a "BESID"). The frontend servers communicate with third party application servers to handle signature requests. A customer registers with the Signature Authority. During the registry process, a customer associates themselves with one or more physical security devices and/or physical security tokens. The security device(s) and/or security token(s) are assigned to two or more backend servers so that those particular backend servers have the information necessary to communicate with the particular security device and/or security token. Additionally, those backend servers each use the security device and/or security token unique information to generate a certificate with a Certificate Authority (CA) that identifies the particular backend server.

When a composite key scheme is used, (a) the security devices generate a private key and a public key and provides the public key to the designated backend servers and/or, (b) when a security token is used, the assigned backend servers generate a private key and a public key associated with the customer. Using the two or more independent public keys, the backend servers each create a composite public key. The backend servers then each create a total public key based on the composite public key and the BESID. The backend servers each independently send the total public key, its BESID, and a unique client identifier (a "CID") the Certificate Authority (CA)). The Certificate Authority generates independent certificates associated with the CID. In some examples, the Certificate Authority (CA) designates one of the certificates as a "primary certificate" and the other certificate as a "secondary certificate. " The Certificate Authority (CA) is a public repository of these certificates that supplies certificates in response to receiving a request that is accompanied by a CID.

When a split key scheme is used, each backend server generates two or more key shares and a public key. Each backend server shares one of the key shares with the security device and keeps one of the key shares. The security device stores each of the key shares associated with BESID of the backend server that generated it. The backend servers then each create a total public key based on the public key and their BESID. The backend servers each independently send the total public key, its BESID, and a unique client identifier (a "CID") the Certificate Authority (CA)).

The security devices may be any portable electronic device that is capable of (a) securely storing the independently generated private key, (b) receiving an input from a signer, (c) reliably authenticating the identity of the signer based on that input, (d) receiving a message to generate a signature, (e) generating the signature with the independently generated private key and the message, and (f) transmitting the signature to a computing device (e.g., a server, etc.) requesting the signature. In some examples, the security devices may be smartphones, smart watches, tablet computers, jewelry with embedded electronics (e.g., bracelets, rings, broaches, etc.), smart cards (e.g., a credit card, an identification card, etc.), and/or an electronic hanko, etc. In some examples, each security device is configured to physically receive an input (e.g., a biometric identifier such as a fingerprint, a password, etc.) from the signer independently from any other security device. In some examples, each security device communicates with computing device (e.g., via a wireless connection to the Internet, etc.). Alternatively, in some examples, one of the security devices acts as a primary device that communicates with the computing device (e.g., via a wireless connection to the Internet, etc.) while other security devices communicate with the primary device via a local area network (e.g., a wireless local area network, a Bluetooth® Low Energy connection, etc.) to communicate with the computing device.

The security token communicates directly or indirectly (e.g., via a mobile device) with the backend server to authenticate an identity of the customer when the backend server is generating a digital signature. The security token may be any mobile device that can communicate with the backend server and securely provide user credentials when the user provides authentication to the device. For example, the device may have biometric sensors and/or biometric input (e.g., a iris scanner, a finger printer scanner, etc.). As another example, the device may have a GPS and may rely on geofencing or its proximity to another device (e.g., a security device) in order to authenticate the user. In some examples, the security token may be another security device that is not involved in the current signature generation. In some examples, the security token is jewelry with embedded electronics (e.g., bracelets, rings, broaches, etc.) or a smart card (e.g., a credit card, an identification card, etc.).

When a digital signature is to be created, the customer provides credentials and/or the customer's CID to an application server (e.g., credential controlled by the application server to identify the customer). The application server uses the identity of the customer to retrieve multiple certificates from the Certificate Authority (CA). The application server has an established relationship with at least two frontend servers of the Signature Authority (e.g., established when the application server enrolls with the Signature Authority, etc.). In some examples, one of the frontend servers may be designated as a "primary server" and another one of the frontend servers may be designated as a "secondary server. " When more than two frontend servers as associated with the application server, the Signature Authority (SA) may designate an order or priority for the backend servers. The application server sends a signature request to the primary (or first) frontend server. The signature request includes the multiple certificates retrieved from the Certificate Authority (CA) and a message. The message may be an original message (e.g., the digital document to be signed) or a message digest computed from the original message by applying a cryptographic hash function (e.g., SHA-<NUM>, etc.) to the original message. If the application server does not received an acknowledgement of its request from the primary frontend server within a threshold period of time (e.g., <NUM> milliseconds, one second, etc.), the application server resends the signature request to the secondary frontend servers. If there are more than two designated frontend servers, this process repeats until the application server receives an acknowledgement of its request. If no acknowledgement is received, the application server generates an error message to the user.

The frontend server extracts the BESID from the primary (or first) certificate and forwards the signature request to the backend server associated with the BESID. If the front end server does not received an acknowledgement of its request from the primary backend server within a threshold period of time (e.g., <NUM> milliseconds, one second, etc.), the frontend server extracts the BESID from the secondary certificate and forwards the signature request to that backend server. If there are more than two certificates that accompany the signature request, this process repeats until the frontend server receives an acknowledgement of its request. If no acknowledgement is received, the frontend server generates an error message and transmits it to the application server the sent the signature request.

The backend server, in conjunction with security devices and/or security tokens generates a signature with the message. The backend sever then uses the finalizing key to generate a finalized signature. The backend server sends the finalized key to the frontend server that sent the signature request. The frontend server then forwards the finalized signature to the application server that requested the signature. The application then appends the finalized signature to a digital document. Later, when required, the digital signature can be verified using the certificate.

<FIG> illustrates a system <NUM> to implement a digital signature system using reliable servers in accordance with the teachings of this disclosure. The system <NUM> generates a digital signature that is secure and reliable. In the illustrated example, the system <NUM> includes a signing authority <NUM>, a certificate authority <NUM>, and one or more application servers <NUM>.

The signing authority <NUM> acts as an intermediary between the application servers <NUM> and one or more security devices <NUM> processed by a <NUM> user of the application server <NUM>. When a security device <NUM> is registered with the signing authority <NUM>, the signing authority <NUM> collects and/or generates information for the certificate authority <NUM> to generate multiple certificates associated with the security device(s) <NUM>. The signing authority <NUM>, in conjunction with the security device(s) <NUM>, generates digital signatures in response to a signature request that includes the certificates that are sent by one of the application servers <NUM>.

The certificate authority <NUM> stores generates and stores certificates. The certificate authority <NUM> generates certificates based on input from the signing authority <NUM>. The input includes a public key and a client identifier (CID). The certificate authority <NUM> stores the generated certificates in a database (sometimes referred to as a "certificate repository" or a "public key repository"). The certificate authority <NUM> provides the stored certificates to the application servers <NUM> in response to receiving a CID associated with the certificates (e.g., the certificates are freely available to an entity that requests them using a CID).

A customer <NUM> may interact with the application server <NUM> in a manner such that the application server <NUM> generates a signature request. For example, the customer <NUM> may be signing a document or accepting a privacy and data use policy on a website. When the application servers <NUM> requires a digital signature, the application servers <NUM> obtains the certificates from the certificate authority <NUM> associated with a CID supplied, directly or indirectly, but the customer <NUM>. The signing authority <NUM> manages the signature process so that the application server <NUM> does not require a direct relationship with the security device(s) <NUM> of the customer <NUM>. The application servers <NUM> are communicative coupled to the signing authority <NUM> via pre-established relationship. For example, when the owner of an application server <NUM> desires to accept digital signatures from the signing authority <NUM>, the signing authority <NUM> may provide settings on how to transmit the signature requests.

<FIG> illustrates a system that employs traditional asymmetric cryptography using a single private key, and generally, the system to verify a signature. A common asymmetric cryptography system (sometimes referred to as a "public key cryptosystem") used for digital signatures is Rivest-Shamir-Adleman (RSA). As illustrated in <FIG>, the RSA cryptosystem uses four functions. The first function is a Private Key Generation function (f<NUM>), which generates a private key <NUM> based on two distinct prime numbers p and q. The integers p and q are randomly chosen and are kept secret. The second function is a Public Key Generation function (f<NUM>) which generates a public key <NUM> based on the two prime numbers p and q. The public key <NUM> consists of a public modulus (n) and a public exponent (e). The public modulus (n) is calculated in accordance with Equation <NUM> below. The public exponent (e) is selected such that Equation <NUM> below is true. <MAT> <MAT> In equation <NUM> above, gcd is the greatest common divisor function that returns the largest positive integer that divides each of the inputs. The RSA cryptosystem uses a signing function (f<NUM>) to sign a message (m) <NUM> with the private key <NUM>, where <MAT>. The RSA cryptosystem uses a private exponent (d) to calculate the signature <NUM> of the message (m) <NUM>. The private exponent (d) is calculated in accordance with Equation <NUM> below. <MAT> The signature <NUM> of the message (m) <NUM> is σ(m), which is calculated in accordance with Equation <NUM> below. <MAT> To verified a received signature (σ) <NUM> and an accompanying message (m) <NUM>, the RSA cryptosystem uses a fourth function (f<NUM>) based on the public modulus (n) and the public exponent (e). The signature (σ) <NUM> is verified when Equation <NUM> below is true.

Secure implementation of a signature scheme based on RSA requires that a signer (e.g., a person or group of persons) has sole control of the functions: the Private Key Generation function (f<NUM>), the Public Key Generation function (f<NUM>), and the signing function (f<NUM>) within a security perimeter. Typically, a device implementing the RSA signature scheme: (a) executes the Private Key Generation function (f<NUM>) and the Public Key Generation function (f<NUM>) only once in a lifetime of the device; and (b) assures that only the authorized signer can execute the signing function (f<NUM>). The private key (e.g., the private key <NUM>) must never leave the device. The device must always be capable of reliably authenticating the signer before executing signing function (f<NUM>). Thus, the security device requires, within the security perimeter, (a) computational power to computer the functions, (b) memory to store the keys, (c) input/output (I/O) devices, and (d) an authentication solution. The security perimeter may consist of separate electronics that each implement a partial functionality. For example, the key generating functions, the Private Key Generation function (f<NUM>) and the Public Key Generation function (f<NUM>), may be implemented by one set of electronics, and the signing function (f<NUM>) may be implemented as a separate set of electronics.

The cryptographic attack tolerance of a signature scheme (such as the RSA cryptosystem described above) is defined in terms of computational complexity theory and has mathematical and physical components. The measure of mathematical attack tolerance takes into account the computational resources (number of steps, memory in bits, program size, etc.) that is necessary to break the scheme (i.e., sign a message without having access to the private key). The computational cost of breaking the scheme is expressed as a security level. The security level is usually expressed in "bits. " "N-bit security" means that the malicious actor would have to perform <NUM>N operations to break the scheme. For example, a signing scheme may have <NUM>-bit or <NUM>-bit security. The monetary cost of breaking the scheme is considered proportional with the computational cost. Physical attack tolerance of a security device refers to the cost of forging a signature without breaking the signature scheme mathematically (e.g., tampering with the security device).

The mathematical and physical attack tolerance required for a signing scheme are derived from risk analysis and takes into account the application in which the signature solution is being used. Often, the physical design of security devices are a weakness in an RSA-based signing scheme. One approach to increasing physical attack tolerance is to require cooperation between multiple devices. In such an approach, a signature key (e.g., a master private key) is shared between several security devices. As such, a signature can only be created when the security devices cooperate. Attacking one device (e.g., physically tampering with one device, uncovering the portion of the master private key on one device, etc.) is insufficient to forge signatures. Cryptography schemes in to address these issues are discussed in connection with <FIG> and <FIG> below.

In <FIG>, a master private key <NUM> is split into two private key shares <NUM> and <NUM> (sometimes referred to as a Split-Key signing scheme). The master private key <NUM> is generated by a trusted dealer <NUM> who splits the master private key <NUM> with a key split function (f<NUM>) to create a first private key share (d') <NUM> and a second private key share (d") <NUM>. The trusted dealer <NUM> may split the master private key <NUM> for additive sharing or for multiplicative sharing. <FIG> illustrates the trusted dealer <NUM> splitting the master private key <NUM> for additive sharing. When splitting for additive sharing, the trusted dealer <NUM> uses the key split function (f<NUM>) to derive the first private key share (d') <NUM> and the second private key share (d") <NUM> based on the private exponent (d) of the master private key <NUM> in accordance to Equation <NUM> below. <MAT> When splitting for multiplicative sharing, the trusted dealer <NUM> uses the key split function (f<NUM>) to derive the first private key share (d') <NUM> and the second private key share (d") <NUM> in accordance to Equation <NUM> below. <MAT> The trusted dealer <NUM> transmits the first private key share (d') <NUM> to a first security device <NUM> and the second private key share (d") to a second security device <NUM>. When generating a signature, the security devices <NUM> and <NUM> perform the signing function (f<NUM>) with their respective private key shares to generate a first signature share (σ') <NUM> and a second signature share (σ") <NUM>. The signature (σ) <NUM> is generated with the first signature share (σ') <NUM> and the second signature share (σ") <NUM> with a splitkey combiner function (f<NUM>). For additive sharing, the splitkey combiner function (f<NUM>) is calculated in accordance with Equation <NUM> below. <MAT> For multiplicative sharing, the splitkey combiner function (f<NUM>) is calculated in accordance with Equation <NUM> below. <MAT> The generated signature <NUM> is used as described above with the traditional RSA signing scheme.

In some examples, one of the private key shares is held by security device and the other private key share is held by a backend server (e.g., the backend server <NUM> of <FIG> below) The Split-Key signing scheme often requires the trusted dealer <NUM> to split a master private key <NUM> into the private key shares <NUM> and <NUM> and then securely transmitting the signature shares <NUM> and <NUM> to the security devices. In some examples, the trusted dealer <NUM> uses a distributed generation of shares is used, where the first signature share (σ') <NUM> and the second signature share (σ") <NUM> and the common public key <NUM> are generated as the outcome of a multi-party cryptographic protocol (e.g., the multi-party cryptographic protocol Π) in which the master private key <NUM> never exists as a whole.

<FIG> illustrates a system that employs composite-key key asymmetric cryptography that uses multiple private keys that are independent of each other. <FIG> illustrates a Comp Key signing scheme using a first security device <NUM> and a second security device <NUM>. In some examples, one of the first or second security devices <NUM> and <NUM> is a backend server (e.g., the backend server <NUM> of <FIG> below). The security devices <NUM> and <NUM> each independently generate a private key <NUM> and <NUM> using the Private Key Generation function (f<NUM>) (as described above). Additionally, the security devices <NUM> and <NUM> each generate a public key <NUM> and <NUM> with a public modulus (n) (e.g., calculated in accordance with Equation <NUM> above) and a public exponent (e) (e.g., determined in accordance with Equation <NUM> above). The public keys <NUM> and <NUM> are transmitted to the backend server. When the security devices <NUM> and <NUM> receive a message <NUM> to use to generate a signature, after the security devices each independently authenticate the signer, the security devices <NUM> and <NUM> use the signing function (f<NUM>) (as described above) to each independently generate a signature <NUM> and <NUM>.

To sign a digital document, a composite signature <NUM> is generated from the first signature (σ<NUM>) <NUM> and the second signature (σ<NUM>) <NUM>. In the illustrated example, the composite signature (σC) <NUM> is generated with a composite signature function (f<NUM>) in accordance with Equation <NUM> below. <MAT> In Equation <NUM> above, n<NUM> is the public modulus of the first public key <NUM> and n<NUM> is the public modulus of the second public key <NUM>. Additionally, the coefficients a and b satisfy an<NUM> + bn<NUM> = <NUM>. The composite signature (σC) <NUM> is further modified by the backend server and then used to append a digital document.

To verify a signed document, the composite public modulus (nC) of the composite public key <NUM> is calculated using a composite public key function (f<NUM>) in accordance with Equation <NUM> below. The composite public modulus (nC) of the composite public key <NUM> is based on the public modulus (n<NUM>) of the first public key <NUM> and the second public modulus (n<NUM>) of the second public key <NUM>.

Using the composite public key <NUM> (<nC, e>) and the message <NUM>, the signature (σS) associated with the signed digital document is verified with function f<NUM> (as described above).

<FIG> illustrates a system that generates a total public key <NUM> and a finalizing key <NUM> using a unique backend server identifier (BESID) <NUM>. The system embeds the BESID <NUM> into the total public key <NUM> and the finalizing key <NUM>. The description below uses the Comp Key scheme, but the Split Key scheme may also be used.

The system generates the total public key <NUM> and a finalized signature <NUM> using an identity embedding function (f<NUM>). The identity embedding function (f<NUM>) uses the composite public key <NUM> (or any other applicable public key) and the BESID <NUM> to generate the total public key <NUM> and the finalized signature <NUM>. In the illustrated example, the identity embedding function (f<NUM>) is calculated in accordance with Equations <NUM> through <NUM> below. First, the system computes an L bound according with Equation <NUM> below. <MAT> The system computes an R bound in accordance with Equation <NUM> below. <MAT> In Equations <NUM> and <NUM> above, c is the m-bit length BESID, k is a reliability parameter, and n' is an RSA modulus (with <NUM>l'-<NUM> ≤ n' < <NUM>l' and <NUM>m-<NUM> ≤ n' < <NUM>m) (such as, the modulus (nC) of the composite public key <NUM>, etc.). The system then finds prime number (p) where Equation <NUM> below is true. <MAT> In Equation <NUM> above, e is the public exponent and gcd is the greatest common divisor function that returns the largest positive integer that divides each of the inputs.

The system computes a modulus (nTP) of the total public key <NUM> in accordance with Equation <NUM> below. <MAT> As a result, the identity embedding function (f<NUM>) outputs the total public key <NUM> as <nTP, e>.

The system computes a finalizing exponent (df) in accordance with Equation <NUM> below. <MAT> The system then finds the Bezout coefficients a' and b' such that Equation <NUM> below is satisfied. <MAT> As a result, the identity embedding function (f<NUM>) outputs the finalizing key <NUM> as (n, a', b', p, df).

After the backend server generates the composite signature <NUM>, the system generates a finalized signature (σF) <NUM> to send to the frontend server to be forwarded to the requesting application server. The finalized signature (σF) <NUM> has the BESID <NUM> of the backend server embedded in it using a finalizing function (f<NUM>). The finalizing function (f<NUM>) uses an RSA signature (σ') (such as, the composite signature (σC) <NUM>, etc.), a padded message P, and the finalizing key <NUM> (e.g., (n, a', b', p, df), etc.) to generate the finalized signature (σF). In the illustrated example, the finalizing function (f<NUM>) is calculated in accordance with Equations <NUM> through <NUM> below. Initially, the system reduces the padded message P in accordance with Equation <NUM> below. <MAT> In Equation <NUM> above, Pf is the reduced message. The system then computes a partial final signature (σf) in accordance with Equation <NUM> below. <MAT> The system them computes the finalized signature (σF) <NUM> in accordance with Equation <NUM> below. <MAT> The system then forwards the finalized signature (σF) to the frontend server.

<FIG> are block diagrams of the certificate authority <NUM>, in cooperation with the signing authority <NUM>, generating certificates <NUM> to be associated with a user. <FIG> illustrates an example when the certificate authority <NUM> has access to internal information of the signing authority <NUM> (such as, the BESIDs <NUM>, etc.). For example, the certificate authority <NUM> may be closely related to the signing authority <NUM> (e.g., operated by the same entity, etc.) or incorporated into the signing authority <NUM>. <FIG> illustrates an example when the certificate authority <NUM> does not have access to internal information of the signing authority <NUM>. For example, the certificate authority <NUM> may be operated by a separate entity as the signing authority <NUM>. In the illustrated examples of <FIG>, the certificate authority <NUM> includes a certificate authority (CA) private key <NUM> and a certificate generator <NUM>. The CA private key <NUM> may be generated by the certificate authority <NUM> by any suitable means (e.g., the Private Key Generation function (f<NUM>) as described above). The certificate generator <NUM> received input from the signing authority <NUM> and generates the certificate <NUM>.

In <FIG>, the certificate generator <NUM> includes a combination function (f<NUM>) that generates a certification statement <NUM> using a public key (e.g., the composite public key <NUM> of <FIG> above), the BESID <NUM>, and a client identifier (CID) <NUM>. The public key, the BESID <NUM>, and the CID <NUM> are received from the signing authority <NUM>. The combination function (f<NUM>) generates the certification statement <NUM> that is a list or concatenation of the public key, the BESID <NUM>, and the CID <NUM>.

In <FIG>, the certificate generator <NUM> includes a combination function (f<NUM>) that generates a certification statement <NUM> using a total public key (e.g., the total public key <NUM> of <FIG> above) and the CID <NUM>. The total public key and the CID <NUM> are received from the signing authority <NUM>. The combination function (f<NUM>) generates the certification statement <NUM> that is a list or concatenation of total public key and the CID <NUM>.

The certificate generator <NUM> generates the certificate <NUM> by applying signing function (f<NUM>) to the certification statement <NUM> using the CA private key <NUM>. The certificate generator <NUM> then stores the certificate <NUM> associated with the CID <NUM> in a database.

When the certificate <NUM> is included in a signature request (e.g., the signature request <NUM> of <FIG> below), the signing authority <NUM> uses an identity extraction function (f<NUM>) to extract the BESID <NUM> from the certificate <NUM>. The identify extraction function (f<NUM>) extracts the BESID <NUM> from the certificate <NUM> by decrypting the certificate using the public key of the certificate authority <NUM> that corresponds to the CA private key <NUM> and extracts the BESID <NUM> from the certification statement <NUM>.

<FIG> is a block diagram of a system to generate multiple certificates <NUM> associated with a customer <NUM>. When the security device <NUM> is first activated, it generates a private key (e.g., the private key <NUM> of <FIG> above) and a public key <NUM>. The security device <NUM> transmits the public key <NUM> to the signing authority <NUM>, which routes the public key <NUM> to at least two backend servers <NUM>. These backend servers <NUM> become the servers with the information (e.g., IP address, credentials, etc.) necessary to communicate with the security device <NUM>. The backend servers <NUM> also receive or otherwise retrieve the CID <NUM> associated with the security device <NUM> (e.g., obtained via an activation process, etc.).

In the illustrated example, the backend servers 702a and 702b independently generate a public key and combine the generate public key with the public key received from the security device <NUM> using the composite public key function (f<NUM>). Alternatively, the customer <NUM> registers two or more security devices <NUM> and the backend servers <NUM> combine the received public keys using the composite public key function (f<NUM>). In the illustrated example, the primary backend server 702a generates a primary composite public key 422a. The primary backend server 702a forwards the composite public key 422a, its BESID 506a, and the CID <NUM> to a frontend server <NUM>. The frontend server <NUM> transmits the composite public key 422a, the CID <NUM>, and the BESID 506a to the certificate authority <NUM>. The certificate authority <NUM>, using the certificate generator <NUM>, generates a primary certificate 706a using the composite public key 422a, the CID <NUM>, and the BESID 506a.

The secondary backend server 702b generates a secondary composite public key 422b. Because the public key generated by the secondary backend server 702b is different than the public key generated by the primary backend server 702a, the secondary composite public key 422b is different than the primary composite key <NUM>. The secondary backend server 702b forwards the composite public key 422b, its BESID 506b, and the CID <NUM> to the frontend server <NUM>. The frontend server <NUM> transmits the composite public key <NUM>, the CID <NUM>, and the BESID 506b to the certificate authority <NUM>. The certificate authority <NUM>, using the certificate generator <NUM>, generates a secondary certificate 706b using the composite public key 422b, the CID <NUM>, and the BESID 506b.

<FIG> is a block diagram of a system that uses redundant certificates (e.g., the primary certificate 706a and the secondary certificate 706b) associated with a customer <NUM> to generate a digital signature (e.g., the finalized signature <NUM>) to sign a document. In the illustrated example, the customer <NUM> interacts with the application server <NUM> such that the application server <NUM> needs to generate a signed document. The application server <NUM> receives and/or otherwise retrieves the CID <NUM> (e.g., via the customer <NUM>). Using the CID <NUM>, the application server requests the certificates associated with the CID <NUM> (e.g., the primary certificate 706a and the secondary certificate 706b, etc.). The application server <NUM> generates a signature request <NUM> that includes (i) the certificates 706a and 706b and (ii) a message <NUM>. The message may be an original message (e.g., the digital document to be signed) or a message digest computed from the original message by applying a cryptographic hash function (e.g., SHA-<NUM>, etc.) to the original message.

The application server <NUM> has an established relationship with at least two frontend servers (e.g., a primary frontend server 704a and a secondary frontend server 704b) of the signing authority <NUM> (e.g., established when the application server <NUM> enrolls with the signing authority <NUM>, etc.). The relationship with multiple frontend servers provide redundancy for when one of the frontend servers is unavailable. The signing authority <NUM> may select which particular frontend servers are assigned to the application server <NUM> based on traffic management principles. For example, application servers <NUM> assigned to the same primary frontend server 704a may be assigned to different secondary frontend servers 704b so that the unavailability of a primary frontend server 704a does not stress any one secondary frontend server 704b. The frontend server that acts as a primary frontend server 704a of one application server <NUM> may be the secondary frontend server 704b of another application server <NUM>.

The application server <NUM> sends the signature request <NUM> to the primary frontend server 704a. If the application server <NUM> does not get an acknowledgement of the signature request <NUM> and/or receives any other indication that the primary frontend server 704a is unavailable, the application server <NUM> sends the signature request <NUM> to the secondary frontend server 704b. In examples where the application server <NUM> is associated with more than two frontend servers, this may continue until the application server <NUM> has tried all of the frontend servers it is associated with. If no frontend servers are available, the application server <NUM> generates an error.

The frontend server (e.g., the primary frontend server 704a or the secondary frontend server 704b) that receives the signature request <NUM> extracts the BESID 506a of the primary backend server 702a from the primary certificate 706a using the identity extraction function (f<NUM>). The frontend sever then forwards the signature request <NUM> to the primary backend server 702a. If the frontend server does not get an acknowledgement of the signature request <NUM> and/or receives any other indication that the primary backend server 702a is unavailable, the frontend server (i) extracts the BESID 506b of the secondary backend server 702b from the secondary certificate 706b using the identity extraction function (f<NUM>) and (ii) sends the signature request <NUM> to the secondary backend server 702b. In examples where the signature request <NUM> includes more than two certificates, this may continue until the frontend server has tried to forward the signature request <NUM> using all of the certificates. If no backend servers are available, the frontend server sends an error message to the application server <NUM>.

The backend server (e.g., the secondary backend server 702b) identifies the customer <NUM>. In the illustrated example, backend server includes a private key associated with the customer <NUM> (e.g., an independent private key for the Comp Key scheme or a key share for the Split Key scheme, etc.). The backend server attempts to authenticate the identity of the customer <NUM> (e.g., via a security token <NUM>). When the backend server successfully authenticates the identity of the customer <NUM>, it uses the signing function (f<NUM>) to generate a first signature (or first signature share) using the message <NUM> and the private key associated with the customer <NUM>. The backend server also sends the signature request (or a part thereof) to the security device <NUM> associated with the customer <NUM>. After the security device <NUM> authenticates the identity of the customer <NUM>, the security device <NUM> generates a second signature (or a second signature share) <NUM> and sends it the backend server that sent it the signature request <NUM>. In a Comp Key embodiments, the backend server generates a composite signature <NUM> using the composite signature function (f<NUM>). In Split Key embodiments, the backend server generates signature using the splitkey combiner function (f<NUM>). Using the finalizing key <NUM>, the backend server generates the finalized signature <NUM> using the finalizing function (f<NUM>).

The backend server sends the finalized signature <NUM> to the frontend server that sent the signature request <NUM>. The frontend server sends the finalized signature <NUM> to the application server <NUM> that sent the signature request <NUM>. The application server <NUM> appends the finalized signature <NUM> to the digital document to be signed.

The frontend servers and the backend servers may operate on the same physical machine or set of physical machines using virtual computing resources, such as virtual machines or containers, etc. In some examples, the frontend servers and the backend servers are isolated from each other so that if one is breached, none of the others are affected. For example, if one frontend server is breached, the other frontend servers and the backend servers are not affected.

<FIG> illustrates a security device <NUM> implementing a device-side portion of the signing scheme of <FIG>, <FIG>, <FIG>, and <FIG>. The security device <NUM> implements the functions: the Private Key Generation function (f<NUM>), the Public Key Generation function (f<NUM>), and signing function (f<NUM>). The security device <NUM> includes a control interface <NUM> and a input/output (I/O) interface <NUM>. The control interface <NUM> receives input from a signer (e.g., the customer <NUM>, etc.) to authenticate the identity of the signer before the security device <NUM> generates a signature (e.g., the signatures <NUM> and <NUM>). The I/O interface <NUM> communicates directly or indirectly with the signing authority <NUM> to transmit the signature and the public key, and receive the message used to generate the signature.

<FIG> is a block diagram of electronic components <NUM> of the security device <NUM> of <FIG>. In the illustrated example, the electronic components <NUM> include the control interface <NUM>, the I/O interface <NUM>, a processor or controller <NUM>, and memory <NUM>, and a data bus <NUM> that connects the other electronic components.

The control interface <NUM> provides a physical interface between the security device <NUM> and the signer. The control interface <NUM> may include a digital camera (e.g., for image capture, visual command recognition, facial recognition, iris recognition, etc.), a touch screen and/or keyboard (e.g., for input of credentials), an audio input device (e.g., a microphone for voice recognition, etc.), a biometric input device (e.g., a fingerprint scanner, etc.) and/or a biometric sensor (e.g., a pulse oximeter, a pulse sensor, etc.). For example, the control interface <NUM> may include the touch screen and fingerprint identity sensor of a smart phone. The input from the signer to the control interface <NUM> is used to authenticate the identity of the signer. In some examples, more than one method of identifying and authenticating the signer is included. For example, the signer may need to provide both a fingerprint and a password. In some examples, the control interface <NUM> may be different between two cooperating security devices <NUM>. For example, one security device <NUM> may have a camera to perform facial recognition and the other security device <NUM> may have a fingerprint scanner.

The I/O interface <NUM> provides an interface to communicate with other devices to transmit the public key and the signature and receive the message. The I/O interface <NUM> includes communication controllers and antenna for one or more for standards-based networks (e.g., Global System for Mobile Communications (GSM), Universal Mobile Telecommunications System (UMTS), Long Term Evolution (LTE), Code Division Multiple Access (CDMA), WiMAX (IEEE <NUM>); Near Field Communication (NFC); local area wireless network (including IEEE <NUM> a/b/g/n/ac or others), Bluetooth® and Bluetooth® Low Energy, and Wireless Gigabit (IEEE <NUM>. 11ad), etc.). The I/O interface <NUM> directly or indirectly (e.g., via anther security device <NUM>) communicates with an external network. The external network may be a public network, such as the Internet; a private network, such as an intranet; or combinations thereof, and may utilize a variety of networking protocols now available or later developed including, but not limited to, TCP/IP-based networking protocols.

The processor or controller <NUM> may be any suitable processing device or set of processing devices such as, but not limited to: a microprocessor, a microcontroller-based platform, a suitable integrated circuit, one or more field programmable gate arrays (FPGAs), and/or one or more application-specific integrated circuits (ASICs). The memory <NUM> may be volatile memory, non-volatile memory, unalterable memory, read-only memory, and/or high-capacity storage devices (e.g., hard drives, solid state drives, etc). In some examples, the memory <NUM> includes multiple kinds of memory, particularly volatile memory and non-volatile memory. Additionally, the memory <NUM> may include secure memory (sometimes referred to as "cryptomemory") which includes an embedded hardware encryption engine with its own authentication keys to securely store information.

<FIG> is a flowchart of a method to use redundant certificates <NUM> associated with a customer <NUM> to generate a document signed by a digital signature, which may be implemented by the application server <NUM> of <FIG> and <FIG>. Initially, at block <NUM>, the application server <NUM> receives an input from a customer <NUM> that results in a digital document to sign. For example, the customer <NUM> may click on an acceptance button to indicate acceptance of a privacy policy of a website associated with the application server <NUM>. At block <NUM>, the application server <NUM> retrieves two or more certificates <NUM> associated with the customer <NUM> from the certificate authority <NUM>. At block <NUM>, the application server <NUM> sends a signature request <NUM> to the primary frontend server 704a. The application server <NUM> is configured to communicatively couple to at least two frontend servers. In some example, the order of the frontend server (e.g., which frontend server is the primary frontend server 704a and which frontend server is the secondary frontend server 704b, etc.) is designated by the signing authority <NUM> when then application server <NUM> registers with the signing authority <NUM>. Alternatively, in some example, the application server <NUM> selects one of the frontend servers to send the signature request <NUM> to first.

At block <NUM>, the application server <NUM> determines whether it has received an indication that the frontend server is unavailable. For example, the application server <NUM> may (b) wait a threshold period of time to receive the signature from the frontend server, (b) receive a message that the frontend server is not available, and/or (c) fail to receive an acknowledgement from the frontend server in response to the signature request <NUM>. If the frontend server is available, the method continues at block <NUM>. Otherwise, if the frontend server is not available, the method continues at block <NUM>.

At block <NUM>, the application server <NUM> receives a finalized signature <NUM> from the frontend server. At block <NUM>, the application server <NUM> appends finalized signature to the digital document.

At block <NUM>, the application server <NUM> determines whether there is another frontend server to send the signature request. If there is another frontend server, the method continues to block <NUM>. Otherwise, if there is not another frontend server, the method continues to block <NUM>.

At block <NUM>, the application server <NUM> sends the signature request <NUM> to the next frontend server (e.g., the secondary frontend server 704b, etc.). The method then returns to block <NUM>.

At block <NUM>, the application server <NUM> generates an error message.

<FIG> is a flowchart of method to use redundant certificates associated with a customer <NUM> to generate a document signed by a digital signature, which may be implemented by the frontend server(s) <NUM> of <FIG> and <FIG>. Initially, at block <NUM>, the frontend server <NUM> receives a signature request <NUM> from an application server <NUM> that includes multiple certificates (e.g., a primary certificate 706a and a secondary certificate 706b, etc.). At block <NUM>, the frontend server <NUM> extracts the BESID <NUM> from the primary certificate 706a using the identity extraction function (f<NUM>). At block <NUM>, the frontend server <NUM> sends the signature request <NUM> to the backend server <NUM> that corresponds to the BESID <NUM> extracted at block <NUM>.

At block <NUM>, the frontend server <NUM> determines whether it has received an indication that the backend server <NUM> is unavailable. For example, the frontend server <NUM> may (b) wait a threshold period of time to receive the signature from the backend server <NUM>, (b) receive a message that the backend server <NUM> is not available, and/or (c) fail to receive an acknowledgement from the backend server <NUM> in response to the signature request <NUM>. If the backend server <NUM> is available, the method continues at block <NUM>. Otherwise, if the backend server <NUM> is not available, the method continues at block <NUM>.

At block <NUM>, the frontend server <NUM> receives the finalized signature <NUM> from the backend server <NUM>. At block <NUM>, the frontend server <NUM> sends the finalized signature <NUM> to the application server <NUM>.

At block <NUM>, the frontend server <NUM> determines whether there is another certificate (e.g., a secondary certificate 706b). If there is another certificate, the method continues to block <NUM>. Otherwise, if there is not another certificate, the method continues to block <NUM>. At block <NUM>, the frontend server <NUM> extracts the BESID <NUM> from the secondary certificate 706b using the identity extraction function (f<NUM>). At block <NUM>, the frontend server <NUM> sends the signature request <NUM> to the backend server <NUM> that corresponds to the BESID <NUM> extracted at block <NUM>. The method then returns to block <NUM>.

At block <NUM>, the frontend server <NUM> sends an error message to the application server <NUM>.

<FIG> is a flowchart of a method to generate a signature for a digital document which may be implemented by the system of <FIG> and <FIG>. In <FIG>, the backend server <NUM> stores a private key for a customer <NUM>. At block <NUM>, the backend server <NUM> sends the signature request <NUM> to the security device <NUM> associated with the corresponding certificate <NUM> included in the signature request <NUM>. At block <NUM>, the security device <NUM> authenticates the customer <NUM>. For example, the security device <NUM> may authenticate the customer <NUM> in response to receiving a finger print and/or a set of credentials. At block <NUM>, the security device <NUM> generates a first signature with its stored private key using the signing function (f<NUM>). At block <NUM>, the security device <NUM> transmits the first signature to the backend server <NUM>.

At block <NUM>, the backend server <NUM> authenticates the customer <NUM>. In some examples, the backend server <NUM> may communicate with a security token to receive credentials or other authentication tokens. For example, the security token may have a finger print scanner to receive an input from the customer <NUM> and a wireless transceiver to determine whether the security token is within a threshold distance of the security device <NUM> (e.g., using RSSI measurements, etc.). At block <NUM>, the backend server <NUM> generates a second signature using the signing function (f<NUM>). At block <NUM>, the backend server <NUM> generates a combined signature (e.g., a composite signature using the composite signature function (f<NUM>), or a splitkey signature using the splitkey combiner function (f<NUM>), etc.). At block <NUM>, the backend server <NUM> generates a finalized signature using the finalizing function (f<NUM>) based on the combined signature and the finalizing key <NUM> associated with the customer <NUM>. At block <NUM>, the backend server <NUM> sends the finalized signature to the frontend server <NUM>.

<FIG> is a flowchart of a method to generate a signature for a digital document which may be implemented by the system of <FIG> and <FIG>. In <FIG>, the backend server <NUM> does not store a private key for a customer <NUM>. At block <NUM>, the backend server <NUM> sends the signature request <NUM> to the security devices <NUM> associated with the corresponding certificates <NUM> included in the signature request <NUM>.

At block <NUM>, the first security device <NUM> authenticates the customer <NUM>. For example, the first security device <NUM> may authenticate the customer <NUM> in response to receiving a finger print and/or a set of credentials. At block <NUM>, the first security device <NUM> generates a first signature with its stored private key using the signing function (f<NUM>). At block <NUM>, the first security device <NUM> transmits the first signature to the backend server <NUM>.

At block <NUM>, the second security device <NUM> authenticates the customer <NUM>. At block <NUM>, the second security device <NUM> generates a second signature with its stored private key using the signing function (f<NUM>). At block <NUM>, the second security device <NUM> transmits the second signature to the backend server <NUM>.

At block <NUM>, the backend server <NUM> generates a combined signature (e.g., a composite signature using the composite signature function (f<NUM>), or a splitkey signature using the splitkey combiner function (f<NUM>), etc.). At block <NUM>, the backend server <NUM> generates a finalized signature using the finalizing function (f<NUM>) based on the combined signature and the finalizing key <NUM> associated with the customer <NUM>. At block <NUM>, the backend server <NUM> sends the finalized signature <NUM> to the frontend server <NUM>.

<FIG> is a flowchart of a method to reissue certificates <NUM>. The certificates may be reissued, for example, when one of the backend servers <NUM> becomes non-functional. A new backend server can be installed and new certificates can be issued based on the existing certificates. As described below, this process is automatic and does not, in some examples, require sending a specific request to the certificate authority <NUM>. If two different backend servers <NUM> are use, and one of them is non-functional, then this automatic certificate issuing procedure enables recovery of the system without any downtime. Initially, the certificate authority <NUM> receives the BESID <NUM> and the public key of the new backend server <NUM>.

At block <NUM>, the certificate authority <NUM> verifies the primary and secondary certificates 706a and 706b associated with the primary and secondary backend servers 702a and 702b. At block <NUM>, the certificate authority <NUM> extracts the CID <NUM>, the public key of the primary certificate 706a, and the public key of the secondary certificate 706b. At block <NUM>, the certificate authority <NUM> computes the public key to the customer's security device <NUM> using the public key of the primary certificate 706a and the public key of the secondary certificate 706b. At block <NUM>, the certificate authority <NUM> creates the new public key using the public key to the customer's security device <NUM> and the public key of the new backend server <NUM> (e.g., using the composite public key function (f<NUM>), etc.). At block <NUM>, the certificate authority <NUM> creates a new certificate <NUM> for the new backend server <NUM> based on the BESID <NUM> of the new backend server <NUM>, the new public key, and the CID <NUM> associated with the primary and secondary certificates 706a and 706b. At block <NUM>, the certificate authority <NUM> the certificate associated with the non-functioning backend server <NUM> with the new certificate.

In this application, the use of disjunctive is intended to include the conjunctive. The use of definite or indefinite articles is not intended to indicate cardinality. In particular, a reference to "the" object or "a" and "an" object is intended to denote also one of a possible plurality of such objects. Further, the conjunction "or" may be used to convey features that are simultaneously present instead of mutually exclusive alternatives. In other words, the conjunction "or" should be understood to include "and/or". As used here, the terms "module" and "unit" refer to hardware with circuitry to provide communication, control and/or monitoring capabilities, often in conjunction with sensors. "Modules" and "units" may also include firmware that executes on the circuitry. The term "remote" means being geographically removed from and communicatively coupled via an internal or external network, such as an intranet or the Internet). The terms "includes," "including," and "include" are inclusive and have the same scope as "comprises," "comprising," and "comprise" respectively.

Claim 1:
A system for generating a digital signature comprising:
a first backend server;
a second backend server;
a frontend server configured to:
receive a signature request from a remote application server, the signature request including a first total public key with a cryptographically embedded first server identifier and a second total public key with a cryptographically embedded second server identifier;
extract the cryptographically embedded first server identifier from the first total public key;
forward the signature request to first backend server that corresponds to the first server identifier;
in response to determining that the first backend server is unavailable, extract the cryptographically embedded second server identifier from the second total public key, and forward the signature request to the second backend server that corresponds to the second server identifier;
forward a second signature to the application server; and
wherein the first and second backend servers are each configured to:
forward the signature request to a plurality of remote security devices associated with the total public key;
receive a first signature from each of the plurality of remote security devices;
generate a combined signature based on the first signatures;
generate the second signature based on the combined signature and a finalizing key, the finalizing key being cryptographically generated based on the server identifier of the backend server; and
forward the second signature to the frontend server.