Multi-step digital signature method and system

Multi-level digital signature method and system

This application is US Patent Application No. 08/181,859, "A Cryptographic System with Key Conditional Entrustment Contract Features", and US Patent Application No. 08/272,203, "Enhancing Encryption System and Method with Key Conditional Entrustment Contract Features "Part of the continuation, the two cases are listed here for reference.

The public key certificate is an electronic document signed by the trust issuer and used to prove the relationship between the user's name and a public key and other related information. The certificate provides confidence to the public that the public key identified in the certificate is owned by the user whose name is in the certificate. The main standards describing the public key certification system include ITU-T X.509 Guidelines-Authentication Organization, and American Bankers Association ANSI X9.30-Part 3: DSA Certification Management (Draft). Many production examples have a hierarchical structure, in which each trust issuer, called a certification authority (CA), certifies the physical key of its subordinate. The CA attaches a digital signature to the electronic file in a way that is identifiable (it can prove that the CA has signed the document) and cannot be counterfeited (it can be highly assured that no one other than the CA has signed the document). For example, there may be quite a few "root" CAs at the top of the CA hierarchy, perhaps one for each country, which certifies the lower CAs. Under the root CA of the hierarchy, a higher-level CA (perhaps a bank) certifies its lower-level CA (such as a company), and it then signs a separate user certificate.

When a CA signature forms a large user class below it, and its signature key is used to sign the certificates of high-value users and subordinate CAs, it shows more value. The CA signature key then also serves as terrorists, economic criminals, foreign troops, and espionage services for economic spying or disrupting the economy through information warfare. All these arguments also apply to the key to the signature of the electronic representative of money.

So far, due to the provision of a "Certificate Signing Unit" (CSU), there is a need for the security of CA's private signature key. It is in compliance with the National Institute of Standards and Technology (NIST) and the Federal Information Processing Standards issued by the Department of Commerce ( FIPS) PUB140-1, an anti-alteration security module of the 3rd or 4th level. This kind of CSU internally generates its public/private signature key pair, securely and permanently "restrict" the private signature key in an area of the device that cannot be read by the outside world, and only outputs the corresponding public key, which will be used Prove its signature. A CSU from Bolt, Baranek, and Newman (BBN) in Boston, MA allows the use of the "N of K Threshold" organization to generate a copy of its private signature key, where the private key is divided into N shares and placed in a small plastic data key Above, each contains a memory chip. The data key is a patented product of the Datakey Company of Bensfield, MN. Then, if the CSU device is destroyed, at least a quorum of K data keys is required to rebuild the private key.

At least most of the security standards, the American Bankers Association ANSI X9.F1 committee on the security of large-cap banking applications recommends that CSU should be designed to prohibit any private key from the device in any form to prevent any possible unauthorized theft and The use of keys. This method requires a large number of steps for damage recovery, including the use of multiple key pairs at the same time. Because a single key only exists in a single CSU at a single location, the loss of a CSU or a location will force the CA to use another pair of keys to continue its business. This will require CA to publicly and/or securely distribute multiple (at least two or three) public keys, each identified by a different code number (for example, BT01, BT02, BT03) so that users can continue to identify them in a group The signature issued by CA after the CSU (which may contain the private key of BT01) is destroyed. Refer to X9.30-Part III of the steps for damage recovery.

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

Another object of the present invention is to provide a signature system in which a digital signature is identifiably related to a signature key, and there is no need for a single signature device to contain the signature key when the document is signed.

Another object of the present invention is to provide a signature system that allows one or more sets of signature devices to be lost or compromised while still remaining usable, without compromising signature services.

Another object of the present invention is to provide a signature system in which multiple sets of signature devices each generate, modify, or combine one or more sets of partial signatures, and the operation results of the multiple sets of signature devices generate a single digital signature.

Another object of the present invention is to provide a signature system in which multiple authorized agents directly or indirectly authorize each respective signature device to add or modify a part of the signature.

Another object of the present invention is to provide a robust and easy-to-use mechanism in which authorized agents can temporarily delegate their authorization capabilities.

The multi-level signature system described here uses a public key cryptographic system to sign an electronic document so that a recipient of the document can use a public identification key of one of the signers to recognize the signature. The private signature key corresponding to the public identification key is not allowed to exist in one place in the form of a whole and available at any time during the general signature operation. On the contrary, a private signature key includes an "operation holder" that can be used to add or modify a part of the signature, and the successive operations of multiple holders produce a signature that can be identified using the public identification key. All signatures are not complete until all or a statutory number of such signature devices have completed their signatures. Before participating in the signing process, each signing device requires authorization from all or a quorum of relevant authorized agents in turn.

When the operating holdings are initially generated, if an entire signing key is generated, the entire signing key is destroyed after the holdings are distributed. As the risk of theft or compromise of any device is now greatly reduced, the information content of each signature device can now be copied (for example, for remote support or plug-in replacement or "hotline" standby) so that if any device fails, it Can be replaced (or rebuilt) and quickly resume service. Because the signature operation cannot be completed with a single device, the consequences of copying any individual signature device are mitigated.

A multi-layer authorization management system is established, so that each signature device has some individuals registered in it (or a designated individual uses an external smart card), and the signature device participates in the signature operation only when authorized by a quorum registered individual . A quorum of these individuals (called authorized agents) also need authorization to change the system, such as registering additional authorized agents, eliminating authorized agents, changing the statutory requirements for any various actions that can be performed by the signature device, or generating And assign additional or replacement key groups.

In this way, a signature can be applied to a situation where a public identification key is used to be identified, but there is no private signature key in a single location that suffers a compromise or a catastrophe. Many locations must be invalidated or compromised before the signing service is interrupted or before the adversary collects sufficient information to counterfeit the signature. The individual signature devices do not need to have the same high level of security for a CSU using a single integral key. An inexpensive device that meets the FIPS 140-1 level 3 standard can be used (that is, a device that can prevent counterfeiting), so there is no need to use a relatively expensive level 4 device (when a modification is detected, it takes active measures To destroy or protect internal information).

An authorized representative agency allows an authorized agent to allow a representative or quorum to authorize his/her smart card to attach his/her signature during a temporary period of time.

The present invention will be described with reference to the accompanying drawings, in which: Figure 1 shows an overall view of the basic structure of an operational signature system according to the present invention; Figure 2 shows a preferred structure for a data center with a signature device; Figure 3 shows a better structure of an authorization device for use by an authorized agent; Figure 4 shows a procedure for temporarily identifying an inactive signature device when the system is turned on and enabled; Figure 5 shows a process for generating And the process of assigning a system-wide authority key to the operation holdings; Figure 6 shows the multi-stage signature steps for re-identifying a signature device; Figure 7 shows an overall system structure for identifying and registering authorized agents; Figure 8 shows a multi-stage signature procedure using an authorized agent; Figure 9 shows the document flow through each authorized agent and signing device in a routine multi-stage signing operation; Figure 10 shows a routine multi-stage signing operation The evolution of signing a document.

Figure 11 shows the document flow of a parallel embodiment of the multi-level signature system.

Figure 12 shows the processing of one of these copies, and the combination of three sets of partial signatures into the system-wide power signature.

Figure 13 shows an order to remove an authorized agent.

Figure 14 shows an order to add an authorized agent.

Figure 15 illustrates the requirement to show an order for adding a manufacturer.

Figure 16 illustrates the requirement to show the removal of a manufacturer's order.

Figure 17 illustrates a request to show an order for adding a model.

Figure 18 illustrates the requirement to show the removal of a type of command.

Figure 19 shows an example of a command including adding a signature device.

Figure 20 shows the message used to remove a signature device.

Figure 21A shows an example of requesting a copy of the key holder for a sending device.

Figure 21B shows an example of a message from a sending device to a receiving device.

Figure 22 shows a procedure for encoding and storing key holdings.

Figure 23 shows the process of generating and distributing coded key shares and decrypting key shares.

Figure 24 shows a chain ring architecture.

Figure 25 shows a procedure for issuing an agent certificate to delegate the authority of an agent.

The most direct explanation of the multi-level signature method will begin with a discussion of a number of related mathematical procedures.

A.<u style="single">Enhanced organization with sequential partial signature</u>

First, the secret signature key belonging to a group of public/private key pairs in a "system-level authority""<i>K</i>_<i>SWA</i>"It is expressed as several ("<i>n</i>0")'s holdings ("<i>a</i>_<i>i</i>") and makes the signature key<i>K</i>_<i>SWA</i>Any threshold number can be used ("<i>t</i>0") is calculated as the product of the holdings, where<i>t</i>0 is less than or equal to<i>n</i>0. This representation is such that when you have less than<i>t</i>0 It is impossible or difficult to return the signature key when holding a share<i>K</i>_<i>SWA</i>. The method to achieve this can be used, for example: 1) Using a Shamir-type secret holding institution (A. Shamir, "How to Share a Secret", ACM Communications, November 1979, V.22, n.11), 2) Use a Blakley-type secret holding branch (GRBlakley, "Procedure Key", Proceedings of the National Computer Conference, 1979, American Federation of Information Processing Associations, V.48, 1979, pp. 242-268); 3) Decompose the key; or 4 ) Generate a key with a product of known factors. What is needed is that the private key is represented as:<img file="TW307075B_D0001.tif" />=<i>a</i>₁^＊<i>a</i>₂^＊…^＊<i>a</i>_<i>t</i>0(2N modulus) where<i>K</i>_<i>SWA</i>Is the signature key and<i>a</i>_<i>i</i>Yes<i>t</i>Any combination of 0 holdings.

Secondly, use a share of the private key<i>a</i>_<i>i</i>, Each device puts a partial signature left by a previous device in the index and uses multiple devices to form a signature. When using "modulus N" arithmetic (one of the arithmetic operations is to divide the result by the modulus N and take the remainder as the result of the modulus N), the following relationship between exponent multiplication and sequential exponent is established:<maths><img file="TW307075B_D0002.tif" /></maths>In other words, if the exponent of a base x is a two-factor<i>a</i>₁And a₂Product of, then if the exponent of the base is a first factor<i>a</i>₁, And the exponent of the result is the second factor<i>a</i>₂The result is the same. Moreover, the order of taking the exponents can be reversed, so that if the base is first taken by the second factor<i>a</i>₂Is an exponent, and the result is then the first factor<i>a</i>₁The result for the index is the same. This relationship can be extended to three or more sets of factors. Unless otherwise stated, all arithmetic operations are considered modulo N.

In the multi-level signature method, the holding of a signature key<i>a</i>₁，<i>a</i>₂，…，<i>a</i>_<i>n</i>0Be assigned to each device. A group of first devices attaches a partial signature to a document by hashing the document (the "H" symbol will be used to indicate the result of the hashing operation) and exponentially taking the hash as: the first Partial signature=<img file="TW307075B_D0003.tif" />(mod <i>N</i>) A set of second devices sign the first part as a second holder<i>a</i>₂Continue the signature for the index: the second part of the signature =<img file="TW307075B_D0004.tif" />(mod <i>N</i>) The procedure is repeated until "<i>t</i>0 "Use each device for each device"<i>t</i>0" respectively hold shares as the index of the hash, and generate available public<img file="TW307075B_D0005.tif" />Identify one of the final signatures.

B.<u style="single">Additional institutions with non-synchronized partial signatures</u>

A different method to achieve a similar result involves dividing the signed private key into the holdings that are added (modulus N) to produce the private key.

<i>K</i>=<i>a</i>₁+<i>a</i>₂+…+<i>a</i>_<i>t</i>(mod <i>N</i>)

This can then be used to use the hash to index each stake to generate an intermediate value separately<img file="TW307075B_D0006.tif" />, And multiply the obtained intermediate value to perform multi-level signature in an asynchronous manner, as shown below:<maths><img file="TW307075B_D0007.tif" /></maths>

Since there is no need to send messages sequentially from one place to another, this method has considerable computational advantages over the above-mentioned sequential method. On the contrary, a central administrator can send the same message (or hash) directly to the location of each part of the signature in a direct way, and then combine the resulting part of the signature to generate the final required official signature. The final combination calculation does not require any special security, because it does not add any information that is not included in the signature of these parts, so it allows the administrator to work on a table. In fact, these partial signatures can even be left to later be combined by the recipient who recognizes the transaction! This burdens the recipient with additional processing work, but does not weaken the security of the official signature.

According to the index method, the signature architecture that can be modified to allow multi-level signatures includes: R. Rivest, A. Shamir and L. Adleman ("RSA"), "Methods of Obtaining Digital Signatures in Public Key Cryptosystems", ACM Communications, V .21, n.2, pp. 120-126, February 1978; D. Kravitz, Digital Signature Algorithm ("DSA"), US Patent No. 5,231,668; Desmet, Y. Frankel, "Threshold Cryptographic System", CRYPTO'89, pp. 307-315, 1989; Taher EL-Gamal, "Public key cryptosystem and a signature authority based on separate logarithms" ("EL-Gamal signature algorithm"), IEEE Journal of Information Theory , Vol.IT-31, No.4, July 1985; S.Micali, "A Safe and Efficient Digital Signature System," MIT/LCS/TM-501, Massachusetts Institute of Technology, Computer Science Laboratory, March 1994; A. Menezes et al., "Elliptic Curve Public Key Cryptography System," 1993.

<u style="single">System Introduction</u>

Figure 1 shows an overview of an architecture for a signature system according to the present invention. The architecture includes a plurality of signature devices 11, 13, 15, 17, 19 connected by a wide area network (WAN) or a local area network (LAN) 21. The respective signature devices 11, 13, 15, 17, 19 are dispersed as widely as possible under the WAN/LAN permission, for example, on separate land, separate venue, or at least separate part of a metropolitan area.

In Figure 1, the signature device 2 is shown in detail as an example. Each signature device is assigned a set of permanent identification code (for example, unique serial number) and a set of logical name (for example, "signature device X") for encoding/decoding a pair of public/private device keys 12a, 12b, and A pair of respective public/private device keys 14a, 14b are used to identify/sign a signature. In addition, each signature device receives a common code key 16 and a common identification key 18 for all other signature devices.

Below, the encoding/decoding key is shown as "KE", and "KS" indicates the signature/recognition key. A positive sign ("+") superscript indicates a public key, and a minus sign ("-") superscript indicates a private key. The subscript indicates the owner of the private key for each key pair.

The groups of authorized agents 23, 25, 27, 29, 31 are connected to each other via the network and connected to the signature devices 11, 13, 15, 17, 19. Each authorized agent is an individual acting through a trusted computer device (such as a smart card that prevents modification, or other trusted devices), which will be described in detail below. Authorized agents can be distributed where LAN/WAN 21 is accessible, but for the convenience of organizations operating the signature system, it is assumed that most of the authorized agents are close to the corresponding signature device.

In Figure 1, the authorized agent 2a (item 25) is taken as an example and uses the same symbol of the key held by the signature device 2 described above. The trust device of each authorized agent is assigned a unique name, and there are a pair of public/private device keys 20a, 20b for encoding/decoding communication, and a pair of public/private device keys 22a, 22b for identification/signature signing, respectively . If the RSA public key cryptosystem is adopted, a pair of such pairs can be used for both signing and encoding. The authorized agent also receives the public coded key 24 and public identification key 26 of all other authorized agents.

The signature device also receives the public coded key 24 and the public identification key 26 for all authorized agents. Similarly, the trust device of the authorized agent receives the common code key 28 and the common identification key 30 for all signature devices.

To facilitate the description of the following multi-level signature process, it will be assumed that all communications on the network are encoded using a standard public key coding system ("PKC") mechanism, such as RSA-key delivery. It is also assumed that the order sent from one network entity to another entity is signed by the sender using a standard (PKC) organization, such as an RSA signature with MD5 message digest. In the following figure, the device encoding/decoding key and the device signature/recognition key can be omitted, but it should be understood that they appear on all devices as described above.

Figure 2 shows a preferred configuration of a secure data center computer configuration 48, in which the signature devices of Figure 1 can be found. In addition to a set of signature devices 29, each data center configuration 48 additionally includes a separate message server 47. The signature device 39 is dedicated to signature operations and is located in an actual safe location, such as a safe. There is no direct connection between the signing device and the external computer network. As will be explained in detail below, the signature device 39 will have a multi-level signature key holder 36, its own device signature key 37, a table 38 identifying its authorized agent letter, and a certificate 40 for its public identification key, selected to cooperate The key holds 36 public keys (wherein the certificate is<i>KS</i>_<i>SWA</i>Sign it.

In the multi-level signature process, a signature device 39 will accept the request via the message server 47. The message server performs routine communication procedures, such as unpacking routine private packets attached by an intermediary (the server 47 does not have a private decryption key for the signing device), and when the inputs are processed faster than they are processed Wait for input to be queued. The message server presents the message to the signing device for signing, receives the signed (or partially signed) result, and (a) sends the partial signature result back to the requester, or (b) sends the result to a device under the agreement. In order to receive and participate in the general communication protocol, the message server also has one pair of public-private keys 32, 33 for its independent message signature, and the other pair 34, 35 for encoding, so that it can receive and open the encoded message-thus The signature device can be free from this routine burden and does not significantly affect the security of the secure signature procedure.

The message server 47 may be a relatively low-security computer in a relatively low-security environment, such as a group of general security data centers. The message server 47 is connected to the LAN/WAN 21 and provides document queue and communication services of the signature device 39. The message server 47 contains a set of system operation records in order to maintain a review record of messages and documents transmitted to and from the signing device. As shown, a signature device and its related message server are preferably divided into two groups of physically separated computers. Although less used, the signature device 39 and the message server 47 can also be made to work separately on a single computer in a highly secure environment.

The message server can also provide a layer of protection, called a "firewall", which separately confirms all transaction inputs before they are passed to the signing device. In addition, a set of "online" signature devices that can be accessed on a public network will be opened for unlimited attempts and network saturation attacks when the service is denied. Negative attacks may split the daily certificate issuance, but will not reduce users who rely on previously signed documents (that is the majority of the estimated number of users). However, constant attempts will be threatening, especially when the attempter identifies some potential flaws. The message server can identify all messages in a list of authorized devices (signature devices and authorized agents), as well as more sophisticated strategies to identify possible attacks, refuse access after several failed attempts, and take proficient actions to track any incorrect data input The source. This will allow the firmware of the signature device to be maintained simple and easy to verify, and it will also allow system operators to modify their detection and evasion strategies based on the current state of network security.

Figure 3 shows the workstation of the authorized agent. An operator as an authorized agent can work in a relatively unwarranted area of a desktop computer or terminal 51 that can be seen in a general office. Each 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 decoding key and a private signature key unique to the smart card. The operator can use the card to issue signature instructions. Such trust devices can be made using FIPS third-level devices, such as the iPower card from California International Semiconductor, which can be easily planned at the firmware level and allows the evolution of new methods and procedures for secure signature and authorization. No need to replace the actual device. The trust device of each authorized agent must have at least one private signature key. Preferably, the private signature key is installed in the device at the time of manufacture, and the corresponding public identification key is "certified" by the manufacturer. The certificate here means that in the trust device, the manufacturer includes the electronic message containing the device serial number and public key, and has other evidence of its model and its trust characteristics, and the message (certification) is signed by the manufacturer.

These operators use their desktop computers to read and generate messages. When an operator wishes to sign a message, the desktop computer sends the message to the trust device, which uses the device's private signature key to attach a digital signature. In a preferred embodiment, the signature is a signature of a set of second signature keys, which is generated specifically for the specific user and proves to belong to him. In this way, the system can continue to use the device's signature to identify the trust level of the device in any transaction, and use the user's signature to prove that the user agrees to the transaction. This makes it possible to remotely generate and cancel user keys based on various management facts related to the user or authorization, while still allowing the device to be used again, or in charge of many other users that the user wishes to do for other unrelated purposes Key pair.

Figure 3 also shows a preferred configuration of a possible trust device that can be used by an authorized agent. It is composed of a conventional "smart card" packed with a single microchip in a card. The microchip device has an input/output circuit 42 for power supply and communication, and a microcontroller 44 for executing firmware programs. The memory 52 includes a system firmware 43 (similar to a simple operating system) for operating the microchip hardware. The memory 52 can also store the device key 45 installed by the manufacturer, the user key 47 that is part of the protocol described here, and the application firmware 49 used to execute the network protocol described herein. In addition, unused memory is used as a work area 54 for temporary storage. The microchip may also contain a set of optional "cryptographic units" 46, which is a special-purpose arithmetic accelerator with hardware for exponential and other arithmetic operations for encoding/decoding and signing procedures. The microchip further includes a set of optional trust timing pulses 48 activated by the manufacturer and useful for timestamp signing (assuming proper battery power is present). The microchip further includes a set of optional random number generator 50 used in conjunction with the encoding/decoding process. The smart card also includes an optional noise source (not shown), such as a diode, which can be inside or outside the microchip to generate random numbers.

The signature device shown in Figure 2 can be a smart card with the same design as an authorized agent's trust device.

The devices in the network will be activated according to the following sequence of steps: 1) coded key distribution; 2) temporary certification of the signature device; 3) distribution of key holdings; 4) recertification of the signature device; and 5) authorized agent certification.

Each step will be discussed in turn. After the discussion of system startup, the best method for signing high security certificates and other documents, as well as further changes and enhancements, will be explained.

<u style="single">Coded key distribution</u>

The reason why each signature device and the smart card of each authorized agent is assumed to be a "trust device" is that it is a tamper-proof device based only on the special micro-function, and its manufacturer makes it have a protective memory A pair of device signature keys and a pair of device code keys. At least, the manufacturer of this device will certify that the device will not reveal itself or the private key of its user unless it undergoes considerable tampering efforts. Each device also has an electronic certificate signed by the manufacturer, including: 1) the serial number of the device; 2) the public signature identification key of the device; and 3) the public code key of the device. The manufacturer can install two separate certificates, one for signing and identifying keys and one for encoding keys. The signature device uses a public/private cryptographic map structure to encode its communication. In this different method, physical protection can be used to provide all devices without manufacturer certification. For example, a small (notebook) computer can be used to replace the trust signature device and activate it in a safe vault.

It is assumed here that each trust device starts with some basic functions, such as software that enables it to be activated and received messages via a network or an electronic mail system, so that it can communicate with other trust devices. At the same time, it is assumed that at least one signature device, designated as a "guidance" device, can receive information about the initial state of the system from the operator responsible for starting the system.

The next step in system preparation is to swap the device keys for the device. The key distribution proceeds as follows.

1) A group of signature devices, designated as "guide" devices, receive the identification of other signature devices in the system from the operator. The guiding device sends its public code key and public signature identification key to other signature devices. Alternatively, the boot device can use, for example, hash its firmware, use its device signing key to sign the hash value and send the signed hash value to other devices to send a message for confirming its operation of the firmware.

2) After the other signature devices receive the public coded key of the guiding device, the other signature devices of each group will send their respective public signature identification key and public coded key certificate back to the guiding device. If the boot device sends one of its firmware hashes, each group of signature devices hashes its own firmware and compares the two. The two sets of hash values must match, otherwise, each signing device stops participating in the agreement and notifies its operator. This comparison of hash values ensures that all signature devices use the same firmware, which is used to check that the boot device is not "counterfeit". Each signature device selectively returns a hash value of its respective firmware to the boot device.

3) The boot device compares the hash value of the firmware of each other device with its own hash value to check that no other device is a counterfeit.

All signature devices have now received the public codes and signature identification keys of other devices. It will be understood that all future messages will be signed using the sender's private signature key and the recipient will be identified using the sender's public identification key. It will also be understood that all communications will be encoded with the recipient's public encoding key and decoded with the recipient's private decoding key.

These additional signature keys will not be used for multi-level signatures (discussed below). It is used to use the routine communication codes and signatures in network entities as a proof of identification of a device. When generating and distributing master key fragments in the actual use of multi-level agreements, this proof of membership and identification in the group is important.

<u style="single">Temporary Certificate of Signature Device</u>

Figure 4 shows the temporary certification of the unactivated signature device. In this procedure, the public key certificates of the signing device (they may not be signed or signed by the device manufacturer) will be replaced by a certificate signed by a temporary administrator 61. The administrator is preferably an operator who is responsible for starting the system and operating via the administrator's personal smart card. This temporary certification establishes improved security in the signature device (belonging to the target group) when the signature device generates a signature key for a multi-level signature. When in actual use, it is expected that the temporary administrator will work with multiple witnesses to ensure the correct steps, and the temporary certification will only be for the situation that requires a minimum time (a few minutes or a maximum of a few hours) to complete the master key generation agreement. has an effect. The provisional certification proceeded as follows:

1) The administrator 61 generates a private signature key 63 and a corresponding public identification key 65.

2) The administrator communicates with each group of signature devices 11, 13, 15, 17, 19 their public signature identification key 65.

3) Each group of signature devices 11, 13, 15, 17, 19 generates a private signature key 67, 69, 71, 73, 75 and a public identification key (not shown), and sends a signature key certification request to the administrator 61. The signature key certification request is an electronic message containing the name of the signature device (for example, a device serial number and/or a logical name, such as "SD1"), the device's most recently generated public signature identification key, and other required management information.

4) The administrator uses the administrator's private signature key to sign each certification request.

5) The administrator sends back the signed signature key certificates 68, 70, 72, 74, and 76 to the signature devices 11, 13, 15, 17, and 19 respectively. The signed certificates 68, 70, 72, 74, 76 have appropriate subscripts and the administrator's signature ("-ADMIN") is attached below as the symbol of the public signature key (KS+). Such certification, of course, will include device identification and type information (not shown).

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

Each group of signature devices now has: a) the administrator's public identification key; b) his own temporary private signature key; c) his own temporary certification, the administrator's signature and the temporary public signature identification key with the signature device; d) Temporary signature identification key certificate for other signature devices. Each signature device can use the administrator's identification key to identify the administrator's signature on the temporary certificate from other signature devices.

Each signature device can now use the signature key that has been certified by the temporary administrator to exchange messages and proceed to a more tightly controlled step of the agreement. For the convenience of explanation, it will be assumed that the network communication of the multi-signature operation from this point to the end of the device re-identification is signed using one of the signature keys certified by the temporary administrator, and each receiver recognizes the sender's signature. If a message is not properly signed, the message will be rejected and the agreement cannot continue unless a confirmation message is provided. At the same time, when an improperly signed or unsigned message is received during multi-stage activation and signing operations, some form of omen analysis or omen response can be performed.

<u style="single">Temporary certification by authorized agent</u>

Figure 4 shows the temporary certification of the authorized agent. As will be described in detail below, a signature device only attaches a set of partial signatures when it reflects the quorum authorization from the authorized agent. The operation of the signature device under the authorization of the temporary administrator also requires a quorum of authorized agents. The temporary certification of the authorized agent ensures that only the designated agent can authorize the signing device during the start-up process.

The steps for temporarily certifying the authorized agent are similar to the steps for temporarily certifying the signature device, and the steps are as follows:

1) The administrator 61 communicates his public signature identification key 65 with each authorized agent 23, 25, 27, 29, 31.

2) Each authorized agent generates a private signature key certification request to the administrator 61. The signature key certification requirements include at least the following information: a) the name of the authorized agent (a human's unique name); b) the identification code of the agent's trust device (for example, the smart card serial number and model number); c) the agent's signature Identification key; and d) the signature identification key of the agent's trust device (it is used to determine that the trust device is of a conventional type).

3) The administrator uses the administrator's private signature key to sign each certification request.

4) The administrator returns the signed signature key certificate to each authorized agent.

<u style="single">Key share distribution</u>

Figure 5 shows the generation and distribution of "operating shares" of a system power (SWA) "official" signature key. A set of signature devices, here signature device 1 (item 11), is designated as a set of "guide" devices. The human operator shall provide at least the following information to the guiding and signing device:

a) Threshold parameters used to divide a key into holdings, that is, the total number of holdings to be generated and the minimum number that needs to be attached to the SWA signature.

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

c) The identification number and/or logical name of the key holder to be assigned to each holder, for example, "SWA-SHR-56789," or "BT01a".

d) The device certificate of the authorized agent who will first be allowed to authorize the specific signature of each device.

The operators can additionally provide a set of numbers, which limits the total number of fragments of a single signature device. It can be used in the case that a signature device has multiple sets of master keys, which will be discussed in detail below.

The next step is to generate a signature key, called a "system power" (SWA) key, which holds a share, which will be used to manage the system. The generation and distribution of public SWA public signature keys and corresponding private SWA key holdings are as follows.

1) Each signature device 11, 13, 15, 17, 19 transmits a code string of random "seed" information to the guiding signature device 11.

2) The guiding device 11 combines the seed information and uses it to generate a public system authority signature identification key (<img file="TW307075B_D0008.tif" />) 91, which was finally used to identify the official signature.

3) The guiding device 11 generates a private SWA signature key operation holdings 93, 95, 97, 99, 101. The steps can be achieved by first using the key generation method of the prior art to generate an integral private/public key pair and then using one of many conventional private signature key separation methods to separate the private signature key 92 into holding shares. One of the requirements for the generation of this holding is a minimum number of separate holdings<i>n</i>0 should be sufficient to complete a system power signature.

4) The guiding device 11 transmits the SWA public identification key 91 and a private signature key holder 95, 97, 99, 101 to each group of other signature devices, and it retains a copy of the SWA public identification key 91 and a group of holders The SWA private signature key 93. Each SWA private signature key share is transmitted with the following additional information: a) a set of type codes for identifying the key-signature key share (also indicating the length of the holding); b) a set of unique keys for SWA public identification key Identification code; c) a set of unique identification codes for the respective SWA private signature key holdings; d) the total number of allocated SWA private signature key holdings; e) the minimum number of SWA private signature key holdings that need to complete an SWA signature F) The identification of the signature device that receives other SWA private signature key holders; and g) The certificate of the authorized agent that will be first allowed to authorize the use of each SWA private signature key holder on the target signature device.

The guiding device 11 will use the publicly-certified public coding key of its respective signature device to encode each SWA private signature key holding.

5) The guidance device 11 outputs the SWA public identification key provided to the operator and eliminates the following information: a) the overall private SWA signature key (if the overall private SWA signature key is stored when the program is generated); and b) the SWA private signature All holdings of the key (except for one holding reserved for your own use).

6) Each recipient's signature device, along with the initial human authorizer certificate of the device, installs its SWA private signature holder in a tamper-proof memory area.

It is preferable that the private SWA signature key only has the guiding signature device 11 at most, and only continues for the minimum time required to generate and distribute the holdings. In this way, the overall private SWA signature key does not exist for operational use, and only when one of the generating programs is attacked for a short period of time.

In this step, each signature device has additionally safely received: a) a copy of the public SWA signature identification key; and b) a set of private SWA signature key holdings.

To illustrate an example in the discussion below, the assumption (for simplicity) needs to be appended to the minimum number of copies of the SWA signature<i>n</i>0 is 2 out of 5 parts. It should be understood that a higher number can also be selected, possibly at least 3 copies, which will increase security, but will also increase the number of steps in the signing process.

<u style="single">Signing device recertification</u>

In the previous step of initiating the agreement, a temporary administrator 61 certifies that the device signs the identification key under its authority, and the signature device certification is signed by the administrator's temporary signature key. When recertifying, each signature device will use a multi-level signature to circulate the new certification requirements for its own public key among other signature devices that will be certified under the system power key.

Figure 6 shows the steps used to recertify the signature device 1. Other devices will re-certify themselves by repeating the procedure for each device. The procedure of signature device 1 is as follows:

1) The signature device 1 generates an unsigned certificate 103 and transmits the certificate to the signature device 2. The certificate includes at least: a) the identification of the signature device (for example, the serial number and/or the logical name of the device); and b) a set of public signature identification keys for the signature keys of the device. The key to be re-certified is the same public key that was originally generated by the device at the beginning of the agreement and was first temporarily certified by the administrator. The key is permanently marked on the device that will become a member of the signature device family that handles the holdings of that particular SWA. (In this procedure, the device's signature key and its related manufacturer's certification remain unchanged, and are permanently maintained as the certification of the device's original and subordinate characteristics.)

2) The signature device 2 uses its SWA signature key holder 93 to attach a set of partial SWA signatures. This partial signature is formed in two steps. First, the signature device 2 should be used to generate a "hash" function (for example, MD5 or SHA) that is identifiably related to a reduced length bit string that is not hashed. The bit string is represented by a binary number of a value (large integer) that can be processed. Second, the signature device 2 uses the hash string to be indexed by its SWA signature key holdings to form a group of partial signatures. That is, the signature device 2 will be the value of the partial signature calculated according to the following formula: --SD2=(Hash (Proof))^{Key Holder 2}Modulus N (Note that in the text or in the figure, the bit string that constitutes a signature block is generally represented by placing a long dash before the signer's identification symbol. The resulting bit block is generally appended to the signed data block The bottom, or can be understood from the text.)

3) The signature device 2 sends the partial signature certificate 105 to the signature device 3.

4) The signature device 3 will take the index of the partial signature-SD2 to complete the system-wide power signature. That is, the signature device 3 calculates a value according to the following formula: --SD3=--SD2^{Key Holder 3}Modulus N=((Hash (Proof)^{Key Holder 2})^{Key Holder 3}=--The partial signature attached by SWA signature device 2 can be used as an audit record and attached to the file. Note that only 2 sets of partial signatures are required in this simplified example.

5) The signing device 3 sends the signed certificate back to the signing device 1, which then sends a copy of the certificate to other signing devices, thus allowing them to recognize their future signatures.

In this example, the signature devices 2 and 3 attach signatures in their order. However, any combination of signature devices can be signed in any order (as long as the number exceeds the minimum<i>t</i>0), and produce the same signature.

Re-certification is important because further operations performed by the entire system of the signature device will only be performed in response to requests from the device certified by the SWA signature (for example, the authorizer, as described below). The signature device itself may require other signature devices. Using this step, the signature devices themselves become the first set of devices certified by the system-wide authority (SWA) using the multi-level signature procedure defined here.

In a different embodiment of the above-mentioned re-certification procedure, the target device group can request their re-certification (unsigned certification) before the initial key of the boot device is generated. The guiding device will sign these certificates when it generates the SWA private signature key, before dividing it into fragments and erasing the entire key. Doing this does not seem to see any major advantages, because the main function of the resulting system is to sign these certificates in a highly controlled and effective manner.

<u style="single">Authorized agent re-certifies</u>

Figures 7 and 8 show the steps used to prove and register an authorized agent. Figure 7 shows an overall system architecture, and Figure 8 shows the processing sequence for certification requirements. The signature device will attach the system-wide power public signature to the authorized agent certification, so the certification is a common signature certification key for each authorized agent. During the registration process, each signature device will also change the internal storage table of the specific authorized agent who will be authorized to instruct the signature device to apply its partial signature. In routine operation, if the request is signed by the minimum number of temporary certificates or SWA certification authorized agents (or if the minimum number of separately signed messages is received), a group of signature devices will attach its partial signatures , Will be explained in detail below. An example of the procedure for certifying the authorized agent 3a (AA3a) and registering AA3a with the signature device 3 is as follows.

For the convenience of presentation, it will be assumed that signature devices 3 and 1 (Figure 7, items 15 and 11) are two of the five signature devices selected to attach SWA signatures.

1) The authorized agent 3a sends repeated certification requests to the signing device 3 via the LAN/WAN 21 (Figure 8, item 121). (Alternatively, authorization and/or registration can be restricted via a set of limited-access communication channels, for example, directly connected to a stand-alone personal computer and directly entered into the signing device). The certification requirements include at least the following information: a) the name of the authorized agent (a human's unique name); b) the identification code of the agent's trust device (for example, the serial number and model number of the smart card); c) a signature recognition of the human agent The key (if initially signed by the temporary administrator); and d) a group signature identification key of the agent trust device, which is used to determine that the device is of a conventional type. This determination is especially important when all or most of the operations are performed in a wide distributed location so that the system operator cannot recognize it by visual observation.

2) The signature device 3 attaches a set of partial SWA signatures (-SD3) to the certificate 121, and transmits the partially signed certificate 123 to another signature device.

3) The signature device 1 authorizes to send part of the certificate to SD1.

4) The signature device 1 uses its holding 93 of the SWA signature key to complete the signature procedure.

5) The signature device 1 sends the complete signature certificate 125 back to the signature device 3.

6) The signature device 3 retains a copy of the signature certificate 111, enters AA3a into a record of one of the authorized agents 113, and sends the signature certificate 125 back to the authorized agent 3a.

This procedure is repeatedly used for all authorized agents 101 registered by the signing device 3, so that each authorized agent 101 has a signature certificate and the signature device 3 has a record 113 of one of all certificates. This procedure is reused for all authorized agents of other signature devices 11, 13, 15, 17, 19.

<u style="single">Multi-level signature</u>

At this time, the signature device is activated with the holding of the SWA private signature key. The signature device has recertified itself, and the authorized agent is recertified and registered with its respective signature device. The system can now enter routine services for system management and official certification functions. In the following discussion, the multi-level signature will be explained for the authorization key of the whole system, which is generally used for system management. As will be discussed below, except that the content of the message signed by the master key may not be management in nature, another "master key" will be generated and used in the same device family in the same way as the authorization key for the entire system. Multi-level signature.

Figures 9 and 10 show multi-level signatures using system-wide authorization keys. Figure 9 shows the document ("DOC") flow through each authorized agent and signing device, and Figure 10 shows the evolution of the signature on the document. This example assumes that the authorized agents 1a and 1b authorize the signing device 1 to attach a set of partial signatures, and the authorized agents 2a and 2b authorize the signing device 2 to complete the SWA signature. For simplicity, it is assumed that any two groups of authorized agents need to activate each signature device. The procedure proceeds as follows.

1) The authorized agent 1a receives the request for a signature via the WAN/LAN. The request is an electronic message 131 with a message header 133 and a document 135 to be signed. The message header will contain a command code specifying the message as a signature request.

2) The authorized agent 1a (figure 9, item 132) strips off the message head and performs some step-by-step checks to determine whether the document should be signed. These specific step-by-step inspections may include the judgment of the human operator AA1a and may vary according to the purpose of the document, and are not closely related to the multi-level signature process itself. When the document should be signed, the authorized agent 1a uses the agent's secret signing key (that is recertified under the SWA signature) to sign the document. As shown in Figure 10, the signature of the authorized agent 1a (--AA1a) is determined by hashing the document and using the secret signature key of AA1a to index the hash result. AA1a then attaches a new message header and sends the post-signature certificate 137 to the authorized agent 1b (for example, the authorized agent 1a is generally for another agent of the same signing device).

3) The authorized agent 1b (figure 9, item 138) strips off the message head and performs some step-by-step inspections (not related to multi-stage signatures) to determine whether the document should be signed. When the certificate should be signed, the authorized agent 1b also signs the document. As shown in Figure 10, the signature of AA1b (--AA1b) is determined as follows: a) The concatenated combination of the hashed document and the signature of AA1b; and the hash result is indexed by the signature key of AA1b. The signature of AA1a remains on the document as an audit record. AA1b then attaches a new header and sends the secondary signature document 139 to the signature device 1 (Figure 9, item 11).

4) The signature device 1 receives the secondary signature document 139, strips off the header and recognizes whether the document carries the necessary number of signatures of its registered authorized agent (two in this example). If so, the signature device 1 strips the authorized agent's signature and attaches a set of partial SWA signatures. As shown in Fig. 10, the basic document (signed by an unauthorized agent) is hashed and the SWA signature key holder 93 of the signature device 1 is used to hash the index to determine the part of the SWA signature (--SD1). The signature device 1 then attaches a new set of headers, and sends a part of the signature document 141 to an authorized agent of another signature device, here is the authorized agent 2a of the signature device 2.

5) The authorized agent 2a (figure 9, item 143) strips off the message head and performs some step-by-step checks (not related to multi-stage signatures) to determine whether the document should be signed. When the certificate should be signed, the authorized agent 2a signs the document. As shown in Figure 10, the decision of AA2a's signature (--AA2a) is as follows: a) The combined combination of the hash certificate and part of the SWA signature (--SD1); and b) The use of AA2a's recertification signature key will be scattered Take the index for the column result. Part of the SWA signature of SD1 remains on the document. AA2a then attaches a new message header and sends the signed certificate 145 to the authorized agent 2b (Figure 9, item 147).

6) The authorized agent 2b (figure 9, item 147) strips off the message head and performs some step-by-step checks (not related to multi-stage signatures) to determine whether the document should be signed. When the document should be signed, the authorized agent 2b will sign the document. As shown in Figure 10, the decision of AA2b's signature (--AA2b) is as follows: a) the hash certificate, part of the SWA signature and the combined combination of the AA1a signature; and b) the use of the AA2b recertification signature key to hash The result is an exponent. This part of the SWA signature and AA1a signature remain on the document. AA1b then attaches a new set of headers and sends the post-signature certificate 149 to the signing device 2 (Figure 9, item 13).

7) The signature device 2 receives the signed document 149, strips off the header and recognizes that the document carries the necessary number of signatures of its registered authorized agent (two in this example). If so, the signing device 2 strips off the signature of its authorized agent and modifies part of the SWA signature to complete the SWA signature. As shown in Fig. 10, the complete SWA signature (--SWA) is determined by using the SWA signature key holder 95 of the signature device 2 to take the index of the partial signature (--SD1) attached by the signature device 1. The signing device 2 then attaches a set of new headers, and sends the partially signed certificate 151 to AA1a (original authorized agent).

In the above example, two sets of signature devices are required to attach a system-wide authorized signature, and each signature device needs to be authorized by two authorized agents. In this system, the total number of signature devices that need to complete a signature can be adjusted when the key holder is generated, and the threshold number of authorized agents for each signature device can also be changed. For example, according to the level of security required by human review, 3 sets of signature devices in 5 groups can be required to complete system-wide authorized signatures, and the number of authorized agents required to authorize a signature device can vary with each signature device.

After establishing one of the above-mentioned multi-level signature procedures, certain core management actions can be taken in accordance with the "consent" of the statutory number of other signature devices authorized by the system-wide authorization key. Some of these management actions are discussed below.

In order to trigger these actions and decisions, the firmware in each tamper-proof signature device will be designed to only reflect the signature commands: 1. In the case of partial signature requirements, use an authorized agent with an appropriate quorum; and 2. In the case of system management changes, use the authority of the entire system itself.

That is, in this preferred embodiment, the relevant requirements on the list of authorized persons or on any signature device shall not be modified except for the consent of the statutory authorized person for a quorum of all signature devices. In some cases, it is an improper burden to obtain the consent of the entire system for certain minor changes, such as authorization to perform code backups. However, compared with the formal commercial volume, it can be expected that such management changes will generally be relatively small and infrequent, and the security requirements of the system should generally be agreed in all cases. Note that in this example, only 4 groups of people are required to sign to (re)certify and (re)register a user.

<u style="single">Parallel signature</u>

Figure 11 shows the document flow of a parallel embodiment of the multi-level signature system. In this figure, it will be assumed that there are a total of three sets of signature devices 169a, 169b, and 169c in the system, and all three sets of signature devices are required to complete the system-wide authority (SWA) signature. It will be understood that the parallel signature can be applied to different numbers of signature devices.

In this parallel method, a document coordinator 161 ("coordinator") receives the document 163 to be signed. The coordinator may be, but not necessarily, the authorized agent of one of the signature devices, but for the sake of generality, the coordinator is shown as a separate entity.

The document coordinator 161 generates three copies of the document 163 to be signed 165a, 165b, 165c (or, three copies of the hash of the document). Each copy is sent to a first authorized agent 167a, 167b, 167c, then to a second authorized agent 171a, 171b, 171c, then to one of the three sets of signature devices 169a, 169b, 169c, and finally back to Coordinator 161. As will be discussed in detail below, the document coordinator combines the respective signatures of the three sets of signature devices and generates a set of system-wide power signatures (--SWA) that are appended to the original document 163 to generate a signed document 173.

Figure 12 shows the processing of one of these copies, and the combination of three sets of partial signatures into the system-wide power signature. It should be understood that, except that different authorized agents and signature devices will add signatures or partial signatures according to their respective signature keys, each of these copies undergoes roughly the same procedure.

In this example, two groups of authorized agents are required to authorize their respective signature devices 169a to attach their signatures. The coordinator 161 sends the first copy 165a of the document to be signed, and a routine information header (not shown) to a first authorized agent 167, which attaches the signature (--AA1a) and will sign the The copy 175a is sent to a group of second authorized agents 171a. The second authorized agent 171a adds a set of second authorized signatures and sends the (second signature) document 179a to the signing device. The signature device 169a recognizes the two groups of authorized signatures, appends its partial signature (--SD1) to the copy, and sends the signed copy 181a back to the coordinator 161.

The second group of other signature devices (not shown) append a partial signature to the copy of the document to be signed and send the signed copy 181b, 181c back to the coordinator. All three sets of copies can be processed in parallel.

After the coordinator receives all three copies of the document to be signed 181a, 181b, and 181c, the coordinator multiplies the three partial signatures (--SD1, --SD2, --SD3) together. The product of the three sets of partial signatures is the system-wide power signature (--SWA).

The smart card and signature device of the authorized agent will become the trust device. The security of this parallel multi-level signature method is not determined by the actual security of the coordinator's workstation. The coordinator does not need to possess any secret keys authorized to the signing device (although it may have routine codes and signing keys for privacy and identification).

The functions of the coordinator can be distributed among authorized agents. A first group of authorized agents can receive the original documents to be signed and designate another group of authorized agents (or another entity that is not an authorized agent, for example, a group of service providers for one of the signing devices) to receive and combine parts Signed. It is expected that the normal operation of the agency will enable the coordinator to preferably receive the documents to be signed, and then be responsible for transmitting the signed documents to their ultimate recipients.

<u style="single">Add/remove authorized agents</u>

Each signature device has an authorized agent of the relevant ethnic group. Because people in and out of the agency, the system uses the public key of the trust device to add and remove authorized agents to dynamically add and remove authorized persons. Adding or removing an authorized agent is accomplished by submitting an order to add or remove an agent's public key to a group of signature devices. The order has the form of an electronic message, which contains a set of numbers as an add/remove order, additional information (discussed below), and authorized signature.

The authorized signature can be from another authorized agent of the same signing device, and the adding/removing procedure can be partially completed by a group of single signing devices. In a different version, the addition/removal step may require the signature of the system-wide power key, and therefore requires a quorum of authorized agents on the relevant signature device to verify and authorize such changes. In another different example, different authorized agents may have different capabilities, and some authorized agents with more power can be added or removed under the system-wide power key, while authorized agents with less power can be a local statutory number. Under its authority, it has been partially added or removed. Preferably, the addition or removal of the authorized agent requires the signature of the system-wide power key.

Figure 13 shows a command 201 to remove an authorized agent. Additional information about the order 203 includes: a) the name of the agent 205; b) the title of the agent 207; c) the ID number of the signature device to be removed 209; and d) the trust device about the authorized agent to be removed The office code 211. After receiving an appropriate signing command, the signing device removes the authorized agent's public identification key from its internal list of authorized agents.

Figure 14 shows the order 213 to add an authorized agent. The additional information includes: a) the name of the agent 217; b) the title of the agent 219; c) the ID number of the signature device authorized by the agent 221; d) the management classification 225 indicating the authorized power of the agent; e ) The expiration date 223 of the power of the new agent; f) The identification code 227 of the master key that the authorized agent may indicate the application of the signature device; g) The ID code 229 of the agent's trust device; and h) The public signature of the trust device One of the identification keys proves 231. Preferably, the public key of the new agent is certified 233 under the authority of the SWA signature key and the certification is included in the order. The device certificate 231, which is signed by the manufacturer of the trust device of the authorized agent, also contains a guarantee that the private signature key of the authorized agent is permanently confined in a smart card or has proven minimum security properties In other trust devices. (Preferably, the minimum security properties of these devices also include life measurement information used to link the smart card to the actual characteristics of the human user. For example, the manufacturer may announce that unless the user activates a set of attached fingerprint reading The card will not generate its user's signature, and the matching fingerprint data is stored in the card and used to activate it.) After receiving an appropriate signature request (that is, after the SWA multi-level signature is completed), the signature device The information of the new agent will be added to its internal list of authorized agents.

<u style="single">Add/remove card manufacturer and type</u>

As mentioned above, authorized agents act via trust devices, which can be smart cards manufactured with predetermined security properties. One of the conditions for adding an authorized agent is that the trust device of the agent must be an approved type. When the system is started, the model of the trust device that will be accepted for use in the system is entered. Usually, the new style will be used, and the safety procedures will be tightened so that the older style is no longer accepted. All signature devices retain the internal list of acceptable types.

New manufacturers can be added by issuing electronic requirements in all signature devices to add a new manufacturer. Figure 15 shows an example of a request. The request contains an order 243, accompanied by the manufacturer's name 245, model or model code 247, and a public signature identification key 249, which are included in a message 241 signed by the system-wide power key.

The old manufacturer can be removed by issuing the electronic request signed by the SWA key to remove the manufacturer's public identification key from the signature device list. Figure 16 shows an example of a requirement including a command 253 and manufacturer name 255. These addition/removal requirements, once signed by a legal number of devices, are sent to all devices and then used<img file="TW307075B_D0009.tif" />Identify them and act on them.

Using an electronic request to send one of the signatures of the SWA key to add a new style can be used to add a new style of an approved manufacturer. Figure 17 shows a request example 261. This requirement will include an order 263; manufacturer's name 265; model number 267 and manufacturer's signed certificate 269, stating that the particular type meets certain safety standards (for example, a type meets FIPS level 3 requirements).

Use the electronic request to send the SWA key to sign in order to remove a form from the signature device list and remove the old form. Figure 18 shows an example of a requirement, which includes: an order 273; manufacturer name 275; and model 277.

<u style="single">Add/remove signature device</u>

Usually, the signature device needs to be removed or added from the system. Each signature device includes a list of other signature devices in the system that holds the SWA key holder (or the holder of the other master key of the multi-level signature, as detailed below). The identification of each signature device is defined as: 1) device identification number (for example, serial number); 2) device public identification key (installed by a manufacturer and certified by the manufacturer's signature, or signed and certified by SWA. Key); 3) Device public code key (used to send coded messages to the device); and 4) Any subsequent proof public key that is uniquely owned.

By issuing an unsigned certificate to other devices to receive the SWA signature and then issuing the signature certificate, a new signature device can be added to the system. The certificate contains the identifying information described above. After the certificate is signed by the SWA key, the certificate is sent to all signature devices, and with an instruction to add the new device to the internal list of other signature devices. FIG. 19 shows a command example 281, which includes a command 283 and a certificate 282. The certificate includes: a new signature device ID code 285; a signature identification key certificate 286 of the signature device (signed by the manufacturer); and a coded key certificate 289 of the signature device (also signed by the device manufacturer). The signature identification key and the coded key can also be included in a single certificate. Other information must be published in other signature devices, such as the identification of the key holder 291 used by the new signature device and the identification of the decryption key holder 292 attached to the new device. Once a signing device is added to the group, it can: 1) participate in the agreement to generate a new set of master keys and receive one of its holdings; 2) serve as a backup unit to receive the contents of a signed SD; or 3) As a replacement unit to receive the restored content of the revised standby signature device that has been destroyed or removed from the service.

Figure 20 shows a message 293 used to remove a signature device. The message 293 includes a command 295 and a device ID code 297.

<u style="single">Copy key holdings</u>

The risk of theft or destruction of the signature device can be reduced because of the multi-stage signature process and the single signature device cannot imitate a signature or reveal the fact that it is sufficient to imitate a signature. The information content of a signature device, including SWA key holdings, for example, can be transferred to another device when the hardware of the signature device is changed or backed up.

The copy of the key holder and other information can be used to send a request, signed by the SWA key, to copy all or some of the information in a specific signing device to a second device. Figure 21a shows an example of requesting a copy of the key holder for a sending device. The request 301 preferably contains: an order 303, signed by the SWA key, identifying the second device manufacturer 305 (it must be included in the list of approved signing devices), model 307 (it must be in the list of approved types) , And the serial number 309; the certificate 311 that the receiving device has a public code key; the ID code 313 of the key to be copied (or the designation of other information); and the sending device ID315. When the signature request is received by the appropriate sending device, the sending device uses the publicly coded key of the receiving device to encode the recognized key holder and related information, and then the encoded information of the sending device is used as an "add key" message. Output to the receiving device. Figure 21(b) shows an example of a message from a sending device to a receiving device. The request 314 preferably includes: a command 316 signed by the sending device (--SD); the receiving device ID317; the sending device ID318; the coded ID code of the key holder 319; and the ID code of the key holder 320. The receiving holding order can also specify a quorum (or other authorization details) for use on the receiving device, but it is preferable that the received key is used according to the original quorum of the receiving device. In a typical operation step, all system operators and authorities will be notified that a copy has been made and accompanied by identification of the storage medium or device storing the copy.

Alternatively, the information can be backed up in encoded form and copied to a storage device that is safe (for example, in a vault) and offline (not subject to remote attack).

<u style="single">Change the quorum requirement</u>

The quorum of the signature device required to attach the SWA key is a system design parameter used by the guided device when generating the key holding. The quorum can be changed in the following ways. First, recombine the key holdings to recover the entire signature key, and then divide the key into an increased number of holdings. They are then redistributed as the original key holdings, but with a new quorum. Require.

The quorum of authorized agents required to authorize a specific signature device to attach a specific signature can be changed without restarting the system. This change is best achieved by sending a request to the respective signature device signed by the SWA key. Or, the authorized agent of a specific signature device can change the partial statutory number by sending a request to be signed by only a partial authorized agent. The number of signatures required to change the quorum can be the same or different from the number required to authorize the signing device to attach SWA signatures. Note that if the SWA key holdings are stored in the signature device in encoded form and if the authorizer retains the following decryption key holdings, the statutory number required for authorizing a signature should not be reduced at least to the decoding of the SWA key holdings The number of shares held. In general banking practice, although certain authorizers may have power on multiple sets of signature devices, the authority's N cannot be less than 2 for each signature device.

<u style="single">Key holdings of the code being saved</u>

In this change, as shown in FIG. 22, each SWA key holder 323 stored in the signature device 321 is stored in a coded form 323. The decoding key ("KEY") is divided into holdings, and the trust devices 325, 327, and 329 of each authorized agent store one holding of the decoding key. As mentioned above, each request for the addition of a set of partial signatures to the signature device must be accompanied by the signature of a quorum authorized agent. In this change, the authorized agent additionally sends one of the decryption keys 331, 333, 335 to the signature device 321. The signature device then: 1) Combine the decoded key holder 337 to restore the decoded key 347; 2) Decode the SWA key holder 339; 3) Use a simple SWA holder 341 to attach a set of partial signatures 343 to a document 345; 4) Eliminate the decoding key 347; 5) Eliminate the holdings 331, 333, 335 of the decoding key; and 6) Eliminate (342) the simple SWA key holdings 341.

When sending a document to a signing device for signature, an authorized agent includes the agent's copy of the decryption key and signs the message. In normal operation, the holding of the decryption key is protected because all communications on the network are encoded using the recipient's public coding key (that is, when a document is published for signature by another authorized agent, Or a public code key of a signing device when sending out a signature request). Alternatively, each authorized agent can develop a key for each message to protect the holding of the decryption key. (That is, whenever a key-containing message is sent from one authorized agent to another authorized agent or to a signing device, a new set of period coded keys are used.) The entire message is then used under the period key coding.

In this way, a pure SWA key holder only temporarily exists when it is used to attach a set of partial signatures. Moreover, the complete combination of the decoding key and the holdings of the decoding key only temporarily exists. If a signature device is stolen, the thief can reply to the coded form of the SWA key holding at most.

The procedure for generating and distributing coded key holdings and decoding key holdings proceeds as follows and is shown in Figure 23.

1) The guiding device generates the holdings 353, 355, 357 of a private SWA signature key and a public SWA identification key 351, the basic changes as described above.

2) The guiding device generates respective public/private coded key pairs 359, 361 for each private share of the SWA signature key (a SWA share 357 is shown, and it should be understood that other holdings are handled similarly).

3) For each private coded key, the guiding device uses a L separation method of M to separate the private decryption key into holdings 363a,...,363m, where M is the total number of holdings and L is the minimum holding required to reconstruct the private decoding key. Number of copies. M can be selected to be equal to the total number of authorized persons on a signature device, and L equal to the legal number of authorized agents required to authorize a signature on the respective SWA key holders.

4) The guiding device encodes each holder of the SWA signature key 357 under the relevant public code key 359, and sends the code holder 365 of the SWA signature key to a respective signature device along with the M holders of the respective private decoding keys.

5) The private decryption key holding of the SWA key can also be delegated conditionally in other signature devices (distributed for safe preservation) so that any private decryption key can be recovered from the signature device, but no set of signature devices contains enough The information can be restored to any decryption key of another device. Such general holdings for any given signature device will be released upon the consent of many other SD quorum authorities.

6) The guiding device removes the private decryption key, the private decryption key holdings, and the entire private SWA signature key (if it still exists) from the memory.

When each signature device registers its respective authorized agent, the signature device additionally sends a copy of the decryption key to each authorized agent, which can be identified by the following two items: 1) One identification number for the decryption key; and 2 ) The identification number of the relevant SWA key holdings.

For example, if there are 5 sets of SWA signature key holdings (only 3 sets for a signature) and each SWA key holding is coded under a separate public coded key, and each SWA key holding requires 5 sets of authorized agents If there are 3 groups, each decoding key will be divided into 5 groups and any 3 groups can reply the decoding key. There are a total of 25 sets of decryption key holdings. Each signature device allocates 5 sets to its authorized agent (as its own key) and reserves one holding of each decryption key to the other 4 sets of devices.

In this way, the authorized agent authorized to a signature device to attach a quorum required for a partial signature will also have a sufficient number of decryption key holdings to allow the signing device to temporarily decode the SWA key holdings for each signature operation.

If one or more groups of authorized agents lose their keys (for example, lose their trust device smart card), the new smart card will be registered on the same signing device. The holding of the decryption key can be returned from other signing devices and can be restored to the newly registered smart card by sending an electronic message signed by the SWA signature key to the signing device to send the holding of the decryption key to the new registration device. Reached. Another method is, with the consent of SWA, a given device can receive all the record holdings, decode the signed holdings, and generate a pair of new coded keys, and then code the signed holdings under the public key to divide the new private The decryption key becomes the new holdings and redistributes these holdings to the trust devices of the relevant authorities, and encodes them under the publicly encoded keys of the trust devices of the receiving authorities.

Another alternative method is that the holdings of the decryption keys described in pending U.S. Patent Application Nos. 08/181,859 and 08/277,438 can be conditioned offline with an independent trust agency.

<u style="single">Cryptographic pulsation</u>

For further protection, each signature device receives a periodic data input ("pulsation"). If interrupted, the signature device will not function. The pulsation is generated from a position away from the signature device, so that if a thief attempts to steal a signature device, they must also enter a separate room or vault to obtain the source of the pulsation. If they do not get the source of the pulsation, the signature device will be inoperative and useless.

In one embodiment, each signature device provides an encoded key to a pulse source. The pulse source periodically sends the coded message to the signing device. If the signature device does not receive the minimum number of messages from the pulsation source after a period of time, the signature device erases its internal memory or takes other evasive actions. These messages can be blank messages or simple messages, and they must be coded by the pulse source using the public key provided by SD. Alternatively, the messages can be a set of pseudo random strings generated by a pseudo random number generator (RNG) in the pulsation source and recognized by a set of synchronous RGNs in the signing device.

Multiple sets of pulsation sources can be established so that a signature device must receive messages from at least one set (or a minimum number) of pulsation sources over a period of time. If a pulsation source is taken offline due to equipment failure or power failure, it will not trigger the hastily erasing of the signature device's memory. The key used for pulse communication can be reserved in multiple locations in a holding mode.

In a second embodiment, each signing device can send a challenge to a group of related ("satellite") devices on the network, and only proceed when at least a quorum of related devices responds. The statutory requirements allow continued operation and response to communications when an inevitable failure occurs.

Although the use of satellite devices is more complicated, it increases actual safety and can be used in places with less safe environments without the need to upgrade equipment such as vaults, security personnel, and monitors.

The communication connection between a signature device and its pulse source or satellite device can be a set of public networks. If a signature device is reported to have been stolen, its associated satellite unit can be deactivated by the system operator to prevent the thief from connecting to the communication line and reconnecting the pulse to the stolen device.

For example, the signature device may be in the United States and its associated satellite device may be in Europe. When the signature device was stolen, the European satellite device was moved offline by its operator. Therefore, the responsibility of the European agent for any wrong actions will be minimal. The previous signature remains in effect. It is also possible to provide a secure physical line between a signature device and its satellite or pulsation source to replace a public network.

<u style="single">Generate another master key</u>

After establishing a secure, multi-level signature system with an SWA key, it is a simple matter to generate some additional "master" keys for other purposes. Although the SWA signature key control system is managed, the master key can be used on behalf of other legal entities to sign other certification messages or documents. The generation and management of other master keys are similar to SWA keys, but there is no intermediate temporary verification step. The method proceeds as follows:

1) Designate a signature device as the "guidance" (it does not need to be the same "guidance" that generates the SWA signature key).

2) Enter an identification code and a logical name of the master key.

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

4) Establish a secure communication channel in the signature device (it is better to use the coded key certificate of each relevant signature device).

5) Obtain random data from each signature device selectively.

6) Generate a new "master" public/private key pair.

7) Allocate private key holdings (selectively encode each holding and allocate the holdings of the decoding key).

8) Eliminate the entire master private key (if it is stored), and eliminate all holdings that are not retained by the guided signature device.

This program can also be used to send an additional command to each signing device, signed by the (old) SWA signature key, and used to replace the SWA signature in order to install the new master key as the SWA signature key. Generally speaking, the master key will have a different purpose than the SWA key and many master keys can be stored in the signature device at the same time. A set of previously generated master keys (different from a set of SWA signature keys) can be removed from the system by sending a message signed by the SWA signature key to remove the master key segment.

<u style="single">Document and signature tracking</u>

It is necessary 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 can be included in the header of each document for use by message servers and authorizers:

1) The signature key identification code of the key that will 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 that have been applied.

3) The key segment identification code that has been used to sign.

4) The identification of the signed signature device (for example, the name of the logical device).

<u style="single">Interlocking ring of signature device</u>

A group of root CAs, using the above-mentioned multi-level signature system, will generally certify CAs located at the lower level of other commercial and government agencies. Hypothetically, the big financial center bank will guarantee the main agent of the state government. The state agent, in turn, can guarantee a company. In this way, the certification procedures are allocated flexibly in a manner consistent with existing political, economic, and social institutions.

However, each intermediate CA must maintain the strong security of its signature key. Some of these institutions, in addition to banks, certain large companies, and certain government agencies, traditionally maintain most high-security data processing equipment and storage vaults. For example, an intermediate CA may have at least one physical location that is nominally safe, such as a data center or vault, but lacks financial resources to serve most locations of the aforementioned multi-device organization. In other cases, the mid-level CA may not have a right and safe location.

A less secure intermediate CA (such as a company CA) may set up their own signature ring (as described above) and link these intermediate rings with the security ring of a more secure superior CA (such as a bank or a security government agency). The above objectives can be achieved when the following themes are separated, (1) key ownership and formal control, (2) management and support responsibilities, and (3) actual ownership of the device.

Using an intermediate CA371 to keep one or more sets of intermediate signature devices 373, 375, 377 in its own secure location can generate a chain ring architecture as shown in Figure 24. The other mid-level signature devices 379, 381 will be kept in a secure location of a higher-level CA383 and may even include some or all of the same devices 379, 381 that form the upper-level (root) CA ring 383 (hence the "chain ring") . The upper-level CA may retain many signature devices 385, 387, and 389 that are not related to any given mid-level CA371. The above-mentioned signature device can retain another master key without additional modification, each of which has a different ownership and is controlled by a separate authorized agent 391a, 391b, and the supplementary master keys are grouped in different ways.

Intermediate CA uses its unique signature device as a "guidance" device to initiate the key generation and share distribution agreement mentioned above, and authorize its unique staff as authorized agents 391b. Some holdings of the new CA master key will reside on the signature devices 373, 375, 377 owned by it, and others will reside on the signature devices of its superior CA379, 381. Although they can also delegate certain powers to certain employees of the higher-level CA in an emergency, the power to issue signatures can only be granted to the employees of the key owner.

Subsequently, the intermediate CA will activate the multi-level signature of the CA's signature based on the signature generated by the smart card owned by the employee, and transmit those requests to their own signature device and/or the device owned by the superior CA. In fact, the signing device does not have to be with the superior CA, but can be in any other CA that also has a secure location and communication access point.

<u style="single">Fully rented service</u>

Even an organization that does not own a security device may want to produce a certificate and become a CA. The institution can rent the use of signature devices that have been established in safe locations by banks or other CAs. The agency will use the smart card of its authorized agent and send the signature request to the signature device via a communication network. The procedures for generating keys, issuing signatures, and performing other management tasks can therefore occur in the device under the actual control of the regional bank in accordance with the contractual trust agreement with the owner.

The staff of the organization will go to the regional security (bank) organization to witness the key generation agreement, which is used to enable their new signature keys to be generated, segmented, and distributed to some of the major organizations they choose (May be other banks or other locations of the same bank). At that time, they can also designate the appropriate management support powers needed.

The agency can then issue official signatures and certifications, without having to establish their own security data centers or vault facilities, and can still roughly achieve the security benefits of the above-mentioned system.

<u style="single">Sign the appointment</u>

When an authorized agent is temporarily out of work (due to vacation, unfitness, etc.), some form of signature power appointment is required. For security reasons, a human operator should not lend his/her smart card 1 and a related private number or key to another person.

One type of appointment agency is for an original authorized agent ("primary user") to issue a specific "appointment" certificate to an alternate authorized agent ("appointer"). The certificate, signed by the main user, will identify the delegator and the delegator's public signature identification key. The appointment certificate will also include the time limit for which the appointment certificate (that is, the power of the appointer) is valid. (See Sudia and Ankney, "Commercialization of Digital Signatures," 1993.) A delegator, using his/her personal smart card, will use the delegator's personal signature key to sign a document and attach a certificate of appointment. The resulting document will be signed by the designated person, not the primary user, and a document recipient must take additional steps to identify the designated person's signature and certification of appointment. This is partly dependent on the ability of all public users of a system to have this recognition ability, and in order to make the right to be deleted before the expiration date, it must also have good access to a discontinued information source (or hotline list") ability.

A preferred method is to allow a delegator to use the smart card of the main user in a safe manner. In fact, the smart card of the main user can be faced by the delegator instead of the main user. Then, the delegator will use the smart card of the main user to attach the signature of the main user, and all document recipients will have the additional burden of identifying and evaluating another complex certificate.

When the main user wishes to delegate the signing authority, the main user issues a "replacement" certificate 409 to the delegate, as shown in Figure 25. This replacement certificate is valid to identify the main user ID411, the delegator ID413, which is used by the main smart card to identify the delegator (probably the delegator's public identification key 417), and the substitute certificate 409 (and therefore the delegate's power) is valid Time limit 415. The main user can identify multiple individuals, any one of them can authorize the smart card, or a group of these multiple individuals must authorize the smart card together. These methods have been discussed in US Patent Nos. 4,868,877, 5,005,200 and 5,214,702 to Addison Fischer.

As shown in FIG. 25, when a delegator wants to sign a document 403 on behalf of the main user, the delegator 401 prepares and signs a request 405 in a specific format for communicating with the main user card 407. Attached to, or otherwise included in the message is a substitute certificate 409. If most appointees need to authorize the main user's card, they can sign the request in order similar to the way that most authorized agents send to the signature device to sign the request. When a signature request is received, the card of the primary user will identify whether the signature of the requested user conforms to the public key originally designated in the replacement certificate, apply the signature of the primary user 419, and send the signature document to a public key in the usual manner. Signing device 421 (or other destination).

The smart card 407 of the primary user can actually be given to a delegator. A "time lock" is provided for the time limit of the power of the delegator, so that the delegator can only use the smart card of the main user for a limited period of time. As mentioned above, the power of the main user is also limited to a fixed period. These restrictions reduce the consequences of theft, and allow the main user and the delegator to store the main user's card in a relatively unsafe office environment. After this period expires, the smart card will not be harmed by any key guessing attacks. (In fact, even if the main user or the delegator writes their private identification code on the card, it will be fine.)

Putting the smart card in a safe or other locked environment, and inserting the card into a card reader that can be accessed electronically but not actually accessed can obtain additional protection against loss or actual attack. In this way, all the actions mentioned above can be performed, but there is no need to actually own the card.

For example, a main user may be a deputy supervisor in charge of purchasing, and he wishes to appoint his specific signing authority to his secretary when he travels to negotiate a pending business. The substitute certificate may specify that his smart card will be issued the deputy supervisor's signature when the following signature requests are received: (a) the secretary, as specified by his substitute certificate; and (b) in the purchasing department Co-signature of any other person who has the main signing authority. The deputy supervisor can leave his card in a card reader in a locked safe.

In order to get the signature of the deputy director, the secretary will prepare the documents to be signed and use his desktop computer terminal to calculate the relevant hash. She will sign the hash, attach the deputy director's public key certificate, and the final recipient will need it and then send them to another purchasing agent as a message. The other purchasing agent jointly signs on the same hash and attaches his public key certificate, along with the authorization certificate granting him the purchasing power. The other purchasing agent sends them to the smart card of the deputy supervisor via a local network in a message. When the deputy director's card also contains a trust copy of the public key of the certification authority that produced these certificates, such as SWA, the deputy director's card will determine that the signatures and certificates are all valid and attach the deputy director's signature to the document. The card may also require all these certificates to be accompanied by a recently signed CRL or a certificate from a regional recognition of the good reputation of the CRL processor.

Such an appointed agency can take advantage of the ability to re-plan the smart card of the main user. The smart card of the main user is a trust device with conventional security features. One of the features must have the security indication of the new instruction (for example, instead of proof), for example, in pending US patent applications 08/181,859 and 08/272,203 The (Sudia) key has conditional superiors and Sudia key has conditional CIP).

The above-mentioned authorization agencies can be generalized so that many high-value end-user digital signature keys are actually generated and used in the tamper-proof security module (TRSM) stored in the security vault or data center, and the authorization of these signatures comes from the Give unofficial (time-locked) smart cards the signature request message signed by their approved users. These TRSMs will maintain the security of tamper-proof to prevent any data center personnel from accessing the user's private key, but can be designed to contain keys of many different users, and each group can be signed according to some single informal signature, or signature and Authorize a certain predetermined combination of authorized actions.

For another use of the authorized agency, in addition to the simple appointment from the user when temporarily away, it can also be a system or method, in which such a programmable signature request can be made to a card (or to a card containing a common TRSM The key is proposed) in order to sign a major "table" or other role in a financial or corporate environment.

After the above-mentioned embodiments, those skilled in the art will be able to make some changes without departing from the spirit and scope of the present invention. The above-mentioned embodiments are only examples and are not intended to unduly limit the scope of the present invention defined by the scope of the following patent applications.

<p>11,13,15,17,19,39Signature device</p><p>23,25,27,29,31Authorized Agent</p><p>21Local Area Network</p><p>48Data Center</p><p>47Message Server</p><p>36Key Hold</p><p>37Signature Key</p><p>38Agent List</p><p>40Public identification key</p><p>49System Record</p><p>51Terminal</p><p>53Card Reader</p><p>55Secure Smart Card</p><p>42Input/Output Circuit</p><p>32,33,34,35Public/private key pair</p><p>44Microcontroller</p><p>46Crypt Unit</p><p>48Trust Clock</p><p>50Random Number Generator</p><p>52Memory</p><p>43System Firmware</p><p>45Manufacturer certification device key</p><p>47User Key</p><p>49Application Firmware</p><p>54Working area</p><p>61Temporary Administrator</p><p>65Public signature and identification key</p><p>67,69,71,73,75,92Private signature key</p><p>68,70,72,74,76Signature key certificate</p><p>93,95,97,99,101holdings</p><p>91Full system authorization certificate key</p><p>103Unsigned certificate</p><p>121,123,125,111Proof</p><p>113Record</p><p>131Electronic Message</p><p>133Information Head</p><p>135,137,139,141,151,145,149Document</p><p>132,138,143,147Authorized Agent</p><p>161Document Coordinator</p><p>163,173File</p><p>165a,165b,165ccopy/hash</p><p>167a,167b,167cauthorized agent</p><p>171a,171b,171cauthorized agent</p><p>169a,169b,169csignature device</p><p>179aFile</p><p>Copy of 181a, 181b, 181c</p><p>201,213,241,251,261Order</p><p>203Removal of Agent Order</p><p>205Name of Agent</p><p>207Agent Title</p><p>271,281,293,301,314Order</p><p>331,333,335holdings</p><p>325,327,329Authorized agent trust device</p><p>321Signature device</p><p>347Decoding Key</p><p>341holding</p><p>343Partial signature</p><p>345File</p><p>351Identifying the key</p><p>353,355,357holdings</p><p>359,361Coded key pair</p><p>363a,...363mholding</p><p>365Code holding</p><p>371Intermediate CA</p><p>373,375,377,379,381Intermediate signature device</p><p>383Advanced CA</p><p>385,387,389Signature device</p><p>391a, 391bAuthorized Agent</p><p>409replacement certificate</p><p>411User ID</p><p>413Delegator ID</p><p>415Time Limit</p><p>417Key Recognition</p><p>401Delegator</p><p>403File</p><p>405Requirement</p><p>407User Card</p><p>419User signature</p><p>421Signature device</p>