4,658,093
`(11) Patent Number:
`115)
`United States Patent
`
` Hellman [45] Date of Patent: Apr. 14, 1987
`
`
`[54] SOFTWARE DISTRIBUTION SYSTEM
`
`[76]
`
`[56]
`
`Inventor: Martin E. Hellman, 730 Alvarado
`Ct., Stanford, Calif. 94305
`
`man IEEE Transaction on Information Theory, vol. 22
`#6, 11/76.
`“Multiuser Cryptographic Techniques”, by Diffie and
`Hellman AFIPS-Conference Proceedings, vol. 45, pp.
`109-112, 6/8/76.
`. No.: 512,68
`Primary Examiner—Salvatore Cangialosi
`No
`[21] Appl.
`5
`Assistant Examiner—Aaron J. Lewis
`[22] Filed:
`Jul. 11, 1983
`Attorney, Agent, or Firm—Flehr, Hohbach, Test,
`
`[S50]. Inte OU ccassccctecaccacains HO4L 9/00=Allbritton & Herbert
`
`[52] WSs Cae sccctsssnsiascoassasnse onseeneecsnsscecns 380/25;ae [57]
`ABSTRACT
`[58] Field of Search ............... 178/22.08, 22.11, 22.09;
`Software (programs, videogames, music, movies, etc.)
`358/86
`can be authorized for use a given number oftimes by a
`base unit after which the base unit (computer, video-
`~ oe Mion record playensviteoreoeroct or “ee
`References Cited
`e manufac-
`isk player) cannot use that software un
`turer sends an authorization for additional uses to the
`U.S. PATENT DOCUMENTS
`
`3,798,605 3/1974 Feistel ...........s+sse 178/22.08—user’s base unit. Authorizations may be sent via tele-
`4,200,770 4/1980 Hellman etal. .
`~ 178/22.11
`phoneline, mail, or whatever form of communicationis
`
`4,218,582
`8/1980 Hellman etal. .
`. 178/22.11
`most suited to the application. Authorizations cannot be
`
`4,264,782
`°4/1981 Konheim .......
`+ 178/22.08
`reused, for example by recording the telephone authori-
`
`tena TEASE: RIVESOF Ble ecseneeecrrores Vesa)
`zation signal and replayingit to the base unit. Similarly,
`424,414
`1/1984 Hellman et al.
`wee 178/22.11
`oes
`‘i
`,
`
`$446,519 5/1984 Thomas secsesscssssccssssecsoone 178/22.08
`authorizations can be made base unit specific, so that an
`
`4,458,315
`7/1984 Uchemick
`erocscccsscsessensese 178/22.08
`authorization for one base unit cannotbe transferred to
`
`4,465,901
`8/1984 Best .scsccsesssssesscsssesssneeesnnes 178/22.08
`another base unit. This invention also solves the “soft-
`4,567,512
`1/1986 Abraham veces. 358/86
`Ware piracy problem” and allows telephone sales of
`ftw
`additional benefits.
`OTHER PUBLICATIONS
`software as
`acieionar
`sens
`“New Directions in Cryptography”, by Diffie and Hell-
`10 Claims, 11 Drawing Figures
`
`ONE Way
`HASH
`
`
`
`
`
`womens
`MEMORY
`
`CRYP
`oe
`|_M_,| UPDATE
`feet} UNIT ma UNIT
`|
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheetl of4
`
`4,658,093
`
`AUTHORIZATION
`BILLING
`
`PUBLIC
`
`SER.NO.
`
`
`
`TABLE OF SER. NO'S
`TABLE OF
`
`
`AND SECRET KEYS
`SOFTWARE
`
`
`
`NAME
`
`
`
`SOFTWARE
`ONE WAY
`
`PACKAGE
`
`HASH
`
`FUNCTION
`
`UNIT
` SOFTWARE
`FOR LARGE
`
`CRYPTOGRAPHIC
`FUNCTION
`
`SOFTWARE
`
`MODIFIED
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet20f4
`
`4,658,093
`
`O (64 BITS)
`
`168 BITS
`
`OF KEY
`
`H (64 BITS)
`
`FIG_GA
`
`26
`
`‘«! MODIFIED
`
`SK
`
`
`
`TEMPORARY
`
`MEMORY SER. NO.
`
`PERM. MEM. NR
`
`SOFTWARE NAME
`
`
`27~.|SOFTWARE NAME SER. NO.
`USER
`IBILLING INFO
`BILLING INFO
`
`FIG_S
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet3 of4
`
`4,658,093
`
`
`SOFTWARE
`
`
`
`ONE WAY
`
`MEMORY
`HASH
`
` PERM.
`
`
`NON
`VOLATILE
`MEMORY
`
`
`CRYPTO
`CHECK
`UNIT
`
`CRYPTOGRAPHIC
`
`FUNCTION
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet4of4
`
`4,658,093
`
`SOFTWARE
`
`42
`
`eeway
`
`
`
`
`
`
`NON
`VOLITILE
`
`UPDATE
`UNIT
`MEMORY
`
`
`
`
`FIG_8
`
`PUBLIC KEY
`CRYPTO
`
`SYSTEM
`
`
`
` PUBLIC KEY
`
`CRYPTO
`SYSTEM
` A
`
`46
`
`H,R,N
`
`44
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`

`

`1
`
`SOFTWARE DISTRIBUTION SYSTEM
`
`4,658,093
`
`The invention relates to a software distribution sys-
`tem and moreparticularly to a secure software distribu-
`tion system in which the numberofuses of software can
`be controlled.
`Control of software is a major problem in the record,
`movie (videotape and disk), computer, and videogame
`industries. In the record industry, illegal home and com-
`mercial taping of recordsis depriving artists, recording
`studios, and manufacturers of significant income which
`is rightfully due them. A similar problem exists with
`illegal taping of movies in the videotape and videodisk
`industries. So called “software piracy” is a major prob-
`lem in the computer and videogameindustry.
`Even if adequate control of software piracy were
`possible with prior art, so that software sold to one
`customercould not be copied and used by another cus-
`tomer, it would still be desirable to sell software on a
`per use basis. Such a system would allow a customer to
`sample software at low cost and only buy more uses of
`software which he found interesting or useful.
`Current methods of software control address primar-
`ily the first issue (piracy or copy protection), and even
`there, do not provide adequate protection against a
`dedicated adversary.
`Software copy protection does not currenty exist in
`the record industry.
`Videotaped movies are sometimes copy protected by
`degrading the horizontal or vertical synchronizing sig-
`nals slightly. A videorecorder requires a cleaner syn-
`chronizing signal than a TV receiver, so that the video-
`taped movie cannot be copied by another videore-
`corder,but will be displayed properly on a TV receiver.
`But, the videotape can still be copied by putting a spe-
`cial device between the two videorecorders which
`cleans up the synchronizing signal.
`Copyprotection has received greater attention in the
`computer software industry. One approach is to use a
`non standard disk format for recording the program of
`real interest. Standard copying programs can only read
`or write data in standard format, making copyingofthis
`program impossible. A short, machine language pro-
`gram,
`in standard format, is included as an auxiliary
`program on the disk. This machine language program
`tells the computer howto read the non standard format
`in which the program is recorded. While this approach
`prevents standard copy programs from copying the
`disk, an adversary can always makea bit for bit copy of
`the disk which will be executable by the computer.
`Another approach to copy protecting computer pro-
`grams is to put a small pin hole or other defect at a
`particular spot on the disk. The program being sold
`avoids using this ruined portion of the disk, but checks
`to make sure that that portion of the disk is, in fact,
`ruined.If it is ruined, the program continues its normal
`execution. If it is not ruined, then the program stops
`execution. Even a bit for bit copy of the program onto
`a new disk will not execute properly because there is
`hidden “information” on the disk (which part is ruined)
`which must be copied if the program is to execute prop-
`erly.
`An adversary can overcomethis copy protection by
`one of two methods. First, he can determine which
`portion of the disk is checked and makesureit is ruined
`on the copy. Or, he can delete the part of the program
`which checks for the ruined portion of the disk. This
`
`20
`
`25
`
`30
`
`40
`
`45
`
`50
`
`60
`
`65
`
`2
`produces a slightly shorter program which does every-
`thing ofvalue to the user that the original program did,
`but this new version of the program can be copied with-
`out any special effort and used on all other base units
`without further modification to the program or the
`other base unit.
`The second problem (pay per use or allowing a cus-
`tomer to preview software before purchasing it) is a
`moredifficult one. It is remotely related to the practice,
`in the photographic industry, of giving a customer
`“proofs” of his pictures. The proofs are of poor quality
`or fade with time, thus allowing the customer to pre-
`view his purchase.
`At least one software manufacturer uses a related
`approach to software sales. The manufacturer provides
`each customer for its program with two versions: the
`regular version is in a sealed enevelope, and a “‘de-
`graded”version, which only allow up to 30 records per
`file. Within a 30 day trial period, the manufactureral-
`lows the customer to return the regular version in its
`sealed envelope for a refund. This way, the customer
`can experiment with the degraded version to determine
`if he wants the full package.
`However, there is no copy protection, so that one
`dishonest customer can make as may copies as he wants
`of the regular version and give or sell them to acquaint-
`ances with similar base units (computers). These ac-
`quaintances can in turn give orsell generation copies to
`their acquaintances, etc.
`It would also be desirble for the customer to experi-
`ment with the full version of the program because cer-
`tain characteristics of the program can ony be deter-
`mined with large data bases with more than 30 records.
`Another method for allowing users to preview soft-
`ware is a system called “‘crypt lock”. As an example, a
`customer might buy a degraded version of a data base
`management program for a small sum which is limited
`to a smal] number ofrecordsperfile.
`If, after using the degraded software, the buyer de-
`cides he wants to buy the complete program hecalls the
`manufacturer, gives the serial numberof his disk and a
`credit card number, receives an authorization code
`from the manufacturer, and uses this code to “unlock”
`the full power of the software. The full version of the
`-program is really contained on the “degraded”disk, but
`parts ofit are not accessible until certain instructions are
`changed. This change is made once the right authoriza-
`tion code is entered.
`This approach suffers from the same drawbacks as
`the approach described immediately beforehand: Once
`the program has been “unlocked” it can be copied at
`will and the customer can only preview a degraded
`version of the program.
`The prior art in cryptography which is relevant to
`this application is described in Diffie and Hellman’s
`tutorial paper “Privacy and Authentication: An Intro-
`duction to Cryptography”, Proceedings of the IEEE,
`November 1979. The prior art describes one-way func-
`tions and cryptographic functions of the type needed as
`components of the present software control system.
`For completeness,three prior art cryptographic func-
`tions required to carry out the present invention are
`described: conventional cryptographic functions or
`systems, One-way functions, and public key cryptosys-
`tems.
`A conventional cryptographic function or system can
`be described by an enciphering and a deciphering func-
`tion. The enciphering function E(K,P)=C operates on
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`

`

`4,658,093
`
`25
`
`35
`
`40
`
`45
`
`20
`
`3
`4
`a plaintext (unscrambled message) P with a key K to
`The recipient of a message M' whichis purported to
`produce ciphertext (scrambled message) C. The deci-
`be signed by the signature SIG’ must verify the signa-
`phering function D(K,C)=P operates on the ciphertext
`ture. To verify that SIG’ is the correct signature for
`C thus produced with key K to reproduce the plaintext
`message M’, the recipient needs only the public key and
`P. Both E(K,P) and D(K,C)are easily implemented and
`not the secret key. Otherwise, he would be able to sign
`easily computed.
`messages as well as authenticate them.
`Such a conventional cryptographic system implicitly
`The recipient operates on the received signature SIG’
`defines a third function T(P,C)=K which computes K
`with PK to obtian H'=PK(SIG’). Therecipient also
`from knowledge of P and C. T(P,C) is the function a
`operates on M’ with the one-way hash function H to
`cryptanalyst must implement and compute when he has
`obtain a check value C=H(M’). If and only if H’=C
`some matched plaintext and ciphertext. T(P,C) must
`does he acceptthe signature as valid. (Since PK and SK
`therefore be difficult to compute—ideally taking mil-
`effect inverse operations, if the received message M’
`lions of years to compute with any imaginablecircuitry.
`equals the original message M andif the signature SIG’
`An example of such a conventional cryptographic
`was properly generated as SK H(M) then H’=PK
`system is the Data Encryption Standard or DES,de-
`SIG'=H(M)andCalso will equal H(M).)
`scribed in Federal Information Processing Standard
`Herein, the term “crytpographic function” is used to
`Publication (FIPS PUB) 46 and available from the Na-
`mean a function that can be implemented either as a
`tional Technical Information Service, 5285 Port Royal
`conventional
`cryptographic
`function, E(K,P) or
`Road, Sprngfield, VA 22161.
`D(K,C), or as a public key cryptographic function,
`A one-way function is a function which is easy to
`PK(SIG) or SK(H(M)).
`compute in the forward direction, but hard to compute
`Accordingly, it is an objective of the invention to
`in the reverse direction. Thatis, if Y=f(X) is a one-way
`allow a software manufacturerto control the numberof
`function then given any X it is easy to compute the
`times a piece of software is used by a customer, in a
`corresponding Y, taking typically a fraction of a second
`mannersuch that the authorization cannot be recorded
`on a small computer. But given any Y it is extremely
`and reused, and such that the authorization is not trans-
`difficult
`to find the corresponding X, ideally taking
`ferable to another base unit.
`millions of years on the most powerful computer imag-
`Another objective of the invention is to allow the use
`inable.
`of software to be sold over the telephone or other simi-
`A method for deriving a one-way function from a
`lar communication channels, but in a way which pre-
`conventional cryptographic system is described in sec-
`vents recording of the software or authorization signal
`tion V of Diffie and Hellman’s paper, “New Directions
`sent over the channel from being reused on that custom-
`in Cryptography”, IEEE Transactions on Cryptogra-
`er’s or another customer’s base unit.
`phy, vol. IT-22, November 1976 (see, especially FIG. 3
`Another objective of the invention is to prevent
`therein): A conventional cryptographic enciphering
`“software piracy.” That is the illegal use of software on
`function E(K,P) is used to obtain Y as Y=E(X,PO),
`a base unit which has not paid a license fee.
`where PO is some fixed, publicly known plaintext
`An illustrated embodiment of the present invention
`value. That is, the input X to the one-way function is
`describes a method and apparatus in which use of the
`used as the key, PO is used as the plaintext, and the
`software can be authorized for a particular base unit a
`output Y from the one-way function is taken as the
`specific number of times. The illustrated embodiment
`computed ciphertext. Computing Y from X merely
`differs from prior approaches to software controlin that
`involves an enciphermentandis therefore a simple com-
`no modification to the software will allow the software
`putation. But computing X from Y involves cryptanaly-
`to be used on all other base units, and in that the soft-
`sis because X=T(PO,Y) and is therefore difficult to
`ware can be used only a specific number of times even
`compute.
`on the licensed base unit.
`A one-way function can be expansionary (i.e., Y is
`In the present invention, a manufacturer of base units
`longer than X), compressive, or neither, depending on
`and software generates a random key andstores it in a
`the relative sizes of the ciphertext (Y) and key (X). For
`base unit whichis sold to a user. When wishing to use a
`purposes of this invention, we are primarily concerned
`certain software package, the user’s base unit generates
`with one-way compressive functions, where X is much
`a random number and communicates it to the manufac-
`longer than Y. Typical values herein will be a 100,000
`turer of the software. The software manufacturer gener-
`bit length for X and a 100 bit length for Y. A method for
`ates an authenticator which is a cryptographic function
`generating such an extremely compressive one-way
`of the base unit’s key, the software, the numberof times
`function is described in the patent.
`use of the software is authorized, and the random num-
`Compressive functions are also called “hash func-
`tions” and a one-way compressive functionis therefore
`ber generated by the base unit. The authenticator is
`communicated to the user’s base unit. The user’s base
`called a one-way hash function.
`unit then uses the same cryptogaphic function to gener-
`The third and last cryptographic entity we shall de-
`ate a check value of the key, the software, the number
`scribe from the priorart is a public key cryptosystem. A
`of times use is authorized, and the random number
`public key cryptosystem differs from a conventional
`cryptographic system in that two different keys are
`which the base unit generated. If the check value and
`the authenticator agree, the base unit accepis the au-
`used. One of these keysis a public key PK and the other
`thenticator as valid and increments the number of times
`is a secret key SK.
`use of that software is authorized.
`For purposes of this invention, the public key cryp-
`tosystem is used in digital signature mode so that the
`Additional objects and features of the present inven-
`secret key is used first to obtain the digital signature
`tion will appear from the description that follows
`SIG from the message M bythe operation SIG=SK H
`wherein the preferred embodiments have been set forth
`(M), where H is a one-way hash function of the mes-
`in detail in conjunction with the accompanying draw-
`sage.
`ings in which:
`
`55
`
`65
`
`PMCExhibit 2083
`Apple v. PM
`IPR2016-0075
`Page
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`

`

`4,658,093
`
`30
`
`35
`
`45
`
`20
`
`6
`5
`TIONis a credit car numberor similar meansforbilling
`FIG. 1 is a block diagram of a pay per use software
`the user for use of the software.
`control system.
`Authorization and billing unit 13 receives the signal
`FIG. 2 is a block diagram of an authorization and
`representing the user originated request for software
`billing unit for generating an authorization for addi-
`use, generates a signal representing an authorizaiton A
`tional software use in the pay per use software control
`for that particular base unit 12 to use the software pack-
`system of FIG.1.
`age 17 an additional N times, and communicates the
`FIG. 3 is a block diagram of a one-way hash function
`signal representing authorization A to base unit 12.
`for performing one-way hashing operations in the au-
`Base unit 12 receives the signal representing authori-
`thorization and billing unit of FIG. 2, in the base unit
`zation A over insecure channel 11. As will be explained
`during verification of authorization of FIG. 6, and in
`shortly in FIG. 6, base unit 12 then checks whether the
`the base unit during use of software of FIG.8.
`authorization is from the software manufacturerand, if
`FIG.3Ais a block diagram of a DES modified for the
`the authorization is correct, base unit 12 updates its
`large key used in FIG. 3.
`memory to allow N additional uses of software package
`FIG.4 is a block diagram of a cryptographic function
`17.
`used for generating authorizations in the authorization
`FIG. 2 depicts an implementation of authorization
`and billing unit of FIG. 2 and in the cyrptographic
`and billing unit 13. Authorization and billing unit 13
`checking unit of FIG.7.
`contains a memory 18 having a table of serial numbers
`FIG.5 is a block diagram ofa base unit during gener-
`and secret keys which allows authorization andbilling
`ation of a request for additional software uses in the pay
`unit 13 to determine a base unit’s secret key, SK, from
`per use software control system of FIG. 1.
`knowledge of the base unit’s public serial number. Au-
`FIG.6 is a block diagram of a base unit during verif-
`thorization and billing unit 13 also contains in another
`ciation of authorization of additional software uses in a
`portion of the memory orin an additional memory 19 a
`pay per use software control system of FIG.1.
`table of software whichallows authorization andbilling
`FIG. 7 is a block diagram of a cryptographic check-
`unit 13 to determine the complete contents of software
`ing unit in a base unit during verification of authoriza-
`package 17 from knowledgeof the much smaller infor-
`tion of additional software uses of FIG.6.
`mation SOFTWARE NAME.Thesoftware package
`FIG.8 is a block diagram ofa base unit during use of
`21 produced at the authorization and billing unit 13 is an
`software in a pay per use software contro] system of
`exact replica of software package 17 whichis available
`FIG.1.
`at base unit 12.
`FIG. 9 is a block diagram ofan alternative implemen-
`Software package 21 is applied as an input signal to
`tation of a cryptographic function used for generating
`one-wayhash function generator 22 to produce an out-
`authorizations in the authorization and billing unit of
`put signal H. This outputsignal H is used as an “abbre-
`FIG.2.
`viation” or name for describing the software package
`FIG. 10 is a block diagram of an alternative imple-
`21. To prevent an opponent from modifying one soft-
`mentation of a cryptographic checking unit in a base
`ware package so that it has the same abbreviation or
`unit during verification of authorization of additional
`name as another software package, one-way hash func-
`software uses of FIG.6.
`tion generator 22 has the following property: Its output
`Referring to FIG. 1, a pay per use software control
`signal, H, is easily commputed from its input signal,
`system is shown in which communication takes place
`software package21, but given an H valueitis difficult,
`over an insecure communication channel 11, for exam-
`taking perhaps millions of years, to compute any other
`ple a telephoneline. Communication is effected over the
`software package wich produces this same H value.
`insecure channel 11 between the base unit 12 and the
`This property is necessary because any two software
`authorization and billing unit 13 using transmitter-
`packages with the same H value are considered equiva-
`lent and therefore have the same authorization A. An
`receiver units 14 and 16, which may be modemssuch as
`Bell 201 modems. Transmit-receive units 14 and 16
`authorization to use the cheaper of two software pack-
`could be humans conversing over a telephoneline. The
`ages with the same H value could also be used as an
`human at the transmit-receive unit 16 would then type
`authorization to use the more expensive of the two. As
`the voice information into a keyboard for entry in the
`with any has function, the one-way has function genera-
`unit 13.
`tor 22 has a much shorter output, perhaps 100 bits, than
`The user at base unit 12 obtains software package 17
`its input, typically 10,000 to 1,000,000 bits in this inven-
`by purchasing it at a store, over telephoneline, or in
`tion. This allows H to be stored more economically than
`some similar manner. The cost for software package 17
`the software package 17 in the base unit’s memory.
`can be set low because additional revenue will be ob-
`Storage of H orof the complete software package 17is
`tained by the software manufacturer when issuing addi-
`desirable to increase the security of the system because
`tional authorizations for use of the software package.
`storage of only SOFTWARE NAME would allow a
`dishonest user to rename software packages and pay for
`Base unit 12 generates and communicates to authori-
`zation and billing unit 13 a signal representing a user
`uses of less expensive packages when really using more
`expensive ones. A method for implementing one-way
`originated request for software use. This request con-
`hash function generator 22 is depicted in FIG. 3, which
`sists of several parts SOFTWARE NAME, SERIAL
`will be explained shortly.
`NUMBER, N, R, and BILLING INFORMATION.
`Thesignal H whichis the output of the one-way hash
`SOFTWARE NAME isthe nameofthe software pack-
`function generator 22 is applied as one of four input
`age to be used. SERIAL NUMBERisaserial number,
`signals to cryptographic function generator 23 to pro-
`identification number, user name or similar identifier
`65
`duce a signal representing authorization A which is
`unique to base unit 12. N is the number of additional
`communicated to base unit 12 over channel 11. The
`uses of software requested. R is a random number,
`other three input signals to generator 23 are R and N
`counter value, or other non-repeating number gener-
`which were received over channel 11 from base unit 12
`ated by the base unit 12, And BILLING INFORMA-
`
`50
`
`55
`
`60
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`

`

`4,658,093
`
`7
`and SK whichis obtained from authorization andbilling
`unit’s table of serial numbers and secret keys.
`Generator 23 has the property that new authoriza-
`tions cannot be inferred from old authorizations. More
`precisely, if cryptographic function generator 23 gener-
`ates a publicly known function and if an opponent has
`many authorizations 'A(i) which go with different se-
`cret keys ‘SK(i), hash values 'H(i), random numbers
`‘RG@), and numbers ‘N(i), so long as the secret keys
`"SK(i) are kept secret, it is difficult for an opponent to
`compute a new authorization A’ which goes with any
`SK’, N’, R', H’ for which an authorization has not al-
`ready been given. Methods and apparatus for imple-
`menting cryptographic functions with this property are
`depicted in FIG. 4 and FIG. 9, which will be explained
`shortly.
`FIG. 3 depicts an implementation of the one-way
`hash function generator 22. As explained by W.Diffie
`and M. Hellman in section V of their paper “New Di-
`rections in Cryptography” (IEEE Transactions on In-
`formation Theory, November 1976) a one-way function
`from a value X to a value Y can be generated from a
`conventional cryptographic system by fixing the plain-
`text at some value, for exampleall binary 0's, applying
`X to the key port, and taking Y as the ciphertext com-
`puted from this plaintext and key. Computing Y from X
`is computationally simple because only an encryptionis
`involved. But computing X from Y is equivalent to
`cryptanalysis, and is thus difficult if the cryptographic
`system is secure.
`In order to make the one-way hash function genera-
`tor 22 in this manner, one needs a cryptographic system
`with a much larger key, typically 10,000 to 1,000,000
`bits, than ciphertext, typically 100 bits in this invention.
`The Data Encryption Standard (DES), described in
`Federal Information Processing Standard 46, is typical
`of a conventional cryptographic system. While the
`DEShas a shorter key (56 bits) than ciphertext (64 bits),
`DES can easily be changed to a DES modified for a
`larger key which then has the desired property.
`FIG. 3A depicts the simplest way to implement a
`DES modified for a large key. In this figure, the plain-
`text P is enciphered four times with the normal DESto
`produce a ciphertext C. te four keys used are K1, K2,
`K3 and K1, so that one key, K1, is repeated. The three
`independent keys used have
`a
`total
`length of
`3X 56= 168 bits, but the plaintext and ciphertext lengths
`are unchangedat 64 bits. Hence the modified DES has
`a key length of 168 bits and a ciphertext of 64 bits.
`K1 is repeated to strengthen security. Ideally, each
`key would be repeated several times. The same basic
`DES circuitry can be used iteratively, rather than repli-
`cated, so that the cost of the circuitry shownin FIG. 3A
`need not be muchgreater than that for a basic DES.
`An alternative, and usually more efficient way of
`producing a DES modified for a large key would be to
`increase the number ofiterations or rounds in DES.
`Since 48 bits of key comeinto play in each DESitera-
`tion, a 1,000 iteration DES would use 48,000 bits of key
`yetstill have only a 64 bit ciphertext. For cryptographic
`security it is necessary that each bit of key be used
`several times, so at least a 3,000 round DES would be
`desirable for compressing 48,000 bits of software pack-
`age into 64 bits of hash value H. the ciphertext size of
`DESis also easily increased if, for example, a 100 bit
`hash value H is needed instead of a 64 bit value.
`While DES is used here for illustative purposes,
`many other methods and apparatus for generating a
`
`20
`
`25
`
`35
`
`45
`
`55
`
`60
`
`65
`
`8
`one-wayhash function are knownto exist. DES encryp-
`tion is very slow on a general purpose signal processor
`such as a microprocessor. Thus, if the signal processing
`in the base unit 12 or authorization andbilling unit 13is
`done primarily with a microprocessor then a one-way
`hash function generator 22 which is computed more
`rapidly on a microprocessor would be desirable. Since it
`is mostly DES’s mixing operation, a permutation or
`tranposition on 32 bits, which makes DES slow on a
`microprocessor, replacement of the mixing operation
`by one more suited to a microprocessor would be desir-
`able.
`One implemenation of the cryptographic function
`generator 23 of FIG. 2 would also involve a one-way
`hash function as depicted in FIG. 3, except H, R and N
`together, instead of the software package, would be the
`input to the one-way hash function and the authoriza-
`tion A, instead of H, would be the output. This imple-
`mentation would have the required property that new
`authorizations could not be predicted from the property
`that given an output valve,
`it is difficult to find the
`corresponding input value to the one-way function.
`FIG. 4 depicts an alternative implementation of the
`cryptographic function generator 23. A modified DES
`26 would have the secret key SK as inputto its key port
`and H, R and N would bethe inputto theplaintext port.
`The authorization A would be obtained as the output of
`the ciphertext port. The DES would have to be modi-
`fied,
`in the manner described above, to have its key
`length equal to the length of SK.
`length
`In addition,
`the modified DES’s plaintext
`would have to be equal to the total length of H, R and
`N andits ciphertext length would have to be equal to
`the length of A. Usually the plaintext and ciphertext are
`the same length, but for our purposes any portion of the
`ciphertext could serve as A. So if the length of A is
`shorter than the combined lengths of H, R and N then
`the modified DES 26 could have its plaintext and ci-
`phertext length equal to the combined lengths of H, R
`and N and the ciphertext could be truncated to generate
`A. Similarly, if the lengths of A is greater than the
`combined lengths of H, R and N then the plaintext and
`ciphertext length of modified DES 26 could be equal to
`the length of A and the plaintext could be padded out
`with binary 0’s to make the proper size input.
`This alternative implemenation would also inherently
`have the property that new authorizations could not be
`predicted from old authorizations because, in a conven-
`tional cryptographic system, given past plaintext-
`ciphertext pairs, it must be difficult to determine the
`plaintext which goes with a new ciphertext.
`For ease of understanding, the implementation of the
`base unit 12 is shown in three figures, corresponding to
`its three phases of operation: when a user generates a
`request for use of a software package; when the base
`unit verifies the validity of the received authorization;
`and when a user later uses the software package. Only
`those elements of the base unit 12 which are needed in
`a particular phase are shown in the corresponding fig-
`ure.
`
`FIG. 5 depicts the operation of the base unit 12 dur-
`ing generation of a request for software use. A user 27
`communicates
`signals
`representing SOFTWARE
`NAME, BILLING INFORMATIONand N,the num-
`ber of additional uses desired, to the base unit 12, for
`example by typing them into a keyboard whichis part
`of base unit. Base unit 12 stores these values in a tempo-
`rary memory 28, for example a RAM,so that they can
`
`PMC Exhibit 2083
`
`Apple v. PM
`IPR2016-00753
`Page 9
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00753
`Page 9
`
`

`

`4,658,093
`
`25
`
`45
`
`50
`
`20
`
`10
`9
`software being used. Update unit 36 applies to interrog-
`be used later whenverifyingthe validity of the received
`authorization for additional software use. A random
`atory signal representing H to a non-volatile memory
`37, for example an EEPROM or a CMOS memory with
`number generator 29 (e.g. a noisy operational amplifier
`battery backup. The non-volatile memory 37 applies a
`with hard quantization) generates a signal representing
`signal to the update unit 36, said signal representing M,
`a random number R whichis also stored in temporary
`the numberof authorized uses of the software package
`memory 28 for later use during verification of the re-
`ceived authorization. The base unit’s serial numberis
`with hash value H which still remain unused prior to
`this new authorization. The update unit 36 adds M and
`stored in a permanent memory 3