`
`
`
`2.x
`
` Vi
`mm mm
`
`fingermdm FIPS PUB 46
`197'? JANUARY “15
`
`FEDERAL. ENFORMATEQN
`PRQCESSHNG STANDARDS PUELICAWQN
`
`REAFFIRMED
`1&38 JANUARY 22
`
`
`
`FiPSFUR45-5
`
`
`
`Unified Patents Inc. Ex. 1015, pg. 1
`
`Unified Patents Inc. Ex. 1015, pg. 1
`
`

`

`M
`
`v.5. {DEPARTMENT OF COMMERCE, C. William Verity, Secrefmy,
`
`I
`
`NA'HONAL BUREAU OF STANDARDS, Emast Amman Dirmor
`
`FGWWQM
`
`Tm Federal Information Processing Standardg Publication Swim; of the: National Human: of
`Standards (NBS)1s Ehe cfficial publiamiuxx miating to stanéards and gu£detmes adopted 333:3 proxmm
`,
`gamd widest that pmvigiom of Smtion 111(d) of the: Fedaral Property and ‘admmistmtive Serviws :i
`Act of 1949 as ammdmi by the Compxums: Security Act; cf 198'! Public Law 100—235 Them man» , , V ,
`dates have: giwm the: Secrmary 0f Commerce. and NBS impartant rcspmnsibflities forImprovmg the:
`utflimtion and mazmgamemt of mmputer and related mmmmmunicatiam sygtams in the: Fefiesmi
`Gcavazmmem: The NBS through its Institum for Computer Scimcas and Tachnoiogy pmviciem
`Iaadcrship, tetahnical gmdanm, and cmrdmatian of Gavemmesm effortsm the deveflopnmm (Bf
`standards am: guidaiinas111 these: areas.
`
`Commants cancm’ning Fedaml Information Processing Standards Publications aw weimméd ,
`and should be acidmssed to the: Director, Institute: for Camputcr Scicnws and Tackmolagy? National ,
`Bureau 0f Standards, Gmthargburg, MI?) 20899
`,
`
`'
`,:
`
`‘
`
`James H. Burmws, Director
`Institute: for Compute-,3: Sciwczm am} Taclmology
`
`Abstract.
`
`Tim mlcctivc appiisatian of technological and mlatcd procaduml safeguazda {a an important rmpomibility of may '
`Fadcml mganizmion In providing adequate: samrity to its ADP systcma. This publicatiun provides a standard m be used by
`Fatima} arganizmians when them organizations specify that crypmgmphic pmmctian m to be m for mnsitiva m: valuabic
`camputcr dam. Pmtwticm 0f camputar data during transmission betwwn electmnic compozmnm (22‘ while‘m ammga may in:
`new :0 maintain the: confidentiality and mmgn‘ty of the: information mprmntad by that dam. The: Standard specifim an
`encryptim aigorithm whichas to be impiemanmdm an ammonia davicee for um in Fadgaml M)? systems and networlm The:
`adgomhm uniquely dcfinm the mathematical scape: rmmwd to maximal computer dam mm a crypmgmphic ciphm' It 211m
`spccffim the swaps; {exquimi ta transfarm the cipher back to its uriginal form. A dwica pufforming mm algorithm my 13% used
`in many applications areas Wham cryptographic (Eats memories: is nmw. Within the comma 9f :1 total :xccurity 13:0ng
`comprising phyaical maturity praccdurcs, good infarmafiou magamfint pmcticm and compumr system/metwmk 3cm
`centrols, the: Dam Encryptiw Standard is being mafia availabke; for use by Fedaral agmcim. This mvision superscdca
`FII’S 46.
`
`Key Worda: ADP wantiry; compumr wcutity; cncxypn'ou; Federal Inmrmation 32’}:ng Standard.
`
`Natl. Bur. Slaw. (113.) Fed. Info. Prawns. Stami Pub]. (FIPS PUB) 464, 16 pagea
`(1988)
`COHERFH’FAT
`
`Fm sale by the National Tachnical Infomtiou Service, US. Ditpammnt of Commune, Springfiald, VA 22161.
`
`'
`
`,
`
`‘
`
`
`
`Unified Patents Inc. Ex. 1015, pg. 2
`
`Unified Patents Inc. Ex. 1015, pg. 2
`
`

`

`
`
` Thie meiotic} may be protected by Copyright on: {Title “l? US Code)
`
`
`
`Federal Information
`
`Processing Standards Publication 46-1
`
`1988 January 22
`
`Announcing the
`
`DATA ENCRYP’I‘ION STANDARD
`
`FIPS PUB 46—1
`
`
`
`Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National Bureau of Standards after approval by
`the Secretary of Commerce pursuant to Section 111(d) of the Federal Property and Administrative Services Act of 1949 as amended by
`the Computer Security Act of 1987, Public Law 100-235.
`
`1. Name of Standard. Data Encryption Standard (DES).
`
`2. Category of Standard. ADP Operations, Computer Security.
`
`3.. Explanation. The Data Encryption Standard (DES) specifies an algorithm to be implemented in elec«
`tronic hardware devices and used for the cryptographic protection of computer data. This publication pro—
`vides a complete description of a mathematical algorithm for encrypting (euciphering) 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 cousists of 64 binary digits (“0”8 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, 5.6., there is an odd number
`of “1”3 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 al-
`gorithm 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.
`
`4. Approving Authority. Secretary of Commerce.
`
`5. Mahxtenance Agency.
`
`Institute for Computer Sciences and Technology, National Bureau of Standards.
`
`6. Applicability; This standard will be used by Federal departments and agencies for the cryptographic
`protection of computer data when the following conditions apply:
`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 date is not classified according to the National Security Act of 1947, as amended, or the Atomic
`Energy Act of 1.954, as amended.
`
`Unified Patents Inc. Ex. 1015, pg. 3
`
`Unified Patents Inc. Ex. 1015, pg. 3
`
`

`

`Ffl’S PUB 46-1
`
`However, Federal agenciss or dopartmcnts which use cryptographic dcviccs for protecting data classified
`according to cithcr of these: acts can use, those devices for protecting unclassifiod data in lieu of the standard.
`
`In addition, this standard may lac adoptcd and used by non-Federal Government organizations. Such use is
`encouraged when it provides the dcsircd security for commcrcial and private organizations.
`
`Data that is considered sensitive by tho responsible authority, data that has a high valuc, or data that repro-
`scnts a high value should be cryptographically protected if it is vulnerable to unauthorized disclosure or
`undetected modification during transmission or whilc in storage. A risk analysis should bc performed under
`the direction of a rcsponsiblc authority to dotcrminc potential throats. The costs of providing cryptographic
`protection using this standard as wcll as alternativc methods of providing this protection and their rcspcctivc
`costs should be projectcd. A responsiblc authority then should make: a decision, based on these analyscs,
`whether or not to use cryptographic protection and this standard.
`
`‘7. Applications. Data encryption (cryptography) may be utilized in various applications and in various
`cnvironmcnts. The specific utilization of encryption and the implementation of the DES will bc based on
`many factors particular to the computer systcm and its associated components. In general, cryptography is
`used to protcct data while it is being communicated between two points or whilc it is stored in a medium
`vulncrablc to physical theft. Communication accurity provides protection to data by cnciphcring it at the
`transmitting point and deciphering it at the receiving point. Filo socurity providcs promotion to data by
`enciphcring it whcn it is recorded on a storage medium and dcciphcring it when it is read back from the
`storage medium. In the first case, the key must be: available at the transmittcr and rcccivcr simultaneously
`during communication. In the second case, the key must bc maintained and acccssiblc for the duration of the
`storage poriod.
`
`8. Hardware Implementation. The algorithm specified in this standard is to bc implcmcntcd in computcr or
`rclatcd data communication devices using hardware (not software) technology. The specific implcmcntation
`may depend on several factors such as the application, the cnvironmcnt, tho technology used, ctc. Implcmom
`tations which comply with this standard include Large: Scale Integration (LSI) “chips" in individual cloc-
`tronic packages, devices built from Medium Scalc Integration (M81) clcctronic componcnts, or other
`electronic devices dedicated to performing the operations of tho algorithm. Micro-processors using Read
`Only Memory (ROM) or micro-programmcd dcviccs using microcode: for hardware lcvcl control instructions
`are cxamplcs of the latter. Hardwarc implementations of the algorithm which are tested and validated by
`NBS will be considered as complying with the: standard. Information about devices that have been validated
`and procedures for testing and validating equipment for conformance with this standard arc available from
`the National Bureau of Standards, Institute for Computer Sciences and Technology, Gaithcrsburg, MD
`20899. Software implementations in general purpose computers arc not in compliance with this standard.
`
`9. Export Control. Cryptographic devices and technical data regarding them arc suhjcct to Fodcral Gov-
`ernment cxport controls as specified in Title 22, Code of Federal Regulations, Parts 121 through 128. Cryptom
`graphic devices implementing this standard and technical data regarding them must comply with those
`Federal regulations.
`
`10. Patents. Cryptographic devices implementing this standard may be covered by US. and foreign
`patents issued to the International Businws Machines Corporation Howcvcr, IBM has granted noncxclusivc,
`royalty-frat: licenses undcr the patonts to makc, use and sell apparatus which complies with the standard. The
`terms, conditions and scope of the licenses arc set out in noticcs published in the May 13, 1975 and August 31,
`1976 issues of tho Official Gazctto of tho United States Patent and Trademark Officc (934 O. G. 452 and 949
`0.. G. 1717).
`
`11. Alternative Modes of Using tho DES. FlPS PUB Bl, DES Modcs of Operation, describes four diffcrcnt
`modes for using the algorithm described in this standard. These four modes are called the Elcctronic Code-
`booh (ECB) mode, the: Cipher Block Chaining (CBC) mode, tho Ciphcr Feedback (CFB) mode, and the
`Output Fccdback (OFB) mods. ECB is a direct application of the DES algorithm to encrypt and dccrypt
`data; CBC is an enhanced mode: of ECB which chains together blocks of cipher text; CFB uscs proviously
`
`M
`
`Unified Patents Inc. Ex. 1015, pg. 4
`
`Unified Patents Inc. Ex. 1015, pg. 4
`
`

`

`FIPS PUB 46-1
`
`generated cipher tcxt as input to tho DES to gcncratc psoudorandom outputs which are combined with the
`plain text to produce ciphcr text, thereby chaining togcthcr the resulting cipher text; OFB is identical to CFB
`except that the provious output of the DES is used as input in OFB while the provious cipher text is used as
`input in CFB. OFB does not chain the. cipher text.
`
`Implementation of (his standard. This standard became effective July 1977. It was rcaffirmcd in 1983
`12.
`and 1988. It applies to all Federal ADP systems and associated telecommunications notworks under develop-
`mcnt as well as to installed systems when it is determined that cryptographic protection is required. Each
`chcral department or agcncy will issue: internal directives for tho use of this standard by their operating units
`based on their data socurity rcquircmcnt dctcrrninations.
`
`NBS providcs technical assistance to Federal agencies in implcménting data cncryption through the issuance
`of gnidclincs and through individual rcimbursablc projects. The National Security Agency assists Federal
`departments and agoncics in communications security for classified applications and in determining specific
`security requirements. Instructions and regulations for procuring data processing cquipmcnt utilizing this
`standard arc inclndcd in the Federal information Resourccs Management Regulation (FIRMR) Subpart
`Mil-8.1114.
`
`13. Specifications. Federal Information Processing Standard (FIPS) 46-1, Data Encryption Standard
`(DES) (affixed).
`
`14. Cross Index.
`
`”‘1'"???msno.62»
`
`FIPS PUB 31, Guidelines to ADP Physical Security and Risk Managcmcnt.
`FIPS PUB 39, Glossary for Computer Systems Scourity.
`FIPS PUB 41, Computer Security Guidelines for lmplcmcnting the Privacy Act of 1974.
`FIPS PUB 65, Gnidclinc for Automatic Data Processing Risk Analysis.
`FIPS l’UB 73, Gnidclincs for Security of Computer Applications.
`FIPS PUB 74, Guidelines for Implementing and Using tho NBS Data Encryption Standard.
`FIPS PUB 81, DES Modes of Operation.
`FIPS PUB 87, Guidelines for ADP Contingoncy Planning.
`FIPS PUB 112, Password Usage.
`FIPS PUB 113, Computer Data Antlmntication
`0thcr FIPS and Federal Standards arc applicable to the implementation and use of this standard In
`particular, the Code for Information Interchange, "its Representations, Subsets, and Extensions (FIPS PUB
`1-2) and other related data storage media or data communications standards should be usedin conjunction
`with this standard. A list of currcntly approvcd FIPS may be ohtaincd from tho National Bureau of
`Standards, Institute for Compntcr Scicnccs and Technology, Gaithcrsburg, Ml) 20899.
`,
`
`15. Qualifications. The cryptographic algorithm specified in this standard transforms a 64bit binary Value
`into a unique 64—bit binary value hosed on a 56nbit variable. If the complete 64~bit input is used (in; 110116: 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 thoDES will guarantee
`finding the chosen kcy. As there are ovor 70,000,000,000,000,000 (seventy quadrillion) poSSiblc keys of 56 hits. ,
`the feasiblity of deriving a particular keyIn this way is extremely unlikely in typical threat environments
`Moreover, if the: keyis changed frequently, the risk of this event is greatly diminishcd However, users should
`be: aware that it is theoretically possible: to derive: tho key in fcwcr trials (with a correspondingly lower
`probability of success depending on the number of lrcys tried) and should bc cautioned to change tho key as
`often as practical. Users must change: tho key and provide it a high lcvcl of protection in order to minimize
`tho potential risks of'Its unauthorized computation or acquisition The feasibility of computing theenrrcct key
`may change with advancesin technology A more complctc dcscription of the strength of this algorithm
`against various throatsrs contained111 FIPS PUB 74, Guldclincs int Irn’plcrncntingand Using the NBS Data
`Encryption Standard
`When correctly implemented and properly used, this standard Will providc a high level of cryptographic
`promotion to computer data. NBS, supported by the tcclmical assistsncc of Government agcncios responsible
`
`Unified Patents Inc. Ex. 1015, pg. 5
`
`Unified Patents Inc. Ex. 1015, pg. 5
`
`

`

`FIPS PUB 46~1
`
`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 5 years to assess
`its adequacy (See Special Information Section). 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 technology available at that time will be evaluated to determine its
`impact on the standard. In addition, the awareness of any breakthrough in tcchnology or any mathematical
`weakness of the algorithm will cause NBS to reevaluate this standard and provide necessary revisions.
`
`16. Comments. Comments and suggestions regarding this standard and its use are welcomed and should be
`addressed to the National Bureau of Standards, Attm Director, Institute for Computer Sciences and
`Technology, Gaithersburg, MD 20899.
`
`1?. 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 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 communications security equipment is to be used. Software implementa-
`tions 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 evaluation does not require waiver approval. Implementation of other special purpose
`cryptographic algorithms in software for limited use within a computer system (e.g., encrypting password
`files) or implementations of cryptographic algorithms in software which were being utilized in computer
`systems before the efiective 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 is upgraded or redesigned to
`include general cryptographic protection of computer data. Waivers will be considered for devices certified
`by the National Security Agency as complying with the Commercial COMSEC Endorsement Program
`(CCEP) when such devices offer equivalent cost/performance features when compared with devices con-
`forming to this standard. Letters describing the nature of and reasons for the waiver should be addressed to
`the Director, Institute for Computer Sciences and Technology, as previously noted.
`
`Sixty days should be allowed for review and response by NBS. The waiver shall not be approved until a
`response {tom NBS is received; however, the final decision for granting the waiver is the responsibility of the
`head of the particular agency involved.
`
`In accordance with the Qualifications Section of this standard, reviews of this
`18. Special Information.
`standard have been conducted every 5 years since its adoption in 197?. The standard was reaffirmed during
`each of those reviews. This revision to the text of the standard contains only editorial and other nonsubstan-
`tive changes, mainly to update the reference list, provide current names and addresses, and supplemental
`information issued after 1977.
`
`19. Where to Obtain Copies. Copies of this publication are for sale by the National Technical Information
`Service, US. Department of Commerce, Springfield, VA 22161. When ordering, refer to Federal Informa-
`tion Processing Standards Publication 46—1 (FIPSPUBdéml), and title. Payment may be made by check,
`money order, or deposit account.
`
`Unified Patents Inc. Ex. 1015, pg. 6
`
`Unified Patents Inc. Ex. 1015, pg. 6
`
`

`

`
`
`Federal Information
`
`Processing Standards Publication 46-1
`
`1988 January 22
`
`SPECIFICATIONS FOR THE
`
`DATA ENCRYPTION STANDARD
`
`FIPS PUB 4&1
`
`
`
`The Data Encryption Standard (DES) shall consist of the following Data Encryption Algorithm to
`be implemented in special purpose electronic {lei/ices. These devices shall be designed in such a way
`that. they may be used in a computer system or networlc 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 hits altered so that the deciphering process is the reverse of
`the enciphering process. A block to he enciphered is subjected to an initial permutation 1?, then to
`a complex key-dependent computation and finally to a permutation which is the inverse of the
`initial permutation IP 1. 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 f is given in terms of primitive functions which are called the selection functions 81‘ and the
`permutation function P. S i, 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 hits of L followed by the bits of R. Since concatenation is associative 8182 .
`.
`. 83,
`for example, denotes the block consisting of the bits of 31 followed by the bits of 82 .
`.
`. followed by
`the bits of 88.
`
`Enciphering
`
`A sketch of the enciphering computation is given in figure 1.
`
`
`
`"Blocks are composed of bits numbered :5er left to right, i.e., the left most bit of a block is hit one.
`
`5
`
`Unified Patents Inc. Ex. 1015, pg. 7
`
`Unified Patents Inc. Ex. 1015, pg. 7
`
`

`

`Ffl’S I’UB 4&1
`
`
`
`ENPUT
`
`
`
`INITIAL PERMUTATIOWPD
`
`PERMUTED
`ENPUT
`
`
`
`
`
`
`OWEPSE lNlTIAL PERM )
`my 7
`1:“
`OUWTFEUT WWWM;
`
`}
`
`FIGURE 1. Encz‘pizering computatim’z.
`
`Unified Patents Inc. Ex. 1015, pg. 8
`
`Unified Patents Inc. Ex. 1015, pg. 8
`
`

`

`The 64 hits; of the input block to be enciphered are first subjected to the following permutation,
`cailed the initial permutation IP:
`
`FIPS PUB 46—1
`
`58
`60
`62
`64
`57
`59
`61
`63
`
`50
`52
`54
`56
`49
`51
`53
`55
`
`42
`44
`46
`48
`41
`43
`45
`47
`
`34
`36
`38
`40
`33
`35
`37
`39
`
`26
`28
`30
`32
`25
`27
`29
`31
`
`18
`20
`22
`24
`17
`19
`21
`23
`
`10
`12
`14
`16
`9
`11
`18
`15
`
`W—‘OOZDA‘AN
`
`5
`7
`
`That is the permuted input has hit 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
`86
`85
`34
`33
`
`8
`7
`6
`5
`4
`3
`2
`1
`
`48
`47
`46
`45
`44
`43
`42
`41
`
`If:
`
`16
`15
`14
`13
`12
`11
`10
`9
`
`56
`55
`54
`58
`52
`51
`50
`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 hit 40 of the preoutpnt block as its first hit, bit 8 as its
`secomi 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 preontput biock
`consisto, but for a final interchange of biocks, of 16 iterations of a calculation that is desseribed below
`in terms of the cipher function fwhich operates (in two blocks, one 01132 bits, and one of 48 bits, and
`produces a block of 32 bits.
`
`Let the 64 hits of the input block to an iteration consist of a 32 bit block [i followed by a 32 bit block
`It. 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~hit key. Then the output L‘R’ of an iteration with
`input LR is defined by:
`
`(I)
`
`L’ - 16
`R" = L ElafiRJk’)
`
`where 95’ denotes hitwby-bit addition moduio 2.
`
`As remarked bofoi‘a 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 biock K of key bites is chosen from the, 64—bit key degignated by KEY.
`
`Unified Patents Inc. Ex. 1015, pg. 9
`
`Unified Patents Inc. Ex. 1015, pg. 9
`
`

`

`FIPS PUB 116-1
`
`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 18 and a 84bit 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,,
`
`-‘- KS('n,KE'Y)
`
`with Kn determined by the bits in 48 distinct bit positions of KEY. K3 is called the key
`schedule because the block K used in the n’th iteration 0H1) is the block K" determined by (:3),
`
`As before, let the permuted input block be LR. Finally, let Li, and R” be respectively L and R
`and let Lu and R" be respectively L’ and R’ of(i) when L and R are respectively Ln , and RR»,
`and K is K”; that is, when n is in the range from 1 to 16,
`
`(8)
`
`Ln = Rn‘i
`Ru : L?i‘“l aafianh Kn)
`
`The preoutput block is then RmLm.
`
`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 [P ‘ applied to the preoutput block is the inverse of the initial permutation
`I1“ applied to the input. Further, from (1) it follows that:
`
`(4)
`
`R =L’
`L —, R' fiflL', K)
`
`Consequently, to decipher it is only necessary to apply the very same algorithm to an encéphered
`message block, taking care that at each iteration of the computation the same block of key bits
`K is used during deciphermont as was used during: the encipherment of the block. Using the
`notation of the previous section, this can he expressed by the equations:
`
`(5)
`
`Riki : [In
`Lnei r R71@flLniKnl
`
`where now Rm L“, is the permuted input block for the deciphering calculation and LOB0 is the
`preoutput block. That is, for the deeipherment calculation with R“; L16 as the permuted input.
`Km is used in the first iteration, K15 in the second, and so on, with K1 used in the 16th
`iteration.
`
`The Cipher Function 1?
`
`A sketch of the calculation off(R, Ki) is given in figure 2.
`
`Unified Patents Inc. Ex. 1015, pg. 10
`
`Unified Patents Inc. Ex. 1015, pg. 10
`
`

`

` (32 BITS)
`IW
`<0
`I
`
`48 BITS
`
`I:
`
`FIPS PUB 464
`
`
`C.
`K (48 BITS)
`J
`
`III III ‘I'ii' "II 'II' III III
`
`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 hits 01" Its output, written as 8 blocks of 6 bits each, are
`obtained by selecting the bits in its inputs in ordes' according to the following" table:
`
`E BI’I‘~SELECTION TABLE
`
`32
`4
`8
`12
`16
`20
`24
`28
`
`1
`5
`9
`13
`17
`21
`25
`29
`
`2
`6
`10
`14
`18
`22
`26
`30
`
`3
`7
`II
`15
`19
`23
`27
`31
`
`4
`8
`12
`16
`20
`24
`28
`32
`
`5
`9
`13
`17
`21
`25
`29
`1
`
`Thus the first three bits of EU?) are the bits in positions 32, 1 and 2 01' R while the last 2 bits
`of EU?) are the bits in positions 32 and I.
`
`Unified Patents Inc. Ex. 1015, pg. 11
`
`Unified Patents Inc. Ex. 1015, pg. 11
`
`

`

`FH’S PUB 46»!
`
`., SK, takes a 6-bit block as input and yields a4~
`.
`Each of the unique selection functions Sh Se, .
`bit block as output and is illustrated by using a table containing the recommended 8,:
`
`é:
`
`Column Number
`
`Row
`
`
`No.0123456777789101112131415
`215118310612
`0
`14
`4
`13
`1
`5
`9
`O
`7
`14
`2
`13
`1
`10
`6
`12
`11
`1
`0
`15
`7
`4
`9
`5
`3
`8
`2
`4
`1
`l4 8
`13
`6
`2
`11
`15
`12
`9
`7
`3
`10
`5
`0
`8
`15
`12
`8
`2
`4
`9
`1
`7
`5
`11
`3
`14
`10
`0
`6
`13
`
`lfSl 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 ol‘B represent in base 2 a number in the range 0 to 3. Let that
`number he i. The middle 4. bits ofB represent in base 2 a number in the range 0 to 15. Let that
`number bej. Look up in the table the number in the i’th row andj’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
`81(8) ofS, 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 13. In row 1 column 13 appears 5 so that the
`output is 0101. Selection functions 5,, SE,
`.
`.
`., Sex of the algorithm appear in the Appendix.
`
`The permutation function P yields a 32-bit output from a 32bit input by permuting the bits of
`the input block. Such a function is defined by the following table:
`
`P
`
`7
`12
`15
`18
`8
`27
`13
`11
`
`20
`28
`23
`31
`24
`3
`30
`4
`
`16
`29
`1
`5
`2
`32
`19
`22
`
`21
`17
`26
`10
`14
`9
`6
`w
`25
`
`The output P(L) for the function P defined by this table is obtained from the input L by
`taking the 16th bit ofL as the first bit of P(L), the 7th hit as the second bit of P( L), and so on
`until the 25th bit of L is taken as the 82nd bit of PULL The permutation function P of the
`algorithm is repeated in the Appendix.
`
`., SS 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 8,, .
`
`. ., Ba to be blocks of 6 bits each for which
`
`(6)
`
`8182...BS;K@E{R)
`
`The blockflR, K) is then defined to be
`
`(’7)
`
`P(SI(BI)SZ(BZ)«--SH(38))
`
`10
`
`Unified Patents Inc. Ex. 1015, pg. 12
`
`Unified Patents Inc. Ex. 1015, pg. 12
`
`

`

`Thus K GBEUB) is first divided into the 8 blockg as indicated in (6). Then each 81 is taken as an
`CL
`input to S,- and the 8 blocks 5108]), 32(82), .
`. ., $438) of 4 bits each are consolidated into “
`single block at" 32 him which forms the input to P. The output (7) is then the output of the
`function ffor the inputs R and K.
`
`FIPS PUB 46-1
`
`11
`
`Unified Patents Inc. Ex. 1015, pg. 13
`
`Unified Patents Inc. Ex. 1015, pg. 13
`
`

`

`Unified Patents Inc. Ex. 1015, pg. 14
`
`Unified Patents Inc. Ex. 1015, pg. 14
`
`

`

`APPENDIX
`
`PRIMITIVE FUNCTIONS FOR THE
`DATA EXNCRY PTION ALGORITHM
`
`FH’S PUB 46-1
`
`to the strength of an
`The choice of the primitive functiems KS, 8,, ..., 88 and P is critical
`encipherment 1031111ng from the algorithm. Specified below is the recommended set of functions,
`describing SI,
`.
`.
`., $8 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 St, .
`
`.
`
`., SS, are:
`
`S:
`
`11
`13
`2
`1
`
`8
`1
`11
`7
`
`14
`O
`4
`15
`
`15
`3
`O
`13
`
`4
`15
`1
`12
`
`1
`18
`14
`8
`
`13
`’7
`14
`8
`
`8
`4
`7
`10
`
`1
`4
`8
`2
`
`14
`7
`11
`1
`
`14
`9
`9
`O
`
`2
`14
`13
`4
`
`6
`15
`1O
`3
`
`15
`2
`6
`9
`
`11
`2
`4
`15
`
`8
`3
`8
`6
`
`8
`4
`15
`9
`
`3
`8
`13
`4
`
`15
`6
`‘1
`8
`
`3
`10
`15
`5
`
`9
`12
`5
`11
`
`1O
`6
`12
`11
`
`7
`0
`8
`F)
`
`6
`12
`9
`3
`
`2
`1
`12
`7
`
`52
`
`4
`14
`1
`2
`
`S3
`
`5
`10
`0
`7
`
`1
`2
`11
`4
`
`13
`8
`1
`15
`
`12
`5
`2
`14
`
`12
`11
`7
`14
`
`5
`9
`8
`1O
`
`9
`5
`10
`0
`
`13
`10
`6
`12
`
`7
`14
`12
`3
`
`12
`6
`9
`0
`
`11
`12
`5
`11
`
`0
`9
`3
`5
`
`4
`11
`10
`5
`
`O
`3
`5
`6
`
`5
`11
`2
`14
`
`2
`15
`14
`2
`
`7
`8
`0
`13
`
`10
`5
`15
`9
`
`8
`1
`7
`12
`
`10
`13
`13
`1
`
`7
`18
`10
`3
`
`2
`14
`4
`11
`
`12
`10
`9
`4
`
`0
`7
`6
`10
`
`13
`8
`6
`15
`
`12
`11
`2
`8
`
`1
`15
`14
`3
`
`9
`0
`4
`13
`
`14
`11
`9
`O
`
`S4
`
`3
`5
`0
`6
`
`0
`6
`12
`10
`
`6
`15
`11
`1
`
`9
`0
`7
`13
`
`1O
`8
`13
`8
`
`1
`4
`15
`9
`
`2
`7
`1
`4
`
`8
`2
`3
`5
`
`5
`12
`14
`11
`
`12
`10
`2
`'7
`
`4
`14
`8
`2
`
`$5
`
`4
`2
`1
`12
`
`1
`12
`11
`7
`
`7.
`4
`10
`1
`
`1O 11
`7
`13
`13
`7
`14
`2
`
`8
`1
`8
`13
`
`Se
`
`10
`4
`15
`2
`
`15
`2
`5
`12
`
`9
`7
`2
`9
`
`‘
`12
`8
`5
`
`6
`9
`12
`15
`
`8
`5
`3
`10
`
`8
`5
`15
`6
`
`U
`b
`7
`11
`
`13
`
`5
`0
`9
`15
`
`3
`15
`12
`0
`
`15
`10
`5
`9
`
`O
`9
`3
`4
`
`15
`1
`O
`14
`
`3
`13
`4
`1
`
`4
`11
`10
`7
`
`14
`0
`1
`b
`
`7
`11
`1‘3
`(l
`
`11
`l
`5
`12
`
`18
`3
`6
`10
`
`15
`9
`4
`14
`
`9
`6
`14
`3
`
`11
`8
`8
`18
`
`111
`8
`0
`:3
`
`5
`8
`11
`8
`
`Unified Patents Inc. Ex. 1015, pg. 15
`
`Unified Patents Inc. Ex. 1015, pg. 15
`
`

`

`FIPSIPUB 464
`
`4
`13
`1
`6
`
`13
`1
`7
`2
`
`11
`0
`4
`11
`
`2
`15
`11
`1
`
`2
`11
`11
`13
`
`8
`13
`4
`14
`
`14
`7
`18
`8
`
`4
`8
`1
`7
`
`15
`4
`12
`1
`
`6
`10
`9
`4
`
`S:
`
`0
`9
`3
`4
`
`8
`1
`7
`10
`
`13
`10
`14
`7
`
`12
`8
`3
`14
`1O 15
`9
`5
`
`9
`5
`6
`0
`
`7
`12
`8
`15
`
`Sa
`
`15
`3
`12
`10
`
`11
`7
`14
`8
`
`1
`4
`2
`13
`
`10
`12
`O
`15
`
`9
`5
`6
`12
`
`3
`8
`10
`9
`
`14
`11
`13
`0
`
`5
`2
`0
`14
`
`5
`0
`15
`‘3
`
`10
`15
`5
`2
`
`0
`14
`3
`5
`
`6
`8
`9
`3
`
`12
`9
`5
`6
`
`1
`6
`2
`12
`
`7
`2
`8
`11
`
`The primitive function P is:
`
`16
`29
`1
`5
`2
`32
`19
`22
`
`7
`12
`15
`18
`8
`27
`13
`11
`
`20
`28
`23
`31
`24
`3
`3O
`4
`
`21
`17
`26
`1O
`14
`9
`6
`25
`
`Recall that K", for 1 $11316, is the block of 48 bits in (2) of the algorithm. Hence, to describe KS, it is
`sufficient t