`
`asttory Copy
`Do not discard
`
`
`
`
`
`
`
`
`
`x
`
`FEB 9
`
`197
`
`,
`
`FEDERAL INFORMATION
`PROCESSING STANDARDS PUBLICATION
`1977 JANUARY 15
`
`CATEGORY: ADP OPERATIONS
`SUBCATEGORY: COMPUTER SECU
`
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`
`Apple v. PMC
`
`IPR2016-00753
`IPR2016-00753
`Page 1
`
`Page 1
`
`

`

`
`
`
`[=
`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`U.S. DEPARTMENT OF COMMERCE ©@ Elliot L. Richardson, Secretary
`
`Edward O. Vetter, Under Secretary
`
`Dr. Betsy Ancker-Johnson, Assistant Secretary for Science and Technology
`
`NATIONAL BUREAU OF STANDARDS @ Ernest Ambler, Acting Director
`
`Foreword
`
`Information Processing Standards Publication Series of the National
`The Federal
`Bureau of Standards is the official publication relating te standards adopted and promul-
`gated under the provisions of Public Law89-306 (Brooks Bill) and under Part 6 of Title 18,
`Code of Federal Regulations. These legislative and executive mandates have given the
`Secretary of Commerce important responsibilities for improving the utilization and man-
`agement of computers and automatic data processing systems in the Federal Government.
`To earry out the Secretary’s responsibilities, the NBS, through its Institute for Computer
`Sciences and Technology, provides leadership,
`technical guidance, and coordination of
`government efforts in the development of technical guidelines and standards in these
`areas.
`
`
`The series is used to announce Federal Information Processing Standards, and to
`provide standards information of general interest and an index of relevant standards
`publications and specifications. Publications that announce adoption of standards provide
`the necessary policy, administrative, and guidance information for effective standards
`implementation and use. The technical specifications of the standard are usually attached
`to the publication, otherwise a reference source is cited.
`
`Comments covering Federal Information Processing Standards and Publications are
`welcomed, and should be addressed to the Associate Direetor for ADP Standards, Institute
`
`for Computer Sciences and Technology, National Bureau of Standards, Washington, D.C.
`sponsible
`20234. Such comments will be either considered by NBS or forwarded to the re
`activity as appropriate.
`
`Page 2
`
`IERNEST AMBLER, Acting Directar
`
`Abstract
`
`The selective application of technological and related procedural safeguards is an
`important responsibility of every Federal organization in providing adequate security toits
`ADP systems. This publication provides a standard to be used by Federal organizations
`when these organizations specify that cryptographic protection is to be used for sensitive
`or valuable computer data. Protection of computer data during transmission between
`electronic components or while in storage may be necessary to maintain the confidentiality
`and integrity of the information represented by that data. The standard specifies an
`encryption algorithm which is to be implemented in an electronic device for use in Federal
`ADP systems and networks. The algorithm uniquely defines the mathematical steps
`required to transform computer data into a eryptographic cipher. It also specifies the steps
`required to transform the cipher back to its original form. A device performing this
`algorithm may be used in many applications areas where cryptographie data protection is
`needed, Within the context of a total security program comprising physical security
`procedures, good information management practices and computer system/network access
`controls, the Data Emeryption Standard is being made available for use by Federal
`agencies.
`
`Key Words: ADPsecurity; computer security; encryption; Federal Information Processing
`Standard,
`
`Nat. Bur. Stand. (U.S), Fed. Info. Process. Stand. Publ. arips pup 46, 17 pages (1977
`CODEN: FIPPAT
`
`
`
`
`For sale by the National Technical Information Service, U.S, Department of Commerce,
`Springfield. Virginia #2161
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 2
`
`
`
`
`
`‘
`
`

`

`
`
`;
`
`*
`
`
`
`Federal Information
`Processing Standards Publication 46
`
`1977 January 15
`
`ANNOUNCING THE
`
`DATA ENCRYPTION STANDARD
`
`FIPS PUB 46
`
`
`
`Federal Information Processing Standards are issued by the National Bureau of Standards pursuant to the Federal
`Property and Administrative Services Act. of 1949, as amended, Public Law 89-306 (79 Stat 1127), Executive Order 11717
`(88 FR 12815, dated May i1, 1973), and Part 6 of Title 15 Code of Federal Regulations (CFR).
`
`Name of Standard: Data Encryption Standard (DES).
`
`Category of Standard: Operations, Computer Security.
`
`Explanation: The Data Eneryption Standard (DES) specifies an algorithm to be implemented in
`electronic hardware devices and used for the cryptographic protection of computer data. This
`publication provides a complete description of a mathematical algorithm for encrypting (encipher-
`ing) and decrypting (deciphering) binary coded information. Encrypting data converts it to an
`unintelligible form called cipher. Decrypting cipher converts the data back to its original form. The
`algorithm described in this standard specifies both enciphering and deciphering operations which
`are based on a binary number called a key. The key consists of 64 binary digits (“0s or “1’s) of
`which 56 bits are used directly by the algorithm and 8 bits are used for error detection.
`
`Binary coded data may be cryptographically protected using the DES algorithm in conjunction
`with a key. The key is generated in such a way that each of the 56 bits used directly by the
`algorithm are random and the 8 errordetecting bits are set to make the parity of each 8-bit byte of
`the key odd, 1.e., there is an odd numberof “1”s in each 8-bit byte. Each member of a group of
`authorized users of encrypted computer data must have the key that was used to encipherthe data
`in order to use it. This key, held by each member in common,is used to decipher the data received
`in cipher form from other members of the group. The eneryption algorithm specified in this
`standard is commonly known among those using the standard. The unique key chosen for use in a
`particular application makes the results of enerypting data using the algorithm unique. Selection of
`a different key causes the cipher that is produced for any given set of inputs to be different. The
`cryptographic security of the data depends on the security provided for the key used to encipher
`and decipherthe data.
`
`Data can be recovered from cipher only by using exactly the same key used to encipher it.
`Unauthorized recipients of the cipher who know the algorithm but do not have the correct key
`cannot derive the original data algorithmically. However, anyone who does have the key and the
`algorithm ean easily decipher the cipher and obtain the original data, A standard algorithm based
`on a secure key thus provides a basis for exchanging encrypted computer data by issuing the key
`used to encipher it
`to those authorized to have the data. Additional FIPS guidelines for
`implementing and using the DES are being developed and will be published by NBS.
`
`Approving Authority: Secretary of Commerce.
`
`Maintenance Agency: Institute for Computer Sciences and Technology, National Bureau of
`Standards.
`
`Applicability: This standard will be used by Federal departments and agencies for the crypto-
`graphic protection of computer data when the following conditions apply:
`1
`
`
`
`
`
`'
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 3
`Page 3
`
`

`

`
`
`
`
`FIPS -PUB-46
`
`1. An authorized official or manager responsible for data security or the security of any
`computer system decides that cryptographic protection is required; and
`2. The data is not classified according to the National Security Act of 1947, as amended, orthe
`Atomic Energy Act of 1954, as amended.
`
`However, Federal agencies or departments which use cryptographic devices for protecting data
`classified according to either of these acts can use those devices for protecting unclassified data in
`lieu of the standard.
`
`In addition, this standard may be adopted and used by non-Federal Government organizations.
`Such use is encouraged when it provides the desired security for commercial and private
`organizations.
`
`Data that is considered sensitive by the responsible authority, data that has a high value, or data
`that represents a high value should be cryptographically protected if it is vulnerable to unauthor-
`ized disclosure or undetected modification during transmission or while in storage. A risk analysis
`should be performed under the direction of a responsible authority to determine potential threats.
`FIPS PUB 31 (Guidelines for Automatic Data Processing Physical Security and Risk Management)
`and FIPS PUB 41 (Computer Security Guidelines for Implementing the Privacy Act of 1974)
`provide guidance for making such an analysis. The costs of providing cryptographic protection
`using this standard as well as alternative methods of providing this protection and their respective
`costs should be projected. A responsible authority then should make a decision, based on these
`analyses, whether or not to use cryptographic protection and this standard.
`
`Applications: Data encryption (cryptography) maybe utilized in various applications and in various
`environments. The specific utilization of encryption and the implementation of the DES will be
`based on many factors particular to the computer system and its associated components. In
`general, cryptography is used to protect. data while it is being communicated between two points or
`while it is stored in a medium vulnerable to physical theft. Communication security provides
`protection to data by enciphering it at the transmitting point and deciphering it at the receiving
`point. File security provides protection to data by enciphering it when it is recorded on a storage
`medium and deciphering it when it is read back from the storage medium. In thefirst case, the key
`must be available at the transmitter and receiver simultaneously during communication. In the
`second case, the key must be maintained and aecessible for the duration of the storage period.
`
`Hardware Implementation: The algorithm specified in this standard is to be implemented in
`computer or related data communication devices using hardware (not software) technology. The
`specific implementation may depend on several factors such as the application, the environment,
`the technology used, etc. Implementations which comply with this standard include Large Scale
`Integration (LSD “chips” in individual electronic packages, devices built from Medium Scale
`Integration (MSDelectronic components, or other electronic devices dedicated to performing the
`operations of the algorithm. Micro-processors using Read Only Memory (ROM) or micro-pro-
`grammed devices using microcode for hardware level control instructions are examples of the
`latter. Hardware implementations of the algorithm which are tested and validated by NBS will be
`considered as complying with the standard. Procedures for testing and validating equipment for
`conformance with this standard are available from the Systems and Software Division, National
`Bureau of Standards, Washington, D.C. 20234. Software implementations in general purpose
`computers are not in compliance with this standard. Information regarding devices which have
`been tested and validated will be made available to all FIPS points of contact.
`
`Export Control: Cryptographic devices and technical data regarding them are subject to Federal
`Government export controls as specified in Title 22, Code of Federal Regulations, Parts 121 through
`128. Cryptographic devices implementing this standard and technical data regarding them must
`eomply with these Federal regulations.
`
`2
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 4
`Page 4
`
`
`
`

`

`
`
`FIPS PUB 46
`
`Patents: Crytographic devices implementing this standard may be covered by U.S. and foreign
`patents issued to the International Business Machines Corporation. However, IBM has granted
`nonexclusive, royalty-free licenses under the patents to make, use and sell apparatus which
`complies with the standard. The terms, conditions and scope of the licenses are set out in notices
`published in the May 18, 1975 and August 31, 1976 issues of the Official Gazette of the United
`States Patent and Trademark Office (934 O. G. 452 and 949 O. G. 1717.
`
`Alternative Modes of Using the DES; The “Guidelines for Implementing and Using the Data
`Emeryption Standard” describe two different modes for using the algorithm described in this
`standard. Blocks of data containing 64 bits may be directly entered into the device where 64-bit
`cipher blocks are generated under control of the key. This is called the electronic code book mode.
`Alternatively, the device may be used as a binary stream generator to produce statistically random
`binary bits which are then combined with the clear (unencrypted) data (1-64 bits) using an
`“exelusive-or’ logic operation. In order to assure that the enciphering device and the deciphering
`device are synchronized, their inputs are always set to the previous 64 bits of cipher that were
`transmitted or received. This second mode of using the encryption algorithm is called the cipher
`feedback (CFB) mode. The electronic codebook mode generates blocks of 64 cipher bits. The cipher
`feedback mode generates cipher having the same numberof bits as the plain text. Each block of
`cipher is independent ofall others when the electronic codebook mode is used while each byte
`(group of bits) of cipher depends on the previous 64 cipher bits when the cipher feedback mode is
`used. The modes of operation briefly described here are further explained in the FIPS “Guidelines
`for Implementing and Using the Data Encryption Standard.”
`
`Implementation of this standard: This standard becomes effective six months after the publication
`date of this FIPS PUB. It applies to all Federal ADP systems and associated telecommunications
`networks under development as well as to installed systems whenit is determined that crypto-
`graphic-protection is required. Each Federal department or agency will issue internal directives for
`the-use of this standard by their operating units based on their data security requirement
`determinations.
`
`NBS-will- provide assistance to Federal organizations by developing and issuing additional
`technical @uidélines on computer security and by providing technical assistance in using data
`encryption. A.data encryption testbed has been established within NBS for use in providing this
`technical-assistance.. The. National Security Agency assists Federal departments and agencies in
`communications. security and.
`in determining. specific security requirements. Instructions and
`regulations for procuring data processing equipment. utilizing this standard will be provided by the
`General Services Administration.
`
`Specifications: Federal Information Processing Standard (FIPS 46) Data Encryption Standard
`(DES) (affixed).
`
`Cross Index:
`
`a. FIPS PUB 381, “Guidelines to ADP Physical Security and Risk Management”
`
`b. FIPS PUB 89, “Glossary for Computer Systems Security”
`
`c. FIPS PUB 41, “Computer Security Guidelines for Implementing the Privacy Act of 1974”
`74
`d, FIPS PUB—, “Guidelines for Implementing and Using the Data Eneryption Standard”(to
`be published)
`
`e, Other FIPS and Federal Standards are applicable to the implementation and use ofthis
`standard, In particular, the American Standard Code for Information Interchange (FIPS PUB 1)
`
`3
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016 -00753
`Page 5
`Page 5
`
`
`
`

`

`and other related data storage media or data communications standards should be used in
`conjunction with this standard. A list of currently approved FIPS may be obtained from the Office
`of ADP Standards Management, Institute for Computer Sciences and Technology, National Bureau
`of Standards, Washington, D.C. 20234.
`
`Qualifications: The cryptographic algorithm specified in this standard transforms a 64-bit binary
`value into a unique 64-bit binary value based on a 56-bit variable. If the complete 64-bit input is
`used (Le. none of the input bits should be predetermined from block to block) and if the 56-bit
`variable is randomly chosen, no technique other than trying all possible keys using known input
`and output
`for
`the DES will guarantee finding the chosen key. As
`there are over
`70,000,000,000,000,000 (seventy quadrillion) possible keys of 56 bits, the feasibility of deriving a
`particular key in this way is extremely unlikely in typieal threat environments. Moreover, if the
`key is changed frequently, the risk of this event is greatly diminished. However, users should be
`aware that it is theoretically possible to derive the key in fewertrials (with a correspondingly lower
`probability of success depending on the numberof keys tried) and should be cautioned to change
`the key as often as practical. Users must change the key andprovideit a high level of protection in
`order to minimize the potential risks of its unauthorized computation or acquisition. The feasibility
`of computing the correct key may change with advances in technology. A more complete
`description of the strength of this algorithm against various threats will be contained in the
`Guidelines for Implementing and Using the DES.
`
`When correctly implemented and properly used, this standard will provide a high level of
`cryptographic protection to computer data. NBS, supported by the technical assistance of Govern-
`ment agencies responsible for communication security, has determined that the algorithm specified
`in this standard will provide a high level of protection for a time period beyond the normallife cycle
`ofits associated ADP equipment. The protection provided by this algorithm against potential new
`threats will be reviewed withinfive years to assess its adequacy. In addition, both the standard and
`possible threats reducing the security provided through the use of this standard will undergo
`continual review by NBS andother cognizant Federal organizations. The new technology available
`at that time will be evaluated to determine its impact on the standard. In addition, the awareness
`of any breakthrough in technology or any mathematical weakness of the algorithm will cause NBS
`to reevaluate this standard and provide necessary revisions.
`
` FIPS PUB 46
`
`Comments: Comments and suggestions regarding this standard and its use are welcomed and
`should be addressed to the Associate Director for ADP Standards, Institute for Computer Sciences
`and Technology, National Bureau of Standards, Washington, D.C. 20234.
`
`Waiver Procedure: The head of a Federal agency may waive the provisions of this FIPS PUB after
`the conditions and justifications for the waiver have been coordinated with the National Bureauof
`Standards. A waiver is necessary if cryptographic devices performing an algorithm other than that
`which is specified in this standard are to be used by a Federal agency for data subject to
`cryptographic protection under this standard. No waiver is necessaryif classified communications
`security equipment is to be used. Software implementations of this algorithmfor operational use in
`general purpose computer systems do not comply with this standard and each such implementation
`must also receive a waiver. Implementation of the algorithm in software for testing or evaluation
`does not require waiver approval. Implementation of other special purpose cryptographic algo-
`rithms in software for limited use within a computer system (e.g., encrypting passwordfiles) or
`implementations of cryptographic algorithms in software which were being utilized in computer
`systems before the effective date of this standard do not require a waiver. However, these limited
`uses should be converted to the use of this standard when the system or equipment involvedis
`upgraded or redesigned to include general cryptographic protection of computer data. Letters
`describing the nature of and reasons for the waiver should be addressed to the Associate Director
`for ADP Standards as previously noted.
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 6
`Page 6
`
`
`
`

`

`
`
`FIPS PUB 46
`
`Sixty days should be allowed for review and response by NBS. The waivershall not be approved
`until a response from NBSis received; however, the final decision for granting the waiver is the
`responsibility of the head of the particular agency involved.
`
`Where to Obtain Copies of the Standard:
`
`Copies of this publication are for sale by the National Technical Information Service, U.S.
`Department of Commerce, 5285 Port Royal Road, Springfield, Virginia 22161. Order by FIPS PUB
`numberand title. Prices are published by NTIS in current catalogs and other issuances. Payment
`may be made by check, money order, deposit account or charged to a credit card accepted by NTIS,
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 7
`Page 7
`
`
`
`

`

`Page 8
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 8
`
`

`

`
`
`.
`
`:
`
`FIPS PUB 46
`
`
`
`Federal Information
`Processing Standards Publication 46
`
`1977 January 15
`
`SPECIFICATIONS FOR THE
`
`DATA ENCRYPTION STANDARD
`
`
`
`The Data Encryption Standard (DES) shall consist of the following Data Encryption Algorithm to
`be implemented in special purpose electronic devices. These devices shall be designed in such a way
`that they may be used in a computer system or network to provide cryptographic protection to
`binary coded data. The method of implementation will depend on the application and environment.
`The devices shall be implemented in such a way that they may be tested and validated as
`accurately performing the transformationsspecified in the following algorithm.
`
`DATA ENCRYPTION ALGORITHM
`
`introduction
`
`The algorithm is designed to encipher and decipherblocks of data consisting of 64 bits under control
`of a 64-bit key. Deciphering must be accomplished by using the same key as for enciphering, but
`with the schedule of addressing the key bits altered so that the deciphering processis the reverse of
`the enciphering process. A block to be enciphered is subjected to an initial permutation /P, then to
`a complex key-dependent computation and finally to a permutation which is the inverse of the
`initial permutation /P—. The key-dependent computation can be simply defined in terms of a
`function f, called the cipher function, and a function KS, called the key schedule. A description of
`the computation is given first, along with details as to how the algorithm is used for encipherment.
`Next, the use of the algorithm for decipherment is described. Finally, a definition of the cipher
`function fis given in terms of primitive functions which are called the selection functions S; and the
`permutation function P. S, P and KS of the algorithm are contained in the Appendix.
`
`The following notation is convenient: Given two blocks L and R of bits, LR denotes the block
`consisting of the bits of L followed by the bits of R. Since concatenation is associative B,B,... Bs,
`for example, denotes the block consisting of the bits of B, followed by the bits of B, ... followed by
`the bits of Bg.
`
`Enciphering
`
`A sketch of the enciphering computation is given in figure 1.
`
`
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 9
`Page 9
`
`

`

`
`
`FIPS PUB 46
`
`PERMUTED
`INPUT
`
`INPUT
`
`INITIAL PERMUTATION
`
`Ki6
`
`
`INVERSE INITIAL PERM
`[|uTPuT
`
`
`FIGURE 1. Eneiphering computation.
`8
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 10
`Page 10
`
`

`

`The 64 bits of the input block to be enciphered are first subjected to the following permutation,
`called the initial permutation IP:
`
`FIPS PUB 46
`
`IP
`
`osng
`
`oroS
`
`>oO
`
`be =
`
`woNo
`
`NO=
`
`oe HS
`
`“JOIGoreOOcebh
`
`That is the permuted input hasbit 58 of the input asits first bit, bit 50 as its second bit, and so on
`with bit 7 as its last bit. The permuted input block is then the input to a complex key-dependent
`computation described below. The output of that computation, ealled the preoutput,
`is then
`subjected to the following permutation which is the inverse of the initial permutation:
`
`40
`39
`38
`ot
`36
`35
`34
`33
`
`8
`7
`6
`5
`4
`3
`2
`1
`
`48
`47
`46
`45
`44
`43
`AZ
`41
`
`ip”
`
`16
`15
`14
`13
`12
`il
`10
`9
`
`56
`do
`o4
`53
`52
`51
`50
`49
`
`24
`23
`22
`21
`20
`19
`18
`17
`
`64
`Ge
`62
`61
`60
`59
`58
`57
`
`32
`3l
`30
`29
`28
`27
`26
`25
`
`That is, the output of the algorithm has bit 40 of the preoutput block as its first bit, bit 8 as its
`second bit, and so on, until bit 25 of the preoutput block is the last bit of the output.
`
`The computation which uses the permuted input block as its input to produce the preoutput block
`consists, but for a final interchangeofblocks,of 16 iterations of a calculation that is described below
`in terms of the cipher function f which operates on two blocks, one of 32 bits and oneof 48 bits, and
`produces a block of 32 bits.
`
`Let the 64 bits of the input block to an iteration consist of a 32 bit block L followed by a 82 bit block
`R. Using the notation defined in the introduction, the input block is then LR,
`
`Let K be a block of 48 bits chosen from the 64-bit key. Then the output L'R’ of an iteration with
`input LA is defined by:
`
`(1)
`
`L'=R
`R'=LOf(R,K)
`
`where © denotes bit-by-bit addition modulo 2.
`
`As remarked before, the input of the first iteration of the calculation is the permuted input
`block. If L'R’ is the output of the 16th iteration then R'L’ is the preoutput block. At each
`iteration a different block K of key bits is chosen from the 64-bit key designated by KEY.
`
`9
`
`
`
`|
`
`
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 11
`Page 11
`
`

`

`FIPS PUB 46
`
`With more notation we can describe the iterations of the computation in more detail. Let KS
`be a function which takes an integer n in the range from 1 to 16 and a 64-bit block KEY as
`input and yields as output a 48-bit block K, which is a permuted selection of bits from KHY.
`That is
`
`(2)
`
`K, = KS(m, KEY)
`
`with K, determined by the bits in 48 distinct bit positions of KEY. KS is called the key
`schedule because the block K used in the n’th iteration of (1) is the block A, determined by (2).
`
`As before, let the permuted input block be LR. Finally, let Z, and R, be respectively L and R
`and let L, and R, be respectively L' and B' of (1) when LZ and # are respectively L,_, and R,_,;
`and K is K,; that is, when 7 is in the range from 1 to 16,
`
`(3)
`
`Ly = Ris
`RE, = En-1 Of (Rat Ky)
`
`The preoutput block is then Ryghisg
`
`The key schedule KS of the algorithm is described in detail in the Appendix. The key schedule
`produces the 16 K, which are required for the algorithm.
`
`Deciphering
`
`The permutation /P~'! applied to the preoutput block is the inverse of the initial permutation
`IP applied to the input. Further, from (1) it follows that:
`
`(4)
`
`R=L'
`L=R' Of’, K)
`
`Page 12
`
`Consequently, to decipher it is only necessary to apply the very same algorithm to an enciphered
`message block, taking care that at each iteration of the computation the same block of key bits
`K is used during decipherment as was used during the encipherment of the block. Using the
`notation of the previous section, this can be expressed by the equations:
`
`(5)
`
`Ray =n
`Lin = RE, © flLn, K,)
`
`where now i, £4, is the permuted input block for the deciphering calculation and L, Ry is the
`preoutput block. That is, for the decipherment calculation with Ry, Ly, as the permuted input,
`K,,; is used in the first iteration, K,, in the second, and so on, with K, used in the 16th
`iteration.
`
`The Cipher Function f
`
`A sketch of the calculation of f( #, K) is given in figure 2.
`
`10
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 12
`
`

`

`
`
`
`
`R (32 BITS)
`
`FIPS PUB 46
`
`
`
`
`
`
`
`[eos
`
`(+)
`
`32 BITS
`
`FIGURE 2. Calculation off (R, K).
`
`Let E denote a function which takes a block of 32 bits as input and yields a block of 48 bits as
`output. Let E be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are
`obtained by selecting the bits in its inputs in order according to the following table:
`
`EBIT-SELECTION TABLE
`
`32
`
`1
`
`a
`
`3
`
`4
`
`5
`
`Thus the first three bits of H( 2) are the bits in positions 32, 1 and 2 of R while the last 2 bits
`of ECR) are the bits in positions 32 and 1.
`
`11
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 13
`Page 13
`
`

`

`FIPS PUB 46
`
`Each of the unique selection functions S,, S,,...,S., takes a 6bit block as input and yields a4.
`bit block as output and is illustrated by using a table containing the recommended S;:
`
`Si
`
`Column Number
`
`No. Oo1 238
`0
`14
`4
`138
`1
`1
`0
`15
`7
`4
`2
`4
`1
`14
`8
`3
`16
`12
`8
`2
`
`4°55
`2
`15
`14
`2
`18
`6
`4
`9
`
`6
`11
`18
`2
`i
`
`7
`8
`21
`11
`7
`
`8
`3
`10
`15
`6&6
`
`9
`10
`6
`12
`11
`
`10
`6
`12
`9
`8
`
`11
`12
`11
`7
`14
`
`12
`5
`9
`3
`10
`
`138
`9
`5
`10
`0
`
`15
`7
`8
`O
`
`14
`O
`3
`5
`6
`
`If S, is the function defined in this table and B is a block of 6 bits, then S, (B) is determined as
`follows: The first and last bits of B represent in base 2 a numberin the range 0 to 3. Let that
`numberbe i. The middle 4 bits of B represent in base 2 a number in the range 0 to 15. Let that
`numberbe j. Look up in the table the number in the ?’th row and j’th column. It is a number
`in the range 0 to 15 and is uniquely represented by a 4 bit block. That block is the output
`S,(B) of S, for the input B. For example, for input 011011 the row is 01, that is row 1, and the
`column is determined by 1101, that is column 18. In row 1 column 13 appears 5 so that the
`output is 0101. Selection functions S,, Sy,...,S,of the algorithm appear in the Appendix.
`
`Page 14
`
`The permutation funetion P yields a 32-bit output from a 32-bit input by permuting the bits of
`the input block. Such a function is defined by the following table:
`
`P
`
`7
`12
`Lo
`18
`8
`27
`13
`il
`
`20
`28
`23
`31
`24
`3
`30
`4
`
`21
`17
`26
`10
`14
`9
`6
`20
`
`16
`29
`1
`5
`2
`32
`19
`22
`
`The output PCL) for the funetion P defined by this table is obtained from the input L by
`taking the 16th bit of Las the first bit of P(L), the 7th bit as the second bit of P(L), and soe on
`until the 25th bit of L is taken as the 32nd bit of P(L). The permutation function P of the
`algorithm is repeated in the Appendix.
`
`Now let S,,..., S, be eight distinct selection functions, let P be the permutation function and
`let & be the function defined above.
`
`To define f(R, K) we first define B,,..., By to be blocks of 6 bits each for which
`
`(6)
`
`B,B,...B,=K PE(R)
`
`The block f(R, K) is then defined to be
`
`(D
`
`P(S(By)S2(B;) ... S9( Bx)
`
`12
`
`,
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 14
`
`

`

`
`
`
`
`
`
`
`
`
`Thus K ®E(R) is first divided into the 8 blocks as indicated in (6). Then each H;is taken as an
`input to S; and the 8 blocks S,(8,), S.(B,), ..., Ss(.B,) of 4 bits each are consolidated into a
`single block of 32 bits which forms the input to P. The output (7) is then the output of the
`funetion f for the inputs # and K.
`
`FIPS PUB 46
`
`13
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 15
`Page 15
`
`
`
`
`

`

`
`
`PMC Exhibit 2095
`PMC Exhibit 2095
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 16
`Page 16
`
`
`
`

`

` The choice of the primitive functions KS, S,, ..., Sg and P is critical
`
`APPENDIX
`
`PRIMITIVE FUNCTIONS FOR THE
`DATA ENCRYPTION ALGORITHM
`
`FIPS PUB 46
`
`to the strength of an
`encipherment resulting from the algorithm. Specified below is the recommended set of functions,
`describing S,, ... S, and P in the same way they are described in the algorithm. For the
`interpretation of the tables describing these functions, see the discussion in the body of the
`algorithm.
`
`The primitive functions S,,..., Sg are:
`
`:
`
`-
`*
`
`Sy
`
`11
`18
`2
`1
`
`8
`+441
`11
`7
`
`16
`8
`6
`10
`12
`158
`5 Ti
`
`Se
`
`9
`4
`i4 12
`#%t
`5
`2
`11
`
`S3
`
`7
`0
`8
`6
`
`144
`0
`4
`15
`
`#4
`15
`1
`12
`
`18
`7
`14
`8
`
`1
`4
`8
`2
`
`1
`15
`818
`0
`14
`18
`8
`
`14
`8
`7
`4
`7 Wt
`10
`1
`
`9
`0
`10
`0
`7
`18
`4
`6
`18
`110 18
`
`14
`9
`9
`0
`
`2
`14
`18
`4
`
`15
`10
`8
`
`6
`3
`8
`6
`
`18
`8
`66
`16
`
`14
`ll
`~=6©9)~6
`0
`
`18
`10
`8
`
`3
`5
`60
`6
`
`6
`6
`612
`10
`
`15
`2
`6
`9
`
`tl
`2
`4
`15
`
`8
`4
`15
`9
`
`6
`15
`«11
`1
`
`8
`8
`18
`4
`
`15
`6
`3
`8
`
`5&5
`10
`0
`7
`
`S4
`
`1
`2
`11
`4
`
`1
`4
`16
`9
`
`9
`0
`C7
`18
`
`10
`38
`18
`8
`
`Ss
`
`6
`12
`9
`8
`
`2
`1
`12
`7
`
`12
`11
`7
`14
`
`18
`10
`6
`12
`
`7
`14
`12
`
`5
`9
`38
`10
`
`12
`6
`9
`0
`
`11
`12
`5
`11
`
`9
`56
`10
`0
`
`0
`9
`8
`5
`
`4
`11
`10
`6
`
`0
`38
`5
`6
`
`56
`t1
`2
`14
`
`2
`15
`14
`2
`
`7
`8
`9
`18
`
`10
`6
`15
`8
`
`8
`#1
`#7
`12
`
`18
`8
`1
`15
`
`12
`56
`2
`14
`
`2
`F
`ht
`4
`
`8
`2
`8
`5
`
`15
`4
`5&5 I 12
`12
`1
`10 4 9
`14 5
`11
`12
`7
`2
`i4
`
`0 1 8
`18
`15
`38
`5&
`8
`6
`11
`#7 10
`1
`4
`212
`9
`8
`6
`38
`0 1 10
`5
`1
`18
`