throbber
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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket