United States Patent [wj
`Hellman
`
`4,658,093
`[ii] Patent Number:
`[45] Date of Patent: Apr. 14,1987
`
`[54] SOFTWARE DISTRIBUTION SYSTEM
`
`[76] Inventor: Martin E. Hellman, 730 Alvarado
`Ct., Stanford, Calif. 94305
`
`[21] Appl. No.: 512,685
`
`[22] Filed:
`
`Jul. 11, 1983
`
`[51]
`Int. a.4.................................................. H04L9/00
`[52] U.S. Cl.............................................. 380/25; 380/4;
`380/30
`[58] Field of Search............... 178/22.08, 22.11, 22.09;
`358/86
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`3/1974 Feistel ............................... 178/22.08
`3,798,605
`4/1980 Hellman et al..................... 178/22.11
`4,200,770
`8/1980 Hellman et al..................... 178/22.11
`4,218,582
`4/1981 Konheim........................... 178/22.08
`4,264,782
`9/1983 Rivest et al........................ 178/22.11
`4,405,829
`1/1984 Hellman et al..................... 178/22.11
`4,424,414
`5/1984 Thomas............................. 178/22.08
`4,446,519
`7/1984 Uchenick .......................... 178/22.08
`4,458,315
`8/1984 Best.................................... 178/22.08
`4,465,901
`1/1986 Abraham ............................... 358/86
`4,567,512
`OTHER PUBLICATIONS
`“New Directions in Cryptography”, by Diffie and Hell­
`
`man IEEE Transaction on Information Theory, vol. 22
`#6, 11/76.
`“Multiuser Cryptographic Techniques”, by Diffie and
`Hellman AFIPS-Conference Proceedings, vol. 45, pp.
`109-112, 6/8/76.
`Primary Examiner—Salvatore Cangialosi
`Assistant Examiner—Aaron J. Lewis
`Attorney, Agent, or Firm—Flehr, Hohbach, Test,
`Albritton & Herbert
`[57]
`ABSTRACT
`Software (programs, videogames, 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.
`
`10 Claims, 11 Drawing Figures
`
`Roku EX1004
`U.S. Patent No. 6,411,941
`
`

`

`U.S. Patent Apr. 14,1987 Sheet 1 of4
`
`4,658,093
`
`FIG-I
`
`FIG-2
`
`FIG-3
`
`SOFTWARE
`
`

`

`U.S. Patent Apr. 14,1987
`
`Sheet2 of4
`
`4,658,093
`
`FIG—3A
`
`FIG—4
`
`FIG—5
`
`

`

`U.S. Patent Apr. 14,1987 Sheet 3 of4
`
`4,658,093
`
`FIG—6
`
`FIG—7
`
`

`

`U.S. Patent Apr. 14,1987 Sheet4of4 4,658,093
`
`FIG-9
`
`FIG-IO
`
`

`

`4,658,
`
`SOFTWARE DISTRIBUTION SYSTEM
`
`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,
`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
`
`io
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`093
`
`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 Diffie and Hellman’s
`tutorial paper “Privacy and Authentication: An Intro­
`duction to Cryptography”, Proceedings of the IEEE,
`November 1979. The prior art describes one-way func­
`tions and cryptographic functions of the type needed as
`components of the present software control system.
`For completeness, three prior art cryptographic func­
`tions required to carry out the present invention are
`described: conventional cryptographic functions or
`systems, one-way functions, and public key cryptosys­
`tems.
`A conventional cryptographic function or system can
`be described by an enciphering and a deciphering func­
`tion. The enciphering function E(K,P)=C operates on
`
`

`

`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 5
`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 10
`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- 15
`scribed in Federal Information Processing Standard
`Publication (FIPS PUB) 46 and available from the Na­
`tional Technical Information Service, 5285 Port Royal
`Road, Spmgfield, VA 22161.
`A one-way function is a function which is easy to 20
`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 25
`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- 30
`tion V of Diffie and Hellman’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), 35
`where PO is some fixed, publicly known plaintext
`value. That is, the input X to the one-way function is
`used as the key, PO 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 40
`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 45
`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 50
`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 55
`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 differs from a conventional
`cryptographic system in that two different keys are 60
`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 65
`SIG from the message M by the operation SIG=SK H
`(M), where H is a one-way hash function of the mes­
`sage.
`
`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
`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:
`
`

`

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

`

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

`

`15
`
`be used later when verifying the validity of the received
`authorization for additional 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 5
`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 quantities stored in 10
`temporary memory 28, N, R, SOFTWARE NAME
`and BILLING INFORMATION, and the serial num­
`ber stored in permanent memory 31 are communcicated
`over channel 11 by the base unit transmit-receive unit
`14.
`FIG. 6 depicts the operation of the base unit 12 dur­
`ing verification of an authorization A to use a software
`package an additional number of times. The base unit
`does not use the software package during this phase, but
`is updating its memory so that the software package can 20
`be used later. Input signals during this phase of opera­
`tion are the software package and authorization A from
`transmit-receive unit 14. A signal representing software
`package 17 is applied as input to a one-way hash func­
`tion generator 33 of the base unit which is functionally 25
`the same as the one-way has function generator 22.
`FIGS. 3 and 3A therefore each depict an implementa­
`tion of one-way function generator 33.
`As depicted in FIG. 6, the base unit 12 has a base unit
`key, K, stored in a permanent memory 31, for example 30
`a PROM which is burned in during manufacture of the
`base unit. While we will later generalize the implemen­
`tation to situations where the base unit key, K, and the
`secret key SK, used by the authorization and billing unit
`are different, for the moment we treat the case where K 35
`