 |
Description  |
|
|
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 recipient is informed
that any material which is signed by the authority of the sender's
certificate, must also be signed by a number of other specified signators.
The recipient is therefore able to verify other joint and counter
signatures by simply comparing the public keys present in each signature
in the certificate. The present invention also includes other ways of
indicating co-signature requirements such as by referencing other
certificates. Such indications of other public key holders may be explicit
(with a list as described here), or implicit, by specifying some other
attribute or affiliation. This attribute or affiliation may also be
indicated in each co-signer's certificate.
The present invention contemplates building "clearance" levels into the
certificate. For example, this allows the military (or any organization
concerned about security), to incorporate security into their
certificates. This feature allows for the confirmation of the exact
security level of the person who authored a signed message.
Conversely, and perhaps more important, is the ability to provide an
additional level of checking when sending digital messages: when messages
are encrypted (a process which also requires a recipient's public key and
therefore the recipient's certificate) the computer system embodying the
present invention will be able to insure that all recipients have the
proper security authorization to receive a particular message containing
sensitive information.
Additionally, the present invention provides for the certification of
digital signatures such that a trust level is granted to the recipient for
doing subcertifications. In this manner, a trust level of responsibility
flows from a central trusted source.
In an exemplary embodiment of the present invention, a certifier is
permitted to assign with one predetermined digital code, a trust level
which indicates that the certifier warrants that the user named in the
certificate is known to the certifier and is certified to use the
associated public key. However, by virtue of this digital code, the user
("certifiee") is not authorized to make any further identifications or
certifications on the certifier's behalf. Alternatively, the certifier may
issue a certificate having other digital codes including a code which
indicates that the user of the public key is trusted to accurately
identify other persons on the certifier's behalf and (perhaps) is even
further trusted to delegate this authority as the user sees fit.
The present invention further provides for a user's public key to be
certified in multiple ways (e.g., certificates by different certifiers).
The present invention contemplates including the appropriate certificates
as part of a user's signed message. Such certificates include a
certificate for the signer's certifier and for the certifiers' certifier,
etc., up to a predetermined certificate (or set of mutually referenced
co-certificates) which is trusted by all parties involved. When this is
done, each signed message unequivocally contains the ladder or hierarchy
of certificates and the signatures indicating the sender's authority. A
recipient of such a signed message can verify that authority such that
business transactions can be immediately made based upon an analysis of
the signed message together with the full hierarchy of certificates.
The present invention provides the ability to hierarchically administer a
large system or group of systems; and to do so in a fashion with maximum
control, and which minimizes the possibility of error, corruption,
subterfuge or mischievous disruption.
Since the certificates created by the present invention convey not only
simple identification, but also authority, restrictions and limitations,
including monetary authority, it is extremely important that certification
be accurately implemented and carefully controlled. In a large
organization (or group of organizations), it becomes more difficult to
centrally confirm everyone's identity (not to mention their authority).
Also there is constant change: employees will need to be re-issued
certificates as their status' change. The present invention incorporates
distributed, hierarchial administration to meet these needs.
The present invention enforces limitations and accountability from
hierarchy to hierarchy so that the recipient of any message signed with
such a (hierarchically derived) certificate can be assured that the
authority represented by the signer is strictly accounted.
This is accomplished by 1) including as part of each certificate the
statement (in a form readily checked by computer, as well possibly by
human confirmation) the powers, authority and limitations which are being
granted.
2) Stipulating in each certificate, the powers and authorities which the
certifier will permit to be further hierarchically granted (if at all).
3) When important, valuable or sensitive authority is being granted,
including possibly the power to in turn grant authority to a yet further
level, or the power to authorize money or other sensitive resource, the
requirement of multiple signatures (co-signatures) can be stipulated. Such
co-signatures may be explicitly indicated (by reference to another
certificate, or public key), or implicitly (by specifying a class of
certificates or public keys, or by some abstract grouping or
identification).
This enforces checks and balances, and mutual decisions, and automatic
policing when sensitive powers are exercised. This also enhances the
integrity of the entire system by reducing the chance that corruption will
occur, and if it does occur, to minimize and isolate any damage. The risk
of collusion can always be reduced by increasing the required number of
necessary co-signers.
4) In large organizations, the private aspect of public keys will
occasionally become compromised (perhaps through carelessness by their
owners), and it may be necessary to issue cancellations notices throughout
a network.
In the current state of the art, the only practical way to do this is for
the maker of a certificate (the certifier) to cancel a certificate.
Otherwise, a malicious or mischievous entity could create bogus
cancellation notices and wreak havoc by falsely cancelling innocent users'
certificates.
The present invention may be used to control cancellation in a distributed
manner, so that the actual maker of a certificate is not required to
always also be the canceller. This allows the "police" power to be safely
regulated, but without requiring the constant attention of those who
define the certificates and insure their accuracy.
The present invention additionally provides a methodology by which multiple
objects such as, for example, a cover letter, an associated enclosed
letter, an associated graphics file, etc., may be signed together in such
a way that each object is individually verifiable and while also
indicating the relationship of each object to the whole group. An
aggregation of data related to all of these objects (possibly the HASH of
each of these objects together with control information) is gathered into
an ordered list. This ordered list is then viewed as an object and is
signed or the hash of the list is signed. This list shows that the signer
individually recognized the associated objects as well as their context in
the group. Thus, each element of this ordered list is processed by a
hashing algorithm (to generate a more compact version thereof) which
results in a list of presignature hash values. The presignature hash list
is then run through a decrypt (signature) cycle to result in the signer's
signature, hereinafter referred to as seal, which becomes part of the
signature packet as will be described in detail below.
The present invention further provides a methodology for digitally signing
documents in which the signature is generated for both computer
verification and for reverification if a document needs to be reconfirmed
in the future by reentering it from a paper rendition. To accomplish this
end, two hash values are utilized in digital signatures of document-type
computer messages. The first hash value which is utilized relates to the
exact bit-for-bit data in the file. This will allow for validation of the
exact original document as long as it is accessible in computer readable
form.
The present invention also embodies a second auxiliary hash value which is
taken across the same data in the file, except the data used for the
second hash value is "white-space-normalized". This white space
normalization allows the data to be re-entered from a printout at some
future time, if necessary, without having to worry about what kind of
unprintable, unseen control characters may have existed on the original.
It should be recognized that in any given application, the public key,
certificate and digital signature may be designed to perform distinct but
somewhat overlapping functions. In this regard, one might possibly include
in the "public" key certain aspects of what is referred to herein as the
"certificate". Conversely, the certificate could be constructed as
containing the public key as part of it. Similarly, some or part of the
certificate and/or public key could be embedded as part of a signature.
This possibility is especially important to keep in mind when the
signature applies to authorizing another certificate. Thus, the specific
examples shown in the detailed description which follows should not be
construed as limiting the present invention.
BRIEF DESCRIPTION OF THE DRAWINGS
These as well as other features of this invention will be better
appreciated by reading the following description of the preferred
embodiments of the present invention taken in conjunction with the
accompanying drawings of which
FIG. 1 is a block diagram of a cryptographic communications system in
accordance with an exemplary embodiment of the present invention;
FIG. 2 is a flow diagram that indicates how a digital signature is created
in accordance with an exemplary embodiment of the present invention;
FIG. 3 is a flow diagram that indicates how a digital signature created in
accordance with FIG. 2 is verified;
FIG. 4 is a flow diagram that indicates how a countersignature is created
for a digital signature;
FIG. 5 is a flow diagram that indicates how a digital certificate in
created in accordance with an exemplary embodiment of the present
invention;
FIG. 6 is a flow diagram that indicates how a joint signature is added to a
certificate;
FIG. 7 is a flow diagram that indicates how the signatures and certificates
are verified by a recipient of the transmitted message;
FIG. 8 is an exemplary memorandum to be electronically transmitted that
includes a digital signature section;
FIGS. 9A and 9B is a flowchart showing the processing associated with
computing the white-space hash function;
FIG. 10 show how a multiple document package is signed in accordance with
the present invention;
FIG. 11 shows how a printed document may be reverified using the white
space hash function; and
FIG. 12 shows how a signature is verified for a multiple document/file
package.
DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENT
FIG. 1 shows in block diagram form an exemplary communications system which
may be used in conjunction with the present invention. This system
includes an unsecured communication channel 12 over which communications
between terminals A,B . . . N may take place. Communication channel 12
may, for example, be a telephone line. Terminals A,B through N may, by way
of example only, be IBM PC's having a processor (with main memory) 2 which
is coupled to a conventional keyboard/CRT 4. Each terminal A,B through N
also includes a conventional IBM PC communications board (not shown) which
when coupled to a conventional modem 6, 8, 10, respectively, permits the
terminals to transmit and receive messages.
Each terminal is capable of generating a plain text or unenciphered message
and performing whatever signature operation may be required, and
transmitting the message to any of the other terminals connected to
communications channel 12 (or to a communications network (not shown)
which may be connected to communications channel 12). Additionally, each
of the terminals A,B through N is capable of performing signature
verification on each message.
Each of the terminal users (as discussed above with respect to public key
systems) has a public encrypting key and an associated private secret
decrypting key. In the public key cryptosystem shown in FIG. 1, each
terminal user is aware of the general method by which the other terminal
users encrypt a message. Additionally, each terminal user is aware of the
encryption key utilized by the terminal's encryption procedure to generate
the enciphered message.
Each terminal user, however, by revealing his encryption procedure and
encryption key does not reveal his private decryption key which is
necessary to decrypt the ciphered message and to create signatures. In
this regard, it is computationally unfeasible to compute the decryption
key from knowledge of the encryption key.
Besides the capability of transmitting a private message, each terminal
user likewise has the capability of digitally signing a transmitted
message. A message may be digitally signed by a terminal user decrypting a
message with his private decrypting key before transmitting the message.
Upon receiving the message, the recipient can read the message by using
the sender's public encryption key. In this fashion, the recipient can
verify that only the holder of the secret decryption key could have
created the message. Thus, the recipient of the signed message has proof
that the message originated from the sender. Further details of an
exemplary digital signature methodology which may be used in conjunction
with the present invention is disclosed in U.S. Pat. No. 4,405,829.
Before describing the details of the enhanced digital certification in
accordance with the present invention, the general operation of FIG. 1 in,
for example, an electronic mail, public key cryptographic context will
initially be described. Initially, presume that the user of terminal A is
a relatively low level supervisor of a General Motors computer automated
design team who wishes to purchase a software package from a computer
software distributor located in a different state. The computer software
distributor has terminal N and an associated modem 10 located at his
store.
The General Motors supervisor at terminal A constructs an electronic
purchase order which identifies the item(s) being ordered and the address
to which the items must be sent as well as other items which are necessary
in a standard purchase order. It should be recognized that, although this
example relates to an electronic purchase order, any aggregation of data
which can be represented in a manner suitable for processing with whatever
public-key method is being used for signatures may likewise be
transmitted. In the more detailed description which follows such an
aggregation of data, e.g., a computer data file, will generically be
referred to as an "object".
The terminal A user, the General Motors supervisor, digitally signs the
purchase order under the authority of a certificate which is appended to
the transmitted message which will be discussed further below. Turning
first to the supervisor's digital signature, a message can be "signed" by
applying to at least a portion of the object being signed, the privately
held signature key. By signing an image of the object (or a more compact
version thereof known as a digest or hash of the object to be explained in
more detail below) with the secret key, it is possible for anyone with
access to the public key to "encrypt" (i.e., reverse) this result and
compare it with the object (or a recomputed hash or digit version
thereof). Because only the owner of the public key could have used the
secret key to perform this operation, the owner of the public key is
thereby confirmed to have signed the message. It is noted that other
methods besides "encryption" may be appropriate for different signature
schemes such as Fiat-Shamir.
In accordance with the present invention, a digital signature is
additionally accompanied by at least one valid certificate which specifies
the identity of the signer and the authorization which the signer has been
granted. The certificate may be viewed as a special object or message
which specifies the identity of the user of a particular public key and
the authority which has been granted to that user by a party having a
higher level of authority than the user.
To be valid a certificate must be signed by the private key(s) associated
with one or more other valid certificates which are hereafter referred to
as antecedents to that certificate. These may also be accompanied by
| | |
