Electrical computers and digital processing systems: support – Multiple computer communication using cryptography
Reexamination Certificate
1999-02-24
2003-02-25
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
C713S151000, C713S153000, C713S168000
Reexamination Certificate
active
06526505
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of data communications, and in particular to the field of secure data communications via systems that employ the Data Encryption System (DES) encryption algorithm.
2. Description of Related Art
The Data Encryption System (DES) encryption algorithm is one of the most widely used symmetric key ciphers in the world. The DES encryption algorithm and associated standards were developed in an era when 8-bit devices and architectures were prevalent. The DES standard includes a permutation of a 64-bit internal data structure to a sequence of 8-bit data elements, to facilitate the use of an 8-bit bus structure.
FIGS. 1 and 2
illustrate the permutation of the DES 64-bit structure to and from an 8-bit structure.
In
FIG. 1
, a 64-bit shift register
100
simultaneously transfers eight selected bits
108
,
116
,
124
,
132
,
140
,
148
,
156
, and
164
to an 8-bit output register
190
. The output register
190
is conventionally associated with an 8-bit data bus (not shown). Another device on the data bus, for example, the transmitter
520
in
FIG. 5
, can thereafter access these eight bits via the data bus, for subsequent actions, such as transmission to a receiver
570
in FIG.
5
. After the eight bits are “unloaded”
171
onto the data bus, the 64-bit shift register
100
shifts each of its bits down, in the direction of the shift arrow
172
. In so doing, the contents of the register at the eight selected bit locations
108
,
116
,
124
,
132
,
140
,
148
,
156
, and
164
receive the value of the previously immediately adjacent bit locations
107
,
115
,
123
,
131
,
139
,
147
,
155
, and
163
. These new values at the eight selected bit locations are transferred to the 8-bit output register
190
, for subsequent access by the other device or devices on the data bus. This unload
171
and shift
172
process is repeated until the 64-bit data in shift register
100
is communicated as eight 8-bit data elements via the register
190
. That is, after seven shifts, the value from the first bit location
101
of shift register
100
will be located in the selected bit location
108
, and transferred to the output register
190
. As illustrated in
FIG. 1
, the contents of the eight selected bit locations
108
,
116
,
124
,
132
,
140
,
148
,
156
, and
164
are transferred to the output register
190
in a permuted form. The fortieth register
140
of shift register
100
is associated with the first bit location
191
of shift register
190
; the eighth register
108
of shift register
100
is associated with the second bit location
192
of the shift register
190
; and so on.
In
FIG. 2
, a 64-bit shift register
200
simultaneously receives eight selected bits
201
,
209
,
217
,
225
,
233
,
241
,
249
, and
257
from an 8-bit input register
290
. The input register
290
is conventionally associated with an 8-bit data bus (not shown), and corresponds to the output register
190
. The registers
190
,
290
are presented herein for ease of understanding; in many embodiments, the 8-bit data is presented directly to the 8-bit data bus from the shift registers
100
,
200
, without the use of the intervening registers
190
,
290
. That is, for example, the transmitter
520
in
FIG. 5
will receive the aforementioned selected bits from a register
100
in the encrypter
510
via the 8-bit register
190
, or an 8-bit data bus, and transmit these bit values to the receiver
570
; the receiver
570
will place the received eight bits from the transmitter
520
into the 8-bit register
290
, or onto an 8-bit data bus, for subsequent access by a decrypter
560
that contains the
64
bit shift register
200
. After receiving the data from the 8-bit register
290
, the 64-bit shift register
200
shifts each of its bits down, in the direction of the shift arrow
272
. In so doing, the contents of the shift register
200
at the eight selected bit locations
201
,
209
,
217
,
225
,
233
,
241
,
249
, and
257
transfer the value to the immediately adjacent bit locations
202
,
210
,
218
,
226
,
234
,
242
,
250
, and
258
. After the contents of the 64-bit shift register
200
are shifted, the next 8-bit data element
290
B is received into the data register
290
, and thereby communicated to the eight selected bit locations
201
,
209
,
217
,
225
,
233
,
241
,
249
, and
257
. This shift
272
and load
271
process is repeated until the eight 8-bit data elements
290
A,
290
B,
290
C,
290
D,
290
E,
290
F,
290
G, and
290
H are loaded via the 8-bit register
290
into the 64-bit shift register
200
. That is, for example, after seven shifts, the value from the second bit location
292
of the first 8-bit data element
290
A will be located in the eighth bit location
208
of shift register
200
, while the value from the second bit location
292
of the last 8-bit data element
290
H will be located in the first bit location
201
of shift register
200
. The values of the second bit location
292
of each of the intermediate 8-bit data elements
209
B-
209
G will be located in the seventh
207
through second
202
register locations of the shift register
200
. As illustrated in
FIG. 2
, the contents of the output register
290
are transferred to the eight selected bit locations
201
,
209
,
217
,
225
,
233
,
241
,
249
, and
257
in a permuted form. This permuted form is the inverse of the permutation effected between the selected bit locations
108
,
116
,
124
,
132
,
140
,
148
,
156
, and
164
of the 64-bit shift register
100
and the output register
190
, illustrated in FIG.
1
.
The DES permuted 64-bit transfer to and from an 8-bit data structure is fairly efficient in a system that uses an 8-bit architecture. However, an 8-bit architecture is no longer common in the art, having been supplanted by the common use of a 32-bit architecture. As illustrated in
FIGS. 3 and 4
, the conventional DES permuted 64-bit transfer is not particularly well suited to a system that uses a 32-bit architecture. As would be evident to one of ordinary skill in the art, because of the number of crossovers in the transfer paths
380
(
480
) of
FIG. 3
(
4
) between the 64-bit shift register
300
(
400
) and the 32-bit data register
390
(
490
) the physical layout of the wiring between the shift register
300
(
400
) and the data register
390
(
490
) can be expected to be complex and area inefficient. Additionally, the structure presented in
FIG. 3
(
4
) requires a 4-bit shift between unload (load) operations. To avoid the time required for a 4-bit shift, alternative architectures are used that employ non-standard devices and structures, requiring more time and effort to design and layout than conventional devices and structures. In like manner, in a software-based DES system, non-standard algorithms are typically required to move the contents of the shift register
300
to the data register
390
, and the contents of the data register
490
to the shift register
400
, because of the complex and somewhat non-algorithmic nature of the mapping.
BRIEF SUMMARY OF THE INVENTION
It is an object of this invention to provide a DES permutation that is well suited for data transfers of 64-bit DES data structure to and from a 32-bit data structure. It is another object of this invention to provide a DES permutation that is area efficient for hardware implementations. It is another object of this invention to provide a DES permutation that is efficient in processing and transfer time. It is another object of this invention to provide a DES permutation that is computationally efficient for software implementations.
These objects and others are accomplished by providing a DES permutation that has minimal crossovers between the DES 64-bit structure and the 32-bit data structures, allows for efficient data transfer, and is easily encoded as a software algorithm. Every other bit location in the DES 64-bit data structure is mapped to a contiguous bit location
Koninklijke Philips Electronics , N.V.
Peeso Thomas R.
Piotrowski Daniel J.
LandOfFree
DES encryption system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with DES encryption system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and DES encryption system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122582