Feistal框架和原理

本文包括：feistal加密解密，参数，验证过程 feistal结构并未指出具体F，因为无论F是什么，都可以消掉 .

起源

起初的密码领域始终无法逃脱统计分析的破译（凯撒密码，playfair密码，hill密码，vigenere等）。香农为了解决此事，提出了混淆和扩散两种方法

扩散（diffusion）：

使明文的统计规律散布到密文中，让每个明文影响多个密文的生成，也可以说，每个密文也是受到多个明文的影响。在二进制密码中，先对明文置换，再作用一个函数，多次重复后，会得到很好的扩散效果。即，这些来自明文的多个位，同时影响密文的某一位。

混淆（confusion）：

与扩散的原理类似，但它扩散的是密文与密钥之间的规律，目的是阻止他人根据密文分析出密钥。方式仍是复杂的算法。

扩散和混淆是分组密码的本质。

.

feistal结构（加密）

分组密码在统计分析的威胁下，feistal提出了乘积密码来逼近理想的分组密码。

乘积密码是 依次使用多个基本密码，最终所得结果的密码强度将强于所有单个密码的强度。

结构如图，

明文等分成LE₀和RE₀左右两部分LE₁=RE₀原封不动RE₁=F（RE₀，K₁）⊕LE₀

F可以理解成w位长的右半分组和y位长密钥的函数，输出w位长的值，即F（RE，K）。 .

每轮迭代都有相同的结构，相同的轮函数F，但不同密钥K不同（后面讲密钥间的联系）。（这种结构属于香农提出的SPN[代替置换网络]的一种特殊形式）。 . 最后一轮迭代之后，会将左右互换作为输出，即RE_n||LE_n。 .

feistal参数

分组长度：分组越长，扩散性越好 [DES分组64位，AES分组128位]密钥长度：密钥越长，混淆性越强 [通常128位]轮数：越多越好 （—，—）子密钥算法复杂度：越复杂越好 （—，—）轮函数F复杂度：越复杂越好 （—，—）

解密

解密结构与加密极其相似，仅是逆序使用密钥K_i 。 如图，（设加密迭代了16轮） 【注意】

为什么解密和加密是相同的结构（算法）？不应该是逆向计算才能解密吗？来验证一下。

验证解密能否真的解密？

****加密的最后一轮

LE₁₆ = RE₁₅RE₁₆ = F（RE₁₅，K₁₆）⊕LE₁₅

.

****解密的第一轮

LD₀ = LE₁₇ = RE₁₆

RD₀ = RE₁₇ = LE₁₆ .

LD1 = RD0 = LE16 = RE15

RD1 = F（RD₀，K₁₆）⊕LE₀

= F（LE₁₆，K₁₆）⊕ RE₁₆= F（RE₁₅，K₁₆）⊕ RE₁₆= F（RE₁₅，K₁₆）⊕ [ F（RE₁₅，K₁₆）⊕ LE₁₅ ]= [ F（RE₁₅，K₁₆）⊕ F（RE₁₅，K₁₆） ] ⊕ LE₁₅= LE₁₅

验证成功，符合上图结果，经过多次迭代，就可以恢复出明文。

【注】 XOR 运算的性质：

[ A ⊕ B ] ⊕ C = A ⊕ [ B ⊕ C ]D ⊕ D = 0E ⊕ 0 = E

. . .

补充二个知识点

.

1.DES的轮函数F如何工作？

将32-bit右半部和48-bit子密钥做以下动作：

（图在下面）

使用置换表E，将32位右半部分R扩展成48位 （扩充置换）。与48位子密钥做异或48位结果送给8个替换盒S-boxes，再变回32位的结果最后使用32位的置换表P，把32位结果再进行一次置换处理输出。（出去跟左半部分L异或）。 . .

2.这么多的子密钥，DES如何生成它们？

（图在下面）

密钥经过一次置换，输出56位的结果，记为K。K循环左移1次，再经过第二次置换，生成K₁。K循环左移2次，再经过第二次置换，生成K₂。… …K循环左移16次，再经过第二次置换，生成K₁₆。

注意：

K循环左移第100次 和 K循环左移第1次，他们的第二次置换算法都是一样的。也就是无论生成多少个密钥，其实置换函数只存在两种，造成各个子密钥不同的原因的循环左移。

. . . 图片素材截取自《密码编码学与网络安全：原理与实践》，自己做了适当调整。如有错误和不足，欢迎指出。

. . 边学边写边复习，编辑器用的不熟，DES具体细节请跳转 . . .