`
` d was N3
`
`
`
`7
`
`197
`
`FEDERAL WFQWMATWN
`PWOCEfifiWG fiTfiNDRWWfi PUfiLWATWN
`
`IWW’ JANUARY :15
`
`"Maw 3;» mw
`
`(“SEWER
`
`
`
`CATEGORY: ADP OPERAmefi
`
`SUBCATEGOR‘Y: COMPUTER 3mm
`
`Apple v. PMC
`|PR2016-01520
`Page 1
`
`PMC Exhibit 2145
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 1
`
`
`
`TNS materiai may be protected by {mm/right law {Title ’3'? U8. (Jamie)
`
`Mfg. fiWfiPARTMfiNT (W {WMM‘EMWM w MEN TL. Rimmafimm Smmmry
`
`Efiwmd (A). mem {2?er Emma’th
`
`Eh. mm Auekermfiwhmmm Amigmm memm Mir Edema? mm? WMWng
`
`NA“ ‘EQNAL BUREAU ("W STANHARHS m Emmfi Am‘flfimg Acmw Haimmmr
`
`
`
`MWQWOM
`
`Infmmmtmh Processing Smndmwia Pubiicatkm germs; of the Nmicmal
`The Federal
`Bumw of Standards m the official pubh 1mm“ refining “to Stamimwia adopted and prm’mfl-
`fixated Luigi‘s!“ the provigmrm of Pubiia‘ Law 8%306 (Broom Bi“) and! under Part: 6 of Time ‘15,
`Ted“ of Fwirfiet'a} Regulatiomg. “Phage zegmmm and (éxevntive mandates; have: given the
`Secretary at“ Cmnmmwe én‘xpormnt mapmmi‘mlitim for impnwmg the utilizaafizm amd mmxm
`agoment {31‘ camputwa mm mmflmat‘zc dam pmmmmg wra‘temta in film Federal Gmfwnmemtm
`To 'm‘ry out the Swwmry’a r‘wgmmibilitm& the NBS, “Waugh its; lumith for (ifompumr
`Seémmes and "l‘evhnaiugy, px‘avidea Eemiemhip,
`technica} guhiamte, and mmniit'xzktion 0?
`government Mfm‘m m the dovehmment M techmmfl Ktlidfliifléfl and mmuiamis in these,
`su‘em‘
`
`
`The: aerim i8 med to announce Fedm‘m Enf‘m‘zmttkm I’mw ginfi St‘zmdanisx and £10
`provide Sicfifidfll‘dfi
`in’ibrmzmon of general EHWVML and an index (if relevant atamiarda
`pubficatimm and mpevif‘ica‘fiimm Mikflicmimm Wm anmmmw m‘lwmon of Mamiardg provide
`the mammary policy, adruinmtrative, ami guidance mfkmmfltkm fm‘ effective stamim‘dm
`impiemenmtimx and mm. The technical Speifiifi ‘mimm 3f the Mamim‘d 21m ummfly amgzciwd
`(,0 Wm pubiimxmm, otherwiae a z‘e’fl‘wmme :50?er is citgd,
`
`infornmthm P’W‘aneming Stmuianw and Pubiicatimm are
`Cummenm Hovering Fmim‘ai
`
`welmmwi, zmd {should be add”?de m the A? “Mam Diwcmr {01‘ ADV Er‘ammlmdw Inmvim‘ie
`far {kmnmtm‘ Sciences and Technology “Eatimml Burma: 0%“ Stamiardm, Wmhingmm, DC,
`20234. Such comments; Wm be mmm‘ (?0k12‘~;id@r0¢‘i by NW3 01‘ fibrwmmimi m Hm X‘izmmzmible
`activity ‘
`:s appmpriatu
`
`E RN ICS’E‘ A MULER, Act 2T w; [.127meth
`
`Ahéflram
`
`The xelectviw 31.)},flécation uf tcvhnmhwiv-a} and related macmiuml mfl‘eg‘ruartm i5 am
`impm‘mnt nmpanfiibilifiy of every Fwierai m‘gjémixafim: in w'oviiiimr smegma/E39 Security to its
`A1,}? @yfimms. This?» {:mblicatiwn pmvidm a satmidmd to kw used by Wade *3} cu‘ganizmiona
`when threw m‘ggamizatioma fizpeciffir that cryptographic gn'otectiwn M m ha week fer Sensitive
`m‘ vahmbke configmm‘ dam” Promctmn M camputer data during tr‘mmmimitm hem/Nu}
`electnmic (*Qmpmwnm m‘ whim in tatomg‘e may b0, nemwaw m rmximmn the wufidentimlity
`31m}
`infiegflfiy 0f the Enfor‘nmmmx mpmmmtwi by that,
`(£21m The. Standard Specifies em
`encryptian zklg<>ritim1 which £3 to be it‘s’xplmmmted in em elw‘h‘onic {:Eeviwa for use in Federal
`ADP aysmmrg and networks.
`(“Hf algm‘mmx uniqueiy dm3119r3 (the n‘mihematical Stem
`required t0 t ‘mmf'm‘m mmgmter dam £11210 a Cl‘ypmg uphic ciphw. it. MM Specifies: the Steps
`required {,0
`trmmfomn the cipher bzwk m its orig-5mg} (mm. A device performing this»;
`Mauritian may 239 (used in many mppiicatioma awzm WhBWJ Hyptogmphic dam 1n‘0twticm is;
`newed. Wimm the mumxt of a €01.22:
`security pmgmn": comprmmg phwmai wmrity
`pmwdurm, goofi informmkm mémaggaamem wmtfims and cmmmtm 5537542391mnetwm‘k mama
`cmxtmfia, the I)»:th Encryption Stamdzwd it»: being: mm available fur mac: by Fm‘iel‘ai
`agencies,
`
`Key Wm‘ds: ADP swuwifiy; cmnputer Security; mwryptian; Fedmai fni‘m‘numiun Pmceming
`Standard.
`
`NM. Ewe“. Wand. {Ufikh Fad,
`
`info“ Macaw. Marni. mm mm PUB) 46, 1‘? pagm (1977)
`COHEN: PTPPAT
`
`
`
`For male by the szamzié ’E‘whh
`51 fnfm‘mutémw Sm‘vuw {343, {iopm‘tmem of CUHHI’WH‘B,
`fiprmgfiem. Virgin in 22 i m
`
`
`
`
`
`I
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 2
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 2
`
`
`
`
`
`1977 January 15
`
`ANNOUNCING THE
`
`
`
`DATA ENCRYPTION STANDARD
`
`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 112?), Executive Order 11717
`{38 FR 12315, dated May 11, 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 Encryption 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 (“0”s 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 error detecting bits are set to make the parity of each 8-bit byte of
`the key odd, i.e., there is an odd number of “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 encipher the 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 encryption 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 encrypting 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 decipher the 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 can 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 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 3
`
`Federal Information
`
`Processing Standards Publication 46
`
`FIPS PUB 46
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`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, or the
`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) may be 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 the first case, the key
`must be available at the transmitter and receiver simultaneously during communication. In the
`second case, the key must be maintained and accessible 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 (LSI) “chips” in individual electronic packages, devices built from Medium Scale
`Integration (MSl) electronic components, or other electronic devices dedicated to performing the
`operations of the algorithm. Microprocessors using Read Only Memory (ROM) or micropro-
`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, DC. 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
`comply with these Federal regulations.
`
`2
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 4
`
`
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`
`
`
`
`Fl PS I’U B 46
`
`Patents: Crytographic devices implementing this standard may be covered by US. and foreign
`patents issued to the International Business Machines Corporation. However,
`lBM has granted
`nonexclusive. royalty-free licenses under the patents to make, use and sell apparatus which
`complies with the stani‘lard. The terms, conditions and scope of the licenses are set out in notices
`published in the May 13, 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. 17”).
`
`Alternative Modes of Using the DES: The “Guidelines for Implementing and Using" the Data
`Encryption Standan” 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
`“exclusiveor” logic operation.
`in order to assure that the enciphering‘ device and the deciphering
`device are synchronized, their inputs are alwaye set to the previous 64 bits of cipher that were
`transn‘iitted or received. This second mode of using; the encryption algorithm is called the cipher
`feedback (CF‘B) mode. The electronic codebook mode generates blocks of (i4 cipher bits. The cipher
`in
`feedback mode renerates ci )her havin r the same number of hits as the ilain text. Each block of
`
`cipher is independent of all othere when the electronic codebook mode is uned 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 FlPS PUB. it applies to all Federal ADP systems and associated telecommimications
`networks under develoiinnent as well as to installed systems when it 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 developii’ig‘ and issuing; additional
`technical guidelines on conmuter 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
`(DES) {affixed}.
`
`Cross Index:
`
`information Processing Standard (FlPS 46) Data Encryption Standard
`
`a. FlPS PUB ill, “Guidelines to ADP Physical Security and Risk Management”
`
`b. FlPS PUB 39, “Gloeeary for Computer Systems Security”
`
`c. FlPS PUB 41, “Computer Security Guidelines for implementing}; the Privacy Act of 1974”
`7‘4
`
`d. FII’S PUBM, “Guidelines for Implementing and Using the Data Encryption Standard” (to
`be published)
`
`e. Other FIPS and Federal Stamiards are applicable to the innilementation and use of this
`standard. in particular, the American Standard Code for information lnterchzmge (Fll’S PUB l}
`
`3
`
`
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 5
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`
`
`
`
`li‘ll‘S PUB 46
`
`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, DC. 20234.
`
`Qualifications: The cryptographh algorithm simcified in this standard transforms a 64—bit binary
`value into a unique 64—bit binary value based on a 56bit
`'ariable. If the complete 64-bit input is
`used (i.e., none of the input bits should be predetermined from block to block) and if the 56bit
`'ariable is rmidomly chosen, no technique other than trying all possible keys using known input
`and output
`for
`the DES will guarantee finding the choaen key. As there are over
`70,000,000,000,000,000 (seventy quadrillion) possible keys of 56 hits, the feasibility of deriving a
`particular key in this way is extremely unlikely in typical threat environments. Moreover, if the
`key is changed frequently, the risk of this event is greatly diminished. However, uoei‘s should be
`aware that it is theoretically possible to derive the key in fewer trials (with a correspondingly lower
`probability of success depending on the number of keys tried) and should be cautioned to change
`the key as often as practi ‘211. Users must change the key and provide it a high level of protection in
`order to minimize the potential risks of its unauthorized computation or acquisition. The feasibility
`of con'iputing 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 normal life, cycle
`of its associated ADP equipment. The protection provided by this algorithm against potential new
`threats will be reviewed within five 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 and other cognizant Federal organizations. The new teclmologj a ’ailable
`at that time will be evaluated to determine its impact on the standard. In addition, the awareness
`of any breakthrough in technology or any mathemati ~al weakness of the algorithm will *ause NBS
`to reevaluate this standard and provide necessary revisions.
`
`Comments: Conunents and suggestions regarding this standard and its use are welcomed and
`should be addressed to the Associate Director for ADP Standards, lnstitute for Conniuter Sciences
`and Technology, National Bureau of Standards. Washington, DC. 20234.
`
`Waiver Procedure: The head of a Federal agency may waive the provisions of this Fll’S PUB after
`the conditions and justifications for the waiver have been coordinated with the National Bureau of
`
`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 necessary if classified communi *ations
`security equipment is to be used, Software implementations of this algorithm for 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 e Valuation
`does not require waiver approval. Implementation of other special purpose cryptographic algo-
`rithms in software for limited use within a computer system (eg, encrypting password files) or
`implementations of cryptographic algorithms in software which were being utilized in conniuter
`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 involved
`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.
`
`o
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 6
`
`
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`
`
`
`
`FIPS PUB 46
`
`Sixty days should be allowed for review and response by NBS. The waiver shall not be approved
`until a response from NBS is 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, Springfieki, Virginia 22161. Order by FIPS PUB
`number“ and 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 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 7
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 7
`
`
`
`
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 8
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 8
`
`
`
`
`
`FIPS PUB 46
`
`
`
`Federal Information
`
`Processing Standards Publication 46
`
`1977 January 15
`
`SPECIFICATIONS FOR THE
`
`DATA ENCRYP‘TION 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 transformations specified in the following algorithm.
`
`DATA ENCRYPTION ALGORITHM
`
`Introduction
`
`The algorithm is designed to encipher and decipher blocks 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 process is the reverse of
`the enciphering process. A block to be enciphered is subjected to an initial permutation IP, then to
`a complex key~dependent computation and finally to a permutation which is the inverse of the
`initial permutation IP". The key/«dependent computation can he 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 f is given in terms of primitive functions which are called the selection functions 8,- and the
`permutation function P. Si, P and KS of the algorithm are contained in the Appendix.
`
`The following notation is convenient: Given two blocks L and R of hits, LR denotes the block
`consisting of the bits of L followed by the bits of R. Since concatenation is associative B’le .
`.
`. BR,
`for example, denotes the block consisting of the bits of 81 followed by the bits of 82 .
`.
`. followed by
`the bits ofBg.
`
`Enciphering
`
`A sketch of the enciphering computation is given in figure 1.
`
`
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 9
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 9
`
`
`
`FIPS PUB 46
`
`INPUT
`
`INITEAL PERMUTATION
`
`INPUT
`
` PERMUTED
`
`K1
`
`K2
`
`R2=L1 (+3 {(R}, K2)
`L2=R1
`"WW-r“
`1*“
`~~~~~ -»-I~~~~~~ —--K
`:
`r
`‘
`1
`<+;M---...,.®._--..__¢
`"
`g‘fifimu.
`"flflm...
`
`J
`
`n
`
`_...___W~_l_
`
`V
`
`, ___
`
`
`
`
`
`INVERSE tmnAL PERM
`
`CUB“?
`
`FIGURE 1. Enc‘iphcring computation.
`
`8
`
`
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 10
`
`[‘fliihwmy' “L53
`
`
`0-'
`
`
`
`
`
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 10
`
`
`
`
`
`The 64 bits of the input block to be enciphered are first subjected to the following permutation,
`called the initial permutation IF:
`
`FIPS PUB 46
`
`58
`60
`62
`64
`57
`59
`61
`63
`
`5O
`52,
`54
`56
`49
`51
`53
`55
`
`42
`44
`46
`48
`41
`43
`45
`47
`
`it
`
`34
`36
`38
`40
`33
`35
`37
`39
`
`26
`28
`30
`32
`25
`27
`29
`31
`
`18
`2O
`22
`24
`17
`19
`21
`23
`
`10
`12
`14
`16
`9
`11
`13
`15
`
`“GOTWHOOG’Jfi-N
`
`That is the permuted input has bit 58 of the input as its 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, called the preoutput,
`is then
`subjected to the following permutation which is the inverse of the initial permutation:
`
`40
`39
`38
`37
`36
`35
`34
`33
`
`8
`7
`6
`5
`4
`3
`2
`1
`
`48
`47
`46
`45
`44
`43
`42
`41
`
`Q:
`
`16
`15
`14
`13
`12
`11
`10
`9
`
`56
`55
`54
`53
`52
`51
`5O
`49
`
`24
`23
`22
`21
`20
`19
`18
`17
`
`64
`63
`62
`61
`60
`59
`58
`57
`
`32
`31
`3O
`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 interchange of blocks, 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 one of 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 32 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 LR is defined by:
`
`(1)
`
`L’ =1?
`13': L $17311")
`
`where 63 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 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 11
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 11
`
`
`
`F‘IPS 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 Kn which is a permuted selection of bits from KEY.
`That is
`
`(2)
`
`K,, = K802, 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 Kn determined by (2).
`
`As before, let the permuted input block be LR. Finally, let Lu and 12,, be respectively L and R
`and let L, and RR be respectively L’ and R’ of(1) when L and R are respectively L,H and Rae,
`and K is K"; that is, when n is in the range from 1 to 16,
`
`The preoutput block is then RWLW.
`
`Ln : Riki
`n Z LII—1 @f‘(Rn-li Kn)
`
`The key schedule KS of the algorithm is described in detail in the Appendix. The key schedule
`produces the 16 Kn which are required for the algorithm.
`
`Deciphering
`
`The permutation IP’l 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‘ @f(L’,K)
`
`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:
`
`Rum] : Ln
`Luil : Rn @flLm Kn)
`
`where now R16 L16 is the permuted input block for the deciphering calculation and LORD is the
`preoutput block. That is, for the decipherment calculation with RIGL”, as the permuted input,
`K,6 is used in the first iteration, K15 in the second, and so on, with Kl used in the 16th
`iteration.
`
`The Cipher Function f
`
`
`
`A. sketch of the calculation off(R, K) is given in figure 2.
`
`10
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 12
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 12
`
`
`
`
`
`
`
`R (32 BITS)
`
`FIPS PUB 46
`
`
`
`L
`
`48
`
`":1
`
`
`
`
`
`32 BITS
`
`FIGURE 2. Calculation of'f(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:
`
`
`E BIT-SELEEETMJIABLE
`
`32
`4
`8
`12
`16
`20
`24
`28
`
`1
`5
`9
`13
`17
`21
`25
`29
`
`2
`8
`1O
`14
`18
`22
`26
`30
`
`8
`’7
`11
`15
`19
`23
`2’7
`31
`
`4
`8
`12
`16
`20
`24
`28
`32
`
`5
`9
`13
`17
`21
`25
`29
`1
`
`Thus the first three bits of E(R) are the bits in positions 32, 1 and 2 of R while the last 2 bits
`of EU?) are the bits in positions 32 and 1.
`
`11
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 13
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 13
`
`
`
`
`
`FIPS PUB 46
`
`., SS, takes a 6—bit block as input and yields a4»
`.
`Each of the unique selection functions 81, Se, .
`bit block as output and is illustrated by using a table containing the recommended SI:
`
`Si
`
`Column Number
`
`Row
`No.
`
`U
`1
`2
`8
`
`0
`
`14
`O
`4
`15
`
`1
`
`4
`15
`1
`12
`
`2
`
`13
`7
`14
`8
`
`3
`
`1
`4
`8
`2
`
`4
`
`2
`14
`13
`4
`
`5
`
`15
`2
`6
`9
`
`6
`
`11
`18
`2
`1
`
`7
`
`8
`1
`11
`7
`
`8
`
`3
`1O
`15
`5
`
`9
`
`10
`6
`12
`11
`
`.10
`
`6
`12
`9
`3
`
`11
`
`12
`11
`7
`14
`
`12
`
`5
`9
`8
`1O
`
`13
`
`9
`5
`10
`0
`
`14
`
`0
`3
`5
`6
`
`15
`
`'7
`8
`0
`13
`
`lfSI is the function defined in this table and B is a block of 6 bits, then 81(8) is determined as
`follows: The first and last bits of 8 represent in base 2 a number in the range 0 to 3. Let that
`number be i. The middle 4 bits of 8 represent in base 2 a number in the range 0 to 15. Let that
`number be 9'. Look up in the table the number in the *i’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) 0181 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 131 In row 1 column 13 appears 5 so that the
`output is 0101. Selection functions S1, 82, .
`.
`., S8 of the algorithm appear in the Appendix.
`
`The permutation function P yields a 32bit output from a 82bit input by permuting the bits of
`the input block. Such a function is defined by the following table:
`
`13
`
`7
`12
`15
`18
`8
`27
`13
`11
`
`20
`28
`23
`31
`24
`8
`3O
`4
`
`21
`1'7
`26
`10
`14
`9
`6
`25
`
`16
`29
`1
`5
`2
`32
`19
`22
`
`The output POL) for the function P defined by this table is obtained from the input L by
`taking; the 16th bit of L as the first bit of P( L), the 7th bit as the second bit of P(L), and so on
`until the 25th bit of L is taken as the 82nd bit of P(L). The permutation function P of the
`algorithm is repeated in the Appendix.
`
`., S8 be eight distinct selection functions, let P be the permutation function and
`.
`Now let 8;, .
`let E be the function defined above.
`
`To defineflR, K) we first define Bi, .
`
`. ., B8 to be blocks of 6 bits each for which
`
`(6)
`
`BIBZ...88:KEBE(R)
`
`The blockflR, K) is then defined to be
`
`(7)
`
`P(S;(Bi)Sg(Ba).-.Sg(Bx))
`
`12
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 14
`
`
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 14
`
`
`
`
`
`Thus K @EU‘?) is first divided into the 8 blocks as indicated in (6). Then each 8; is taken as an
`input to S,- and the 8 blocks 81(81), 82(32), .
`. ., 88(88) of 4 bits each are consaolidated into a
`single block of 32 bits which forms theinput to P. The output ('7) is then the output of the
`functionffor the inputs R and K.
`
`FEPS PUB 46
`
`
`
`18
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 15
`
`
`
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 15
`
`
`
`
`
`PMC Exhibit 2145
`
`Apple v. PMC
`|PR2016-01520
`
`Page 16
`
`PMC Exhibit 2145
`Apple v. PMC
`IPR2016-01520
`Page 16
`
`
`
`
`
`APPENDIX
`
`PRIMITIVE FUNCTIONS FOR THE
`
`DATA ENCRYPTION ALGORITHM
`
`FIPS PUB 46
`
`t0 the Strength of an
`The choice of the primitive functions KS, 8:, ..., S8 and P is criticafl
`encipherment resulting from the algorithm. Specified be10w is the recommended Set of functions,
`describing SI, ..., 88 and P in the same way they are described in the algorithm. For the
`interpretatknl of the talfles describhig these furufijons, see the (fiscusskni
`in the tuxiy 0f the
`aigorithm.
`
`The primitive functions 8,, .
`
`. 1, SS, are:
`
`
`
`
`S]
`
`11
`13
`2
`1
`
`8
`1
`11
`’7
`
`14
`9
`4
`15
`
`15
`3
`0
`13
`
`4
`15
`1
`12
`
`1
`13
`14
`8
`
`13
`7
`14
`8
`
`8
`4
`7
`10
`
`9
`0
`4
`13
`
`1
`4
`8
`2
`
`14
`7
`11
`1
`
`14
`9
`9
`O
`
`2
`14
`13
`4
`
`6
`15
`10
`3
`
`15
`2
`6
`9
`
`11
`2
`4
`15
`
`6
`3
`8
`6
`
`3
`4
`15
`9
`
`3
`8
`13
`4
`
`15
`6
`3
`8
`
`3