| [watermark]现代分组加密算法S-DES\DES\IDEA
7.1 S-DES
7.2 DES
7.3 IDEA
7.1.1 简化的DES
Simplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。
注：1.* 加密算法涉及五个函数：
(1)初始置换IP(initial permutation)
(2)复合函数fk1，它是由密钥K确定的，具有转换和替换的运算。 (3)转换函数SW
(4)复合函数fk2
(5)初始置换IP的逆置换IP-1
7.1.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(密文)))))
7.1.3算法描述
（1） S-DES的密钥生成：
设10bit的密钥为（ k1,k2,…,k10 )
置换P10是这样定义的
P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)
P8= (k1,k2,…,k10)=(k6,k3,k7,k4,k8,k5,k10,k9 )
LS-1为循环左移1位， LS-2为循环左移2位
按照上述条件,若K选为(1010000010), 产生的两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)
7.1.4 S-DES的密钥生成
S-DES的加密运算:
初始置换用IP函数:
IP= 1 2 3 4 5 6 7 8
2 6 3 1 4 8 5 7
末端算法的置换为IP的逆置换:
IP-1= 1 2 3 4 5 6 7 8
4 1 3 5 7 2 8 6
易见IP-1(IP(X))=X
7.1.5 S-DES加密图
函数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
4 1 2 3 2 3 4 1
事实上，它的直观表现形式为：
n4 n1 n2 n3
n2 n3 n4 n1
8-bit子密钥：
K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：
n4+k11 n1+k12 n2+k13n3+k14
n2+k15 n3+k16n4+k17n1+k18
把它们重记为8位：
P0,0 P0,1 P0,2 P0,3
P1,0 P1,1 P1,2 P1,3
上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。
两个S盒按如下定义：
•S盒按下述规则运算：
•将第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
– 2 4 3 1
–它的输出就是F函数的输出。
Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。
S-DES的安全性分析
对10 bit密钥的强行攻击是可行的
密钥空间：2^10=1024
密码分析：利用已知明文攻击：
已知: 明文（p1,p2,……,p8), 及对应的密文
（c1,c2,……,c8),
未知：(k1,k2, ……，k10)
Ci是pj’s和kj’s的函数
这些加密算法可以表示成8个含10个变量的非线性方程
非线性是由S盒作用的结果
S0的非线性表示如下：
设a,b,c,d为输入的4个比特，输出的两个比特分别为q,r.
则 q=abcd+ab+ac+b+d mod2
r=abcd+abd+ab+ac+ad+a+c+1 mod2
线性映射与非线性映射交替产生了复杂的密文比特输出函数，使得密码分析很困难。（可以试图寻找8个密文比特的复杂度）
7.2 数据加密标准（DES)
DES的历史
1971 IBM，由Horst Feistel 领导的密码研
究项目组研究出LUCIFER算法。并应于商业领域。
1973美国标准局征求标准，IBM提交结果，
在1977年，被选为数据加密标准。
7.2 DES的描述
DES利用56比特长度的密钥K
分组长度64比特，密文64比特
算法分三个阶段实现：
1.对明文X，通过一个固定的初始置换IP得到X0。
X0=IP（X）=L0R0
分为左右两部分
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）
(a) 初始置换(IP)
58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7
(b) 初始置换的逆置换(IP-1)
© 扩展置换(E)
(d) 置换函数(P,32bit)
PC1
57, 49, 41, 33, 25, 17, 9, C Half
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, D Half
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4
S-box-1
0 1 2 3 4 5 6 7 8 9 a b c d e f
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15,12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
DES一轮加密的简图
F（Ri-1, Ki）：
函数F有两个输入：32的消息A=R（32bits）作第一个输入，48比特的子密钥J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。
(1)对第一个变元A，先利用扩展函数E，扩展成48位E（A）
(2)计算E（A）XOR 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为固定置换。
初始置换IP：对明文输入进行次序的打乱。
逆置换IP-1：
扩展函数E；（32到48）
置换函数P。
密钥K是长度为64的位串，56位参加子密钥编排。8位是奇偶校验位（为了检错），在密钥编排的计算中，不参加运算。
(1). 给定64位的密钥K，放弃奇偶校验位（8，16，…，64）并根据固定置换PC-1（见144页图4-4-9）来排列K中剩下的位。我们写
PC-1(K)=C0D0
其中C0由PC-1（K）的前28位组成；D0由后28位组成。
(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为固定置
注：一共16轮，每一轮使用K生成的一个子密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如：
第7轮的表7：K7取K中的比特情况：
52 57 11 1 26 59 10 34 44 51 25 19
9 41 3 2 50 35 36 43 42 33 60 18
28 7 14 29 47 46 22 5 15 63 61 39
4 31 13 38 53 62 55 20 23 37 30 6
轮密钥编排
57, 49, 41, 33, 25, 17, 9, C Half
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, D Half
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4
PC2
14, 17, 11, 24, 1, 5, C half
3, 28, 15, 6, 21, 10, (bits 1-28)
23, 19, 12, 4, 26, 8,
16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, D half
30, 40, 51, 45, 33, 48, (bits 29-56)
44, 49, 39, 56, 34, 53,
46, 42, 50, 36, 29, 32
C half provides bits to S1-S4, D half to S5-S8
7.3 DES加密的一个例子
取16进制明文X：0123456789ABCDEF
密钥K为：133457799BBCDFF1
去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000
应用IP，我们得到：
L0=11001100000000001100110011111111
L1=R0=11110000101010101111000010101010
然后进行16轮加密。
最后对L16, R16使用IP-1得到密文：85E813540F0AB405
7.4 DES的争论
DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。
S盒的设计准则：
1. S盒不是它输入变量的线性函数
2.改变S盒的一个输入位至少要引起两位的输出改变
3. 对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。
公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有陷门？）。
密钥长度是否足够？
迭代的长度？（8、16、32？）
7.5 三重DES
7.5.1双重DES
加密
解密
问题：下式成立吗？
7.5.2 三重DES(Cont.)
两个密钥的三重DES
目前，没有针对三重DES的攻击方法，它是一种较受欢迎的DES替代方案。
7.6 IDEA简介
瑞士的Xuejia Lai和James Massey于1990年
公布了IDEA密码算法第一版，称为PES
(Proposed Encryption Standard)。为抗击
差分密码攻击，他们增强了算法的强度，
称IPES（Improved PES)，并于1992年改
名为IDEA（International Data encryption Algorithm，国际数据加密算法。）
7.6.1 IDEA(Cont.)
IDEA：
分组长度为64位
密钥长度为128位（抗强力攻击能力比DES强），同一算法既可加密也可解密。
IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：
7.6.2 IDEA简介(Cont.)
异或运算（ ）
整数模216加（ + ）
整数模216+1乘（ ）(IDEA的S盒）
扩散由称为MA结构的算法基本构件提供。
7.6.3 IDEA简介(Cont.)
实现上的考虑
–使用子分组：16bit的子分组；
–使用简单操作（易于加法、移位等操作实现）
–加密解密过程类似；
–规则的结构（便于VLSI实现）。
7.6.4 IDEA的密钥生产
52个16bit的子密钥从128bit的密钥中生成
前8个子密钥直接从密钥中取出；
对密钥进行25bit的循环左移，接下来的密钥就从中取出；
重复进行直到52个子密钥都产生出来。
IDEA的解密
加密解密实质相同，但使用不同的密钥；
解密密钥以如下方法从加密子密钥中导出：
–解密循环I的头4个子密钥从加密循环10－I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；
–对前8个循环来说，循环I的最后两个子密钥等于加密循环9－I的最后两个子密钥；
7.6.5 IDEA(Cont.)
IDEA是PGP的一部分；
IDEA能抗差分分析和相关分析；
IDEA似乎没有DES意义下的弱密钥；
Bruce Schneier 认为IDEA是DES的最好替代.
7.6.7先进分组密码的特点
可变密钥长度
混合操作
依赖数据的循环移位
依赖于密钥的循环移位
依赖S盒子
冗长的密钥调度算法
可变的F函数和可变的明文/密文长度
可变的循环次数
在每次循环中都对两半数据进行操作
7.7 分组密码工作模式
分组密码加密固定长度的年信息，eg. DES加密64-bit，使用 56-bit key
需要一种使用方法，加密任意长度的消息
这种使用方法叫做工作模式Mode of Use
对于DES ，定义了4种模式（in ANSI standard ANSI X3.106-1983 Modes of Use）
四种模式:
Block Modes
–ECB, CBC
Stream Modes
–CFB, OFB
7.7.1. Electronic Codebook Book (ECB)
消息分成相互独立的加密模块
每块独立使用DES算法
Ci = DESK1 (Pi)
适合少量的数据加密.
特点:对于同一个64比特明文,如果出现多次,其密文是相同的.(不安全的)
7.7.2. Cipher Block Chaining (CBC)
密码分组链接模式
消息分成模块
加密是相互联系的
密文与明文联结
利用一个初始向量开始：
Ci = DESK1(Pi XOR Ci-1)
C-1 = IV
适合加密长度大于64比特的消息
还可以用来进行用户鉴别(见报文鉴别部分)
7.7.3.Cipher FeedBack (CFB)
密码反馈模式
消息被看作bit流
被加到分组密文的输出
并把结果反馈到下一阶段
标准允许反馈任意比特 (1,8 or 64 or whatever)
记作 CFB-1, CFB-8, CFB-64 etc
CFB-64 ：
Ci = Pi XOR DESK1 (Ci-1)
C-1 = IV
CFB特点
适合数据以比特或字节为单位出现
错误传播
7.7.4 输出反馈方式(OFB)
OFB的特点
消息作为比特流
分组加密的输出与被加密的消息相加
比特差错不容易传播
小结
分组密码算法DES\IDEA
分组密码的工作模式
（全文完）Thanks！
[/watermark] |
