Feistel密码结构与DES加密算法

Feistel

Feistel是现代密码学常用的分组密码结构，1973年，Horst Feistel提出了基于可逆乘积加密器概念的Feistel Cipher。

其将输入分组成左半和右半两部分（$L_0,R_0$），每轮加密把右半放到左边，然后把左半结合子密钥进行计算：$R_i=L_{i-1}\oplus F(R_{i-1},K_i)$，其中$K_i$是由密钥$K$得到第$i$轮的子密钥，$F()$是轮函数，可以随意设计，只要对于一个输入有一个固定的输出就可以了（假如不考虑安全性）。

一般来说，分组越长、密钥越长、迭代轮次越多，安全性也越高，但是算法速度就会越低。同时轮函数的设计对安全性也很重要，需要做到非线性、混乱性、雪崩性（改动1bit就会影响很多个bit）。

使用这种结构的好处是，加密和解密过程是对称的，只要将密文作为算法的输入，以相反的次序使用子密钥就能解密，以两个round为例子：

DES

DES使用64bit分组，56bit秘钥（使用时是64bit，其中8bit没有用），进行16轮加密变换。DES的F函数如下，$R_{i-1}$先经过一个将32bit映射为48bit的E table，再与密钥异或，再进入S-box映射回32bit，最后进行P置换。除此以外，DES还在最初和结束时额外进行了一次置换，称为IP和FP，其中FP是IP的反函数。DES还有一种使用56bit秘钥生成16个48bit的子密钥的算法。

E table

多出来的16bit通过上图所示得到，没进行什么计算，也可以画成下面这个表

S-box

如上图，对于每6bit进行一个计算得到4bit，从而把多出来的16bit弄掉，具体规则如下图，bit2到5组成一个4位的二进制数，选择0到15的一个数，而bit1和bit6选择0到3的一个数，然后通过一个固定的S-box table得到那4个输出bit。S-box的table每一轮是一样的，但是同一轮中每6个bit组是不一样的。

P置换

就是一个简单的映射，每一轮都一样，对于开始和结束的IP和FP（也叫做IP^-1）也是一个表格，如图可以看到IP的1是第40个，也就是40->1，而FP是1->40。

子密钥

如图，64bit密钥先进行PC1（置换1），PC1将密钥的64bit的第$n*8$个bit丢弃，然后重排顺序得到两个28bit。之后每一轮左移k个bit（第1 2 9 16轮k=1，其余k=2）（没找到资料，应该是循环左移？）。然后每一轮执行PC2（置换2）得到子密钥。

参考文献：

田老师的PPT！

algorithm design - Are there any specific requirements for the function $F$ in a Feistel cipher? - Cryptography Stack Exchange

Data Encryption Standard (tutorialspoint.com)