Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Reexamination Certificate
1997-05-20
2001-10-02
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
C380S028000
Reexamination Certificate
active
06298136
ABSTRACT:
BACKGROUND OF THE INVENTION
CROSS REFERENCE TO RELATED APPLICATIONS
1. Field of the Invention
The invention relates to a method for converting a digital input block into a digital output block; said conversion comprising the step of merging a selected part M
1
of the digital input block with a first key K1 and producing a data block B1 which non-linearly depends on the selected part M1 and the first key K1, and where a selected part of the digital output block is derived from the data block B1.
The invention further relates to an apparatus for cryptographically converting a digital input block into a digital output block; the apparatus comprising first input means for supplying the digital input block; second input means for supplying a first key K1; cryptographic processing means for converting the digital input block into the digital output block; such conversion comprising merging a selected part M1 of the digital input block with the first key K1 and producing a data block B1 which non-linearly depends on the selected part M1 and the first key K1, and where a selected part of the digital output block is derived from the data block B1; and output means for outputting the digital output block.
2. Description of the Related Art
The Data Encryption Standard (DES) of the National Bureau of Standard [FIPS publication 46, Jan. 15, 1977] describes a widely used algorithm for converting a digital input block into a digital output block. Such an algorithm is generally referred to as a block cipher. The DES algorithm is used for encrypting (enciphering) and decrypting (deciphering) binary coded information. Encrypting converts intelligible data, referred to as plaintext, into an unintelligible form, referred to as ciphertext. Decrypting the ciphertext converts the data back to its original form. In the so-called electronic code book mode, DES is used to encrypt blocks of 64 bits of plaintext into corresponding blocks of 64 bits of ciphertext. In this mode, the encryption uses keys which are derived from a 64 bit key, of which 56 bits may be freely selected.
FIG. 1
shows the overall structure of DES during encrypting. In the encrypting computation, the input (64 bit plaintext) is first permuted using a 64 bit fixed permutation IP. The result is split into 32 left bits L
0
and 32 right bits R
0
. The right bits are transformed using a cipher function f(R
0
,K
1
), where K
1
is a sub-key. The result f(R
0
, K
1
) is added (bit-wise modulo 2) to the left bits, followed by interchanging the two resulting 32 bit blocks L
0
⊕ f(R
0
,K
1
) and R
0
. This procedure is continued iteratively for a total of 16 rounds. At the end of the last round the inverse permutation of the initial permutation IP is applied.
In the calculation of f(R
i
,K
i+1
) the 32 right bits R
i
are first expanded to 48 bits in the box E, as illustrated in FIG.
2
. According to a given table this expansion is performed by taking some input bits twice as an output bit and others only once. Then, the expanded 48 bits are added (bit-wise modulo 2) to the 48 key bits K
i
. The resulting 48 bits are split into 8 groups of 6 bits each. Each of these groups is processed by an S box (S
i
), which reduces the 6 bits to 4 bits in a non-linear operation. The eight S
i
boxes are given in the form of a table. The total output is 32 bits, which is permuted in the box P. P is also given in the form of a table.
FIG. 3
illustrates the key schedule calculation. The key consists of 64 bits, of which only 56 are used in the algorithm. Those 56 bits should be chosen randomly. Eight complementing error detecting bits are used to make the parity of each byte of the key odd. The selection of the 56 bits is performed in box PC1, together with a permutation. The result is split into two 28 bit words C
0
and D
0
. To obtain the 48 key bits for each round, first the words C
0
and D
0
are left shifted once or twice. A selection and a permutation PC2 are then applied to the result. The output of PC2 is the 48 bit sub-key K
i
which is used in f(R
0
,K
i
). The process of shifting, selecting and permutating is repeated to generate a sub-key for each round. A table specifies how many shifts must be performed to obtain the next 48 bits of the sub-key for the following round.
The same algorithm and key can be used for decrypting a ciphertext. The initial permutation for the decrypting cancels the inverse permutation of the encrypting. Each round consists of a, so-called, Feistel cipher. It is well-known that for Feistel-ciphers the inverse operation consists of using the same rounds as used for encrypting but applying the sub-keys in inverse order. As such, the first decrypting round must be supplied with the same sub-key as used for the sixteenth encrypting round, the second decrypting round must be supplied with the same sub-key as used for the fifteenth encrypting round, etc. It is also well-known how the DES algorithm can be used in other encryption modes, such as the cipher feedback mode. In this mode, the DES algorithm is used to generate a stream of statistically random binary bits, which are combined with the plaintext, using, for instance, an exclusive-or logic operation.
The DES algorithm, in essence, comprises an initial permutation, followed by sixteen key-dependent computations on part of the data and terminated with an inverse permutation. Each key dependent computation comprises adding (module 2) key-dependent bits to the data part, followed by a non-linear operation on sub-blocks of the data part, and terminated by a permutation (linear operation) of the data part.
In general, DES is considered to be a good encryption/decryption tool. It is, however, an open question whether or not DES has remained secure over the past years, particularly in view of the recent very powerful differential cryptanalytic attacks.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a cryptographic method and apparatus of the kind set forth which is more robust against cryptanalytic attacks.
To achieve this object, the cryptographic method according to the invention is characterised in that the step of emeriging the data and the key is performed by executing a non-linear function g for non-linearly merging said selected part M1 of the data and said first key K1 in one, sequentially inseparable step. In the DES system, as shown in
FIG. 2
, in a first processing step the R data is bit-wise added to the key, followed by a second processing step of non-linearly processing the result (S-boxes). According to the invention, an algorithm is used which non-linearly merges data with a key in one step (i.e. one, sequentially inseparable step). As such, adding the key bits to the data is an integrated part of the non-linear operation, making the system more immune against modern attacks, such as differential cryptanalysis.
In an embodiment of the method according to the invention, in each round both parts of the digital input block are processed, giving a better encryption result than for conventional Feistel ciphers, such as DES, where during each round only half of the digital input block is being processed. To ensure that the same system can be used for both encryption and decryption, one part of the data is processed using an operation g, whereas the other half is processed using the inverse operation g
−1
. Using this scheme, decrypting is performed by using the same system but supplying the keys in reverse order to the rounds (during decryption the first non-linear step is supplied with the key which, during encryption, was supplied to the last non-linear step, etc ). Compared to a conventional implementation of a Feistel cipher with twice as many rounds, the system according to the invention is faster.
The measure of splitting a relatively large data block and key, of for instance 64 bits, into smaller sub-blocks and sub-keys simplifies real-time non-linear processing.
In an embodiment of the method according to the invention, a constant is used to enhance the quality of the encryption. Advantageously, the co
Hayes Gail
Seal James
Thorne Gregory L.
U.S. Philips Corporation
LandOfFree
Cryptographic method and apparatus for non-linearly merging... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic method and apparatus for non-linearly merging..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic method and apparatus for non-linearly merging... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2616944