(PICTURE)(PICTURE) (PICTURE)Europäi _hes Patentamt
_ (PICTURE) EuroPean Patent offi_e
(PICTURE) Offi_e euroPeen des brevets _ PubIication number . O 328 232 B1
_ EUROPEA_ PATE_T SPECIFICATlO_
_ Date oF pubI_i_t_ion oF patent spec_ifcat_ion .. _ _nt. __.6 .. HO4_ 9JOO
O3.O_.9_ Bulletin 9_l_8
_ APPlication number . 893oo___.2
_ Date oF FiIing . o6.o_.8a
(PICTURE)
(PICTURE)_ Publi_ keylsignature _yPtosystem with enhan_ed digi_l signature _e_if_ation.
_ Note . w.ith.in n.ine months From the pubI.icat.ion oF the ment.ion oF the grant oF the European patent any
_ pe_on may give notice to the European patent oFFice oF opposition to the European patent gra'nte_.
_ Notice of opposition shall be fled in a written reasoned statement. It shall not be deemed to have been
W fled until the opposition fee has been paid (Art. 99(1) European patent convention).
(PICTURE)Jouve, 18, rue Saint-Denis, 75OO1 PARIS
EP O 328 232 B_
Des_ription
(PICTURE)FIELD OF THE Ih1VEh1TlOh1
5 This invention relates to a cryptographic communications system and method. More particularly, the in-
vention relates to a public key or signature cryptosystem having improved digital signature certification for in-
dicating the identity, authority and responsibility levels associated with at least the senderofa digital message.
BACKGROUh1D Ah1D SUMMARY OF THE Ih1VEh1TlOh1
1O (PICTURE)
The rapid growth of electronic mail systems, electronic funds transfer systems and the like has increased
concerns over the security of the data transferred over unsecured communication channels. Cryptographic
systems are widely used to insure the privacy and authenticity of messages communicated over such insecure
channels.
15 In a conventional cryptographic system, a method of encryption is utilized to transform a plain text mes-
sage into a message which is unintelligible. Thereafter, a method of decryption is utilized for decoding the en-
crypted 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
2o 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, if it is far more difficult to compute the inverse of the hashing function than it is to compute the
function. For all practical purposes, the value obtained from applying the hashing function to the original ag-
25 gregation 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 likewise 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
3o in 1 977 approved a block cipher algorithm referred as the (PICTURE)(PICTURE) (DES). (PICTURE)(PICTURE)
Standard, FIPS PUB 46, National Bureau of Standards, January 1 5, 1 977.
(PICTURE)n DES, binary coded data is cryptographically protected using the DES algorithm in conjunction with a
key. Each member ofa group ofauthorized users ofencrypted 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
35 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 al-
gorithm 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.
4O Thus, the cryptographic security ofthe 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 ofthe 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.
45 In such conventional cryptographic systems, some secure method must be utilized to distribute a secret
key to the message senderand receiver. Thus, one ofthe majordifficulties 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
5O example, a private courier or registered mail. While providing the necessary security such key distribution tech-
niques are usually slow and expensive. Ifthe need for the sender and receiver is only to have one private mes-
sage exchange, such an exchange could be accomplished by private courier or registered mail, thereby ren-
dering the cryptographic communication unnecessary. Moreover, if the need to communicate privately is ur-
gent the time required to distribute the private key causes an unacceptable delay.
55 Public key cryptographic systems solve many of the key distribution problems associated with conven-
tional 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
2
EP O 328 232 B_
the encryption key. Even with 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 encryptionldecryption key pair be generated. The encryption keys for
5 all users may be distributed or published and anyone desiring to communicate simply encrypts his or her mes-
sage under the destination user's public key.
Only the destination user, who retains the secret decrypting key, is able to decipher the transmitted mes-
sage. Revealing the encryption key discloses nothing useful about the decrypting key, i.e., only persons having
knowledge of the decrypting can decrypt the message. The RSA cryptographic system which is disclosed in
1o U.S. Patent No. 4,4O5,829 issued to Rivest et al discloses an exemplary methodology for a practical imple-
mentation 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. An authenticating technique known utilizing
''digital signatures'' allows a user to employ his secret key to ''sign a message'' which the receiving party or a
15 third party can validate using the originator's public key. See for example U.S. Patent No. 4,4O5,829.
A user who has filed a public key in a publicly accessible file can digitally sign a message by decrypting
the message or a hash of it with the user's private key before transmitting the message. Recipients ofthe mes-
sage 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
2o 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.
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 foraddressing 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
25 who 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 known as a certificate,
is sent along with the user of the claimant's own digital signature. Any recipient of the claimant's message can
3o 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.
Prior to the present invention, the transmitted certificate failed to provide any indication of the degree of
trust or the level of responsibility with which the sender of the message should be empowered. Instead, the
certification merely indicates that the identified trusted authority recognized the sender's public key as be-
35 longing 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
4O people who they are claiming to be. Thus, a party may provide a public key to be maintained in the public di-
rectory under the name ofthe chairman ofa 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,
45 including, for example, the Fiat-Shamir algorithm. Any digital signature methodology may be employed to im-
plement the digital signatures referenced herein. Any reference to public key cryptosystems should also be
construed to reflectsignature 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.
5O C Pomerance . ''Advances in Cryptology-Crypto '87'' 1 987, Springer Verlag, Berlin pp 211 to 21 5, and;
Computers & Security vol 6, no. 3, June 1 987, Amsterdam NL pp 2O6-21 8; K Rihaezek . ''Teletrust-Osis and
Communication Security'' both relate to systems forthe verification of personal identity using a public key iden-
tification system. A private key is used to digitally sign a message.
The present invention addresses such problems with the public key or signature cryptographic system re-
55 lating to authenticating the identity ofthe public key holder by expanding the capability of digital signature cer-
tification. In this regard, a certification methodology is utilized which employs multiple level certification while
at the same time indicating the authority and responsibility levels of the individual whose signature is being
certified as is explained in detail below. 3
EP O 328 232 B_
According to the present invention there is provided;
in a communication system having a plurality ofterminal devices coupled to a channel overwhich users
of said terminal devices may exchange messages, at least some of said users having a public key and an as-
sociated private key, a method for managing authority by digitally signing and certifying a digital message to
5 be transmitted to an independent recipient comprising the steps of.
generating at least a portion of said digital message;
digitally signing at least said portion of said message; and characterised by
associating with said message an authorizing digital certificate having a plurality ofdigital fields created
by a certifier, said authorizing certificate being created by the steps of.
1o specifying by the certifier in at least one ofsaid digital fields, the authority which is vested in the certifier
and which has been delegated to the signerofsaid message, by including sufficient digital information to enable
said independent recipient of said message to verify, by electronically analyzing said message in accordance
with a predetermined validation algorithm, that the authority exercised by the signer in signing the content of
said message created by the signerwas properly exercised by the signer in accordance with the authority dele-
15 gated by the certifier; and
identifying the certifierwho has created the signer's certificate in other ofsaid digital fields by including
sufficient digital information forsaid recipient ofthe message to determine by electronically analyzing said mes-
sage that the certifier has been granted the authority to grant said delegated authority.
The present invention enhances the capabilities of public key cryptography so that it may be employed in
2o a widervariety of business transactions, even those where two parties may be virtually unknown to each other.
The digital signature certification method and apparatus of the present invention provides for a hierarchy
of certifications and signatures. It also allows for co-signature requirements. In this regard, 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
25 winds his way through a corporate bureaucracy.
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 spe-
cialmessage that includes fields identifying the public key which is being certified, and the name of the cer-
tifiee. In addition, the certificate constructed by the certifier includes the authority which is being granted and
3o 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 specifyco-signature requirements as being imposed upon the certifiee.
The present invention further provides for certifying digital signatures such that requirement for further
joint certifying signatures is made apparent to any receiver of a digital message. The requirement forjoint sig-
35 natures is especially useful 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 ofjoint 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
4O material which is signed by the authorityof the sender's certificate, must also be signed by a number of other
specified signators. The recipient is therefore able to verify otherjoint and counter signatures by simply com-
paring 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 indicating othercertificates. Such indications ofother
public key holders may be explicit (with a list as described here), or implicitly, by specifying some otherattribute
45 or affiliation. This attribute or affiliation may also be indicated in each co-signer' certificate.
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 prede-
5O termined digital code a trust level which indicates that the certifier warrants that the user named in the certif-
icate is known to the certifier and is certified to use the associated public key. However, by virtue of this digital
code, the user 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 is
55 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., certif-
icates 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 certi-
4
EP O 328 232 B_
fiers' certifier, etc., up to a predetermined certificate 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 indi-
cating the sender's authority. Arecipient ofsuch 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
5 hierarchy of certificates.
(PICTURE)BRIEF DESCRIPTlOh1 OF THE DRAWlh1GS
These as well as other features of this invention will be better appreciated by reading the following de-
1o scription of the preferred embodiment of the present invention taken in conjunction with the accompanying
drawings of which
FIGURE 1 is a exemplary block diagram of a cryptographic communications system in accordance with
an exemplary embodiment of the present invention;
FIGURE 2 is a flow diagram that indicates how a digital signature is created in accordance with an exem-
15 plary embodiment of the present invention;
FIGURE 3 is a flow diagram that indicates how a digital signature created in accordance with FIGURE 2
is verified;
FIGURE 4 is a flow diagram that indicates how a countersignature is created for a digital signature;
FIGURE 5 is a flow diagram that indicates how a digital certificate in created in accordance with an ex-
_o emplary embodiment of the present invention;
FIGURE 6 is a flow diagram that indicates how a joint signature is added to a certificate; and
FIGURE 7 is a flow diagram that indicates how the signatures and certificates are verified by a recipient
of the transmitted message.
_5 (PICTURE)DETAILED DESCRIPTlOh1 OF THE PRESEh1TLY PREFERRED EMBODIMEh1T
Figure 1 shows in block diagram form an exemplary communications system which may be used in con-
junction 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 1 2 may, for example,
3o 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 keyboardICRT 4. Each terminal A,B through N also
includes a conventional IBM PC communications board (not shown) which when coupled to a conventional mo-
dem 6, 8, 1 O, respectively, permits the terminals to transmit and receive messages.
Each terminal is capable of generating a plain text or unenciphered message, transforming the message
35 to an encoded, i.e., enciphered form, 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 com-
munications channel 12). Additionally, each of the terminals A,B through N is capable of decrypting a received
enciphered message to thereby generate a message in plain text form.
Each ofthe terminal users (as discussed above with respect to public key systems) has a public encrypting
4O key and an associated private secret decrypting key. In the public key cryptosystem shown in Figure 1 , each
terminal user is aware ofthe general method bywhich the otherterminal 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
45 his private decryption key which is necessary to decrypt the ciphered message and to create signatures. In
this regard, it is simply not feasible to compute the decryption key from knowledge of the encryption key. Each
terminal user, with knowledge of another terminal's encryption key, can encrypt a private message for that ter-
minal user. Only the terminal end user with his secret decrypting key can decrypt the transmitted message.
Besides the capability of transmitting a private message, each terminal user likewise has the capability
5O 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 a digital sig-
55 nature methodology which may be used in conjunction with the present invention is disclosed in U.S. Patent
No. 4,4O5,829.
Before describing the details ofthe enhanced digital certification in accordance with the present invention,
the general operation of Figure 1 in an electronic mail, public key cryptographic context will initially be descri-
_
EP O 328 232 B_
bed. Initially, presume that the user of terminal A is a relatively low level supervisor of a General Motors com-
puter automated design team who wishes to purchase a software package from a computer software distrib-
utor located in a different state. The computer software distributor has terminal N and an associated modem
1 O located at his store.
5 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 neG
essary 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
1o 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
15 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 this result and compare it with the object
(or a recomputed hash or digit version thereo_. 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 mes-
_o sage.
In accordance with the present invention, a digital signature is additionally accompanied by at least one
valid certificate which specifies the identity ofthe signerand the authorization which the signer has been grant-
ed. 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
_5 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 cer-
tificates which are hereafter referred to as antecedents to that certificate. Each of these antecedent certifi-
cates must grant the signer the authority to create such a signature andlor to issue the purchase order in our
example. Each of the antecedent certificates may in turn have its own antecedent(s).
3o An exemplary embodiment of the present invention contemplates utilizing an ultimate antecedent certif-
icate of all certificates, which is a universally known and trusted authority, e.g., hypothetically the National
Bureau of Standards, and which is referred to as a meta-certificate. The meta certificate is the onlyitem that
needs to be universally trusted and known. There may be several meta-certifiers, and it is possible that meta-
certificates may even reference each other for required co-signatures.
35 Turning back to our example, when the message is ultimately transmitted from terminal A to the computer
software distributor at terminal N, the recipient in a manner which will be described in detail below, verifies
the signature of the General Motors supervisor. Additionally, he verifies that all the other signatures on the
message certificate and the antecedent certificates are present which provides further assurance to the ter-
minal N software distributor that the transaction is a valid and completely authorized. As should be recognized,
4o such assurances are critically important prior to shipping purchased items and are perhaps even more impor-
tant in an electronic funds transfer context.
Any party who receives a message transmitted by the user of terminal A (whether such a party is the ul-
timate recipient of the message at terminal N or other parties within for example a corporate hierarchy such
as General Motors) can verify and validate A's signature and the authority that the terminal A user exercised.
45 Such validation is possible since a complete hierarchy ofvalidating certificates is transmitted with the original
purchase orderwhich permits the ultimate recipient to feel confident that the requested transaction is authentic
and properly authorized.
Focussing more generically on major transactions emanating from, for example, General Motors Corpor-
ation, it is helpful to focus first on the ultimate certifier(s) mentioned above, i.e., the meta-certifiers. In this
5O regard, General Motors and parties who plan to do business with General Motors or otherwise participate in
the public key cryptosystem may initially choose to approach a universally recognized trusted authority e.g.,
hypothetically the Bureau of Standards andlor one of the country's largest banks. Corporate and other partici-
pants in this system register a set of public keys (which they are authorized to use by virtue of an action of
their corporate board of directors) with the meta-certifier. These are ''high level'' keys to be used within the
55 General Motors environment primarily for certifying General Motors' internal personnel. The meta-certifier in
return distributes to General Motors its certification that each ofthese supplied public keys created by General
Motors is authorized for their own use. In effect, the meta-certifier is certifying that the party using each key
is actually associated with General Motors. The meta-certifier's certification may include embedded textwhich
6
EP O 328 232 B_
indicates that the users of registered public keys are properly associated with General Motors. For example,
General Motors may decide to have three ''high level'' keys certified, e.g., corporate officers, such as the vice
president, financial officer, and the security officer. At General Motors' request each of the three certificates
indicate the public keys of the other two as required joint signatures.
5 Thus, once having obtained the highest level certificate(s) from the meta-certifier, several officials within
General Motors may have to jointly sign certificates at the next lower level and such joint signatures. Each of
these high level General Motors' certificates would mutually reference each other as required co-signers Athis
Ievel no single corporate officer acting alone may authorize anything because embedded within each of the
three certificates is a requirement forthe signature ofothers who are specifically identified. In turn then, these
1o 3 officers create and sign public keys for the other General Motors' employees, that define exactly the level
of authority, responsibility and limitations each employee is to have. One of these certificates may belong to
user A, or will be an antecedent to user's A's certificate.
Each of these three high level certificates may digitally sign terminal B user's certificate preferably after
a face to face ortelephone verification. Aftereach ofthe required signatures has been created, the certificate's
15 signatures by the vice president, financial officer and security officer as well as their respective 3 certificates,
as well as those certificates' respective signatures by the meta-certifier are ultimately returned to the General
Motors' supervisor at terminal B to be stored for ongoing use, such as in our example for subcertifying terminal
user A. In this manner, the signed message unequivocally contains the ladder or hierarchy of certificates and
signatures verifying terminal A user's identify and his authority.
2o When a party B in a ladder of certifications creates an authorizing certificate for party A, the certificate
includes a specification of A's identity together with A's public encryption key. Additionally, the certificate in-
dicates the authority, capabilities and limitations which B wishes to grant A. By granting this certificate B ex-
plicitly assumes responsibility for both A's identity and authority.
B's certificate for A also permits a specification of other parties who are required to cosign actions taken
25 by A when using this certificate as will be explained further below. Cosignatures may take the form of either
joint signatures orcountersignatures. Additionally party B can define in the certificate forAthe degree towhich
B will recognize subcertifications performed by A.
In accordance with an exemplary embodiment of the present invention, trust levels which are granted by
the certifier to the certifiee are specified in the certificate by a predetermined digital code. Such a trust level
3o is used by the recipient ofthe message as an indicator of the authority granted to the certifiee and the respon-
sibility assumed by the certifier for the certifiee's actions with respect to the use of the public key being cer-
tified.
By way of example only trust levels may be indicated by trust level values O, 1 , 2, and 3.
Trust level O indicates that the certifier vouches that the certified public key belongs to the individual
35 named in the certificate; but that the certifierwill not assume responsibility for the accuracy ofany certificates
produced by the certifiee. The essence of this would be a statement by the certifier that. ''l warrant the user
named in this certificate is known to me and is being certified to use the associated public key -- however l
do not trust him to make any further indentifications on my behaIF'.
Trust level 1 empowers the certifiee to make level O certifications on behalf of the certifier. The essence
4O of this would be a statement by the certifier that. ''l know the user of this public key and l trust himlher to ac-
curately identify other persons on my behalf. l will take responsibility for such identifications. However, l do
not trust this person to identify persons as trustworthy.''
Trust level 2 empowers the certifiee to make level O, 1 and 2 certifications on behalf of the certifier. The
essence ofthis would be a statement by the certifier that . ''l know the user ofthis public key and l trust himlher
45 to accurately identify other persons on my behalf, and l furthermore trust them to delegate this authority as
they see fit. l assume due responsibility for any certifications done by them or any duly authorized agent cre-
ated by them or by other generation of duly created agents''.
Trust level 3 is reserved exclusively for an ultimate meta certifier whose public key and certificate is es-
tablished and also well known (possibly by repetitive and widespread media publication) and whose accuracy
5O is universally respected. This certifier takes responsibility only for accurately identifying the entities whose
public keys it certifies. It assumes no responsibility for the use of these keys.
Additionally, each certification may specify the monetary limit, i.e., the maximum amount of money value
which the certifiee is authorized to deal with. The monetary limit must not of course exceed the limit in the
certifier's own certificate to insure that the certifier does not delegate more than he is allowed to handle.
55 Before discussing further details of the digital signature and certification techniques of the present inven-
tion, it may be helpful to first define certain terminology. As noted above, the term ''object'' is generically used
to describe any aggregation ofdata that can be ultimately represented in a manner suitable for processing with
whatever public key method is being utilized for signatures andlor encryption. The term object may apply to
l
EP O 328 232 B_
a ''primary'' object such as a purchase order or check, or money transfer; or to a ''seconday'' object such as
a certificate, or another signature.
The methodology of the present invention in order to increase processing efficiency generally applies a
function to the object to create a generally smaller, more compact, more easily processed object, i.e., typically
5 a fixed size bit string of several dozen or more bits. Such a function is referred to as a hash or digest of the
object.
An example of such a hash or digest would be the output obtained by processing an image of the object
with the data encryption standard (DES) using cipher block chaining mode (CBC). Processing may be done
with two different DES keys (both of which are fixed, non-secret and commonly known). Thereafter, each of
1o the final output chaining values are concatenated or merged in some way to become the several dozen or more
bits constituting the digest or hash value.
An important characteristic ofthe digest or hashing algorithm is that, while it is easy to compute the digest
of an object it is essentially impossible to construct a different or modified object with an equal digest. For all
practical purposes the digest is an unforgeable unique fingerprint of the original object. If the original object is
15 changed in any manner, the digest will be different. In otherwords, for all practical purposes, the more compact
representation of the original object is unique to the original object. Ideally, also a hash should not reveal any
clue about specific data values contained within the message. The hash's contemplated in the exemplary em-
bodiment have at least 128 bits.
Turning now to Figure 2, this figure shows the data flow and the manner in which signatures are created.
2o The signature process applies not only to general objects such as arbitrary computer fles, letters, electronic
purchase orders, etc., but also to specialized objects such as signatures and certificates.
Each digital signature is accompanied, as is generally shown in Figure 2, by a certification of the public
key performing the signature. The certificate, as will be discussed in detail in conjunction with Figure 5, is sign-
ed by one or more higherauthorities (i.e., the immediate certifiers) and identifies the original signerwhile spec-
25 ifying the degree of authority which has been granted to the original signer.
In accordance with the present invention, the original signer may have more than one certificate and may
utilize different certificates for different levels of authority. Each of the certificates may carry different limit-
ations and requirements including different money limitations, trust levels, joint signature requirements and
counter signature requirements.
3o It is incumbent on the signer to select the appropriate signaturelcertificate with which to sign a particular
object. For example, purchase orders may require a different type of authority (and therefore a different cer-
tificate) than merely a letter of inquiry. Thus, the certificate is a very important portion ofthe transmitted mes-
sage in that it identifies the signer as well as the signer's level of authority.
As shown in Figure 2, in creating the signature the user utilizes the object 2O (which may, for example, be
35 a purchase ordei) and specifies the type ofobject 22. The documentation added under the type ofobject field,
for example, indicates that the object is a purchase order data file. In other instances the type of object field
22 would identify that the object is another signature or a certificate. As indicated at 24, the date of the sig-
nature is also identified.
The comment field 26 is utilized to add documentation which, for example, places limitations on the sig-
4O nature or adds other commentary. The signer may indicate that his signature or the object is only good and
valid for a predetermined period of time. Additionally, any desired comments regarding the particular transac-
tion, e.g., the purchase order, may be added as comment data.
Also incorporated in the signature is the original signer's certificate 28 which includes the original signer's
public key 3O and numerous other fields which are discussed in detail below in conjunction with Figure 5. As
45 noted above, public key signature methods require the use of a public key 3O and an associated private key
which is shown in Figure 2 at 32.
The object field 2O (e.g., purchase order data), the type of object field 22, the signing date field 24, the
comment field 26, and the signer's certificate field 28 are hashed via a hashing algorithm at 34 to enhance
processing efficiency. Additionally, each of the fields 2O, 22, 24, 26 and 28 are incorporated in the signature
5O packet 42 to become part of the signature record. A hashing algorithm 44 is also applied to the object 2O to
place it in a more compact form prior to incorporation in the packet 42.
Afterapplication ofthe hashing algorithm 34 to the fields previously discussed, a presignature hash results
therefrom as indicated at 36. The presignature hash 36 is then run through a decrypt (signature) cycle as in-
dicated at 38 using the signer's private key 32 to thereby result in the signer's signature 4O. The signer's sig-
55 nature 4O together with items 2O (or the hash of 2O), 22, 24, 26 and 28 become the final signature packet 42.
When this signature is transmitted with the associated object, it allows the recipient to verify that the object
is intact as it was signed. Furthermore, when sufficient certificates are also included, the recipient can validate
the true identity of the signer and the authority which has been granted in the signer's chain of certificates.
8
EP O 328 232 B_
Turning now to Figure 3, this figure shows how a recipient of the transmitted message, including the sig-
nature packet 42 constructed in accordance with Figure 2, verifies the signature. As shown in Figure 3, the
recipient utilizes the signature packet 42 and the associated fields 22, 24, 26 and 28 as well as the object 2O
and applies the same hashing algorithm 34 as applied to these same fields in Figure 2 to thereby result in a
5 presignature hash 5O.
The recipient then utilizes the public encrypting key transmitted with the signer's certificate 28 and per-
forms an encrypt (verification) operation 52 on the signature to be verified 4O (which was transmitted with the
signature packet) to thereby generate a presignature hash 54. The recipient, by recomputing the presignature
hash in the same way as the signer, then compares this value with the encryption (verification) of the signer's
1o signature.
As indicated at block 56, if these two values at 5O and 54 are not equal, the recipient cannot accept the
received signature as being valid. Whether intentional or otherwise, the object andlor the signature must have
been changed or tampered with in some way since they were signed. By virtue of this verification step, the
recipient determines that the digital signal is consistent with the public key that was named.
15 In this manner, the object and its signature are processed to insure that the object is identical to the data
which existed as it was signed by the owner of the public key. This is the first step ofan overall validation proc-
eSS.
Other steps in the validation process insure that the public key belongs to the person named in the asso-
ciated certificate and that the person has the authority stipulated in the certificate. This verification process
2o applies generally to any object even ifthatobject is anothersignature ora certificate. To complete the validation
process, the recipient analyzes the certificates associated with the signature to determine that the proper au-
thority has been conveyed to each certificate through its signatures and the antecedent certificate(s) of these
authorizing signatures.
An object may be accompanied by more than one signature. Such cosignatures fall into the category of
25 either a joint signature or a counter signature. Ajoint signature is simply another signature of an object by a
different party. The signature process is no different than that used to create the initial signature as described
in conjunction with Figure 2.
A counter signature is a signature of a signature. Thus, when A signs an object, this signature may itself
be thought of as an object. Thus, when C countersigns A's signature, the object C is signing is A's signature
3o itselfratherthan the original object. The countersignature must therefore occur afterthe signature being coun-
tersigned and reflects approval (or at least recognition) of both the underlying object as well as the fact that
A has signed that object. This mechanism allows a chain of authority where each higher level approves any
commitment made at a lower level. One ofthe unique aspects ofthis system is that the certificate Aassociates
with this signature may in fact require that the use of A's signature be accompanied by particular otherjoint or
35 counter signatures.
Turning next to the creation of a counter signature which is shown in Figure 4, initially A signs at 63 a pri-
mary object 6O in accordance with the procedure outlined in detail in conjunction with Figure 2. The primary
object 6O may be a purchase order or some other commitment or it may be a counter signature of some other
signature of a primary object.
4O As explained above in regard to Figure 2, the process of A signing an object may also involve some other
party signing A's signature. Thus, A's certificate 62 specifically defines at 65 that, in order for A's signature to
be valid (i.e., ratified), a counter signature by C is required, for example, using C's specific certificate Y.
After A signs the object, A's signature packet 66 is then forwarded along with the primary object and all
associated signatures and certificates to C and Arequests that C add his counter signature 64. Upon receiving
45 the material, C reviews all existing signature certificates and the primary object and if everything meets with
his approval he would decide to sign A's signature 68. A's signature inherently reflects the primary object and
C's signature inherently reflects A's signature so C will essentially have ''signed on the line below A's signa-
ture''.
Once C decides to approve A's signature at 68, the process of creating a signature as shown in detail in
5O Figure 2, is duplicated except that the object is A's signature. Thus, with A's signature as the object (and the
type of object being designated as a signature at 72), the counter signature date 74, C's counter signature
comment 76, and C's certificate 7O are applied to a hashing algorithm 8O to thereby result in a presignature
hash 82. At the same time, these fields are also inserted into the counter signature packet 88 as discussed
above with respect to the signature packet 42 (with a hashing algorithm 69 being applied to the signature ob-
55 ject).
Presignature hash 82 and C's secret key 92 are applied in a signature operation 84 to generate a counter
signature 86. This counter signature becomes part of the counter signature packet 88 in precisely the same
fashion as described previously in regard to the creation of signature packet 42 in Figure 2.
9
EP O 328 232 B_
Because the certificate ''Y'' which C must use to perform the signature has been explicitly stated (in the
certificate which A used to sign), C may also be required to meet his own cosignature obligations so specified
by '_'' and forward this entire package including his own newly added signature on to other parties for further
cosignatures (either joint or counter signatures). This recursive signature gathering process continues until
5 sufficient signatures are added to fully satisfy all cosignature requirements of at least one party who initially
signed the primary object.
Turning next to how one party creates an authorizing certificate for another, it is noted that B creates an
authorizing certificate for A by combining a specification of A's identity togetherwith the public encrypting key
which Agenerated for himself. Additionally B specifies the authority capabilities and limitations which B wishes
1o to grant A. By signing the certificate B explicitly assumes responsibility for A's identity and authority.
The present invention permits B to specify other signators who are required to cosign actions taken by A
when using the certification. As noted above, B can further define in the certificate for A the degree to which
B will recognize subcertifications performed by A.
Additionally, many other limitations and restrictions may be imposed by B. For example, B may impose a
15 money limitwhich will insure that any recipient ofA's certificate will be aware ofthe limit B is willing to authorize.
Since the process ofcreating a certificate, as will be shown below involves signatures, the use ofcosignatures
is extended to permit certification authorization. Forexample, certificates may be designed to allow delegation
of subcertification, but only if particular multiple cosigners are involved. This allows checks and balances to
be structured into a hierarchy ofauthority so that electronic digital signatures can be used across organization
2o and institutional boundaries with great confidence -- both by the parties receiving the signatures and the par-
ties granting the authority to use the signatures.
The manner in which a party B creates a certificate for party A is shown in Figure 5. As indicated at 1 OO,
A creates a publiclprivate key pair in accordance with conventional public key signature systems and supplies
the public key to B 1 O2. Once B obtains the public key provided by A for certification, it is important for B to
25 insure that the public key is actually one generated by A and not someone masquerading as A. In this regard,
it may be desirable for the public key generated by A to be provided on a face to face basis.
Having selected his own certificate with which to sign A's certificate, B at 1 O6 utilizes the certificate 1 O8
with the associated public key 1 1 O to create a signature of a new certificate 112. As in Figure 2, the signature
is created using an object (A's certificate 11 6) and a certificate (B's certificate 1 O8). B's secret private key is
3o utilized in the decrypt operation to create the signature 11 2 ofthe new certificate 11 6 and the signature packet
1 14 of B's signature becomes part of A's new certificate packet.
Focussing on the certificate for Awhich is constructed using information about A specified by B, B builds
the certificate by utilizing the public aspect of A's public key as provided by A via line 1 O3. B also sets forth
A's full name, A's title and other important statistics such as his address, and telephone number. B may also
35 include a comment to go with the certification which will be available to any person in the future who needs
to examine A's certificate.
B additionally will indicate an expiration date of the certificate. This date may reflect the date after which
A should not use the certificate. Alternatively, the date may call for any certificate created by A to also expire
on this date. B may also indicate in the certificate an account number for A which may represent an internal
4O identification code within B's organization.
Additionally, B may place a monetary limit in the certificate. This monetary authority or credit limit is
checked against the limit in B's own certificate to insure that B does not delegate more than he is empowered
to delegate. This same relationship is also verified by future recipients as part of their validation process.
As discussed above, B also defines the degree of responsibility to which B is willing is assume for sub-
45 certifications done by A. This field must be compatible with the trust level which is allowed B's own certificate.
The relationship between the trust level granted to B and that granted by B is another of the relationships va-
lidated whenever future recipients validate the hierarchy of certificates which are presented to them.
Finally B inserts cosignature requirements into A's certificate which specify how many and what type of
cosignatures are required to accompany A's signature when A uses this new certificate. As indicated above,
5O cosignatures may be in the form ofjoint signatures andlor counter signatures. The counter signature indicates
an approval of the use of the certificate and the approval necessarily follows the associated signature. Joint
signatures can be done in any order and do not necessarily reflect approval ofthe other signatures, but simply
approval (or recognition) of a common object.
Cosignature requirements may, for example, be specified in the certificate in a variety ofways. One tech-
55 nique which may be used is to explicitly define a list of valid joint signers and a list of valid counter signers.
Associated with each list is the number specifying the minimum associated signatures which must be present
in order for a recipient to recognize the signature as being fully approved. The joint signature list may be a
vector of hash values of each of the set of other public keys. Some specified minimum number of these keys
_ O
EP O 328 232 B_
must appear in certificates ofothersignatures applied to any objectsigned by Awhen using this newcertificate.
Otherwise any recipient should not treat A's signature as valid.
The counter signature list is a vector of hash values of other certificates which must be used to sign any
signature made under the authority of this certificate. Since this references certificates (rather than public
5 keys), it is possible to reference specific certificates which themselves need further joint or counter signing.
By selecting appropriate certificates to appear here, it is possible to create hierarchy of counter signature re-
quirements to whatever a level an organization feels comfortable. A specified number of cosigners is required
from each category. This can range from all the candidates to some subset, for example, O, 1 , 2 or 3.
The set of possible co-signers may be indicated explicity in a list as described here, or implicitly by spec-
1o ifying some quality or attribute specification which is designated in each possible co-signer's certificate.
Other fields may be included in the certificate. For example, the current date and time which reflects the
moment of the initial creation of the certificate. As indicated in Figure 5, the complete certificate consists of
a certificate packet with includes the certificate 11 6 for A and the signature packet 114 of B's signature to A's
certificate.
15 B's signature and the hierarchy of all certificates and signatures which validate it are kept by A and sent
along whenever A uses his certificate. It is contemplated that B or other parties may create several certificates
forA. Forexample, one certificate might allow Ato reliably identify himselfwith no further designated authority.
Another certificate might allow authorization to A of certain limited money amounts without requiring any co-
signatures. A third might allow authorization for larger amounts but require one or more cosignatures. Still an-
2o other might allow A to subcertify other persons according to still different money andlor authority limitations
andl or co-signature specifications.
Assuming that B has created a certificate for A as shown in Figure 5, if B requires no cosigners then the
certificate is complete. However, the certificate which empowered B to create A's certificate may have required
that B have cosigners. There may be one or more joint signature andlor counter signature requirements.
25 Figure 6 exemplifies the steps taken by party C to jointly certify the certificate of A. The requirement to
have a joint signer would be specified in B's own certificate. In this case, a transmitted object (in this case A's
new certificate) signed with B's certificate would be rejected by a recipient if C's joint signature is not also
present on the object.
As shown in Figure 6, if such a joint signature is required, a copy of B's certificate for A is sent to C who
3o mustjointly sign the certificate 12O. C then examines A's certificate 122 and verifies that the public key of the
certificate actually belongs to A in accordance with process outlined in conjunction with Figure 3.
C then examines the signed attributes and authorizations setforth in the certificate including the assigned
monetary level, trust level, etc.. C then, upon concluding that all the fields in B's certificate forAare appropriate,
selects his own certificate with which to perform the signature 126. With his own certificate 128, C signs B's
35 certificate of A 1 32 (1 3O). Once C signs his certificate his signature appears essentially parallel with B's sig-
nature and any other cosigners as shown at 1 34 and 1 36 of Figure 6. Thus, it is important that C exercise as
much caution as B when approving A's certificate. Once A's certificate is created no cosigner may change the
certificate forto do so would create essentially a different object to which none ofthe previous signatures would
apply. If C does not approve the certificate he must avoid signing it, and should have a different certificate
4O constructed and re-signed by all necessary parties. After C adds his joint certificate to B's certificate ofA, A's
certificate packet consists of the certificate for A 1 32, B's signature packet for A's certificate 1 34 and finally
C's signature packet for A's certificate 1 36.
In regard to C's signature packet, it is noted that, in orderfor C to validly sign the certificate, he must select
one of his own certificates which grants him sufficient authority to coverwhat is specified in the new certificate
45 for A. If C has no such certificate, then it is impossible for him to validly sign the certificate since future reci-
pients would reject his certificate as having insufficient authority.
It is noted that C's certificate may also require a counter signature by another party. If so, C forwards the
certificate and all associated signatures to the specified party, e.g., D, to counter sign C's signature. When
D receives the material he performs the same verification steps as C on the new certificate. If he approves,
5O then D adds his signature to the set. However, D signs C's signature rather then the original certificate object.
That is, the object of D's signature is not the object of C's signature (which in this case was the certificate for
A) but rather the object is C's signature itself. This counter signature therefore differs from the joint signature
which is simply another signature of the same object.
The application ofjoint andlor counter signatures can be nested to whatever depth is required, Thus, if D
55 is required to have joint signatures, then this package should be passed to one of D's candidate joint signers
for approval of C's signature. This would be a joint counter signature. Similarly, in organizational hierarchies
it is possible that D might require countersignatures in which case someone else will need to sign D's signature.
As explained above, the recipient of a primary_ _object (such as a purchase ordei) and its associated sig-
EP O 328 232 B_
natures, processes the received materials to insure that the object is identical to the material which existed as
it was signed by the owner of the public key. The process for verifying the signature and for verifying that the
object had not been tampered with has been explained above in regard to Figure 3.
Additionally, the recipient needs to verify that the identity ofthe signer is correct and further that the signer
5 has the proper authority within his organization to make the commitments implied by the received object. The
sender of the object (e.g., the purchase ordei) has the responsibility of sending all generations of antecedent
certificates and signatures (up to and including the meta-certificate) which are needed for a recipient to per-
form validation operations.
In validating the object and its signatures, the recipient may, for example proceed as follows. First the re-
1o cipient insures that the primary object 1 5O has at least one signature. In the example shown in Figure 7, the
primary object 1 5O has four associated joint signatures 1 52, 168, 1 8O and 2OO, each of which has associated
certificates 1 54, 1 7O, 1 82 and 2O2 respectively.
Certificate 1 54 was made requiring joint signatures by the owners of certificates 1 7O, 1 82 and 2O2, and
counter-signatures by the owners ofcertificates 162 and 166 using these specific certificates. The certificate
15 1 54 itself was authorized by the owner of certificate 1 58 as evidenced by signature 1 56.
In this example, the owner of 1 54 has obtained the necessary counter signatures 16O and 164 by the hold-
ers of certificates 1 62 and 1 66, as well as the necessary joint-signatures 168, 1 8O and 2OO.
To provide validation for his signature 168, the owner of certificate 1 7O must include the authorization for
his certificate. His certificate was signed by the holder ofcertificate 1 74 (as evidenced by 1 72), however 1 74's
2o certificate specified that a joint signature by the owner of 1 78 was required in order to fully ratify 1 74's sig-
nature 1 72. Thus signature 1 76 which was made sometime in the past, fulfilled all of 1 74's joint signature re-
quirements and thereby validated (ratified) the use of 1 7O.
Looking at joint signature 1 8O, by the owner of 1 82, we learn that 1 82 requires counter signatures by the
holder of 1 86 using the specific certificate 1 86. The holder of 1 82, did in fact get the counter-signature 1 84
25 by the holder of 1 86. However, certificate 1 86 requires that any signature by 1 86 itself be countersigned by
the holders of certificates 1 9O and 1 94 (using these respective certificates). These two holders have in fact
countersigned 1 84 as evidenced by 1 88 and 1 92. At one further level we learn that certificate 1 94 requires
any signature by 1 94 be countersigned by the holderofcertificate 1 98, which signature 1 96 has been obtained.
Certificate 2O2 requires no co-signature.
3o All certificates must be accompanied by signatures which are themselves authorized by antecedent cer-
tificates. Ultimately all the authority can be traced to a set ofcertificates which have been signed by the holder
of the meta-certificate (or possibly a small set of meta-certificates). Each meta-certificate is well known and
distributed to all parties ''throughout the world''.
The recipient examines every signature supplied and verifies that each accurately signs its purported ob-
35 ject (whether the object is a primary object, a certificate, or another signature) using the procedure detailed
in Figure 3. The recipient insures that each signature includes a corresponding validated certificate.
If a certificate requires joint signatures, then the recipient insures that the required number of these nec-
essary signatures (to the same object) are present. If the certificate requires counter signatures, then the re-
cipient insures that the required number from the designated subset are present (the counter signatures have
4O signatures as their object).
All certificates are then examined. Acheck is made forthe special meta-certificate which has no signature
but which is universally known and trusted and a copy of which is already stored in the recipient's computer.
If a certificate is received which claims to be the meta-certificate but which is not equal to that already known
to and accepted by the recipient, then a rejection is issued. If the meta-certificate is properly recognized, then
45 the validation process continues.
Additionally, a check is made to insure that any other certificate besides the meta-certificate has at least
one signature. As noted above, a check is made to insure that all necessary cosignatures for all presented
objects are present. Additionally, a check is made to determine that antecedent certificates grant sufficient
authority to the subcertificate signers to permit them to validly sign the certificate.
5O In this regard, the trust value in the certificate must be consistent with the antecedent i.e., the certificate
of its signers). By way ofexample only, the following trust field combinations are valid (using the example spe-
cified earlier).
55 _2
EP O 328 232 B_ Tru st __a lue and
__te_ede_t T_u st Va lue I mmedi a te Ce p t i _ i c ate
5 o _
1o o 2
O 3
_ 2
_ 3
15 _ 2
2 3
_o Additionally, any monetary limitations set forth in the certificate must be observed. The money limit al-
Iowed by a certificate must not exceed its antecedent. Additionally a check should be made to insure that the
antecedent's expiration date is compatible with the antecedent's expiration date. By way of example only, a
check may be made to insure that the expiration date in every certificate exceeds the date of each signature
which relies on it. In some cases, it may be desirable to reject any material which is controlled by an obsolete
_5 certificate.
In order to detect ''closed'' authority loops (by which a series of certificates may be structured in a loop
with the last member of the loop granting authority to the first), it is necessary to insure that all authority ulti-
mately flows from recognized meta-certificates. In this manner, a chain of false or artificial certificates which
mutually certify each other will not be inadvertently allowed to incorrectly pass the validation process.
3o One way to accomplish this is to check off certificates in a series of iterations, starting at the top with the
meta-certificate. At each iteration, certificates are scanned and in the process certificates having at least one
checked off antecedent would in turn be checked off. The iteration stops when no new certificates have been
checked off. If any certificates have not been checked off, then these are ''orphans'' which should never have
been supplied. Such a transmitted package would be rejected.
35 Once the signatures and certificates are validated (based on the ultimate authority of the meta-
certificate(s)), the final step is to insure that the commitment inherent in the primary object is within the au-
thority granted to its immediate _oint) signers. This is done by considering the value imputed to the primary
object with the certificates of its signers.
Although the use of a meta-certifier insures that all authority ultimately flows from a trusted source and
4o provides protection, the present invention is not limited to a certification methodology which necessarily in-
cludes a single meta-certifier. On the other hand, it is contemplated by the present invention to allow for the
use of multiple meta-certifiers. These should be certificates governed by entirely independent sources pos-
sibly reflecting the apex of entirely different authorizing hierarchies (e.g., the governmental sector versus the
private sector).
45 Another use of multiple meta-certifiers could be to avoid concentrating full meta-certification responsibil-
ity with one group. For example, it might be uncomfortable to know that there is a single entity which could in
theory create forgeries on behalf of anyone else by creating false certificates. This concern may be alleviated
ifthe meta-certification authority were distributed among different trusted meta-certifiers. Each meta-certifier
would operate completely independently but each certificate would specifically require the others asjoint sign-
5O ers. This would essentially eliminate the possibility that isolated corruption within a single organization would
compromise the system. For example, any organization that wished to be certified would need to have their
own high level master certificate corroborated by each separate entity. Large organizations may likewise wish
to structure their own master certificates to be constructed so as to require joint signatures in order to provide
multiple safeguards against the danger of isolated corruption within the organization.
55 While the invention has been described in connection with what is presently considered to be the most
practical and preferred embodiment, it is to be understood that the invention is not to be limited to the disclosed
embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements in-
cluded within the scope of the appended claims. _3
EP O 328 232 B_
Claims
_ . In a communication system having a plurality of terminal devices (terminals A to N) coupled to a channel
(12) over which users ofsaid terminal devices may exchange messages, at least some of said users hav-
5 ing a public key (3O) and an associated private key (32), a method for managing authority by digitally sign-
ing and certifying a digital message to be transmitted to an independent recipient comprising the steps
of. generating at least a portion of said digital message (2O);
digitally signing at least said portion of said message (4O); and characterised by
1o associating with said message an authorizing digital certificate (28,1 16) having a plurality of digital
fields created by a certifier, said authorizing certificate being created by the steps of.
specifying by the certifier in at least one of said digital fields, the authority which is vested in the
certifier and which has been delegated to the signer of said message, by including suffcient digital in-
formation to enable said independent recipient of said message to verify, by electronically analyzing said
15 message in accordance with a predetermined validation algorithm, that the authority exercised by the
signer in signing the content of said message created by the signer was properly exercised by the signer
in accordance with the authority delegated by the certifier; and
identifying the certifier who has created the signer's certificate in other of said digital fields by in-
cluding sufficient digital information for said recipient of the message to determine by electronically ana-
_o Iyzing said message that the certifier has been granted the authority to grant said delegated authority.
2. A method according to Claim 1 , further including the step of providing at least one field in said message
identifying the nature of the digital data being transmitted.
_5 3. A method according to Claim 1 , wherein the formulating step includes the step of providing a field allowing
the user to insert a predetermined comment (26) regarding the date being transmitted.
4. A method according to Claim 1 , further including the step of applying a hashing function (34) to at least
a portion of the message to be transmitted to form a presignature hash (36); and wherein the digitally
3o signing step includes the step of processing said presignature hash with the signer's private key (32) to
form said digital signature.
_. A method according to Claim 4, further including the step of forming a digital signature packet (42) com-
prising the digital signature and a representation of said at least a portion of the message to be transmit-
ted.
35 6. A method according to Claim 1 , wherein said authorizing certificate (11 6) includes digital fields defining
the cosignature requirements which must accompany the signer's signature in order for the signer's sig-
nature to be treated as properly authorized.
4o l. A method according to Claim 6, wherein said digital fields defining co-signature requirements set forth a
required digital signature by a specified third party indicating approval of the signer's signature (11 6) to
thereby define a counter signature requirement.
8. A method according to Claim 7, wherein the third party countersigns (86) by digitally signing the signer's
45 digital Signatufe.
9. A method according to Claim 6, wherein the cosignature requirements include a digital field specifying
at least one other digital signature which is required to appear in the digital message thereby defining a
joint signature requirement (1 16).
5O _ O. A method according to Claim 1 , wherein said authorizing certificate includes at least one digital field de-
fining limitations as to the authority granted by the certificate (1 16).
__. A method according to Claim 1 O, further including the step of specifying a monetary limit for the signer
in a digital field in said certificate (1 16).
55 _2. A method according to Claim 1 , wherein said authorizing certificate (116) includes at least one digital field
defining a trust level indicative of the degree of responsibility delegated to the signer by the certifier.
_4
EP O 328 232 B_
_ 3. A method according to Claim 1 , wherein said identifying step includes the step ofspecifying in digital fields
in said authorizing certificate a hierarchy of certificates, whereby a recipient of the message can elec-
tronically verify in accordance with a predetermined validation algorithm the authority of the signer based
upon an analysis of the signed message.
5 Patentanspr ü_he
_ . Verfahren zur Handhabung der Zugriffsberechtigung durch digitale Bezeichnung und Zulassung einer di-
1o gitalen Nachricht, die an einen unabhängigen Empfänger übermittelt werden soll, bei einem Kommuni-
kationssystem mit einer Vielzahl von Datenstationen (Datenstationen A bis N), die mit einem Kanal (1 2)
verbunden sind, über den Benutzer der Datenstationen Nachrichten austauschen können, wobei wenig-
stens einige der Benutzer eine öffentliche Verschlüsselung (3O) und eine zugeordnete private Verschlüs-
selung (32) besitzen, weist folgende Schritte auf.
15 Erzeugung wenigstens eines Bereichs der digitalen Nachricht (2O);
digitale Bezeichnung wenigstens dieses Bereiches der Nachricht (4O); und gekennzeichnet durch
Verknüpfung der Nachricht mit einer berechtigenden digitalen Zulassung (28, 1 1 6) mit einer Vielzahl von
durch eine Zulassungseinheit erzeugten digitalen Felder, wobei die berechtigende Zulassung durch fol-
gende Schritte erzeugt wird.
2o Festsetzung der Zugriffsberechtigung, die durch die Zulassungseinheit verliehen wurde und die im Be-
zeichner der Nachricht angeordnet worden ist, durch die Zulassungseinheit in wenigstens einem der di-
gitalen Felder, durch Einbinden geeigneter digitaler Information, um dem unabhängigen Empfänger der
Nachricht zu ermöglichen durch elektronische Analyse der Nachricht gemä_ eines vorbestimmten Be-
rechtigungsalgorithmus zu prüfen, da_ die Zugriffsberechtigung, die durch den Bezeichner beim Bezeich-
25 nen des Inhalts der durch den Bezeichner erzeugten Nachricht, gemä_ der durch die Zulassungseinheit
angeordneten Zugriffsberechtigung passend durch den Bezeichner vergeben wurde; und
Identifizierung der Zulassungseinheit, der die Zulassung des Bezeichners in anderen digitalen Feldern
durch Einbinden geeigneter digitaler Information für den Empfänger der Nachricht erzeugt hat, um durch
elektronische Analyse der Nachricht, die die Zulassungseinheit erteilt hat, die Zugriffsberechtigung zu be-
3o stimmen, um die angeordnete Zugriffsberechtigung zu erteilen.
2. Ein Verfahren nach Anspruch 1 , welches au_erdem den Schritt aufweist, wenigstens ein Feld in der Nach-
richt vorzusehen, um die Art der übermittelten digitalen Daten zu identifizieren.
35 3. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, da_ der Formulierungsschritt einen Schritt auf-
weist, der ein Feld vorsieht, das dem Benutzer das Einfügen eines vorbestimmen Kommentan (26) be-
züglich der übermittelten Daten gestattet.
4. Verfahren nach Anspruch 1 , welches zusätzlich den Schritt aufweist, eine Kontrollfunktion (34) auf we-
4o nigstens einen Bereich der zu übermittelnden Nachricht anzuwenden, um eine vorbezeichnete Kontrolle
(36) zu bilden; und wobei der digitale Bezeichnungsschritt einen Schritt zur Erzeugung der vorbezeich-
neten Kontrolle mit der privaten Verschlüsselung (32) des Bezeichners aufweist, um die digitale Kennung
zu bilden.
_. Verfahren nach Anspruch 4, welches zusätzlich den Schritt zur Zusammenstellung eines digitalen Ken-
45 nungipaketi (42) au Fwe_iit, der e_ine d_ig_ita_e Kennung und e_ine _epra__ientat_ion wen_igiteni e_inei Bere_ichi
der zu übermittelnden Nachricht enthält.
6. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, da_ die Zugriffsberechtigungs-Zulassung (1 1 6) di-
gitale Felder aufweist, die Zusatzbezeichnungserfordernisse, die zur Kennung des Bezeichners gehören,
5O definieren, io da_ die Kennung dei Bezeichneri io behandelt werden kann, ali ob iie geeignet zugriffi_
berechtigt ist.
l. Verfahren nach Anspruch 6, dadurch gekennzeichnet, da_ die digitalen Felder, die die Zusatzkennungs-
erfordernisse definieren, eine erforderliche digitale Kennung durch eine spezifische dritte Partei bekannt
55 machen, die das Zulassen der Bezeichnerkennung (1 1 6) anzeigen, um dadurch eine Zähleranforderungs-
kennung zu definieren.
8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, da_ die dritte Partei (86) durch digitales Bezeich-
_ _
EP O 328 232 B_
nen die digitale Bezeichnerkennung bestätigt.
9. Verfahren nach Anspruch 6, dadurch gekennzeichnet, da_ die Zusatzkennungserfordernisse ein digitales
Feld beinhalten, das wenigstens eine weitere digitale Kennung spezifiziert, die erforderlich ist, um in der
5 digitalen NaChfiCht aufzutauChen, um dadufCh eine VefbindungSkennungSanf_fdefung (1 16) zu definie-
fen.
_ O. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, da_ die Zugriffsberechtigungszulassung wenig-
stens ein digitales Feld beinhaltet, das die Grenzen entsprechend der durch die Zulassung (11 6) erteilten
1o Zugriffsberechtigung bestimmt.
__. Verfahren nach Anspruch 1 O, welches au_erdem den Schritt aufweist, eine geldliche Grenze für den Be-
zeichner in einem digitalen Feld in der Zulassung (116) zu spezifizieren.
_2. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, da_ die Zugriffsberechtigungszulassung (1 16) we-
15 n_igiteni e_in d_ig_ita_ei Fe_d be_inha_tet, dai e_inen vertraueniwert deF_in_iert, der den Grad der vertraueni-
würdigkeit anzeigt, der dem Bezeichner durch die Zulassungseinheit zugewiesen wurde.
_3. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, da_ der Identifizierungsschritt einen Schritt bein-
haltet, der in den digitalen Feldern bei derZugriffsberechtigungszulassung eine Hierarchie von Zulassun-
2O gen ermittelt, wobei ein Empfänger der Nachricht elektroniich gemä_ einem vorbeitimmten Berechti-
gungsalgorithmus die Zugriffsberechtigung des Bezeichners, die auf einer Analyse der bezeichneten
Nachricht basiert, verifizieren kann.
25 _eve_di_a_io__
_ . Procédé pour gérer l'habilitation par signature numérique et la certification d'un message numérique à
transmettre à un destinataire indépendant dans un système de communications comportant une pluralité
de dispositifs terminaux (terminaux A à N) connectés à un canal (12) par lequel les utilisateurs desdits
3O diipoiitifi terminaux peuvent échanger dei meiiagei, au moini un certain nombre deiditi utiliiateuri
ayant une clé publique (3O) et une clé privée associée (32), ledit procédé comprenant les étapes de .
- génération d'au moins une partie dudit message numérique (2O) ;
- signature numérique (4O) d'au moins ladite partie dudit message ; et étant caractérisée par
l'association audit message d'un certificat d'habilitation numérique (28, 11 6) comportant une
35 pluralité de champi numériquei crééi par un certificateur, ledit certificat d'habilitation étant créé par
Ies étapes consistant à .
- spécifier par le certificateur dans au moins un desdits champs numériques, l'habilitation dont est
investi le certificateur et qui a été déléguée au signataire dudit message, en ajoutant une information
numérique suffisante pour permettre audit destinataire indépendant dudit message de vérifier, en
4O analyiant électroniquement ledit meiiage ielon un algorithme de validation prédéterminé, que l'ha-
bilitation exercée par le signataire en signant le contenu dudit message créé par le signataire était
correctement exercée par le signataire selon l'habilitation déléguée par le certificateur ; et
- identifier le certificateur qui a créé le certificat du signataire dans un autre desdits champs numé-
riques en ajoutant une information numérique suffisante pour que ledit destinataire du message dé-
45 termine par analyie électronique dudit meiiage que le certificateur a eu l'accord d'habilitation pour
déléguer ledit accord d'habilitation.
2. Procédé selon la revendication 1 , comprenant en outre une étape de création d'au moins un champ dans
Iedit message identifiant la nature des données numériques qui sont transmises.
5O 3. Procédé selon la revendication 1 , dans lequel l'étape de formulation comprend l'étape de création d'un
champ permettant à l'utilisateur d'introduire un commentaire prédéterminé (26) concernant les données
qui sont transmises.
55 4. Procédé selon la revendication 1 , comprenant en outre une étape d'application d'une fonction (34) per-
mettant de condenser au moins une partie du message à transmettre, pour constituer un condensé de
présignature (36) et dans lequel l'étape de signature numérique comprend l'étape de traitement dudit
condensé de présignature au moyen de la clé privée (32) du signataire pour constituer ladite signature
_6
EP O 328 232 B_
numérique.
_. Procédé selon la revendication 4, comprenant en outre une étape de formation d'un paquet de signature
numérique (42) comprenant la signature numérique et une représentation d'au moins une partie du mes-
5 Sage à tfanSmettfe.
6. Procédé selon la revendication 1 , dans lequel ledit certificat d'habilitation (1 16) comprend des champs
numériques définissant les obligations de co-signature qui doivent accompagner la signature du signa-
taire afin que la signature du signataire soit traitée comme une habilitation correcte.
1O l. Procédé selon la revendication 6, dans lequel lesdits champs numériques définissant les obligations de
co-signature présentent une signature numérique obligatoire d'une tierce personne spécifiée, qui indique
l'approbation de la signature du signataire (1 16) pour définir par ce moyen une obligation de contre-
signature.
15 8. proce_de_ se_on _a revend_icat_ion _, dans _eque_ _a t_ierce personne contre-s_igne (86) en s_ignant nume_r_ique-
ment la signature numérique du signataire.
9. Procédé selon la revendication 6, dans lequel les obligations de co-signature comprennent un champ nu-
mérique définissant au moins une autre signature numérique qui doit apparaitre obligatoirement dans le
2O message numérique, définissant par ce moyen une obligation de signature jointe (1 16).
_ O. Procédé selon la revendication 1 , dans lequel ledit certificat d'habilitation comprend au moins un champ
numérique définissant des limitations identiques à celles de l'habilitation accordée par le certificat (11 6).
25 __. PfOCédé SelOn la fevendiCatiOn 1 O, COmpfenant en Outfe une étape de SpéCifiCatiOn d'une limite mOnétaife
pour le signataire dans un champ numérique dudit certificat (116).
_2. Procédé selon la revendication 1 , dans lequel ledit certificat d'habilitation (11 6) comprend au moins un
champ numérique définissant une niveau de confiance représentatifdu degré de responsabilité déléguée
3o au signataire par le certificateur.
_3. Procédé selon la revendication 1 , dans lequel ladite étape d'identification comprend une étape de spé-
cification dans les champs numériques dans ledit certificat d'habilitation d'une hiérarchie de certificats,
de sorte que le destinataire du message peut vérifier électroniquement, selon un algorithme de validation
35 prédéterminé, l'habilitation du signataire fondée sur une analyse du message signé.
4O
45
5O
55 _l
(PICTURE)
EPO328232B_
(PICTURE)
' _oMM_N/__if__i7___ _H___f_ /_
_8
_
EP O328232 B_
F _ _ _ _X___-__/_______
(PICTURE)
_D' __ VX__F/__
_9
(PICTURE)
EP O 328 232 B_
2O
(PICTURE)
EP O 328 232 B_
2_
(PICTURE)
EP O 328 232 B_
_\0 22
(PICTURE)
_(PICTURE)_ _
EP O 328 232 B_
23