第三章 对称加密体制
回顾
对称密码体制
? Kd=Ke,或者由其中一个很容易推出另一个
? 特点:发送者和接收者之间密钥必须安全传送。
? 代表密码,DES,IDEA
用对称密钥加密的特点
密钥必须秘密地分配
如果密钥被损害了,攻击者就能解密所有
消息,并可以假装是其中一方。
假设网络中每对用户使用不同的密钥,那
么密钥总数随着用户的增加而迅速增加。
? n个用户需要的密钥总数 =n(n-1)/2
? 10个用户需要 45个密钥
? 100个用户需要 4950个不同的密钥
回顾
分组密码体制
? 设 M为明文,分组密码将 M划分为一系列明文
块 Mi,通常每块包含若干字符,并且对每一块
Mi都用同一个密钥 Ke进行加密。即,
M=(M1,M2,… M n,) C=(C1,C2… C n,)
其中 Ci=E(Mi,Ke) i=1,2…n
回顾
序列密码体制(流密码)
? 将明文和密钥都划分为位 (bit)或字符的序列,
并且对明文序列中的每一位或字符都用密钥序
列中对应的分量来加密,即,
M=(m1,m2,… m n) Ke=(ke1,ke2…k e1)
C=(c1,c2…c n) 其中 ci=E(mi,kei) i=1,2…n
分组密码和序列密码的区别
分组密码每次加密一个明文块,序列密码每次加
密一个比特位或一个字符
序列密码的密钥有多个,组成一个密钥序列
3.1.1 分组密码设计原理
分组密码是将明文消息编码表示后的数字
(简称明文数字)序列,划分成长度为 n的
组(可看成长度为 n的矢量),每组分别在
密钥的控制下变换成等长的输出数字(简
称密文数字)序列
实际上是对长度为 n的数字序列进行置换
实现的设计原则 1
分组长度足够大
? 但是要考虑分组长度大带来的缺点
密钥空间足够大
? 目前认为 128位足够安全
由密钥确定的算法足够复杂
实现的设计原则 2
软件实现的要求:使用子块和简单的运算。密码
运算在子块上进行,要求子块的长度能自然地适
应软件编程,如 8,16,32比特等。在子块上所
进行的密码运算尽量采用易于软件实现的运算。
最好是用处理器的基本运算,如加法、乘法、移
位等。
硬件实现的要求:加密和解密的相似性,即加密
和解密过程的不同应仅仅在密钥使用方式上,以
便采用同样的器件来实现加密和解密,以节省费
用和体积。尽量采用标准的组件结构,以便能适
应于在超大规模集成电路中实现。
两个基本设计方法
Shannon称之为理想密码系统中,密文的
所有统计特性都与所使用的密钥独立
混乱 (confusion):使得密文的统计特性与
密钥的取值之间的关系尽量复杂,也就是,
当明文中的字符变化时,截取者不能预知
密文有什么变化
? 例如:凯撒密码的混乱性并不好,因为只要推
断出几个字母的转换方式,不需要更多信息就
能预测出其他字母的转换方式
扩散( Diffusion):明文的统计结构被扩散
消失到密文的长程统计特性,使得明文和密
文之间的统计关系尽量复杂
? 也就是明文的小小变化会影响到密文的很多部
分。
Li-1 Ri-1 一个分组
3.1.2 分组密码的一般结构
Feistel网络结构
Li Ri
F Ki
3.2 数据加密标准 (DES)
1973年 5月 15日,NBS开始公开征集标准加密算法,并公布
了它的设计要求,
(1)算法必须提供高度的安全性
(2)算法必须有详细的说明,并易于理解
(3)算法的安全性取决于密钥,不依赖于算法
(4)算法适用于所有用户
(5)算法适用于不同应用场合
(6)算法必须高效、经济
(7)算法必须能被证实有效
(8)算法必须是可出口的
DES的产生
1974年 8月 27日,NBS开始第二次征集,IBM提交了
算法 LUCIFER,该算法由 IBM的工程师在 1971~1972
年研制
1977年 1月 15日,“数据加密标准, FIPS PUB 46发
布
该标准规定每五年审查一次,计划十年后采用新
标准
最近的一次评估是在 1994年 1月,已决定 1998年 12
月以后,DES将不再作为联邦加密标准。
武汉工业学院计算机与信息工程系
DES特点
设计目标:用于加密保护静态储存和传输
信道中的数据,安全使用 10-15年
综合应用了置换、代替、代数等多种密码
技术
分组密码。明文、密文、密钥的分组长度
为 64位,采用 feistel结构
面向二进制的密码算法。
加密解密共用一个算法。
武汉工业学院计算机与信息工程系
DES的加密解密原理
64位密钥经子密钥产生算法 产生出 64个子密钥,K1K2…K 16,
分别供第一次、第二次 … 第十六次加密使用
64位明文首先经过 初始置换 IP(Initial Permutation),将数据
打乱重新排列并分成左右两半。左边 32位构成 L0,右边 32
位构成 R0
由加密函数 f实现子密钥 K1对 R0的加密,结果得 32位的数据
组 f(R0,K1)。 f(R0,K1)再与 L0模 2相加,又得到一个 32位的
数据组作为第二次加密迭代的 R1,以 R0作为第二次加密迭
代的 L1。至此,第一次加密迭代结束。
第二次加密迭代至第十六次迭代 分别用子密钥 K2… K16进行,
过程与第一次相同。
第十六次加密迭代结束后,产生一个 64位的数据组。左边
32位作为 R16,右边 32位作为 L16,两者合并在经过 逆初始置换
IP-1,将数据重新排列,得到 64位密文。加密过程全部结束
DES利用 56比特串长度的密钥 K来加密长度为 64位的明文,得到
长度为 64位的密文
输入 64比特明文数据
初始置换 IP
在密钥控制下
16轮迭代
初始逆置换 IP-1
输出 64比特密文数据
产生 16个密钥
Feistel结构
DES的算法细节
初始置换 IP,初始逆置换
DES的算法细节
加密函数
选择运算 E:输入 32位,输出 48位
与子密钥模 2相加
S盒运算,6位输入,4位输出
置换函数 p运算
F Ki
DES的解密过程
对合运算:加密和解密共用一个运算,子
密钥使用的顺序不同
DES存在的安全弱点
密钥较短,56位
F函数设计原理未知
存在弱密钥
? 子密钥有相重
DES的历史回顾
关于 DES算法的另一个最有争议的问题就是担心
实际 56比特的密钥长度不足以抵御穷举式攻击,
因为密钥量只有 256个
早在 1977年,Diffie和 Hellman已建议制造一个每
秒能测试 100万个密钥的 VLSI芯片。每秒测试
100万个密钥的机器大约需要一天就可以搜索整
个密钥空间。他们估计制造这样的机器大约需要
2000万美元。
在 CRYPTO’93上,Session和 Wiener给出了一
个非常详细的密钥搜索机器的设计方案,这个
机器基于并行运算的密钥搜索芯片,所以 16次
加密能同时完成。此芯片每秒能测试 5000万个
密钥,用 5760个芯片组成的系统需要花费 10万
美元,它平均用 1.5天左右就可找到 DES密钥。
1997年 1月 28日,美国的 RSA数据安全公司在
RSA安全年会上公布了一项, 秘密密钥挑战,
竞赛,其中包括悬赏 1万美元破译密钥长度为
56比特的 DES。美国克罗拉多洲的程序员
Verser从 1997年 2月 18日起,用了 96天时间,
在 Internet上数万名志愿者的协同工作下,成
功地找到了 DES的密钥,赢得了悬赏的 1万美
元。
1998年 7月电子前沿基金会( EFF)使用一台
25万美圆的电脑在 56小时内破译了 56比特密钥
的 DES。
1999年 1月 RSA数据安全会议期间,电子前沿
基金会用 22小时 15分钟就宣告破解了一个 DES
的密钥。
DES即将完成它的历史使命,给我们留下了关
于商业密码技术和商业密码政策等多方面的深
刻启发。
几个著名的对称密码体制
IDEA
? IDEA是 International Data Encryption Algorithm 的 缩写
是 1990年 由 瑞士联邦技术学院 来 学嘉 X.J.Lai 和 Massey
提 出的 建议标准 算法称作 PES Proposed Encryption
Standard Lai 和 Massey 在 1992 年 进行了 改 进 强化 了 抗差
分分 析 的能 力改 称为 IDEA
? 它也是对 64bit大 小 的数 据 块加密的分组加密算法密钥
长度为 128位它基于, 相 异 代数 群上 的 混 合运算, 设 计
思想 算法用 硬 件和 软 件实现都很 容易 它 比 DES在实现 上
快 得多
AES算法
AES算法
1997年 4月 15日美国国家标准 和 技术研究 所 NIST 发起了 征 集 AES
算法的 活动 并成 立 了 专门 的 AES工作组
目 的,为了 确 定一个非 保 密的公开 披露 的全 球免费 使用的分组密码
算法用于 保护 下一 世纪政 府 的 敏感 信息并 希望 成为秘密和公开 部
门 的数 据 加密 标准
1997年 9月 12日 在 联邦 登 记 处 公 布 了 征 集 AES候 选 算法的通 告
AES的基 本 要 求 是 比三重 DES快 而且 至 少和 三重 DES一样安全,
1998年 8月 20日 NIST召 开了 第 一次 候 选 大会并公 布 了 15个 候 选 算
法
1999年 3月 22日 举行了 第二 次 AES候 选 会 议 从中 选 出 5个 AES将成
为 新 的公开的 联邦 信息 处 理 标准
入 选 AES的五种算法是 MARS RC6 Serpent Twofish Rijndael
2000年 10月 2日美国 商务 部部 长 Norman Y,Mineta宣 布 经过 三年 来
世 界著 名密码 专家之 间的 竞争,“Rijndael数 据 加密算法, 最 终获胜
为 此 而在全 球 范围 内 角 逐 了数 年 的 激烈竞争宣告 结 束 这一 新 加密
标准 的 问 世 将取代 DES数 据 加密 标准 成为 21世纪保护国家 敏感 信
息的 高 级 算法,
思考题
一个通信游戏
两个朋友 Alice和 Bob想在晚上一起外出,
但是他们定不下是去电影院还是歌剧院。
于是,他们达成了一个通过掷硬币来决定
的协议。
Alice拿着硬币对 Bob说:, 你选择一面,
我来抛, Bob选择后,Alice把硬币抛向空
中。然后他们都注视硬币,如果 Bob选择的
那一面朝上,则他可以决定要去的地方,
否则由 Alice决定。
假如两人在电话两端
Alice对 Bob说:“你选一面,我来抛,然后
我告诉你你是否赢了”
Bob会同意吗?
如何解决?
提示
引入一个函数,我们暂时称它为奇妙函数,
它具有下面的特点
? 对于任意整数 x,由 x计算 f(x)是容易的,而给出
f(x),计算 x是不可能的
? 不可能找出一对整数( x,y),满足 x≠ y且
f(x)=f(y)
回顾
对称密码体制
? Kd=Ke,或者由其中一个很容易推出另一个
? 特点:发送者和接收者之间密钥必须安全传送。
? 代表密码,DES,IDEA
用对称密钥加密的特点
密钥必须秘密地分配
如果密钥被损害了,攻击者就能解密所有
消息,并可以假装是其中一方。
假设网络中每对用户使用不同的密钥,那
么密钥总数随着用户的增加而迅速增加。
? n个用户需要的密钥总数 =n(n-1)/2
? 10个用户需要 45个密钥
? 100个用户需要 4950个不同的密钥
回顾
分组密码体制
? 设 M为明文,分组密码将 M划分为一系列明文
块 Mi,通常每块包含若干字符,并且对每一块
Mi都用同一个密钥 Ke进行加密。即,
M=(M1,M2,… M n,) C=(C1,C2… C n,)
其中 Ci=E(Mi,Ke) i=1,2…n
回顾
序列密码体制(流密码)
? 将明文和密钥都划分为位 (bit)或字符的序列,
并且对明文序列中的每一位或字符都用密钥序
列中对应的分量来加密,即,
M=(m1,m2,… m n) Ke=(ke1,ke2…k e1)
C=(c1,c2…c n) 其中 ci=E(mi,kei) i=1,2…n
分组密码和序列密码的区别
分组密码每次加密一个明文块,序列密码每次加
密一个比特位或一个字符
序列密码的密钥有多个,组成一个密钥序列
3.1.1 分组密码设计原理
分组密码是将明文消息编码表示后的数字
(简称明文数字)序列,划分成长度为 n的
组(可看成长度为 n的矢量),每组分别在
密钥的控制下变换成等长的输出数字(简
称密文数字)序列
实际上是对长度为 n的数字序列进行置换
实现的设计原则 1
分组长度足够大
? 但是要考虑分组长度大带来的缺点
密钥空间足够大
? 目前认为 128位足够安全
由密钥确定的算法足够复杂
实现的设计原则 2
软件实现的要求:使用子块和简单的运算。密码
运算在子块上进行,要求子块的长度能自然地适
应软件编程,如 8,16,32比特等。在子块上所
进行的密码运算尽量采用易于软件实现的运算。
最好是用处理器的基本运算,如加法、乘法、移
位等。
硬件实现的要求:加密和解密的相似性,即加密
和解密过程的不同应仅仅在密钥使用方式上,以
便采用同样的器件来实现加密和解密,以节省费
用和体积。尽量采用标准的组件结构,以便能适
应于在超大规模集成电路中实现。
两个基本设计方法
Shannon称之为理想密码系统中,密文的
所有统计特性都与所使用的密钥独立
混乱 (confusion):使得密文的统计特性与
密钥的取值之间的关系尽量复杂,也就是,
当明文中的字符变化时,截取者不能预知
密文有什么变化
? 例如:凯撒密码的混乱性并不好,因为只要推
断出几个字母的转换方式,不需要更多信息就
能预测出其他字母的转换方式
扩散( Diffusion):明文的统计结构被扩散
消失到密文的长程统计特性,使得明文和密
文之间的统计关系尽量复杂
? 也就是明文的小小变化会影响到密文的很多部
分。
Li-1 Ri-1 一个分组
3.1.2 分组密码的一般结构
Feistel网络结构
Li Ri
F Ki
3.2 数据加密标准 (DES)
1973年 5月 15日,NBS开始公开征集标准加密算法,并公布
了它的设计要求,
(1)算法必须提供高度的安全性
(2)算法必须有详细的说明,并易于理解
(3)算法的安全性取决于密钥,不依赖于算法
(4)算法适用于所有用户
(5)算法适用于不同应用场合
(6)算法必须高效、经济
(7)算法必须能被证实有效
(8)算法必须是可出口的
DES的产生
1974年 8月 27日,NBS开始第二次征集,IBM提交了
算法 LUCIFER,该算法由 IBM的工程师在 1971~1972
年研制
1977年 1月 15日,“数据加密标准, FIPS PUB 46发
布
该标准规定每五年审查一次,计划十年后采用新
标准
最近的一次评估是在 1994年 1月,已决定 1998年 12
月以后,DES将不再作为联邦加密标准。
武汉工业学院计算机与信息工程系
DES特点
设计目标:用于加密保护静态储存和传输
信道中的数据,安全使用 10-15年
综合应用了置换、代替、代数等多种密码
技术
分组密码。明文、密文、密钥的分组长度
为 64位,采用 feistel结构
面向二进制的密码算法。
加密解密共用一个算法。
武汉工业学院计算机与信息工程系
DES的加密解密原理
64位密钥经子密钥产生算法 产生出 64个子密钥,K1K2…K 16,
分别供第一次、第二次 … 第十六次加密使用
64位明文首先经过 初始置换 IP(Initial Permutation),将数据
打乱重新排列并分成左右两半。左边 32位构成 L0,右边 32
位构成 R0
由加密函数 f实现子密钥 K1对 R0的加密,结果得 32位的数据
组 f(R0,K1)。 f(R0,K1)再与 L0模 2相加,又得到一个 32位的
数据组作为第二次加密迭代的 R1,以 R0作为第二次加密迭
代的 L1。至此,第一次加密迭代结束。
第二次加密迭代至第十六次迭代 分别用子密钥 K2… K16进行,
过程与第一次相同。
第十六次加密迭代结束后,产生一个 64位的数据组。左边
32位作为 R16,右边 32位作为 L16,两者合并在经过 逆初始置换
IP-1,将数据重新排列,得到 64位密文。加密过程全部结束
DES利用 56比特串长度的密钥 K来加密长度为 64位的明文,得到
长度为 64位的密文
输入 64比特明文数据
初始置换 IP
在密钥控制下
16轮迭代
初始逆置换 IP-1
输出 64比特密文数据
产生 16个密钥
Feistel结构
DES的算法细节
初始置换 IP,初始逆置换
DES的算法细节
加密函数
选择运算 E:输入 32位,输出 48位
与子密钥模 2相加
S盒运算,6位输入,4位输出
置换函数 p运算
F Ki
DES的解密过程
对合运算:加密和解密共用一个运算,子
密钥使用的顺序不同
DES存在的安全弱点
密钥较短,56位
F函数设计原理未知
存在弱密钥
? 子密钥有相重
DES的历史回顾
关于 DES算法的另一个最有争议的问题就是担心
实际 56比特的密钥长度不足以抵御穷举式攻击,
因为密钥量只有 256个
早在 1977年,Diffie和 Hellman已建议制造一个每
秒能测试 100万个密钥的 VLSI芯片。每秒测试
100万个密钥的机器大约需要一天就可以搜索整
个密钥空间。他们估计制造这样的机器大约需要
2000万美元。
在 CRYPTO’93上,Session和 Wiener给出了一
个非常详细的密钥搜索机器的设计方案,这个
机器基于并行运算的密钥搜索芯片,所以 16次
加密能同时完成。此芯片每秒能测试 5000万个
密钥,用 5760个芯片组成的系统需要花费 10万
美元,它平均用 1.5天左右就可找到 DES密钥。
1997年 1月 28日,美国的 RSA数据安全公司在
RSA安全年会上公布了一项, 秘密密钥挑战,
竞赛,其中包括悬赏 1万美元破译密钥长度为
56比特的 DES。美国克罗拉多洲的程序员
Verser从 1997年 2月 18日起,用了 96天时间,
在 Internet上数万名志愿者的协同工作下,成
功地找到了 DES的密钥,赢得了悬赏的 1万美
元。
1998年 7月电子前沿基金会( EFF)使用一台
25万美圆的电脑在 56小时内破译了 56比特密钥
的 DES。
1999年 1月 RSA数据安全会议期间,电子前沿
基金会用 22小时 15分钟就宣告破解了一个 DES
的密钥。
DES即将完成它的历史使命,给我们留下了关
于商业密码技术和商业密码政策等多方面的深
刻启发。
几个著名的对称密码体制
IDEA
? IDEA是 International Data Encryption Algorithm 的 缩写
是 1990年 由 瑞士联邦技术学院 来 学嘉 X.J.Lai 和 Massey
提 出的 建议标准 算法称作 PES Proposed Encryption
Standard Lai 和 Massey 在 1992 年 进行了 改 进 强化 了 抗差
分分 析 的能 力改 称为 IDEA
? 它也是对 64bit大 小 的数 据 块加密的分组加密算法密钥
长度为 128位它基于, 相 异 代数 群上 的 混 合运算, 设 计
思想 算法用 硬 件和 软 件实现都很 容易 它 比 DES在实现 上
快 得多
AES算法
AES算法
1997年 4月 15日美国国家标准 和 技术研究 所 NIST 发起了 征 集 AES
算法的 活动 并成 立 了 专门 的 AES工作组
目 的,为了 确 定一个非 保 密的公开 披露 的全 球免费 使用的分组密码
算法用于 保护 下一 世纪政 府 的 敏感 信息并 希望 成为秘密和公开 部
门 的数 据 加密 标准
1997年 9月 12日 在 联邦 登 记 处 公 布 了 征 集 AES候 选 算法的通 告
AES的基 本 要 求 是 比三重 DES快 而且 至 少和 三重 DES一样安全,
1998年 8月 20日 NIST召 开了 第 一次 候 选 大会并公 布 了 15个 候 选 算
法
1999年 3月 22日 举行了 第二 次 AES候 选 会 议 从中 选 出 5个 AES将成
为 新 的公开的 联邦 信息 处 理 标准
入 选 AES的五种算法是 MARS RC6 Serpent Twofish Rijndael
2000年 10月 2日美国 商务 部部 长 Norman Y,Mineta宣 布 经过 三年 来
世 界著 名密码 专家之 间的 竞争,“Rijndael数 据 加密算法, 最 终获胜
为 此 而在全 球 范围 内 角 逐 了数 年 的 激烈竞争宣告 结 束 这一 新 加密
标准 的 问 世 将取代 DES数 据 加密 标准 成为 21世纪保护国家 敏感 信
息的 高 级 算法,
思考题
一个通信游戏
两个朋友 Alice和 Bob想在晚上一起外出,
但是他们定不下是去电影院还是歌剧院。
于是,他们达成了一个通过掷硬币来决定
的协议。
Alice拿着硬币对 Bob说:, 你选择一面,
我来抛, Bob选择后,Alice把硬币抛向空
中。然后他们都注视硬币,如果 Bob选择的
那一面朝上,则他可以决定要去的地方,
否则由 Alice决定。
假如两人在电话两端
Alice对 Bob说:“你选一面,我来抛,然后
我告诉你你是否赢了”
Bob会同意吗?
如何解决?
提示
引入一个函数,我们暂时称它为奇妙函数,
它具有下面的特点
? 对于任意整数 x,由 x计算 f(x)是容易的,而给出
f(x),计算 x是不可能的
? 不可能找出一对整数( x,y),满足 x≠ y且
f(x)=f(y)