(12) United States Patent
`Haverty
`
`USOO6189096B1
`US 6,189,096 B1
`(10) Patent No.:
`Feb. 13, 2001
`(45) Date of Patent:
`
`(54) USER AUTHENTIFICATION USINGA
`VIRTUAL PRIVATE KEY
`
`(75) Inventor: Rand Haverty, Ottawa (CA)
`(73) Assignee: Kyberpass Corporation, Nepean
`Ontario (CA)
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/129,795
`(22) Filed:
`Aug. 6, 1998
`Related U.S. Application Data
`(60) Provisional application No. 60/084,410, filed on May 6,
`1998.
`(51) Int. Cl." ........................................................ H04L 9/32
`(52) U.S. Cl. .......................... 713/155; 713/156; 713/170;
`713/181; 713/183; 713/185; 713/178
`(58) Field of Search ..................................... 713/155, 156,
`713/175, 178, 154, 170, 181, 183, 185,
`201; 709/229
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,351,295
`5,442,342
`5,497,421
`5,666,415
`5,764,772
`
`9/1994 Perlman et al. ..................... 713/162
`8/1995 Kung ............................... 340/825.34
`3/1996 Kaufman et al. .
`9/1997 Kaufman .............................. 713/159
`6/1998 Kaufman et al. ...................... 380/30
`
`
`
`FOREIGN PATENT DOCUMENTS
`0307627
`3/1989 (EP).
`0661844 A2 12/1994 (EP).
`00807911
`11/1997 (EP).
`
`* cited by examiner
`
`Primary Examiner-Gilberto Barrón, Jr.
`(74) Attorney, Agent, or Firm-Sughrue, Mion, Zinn,
`Macpeak & Seas, PLLC
`(57)
`ABSTRACT
`A method, computer System, and program product provides
`for authentication of user messages using PKI technology in
`environments where limited capacity prevents direct PKI
`technology use, and Strong Security is provided using mag
`netic Swipe cards or the like, and a pass phrase is used for
`enhanced Security and to avoid the need for Special purpose
`devices. The invention is advantageous where there are
`limitations on the space available for PKI credentials, such
`as in the uSerid and password fields of a remote access
`protocol. PKI techniques are used without transferring
`lengthy keys or certificates once an initial registration pro
`ceSS is complete. A Secret key is used. A digest is computed
`of the Secret key, the user's certificate Serial number, and a
`time Stamp. The digest, together with the user's certificate
`Serial number and the time Stamp, forms a compact message
`that may be transmitted. Private keys and Secret keys are not
`Sent during authentication. Replay attacks are prevented.
`
`62 Claims, 11 Drawing Sheets
`
`compute digest of
`unencrypted message
`
`410
`
`encrypt digest with
`sender's private key
`
`420
`
`combine encrypted
`digest with
`unencrypted message
`
`430
`
`encrypt
`message-digest using
`receiver's public key
`
`440
`
`Lenovo
`Ex. 1029 - Page 1
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 1 of 11
`
`US 6,189,096 B1
`
`F.G. 1
`
`110
`
`12O
`
`Security
`Server
`
`
`
`
`
`130
`
`Applications
`Server
`
`Lenovo
`Ex. 1029 - Page 2
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 2 of 11
`
`US 6,189,096 B1
`
`
`
`txm
`
`Lenovo
`Ex. 1029 - Page 3
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 3 of 11
`
`US 6,189,096 B1
`
`
`
`Lenovo
`Ex. 1029 - Page 4
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 4 of 11
`
`US 6,189,096 B1
`
`Fig. 4
`
`
`
`compute digest of
`unencrypted message
`
`41 O
`
`encrypt digest with
`sender's private key
`
`42O
`
`combine encrypted
`digest with
`unencrypted message
`
`43O
`
`encrypt
`message-digest using
`receiver's public key
`
`440
`
`Lenovo
`Ex. 1029 - Page 5
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet S of 11
`
`US 6,189,096 B1
`
`Fig. 5
`begin
`
`510
`
`tXm
`decrypt with receiver's
`private key
`
`edm
`separate message and
`encrypted digest
`
`53O
`
`
`
`determine sendler's
`identity from
`unencrypted message
`
`
`
`compute digest of
`unencrypted message
`
`ed
`
`550
`
`determine sendler's
`public key
`
`decrypt digest using
`sender's public key
`
`54O
`
`cc.
`
`dic
`
`560
`
`570
`
`O
`
`yes
`
`message was not sent
`by sender or was
`altered
`
`
`
`message was sent by
`sender and was not
`altered
`
`58O
`
`590
`
`Lenovo
`Ex. 1029 - Page 6
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 6 of 11
`
`US 6,189,096 B1
`
`
`
`
`
`compare
`
`
`
`separate
`
`51O
`
`Lenovo
`Ex. 1029 - Page 7
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 7 of 11
`
`US 6,189,096 B1
`
`Fig. 7
`
`110
`
`7OO
`
`Communications
`Server
`
`
`
`
`
`
`
`12O
`
`Security
`Server
`
`
`
`
`
`130
`
`Applications
`Server
`
`Lenovo
`Ex. 1029 - Page 8
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 8 of 11
`
`US 6,189,096 B1
`
`
`
`establish Connection
`and request
`registration
`
`get private key from
`Se
`
`generate secret key
`
`encrypt secret key
`with user's public key
`and store at client
`
`send encrypted
`message to security
`server with secret key,
`user's certificate, and
`digital signature
`
`send security server's
`certificate to client
`
`decrypt message and
`ensure validity with
`digital signature and
`Walidate ser
`Certificate
`
`store user's certificate;
`encrypt and store
`client's secret key with
`the certificate
`
`Lenovo
`Ex. 1029 - Page 9
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 9 of 11
`
`US 6,189,096 B1
`
`Fig. 9
`
`110
`
`7OO
`
`120
`
`get private key from
`se
`
`retrieve from storage
`and decrypt user's
`secret key
`
`prepare preliminary
`message with user's
`certificate slin, a time
`stamp, and user's
`secret key
`
`910
`
`920
`
`930
`
`compute digest for
`preliminary message
`
`940
`
`
`
`prepare transmission
`message having user's
`certificate slin, the time
`stamp, and the
`preliminary digest
`
`950
`
`send transmission
`message to security
`server in userid I
`password fields
`
`96.O
`
`
`
`97O
`
`975
`
`98O
`
`obtain user's
`certificate sln and the
`time stamp from
`transmission message
`
`retrieve from storage
`and decrypt secret key
`Corresponding to
`user's certificate
`
`compute digest of
`user's certificate sln,
`the time stamp, and
`the retrieved secret
`key
`
`
`
`
`
`
`
`Compare computed
`digest with preliminary
`digest received in
`transmission message
`
`
`
`
`
`Compare the received
`time stamp with time
`stamp of most recent
`message from user
`
`validate user's
`certificate
`
`992
`
`Lenovo
`Ex. 1029 - Page 10
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 10 of 11
`
`US 6,189,096 B1
`
`
`
`Fig. 10
`
`establish connection and
`request registration
`
`send security server's
`Certificate to client
`
`compute digest of reference
`as Secret key
`
`get private key from user
`
`send encrypted message to
`security server with secret
`key, user's certificate, and
`digital signature
`
`decrypt message and ensure
`validity with digital signature
`and validate user's certificate
`
`store user's certificate;
`encrypt and store client's
`secret key with the
`certificate
`
`Lenovo
`Ex. 1029 - Page 11
`
`

`

`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 11 of 11
`
`US 6,189,096 B1
`
`Fig.11
`
`110
`
`12O
`
`obtain reference
`
`compute digest of reference
`as secret key
`
`1110
`
`1120
`
`prepare preliminary message
`with user's certificate sln, a
`time stamp, and user's secret
`key
`
`93O
`
`compute digest for
`preliminary message
`
`
`
`prepare transmission
`message having user's
`certificate sln, the time
`stamp, and the preliminary
`digest
`
`940
`
`950
`
`send transmission message
`to security server
`
`1160
`
`
`
`t
`obtain user's certificate sln
`and the time stamp from
`transmission message
`
`retrieve from storage and
`decrypt secret key
`corresponding to user's
`certificate
`
`f
`te di
`compute digest of user's
`certificate slin, the time
`stamp, and the retrieved
`secret key
`
`compare computed digest
`with preliminary digest
`received in transmission
`message
`
`compare the received time
`stamp with time stamp of
`most recent message from
`Se
`
`97O
`
`975
`
`98O
`
`985
`
`990
`
`Walidate user's certificate
`
`992
`
`Lenovo
`Ex. 1029 - Page 12
`
`

`

`US 6,189,096 B1
`
`1
`USER AUTHENTIFICATION USINGA
`VIRTUAL PRIVATE KEY
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`This application is an application filed under 35 U.S.C. S
`111(a) claiming benefit pursuant to 35 U.S.C. S 119(e)(1) of
`the filing date of the Provisional Application 60/084,410
`filed on May 6, 1998; pursuant to 35 U.S.C. S 111(b). The
`Provisional Application 60/084,410 is incorporated by ref
`CCCC.
`
`2
`One example of Such an environment involves cards with
`magnetic Strips. Devices Such as credit cards and other
`magnetic Swipe cards do not have the capacity to Store 2,000
`bytes. Thus, Such devices cannot use digital ignatures.
`Another example of a limiting environment exists in
`remote acceSS Systems. Here, the client Station does not
`communicate directly with a Security Server. Instead, the
`client Station communicates with a communications Server,
`which, in turn, communicates with a remote acceSS Security
`Server. The protocol used for communication between the
`client Station and the communications Server is typically
`designed to get a uSerid and password from the user. A
`typical example of such a protocol is the Point to Point
`Protocol (PPP). Such userid/password oriented protocols
`can pass about 60 bytes in their uSerid/password fields,
`which is insufficient to support for the direct use of public
`key technology for user authentication, encryption, or for
`digital Signatures. Thus, PKI authentication cannot effec
`tively be used in this type of remote access System.
`To combat the weak link problem, there have been
`developed So-called “two-factor” techniques for improving
`the Strength of the user authentication procedure. Here,
`authentication of the user is based on two factors:
`Something the user knows (e.g., a password), and Some
`thing a user has (e.g., a Smart card, a fingerprint, or the like).
`In a System operating according to a two factor technique,
`even if an intruder knows the password of a Ser, the intruder
`will not be authenticated unless he satisfies the other factor
`(i.e., possesses the necessary Smart card or fingerprint).
`Two factor techniqueS provide very Strong protection, and
`overcome the weak link problem of password protection, but
`are very disadvantageous. The disadvantage of a system
`using a two factor technique is the requirement for addi
`tional devices to perform user authentication. For example,
`a System using the two factor technique might employ a
`Smart card as one of the two factors. This necessitates the
`presence of a card reader adapted to read the Smart card.
`Likewise, relying on a user's fingerprint is as a factor
`requires a fingerprint Scanner.
`Such additional devices are not commonly included with
`computer Systems today, and this is problematic for the user
`who needs to use a WorkStation that has no Such additional
`device. Moreover, Such additional devices may be costly.
`Two-factor techniques provide for improved user
`authentication, and overcome the weak link problem of
`password protection, but they are nevertheless an undesir
`able Solution.
`What is needed is an improved approach to user authen
`tication which overcomes the weak link problem of pass
`word protected private keys, but which also avoids the
`above-identified disadvantages of the two factor techniques.
`Also, what is needed is a way to use PKI technology in
`environments where Storage is limited.
`SUMMARY OF THE INVENTION
`This invention involves solving the above-identified prob
`lems using digests in a two Step process of registration and
`authentication.
`In one preferred embodiment, there is a method of user
`authentication using PKI technology in environments where
`limited capacity prevents direct PKI technology use. In a
`magnetic Swipe card System, the data Storage is the capacity
`that is limited. In a remote access (dial-up) System, the
`length of the uSerid/password fields is the capacity that is
`limited. The method according to the invention is most
`
`5
`
`15
`
`35
`
`25
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates to a method for providing Strong
`authentication of users within a Public Key Infrastructure
`(PKI).
`In one preferred embodiment, the invention involves
`using a virtual private key. The invention also relates to a
`program product bearing Software which enables user
`authentication with a virtual private key to be practiced on
`a computer System. The invention further relates to a com
`puter System which operates So that user authentication is
`performed using a virtual private key.
`In a Second preferred embodiment, the invention involves
`a method for providing Strong authentication of users within
`a PKI using a device Such as a magnetic Swipe card or a
`biometric device. The invention also relates to a program
`product bearing Software which enables user authentication
`with a magnetic Swipe card or the like to be practiced on a
`computer System. The invention further relates to a com
`puter System which operates So that user authentication is
`performed using a magnetic Swipe card or the like.
`In a third preferred embodiment, the invention involves a
`method for providing Strong authentication of users within a
`PKI using a pass phrase. The invention also relates to a
`program product bearing Software which enables user
`authentication with a pass phrase to be practiced on a
`computer System. The invention further relates to a com
`puter System which operates So that user authentication is is
`40
`performed using a pass phrase.
`2. Related Art
`In PKI Systems today, authentication of a user may be
`based on that user's knowledge of a private key. Private
`keys, however, are not Something that a user can be expected
`to remember and to enter himself. It is often the case,
`therefore, that a user's private key is Stored in encrypted
`from on the user's personal computer, and is accessed by the
`user with a password. This is a problem, however, because
`now it the password which becomes the weakest link in the
`Security chain. Passwords that users can remember are
`notorious for being easy to determine by the clever intruder
`or hacker. If that password can be hacked by an intruder,
`then the otherwise strong security offered by the PKI is
`reduced to Simple password-based Security.
`Thus, today's PKI systems may be said to have a weak
`link problem because of the private key being only password
`protected.
`Another problem is that PKI is cannot readily be used in
`certain environments where Storage is limited.
`To explain, it should be noted that PKI systems use digital
`Signatures to ensure the authenticity of the Sender is of a
`message. Up to 2,000 bytes are required for digital Signa
`tures based on 1024-bit keys. However, in some situations,
`it is not practical or possible to directly use PKI technology,
`especially digital Signatures, due to limitations in the envi
`rOnment.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Lenovo
`Ex. 1029 - Page 13
`
`

`

`3
`useful where there are limitations on the Space available for
`PKI credentials.
`According to this first embodiment of the invention, a
`novel dialog is used in Such a way that PKI techniques can
`be used without actually transferring lengthy keys or cer
`tificates. The method of the invention also includes a tech
`nique for mapping a relatively short data field onto a full
`private key field.
`In the case of applying the method of the invention to
`remote access environments, the invention modifies both the
`conventional registration and authentication processes nor
`mally used.
`According to the invention, a virtual private key is used
`so that PKI can be used without passing actual PKI keys,
`certificates, or digital Signatures.
`In the main, the invention resides in a method, a computer
`System, and a computer program product providing for
`authentication of user messages using PKI technology in
`environments where limited capacity prevents direct PKI
`technology use. The invention is advantageous where there
`are limitations on the space available for PKI credentials,
`Such as in the uSerid and password fields of a remote acceSS
`protocol. PKI techniques are used without actually transfer
`ring lengthy keys, certificates, or digital Signatures once an
`initial registration proceSS is complete. A private key authen
`ticates a user at a client and is used to retrieve a stored,
`encrypted Secret key. A digest is computed of the Secret key,
`the user's X.509 ISO standard public key certificate, and a
`time Stamp. To further minimize the Size of the message, the
`unique Serial number of the user's certificate (the certificate
`Serial number, also referred to as the certificate S/n) may be
`employed. The digest, together with the user's certificate
`Serial number and the time Stamp, forms a compact message
`that may be transmitted in the uSerid and password fields of
`a remote acceSS protocol. The private key and the Secret key
`are not sent. The Secret key, Stored beforehand at the Server,
`is used along with the Sent user's certificate Serial number
`and the Sent time Stamp to compute another digest which is
`compared with the first digest. When the two digests match,
`the user is considered authentic. The time Stamp is used to
`prevent replay attackS.
`In a Second embodiment of the invention, there is pro
`Vided a way to use certain information referred to as a
`“reference' instead of a user's private key. Basically, the
`Second embodiment differs from the first embodiment in that
`the user's private key is required during only the registration
`process. Thereafter, the user's private key is not used but,
`rather, a reference is read from Something the user has, Such
`as a magnetic Swipe card or a biometric device. The refer
`ence is digested to provide a client Secret key, and a
`preliminary digest is made of the user's certificate Serial
`number, a time Stamp, and this Secret key. This preliminary
`digest is sent, along with the user's certificate Serial number
`and the time Stamp, to the authentication Server. The authen
`tication Server may store the reference itself or may store a
`digested version of the reference. The digested reference
`Serves as the Server Secret key. Upon receipt of the message,
`authentication is performed by digesting the time Stamp and
`user certificate Serial number and Secret key, and comparing
`this computed digest with the preliminary digest Sent in the
`message. This embodiment of the invention is advantageous
`in that the reference is not Stored at the client. A hacker
`cannot obtain the reference by attacking the client Station.
`Also, the user's private key is not used after registration.
`Moreover, when the user has a magnetic Swipe card or the
`like, the user can very easily determine when the card is
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,189,096 B1
`
`4
`missing. Instead of a magnetic Swipe card, the reference may
`be provided by a fingerprint reader, retinal Scanner, or the
`like. In addition, the reference itself is Sent only during the
`registration process, and thereafter is not per Se Sent over the
`network.
`According to the third preferred embodiment of the
`invention, there is provided a passphrase which Substitutes
`for the reference. In other words, the third embodiment is
`Substantially similar to the Second except that the user does
`not provide a “thing” Such as a Swipe card or a fingerprint.
`The user provides from memory a passphrase which Serves
`as a reference. Like the reference, the pass phrase is not
`stored at the client and cannot therefore be discovered by
`hacker. AS in the Second embodiment, the user's private key
`is used during only the registration process, and the pass
`phrase is not per Se Sent over the network afterward.
`Moreover, the third embodiment of the invention does not
`require any card reader or biometric device because the pass
`phrase may be entered using a keyboard.
`The advantages and operations of the invention will
`become more clear in the light of the detailed description
`below taken in conjunction with the drawing figures.
`BRIEF DESCRIPTION OF THE DRAWING
`FIGURES
`FIG. 1 illustrates a Security Server approach to network
`Security.
`FIG. 2 illustrates the use of public and private keys in a
`PKI system.
`FIG. 3 illustrates a public key look-up table.
`FIG. 4 illustrates how a digital Signature may be included
`in a message.
`FIG. 5 illustrates how a digital signature included in a
`message may be verified.
`FIG. 6 illustrates the data flows involved in digital sig
`nature production and verification.
`FIG. 7 illustrates a remote access environment.
`FIG. 8 illustrates a registration procedure for a Virtual
`Private Key (VPK).
`FIG. 9 illustrates an authentication procedure using a
`VPK.
`FIG. 10 illustrates a registration procedure in different
`embodiments of the invention.
`FIG. 11 illustrates an authentication procedure corre
`sponding to the registration procedures of FIG. 10.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The presently preferred embodiments of the invention
`will now be described, first with respect to a remote acceSS
`environment. Afterward, the invention will be described
`with respect to a magnetic Swipe card environment. Then,
`the invention will be described with respect to a passphrase.
`The description of these three presently preferred embodi
`ments includes numerous details. It is to be understood,
`however, that the present invention may be practiced with
`out incorporating these specific configurations.
`Embodiment of the Invention in a Remote Access
`Environment
`In particular, the description of the invention in a remote
`acceSS environment will begin with a description of Some of
`the underlying principles of the invention, to wit, the Secu
`rity Server approach to Security, the use of public and private
`keys in a PKI System, and digital Signatures.
`
`Lenovo
`Ex. 1029 - Page 14
`
`

`

`US 6,189,096 B1
`
`15
`
`35
`
`40
`
`25
`
`S
`Security is a Serious problem on the Internet and other
`public networks today. An important aspect of network
`Security is user authentication. User authentication includes
`the verification of the identity of a user at the initiation of a
`Session or other activity, and also the prevention of unau
`thorized mimicry of an already-Verified user.
`To deal with Security, the industry has adopted a Security
`Server approach. Under this approach, a Security Server is
`interposed between a client and an applications Server. The
`role of the security server is to be the sole link between the
`client and the applications Server. The Security Server estab
`lishes communications between the client and the applica
`tions Server if and only if the user at the client is authenti
`cated. The term "security Server, as used in this Sense, is
`meant to encompass Security Servers, proxy Servers,
`firewalls, and authentication Servers.
`The Security Server Approach
`The Security Server approach is illustrated, in Very Sim
`plified form, in FIG. 1. In FIG. 1, reference numeral 10
`indicates a client. A client may be understood to be a proceSS
`that runs on a general purpose or Specialized computer
`System. A client, as a process, may represent a user wishing
`to perform Some operation with respect to an application on
`a network.
`In FIG. 1, reference numeral 20 indicates a security server
`and reference numeral 30 indicates an applications Server.
`There is no direct communication between the client 10 and
`the applications server 30. The security server 20 is inter
`posed between client 10 and applications server 30. Security
`Server 20 may be understood to be a process that runs on a
`general purpose or Specialized computer System. Applica
`tions server 30 also may be understood to be a process in like
`C.
`More particularly, a user wishing to perform Some opera
`tion with respect to a network uses client 10 as his interface
`to the network, and communicates via Security Server 20
`with applications server 30. The operation desired by the
`user is to be performed by applications server 30. By
`interposing Security Server 20 as shown in FIG. 1, a certain
`measure of Security is obtained. That is, users who are
`authorized to cause operations to be performed by applica
`tions server 30 are authenticated by security server 20, and
`are allowed to cause Such operations. Users who are not So
`authorized are prevented by, Security Server 20, from passing
`commands to cause unauthorized operations to applications
`Server 30.
`It is typical that the computer Systems, upon which run
`client 10, security server 20, and applications server 30 all
`run, are physically different computer Systems Separated by
`great distances. Although this arrangement is typical, the
`concept of the Security Server approach applies also even
`when the three foregoing processes are not running on
`physically different computer Systems, or are not on com
`55
`puter Systems Separated by great distances. It will be
`appreciated, however, that the general context of this
`description relates to the typical arrangement just described.
`The manner in which the computer Systems communicate
`is treated herein at a high level, and the details are omitted
`for the sake of clarity. For more detailed information on Such
`communications, reference may be made to Data and Com
`puter Communications or to Local Networks, both by Wil
`liam Stallings, and both incorporated by reference in their
`entirety for their useful background information.
`Processes (including client processes, Security server
`processes, and applications server processes), on a practical
`
`45
`
`50
`
`60
`
`65
`
`6
`level, are Supplied as Software on any one of a variety of
`media. Furthermore, the Software actually is or is based on
`Statements written in a programming language. Such pro
`gramming language Statements, when executed by a
`computer, cause the computer to act in accordance with the
`particular content of the Statements, thereby causing the
`defined process to run in a predetermined manner.
`Furthermore, software may be provided in any number of
`forms including, but not limited to, original Source code,
`assembly code, object code, machine language, compressed
`or encrypted versions of the foregoing, and any and all
`equivalents.
`One knowledgeable in computer Systems will appreciate
`that “media', or “computer-readable media', as used here,
`may include a diskette, a tape, a compact disc, an integrated
`circuit, a cartridge, a remote transmission via a communi
`cations circuit, or any other Similar medium uSeable by
`computers. For example, to Supply Software that defines a
`process, the Supplier might provide a diskette or might
`transmit the Software in Some form via Satellite
`transmission, via a direct telephone link, or via the Internet.
`Although Such Software instructions might be “written
`on a diskette, “Stored in an integrated circuit, or “carried
`over a communications circuit, it will be appreciated that,
`for the purposes of this discussion, the computer usable
`medium will be referred to as “bearing” the software. Thus,
`the term “bearing” is intended to encompass the above and
`all equivalent ways in which Software may be associated
`with a computer usable medium.
`For the Sake of Simplicity, therefore, the term “program
`product' is hereafter used to refer to a computer uSeable
`medium, as defined above, which bears Software in any
`form.
`FIG. 1 thus illustrates one typical arrangement to provide
`for Security in a network of computer Systems.
`PKI Technology
`To ensure the privacy of communications, there has been
`developed a system known as a Public Key Infrastructure
`(PKI). In a PKI system, each party or user has two crypto
`graphic keys. The two cryptographic keys are a public key
`and a private key. The public key of a user is a key which
`is available to any other user. The private key of a user is
`never revealed to any other user. The use of private and
`public keys will now be discussed using a simplified
`example. For more detailed information concerning PKI
`Systems, reference may be made to Secure Electronic
`Commerce, by Warwick Ford and Michael Baum, Prentice
`Hall, ISBN 0-13-476342-4, which is hereby incorporated by
`reference in its entirety for its useful background informa
`tion.
`FIG. 2 shows a sender, indicated by User A, and a
`receiver, indicated by User B. User A wishes to send a
`message m to user Bunder a PKI system. In this PKI system,
`User B has a public key B-pub and a private key B-pri.
`FIG.3 shows a table 300 which is available to the persons
`in the PKI system. It will be appreciated that, although the
`actual implementation of table 300 in a PKI system is not
`exactly that is illustrated in FIG. 3, the concepts are the
`same. Table 300 may be referred to as a public key look-up
`table. Public key look-up table 300 includes, for each user,
`information Such as a certificate Serial number, a user name,
`and a public key. The certificate Serial number typically is a
`numeric identifier that uniquely identifies a particular user.
`The user name may be an alphanumeric for conveniently
`identifying a user's entry. The public key in this example is
`1,024 bits in length.
`
`Lenovo
`Ex. 1029 - Page 15
`
`

`

`US 6,189,096 B1
`
`15
`
`7
`Returning to FIG. 2, User A has a message m that is to be
`sent to User B. User A determines the public key B-pub of
`User B from public key look-up table 300. The unencrypted
`message m is encrypted by an encryption proceSS 240 using
`the public key B-pub of User B. The encrypted message,
`Suitable for transmission, is indicated by reference Symbol
`tXm. When User B receives tXm, it decrypts tXm with a
`decryption process 250. Decryption process 250 uses the
`private key B-pri of User B. The private key B-pri of User
`B is known only to User B. The output from decryption
`process 250 is the decrypted message m. The content of
`decrypted message m from decryption proceSS 250 is the
`Same as the content of unencrypted message m produced by
`User A, as long as the message has not been altered during
`transmission.
`Encrypted message tXm, which has been encrypted with
`B-pub, is completely unintelligible and can be decrypted
`only with B-pri. Thus, encrypted message tXm may Securely
`be sent over any communications network without fear of
`the message being read by an unauthorized recipient.
`The existence of public key look-up table 300 is not
`completely essential to a PKI System. It may be imagined
`that, to establish Secure communications, User A does not
`use public key look-up table 300 to determine B-pub but,
`rather, asks User B directly for B-pub. Since B-pub is the
`public key of User B, User B may freely provide B-pub.
`Thus, it will be appreciated that, in a PKI system, a sender
`encrypts messages using the receiver's public key, and a
`receiver decrypts messages received using its own private
`key. It is important to note also that, if User B encrypts a
`message using B-pri, then the message can be decrypted
`only with B-pub.
`Although User B may Securely receive a message Sent to
`it, and be assured that no unauthorized parties could have
`read and understood the encrypted message in transit, User
`B cannot be certain of the Source of the message. A message
`that States it has been Sent by User A might have been sent,
`instead, by User C masquerading as User A. Thus, User C (a
`thief) might send a message to User B (a bank) Such as, “I
`40
`am User A and I direct you to wire all the money from my
`account to User C.” The message could be encrypted using
`B-pub, because this information is freely available.
`Although User B can decrypt the message, the mere fact of
`Successful decryption does not mean the message came from
`User A.
`
`25
`
`8
`encrypted digest ed is combined with the unencrypted
`message m. The result of combining ed and m is referred to
`as ed+m for convenience. In step 440, the combination of
`encrypted digested and message m is encrypted using the
`receiver's public key to provide an encrypted message tXm.
`In this case, tXm includes not only the original message but
`also the digital Signature of the Sender.
`FIG. 5 shows the high level steps in decrypting such a
`message. The incoming encrypted message tXm is first
`decrypted using the private key of the receiver in step 510.
`The result is a combination of the unencrypted message m
`and the encrypted message digested (i.e., ed+m). These two
`are separated in step 520. In step 530, the unencrypted
`message m may be used to determine the Supposed identity
`of the sender. This information may be used in step 550 as
`described below.
`In Step 540, the text of the unencrypted message m is used
`to compute a message digest; the result is a computed digest
`cd.
`In step 550, the public key of the Supposed sender is
`obtained. The identity of the supposed sender may be
`included in message m and determined in step 530. The
`identity is used, along with public key look-up table 300, to
`determine the public key to be used to decrypt ed. In