Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 1 of 13
`
`Exhibit Q
`
`

`

`United States Patent 19
`Hellman
`
`Patent Number:
`11)
`(45) Date of Patent:
`
`4,658,093
`Apr. 14, 1987
`
`54 SOFTWARE DISTRIBUTION SYSTEM
`Martin E. Hellman, 730 Alvarado
`76) Inventor:
`Ct., Stanford, Calif. 94305
`21) Appl. No.: 512,685
`22 Filed:
`Jul. 11, 1983
`51) int. Cl. ............................................... H04L 9/00
`52 U.S.C. .......................................... 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,798,605 3/1974 Feistel .............................. 178/22.08
`4,200,770 4/1980 Hellman et al.
`... 178/2.2.11
`4,218,582 8/1980 Hellman et al.
`... 178/2.2.11
`4,264,782 4/1981 Konhein ........
`... 178/22,08
`4,405,829 9/1983 Rivest et al. ...
`... 178/2.2.1
`4,424,414 1/1984 Hellman et al.
`... 178/2.2.1
`4,446,519 5/1984 Thomas ..........
`... 178/2.2.08
`4,458,315 7/1984 Uchenick ...
`... 178/2.2.08
`4,465,901 8/1984 Best ............
`... 178/2.2.08
`4,567,512 1/1986 Abraham .............................. 358/86
`OTHER PUBLICATIONS
`"New Directions in Cryptography', by Diffie and Hell
`
`man IEEE Transaction on Information Theory, vol. 22
`#6, 1 1/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
`
`
`
`SOFTWARE
`
`7
`
`PERM.
`MEMORY
`
`28
`
`
`
`
`
`TEMP
`MEMORY
`
`ONE WAY
`HASH
`
`volt MUPDATE
`M.N. UNIT
`
`MEMORY
`
`CrYPTO
`CHECK
`UNT
`
`2
`
`34
`
`
`
`
`
`
`
`
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 2 of 13
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet 1 of 4
`
`4,658,093
`
`6
`
`SOFTWARE
`
`AUTHORIZATION
`BLNG
`UNIT
`
`A/G/
`
`
`
`
`
`TABLE OF SER. NO'S
`AND SECRET KEYS
`K S N R H
`
`PUBLIC
`SER.N.O.
`
`
`
`CRYPTOGRAPHIC
`FUNCTION
`
`
`
`
`
`
`
`TABLE OF
`SOFTWARE
`
`SOFTWARE
`NAME
`
`
`
`SOFTWARE
`PACKAGE
`
`
`
`ONE WAY
`HASH
`FUNCTION
`
`A/G2
`
`
`
`SOFTWARE
`
`
`
`O
`p
`DES
`MODIFIED
`K FOR LARGE
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 3 of 13
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet 2 of 4
`
`4,658,093
`
`O (64. BITS)
`
`168 BITS
`OF KEY
`
`H (64. BITS)
`A/654
`
`
`
`
`
`SK
`
`K
`
`H, R, N
`
`Pl
`MODIFIED
`DES
`
`26
`
`
`
`
`
`RANDOM NO. GEN.
`
`
`
`4.
`
`TEMPORARY
`MEMORY
`
`28
`
`SER NO.
`PERM. MEM.
`
`
`
`27 1 SOFTWARE NAME
`USER BILLING INFO
`A/G 5
`
`N, R
`SOFTWARE NAME
`SER. NO.
`BILLING INFO
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 4 of 13
`
`

`

`U.S. Patent Apr. 14, 1987
`
`shee 3 of 4
`
`4,658,093
`
`SOFTWARE
`
`28
`
`TEMP
`MEMORY
`
`
`
`
`
`
`
`NON
`VOLATLE
`MEMORY
`
`
`
`2
`
`CRYPTO
`CHECK
`UNIT
`
`34
`
`
`
`38
`
`CRYPTOGRAPHC
`FUNCTION
`
`39
`
`
`
`COMPARATOR
`
`N, H 8
`TO 36
`SOFTWARE NAME
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 5 of 13
`
`

`

`U.S. Patent Apr. 14, 1987
`
`Sheet 4 of4
`
`4,658,093
`
`SOFTWARE
`
`
`
`-
`
`
`
`
`
`
`
`ONE WAY
`
`
`
`
`
`voire
`
`M
`
`UPDATE
`N
`
`A/G3
`
`
`
`SK
`
`H, R, N
`
`PUBLIC KEY
`CRYPTO
`SYSTEM
`
`43
`
`
`
`
`
`
`
`PUBLIC KEY
`CRYPTO
`SYSTEM
`
`
`
`COMPARATOR
`
`N, H
`TO 36
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 6 of 13
`
`A.
`
`44
`
`46
`
`H, R, N
`
`

`

`1.
`
`SOFTWARE DISTRIBUTION SYSTEM
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 7 of 13
`
`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
`10
`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
`15
`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
`20
`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
`25
`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
`30
`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.
`35
`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
`40
`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
`45
`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 forbit copy of
`50
`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
`65
`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
`
`5
`
`4,658,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 databases 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
`
`55
`
`

`

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

`

`10
`
`15
`
`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 authorizaiton A
`tional software use in the pay per use software control
`for that particular base unit 12 to use the software pack
`system of FIG. 1.
`age 17 an additional N times, and communicates the
`FIG. 3 is a block diagram of a one-way hash function
`signal representing authorization A to base unit 12.
`for performing one-way hashing operations in the au
`Base unit 12 receives the signal representing authori
`thorization and billing unit of FIG. 2, in the base unit
`zation A over insecure channel 11. As will be explained
`during verification of authorization of FIG. 6, and in
`shortly in FIG. 6, base unit 12 then checks whether the
`the base unit during use of software of FIG. 8.
`authorization is from the software 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
`20
`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
`unit 13 to determine the complete contents of software
`25
`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
`F.G. 1.
`at base unit 12.
`30
`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 His used as an "abbre
`F.G. 2.
`viation" or name for describing the software package
`FIG. 10 is a block diagram of an alternative imple
`21. To prevent an opponent from modifying one soft
`35
`mentation of a cryptographic checking unit in a base
`ware package so that it has the same abbreviation or
`unit during verification of authorization of additional
`name as another software package, one-way hash func
`software uses of FIG. 6.
`tion generator 22 has the following property: Its output
`Referring to FIG. 1, a pay per use software control
`signal, H, is easily commputed from its input signal,
`system is shown in which communication takes place
`software 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
`lent and therefore have the same authorization A. An
`45
`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
`tor 22 has a much shorter output, perhaps 100 bits, than
`unit 13.
`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.
`Storage of H or of the complete software package 17 is
`can be set low because additional revenue will be ob
`tained by the software manufacturer when issuing addi
`desirable to increase the security of the system because
`55
`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
`uses of less expensive packages when really using more
`zation and billing unit 13 a signal representing a user
`expensive ones. A method for implementing one-way
`originated request for software use. This request con
`hash function generator 22 is depicted in FIG. 3, which
`sists of several parts SOFTWARE NAME, SERIAL
`will be explained shortly.
`NUMBER, N, R, and BILLING INFORMATION.
`The signal H which is the output of the one-way hash
`SOFTWARENAME 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
`uses of software requested. R is a random number,
`communicated to base unit 12 over channel 11. The
`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
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 9 of 13
`
`65
`
`

`

`5
`
`10
`
`15
`
`4,658,093
`8
`7
`one-way hash function are known to exist. DES encryp
`and SK which is obtained from authorization and billing
`tion is very slow on a general purpose signal processor
`unit's table of serial numbers and secret keys.
`such as a microprocessor. Thus, if the signal processing
`Generator 23 has the property that new authoriza
`in the base unit 12 or authorization and billing unit 13 is
`tions cannot be inferred from old authorizations. More
`precisely, if cryptographic function generator 23 gener
`done primarily with a microprocessor then a one-way
`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 'SKCi), hash values H(i), random numbers
`R(i), and numbers NG), so long as the secret keys
`tranposition on 32 bits, which makes DES slow on a
`microprocessor, replacement of the mixing operation
`'SK(i) are kept secret, it is difficult for an opponent to
`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.
`One implemenation of the cryptographic function
`ready been given. Methods and apparatus for imple
`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
`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
`mentation would have the required property that new
`and M. Hellman in section V of their paper "New Di
`rections in Cryptography” (IEEE Transactions on In
`authorizations could not be predicted from the property
`20
`formation Theory, November 1976) a one-way function
`that given an output valve, it is difficult to find the
`corresponding input value to the one-way function.
`from a value X to a value Y can be generated from a
`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
`26 would have the secret key SK as input to its key port
`25
`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
`fied, in the manner described above, to have its key
`length equal to the length of SK.
`system is secure.
`30
`In order to make the one-way hash function genera
`In addition, the modified DES's plaintext length
`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
`the length of A. Usually the plaintext and ciphertext are
`bits, than ciphertext, typically 100 bits in this invention.
`the same length, but for our purposes any portion of the
`The Data Encryption Standard (DES), described in
`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.
`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 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
`with binary 0's to make the proper size input.
`45
`independent keys used have a total length of
`This alternative implemenation would also inherently
`3X56= 168 bits, but the plaintext and ciphertext lengths
`have the property that new authorizations could not be
`are unchanged at 64 bits. Hence the modified DES has
`predicted from old authorizations because, in a conven
`tional cryptographic system, given past plaintext
`a key length of 168 bits and a ciphertext of 64 bits.
`K1 is repeated to strengthen security. Ideally, each
`ciphertext pairs, it must be difficult to determine the
`plaintext which goes with a new ciphertext.
`key would be repeated several times. The same basic
`DES circuitry can be used iteratively, rather than repli
`For ease of understanding, the implementation of the
`base unit 12 is shown in three figures, corresponding to
`cated, so that the cost of the circuitry shown in FIG. 3A
`its three phases of operation: when a user generates a
`need not be much greater than that for a basic DES.
`An alternative, and usually more efficient way of
`request for use of a software package; when the base
`55
`producing a DES modified for a large key would be to
`unit verifies the validity of the received authorization;
`and when a user later uses the software package. Only
`increase the number of iterations or rounds in DES.
`Since 48 bits of key come into play in each DES itera
`those elements of the base unit 2 which are needed in
`a particular phase are shown in the corresponding fig
`tion, a 1,000 iteration DES would use 48,000 bits of key
`yet still have only a 64-bit ciphertext. For cryptographic
`le.
`security it is necessary that each bit of key be used
`FIG. 5 depicts the operation of the base unit 12 dur
`ing generation of a request for software use. A user 27
`several times, so at least a 3,000 round DES would be
`desirable for compressing 48,000 bits of software pack
`communicates signals representing SOFTWARE
`age into 64 bits of hash value H. the ciphertext size of
`NAME, BILLING INFORMATION and N, the num
`DES is also easily increased if, for example, a 100 bit
`ber of additional uses desired, to the base unit 12, for
`65
`example by typing them into a keyboard which is part
`hash value H is needed instead of a 64 bit value.
`While DES is used here for illustative purposes,
`of base unit. Base unit 12 stores these values in a tempo
`many other methods and apparatus for generating a
`rary memory 28, for example a RAM, so that they can
`
`50
`
`35
`
`Case 6:21-cv-00735-ADA Document 23-17 Filed 11/23/21 Page 10 of 13
`
`

`

`O
`
`4,658,093
`10
`software being used. Update unit 36 applies to i