United States Patent (19)
`Sudia
`
`54) ENHANCED CRYPTOGRAPHIC SYSTEM
`AND METHOD WITH KEY ESCROW
`FEATURE
`
`Inventor: Frank Wells Sudia, New York, N.Y.
`Assignee: Certco LLC, New York, N.Y.
`
`Appl. No.: 08/802,603
`Filed:
`Feb. 19, 1997
`Related U.S. Application Data
`
`Division of application No. 08/272.203, Jul. 8, 1994, aban
`doned, which is a continuation-in-part of application No.
`08/181859, Jan. 13, 1994, abandoned.
`Int. Cl. ...................................................... H04L 9/32
`... 380/25; 380/30
`Field of Search .................................... 380/30, 4, 25,
`380/49
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,200,770 4/1980 Hellman et al..
`4,218,582 8/1980 Hellman et al..
`4,405,829 9/1983 Rivest et al..
`4,558,176 12/1985 Arnold et al. .............................. 380/4
`4,771,461 9/1988 Matyas ...................................... 380/24
`4,868,877 9/1989 Fischer.
`4,995,082 2/1991 Schnorr.
`5,001,752 3/1991 Fischer.
`5,005,200 4/1991 Fischer.
`5,136,643 8/1992 Fischer.
`5,150,411
`9/1992 Maurer.
`5,164,988 11/1992 Matyas et al..
`5,199,070 3/1993 Matsuzaki et al..
`5,214,700 5/1993 Pinkas et al..
`5,214,702 5/1993 Fischer.
`5,222,140 6/1993 Beller et al..
`5,261,002 11/1993 Perlman et al..
`5,276,737
`1/1994 Micali.
`5,313,521
`5/1994 Torii et al..
`5,315,658 5/1994 Micali.
`5,499.295 3/1996 Cooper ...................................... 380/23
`5,787,172 7/1998 Arnold ...................................... 380/21
`
`USOO60.09177A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,009,177
`Dec. 28, 1999
`
`OTHER PUBLICATIONS
`American National Standard X9.30, “Public Key Cryptog
`raphy Using Irreversible Algorithms for the Financial Ser
`vices Industry: Part 1: The Digital Signature Algorithm
`(DSA)” (American Bankers Assn., Washington, D.C.,
`1993).
`American National Standard X9.30, “Public Key Cryptog
`raphy Using Irreversible Algorithms for the Financial Ser
`vices, Industry: Part 2: The Secure Hash Algorithm (SHA)”
`(American Bankers Assn., Washington, D.C., 1993).
`American National Standard X9.30, “Public Key Cryptog
`raphy Using Irreversible Algorithms for the Financial Ser
`vices, Industry: Part 3: Certificate Management for DSA’
`(American Bankers Assn., Washington, D.C., 1993).
`Silvio Micali, “Fair Public Key Cryptosystems”, Laboratory
`for Computer Science of the Massachusetts Institute of
`Technology, Oct. 13, 1993.
`Donn B. Parker, “Crypto and Avoidance of Business Infor
`mation Anarchy First Annual AC Conference on Computer
`and Communication Security, Nov. 3-5, 1993, Reston, VA.
`(List continued on next page.)
`Primary Examiner-Gilberto Barrón, Jr.
`Attorney, Agent, or Firm-Steptoe & Johnson LLP
`57
`ABSTRACT
`The invention provides a cryptographic System and method
`with a key escrow feature that uses a method for verifiably
`Splitting users’ private encryption keys into components and
`for Sending those components to trusted agents chosen by
`the particular users, and provides a System that uses modern
`public key certificate management, enforced by a chip
`device that also self-certifies. The methods for key escrow
`and receiving an eScrow certificate are also applied herein to
`a more generalized case of registering a trusted device with
`a trusted third party and receiving authorization from that
`party enabling the device to communicate with other trusted
`devices. Further preferred embodiments provide for rekey
`ing and upgrading of device firmware using a certificate
`System, and encryption of Stream-oriented data.
`
`18 Claims, 25 Drawing Sheets
`
`Ks-ttp
`241-1 KKStpp swa
`
`244,
`A USER'S REG, REEST
`
`KSmfgr
`KSiswa
`
`REG, F EWIE
`WITH TRUSTE
`THIRD PARY
`
`8, TTP's RESPONSE
`
`246
`
`
`
`242 EWE ERT
`OWIE Yp
`DEVICE SER No.
`KSidew
`-mfgr.
`
`
`
`
`
`TT's GRANT
`SFWARE AND/OR PLB,
`E. ALITHIRIZATION key LeAES cop.
`TT NAME
`TRS. SFTWARE
`App I, ATA
`TRUSE KEYS
`LSER IN
`APPLIC, ATA
`DEVICE INF
`tto -
`-247
`KSidew
`24g
`-ttP - - - - - - - - -
`NAME
`HEiver
`AR5UAERADE'' - UPGRADE AUTH-24
`ALTH CER
`SW
`
`
`
`
`
`
`
`24.)
`
`242
`
`Wre
`
`RUST
`KSew
`KS devemf gr
`KSimfgr
`kStswa
`
`TRANSACTIONCS)
`USER'S ALTH
`249
`242 TTP's GRANT
`TRANS, DATA
`F ATH,
`User INF
`--
`KSidew
`- Pl
`-dew
`
`
`
`FURTH PARTY
`(eg TRADING
`pARTNER)
`KSiswa
`Kshttp
`
`SAMSUNG EX. 1037 - 1/53
`
`

`

`6,009,177
`Page 2
`
`OTHER PUBLICATIONS
`CCITT Recommendation X.509, “The Directory-Authen
`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, “Commercial Encryption', IEEE Net
`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”,
`IEEE Network Magazine, Apr. 1987, vol. 1, No. 2, pp.
`11-16.
`
`IBM Technical Disclosure Bulletin, “Cyrptographic Micro
`code Loading Controller for Secure Function”, vol. 34, No.
`4B, Sep. 1991, pp. 34–36.
`
`SAMSUNG EX. 1037 - 2/53
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 1 of 25
`
`6,009,177
`
`DIFFIE-HELLMAN AND MICALI ABBREVIATIONS
`
`X
`X1 , , ,
`x i
`
`RECIPIENTS PRIVATE KEY (EXPONENT )
`NUMBERED FRAGMENTS OF PRIVATE KEY
`i-th FRAGMENT OF PRIVATE KEY
`SENDER" S. EPHEMERAL PRIVATE KEY C EXPONENT )
`PLELIC BASE NUMBER
`PUBLIC PRIME MOLLUS NUMBER
`INTERMEDIATE NUMBER = ox mod P
`OHx
`INTERMEDIATE NUMBER = oy mod P
`OH
`DIFFIE-HELLMAN OERIVED MESSAGE KEY
`Kd
`V1, ... n MICALI INTERMEDIATE NUMBER, s axi mod P
`
`THER SYMMETRIC KEY ABBREVIATIONS
`
`
`
`Kmsg
`
`C
`
`RANDOM OR DERIVED MESSAGE KEY
`PLAINTEXT MESSAGE
`CIFPHERTEXT MESSAGE
`
`FIG. BSEESA, ASMETRIC
`
`PUBLIC PRIVATE
`
`
`
`SIGNATURE
`
`ENCRYPTION
`
`KKS dev>mfor
`
`FIG. CRESSEATE
`
`PBLIC SIGNATURE KEY
`OF THE DEVICE
`SIGNED BY MANUFACTURER
`(USING MFGR PRIVATE KEY: KS-mfgr)
`
`SAMSUNG EX. 1037 - 3/53
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet 2 0f 25
`
`6,009,177
`
`
`
`quwflthm>muzmmmDHwu<mmmz
`
`
`
`
`
`>w¥ZDHHQ>muzwUHJmDQ
`
`HZmHQHummwIHum
`
`a.umg+my‘nmu<mmmzv
`
`zmhm>muzm>w¥UHJmflm
`
`
`
`nmez<xwvZDHH<HDZ
`
`o—.9...—
`
`nm>m¥mm3h<zunUHJmemDuv>HHmDIH3<DZH>mHHmwu
`
`
`
`
`hzwzwumuuzm3<J nfilmmwzwzu
`AmwwjZ<IhmeHDquwUH>wDmumwzznmezo
`wuH>mDDwFMDMHmIHmummMJHu<u32<zLm+s
`
`
`
`
`>wv_wkuzwmE.me3mmxHuufimmv.Q—l
`
`
`muH>mDDmkmzmkthmmmmw:C...~me3me:
`
`wm<mwmz<umHzmHmHuwmQ_UUL
`
`>hHmDIF3<wDHBIszM>M03m
`
`wu<wwwz<ummmazmmLuncmm
`
`XDmmeDuwD
`
`
`
`muH>mDthwzmha
`
`
`
`mwkzwuBumuwwum
`
`
`
`kzwu<Bumumwom
`
`SAMSUNG EX. 1037 - 4/53
`
`SAMSUNG EX. 1037 - 4/53
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 3 of 25
`
`6,009,177
`
`FIG. F
`SHORTHAND NOTATION - SIGNING
`
`<doto) dev
`
`{dotod KS dev
`
`-dev
`
`FIG. G
`SHORTHAND NOTATION - ENCRYPTION
`<dotoxsender = ( dota ) KEsender
`
`FIG. 2
`INTERACTIVE DIFFIE-HELLMAN KEY OERIVATIVE
`PRIOR AGREEMENT ON (NON-SECRET )
`PRIME P AND VALUE a
`PARTY A
`GENERATE SECRET 21
`GENERATE SECRET
`RANDOM NUMBER x
`RANDOM NUMBER y
`COMPUTE
`COMPUTE
`ax mod p
`oy mod p
`COMPUTE KEY
`COMPUTE KEY
`(oy) mod
`c ox)y mod
`COMMON KEY axy mod p KNDWN BY A AND B
`BUT NOT DEDUCIBLE BY AN EAVESOROPPER
`
`PARTY B
`
`
`
`22
`
`24
`
`23
`
`
`
`
`
`
`
`
`
`
`
`
`
`221
`
`223
`FIG. 22
`DEVICE OWNER'S
`CERTIFICATE ( EXAMPLE)
`
`
`
`
`
`
`
`VERSION NO ,
`DEVICE SERIA No.
`OWNER NAME
`OWNER UNIQUE ID
`KS
`WNER
`PURCHASE DATE
`
`220
`
`222
`
`224
`
`225
`
`MFGR SIGNATURE
`
`SAMSUNG EX. 1037 - 5/53
`
`

`

`US. Patent
`
`])ec.28,1999
`
`Sheet 4 0f 25
`
`6,009,177
`
`
`
`
`
`n<uv>._.Hw_n_I._._u_<wzH>uHhmemmmm:.<
`
`
`
`HzmHmHuww.wmlalfiuzv
`
`~
`
`A<mu‘>V
`
`
`>m¥wk<>Hmmm<ummnmmH
`<._.<Dw._.<uH”.H._.~_m_uwmm
`
`mz<zmmw:
`
`AXID.oH:
`
`
`
`mm._.<n_DHJ<>
`
`HHzmzumxw
`
`
`
`mmeZZwH<HDwzmmHZHID
`
`XIDllmU05xo
`
`an>my
`
`>4mm2umw
`
`
`
`AXID‘O.nC
`
`
`mk<>Hmmmuchm
`
`>wv_uHn_m3n_mmmw:
`
`
`
`<._.<Dn<uvmz<zmwjmmH
`
`
`>wv_m.._.<>Hw_n_
`MHZ<HMZDUUH153m
`
`szuHm
`
`
`
`.Hmmu<._.<n_Vmmm:._.<._.<zuHmmwjmmHwajmwmwH<UHuHmmu
`
`
`
`
`
`mm-mmm__)_<zmmw:‘AXID‘0.0:
`
`
`
`
`
`
`
`.meu.uz4<Hmmm.meu“m
`
`
`
`Nm
`
`.DZZDHmmw>
`
`mmmhwz<m<mIDmk<mmzwu
`
`Dwummmmu33:53as;m9...
`<u>mmmm:upzmzhmm.
`
`
`
`
`
`z<zlijImHuuHDDwHu5.me
`
`
`
`ZDH._.<an_H._.w_m_uI
`
`SAMSUNG EX. 1037 - 6/53
`
`SAMSUNG EX. 1037 - 6/53
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`])ec.28,1999
`
`Sheets 0f25
`
`6,009,177
`
`wkjmzuu
`
`ZDHmmmw
`
`mum>wy
`
`ww<mwwz
`
`km>muwo
`
`
`
`Ammo.mmv
`
`Hm
`
`4<ZHUHMD
`
`>m¥meuww
`
`
`
`HzmHmHuwm.mow
`
`V.O_h_nwEEuzm
`
`
`.Ez<244wzumHuuHaxHume:HHzAmmo>V
`
`0235mm;
`
`awHuHhmmumu<mmmzmu<wmmzFm>muzm
`
`
`
`amkm>muzm
`
`amu<mmmz
`
`m?
`
`mm
`
`wH<UHmHHmmu
`
`M.mw>Hmuwm
`
`
`
`<H<Dmh<uHuHHmmu
`
`
`
`mmZH<ZDHMmmJMMH
`
`mm
`
`>m¥UHszm
`
`<ummflme
`
`mwmzmm.<
`
`>m<mumzwh
`
`m~mwmzwm
`
`“V
`
`mm
`
`>w¥
`
`mh<>Hm1
`HEmzuaxm
`
`ZDDZ<m
`
`wk<mwzmw
`
`AXID.0.&V
`
`M.1Humm
`
`ZH<FmD
`
`UHszm
`
`<H<D>w¥
`
`mk<HDwZMMHzH
`
`mmeJZID
`
`El3:0m.mwgzwmlOfi
`
`ZDHwaw
`
`mum>m¥
`
`wu<mmwz
`
`NV
`
`
`
`cu¥.A|.¢uoe>nxxov
`
`SAMSUNG EX. 1037 - 7/53
`
`SAMSUNG EX. 1037 - 7/53
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet6 0f25
`
`6,009,177
`
`
`
`Dwkm>muzw<Mm
`
`>w¥wwa
`
`Dmhm>muzwmma
`
`wu<mwmz
`
`mm
`
`>m¥wwo
`
`<mm
`
`kl>muzw
`
`
`
`ompm>muzw<mm_m
`
`
`
`J<ZHUHMDwwD
`
`Hm>muzw
`
`wu<mwwzZDHHUZJu
`
`
`
`ZDHkm>mumDIHmummz<MH>m¥<Mm
`wh<>Hmmw.w—mM‘kszmHuwmmm
`
`>w¥
`
`Nmmm<wwwz
`
`thm>muzmme
`
`J<ZHuHmD
`
`>w¥wmm
`
`ZDHHUZZu
`
`Fm>muzm
`
`<Mm
`
`
`
`Dmhl>muzw<Mm
`
`>w¥me
`
`SAMSUNG EX. 1037 - 8/53
`
`ZDHHUZZu
`
`Dwkm>muzwMwD
`
`wu<mwmz
`
`ZDHHUZju
`
`Hm>muzw
`
`mmm
`
`AHM<uV
`
`mm
`
`>w¥mwa
`
`ZUDZ<m
`
`haulmz<mh>w¥<Mm
`ZDHhm>muzwIm.OPK
`
`M‘szHmHumm
`
`>w¥UHijm
`
`mm
`
`SAMSUNG EX. 1037 - 8/53
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 7 of 25
`
`6,009,177
`
`
`
`G/.S , (JEUNES
`
`
`
`
`
`94.
`
`
`
`24.
`
`SAMSUNG EX. 1037 - 9/53
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 8 of 25
`
`6,009,177
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG
`
`MICAL ESCROW PROCESS EXAMPLE -
`USER OPERATIONS
`
`SECRET
`GENERATE OH PARAMETERS g2 RANDOM
`NUMBERS
`PRIVATE KEY COMPONENTS
`x1, x2, x
`3
`
`PUBLIC CONSTANTS
`PRIME
`Pl
`BASE
`a
`
`USERS PRIVATE KEY X
`( x1 + x2 + x3) mod P-O-X
`
`
`
`
`
`STORE PRIVATE
`KEY
`SECURELY
`
`OH INTERMEDIATE NO ,
`oxmod P-O-DHX
`
`
`
`
`
`
`
`
`
`99
`
`USER PUBLIC KEY
`(P o DHx)
`
`
`
`MICALI INTERMEDIATE Nos
`aximod P-V1
`ax?mod P-V2
`oxmod P-V3
`(V1 kV22kV3)mod P-o-DHX
`
`
`
`
`
`93
`
`
`
`
`
`ESCROW AGENTS STATS
`(P, o, OHx, V1, x1, USER NAME}
`(P, o, OHx, V2, x2, USER NAME}
`(P,
`OHx, V3, X3, USER NAME)
`O ,
`
`SEND 1
`94
`SHARE TO
`EACH ESCROW TO ESCROW
`AGENT
`AGENT 1.
`
`94
`TO ESCROW
`AGENT 2
`
`94
`TO ESCROW
`AGENT 3
`
`SAMSUNG EX. 1037 - 10/53
`
`

`

`US. Patent
`
`D
`
`9
`
`771,
`
`
`
`
`
`MZDHH<mwnE...zww<BumuwwIm|_n_z<xwmmwuammzawfimm”34‘qu0—0—H
`
`
`
`
`
`
`
`
`
`mwm:zumn.
`
`
`
`mszuimmm:20m”.Nszu<aFzmu<
`
`
`
`mmm:ZDNE
`
`mwMJ‘mx‘m>.XID‘o.
`__,_______
`mmw:.mx.m>‘x1n_‘o‘
`*mz/‘zn;mwMZJX.
`
`*wz<zn;~>sXID.o.n;
`
`wz<z
`
`A
`
`m>HIum<_“NVm>qum<_Advm>HIum<w__Wm,m>LTIn_uoemxo__“>111nosfixow“my>uHmw>_Amy
`
`
`
`
`
`
`
`
`
`Amx‘mz<zmmmzv_Amx‘mz<zmwmzv_Afix\wz<zmwmnv”Amy
`>uHmw>_n_v>uHmm>
`
`f__o__
`
`wh<>Hmm5m‘mhzwu<_m.mszu<_m‘fiPzwu<
`
`
`
`
`
`
`
`J<>nmmm<_Amy<H<a4<>um¢m<_“flu<F<nJ<>ummm<amz<zmmm:.m>.x:a.o~mv_mz<zmmmz‘m>.xxa‘o.mv_wz<zmmm:.~>.xxa‘o‘mvw“my<F<a
`mh<>Hmmmh<>Hmm
`
`
`mank<zuHm_mmzh<zuHm_mmzk<zun
`
`>m¥_>m¥_>my
`
`(m,m<H<a4<>umma<_m<k<a4<>ummm<_fl<P<a4<>nmmm<__mm
`
`
`
`
`
`9__mmmzizBmm.mEH;mmnzzflmPmEm?mmazzuHmm;Ema:
`
`
`
`SAMSUNG EX. 1037 - 11/53
`
`mm
`
`SAMSUNG EX. 1037 - 11/53
`
`
`
`
`

`

`US. Patent
`
`])ec.28,1999
`
`Sheet10 0f25
`
`6,009,177
`
`
`
`
`
`
`
`MZDHH<mwn=uawhzmuBflmumwmwhmflzIm4mz<xwmmwuflmm3DmummH4<UHZ:0?.“
`
`
`
`
`
`
`
`
`
`m.mszu<
`
`UHszm
`
`ZDHH<uHmHmm>
`
`>w¥
`
`m.Nszu<
`
`UHJmflm
`
`ZDHH<UHuHmw>
`
`>wy
`
`m-hzwu<
`
`UHJmJQ
`
`ZDHH<uHuHmm>
`
`>my
`
`mm_mm_mm
`
`
`
`
`
`
`
`<H<oaw>umam<_<F<aam>ammm<_<h<aam>um¢m<
`
`
`
`wm3H<zuHmm\NHzmu<mm3H<ZUHMm._szu<
`
`________
`
`
`
`m<H<DDm>Dmmm<
`
`mmjk<zunm~mszu<
`
`mHzmu<mm
`
`Dm>Dmmm<Nszu<mm
`N<H<D
`
`20mm_
`
`:Dmu
`
`fl<F<DDm>Dmmm<ahzmu<
`zumumm
`
`
`
`
`
`sz<zmmwj‘m>‘XID.omy_awz<zmmmz~m>‘XID‘o‘mvAmz<zmwm:‘~>.XID.o.mv
`
`
`
`
`
`
`
`
`
`.ozJ<Hmwm.Hmwunuzv>uHmm>w.mww:
`mz<zmmm:Ianvmu“*m>*m>*~>vwk<uHqummuzmnhmm
`
`
`
`
`sza0avxasm.mmhzmummpm<zmmm:
`‘.mm3h<zuHm
`
`
`
`AN>.wz<zm.Nszu<vmmhw<z
`
`Am>wz<zm~mszu<vM.mmhzwu
`
`
`‘w>HIum<
`
`
`
`wwH<DDH4<>
`
`
`
`A~>.wz<zm‘fiszu<v
`
`
`
`mum:wh<wmu
`
`
`
`<H<D.Hmmu
`
`
`
`w~mwhzmummhm<z
`
`
`
`wm2k<zunwh<>Hmm
`
`>wM
`
`SAMSUNG EX. 1037 - 12/53
`
`SAMSUNG EX. 1037 - 12/53
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sheet 11 0f 25
`
`6,009,177
`
`Dec. 28, 1999
`FIG. 2
`
`ESCROW CERTIFICATE ( EXAMPLE X
`
`VERSION NO ,
`CERTIFICATE SERIAL No.
`ESCROW CENTER NAME
`ESCROW CENTER COUNTRY CODE
`KE ec (FOR LEAF USE)
`USER NAME
`KEt user (FOR MESSAGES)
`KStdev ( To VERIFY LEAF
`VALIDITY PERIOO
`
`ESCROW CENTER SIGNATURE
`
`123
`21
`
`122
`
`124
`
`25
`
`FIG. 3
`
`CLIPPER LEAF PACKET C CONJECTURED)
`* msgkdv
`CHECKSUM OF Kmsg
`
`
`
`
`
`OEVICE SERIA No,
`
`CHECKSUM OF LEAF
`
`Kfam
`
`
`
`
`
`SYMMETRIC MESSAGE KEY
`EMBEDOED SYMMETRIC DEVICE KEY
`SYMMETRIO CLIPPER FAMILY KEY
`
`SAMSUNG EX. 1037 - 13/53
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 12 of 25
`
`6,009,177
`
`FIG. 4
`DEVICE CERTIFICATE : <KS devemfgr. C EXAMPLE)
`
`
`
`
`
`VERSION NO ,
`MFGR NAME
`DEVICE SERIAL. No,
`OEVICE TYPE/MOOEL
`MFG DATE
`KS todev
`ATTRIBUTE CODES (OPTIONAL )
`
`MFGR SIGNATURE
`
`FIG. 18
`MESSAGE CONTROL HEADER C EXAMPLE)
`( IN RSA - KEY - TRANSPORT FORMAT )
`
`
`
`
`
`VERSION NO ,
`(MESSAGE KEY) KErecip
`SENDER ESCROW CENTER NAME ( 21 )
`SENDER ESCROW CENTER COUNTRY COOE
`RECIPIENT ESCROW CENTER NAME ( eC2)
`RECIPIENT ESCROW CENTER COUNTRY CODE
`(SENDER ESCROW CERT, NO, ) KE ec 1
`(MESSAGE KEY) KEtsender (TD HIMSELF)
`C RECIP, ESCROW CERT. No, ) KEtec2
`TIMESTAMP (OPTIONAL )
`
`SENOER DEVICE SIGNATURE
`
`B1
`
`181
`
`181
`81
`
`SAMSUNG EX. 1037 - 14/53
`
`

`

`SAMSUNG EX. 1037 - 15/53
`
`

`

`US. Patent
`
`])ec.28,1999
`
`Sheet 14 0f 25
`
`6,009,177
`
`we“
`
`mm“
`
`>MUI
`
`umm>my
`
`mwk<uHuHhmwu
`
`wZDJ<wuH>wDDwPMZWE.2DDwm<mmF.0—k
`
`UZHHHHJQM>w¥w4m<HmHmw>
`
`
`
`
`
`
`
`UHszmmuH>maomkmzmh2mmmuH>mn
`
`
`
`mummw3Dmumwozm+M¥Lm+e+mywhzwzu<mu>m¥
`
`
`
`.HmmuwuH>mD
`
`3DMUMwm~szu<>UUIM¥>UU+M¥mX.NX.~X
`
`
`
`
`LsLsLwhzmu<~0m+m¥LumzumyLumg+mym.azmmzmmab<
`
`
`
`
`
`um:fimfi
`
`
`
`
`
`
`
`
`
`om~~UCOCLum:.UEOCme:~UEOCLUMJ
`
`.n>uu.n>mu~n>mu
`
`
`
`
`
`anHmmumkzu3amumm‘Lum:+m¥.Lum:+m¥‘me:+my
`
`
`
`
`
`
`
`mwhzwuUU+mv_>U_ul>UUI>UUI
`
`
`
`
`
`
`
`zumuwwum+w¥momAmL.mxvNomnNL.Nxv“omhfig.~xv
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.+wM~%>MU.UEOCLON:k>UD.mX"ULOPm%>UU.NX“NLOPm%>UU.HX"ULO¥MmHzmu<BumumwNhzwu<Bumuwwflhzwu<Bumumw
`
`
`
`UNAUEOCWON
`‘NEOCNomqu
`.NEOC—Om‘~Lv
`
`
`
`
`
`momlNoun,down
`
`
`
`
`
`‘momhn>uv‘vaomflu>mu.mgvomnn>uu._gvLme3+w¥~weocme3+wy.msocLum3+wy.meoc
`
`
`
`MHZUzumumm
`
`
`
`mL‘NL~_L>uHmm>
`
`wz<m
`
`>mnl
`
`weocme:
`
`Lum3+my
`
`>uu+wy
`
`mmfi
`
`wh<UHuHHmwu
`
`
`
`
`
`zumummmh<mmumwm:uhzmzkmm
`
`bmd
`
`SAMSUNG EX. 1037 - 16/53
`
`SAMSUNG EX. 1037 - 16/53
`
`
`
`
`
`
`
`

`

`US. Patent
`
`771,9m
`
`
`
`
`
`
`
`6,nzmH>~m>EE:1:;$532awE>muzmazmmfi—.0.“—
`
`wyfimmsyv|u<m4Nb“
`a_uuL
`
`Lmucmm+mynmmsyv
`
`
`
`DwHMDMHM‘mmmzwm
`
`mh
`H
`
`
`
`3Dmumwmwnzww
`
`mh<UHuHHmwu
`
`mh~
`
`wu<wwmz
`
`~>mu+my
`
`
`5.meEasmeHmm;m29:5mmmzbizzémm26.1:imwfizmms
`
` umEuz_._m_wEuEmeu_mzmkwfimums___i_m>mu+my”IE01,ESEHEB3,390mm
`
`.EummmHEBi
`
`.m333fiHmqu<waszmth
`
`m2
`
`SAMSUNG EX. 1037 - 17/53
`
`SAMSUNG EX. 1037 - 17/53
`
`
`
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet 16 0f 25
`
`6,009,177
`
`N>mn+w¥
`
`
`
`IELuucummxmmsv:
`390mm.Eumm|mm“mmfiqu
`
`mh<uHuHhmmumh<>Hhu<a»a_UULmun.meyv
`
`
`
`Noun
`
`
`
`amhmnmhm.kszmHumm
`
`muH>ma
`
`
`
`
`mu<mmmzAnuuum>muuw¥Annnusumummmmazmm
`L.+EA>uu+myvvawh<uHuHhmmu
`
`fimfi
`
`mmeynmu<wmmzv
`
`
`
`
`
`
`
`mm“nun-Imamammnnnu..L--mmmmmmmmnnu
`
`
`
`
`
`nsz>mw>UvquIt”:wu<wwwzDw._.n;w_u2m_w>kuwmmF.o—k
`
`
`
`
`
`Q_UMLIm¥
`
`__
`
`_
`
`wwHuHmw>
`
`7.1.I.I
`
`_wh<uHqummu_mm“thw>wHum
`
`SAMSUNG EX. 1037 - 18/53
`
`~>uu+mg
`
`SAMSUNG EX. 1037 - 18/53
`
`
`
`
`
`
`

`

`US. Patent
`
`])ec.28,1999
`
`Sheet 17 0f 25
`
`6,009,177
`
`mmkzmu
`
`
`
`3DmumwbON
`
`
`
`
`
`
`
`nm4m2<xwvBDIEMwmunmmxummeDuwDON.0-k
`
`AUAU
`
`mwz<z
`
`
`.mm<3.ommMUDJUmszamhmzmp
`momxum
`
`"2H<Pmu“thmnm>my.mmzm.mzmm‘xumxonAxon+myv>m¥mwzm.mzm
`
`
`
`
`muwwm3%?amE22“.w
`zumuww.>mn_.n_m|_<>w_w.rzHwzfl.._.z<mw_<3%z<H.‘
`
`
`
`Amy”Emu0mx‘mx;x“whimE:uxumm‘xum
`
`
`mwzmm<mmzzaAmzH».mthvmsz.mmau.>a<mm
`
`
`
`
`
`
`mmm:m<m.._._>wv_.mumD>Hw_n_w.xumxonlmymDNmz<HmwzHH.w
`HmwuN;umcm_ml9me
`
`>my.uHm.>Hmmm.xumwxxon‘my.mmnu<mammH=
`
`
`
`
`
`Hmwumum:M.x_umLm+EAxon+M¥v
`
`
`
`
`
`
`
`Amwmmi.”EVDONxummeDuwDunummmwmzf.
`
`
`
`ZDHHUZNFMZHmmzzuXDm
`
`HHJmm>mymHmum:mumum:u>uumumxon+myn_xvmommum:MnHzmu<
`
`
`BnmuwmnxumDHDmcm_mlSum“.
`
`
`
`:MHmmu+wuH>wa®xum:nwntfixamm.xam
`
`myxumHmmu
`
`>my.IF:<wquszm>mahanAxum>m.xon+my
`
`
`
`umhwnmkvmum:xumah¥u<mqun<w4xummxhan>myqu4mzmwrhmmoz:
`
`
`
`whmmuszu<zumuwmIu<kh<"mhnz///amhm>muzmmH_FHJmm>my.mhaz
`
`
`
`
`
`mum:mum:
`
`
`
`
`22.2mezumummmumcmfilzumu
`NCm....u_DHx<kahmwu
`mommz<zmmzzummwmmmnxum.
`
`
`
`SAMSUNG EX. 1037 - 19/53
`
`SAMSUNG EX. 1037 - 19/53
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 18 of 25
`
`6,009,177
`
`TAMPER-RESISTANT DEVICE
`
`CPU
`CRYPTO
`CDPROCESSOR
`
`21 O
`
`MEMORY:
`KST dev
`<KS dev>mfg
`KS swo
`FIRM NAME
`OTHER KEYS
`& CERTS
`DEVICE
`
`CLOCK BATTERYC
`
`
`
`TRUSTED TIME-SETTING
`ENT (eg POST OFFICE)
`2 1
`TIME-SET
`INSTRUCTION
`THE TIME IS NOW
`3: O5PM JAN 3, 1994
`SET YOURSELF AND
`PROCEEO
`SIGNED,
`POST OFFICE
`
`TIME-SET AUTH, CERT,
`"POST OFFICE" IS. A
`TRUSTED TIME-SETTER
`SIGNED, SYSTEMWIDE
`AUTHORITY
`
`212
`
`VERIFIES
`
`(NOTE: TIMESTAMP WILL
`BE NULL IF CLOCK
`NOT CALIBRATED )
`
`ANY DATA STRUCTURE
`CONTAINING A CONTEMP
`ORANEOUS TIMESTAMP
`
`213
`JAN 3, 1994 - 3:05PM
`
`214
`
`SIGNED, DEVICE
`
`25
`
`DEVICE MFGR'S CERT,
`"DEVICE i
`IS TRUSTED
`TD ISSUE TIMESTAMPS
`KStdev
`SIGNED, MFGR
`
`FIG.2
`SELF-CERTIFYING TRUSTED TIMESTAMP DEVICE
`
`SAMSUNG EX. 1037 - 20/53
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 19 of 25
`
`6,009,177
`
`239
`
`231
`
`232
`233
`234
`
`235
`
`236
`237
`SIGN
`
`23 B
`
`
`
`230
`
`TRUSTED
`DEVICE
`
`NEW ESCROW
`REUEST
`MESSAGES
`
`t
`
`C
`
`E
`
`235
`
`234
`
`FIG. 23
`OWNER REKEY INSTRUCTIONS PROCESS
`
`SAMSUNG EX. 1037 - 21/53
`
`

`

`US. Patent
`
`hS
`
`77
`
`
`
`wuH>moum.uwmA.ppv>Fm<mamHIhawszmk
`
`
`
`
`
`85:51:;.VNOT..—Lmtme.3°78.
`
`
`
`>Hm<mamHIH.ozm+m¥ozmAaap+myv
`
`mVN
`
`wwzummwmm.n:.._..m
`
`
`
`
`
`hwwzumm.uww.mimm:.4.
`
`EN
`
`
`
`fl,m>myumhmzmh<H<a.uH4¢a<%wm<3hunmawhwzmhmz<zmkkm“Hueymmn<mum3>myzuHH<NHmDIF2<
`
`
`
`
`
`
`
`
`
`
`
`
`.mflmmu\Dz<wm<3Hu=um”E._.Z.<w_um.n_._.._.
`
`wuqummm:
`
`
`m\mhkwmz<zmkk
`
`Izmhm>w>HHHzmnHmnHzm.p»+my
`
`f.mu<mumzaz<MIh3<ma<mum3ommovm5mvmi.53it:
`
`
`
`19Q03mMy9P+Wozwfimwma52:8.
`
`(uAmeP<m.IH:<mu<k<n.mz<mh>umnwym¢m
`
`,L+A>mnmy
`u>wmwm<mwazmwkz<mum.mhhnvmme
`
`
`
`
`
`AmvzuHhu<mz<mp.Ik:<m.mmw:.umuH>munmkmnmh
`
`SAMSUNG EX. 1037 - 22/53
`
`SAMSUNG EX. 1037 - 22/53
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 28, 1999
`
`Sheet 21 of 25
`
`6,009,177
`
`
`
`254
`
`lo
`
`FF
`
`252
`256
`257
`256
`257
`
`253
`
`
`
`
`
`
`
`
`
`
`
`
`
`251
`255
`257
`
`258
`
`FIG. 25
`LAW ENFORCEMENT ACCESS FIELD C MULTIPLE RECIPIENTS )
`(IN RSA - KEY - TRANSPORT FORMAT )
`
`SAMSUNG EX. 1037 - 23/53
`
`

`

`SU
`
`2a.D
`
`m
`
`6
`
`77
`
`
`
`
`
`n...ommmmmmEuEHEmumwzzm
`
`mwzzn“auzBmmmzmw08,mmor.
`”m._<m.3552E:Eu3sz;
`
`
`
`mmmI'll—mmEHmmSQ
`
`
`
`
`>my.mza.muzIIIIIImsz<zuHm.muz
`
`
`tyzfimIIIIIIEV..Bmuflmzm
`
`
`
`
`mmzsun.wmmmommzm@Emmmagma8.5szmm?magma
`
`
`
`
`
`2255.55mmumzéhmwzza0on.mm0—“—
`
`
`
`50mmNmNmat.muH>mDnmmumzéh@33sz
`
`19.wmmEEmSG
`
`
`
`0,Ev..mE.Ez—IIIIIImmzzzuHmTmmzzummm
`
`
`
`
`Ev.mamHmmzznIIIIIIEv.Hana.mlmmzzuvmm
`
`
`
`
`
`Emmwufinmm@magma353m;mmmzzzmagma
`
`SAMSUNG EX. 1037 - 24/53
`
`SAMSUNG EX. 1037 - 24/53
`
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet 23 0f 25
`
`6,009,177
`
`Bumumm
`
`mmhzmu
`
`®
`
`I@
`
`DwHMZQH
`
`wuH>mD
`
`
`
`UHJmZmm.mw23D
`
`
`
`>m¥.meZH
`
`OBNW.mwzzn—
` wuH>wD9MZDHHUDMHMZHNPN
`
`
`mmmZZZ
`
`
`
`
`
`wz<2mmhzwu3Dmumm
`
`
`
`mwz<zszu<3Dmumw
`
`
`
`*DHwDUHZjmm23u
`
`
`
`
`
`o.kmwummhzwuBumummv
`
`
`
`uHmmwkzwuBumumm
`
`
`
`>m¥muzw.mflmmmzzu
`
`Hmmumum:ZHM><Hw*DHmwzzu
`
`
`
`.Hmwuzumumm3wz
`
`wz<zmmm:
`
`>wymuzw.mjmmwm:
`
`
`
`*DHwjaHz:mwzzu
`
`memHmm>fi.l
`mm3h<ZDHmwmwzzu
`
`~
`
`
`
`mh<>Hm1mmzzu
`
`>w¥mmnk<zun
`
`mum
`
`
`
`
`
`.mmz<zszu<MJUMFZDUmwzzunwwhnz
`
`sum.0.“—
`
`
`
`mmwuumm>m¥wmDwJJDMHZDUmwzzu
`
`
`
`
`
`SAMSUNG EX. 1037 - 25/53
`
`SAMSUNG EX. 1037 - 25/53
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet24 0f25
`
`6,009,177
`
`mZDHH<Z<ZDHF<Z
`
`
`
`
`
`.Hmwu3DmummwamjmmN“mm.HmeBumuwwfimmM:
`
`
`
`
`
`mm.9... unIHZ<
`
`
`wDszwHM>MuHmIHJ<wDszth>M
`>w¥umzwuHszmN<w>w¥umzwUHJmJQH<w
`
`>w¥DHMUHJmflmN<w>m¥DHMUHJmflmfi<w
`
`>mHZJDUwmZ<ZN<w>w¥UHijm>mHZJDUamZ<Z~<m
`
`mm>Hszu<UHszmDZnHzmu<UHJme
`
`
`
`
`
`mDDu>mH23DUNmmm:mDDU>mHZJDuHmwm:
`>w¥uzwmjmwaMZ>m¥uzwmjmHmmm:
`fi<wmmnzzuHmN<m853m...mwnzwmEAmwjmmHvwz<zN<wAmeMMHVwZ<Z
`
`
`
`
`
`mh<uHuHhmmuN<w>HHMDIH3<MDHBthm>Mwh<UHuHhmwu~<w
`
`wUH>wD
`
`
`
`szzwummuzwmwazmmIZDHPUHMFMmmZH<XDD
`
`
`
`
`
`SAMSUNG EX. 1037 - 26/53
`
`SAMSUNG EX. 1037 - 26/53
`
`

`

`US. Patent
`
`Dec. 28, 1999
`
`Sheet25 0f25
`
`6,009,177
`
`mZDHH<Z
`
`
`
`wz<zmezww
`
`
`
`
`
`.Hmwu3DmummmmDwa
`
`
`
`me<wIJMHUwmz
`
`
`
`mH<UHuHHmemwazww
`
`wh<uHqummu<wmwazmm
`
`
`
`kzwzmumuuzmmw>kuwmI
`
`
`
`ZUHHUHmhwwmZH<ZDD
`
`on.9...—
`
`<ZDHH<Z
`
`
`
`Bumummwh<>Hmm
`
`kzwu<
`
`
`
`
`
`mDDu>mP23Dumwozmm
`
`
`
`NUH>wDDwHMZMF
`
`szHmHummmu
`
`
`
`>HHmDIh3<wDszme>m
`
`>mMUHijm
`
`wauu>mhzzuu.mHuwm>myuHmUHszm<w
`
`
`.kmmuzumumm.mHummmk<uHuHHmwu<w
`
`
`>wMuzwmjm.mHuwm>m¥umzmUHszm<m
`AmmZMMHVwz<2<wDZHhzwu<UHJmflm
`
`
`wZ<Z.mHuwm>MHZJDUawZ<Z<w
`
`wyuwIUIwmeu
`
`
`
`mmnh<zuHM<wIIIIIIIIIuHmIHJ<wDHBZwHM>M
`
`SAMSUNG EX. 1037 - 27/53
`
`>w¥uzwmflmmwazwm
`
`AmwnmmHvmz<z<m
`
`mmzk<zuHm<m
`
`SAMSUNG EX. 1037 - 27/53
`
`
`
`
`
`

`

`6,009,177
`
`1
`ENHANCED CRYPTOGRAPHC 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, now abandoned which is a continuation-in-part
`of application Ser. No. 08/181859, filed Jan. 13, 1994, now
`abandoned.
`
`2
`149. The sender cryptographic device uses the DES algo
`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
`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
`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
`Slow and cumberSome, and is thus unworkable in Situations
`requiring spontaneous or unsolicited communications, or in
`Situations requiring communications between parties unfa
`miliar with each other. Moreover, interception of the cipher
`key by an unauthorized third party will enable that party to
`eavesdrop on both ends of the encrypted conversation.
`The Second class of cryptographic algorithms, asymmet
`ric key algorithms, uses different cipher keys for encrypting
`and decrypting. In a cryptosystem using an asymmetric key
`algorithm, the user makes the encryption key public and
`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
`that public key could decipher the message. This public/
`private key System was first proposed in Diffie and Hellman,
`“New Directions in Cryptography,” IEEE Transactions on
`Information Theory, Nov. 1976, and in U.S. Pat. No. 4,200,
`770 (Hellman et al.), both of which are hereby incorporated
`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
`algorithm, two interacting users Simultaneously and inde
`pendently generate a Secure cipher key that cannot be
`deduced by an eavesdropper and that is to be used Sym
`metrically to encode that Session of communications
`between the users. This interactive method of generating a
`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
`publicly-known numbers and the secret number 21.22 cho
`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 25 using his own Secret number
`21,22 and the intermediate number 24.23 just received from
`the other user. The interactively generated cipher key 25 is
`then used symmetrically by both users as a DES or other
`Symmetric cipher key to encrypt and decrypt that Session of
`communications over an otherwise insecure channel in the
`manner of Symmetric key algorithm communications. This
`interactive process requires only a few Seconds of real time,
`and all digital communications, including digitized Sound or
`Video transmissions, in a particular Session can be encrypted
`merely by pushing a button at the outset of a Session to
`initiate the interactive key exchange process. Because all the
`numbers chosen in the Interactive Diffie-Heilman key gen
`eration Scheme are very large, the computations are infea
`Sible to invert and the Secret cipher key cannot be computed
`
`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
`cate management enforced by a Self-certifying chip device.
`The development and proliferation of Sophisticated com
`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
`tronic eavesdropping or alteration. Cryptographic commu
`nications Systems preserve the privacy of these transmis
`Sions by preventing the monitoring by unauthorized parties
`of messages transmitted over an insecure channel. Crypto
`graphic communications Systems also ensure the integrity of
`these transmissions by preventing the alteration by unau
`thorized parties of information in messages transmitted over
`an insecure channel. The cryptographic communications
`Systems can further ensure the integrity and authenticity of
`the transmission by providing for recognizable, unforgeable
`and document-dependent digitized signatures that can pre
`vent denial by the Sender of his own message.
`Cryptographic Systems involve the encoding or encrypt
`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 and/or numbers is encoded numeri
`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
`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 the communication and
`decrypting by the receiver of the communication. Symmet
`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.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`SAMSUNG EX. 1037 - 28/53
`
`

`

`6,009,177
`
`15
`
`25
`
`3
`by an eavesdropper, thus preserving the privacy of the
`communication. Because the computations are infeasible to
`invert, each user knows that any communication received
`using this algorithm was not altered and could have been
`Sent only by the other user, thus preserving the integrity and
`authenticity of the communication. This interactive key
`eXchange method, however, requires the parties to interact in
`real time in order to create the cipher key and may not be
`useful for unsolicited communications or unfamiliar parties.
`In particular, the Interactive Diffie-Rellman key exchange
`Scheme does not work for Store-and-forward electronic-mail
`Style messaging or for long-term Storage of documents in an
`electronic data Storage System, because the recipient is not
`on-line to negotiate the Session key.
`A modified, non-interactive form of the Diffie-Hellman
`Scheme, known as Certified Diffie-Hellman, can be used
`when the communicating parties are not on-line together.
`The initial, certification step of the Certified Diffie-Hellman
`Session key generation Scheme is shown in FIG. 3. One user,
`the recipient-to-be, randomly chooses a Secret number 31
`(his private key) and then computes an intermediate number
`33 using two publicly-known numbers 32 and the secret
`number 31 chosen by that user. That user then sends proof
`of identification along with the intermediate number and the
`two public numbers, which numbers together form his
`public key 34, to a certifying authority that then issues a
`public key certificate 35 digitally signed 36 by the issuing
`certifying authority binding the user's identity to the user's
`Diffie-Hellman public key information 34. The public key
`34 publicized by that user remains the same until he decides
`to rekey and choose another private key 31. MeSSaging using
`the Certified Diffie-Hellman method is shown in FIG. 4. In
`order to transmit a message to that-user, a Sending user first
`obtains the receiving user's certificate 35 and verifies the
`certifying authority's Signature 36. The Sender next com
`35
`putes the Session key 42 for that communication Session
`using the recipient's intermediate number 33 (from the
`recipient's certificate) and the Sender's own Secret number
`41 (his private key), which he chooses at random. The
`Sender then encrypts a message 43 using the Session key 42
`and places his own intermediate number 40 unencrypted at
`the head of the communication. Upon receiving the
`communication, the recipient computes the Session key 42
`using the Sender's unencrypted intermediate number 40 and
`his own Secret number 31 (or private key), and then uses the
`Session key 42 to decrypt the message 43. AS with the
`Interactive Diffie-Hellman Scheme, the Session key gener
`ated in the Certified Diffie-Hellman scheme is then used by
`both parties to encrypt and decrypt communications during
`that Session over an otherwise insecure channel using a
`conventional symmetric algorithm, such as DES. The Cer
`tified Diffie-Hellman scheme, however, requires that a
`trusted entity or a certifying authority sign the receiving
`user's public key certificate So that a Sending user can trust
`that the information contained within is correct. In addition,
`the private key randomly chosen by the sender, with which
`he computes both the Session key and the intermediate
`number for that communication, must not be identical to the
`private key that is connected to the Sender's own public key
`certificate; in order to avoid others learning his permanent
`60
`private key numbers (corresponding to the public key num
`bers that have been certified), the sender should keep them
`distinct from any ephemeral private keys or intermediate
`numbers that are generated only for Specific messages.
`Another asymmetric key algorithm, named the RSA algo
`rithm after the inventors Rivest, Shamir and Adleman, is
`described in U.S. Pat. No. 4,405,829 (Rivest et al.), which is
`
`4
`hereby incorporated by reference, and involves the difficulty
`of factoring a number that is the product of two large prime
`numbers. As with the Interactive Diffie-Hellman Scheme, the
`RSA algorithm is relatively straightforward to compute but
`practically infeasible to invert. Thus, it is not feasible to
`derive the private key from the public key and, in this way,
`the privacy of the communication is preserved. Once a
`message is encrypted with the public key using the RSA
`algorithm, only the private key can decrypt it, and Vice
`versa. As with the Certified Diffie-Hellman Scheme, the RSA
`algorithm requires a trusted entity to certify and publicize
`the users public keys. In contrast to