P.121 Promblem 4.7

problem 4.7: Show that DES decryption is, in fact, the inverse of DES encryption.

设明文64位为p, 密钥56位为k，密文64位为c，encryption过程为E()，decryption过程为D()。

已知E(p, k) = c，要证D(c, k) = p。

 

decryption依然可以生成与encryption相同16个子密钥，依然可以为k1, k2..., k16，只是倒序使用，Round 1用的是k16, Round 2用的是k15，依此类推，Round 16用的是k1。

以上是encryption和decryption的round的比较，注意：decryption的是从下往上看的。

令encryption的Initial permutation后分组分别为LE0和RE0，Round i之后的分组分别是LEi和REi。

令decryption的Initial permutation后分组分别为LD0和RD0，Round i之后的分组分别是LDi和RDi。

(1 <= i <= 16)

LEi = REi-1;
REi = LEi-1 ⊕ F(REi-1, ki);

LDi = RDi-1;
RDi = LDi-1 ⊕ F(RDi-1, k(16 - i + 1));

F()是一连串的变换的组合，但是可以确定F()在参数一样的情况下的输出是相同的，因为F()中没有随机的操作。

可得：
LD0 = RE16;
RD0 = LE16;

可证：
LDi = RE16-i, RDi = LE16-i, 0 <= i <= 16;

用归纳法证明如下：

1. 

LD0 = RE16;
RD0 = LE16;

2.

在LDi-1 = RE16-i+1, RDi-1 = LE16-i+1成立的情况下，可证LDi = RE16-i, RDi = LE16-i。

由于用i做下标写得比较混乱，所以证明过程以i = 1为例。

LD0 = RE16;
RD0 = LE16;

LE16 = RE15;
RE16 = LE15 ⊕ F(RE15, k16);

LD1 = RD0 = LE16 = RE15;
RD1 = LD0 ⊕ F(RD0, k16) = RE16 ⊕ F(LE16, k16) = LE15 ⊕ F(RE15, k16) ⊕ F(RE15, k16)

XOR运算性质：
A ⊕ B ⊕ C = A ⊕ (B ⊕ C)
A ⊕ A = 0
A ⊕ 0 = A

RD1 = LE15 ⊕ (F(RE15, k16) ⊕ F(RE15, k16)) = LE15 ⊕ 0 = LE15

得证：LDi = RE16-i, RDi = LE16-i, 0 <= i <= 16;

令i = 16，LD16 = RE0, RD16 = LE0。

32bits swap后即为(LE0, RE0)。

令Initial permutation操作为IP()，Inverse initial permutation操作为IIP()，

由于IP(p) = (LE0, RE0)，则IIP((LE0, RE0)) = p。

即D(c, k) = p。

所以Decryption是Encryption的逆运算。