以 Verilog 描述 DES 加密算法 (电子书)

目录：

1. 简介

2. 非线性 S-box

3. 加密函数 Cipher function

4. Sub-Key 的产生

5. 整个加密流程

这里,我们是将整个算法拆解, 以 bottom-up 的方式, 逐一介绍它的原理与其 Verilog 的写法

简介

DES, Data Encryption Standard, 是一个相当普遍, 流传相当久远的算法,现在网络上常用的 SET, SSL, SSH 都是以 DES 为基础来执行加解密的动作

DES 加密函数可以用函数表示:

cipher[1:64] = des(plaintext[1:64], key[1:56])

它将 64bits 的输入用一个类似洗牌的交错动作产生 64bits 的输出, 与洗牌不同的是, 它还可以洗的回来

plaintext[1:64] = des_inverse(cipher[1:64], key[1:56])

也就是将 64bit 的输出再还原回原先的那 64bit,而这个洗牌动作的控制就在于那个 56bits 的 key

非线性 S-box

S-box 是整个算法唯一非线性的部分, 也被怀疑是美国政府留下后门的地方

在整个加密过程中, 会用到 8 个类似的 S-box, (如下图)

<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 344.25pt; HEIGHT: 247.5pt" alt="" type="#_x0000_t75"><imagedata o:href="http://www.icdiy.org/images/archive/des.gif" src="file:///C:%5CDOCUME~1%5CWast%5CLOCALS~1%5CTemp%5Cmsohtml1%5C02%5Cclip_image001.gif"></imagedata></shape>

其函数可表示为

Out[4] = S(In[6])

以 S1 为例子, 输出的 4bit, 由下表决定 由{In[1],In[6]}决定列数, {In[2:5]}决定行数

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

用 verilog 写来的模块如下

module sbox1(addr, dout);

input [1:6] addr;

output [1:4] dout;

reg [1:4] dout;

always @(addr) begin

case ({addr[1], addr[6], addr[2:5]}) //synopsys full_case parallel_case

0: dout = 14;

1: dout = 4;

2: dout = 13;

3: dout = 1;

...

62: dout = 6;

63: dout = 13;

endcase

end endmodule

其实从硬件的角度来看 S-box 就是一个 64x4 的 ROM

加密函数 Cipher function

现在, 接着介绍 S-BOX 如何应用于整个加密函数

整个 DES 函数 64 bits 的输入数据和 56 bits 的 key 经过一些前处理后得到

32 bits 的输入数据 R 和 48 bits 的 sub-key K 输入此加密函数

下图是整个加密函数方块图

<shape id="_x0000_i1026" style="WIDTH: 344.25pt; HEIGHT: 247.5pt" alt="" type="#_x0000_t75"><imagedata o:href="http://www.icdiy.org/images/archive/des.gif" src="file:///C:%5CDOCUME~1%5CWast%5CLOCALS~1%5CTemp%5Cmsohtml1%5C02%5Cclip_image001.gif"></imagedata></shape>

首先, 32 BITS 的数据 R 先经过一个延伸表 E (如下表) 转为 48 BITS

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

例如, 第一个 BIT 放 R[32], 第二个 BIT 放font-size: 10pt; color: black; fo