United States Patent
`
`[19]
`
`[11]
`
`4,172,213
`
`[45] Oct. 23, 1979
`Barnes et al.
`
`
`
`[54] BYTE STREAM SELECTIVE
`ENCRYPTION/DECRYPTION DEVICE
`
`[75]
`
`Inventors:
`
`Vera L. Barnes, Wayne; Thomas J.
`Dodds, Jr., Drexel Hill; Harold F.
`Gibson, Downingtown; Carl M.
`Campbell, Jr., Newtown Square, all
`of Pa.
`
`[73] Assignee: Burroughs Corporation, Detroit,
`Mich.
`
`[21] Appl. No.: 852,444
`[22] Filed:
`Nov. 17, 1977
`
`Int. Cl.2 ............................................... H04L 9/00
`[51]
`
`[52] US. Cl. ............
`178/22; 340/146.1 AL
`[58] Field of Search ................. 178/22; 340/146.1 AL
`[56]
`References Cited
`U.S. PATENT DOCUMENTS
`
`3,657,699
`3,740,475
`3,798,605
`3,962,539
`3,984,668
`
`......................... 178/22
`4/1972 Rocher et a1.
`178/22
`6/1973
`Ehrat .......
`
`3/1974
`Feistel .....
`. 364/200
`
`
`Ehrsam et al.
`..
`6/1976
`178/22
`Zetterberg et a1.
`.........
`10/1976
`178/22
`OTHER PUBLICATIONS
`
`C. M. Campbell, Jr.; Conf. on Computer Security and
`the Data Encryption Standard; NBS (Preprint of Pa-
`pers); Feb. 15, 1977.
`B. Morgan; Conf. on Computer Security and the Data
`Encryption Standard; NBS (Preprint of Papers); Feb.
`15, 1977.
`
`Primary Examiner—S. C. Buczinski
`Attorney, Agent, or Firm—Mark T. Starr
`[57]
`ABSTRACT
`An apparatus for insertion in a communications line for
`providing message secrecy within a significant portion
`of existing communications networks. At the transmit-
`ter end, the apparatus receives messages from the com-
`munications line, enciphers them and retransmits them
`onto the communications line. At the receiver end, the
`apparatus receives messages from the communications
`line, deciphers them and retransmits them onto the
`communications line. The apparatus contains both a
`transmitter and receiver and is capable of full duplex
`operation in a bidirectional communications line. Ac-
`cording to the invention, data is enciphered by combin-
`ing the data received with the output of an algorithm,
`the algorithm output being dependent on the data previ-
`ously enciphered and a unique key entered by the user.
`As data is received it is combined with the output of the
`algorithm, transmitted and using cipher feedback tech-
`niques fed back as an input to the algorithm to be used
`to encipher subsequently received data. Data is deci-
`phered using equivalent elements as used for encipher-
`ing,
`the basic difference in the apparatus operation
`being the point from which data fed back into the algo-
`rithm is taken. The apparatus operates on a byte-by-byte
`basis, and contains provisions for responding to control
`characters and ignoring messages intended for a differ—
`ent apparatus.
`
`49 Claims, 17 Drawing Figures
`
`
`INPUI touwur
`.
`
`pnuurr rummncnu \ 0 SENS/PARALLEL
`
`(IP)
`
`
`I_I
`
`
`(3-5414 ROMS)
`
`
`
`
`
`(SZ-EXCLUSWE OR'S)
`
`Unified Patents Inc. Ex. 1016, pg. 1
`
`Unified Patents Inc. Ex. 1016, pg. 1
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 1 of 15
`
`4,172,213
`
`KEY
`IN
`
`6’
`
`8X8 BIT
`SERIES/PARALLEL
`H
`
`c
`
`KEY STORAGE
`
`D
`
`®
`
`g
`
`Ln
`
`Q (8-8 BIT REG.)
`Rn
`
`TRANSFORM
`(E)
`
`‘
`
`6
`
`1
`I
`I
`
`II
`
`PERMUTE
`(P02)
`
`€13
`
`EXCLUSIVE UR
`
`66666666
`
`SUBSTITUTION
`
`
`
`PERMUTE (P)
`
`6?
`
`EXCLUSIVE 0R
`
`Fig. /
`
`(32—EXCLUSNE OR'S)
`
`I | I II| l iI
`
`I T|| E I I
`
`Unified Patents Inc. Ex. 1016, pg. 2
`
`DATA
`IN
`
`TO Rn
`
`DATA
`OUT
`
`
`‘9
`
`
`L
`
`DATA STORAGE
`
`R
`
`9?
`
`INPUT & UUTPUT
`9 PERMUTE AUTOMATICALLY
`UP)
`
`Unified Patents Inc. Ex. 1016, pg. 2
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 2 of 15
`
`4,172,213
`
`5&8a“
`
`NZ
`
`___
`
`
`
`E581éfiafl:E120
`
`
`
`535:;.25:59:49:28E:.m3
`5%:H$823535
`
`
`ENum
`
`
`
`
`
`0:olllllllllllllll:lwajmilij
`
`._.a@fi4rm5%Ew
`
`_IIFI_.5:3
`$55:£58..
`
`m_
`
`0
`
`Unified Patents Inc. Ex. 1016, pg. 3
`
`Unified Patents Inc. Ex. 1016, pg. 3
`
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 3 of 15
`
`4,172,213
`
`
`
`.27:szzoEEoE,Emfig
`
`MOSHE
`
`
`
`2855328Eamgfiézam
`
`$355
`
`225555
`
`$58
`
`
`
`.23sz
`
`zoEEoE
`
`55%
`
`5955
`
`$255
`
`225552“.
`
`magma
`
`52:5
`
`35:55
`
`magma
`
`€255
`
`
`
`22:18:282.85::
`
`3mma.w Nomefo
`
`
`
`SiouxééfifiEEG
`
`Unified Patents Inc. Ex. 1016, pg. 4
`
`Unified Patents Inc. Ex. 1016, pg. 4
`
`
`
`
`
`
`
`
`
`
`

`

`3.W31m.M,%hm
`
`2EW$022628
`
`PS
`
`WB,
`
`4w
`
`m
`
`4
`
`%225%Es:
`
`9:23
`
`:3312%m553:m22%:
`225%-as:
`
`a.:2ng085m
`
`
`
`
`
`U225$:25H52%52%w:33V2%J:25:
`
`
`
`
`
`
`
`cm55¢20:3EESOEEE”2553-23”
`
`Unified Patents Inc. Ex. 1016, pg. 5
`
`Unified Patents Inc. Ex. 1016, pg. 5
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 23, 1979
`
`Sheet 5 of 15
`
`4,172,213
`
`29:2:
`
`ESE
`
`m;
`
`__$55.1%.?
`
`9%.:51%Ex5%;
`5:3‘=52;
`
`
`
`5%:£38m
`
`oz<35.28
`
`gimafiEEG
`
`E581
`
`LEEx:
`
`5555
`
`”355$
`
`magma
`
`mwéog
`
`Em:$55”;
`
`zEESé
`
`SEZS
`
`ma
`
`2558.2
`
`émaw$55
`5,;on
`
`5%::52;
`==
`Q24sEZS
`:mE;
`
`
`$55M”—
`
`22323:
`
`$2.925”;
`
`$53
`
`Unified Patents Inc. Ex. 1016, pg. 6
`
`E55:.0.%
`
`o-~mm-m~_
`
`
`
`£55?:2ng
`
`5%:sate
`
`N3
`
`Unified Patents Inc. Ex. 1016, pg. 6
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 6 of 15
`
`4,172,213
`
`ONE BIT SHIFT
`PER BIT
`
`7‘2
`
`BBITS
`/—’\—\
`
`'mmmmmmmm
`
`KEY
`— _ _ TEE—ALG—(TRTTTIIT— _______ 7
`
`VARIABLE
`STRANSFERS/BIT
`
`
`
`
`
`ACTIVATE
`ONCE PER
`0 BIT
`
`
`
`
`
`Unified Patents Inc. Ex. 1016, pg. 7
`
`Unified Patents Inc. Ex. 1016, pg. 7
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 7 of 15
`
`4,172,213
`
`50:
`
`22.;
`
`SE
`
`EEfiEES
`
`.5528tn:
`
`EEG
`
`Eggs
`
`Emma
`
`
`
`.-__—.___-_mag20:;
`
`EIHquz
`
`820Nm
`
`E5:8
`
`
`
`maze2
`
`$538
`
`a
`
`EEzmz<E
`
` 40m-zoo
`
`22.53%;5
`
`.5528Cm:
`
`EEG
`
`Emacs
`
`2:58:
`
`m5EOE
`
`4<z2mwp
`
`22.:
`
`So:
`
`”Hmmpg
`
`mwzo2
`
`$528
`
`Unified Patents Inc. Ex. 1016, pg. 8
`
`Unified Patents Inc. Ex. 1016, pg. 8
`
`
`
`
`
`
`

`

`US. Patent
`
`C
`
`m,
`
`5
`
`3
`
`21w
`
`t.1
`
`
`
`o@2202:EEO?
`
`
`
`”58-2‘ESE/‘5
`
`moEzEE522
`
`WEE_:zwzs:
`
`MaoHME
`
`“23-2
`
`mofizflz
`
`
`
`1:moSmo‘29:8_,mEgg:Gig:ILfig_8.m'aamE.a-53:_was;
`e_E_%A_5528fi2558:_47mllllllllL?
`
`
`
`ME5025a;Em,...._..........m{£111mellllllllllw4”,$55:-_IIIII_
`5:05o;__LEE:-___
`
`
`
`2250$4505Ex1:;9mmlllll
`
`Unified Patents Inc. Ex. 1016, pg. 9
`
`Unified Patents Inc. Ex. 1016, pg. 9
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 9 of 15
`
`4,172,213
`
`F[9. l3
`
`l3'4
`
`PARITY
`CHECK
`
`AF
`
`GENERATION E“—
`
`IF
`GENERATION
`
`
`
`CHARACTER
`MAW
`
`.
`
`INPUT DATA FROM DTE
`
`DATA
`INPUT
`REGISTER
`
`I3'2
`
`CHARACTER
`STORAGE
`DELAY
`
`SELECT
`
`I EXCLUSIVE-0R
`
`AND
`TRANSFORMATION
`
`I3-10
`
`'58
`
`|3-lO
`
`
`
`_
`
`SELECT
`
`TOTTIEATIG‘ATToR‘
`DEVICE
`
`OUTPUT
`GHARAGTER
`BUFFER
`
`6-6
`
`OUTPUT DATA TO DGE
`
`KEY MEMORY
`STORAGE
`
`DATA FROM ALGORITHM
`
`DATA TO ALGORITHM
`GONTROLIGIRHER
`FEEDBACK REGISTER)
`
`PARITY
`“NEW
`
`"KEY BITS"(6 AT)
`00
`OI
`IO
`
`II
`
`,
`I
`
`"KEY BITS“ (6 AT)
`DO
`OI
`I0
`
`II
`
`IBIIRUT
`(52,7)
`
`NUT
`(6&7)
`
`GO
`0|
`10
`II
`
`DO
`OI
`10
`II
`
`OO
`00
`I
`II
`OO\OO\U IO
`II
`OI
`i
`IO
`OI OI\\OO\\II
`\
`'0
`U
`IO
`l0
`l|\QO\Q|
`OI
`IO
`II
`II
`IO 0l\@\|
`EXCLUSIVE—0R
`\l
`OUTPUT
`(A)
`(B)
`
`Fig/0
`
`OO—GOIITROLGHARAGTER
`IO
`0'
`II
`
`NON—GONTROL
`CHARACTER
`
`Unified Patents Inc. Ex. 1016, pg. 10
`
`Unified Patents Inc. Ex. 1016, pg. 10
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 10 of 15
`
`4,172,213
`
`N
`YT
`gEFT EYTE SHI
`
`FT
`
`”'2
`
`8 BITS
`r—A‘——\
`
`“mmmm “mm
`
`
`
`
`| IIIIIIII
`|
`Q’
`-
`
`I
`
`ENCRYPT MODE
`
`®
`
`| l
`
`(i)
`l III-Ill. 6)
`
`o
`
`ACTNATE
`
`ONCE PER
`
`BYTE
`
`0
`
`a
`
`|____DES_ALGWTITW—————— fl
`|
`8TRANSFERS/BYTE
`
`KEY
`VARIABLE
`
`. M W
`
`AND
`
`RECEIVE
`
`KEY BITS
`
`IIIIIIII
`
`9
`
`IHZ
`
`CONTROL
`
`'N
`
`IIIIIIII
`
`XOR AND m
`TRANSFORMATION
`
`'
`
`IHO
`
`' PLAIN TEXT
`
`Fig. //
`
`Unified Patents Inc. Ex. 1016, pg. 11
`
`Unified Patents Inc. Ex. 1016, pg. 11
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 11 0E 15
`
`4,172,213
`
`TRANSMITTING
`
`PLAIN
`TEXT
`
`'2'4
`
`A
`
`A
`H
`
`.A A_.
`
`A
`2
`
`D
`I
`
`S
`
`I
`X
`
`,3
`A A,
`S
`E
`D
`D
`0
`H
`|
`2
`X
`
`TRANSMITTING
`
`
`IDENTIFICATION FIELD (IF)
`SELECTIVE ENCRVPTION/
`
`
`AUTHENTICATION DEVICE
`
`S
`A
`A V.
`,1:
`PLAIN
`5
`CIPHER
`'
`D
`D
`E
`TEXT
`E
`TEXT
`C
`3
`4
`I
`F
`
`PLAIN
`TEXT
`
`3
`E
`F
`
`PLAIN
`TEXT
`
`E
`E
`F
`
`E
`
`E
`F
`
`PLAIN
`
`TEXT
`
`E
`E
`X
`
`A
`C
`00
`
`E
`
`E
`X
`
`A
`
`C
`0|
`
`:E:~I—22
`
`5AA...3 5
`H
`I
`2
`X
`C
`
`A
`3
`
`A V...V PLAIN
`4
`I
`8
`
`
`
`TIECEIVINC
`SELECTIVE ENCRVPTION/
`AUTHENTICATION DEVICE
`
`III -:
`
`H
`
`I
`
`2
`
`TEN
`
`S
`F
`
`E
`
`F
`
`CIPIIER
`
`TEN
`
`E
`F
`
`E
`
`F
`
`PLAIN
`
`E
`X
`
`A
`02
`
`PEN E3
`
`X
`
`03
`
`RECEIVING DTE
`
`ADI,AD2 INDICATE RECEIVING DTE
`SIC = SELECTIVE IDENTIFICATION CHARACTER = IIIIIDI
`AD3,AD4 INDICATE TRANSMITTING DTE
`VFI-VF8=VARIABLE FILL CHARACTERS
`SEF =START ENCRYPT FIELD
`EEF = END ENCRYPT FIELD
`
`
`Unified Patents Inc. Ex. 1016, pg. 12
`
`Unified Patents Inc. Ex. 1016, pg. 12
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 12 of 15
`
`4,172,213
`
`DATA FROM DCE
`
`DATA
`INPUT
`REGISTER
`
`I4—2
`
`I
`I
`I
`
`_—————
`
`M A
`
`VERIFICATION
`ND
`_s_TRIPPINC_ _
`7'?—
`
`I—“—‘_I
`I
`FOUR
`I
`—— CHARACTER
`TJEUILJW I
`I
`I
`9|
`II
`I
`I
`
`I | I I I
`
`DATA FROM
`ALGORITHM
`
`DATA TO
`ALGORITHM
`ICIPHER FEEDBACK
`REGISTER)
`
`I
`
`E
`L
`E
`'CT
`
`‘
`
`‘
`
`AND
`
`IF VERIFICATION
`I STRIPPING
`
`‘
`
`LCADINC
`0F VARIABLE
`FILL
`
`
`
`
`EXCLUSIVE
`OR AND
`TRANSFORMATION
`
`SELECT
`
`PARITY
`CHECK
`
`_.
`
`r
`
`KEYMEMORY
`STORAGE
`
`CHARACTER
`MATRIX
`
`
`
`PARITY
`GENERATION
`
`”‘4
`
`CHARACTER
`
`STORAGE
`
`RECIsTER
`
`DATA TD DTE
`
`F19. /4
`
`
`Unified Patents Inc. Ex. 1016, pg. 13
`
`Unified Patents Inc. Ex. 1016, pg. 13
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 13 of 15
`
`4,172,213
`
`ONE BYTE SHIFT
`PER BYTE
`
`3”“
`
`m
`.VARABLE
`
`l5-6
`
`r”
`
`
`
`9
`
`V___fifi@fim ‘‘‘‘‘‘‘‘
`'
`1
`
`8TRANSFERS/BYTE
`
`-
`
`=
`-
`E
`® -
`I
`
`llllllll
`1%,
`
`lI
`
`RRRR'
`BYTE
`I
`1
`
`0
`
`ENCRYPT MODE
`
`'
`
`@
`i
`{ IIIIIIII 9
`
`IIIIIIII
`
`15-12
`
`GENERATOR
`
`J
`
`RECEIVE
`COMPARATOR
`
`‘
`
`0
`
`KEY
`ans
`
`PLAIN .
`TEXT
`
`IIIIIIII 1
`
`XOR
`
`TRANSFORMATION
`
`I
`
`INTERCHANGE
`
`STATUS
`
`
`
`[5-8
`
`KOUTPUT
`
`l5-I0
`
`__ELCJ- /5
`
`Unified Patents Inc. Ex. 1016, pg. 14
`
`Unified Patents Inc. Ex. 1016, pg. 14
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 14 of 15
`
`4,172,213
`
`I -
`
`TRANSMITTING
`
`A
`D
`I
`
`o
`
`S
`° T
`X
`
`PLAIN
`TEXT
`
`><--OI'_"I
`
`00w
`
`SELECTIVE ENCRYPTION/
`AUTHENTICATION DEVICE
`
`
`
`IDENTIFICATION FIELD (IF)
`
`
`AUTHENTICATOR FIELD (AF)
`
`I003
`[\J'UD
`
` TRANSMITTING
`
`
`()4'1'1>
`
`43m)
`
`x—lm
`
`COED
`
`m‘fi:>
`
`4>~n>
`
`><—-lr‘r1
`
`Goa:
`
`V
`A
`A
`S
`S
`A
`A
`S
`ODDo-TIDDFH-
`
`H
`
`I
`
`2
`
`X
`
`C
`
`3
`
`4
`
`l
`
`A
`A
`D D-
`I
`2
`
`V
`-F
`8
`
`
`
`
`RECEIVING
`SELECTIVE ENCRYPTION/
`AUTHENTICATION DEVICE
`
`S
`O
`H
`
`S O H
`
`I640
`
`RECEIVING DTE
`
`ADI,AD2 INDICATE RECEIVING DTE
`SIC = SELECTIVE IDENTIFICATION CHARACTER =II||IOI
`AD3,ADA INDICATE TRANSMITTING DTE
`E] =OPTIONAL CHARACTER THAT INDICATES THE STATE OF AUTHENTICITY OF THE MESSAGE
`VFI-VF8 = VARIABLE FILL CHARACTERS
`
`Unified Patents Inc. Ex. 1016, pg. 15
`
`Unified Patents Inc. Ex. 1016, pg. 15
`
`

`

`US. Patent
`
`Oct. 23, 1979
`
`Sheet 15 of 15
`
`4,172,213
`
`TRANSMITTING
`
`DTE
`
`I
`
`Fig. /7
`
`s
`A
`PLAIN
`5
`PLAIN
`,3
`A
`ODD
`T
`TEXT
`E
`TEXT
`H
`I
`2
`x
`F
`
`SELECT'VE ENCRYPT'ON’
`IDENTIFICATION FIELD (IF)
`OPTIONAL
`
` ETQ
`SSAAV
`V
`s
`AAAEB
`~TIDDE-o-EIT’E’L'IIER'ETTEREGEQITN FFFFTC
`110341
`8
`F
`E
`|234XC|
`
`
`
`TRANSMITTING
`
`AUTHENTICATION
`DEVICE
`
`SAA
`ODD
`HI2
`
`E
`E
`F
`
`PLAIN
`TEXT
`I.
`,
`
`EB
`To
`N
`Go
`
`
`
`AUTHENTICATOR FIELD IAEI
`
`DCE
`
`DCE
`
`3AA
`SSAAV
`V
`OD D---T I
`D
`D F-o-F IT’LEQITN
`HI2
`XC34I 8.
`
`
`
`RECEIVINC
`SELECTIVE ENCRYPTION/
`AUTHENTICATION
`DEVICE
`
`SAA,,,S PLAIN
`ODD
`T
`TEXT
`H12»
`x
`
`5
`E
`F
`
`PLAIN
`TEXT
`
`RECEIVING DTE
`
`‘
`
`s
`E
`F
`
`F
`E
`F
`
`HELLER
`
`E
`E
`
`AAAAEB
`TERIII FFFFTC
`1234XC2
`
`PLAIN
`TEXT
`
`EB
`TC
`X03
`
`ADI,AD2 INDICATE RECEIVING DTE
`SIC = SELECTIVE IDENIFICATION CHARACTER = I|I|IOI
`AD5,AD4 INDICATE TRANSMITTING DTE
`[T =0PTIONAL CHARACTER THAT INDICATES THE STATE OF AUTHENTICITY OFTHE MESSAGE
`VFI-VF8=VARIABLE FILL CHARACTERS
`
`SEF = START ENCRYPT FIELD
`EEF= END ENGRYPT FIELD
`
`Unified Patents Inc. Ex. 1016, pg. 16
`
`Unified Patents Inc. Ex. 1016, pg. 16
`
`

`

`1
`
`BYTE STREAM SELECTIVE
`ENCRYPTION/DECRYPTION DEVICE
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`Reference is hereby made to two utility applications
`entitled LINK ENCRYPTION DEVICE, Ser, No.
`452,443,
`and COMMUNICATIONS LINE AU-
`THENTICATION DEVICE, Ser. No. 852,446, by the
`same inventors as the instant invention and filed concur-
`rently with the instant application, and to a design appli—
`cation entitled DATA ENTRY KEYBOARD, by
`Jerry Joseph Sims et al., Ser. No. 835,840, filed Sept. 22,
`1977.
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates generally to the art of
`cryptography and more specifically to hardware and
`techniques for achieving data communicating security.
`With the growing use of remote communications
`lines to transfer data between processing systems, be-
`tween terminals and remote data banks, and between
`terminals connected to the same or different computers,
`the need to safeguard the data being transferred has
`grown. In the banking industry, there is a growing need
`to prevent the fraudulent modification of “electronic
`money" in electronic funds transfer. Similar needs exist
`in business to prevent the disclosure of sensitive data. In
`the government sector, present and/or future privacy
`acts place restrictions on the ability to access sensitive
`information. This need to safeguard sensitive informa-
`tion is likely to grow as future privacy legislation will
`most probably impose data communications security
`requirements on the private sector.
`.
`Previous efforts to safeguard data communications
`have been made,
`for example,
`in US. Pat. No.
`3,798,605,
`issued Mar. 19, 1974, which pertains to a
`multi—terminal data processing system having means
`and process for verifying the identiy of subscribers to
`the system. Validity of a terminal request for communi-
`cations with the data processing system are determined
`on the basis of a centralized verification system. Each
`subscriber to the system is identified by a unique key
`binary signal pattern. The central data processing unit
`contains a listing of all valid keys for subscribers to the
`system. Two embodiments of the centralized verifica-
`tion system are presented, a password system and a
`handshaking system. In the password system, all data or
`information originating at the terminal under use of the
`subscriber is enciphered in combination with the unique
`subscriber key. Upon proper deciphering of the key or
`password at the central processing unit and arriving at
`a match with one of the keys in the processor’s listing,
`the subscriber may communicate with the processing
`system. In the handshaking system embodiment the user
`and the central processor exchange a plurality of mes-
`sages each formed by a combination of new and prior
`received data. Received data messages are also main-
`tained within the registers at both the terminal and the
`central processor for further verification upon the re-
`turn of the portion of the message that was previously
`transmitted. The techniques described in the latter pa-
`tent have several drawbacks. First, the techniques are
`restricted to communications between a central proces-
`sor and terminals attached to the central processor. No
`provision is available for communications between ter-
`minals or for transmitting a message received by, but
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4,172,213
`
`2
`not intended for, a first terminal to a second terminal
`which is intended to receive the message. Second, the
`system enciphers all data and hence is not capable of
`selective encryption. Third, communications must be
`initiated by the terminal, and may not be initiated by the
`central processor. Fourth, the system is not designed for
`insertion in previously existing communications sys-
`tems.
`
`Another cryptographic technique to achieve data
`security is presented in U.S. Pat. No. 3,798,360, issued
`Mar. 19, 1974, which system provides multiple level
`encipherment of a block of data by means of a stepped
`block cipher process. This system suffers from the same
`drawbacks as previously discussed for U.S. Pat. No.
`3,798,605. Further, this system is restricted to operation
`on’blocks of data and is not capable of bit-by-bit encryp—
`tion.
`
`OBJECTS OF THE INVENTION
`
`It is the general object of this invention to provide a
`cryptographic system to provide communications secu-
`rity for communications links in point-to-point or multi-
`point networks without changes to existing hardware or
`software configurations.
`It is another object of this invention to provide link
`encryption on a byte-by-byte basis in common carrier or
`direct connect circuit environments.
`It is a further object of this invention to provide a
`cryptographic system, for insertion between a data set
`and a terminal or central processing unit, which enci-
`phers and deciphers binary data on a byte-by—byte basis.
`It is a further object of this invention to provide a
`self-contained cryptographic system, for insertion be-
`tween a data set and a terminal or central processing
`unit, which enciphers and deciphers data on a byte-by-
`byte basis without modifying control commands and
`communications protocols.
`It is another object of this invention to provide a
`cryptographic system, for insertion in communications
`links, which can selectively encrypt binary data.
`It is still another object of the present invention to
`provide a system which maintains message secrecy as a
`message is transmitted from a first terminal or processor
`until the message reaches its ultimate destination point
`after passing through terminals or processors for which
`the message is not intended.
`It is a further object of the present invention to pro-
`vide a system to maintain privacy between selected
`terminals in a data communications network having a
`plurality of terminals.
`It is another object of the present invention to pro-
`vide a cryptographic system which enciphers binary
`data into an enciphered data that is not susceptible to
`successful cryptoanalysis.
`It is still another object of the present invention to
`provide a cryptographic system that enciphers and
`deciphers data and which is dependent on a key stored
`in the cryptographic system and data previously re-
`ceived by the cryptographic system.
`These and other objects, features and advantages of
`the present invention will become apparent from the
`description of the preferred embodiments of the inven-
`tion when read in conjunction with the drawings con-
`tained herewith.
`
`Unified Patents Inc. Ex. 1016, pg. 17
`
`Unified Patents Inc. Ex. 1016, pg. 17
`
`

`

`3
`
`4,172,213
`
`SUMMARY OF THE INVENTION
`
`The foregoing objects of the present invention are
`achieved by providing an apparatus for insertion in an
`existing communications line for providing message
`secrecy within a significant portion of existing commu-
`nications lines.
`The apparatus has both encryption and decryption
`capabilities and can function in a full duplex environ-
`ment to encipher and transmit data received from a first
`direction, and decipher and transmit data received from
`a second direction. Data received from the first direc-
`tion is enciphered by combining the data received with
`the output of an algorithm, the algorithm output being
`dependent on the data previously enciphered and a
`unique key entered in the apparatus by the user. As data
`is received from the first direction, it is combined with
`the output of the algorithm and the resulting enciphered
`data is transmitted back onto the communications line in
`the first direction and fed back to a cipher feedback
`register which provides input data to the algorithm for
`use in enciphering data subsequently received by the
`apparatus.
`Data received from the second direction is deci-
`phered using equivalent elements and the same algo-
`rithm as used for enciphering, the basic difference in the
`operation of the apparatus being the point from which
`data fed back to a cipher feedback register is taken.
`The apparatus operates on a byte-by-byte basis and is
`sensitive to control character sequences. In response to
`the receipt of specified control characters, the apparatus
`has provisions for selectively encrypting or decrypting
`data received, and provisions for transmitting the data
`received from the first direction without enciphering it.
`In an alternate embodiment, the apparatus contains
`provisions for storing a plurality of unique keys, each
`key having associated with it a unique address. When
`the apparatus receives a message from its second direc-
`tion it uses the address contained in the message to load
`the key, corresponding to the address received, into its
`algorithm. The apparatus then deciphers the data re-
`ceived based on the key that was loaded into its algo-
`rithm. If the address contained in the message is not one
`of the ones stored in the apparatus, the apparatus will
`transmit the message received without alteration, as it
`was not intended for that apparatus.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of the data encryption
`standard used in the preferred embodiment of this in-
`vention.
`FIG. 2 is a functional diagram of the cryptographic
`technique utilized in the selective encryption/authenti-
`cation device.
`FIG. 3 is a functional diagram showing the transmit-
`ter cipher feedback register run as a shift code counter.
`FIG. 4 illustrates typical point-to-point and multi-
`point networks utilizing the SE/AD in link encryption
`mode.
`FIG. 5 shows a typical end-to-end mode communica-
`tion network configuration with multiple nodes and a
`variety of links containing a mixture of terminals and
`processors.
`FIG. 6 is a functional block diagram of an SE/AD in
`the link encryption mode of operation.
`FIG. 7 illustrates the SE/AD as a bit-stream encryp-
`tion/decryption device operating in the link encryption
`mode.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`FIG. 8 illustrates the modem delay compensation
`circuitry utilized in both the transmit and receive opera-
`tions.
`FIG. 9 is a functional block diagram of the SE/AD in
`the end-to-end selective encryption mode of operation.
`FIG. 10 illustrates the translation performed on con-
`trol characters.
`FIG. 11 is a functional block diagram of the SE/AD
`as a byte stream encryption/decryption device operat-
`ing in any end-to—end mode.
`FIG. 12 shows the message flow in a communication
`network that utilizes the SE/AD in the end-to-end
`selective encryption mode.
`FIG. 13 is a simplified block diagram of the transmit
`processing operation.
`FIG. 14 is a simplified block diagram of the receive
`processing operation.
`FIG. 15 illustrates the SE/AD utilized as just an
`authentication device which serves as both a transmitter
`and a receiver.
`FIG. 16 shows the message flow in a communication
`network that utilizes end-to-end authentication mode
`devices.
`FIG. 17 shows the message flow in a communication
`network which combines the selective encryption mes-
`sage flow and the authentication message flow into a
`system containing both modes of operation.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`Throughout this description and in the accompany-
`ing drawings, the following terms and expressions will
`be utilized in accordance with the following definitions:
`
`Algorithm: A prescribed set of well-defined rules or
`processes for the solution of a problem in a finite num-
`ber of steps.
`Authentication: The process of appending crypto
`check digits to a plain text message by means of a
`Crypto System where the Crypto check digits are gen-
`erated by Encryption of the entire plain text message.
`Cipher Feedback: A technique in which the key gen-
`erated is a function of the preceding cipher.
`.
`Cipher Text: The unintelligible form of information
`resulting from Encryption of plain text by a Cryptosys-
`tern.
`
`Cryptographic System (Cryptosystem): The associ—
`ated items of documents, devices, or equipment that are
`used as a unit, and provide a single means of encryption.
`(The term “Encryption” used in this specification im-
`plies the capability of the inverse function, i.e., “De-
`cryption”.)
`Crypto Unit: That portion of a Cryptosystem where
`the actual Encryption and Decryption takes place.
`Decryption (Deciphermcnt): The process of convert—
`ing encrypted text
`into its equivalent plain text by
`means of a Cryptosystem.
`Encryption (Encipherment): The process of convert-
`ing plain text into unintelligible form by means of a
`Cryptosystem.
`End-To-End Selective Encryption/Authentication:
`Encryption of authentication in point-to-point multi-
`point networks to provide protection of data on the data
`communication line and within interspersed message
`switches or concentrators.
`Garble: Unintelligible information caused by a modi—
`fication to a cipher bit(s).
`
`Unified Patents Inc. Ex. 1016, pg. 18
`
`Unified Patents Inc. Ex. 1016, pg. 18
`
`

`

`5
`Key: Bits generated by a crypto unit under control of
`the key variable which are logically combined with
`plain text to form unintelligible information i.e., cipher
`text, or inversely, logically combined with cipher text
`to produce the original plain text.
`Key Variable: A symbol, or sequence of symbols (or
`electrical or mechanical correlates to symbols) which
`control the operations of encryption and decryption
`(e.g., a finite length bit pattern).
`Link Encryption: Encryption in point-to-point or
`multipoint networks to provide protection of data on
`the data communications line.
`Message Integrity: A message in which the data is
`received at the proper destination exactly as sent by the
`originator, i.e., without any changes or tampering.
`Message Secrecy: A message in which the data is
`incomprehensible to any viewer or listener from the
`time it leaves the source until it arrives at the proper
`destination.
`Plain Text: Intelligible text or signals which have
`meaning and which can be read or acted upon without
`the application of any decryption.
`Selective Encryption: The process of converting
`portions of plain text which are delineated by selected
`character(s) into unintelligible form by means of a
`Cryptosystem.
`Variable Fill: A random bit pattern provided as the
`input to the algorithms of both transmit and receive
`crypto units during initialization.
`Data Encryption Standard: The Data Encryption
`Standard (DES) is an algorithm released by the Na-
`tional Bureau of Standards in the Federal information
`Processing Standards Publication (FIPS Pub) 46-Jan.
`15, 1977, and is intended for use as an industry standard.
`It was designed for 64-bit block data operation. The key
`variable is 56 bits in length and-is loaded into the algo-
`rithm before the encryption/decryption process is initi-
`ated. In the encrypt mode the algorithm produces 64
`bits of cipher text for each 64 bits of input plain text.
`Conversely, in the decrypt mode if these 64 bits of ci-
`pher text are provided as the input, the algorithm will
`produce the original 64 bits of input plain text. The Data
`Encryption Standard is incorporated by reference in
`this specification. Additional description of the Data
`Encryption Standard is also presented in U.S. Pat. Nos.
`3,796,830 and 3,798,359, issued Mar. 12, 1974 and Mar.
`19, 1974, respectively.
`
`FIG. 1 is a block diagram of the data encryption
`standard. As shown, the implementation of the data
`input and data output is provided in 8—bit bytes. The key
`input is entered in 8-bit bytes: 7 bits plus parity. Parity is
`not stored in the key storage register.
`q
`Twenty-four clock periods are required to load the
`data input. Data output is simultaneously available dur-
`ing this period. Sixteen iterations of the algorithm at
`two clock periods per iteration, require an additional 32
`clock periods, giving a total of 56 clock periods needed
`for a complete algorithm load and run cycle. At the
`system clock of 1.2288 MHz, the algorithm is cycled in
`45.6p. seconds.
`FIG. 2 is a functional diagram of the cryptographic
`technique utilized in the Selective Encryption/Authen-
`tication Device (SE/AD). Operation of the algorithm
`unit (DES) 2-2 is described, supra, and is shown only to
`indicate the required interconnections. In this discus-
`sion, the algorithm is only operated in the encrypt mode
`and is being utilized as a key generator. This technique
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4,172,213
`
`6
`operates on the principle that “plain text” exclusive-
`ORed with “key” produces cipher, and conversely that
`“cipher” exclusive-ORed with “key” produces the orig-
`inal plain text.
`The algorithm was designed to operate on 64-bit
`blocks of input data; however, it can be operated (i.e.,
`cycled through the required [6 iterations) on any num-
`ber of input bits up to this maximum of 64 bits. As
`shown in FIG. 2, the algorithm 2-2 is being cycled once
`for each data input bit. Each time a data input bit is
`transferred into the 64-bit input register 24, the entire
`contents of this register 2-2 are transferred into the
`algorithm 2-2. Although 64 key bits are produced each
`cycle and are available at the output, only a single key
`bit is utilized and the other 63 key bits are ignored. Also
`shown in FIG. 2 within the dotted lines is an 8-bit out-
`put register 2-6. If the input to the algorithm is provided
`as a single character, or 8-bit byte, and then cycled, and
`8—bit byte of key bits can be provided as the output. It is
`important to note that with a fixed key variable, for a
`given pattern of 64 algorithm input bits, a given pattern
`of 64 output, or key bits is always generated.
`Shown at the top of FIG. 2 is a 64—bit shift register
`called the cipher feedback register 2-4. In the transmit
`mode as each input plain text bit is exclusive-ORed with
`a key bit by exclusive-OR 2-8, the resultant cipher bit is
`sent as the output bit and simultaneously entered into
`the cipher feedback register 24. Thus the input to the
`algorithm unit 2—2 which produces key bits is the last 64
`bits of the output cipher bit stream.
`In the receive mode, the system operates in a similar
`manner. In this instance the input to the unit is the same
`cipher bit stream produced at the transmitter output.
`Since this infomiation must be decrypted, the cipher bit
`stream is entered directly into the cipher feedback regis-
`ter 2-4 as shown. Hence, the input to the algorithm 2-2
`is the last 64 input cipher bits. By performing the in-
`verse operation of exclusive-ORing the cipher bits with
`the identical key bits as were generated in the transmit-
`ter, the original plain text is provided as the receiver
`output.
`In order for the encryption/decryption process to
`proceed without error, or garble, the bit patterns in the
`cipher feedback registers 2-4 of both transmitter and
`receiver must be identical when generating the key bit
`to
`
`produce the cipher bit from the incoming plain text
`bit in the transmitter, and
`to produce the original plain text bit from the incom-
`ing cipher text in the receiver.
`The method of ensuring that the transmitter and re-
`ceiver are in synchronization is to randomly preset the
`cipher feedback register 2-4 in the transmitter to some
`bit pattern and precede the output cipher text message
`with these 64 preset bits. The receiver would place the
`first 64 bits received into its cipher feedback register 24
`as the initial preset before running the algorithm to
`produce the same key bits which are then processed
`with the incoming data. This initialization technique is
`called variable fill.
`Variable fill refers to the bit pattern, or fill, to which
`both the transmitter and receiver cipher feedback regis-
`ters 2-4 are set before processing input plain text in the
`transmitter and cipher text in the receiver.
`When not in the transmit mode, the transmitter cipher
`feedback register 24 is run as a 49-bit shift code counter
`driven by the recursion X3 =X41 $1!55 shown in FIG. 3.
`The preset to the shift code counter is the cipher residue
`
`Unified Patents Inc. Ex. 1016, pg. 19
`
`Unified Patents Inc. Ex. 1016, pg. 19
`
`

`

`4,172,213
`
`7
`remaining from the last transmission. This assures that
`the preset to the counter is also random in nature.
`Whenever a variable fill is required, the transmitter
`cipher feedback register 2-4 is returned to its' normal
`operation: the shift code counting is inhibited; the algo-
`rithm unit 2-2 is re-enabled; and the register 2-4 is oper«
`ated at the selected input data rate. The input plain text
`data line is held in the mark condition and is exclusive-
`ORed with the key bits which are being generated as a
`result of the random bit pattern contained in the cipher
`storage register 24. A space is placed on the output data
`line and the operation proceeds as described, supra, for
`a predetermined number of bit times, i.e., cipher text is
`generated and sent as a variable fill as the transmitter
`output and simultaneously fed back as the input to the
`cipher feedback register 2-4. After the selected number
`of bits have been transmitted, the remainder of the bit
`positions in the cipher feedback register 2-4 are reset to
`zero, and the unit starts to process incoming plain text
`data as described previously.
`Operation of the receive unit is triggered by the de-
`tection of a mark-to-space transition. Following this
`transition, the incoming data is processed as described
`previously. However, the output data is inhibited. The
`incoming variable fill is entered into the cipher feedback-
`register 2-4 for the predetermined number of bits and
`when completed, the remainder of the cipher feedback
`register 2-4 is reset to zero.
`At this point, the receiver cipher feedback register
`24 contains the identical bit pattern as that contained in
`the transmitter cipher feedback register 2-4 when it
`started to process the incoming plain text data. Hence
`the receiver will at this point in time begin to process
`the incoming cipher text data to produce the original
`plain text data as its output.
`As explained previously, for a given key variable the
`algorithm 2-2 will always produce the identical 64 out-
`put key bi