United States Patent
`
`[19]
`
`[11] Patent Number:
`
`4,653,093
`
`[45] Date of Patent:
`Hellman
`Apr. 14, 1987
`
`man IEEE Transaction on Information Theory, vol. 22
`#6, ll/76.
`“Multiuser Cryptographic Techniques", by Diffie and
`Hellman AFIPS-Conference Proceedings, vol. 45, pp.
`l09~—l12, 6/B/76.
`
`Prr'mary Examiner--Salvatore Cangialosi
`Assistant Exam:'ner'—Aaron J. Lewis
`Attorney. Agent, or F1'nn-—F1ehr, Hohbach. Test.
`Albritton 8: Herbert
`
`ABSTRACT
`[57]
`Software (programs, vicleogames, music, movies. etc.)
`can be authorized for use a given number of times by a
`base unit after which the base unit (computer, video-
`game base unit, record player. videorecorder or video-
`disk player) cannot use that software until the manufac-
`turer sends an authorization for additional uses to the
`user’s base unit. Authorizations may be sent via tele-
`phone line. mail. or whatever form of communication is
`most suited to the application. Authorizations cannot be
`reused, for example by recording the telephone authori-
`zation signal and replaying it to the base unit. Similarly,
`authorizations can be made base unit specific, so that an
`authorization for one base unit cannot be transferred to
`another base unit. This invention also solves the “soft-
`ware piracy problem" and allows telephone sales of
`software as additional benefits.
`
`[54] SOFTWARE DISTRIBUTION SYSTEM
`
`[76]
`
`Inventor: Martin E. Hellman, 730 Alvarado
`Ct., Stanford, Calif. 94305
`
`[21] App]. No.: 512,635
`
`[22] Filed:
`
`Jul. 11, 1933
`
`[51]
`Int. cu ............................................. .. H04-L 9/00
`
`[52] U.S. Cl. .................... .. .
`.... .. 389/25; 380/41;
`380/30
`
`[58] Field of Search ............... 178/22.08, 22.11, 22.09;
`353/86
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`178/22.08
`.. 178/22.1!
`
`..... 178/22.1]
`
`173/22.08
`358/B6
`
`
`
`3.798.605 3/I974 Feistel
`4.200.770 4/I980 Hellman et al. .
`4.218.532
`8/1980 Hellman et al. .
`4,264,782 4/i931 Konhcirn ....... ..
`4,405,829 9/ 1983 Rivest et al.
`....
`4,424,414
`1/1984 Hellman et al.
`4,446,519 5/1984 Thomas
`4.453.315 7/ I984 Uchenick
`4.465.901 B/1934 Best
`4.567.512
`1/1986 Abraham
`
`OTHER PUBLICATIONS
`
`PMC Exhibit 2083
`
`Apple v. PMC
`|PR2016-00755
`
`Page 1
`
`
`
`“New Directions in Cryptography", by Diffie and Hell-
`
`10 Claims, 11 Drawing Figures
`
`MEMORY
`
`NON
`VOLATILE
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 1
`
`

`
`U. S. Patent Apr. 14,1987
`
`Sheetl of-4
`
`4,658,093
`
`AUTHORIZATION
`BILLING
`UNIT
`
`TABLE or-' sea. NO'S
`nun secnsr KEYS
`
`SKN R
`
`H
`
`SOFTWARE
`NAME
`
`ONE WAY
`
`HASH
`
`FUNCTION
`
`F/6.2
`
`_:p|
`
`DES
`
`SOFTWARE
`
`MODIFIED
`K FOR LARGE
`
`PMC Exhibit 2083
`
`Apple v. PMC
`|PR2016-00755
`
`
`
`Page 2
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 2
`
`

`
`U. S. Patent Apr. 14,1987
`
`Sheet2 of4
`
`4,658,093
`
`168 BITS
`
`OF KEY
`
`26
`
`
`
`TEMPORARY
`MEMORY
`
`
`
` SER. NO.
`
`
`
`
`
`PMC Exhibit 2083
`
`Apple v. PMC
`|PR2016-00755
`
`Page 3
`
`
`
`N R
`SOFTWARE NAME
`
`SER. NO.
`BILLING INFO
`
`PERM. MEM.
`
`N
`
`
`
`27
`USER
`
`. SOFTWARE NAME
`BILLING INFO
`
`L F/G_5
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 3
`
`

`
`U. S. Patent Apr. 14, 1987
`
`Sheet3 of4
`
`4,658,093
`
`SOFTWARE
`
`
`
`VOLATI LE
`
`MEMORY
`
`NON
`
`33
`
`CRYPTOGRAPHIC
`FUNCTION
`
`
`
`39
`
`COMPJIRATOR
`
`N,H 8:
`TO 36
`SOFTWARE NAME
`
`PMC Exhibit 2083
`
`Apple v. PMC
`|PR2016-00755
`
`Page 4
`
`
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 4
`
`

`
`U. S. Patent Apr. 14, 1937
`
`Sheet4 of4
`
`4,658,093
`
`SOFTWARE
`
`
`
`‘*2 33
`
`
`-
`ONE wA4r
`
`
`
`
`E1 UPDME
`1!: UN"
`uj
`
`F/G_8
`
`H,R,N
`
`SK
`
`PUBLIC KEY
`
`CRYPTO
`SYSTEM
`
`43
`
`F/6.9
`
`H‘, R‘. N‘
`
`
`
`
`PUBLIC KEY
`
`CRYPTO
`
`SYSTEM
`
`N,H
` COMPARATOR
`
`TO 36
`
`A
`
`44
`
`46
`
`H,R,N
`
`PMC Exhibit 2083
`
`Apple v. PMC
`|PR2016-00755
`
`Page 5
`
`
`
`. F/6‘_/'0
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 5
`
`

`
`1
`
`SOFTWARE DISTRIBUTION SYSTEM
`
`4,658,093
`
`The invention relates to a software distribution sys-
`tem and more particularly to a secure software distribu-
`tion system in which the number of uses 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 records is 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 videogame industry.
`Even if adequate control of software piracy were
`possible with prior art, so that software sold to one
`customer could 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 videota-
`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.
`Copy protection 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 copying of this
`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 how to 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 make a 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 mined 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 overcome this copy protection by
`one of two methods. First, he can determine which
`portion of the disk is checked and make sure it is ruined
`on the copy. Or, he can delete the part of the program
`which checks for the ruined portion of the disk. This
`
`ll}
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`2
`produces a slightly shorter program which does every-
`thing of value 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
`more difficult 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 manufacturer al-
`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 or sell 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 small number of records per file.
`If, after using the degraded software, the buyer de-
`cides he wants to buy the complete program he calls the
`manufacturer, gives the serial number of 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 of it 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 Dilfie and Hellmaifs
`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 ciphering and a deciphering func-
`tion. The enciphering function E(K,P)=C operates on
`
`PMC Exhibit 2083
`
`Apple v. PMC
`
`|PR2016-00755
` Page 6
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 6
`
`

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

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

`
`4,658,093
`
`50
`
`55
`
`8
`7
`one-way hash function are known to exist. DES encryp-
`and SK which is obtained from authorization and billing
`unit’s table of serial numbers and secret keys.
`-tion is very slow on a general purpose signal processor
`such as a microprocessor. Thus, if the signal processing
`Generator 2.3 has the property that new authoriza-
`tions cannot be inferred from old authorizations. More
`in the base unit 12 or authorization and billing unit 13 is
`5 clone primarily with a microprocessor then a one-way
`precisely, if cryptographic function generator 23 gener-
`hash function generator 22 which is computed more
`ates a publicly known function and if an opponent has
`rapidly on a microprocessor would be desirable. Since it
`many authorizations 'A[i) which go with different se-
`is mostly DES's mixing operation, a permutation or
`cret keys ’SK(i), hash values 'H(i), random numbers
`tranposition on 32 bits, which makes DES slow on a
`’R(i), and numbers 'N(i), so long as the secret keys
`'SlC(i) are kept secret, it is difficult for an opponent to lo microprocessor, replacement of the mixing operation
`compute a new authorization A’ which goes with any
`by one more suited to a microprocessor would be desir-
`SI{', N’, R’, H’ for which an authorization has not al-
`able.
`ready been given. Methods and apparatus for itnple-
`One itnplernenation of the cryptographic function
`menting cryptographic functions with this property are
`generator 23 of FIG. 2 would also involve a one-way
`depicted in FIG. 4 and FIG. 9, which will be explained 15 hash function as depicted in FIG. 3, except H, R and N
`shortly.
`together, instead of the software package, would be the
`FIG. 3 depicts an implementation of the one-way
`input to the one-way hash function and the authoriza-
`hash function generator 22. As explained by W. Diffie
`tion A, instead of H, would be the output. This imple-
`and M. Hellman in section V of their paper “New Di-
`mcntation would have the required property that new
`rections in Cryptography" (IEEE Transactions on In- 20 authorizations could not be predicted from the property
`formation Theory, November 19':-'6)aone-way function
`that given an output valve,
`it is difficult to find the
`from a value X to a value Y can be generated from a
`corresponding input value to the one-way function.
`conventional cryptographic system by fixing the plain-
`FIG. 4 depicts an alternative implementation of the
`text at some value, for example all binary 0’s, applying
`cryptographic function generator 23. A modified DES
`X to the key port, and taking Y as the ciphertext com- 25 26 would have the secret key SK as input to its key port
`puted from this piaintext and key. Computing Y from X
`and H, R and N would be the input to the plaintext port.
`is computationally simple because only an encryption is
`The authorization A would be obtained as the output of
`involved. But computing X from Y is equivalent to
`the ciphertext port. The DES would have to be modi-
`cryptanalysis, and is thus difficult if the cryptographic
`fled,
`in the manner described above, to have its key
`system is secure.
`30 length equal to the length of SK.
`length
`In order to make the one-way hash function genera-
`In addition,
`the modified DES's plaintext
`tor 22 in this manner, one needs a cryptographic system
`would have to be equal to the total length of H, R and
`with a much larger key, typically 10,000 to 1,000,000
`N and its ciphertext length would have to be equal to
`bits, than ciphertext, typically 100 bits in this invention.
`the length of A. Usually the plaintext and ciphertext are
`The Data Encryption Standard (DES), described in 35 the same length, but for our purposes any portion of the
`Federal Information Processing Standard 46, is typical
`ciphertext could serve as A. So if the length of A is
`of a conventional cryptographic system. While the
`shorter than the combined lengths of H, R and N then
`DES has a shorter key (56 bits) than ciphertext (64 bits),
`the modified DES 26 could have its plaintext and ci-
`DES can easily be changed to a DES modified for a
`phertext length equal to the combined lengths of H, R
`larger key which then has the desired property.
`40 and N and the ciphertext could be truncated to generate
`FIG. 3A depicts the simplest way to implement a
`A. Similarly, if the lengths of A is greater than the
`DES modified for a large key. In this figure, the plain-
`combined lengths of H, R and N then the plaintext and
`text P is enciphered four times with the normal DES to
`ciphertext length of modified DES 26 could be equal to
`produce a ciphertcxt C. re four keys used are K1, K2,
`the length of A and the plaintext could be padded out
`K3 and K1, so that one key, K1, is repeated. The three 45 with binary 0'5 to make the proper size input.
`independent keys used have
`a
`total
`length of
`This alternative implemenation would also inherently
`have the property that new authorizations could not be
`3 X 56= 168 bits, but the plaintext and ciphertext lengths
`are unchanged at 64 bits. Hence the modified DES has
`predicted from old authorizations because, in a conven-
`a key length of 168 bits and a ciphertext of 64 bits.
`tional cryptographic system, given past plaintext-
`K1 is repeated to strengthen security. Ideally, each
`ciphertext pairs, it must be difiicult to determine the
`key would be repeated several times. The same basic
`plaintext which goes with a new ciphertcxt.
`DES circuitry can be used iteratively, rather than repli-
`For ease of understanding, the implementation of the
`cated, so that the cost of the circuitry shown in FIG. 3A
`base unit 12 is shown in three figures, corresponding to
`need not be much greater than that for a basic DES.
`its three phases of operation: when a user generates a
`An alternative, and usually more efficient way of
`request for use of a software package; when the base
`producing a DES modified for a large key would be to
`unit verifies the validity of the received authorization;
`increase the number of iterations or rounds in DES.
`and when a user later uses the software package. Only
`those elents of the base unit 12 which are needed in
`Since 43 bits of key come into play in each DES itera-
`tion, a 1,000 iteration DES would use 48,000 bits of key
`a particular phase are shown in the corresponding fig-
`ure.
`yet still 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,090 hits of software pack-
`age into 64 bits of hash value H. the ciphertext size of
`DES is 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
`
`65
`
`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 INFORMATION and N, the num-
`ber of additional uses desired, to the base unit 12, for
`example by typing them into a keyboard which is 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 208
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2083
`Apple v. PMC
`IPR2016-00755
`Page 9
`
`

`
`4,658,093
`
`10
`software being used. Update unit 36 applies to interrog-
`atory signal representing H to a non-volatile memory
`37, for example an EEPROM or a CMOS memory with
`battery backup. The non-volatile memory 3'? applies a
`signal to the update unit 36, said signal representing M,
`the number of authorized uses of the software package
`with hash value H which still remain unused prior to
`this new authorization. The update unit 36 adds M and
`N and applies a signal representing M-l-N to the non-
`volatile memory 37, so that M+N replaces the old
`number M in the non-volatile memory 37 as the number
`of uses of the software package which have been paid
`for.
`FIG. 7 depicts an impletnentation of the crypto-
`graphic check unit 34. Signals representing K, N, R, and
`H are applied as inputs to a cryptographic function
`generator 38 which generates a check value C as an
`output signal. Signals C and A are input to a compar