Question

有关DES算法的一道证明题

最好通过互补性来证明 也可以用其他方法 要详细过程 可手写然后上传照片

Answer 1

证明：DES算法的加密算法和解密算法是完全一样的，所不同的是密钥以相反的顺序依次加入到轮函数中。

DES算法的加密流程如下：
（1）生成子密钥
首先，将64比特的密钥（实际有效位数只有56比特）进行置换，得到56比特的密钥串；
然后，将56比特的串分为两个28比特的子串，经过16轮的循环左移以及合并置换，生成16个子密钥，记为K1K2K3...K16；
（2）加密
首先，将64比特的明文W做初始置换，得到结果IP（W）；
将结果分成两个32比特的子串，记为L0和R0，所以L0R0=IP（W）；
然后，根据L0、R0以及K1，求得L1和R1，具体如下：
L1=R0，即L1跟R0完全相同；
R1=P(S(E(R0)^K1))^L0，其中：
E(R0)表示对R0做扩展置换；
E(R0)^K1表示上一步的结果与K1做异或运算；
S(E(R0)^K1)表示上一步的结果做S-box运算；
P(S(E(R0)^K1))表示上一步的结果做置换；
P(S(E(R0)^K1))^L0表示上一步的结果与L0做异或运算。
以上的过程就是一次轮函数。如此，再由L1、R1以及K2，求得L2R2。以此类推，经过16次轮函数的迭代即可求得L16R16。
最后，把L16R16交换顺序，得到R16L16，再经过一次逆置换FP(R16L16),可以得到64比特的密文C,所以C=FP（R16L16）。

我们知道，DES的解密只需将16个子密钥以相反的顺序加入到轮函数中，重复加密的步骤即可。 现在我们要证明DES加密和解密的算法是完全一样，只是子密钥使用的顺序相反。也就是说，我们要证明密文经过子密钥顺序相反的加密之后可以得到明文。
DES算法的解密流程如下：
（1）生成子密钥
解密的时候使用的子密钥与加密时的顺序相反，记为K16K15...K2K1；
（2）解密
首先，将64比特的密文C做初始置换IP（C），
由于C=FP（R16L16），所以IP（C）=IP（FP（R16L16））=R16L16，因此得到的结果为R16L16。
将结果分成两个32比特的子串，也就是R16和L16。
然后，对其进行轮函数运算，结果记为XY，具体如下：
X=L16，
Y=P(S(E(L16)^K16))^R16。
从加密的过程中，我们知道，
L16=R15,
R16=P(S(E(R15)^K16))^L15，
因此，Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15。
由于L16=R15，所以P(S(E(L16)^K16))=P(S(E(R15)^K16))，
所以P(S(E(L16)^K16))^P(S(E(R15)^K16))=00000000000000000000000000000000，
因为00000000000000000000000000000000^L15=L15，
所以Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15=L15。
由此可知，R16L16经过一次轮函数之后，得到的结果是R15L15。
如此，在对R15L15做轮函数运算，得到R14L14。以此类推，经过16次轮函数的迭代，得到R0L0。
最后，把R0L0交换顺序，得到L0R0，再经过一次逆置换FP（L0R0）=FP（IP（W））=W，就得到了明文W。
综上所述，DES算法的加密算法和解密算法是完全一样的，所不同的是密钥以相反的顺序依次加入到轮函数中。