2010-5-14 1
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
三,美国数据加密标准 — DES
（ Data Encryption Standard）
2010-5-14 3
美国制定数据加密标准简况
? 目的
通信与计算机相结合是人类步入信息社会的一个阶梯，
它始于六十年代末，完成于 90年代初。计算机通信网的形
成与发展，要求信息作业标准化，安全保密亦不例外。只
有标准化，才能真正实现网的安全，才能推广使用加密手
段，以便于训练、生产和降低成本。
2010-5-14 4
美国制定数据加密标准简况
? 美国 NBS在 1973年 5月 15公布了征求建议。 1974年 8月
27日 NBS再次出公告征求建议，对建议方案提出如下
要求：
? 算法必须完全确定而无含糊之处；
? 算法必须有足够高的保护水准，即可以检测到威胁，
恢复密钥所必须的运算时间或运算次数足够大；
? 保护方法必须只依赖于密钥的保密；
? 对任何用户或产品供应者必须是不加区分的。
2010-5-14 5
美国制定数据加密标准简况
? IBM公司在 1971年完成的 LUCIFER密码 (64 bit分组, 代
换 -置换, 128 bit密钥 )的基础上, 改进成为建议的 DES体
制
? 1975年 3月 17日 NBS公布了这个算法, 并说明要以它作为
联邦信息处理标准, 征求各方意见 。
? 1977年 1月 15日建议被批准为联邦标准 [FIPS PUB 46],并
设计推出 DES芯片 。
? 198 1年美国 ANSI 将其作为标准, 称之为 DEA[ANSI
X3.92]
? 1983年国际标准化组织 (ISO)采用它作为标准, 称作 DEA-
1
2010-5-14 6
美国制定数据加密标准简况
? NSA宣布每隔 5年重新审议 DES是否继续作为联邦标准,
1988年 （ FIPS46-1）, 1993年 （ FIPS46-2）, 1998年不再重
新批准 DES为联邦标准 。
? 虽然 DES已有替代的数据加密标准算法, 但它仍是迄今为止
得到最广泛应用的一种算法, 也是一种最有代表性的分组加
密体制 。
? 1993年 4月, Clinton政府公布了一项建议的加密技术标准,
称作密钥 托管加密技术标准 EES(Escrowed Encryption
Standard)。 算法属美国政府 SECRET密级 。
2010-5-14 7
美国制定数据加密标准简况
? DES发展史确定了发展公用标准算法模式, 而 EES的制定
路线与 DES的背道而驰 。 人们怀疑有陷门和政府部门肆意
侵犯公民权利 。 此举遭到广为反对 。
? 1995年 5月 AT&T Bell Lab的 M,Blaze博士在 PC机上用 45分
钟时间使 SKIPJACK的 LEAF协议失败, 伪造 ID码获得成
功 。 1995年 7月美国政府宣布放弃用 EES来加密数据, 只将
它用于语音通信 。
? 1997年 1月美国 NIST着手进行 AES（ Advanced Encryption
Standard） 的研究, 成立了标准工作室 。 2001年 Rijndael
被批准为 AES标准 。
2010-5-14 8
DES 算法
? 分组长度为 64 bits (8 bytes)
? 密文分组长度也是 64 bits。
? 密钥长度为 64 bits,有 8 bits奇偶校验, 有效密钥长
度为 56 bits。
? 算法主要包括：初始置换 IP,16轮迭代的乘积变换,
逆初始置换 IP-1以及 16个子密钥产生器 。
2010-5-14 9
DES算法框图
输入
64 bit明文 数据
初始置换 IP
乘积变换
（ 16轮迭代）
逆初始置换 IP-1
64 bit密文数据
输出
标
准
数
据
加
密
算
法
2010-5-14 10
初始置换 IP
? 将 64 bit明文的位置进行置换，得到一个乱序的 64 bit
明文组，而后分成左右两段，每段为 32 bit,以 L0和 R0
表示,IP中各列元素位置号数相差为 8，相当于将原明
文各字节按列写出，各列比特经过偶采样和奇采样置
换后，再对各行进行逆序。将阵中元素按行读出构成
置换输出。
? 逆初始置换 IP-1。 将 16轮迭代后给出的 64 bit组进行置
换, 得到输出的密文组 。 输出为阵中元素按行读得的
结果 。
? IP和 IP-1在密码意义上作用不大, 它们的作用在于打
乱原来输入 x的 ASCII码字划分的关系, 并将原来明文
的校验位 x8,x16,?,x64变成为 IP输出的一个字节 。
2010-5-14 11
Li-1(32bit) Ri-1(32bit)
选择扩展运算 E
48 bit寄存器
按 bit模 2加密
48 bit寄存器
选择压缩运算 S
32 bit寄存器
置换运算 P
按 bit模 2和
Li (32bit) Ri (32bit)
乘积变换框图
密
钥
产
生
器
2010-5-14 12
乘积变换
? 它是 DES算法的核心部分 。 将经过 IP置换后的数据分成 32
bit的左右两组, 在迭代过程中彼此左右交换位置 。
? 每次迭代时只对右边的 32 bit进行一系列的加密变换, 在此
轮迭代即将结束时, 把左边的 32 bit与右边得到的 32 bit逐位
模 2相加, 作为下一轮迭代时右边的段, 并将原来右边未经
变换的段直接送到左边的寄存器中作为下一轮迭代时左边
的段 。
? 在每一轮迭代时, 右边的段要经过 选择扩展运算 E,密钥加
密运算, 选择压缩运算 S,置换运算 P和左右混合运算 。
2010-5-14 13
乘积变换
选择扩展运算 E。 将输入的 32 bit Ri-1扩展成 48 bit的输出, 令 s
表示 E原输入数据比特的原下标, 则 E的输出是将原下标 s?0或
1(mod 4)的各比特重复一次得到的, 即对原第 32,1,4,5,8,9,
12,13,16,17,20,21,24,25,28,29各位都重复一次,实现数据扩
展 。 将表中数据按行读出得到 48 bit输出 。
密钥加密运算 。 将子密钥产生器输出的 48 bit子密钥 ki与选择
扩展运算 E输出的 48 bits数据按位模 2相加 。
选择压缩运算 S。 将前面送来的 48 bit数据自左至右分成 8组,
每组为 6 bit。 而后并行送入 8个 S一盒, 每个 S盒为一非线性代
换网络, 有 4个输出, 运算 S的框图在图 4-4-6中给出 。
2010-5-14 14
选择压缩运算 S
6 bit
选择函数组
4 bit
48 bit 寄存器
32 bit 寄存器
S1 S2 S3 S4 S5 S6 S7 S8
2010-5-14 15
乘积变换
置换运算 P。 对 S1至 S8盒输出的 32 bit数据进行坐
标置换, 置换 P输出的 32 bit数据与左边 32 bit即 Ri-
1逐位模 2相加, 所得到的 32 bit作为下一轮迭代用
的右边的数字段 。 并将 Ri-1并行送到左边的寄存器,
作为下一轮迭代用的左边的数字段 。
子密钥产生器 。 将 64 bit初始密钥经过 置换选择
PC1,循环移位置换, 置换选择 PC2给出每次迭代
加密用的子密钥 ki，
2010-5-14 16
子密钥产生器框图
密钥（ 64 bit ）
置换选择 1,PC1
置换选择 2,PC2
Ci(28 bit) Di(28 bit)
循环左移 ti+1bit 循环左移 t
i+1bit
除去第 8,16,?,64位 (8个校验位 )
ki
2010-5-14 17
DES的 安全性
? 互补性 。 DES算法具有下述性质。若明文组 x逐位取
补，密钥 k逐位取补，即 y=DESk(x),则有
这种互补性会使 DES在选择明文破译下所需的工
作量减半 。
? 弱密钥和半弱密钥 。 DES算法在每次迭代时都有一
个子密钥供加密用 。 如果给定初始密钥 k,各轮的子
密钥都相同, 即有 k1=k2= … =k16
就称给定密钥 k为弱密钥 (Weak key)。
)( xDESy K?
2010-5-14 18
DES的 安全性
若 k为弱密钥，则有
DESk(DESk(x))=x
DESk-1(DESk-1(x))=x
即以 k对 x加密两次或解密两次都可恢复出明文 。 其加密
运算和解密运算没有区别 。
弱密钥下使 DES在选择明文攻击下的搜索量减半 。
如果随机地选择密钥, 弱密钥所占比例极小, 而且稍加
注意就不难避开 。 因此, 弱密钥的存在不会危及 DES的
安全性 。
2010-5-14 19
DES的 安全性
密文与明文, 密文与密钥的相关性 。
Meyer[1978]详细研究了 DES的输入明文与密文及密钥与
密文之间的相关性 。 表明每个密文比特都是所有明文比
特和所有密钥比特的复合函数, 并且指出达到这一要求
所需的迭代次数至少为 5。 Konheim[1981]用 ?2检验证明,
迭代 8次后输出和输入就可认为是不相关的了 。
2010-5-14 20
DES的 安全性
S盒设计 。
DES靠 S盒实现非线性变换 。
密钥搜索机 。
对 DES安全性批评意见中, 较为一致的看法是 DES的
密钥短了些 。 IBM最初向 NBS提交的建议方案采用 112
bits密钥, 但公布的 DES标准采用 64 bits密钥 。 有人认
为 NSA故意限制 DES的密钥长度 。 采用穷搜索对已经
对 DES构成了威胁,
2010-5-14 21
二重 DES
用 DES进行两次加密，但这是否就意味着两重
DES加密的强度等价于 112 bit密钥的密码的强度？
答案是否定的。
中途相遇攻击法 (Meet-in-the-Middle Attack)
由 Diffie和 Hellman[1977]最早提出，可以降低搜
索量其基本想法如下。若有明文密文对 (xi,yi)满足
yi=Ek2[Ek1[xi]]
则可得 z=Ek1[xi]=Dk2[yi]
2010-5-14 22
二重 DES
图 4-14-1 中途相遇攻击示意图
zE E D Dx
i
yi x
i
z yi
k1 k1k2k2
2010-5-14 23
中途相遇攻击
给定一已知明密文对 (x1,y1),可按下述方法攻击 。
? 以密钥 k1的所有 256个可能的取值对此明文 x1加密, 并
将密文 z存储在一个表中；
? 从所有可能的 256个密钥 k2中依任意次序选出一个对给
定的密文 y1解密, 并将每次解密结果 z 在上述表中查
找相匹配的值 。 一旦找到, 则可确定出两个密钥 k1和
k2；
? 以此对密钥 k1和 k2对另一已知明文密文对 (x2,y2)中的明
文 x2进行加密, 如果能得出相应的密文 y2就可确定 k1和
k2是所要找的密钥 。
2010-5-14 24
中途相遇攻击
? 对于给定明文 x,以两重 DES加密将有 264个可能的密文 。
? 可能的密钥数为 21 12个 。 所以, 在给定明文下, 将有
2112/264=248个密钥能产生给定的密文 。
? 用另一对 64bits明文密文对进行检验, 就使虚报率降为
248-64=2-16。
? 这一攻击法所需的存储量为 256× 8 Byte,最大试验的加
密次数 2× 256 =257。 这说明破译双重 DES的难度为 257量级 。
2010-5-14 25
三重 DES加密
加密,y=Ek1[Dk2[Ek1 [x]]]
解密,x=Dk1[Ek2[Dk1[y]]]
? 称其为加密 -解密 -加密方案, 简记为 EDE(encrypt-
decrypt-encrypt)。
? 此方案已在 ANSI X9.17和 ISO 8732标准中采用, 并在
保密增强邮递 (PEM)系统中得到利用 。
? 破译它的穷举密钥搜索量为 2112?5× 1035量级, 而用差
分分析破译也要超过 1052量级 。 此方案仍有足够的安
全性 。
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
三,美国数据加密标准 — DES
（ Data Encryption Standard）
2010-5-14 3
美国制定数据加密标准简况
? 目的
通信与计算机相结合是人类步入信息社会的一个阶梯，
它始于六十年代末，完成于 90年代初。计算机通信网的形
成与发展，要求信息作业标准化，安全保密亦不例外。只
有标准化，才能真正实现网的安全，才能推广使用加密手
段，以便于训练、生产和降低成本。
2010-5-14 4
美国制定数据加密标准简况
? 美国 NBS在 1973年 5月 15公布了征求建议。 1974年 8月
27日 NBS再次出公告征求建议，对建议方案提出如下
要求：
? 算法必须完全确定而无含糊之处；
? 算法必须有足够高的保护水准，即可以检测到威胁，
恢复密钥所必须的运算时间或运算次数足够大；
? 保护方法必须只依赖于密钥的保密；
? 对任何用户或产品供应者必须是不加区分的。
2010-5-14 5
美国制定数据加密标准简况
? IBM公司在 1971年完成的 LUCIFER密码 (64 bit分组, 代
换 -置换, 128 bit密钥 )的基础上, 改进成为建议的 DES体
制
? 1975年 3月 17日 NBS公布了这个算法, 并说明要以它作为
联邦信息处理标准, 征求各方意见 。
? 1977年 1月 15日建议被批准为联邦标准 [FIPS PUB 46],并
设计推出 DES芯片 。
? 198 1年美国 ANSI 将其作为标准, 称之为 DEA[ANSI
X3.92]
? 1983年国际标准化组织 (ISO)采用它作为标准, 称作 DEA-
1
2010-5-14 6
美国制定数据加密标准简况
? NSA宣布每隔 5年重新审议 DES是否继续作为联邦标准,
1988年 （ FIPS46-1）, 1993年 （ FIPS46-2）, 1998年不再重
新批准 DES为联邦标准 。
? 虽然 DES已有替代的数据加密标准算法, 但它仍是迄今为止
得到最广泛应用的一种算法, 也是一种最有代表性的分组加
密体制 。
? 1993年 4月, Clinton政府公布了一项建议的加密技术标准,
称作密钥 托管加密技术标准 EES(Escrowed Encryption
Standard)。 算法属美国政府 SECRET密级 。
2010-5-14 7
美国制定数据加密标准简况
? DES发展史确定了发展公用标准算法模式, 而 EES的制定
路线与 DES的背道而驰 。 人们怀疑有陷门和政府部门肆意
侵犯公民权利 。 此举遭到广为反对 。
? 1995年 5月 AT&T Bell Lab的 M,Blaze博士在 PC机上用 45分
钟时间使 SKIPJACK的 LEAF协议失败, 伪造 ID码获得成
功 。 1995年 7月美国政府宣布放弃用 EES来加密数据, 只将
它用于语音通信 。
? 1997年 1月美国 NIST着手进行 AES（ Advanced Encryption
Standard） 的研究, 成立了标准工作室 。 2001年 Rijndael
被批准为 AES标准 。
2010-5-14 8
DES 算法
? 分组长度为 64 bits (8 bytes)
? 密文分组长度也是 64 bits。
? 密钥长度为 64 bits,有 8 bits奇偶校验, 有效密钥长
度为 56 bits。
? 算法主要包括：初始置换 IP,16轮迭代的乘积变换,
逆初始置换 IP-1以及 16个子密钥产生器 。
2010-5-14 9
DES算法框图
输入
64 bit明文 数据
初始置换 IP
乘积变换
（ 16轮迭代）
逆初始置换 IP-1
64 bit密文数据
输出
标
准
数
据
加
密
算
法
2010-5-14 10
初始置换 IP
? 将 64 bit明文的位置进行置换，得到一个乱序的 64 bit
明文组，而后分成左右两段，每段为 32 bit,以 L0和 R0
表示,IP中各列元素位置号数相差为 8，相当于将原明
文各字节按列写出，各列比特经过偶采样和奇采样置
换后，再对各行进行逆序。将阵中元素按行读出构成
置换输出。
? 逆初始置换 IP-1。 将 16轮迭代后给出的 64 bit组进行置
换, 得到输出的密文组 。 输出为阵中元素按行读得的
结果 。
? IP和 IP-1在密码意义上作用不大, 它们的作用在于打
乱原来输入 x的 ASCII码字划分的关系, 并将原来明文
的校验位 x8,x16,?,x64变成为 IP输出的一个字节 。
2010-5-14 11
Li-1(32bit) Ri-1(32bit)
选择扩展运算 E
48 bit寄存器
按 bit模 2加密
48 bit寄存器
选择压缩运算 S
32 bit寄存器
置换运算 P
按 bit模 2和
Li (32bit) Ri (32bit)
乘积变换框图
密
钥
产
生
器
2010-5-14 12
乘积变换
? 它是 DES算法的核心部分 。 将经过 IP置换后的数据分成 32
bit的左右两组, 在迭代过程中彼此左右交换位置 。
? 每次迭代时只对右边的 32 bit进行一系列的加密变换, 在此
轮迭代即将结束时, 把左边的 32 bit与右边得到的 32 bit逐位
模 2相加, 作为下一轮迭代时右边的段, 并将原来右边未经
变换的段直接送到左边的寄存器中作为下一轮迭代时左边
的段 。
? 在每一轮迭代时, 右边的段要经过 选择扩展运算 E,密钥加
密运算, 选择压缩运算 S,置换运算 P和左右混合运算 。
2010-5-14 13
乘积变换
选择扩展运算 E。 将输入的 32 bit Ri-1扩展成 48 bit的输出, 令 s
表示 E原输入数据比特的原下标, 则 E的输出是将原下标 s?0或
1(mod 4)的各比特重复一次得到的, 即对原第 32,1,4,5,8,9,
12,13,16,17,20,21,24,25,28,29各位都重复一次,实现数据扩
展 。 将表中数据按行读出得到 48 bit输出 。
密钥加密运算 。 将子密钥产生器输出的 48 bit子密钥 ki与选择
扩展运算 E输出的 48 bits数据按位模 2相加 。
选择压缩运算 S。 将前面送来的 48 bit数据自左至右分成 8组,
每组为 6 bit。 而后并行送入 8个 S一盒, 每个 S盒为一非线性代
换网络, 有 4个输出, 运算 S的框图在图 4-4-6中给出 。
2010-5-14 14
选择压缩运算 S
6 bit
选择函数组
4 bit
48 bit 寄存器
32 bit 寄存器
S1 S2 S3 S4 S5 S6 S7 S8
2010-5-14 15
乘积变换
置换运算 P。 对 S1至 S8盒输出的 32 bit数据进行坐
标置换, 置换 P输出的 32 bit数据与左边 32 bit即 Ri-
1逐位模 2相加, 所得到的 32 bit作为下一轮迭代用
的右边的数字段 。 并将 Ri-1并行送到左边的寄存器,
作为下一轮迭代用的左边的数字段 。
子密钥产生器 。 将 64 bit初始密钥经过 置换选择
PC1,循环移位置换, 置换选择 PC2给出每次迭代
加密用的子密钥 ki，
2010-5-14 16
子密钥产生器框图
密钥（ 64 bit ）
置换选择 1,PC1
置换选择 2,PC2
Ci(28 bit) Di(28 bit)
循环左移 ti+1bit 循环左移 t
i+1bit
除去第 8,16,?,64位 (8个校验位 )
ki
2010-5-14 17
DES的 安全性
? 互补性 。 DES算法具有下述性质。若明文组 x逐位取
补，密钥 k逐位取补，即 y=DESk(x),则有
这种互补性会使 DES在选择明文破译下所需的工
作量减半 。
? 弱密钥和半弱密钥 。 DES算法在每次迭代时都有一
个子密钥供加密用 。 如果给定初始密钥 k,各轮的子
密钥都相同, 即有 k1=k2= … =k16
就称给定密钥 k为弱密钥 (Weak key)。
)( xDESy K?
2010-5-14 18
DES的 安全性
若 k为弱密钥，则有
DESk(DESk(x))=x
DESk-1(DESk-1(x))=x
即以 k对 x加密两次或解密两次都可恢复出明文 。 其加密
运算和解密运算没有区别 。
弱密钥下使 DES在选择明文攻击下的搜索量减半 。
如果随机地选择密钥, 弱密钥所占比例极小, 而且稍加
注意就不难避开 。 因此, 弱密钥的存在不会危及 DES的
安全性 。
2010-5-14 19
DES的 安全性
密文与明文, 密文与密钥的相关性 。
Meyer[1978]详细研究了 DES的输入明文与密文及密钥与
密文之间的相关性 。 表明每个密文比特都是所有明文比
特和所有密钥比特的复合函数, 并且指出达到这一要求
所需的迭代次数至少为 5。 Konheim[1981]用 ?2检验证明,
迭代 8次后输出和输入就可认为是不相关的了 。
2010-5-14 20
DES的 安全性
S盒设计 。
DES靠 S盒实现非线性变换 。
密钥搜索机 。
对 DES安全性批评意见中, 较为一致的看法是 DES的
密钥短了些 。 IBM最初向 NBS提交的建议方案采用 112
bits密钥, 但公布的 DES标准采用 64 bits密钥 。 有人认
为 NSA故意限制 DES的密钥长度 。 采用穷搜索对已经
对 DES构成了威胁,
2010-5-14 21
二重 DES
用 DES进行两次加密，但这是否就意味着两重
DES加密的强度等价于 112 bit密钥的密码的强度？
答案是否定的。
中途相遇攻击法 (Meet-in-the-Middle Attack)
由 Diffie和 Hellman[1977]最早提出，可以降低搜
索量其基本想法如下。若有明文密文对 (xi,yi)满足
yi=Ek2[Ek1[xi]]
则可得 z=Ek1[xi]=Dk2[yi]
2010-5-14 22
二重 DES
图 4-14-1 中途相遇攻击示意图
zE E D Dx
i
yi x
i
z yi
k1 k1k2k2
2010-5-14 23
中途相遇攻击
给定一已知明密文对 (x1,y1),可按下述方法攻击 。
? 以密钥 k1的所有 256个可能的取值对此明文 x1加密, 并
将密文 z存储在一个表中；
? 从所有可能的 256个密钥 k2中依任意次序选出一个对给
定的密文 y1解密, 并将每次解密结果 z 在上述表中查
找相匹配的值 。 一旦找到, 则可确定出两个密钥 k1和
k2；
? 以此对密钥 k1和 k2对另一已知明文密文对 (x2,y2)中的明
文 x2进行加密, 如果能得出相应的密文 y2就可确定 k1和
k2是所要找的密钥 。
2010-5-14 24
中途相遇攻击
? 对于给定明文 x,以两重 DES加密将有 264个可能的密文 。
? 可能的密钥数为 21 12个 。 所以, 在给定明文下, 将有
2112/264=248个密钥能产生给定的密文 。
? 用另一对 64bits明文密文对进行检验, 就使虚报率降为
248-64=2-16。
? 这一攻击法所需的存储量为 256× 8 Byte,最大试验的加
密次数 2× 256 =257。 这说明破译双重 DES的难度为 257量级 。
2010-5-14 25
三重 DES加密
加密,y=Ek1[Dk2[Ek1 [x]]]
解密,x=Dk1[Ek2[Dk1[y]]]
? 称其为加密 -解密 -加密方案, 简记为 EDE(encrypt-
decrypt-encrypt)。
? 此方案已在 ANSI X9.17和 ISO 8732标准中采用, 并在
保密增强邮递 (PEM)系统中得到利用 。
? 破译它的穷举密钥搜索量为 2112?5× 1035量级, 而用差
分分析破译也要超过 1052量级 。 此方案仍有足够的安
全性 。
