第三章 现代加密方法 1 简化的DES DES-Data Encryption Standard (1977年元月15日-美国联邦标准） 1998年！！ Simplified DES方案，简称S-DES方案。 注：1.* 加密算法涉及五个函数： (1)初始置换IP(initial permutation)

Presentation on theme: "第三章 现代加密方法 1 简化的DES DES-Data Encryption Standard (1977年元月15日-美国联邦标准） 1998年！！ Simplified DES方案，简称S-DES方案。 注：1.* 加密算法涉及五个函数： (1)初始置换IP(initial permutation)"— Presentation transcript:

1 第三章 现代加密方法 1 简化的DES DES-Data Encryption Standard (1977年元月15日-美国联邦标准） 1998年！！ Simplified DES方案，简称S-DES方案。 注：1.* 加密算法涉及五个函数： (1)初始置换IP(initial permutation) (2)复合函数fk1，它是由密钥K确定的，具有转换和 替换的运算。 (3)转换函数SW (4)复合函数fk2 (5)初始置换IP的逆置换IP-1

2 S-DES方案示意图 10bit密钥 加密 解密 P10 8bit明文 8bit明文 IP 移位 IP-1 P8 fk fk SW 移位

3 2*. 加密算法的数学表示： IP-1*fk2*SW*fk1*IP 也可写为 密文=IP-1（fk2(SW(fk1(IP(明文))))) 其中 K1=P8(移位(P10(密钥K))) K2=P8(移位(移位(P10(密钥K)))) 解密算法的数学表示： 明文=IP-1（fk1(SW(fk2(IP(密文)))))

4 对S-DES的深入描述 （1） S-DES的密钥生成： 设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7, k8,k9,k10) 置换P10是这样定义的 P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 相当于 P10= LS-1为循环左移，在这里实现左移2位 P8= 按照上述条件,若K选为( ), 产生的两个子密钥分别为K1=( ),K2=( )

5 S-DES的密钥生成 10-bit密钥 P10 LS-1 LS-1 5 5 P8 8 K1 LS-2 LS-2 5 5 P8 8 K2

6 (2) S-DES的加密运算: 初始置换用IP函数: IP= 末端算法的置换为IP的逆置换: IP-1= 易见IP-1(IP(X))=X

7 S-DES加密图 8-bit 明文 IP fk L R 4 E/P 4 8 + K1 F 4 4 S0 S1 P4 +

8 S-DES加密图(续) SW 4 4 fk E/P 8 8 K2 F + 4 4 S0 S1 2 2 P4 + 4 IP-1 8
8-bit 密文

9 函数fk，是加密方案中的最重要部分，它可表示为：
fk(L,R)=(LF(R,SK),R) 其中L，R为8位输入, 左右各为4位, F为从4位集到4位集的一个映射, 并不要求是1-1的。SK为子密钥。 对映射F来说： 首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算： E/P 事实上，它的直观表现形式为： n4 n1 n2 n3 n2 n3 n4 n1

10 8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：
n4+k11 n1+k12 n2+k13 n3+k14 n2+k15 n3+k16 n4+k17 n1+k18 把它们重记为8位： P0,0 P0,1 P0,2 P0,3 P1, P1,1 P1,2 P1,3 上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：

11 将第1和第4的输入比特做为2- bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。
例如：（P0,0, P0,3）=(00),并且(P0,1,P0,2)=(1 0) 确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出。 由S0, S1输出4-bit经置换 P4 它的输出就是F函数的输出。

12 2 DES的描述 DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文
该算法分三个阶段实现： 1. 给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。 X0=IP（X）=L0R0 其中L0由X0前32位组成，R0由X0的后32位组成。 2.计算函数F的16次迭代, 根据下述规则来计算LiRi(1<=i<=16） Li=Ri-1, Ri=Li-1  F(Ri-1, Ki) 其中Ki是长为48位的子密钥。子密钥K1，K2，…，K16是作为密钥K（56位）的函数而计算出的。 3.对比特串R16L16使用逆置换IP-1得到密文Y。 Y=IP-1（R16L16）

13 一轮加密的简图 Li-1 Ri-1 F Ki + Li Ri

14 对F函数的说明：（类比于S-DES）F（Ri-1, Ki） 函数F以长度为32的比特串A=R（32bits）作第一个输入，以长度为48的比特串变元J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。 (1)对第一个变元A，由给定的扩展函数E，将其扩展成48位串，E（A） (2)计算E（A）+J，并把结果写成连续的8个6位串, B=b1b2b3b4b5b6b7b8 (3)使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取0~15的整数。给定长度为6个比特串，如 Bj=b1b2b3b4b5b6 计算Sj(Bj)如下：b1b6两个比特确定了Sj的行数, r(0<=r<=3); 而b2b3b4b5四个比特确定了Sj的列数c（0<=c<=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）, 得Cj=Sj(Bj)。 (4) 最后，P为固定置换。

15 A=R(32 bits) J=K(48 bits) E(A)为48 bits E + 写成8个6比特串 B
B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 P 32 bits F(A,J) DES 的F函数

16 DES中使用的其它特定函数： 初始置换IP：见68页表3
DES中使用的其它特定函数： 初始置换IP：见68页表3.2, 从表中看出X的第58个比特是IP（X）的第一个比特；X的第50个比特是IP（X）的第二个比特… 逆置换IP-1；扩展函数E；置换函数P。 从密钥K计算子密钥： 实际上，K是长度为64的位串，其中56位是密钥，8位是奇偶校验位（为了检错），在密钥编排的计算中，这些校验位可略去。 (1). 给定64位的密钥K，放弃奇偶校验位（8，16，…，64）并根据固定置换PC-1（见72页表3.4（a））来排列K中剩下的位。我们写 PC-1(K)=C0D0 其中C0由PC-1（K）的前28位组成；D0由后28位组成。

17 (2)对1<=i<=16，计算 Ci=LSi(Ci-1) Di=LSi(Di-1) LSi表示循环左移2或1个位置，取决于i的的值。i=1,2,9和16 时移1个位置，否则移2位置。 Ki=PC-2(CiDi), PC-2为固定置换, 见72页3.4(b)。 注：一共16轮，每一轮使用K中48位组成一个48比特密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如： 第7轮的表7：K7取K中的比特情况：

18 图表（密钥生成Ki） K PC-1 C0 D0 LS1 LS1 C1 D1 PC-2 K1 LS2 LS2 … LS16 LS16

19 DES加密的一个例子 取16进制明文X： ABCDEF 密钥K为： BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是 应用IP，我们得到： L0= L1=R0= 然后进行16轮加密。 最后对L16, R16使用IP-1得到密文：85E813540F0AB405

20 3 DES的争论 DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。
1976年美国NSA提出了下列几条S盒的设计准则： 1. S盒的每一行是整数0，…，15的一个置换 2. 没有一个S盒是它输入变量的线性函数 3.改变S盒的一个输入位至少要引起两位的输出改变 4.对任何一个S盒和任何一个输入X，S（X）和 S(X001100）至少有两个比特不同（这里X是长度为6的比特串） 5.对任何一个S盒，对任何一个输入对e,f属于{0,1}, S(X) S(X11ef00)

21 6. 对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目。
参见74页3.4 DES的强度。

22 4 差分密码分析与线性密码分析 (1)差分密码分析 对DES有效的分析方法--差分分析方法，是由E.Biham和A.Shamir提出的。见 Differential Cryptanalysis of DES-like Cryptosystems. E.Biham A.Shamir The Weizmann Institute of ScienceDepartment of Aplied Mathematics June 18,1999 该文给出选择性明文攻击，是一个很有效的方法。对于攻击8轮DES，在486那样的计算机上，只需2分钟可攻破。

23 首先说明： 1. 对于DES的分析，可忽略初始置换IP和IP-1。 2. 对DES限制到n轮（n<=16）。 3
首先说明： 1. 对于DES的分析，可忽略初始置换IP和IP-1。 2. 对DES限制到n轮（n<=16）。 3. 以L0R0为明文，且以LnRn作为n轮DES的密文。 4. 对两个明文L0R0和L0*R0*，规定它们的异或值为L0´R0 ´ =L0R0  L0*R0*，整个讨论都使用撇号 （ ´）表示两个比特串的异或值。 定义1：设Sj是一个特定的S盒（1<=j<=8)，考虑长度为6的比特串的一个有序对（Bj,Bj*）,我们说Sj的输入异或是Bj  Bj*, 输出异或是Sj(Bj)  Sj(Rj*) 注：输入异或是长度为6的比特串，输出异或是长度为4的比特串。

24 定义2：对任何一个Bj´(Z2)6= {a0,a1,a2,a3,a4,a5|aj∈ {0,1}}，定义集合△(Bj´)是由输入异或为Bj´的有序对(Bj,Bj*)组成。
注：1*. 对比特串Bj´来说，集合△ (Bj´)包含26=64个有序对元素。有 △ (Bj´)={(Bj,Bj  Bj´)| Bj ∈(Z2)6} *. 对△ (Bj´)中的每一对，我们能计算出Sj的输出异或，同时用表列出结果的分布。 有64个输入异或，它们经Sj的输出分布在24=16种可能值之中，这些分布的非均匀性，就是攻击DES的基础。

25 3*. 表示一个S盒的所有可能对的输入异或和输出异或分布的表称为该S盒的差分分布表。
例子1。若考虑第一个S盒S1，输入异或为B1´=110100, 那么： △ (B1´)= △(110100)={(000000,110100), (000001, ), …., (111111, )} 对集合△ (B1´)中的每一对，计算S1盒的输出异或。 例如 S1(000000)=E16= S1(110100)=916=1001 所以(000000,110100)的输出异或是0111。 计算△ (B1´)= △ (110100)中所有64对的输出异或，得输出异或分布表： +

26 注意！16个可能输出异或中，仅有8种出现。它们的分布是不均匀的。 一般说来，对固定的一个S盒Sj说来，给一个输入异或Bj´, 那么平均出现75%-80%的相异输出异或。 为描述这类分布如何产生的，先表述一些进一步的概念。 0个 个 16个 6个 2个 0个 0个 12个 6个 个 0个 0个 0个 8个 0个 16个

27 定义3：对长度为6的比特串Bj´和长度为4的比特串Cj´ (1<=j<=8), 定义 INj(Bj´,Cj´)={Bj（Z2）6|Sj(Bj) Sj(Bj  Bj´)=Cj´} Nj(Bj´,Cj´)=|INj(Bj´,Cj´)| 注：1*.对特定的S盒Sj,它的输入异或为Bj´且相应的输出异或为Cj´，这里Nj(Bj´,Cj´)就是用来表示其输入对的数目。 2*.对于上述例子1中的输出异或分布表表现了N1（110100，C1´）(其中C1´ (Z2)4)所指示的对S盒S1来说，它的输入异或为（110100）且相应的输出异或为C1´的分布情况。 3*. 对于集合IN1（110100，C1´），表示输入异或为（110100）的所有可能输入引起输出异或情况的分布表，见下页：

28

29 考虑一般的情况：对于DES的8个S盒的每一个盒有64种可能的输入异或，于是可算出有512个分布。 回忆上一讲：知在第i轮中S盒的输入为B=E  J，其中E=E（Ri-1）是Ri-1的扩展，J=Ki是由第i轮的密钥比特组成。 现在对所有8个S盒的输入异或计算如下： B B*=(E J)  (E*  J)= E  E*=E´ 由此可见，输入异或不依赖于密钥比特J. 将B，E和J均写成8个6比特串的并： B=B1B2B3B4B5B6B7B E=E1E2E3E4E5E6E7E J=J1J2J3J4J5J6J7J8 类似地可表述B*，E*，J*（表达式略） 假设我们知道Ej和Ej*的值（对某一个j,1<= j<=8）和Sj的输出异或值Cj ´=Sj(Bj)  Sj(Bj*), 那么必有 Ej  JjINj(Ej ´,Cj ´)， Bj=Ej  Jj; Bj ´=Ej  Ej*

30 我们的目的是要破译密钥J的部分比特串Jj。定义测试集合Testj
定义4（Testj）:设Ej和Ej*是长度为6的比特串，Cj´是长度为4的比特串，定义 Testj(Ej,Ej*,Cj´)={Bj Ej|Bj∈INj(Ej´,Cj´)} 这里Bj Ej 是Jj的形式，Ej是固定的,Ej´=Ej Ej* 我们有 定理1：假设Ej和Ej*是S盒Sj的两个输入，Sj的输出译或为Cj ´，记Ej ´=Ej Ej* ，那么密钥比特Jj出现在集合Testj(Ej,Ej*,Cj ´)之中。 注：可见在集合Testj(Ej,Ej*,Cj ´)中，长度为6比特刚好有Nj(Ej ´,Cj ´)个，Jj的正确值一定是这些可能值中的一个。

31 例子2：假设E1=000001，E1*=110101和C1  =1101，因为N1（110100，1101）=8，（见第5面110100输入分布表），可知集合Test1(000001，110101，1101）中，刚好有8个比特串：原因为 可从表中得到： IN1（110100，1101）={000110，010000，010110，011100，100010，100100，101000，110010} 分别计算它们与E1=000001的异或得： Test1(000001,110101,1101)={000111,010001, , ,100011,100101,101001,110011} 如果有两个这样的三元组E1，E1*，C1  ，那么就可得到J1中密钥比特可能值的第2个集合Test1(2)(E1,E1*,C1)。易见密钥比特Jj∈Test1∩Test1 (2) !! 自然这样的三元组如果更多些，定出Jj是肯定的。关于这方面的计算，可想出若干技巧。

32 攻击3轮DES 明文P(64bits) R0 L0 K1 F + K2 L1=R0 + F L2=R1 K3 + F L3=R2 密文
Li=Ri-1 Ri=Li-1 f(Ri-1,Ki) L0 K1 A F + K2 L1=R0 B + F R1=L0  f(R0,K1) L2=R1 K3 C + F R2=L1  f(R1,K2) L3=R2 R3=L2  f(R2,K3) 密文 3轮DES图

33 DES的F函数 输入32比特 E + B B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8
48bits E1|E2|E3|E4|E5|E6|E7|E8 子密钥 J1|J2|J3|J4|J5|J6|J7|J8 + B B B B B B B B B8 S1 S2 S3 S4 S5 S6 S7 S8 C C C C C C C C8 P Output(32bits)

34 我们对3轮作选择明文攻击。用明文对和相应的密文对开始我们的分析： 明文对为：L0R0; L0. R0. 密文对为：L3R3; L3. R3
我们对3轮作选择明文攻击。用明文对和相应的密文对开始我们的分析： 明文对为：L0R0; L0*R0* 密文对为：L3R3; L3*R3*。有表达式： R3=L2 f(R2,K3)=R1 f(R2,K3) =L0 f(R0,K1) f(R2,K3) R3*可用类似的方法得到： R3*=L0* f(R0*,K1) f(R2*,K3), 于是有 R3´=L0´ f(R1,K1) f(R0*,K1) f(R2,K3) f(R2*,K3) 假设选择了明文，使R0=R0*,此时R0´=00…0 且f(R0,K)=f(R0*,K)，所以 R3´=L0´ f(R2,K3) f(R2*,K3) 由于R3´可从两个密文R3,R3*计算出，可知R3´和L0´已知。有： F(R2,K3) f(R2*,K3)=R3´ L0´

35 知f(R2,K3)=P(C) 和f(R2. ,K3)=P(C. ),其中 C和C
知f(R2,K3)=P(C) 和f(R2*,K3)=P(C*),其中 C和C*分别表示8个S盒的两个输出。而P是固定的，为公开已知的置换，因此 P(C) =P(C*)=R3´ L0´,由此可知 C´=C C*=P-1(R3´ L0´)….为3轮中8个S盒的两个输出异或。 另外，R2=L3和R2*=L3*是已知的（它们是密文的一部分），因此，可用公开已知的扩展函数E计算 E=E(L3)和E*=E(L3*) 对第三轮说来，它们是S盒的输入。于是可由E，E*和C。象前面的例子那样对J1，J2，J3，J4，J5，J6，J7，J8中密钥比特可能值，着手构造集合Test1,Test2,…, Test8。由它们来确定第三轮密钥K3中的48bits。56bits密钥中剩下的8比特可通过穷举28=256种可能来确定。

36 3轮DES的差分攻击模式： 输入：L0R0,L0. R0. ,L3R3和L3. R3. ，其中R0=R0. 1
3轮DES的差分攻击模式： 输入：L0R0,L0*R0*,L3R3和L3*R3*，其中R0=R0* 1.计算C  =P-1(R3  L0 ) 2.计算E=E(L3)和E* 3. For j=1 to 8 do 计算Testj(Ej,Ej*,Cj ) 例子3。我们有如下三组明密文对，并有固定的异或值。用相同的密钥进行加密。为简单用16进制表示. 明文 密文748502CD C70306D8A09F A0960E6D4CB ACDFF31 45FA28BE5ADC BD31F6ACDFF31 134F7915AC DA013FEC86 D8A31B2F28BBC5CF FEC86 0F317AC2B23CB944

37 对第一组，可计算S盒的输入（对第三轮），它们是 E=E(L3)= E*=E(L3*)= 还可算出S盒的输出异或为： C=C C*=P-1(R3  L0 ) = 对第二组，第二组给出相同的计算，结果（略）。 我们给出八个计数器阵列，每个阵列为16*4。这样按书写方式排有64个位置：0,1,2,…,63。在第一组中，我们有E1  =101111和C1 =1001,集合IN1(101111,1001)={000000,000111,101000,101111}

38 因为E1=000000，我们有J1∈Test1(000000,101111,1001) ={ , ,101000,101111} 将其中6bits串用2进制数表示成对应J1阵列中的位置数0,7,40,47对应于{000000,000111,101111}, 相当于在阵列表的空位的相应位置增值 J1

39 对三组算得的三个集合Test1(1),Test1(2),Test1(3)。它们中的元素对应的数增值J1位置处的1个单位数。 于是算得J1=47=101111，类似地方法定出J2=000101，J3=010011，J4= ，J5=011000，J6=000111，J7=000111，J8=110001 注：1*.差分攻击技术还可用于6轮DES，对8轮的DES需214个组选择明文。现在对16轮DES也是相当有效的。见: 2*. 对其它体制的攻击，例Feal,LOKI,REDOC-II，也是有效的。

40 (2). 线性密码分析 见书78页。参考文献： Matsui
(2). 线性密码分析 见书78页。参考文献： Matsui. M, Linear Cryptanalytic Method for DES Cipher, Advances in Cryptology-Eurocrypt´93, Springer-Verlag, PP , 1994.