`
`[19]
`
`[11] Patent Number:
`
`4,658,093
`
`
`
` Hellman [45] Date of Patent: Apr. 14, 1987
`
`
`
`[54] SOFTWARE DISTRIBUTION SYSTEM
`
`[76]
`
`Inventor: Martin E. Hellman, 730 Alvarado
`CL, Stanford, Calif. 94305
`
`[21] AF'li’]
`[22] Filed;
`
`.N .: 512,153
`°
`
`5
`Jul. 11, 1933
`
`man IEEE Transaction on Information Theory, vol. 22
`#6, “fill.
`“Multiuser Cryptographic Techniques", by Diffie and
`Hellman AMPS-Conference Proceedings, vol. 45. pp.
`109412, 6/3/76.
`Primary Examiner-aSalvatore Cangialosi
`Assistant Examiner—Aaron J. Lewis
`Attorney. Agent, or firm—Flehr, Hohbach. Test,
`Albrittcm 8: Herbert
`
`[51]
`
`Int. cu ............................................... 1104:. 9/00
`
`[1.5. C]. ...................... .
`......
`[50] Field of Search ............... ITS/22.08, 22.11, 22.09;
`353/36
`
`[56]
`
`References Cited
`U‘S' PATENT DOCUMENTS
`3,793,605
`3/1914 Feistel
`4.200.770 4/1930 Hellman £1 31- -
`4313-532
`3/1930 Hallma‘“ ‘1 a" '
`43645732 4/3931 Kom'm """" "
`'
`.
`1’33"???
`gevllemanflat: a1
`4‘446'519 5/1984 mamas
`4:453:315
`7/1934 Uchenjck
`4’455‘901
`3/1934 Best
`4.567.512
`1/1986 Abraham
`OTHER PUBLICATIONS
`
`
`
`i
`
`ITS/22.08
`178/21“
`- 173/21“
`" 178/2108
`IL. 178 22.11
`17322.11
`173/2108
`173/2103
`173/2233
`358/86
`
`Software (Programs, vidwsamess music, movies: etc-J
`can be authorized for use a given number of times by a
`base unit after which the base unit (computer, video-
`381:8 :Jase ;1nit. record pgyer,fvideorcctojrdher or video-
`dis payer cannotuset
`tso mareun'
`emanu ac—
`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—
`.
`.
`.
`.
`.
`.
`.
`mm“ T519331 and replay“ “ ‘0 the?“ “.m' 5mm)“
`authonzanons can be made base “mt SPQCIfiC, 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
`ftw
`add't' nal b
`ef'ts.
`3°
`are”
`“°
`“1 1
`
`
`
`I4
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 1
`
`“New Directions in Cryptography", by Diffie and Hell-
`
`10 Claims, 11 Drawing Figures
`
`IT
`
`ONE WHY
`HRSH
`
`
`
`
`(2 VP
`£11:ch
`voEAo'PiLE "Pm-E
`—
`MEMORY m “N” - um‘r
`
`
`
`I2
`
`
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 1
`
`
`
`U. S. Patent Apr. 14,1987
`
`Sheet] of4
`
`4,658,093
`
`|6
`
` II
`
`SOFTWARE
`
`'
`
`AUTHORIZATION
`BILLING
`UNIT
`
`F/6_ /
`
`TABLE OF SER. wo's
`AND SECRET KEYS
`
`SKN a
`
`H
`
`CRYPTOGRQPHIC
`FUNCTION
`
`
`
`
`
`ONE WAY
`HASH
`FUNCTION
`
`[-76.2
`
`MODIFIED
`
`_.p|
`
`DES
`
`K FOR LARGE
`
`SOFTWARE
`
`TABLE OF
`SOFTWARE
`
`SOFTWARE
`NAME
`
`SOFTWARE
`PACKAGE
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 2
`
`
`
`U. S. Patent Apr. 14,1987
`
`Sheet2 of4
`
`4,658,093
`
`9 {64 BITS)
`
`IGB BITS
`
`OF KEY
`
`H (64 BITS)
`
`F/G_ 3.4
`
`H.R1N
`
`SK
`
`IPI
`
`.K: MODIFIED
`
`26
`
`RANDOM NO. GEN.i! I4
`
`TEMPORARY
`MEMORY
`
`
`SER. N0.
`
`
`
`
`
`
`
`
`
`
`N
`
`PERM. MEM.
`
`N R
`SOFTWARE NAME
`
`
`
`27
`USER
`
`. SOFTWARE NAME
`BILLING INFO
`
`- F/G_5
`
`SER. NO.
`BILLING INFO
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 3
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 3
`
`
`
`U. S. Patent Apr. 14, 1987
`
`Sheet3 of4
`
`4,658,093
`
`SOFTWARE
`
`NON
`
`VOLATI LE
`
`MEMORY
`
`3’3
`
`CRYPTOGRAPHIC
`FUNCTION
`
`
`
`
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 4
`
`
`
`39
`
`COMPnRATOR
`
`N,H 8.
`TO 56
`SOFTWARE NAME
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`
`
`U. S. Patent Apr. 14, 1937
`
`Sheet4 of4
`
`4,658,093
`
`
`
`SOFTWARE
`
`
`
`PLAYER
`
`-
`
`SWITCH
`
`ONE waif
`
`
`
`
`
`
`
`
`
`
`
`m- UPDATE
`Im- UNIT
`_
`
` NON
`VOLITlLE
`
`
`
`MEMORY
`
`F/G_8
`
`
`
`H,R,N
`
`PUBLIC KEY
`
`CRYPTO
`SYSTEM
`
`SK
`
`43
`
`PUBLIC KEY
`
`CRYPTD
`
`SYSTEM
`
`N,H
` COMPARATOR
`
`
` A
`
`46
`
`H,R,N
`
`44
`
`TO 36
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 5
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`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 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.
`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 ruined portion of the disk, but checks
`to make sure that that portion of the disk is, in fact,
`mined. If it is ruined, the program continues in: normal
`execution. If it is not mined. then the program steps
`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}
`
`15
`
`20
`
`25
`
`3O
`
`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 any 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
`pans 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: Ones
`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 Hellman's
`tutorial paper “Privacy and Authentication: An Intro-
`duction to Cryptography", Proceedings of the IEEE,
`November 1979. The prior art desoribes 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-
`tiori. The enciphering function E(K,P)=C operates on
`
`PMC Exhibit 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 6
`
`
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`
`
`3
`a plaintext (unscrambled message) P with a key K to
`produce ciphcrtext (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 Hellman‘s paper, “New Directions
`in Cryptography", IEEE Transactions on Cryptogra-
`phy, vol. IT-22, N0vember 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 difl‘ers 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
`
`4s
`
`55
`
`65
`
`4,658,093
`
`
`
`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(SIG'). 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
`SIG’=H(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(K,C), or as a public key cryptographic function,
`PK(SIG) or SK(H(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 in 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
`an 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 cryptogapbic 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 213
`
`Apple v. PM
`|PR2016-0152
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`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 DES 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 bIOck diagram of a base unit during me 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 in
`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—repeating number gener-
`ated by the base unit 12. And BILLING INFORMA-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`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 authorization
`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 computed 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 H value.
`This property is necessary because any two software
`packages with the same H 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 H 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 1‘? 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 funcan 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 2133
`
`Apple v. PMC
`|PR2016-01520
`
`Page 8
`
`
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 8
`
`
`
`4,658,093
`
`50
`
`55
`
`65
`
`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 progeny that new authorin-
`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 onoway
`precisely, if cryptographic function generator 23 gener-
`hash function generator 22 which is computed more
`ates a publicly known functiou and if an opponent has
`rapidly on a microprocessor would be desirable. Since it
`many authorizations 'Ati) 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
`'SKfi) 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-
`SK', N’, R', H’ for which an authorization has not al-
`able.
`ready been given. Methods and apparatus for imple-
`One implemenation 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-
`mentation 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 1976)a0ne-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 plaintext 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 fou: times with the normal DES to
`ciphertext length of modified DES 26 could be equal to
`produce a ciphertext C. te 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‘s 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 canvas:-
`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 difi'icult to determine the
`key would be repeated several times. The same basic
`plaintext which goes with a new ciphertext.
`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 bear:
`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,000 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
`
`
`
`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 bane 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 213
`
`Apple v. PM
`|PR2016-0152
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-01520
`Page 9
`
`
`
`4,658,093
`
`9
`be used later when verifying the validity of the received
`authorization for additioual software use. A random
`number generator 29 (e. g. a noisy operational amplifier
`with hard quantization) generates a signal representing
`a random number R which is also stored in temporary
`memory 28 for later use during verification of the re-
`ceived authorization. The base unit’s serial number is
`stored in a permanent memory 31, for example a PROM
`which was burned in during manufacture of the base
`unit. Signals representing the four quantifies stored in
`temporary memory 23, N, R, SOFTWARE NAME
`and BILLING INFORMATION, and the serial num-
`ber stored in permanent memory 31 are oommuncicated
`over channel 11