Multi-step digital signature method and system.

(74) Agent: HUANG, Stuart, T „F. et ÉL; Steptoe &. Johitóon, L.LP., 1330 Connecticut Avenue, NW, Washington, DC 20036 (US).

(30) Prtarity Data:

08 / 462,430 5 June 1995 (Ο5Λ5.95) US (60) Parent Appücation or Grant (63) Related by Cantinuation

US 08 / 462,430 (CIP)

Fíledon 5 June 1995 (05.06.95) (81) Deslgnated Statea; AL, AM, AT, AU, AZ, BB, BG, BR, BY, CA, CH, CN, CZ, DE, DK, EE, ES, Fl, GB, GE, HU, IS, JP, KE, KG, KP, KR, KZ, LK, LR, LS, LT, LU, LV, MD, MG, MK, MN, MW, MX, NO, NZ, FL, PT, RO, RU, SD, SE, SG, SI, SK, TJ, TM, TR, TT, UA, UG, US, UZ, VN, ARIPO patent (KE, LS, MW, SD, SZ, UG), Emanan patent (AM, AZ, BY, KG, KZ, MD , RU, 17, TM), Eurcpean patent (AT, BE, CH, DE, DK, ES, H, FR, GB, GR, E, IT, LU, MC, NL, PT, SE), OAPI patent (BF , BJ, CF, CG, a, CM, GA, GN, ML, MR, NE, SN, TD, TG).

(71) Applicant (for all designated Stares except US) t BANKERS

TRUST COMPANY [US / US]; 280 Parit Avenue, New York, NY 10017 (US).

(72) Inventor; and (75) Inveuton / AppUcants (for US onfy) t SUDIA, Frank, W. [US / US]; Apartment 48, 110 Bait 84th Stieet, New York, NY 10028 (US). FREUND, Peta, C. [US / US]; 8th floor, 139 Eut 79Λ Strret, New York, NY 10021 (US). HUANG, Stuart, T „F. [US / US ?, 2939 Van Nen Street, NW # 907, Washington, DC 20008 (US).

Publlshed international search repon

Befare the expiration af the time limit for amending the claünr and to be republished in the erees of the receipt of amendments.

(54) TWe: MULTI-STEP DIGITAL SIGNATURE METHOD AND SYSTEM

<img file="MX9709760A_D0001.tif" />

(57) Abstract!

A multi-etep signing lystem and method uses multiple signing devices (11, 13, 15, 17, 19) affix a single signature wttích can be verified using a single public verified: Ley. Each signing devicc posteases a share of the signature key and affixes a partial signature in rasponee to «uthorization from a phuality af nKhcddng agent (23, 25, 27, 29, 31). Go to aerial embodiment, afta to ftnt departed! signature has been affixcd, a second signing device expooentístea the finrt partial signature. In a pwallel embodiment, each aigning device affixes a partial signature, and the pluiality of partial signaturas ara multiplied together to form the final signature. Security of tira aystem is enhanced by distributing capabüity to afifix signaturas among a plurallty cf signing devices and by dútributing authority to affix a partial signatura among a plurallty of authorizing agenta.

DIGITAL SIGNATURE METHOD MULTI-STAGES AND BACKGROUND SYSTEM

Public key certificates are electronic documents signed by a trusted issuer and used to certify the binding of a username to a public key and other related data. Certificates provide assurance to the public that the public key identified in the certificate is owned by the user whose name appears on the certificate. The main standards that describe public key certificate systems include ITU-T X.509 from The Directory-Authentication Framework, The American Bankers Associations ANSI X9.30- Part 3: Get Certified Management for DSA (draft). Many

<td>realizations</td><td>they have a hierarchical structure in which</td>

<td>each issuer</td><td>trusted, referred to as the authority of</td>

<td>certification</td><td>(CA), certifies keys for entities that are</td>

subordinate to him. The CA affixes a digital signature to an electronic document in a verifiable way (one can prove that the

CA signed the document) and that it cannot be falsified (one can be assured to a high level of confidence that no one other than CA signed a document). For example, at the top of the CA hierarchy there may be relatively few root CAs, perhaps one per country which certifies subordinate CAs. Below the root CA in the hierarchy, the high-level CAs (perhaps the banks) certify the low-level CAs below them (example companies), which in turn sign individual user certificates.

A CP signature becomes more valuable as it creates a large hierarchy of users below it and uses its signing key to sign certificates for both high-value users and subordinate CPs. The CP signing key then also likely becomes the target of terrorists, criminals bent on economic gain, and foreign military and espionage services bent on economic espionage or the destabilization of the economy via war information. All these issues also apply with equal force to the keys used to sign electronic currency representations »

With this scope, the security need for a CA private signature key has been addressed to provide a certified signature unit (CSU), which is a secure, tamper-proof module that meets the standards set by the processing standard. FIPS PUB 140-1, Level 3 or 4 as published by The United States Department of Commerce, National Institute of Standards and Technology (NIST). Such CSU generates its public / private signature key pair internally, confines the private signature key securely and permanently within an area of ​​the device that cannot be read externally, and given only the corresponding public key, which will be used to verify their signatures. A CSU available from Bolt, Baranek, and Newrnan of Boston, ΜΑ (BBN) is configured to allow a collection version of your private signature keys to be created using a K-of-N threshold scheme, in which the private key is divided into N parts and located in small plastic data keys, each of which contains a memory chip. Data keys are a proprietary product of Datakey, Inc. of Burnsville, FIN. So if the CSU device is destroyed, a quorum of at least K data keys can rebuild the private key.

At least one major standard security body, the American Bankers Association Committee ANSI X9.F1 for Cryptographic Security in Banking Applications of All Kinds of Sales has recommended that the CSU should be designed to prohibit any export of private keys from the device in any way in order to prevent any possible theft and unauthorized use of the key. This approach would require an elaborate procedure for disaster recovery, involving the use of multiple key pairs simultaneously. Because a unique key would exist only in a single CSU at a single site, the loss of a CSU or site would force the CA to use another key pair in order to continue business. This would require the CA to securely publish and / or distribute several (at least 2 or 3) public keys, each identified by a different code number (example BT01, BT02, BT03), so that users could continue with the verification of the signatures that the CA published after the CSU (possibly containing the private key for BT01) had been destroyed. See part X9.30 3 regarding disaster recovery procedures.

BRIEF DESCRIPTION OF THE INVENTION

An object of the present invention is to provide a digital signature system (signature system) for certificates and other high value documents (including contracts, electronic representations of currency, negotiable documents, etc.) with improved security and flexibility.

A further object of the present invention is to provide a signature system in which a digital signature is verifiably related to a signature key and in which no signature device containing the signature key is required during the operation of document signature.

A further object of the present invention is to provide a signature system which allows loss or compromise of one or more signature devices while non-compromised signature services remain available.

A further object of the present invention is to provide a signature system in which multiple signature devices each create, modify or combine one or more partial signatures, and the result of operations by means of multiple signature devices produces a digital signature only.

A further object of the present invention is to provide a signature system in which multiple agents directly or indirectly authorized authorize each individual signature device to sign or modify a partial signature.

A further object of the present invention is to provide a robust and user friendly mechanism in which authorizing agents can temporarily delegate their authorization capacity.

The multi-stage signature system described here uses a public key cryptosystem scheme to sign a document so that a recipient of the document can verify the signature using a public verification key of the signer. The private signature key that corresponds to the public verification key is not allowed to exist fully, available in one place at any time during normal signing operations. Instead, a private signature key consists of operational parts which can be used to set or modify a partial signature, and a multi-part sequential operation produces a signature that can be verified using the public verification key. The full signature is not completed until all, or some quorum, of the signing devices have signed. Each of the signing devices instead requires authorization from all, or some quorum from its associated authorization agents before participating in the signing process.

If, during the initial generation of the operational parts, a full signing key is generated, the full signing key is destroyed after the parts are distributed. Because the risk of loss due to theft or compromise of any device is now greatly reduced, the information content of each of the signature devices can be duplicated now, (for example by remote collection or by connection replacement or wait "hot" for if any device fails, it can be replaced, (or reconstituted), and service can be quickly resumed. The consequence of subversion of any individual signing device is decreased, because the signing operation cannot be completed with a single device.

A multi-layer authorization management system is established, such that each of the signature devices has registered within it an individual number (or designated external smart cards), and the signature operation device only up to the registered individuals. . A quorum of authorization agents) is also changes in the system, such as additional authorization, deletion used by signature individuals participating in the authorization of a quorum of these individuals (calls required to use the registration of agents of authorization agents , alteration of the quorum requirements for any of the various actions that the signature devices may carry out, or the generation and additional distribution or substitution of key groups.

In this way, a signature can be applied in such a way that it can be verified using a public verification key, but without having a private signature key at a single site where it may be subject to compromise or catastrophe. Multiple sites must fail or be compromised before interruption of signature services or before an adversary acquires enough information to falsify signatures. Individual signing devices do not need to be as highly secure for a CSU that uses a single full key. A relatively inexpensive device that complies with FIPS 140-1 level 3 standards can be used (for example, a device that is violation resistant), thus avoiding the need to use a relatively expensive level 4 device (which takes active measures to destroy or safeguard internal information when violation is detected).

An authorization delegation mechanism allows an authorization agent to allow a delegate or delegate quorum to authorize their smart card to affix their signature for temporary periods of time.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described below with reference to the accompanying drawings in which:

Figure 1 illustrates a view of the basic architecture for the operational signature system according to the present invention;

Figure 2 shows a preferred architecture for the data center having a signature device;

Figure 3 illustrates a preferred architecture for a trusted device used by an authorization agent;

Figure 4 illustrates a process for temporary certification of uninitiated signing devices, during system boot and initialization;

Figure 5 illustrates a process for generating and distributing operational parts of a broad authority key of the system;

Figure 6 illustrates a multi-stage signing procedure for recertification of a signing device;

Figure 7 shows a total system architecture for the certification and registration of authorization agents;

Figure 8 illustrates a multistage signing procedure using authorization agents;

Figure 9 illustrates the flow of a document through various authorization agents and signing devices during the routine of multi-stage signing operations;

Figure 10 illustrates the evolution of signature on a document during the routine of multi-stage signature operations.

Figure 11 illustrates the flow of a document during a parallel mode of the multi-stage signing system.

Figure 12 illustrates the processing of one of the copies, and the combination of the three partial signatures in the 10 system authority signature.

<td colspan="2"></td><td>The</td><td>figure 13</td><td>illustrates</td><td>a</td><td colspan="2">command to delete r</td><td>a</td>

<td> -</td><td>agent</td><td colspan="2">authorization.</td><td></td><td></td><td></td><td></td><td></td>

<td></td><td></td><td>The</td><td>figure 14</td><td>illustrates</td><td>a</td><td colspan="2">command to add</td><td>a</td>

<td></td><td>agent</td><td colspan="2">authorization.</td><td></td><td></td><td></td><td></td><td></td>

<td> 15</td><td></td><td>The</td><td>figure 15</td><td>illustrates</td><td>a</td><td>sample request</td><td>with</td><td>a</td>

<td></td><td>command</td><td>for</td><td>add a</td><td colspan="2">maker.</td><td></td><td></td><td></td>

<td></td><td></td><td>The</td><td>figure 16</td><td>illustrates</td><td>a</td><td>sample request</td><td>with</td><td>a</td>

<td></td><td>command</td><td>for</td><td>delete a</td><td colspan="2">maker.</td><td></td><td></td><td></td>

<td></td><td></td><td>The</td><td>figure 17</td><td>illustrates</td><td>a</td><td>sample request</td><td>with</td><td>a</td>

<td> 20</td><td>command</td><td>for</td><td>add a</td><td colspan="2">model number</td><td></td><td></td><td></td>

<td></td><td></td><td>The</td><td>figure 18</td><td>illustrates</td><td>a</td><td>sample request</td><td>with</td><td>a</td>

<td></td><td>command</td><td>for</td><td>delete a</td><td>model.</td><td></td><td></td><td></td><td></td>

<td></td><td></td><td>The</td><td>figure 19</td><td>illustrates</td><td>a</td><td colspan="3">instruction shows that</td>

includes a command to add a signing device.

Figure 20 illustrates a message to remove a signing device.

-1010

Figure 21A illustrates a sample request for a sending device to copy the key (s) you publish. Figure 21B illustrates a sample message from a sending device for a receiving device.

Figure 22 illustrates a process for encrypting stored key parts. Figure 23 illustrates a process for generating and distributing encrypted key parts and decrypted key parts. Figure 24 illustrates an interlock ring architecture.

Figure 25 illustrates a process for issuing a replacement certificate to delegate signing authority.

DETAILED DESCRIPTION OF THE PREFERRED MODALITIES

The most direct explanation of the multi-step signature method begins with the discussion of several relevant mathematical processes. A- Multiplicative Scheme with Sequence Signature! Partial

First, a Kswa secret signing key of a public / private key pair belonging to a system-wide authority "is represented as number (nO") of parts (ai ") such that the KSWA signing key can be computed as a product of any threshold number (tO) of

-1111 parts, where tO is less than or equal to nO. The representation is made in such a way that it is difficult or impossible to retrieve the K $ wa signing key when it is owned by less than TO parts. This can be accomplished by, for example: 1) using a Shamir-type secret part scheme (A. Shamir, How to Share a Secret,

ACN Communications, Nov „1979, V.22,

n.ll), 2) using a secret parts scheme of the type

Blakley CG-R. Blakley,

Safeguard Cryptographic Keys,

Procedures of the

National Conference on Computing,

1979, American Federation of Societies of

Processing of

Info rrnation,

v.

48, 1979, pp. 242-268);

3) factoring the key; or 4) generating the key as a product of known factors. All that is necessary is that the private key be represented as:

where

K SHA

Kai * a2 * ato (mod

2N) sha is a signature key and ai is any combination of parts tO.

Second, a signature is formed using multiple devices with each device having to exponentiate a partial signature left by the previous device, using an ai part of a private key. When using a module

N^H arithmetic (where the arithmetic operation concludes by dividing the result by a modulus N and taking the remainder as the result of the modulus N), the following relationship between multiplication of exponents and sequential exponentiation is true:

-1212 (χιΐ a2) (mod N) - C (X * 2) a2) (mod N) - ((X * 2) al) (rnod N) otherwise stated, if a base value x is exponentiated by the product of two factors al and a2, the result is the same as if the base were exponentiated by a first factor al, and that result exponentiated by the second factor a2. in addition, the order of the exponentiation can be reversed, so that the result will be the same if the base is first exponentiated by the second factor a2, and that result exponentiated by the first factor al. This relationship can be generalized for exponentiation by means of three or more factors. Unless otherwise stated, all arithmetic operations must be considered modulo N.

In the multi-pass signing method, the parts of a signing key al, a2 ,. »« a «or are distributed to separate the devices. A first device fixes a partial signature to a document by redoing the document (the symbol '* H' * will be used to designate the result of the remade operation) and exponentiate the remade as:

first partial signature = (H) * i (mod N)

A second device advances the signature by exponentiating the first partial signature using a second part a2 as: second partial fix ~ ((H) * i) * 2 (mod N)

The process is repeated until all devices have exponentially redone it using each of the ⁿt0 separate parts, to produce a final signature that can be verified using the public K “-SUA.

B. Additive Scheme with Asynchronous Partial Signature

An alternative way to accomplish a similar result involves dividing a signing authority's private key into parts that can be added (module N) to produce the private key.

K - ai +32 * · .. at (mod N)

This instead allows the multi-stage signature to be developed in an asynchronous way by separately generating intermediate values ​​(H) »i by exponentiating the remade for each of the parts, and then multiplying the result of the intermediate values, such as follow:

S ~ H * 1 * ... H »3 (mod n)

This can have considerable operational advantages over the sequential method described above, because it is not necessary to route the message sequentially from one site to another. Instead, a central administrator can, in a very direct way, simply send the same message (or remake it) directly to each site for partial signature, and then combine the resulting partial signature to produce the desired final official signature. This final merge operation does not require any special security, because this does not add any information not already contained in the partial signatures, thus allowing the administrator to work on his desktop. In this way, partial signatures can conceivably be left for later combinations by the receiver who verifies the transaction. This loads the receiver with an additional processing workload, but does not break the security of the official signature.

Exponentiation-based signature schemes that can be modified to allow multi-stage signing include: R. Rivest, A. Shamir and L. Adleman (¹¹RSA), A method for obtaining digital signatures and public key cryptosystems, ACM Communications, v.21, n.2, pp. 120126, February 1978); D. Kravitz, Digital Signature Algorithm (OSA), US Patent No. 5,231,668; Desmet, Y. Frankel, Threshold Cryptosystems, CRYPTO 89, pp. 307-15, 1989; Taher El-Gamal, Public Key Cryptosystems and Signature Schemes Based on Discrete Logarithms (El-Gama1 Signature Algorithm), IEEE Tra nctions on Information Theory, Vol. IT-31, No. 4, July 1985; S. Micali, A Secure and Efficient Digital Signature System, MIT / LCS / TM-501, Massachusetts Institute of Technology, Laboratory for Computer Science, March 1994; A. Menezes et al., Elliptic Curve Public Cryptokey Systems, 1993.

REVIEW OF THE SYSTEM

Figure 1 illustrates a general idea of ​​an architecture for a signature system according to the present invention. The architecture includes multiple signature devices, 11, 13, 15, 17, 19 interconnected by means of a wide area network (UAN) or a local area network

-1515

CLAN)

twenty-one. The individual signature devices 11, .13, 15,

17, 19 are geographically dispersed as widely as UAN / LAN allow, such as on separate continents, cities in at least separate areas, or separate parts of an area

<td>metropolitan</td><td>only.</td><td></td><td></td><td></td><td></td>

<td>In</td><td>figure 1,</td><td colspan="2">the device</td><td>fi rrna</td><td>2 has been</td>

<td>illustrated in</td><td>great detail</td><td>as a</td><td>example. TO</td><td>every</td><td>device</td>

<td>signature</td><td colspan="2">a code is assigned</td><td colspan="2">identification</td><td>permanent</td>

<td colspan="2">(example, serial number</td><td>unique) and</td><td>a name</td><td colspan="2">logical (example</td>

<td>Device</td><td>Signature X</td><td>) together</td><td colspan="2">with a couple of</td><td>keys of</td>

public / private device 12a, 12b, to encrypt / decrypt communications and a public / private device key pair 14a,

In addition, each public encryption

14b, to verify, make signatures.

the devices receives the keys from and the public verification keys for all other signing devices.

Hereinafter, the encryption, decryption keys are designated as KE, while KS designates the signing / verification keys. A super-written (+) indicates a public key, and a super-written minus indicates a private key. Super-writes indicate the owners of the private keys of the respective key pairs.

Authorization agent groups 23, 25, 27, 29, are also interconnected through network 1 to each other and to signature devices 11, 13, 15, 17, 19. Each authorization agent is a person acting through from a computer

-16.16 reliable (such as a rape resistant smart card, or other reliable device) as will be discussed further below. Authorization agents may be scattered over the entire length of LAN / WAN 21, but 5 it is assumed that groups of authorization agents will be located in proximity to the corresponding signature devices most of the time for the convenience of handling the organization of the signature system.

In Figure 1, authorization agent 2a (item

25) has been illustrated by means of an example and using the same notation for the keys as discussed above in relation to the keys held by the signature device 2. Each of the trusted authorization agent devices has been assigned a unique name, along with a public / private device key pair 20a, 20b for encryption / decryption communications, and a separate public / private device key pair 22a 22b for signature verification / realization »If an RSA public key cryptosystem is employed, then one such pair could be used for both signatures and encryption at the same time. Authorization agents also receive public encryption keys 24 and public verification keys 26 from all other authorization agents.

The signing devices also receive public encryption keys 24 and public verification keys 26 for all authorization agents.

-1717

Similarly, trusted authorization agent devices receive public encryption keys 28 and public verification keys 30 for all signing devices.

For an easy explanation of the multi-stage signing process that follows it will be assumed that all communications over the network are encrypted using a standard public key cryptosystem ("PKC") scheme, such as RSA-key-transport. It will also be assumed that the commands sent from one entity in the network to another are signed by the sender using a standard scheme (PKC), such as the RCA signature with acceptance of the MD5 message. In future designs, device encryption / decryption keys, and device signing / verification keys may be omitted, but should be understood as present on all devices as discussed above.

Figure 2 shows a preferred architecture for a secure data computing center configuration 48, where each of the signature devices of Figure 1 will preferably be found. In addition to a signing device 39, each of the data center configurations 48 additionally contains a separate message server 47. The signing device 39 is dedicated to signing operations and is located in a physically secure location, such as a vault. There is no direct connection between the signing device and the external computer network. How I know

-1818 will fully discuss later, signing device 39 will be provided with a key part for multi-stage signing 36, its own device signing key 37, Table 3Θ identifying authorization agents, and a certificate for its public verification key 40, a public key chosen to match its key part 36, where the certificate is signed by the entire KSswa via a multi-stage method).

During multi-stage signing processes, a signing device 39 will receive the requests through a message server 47. The message server develops routine communication processes, such as stripping routine private envelopes which have been set by intermediaries (server 47 does not have the private decryption key of the signing device), and queuing entries in the event that they are presented faster than they can be processed. The message server presents messages to the signing device to be signed, receives the signed (or partially signed) result, and (returns the partially signed result to the requestor, or (b) routes the result to the next device in the protocol. In order to receive and participate in ordinary communication protocols, the message server also has a public / private key pair 32, 33 to sign its own messages, and another 34, 35 for encryption, in order to enable it to receive and open encrypted messages leaving

-1919 This way released the signing device from its routine load without significantly affecting the security of the secure signing process.

Message server 47 may be a comparatively less secure computer in a lesser security environment such as an ordinary secure data center. Message server 47 connects to LAN / WAN 21 and provides a document queue and communications services to signing device 39. Message server 47 includes a system log 49 that maintains an audible track of messages and documents sent to and from the signature device. As shown, a signing device and its associated message server are preferably divided into two physically separate computers. Although less preferably, the signing device 39 and the message server 47 could be structured as separate tasks or a single computer in a highly secure environment.

The message server can also provide a layer of protection, known as a wall of fire, that separately validates all transaction entries before they are passed to signature devices. On the other hand, an online signature device accessible to the public network would be open to unlimited attempts, as well as network saturation attacks the purpose by delegating the service.

Attacks from denial can disorganize the certified broadcast daily, but it would not paralyze users who

-2020 trust previously signed documents (who is the vast majority of the prospective user population). However, cheating attempts will always pose a threat, especially if those who want to cheat identify some hidden flow »The message server can verify all messages against a list of authorized devices (signing devices and authorization agents), too as more complex strategies to identify possible attacks, deny access after a number of 10 failed attempts, and take sophisticated actions to trace the source of any false data entry. This will allow the signature device's signature structure to remain simpler and easier to validate, while also allowing system operators to modify their detection and 15 evasion strategies according to the current state of network security. .

Figure 3 illustrates a workstation for authorization agents. Human operators who act as authorization agents can work in relatively insecure areas 20 on desktops or terminals 51 typically found in a business office. Each such computer or terminal will have a card reader 53, and each operator will have a secure smart card 55. Each smart card 55 securely contains a private decryption key 25 and a private signature key which is unique to the smart card. The human operator

-2121 can use the card to issue signing instructions. Such a reliable device can be implemented using a level -3 FIPS device, such as a Power card from National Semiconductor Corp. of Santa Clara, CA, which can be easily reprogrammed at the signature structure level to allow for the progressive return of new methods and procedures to ensure signature and authorization without the need to replace physical devices. Each of the trusted authorization agent devices must have at least one private signing key. Preferably, the private signature key is installed on the device at the manufacturer's time, and the corresponding public verification key is certified by the manufacturer. Certification here means that the manufacturer has included, with the trusted device, an electronic message containing the serial number of the device and the public key, along with its model number and other evidence of its reliable characteristics, and that message, certified, has been signed by the manufacturer.

Human operators use their desktop computers to read and generate messages. When the human operator wants to sign a message, the desktop computer sends the message to the trusted device, which adds a digital signature using the device's private signature key. In the preferred embodiment, this signature is the signature of a second for signature keys that have been specifically generated and

-2222 certified as belonging to the specified user. In this way, the system can continue to use the device signature to verify the device's level of reliability on a given transaction, while using the user's signature to certify the user's identity and consent to the transaction. This allows the user key to be remotely generated and revoked, possibly depending on various administrative facts regarding the identity of the user or authority, while also allowing the device to be reused, or to accept various other pairs of user keys. which the user may wish to use for other unrelated purposes.

Figure 3 also illustrates a preferred architecture for a possible trusted device to be used by an authorization agent. This comprises a single micro chip inserted into a card in a configuration known as a smart card. The micro chip device has an input / output circuit 42 for power and communications, and a micro controller 44 for executing the programs of the signature structure. Memory 52 contains systems of signature structure 43 for operating the micro chip equipment (similar to a single operating system). Memory 52 also includes areas for storing device keys installed by the manufacturer 45, user keys 47 received as part of the protocol described here_t and application structure 49 for executing the described network protocols

-2323 here. Unused memory is provided as a workspace 54 for temporary storage as required. The micro chip may also include an optional crypto unit 46, which is a special arithmetic purpose accelerator unit that has equipment to perform accelerated exponentiation and other encryption / decryption arithmetic operations and signature processes. The micro chip also includes an optional 48 reliable clock (assuming the presence of a suitable power battery) initialized by the manufacturer and useful for time-stamped signatures. It also includes an optional random number generator 50 for use with encryption / decryption processes. The smart card may also include an optional noise source (not shown) such as a diode, which may either be internal or external to the micro chip, for use in generating random numbers.

The signature device previously shown in Figure 2 can also be a smart card that has the same general design as the trusted authorization agent devices.

Devices on the network will be initialized in a series of stages as follows:

1) Distribution of the encryption key;

2) Temporary certification of the signature device;

3) Temporary certification of the authorization agent;

-2424

4) Distribution of the public key;

5) Recertification of the signing key; and

6) Certification of the authorization agent.

preferred discussion

<td>Every</td><td>one</td><td>will be</td><td>argued</td><td>by</td><td>shifts. Following the</td>

<td>of</td><td>the</td><td colspan="2">initialization</td><td>of the s</td><td>system, methods</td>

<td>of</td><td>use</td><td>for</td><td colspan="2">the certificates</td><td>highly signature</td>

Insurance and other documents will be explained, as well as variations and improvements.

DISTRIBUTION OF THE ENCRYPTION KEY

Each signing device, and each authorization agent smart card is assumed as one device

<td>reliable in</td><td>reason this is a device resistant to</td>

<td>rape that</td><td>works only according to the characteristics!</td>

<td>established,</td><td>and whose manufacturer has provided it with a for</td>

device signing keys and a key pair of

<td>encryption</td><td>of the device stored in a memory</td>

protected. At a minimum, the manufacturer of such a device will certify that the device does not disclose your private or user keys without costly breach efforts. Each device also has an electronic certificate, signed by the manufacturer, containing: 1) the serial number of the device; 2) the verification key of the public signature before the device; 3) the public encryption key of the device. Manufacturing can

-2525 install two separate certificates, one for the signature verification key and one for the encryption key. Signature devices encrypt their communications using a public / private cryptographic scheme. In the alternative, the method can take place without manufacturer's certificates by providing physical protection to all devices, such as by conducting initialization tasks in a secure vault where a small computer (notebook) is used in conjunction with a reliable signature.

Each of the trusted devices is assumed to start with some basic functionality, such as software that gives you the ability to start and receive messages over the network or email system, allowing you to communicate with other trusted devices . It is assumed that at least one signature device, designated as the primary device, ”is capable of receiving information about the initial state of the system from human operators responsible for system initialization.

The next step in preparing the system for devices is to exchange device keys. The key distribution is carried out as follows.

1) A signature device, designated as the primary one, receives from human operators the identities of other signature devices in the system. The primary device sends its public encryption key and the public signature verification key to the other

-2626 signature. Optionally, the primary device can also send messages to validate the signature structure it is operating under, for example, by redoing its signature structure, signing the redone value using its device signing key, and sending the signed redone value to others. devices.

2) After other signing devices receive the public encryption key from the main device, each of the other devices sends their respective verification key of the respective public signature and the public encryption key certificates return to the main device. If the primary device sends a recomposition of its signature structure, each of the other signature devices remakes its own signature structure and compares the two. The two remakes must fit together, otherwise the respective signing device stops participation in the protocol and notifies its operators. This comparison of the redone values ​​ensures that all signature devices use an identical signature structure, which acts as a check that the primary device is not an impostor. Each signature device optionally returns a recomposition of its respective signature structure to the main device.

3) The primary device compares the composites of the other respective device signature structures against its own composite, which checks that none of the other devices is an impostor.

-2727

All signing devices have now received public encryption and signature verification keys for the other devices. It will be understood that future messages will be signed by means of the private signature key of the sender and verified by the recipient using the public verification key of the sender. It will be understood that all communications will be encrypted using a public encryption key of the receiver and decrypted using the private decryption key of the recipient.

These additional signature keys are not used for multi-stage signing (which will be discussed later), but are instead used to encrypt and sign routine communications between entities on the network as proof of the device's individual identity. Such proofs of identity and group membership are of critical importance when generating and distributing the master key fragments for use in the current multistage protocol.

TEMPORARY CERTIFICATION OF THE SIGNATURE DEVICE

Figure 4 illustrates the temporary certification of uninitiated signing devices. During this process, the public key certificates of the signing devices (which were not signed or signed by the device manufacturer, will be replaced by the certificates

-2828 signed by a temporary administrator (the administrator) 61. The administrator is preferably a human operator responsible for system initialization and acts through the administrator's personal smart card. This temporary certification establishes a level of increased security between signature devices (as belonging to the target group) to be used while they generate the signing keys for multi-stage signatures. During current use, it is anticipated that the temporary administrator will be operating with multiple human witnesses to ensure correct procedures, and that temporary certification is effectively only for the minimum time (few minutes or hours, maximum) necessary to develop the complete master key generation protocol.

Temporary certification is carried out as follows:

1) Administrator 61 generates a private signature key 63 and a corresponding public verification key 65.

2) The temporary administrator 61 communicates its public signature verification key 65 to each of the signature devices 11, 13, 15, 17, 19.

3) Each of the signature devices 11, 13, 15,

17, 19 generates a private signing key 67, 69, 71, 73, 75, and a public verification key (not shown), and sends a request for signing key certification to administrator 61. The request for signing key certification signature is a

-2929 electronic message containing the name of the signing device (example a device serial number and / or a logical name, such as (SD1¹*), the verification key of the public signature newly generated by the device, and other administrative information as desired.

4) The administrator signs each of the certification requests using the administrator's private signature key.

5) The administrator returns the signed signing key certificates 66, 70, 72, 74, 76 to the respective signing devices 11, 13, 15, 17, 19. The signed certificates 68, 70, 72, 74, 76 they are illustrated as symbols for the signing keys (KS +) with their appropriate indexes and, attached to the bottom, the administrator's signature ΑϋΙΊΤΝ). Such certificates will, of course, include information about the identity of the device and the type (not shown).

6) The signing devices exchange their new temporary public signature verification key certificates with each other.

Each of the signing devices now has: a) the administrator's public verification key; b) your own temporary private signature key; 3) its own temporary certificate, signed by the administrator and bearing the verification key of the temporary public signature of the signing device; and 4) the verification certificates of the temporary signature of the other devices of

-3030 signature. Each of the signing devices can use the administrator verification key to verify the administrator's signature on temporary certificates received from other signing devices.

Each of the signing devices can now move to a more tightly controlled phase of the signing protocol that has been certified by a temporary administrator. For ease of explanation, it will be assumed that communications on the network involve multi-signature operations from this point until the end of device recertification is signed using a signature key that has been certified, verify the signature of the sender, if a message is not properly signed, the message will be rejected and the protocol will fail to continue unless a conformance message is supplied. It is further contemplated that some form of threat analysis or threat response may be undertaken when an improperly signed or unsigned message is received during multi-stage initialization and signature operations.

TEMPORARY CERTIFICATION OF THE AUTHORIZATION AGENT

Figure 4 illustrates the temporary certification of authorization agents. As discussed more fully below, a signature device fixes a partial signature only in response to authorization from a quorum of security agents.

-3131 authorization. Signature devices that operate under the authorization of the temporary administrator also require a quorum of authorization agents. Temporary certification and authorization agents ensure that only a designated human agent can secure signature devices during the initiation of the process.

The procedure for temporary authorization agents is similar to the previous procedure for temporary certification signing devices, and is performed as follows:

1) Administrator 61 communicates its public signature verification key 65 to each of the authorization agents 23, 25, 27, 29, 31.

2) Each authorization agent generates a private signature key certification request to administrator 61. The signature key certification request contains at least the following information: a) name of the authorization agent (human distinguishable name); b) identification code for the agent's trusted device (example, smart card serial number and model number); c) signature verification key for the human agent; and d) signature verification key for the agent's trusted device (which serves to ensure that the trusted device is of known type).

3) The administrator signs each of the certification requests using the private signature key of the

-3232 administrator.

4) The administrator returns the signed signing key certificates to the respective authorization agents.

DISTRIBUTION OF THE KEY PARTS

Figure 5 illustrates the generation and distribution of the operational parts of the system's widely authorized official signature key (SUR). A signing device, referred to herein as a Signing Device 1 (item 11), is designated as the primary device. Human operators provide this primary signing device with at least the following information:

a) the threshold parameters to split a key into parts, example the total number of parts to be generated and the minimum number necessary to set the SWA signature.

b) The key identification number and / or the logical name to be assigned to the public / private key pair, example key serial number KS-01234, or logical name * 'BT01.

c) The identification numbers of the parts of the key and / or the logical names to be assigned to the respective parts, example; SUIA-SHR-56789,¹¹ or BTOla.

d) The device certificates of the authorization agents who will initially be allowed to authorize that particular signature for each of the

-3333 devices.

Human operators can additionally provide a number that limits the total number of chunks that can reside on a single signing device, which can be used when the signing device has multiple master keys as discussed further below.

The next step is to generate the parts for the signing key, called the 1st broad authorization system key¹¹ (SUA), which will be used to administer the system. The public SWA public signature key are generated and distributed as follows.

1) Each signature device 11, 13, 15, 17, 19 encrypts a random seed information string to the main signature device 11.

2) Primary device 11 combines seed information and uses it to generate public authority wide authority signature verification keys (KSswa⁺) 91, which will finally be used to verify the official signatures.

3) The main device 11 generates operational parts 93, 95, 97, 99, 101 of the private signature key SWA. This can be accomplished by first generating a complete private / public key pair using key generation methods known in the prior art, and then splitting the private signature keys 92 into parts using

-3434 one of several well-known private signature key partitioning methods. Generating parts carries with it a requirement for a minimum number of separate parts nO that are sufficient to complete a widely authoritative system signature.

4) The primary device 11 does not transmit a SUR 91 public verification key and a private signature key part 95, 97, 99, 101 to each of the other signature devices, as long as they retain a copy of the verification key. public SUA 91 and a part of the private signature key SUA 93 for themselves. Each of the SUA private signature key parts is transmitted with the following additional information:

a) type code that identifies the key as a signature key part (also indicating the length of the part);

b) a unique identification code for the SUA public verification key;

c) a unique identification code for each of the respective SUR private signature key parts;

d) the total number of SUA private signature key parts distributed;

e) the minimum number of SUA private signature key parts required to complete the SUR signature;

f) the identities of the signing devices that the other parts of the private signature key SUA receive; and

g) Agents' authorization certificates to

-3535 who will initially be allowed to authorize the use of each of the parts of the SUR private signature key on the target signature device.

The main device 11 will encrypt each part of the key of the private signature SUR using a certified public encryption key of the respective signature device for which it is made.

5) The main device 11 removes the SUA public verification key for human operators and deletes the following information:

a) SVJR full private signing key (if at any time during the SUA full private signing key generation process was stored); and

b) all parts of the SWA private signature key (except for that part that it retains for its own use).

6) Each of the receiving signature devices installs its share of SUR private signature key in a tamper-proof memory area, along with the certificates of the initially authorized humans for that device.

It is preferred that the SUR private signing key exist at most only on the primary signing device 11, and then only for the minimum time necessary to generate and distribute the parts. In this way, the SWA full private signature key simply does not exist for operational use, and is likely to be attacked only for a short period of time.

-3636 during the generation process.

At this stage, each of the devices has additionally received securely: a) a copy of the signature verification key p SUA; and b) a part of the SUA private signature key.

For the purpose of illustrating the following discussion with an example, it will be assumed (for the sake of simplicity) that the minimum number of parts nO necessary to fix the SUA signature is two out of five parts. It will be understood that a larger number can be chosen, more likely at least 3, which will increase security, but will also increase the number of steps in the signing process.

RECERTIFICATION OF THE SIGNATURE DEVICE

During the initial steps of the initialization protocol, a signature verification keys of the temporary administrator certificate device 61 under the authority of the temporary administrator 61, and the certificates of the signing device were signed by the temporary administrator signing key. During recertification, each of the signing devices will circulate a new certificate request for its own public key among the other signing devices to be certified under the system wide authority key using multi-stage signing.

Figure 6 illustrates the steps for recertification.

-3737 of the signing device 1. The other signing devices will recertify themselves by repeating the process for each of the devices. The process for signing device 1 is done as follows:

1) Signing device 1 generates an unsigned certificate 103 and transmits that certificate to signing device 2. The certificate includes at least: a) the identity of the signing device (example serial number and / or logical name of the device; and b) a public signature verification key for the device signing key. The key that is temporarily recertified is the same public key that was originally the device at the beginning of the protocol, and first certified by the administrator. This key will now become certified by the administrator. The key will become the permanent indication of the membership device in the family of signature devices that handle the parts of this particular SUA key. (The device signing key and its associated manufacturer certificate remain unchanged during this process, and are permanently retained as proof of the device's origin and underlying characteristics.)

2) Signing device 2 sets a SUA partial signature using its SUA signature key part 93. The partial signature is formed in two steps. First, signature device 2 applies a redo function (such as MD5 or SHA) that generates a stream of reduced length that is

-3838 verifiably related to unremade certificate. This string is expressed as binary digits that can be manipulated as a numeric value (large integer). Second, signature device 2 forms a partial signature by exponentiating the redo string with its SUR signature key portion. That is, the signature device 2 calculates the numerical value, which becomes a partial signature, according to the formula:

--SD2 = (HASH (CERT)) KEY PART 21 module N (Note that in both texts and drawings, the bit string that constitutes the signature block is typically indicated by locating a long hyphen in front of the label that identifies the signing.

The resulting block is typically added to the bottom of the data block that was signed, or the context is otherwise obvious.)

3) Signing device 2 sends the partially signed certificate 105 to signing device 3.

4) Signature device 3 completes the system's wide authority signature by exponentiating the partial signature already applied --SD2. That is, the signature device 3 calculates a numerical value according to the formula:

- SD3 = E - SD2K KEY PART 3] module N = UHASH (CERT) exp KEY PART 2) exp

KEY PART 3) = - ~ SUA

The partial signature set by signature device 2 may be allowed to remain attached to the document as a

-3939 audible track. Note that only partial 2 signatures are required in this simplified example.

5) Signing device 3 returns signed certificate 107 to signing device 1, which then distributes copies of the certificate to other signing devices, thereby allowing them to verify their future signatures.

In this example, signing devices 2 and 3 set signatures in that order. Any combination of the signature devices can be signed in any order (as long as a number exceeds the minimum number tO), producing the same signature.

Recertification is important, because future operations developed by the complete system of signature devices will preferably be performed only in response to the request of the devices (example of approvers, as described above) that have

<td>been certified</td><td>as a SWA firm. Signature devices in</td>

<td>if they can</td><td>make requests to other devices</td>

<td>firm. Through</td><td>of this procedure, the</td>

Minimum signatures become the first devices certified by means of Broad System Authority (SWA)

<td>like an everything,</td><td>using</td><td>the</td><td>process</td><td>of</td><td>firm</td><td>multi-stage</td>

<td>defined here.</td><td></td><td></td><td></td><td></td><td></td><td></td>

<td>In</td><td colspan="2">a modality</td><td colspan="2">alternative</td><td>of the</td><td>process of</td>

<td>recertification</td><td>previous,</td><td>the</td><td>group</td><td>of</td><td>the</td><td>devices</td>

-4040 targets could supply their recertification requests (unsigned certificates) prior to generating the initial key via the primary device. The primary device would sign these certificates while creating a SUR private signing key before breaking it into fragments and erasing the entire key. There seems to be no greater advantage in doing this, as the main function of the resulting system is to sign such certificates in a still highly controlled and efficient manner.

AUTHORIZING AGENT RECERTIFICATION

Figures 7 and 8 illustrate the steps for recertification and registration authorization agents, Figure 7 shows the architecture of the entire system, while Figure 0 illustrates the processing sequence for the certification request. The signature devices will set the official signature of the system's wide authority to authorize the agent's certificates, thus certifying a public signature verification key for each of the authorization agents.

In the registration process, each of the signature devices will update an internally stored table of the particular authorization agents who will be in charge of instructing the signature devices to apply their partial signature. During routine operation, a signature device will set its partial signature only if

-4141 the request is signed by a minimum number of temporarily certified or SUñ-certified authorizing agents (or if a minimum number of individually signed messages are received) as discussed below. An example of the process to certify an authorization agent 3a (AA3a) and AA3a registration with signature device 3 is performed as follows.

For illustration purposes, it will be assumed that each signature device 3 and 1 (Figure 7, items 15 and 11) are 2 of the five signature devices selected to set the SUR signature.

1) The authorization agent 3a 109 supplies a recertification request for it (Figure 8, item 121) for the Signature Device 3 through the LAN / WAN 21. (Alternatively, the authorization and / or registration can be restricted to direct entry to the signing device through a limited access communication channel, for example direct connection to a personal computer remains alone). The certification request includes at least the following information: a) the name of the authorization agent (human distinguishable name); b) identification code for the trusted agent device (example smart card serial number and model number); c) a signature verification key for the human agent (as initially stated by the temporary administrator); and d) a signature fingering key for the trusted agent device, which serves as security of your device is

-4242 known type. Such assurances are particularly critical when all or substantially all operations are performed at widely separated sites, such that system operators cannot verify anything by visual inspection.

2) The SUA partial signature device (-SD3) to the partially signed certified certificate 123

fifteen fix a signature

121, and transmits it to other signed devices.

3) The Authorization Agent authorizes it that the partial certificate 123 can now be sent to the signing device 1 11.

4) Signing Device 1 completes the signing process using its 93 part of the SUA signing key.

5) Signature Device 1 returns the fully signed certificate 127 to Authorization Agent 3a.

6) Signature Device 1 retains a copy of the signed certificate 127, enters AA3a in a registry of authorization agents (not shown), and returns the signed certificate 127 to authorization agent 3a.

The process is repeated for all authorization agents who must be registered with Signature Device 3, leaving each authorization agent with the signed certificate and leaving Signature Device 3 with a record of all certificates. The processes are repeated for all agents

-4343 authorization of the other signature devices 11, 13, 17,

19.

MULTI-STAGE SIGNATURE

At this stage, the signing devices have been initialized with parts of the SUA private signing keys. The signature devices have been recertified themselves, and the authorization agents have been recertified and registered with their respective signature devices. The System ID is now ready to enter routine service for both the administration system and the official certification functions. In the following discussion, the multi-step signature will be described for the system wide authority key, which will typically be authorized by the administration systems. As will be discussed below, additional master keys will also be generated and used by multi-stage signatures within the same device families, in the same way as for the system wide authority key, except that the content of the 20 messages to be signed by such master keys cannot be administrative in nature.

Figures 9 and 10 illustrate a multi-stage signature using the system's wide authority key. Figure 9 illustrates the flow of a document (DOC) through various authorization agents and signing devices, while Figures 10 illustrate the evolution of the signatures in the document.

-44 This example assumes that authorization agents la and Ib authorize device 1 to set a partial signature, and authorization agents 2a and 2b authorize signature device 2 to complete the SUA signature. For simplicity, we 5 assume that either authorization agent is required to activate each of the signing devices.

The sequence occurs as follows:

1) The Authorization Agent receives a request for a signature through the UAN / LAN. The request is an electronic message 131 that has a header 133 and the document to be signed 135. The header will contain the command code that defines the message as the signature request.

2) The Authorization Agent (Figure 9, item 132) strips the header and develops a check procedure number to determine if the document should be signed. The specific checking procedure, which may include the judgment of the human operator AAla and which may vary depending on the underlying purpose of the document, is not related to the multi-stage signing process itself.

When the fact that the document must be signed is satisfied, the Authorization Agent signs the document using the people's secret signature key (which was recertified under the SUA signature). As shown in Figure 10, the Agent's Authorization Signature (--AAla) is determined by the shredding of the document and the exponentiation of the shredding of the document and the

-4545 shredding exponentiation using the secret signature key

Sharpen. The Sharpen then sets a new heading and sends the

<td></td><td>certificate</td><td>signed 137 at</td><td>Authorization Agent</td><td>Ib (other</td>

<td></td><td>agent for</td><td>the same device</td><td>signature signature that the</td><td>Agent of</td>

<td> 5</td><td>Authorization</td><td>the) .</td><td></td><td></td>

<td></td><td> 3)</td><td colspan="2">Authorization Agent 1b (Figure 9,</td><td>item 138)</td>

<td></td><td>cut the</td><td>heading and</td><td>conducts a</td><td>number of</td>

Procedural checks (not related to the multi-stage signature) to determine if the document should be signed.

ID When it is satisfied that the certificate must be signed, the

Ib Authorization Agent also signs the document. As shown in Figure 10, the signature of the AAlb (~~ AAlb) is .15 determined concatenated by the exponentiation of the

AAlb. The signature of the

1) shredding of the document and signature combination of the AAlb;

shredded using the signing key

AAlb is left on the document as

b) from the audit trail. The AAlb then sets a new heading and sends the double-signed document 139 to signature device 1 (Figure 9, item 11).

4) Signature device 1 receives the double-signed document 139, cuts the heading, and verifies that the document bears the necessary number of signatures from its registered authorization agents (in this example, 2). If so, the signature device 1 removes the signatures of the authorized agents and sets a partial SUfi signature. As shown in Figure 10, the partial SWA signature C - SD1) is determined by the

-4646 shredding the base document (without the authorization agent signatures) and exponentiation of the shredding using the SUA signing key portion of the signing device 1, 93. The signing device 1 then sets a new heading, and sends the partially signed document 141 to an Authorization Agent for another signature device, here Authorization Agent 2a of signature device 2.

5) Authorization agent 2a (Figure 9, item 143) cuts the heading and performs a number of procedural checks (not related to multi-stage signing) to determine if the document should be signed. When it is satisfied that the certificate must be signed, Authorization Agent 2a signs the document. As shown in Figure 10, the signature of AA2a (--AA2a) is determined by: 1) shredded from the concatenated combination of the certificate and the partial SWA signature (--SD1); and b) exponentiation of the crumble using the AA2a recertified signature key. The partial SUA signature of SSD1 is left on the document. AA2a then sets a new header and sends signed certificate 145 to Authorization Agent 2b (Figure 9, item 147).

6) Authorization agent 2b (Figure 9, item 147) cuts the heading and performs number of procedural checks (not related to multi-stage signing) to determine if the document should be signed. When it is satisfied that the document must be signed, the

-4747

Authorization Agent 2b signs the document. As shown in Figure 10, the signature of the AA2b (--AA2b) is determined by: .1) shredded from the concatenated combination of the certificate, the partial SUR signature, and the signature of the AA2a; and b) shredding exponentiation using the AA2b recertified signature key. The partial SWA signature and the AA2a signature are left on the document. AA2b then sets a new header and sends signed certificate 149 to signing device 2 (Figure 9, item 13).

7) Signature Device 2 receives signed document 149, removes the heading, and verifies that the certificate carries the required number of signatures from its registered authorization agents (in this example, two). If so, Signature Device 2 removes the signatures of its authorized agents and modifies the partial SUA signature to complete the SWA signature. As shown in Figure 10, the completed SUA signature (--SVJA) is determined by the exponentiation of the partial signature set by signing device 1 (--SD1) using the SWA 95 signing key portion of the Signature 2. Signature Device 2 then sets a new header, and sends the partially signed certificate 151 to the AAla (the originating Authorization Agent).

In the example described above, two signature devices were required to set the system wide authority signature, and each signature device required authorization from two Authorization Agents. The number

-4848 total signature devices required to complete signature on the system can be adjusted at the time that key portions are generated, and the limit numbers of authorization agents for each signature device may also vary. For example, three signature devices may be required for 5 to complete the system wide authority signature, and the number of authorization people required to authorize a signature device may vary for each signature device, depending on the level of human review. desired for security purposes.

After having established a multi-stage signing process as discussed above, certain central administrative actions may be conditioned on the establishment of a quorum of other signature devices as authorized by the presence of the system's broad authority key. Some of these administrative actions are discussed below.

To carry out such actions, the company within each violation signature device will be programmed to respond to decisions, resistant only to the signed commands:

one. In the case of partial signature requirements, by an appropriate quorum of authorization agents; and

2. In the case of a system of administrative changes, by the broad authority of the system itself.

This is, in the preferred embodiment, no change

-4949 may be listed on approvers or related requirements on any signature devices by the consent of a quorum of approvers on the quorum of signature devices. In some cases, it may be unduly difficult to obtain full system consent for certain minor changes, such as authority to carry out encrypted backups. However, it is anticipated that such administrative changes will generally be relatively few and infrequent, in contrast to official turnover, and that system security requires that such consent should normally be obtained in all cases. Note that in the example, only 4 human signatures were required to recertify and register a user.

PARALLEL SIGNATURES

Figure 11 illustrates the flow of a document during a parallel mode of the multi-stage signing system. In this illustration, it will be assumed that a total of three signature devices 169a, 169b, 169c exist in the system, and that all three signature devices are required to complete the system wide authority signature (SWA). It will also be understood that the parallel signature can be adapted to different numbers of signature devices.

In the parallel method, a document coordinator

-5050

161 (the coordinator) receives a document to be signed 163. The coordinator may but does not require to be an authorization agent for one of the signing devices, but the coordinator is illustrated as a separate entity in general.

Document Coordination 161 generates three copies (or alternatively, three copies of a shredded document) 165a, 165b, 165c of the document to be signed 163. Each copy is sent to a first authorization agent 167a, 167b, 167c , then to a second authorization agent 171a, 171b, 171c, and then to one of the three signature devices 169a, 169b, 169c, and is finally returned to coordinator 161. In a more fully discussed manner, the document coordinator coordinates the separate signatures of the three signature devices and produces a system wide authority signature (-SWA) which sets the original document 163 to produce a signed document 173.

Figure 12 illustrates the processing of some of the copies, and the combination of three partial signatures on the system wide authority signature. It should be understood that each of the copies involves a process that is essentially the same, except that different authorization agents and signing devices will set the signatures, or partial signatures, according to their individual signing keys.

In this example, two authorization agents are required to authorize their respective signature devices.

-5151

169a to affix your signature. Coordinator 161 sends a first copy 165a of the document to be signed, along with a routing and information header (not shown) to a first authorization agent 167a, who fixes his signature (—Afila) and sends the signed copy 175a to a second authorization agent 171a. The second authorization agent

171a adds twice) a second authorization signature via (signed document 179a to the signature devices. Signature device 169a verifies the two authorization signatures, fixes its partial signature (--SD1) to the copy, and return signed copy 181a to coordinator 161

Two other signature devices (not shown) attach partial signatures to the copies of the document to be signed and return the signed copies 181b, 181c to the coordinator. All three copies can be processed in parallel

After the coordinator has three copies 181a, 181b, 181c of the received document all to be signed, the coordinator multiplies together the three partial signatures (--SD1, ~~ SD2, ~ ”SD3). The product of the three partial signatures is the broad system authorization signature (--SUR).

The signing device and smart cards of authorization agents will be trusted devices. The security of this multi-stage parallel signing method does not depend on the physical security of the coordinator workstation. The coordinator does not need to have a password

-5252 secret to authorize signature devices (although he will also have to route with encryption and signature keys to give privacy and for identification purposes).

The functions of the coordinator can be dispersed among the authorization agents. A first authorization agent can receive the original document to be signed and designate another authorization agent (or even another entity that is not an authorization agent, such as a server for one of the signature devices) to receive and combine the lü partial signatures. It is expected that the normal operation of the organization will preferably cause the coordinator to receive both documents to be signed, and then be responsible for supplying the signed document to the last recipient.

ADDING / REMOVING AUTHORIZATION AGENTS

Each signing device has an associated group of authorization agents. Because people come and go in an organization in 2D, the system includes provisions for dynamically adding or removing approvers by adding and removing public keys from the authorization agents' reliability devices. Adding, or removing an authorization agent is accomplished by submitting, to a signing device, a command to add or remove a public key from people. The command takes the form of an electronic message that

-5353 has a code for the add / remove command, additional information (discussed later), and authorization signatures.

Authorization signatures can be from other authorization agents on the same signing device, and the add / remove process can be completed locally by a single signing device. In an alternate version, the add / remove procedure may require the signing of the broad authority key to the system, thus requiring authorization agent quorum on a quorum of related signature devices another alternative, to approve and authorize the change. Even in different authorization agents they may have different capabilities, and some more powerful authorizations may be added or removed under the broad authority key of the system, while less capable authorizations may be added or removed locally under the authority of a local quorum. Preferably, the addition or removal of authorization agents requires the signature of the system wide authority key.

Figure 13 illustrates a command 201 to remove an authorization agent. Additional information with command 203 includes: a) the name of agent 205; b) the title of agent 207; c) ID number 209 of the signing device from which the agent is to be removed; and d) the identification code 211 of the trusted device associated with the authorization agent to be removed. After receiving an appropriately signed command, the device

-5454 signature removes the authorization agent's public verification key from its internal list of authorization agents.

Figure 14 illustrates a command 213 adding an authorization agent. Additional information includes: a) the name of agent 217; b) the title of agent 219; c) the ID number 221 of the signing device for which the agent is authorized 221; d) an administrative class 225 that indicates the powers for which the agent is authorized; e) an expiration date 223 for the new authority of the people; f) identification codes 227 for the master key or master keys that the authorization agent can instruct the signing device to apply; g) II) 229 code of the agent's trusted device; and h) a certificate 231 with the public signature verification key of the trusted device. Preferably the new agent's public key is certified 233 under the authorization of the SSWA signing key and the certificate is included with the command. The device 231 certificate, signed by the manufacturer of the trusted device associated with the authorization agent, also includes an assurance that the private signature key of the authorization agent is permanently confined to a smart card or other trusted device that has properties minimum safety requirements. (Preferably, the minimum security properties of the device will include the fact that biometric information is used to link the smart card with a physical characteristic of the user.

-5555 human. For example, the manufacturer may set the card not to create user signatures unless the user activates an attached fingerprint reader, where matching fingerprint data is stored inside the card and used to activate it.) After receiving a properly signed request (for example, after a multi-stage SWA signing has been completed), the signing device will add the new agent information to its internal list of authorization agents.

ADD / REMOVE CARD MANUFACTURERS AND MODELS

As previously discussed, authorization agents act through trusted devices, which can be smart cards manufactured with certain security properties. As a condition for adding an authorization agent, © 1 trusted agent device must be of a model approved. During system startup, trusted device model numbers that would be acceptable for use in the system were entered. Over time, new models will become available, and safety procedures can be adjusted so that older models are no longer acceptable. All signing devices maintain an internal table of accepted models.

New manufacturers can be added by circulating an electronic requirement among all

-5656 signature devices to add a new manufacturer. Figure 15 illustrates a sample requirement. The requirement includes a command 243 along with the manufacturer name 245, the model name or code 247, and a public signature verification key 249, joined together in a message 241 signed by the system wide authority key.

Older manufacturers can be removed by circulating an electronic requirement, signed by the SUR key, to remove the manufacturer's public verification key from the signature device tables »Figure 16 illustrates a sample requirement 251 that includes a 253 command and the name of the manufacturer 255. These add / remove requirements, once signed by a device quorum, are then sent to all devices, which are then verified using K⁺_ewi and act on them.

New models for an already approved manufacturer can be added by submitting an electronic requirement, signed by the SWA key, to add a new model. Figure 17 illustrates a sample requirement 261. The requirement will include a 263 command; the name of the manufacturer 265; the model number 267 and a 269 certificate, signed by the manufacturer, that the particular model meets certain safety standards (for example, a certificate that a model meets the requirements of level 3 FIPS).

Old models can be removed by submitting a

-5757 electronic request, signed by the SUA key, to remove the model from the tables of the signature devices.

Figure 13 illustrates a sample requirement 271, which includes: a command 273; the name of the manufacturer 275; and model number 277.

ADD / REMOVE SIGNATURE DEVICES

Over time, it will be desirable to add or remove 1Q signature devices from the system. Each signing device contains a table of other signing devices in the system that hold portions of the SUA key or portions of another master key for multi-stage signing as fully discussed below.) The identity of each signature device is defined by: 1) the device identification number (eg serial number; 2) the device's public verification key (installed by a manufacturer and certified under the manufacturer's signature, or a similar key recertified by the SWA firm); 3) the device's public encryption key 20 (used to send encrypted messages to the device); and 4) any subsequent certified public key only in its position.

New signing devices are added to the system by circulating an unsigned certificate among 25 other devices to receive the SWA signature and then circulate the signed certificate. The certificate contains the information

-5858 identifier as discussed above. After the certificate has been signed by the SUA key, the certificate is sent to all other signing devices with an instruction to add the new device to the internal tables of the other signing devices. Figure 19 illustrates a sample instruction 281, which includes a command 283 and a certificate 282. The certificate includes: the new identification code for the signature device 285; a signature verification key 287 certificate from the signing devices (signed by the manufacturer); and a signature device 289 encryption key certificate (also signed by the device manufacturer). The signature verification key and the encryption key could also be in a single certificate. Other information can be circulated among the other signing devices, such as the identities of key portions 291 used for the new signing device and the decryption key portions 292 included with the new devices. Once the signing device is added to the group, it can: 1) participate in the protocols to generate a new master key and receive a portion of it; 2) serve as a backup unit to receive the contents of an SD signature; or 3) serve as a replacement unit to receive the restored contents of a signature device backed up for review that has been destroyed or removed from service.

Figure 20 illustrates a message 293 to remove a

-59 signature device. Message 293 includes a command 295 and the device ID code 29 ?.

COPY KEY PORTIONS

The risk (consequences) of theft or destruction of signature devices has been reduced by virtue of the multi-stage signature process and the fact that no single signature device is capable of disclosing sufficient information to form a signature or form a firm. The information content of a signing device, including the SUA key portion, may therefore; or be transferred to another device, for example, when the physical support of the signing device is improved or for backup purposes.

Copying of the key portions and other information is accomplished by submitting or issuing a request, signed by the SUA key, to copy all or some of the information on a particular signing device to a second device. Figure 21a illustrates a sample requirement for a shipping device to copy its key portion (s). Requirement 301 preferably includes: a command 303, signed by the SUA key, identifying the second device by manufacturer 305 (which must already be included in the list of approved manufacturers' signature devices), and the model number 307 (which must already be on an approved model list), a serial number 309; a 311 certificate with a public encryption key to receive device; ID codes 313 of the key portions (or other information designation) to be copied ,; and the sending device ID 315. When the signed request is received by the appropriate sending device, the appropriate sending device, the sending device encrypts the identified key portion (s) and related information using the public encryption key the sending device sends the encrypted information as a key message) added)¹¹ to the receiving device. Figure 21 (b) illustrates a sample message from a sending device to a receiving device. Requirement 314 preferably includes: a command 316, signed by the sending device (--SD;); the receiving device ID 317; the sending device ID 318; the th-ID codes of the encrypted key portions 319; and key portion owner ID code 320. The receive command can also specify a quorum (or other authorization details) for use on the receiving device, but preferably, the receive key will be used according to the original quorum on the receiving device. As a typical operating procedure, all operators and system authorities should be informed that a copy has been made, along with the identity of the device or storage medium that maintains the copy.

-6161

Alternatively, the information can be copied to a storage device that is physically kept secure (eg stored in a vault) and offline (not subjected to remote attacks) in encrypted form for use as a backup.

QUORUM CHANGE REQUIREMENTS

The signing device quorum needed to set the SWA key is a system design parameter used by the leading device when generating the key chunks. This quorum can be changed by recombining the key chunks to retrieve the full signing key, and then dividing the key into an increased number of chunks that are then redistributed as with the original key chunks, but with a new requirement to quorum.

The quorum of authorization agents needed to authorize a particular signing device to set a partial signature can be changed without re-initializing the system. Such a change is preferably carried out by issuing a request to the respective signing device signed by the SUA key. Alternatively, authorization agents for a particular signing device can change the local quorum by issuing a request signed only by local authorization agents. The number of signatures that

-62 need to change the quorum can be equal to or different from the number required to authorize the signing device to set the SWA signature. Note that if the SUR key portions are stored inside the signing devices in encrypted form and yes. If the approvers keep the decryption key chunks as discussed below, the quorum needed to authorize a signature should not be reduced to less than the number of chunks needed to decrypt the SUA key chunk. In normal banking practice, the N of authorities should not be less than 2 per signature device, although some authorizers may have rights to multiple signature devices.

ENCRYPT KEY PORTIONS STORED

In this variation, shown in Figure 22, each portion of SUR key stored within a signature device 321 is stored in encrypted form 323. The decryption key (KEY) is divided into portions, and each agent trusted device Authorization 325, 327, 229 stores a portion of the decryption key. As discussed above, each requirement for the signing device to set a partial signature must be accompanied by signatures from a quorum of authorization agents. Pursuant to this variation, authorization agents additionally submit a portion of the decryption key

331, 333, 335 to the signing device 321. The signing device then:

1) combine decryption key portions 33? to retrieve decryption key 347;

2) 339 decrypts its SWA key portion;

3) use the complete SWA portion 341 to attach a partial signature 343 to a document 3 45;

4) delete decryption key 347;

5) delete portions 331, 333, 335 from the decryption key; and

6) Delete 342 the entire SWA key portion of 341.

When a document is sent to a signing device for signature, an authorization agent includes that agent portion of the decryption key and signs the message. In normal operation, the decryption key portions are protected due to the fact that all communications over the network are encrypted using the recipient's public encryption key (for example, from another authorization agent when a document is being circulated for signature agent, or a signature device when submitted for signature). Alternatively, each authorization agent can develop a session key for each message in order to protect the decryption key portions. (That is, each time a message contains a key it passes from one authorization agent to another authorization agent or to a

-6464 signing device, a new session encryption key is used). The entire message is then encrypted under the session key.

In this way, the full text of the SUR key portion exists only temporarily during the time it is being used to set a partial signature. Traditionally, the decryption key, and a complete set of portions of the decryption key exist only transiently. If a signing device is stolen, thieves may at best be able to retrieve the encrypted form of the SUR key portion.

The process for generating and distributing encrypted key portions and decryption key portions would proceed as follows and illustrated in Figure 23.

1) The primary device generates a public SUA verification key 351 and portions 353, 355, 357 of a private SUA signature key as discussed above for the basic variation.

2) The primary device generates a separate public / private encryption key pair 359, 361 for each private portion of the SUR signing key (a private portion of the SUA signing key is illustrated, and it should be understood that other portions are processed similarly).

3) For each private encryption key, the primary device divides the private decryption key into portions 363a, ... 363m using a division L of M where ΙΊ

-6565 is the total number of chunks, and L is the minimum number of chunks required to rebuild the private decryption key. M can be chosen to match the total number of approvers on a signature device, while L matches the quorum of authorization agents required to authorize a signature on the respective SUIA key portion.

4) The primary device encrypts each portion of the SVJA 357 signing key under the associated public encryption key 359, and sends an encrypted portion 365 of 1¿ * SWA signing key to a respective signing device along with the Γ1 portions of the respective private decryption key.

5) The private decryption key portions for the SUR key portions can also be distributed (distributed for secure maintenance) among other signing devices such that any private decryption key can be retrieved from the signing devices, but no device Signature contains enough information to retrieve any decryption key for another device. Such general portions for any given signature device would be released and with the consent of a quorum of authorities over various other SDs.

6) The primary device deletes the private decryption keys, the private decryption key portions, and the full private SUR signing key (if it still exists) from its memory.

6Β

When each signing device registers its respective authorization agents, the signing device additionally sends each authorization agent a decryption portion, identified by: 1) an identification number for the decryption key portion; and 2) the identification number for the associated SUA key portion.

For example, if there are five SWA signing key chunks, (requiring three for a signature) and each SUA key chunk was encrypted under a separate public encryption key, and each SUA key chunk requires three of the five authorization agents, then each decryption key can be divided into 5 parts

<td>with anyone</td><td>of three of them able to recover the key of</td>

<td>decryption.</td><td>There would then be 25 key portions of</td>

<td>decryption,</td><td>with each signature device having five</td>

distributed to their authorization agents (for their own key) and maintaining a portion of each of the decryption keys for 4 other devices.

In this way, the authorization agents required to authorize a signing device to set a partial signature will also have a sufficient number of decryption key portions to allow the signing device to decrypt the signing key portion.

SUA temporarily for each signing operation.

If one or more of the authorization agents loses your passwords (for example, you lose your

-6767 trusted device), then new smart cards would be registered on the same signature devices. The decryption key portions could be retrieved from other signature devices and could be restored to newly registered smart cards by submitting or issuing an electronic message, signed by the SWA signing key, for the signature devices to transfer portions of the decryption key to recently registered devices · As an alternative method, subject to the consent of the SUA, a given device could receive all decryption portions, decrypt its signature portion, generate a new encryption key pair, re-encrypt the signature portion under the public key, split the new private decryption key into new portions, and redistribute these portions to the trusted devices of the relevant authorities, taking care to encrypt them under the public encryption keys of those trusted devices of the receiving authorities.

As an alternate backup method, even decryption key portions can be distributed offline with an independent trusted institution as described in US Patent Pending Application Nos. 00 / 181,859 and 08 / 277,438.

-6860

CRYPTOGRAPHIC BEAT

As an added protective measure, each signing device receives a periodic (heartbeat) data input that, if interrupted, causes the signing device to be disabled. The heartbeat must be generated from a separate link from the signature device so that, if thieves attempt to steal a signature device, they must also enter a separate room or vault to obtain the source of the heartbeat. If they fail to acquire the heartbeat source, the signing device will become inactive and will not be useful.

In one deployment, each signing device supplies an encryption key to a heartbeat source. The heartbeat source periodically sends encrypted messages to the signing device. If the signing device fails to receive a minimum number of messages over a period of time from the heartbeat source, then the signing device clears its internal memory or takes other evasive action. The messages can be empty messages or simple messages, which must be encrypted by the heartbeat source using the public key given to it by the SD. Alternatively, the messages may be a random seth string generated at the heartbeat source by a pseudo-random number generator (RNG) and verified by a synchronized (RNG) on the fi rma-6969 device.

Multiple heartbeat sources can be set such that the signing device must receive messages from at least 1 (or a minimum number) over a period of time. If a heartbeat goes offline due to equipment failure or power drop, it will not trigger premature erasure of the signature device memories. The keys used in heartbeat communications can be retrieved in chunks at multiple locations.

In a second implementation, each signing device can send a request to a group of associated (satellite) devices on the network, and continue the operation only if at least a quorum of associated devices responds.

Requiring a quorum allows operations to continue during unavoidable crashes and communications repairs.

The use of a satellite device, while more complex, adds physical security and can be used in locations that have less safe environments, instead of improving these facilities with vaults, guards, cameras, etc.

Communication is linked between a signature device and its heartbeat source, or a satellite device can be a public network. If a signature device has been stolen, its associated satellite units can be disabled by system operators to prevent thieves from entering communication lines and rerouting heartbeats to the

-7070 stolen device.

For example, the signing device may be in the United States and its associated satellite device in

Europe.

When the signing device is stolen, the satellite device

European goes offline for its operators.

The reliability of the European agent for any erroneous action would be minimal, because the removal of the satellite only interferes with new signature operations for a short time. Previously signed firms remain active.

Alternatively, physical security wiring may be provided between a signature device and its satellite or heartbeat source instead of a public network.

GENERATION OF ADDITIONAL MASTER KEYS

Having established a secure multi-stage signing system with a SWA key, it is quite simple to generate an additional number of master keys to be used for other purposes. While the SWA signing key controls system administration, master keys can be used to sign other certified messages or documents for use on behalf of other legal entities. The generation and administration of other master keys is similar to the SUA key but without intermediate temporary certification stages. The method proceeds as follows:

1) Appoint a signature device as leader

-7171 (this is not necessarily the same leader that generated the SWA signing key).

2) Enter some public key certificates in the signature device list to receive portions of the master key.

3) Enter an identification code for the master key and a logical name.

4) Establish secure communication channels between signing devices (preferably using encryption key certificates for each related signing device).

5) Optionally obtain random material from each signature device.

6) Generate a new one for master public private keys

7) Distribute portions of private keys (optionally encrypted each portion and distributed portions of decryption keys).

8) Delete the entire master private key (if it was stored) and delete all the portions not retained by the leading signing device.

This process can also be used to replace the SWA signature, additionally sending a command to each signing device, signed by the SUA (old) signing key to install the new master key as the SUA signing key. Generally, the master key will have separate uses from

-7272 the SWA key and portions of the various master keys can coexist on signing devices. A previously generated master key (other than the SWA signing key) can be removed from the system by sending a message, signed by the SWA signing key, to remove fragments of the master key.

DOCUMENT AND SIGNATURE TRACKING

It is desirable to assign a unique identification code to each document to be signed in order to assist in managing the flow of documents through the system. The following information may be included in the headings of each document for use by message servers and authorizers:

1) The signature key identification code of the key to be used to sign the document.

2) The total number of partial signatures required to complete the signature and / or the number of partial signatures already applied.

3) The key fragment identification codes that have already been used to sign.

4) The identities of the signing devices that have already signed (for example, logical device names).

-7373

SIGNAL DEVICES INTERLOCK RINGS

A root CA, using a multi-stage signature system as described above, will generally certify the

CA subordinates located in other businesses and government organizations. Hypothetically, a large central currency bank can certify a major agency of a state in turn, can certify a corporation. This distributes the certification process flexibly in a way that can conform to existing political, economic, social organizations

However, each half of

CA must maintain strong security over its key from organizations, other than banks, signature. Few of such a few large corporations, and some government agencies, maintain highly secure multiple data processing facilities and storage vaults. For example, one half of a CA may possess at least one nominally secure physical location, such as a data center or vault operation, but lacks the funds to serve multiple sites for the multi-device schemes described above, in an alternative , the middle part of the CA may not have a truly secure location.

Less secure CA halves (such as CA corporations) can however establish their own signature rings (as described above) and interlock these rings

-7474 means with a higher security ring than a relative CA (such as a bank or a secure government agency). This can be done while separating the following issues: (1) key ownership and official control, (2) administrative and backup responsibility, and (3) physical possession of the devices.

A deadlock ring architecture can be created as shown in Figure 24 but having a medium CA 371 keeping one or more medium signature devices 373, 375, 377 in their own secure locations. Additional media signature devices 379, 381 may be kept in secure locations of a relative CA 383 and may still include some or all of the same devices 379, 381 that form the relative (root) CA ring 383 (hence interlocking rings). The parent CA may maintain multiple signature devices 385, 387, 389 that are independent of those of any given average CA 383. The signature devices described above do not require additional modifications to maintain additional master keys, each under different owners and control by respective authority officers 391a, 391b, with supplemental master keys grouped in different ways.

The average CA initiates key generation and distributes previously designed protocol portions using one of its own signature devices as a leading device, and authorizes its own officers as

-7575 licensing agents 391b. Some portions of the new CA master key receive on their own signature device 373, 375, 377, while others will reside on signature devices of their parent CA 379, 381. Authority to issue signatures may remain distributed only to officers from key owners, although they may also delegate some of this authority to some officers of the parent CA institution, in an emergency.

Thereafter, the average CA would initiate a multi-stage signature of CA signatures based on signatures generated by smart cards owned by its officials, and route those requirements to its own signature devices and / or devices in possession of the parent CA. In fact, signing devices do not need to be located with the parent CA, but can be located in any other CA that has a secure location and communication access.

COMPLETE LEASE SERVICES

An organization that does not have adequate and secure facilities can still generate certificates and can become a CA. The organization can rent the use of signature devices located in secure locations already established by various banks and other CAs. The organization takes possession of smart cards for its authorization agents, and routes signature requirements for signature devices to

-7676 through the communication network. The processes of generating keys, issuing signature, and carrying out other administrative tasks can therefore occur within devices under physical control of the local bank in accordance with contractual trust arrangements with the owner.

Officials from the organization would go to the local secure facilities (bank) to witness the key generation protocol by which their new signature keys are created, a number of facilities, other locations are divided, and distributed to each of host (possibly other banks or the same bank) that they have selected. At that time they can also assign powers for appropriate administrative backups as needed.

The organization can then issue official signatures and official certifications, without the need to establish its own security data center or vault hassles, while still substantially achieving all of the security benefits of the system as described.

DELEGATION OF SIGNATURE

When an authorized agent is temporarily unavailable (due to being on vacation, disability, etc.), some form of delegation of signing authority is desirable. It is undesirable for a human operator to lend his

-7777 smart card and an associated identification number or key to another, because this creates an unmanageable security risk.

An alternate delegation mechanism is for an original authorization agent (primary user) to issue a specialized delegation certificate for a substitute authorization agent (delegate). The certificate, signed by the primary user, would identify the delegate and the delegate's 13 public signature verification key. The delegation certificate would also contain a time limit during which the delegation certificate, and therefore the authority of the delegate) would be valid (see Sudia &amp; Ankney, Marketing of Digital Signatures, 1993). A delegate, using her personal smart card, would sign a document using the delegate's personal signature key and could bind the delegation certificate. The resulting documents would be signed by the delegate, not the primary user, and a document recipient must go through additional steps to verify the delegate's signature and the delegate's certificate. This rests, in part, on the ability for a public user of a system to have such verification capabilities and to have good access to a source of revocation information (or hot list), should the authority be terminated before its expiration.

A preferred approach is to allow a delegate to use the primary user's smart card in a way

-7878 is sure to actually replace the human delegate with the human primary user face-to-face or directly with the primary user's smart card. The delegate would then use the primary user's smart card to set the primary user's signature, and the universe of document recipients would save the additional inconvenience of verifying and evaluating another complex certificate.

When the primary user wants to delegate signing authority, the primary user issues a "substitute * certificate"¹ 409 to the delegate as illustrated in Figure 25. The substitution certificate identifies the primary user IB 411, the delegate ID 413, a means for the primary smart card to recognize the delegate (usually the delegate's public verification key 417 ), and a time limit 415 during which the certificate of substitution 409 (and therefore the authority of the delegate) is valid. The primary user can identify multiple individuals, any one of whom can authorize the smart card, or a group of individuals of which several must join to authorize the smart card. The background to such methods has been discussed in North American Patents Nos. 4,868,877, 5,055,200, and 5,214,702 by Addison Fischer.

As shown in Figure 25, when a delegate wants to sign a document 403 on behalf of a primary user, delegate 401 prepares and signs a request 405 in a

-7979 format specified to be communicated to the card of the primary user 407. Along with this, or included in the message otherwise is the certificate of substitution 409. If multiple delegates require authorization of the card of the primary user, they can sequentially sign the requirement in a manner similar to the signature of multiple authorization agents a request issued to a signing device as discussed above. Upon receipt of the signature request, the primary user's card will verify that the signature of the requesting user matches the public key that was originally specified in the replacement certificate, apply the signature of the primary user 419, and send the document signed to a 421 signing device (or other destination) in the usual way.

The primary user's smart card 407 can be physically given to a delegate. The presence of a time limit for delegate authority provides a time lock such that delegates can only use the primary user's smart card for a limited period. As previously discussed, the authority of the primary user is also limited to a fixed period of time. These limits reduce the consequences of theft, and allow primary and delegated users to store primary user cards in relatively unsafe office environments. After the time period has expired, the smart card does not become vulnerable to any attack from

-8080 key guessing. (In fact, it would be immune from attack even if the primary user or the delegate had written keys directly on the card).

Additional protection against loss or physical attack can be achieved by placing the smart card in a vault or other closed environment, and inserting the card into a card reader where it can be entered electronically but not physically. In this way, all the actions described above can be carried out, but none can have physical possession of the card.

For example, a primary user may be a vice president in charge of purchasing, who wants to delegate his specific signing authority to his secretary while he is traveling on business. The certificate of substitution may specify that your smart card must issue the signature of said president only upon receipt of a signature request signed by: (a) the secretary, as designated by your certificate of substitution; and b) confirmed by any other person with primary signing authority in the purchasing department. The vice president places his card in a card reader in a closed vault and leaves it.

To obtain the vice president's signature, the secretary would prepare the document to be signed and compute the crumbling of his associate using his computer terminal. She would then sign the shredded, place the vice president's public key certificate, the final recipient

-818.1 will need and then I would message them to another purchasing agent. The other purchasing agent would confirm the same shredded and link their public key certificate, along with their authorization certificate that has been issued to them by their purchasing authority. The other purchasing agent sends a message to the vice president's smart card via a local area network. Since the vice president's card also contains backup copies of the public keys of the certificate authorities that created these certificates, such as SUR, the vice president's card determines that the signing and certificates are all valid and sets the vice president's signature to the document. The card may also require that all these certificates be accompanied by recently signed CRLs or certificates in good faith from a locally recognized CRL handler.

This delegation mechanism has the advantage of the ability to reprogram the primary user's smart card. The primary user's smart card is a trusted device that has known security features, one of which may be an ability to engage in a secured load of new instructions (for example replacement certificates), as described for example in North American Patent Applications still pending 08 / 181,859 and 08 / 272,203 (relative escrow of code Sudia and CIP escrow of code Sudia).

-8282

The above delegation mechanism can be generalized such that it can have high value end user digital security keys that are in fact generated and used

<td></td><td>inside</td><td>of</td><td>security modules</td><td>resistant</td><td>to rape</td>

<td> 5</td><td>(TRSM)</td><td>than</td><td>are stored inside</td><td>vaults of</td><td>security or</td>

<td></td><td>centers</td><td>of</td><td>data while the</td><td>authorization</td><td>for such</td>

Signatures come from signature request messages signed by approved users who are not given smart cards to carry with them. These TRSM violations, to prevent data from being accessed, may be designated for different users, each authorized to act based (locked in time) to remain secure against any personnel in the user's private key center, but contain the keys of many of which may be in some unique unofficial signature, or some pre-arranged combination of signatures and authorizations.

Another use for the delegation mechanism, apart from the unique delegation from users on temporary absences, would be a system or method by which a programmatic signature 20 requires a programmatic signature requirement would be made to a card (or to a key concatenated with a common TRSI) to carry out a major desk signing or other role within a corporate or financial environment.

After learning from the modalities described above, people who practice this technique will be able to do

-8383 variations that fall within the spirit and scope of the invention. The embodiments described above are examples that do not unduly limit the scope of the invention which is defined in the following claims.

-8434