United States Patent
`Feistel
`
`c191
`
`3,798,359
`[ 11]
`[45] Mar. 19, 1974
`
`[54) BLOCK CIPHER CRYPTOGRAPHIC
`SYSTEM
`Inventor: Horst Felstel, Mount Kisco, N.Y.
`
`[75)
`
`[ 7 3) Assignee:
`
`International Business Machines
`Corporation, Armonk, N.Y.
`
`June 30, 1971
`[22) Filed:
`[21) Appl. No.: 158,360
`
`[52] U.S. Cl... ............... 178/22, 340/172.5, 340/348
`Int. Cl . .............................................. H041 9/00
`[ 5 I )
`[ 58] Field of Search ............ 178/22; 340/172.5, 348
`
`[ 5 6]
`
`3,657,699
`2,984,700
`3,170,033
`2,995,624
`2,917,579
`
`References Cited
`UNITED STATES PATENTS
`178/22
`4/1972
`Rocher.......................
`5/196 l
`Small .................................... 178/22
`2/1965
`Vasseur ................................ 178/22
`8/1961
`Watters ................................. 178/22
`12/l 959
`Hagel in ................................. 178/22
`
`Primary Examiner-Benjamin A. Borchelt
`Assistant Examiner-H. A. Birmiel
`Attorney, Agent, or Firm-Victor Siber
`
`[57)
`ABSTRACT
`A cryptographic system for encrypting a block of bi-
`
`nary data under the control of a key consisting of a set
`of binary symbols. The cryptographic system is uti(cid:173)
`lized within a data processing environment to ensure
`complete privacy of data and information that is
`stored or processed within a computing system. All
`authorized subscribers who are permitted access to
`data within the network are assigned a unique key
`consisting of a combination of binary symbols. The
`central processing unit within the computing network
`contains a complete listing of all distributed autho(cid:173)
`rized subscriber keys. All communications transmitted
`from terminal input are encrypted into a block cipher
`by use of the cryptographic system operating under
`the control of the subscriber key which is inputed to
`the terminal device. At the receiving station or central
`processing unit, an identical subscriber key which is
`obtained from internal tables stored within the com(cid:173)
`puting system is used to decipher all received ciphered
`communications.
`The cryptographic system develops a product cipher
`which
`is a combination of linear and nonlinear
`transformations
`of
`the
`clear message,
`the
`transformation being a function of the binary values
`that appear in the subscriber key. In addition to the
`transformation,
`the key controls various
`register
`substitutions and modulo-2 additions of partially
`ciphered data within the cryptographic system.
`13 Claims, 31 Drawing Figures
`
`36
`
`KEY
`
`REG.
`
`OSK
`
`MANGLER
`
`CONFUSER
`
`DIFFUSER
`
`30
`
`-32
`
`34
`
`INTERRUPTER
`
`Oracle-1043 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATHHEOMAR 19 1974
`
`3. 798.359
`
`MET 01 Of 25
`
`FIG. 1
`
`sw---
`
`PROCESSING
`CENTER
`
`KEY LIST
`SUBSCRIBER KEY (Kr)
`A
`B
`C
`
`10
`
`FIG. 2
`
`D
`
`1T
`
`D
`
`INVENTOR
`HORST FEISTEL
`
`BY l:fr:z ~~
`
`ATTORNEY
`
`Oracle-1043 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MAR 19 1974
`
`3,798,359
`
`SHEET 02 Of 25
`
`FIG. 3
`
`MANGLER
`
`CONFUSER
`
`30
`
`32
`
`34
`
`DIFFUSER
`
`/36
`
`INTERRUPTER
`
`318
`
`KEY
`
`REG.
`
`Oracle-1043 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATHHE0~11\n i 9 1874
`
`3. 798.359
`
`SHEET OJ Of 25
`
`FIG. FIG. FIG. FIG.
`4A 48 4C 40
`FIG.4 FIG. FIG. FIG. FIG.
`4E 4F 4G 4H
`
`FIG. FIG. FIG. FIG.
`4I 4J 4K 4L
`
`FIG. 4A
`
`(
`
`v80--...
`
`vBO,
`
`4~
`
`4~
`
`.......
`
`MANGLER
`\
`\
`
`~
`
`-
`~ .......
`44
`~ ~ ~ ~ /
`6DOOPC:
`
`I
`
`.
`
`275
`
`I
`I
`
`j
`
`30
`)
`I
`
`I j
`
`I
`
`I
`
`~
`
`I
`
`42A
`
`43A
`
`15(
`
`1~
`
`15{
`
`15(
`
`'
`
`275
`
`-
`
`--
`
`-
`
`-
`
`-
`
`133
`\
`
`j
`I
`I
`
`132
`)
`
`I
`I
`
`131
`)
`
`I
`
`13?
`
`I
`
`I
`
`Oracle-1043 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MAR 191974
`
`3. 798,359
`
`SHEET
`
`011 Of 25
`
`FIG. 48
`
`275
`
`81"-
`
`L---81----._
`
`82,
`
`INFORMATION
`IN
`
`275
`
`I
`
`I
`
`I
`
`I
`I
`
`_,.....,...._ __ \
`
`30
`\
`
`I 1
`
`I 7
`
`i--
`
`..__ J54
`15(
`
`15(
`
`15(
`
`I
`
`- _.___._ - ----1--J..... -
`
`,
`--,
`7
`
`I
`I
`
`I
`
`I
`
`Oracle-1043 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATHHEO MAR i 9 !874
`
`3. 798,359
`
`SHEET OS Of 25
`
`FIG. 4C
`
`275 v-83-----.
`
`v83"
`
`_.,,.-84""
`
`.,,,-84,
`
`I
`
`.
`
`f-..
`
`I
`
`275
`A
`
`I
`I
`
`I
`
`I
`
`I
`
`~
`
`I
`
`3,0
`I
`
`5~
`
`5f
`I
`
`, -
`
`,-
`
`,__
`
`-
`5~ ~ ~ ~ 60
`0 0 0 0/
`ti1d6~ 70
`
`I
`
`54
`
`,-
`
`5\5
`\
`
`,-
`
`, -
`
`53
`i---1 --
`-
`1 ~ ~ ~ [~'l6
`, ~~~~ 70
`- -
`
`53A
`
`54A
`
`55A
`
`56A
`
`57A
`
`58A
`
`59A
`16z
`
`60A
`
`169
`'---
`
`117 116 115 114
`
`l )
`
`I
`
`I
`
`I
`
`I
`
`16z
`
`16~
`
`16z
`
`16t_
`
`167
`'---
`
`162
`/
`
`-----
`
`121
`i
`
`I
`
`120 119 118
`l
`)
`)
`
`I
`
`I
`I
`
`I
`
`I
`
`.
`
`I
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`I
`
`Oracle-1043 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`SHEET 06 Of 25
`
`3,798,359
`
`90
`
`KEY
`
`INPUT I
`
`92
`
`\ 0
`
`-
`
`KEY
`EFFEC~~
`ROUTER
`100
`
`FIG. 4D
`
`I
`
`I 2i75 vB5""-
`
`I
`
`~
`
`-ti
`I
`
`'1
`
`vB5,
`
`62
`\
`
`,__
`
`6~
`
`--
`
`I
`
`,__
`~1
`
`I
`
`I
`
`MANGLER
`~ ,_ ~/30
`~~~~v
`.QdQ~
`,___+- 61A
`62A
`17( 17l
`r--,._,170
`
`64A
`
`63A
`171_
`
`1\2 T 1;0
`
`I
`
`I
`I
`
`113
`l
`
`I
`I
`I
`
`t--
`
`~ -
`
`I
`
`-
`
`-
`
`-
`
`-
`
`r--
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I ',
`
`! I
`
`93
`\
`
`0
`
`-
`
`-
`
`-·i..----
`
`Oracle-1043 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTEO~AR 19 1974
`
`3,798,359
`
`SHEET O 7 Of 25
`
`co NFUSER t 150
`
`150A
`
`2)5
`
`151
`
`152
`
`153
`
`FIG. 4E
`32"
`
`151A
`
`So
`
`G
`
`186
`
`1528
`
`1518
`
`S1
`
`G
`
`187
`
`I
`
`I I
`
`1508
`
`180
`
`I
`
`200
`
`200
`
`Oracle-1043 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATHHEOMAR i 91974
`
`3,798,359
`
`-
`
`-
`
`SHEET oa or 25
`-
`-
`
`-
`
`c-154 ,-J55 -156 -157
`
`/32
`I
`
`r--158 r--159 r--160 r--161
`
`FIG. 4F
`
`7
`
`I
`
`I
`
`-
`
`I
`
`I
`
`I
`
`-
`
`I
`
`I
`
`G
`
`1Ja
`
`I
`I
`
`I
`
`LJ
`
`G
`)
`189
`
`r-
`
`I
`
`G
`1Jo
`
`L
`I
`
`I
`LJ
`
`G
`
`1J1
`
`l/201----..
`
`v20k
`
`v202~
`
`v202--..__
`
`I
`
`.__ ---
`-
`
`I
`
`-
`
`-
`
`-
`
`-
`
`-
`
`---154A i---J55A r---J56A ~1578 t156B -155B 154B r---158A r--J59A r-160A ~1618 r160B "'-1598 158B
`•
`'
`'
`
`So
`
`I
`
`S1
`
`I
`
`So
`
`I
`
`s,
`
`I I
`
`1~0
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I
`
`1~1
`
`18z
`
`I
`
`7
`
`I
`
`Oracle-1043 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTEO~B ·191874
`
`-
`
`-
`
`-
`
`SHEET 09 Of 25
`-
`-
`
`-
`
`----163
`
`----164 ----165
`
`I
`
`'-162
`- -
`
`,,,..32
`
`/
`
`---166
`
`r---167
`
`----168
`
`'--169
`
`FIG. 4G
`~
`
`I
`
`----168A
`
`~1698 t1688
`
`-1678
`
`1668 I
`
`---162A --163A
`
`--...
`----1638 1628 ----166A -167A
`----164A' ~1658 r1648,
`,
`1
`1
`1
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`-
`
`So
`
`I
`
`S1
`
`I
`
`So
`
`I
`
`S1
`
`I
`
`•
`
`G
`)
`192
`
`r
`
`LJ
`
`G
`
`1J3
`
`r
`
`I
`
`G
`)
`194
`
`-
`
`I
`LJ
`
`G
`)
`195
`
`I I
`1~0
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`1~1
`
`182
`)
`
`1~3
`
`184
`\
`
`'
`
`I
`
`~
`
`,,-203-'\_
`
`AOh
`
`,,-204"'
`
`/204-----
`
`-
`
`-
`
`-
`
`-
`
`-
`
`I
`
`~
`
`I
`
`Oracle-1043 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`3. 798.359
`
`170
`
`171
`
`172
`
`173
`
`SHEET 10 OF 25
`
`FIG. 4H
`
`I I
`I I
`CONFUSER
`I I
`~ I I I
`
`170A
`
`171A
`
`So
`
`1718 1708~~32
`
`1728
`
`S1
`
`180
`
`181
`
`182
`
`183
`
`184
`
`185
`
`100
`
`G
`
`196
`
`205
`
`205
`
`G
`
`197
`
`11
`I I
`I I
`I I
`I I
`I I
`_J I
`I
`I
`I
`I
`_J
`
`-7
`I
`I
`I
`I
`I
`-7 I
`I I
`I I
`I I
`I I
`7 II
`I I I
`I I I
`I I:
`I I I
`I I 1
`I j I
`I IL
`I I
`
`Oracle-1043 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MAR 19 !974
`
`'
`
`.
`3. 798.359
`
`SHEET 11 OF 25
`-
`-
`-
`275
`
`~20°i
`
`}-200-{
`
`-
`
`34\
`
`~
`
`,-
`
`I
`1~225
`0
`
`f'---226
`
`......____227
`
`0
`
`0
`
`-
`r----228
`
`251
`
`2~2
`
`253
`254
`
`FIG. 4I
`
`I
`
`L
`
`INTERRUPTER-
`
`/
`
`/
`
`I
`
`I
`
`I
`
`.
`
`I
`
`I
`
`.
`
`I
`
`I
`
`;
`
`.
`
`I
`
`I
`
`I
`
`Oracle-1043 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`OATEl!Trr I'
`. r 1874
`I ~ L lJ ,1; 11 ,"', I j
`I .
`
`-
`
`I
`
`I
`
`SHEET 12 Of 25
`
`3,798,359
`
`DIFFUSER
`
`-
`
`I
`
`I
`
`-229
`
`r---230
`
`-231
`
`---232
`
`r-233
`
`i---234
`
`-
`
`-235 236-
`I
`251
`I
`252
`2i3
`
`0
`
`0
`
`0
`
`0
`
`0
`
`2~1
`
`254
`ds
`256
`
`2~7
`J
`258
`
`2is
`I
`260
`0
`
`/ 262
`
`.~
`
`0
`
`I
`
`:
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`:I
`
`:I
`
`I
`
`~ - - - - - - - - - . - - -~
`F I G. 4 J
`'"36
`
`I
`
`I
`
`Oracle-1043 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`3,798,359
`
`SHEET 13 Of 25
`
`/34
`
`1----237
`
`r---238
`
`f----239
`
`f--._240
`
`i------241
`
`-242
`
`'-243 244-
`
`I
`
`I
`
`I
`
`I
`
`I
`
`.
`
`I
`
`I
`
`I
`
`)
`
`251
`I
`252
`I
`253
`)
`254
`
`2~5
`
`21s
`
`257
`I
`258
`I
`259
`I
`260
`)
`261
`
`2J2
`
`2~3
`
`2~4
`}
`265
`1
`266
`
`2J7
`
`10
`
`2~9
`2ds
`0
`
`270
`
`-I
`
`'
`
`I
`
`;
`
`I
`
`0
`
`0
`
`10
`
`0
`
`~
`0
`
`I
`
`I
`
`I
`
`I
`
`~ - -
`
`FIG. _4_K_ - - -------3s- - - ~
`
`Oracle-1043 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MAR 191974
`
`,- ~205i
`
`-
`
`}--205--!
`
`-
`
`245~
`
`246--..
`
`247-
`
`I
`
`-
`
`I
`
`I
`
`I
`
`I
`
`.
`
`'.~
`
`0
`
`-
`
`0
`
`'-
`
`'-36
`
`'
`
`.
`.
`3,798,359
`
`-
`
`SHEEI
`
`/34
`
`111 Of 25
`-
`I I
`100---- I I
`I I
`KEY_....-
`I I
`EFFECT
`I I
`ROUTER
`
`248----
`
`7
`
`2~1
`
`11
`
`11
`
`-
`96
`\
`0
`
`11
`
`2~2
`
`2~3
`214
`
`215
`
`216
`
`2~7
`
`2~8
`
`219
`
`2~0
`
`2~1
`
`2~2
`
`2~6
`
`2~7
`2~8
`
`2~9
`
`2JO
`
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I
`I L_
`I
`I
`I
`2~3
`I
`264
`I
`l_
`I
`2~5
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`L _
`
`2~1
`212
`2)3
`I 2~4
`
`0
`_j
`----INTERRUPTER
`
`-
`
`97
`
`\0
`
`FIG. 4L
`
`Oracle-1043 p. 15
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`SHEET 1 S Of 25
`
`3. 798,359
`
`n-lNPUTS
`
`(M)---J=±===+====I'
`
`FIG. SA
`
`s
`
`MSK = E
`Es-1 = MS s-1
`K
`K K
`E sK1 = M
`
`POSSIBLE
`n {
`2 ! PERMUTATIONS
`
`FIG. 5 B
`
`DECODER
`
`ENCODER
`
`(E)
`
`175
`
`176
`
`Oracle-1043 p. 16
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`3,798,359
`
`SHEET 16 Of 25
`
`FIG.6
`
`FIG. FIG. FIG.
`GA GB GC
`
`FIG. FIG. FIG.
`GD GE GF
`
`FIG. 6A
`
`v81" 275
`~
`ff
`
`So
`
`I
`
`i---200~
`-
`
`-
`
`v201-
`
`S1
`
`I
`
`I
`
`•
`
`i---201~ 7
`------- I
`
`L --275 v-200-
`-
`
`"
`
`Oracle-1043 p. 17
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MA~ 19 1974
`
`.
`3,798,359
`
`.
`
`SHEET
`
`l 7 OF 25
`
`FIG. 6 B
`
`INFORMATION
`IN
`
`275
`
`v82---....
`
`v82-...__
`
`vB3,
`
`vB3.....___
`
`;
`
`;
`
`I
`
`I r I
`
`I -..___
`
`I
`
`I
`
`.
`
`I
`
`30
`\
`I
`
`•
`
`~ I
`
`-
`
`-
`
`I
`
`I
`
`I
`
`50
`
`5\1
`
`5~
`
`~
`
`0--
`
`49
`
`'.'._
`
`--
`--
`--
`10~ ~ L0J ~ ~ ~ ~ ~v
`4~ QQ 5
`_'51A _ Q Q Q-56A
`
`5~
`,__
`
`5\5
`,__,I
`
`53
`
`~
`
`,_ 56
`
`70
`
`I
`
`50A
`345
`
`51A
`
`317
`
`343
`
`I
`
`54A
`
`3~1
`
`35}
`
`55A
`355
`
`/-32
`3go
`
`341 ~\ ~~ ~~ ~? 349 350 ~~ h\
`I n~
`n
`GIG G G GIG G Gr- GIG GIG: GIG GIG ~
`
`356
`
`3~1
`
`l ~ ~ ~ ~ ~-= ~ _J
`
`e--------
`t:?
`F:::
`r::==
`~ ~ ~ r----_
`
`I
`
`~ I
`
`So
`
`S1
`
`v-202-
`•
`
`-
`
`-
`
`i----202-
`
`i----203~
`
`'
`
`-
`
`-
`
`-
`
`i----203-
`
`I
`
`-
`
`I
`
`~ I
`
`Oracle-1043 p. 18
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED ~:AR i 9 IS74
`
`.
`3,798,359
`
`.
`
`SHEET 18 OF 25
`
`FIG. 6C
`
`90 KEY
`
`INPUT
`
`275
`
`84
`
`85
`
`85
`
`57
`58
`
`59
`
`60
`
`62
`
`63
`
`So
`
`S1
`
`204
`
`204
`
`205
`
`205
`
`KEY
`EFFECT
`ROUTER
`100
`
`MANGLER
`CONTROL
`LINES
`
`r-
`I
`I
`I
`I
`I
`I
`I
`I
`-- J
`-7
`-7
`I I
`I I
`I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`1L
`
`301
`
`302
`
`~)1
`
`_J
`
`Oracle-1043 p. 19
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`SHEET 19 OF 2 5
`-
`
`2~5 t-200~
`
`2001'
`
`3,798.359
`
`-
`
`3\
`
`~201
`
`-
`
`}-201
`
`-
`
`'
`
`~226 -227 ~228 ~229
`
`I
`
`! ~225
`10
`-
`
`0
`
`0~
`
`0
`
`0
`
`-----230
`)
`251
`7
`252
`}
`253
`)
`254
`255
`0
`
`)
`
`I
`
`I
`
`I
`
`--
`
`-----231
`
`232---
`
`I
`
`2j6
`2;1
`0
`
`258
`
`·-
`.
`
`I
`
`I
`
`I
`
`I
`
`I
`
`FIG. 60
`
`I L
`
`/
`INTERRUPTER_.,.....,.
`
`\
`
`-
`
`Oracle-1043 p. 20
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATENTED MAR 19 1974
`
`3,798.359
`
`SHEET 20 OF 25
`
`DIFFUSER
`
`e-233 r-234 r-235 r-236 ~237
`
`r---238 ~239 r-240
`
`251
`
`}
`
`252
`I
`253
`
`d4
`I
`255
`I
`256
`
`2~7
`
`2~8
`I
`259
`
`2~0
`
`2~1
`I
`262
`263
`
`2~4
`I
`265
`266
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`I
`
`I
`
`I
`
`I
`
`•
`
`I
`
`I
`
`I
`
`I
`
`. .
`
`I
`
`I
`
`.
`
`I
`
`i :
`
`FIG. 6 E
`
`'36
`
`I
`
`7
`
`Oracle-1043 p. 21
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`--.---,-- - - . - -..... -
`~204
`204
`
`I
`
`SHEET 21 OF 25
`-----.- - --,---,-- -
`205i
`1-205i
`
`3. 798,359
`
`- - - I - _....;...._,_ +---+-- --+---I- - - - , I 251
`
`...,.-241 v--242
`
`i---243
`
`i---244 v-245 1----246 ~247
`
`-
`
`.
`
`'
`
`.
`
`~M----+---------+---+------+---+---------+----t----+--2_,__F-------j
`
`I
`
`0i----+---+--t----+--+---t--t-~2~_8-j
`l--------------<0 ____ ---t---+--+------+----t----+--2-'--~ 9-------j
`1-----------1G),....__-----t---+---i------r----t--2~J_O--,
`271
`~
`1-----------~6--------r---t--------f--t-~'----,
`-------------------0---+---+--t~2 J-2----,
`..... • ---------------,0------;--;--~2}_3---,
`
`r -- -----.-,"-3_6__ -~,'----IN TE-R-RU-PT_ER_
`
`l - - - - - - - - - - - - - - -10 ___ --+_2_,__~4-----1
`I
`-
`
`- -.....-,----,,,---
`I
`352 \
`I
`I
`0
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`)
`252
`}
`
`254
`)
`255
`)
`
`257
`)
`258
`)
`
`262
`l
`263
`)
`264
`)
`265
`I
`266
`)
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`L_
`
`KEY
`"'-
`'------EFFECT
`ROUTER
`100
`
`FIG. 6F
`
`Oracle-1043 p. 22
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`(D
`U1
`w
`0) .
`w . _,
`
`(D
`
`..:-
`-J
`CD
`
`<.D
`
`u,
`N
`
`r'T"\ -
`U? = rr,
`
`-.-,
`c::,
`N
`N
`
`;;.u
`::.(cid:173)
`==-=
`c:,
`
`rr,
`--1
`J>
`7:J
`
`:z::: -rr1
`
`)
`
`4 BITS
`
`CONVOLUTION REGISTERS
`
`MOD-2 ADDERS
`.
`
`I
`
`I
`
`\
`
`E
`
`H
`
`I )H -
`
`H
`
`H
`
`F ~
`
`..
`5 BITS
`5 BITS
`
`I
`
`G
`
`G
`
`F
`
`6 BITS
`
`7 BITS
`
`\
`
`4 BITS
`
`5 BITS
`
`B
`
`I
`
`j
`
`8 BITS
`
`(±)
`
`(±)
`
`3 BITS
`
`:!
`
`! . ! ' I
`
`B
`
`7 BITS
`
`B
`
`B
`
`o BITS
`,, -
`
`8 BITS
`
`8 BITS
`
`8 BITS
`
`8 BITS
`
`8 BITS
`
`8 BITS
`
`8 BITS
`
`ADDER
`MOD-2
`
`E
`
`REGISTERS
`ff SOURCE
`
`D
`
`r:CONVOLUTION REGISTERS
`
`FIG. 7
`
`c~
`
`.. ,
`
`I I I
`
`A
`
`~
`
`I
`
`A; I .
`
`A
`
`A
`
`C
`
`Oracle-1043 p. 23
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PATEiHEOMB i 9 1874
`
`3,798,359
`
`SHEET 2 3 OF 25
`
`FIG.8 FIG. FIG.
`SA 8B
`
`FIG. SA
`
`INPUT
`
`)o
`
`GATES ,---L--7
`
`0 ~ 12
`1
`15
`- - ~
`w
`2 ~ 7
`--g 3 ~ 10
`--u
`~
`:IE
`14 ~ 5
`15 ~ 8
`L ____ J'
`, - - - -7
`
`Lu
`I--+- o
`
`0 ~ 7
`1 ~ 2
`~
`~
`2 ~ 14
`o
`3 ~ 9
`u
`~
`z
`::E
`w
`14 ~ 8
`15
`'.::: 5
`L __ ~ _ _J'
`"s 1
`
`-
`
`----
`
`----
`
`SOURCE J
`
`REGISTERS
`
`INPUT
`INTERCHANGE
`CONTROL
`
`KEY SHIFT____,,,,(cid:173)
`REG I STE RS
`
`-- I --
`
`---i -
`~
`
`~
`I
`
`Oracle-1043 p. 24
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PAT ENT ED r,:Ak i 9 1374
`
`3. 798,359
`
`SHEET
`
`2l+ or 25
`
`CONVOLUTION
`REGISTERS
`
`FIG. 8 B
`-
`~ /
`~ -
`-
`~
`-
`~
`-
`I -
`~
`-
`~
`I
`I -
`~~
`I - ~ -
`
`I
`
`r
`
`I
`
`I
`
`I
`
`,__
`
`TO
`
`T1
`
`T2
`
`T3
`
`T4
`
`TS
`
`T6
`
`T1
`
`I
`
`I
`
`I
`
`I
`
`I
`
`•
`
`.
`
`I
`
`•
`
`I
`
`INPUT
`INTERCHANGE
`CON)ROL
`
`SELECTOR GATES
`\
`t
`
`G
`
`G
`
`G
`
`G
`
`- G
`
`. G
`
`G
`
`t
`
`{
`
`FROM
`KEY
`COUNTER
`
`KEY ROS
`
`KA
`
`KB
`
`KC
`KD
`
`KE
`KF
`
`KG
`
`KH
`
`SUBSTITUTION
`
`I CONTROL
`
`REGISTER
`
`1s
`
`' - - -
`
`' - - -
`
`' - - -
`
`' - - -
`
`' - - -
`
`' - - -
`
`-
`-----
`
`Oracle-1043 p. 25
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`SHEET 25 Of 25
`
`3,798,359
`
`0 1
`
`! 7 8
`
`ENCIPHER -
`
`FIG.9
`
`2 3 4 5 6
`7
`14
`13
`12
`10
`9
`11
`0 1 2 3 4 5
`14
`15
`5 6
`10
`11
`12
`7
`8
`9
`14
`0 1 2 3
`12
`13
`15
`3 4 5 6
`10
`8
`9
`7
`10
`11
`12
`13
`14
`15
`0 1
`1 2 3 4 5 6
`7
`8
`10
`12
`13
`14
`15
`8
`11
`9
`15 0 1 2 3 4 5 6
`11
`12
`10
`6
`7
`8
`9
`13
`14
`0 1 2 3 4
`15
`13
`4 5 6
`11
`9
`10
`7
`8
`11
`0 1 2
`12
`14
`15
`13
`7
`6
`8
`9
`14
`15
`0
`13
`
`t ! 3 4 5
`
`10
`
`11
`
`12
`
`DECIPHER-
`
`F I G 10
`•
`
`KEY SHIFT
`/REGISTERS
`
`I 15 I 14113 I 12 I 11 I 10 I s I a I 1 I 6 I s I 4 I 3 I 2 I 1 I o I
`16 BITS
`
`16 8 ITS
`
`16 BITS
`
`16 BITS
`
`16 BITS
`
`16 BITS
`
`16 BITS
`
`16 Bl TS
`
`Oracle-1043 p. 26
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`1
`BLOCK CIPHER CRYPTOGRAPHIC SYSTEM
`
`3,798,359
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`Reference is hereby made to application Ser. No.
`158,183, of H. Feistel, filed concurrently herewith and
`entitled "Centralized Verification System" and to ap(cid:173)
`plication Ser. No. 158,174, of H. Feistel, also filed con(cid:173)
`currently herewith and entitled, "Multiple Enciphering
`System" for descriptions of data security systems which
`utilize the block ciphering cryptographic system of the
`present application.
`
`5
`
`15
`
`2
`may be found in ciphering wheel devices. For example,
`those disclosed in U.S. Pat. Nos. 2,964,856 and
`2,984,700 filed Mar. 10, 1941 and Sept. 22, 1944, re-
`spectively.
`Further teachings on the design of principles of more
`advanced substitution techniques may be found in
`"Communication Theory of Secrecy Systems" by C. E.
`Shannon, Bell System Technical Journal, Vol. 28,
`pages 656-715, October 1949. Shannon, in his paper,
`JO presents further developments in the art of cryptogra(cid:173)
`phy by introducing the product cipher. That is. the suc(cid:173)
`cessive application of two or more distinctly different
`kinds of message symbol transformations. One example
`of a product cipher consists of a symbol substitution
`( nonlinear transformation) followed by a symbol trans(cid:173)
`position (linear transformation).
`Another well known technique for enciphering a
`clear text message communication, is the use of a ci(cid:173)
`phered stream bit sequence which is used to form a
`modulo sum with the symbols of the clear text. The ci(cid:173)
`phered output message stream is uninteligible without
`having knowledge of the stream bit generator se(cid:173)
`quence, which is sometimes referred to as a "key". Ex-
`amples of such key generators may be found in U.S.
`Pat. Nos. 3,250,855 and 3,364,308, filed May 23, 1962
`and Jan. 23, 1963, respectively.
`Various ciphering systems have been developed in
`the prior art for rearranging communication data in
`some ordered way to provide secrecy. For example,
`U.S. Pat. No. 3,522,374 filed June 12, 1967 teaches the
`processing of a clear text message with a key material
`generator that controls the number of cycles for cipher(cid:173)
`ing and deciphering. Related to this patent, is U.S. Pat.
`No. 3,506,783, filed June 12, 1967 which discloses the
`means for generating the key material which gives a
`very long pseudo random sequence.
`Another approach which has been utilized in the
`prior art for establishing secret communications, is the
`coding of the electrical signals themselves which are
`transmitted on the channel. These types of techniques
`are more effective in preventing jamming or unautho(cid:173)
`rized tapping of a communications channel then in pre-
`venting a cryptanalist from understanding a cipher
`message. Examples of these types of systems may be
`found in U.S. Pat. Nos. 3,411,089, filed June 28, 1962
`and 3,188,390, filed June 8, 1965.
`With all of the various approaches taken in the prior
`art, there still remains the problem of obtaining a highly
`secure system applicable to a data processing environ(cid:173)
`ment which is not susceptible to analysis by an unau(cid:173)
`thorized individual not withstanding the fact that the
`unauthorized person has knowledge of the structure of
`the system. Furthennore, with many of the prior art
`devices, a cracking of the cipher may be achieved by
`having an opportunity to send specially designed mes(cid:173)
`sages through the ciphering system and observing the
`output; e.g., sending an all O pattern followed by a sin-
`60 gle bit at the various positions within the data word.
`None of the prior art systems have utilized the advan(cid:173)
`tages of a digital processor and its inherent speed in de(cid:173)
`veloping a cryptographic system which produces cipher
`particularly useful in a computer system network, and
`not susceptible to "cracking" notwithstanding the pos-
`sibility that the cryptanalyst has knowledge of the
`structure of the cryptographic device.
`
`35
`
`BACKGROUND OF THE INVENTION
`With the growing use of remote-access computer net(cid:173)
`works which provide a large number of subscribers ac(cid:173)
`cess to "Data Banks" for receiving, storing, processing
`and furnishing information of a confidential nature, the
`question of data security has come to be of increasing 20
`concern. Generally, present day computing centers
`have elaborate procedures for maintaining physical se(cid:173)
`curity at the location where the central processor and
`data storage facilities are located. For example, some
`procedures which are used are restricting of personnel 25
`within the computing center, utilization of mechanical
`keys for activating computer systems and associated
`terminal devices, and other techniques of this type.
`These security procedures while providing a measure
`of safety in keeping out unauthorized individuals from 30
`the computing center itself, are not effective with re(cid:173)
`spect to large remote access computer networks which
`have many terminals located at far distant sites or sys(cid:173)
`tems which have a capability of accepting terminal in-
`puts via telecommunication lines.
`Some digital techniques have been implemented in
`computing systems for the purpose of maintaining pri(cid:173)
`vacy of data. One such approach is the use a feature
`generally known as memory protection. This type of
`data security approach associates with various seg- 40
`ments of the storage within the central processor a
`unique binary key. Then, internal to the processor,
`there are various protection circuits that check for a
`match of the binary key executable instructions and
`those sections of storage which are to be accessed. 45
`While this type of protection system provides a certain
`measure of privacy with respect to accidental destruc(cid:173)
`tion of stored information, it would not prove very ef(cid:173)
`fective in protecting information within the computing
`system from a sophisticated cryptanalyst who has com-
`plete knowledge of the computing system. In the field
`of communication, cryptography has long been recog(cid:173)
`nized as a means of achieving certain aspects of secu(cid:173)
`rity. Various systems have been developed in the prior
`art for encrypting messages for maintaining secrecy of
`communications. One well known technique for gener(cid:173)
`ating ciphers from clear text messages, is the use of sub(cid:173)
`stitution systems. Technically, in such a system, letters
`or symbols of the clear text are substituted by some
`other symbol in accordance with a predetermined
`"Key". The resulting substituted message, comprises
`a cipher which is secret and hopefully cannot be under(cid:173)
`stood without knowledge of the appropriate key. A par(cid:173)
`ticular advantage of substitution in accordance with a 65
`prescribed key is that the deciphering operation is eas-
`ily implemented by a reverse application of the key. A
`common implementation of substitution techniques
`
`50
`
`55
`
`Oracle-1043 p. 27
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`3
`
`3,798,359
`
`OBJECTS OF THE INVENTION
`Therefore, it is an object of this invention to provide
`a cryptographic system capable of maintaining secrecy
`within a data processing environment.
`It is another object of the present invention to pro(cid:173)
`vide a cryptographic system which enciphers binary
`data blocks into a cipher test that is not susceptible to
`successful cryptanalysis.
`It is another object of the present invention to pro- 10
`vide a cryptographic system that operates on block
`data by developing a product cipher which is depen(cid:173)
`dent on a plurality of unique symbol keys, each key
`known only to assigned authorized users and to the sys(cid:173)
`tem.
`It is another object of the present invention to enci(cid:173)
`pher a clear text message by means of a product cipher
`consisting of a combination of linear and nonlinear
`transformations that are functions of a subscriber sym(cid:173)
`bol key combination.
`It is another object of the present invention to pro(cid:173)
`vide a secrecy system to maintain privacy between a
`plurality of terminal users and a central processor with
`its associated data banks.
`The foregoing and other objects, features and advan(cid:173)
`tages of the invention will be apparent from the follow(cid:173)
`ing more particular description of the preferred em(cid:173)
`bodiments of the invention as illustrated in the accom(cid:173)
`panying drawings.
`
`4
`practice many more terminals are utilized within a data
`processing network. For example, CPU 10 might con(cid:173)
`sist of a time sharing system such as the IBM System
`360/67 being interconnected with a plurality of data
`5 storage means, input and output
`terminals, telepro(cid:173)
`cessing equipment, etc.
`In order for a user or subscriber that is located at a
`particular terminal in the network to gain access to the
`CPU, he must identify himself to the system and be ac(cid:173)
`cepted as a valid subscriber before carrying out a set of
`communications with the CPU. A process for verifica-
`tion of subscribers in accordance with the users unique
`key code symbols is described in the Centralized Verifi(cid:173)
`cation System of application Ser. No. 158,183. After
`15 the terminal entry has been identified by the CPU as
`being made by a bona fide user, data within the CPU
`is available to the user.
`Referring now to FIG. 2, there is shown a symbolic
`representation of a block cipher cryptographic system
`20 which transforms a data block D into a cipher block
`DS1c under the control of a specific subscriber key K •.
`The cipher block DS1c is then transmitted over some
`communication channel from the terminals A-H to the
`switching units SW which are physicall located at the
`25 extremity of the CPU. The received DS1c is then pro(cid:173)
`cessed by an inverse cryptographic block cyphering de(cid:173)
`vice that operates under the control of inverse key K, - •.
`The deciphering operation carried out by the crypto(cid:173)
`graphic device 7T re-establishes the data block D in its
`30 clear text form.
`Referring now to FIG. 3, there is shown a block dia(cid:173)
`gram of the internal structure of the cryptographic
`block ciphering device which is symbolically repre(cid:173)
`sented by the mathematical symbol rr. The 7T cryto-
`35 graphic system is comprised of four major constituents,
`each making a transformation to the digital informa(cid:173)
`tion that passes through its circuits. The constituent
`parts are as follows: ( I ) a mangler 30; ( 2) a confuser
`32; ( 3) a diffuser 34; and ( 4) an interrupter 36. Note
`40 that various arrangements of the four constituent parts
`are within the scope of this invention. e.g., mangler 30
`may be located at any position in the data flow. The
`transformations carried out by the mangler 30, con(cid:173)
`fuser 32 and interrupter 36 are a function of a sub-
`45 scriber key K. which is stored in key register 38. A data
`block D which is to be enciphered by the 1r crypto(cid:173)
`graphic system is first introduced to the mangler 30.
`Note that the data block may be loaded in either serial
`or parallel fashion so long as the entire block D which
`50 consists of n bits is fully assembled within the internal
`registers of the mangler 30. The size of the data block
`Dis a function of the specific hardware implementation
`of the concepts herein disclosed and the principles of
`the invention are not limited to any particular block
`size. For the purposes of this specification, a data block
`consisting of 48 bits in dimension is chosen.
`The cryptographic system 7T enciphered data block D
`into a Dsk by executing a plurality of transformations,
`substitutions, and modulo-2 additions in accordance
`with the condition of the binary digit appearing in the
`key register 28. The enciphering process is carried out
`by executing the cryptographic system 7T several
`rounds, where each round represents the passing of a
`data block through all of the constituent stages of the
`cryptographic system.
`During the initial round, the data block D is first
`loaded into the internal registers of mangler 30. At this
`
`55
`
`BRIEF DESCRIPTION OF THE ORA WINGS
`FIG. I is a block diagram representation of a central(cid:173)
`ized system having a plurality of subscriber terminals
`each with its own unique key.
`FIG. 2 is a symbolic representation of a block cipher
`graphic system operating on a block of data.
`FIG. 3 is a more detailed block diagram of the block
`cipher cryptographic system.
`FIGS. 4A-4L are a detailed schematic diagram of the
`cryptographic block ciphering system shown in FIG. 3.
`
`FIGS. SA and SB are a more detailed representation
`of a substitution unit within the cryptographic block ci(cid:173)
`phering system.
`FIGS 6A through 6F show a detailed diagram of a
`more economical embodiment of the cryptographic
`block ciphering system.
`FIG. 7 shows a block diagram of a serial embodiment
`of the cryptographic block ciphering system.
`FIGS. 8A and 88 show a schematic diagram of the
`serial cryptographic system of FIG. 7.
`FIG. 9 is a diagramatic representation of the sub(cid:173)
`scriber key-byte accessing order.
`FIG. 10 is a diagramatic representation of the key
`registers which access the subscriber key-byte.
`
`DETAILED DESCRIPTION OF THE INVENTION
`Referring now to FIG. 1, there is shown a centralized
`subscriber network consisting of central processor unit 60
`(CPU) 10 and a plurality of terminals A, B, C, D, E, F,
`G and H. Each of the terminal units are connected to
`the central processor 10 by means of a switching device
`physically located at the channel connection of the
`CPU 10. As indicated, the CPU 10 contains a listing of 65
`system subscribers with a unique key code defined for
`each subscriber in the network. Note, that while the
`system is illustrated as having 8 terminals, in actual
`
`Oracle-1043 p. 28
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`3,798,359
`
`5
`point in time, mangler 30 does not cause any operation
`to be carried out on the data block. The various binary
`substitions of information within the internal registers
`of mangler 30 are carried out subsequent to the opera(cid:173)
`tions of interrupter 36. Note, that the operation of the 5
`mangler 30 can be instituted at any point in the flow of
`information through the cryptographic system, and that
`its placement is a matter of design choice. The data
`block D as it appears in the internal registers of man(cid:173)
`gler 30 is presented to the confuser 32 which provides 10
`the functional operation of a nonlinear transformation
`of the block output from mangler 30. This is accom(cid:173)
`plished by a substitution process which converts the n
`binary inputs into confuser 32 to one of the possible 2"
`factorial combinations of the n inputs. After the non- 15
`linear transformation, the output of the confuser 32 is
`presented to diffuser unit 34 which provides the means
`for executing a transposition of the symbols appearing
`at the output of the confuser 32 so as to change the
`physical location of each of the symbols in accordance
`with some prewired interchange. This linear transfor(cid:173)
`mation of diffuser 34 which follows the nonlinear trans-
`formation of confuser 32 forms the product cipher
`which is further altered by the interrupter 36 which in 25
`turn executes a plurality of modulo 2 additions of the
`product cipher with selected signal lines from the key
`register 38. The output of interrupter 36, is fed back to
`mangler 30 which executes a further modulo 2 addi(cid:173)
`tion of the binary symbols appearing at the interrupter
`output with the binary symbols existing in the internal
`registers of mangler 30. Then, depending on whether
`symbol values of particular lines in the key register 38
`are I or 0, shifts of data within the mangler 30 are exe(cid:173)
`cuted or not. Note, that while in the preferred embodi(cid:173)
`ments of this disclosure the interrupter 36 is located
`after confuser 32, it could alternatively be placed prior
`to the confuser 32.
`In order to complete the cryptographic process and
`assure secrecy of the cipher text, the above process
`must be repeated for X rounds, where the number Xis
`a function of the size of the key register 38. For the pre(cid:173)
`ferred embodiment disclosed herein it is necessary to
`execute 16 rounds prior to providing the cipher text
`output DSk.
`Referring now to FIGS. 4A, 4B, 4C, 4D, 4E, 4F, 40,
`4H, 41, 4J, 4K and 4L, there is shown a more detailed
`schematic diagram of the ff cryptographic system. This
`1r cryptographic system is capable of encrypting any
`kind of information whatsoever, represented in terms
`of binary digits. It should be recognized by those skilled
`in the art, that while the specific implmentation of the
`device is shown as taking the form of a "hardware" sys(cid:173)
`tem, the novel concepts presented herein may also be
`implemented by appropriately programming a general 55
`purpose computer, the choice being one of conve(cid:173)
`nience and trade-off in terms of dollar cost.
`For the purpose of illustration, so as to facilitate ease
`of understanding of the invention, the dimension of the
`basic message block is chosen to be 24 binary digits.
`It should be recognized by those skilled in the art, that
`this message block size is arbitrary and other message
`block sizes would serve the purposes of the invention
`as well. Generally, it is more desirable to increase the 65
`message block size in order to increase the throughput
`of the cryptographic system and also to generate a
`more complex cipher text.
`
`6
`As h