Cryptography – Key management – Key escrow or recovery
Reexamination Certificate
1998-12-23
2002-06-25
Barron, Jr., Gilberto (Department: 2767)
Cryptography
Key management
Key escrow or recovery
C380S030000, C713S180000
Reexamination Certificate
active
06411716
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to multi-step digital signature systems. More particularly, the present invention relates to the management of the cryptographic keys used by certification authorities in multi-step digital signature systems.
BACKGROUND OF THE INVENTION
Historically, written documents have been used by parties to record for future reference, or to conduct, commercial transactions when the parties are either unable, or find it undesirable, to meet face to face. Written contracts and other commercial papers continue to account for the bulk of all commercial transactions. As a result, procedures have been developed and currently exist for verifying the identity of the parties who have engaged in a written commercial transaction. The most fundamental of these procedures is the requirement that each ascribing party obtain a notary stamp verifying their individual handwritten signatures. By requiring that this procedure be used, each party to the transaction can be assured of having a signature of the other contracting party which, if the need arises, can be independently verified by handwriting analysis. Further, each party has the added security of the notary who attested to the signing of the document and who can be called upon to verify the identity of a signatory to the document.
As the availability of electronic communication technology continues to grow, companies, such as large financial institutions, have shown great interest in applying such technologies to their day-to-day commercial transactions. The use of such electronic communication technology advances in modern commercial transactions has been hampered, however, by the relative ease within which electronic messages can be altered or forged and the difficulty encountered in verifying the integrity of both the received information and the identity of the party sending the transmission. Without a means for verifying both the integrity and the author of an electronic transmission, such transmissions would be unusable in a commercial setting. As a result, systems have been proposed to prevent the alteration and forging of electronic communications and to enable the verification of the identity of the transmitting party. One class of these systems relies on asymmetric-key cryptography wherein each member of the system creates a private signature key, which is maintained in strict secrecy, and a corresponding verification key which is publicly disseminated. When a first party, called the signer, wishes to sign a message, the signature is created using the message and the signer's own private signature key. A second party, called the verifier, can then verify the signature by performing a computation using the signer's public verification key, the message, and the signature. The properties of these computations assure the verifier that the document has been unchanged since it was signed. One such asymmetric-key cryptographic system is described in U.S. Pat. No. 4,405,829.
One problem encountered in asymmetric-key cryptographic systems is the need for a verifier to be assured that a public verification key belongs to a particular signer. Without such assurance, a verifier will have no way of discerning whether a message has in fact been sent by an intended signer or has been “forged” by a third party claiming to be that signer. This identification problem has been ameliorated in some systems through the use of a certification authority (CA). The CA produces a “root” verification key that is made widely available in a manner in which users can be assured that they have a correct copy of the root verification key. Then a signer can have their verification key “certified” (i.e., signed) by the CA, specifically by the CA root signature key. After verifying the signature on the document, a verifier can also verify the signature on the signer's verification key and is thereby assured of the identity of the signer.
The strength of the foregoing cryptographic system typically resides in the computational infusibility of deriving a signature key from knowledge of either the verification key or signed messages. Thus, so long as the signature key is kept secret, the signers have some assurance that documents cannot be forged in their name, and the verifiers have some assurance that documents bearing the electronic signature of the signer were in fact generated by the signer.
It is critical in these systems, however, that the respective signature keys of the signer and CA continue to be maintained in strict secrecy. Any compromise of the secrecy of these keys results in a breakdown of the integrity of the system. If a user's signature key is compromised, the CA must be notified to revoke the certificate and reissue a new one. If a CA's private signature key is compromised, all users who might rely on that key must be notified, all outstanding certificates must be revoked, the CA must generate a new asymmetric key pair, all users must be recertified, and the CA must broadly distribute its new public verification key. This is particularly a problem for the root verification key, because this key would likely be made available to, and potentially be relied upon by, millions of users. Such a loss can impose a great burden on the system. For such a key, a single fraudulent signature can cause substantial losses for a corporation.
In order to further ameliorate the problem of trying to protect a single private key, a system and method have been described for generating private key fragments for the root certification authority and then distributing these fragments amongst a number of members of a multi-step signing group. In accordance with this system and method, the private key for the root certification authority never exists in toto at any time. This system and method are disclosed in the co-pending U.S. patent application Ser. No. 08/462,430 (the '430 application), filed Jun. 5, 1995.
In the system and method of the '430 application, a private root signature key is fragmented and each of the fragments is distributed to a different member of a signature group. The message to be signed is distributed to each of the members of the signature group, either serially or in parallel, and the message is signed by each member using its fragment of the private root signature key. When a message has been signed by all members and thus, using all fragments, a final signature is formed which can be verified using a single public verification key. Further, because all fragments of the private root signature key are maintained in separate devices at separate locations at all times, security of the key is enhanced.
Each member of the multi-step signature group takes significant precautions to maintain the secrecy of the key fragment in their possession. This makes it physically infeasible to acquire all of the private key fragments and, because it is computationally infeasible to derive the signature key from the verification key or from a set of messages signed with the signature key, this system offers a greater barrier to would be adversaries.
The foregoing multi-step signature system and method represents a significant improvement over prior asymmetric-key cryptographic systems. A loss of one or more, but less than some specified amount k, of the key fragments will not compromise the integrity of a multi-step system. Improvements to the foregoing system are still desirable, however, for changing the key fragments in response to system events such as the actual or suspected compromise of a key, the addition or removal of key fragment holders, the need to modify the key fragments, a change in the number of fragment holders required to sign, or a loss of a key fragment. Using current, standard technology, such events will require generation of new CA keys, revocation and reissuance of all certificates, redistribution of the CA's new public verification key, a change of the private and public keys and notification to all potentially affected users. A need still exists, therefore
Barron Jr. Gilberto
Certco, Inc.
LandOfFree
Method of changing key fragments in a multi-step digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of changing key fragments in a multi-step digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of changing key fragments in a multi-step digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917391