暗号化三番

今回の記録の最初のキースケジュールの話はWikipediaの説明を元にしています。そのあとの計算式の分析はMirza教授の論文を参照しています。
In the DES encryption algorithm, sixteen rounds are used, requiring sixteen subkeys. A subkey is a key derived from the original key known by encryptor and decryptor. From the original 64 bits of the key, 56 are selected by Permuted Choice 1 (PC-1) and divided into two 28-bit halves. These halves are used separately in all sixteen rounds. In each round, each half is rotated left by one or two bits (i.e. 1001->0011 if the cyclic shift is one bit), and 24 bits are selected from each half by the Permuted Choice 2 (PC-2) algorithm. Due to the rotation, each bit in each half is used in approximately 14 of sixteen possible subkeys, although I have not read a proof of this. Note that, in decryption, the same subkeys are used but applied in reverse order (i.e. encryption subkey 16 is used in decryption round one). Thus, due to the fact that an extra permutation is applied after the last round function in both encryption and decryption (undoing the last swap), identical functions can be used for encryption and decryption with only the order of subkey application differing. Thus, DES is considered E-D similar.
I was unclear about why the extra permutation is needed at the end. The easiest way to see this is to consider a one-round algorithm. The substitution function sigma is an involution, i.e. sigma^2 = 1. sigma(Li,Ri) = sigma(L(i-1)XOR F(R(i-1),Ki), R(i-1)). If we encrypt using sigma and K1, we can recover (L,R) plaintext by decrypting with the same subkey. However, if we use a swap of L and R called pi, pi(L,R) = (R,L), after sigma, the function is not an involution. i.e. pi(sigma(pi(sigma(L,R))))!=(L,R). However, if we apply pi a second time after the permutation, i.e. pi(pi(sigma)), we are left with sigma. If the decryption algorithm applies sigma first, we are left with the plaintext. Applying pi to this yields pi(L,R). So we apply pi again to undo the swap, yielding the plaintext. To comprehend why this works in a multi-round function, consider what the input to each decryption round will be in an n-round function. In round one of decryption, the input will be the output of encryption round n's sigma (due to extra pi at end of encryption). Applying sigma to this obtains the output of encryption round n-1, and applying pi to this yields the output of round n-1's sigma function. Continuing this process n times will yield the reverse of the plaintext, or (R,L). Applying the extra permutation will obtian (L,R).