Public key/signature cryptosystem with enhanced digital signature certification

Claims

I claim:

1. In a communication system having a plurality of terminal devices coupled to a channel over which users may exchange messages, at least some of said user's having a public key and an associated private key, a method for controlling authority in a hierarchical manner among a group of users, comprising the steps of:

specifying at least first and second digital authority defining data structures, said data structures having digital values which can be associated with at least one user's private key,

said step of specifying including the step of

digitally specifying a set of authorities from a sufficient plurality of authorities so that a first user may digitally delegate authorities to second and third users so that the authorities delegated to the second user are different than those delegated to the third user, providing that the first user's digital authority defining data structure allows for such delegation; and

digitally signing by the first user the second digital data structure so that signatures performed by the second user's private key associated with the second data structure will be recognized upon an electronic analysis of the digital signature as having been granted said authority by the first user in accordance with the first user's authority-defining data structure.

2. A method according to claim 1, wherein said step of specifying includes the steps of delegating the authority to cancel a digital certificate on behalf of the certifier and to subauthorize authority on behalf of the certifier.

3. A method according to claim 1, wherein said step of specifying includes the step of defining the security or clearance level of the signer of an authority defining data structure.

4. A method according to claim 1, wherein said authority defining data structure defines the cosignature requirements which must accompany the signer's signature.

5. A method according to claim 4, wherein a digital signature by a third party indicating approval of the user's signature is required thereby defining a counter signature requirement.

6. A method according to claim 4, wherein the step of defining cosignature requirements includes the step of specifying at least one other digital signature which is required to appear in the authority defining data structure thereby defining a joint signature requirement.

7. A method according to claim 1, further including the steps of:

creating a hash value of a message to be transmitted based on the exact bit-for-bit data to be transmitted;

creating an auxiliary hash value designed to verify the genuineness of a printed version of the message; and

incorporating both hash values as part of the digital signature.

8. In a communications system for exchanging messages over a communications channel, a method of digitally signing a message to be transmitted comprising the steps of:

creating a digital hash value of the message to be transmitted based on the exact bit-for-bit data to be transmitted;

creating an auxiliary digital hash value to permit subsequent verification of the genuineness of a printed version of the message; and

incorporating both hash values as part of a digital signature.

9. A method according to claim 8, wherein said step of creating an auxiliary digital hash value includes the step of processing a digital representation of said message to reduce the message to a predetermined underlying character set.

10. A method according to claim 9, wherein said predetermined underlying character set is ASCII.

11. A method according to claim 8, wherein said step of creating an auxiliary hash value includes the step of:

changing all tab characters in at least a first portion of the message into blanks.

12. A method according to claim 8, wherein said step of creating an auxiliary hash value includes the step of:

eliminating control characters in at least a first portion of the message which do not produce a printable character.

13. A method according to claim 8, wherein said step of creating an auxiliary hash value includes the step of:

changing in at least a first portion of the message information which will result in the printing of one or more blanks to blanks.

14. A method according to claim 8, wherein said step of creating an auxiliary hash value includes the step of:

eliminating leading and trailing blanks in at least a first portion of the message; and

eliminating lines in the message which are totally blank.

15. A method according to claim 8 wherein said step of creating an auxiliary hash value includes the step of:

changing multiple contiguous blanks in the message to a single blank.

16. A method according to claim 8 wherein said step of creating an auxiliary hash value includes the steps of:

processing the message on a line by line basis and appending control information to the processed line information to delineate the end of a line.

17. A method according to claim 8, further including the step of verifying the genuineness of a printed document containing said message using said auxiliary hash value.

18. A method according to claim 17, wherein said step of verifying the genuineness includes the steps of:

entering the body of said message;

computing a white-space-hash value for said entered body of the message;

entering the digital signature from said printed version of said document; and

comparing the white-space-hash value from said digital signature with said computed white-space-hash value.

19. A method according to claim 8, further including the steps of:

creating said digital signature with a designated certificate;

verifying the genuineness of a document containing said message by:

entering the digital signature on a printed document and the seal associated with said digital signature;

computing the hash of said digital signature to generate a first value;

processing the hash of said seal with the signer's public key to generate a second value; and

comparing the first value with the second value to determine whether the document was signed with the designated certificate.

20. In a communications system for exchanging messages over a communications channel, apparatus for digitally signing a message to be transmitted comprising:

means for creating a digital hash value of the message to be transmitted based on the exact bit-for-bit data to be transmitted;

means for creating an auxiliary digital hash value to permit the subsequent verification of the genuineness of a printed version of the message; and

means for incorporating both hash values as part of a digital signature.

21. Apparatus according to claim 20, wherein said means for creating an auxiliary digital hash value includes means for processing a digital representation of said message to reduce the message to a predetermined underlying character set.

22. Apparatus according to claim 10, wherein said predetermined underlying character set is ASCII.

23. Apparatus according to claim 20, wherein said means for creating an auxiliary hash value includes:

means for eliminating control characters in the message which do not produce a printable character.

24. Apparatus according to claim 20, wherein said means for creating an auxiliary hash value includes:

means for changing information which will result in the printing of one or more blanks to blanks.

25. Apparatus according to claim 20, wherein said means for creating an auxiliary hash value includes:

means for eliminating leading and trailing blanks in the message; and

means for eliminating lines in the message which are totally blank.

26. Apparatus according to claim 20, wherein said means for creating an auxiliary hash value includes:

means for changing multiple contiguous blanks in the message to a single blank.

27. Apparatus according to claim 20, further including means for verifying the genuineness of a printed document containing said message using said auxiliary hash value.

28. Apparatus according to claim 27, wherein said means for verifying the genuineness includes:

means for entering the body of said message;

means for computing a white-space-hash value for said entered body of the message;

means for entering the digital signature from said printed version of said document; and

means for comparing the white-space-hash value from said digital signature with said computed white-space-hash value.

29. Apparatus according to claim 20, further including:

means for creating said digital signature with a designated certificate verifying the genuineness of a document containing said message by:

means for entering the digital signature on a printed document and the seal of a representation of said signature;

means for computing the hash of said digital signature to generate a first value;

means for processing the hash of said seal with the signer's public key to generate a second value; and

means for comparing the first value with the second value to determine whether the document was signed with the designated certificate.

30. In a communications system for exchanging messages over a communication channel, a method for digitally signing said messages comprising the steps of:

assembling a digital package including a group of related but distinct message portions;

creating a digital list of the distinct message portions to be signed; and

processing a digital representation of at least said list of distinct message portions with the signer's private key, such that said distinct message portions are individually verifiable as having been signed and are verifiable as being a member of said group, whereby a plurality of distinct documents maybe organized, processed and signed as a package.

31. A method according to claim 30, further including the steps of:

computing a hash value for a plurality of the distinct message portions to be transmitted;

storing the hash values in said list of distinct message portions.

32. A method according to claim 30, wherein said processing step includes the step of:

computing a hash value reflecting at least said list of related message portions or hashes of the message portions; and

creating a seal for the signature with said hash value.

33. A method according to claim 31, including the step of computing an auxiliary hash value for at least one of said distinct message portions; and

incorporating both said hash value and said auxiliary hash value as part of the digital signature for said digital package.

34. A method according to claim 33, wherein said auxiliary hash value is a white-space-normalized hash value.

35. A method according to claim 30, wherein said step of assembling a digital package includes the step of creating a signature definition for said package.

36. A method according to claim 30, wherein said step of assembling a digital package includes the step of including at least one digital certificate portion in said package for permitting a recipient to determine that the signature is valid and properly authorized.

37. A method according the claim 30, wherein said step of assembling include the step of assembling a digital representation of a cover letter and an associated enclosed letter to be transmitted.

38. A method according to claim 30, wherein said step of assembling includes the step of assembling a digital representation of a cover letter and at least one digital data file.

39. A method according to claim 31, including the step of verifying that the digital package is genuine upon receipt of said package including the steps of:

calculating the hash value for at least a plurality of said related message portions; and

comparing the calculated hash values with corresponding values in the list of related message portions.

40. A method according to claim 31 further including the step of verifying that the digital package is genuine upon receipt of said package; said step of verifying including the step of verifying that the digital signature actually used to sign the package represents the valid digital signature for the package.

41. A method according to claim 40, wherein the step of verifying the digital signature includes the step of determining that a designated private key was used to sign each of the received message portions in the order shown in the received digital signature.

42. A method according to claim 30, including the step of verifying at least one of the message portions individually by using only the digital signature of the package.

43. In a communication system for exchanging messages over a communication system, apparatus for digitally signing said messages comprising:

means for assembling a digital package including a group of related but distinct message portions;

means for creating a digital list of the distinct message portions to be signed; and

means for processing a digital representation of at least said list of distinct message portions with the signer's private key, such that said distinct message portions are individually verifiable as having been signed and are verifiable as being a member of said group, whereby a plurality of distinct documents may be organized, processed and signed as a package.

44. Apparatus according to claim 43, further including:

means for computing a hash value for at least a plurality of the distinct message portions to be transmitted; and

means for storing the hash values in said list of distinct message portions.

45. Apparatus according to claim 43, wherein said means for processing includes:

means for computing a hash value reflecting at least said list of related message portions or hash values thereof and means for creating a seal for the signature.

46. Apparatus according to claim 44, including means for computing an auxiliary hash value for at least one of said distinct message portions; and

means for incorporating a hash value and said auxiliary hash value as part of the digital signature for said digital package.

47. Apparatus for according to claim 46, wherein said auxiliary hash value is a white-space-normalized hash value.

48. Apparatus according to claim 43, wherein said means for assembling a digital package includes means for creating a signature definition for said package.

49. Apparatus according to claim 43, wherein said digital package includes at least one digital certificate portion in said package for permitting a recipient to determine that the signature is valid and properly authorized.

50. Apparatus according to claim 43, wherein said digital package includes a digital representation of cover letter and an associated enclosed letter to be transmitted.

51. Apparatus according to claim 43, wherein said digital package includes a digital representation of a cover letter and at least one digital data files.

52. Apparatus according to claim 44, including means for verifying that the digital package is genuine upon receipt of said digital package including:

means for calculating the hash value for at least a plurality of said related message portions; and

means for comparing the calculated hash values with corresponding values in the list of related message portions.

53. Apparatus according to claim 43 further including means for verifying that the digital package is genuine upon receipt of said package, said means for verifying including means for verifying that the digital signature actually used to sign the package represents the valid digital signature for the package.

54. Apparatus according to claim 53, wherein the means for verifying the digital signature includes means for verifying that a designated private key was used to sign each of the received message portions in the order of shown in the received digital signature.

55. In a communication system for exchanging messages over a communications channel, a method of digitally signing a message to be transmitted comprising the steps of:

creating a digital hash value of the message to be transmitted designed to permit subsequent verification of the genuineness of a printed version of the message including the step of processing the digital message to reduce the message to a predetermined underlying character set; and

incorporating said digital hash value as part of a digital signature.

56. A method according to claim 55, wherein said underlying character is ASCII.

57. In a communication system having a plurality of terminal devices coupled to a channel over which users may exchange messages, at least some of said user's having a public key and an associated private key, a method for controlling authority in a hierarchical manner among a group of users, comprising the steps of:

specifying at least first and second digital authority defining data structures, said data structures having digital values which can be associated with at least one user's private key,

wherein said step of specifying includes the step of

digitally specifying a set of authorities to allow a first user to digitally delegate authority to a second user, said delegated authorities allowing said second user to further digitally delegate authority to a third user; and

digitally signing by the first user the second digital data structure so that signatures performed by the second user's private key associated with the second data structure will be recognized upon an analysis of the digital signature as having been granted said authority by the first user in accordance with the first user's authority-defining data structure.

58. A method according to claim 57, wherein said authority defining data structure defines the cosignature requirements which must accompany the signer's signature.

FIELD OF THE INVENTION

This invention relates to a cryptographic communications system and method. More particularly, the invention relates to a public key or signature cryptosystem having improved digital signature certification for indicating the identity, authority and responsibility levels associated with at least the sender of a digital message.

BACKGROUND AND SUMMARY OF THE INVENTION

The rapid growth of electronic mail systems, electronic funds transfer systems and the like has increased concerns over the security of data transferred over unsecured communication channels. Cryptographic systems are widely used to insure the privacy and authenticity of messages communicated over such insecure channels.

In a conventional cryptographic system, a method of encryption is utilized to transform a plain text message into a message which is unintelligible. Thereafter, a method of decryption is utilized for decoding the encrypted message to restore the message to its original form.

Conventional crypotographic signature and authentication systems typically utilize a "one way" hashing function to transform the plain text message into a form which is unintelligible. A "hashing" function as used herein is a function which can be applied to an aggregation of data to create a smaller, more easily processed aggregation of data.

An important characteristic of the hashing function is that it be a "one-way" function. A hash is a "one-way" function which should be computationally easy to compute give the underlying data. The hash function should be computationally impossible given a hash value, to either determine the underlying data, or to create any data which has the specified value as its hash. For all practical purposes, the value obtained from applying the hashing function to the original aggregation of data is an unforgeable unique fingerprint of the original data. If the original data is changed in any manner, the hash of such modified data will be different.

In conventional cryptographic systems, binary coded information is encrypted into an unintelligible form called cipher and decrypted back into its original form utilizing an algorithm which sequences through encipher and decipher operations utilizing a binary code called a key. For example, the National Bureau of Standards in 1977 approved a block cipher algorithm referred as the Data Encryption Standard (DES). Data Encryption Standard, FIPS PUB 46, National Bureau of Standards, Jan. 15, 1977.

In DES, binary coded data is cryptographically protected using the DES algorithm in conjunction with a key. Each member of a group of authorized users of encrypted computer data must have the key that was used to encipher the data in order to use it. This key held by each member in common is used to decipher the data received in cipher form from other members of the group.

The key chosen for use in a particular application makes the results of encrypting data using the DES algorithm unique. Selection of a different key causes the cipher that is produced for a given set of inputs to be different. Unauthorized recipients of the cipher text who know the DES algorithm, but who do not have the secret key, cannot derive the original data algorithmically.

Thus, the cryptographic security of the data depends on the security provided for the key used to encipher and decipher the data. As in most conventional cryptographic systems the ultimate security of the DES system critically depends on maintaining the secrecy of the cryptographic key. Keys defined by the DES system include sixty-four binary digits of which fifty-six are used directly by the DES algorithm as the significant digits of the key and eight bits are used for error detection.

In such conventional cryptographic systems, some secure method must be utilized to distribute a secret key to the message sender and receiver. Thus, one of the major difficulties with existing cryptographic systems is the need for the sender and receiver to exchange a single key in such a manner that an unauthorized party does not have access to the key.

The exchange of such a key is frequently done by sending the key, prior to a message exchange, via, for example, a private courier or registered mail. While providing the necessary security such key distribution techniques are usually slow and expensive. If the need for the sender and receiver is only to have one private message exchange, such an exchange could be accomplished by private courier or registered mail, thereby rendering the cryptographic communication unnecessary. Moreover, if the need to communicate privately is urgent the time required to distribute the private key causes an unacceptable delay.

Public key cryptographic systems solve many of the key distribution problems associated with conventional cryptographic systems. In public key cryptographic systems the encrypting and decrypting processes are decoupled in such a manner that the encrypting process key is separate and distinct from the decrypting process key. Thus, for each encryption key there is a corresponding decryption key which is not the same as the encryption key. Given the knowledge of the encryption key, it is not feasible to compute the decryption key.

With a public key system, it is possible to communicate privately without transmitting any secret keys. The public key system does require that an encryption/decryption key pair be generated. The encryption keys for all users may be distributed or published and anyone desiring to communicate simply encrypts his or her message under the destination user's public key.

Only the destination user, who retains the secret decrypting key, is able to decipher the transmitted message. Revealing the encryption key discloses nothing useful about the decrypting key, i.e., only persons having knowledge of the decrypting key can decrypt the message. The RSA cryptographic system which is disclosed in U.S. Pat. No. 4,405,829 issued to Rivest et al discloses an exemplary methodology for a practical implementation of a public key cryptographic system.

A major problem in public key and other cryptographic systems is the need to confirm that the sender of a received message is actually the person named in the message. A known authenticating technique utilizing "digital signatures" allows a user to employ his secret key to "sign a message" which the receiving party or a third party can validate using the originator's public key. See for example U.S. Pat. No. 4,405,829.

With the advent of such digital signatures, it is now possible for any digital message to be signed so that the recipient is assured that the message is received as sent, and that it is not a forgery. This is done by using the "public key" and digital signature methodology such as described by at least U.S. Pat. No. 4,405,829, hereinafter referred to as RSA technique. There are other public key and signature techniques which use methodologies other than RSA. Examples of other public key or signature techniques include Fiat-Shamir, Ong-Schnorr-Shamir, and several others derived from zero-knowledge proof techniques. While none of these other techniques include the privacy capabilities of RSA, they do allow for digital signatures. The present invention is not limited to any particular public key or signature technique.

A user who has filed a public key in a publicly accessible file can digitally sign a message by "decrypting" (or "signing") the message or a hash of it with the user's private key before transmitting the message. Recipients of the message can verify the message or signature by encrypting it with the sender's public encryption key. Thus, the digital signature process is essentially the reverse of the typical cryptographic process in that the message is first decrypted and then encrypted. Anyone who has the user's public encryption key can read the message or signature, but only the sender having the secret decryption could have created the message or signature.

In general, the digital signature assures the recipient of the integrity of the message at the time the signature was computed. However, the authenticity of the signer is only assured to the extent that the recipient is assured that the public key used to sign the digital message actually belongs to the purported sender. This issue becomes more important as the use of digital signatures become more widespread, and the various correspondents (perhaps otherwise unknown to each other) obtain one another's public keys through centrally maintained "directories" (or any other means).

Thus, serious problems still persist in public key cryptosystems of assuring that a specified public key is that actually created by the specified individual. One known technique for addressing this problem is to rely on some trusted authority, e.g., a governmental agency, to insure that each public key is associated with the person claiming to be the true author.

The trusted authority creates a digital message which contains the claimant's public key and the name of the claimant (which is accurate to the authority's satisfaction) and a representative of the authority signs the digital message with the authority's own digital signature. This digital message, often referred to as a certificate, is sent along with the use of the claimant's own digital signature. Any recipient of the claimant's message can trust the signature, provided that the recipient recognizes the authority's public key (which enables verification of the authority's signature) and to the extent that the recipient trusts the authority.

Certificates can be thought of as brief messages which are signed by the trusted authority, and which contain, either explicitly or implicitly, a reference to the public-key which is being therein certified, and the identity of the public key's owner (creator). In such an implementation, if "C" has provided a certificate for "A"; then recipient "B" can trust the use of "A's" public key, provided that "B" trusts "C", and provided that "B" possesses "C's" certification of "A's" public key.

In conventional communication systems, the transmitted certificate does not provide any indication of the degree of trust or the level of responsibility with which the sender of the message is empowered. Instead, the certification merely indicates that the identified trusted authority recognizes the sender's public key as belonging to that person.

The public key system is designed to operate such that the public keys of various users are published to make private communications easier to accomplish. However, as the number of parties who desire to use the public key system expands, the number of published keys will soon grow to a size where the issuing authority of the public keys can not reasonably insure that the parties whose public keys are published are, in fact, the people who they are claiming to be. Thus, a party may provide a public key to be maintained in the public directory under the name of the chairman of a major corporation, e.g., for example, General Motors Corporation. Such an individual may then be in a position to receive private messages directed to the chairman of General Motors or to create signatures which ostensibly belong to the impersonated chairman.

There are also technologies for producing digital signatures which may not require full public key capability, including, for example, the Fiat-Shamir algorithm. Any reference to public key cryptosystems should also be construed to reflect signature systems. Any reference to public key decryption should be taken as a generalized reference to signature creation and any reference to encryption should be taken as a reference to signature verification.

The present invention addresses such problems with public key or signature cryptographic systems relating to authenticating the identity of the public key holder by expanding the capabilities of digital signature certification. In this regard, a certification methodology is utilized which employs multiple level certification while at the same time indicating the "authority" of the individual whose signature is being certified as will be described in detail below. As used herein, an indication of "authority" broadly refers to any indication of power, control, authorization, delegation responsibilities or restrictions placed thereon through the use of digital signatures or certificates.

The present invention enhances the capabilities of public key cryptography so that it may be employed in a wider variety of business transactions, even those where two parties may be virtually unknown to each other.

The present invention advantageously provides the ability to specify a variety of attributes associated with the certification. These attributes extend beyond merely assuring the correct identity of an individual, and actually specify the authority or constraints (in a wide variety of situations) which are conferred on the certifiee by certifier.

For example, the present invention allows a corporation to not only certify that a particular public key is used by a particular employee, but also allows that corporation to explicitly state the authority which it has granted that individual in the context of his employment, and use of that key on the corporation's behalf.

The types and classes of authority which are granted are not limited. In the present invention, a digital signature is certified in a way which indicates the authority the has been granted to the party being certified (the certifiee). The certifier in constructing a certificate generates a special message that includes fields identifying the public key which is being certified, and the name and other identification of the certifiee. In addition, the certificate constructed by the certifier includes the authority which is being granted and limitations and safeguards which are imposed including information which reflects issues of concern to the certifier such as, for example, the monetary limit for the certifiee and the level of trust which is granted to the certifiee. The certificate may also specify co-signature requirements as being imposed upon the certifiee. Some of the more practical classes of authority and/or limitations thereon contemplated by the present invention are summarized below:

A certificate may include the monetary amount which a certified employee is able to authorize using a particular digital signature. Such a limitation will become increasingly important as more and more business is transacted electronically over digital networks. Since this limitation is "built-in" to the certificate, it allows any recipient to know immediately whether, for example, a digitally-signed purchase order is valid.

The present invention may also require digital "co-signatures" to be used whenever a particular certified public key is used. The term "co-signature" is used to encompass either "joint" or "countersignatures". As used herein, joint signatures are signatures which are applied directly to the same "object" (e.g., document purchase order), whereas counter signatures are signatures which are applied to another signature. In principle, joint signatures can be applied "in parallel", in any order, whereas a counter signature specifically "ratifies" an existing signature. Thus, the digital signature certification method and apparatus of the present invention provides for a hierarchy of certifications and signatures. With respect to co-signature requirements, counter-signature and joint-signature requirements are referenced in each digital certification to permit business transactions to take place electronically, which heretofore often only would take place after at least one party physically winds his way through a corporate bureaucracy. This will allow an organization to mimic, for example, the current practice of requiring multiple signatures to authorize spending (or any other sensitive purpose that may be deemed appropriate). Since this requirement is built into the digital certificates of the present invention, it will be clear to the receiver when (one or more) co-signatures are required, and the recipient (or the recipient's software) can determine whether the necessary appropriate co-signatures are present.

The present invention further provides for certifying digital signatures such that the requirement for further joint certifying signatures is made apparent to any receiver of a digital message. The requirement for joint signatures is especially useful, for example, in transactions where money is to be transferred or authorized to be released. To accomplish this end, the certificate of the present invention is constructed to reflect (in addition to the public key and the name of the certifiee and other fields) the number of joint signatures required and an indication as to the identity of qualifying joint signers. Thus, an explicit list of each of the other public key holders that are required to sign jointly may be included in the certificate. In this fashion, the rec