暗号化の続き

One of the most common encryption techniques is called Feistel cipher, named for Horst Feistel of IBM. It is a multi-round algorithm where each round involves substitution (using the cipher function F) and permutation. A distinctive feature of the Feistel cipher is that the plaintext is divided into two halves: left and right. In each round, the left half of the previous round's output is used to encrypt the right half, and the left half is typically set to be the previous round's right half.
PlaintextHalf(left round 1) PlaintextHalf(right round 1)

--------------

XOR------------------------------F

• • • • • • • • • • • • • • • • • • • |-------------

| |

• • • • • • • • • • • • • • • • • • • |

Left (round 2) Right (round2)

A canonical example of Feistel cipher encryption is the Data Encryption Standard algorithm (DES), which for many years was the standard cipher used by United States government agencies. In DES, the cipher function consists of four parts: expansion, key mixing, substitution, and permutation.
1. Expansion- a 32-bit plaintext half is expanded to 48-bits. The expansion permutation duplicates some bits.
2. Key mixing: an XOR operation combines a subkey with the expanded plaintext half.
3. Substitution: the output of the key mixing is divided into eight six-bit blocks. Each block is fed into a separate S-box, where it is converted to a four-bit output by a lookup table. (This causes the output to be 32-bits, so that the input to round i+1 has the same number of bits as the input to round i).
4. Permutation: 32-bit S-box outputs are permuted by a P-box permutation.
Two questions I have are:
1. The article claims that, without S-box lookup, the cipher would be linear and trivially solvable. Is this true? Without the permutation or S-boxes, Ri = L(i-1) XOR (R(i-1)XOR Ki). In a one-round cipher where one plaintext and one ciphertext are known, Ki = Ri XOR L(i-1) XOR R(i-1)
Note that this calculation assumes that the elimination of the S-boxes causes the elimination of expansion. This is solvable, as XOR is its own inverse. Is it linear, though? i.e. Does doubling the key actually induce a change in the ciphertext linearly related to 2 (i.e. 2x+b)?
2. Does DES have diffusion? i.e. Is every bit of the ciphertext dependent on every bit of the plaintext and every bit of the key? Permutation and expansion seem to induce this.
3. Is confusion in DES caused by S-box lookups? A lookup table would induce non-linearity, although I am not sure that this is the only source of non-linearity (i.e. permutation and expansion might also account for this).
Key Schedule