Feistel密码结构与DES加密算法

本文最后更新于:2022年4月3日 上午

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)。

Feistel Cipher

使用这种结构的好处是,加密和解密过程是对称的,只要将密文作为算法的输入,以相反的次序使用子密钥就能解密,以两个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的子密钥的算法。

DES总体预览

DES的F函数

E table

Permutation Logic

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

DES Specification

S-box

s-boxes

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

S-box Rule

DES_S-box table

P置换

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

P置换

IP和FP

子密钥

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

DES-key-schedule

PC1

PC2

参考文献:

田老师的PPT!

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

Data Encryption Standard (tutorialspoint.com)