United States Patent [l9]
`Sudia
`
`[54] ENHANCED CRYPTOGRAPHIC SYSTEM
`AND METHOD WITH KEY ESCROW
`FEATURE
`
`[75]
`
`Inventor: Frank Wells Sudia. New York. N.Y.
`
`[73] Assignee: CertCo LLC. New York. N.Y.
`
`[21] Appl. No.: 803,17()
`
`[22] Filed:
`
`Feb. 19, 1997
`
`Related U.S. Application Data
`
`[60] Division of Ser. No. 272.203. Jul. 8, 1994, abandoned,
`which is a continuatiou-ill-part of Ser. No. 181,859, Jan. 13,
`1994, abandoned.
`Int. CI.6
`........................................................ H04L 9/32
`[51]
`[52] U.S. CI. ................................................. 380/23; 380/30
`[58] Field of Search .......................................... 380/30. 23
`
`[56]
`
`References Cited
`
`u.s. PPJENT DOCUMENTS
`4/1980 Hellman et aI ..
`8/1980 Hellman et aI ..
`9/1983 Rivest et aI.
`9/1989 Fischer.
`211991 Scbnorr.
`3/1991 Fischer.
`4/1991 Fischer.
`8/1992 Fischer.
`9/1992 Maurer.
`11/1992 Matyas et aI ..
`3/1993 Matsuzaki et aI ..
`5/1993 Pinkas et aI ..
`5/1993 Fischer.
`6/1993 Beller et aI ..
`11/1993 Perlman et aI.
`111994 Micali.
`5/1994 Torii et aI ..
`5/1994 Micali.
`12/1994 Diffie et aI ................................ 380121
`3/1995 Ishiguro et aI.
`.. ........................ 380125
`7/1996 Davis ........................................ 380/50
`911996 Rosen ...................................... 364/408
`
`4,200,770
`4,218,582
`4,405.829
`4,868,877
`4,995,082
`5,001,752
`5,005,200
`5,136,643
`5,150,411
`5,164,988
`5,199,070
`5,214,700
`5,214,702
`5,222,140
`5,261,002
`5,276,737
`5,313,521
`5,315,658
`5,371,794
`5,396,558
`5,539,828
`5,557 ,518
`
`11111111111111111111111111111111111111111111111111111111111111111111111
`US005799086A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,799,086
`Aug. 25, 1998
`
`OTHER PUBLICATIONS
`
`American National Standard X9.30. "Public Key Cryptog(cid:173)
`raphy Using Irreversible Algorithms for the Financial Ser(cid:173)
`vices Industry: Part 1: The Digital Signature Algoritlun
`(DSA)" (American Bankers Assn.. Washington. D.C ..
`1993).
`American National Standard X9.30. "Public Key Cryptog(cid:173)
`raphy Using Irreversible Algorithms for the Financial Ser(cid:173)
`vices Industry: Part 2: The Secure Hash Algorithm (SHAt
`(American Bankers Assn .. Washington. D.C .. 1993).
`American National Standard X9.30. "Public Key Cryptog(cid:173)
`raphy Using Irreversible Algorithms for the Financial Ser(cid:173)
`vices Industry: Part 3: Certificate Management for DSA"
`(American Bankers Assn .. Washington. D.C .• 1993).
`Silvio Micali. "Fair Public Key Cryptosysterns". Laboratory
`for Computer Science of the Massachusetts Institute of
`Technology •. Oct. 13.1993.
`Donn B. Parker. "Crypto and Avoidance of Business Infor(cid:173)
`mation Anarchy" First Annual AC Conference on Computer
`and Communication Security. Nov. 3-5. Reston. VA.
`
`(List continued on next page.)
`
`Primary Emminer-Gilberto Barron. Jr.
`Attome)l Agent, or Firm-Steptoe & Johnson UP
`
`[57]
`
`ABSTRACT
`
`A cryptographic system with key escrow feature that uses a
`method for verifiably splitting user's private encryption keys
`into components and for sending those components to
`trusted agents chosen by the particular users is provided. The
`system uses public key certificate management, enforced by
`a chip device that also self-certifies. The methods for key
`escrow and receiving an escrow certificate are applied to
`register a trusted device with a trusted third party and to
`receive authorization from that party enabling the device to
`communicate with other trusted devices. The methods for
`key escrow also provide assurance that a trusted device will
`engage in electronic transactions in accordance with prede(cid:173)
`termined rules.
`
`12 Claims, 25 Drawing Sheets
`
`~176
`HESSAGE
`
`I 73
`
`SENDER ESCR[JW
`CERTIFICATE
`KE+sender
`~Sfdevl
`eel
`
`V-
`
`REClP. ESCROW
`CERTIFICATE
`KE.f rec i p
`KSidev2
`-ec2
`E[2 SY~IDY
`CERTIFICATE
`~2
`-SWQ t-vE"
`(175
`
`r-
`1
`I
`L
`VER!FI ES
`
`(171
`
`SENDER' S TRUSTED
`DEVICE
`
`KS-devl
`«S+ dev 1 >mfgr
`Ks+5WO
`
`-
`
`172 'l LEAF
`(K~s9 )KE rec i.E..
`(Kmsg )KE+se:ndel"
`
`~ ,
`
`')
`I
`L
`SIGNS
`
`devl
`
`- , (MESSAGE )Kms91
`(76
`
`J
`RIFlES
`
`NOTE, SYSTEHWIDE AUTHORITY (.wo)
`CAN BE MANUFACTURSR (mtgr)
`OR OTHER.
`
`SEllO ENC~YPTED MESSA liE WITH MCH (OVERVIEW)
`
`COMPASS EXH. 1005 - Page 1 of 53
`
`

`
`5,799,086
`Page 2
`
`OTHER PUBLICATIONS
`
`CCnT Recommendation X.509. 'The Directory-Authen(cid:173)
`tication Framework". International Standards Organization
`(ISO). Melbourne. Australia 1988.
`Dorothy E. Denning. 'The Clipper Encryption System".
`American Scientist. Jul.-Aug .. 1993. pp. 319-323.
`
`Martin E. Hellman. "Conunercial Encryption". IEEE Net(cid:173)
`work Magazine. Apr. 1987. vol. 1. No.2. pp. 6-10.
`
`David B. Newman. Jr .. Jim K. Omura and Raymond L.
`Pickholtz. "Public Key Management for Network Security".
`mEE Network Magazine, Apr. 1987. vol. 1. No.2. pp.
`11-16.
`
`COMPASS EXH. 1005 - Page 2 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 1 of 25
`
`5,799,086
`
`Y
`
`DIFFIE-HELLMAN AND MICALI ABBREVIATIONS
`RECIPIENTS PRIVATE KEY (EXPONENT)
`x
`xl ... n NUMBERED FRAGMENTS OF PRIVATE KEY
`j-th FRAGMENT OF PRIVATE KEY
`xi
`SENDER'S EPHEMERAL PRIVATE KEY (EXPONENT)
`PUBLIC BASE NUMBER
`PUBLIC PRIME MODULUS NUMBER
`P
`INTERMEDIATE NUMBER, = aX mod P
`DHx
`INTERMEDIATE NUMBER, = a Y mod P
`DHy
`DIFFIE-HELLMAN DERIVED MESSAGE KEY
`Kdh
`VI. .. n MICALI INTERMEDIATE NUMBER, = a xi mod P
`
`Q
`
`k msg
`M
`[
`
`OTHER SYMMETRIC KEY ABBREVIATIONS
`RANDOM OR DERIVED MESSAGE KEY
`PLAINTEXT MESSAGE
`CIPHERTEXT MESSAGE
`FIG.1A
`
`FIG 18 GENERAL ASSYMETRIC
`•
`KEY NOTATION
`PUBLIC PRIVATE
`
`SIGNATURE
`
`ENCRYPTION
`
`FIG 1C PUBLIC KEY CERTIFICATE
`•
`NOTATION (EXAMPLE)
`
`~+-~-----PUBLIC SIGNATURE KEY
`'-----+---OF THE DEV I CE
`'---SIGNED BY MANUFACTURER
`(USING MFGR PRIVATE KEY:KS-mfgr)
`
`COMPASS EXH. 1005 - Page 3 of 53
`
`

`
`FIG. 10
`PUBLIC KEY ENCRYPTON
`NOTATION (EXAMPLE)
`
`( MESSAGE) ~+re7e i p
`l[!
`I
`It -
`
`MESSAGE TO BE ENCRYPTED USING
`PUBLIC ENCRYPTION KEY
`~--DF THE RECIPIENT
`
`FI G. 1 E SUFFIXES USED TO DENOTE KEY OWENERSHIP
`
`box
`co
`dey
`
`eo
`ec
`mfgr
`owner
`reclp
`sender
`swo
`user
`
`col ... n
`
`LAW ENFORCEMENT DECODER BOX
`CERTIFYING AUTHORITY (FOR PUBLIC SIGNATURE KEYS)
`DTRUSTED DEVICE
`I ESCROW AGENT
`eo 1 , .. n
`ESCROW CENTER
`eel ... n
`mfgl.,.n MANUFACTURER OF THE TRUSTED DEVICE
`OWNER OF DEVICE (IF OTHER THAN USER)
`RECIPIENT OF A MESSAGE
`SENDER OF A MESSAGE
`SYSTEM-WIDE AUTHORITY
`userl ... n I USER OF THE TRUSTED DEVICE
`
`
`
`~ • 00
`
`•
`~
`~
`~
`
`~ a
`
`N
`
`> = ~
`~Ul -~ QC
`
`~
`~
`N
`g,
`N
`Ut
`
`~
`':...:i
`\C
`\C
`b
`Qe
`="
`
`COMPASS EXH. 1005 - Page 4 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 3 of 25
`
`5,799,086
`
`FIG.1F
`SHORTHAND NOTATION - SIGNING
`<data>dev foR\ ~ = <data> KS-dev
`v~
`
`FIG.1G
`SHORTHAND NOTATION - ENCRYPTION
`<data>sender = (data) KE+sender
`
`FIG. 2
`INTERACTIVE DIFFIE-HELLMAN KEY DERIVATIVE
`PRIOR AGREEMENT ON (NON-SECRET)
`PRIME P AND VALUE a
`PARTY A
`GENERATE SECRET
`RANDOM NUMBER x
`COMPUTE
`aX mod p
`COMPUTE KEY
`(aY)x mod
`
`PARTY B
`22 GENERATE SECRET
`RANDOM NUMBER Y
`COMPUTE
`aY mod p
`COMPUTE KEY
`(aX)Y mod
`
`21
`
`COMMON KEY aXY mod p KNOWN BY A AND 8
`BUT NOT DEDUCIBLE BY AN EAVESDROPPER
`
`FIG. 22
`DEVICE OWNER'S
`CERTIFICATE (EXAMPLE)
`
`VERSION No.
`221 .......,.. DEVICE SERIAL No.
`OWNER NAME
`223 --"'" OWNER UNIQUE 10
`KS+ OWNER
`PURCHASE DATE
`
`225 ---.... MFGR SIGNATURE
`
`i---"
`
`220
`
`V-
`
`222
`
`.. v
`
`224
`
`COMPASS EXH. 1005 - Page 5 of 53
`
`

`
`~
`
`00 .
`~ = ~ g .....
`
`> = ~
`
`N
`",Ul
`
`~
`
`~
`00
`
`rJ:;. =-
`~
`.a:.
`S,
`N
`!II
`
`til
`':...J
`~
`b
`QiO
`0\
`
`A. USER
`(WOULD-BE RECIPIENT
`GENERATE DH PARAMET
`i
`
`31
`
`PRIV ATE KEY
`EXPDN ENT 0
`
`32
`PUBLIC CONSTANTS
`[E]
`PRIME
`BASE ~
`
`aX mod P~DHx =r 33
`
`DH INTERMEDIATE NUM
`
`USERS PUBLIC KEY
`{P,Q,OHx}
`
`S TORE PRIVATE
`KEY 0
`SECURELY
`
`CERIFICATE REQUEST
`T DATA
`{P,Q/DHx}, USER
`NAME
`
`FIG. 3
`CERTIFIED DIFFIE-HELLMAN
`- CERTIFICATION
`
`SIGNED
`RETURN TO USER
`
`
`
`B. CERTIFYING AUTHORITY (CA)
`
`VERSION NO.
`CERT. SERIAL NO.
`ISSUER NAME (CA)
`USER NAME
`{P,a,DHx}
`VALID DATES
`
`CERT.
`DATA
`
`36
`
`ISSUER CAtS
`PRIVAT~ K~Y
`( y, DSA)
`
`CERTIFICATE DATA
`ISSUER SIGNATATURE
`
`SIGNED
`CERT.
`
`36
`
`DIRECTORY
`MAINTAINED
`BY CA
`
`COMPASS EXH. 1005 - Page 6 of 53
`
`

`
`A. SENDER
`
`RECEIVER1S
`CERTIFICATE
`\35
`CERTIFICATE DATA i
`ISSUER SIGNATURE
`
`ISSUER CA
`PUBLIC KEY
`
`36
`
`OBTAIN
`RECIP'S
`PUBLIC
`KEY DATA
`
`GENERATE
`RANDOM
`EXPONENT [Y]
`
`41
`SENDER'S
`TEMPORARY
`PRIVATE
`KEY
`
`40
`
`B. RECIPIENT
`
`31
`
`ORIGINAL
`
`SECRET KEY o
`
`o
`00 .
`
`~
`~
`f"'f>.
`
`~ f"'f>.
`
`i
`
`!
`
`COMPUTE
`'SESSION
`
`L...:(~D:.H:!.y..:.)X...:m.:o:.:d:....:..P_---_!;;;;1 K,d;;;;;h;;:..J1 I KEY FOR
`
`I
`
`MESSAGE
`
`N
`
`> = ~
`~Ul -~
`
`OCI
`
`SENDER'S
`INTERMEDIATE
`DH NUMBER
`
`40
`
`[g
`
`MESSAGE
`[ill
`
`CIJ :r
`~ a
`Ul
`o
`~
`N
`VI
`
`ENCRYPTED
`MESSAGE
`K1
`
`ENCRYPTED
`MESSAGE
`WITH PREFIX
`
`FIG. 4
`CERTIFIED
`DIFFIE-HELLMAN
`- MESSAGING
`
`"..
`
`tit
`"'-l
`~
`\C
`
`".. = 00
`a-...
`
`aYmod
`
`(DHx)Ymod
`
`43 I MESSAGE
`[EJ
`
`
`
`COMPASS EXH. 1005 - Page 7 of 53
`
`

`
`o en .
`~ = ~ a
`
`> = ~
`
`N
`",VI
`
`1-1
`
`~
`
`171 =-('!)
`('!) -C"-
`o ...,
`
`N
`VI
`
`Ul
`'!..:I
`\C
`\C
`-..
`C oc
`0\
`
`53 RECIPIENT'S 'I-__ ----,
`PUBLIC KEY
`
`51
`
`FIG 5 RSA KEY TRANSPORT
`•
`- ENCRYPTION
`
`RSA ENCRYPTED
`DES KEY
`
`55
`RSA ENCRYPTED
`DES KEY
`
`( SLOW)
`
`.---------t.-.t~ DES ENCRYPT ED
`MESSAGE
`
`DES ENCRYPTED 1-1 __ - - - - '
`MESSAGE
`
`54
`
`(FAST)
`
`54
`
`DES ENCRYPTED
`MESSAGE
`
`RSA ENCRYPTED
`DES KEY
`55
`
`ORIGINALI
`MESSAGE
`
`52
`
`56" RECIPIENT'S
`PRIVATE KEY t-I - - - - '
`
`FIG. 6
`RSA KEY TRANSPORT - DECRYPTION
`
`
`
`COMPASS EXH. 1005 - Page 8 of 53
`
`

`
`72
`
`MESSAGE
`
`SIGNED HASH
`
`76
`
`o
`00 •
`~
`"* ~
`"*
`
`> = ~
`
`N
`~tIl
`.....
`~
`
`rJj =r a
`
`-...l
`~
`N
`til
`
`tit
`'" .....:J
`I..Q
`I..Q
`
`'" = QO
`
`0\
`
`FIG. 7
`RSA SIGNATURE - CREATION
`
`75
`
`MESSAGE
`
`76
`
`SIGNED HASH
`
`FIG. 8
`RSA SIGNATURE
`- VERIFICATION
`
`SENDER'S
`PUBLIC KEY
`
`
`
`COMPASS EXH. 1005 - Page 9 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 8 of 25
`
`5,799,086
`
`STORE PRIVATE
`KEY 00
`SECURELY
`
`FIG 9 MICALI ESCROW PROCESS EXAMPLE -
`•
`USER OPERATIONS
`SECRET
`I GENERATE OH PARAMETERS I 92 RANDOM
`7 NUMBERS
`t
`t
`PUBLIC CONSTANTS
`PRIVATE KEY COMPONENTS
`xl, x2, x3
`[E]
`PRIME
`I
`l
`BASE @]
`I
`I
`(xl + x2 + x3) mod p-x'l ~l
`USERS PRIVATE KEY X
`,
`
`90)
`MICALI INTERMEDIATE No's
`ax1mod P--Vl
`ax2mod P--V2
`oX3mod P--V3
`(Vl*V2*V3)mod P--DHx
`I
`
`DH INTERMEDIATE No.
`oXmod P~OHx
`..
`USER PUBLIC KEY
`{P, a, OHx}
`I
`!
`t
`- {P, 0, DHx, Vi, x I, USER NAME}
`ESCROW AGENTS STATS
`
`99---
`
`93
`
`{P, c, OHx, V2, x2, USER NAME}
`{P, a, OHx , V3, x3, USER NAME}
`
`SEND 1
`SHARE TO
`AGENT
`
`i
`EACH ESCROW I TO ESCROW
`AGENT 1
`
`94}
`
`t
`I TO ESCROW I I TO ESCROW
`
`(94
`
`(94
`
`AGENT 2
`
`AGENT 3
`
`COMPASS EXH. 1005 - Page 10 of 53
`
`

`
`FIG. 10 MICALI ESCROW PROCESS EXAMPLE - ESCROW AGENT OPERATIONS
`
`\.
`
`{P,o,OHx,Vl,Xl,USER}
`NAME
`J L l£_
`(95
`VERIFY ( 1 )
`OX 1 mod P----V 1
`
`r
`
`90)
`ARCHIVE ( 1 )
`~ {USER NAME, xl}
`
`{P,o,DHX,V2,X2,USER}
`NAME
`L tt_
`
`l
`
`(95
`VERIFY (2)
`ox2mod P--"V2
`
`90)
`ARCHIVE (2)
`~ {USER NAME, x2}
`
`{P,a,OHx,V3,X3,USER}
`NAME
`L ~9
`
`\.
`
`T
`(95
`VERIFY (3)
`ox3mod P-V3
`
`90)
`ARCHIVE (3)
`~ <USER NAME, x3}
`
`APPROVAL DATA ( 1 )
`{P,o,DHx,Vl,USER NAME
`
`APPROVAL DATA (2)
`{P,o,DHx,V2,USER NAME
`
`APPROVAL DATA (3)
`{P,o,DHx,V3,USER NAME I
`
`I
`
`AGENT l' 5
`PRIVATE
`SIGNATURE
`KEY
`,
`(96
`APPROVAL DATA 1
`AGENT 1'5 SIGNATURE
`
`AGENT 2'5
`PRIVATE
`SIGNATURE
`KEY
`96
`
`APPROVAL DATA 2
`AGENT 2'5 SIGNATURE
`
`AGENT 3'5
`PRIVATE
`SIGNATURE
`KEY
`(96
`APPROVAL DATA 3
`AGENT 3'5 SIGNATURE
`
`~
`~ •
`~ ~
`~ = ~
`
`>(cid:173)= ~
`
`N
`.. !.11
`I-'
`
`~
`
`rJJ =-a
`
`I,Q
`~
`N
`!II
`
`til
`~
`\C
`
`\C = QO '"
`
`\.
`
`
`
`
`
`
`
`COMPASS EXH. 1005 - Page 11 of 53
`
`

`
`FIG. it MICALI ESCROW PROCESS EXAMPLE - MASTER ESCROW CENTER OPERATIONS
`
`APPROVED DATA 1
`AGENT 1'5 SIGNATURE
`
`AGENT l's
`PUBLIC
`VERIFICATION
`KEY
`
`APPROVED DATA
`{P,Q,DHx,Vl,USER NAME}
`I
`
`98)
`
`RETURN
`TO
`USER
`
`USER'S
`CERTIFICATE
`MASTER CENTER'S
`SIGNATURE
`
`APPROVED DATA 3
`AGENT 3 ' 5 SIGNATURE
`
`AGENT 3'5
`PUBLIC
`VERIFICATION
`KEY
`
`APPROVED DATA 2
`AGENT 2' 5 SIGNATURE
`
`I
`I
`I
`I
`I
`I VERIFY
`I SIG.
`I
`96)
`I
`APPROVED DATA
`I
`I {P,Q,DHx,V2,USER NAME}
`
`AGENT 2'5
`PUBLIC
`VERIFICATION
`KEY
`
`VERIFY (MC)
`(Vl*V2*V3*)mod P~DHx
`
`/
`1...97 99.
`
`~
`
`o en .
`~ = "*"
`("t) a
`
`> c
`
`~
`N
`... 0\
`
`....
`~
`
`~
`~ .....
`.....
`o
`S,
`N
`U\
`
`01
`~
`~
`
`~ = 00
`
`="
`
`I
`
`1
`
`I
`I
`I
`I
`I
`I VERIFY
`I SIG.
`I
`(96
`I
`APPROVED DATA
`I
`I {P,a,DHx,V3,USER NAME}
`I
`CERT. SERIAL No.
`USER NAME
`{P,Q,OHx}
`VALID DATES
`{AGENT 1'5 NAME,Vl} I
`{AGENT 2' 5 NAME,V2}
`{AGENT 3' 5 NAME,V3}
`
`I CREATE USER I
`~ CERT. DATA
`
`&c
`SIGN
`
`MASTER CENTER'S
`PRIVATE SIGNATURE
`KEY
`
`
`
`
`
`
`
`
`
`I
`MASTER
`CENTER'S
`ARCHIVE
`
`'-
`
`COMPASS EXH. 1005 - Page 12 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 11 of 25
`
`5,799,086
`
`FIG. 12
`ESCROW CERTIFICATE (EXAMPLE)
`
`,,-
`
`..",.-
`
`123
`121
`
`-v
`122
`
`VERSION No.
`CERTIFICATE SERIAL No.
`ESCROW CENTER NAME
`ESCROW CENTER COUNTRY [ODE
`KE+ec (FOR LEAF USE)
`USER NAME
`KE+user (FOR MESSAGES)
`KS+dev (TO VERIFY LEAF)
`VALIDITY PERIOD
`ESCROW CENTER SIGNATURE
`
`_..r
`
`124
`
`V
`
`125
`
`FIG. 13
`CLIPPER LEAF PACKET (CONJECTURED)
`I
`,\
`
`(k msg )Kdv
`CHECKSUM OF Kmsg
`DEVICE SERIAL No.
`
`\ CHECKSUM OF LEAF II
`kmsg SYMMETRIC MESSAGE KEY
`kdev EM8EDDED SYMMETRIC DEVICE KEY
`kfam SYMMETRIC CLIPPER FAMILY KEY
`
`COMPASS EXH. 1005 - Page 13 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 12 of 25
`
`5,799,086
`
`FIG. 14
`DEVICE CERTIFICATE: <KS+dev)mfgr (EXAMPLE)
`
`VERSION No.
`MFGR NAME
`DEVICE SERIAL No.
`DEVICE TYPE/MODEL
`MFG DATE
`KS+dev
`ATTRIBUTE [ODES (OPTIONAL)
`MFGR SIGNATURE
`
`FIG. 18
`MESSAGE CONTROL HEADER (EXAMPLE)
`(IN RSA - KEY - TRANSPORT FORMAT)
`
`V-
`
`VERSION No.
`(MESSAGE KEY) KE+recip
`SENDER ESCROW CENTER NAME ( ec 1 )
`SENDER ES[ROW CENTER COUNTRY CODE
`RECIPIENT ESCROW CENTER NAME (ec2)
`RECIPIENT ESCROW CENTER COUNTRY CODE
`(SENDER ESCROW CERT. No. ) KE+ ec 1
`-V-
`(MESSAGE KEY) KE+sender (TO HIMSELF)_ ..;--
`(RECIP. ES[ROW CERT. No. ) KE+ec2
`TIMESTAMP (OPTIONAL)
`SENDER DEVICE SIGNATURE
`
`----
`
`181
`
`181
`181
`181
`
`COMPASS EXH. 1005 - Page 14 of 53
`
`

`
`156
`DEVICE SER. No.
`KE+user
`KS+dev
`
`ec
`
`...,
`~154
`r.-151
`r-..157
`1-1..,<
`I~
`11-1
`.J~
`
`ESCRDW CNTR NAME
`KS+ec
`
`swa
`
`-'
`
`lls8
`
`REDELIVER
`
`e
`00
`•
`~
`~
`
`"""" ~ a
`
`>
`==
`ttC
`N
`~!.Il
`
`....
`~
`
`~ rt>
`
`rt> -....
`
`(.U
`
`~
`N
`Ut
`
`U1
`'!..:t
`\C
`\C
`'" = QO
`'"
`
`TRUSTED DEVICE
`KS+mfgr
`KS+swa
`1
`KS-dev
`I
`~ <KS+dev>mfgr
`I
`GEN-
`: {( KE+user
`I
`ERATE:
`KE-user
`I VERIFY
`® INPUT ~l OUTPUT@L -
`-
`-
`c
`
`150
`CD
`REG.
`COMPo
`
`r
`
`..
`"-
`
`152)
`
`ESCROW CNTR NAME
`KE+ec
`
`-swa
`
`OBTAIN
`
`
`
`
`
`
`
`~151
`( KE-user
`~lS4
`KE+user
`DEVICE SER. No. J-r
`KE+ ec
`-dey
`f
`I
`t--..J
`VERIFY
`
`DEVICE SER. No.
`KS+dev
`
`-mfgr
`
`155_
`
`@
`TRANSMIJ
`
`...,
`
`~
`
`153}
`ESCROW CENTER
`KS+mfgr
`KS-ec
`G)
`KE-ec
`·VERIFY SIGNATURES
`'DECRYPT PACKET
`·STORE KE- user
`I
`
`FIG. 15 REGISTERING WITH A SINGLE ESCROW CENTER (EXAMPLE)
`
`COMPASS EXH. 1005 - Page 15 of 53
`
`

`
`CERTIFICATES
`I
`ESCROW
`AGENT 1
`
`-
`
`PUBLIC
`ERROR
`KEYS 0
`F
`OW
`3 ESCR
`AGENTS
`
`~
`00 .
`;p
`~ g
`
`~
`
`>
`~
`
`N
`",01
`
`I-'
`
`~
`00
`
`ga
`! .....
`
`.&:;.
`~
`N
`til
`
`Ot
`~
`\,C
`
`\,C = 00
`
`="
`
`KE+ea 1
`I-
`-EC ~
`~160
`
`I
`ESCROW CNTR
`KS+ec
`KE+ec
`-swo
`
`CERT. 0
`F
`ESCROW
`CENTER
`
`•
`
`{164
`user name, dev#, KE+,
`(rl,eal name,
`r 2 ,eo2 name,
`r3,eo3 nome)ec
`-dey
`
`f i ~
`
`<165
`
`ESCRDW CNTR
`VERIFY rl,r2,r3
`SAME
`
`ESCROW AGENT 1 ESCROW AGENT 2 ESCROW AGENT 3
`store: xl, dev# stare: x2,dev# store: x3,dev#
`t
`t
`name, KE+user
`name, KE+ user
`(r2, dev# )eo
`(r3, dev# )eo
`-ea2
`-eo3
`
`name,KE+user
`( r 1 , dev# )eo
`-eal
`
`•
`I
`167J
`I RETURN TO USER J
`
`167)
`
`I
`
`167)
`
`CREATE ESCROW
`CERTIFICATE
`
`16~ user name
`KE+user
`KS+dev
`-dey
`
`
`
`
`
`
`
`~
`
`
`FIG 16 vERIFIABLE KEY SPLITTING
`•
`BASED ON TRUSTED DEVICE ALONE
`DEVICE CERT.
`TRUSTED DEVICE
`DEV No.
`KS+mfgr KS+swa
`KS+dev
`r - - KS+dev KS-dev
`-mfgr
`KS+user KS-user
`I
`(162
`...
`i
`161)
`user name,
`dey #,
`KE+user,
`(x2, r2 )ea2
`-dey
`
`DEVICE GEN.
`KEY FRAGMENTS
`xl, x2, x3
`AND RANDOM #'5
`rl, r2,r3
`t
`161)
`user nome,
`dey #,
`KE+user,
`(xl,rl )eal
`-dey
`
`163) t
`
`(161
`
`t
`user none,
`dey #,
`KE+user,
`(x3,r3)eo3
`-dey
`
`I63} r +
`
`+ 163) r +
`
`COMPASS EXH. 1005 - Page 16 of 53
`
`

`
`172
`
`( Kms9_ )KE+rec i p
`(Kmsg)KE+sender
`
`-devl
`
`~
`
`00 .
`~
`~ .......
`
`~ a
`
`> = cto
`
`N
`"VI
`......
`~
`OCI
`
`~
`!l
`......
`VI
`~
`N
`VI
`
`Ot
`'!...l
`~
`
`~ = 00
`
`Q\
`
`...)
`
`__ J
`VERIFIES
`
`NOTE: SYSTEMWIDE AUTHORITY (swa)
`CAN BE MANUFACTURER (mfgr)
`OR OTHER.
`
`FIG. 17sENO ENCRYPTED MESSAGE WITH MCH (OVERVIEW)
`
`
`
`
`
`
`
`
`
`~
`
`I MES_SAGE
`
`r 176
`
`173
`
`)
`
`I-
`
`c::=>
`174
`r--
`
`171
`SENDER'S TRUSTED
`DEVICE
`KS-devl
`<Ks+ dey 1 >mfgr
`KS+swa
`
`~
`
`" c::=>
`"(cid:173) ,
`1
`I
`L
`SIGNS
`
`!-"
`
`.
`
`SENDER ESCROW
`CERTIFICATE
`KE+sender
`KS+devl
`-eel
`RECIP. ESCRDW
`CERTIFICATE
`KE+reclp
`KS+dev2
`-ec2
`EC2 SYSTEM
`CERTIFICATE
`L
`KS:j:ec2
`VERIFIESrl------------~
`
`COMPASS EXH. 1005 - Page 17 of 53
`
`

`
`I (MESSAGE )Kmsg r 191
`
`MCH
`
`rl92
`
`(Kmsg)KE+reclp
`(Kmsg)KE+sender
`
`i
`
`-devl I
`SENDER ESCRDW
`CERTIFICATE
`KE+sender
`KS+devl
`-eel
`ECl SYSTEM
`CERTIFICATE
`KS+ec2
`-swo
`
`94
`
`95
`
`___ ...1
`
`VERIFIES
`
`TO ACTIVATE
`
`190)
`RECIPIENT'S TRUSTED
`DEVICE
`KS-dev2
`<KS+dev>mfgr
`KS+swa
`KE-rec I p
`
`--
`
`c::::>
`r(cid:173)
`I
`I
`
`~- -196
`
`193
`
`RECIP, ESCROW
`CERTIFICATE
`KE+recip
`KS+dev2
`-ec2
`
`c::::> I MESSAGE I
`
`o
`00 .
`-0
`~
`""'"
`(t) a
`
`>
`~
`
`N
`... VI
`.....
`~
`00
`
`~
`~
`.....
`C"I
`~
`N
`til
`
`{JJ
`':...J
`\C
`\C
`Q
`QO
`0'\
`
`FIG. 19 RECEIVE ENCRYPTED MESSAGE WITH MCH (OVERVIEW)
`
`VERIFI
`
`I
`L
`VERIFIES
`
`
`
`
`
`
`
`
`
`~
`
`COMPASS EXH. 1005 - Page 18 of 53
`
`

`
`@
`@
`SUBMIT:
`OBTI
`1 . LEAF
`USEI
`2.BOX
`DEV:
`[ER'
`[ERTS
`3o.WARR. NAMI
`OR
`OF (
`3b.OEV.
`ESC!
`OWNER AGEl
`[ERT
`(
`
`1
`
`® /#3
`1#2
`ESCROW
`AGENT #1
`
`-
`
`10-
`
`1=3
`1=2
`1=1
`
`N:
`
`E
`
`)
`
`6
`
`~
`
`00 • ;p
`..... a
`
`> ~
`
`~
`N
`,.th
`
`....
`!
`
`~
`m.
`....
`-..,J
`S,
`N
`th
`
`til
`~ -....l
`\0
`\0
`
`---o oe
`
`Q\
`
`FIG. 20 DECODER BOX PROCESS FLOW (EXAMPLE)
`
`207 __
`
`BOX 0
`CD HIS
`PU
`&
`&
`
`(200
`
`ESCROW
`CENTER
`(OF TAPPEE)
`
`BOX'S
`"1 AM
`READY
`[ERT
`
`BOX'S
`OEVI[
`(ERT
`FROM
`MFGR
`
`
`""0
`
`
`
`
`
`
`
`~
`
`(
`
`l
`
`I
`
`r BOX TYPE #
`
`"BOX
`(ERTS"
`
`r-... @
`'-202
`
`-203
`
`BOX KS+
`-signed
`MFGR
`BOX #
`OWNER'
`OWNER NAME
`BOX #
`>' 8c TAX 10
`CERT.
`-signed
`FROM
`,
`MFGR
`MFGR
`..I
`NOTE: KEY SPLIT xl IS ENCRYPTED
`UNDER THE PUBLIC KEY OF THE BOX,
`KE+box
`
`TAMPERPROOF DECODER SOX
`\/ER INSTRUCTION
`(KS+box)mfgr SOX'S MFGR CERT
`IE A CURR.
`-4"", KS- box,.
`BOX'S PRIV. SIG. KEY
`V <KE+box>oox SOX'S PUB. EMER. KEY
`EMER KEY
`MESTAMP
`205, KE-box
`BOX'S PRIV OECR. KEY
`~'~
`GN IT,"
`~Ol
`TRUSTED TIME CLOCKl
`KEY SPLITS: Xl' X2' X3 ®
`BOX #
`,
`KE+box
`8
`> CURR TIME
`WARRANT TIME INTERVAL
`(TIME l, - TIME 2 )
`.
`-signed
`~
`204
`BOX
`l ~CD
`} r
`1
`TO BOX #
`HERE IS KEY SPLIT
`( x I )KE+box FOR dev#
`WARRANT TIME INTERVAL r;;;::
`IS TIMEl - TIME2
`~
`-®
`-signed
`ESCROW AGENT#l
`...
`' " NOTE: ATTACH ESCROW AGENT (ERTS
`LEADING BACK TO BOX MFGR (TRUSTED
`BY BOX) OR TO SYSTEMWIDE AUTH. KEY
`
`COMPASS EXH. 1005 - Page 19 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 18 of 25
`
`5,799,086
`
`./210
`
`TAMPER-RESISTANT DEVICE
`
`MEMORY:
`r--- KS-dev
`<KS+dev>mfg
`KS+swa
`FIRM NAME
`OTHER KEYS
`& CERTS
`DEVICE #
`
`~ CPU
`CRYPTO
`COPROCESSOR
`-
`12
`L3)
`~ 9
`1-3-94
`-
`6
`216
`L{ CLOCK SA TTERY )
`
`TRUSTED TIME-SETTING
`ENT. (eg POST OFFICE)
`TIME-SET
`2) 1
`j INSTRUCTION
`THE TIME IS NOW
`3:05PM JAN 3,1994
`SET YOURSELF AND
`PROCEED
`SIGNED,
`POST OFFICE
`
`r--
`
`TIME-SET AUTH. CERT.
`·POST OFFICE N
`IS A -
`TRUSTED TIME-SETTER
`SIGNED, SYSTEMWIDE
`AUTHORITY
`
`212)
`
`VERIFIES
`( NOTE: TIMESTAMP WILL
`BE NULL IF CLOCK
`NOT CALIBRATED. )
`
`ANY DATA STRUCTURE
`CONTAINING A CDNTEMP-
`DRANEOUS TIMESTAMP
`
`... JAN 3, 1994 - 3:05PM
`
`213)
`
`214)
`~ SIGNED, DEVICE (
`? DEVICE MFGR'S CERT.
`215
`·OEVICE #. IS TRUSTED
`TO ISSUE TIMESTAMPS
`KS+dev
`SIGNED, MFGR
`
`-
`
`FIG. 21
`SELF-CERTIFYING TRUSTED TIMESTAMP DEVICE
`
`COMPASS EXH. 1005 - Page 20 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 19 of 25
`
`5,799,086
`
`239
`
`VERSION No.
`DEVICE SERIAL NO.
`OWNER NAME
`OWNER UNIQUE 10
`KS+ OWNER
`PURCHASE DATE
`-mfgr
`
`231
`DEVICE SERIAL NO.
`OWNER UNIQUE 10
`ec NAME
`eol NAME
`eo2 NAME
`eo3 NAME
`REKEY EXPIRE DATE
`INSTRUCTION SER. No.
`
`-owner
`
`230
`
`TRUSTED
`DEVICE
`
`NEW ESCROW
`REQUEST
`MESSAGES
`
`-swa
`
`234
`
`FIG. 23
`OWNER REKEY INSTRUCTIONS PROCESS
`
`
`
`COMPASS EXH. 1005 - Page 21 of 53
`
`

`
`Cj
`~ •
`
`~ ;-a
`
`>(cid:173)= ~
`~U1 ....
`~
`
`N
`
`QO
`
`~
`!
`N o
`s.,
`
`N
`U1
`
`VI
`'!..;J
`'C
`'C
`".
`Q
`QO
`Q\
`
`TRUSTED THIRD PARTY (ttp)
`KS-ttp
`KS+mfgr
`KS+swa
`241-"" <KS+tpp>swa
`
`
`REG. OF DE VICE
`FIG 24 WITH TRUST
`ED
`THIRD PART
`•
`Y
`
`244)
`A. USER'S REG, REQUEST
`
`2~ USER INFO
`APPL,
`INFO
`-dev h
`I
`242 DEVICE CERT
`I
`"- DEVICE TYPE
`I
`DEVICE SER, No,
`I-J
`KS+dev
`-mfgr
`
`~46
`
`8. TTP's RESPONSE
`TTF's GRANT OF SOFTWARE AND/OR PUB,
`AUTHORIZATION
`KEY UPGRADES (OP~)
`TTP NAME
`TRUSTED SOFTWARE
`APPLIC. DATA
`TRUSTED KEYS
`APPLIC, DATA
`USER INFO
`DEVICE INFO
`-ttp ~
`KS+dev
`t248
`1'-247
`I
`-ttp ~--------~
`TTP NAME
`I
`TTP's SYSTEM-
`KS+ttp
`I--_.J
`WIDE IDENTITY UPGRADE AUTH,
`v 243
`AND UPGRADE
`-swo
`AUTH, CERT.
`
`240)
`TRUSTED DEVICE
`KS-dev
`242 ... ~KS+dev>mf9r
`KS+mfgr
`KS+swo
`
`C, USER'S AUTH, TRANSACTION(S)
`247 TTP's GRANT
`249)
`TRANS. DATA ~ OF AUTH,
`KS+dev
`USER INFO
`r-
`-ttp
`-dev ~
`
`(250
`FOURTH PARTY-
`(eg TRADING
`f--t- PARTNER)
`KS+swo
`KS+ttp
`
`
`
`
`
`
`
`
`
`COMPASS EXH. 1005 - Page 22 of 53
`
`

`
`u.s. Patent
`
`Aug. 25, 1998
`
`Sheet 21 of 25
`
`5,799,086
`
`_r 254
`
`--
`
`252
`256
`..-'
`257
`256
`.... ,
`257
`
`10 --
`
`1 b -
`
`-
`
`.... ,
`253
`
`--
`-
`
`20 -
`
`f-
`
`I-
`
`251
`255
`257
`~
`
`-
`
`258
`
`VERSION NUMBER
`RECIPIENT NAME
`(TO RECIPIENT)
`(MESSAGE KEY) KE+RECIP
`RECIPIENT ESCROW CENTER NAME (ec 1 )
`(RECIPIENT CERTIFICATE No. ) KE+ecl
`RECIPIENT EMPLOYER 10 NAME (empl 10 )
`(MESSAGE KEY, RECIP. CERTIF. No,) KE+empl
`RECIPIENT EMPLOYER Ib NAME (empl 1 b )
`(MESSAGE KEY, RECIP. CERTIF. No.) KE+empl
`
`· · ·
`
`SENDER NAME
`(MESSAGE KEY) KE+SENDER (TO HIMSELF)
`SENDER ESCROW CENTER NAME (ec2)
`(SENDER CERTIFICATE No. ) KE+ec2
`SENDER EMPLOYER 20 NAME (empl 20)
`(MESSAGE KEY, SENDER CERTIF. No.) KE+emp I
`
`· · ·
`
`SENDER MESSAGE SEQUENCE NUMBER
`HASH OF MESSAGE
`TIME OF CREATION
`SENDER DEVICE SIGNATURE
`
`FIG. 25
`LAW ENFORCEMENT ACCESS FIELD (MULTIPLE RECIPIENTS)
`(IN RSA - KEY - TRANSPORT FORMAT)
`
`COMPASS EXH. 1005 - Page 23 of 53
`
`

`
`0 •
`r.I1 •
`~
`~
`
`"""'" ~ a
`
`> = ~
`....
`~
`00
`
`N
`"U'I
`
`~
`fi
`
`N
`N
`~
`N
`VI
`
`01
`....
`........
`
`~ .... o
`
`co
`="
`
`26
`
`OWNER CERTIFICATE 262
`DEVI[E TYPE
`~OWNER PUBLIC SIG. KEY
`MFR. SIGNATURE
`
`® EMBEDS
`
`CD VERIFIES
`
`260
`
`TRUSTED DEVICE
`BLANK
`MFR. PUB. KEY
`
`,;
`
`~
`
`264
`
`263
`
`FIG. 26
`EMBEDDING OF OWNER PUBLIC KEY UPON INITIAL SALE
`
`OWNER TRANSFER INSTRUCTION
`DEVICE TYPE
`DEVICE NUMBER
`-
`OWNER-2 PUBLIC KEY
`-~ DWNER-l SIGNATURE
`
`284
`
`283
`
`282
`® REPLACES
`
`CD VERIFIES
`
`FIG. 28
`OWNERSHIP TRANSFER
`
`280
`
`TRUSTED DEVICE
`
`~ OWNER 1 PUB KEY
`- MFR. PUB. KEY
`
`81
`
`
`
`
`
`
`
`COMPASS EXH. 1005 - Page 24 of 53
`
`

`
`270
`
`\..!;.I
`
`~8ANK l~
`TRUSTED
`DEVICE
`J BANK 2 I
`ESCROW
`OWNER'S PUBLIC ~ ~ CENTER
`INSTR. KEY
`BANK 3
`
`(271
`
`NEW ESCROW CERT.
`
`@
`
`USER NAME
`USER PUB. ENCR KEY
`OWNER UNIQUE 10*
`OWNER PUB. ENCR KEY
`ESCRDW CENTER SIG
`(ESCRDW CENTER [ERT. )
`
`f---
`
`e
`00 •
`
`~
`~
`~
`
`~ = ~
`
`>(cid:173)c:
`
`~
`N
`"Ul
`.....
`~
`QC
`
`g2
`!
`~
`~
`N
`f.Il
`
`01
`':..J
`\C
`
`\C = QC
`
`Q\
`
`2
`
`DEVICE NUMBER
`ESCROW CENTER NAME
`ESCROW AGENT NAMES
`OWNER UNIQUE 10*
`OWNER'S SIGNATURE
`t
`3)
`27
`OWNER PRIVATE vr 274
`SIGNATURE KEY
`
`r-- 1-
`I
`I
`... _ J VERIFIES
`
`JTES:OWNER CONTROLS AGENT NAMES.
`N
`OWNER 10* STAYS IN USER CERT.
`
`-
`
`FIG. 27
`OWNER CONTROLLED REKEY PROCESS
`
`
`
`
`
`
`
`COMPASS EXH. 1005 - Page 25 of 53
`
`

`
`NATION A
`USERl ESCRDW CERT _291
`' -
`USERl NAME
`USERl COUNTRY CODE~ r-.... r- 297
`USERl PUB ENC KEY
`EAl NAME (ISSUER)
`EAl SIGNATURE
`
`EAl CERTIFICATE
`EAl NAME ~ COUNTRY
`EAl PUBLIC SIG KEY
`EAl PUBLIC ENRC KEY
`PUBLIC AGENT = NO
`,. r-.... _298
`SYSTEMWIDE AUTH SIG
`
`292
`
`SENDER TRUSTED
`DEVICE
`SYSTEMWIDE AUTHORITY
`PUBLIC KEY
`
`290)
`
`293
`
`r--~
`
`NATION B
`USER2 ESCROW CERT
`USER2 NAME
`295' r---. USER2 COUNTRY CODE
`USER2 PUB ENC KEY
`EA2 NAME (ISSUER)
`EA2 SIGNATURE
`
`r--
`
`29' ' -
`
`EA2 CERTIFICATE
`EA2 NAME & COUNTRY
`EA2 PUBLIC SIG KEY
`EA2 PUBLIC ENRC KEY
`299 ;" ~ - PUBLIC AGENT = YES
`SYSTEMWIDE AUTH SIG
`-
`
`294
`
`FIG. 29
`DOMAIN RESTRICTION - SENDER ENFORCEMENT
`
`~
`00 •
`~
`~
`~
`
`~ = ~
`
`N
`
`> = ~
`",til -~
`
`~ a
`~
`s,
`
`N
`til
`
`Ol
`'!...l
`~
`b
`00
`C'\
`
`..--
`
`-
`
`
`
`
`
`
`
`
`
`1
`
`COMPASS EXH. 1005 - Page 26 of 53
`
`

`
`MSG CTRL HEADER
`~....::: ~ "L.
`'...!.l. ::/.~.!.~ '.t, ,//~%
`~~~LC;RYr1~9, }1f/S~"}~E ~ f - -
`SENDER CERTIFICATE
`SENDER EA CERTIFICATE 1-
`
`1-
`
`Cj
`00 •
`~ .....
`~ = ....
`
`> = ~
`
`N
`,#Ul
`.....
`~
`CO
`
`g2
`
`::g -N
`
`Ul
`~
`N
`VI
`
`Ol
`~
`~
`\C
`.,.
`Q
`00
`r:J\
`
`i
`
`1-
`
`1-
`
`~
`
`3~O
`
`NATION B
`TRUSTED DEVICE
`OF RECIPIENT
`SYSTEMWIDE AUTHORITY
`PUBLI[ KEY
`
`r-
`I
`RE[IP. ES[ROW CERT.
`I
`I
`RECIP. NAME
`CROSS-CHECKS
`I
`----------- RECIP. COUNTRY CODE
`I
`RECIP. PUB ENC KEY
`I
`EA NAME (ISSUER)
`I
`EA SIGNATURE
`.-I
`
`VERIFIES
`- ~ ~ -
`-
`
`-
`
`-
`
`-
`
`FIG. 30
`
`PRIVATE ESCROW
`AGENT
`SENDER ESCROW CERT.
`SENDER NAME
`SENDER COUNTRY CODE
`SENDER PUB ENC KEY
`EA NAME (ISSUER)
`EA SIGNATURE
`
`EA CERTIFICATE
`EA NAME & COUNTRY
`EA PUBLIC SIG KEY
`EA PUBLIC ENRC KEY
`PUBLIC AGENT = NO
`SYSTEMWIDE AUTH SIG.
`
`- - - -_ ... _-----_.-
`
`-
`
`~.
`
`- - " - - -
`
`1-
`
`I- ,....,
`
`I
`I
`I
`I
`I
`I
`L
`
`I -
`
`1-
`
`I--
`
`1- 041 -
`
`r-
`
`'---
`
`
`""0
`
`
`
`
`
`
`
`0)
`
`COMPASS EXH. 1005 - Page 27 of 53
`
`

`
`5,799,086
`
`1
`ENHANCED CRYPTOGRAPHIC SYSTEM
`AND METHOD WITH KEY ESCROW
`FEATURE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This is a division of application Ser. No. 08/272,203, filed
`Jul. 8. 1994, abnd which is a continuation-in-part of appli(cid:173)
`cation Ser. No. 08/181,859, filed Jan. 13. 1994, now aban(cid:173)
`doned.
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to cryptographic communications
`systems. More particularly, this invention relates to the
`secure generation, certification. storage and distribution of
`cryptographic keys used in cryptographic communications
`systems. Still more particularly, this invention relates to a
`system of cryptographic key escrow and public-key certifi(cid:173)
`cate management enforced by a self-certifying chip device.
`The development and proliferation of sophisticated com(cid:173)
`puter technology and distributed data processing systems
`has led to a rapid increase in the transfer of information in
`digital form. This information is used in financial and
`banking matters. electronic mail. electronic data interchange
`and other data processing systems. Transmission of this
`information over unsecured or unprotected communication
`channels risks exposing the transmitted information to elec(cid:173)
`tronic eavesdropping or alteration. Cryptographic commu(cid:173)
`nications systems preserve the privacy of these transmis(cid:173)
`sions by preventing the monitoring by unauthorized parties
`of messages transmitted over an insecure channel. Crypto(cid:173)
`graphic communications systems also ensure the integrity of
`these transmissions by preventing the alteration by unau(cid:173)
`thorized parties of information in messages transmitted over
`an insecure channel. The cryptographic communications
`systems can further ensure the integrity and authel).ticity of
`the transmission by providing for recognizable, unforgeable
`and document-dependent digitized signatures that can pre(cid:173)
`vent denial by the sender of his own message.
`Cryptographic systems involve the encoding or encrypt(cid:173)
`ing of digital data transmissions, including digitized voice or
`video transmissions. to render them incomprehensible by all
`but the intended recipient. A plaintext message consisting of
`digitized sounds. letters andlor numbers is encoded numeri(cid:173)
`cally and then encrypted using a complex mathematical
`algorithm that transforms the encoded message based on a
`given set of numbers or digits, also known as a cipher key.
`The cipher key is a sequence of data bits that may either be
`randomly chosen or have special mathematical properties,
`depending on the algorithm or cryptosystem used. Sophis(cid:173)
`ticated cryptographic algorithms implemented on computers
`can transform and manipulate numbers that are hundreds or
`thousands of bits in length and can resist any known method
`of unauthorized decryption. There are two basic classes of
`cryptographic algorithms: symmetric key algorithms and
`asymmetric key algorithms.
`Symmetric key algorithms use an identical cipher key for
`both encrypting by the sender of tbe communication and
`decrypting by the receiver of the communication. Symmet(cid:173)
`ric key cryptosystems are built on the mutual trust of the two
`parties sharing the cipher key to use the cryptosystem to
`protect against distrusted third parties. The best known
`symmetric key algorithm is the National Data Encryption
`Standard (DES) algorithm first published by the National
`Institute of Standards and Technology. See Federal Register,
`Mar. 17. 1975, Vol. 40, No. 52 and Aug. 1. 1975, Vol. 40. No.
`
`2
`149. The sender cryptographic device uses the DES algo(cid:173)
`rithm to encrypt the message when loaded with the cipher
`key (a DES cipher key is 56 bits long) for that session of
`communication (the session key). The recipient crypto(cid:173)
`graphic device uses an inverse of the DES algorithm to
`decrypt the encrypted message when loaded with the same
`cipher key as was used for encryption. However. the
`adequacy of symmetric key cryptosystems in general has
`been questioned because of the need for the sender and the
`10 recipient to exchange the cipher key over a secure channel
`to which no unauthorized third party has access. in advance
`of the desired communications between the sender and
`recipient. This process of first securely exchanging cipher
`keys and only then encrypting the communication is often
`15 slow and cumbersome, and is thus unworkable in situations
`requiring spontaneous or unsolicited communications, or in
`situations requiring communications between parties unfa(cid:173)
`miliar with each other. Moreover, interception of the cipher
`key by an unauthorized third party will enable that party to
`20 eavesdrop on both ends of the encrypted conversation.
`The second class of cryptographic algorithms, asymmet(cid:173)
`ric key algorithms. uses di1ferent cipher keys for encrypting
`and decrypting. In a cryptosystem using an asymmetric key
`algoritlun. the user makes the encryption key public and
`25 keeps the decryption key private. and it is not feasible to
`derive the private decryption key from the public encryption
`key. Thus, anyone who knows the public key of a particular
`user could encipher a message to that user. whereas only the
`user who is the owner of the private key corresponding to
`30 that public key could decipher the message. This publici
`private key system was first proposed in Diffie and Hellman,
`"New Directions in Cryptography," ffiEE Transactions on
`Information Theory, Nov. 1976, and in U.s. Pat. No. 4.200.
`770 (Hellman et al.), both of which are hereby incoIporated
`35 by reference.
`An early type of asymmetric key algorithm allows secure
`communication over an insecure channel by interactive
`creation by the communicating parties of a cipher key for
`that session of communication. Using the asymmetric key
`40 algorithm. two interacting users simultaneously and inde(cid:173)
`pendently generate a secure cipher key that cannot be
`deduced by an eavesdropper and that is to be used sym(cid:173)
`metrically to encode that session of communications
`between the users. This interactive method of generating a
`45 secure cipher key was described by Diffie and Hellman in
`their 1976 paper. Under this prior art method. known as the
`Interactive Diffie-Hellman scheme. shown in FIG. 2, each of
`the two users A..B randomly chooses a secret number 21.22
`and then computes an intermediate number 23.24 using two
`50 publicly-known numbers and the secret number 21.22 cho(cid:173)
`sen by that user. Each user next transmits the intermediate
`number 23,24 to the other user and then computes the secret
`(symmetric) cipher key 2S using his own se