2011年 10月 17日星期一
导 论
认证技术
网络安全
系统安全
安全管理
安全协议
加密技术
密钥管理
2011年 10月 17日星期一
导 论
认证技术
网络安全
系统安全
安全管理
安全协议
加密技术
密钥管理
密码学概述
对称密码体制
公钥密码体制
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
密码学的发展
第 2章




上一页
下一页
目录
结束
10:22
密码学 (Cryptology),是研究信息系统安全保密的
科学。密码学作为数学的一个分支,包括密码编码
学和密码分析学。
密码编码学 (Cryptography),主要研究对信息进行
编码,实现对信息的隐蔽 。密码体制的设计是密码
编码学的主要内容,
密码分析学 (Cryptanalytics):主要研究加密消息
的破译或消息的伪造。密码体制的破译是密码分析
学的主要内容。
密码学概述
基本概念
密码学 (1/3)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
密码学 (2/3)
密码编码学
密码分析学
密码体制的设计
密码体制的破译



密码编码技术和密码分析技术是相互依存、相互
支持、密不可分的两个方面。
精于此道的人称为密码学家( Cryptologist),
现代的密码学家通常也是理论数学家。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
密码学 (3/3)
密码学的主要作用
提供机密性
鉴 别 消息的接收者应该能够确认消息的来源;入侵者不可能伪装成他人。
完整性
消息的接收者应该能够验证在传送过程中
消息没有被修改;入侵者不可能用假消息
代替合法消息。
抗抵赖 消息的发送者事后不可能虚假地否认他发送的消息。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
密码学的发展
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (1/11)
明文
信息的原始形式称为明文( plaintext)。
明文用 M或 P表示。
位序列,文本文件,位图,
数字化语音序列,数字化视频图像等。
明文的形式可能是,
对于计算机,明文指二进制数据。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (2/11)
密文
明文经过加密变换后的形式称为密文
( ciphertext)。
密文用 C表示。
对于计算机,密文是二进制数据。
第 2章




上一页
下一页
目录
结束
10:22
加密
由明文变成密文的过程称为加密 (enciphering)。
通常记作 E。
加密函数 E作用于 M得到密文 C。
可用数学公式表示,
E(M) = C
密码学概述
基本概念
基本术语 (3/11)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (4/11)
解密
由密文变成明文的过程称为解密 (deciphering)。
通常记作 D。
解密函数 D作用于 C得到明文 M。
可用数学公式表示,
D(C) = M
第 2章




上一页
下一页
目录
结束
10:22
加密和解密的过程可以表示为,
密码学概述
基本概念
基本术语 (5/11)
明文 明文 密文
先加密再解密,原始明文将恢复。故等式,
D(E(M)) = M
必须成立
加密 解密
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (6/11)
算法
算法是用于加密和解密的数学函数。
如果算法的保密性是基于保持算法的秘密,这种
算法称为 受限制的算法 。
受限制的算法流行于低密级的应用。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (7/11)
密钥
密钥是参与加密或解密变换的参数 (key)。通常
用 K表示。
通过引入密钥,算法的安全性依赖于密钥的安全
性,而不是算法细节的安全性。
密钥的引入使得算法可以公开,或被分析,并使
大量生产使用某一算法的产品成为可能。
第 2章




上一页
下一页
目录
结束
10:22
明文 明文 密文
密钥 密钥
密码学概述
基本概念
基本术语 (8/11)
加密和解密算法的操作通常都是在一组密钥的控
制下进行的,分别称为 加密密钥 (EncryptionKey)
和 解密密钥 (Decryption Key),
加密函数为,EK1(M)=C 解密函数为,DK2(C)=M
并满足,DK2(EK1(M)) = M
第 2章




上一页
下一页
目录
结束
10:22
密码体制
密码学概述
基本概念
基本术语 (9/11)
通常一个完整的密码体制是一个五元组( P,C,K,E,D)
满足条件,
1) P是可能明文的有限集;(明文空间)
2) C是可能密文的有限集;(密文空间)
3) K是一切可能密钥构成的有限集;(密钥空间)
4)任意 k∈ K,有一个加密算法 ek∈E 和相应的解密
算法 dk∈D,使得 ek:P?C和 dk:C ?P分别为加密解
密函数,满足 dk(ek(p))=p,这里 p∈ P。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (10/11)
小结 -1
明文( Plaintext):消息的初始形式;
密文( CypherText):加密后的形式
明文记为 P且 P为字符序列,P=[P1,P2,…,Pn]
密文记为 C,C=[C1,C2,…,Cn]
明文和密文之间的变换记为 C=E(P)及 P=D(C)
其中,C表示密文,E为加密算法;
P表示明文,D为解密算法
我们要求密码系统满足,P=D(E(P))
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
基本术语 (11/11)
小结 -2
需要密钥的加密算法,记为,C=E(K,P),即密文消
息同时依赖于初始明文和密钥的值。
实际上,E是一组加密算法,而密钥则用于选择其
中特定的一个算法。
加密与解密的密钥相同,即,P=D(K,E(K,P))
加密与解密的密钥不同,则,P=D(KD,E(KE,P))
无钥密码:不需要使用密钥的密码
单钥密码:加密与解密的密钥相同
双钥密码:加密与解密的密钥不同
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
密码学的发展
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类 (1/5)
基本概念
? 按照保密的内容分类,
? 受限制的( restricted)算法,算法的保密性基
于保持算法的秘密。
? 基于密钥( key-based)的算法,算法的保密性基
于对密钥的保密。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类 (2/5)
基本概念
? 基于密钥的算法,按照密钥的特点分类,
? 对称密码算法( symmetric cipher),又称传统
密码算法( conventional cipher),就是加密密钥
和解密密钥相同,或实质上等同,即从一个易于推
出另一个。又称秘密密钥算法或单密钥算法。
? 非对称密钥算法( asymmetric cipher):加密密
钥和解密密钥不相同,从一个很难推出另一个。又
称公开密钥算法( public-key cipher) 。
公开密钥( public key),公开密钥算法中的加密
密钥,简称公钥。
私人密钥( private key):公开密钥算法中的解密
密钥,简称私钥。
第 2章




上一页
下一页
目录
结束
10:22
? 按照明文的处理方法分类,
? 分组密码( block cipher):将明文分成固定长
度的组,用同一密钥和算法对每一块加密,输出也
是固定长度的密文。
? 流密码( stream cipher):又称 序列密码,序列
密码每次加密一位或一字节的明文,也可以称为流
密码。
序列密码是手工和机械密码时代的主流
密码学概述
密码算法的分类 (3/5)
基本概念
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类 (4/5)
基本概念
? 对称密钥密码又可分为,
? 分组密码
每次对一块数据加密
多数网络加密应用
DES,IDEA,RC6,Rijndael
? 流密码
每次对一位或一字节加密
手机
One-time padding,Vigenére,Vernam
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类 (5/5)
基本概念
? 公开密钥密码,
? 大部分是分组密码,只有概率密码体制属
于流密码
每次对一块数据加密
数字签名,身份认证
RSA,ECC,ElGamal
加密解密速度慢
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
? 密码学的发展
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
基本概念
密码学的发展
1.密码学的起源
作为保障数据安全的一种方式,数据加密起源于公
元前 2000年。埃及人是最先使用特别的象形文字作
为信息编码的人。随着时间推移,巴比伦、美索不
达米亚和希腊都开始使用一些方法来保护他们的书
面信息。
2.密码学的发展
密码学的发展可以分为三个阶段,
第一个阶段:古代加密法 (隐写术、黑帮行话 )
第二个阶段:传统密码学阶段 (手工或机械变换 )
第三个阶段:计算机密码学阶段
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法的分类
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
密码学的发展
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (1/23)
经典密码又称古典密码,它是基于字符的密码。
? 代替密码( substitution cipher):就是明
文中的每一个字符被替换成密文中的另一个字符。
接收者对密文做反向替换就可以恢复出明文。
? 置换密码 (permutation cipher),又称换位
密码( transposition cipher):明文的字母保
持相同,但顺序被打乱了。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (2/23)
1,代替密码
单表代替密码
多名码代替密码 多字母代替密码
多表代替密码
单字母密码
多字母密码
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (3/23)
1) 单表代替密码
明文的一个字符用相应的一个密文字符代替。
简单代替密码由于使用从明文到密文的单一映
射,所以明文字母的单字母出现频率与密文中
相同。
移位 (shift)密码、乘数 (multiplicative)密码,
仿射 (affine)密码、多项式 (Polynomial)密码,
密钥短语 (Key Word)密码
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (4/23)
① Caesar( 恺撒 ) 密码
它的加密方法就是把明文中所有字母都用它右边的
第 k个字母替代, 并认为 Z后边又是 A。 这种映射关系
表示为如下函数,
c=F(m)=(m+k) mod n (n为字母个数 )
明文 a b c d e f g h i j k l m
密文 E F G H I J K L M N O P Q
明文 n o p q r s t u v w x y z
密文 R S T U V W X Y Z A B C D
m=end c=IRH K=4
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (5/23)
② 其它单字母单表代替密码 -1
( Key=GUANGDONGGDCCHUMEIYAN)
明文 a b c d e f g h i j k l m
密文 G U A N D O C H M E I Y B
明文 n o p q r s t u v w x y z
密文 F J K L P Q R S T V W X Z
m=internet c=MFRDPFDR
第 2章




上一页
下一页
目录
结束
10:22
对字母进行无规则的重新排列
E(i)=3*i mod 26
密码学概述
密码算法概述
经典密码算法 (6/23)
② 其它单字母单表代替密码 -2
例,m=internet
c=YNFMZNMF
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
a d g j m p s v y b e h k n q t w z c f i l o r u x
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (7/23)
2) 多表代换密码
由多个简单的代替密码构成。它有多个单字母密钥,
每一个密钥被用来加密一个明文字母。
维吉尼亚 (Vigenere)密码、博福特 (Beaufort)密
码,
滚动密钥 (running-key)密码、弗纳姆 (Vernam)密
码、转子机 (rotor machine)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (8/23)
例:维吉尼亚 ( Vigenere) 密码
这种替代法是循环的使用有限个字母来实现替代的
一种方法 。 若明文信息 mlm2m3… mn,采用 n个字母
( n个字母为 B1,B2,… Bn) 替代法, 那么, mn将根
据字母 Bn的特征来替代, mn+l又将根据 B1的特征来
替代, mn+2又将根据 B2的特征来替代 ……, 如此循
环 。 可见 B1,B2,… Bn就是加密的密钥 。
这种加密的加密表是以字母表移位为基础把 26个英
文字母进行循环移位, 排列在一起, 形成 26× 26的
方阵 。 该方阵被称为维吉尼亚表 。 采用的算法为,
F(a)=(a+Bi) mod n ( i=( 1,2,…, n))
第 2章




上一页
下一页
目录
结束
10:22
设 d为一固定的正整数,d个移位代换表 π=(π 1,
π 2,… π d)由密钥序列 K= (k1,k2,…,kd)给定,第
i+td个明文字母由表 π i决定,即密钥 ki决定。
ek(xi+td)=(xi+td+ki,) mod q =y
dk(yi+td)= (xi+td-ki) mod q =x
如,q=26,m=polyalphabetic cipher,K=RADIO
明文 m=p o l y a l p h a b e t i c c i p h e r
密钥 k=R A D I O R A D I O R A D I O R A D I O
密文 c=G O O G O C P K I P V T L K Q Z P K M F
密码学概述
密码算法概述
经典密码算法 (9/23)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (10/23)
3) 多字母代替密码
字符块被成组加密。
明文中的字符映射到密文空间的字符还依赖于
它在上下文中的位置。
可以用矩阵变换方便地描述多字母代换密码,
所以有时又称起为矩阵变换密码。
Hill cipher
Playfair cipher
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (11/23)
① HiLL密码
? Hill密码是一个基于矩阵的线性变换
? 将明文 P分成 m个字母一组的明文组,即 明文 p与
密文 c都是 m元的向量,
( p1,p2 …,pm );(c1,c2,…,cm),
? K是一个 m× m矩阵,在 Z/(26)上可逆,即存在 K-1
使得, KK-1 = I (在 Z/(26))
? 则, C=KP
C1
=
k11 k12 … k1m P1
C2 k21 k22 … k2m P2 …





CM km1 km2 … kmm PM
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (12/23)
例:用密钥 K= 来加密明文,july 11 3 8 7
将 P=(j u l y)=(9,20,11,24)分成 m(m=2)个字母一
组,即,(9,20),(11,24),计算如下,
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C1 = 11 3 9 = 99 + 60 = 3 = D
C2 8 7 20 72 + 140 4 E
C3 = 11 3 11 = 121 + 72 = 11 = L
C4 8 7 24 88 + 168 22 W
C=DELW
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (13/23)
解密:用密钥矩阵的逆矩阵 K-1对密文 DELW进行解
密。计算如下:设,K-1=
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
P1 = 7 23 3 = 21 + 92 = 9 = j
P2 18 11 4 54 + 44 20 u
P3 = 7 23 11 = 77 + 506 = 11 = l
P4 18 11 22 198 + 242 24 y P=july
P=K-1C
KK-1= I
a b
c d
11 3 a b = 11a+3c 11b+3d = 1 0
8 7 c d 8a+7c 8b+7d 0 1
解方程组,11a+3c=1 11b+3d=0 8a+7c=0 8b+7d=1 7 23 18 11 K-1=
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (14/23)
4) 多名码代替密码
单个字符明文可以映射成密文的几个字符之一。
与简单代替密码类似,只是映射是一对多的,每个
明文字母可以加密成多个密文字母。
例如,A可能对应于 5,13,25
B可能对应于 7,9,31,42
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (15/23)
2,置换密码
在置换密码中,明文的字母保持相同,但顺序
被打乱。
列换位法 矩阵换位法
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (16/23)
1) 列换位法
列换位法就是将明文字符分割成为若干个字符一列
的分组,并按一组后面跟着另一组的形式排好。
如明文是,WHAT YOU CAN LEARN FROM THIS BOOK
分组排列为,
W H A T Y
O U C A N
F R O M T
H I S B O
O K X X X
密文则以列的形式读出,
WOFHOHURIKACOSXTAMBXYNTOX
这里的密钥是数字 5。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (17/23)
2) 矩阵换位法
这种加密是把明文中的字母按给定的顺序安排在一
个矩阵中,然后用另一种顺序选出矩阵的字母来产
生密文。
如将明文 ENGINEERING按行排在 3*4矩阵中,如下所
示,
1 2 3 4
E N G I
N E E R
I N G ???
?
??
?
?
?
2 4 1 3
1 2 3 4
f
给定一个置换,
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (18/23)
现在根据给定的置换, 按
第 2列, 第 4列, 第 1列, 第
3列的次序排列, 就得得到
密文,
NIEGERNEN IG
在这个加密方案中, 密钥
就是矩阵的行数 m和列数 n,
即 m*n= 3*4,以及给定的
置换矩阵 。 也就是,
k=( m*n,f)
1 2 3 4
N I E G
E R N E
N I G
1 2 3 4
E N G I
N E E R
I N G
第 2章




上一页
下一页
目录
结束
10:22
其解密过程是将密文根据 3*4矩阵, 按行,
列的顺序写出, 再根据给定置换产生新的矩
阵, 恢复明文为,
ENGINEERING
1 2 3 4
N I E G
E R N E
N I G
1 2 3 4
E N G I
N E E R
I N G
密码学概述
密码算法概述
经典密码算法 (19/23)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (20/23)
3.一次密码本
? 有一种理想的加密方案,叫做一次密码本
( One-Time Pad) 。
? 一次密码本是一个大的不重复的真随机密钥字
母集,这个密钥字母集被写在几张纸上,并被粘成
一个密码本。它最初的形式是用于电传打字机。
? 发送者用密码本中的每一密钥字母准确地加密
一个明文字符。
? 加密是明文字符和一次密码本密钥字符的模 26
加法。
第 2章




上一页
下一页
目录
结束
10:22
? 每个密钥仅对一个消息使用一次。
? 发送者对所发送的消息加密,然后销毁密码本
中用过的一页或磁带部分。
? 接收者有一个同样的密码本,并依次使用密码
本上的每个密钥去解密密文的每个字符。
? 接收者在解密消息后销毁密码本中用过的一页
或磁带部分。
? 新的消息则用密码本中新的密钥加密。
密码学概述
密码算法概述
经典密码算法 (21/23)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
经典密码算法 (22/23)
例如, 如果消息是,
ONE TIME PAD
而取自密码本的密钥序列是,
TBF RGFA RFM
那么密文就是,
IPK LPSF HGQ
因为
O+ T mode 26=I
N+ B mode 26=P
E+ F mode 26=K
第 2章




上一页
下一页
目录
结束
10:22
一次一密密码体制的特点,
? 每个密钥仅对一个消息使用一次
? 密钥以随机方式产生。
? 密钥长度等于明文长度。
? 发送者和接收者必须完全同步。
? 是 唯一达到理论不可破译的密码体制。
密码学概述
密码算法概述
经典密码算法 (23/23)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
对称算法 (1/4)
对称算法 (symmetric algorithm)中,加密密钥
能够从解密密钥中推算出来,反之也成立。
在大多数对称算法中,加密密钥和解密密钥是相
同的。
对称算法又叫:秘钥密码算法、单密钥算法
对称算法的安全性依赖于密钥。
对称算法的加密和解密可表示为,
EK(M) = C
DK(C) = M
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
对称算法 (2/4)
小王使用密
钥进行解密
老李使用密
钥进行加密
“我们的五年计划是,..”
老李 小王
密钥
“Py75c%bn&*)9|fDe^bDFaq#x
zjFr@g5vMd’rkgMs”
密文
“我们的五年计划是,..”
Internet
解密
Decryption
加密
Encryption
密钥密码 ( 对称密钥 ) 体制, 就
是加密密钥和解密密钥相同, 即,
Ke=Kd=K
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
对称算法 (3/4)
对称算法存在的问题,
1)通信双方如何安全交换密钥的问题。虽然对称加
密体制使加密和解密都比较快,问题是如何将密钥传
给要保密的用户。(因为,密钥的传送也属于信息的
传递,一旦被黑客截获,原信息虽然已经被加密,在
传送过程中也不再安全)
2)当某一贸易方有 n个贸易关系时,那么他就要维护
n个专用密钥,即每把密钥对应一个贸易方。密钥空
间为 n?(n+1)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
对称算法 (4/4)
3)无法鉴别贸易发起方和贸易最终方。
4)用穷举搜索法破译 DES已成为可能。
5)密钥更新的周期长。为了解决 DES免糟破译的问
题,需要加长或常更密钥。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
公开密钥算法 (1/4)
公钥密码 ( public-key algorithm)算法也称双钥密
码(或非对称密钥钥)体制。
公开密钥算法中,加密密钥不同于解密密钥,
并且解密密钥不能根据加密密钥计算出来。
在公开密钥算法中,加密密钥可以公开,即陌生者可
以用加密密钥加密信息,但只有用相应的解密密钥才
能解密信息。
加密密钥叫公开密钥( public-key,简称 公钥 )
解密密钥叫私人密钥( self-key,简称 私钥 )
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
公开密钥算法 (2/4)
公钥密码体系的主要特点
公钥密码体系的主要特点就是加密和解密使用不同的
密钥, 每个用户都有一对选定的密钥 ( 所以又称双
钥 ), 即,
? 公钥 KP( public key) 是可以公开的, 它可以
像电话号码一样注册公布
? 私钥 KS( self key) 是秘密的, 私用的 。
? 由 KP不能计算出 KS。
? 加密和解密分开 。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
公开密钥算法 (2/4)
Internet
“Py75c%bn&*)9|fDe^b
DFaq#xzjFr@g5vMd’rk
gMs”
“我们的五年计划
是,..”
小王使用自己
的私钥进行解
密得到明文
老李使用对方
的公钥对信息
明文进行加密
老李 A 密文
“我们的五年计划
是,..”
解密
Decryption
加密
Encryption
小王的
公钥
小王的
私钥
小王 B
公钥密码 ( 非对称密钥 ) 体制, 就
是加密密钥和解密密钥不同, 即,
Ke?Kd
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
公开密钥算法 (3/4)
具体步骤为,
( 1)信息接收端首先产生一对密钥,其中一把作为私钥
保存起来,另一把作为公钥,通过非保密方式传送给信
息发送方;
( 2)信息发送方使用接收到的公钥和公开密钥加密算法
对发送的信息进行加密,产生密文;
( 3)密文通过网络传送到信息接收方;
( 4)信息接收方使用自己的私钥和公开密钥加密算法对
密文进行解密,得到信息明文。
A 端 C=EKPB(m)
B 端 m=DKSB(c)= DKSB(EKPB(m))
第 2章




上一页
下一页
目录
结束
10:22
公开密码体制具有如下优点,
1)密钥分发简单。
2)秘密保存的密钥量减少。
3)在互不信任的通信双方之间,可以相互验证
对方身份。
4)可以实现数字签名。
密码学概述
密码算法概述
公开密钥算法 (4/4)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
混合密码系统( 1/2)
混合密码系统中,公开密钥密码用来保护和分发密
钥。这些会话密钥用在对称算法中,对通信消息进
行保密。
使用混合密码系统的优势,
1)把公开密钥密码用于密钥分配解决了对称密
码系统的密钥管理问题。
2)公开密钥算法比对称算法慢。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
混合密码系统( 2/2)
? ? 公钥 公钥




Internet ? ? ? ?
? ? ? ?
? ? 对称密钥
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性
?
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
加密模式
对明文的加密模式有,
流密码( stream cipher):又称 序列密码,序列密码
每次加密一位或一字节的明文,也可以称为流密码。
序列密码是手工和机械密码时代的主流
分组密码( block cipher):将明文分成固定长度的
组,用同一密钥和算法对每一块加密,输出也是固
定长度的密文。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码学的发展
基本概念
密码学
基本术语
密码算法概述
经典密码算法
对称算法
公开密钥算法
混合密码系统
加密模式
算法的安全性 ?
第 2章




上一页
下一页
目录
结束
10:22
1,密码分析
密码分析学是在不知道密码的情况下,恢复出明文
的科学。
对密码进行分析的尝试称为攻击。
密码分析的一个基本假设,秘密必须全寓于密钥中。
即假设破译者是在已知密码体制的前提下来破译加
密者使用的密钥。这个假设称为 Kerckhoff原则。
其一切的目的在于 破译出密钥或密文。
密码学概述
密码算法概述
算法的安全性 (1/11)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (2/11)
最常见的破解类型,
1) 唯密文攻击 (ciphertext-only attack)
2) 已知明文攻击 (known-plaintext attack)
3) 选择明文攻击 (chose-plaintext attack)
4) 选择密文攻击 (chosen-ciphertext attack)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (3/11)
1) 唯密文攻击
密码分析者有一些消息的密文,这些消息都用同一
加密算法加密。
密码分析者的任务是:恢复尽可能多的明文,或能
够推算出加密消息的密钥,以便可采用相同的密钥
解出其他被加密的消息。
已知,C1=EK(P1),C2=EK(P2),…,Ci=EK(Pi)
推导出,P1, P2,…,Pi;或者 K
除一次一密乱码系统外,所有其他密码系统在唯密
文攻击中都是可破的。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (4/11)
2)已知明文攻击
密码分析者不仅有一些消息的密文,而且也知道
这些消息的明文。
密码分析者的任务是:用加密信息推算出加密消
息的密钥,或导出一个算法,此算法可以对用同
一密钥加密的任何新的消息进行解密。
已知,
P1,C1=EK(P1),P2,C2=EK(P2),…,Pi,Ci=EK(Pi)
推导出,
密钥 K;或者从 Ci+1=EK(Pi+1)推导出 Pi+1的算法。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (5/11)
3)选择明文攻击
密码分析者不仅有一些消息的密文和明文,而且也
可选择被加密的明文。
密码分析者的任务是:推出加密消息的密钥,或导
出一个算法,此算法可以对用同一密钥加密的任何
新的消息进行解密。
已知,
P1,C1=EK(P1),P2,C2=EK(P2),…,Pi,Ci=EK(Pi),
其中 P1, P2,…,Pi可以由密码分析者选择。
推导出,
密钥 K;或者从 Ci+1=EK(Pi+1)推导出 Pi+1的算法。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (6/11)
选择明文攻击比已知明文攻击更有效。因为密码分
析者能够选择特定的明文块加密,那些块可能产生
更多的关于密钥的信息。
自适应选择明文攻击
密码分析者不仅能选择被加密的明文,而且也能基
于以前加密的结果修正这个选择。
自适应选择明文攻击是选择明文攻击的特殊情况。
在自适应选择明文攻击中,密码分析者可以选取较
小的明文块,然后再基于第一块的结果选择另一明
文块。而在选择明文攻击中,密码分析者可以选取
一大块被加密的明文。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (7/11)
4) 选择密文攻击
密码分析者可选择不同的被加密的密文,并可得到
对应的解密的明文。
密码分析者的任务是:推出加密消息的密钥。
已知,
C1,P1=DK(C1),C2,P2=DK(C2),…,Ci,Pi=DK(Ci),
推导出,
密钥 K
选择密文攻击主要用于公开密钥算法。
第 2章




上一页
下一页
目录
结束
10:22
2,算法的安全性
根据被破译的难易程度,不同的密码算法具有不同
的安全等级。
无条件安全( Unconditionally secure)
无论破译者有多少密文,他也无法解出对应的明文,
即使他解出了,他也无法验证结果的正确性,
例如:一次一密乱码本 (One time pad)
计算上安全( Computationally secure)
破译的代价超出信息本身的价值
破译的时间超出了信息的有效期
密码学概述
密码算法概述
算法的安全性 (8/11)
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (9/11)
破译算法按安全性递减的顺序分类为,
( 1) 全部破译 ( total attack)。密码分析者找出
密钥 K,这样 DK( C) = P。
( 2) 全盘推导 ( global deduction)。密码分析者
找到一个代替算法 A,在不知道密钥 K的情况下,等
价于 DK( C) = P。
( 3) 实例(或局部)推导 ( instance (or local)
deduction)。密码分析者从截获的密文中找出明文。
( 4) 信息推导 ( information deduction)。密码
分析者获得一些有关密钥或明文的信息。这些信息
可能是密钥的几个位,有关明文格式的信息等。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (10/11)
3,算法的复杂性
密码学更关心 在计算上不可破译的密码系统 。如果
一个算法用可得到的资源都不能破译,这个算法则
被认为在计算上是安全的。
攻击方法的复杂性
可用不同方式衡量攻击方法的复杂性,
1)数据复杂性:用作攻击输入所需的数据量。
2)处理复杂性:完成攻击所需要的时间。
3)存储需求,进行攻击所需要的存储量。
攻击的复杂性取三个因数的最小值。
第 2章




上一页
下一页
目录
结束
10:22
密码学概述
密码算法概述
算法的安全性 (11/11)
一个算法的复杂性即运行它所需的计算能力。
复杂性用数量级表示。
如果算法的处理复杂性是 2128,那么破译这个算法需
要 2128次运算。
假设有足够的计算速度完成每秒钟 100万次运算,并
且用 100万个并行处理器完成这个任务,仍需花费
1019年(宇宙年龄的 10亿倍)以上才能找出密钥。
当攻击的复杂性是常数时,则破译算法的难度只取决
于计算能力。
2011年 10月 17日星期一
导 论
认证技术
网络安全
系统安全
安全管理
安全协议
加密技术
密钥管理
密码学概述
对称密码体制
公钥密码体制
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码分类
对称密码的基本运算
对称密码分析的基本方法
对称密码的设计原则
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
在对称密码体制中,加密密钥和解密密钥相同,
或彼此之间容易相互确定。
分组密码( block cipher):将明文分成固定长度
的组,用同一密钥和算法对每一块加密,输出也
是固定长度的密文。
流密码( stream cipher):又称序列密码,序列密
码每次加密一位或一字节的明文,也可以称为流
密码。
对称密码分类 (1/4)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分类 (2/4)
1,流密码的基本原理
1) 根据密钥 k,由密钥发生器 f 产生一个密钥流
z = z0z1…
zi = f( k,?i )
?i是加密器中记忆元件(存储器)在时刻 i的
状态
2) 对明文串 M=m0m1m2… 进行如下规则的加密操作,
C=ez0(m0)ez1(m1)ez2(m2)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分类 (3/4)
M C
K
k0 k1 …
m0 m1 …
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分类 (4/4)
2,分组密码的基本原理
1) 将明文分为 n 个组,
M=m0 m1 m2 … mn
2) 对不同的明文组采用同样的密钥 k 加密,
C=ek(m0)ek(m1)… ek(mn)
M C
K
m0 m1 …
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码分类
对称密码的基本运算
对称密码分析的基本方法
对称密码的设计原则
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码的基本运算
1.代替
代替( substitution):就是明文中的每一个字符被
替换成密文中的另一个字符。接收者对密文做反
向替换就可以恢复出明文。
2.置换
置换 (permutation),又称换位( transposition):
明文的字母保持相同,但顺序被打乱了。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码分类
对称密码的基本运算
对称密码分析的基本方法
对称密码的设计原则
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分析的基本方法 (1/4)
1,系统分析法 (统计分析法 )
1)通过字母的使用频率分析
0
2
4
6
8
10
12
14
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
?μ ?ê
第 2章




上一页
下一页
目录
结束
10:22
例:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMD
ZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZ
HMDJUDTMOHMQ
0
2
4
6
8
10
12
14
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
?μ ?ê ?ü ?? ×? ?? ?μ ?ê
对称密码体制
对称密码体制概述
对称密码分析的基本方法 (2/4)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分析的基本方法 (3/4)
2)根据英文单词组合统计规律。例:有一密文,
wklv phvvdjh lv qrw wrr kdug wr euhdn
T--- ------- -- -OT TOO ---- TO -----
T--- ------- -- NOT TOO ---- TO -----
T-IS ------- IS NOT TOO ---- TO -----
1,空格给出了分词的重要信息(通常实用中将空格删除,
甚至通常将字符分 5个一组书写。)
2,先考虑英语中的短词,如,am is to be he we …,and are
you she 等
3,重要线索,wrr,英文中常用 xyy结构的单词只有 see和 too,
次常用的单词还有 add,odd,off,特别生疏的单词 woo和 gee
4,单词 lv是 wklv的结尾,有可能是双字母单词 SO,IS,IN等等
…,T -SO不可能 ;q=N,IN不可能。 Lv可能是 IS,
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码分析的基本方法 (4/4)
2,穷举法
只要简单地一个接一个地去试每种可能的密钥,
并且检查所得的明文是否有意义,就可分析出其
密码系统。
该方法也叫“蛮力攻击”。
但这种方法不能用于一次一密乱码系统。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码分类
对称密码的基本运算
对称密码分析的基本方法
对称密码的设计原则
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码的设计原则 (1/2)
对称密码的设计原则是混淆和扩散。
1,混淆
使得密文的统计特性与密钥的取值之间的关系尽
量复杂。在一个理想的密码系统中,密文的所有
统计特性都应与所使用的密钥独立,然而实用的
密码系统都很难达到这个目标。(除一次一密乱
码本)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
对称密码体制概述
对称密码的设计原则 (2/2)
2,扩散
明文的统计结构被扩散消失到密文的长程统计特
性,使得明文和密文之间的统计关系尽量复杂。
要做到这一点,就必须让明文的每个比特影响到
密文许多比特的取值,即每个密文比特被许多明
文比特影响。
迭代密码是实现混淆和扩散原则的一种有效方法。
合理选择的轮函数经过若干次迭代后能提供必要
的混淆和扩散。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的一般原理
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
分组密码的结构
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的一般原理 (1/3)
分组密码是将明文消息编码表示后的数字(简称明
文数字)序列,划分成长度为 n的组(可看成长度
为 n的矢量),每组分别在密钥的控制下变换成等
长的输出数字(简称密文数字)序列。
加密算法 k=( k0,k1,… kn-1 )
( m0,m1,… mn-1 )
( c0,c1,… cn-1 )
( m0,m1,… mn-1 )
解密算法 k=( k0,k1,… kn-1 )
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的一般原理 (2/3)
1) 将明文编码表示为数字序列
m0,m1,m2,……
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
如:明文 Information Security,可表示为,
8,13,5,14,17,12,0,19,8,14,13,18,4,2,20,17,8,19,24
2) 再划分为长度为 n的组
M = ( m0,m1,… mn-1 )
3) 每组分别在密钥 K=( k0,k1,… kn-1 )控制下变换
成等长的密文数字序列 C=( c0,c1,… cn-1)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的一般原理 (3/3)
实现的设计原则,
? 软件实现的要求:使用子块和简单的运算 。 密码
运算在子块上进行, 要求子块的长度能自然地适应
软件编程, 如 8,16,32比特等 。 应尽量避免按比特
置换, 在子块上所进行的密码运算尽量采用易于软
件实现的运算 。 最好是用处理器的基本运算, 如加
法, 乘法, 移位等 。
? 硬件实现的要求:加密和解密的相似性, 即加密
和解密过程的不同应仅仅在密钥使用方式上, 以便
采用同样的器件来实现加密和解密, 以节省费用和
体积 。 尽量采用标准的组件结构, 以便能适应于在
超大规模集成电路中实现 。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的一般原理
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
分组密码的结构
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的结构 (1/5)
常用的分组密码结构有两种,
1) Feistel网络结构
DES
FEAL
Blowfish
RC5
2) SP网络结构
SAFER
SHARK
AES
第 2章




上一页
下一页
目录
结束
10:22
1,Feistel网络结构
1)将明文 P分为左右相等
长度的两半 L0,R0
2)将 R0→ L 1
L0⊕F(R 0,k1) →R 1
3)在第 i轮时
Ri-1→ L i
Li-1⊕F(R i-1,ki) →R i
4)至止最后一轮 n
Ln=Rn-1
Rn=Ln-1⊕F(R n-1,kn)
对称密码体制
分组密码原理
分组密码的结构 (2/5)
P
L0 R0
L1 R1
k1
F +
F +
Li Ri
ki


F +
Ln Rn
kn


第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的结构 (3/5)
Feistel网络的结构描述,
加密, Li = Ri-1
Ri = Li-1?F(Ri-1,Ki)
解密, Ri-1 = Li
Li-1 = Ri?F(Ri-1,Ki)
= Ri?F(Li,Ki)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的结构 (4/5)
Feistel结构的分析,
? Block size(64 ? 128)
? Key size(56 ? 128~256)
? Number of rounds(16)
? Subkey generation
? Round function(F)
? Fast software encryption/decryption
? Easy hardware implementation
? Simple structure
? Ease of analysis
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码原理
分组密码的结构 (5/5)
2.SP网络结构
在这种密码的每一轮中,
轮输入首先被一个由子
密钥控制的可逆函数 S作
用,然后再对所得结果
用置换(或可逆线性变
换) P作用。 S和 P分别被
称为混乱层和扩散层,
主要起混乱和扩散作用。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES背景 (1/5)
1,DES的产生
1972年
美国国家标准局( NBS)拟订了一个旨在保护计算机
和通信数据的计划。开发一个单独的标准密码算法
是该计划的一部分。
1973年 5月 15日
美国国家标准局( NBS)发布征集标准密码算法公告。
DES,Data Encryption Standard,数据加密标准
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES背景 (2/5)
同时,NBS确定了一系列设计准则,
? 算法必须提供较高的安全性。
? 算法必须完全确定且易于理解。
? 算法的安全性必须依赖于密钥,而不应依赖
于算法。
? 算法必须对所有的用户都有效。
? 算法必须适用于各种应用。
? 用以实现算法的电子器件必须很经济。
? 算法必须能有效使用。
? 算法必须能验证。
? 算法必须能出口。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES背景 (3/5)
1974年 8月 27日
美国国家标准局( NBS)第二次发布征集标准密码
算法公告。
IBM提交了算法 LUCIFER,该算法由 IBM的工程师在
1970年初开发的一个算法基础上,于 1971~ 1972年
研制成功。
1975年 3月 17日
NBS公布该算法细节。
1976年
NBS成立专题小组评估提出的整个标准。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES背景 (4/5)
1976年 11月 23日
采纳 IBM公司的设计方案 为联邦标准,并授权在非密
级的政府通信中使用。
1977年 1月 15日
FIPS PUB 46( DES标准的正式文本)公布,并在六
个月后生效。
1980年
FIPS PUB 81( DES工作方式)公布。
1981年
公布 FIPS PUB 74(实现和使用 DES的指南)
DES算法是第一个公布的 NSA(美国国家安全局)执
行算法。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES背景 (5/5)
2,DES的采用
1979年,美国银行协会批准使用
1980年,美国国家标准局( ANSI)赞同 DES作为私
人使用的标准,称之为 DEA( ANSI X.392)
1983年,国际化标准组织 ISO赞同 DES作为国际标准,
称之为 DEA-1
该标准规定每五年审查一次,计划十年后采用新标

最近的一次评估是在 1994年 1月,已决定 1998年 12
月以后,DES将不再作为联邦加密标准。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (1/26)
?
D
E
S



DES使用 56位密钥对 64位
数据块进行加密,需要
进行 16轮编码。
第 2章




上一页
下一页
目录
结束
10:22 DES算法框图
对称密码体制
DES
DES算法描述 (2/26)
? DES描述
输入 64比特明文数据
在密钥控制下
16轮迭代
初始置换 IP
交换左右 32比特
初始逆置换 IP-1
输出 64比特密文数据
DES对 64位的明文分组进行
操作。通过一个初始置换,
将明文分组分成左半部分和
右半部分,各 32位长。然后
进行 16轮完全相同的运算,
这些运算被称为函数 f,在运
算过程中数据与密钥结合。
经过 16轮后,左、右半部分
合在一起,经过一个末置换
(初始置换的逆置换),这
样该算法就完成了。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (3/26)
? DES算法特点
1) 分组加密算法,
以 64位为分组。 64位一组的明文从算法一端输入,
64位密文从另一端输出。
2) 对称算法,
加密和解密用同一密钥。
3) 有效密钥长度为 56位。
密钥通常表示为 64位数,但每个第 8位用作奇偶校
验,可以忽略。
第 2章




上一页
下一页
目录
结束
10:22
4) 代替和置换
DES算法是两种加密技术的组合:混乱和扩散。先代
替后置换。
5) 易于实现
DES算法只是使用了标准的算术和逻辑运算,其作用
的数最多也只有 64位,因此用 70年代末期的硬件技
术很容易实现。
算法的重复特性使得它可以非常理想地用在一个专
用芯片中。
对称密码体制
DES
DES算法描述 (4/26)
第 2章




上一页
下一页
目录
结束
10:22
? DES算法的总体过程
输入 64位明文数据,并
进行 初始置换 IP;
在初始置换 IP后,明文
组再被 分 为左右两部分,
每部分 32位,以 L0,R0
表示。
在密钥的控制下,经过
16轮运算 (?);
16轮后,左、右两部分
交换,并连接在一起;
经过 末置换 (初始置换
的逆置换);
输出 64位密文。
初始置换 IP
+ ? k
1
+ ? k
2
+ k16 ?
IP-1
L0 R0
L1=R0 R1=L0 ??(RO,K1)
L2=R1 R2=L1 ??(R1,K2)
L15=R14 R15=L14 ??(R14,K15)
R16=L15 ??(R15,K16) L16=R15
64位明文
64位密文
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (6/26)
? 初始置换与未置换
初始置换 IP (initial permutation)在第一轮运算
之前进行。未置换 IP-1(初始置换的逆置换 )在第十
六轮运算之后进行。
初始置换 IP 初始逆置换 IP-1
58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32
60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31
62 54 46 38 30 22 14 6 38 6 46 14 54 22 62 30
64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29
57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28
59 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27
61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26
63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (7/26)
初始置换和对应的末置换并不影响 DES的安全性。
其主要目的是为了更容易地将明文和密文数据以字
节大小放入 DES芯片中。
由于这种位方式的置换用软件实现很困难,很多
DES的软件实现方式删去了初始置换和末置换。这
些新的算法安全性不比 DES差,但并未遵循 DES标准,
故而不应叫做 DES。
将该表应从左向右,从上向下读。
例如,初始置换将明文的第 58位换到 第 1位
第 50位换到 第 2位
第 42位换到 第 3位
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (8/26)
? 迭代过程
经过初始置换后,进行 16轮完全相同的运算。这些
运算被称为 ?,在运算过程中数据与密钥结合。
+ ? k
1
L0 R0
L1=R0 R1=L0 ??(RO,K1)
函数 ?的输出经过一个异或运算,和左半部分结合,
其结果成为新的右半部分,原来的右半部分成为新
的左半部分。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (9/26)
假设 Li和 Ri是第 i次
迭代结果的左半部
分和右半部分,Ki
是第 i轮的 48位密
钥,则 每一轮迭代
过程可以表示为,
Li-1(32bit) Ri-1(32bit)
扩展置换 E
S盒代替
P-盒置换
Ri(32bit) Li(32bit)
? Ki 48bit
?
Ri=Li-1 ??(Ri-1,Ki-1) Li=Ri-1
32位
48位
48位
32位
32位
32位
? ?函数
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (10/26)
? ?函数
函数 ?由四步运算构成,
1) 密钥置换
2) 扩展置换
3) S-盒代替
4) P-盒置换
1) 密钥置换
DES算法由 64位密钥产生 16轮的 48位子密钥。
在每一轮运算过程中,使用不同的子密钥。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (11/26)
64位密钥
置换选择 1
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
置换选择 2
循环左移 循环左移
Ci(28位 ) Di (28位 )
置换选择 2
56位
k1
48位
ki
48位 56位
压缩置换。将 56
位输入置换为 48
位。
不考虑每字节的
第 8位,将 64位
密钥减至 56位。
然后进行一次密
钥置换。
各轮循环移动的次
数由轮数决定。
每一轮子密钥
生成过程可以
表示为,
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (12/26)
由于不考虑每个字节的第 8位,DES
的密钥由 64位减至 56位。每个字节
的第 8位可作为奇偶校验以确保密钥
不发生错误。
然后进行置换选择 1,如下表所示。
64位密钥
置换选择 1
置换选择 1表
57,49,41,33,25,17,9,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,7,62,54,46,38,30,22,
14,6,61,53,45,37,29,21,13,5,28,20,12,4
第 2章




上一页
下一页
目录
结束
10:22
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
64位密钥
置换选择 1
对称密码体制
DES
DES算法描述 (13/26)
经过置换选择 1,将输出的
56位密钥分成两部分,每
部分 28位。
然后,根据轮数,将两部
分分别循环左移 1位或 2位。
如下表所示。
每轮移动的位数表
轮 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (14/26)
64位密钥
置换选择 1
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
置换选择 2
56位
k1
48位
移动后,从 56位输出中选
出 48位。由于该运算不仅
置换了每位的顺序,同时
也选择了密钥,因而被称
为 压缩置换 。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (15/26)
压缩置换表(置换选择 2)
14,17,11,24,1,5,3,28,15,6,21,10,
23,19,12,4,26,8,16,7,27,20,13,2,
41,52,31,37,47,55,30,40,51,45,33,48,
44,49,39,56,34,53,46,42,50,36,29,32
例如,处在第 33位的那一位在输出时移到了第 35位,
而处在第 18位的那一位被省略了。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (16/26)
在每一轮子密钥
生成运算中有移
动运算,因此在
每个子密钥中使
用了不同的密钥
子集的位。
64位密钥
置换选择 1
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
置换选择 2
循环左移 循环左移
Ci(28位 ) Di (28位 )
置换选择 2
56位
k1
48位
ki
48位 56位
自此,完成一轮
子密钥生成。
第 2章




上一页
下一页
目录
结束
10:22
2) 扩展置换 E
通过扩展置换 E,数据的
右半部分 Ri从 32位扩展到
48位。扩展置换改变了位
的次序,重复了某些位。
扩展置换有两方面的目的,
? 产生与密钥同长度的
数据以进行异或运算;
? 提供更长的结果,使
得在替代运算时能够进行
压缩。
对称密码体制
DES
DES算法描述 (17/26) Li-1(32bit) Ri-1(32bit)
扩展置换 E
S盒代替
P-盒置换
Ri(32bit) Li(32bit)
? Ki 48bit
?
Ri=Li-1 ??(Ri-1,Ki-1) Li=Ri-1
32位
48位
48位
32位
32位
32位
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (18/26)
在密码学上,由于
扩展置换中输入的
一位将影响两个替
换,所以输出对输
入的依赖性将传播
得更快。这叫 雪崩
效应 。
DES的设计着重于尽
可能快地使得密文
的每一位依赖于明
文和密钥的每一位。
在扩展置换中,尽管输出分组大于输入分组,但每
个输入分组产生唯一的输出分组。
32 | 01 02 03 04 | 05
04 | 05 06 07 08 | 09
08 | 09 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 | 01
扩展置换 E
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (19/26)
3) S盒代替
压缩后的密钥与扩展
分组异或以后,将 48
位的结果送入,进行
代替运算。
Li-1(32bit) Ri-1(32bit)
扩展置换 E
S盒代替
P-盒置换
Ri(32bit) Li(32bit)
? Ki 48bit
?
Ri=Li-1 ??(Ri-1,Ki-1) Li=Ri-1
32位
48位
48位
32位
32位
32位
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (20/26) S-盒代替
48-位输入
32-位输出
S-盒 1 S-盒 2 S-盒 3 S-盒 4 S-盒 5 S-盒 6 S-盒 7 S-盒 8
代替运算由 8个不同的代替盒( S盒)完成。每个 S盒有 6
位输入,4位输出。
48位的 输入被分为 8个 6位的分组,每一分组对应一个 S-
盒代替操作。
经过 S盒代替,形成 8个 4位分组 。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (21/26)
每个 S盒是一个 4行,16列的表。例如,
S-盒 6
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13
盒中的每一项都是一个 4位的数。 S-盒的 6个位输入
确定了其输出在哪一行哪一列。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (22/26)
输入位以一种非常特殊的方式确定了 S-盒中的项。
假定将 S-盒的 6位输入标记为 b1,b2,b3,b4,
b5,b6,则
1) b1和 b6组合构成了一个 2位的数,从 0到 3,它
对应着表中的一行。
2)从 b2到 b5构成了一个 4位的数,从 0到 15,对应
着表中的一列。
3)行列交叉处的数就是 S-盒的输出。
第 2章




上一页
下一页
目录
结束
10:22
例如,假设 S-盒 6的输入 (即异或函数的第 31位到 36位 )
为 110011。
第 1位和最后一位组合形成了 11,它对应着 S-盒 6的第 3
行。
中间的 4位组合形成了 1001,它对应着 S-盒 6的第 9列。
S-盒 6的第 3行第 9列处的数是 14,得到输出值为 1110。
S-盒 6
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13
对称密码体制
DES
DES算法描述 (23/26)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (24/26)
在 DES算法中,S-盒是
关键步骤。
S-盒是非线性的,所有
其他运算都是线性的,
它比 DES的任何其它一
步都提供了更好的安全
性。
Li-1(32bit) Ri-1(32bit)
扩展置换 E
S盒代替
P-盒置换
Ri(32bit) Li(32bit)
? Ki 48bit
?
Ri=Li-1 ??(Ri-1,Ki-1) Li=Ri-1
32位
48位
48位
32位
32位
32位
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (25/26)
Li-1(32bit) Ri-1(32bit)
扩展置换 E
S盒代替
P-盒置换
Ri(32bit) Li(32bit)
? Ki 48bit
?
Ri=Li-1 ??(Ri-1,Ki-1) Li=Ri-1
32位
48位
48位
32位
32位
32位
3) P盒置换
S-盒代替运算后的 32位输
出依照 P盒进行置换。
P盒置换将每一输入位映
射到输出位。任一位不能
被映射两次,也不能被略
去。
经过 P-盒置换的结果与最
初 64位分组的左半部分异
或,然后左右两部分交换,
开始下一轮迭代。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES算法描述 (26/26)
P-盒置换表
16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,
2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25
例如,第 21位移到了第 4位,第 4位移到了第 31位。
第 2章




上一页
下一页
目录
结束
10:22
初始置换 IP
+ ? k
1
+ ? k
2
+ k16 ?
IP-1
L0 R0
L1=R0 R1=L0 ??(RO,K1)
L2=R1 R2=L1 ??(R1,K2)
L15=R14 R15=L14 ??(R14,K15)
R16=L15 ??(R15,K16) L16=R15
64位明文
64位密文
DES算法大致可以分为 3
个部分,
? 初始置换
? 迭代过程
? 逆置换
迭代过程,
? 密钥置换
? 扩展置换
? S-盒代替
? P-盒置换
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES解密( 1/2)
在经过所有的代替, 置换, 异或和循环移动之
后, 获得了这样一个非常有用的性质:加密和解密
可使用相同的算法 。
DES使得用相同的函数来加密或解密每个分组成
为可能, 二者的唯一不同之处是密钥的次序相反 。
这就是说, 如果各轮的加密密钥分别是 K1,K2,
K3…, K16那么解密密钥就是 K16,K15,K14……,
K1。 为各轮产生密钥的算法也是循环的 。 密钥向右
移动, 每次移动个数为 0,1,2,2,2,2,2,2,1,
2,2,2,2,2,2,1。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES解密 (2/2)
简单地说,
- DES的解密和加密使用相同的算法。
- 解密过程中使用的子密钥顺序与加密过程中使用的
密钥顺序相反。
即:如果各轮的加密密钥是 K1,K2,K3,…,K16,
那么解密密钥就是 K16,K15,K14,…,K1。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
第 2章




上一页
下一页
目录
结束
10:22
DES可以使用硬件和软件方法得以高速实现。
1) DES芯片
目前为止,速度最快的 DES芯片能够在 1秒内
加密 16 800 000个数据分组。
2) DES软件实现
在 IBM 3090大型计算机上,使用软件实现方
法,每秒能够完成 32 000次加密。
对称密码体制
DES
DES的实现 (1/5)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
举例,
已知明文 m=computer,密钥 k=program,用 ASCII
码表示为,
m=01100011 01101111 01101101 01110000
01110101 01110100 01100101 01110010
k=01110000 01110010 01101111 01100111
01110010 01100001 01101101
因为 k只有 56位,必须插入第 8,16,24,32,
40,48,56,64位奇偶校验位,合成 64位。而这 8
位对加密过程没有影响。
DES的实现 (2/5)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
m经过 IP置换后得到
L0= 11111111 10111000 01110110 01010111
R0= 00000000 11111111 00000110 10000011
密钥 k通过 PC-1得到
C0= 11101100 10011001 00011011 1011
D0= 10110100 01011000 10001110 0110
再各自左移一位,通过 PC-2得到 48位
k1=00111101 10001111 11001101 00110111 00111111
00000110
R0( 32位)经 E作用膨胀为 48位,
10000000 00010111 11111110 10000000 11010100
00000110
DES的实现 (3/5)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
再和 k1作异或运算得到 ( 分成 8组 )
101111 011001 100000 110011 101101 111110
101101 001110
通过 S盒后输出位 32比特,
01110110 00110100 00100110 10100001
S盒的输出又经过 P置换得到
01000100 00100000 10011110 10011111
这时,
所以, 第一趟的结果是,00000000 11111111
00000110 10000011 10111011 10011000 11101000
11001000
DES的实现 (4/5)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
如此,迭代 16次以后,得到密文,
01011000 10101000 01000001 10111000
01101001 11111110 10101110 00110011
明文或密钥每改变一位,都会对结果密文产生剧
烈的影响。任意改变一位,其结果大致有将近一
半的位发生了变化。
DES的实现 (5/5)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES问题的讨论 (1/5)
DES是密码学史上的一个创举。以往任何密码算
法的密码体制和设计细节都是严加保密的,而
DES算法的安全性不再依赖于算法细节的保密。
S-Box是 DES的安全核心。因为在 DES算法中,除
了 S-Box外,所有计算都是线性的。
1,S-Box问题
S盒的设计准则并没有完全得到规范。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES问题的讨论 (2/5)
1976年美国 NSA提出了下列几条 S盒的设计准则,
1) S盒的每一行是整数 0,…, 15的一个置换 ;
2) 没有一个 S盒是它输入变量的线性函数
3) 改变 S盒的一个输入位至少要引起两位的输出改
4) 对任何一个 S盒 Si和任何一个输入 X,Si( X)和
Si(X?001100)至少有两个比特不同(这里 X是长
度为 6的比特串 );
5) 对任何一个 S盒和任何一个比特对 (e,f),都存在,
Si(X) ≠S i(X?11ef00)
6) 对任何一个 S盒 Si,如果固定一个输入比特,来
看一个固定输出比特的值,这个输出比特为 0的输
入数目将接近于这个输出比特为 1的输入数目。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES问题的讨论 (3/5)
2.密钥长度
目前,只有穷举搜索攻击是最好的破译 DES的算法。
关于 DES算法的另一个最有争议的问题就是担心实际
56比特的密钥长度不足以抵御穷举式攻击,因为密
钥量只有 256≈10 17个。
早在 1977年,Diffie和 Hellman已建议制造一个每秒
能测试 100万个密钥的 VLSI芯片。每秒测试 100万个
密钥的机器大约需要一天就可以搜索整个密钥空间。
他们估计制造这样的机器大约需要 2000万美元。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES问题的讨论 (4/5)
在 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万美元。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES问题的讨论 (5/5)
1998年 7月电子前沿基金会 (EFF)使用一台 25万美圆
的电脑在 56小时内破译了 56比特密钥的 DES。
1999年 1月 RSA数据安全会议期间,电子前沿基金会
用 22小时 15分钟就宣告破解了一个 DES的密钥。
3.DES的 破译
利用差分密码分析和线性密码分析都可对 DES进行
选择明文攻击。
线性密码分析比差分密码分析更有效。
4.弱密钥与半弱密钥
?弱密钥, EK?EK = I,DES存在 4个弱密钥
?半弱密钥, EK1 = EK2,至少有 12个半弱密钥
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
DES背景
DES算法描述
DES解密
DES问题的讨论
DES的实现
DES的发展
AES
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES的发展 (1/5)
由于 56位密钥的 DES已经不够安全,因此,1998年
12月以后,56位密钥的 DES已经不再作为联邦加密
标准。为了使已有的 DES算法投资不浪费,人们尝
试用 DES和多个密钥进行多次加密。
1,双重 DES(Double DES)
C = EK2(EK1(P)) ? P = DK1(DK2(C))
E E P x C
K1 K2
D D C x P
K1 K2
加密
解密
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES的发展 (2/5)
双重 DES的讨论
? 假设对于 DES和所有 56比特密钥,给定任意两个密钥
K1和 K2,都能找到一个密钥 K3使得 EK2(EK1(P)) = EK3
(P) 。如果这个假设是事实,则 DES的两重加密或者多
重加密都将等价于用一个 56比特密钥的一次加密。
? 直观上看, 上面的假设不可能为真 。 因为 DES的加密事
实上就是从一个 64比特分组到另一个 64分组的置换,
而 64比特分组共有 264可能的状态, 因而可能的置换个
数为,264!>10347380 000 000 000 000 000>103·1020
? 另一方面,DES的每个密钥确定了一个置换,因而总
的置换个数为, 256<1017。
? 1992年有人证明了这个结果 ——上述假设不成立 。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES的发展 (3/5)
2.中途攻击
C = EK2(EK1(P)) ? X = EK1(P) = DK2(C)
? 给定明文密文对 (P,C)
1) 对所有 256个密钥,加密 P,对结果排序
2) 对所有 256个密钥,解密 C,对结果排序
3) 逐个比较,找出 K1,K2使得 EK1(P) = DK2(C)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES的发展 (4/5)
? 已知,给定一个明文 P,经二重 DES加密有 264个
可能的密文。而二重 DES所用密钥的长度应是 112
bits,所以选择密钥有 2112个可能性。于是对给
定一个明文 P加密成密文有 2112/264=248种可能。
给定两个明密文对,虚警率降为 248-64=2-16。换句
话说,对已知 2个明文 -密文对的中间相遇攻击成
功的概率为 1-2-16。
? 攻击用的代价 (加密或解密所用运算次数 )≦2 56
? 需要大量的存储器, 256 ? 64=1017字节
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
DES的发展 (5/5)
3.三重 DES
加密
解密
D E P A B
K1 K2
E C
K3
C=EK1(DK2(EK1(P)))
E D C A B
K1 K2
D P
K3
P=DK1(EK2( DK1(C)))
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
AES简介
AES算法结构
AES的背景
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES的背景 (1/4)
? 1997年 4月 15日, 美国国家标准技术研究所 (NIST)
发起征集高级加密标准 (Advanced Encryption
Standard)AES的活动, 活动目的是确定一个非保
密的, 可以公开技术细节的, 全球免费使用的分
组密码算法, 作为新的数据加密标准 。
? 1997年 9月 12日, 美国联邦登记处公布了正式征集
AES候选算法的通告 。 作为进入 AES候选过程的一
个条件, 开发者承诺放弃被选中算法的知识产权 。
对 AES的基本要求是:比三重 DES快, 至少与三重
DES一样安全, 数据分组长度为 128比特, 密钥长
度为 128/192/256比特 。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES的背景 (2/4)
? 1998年 8月 12日, 在首届 AES会议上指定了 15个候选
算法 。
? 1999年 3月 22日第二次 AES会议上, 将候选名单减少
为 5个, 这 5个算法是 RC6,Rijndael,SERPENT,
Twofish和 MARS。
? 2000年 4月 13日, 第三次 AES会议上, 对这 5个候选
算法的各种分析结果进行了讨论 。
? 2000年 10月 2日, NIST宣布了获胜者 ——Rijndael
算法, 2001年 11月出版了最终标准 FIPS PUB197。
第 2章




上一页
下一页
目录
结束
10:22
为 AES开发 Rijndael算法的是两位来自比利时的密码
专家,Proton World International的 Joan daemen
博士,Katholieke Universiteit Leuven电子工程
系 (ESAT)的 Vincent Rijmen 博士后。两位先生在加
密领域里一直比较活跃。
NIST主任 Ray Kammer 在马里兰召开的新闻发布会上
说,之所以选中 Rijndael,是因为它很快而且所需的
内存不多。这个算法是如此可靠,就连在密码方面最
内行的美国国家安全局也决定将用它来保护一些关键
数据不被窥视。
对称密码体制
AES
AES的背景 (3/4)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES的背景 (4/4)
Rijndael也是 5个上了决赛名单中唯一一个不面临
潜在的日立公司侵犯专利诉讼的算法。
日立在 2001年早些时候宣布了对一系列密码采用的
数学技术的所有权,但 Kammer说法律问题不是决定
算法选择的因素。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
AES简介
AES算法结构
AES的背景
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES简介 (1/3)
? Rijndael算法的原形是 Square算法。
? 它的设计策略是宽轨迹策略 WideTrail Strategy,
这种策略是针对差分分析和线性分析提出来的。是
一个分组迭代密码,具有可变的分组长度和密钥长
度。
? AES被设计成三个密钥长度 128/192/256比特,用
于加密长度为 128/32=Nb比特的分组,相应的轮数为
10/12/14。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES简介 (2/3)
Key Length
(NK words)
Block Size
(Nb words)
Number of
Rounds
(Nr)
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14
AES参数
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES简介 (3/3)
? Rijndael汇聚了安全、性能、效率、可实现性和
灵活性等优点,尤其是在无论有无反馈模式的计算
环境下的软硬件中,Rijndael都显示出其非常好的
性能。
? Rijndael的对内存的需求非常低,也使它很适合
用于受限制的环境中。
? Rijndael的操作简单,并可抵御强大和实时的攻
击。
? 此外它还有许多未被特别强调的防御性能。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
AES简介
AES算法结构
AES的背景
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES算法结构 (1/3)
1,AES算法特点
? 不属于 Feistel结构
? 加密、解密相似但不对称
? 支持 128/32=Nb数据块大小
? 支持 128/192/256(/32=Nk)密钥长度
? 有较好的数学理论作为基础
? 结构简单、速度快
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES算法结构 (2/3)
2.AES算法的轮变换
? AES算法的轮变换中没有 Feistel结构,轮变
换是由四个不同的可逆一致变换组成,称之
为层,
1)线性混合层:行移位 SR和列混合 MC
2)非线性层:字节代替 BS
3)密钥加层:轮密钥简单地异或到中间状态
上。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
AES
AES算法结构 (3/3)
明文 P
⊕ 子密钥 K0
r轮选代
密文 C
AES算法框图
Xi-1
字节代替 BS
行移位 SR
列混合 MC
Xi
Ki-1 ⊕
一轮 AES结构
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
密码反馈模式 (CFB)
电码本模式 (ECB)
密码分组链接模式 (CBC)
输出反馈模式 (OFB)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
电码本模式 (1/2)
ECB (electronic codebook mode)
加密
P1
C1
K 加密
P2
C2
K 加密
Pn
Cn
K …
解密
C1
P1
K 解密
C2
P2
K 解密
Cn
Pn
K …
Ci = EK(Pi) ? Pi = DK(Ci)
第 2章




上一页
下一页
目录
结束
10:22
ECB特点,
? 简单和有效
? 可以并行实现
? 不能隐藏明文的模式信息
? 相同明文 ?相同密文
? 同样信息多次出现造成泄漏
? 对明文的主动攻击是可能的
? 信息块可被替换、重排、删除、重放
? 误差传递:密文块损坏 ?仅 对应明文块损坏
? 适合于传输短信息
对称密码体制
分组密码的工作模式
电码本模式 (2/2)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
密码反馈模式 (CFB)
电码本模式 (ECB)
密码分组链接模式 (CBC)
输出反馈模式 (OFB)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码分组链接模式 (1/3)
CBC (cipher block chaining)
加密
P1
C1
K 加密
P2
C2
K 加密
Pn
Cn
K …
+
V1
+ + Cn-1
解密
C1
P1
K 解密
C2
P2
K 解密
Cn
Pn
K …
+ + + V1 Cn-1
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码分组链接模式 (2/3)
加密,
C1 = EK(V1?P1)
Ci = EK(Ci-1?Pi)
解密,
P1 = DK(C1 )?V1
= DK(EK(V1?P1))?V1 = V1?P1?V1 = P1
Pi = DK(Ci )? Ci-1
= DK(EK(Ci-1?Pi))? Ci-1 = Ci-1?Pi? Ci-1
= Pi
可见 V1和 K一样,都是收、发双方都应已知的。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码分组链接模式 (3/3)
CBC特点
?没有已知的并行实现算法
?能隐藏明文的模式信息
?需要共同的初始化向量 V1
?相同明文 ?不同密文
?初始化向量 V1可以用来改变第一块
?对明文的主动攻击是不容易的
?信息块不容易被替换、重排、删除、重放
?误差传递:密文块损坏 ?两 明文 块 损坏
?安全性好于 ECB
?适合于传输长度大于 64位的报文,还可以进行用
户鉴别,是大多系统的标准如 SSL,IPSec
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
密码反馈模式 (CFB)
电码本模式 (ECB)
密码分组链接模式 (CBC)
输出反馈模式 (OFB)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (1/6)
CFB (cipher feedback)
CFB模式的原理, 分组密码 ?流密码
Si 为移位寄存器 (通常为 64比特 );
j 为流单元宽度 (通常为 8比特 );
Pi 和 Ci 一样长,均为 j比特;
加密, Ci =Pi?(EK(Si)的高 j位 )
Si+1=(Si<<j)|Ci
解密, Pi=Ci?(EK(Si)的高 j位 )
Si+1=(Si<<j)|Ci
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (2/6)
加密,Ci =Pi?(EK(Si)的高 j位 ) Si+1=(Si<<j)|Ci
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P1
C1
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P2
C2
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
Pn
Cn
K
64
64
j j
j
……
Cn-1 V1
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (3/6)
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P1
C1
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P2
C2
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
Pn
Cn
K
64
64
j j
j
……
Cn-1 V1
解密, Pi=Ci?(EK(Si)的高 j位 )
Si+1=(Si<<j)|Ci
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (4/6)
在这种模式中,
加密时,
加密算法的输入是 64bit的移位寄存器的内容
Si,其初始值是某个初始向量 V1;
加密算法输出的最左边 j bit,即 EK(Si)的高 j
位与明文的第 i个单元 Pi异或,产生密文 Ci,即,
Ci =Pi?(EK(Si)的高 j位 )
移位寄存器的内容左移 j位,并将 Ci送入寄存
器的最右边,即 Si+1=(Si<<j)|Ci。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (5/6)
解密时,
仍然采用与加密时的 加密 方法,即:加密算法
的输入仍是 64bit的移位寄存器的内容 Si,其初始
值即为加密时的初始向量 V1;
对于第 i位,移位寄存器的内容左移 j位,并将
Ci送入寄存器的最右边,即 Si+1=(Si<<j)|Ci;
以上算法都与加密时采用的算法一样,只是在
解密时,加密算法输出的最左边 j bit,即 EK(Si)的
高 j位与收到 密文 的第 i个单元 Ci异或,产生明文 Pi,
即,Pi=Ci?(EK(Si)的高 j位 )。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
密码反馈模式 (6/6)
Pi=Ci?(EK(Si)的高 j位 )
因为,Ci=Pi?(EK(Si)的高 j位 )
则,Pi=Pi?(EK(Si)的高 j位 ) ?(EK(Si)的高 j位 )
=Pi? 0 = Pi
CFB的特点,
?分组密码 ?流密码
?没有已知的并行实现算法
?隐藏了明文模式
?需要共同的移位寄存器初始值 V1
?对于不同的消息,V1必须唯一
?误差传递:一个单元损坏影响多个单元
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
DES
分组密码原理
对称密码体制概述
分组密码的工作模式
AES
密码反馈模式 (CFB)
电码本模式 (ECB)
密码分组链接模式 (CBC)
输出反馈模式 (OFB)
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
输出反馈模式 (1/4)
OFB (output feedback)
OFB模式原理,分组密码 ?流密码
Si 为移位寄存器,j为流单元宽度
加密, Ci =Pi?(EK(Si)的高 j位 )
Si+1=(Si<<j)|(EK(Si)的高 j位 )
解密, Pi=Ci?(EK(Si)的高 j位 )
Si+1=(Si<<j)|(EK(Si)的高 j位 )
从上面可以看出,OFB模式与 CFB在结构上类同,不
同的是 OFB模式将加密算法的输出反馈到移位寄存器;
而 CFB模式是将密文单元反馈到寄存器。
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
输出反馈模式 (2/4)
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P1
C1
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P2
C2
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
Pn
Cn
K
64
64
j j
j
……
On-1 V1
Ci =Pi?(EK(Si)的高 j位 );Si+1=(Si<<j)|(EK(Si)的高 j位 )
加密
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
输出反馈模式 (3/4)
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P1
C1
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
P2
C2
K
64
64
j j
j
Shift register
|j bit
64-j bit
Encrypt
Select
j bit
Discard
64-j bit
Pn
Cn
K
64
64
j j
j
……
On-1 V1
Pi=Ci?(EK(Si)的高 j位 ); Si+1=(Si<<j)|(EK(Si)的高 j位 )
解密
第 2章




上一页
下一页
目录
结束
10:22
对称密码体制
分组密码的工作模式
输出反馈模式 (4/4)
OFB的特点,
? 分组密码 ?流密码
? 没有已知的并行实现算法
? 隐藏了明文模式
? 需要共同的移位寄存器初始值 V1
? 误差传递:一个单元损坏只影响对应单元
? 对明文的主动攻击是可能的
? 信息块可被替换、重排、删除、重放
? 安全性较 CFB差
2011年 10月 17日星期一
导 论
认证技术
网络安全
系统安全
安全管理
安全协议
加密技术
密钥管理
密码学概述
对称密码体制
公钥密码体制
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
公钥密码体制的产生
公钥密码体制工作原理
公钥密码基于的数学难题
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制的产生 (1/4)
1.问题的提出
(1) 密钥管理量的困难
传统密钥管理:两两分别用一对密钥时,则 n个用户
需要 C(n,2)=n(n-1)/2个密钥,当用户量增大时,密
钥空间急剧增大。如,
n=100 时,C(100,2)=4,995
n=5000时,C(5000,2)=12,497,500
(2) 数字签名的问题
传统加密算法无法实现抗抵赖的需求。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制的产生 (2/4)
(3) 密钥分配和传输
? 保密通信双方需共享密钥
? 共享密钥要经常更换
? A选择密钥并手工传递给 B
? 第三方 C选择密钥分别手工传递给 A,B
? 用 A,B原有共享密钥传送新密钥
? 与 A,B分别有共享密钥的第三方 C传送新密钥给 A
和 /或 B
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制的产生 (3/4)
? 通过密钥分发中心 (Key Distribution Center)
? 每个用户与 KDC有共享密钥 (Master Key)
? N个用户,KDC需分发 N个 Master Key
? 两个用户间通信用会话密钥 (Session Key)
? 用户必须信任 KDC
? KDC能解密用户间通信的内容
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制的产生 (4/4)
2,公钥密码的起源
公钥密码又称为双钥密码和非对称密码,是 1976
年由 Diffie和 Hellman在其, 密码学新方向, 一
文中提出的。
公钥算法的代表 RSA公钥算法是由 Rivest,Shamir
和 Adleman在 1978年提出来的。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
公钥密码体制的产生
公钥密码体制工作原理
公钥密码基于的数学难题
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (1/9)
1,什么是公钥密码体制
公钥密码又称为双钥密码和非对称密码 。公钥密码
体制加密的算法是基于单向陷门函数。
2,单向陷门函数
单向陷门函数 是满足下列条件的函数 f
(1)给定 x 计算 y=f(x)是容易的
(2)给定 y,计算 x使 y=f-1(x)是困难的
(所谓计算 x=f-1(y)困难是指计算上相当复杂,已无
实际意义 )
(3)存在 ?,已知 ? 时,对给定 ? 的任何 y,若相应
的 x存在,则计算 x使 y=f(x)是容易的。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (2/9)
? 仅满足 (1) (2)两条的称为单向函数;第 (3)条称
为陷门性,? 称为陷门信息。
? 当用陷门函数 f作为加密函数时,可将 f公开,这
相当于公开加密密钥。此时加密密钥便称为公开钥
记为 Pk。 f函数的设计者将 ?保密,用作解密密钥,
此时 ?称为秘密钥匙,记为 Sk。由于加密函数是公开
的,任何人都可以将信息 x加密成 y=f(x),然后送
给函数的设计者 (当然可以通过不安全信道传送 );
由于设计者拥有 Sk他自然可以解出 x=f-1(y)。
? 单向陷门函数的第 (2)条性质表明窃听者由截获
的密文 y=f(x)推测 x是不可行的。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (3/9)
3,公开密钥密码的重要特性
? 加密与解密由不同的密钥完成
加密, X?Y,Y = EKU(X)
解密, Y?X,X = DKR(Y) = DKR(EKU(X))
? 知道加密算法,从加密密钥得到解密密钥在计算
上是不可行的
? 两个密钥中任何一个都可以用作加密而另一个用
作解密 (不是必须的 )
X = DKR(EKU(X)) = EKU(DKR(X))
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (4/9)
4,基于公开密钥的加密过程
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (5/9)
5,基于公开密钥的鉴别过程
第 2章




上一页
下一页
目录
结束
10:22
6,用公钥密码实现保密
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (6/9)
? 用户拥有自己的密钥对 (KU,KR)
? 公钥 KP公开,私钥 KS保密
? A?B,Y=EKPb(X)
? B,DKSb(Y)= DKSb(EKPb(X))=X
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (7/9)
7,用公钥密码实现鉴别
? 条件, 两个密钥中任何一个都可以用作加密
而另一个用作解密。
? 鉴别,
A?ALL,Y=DKSa(X)
ALL,EKPa(Y)=EKPa(DKSa(X))=X
? 鉴别 +保密,
A?B,Z= EKPb(DKSa(X))
B,EKPa(DKSb(Z))=X
第 2章




上一页
下一页
目录
结束
10:22
8,公钥密钥的应用范围
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (8/9)
? 加密 /解密
? 数字签名 (身份鉴别 )
? 密钥交换
算法 加 /解密 数字签名 密钥交换
RSA 是 是 是
Dieffie-Hellman 否 否 是
DSS 否 是 否
第 2章




上一页
下一页
目录
结束
10:22
9,基本思想和要求
公钥密码体制
公钥密码体制的基本原理
公钥密码体制工作原理 (9/9)
涉及到各方:发送方、接收方、攻击者
涉及到数据:公钥、私钥、明文、密文
公钥算法的条件,
? 产生一对密钥是计算可行的
? 已知公钥和明文,产生密文是计算可行的
? 接收方利用私钥来解密密文是计算可行的
? 对于攻击者,利用公钥来推断私钥是计算不可行的
? 已知公钥和密文,恢复明文是计算不可行的
? (可选 )加密和解密的顺序可交换
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
公钥密码体制的产生
公钥密码体制工作原理
公钥密码基于的数学难题
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (1/10)
? 背包问题
( Merkle-Hellman,MH背包公钥密码 )
? 大整数分解问题
( The Integer Factorization
Problem,RSA体制 )
? 有限域的乘法群上的离散对数问题
( The Discrete Logarithm Problem,
ElGamal体制 )
? 椭圆曲线上的离散对数问题
( The Elliptic Curve Discrete
Logarithm Problem,类比的 ElGamal体制 )
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (2/10)
? 背包问题
背包问题描述:已知一长度为 b 的背包及长度分别
为 a1,a2,… an的 n个物品。假定这些物品的直径与背
包相同,若从这些物品中选出若干个正好装满这个
背包,那么,究竟是那些物品?
把背包问题抽象成数学模型,称为子集合问题:设
有长度为 n的向量 A =( a1,a2,…, an),任意给定
一个正数 b,寻找有没有一些 ai的和恰好等于 b,
n
即求解, Σ aixi=b
i=1
的解向量 x=(x1,x2,…,xn),其中 xi=0或 1;
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (3/10)
? 背包问题(续 1)
背包问题是著名的 NP—完全问题。
P问题:可解的问题;
NP问题:可验证的问题;
NP—完全问题:是 NP问题中最难解决的问题
目前,已经列出的 NP—完全问题大约有 300多个。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (4/10)
? 背包问题(续 2)
之所以说背包问题是 NP—完全问题,是因为背包问
题导致求一个 Xi向量,
x=(x1,x2,…,xn),其中 xi=0或 1
当背包向量的长度 n 比较小时,可以用穷举搜索法
求得解向量。但当 n比较大时,比如说 100,那么穷
举搜索法就不可能了。因为它要对 2n种所有的可能
进行穷举搜索。 2100=1.27× 1030,以每秒搜索 107种
方案的计算机进行穷举,需要 4× 1015年。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (5/10)
? 整数分解问题 ——NP完全问题
任何整数都可以分解成标准形式,
n
m = ? Pi ei,Pi是素数,ei∈N
i=1
当 m较小时,这个问题不太困难,例如,
6=2× 3 100=22× 52
但当 m较大时,此问题就变的非常困难了。例如,
8 616 460 789 = 89 681 × 96079
特别是当 m达到几百位时,根据现有的算法用最快
的计算机也不行。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (6/10)
? 整数分解问题 ——数论基础
Fermat定理, p素数,a是整数且不能被 p整除,则,
ap-1 ? 1 mod p
推论, p素数,a是任意整数,则, ap ? a mod p
Euler数,?(n)定义为小于 n且与 n互素的正整数个数
– p是素数,?(p)=p-1
– 若 n的因子分解为 n=?Piai,ai>0,Pi互不相同,
则 ?(n)= ?Piai?(1-1/Pi)
– 若 gcd(m,n)=1,则 ?(mn)=?(m)?(n),特别地,若
p?q且都是素数,?(pq)=(p-1)(q-1)
第 2章




上一页
下一页
目录
结束
10:22
Euler定理, 若 a与 n为互素的正整数,则
a?(n) ? 1 mod n
推论, 若 n=pq,p?q都是素数,k是任意整数,则
mk(p-1)(q-1)+1 ? m mod n,对任意 0? m? n
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (7/10)
? 整数分解问题 ——数论基础 (续 )
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (8/10)
? 离散对数问题
设 x,r,n是正整数。
已知 x,r和 n,可以很快地求得
y=xr(mod n)
反过来,如果已知 y,x和 n,求 r使得,
y=xr(mod n)
成立。这便是模指数运算,即离散对数问题。
离散对数问题也是 NP-完全问题。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (9/10)
? 离散对数问题 ——原根
? Euler定理表明,对两个互素的整数 a,n,
a?(n) ? 1 mod n
?原根 的定义,
存在最小正整数 m??(n) (m|?(n)),使得
am ? 1 mod n
若对某个 a,m=?(n),则称 a是 n的一个原根
对于素数 p,若 a是 p的一个原根,则,
a,a2,…,ap-1
关于 p两两不同余,从而构成了 p的非 0剩余类,即
与 {1,2,…,(p-1)}关于模 p等价,
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
公钥密码基于的数学难题 (10/10)
? 离散对数问题 ——离散对数的求解
? 若 a是素数 p的一个原根,则对任意整数 b,
b?0 mod p,存在唯一的整数 i,1?i?(p-1),使得,
b?ai mod p
i称为 b以 a为基模 p的 指数 (离散对数 ),记作 inda,p(b).
容易知道,
inda,p(xy)= [inda,p(x)+inda,p(y)] mod ?(p)
inda,p(xr)= [r?inda,p(x)] mod ?(p)
? 离散对数的计算,
y?gx mod p
? 已知 g,x,p,计算 y是容易的
? 已知 y,g,p,计算 x是困难的
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
背包问题
转换背包
超递增 背包
EIGamal密码体系
椭园曲线密码体系
MH公钥算法
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
背包问题
1,问题描述
? 给定一个正整数 S和一个背包向量 A=(a1,…,an),
其中 ai是正整数,求满足方程
S = ∑a ixi 的二进制向量 X=(x1,…,xn)。
? 解决这个问题所需要的时间与 n呈指数增长
2,背包问题用于公钥密码学
? 做法方法:明文为 X,S为密文
? 奥妙在于有两类背包,一类可以在线性时间内
求解,另一类则不能
? 把易解的背包问题修改成难解的背包问题
?公开密钥使用难解的背包问题
?私钥使用易解的背包问题
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
背包问题
转换背包
超递增 背包
EIGamal密码体系
椭园曲线密码体系
MH公钥算法
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
超递增 背包 (1/2)
? 满足下列条件的背包
ai > ∑a j (j = 1,…,i-1)
? 这样的背包就称为超递增背包,或称简单背包。
例如,
1,2,4,8,…, 2n
必须提出的是,并非所有的背包问题都没有有效的
算法不是任意背包问题都难解决,超 递增序列 背包
就容易获解。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
超递增 背包 (2/2)
? 求解
? 从最大的 ai开始,如果 S大于这个数,则减去
ai,记 xi为 1,否则记 xi为 0
? 如此下去,直到最小的 ai
? 例如背包序列 {2,3,6,13,27,52}
? 求解 70的背包
?结果为 {2,3,13,52}
?所以,密文 70对应的明文为 110101
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
背包问题
转换背包
超递增 背包
EIGamal密码体系
椭园曲线密码体系
MH公钥算法
第 2章




上一页
下一页
目录
结束
10:22
? 简单背包用作私钥
? 如何产生相应的公钥 ——转换
? 做法,
选择一个整数 m > ∑a i (i = 1,…,n)
然后选择一个与 m互素的整数 w,然后
bi = wai (mod m) (i = 1,…,n)
这里的 bi是伪随机分布的
这样得到的背包是非超递增背包
公钥密码体制
背包算法
转换背包 (1/2)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
转换背包 (2/2)
例,1,3,7,13,26,65,119,267是超递增序列。
1+3+7+13+26+65+119+267=501
选择一个大于 ∑ ai (i = 1,…,n)的整数,m=523
然后选择一个与 m互素的整数, w=467,w-1=28
那么,bi = wai (mod m)
b1=1× 467(mod 523)≡467
b2=3× 467(mod 523)≡355
b3=7× 467(mod 523)≡131
b4=13× 467(mod 523)≡318
b5=26× 467(mod 523)≡113
b6=65× 467(mod 523)≡21
b7=119× 467(mod 523)≡135
b8=267× 467(mod 523)≡215
则背包 B
( 467,355,131,318,
113,21,135,215)为
非超递增背包 。
将背包 B作为公钥予
以公布。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
背包问题
转换背包
超递增 背包
EIGamal密码体系
椭园曲线密码体系
MH公钥算法
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
MH公钥算法 (1/3)
MH公钥算法即为基于背包问题的公钥密码系统
? 加密
? 将明文分为长度为 n的块 X=(x1,…,xn)
? 然后用公钥 A’ = (a1’,…,an’),将明文变为密
文 S
S = E(X) = ∑a i’xi
? 解密
? 先计算 S’ = w-1S mod m
? 再求解简单背包问题
S’ = ∑a ixi
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
MH公钥算法 (2/3)
例:已知公钥 B( 467,355,131,318,113,21,135,215),
对于明文 m=(10101100)加密得到密文,
b1+b3+b5+b6=467+131+113+21=732
∵ w × w-1≡1(mod 523) ≡467 × 28
∴ w -1=28
接收者收到密文 732后,先计算,
S’ = w-1S mod m
732× 28=20496≡99(mod 523)
然后解:超递增序列背包,
m1+3m2+7m3+13m4+26m5+65m6+119m7+267m8≡99
∴ m 1=m3=m5=m6=1,m2=m4=m7=m8=0
即得明文,10101100
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
背包算法
MH公钥算法 (3/3)
背包密码系统的意义
?是第一个公钥密码系统
?有较好的理论价值
?在实践过程中,大多数的背包方案都已被破
解,或者证明存在缺陷
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
RSA算法的由来
RSA算法描述
RSA密码体制的实现
RSA的性能
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
1977年由 Ron Rivest,Adi Shamir和 Len
Adleman发明,1978年公布
是一种分组加密算法,而且是应用最广泛的公
钥密码算法。
? 明文和密文在 0~ n-1之间,n是一个正整数
既能用于加密,也能用于数字签名
只在美国申请专利,且已于 2000年 9月到期
RSA算法的由来
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
RSA算法的由来
RSA算法描述
RSA密码体制的实现
RSA的性能
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA算法描述 (1/6)
?分组大小为 k,2k < n ? 2k+1
?加密, C = Me mod n
?解密, M = Cd mod n = Med mod n
?公钥, KP={e,n},私钥, KS={d,n}
?上述算法需要满足以下条件,
? 能够找到 e,d,n,使得 Med mod n = M,对所
有 M<n
? 计算 Me和 Cd相对容易
? 从 e和 n得到 d是在计算上不可行的
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA算法描述 (2/6)
? RSA密钥生成原理
? 令 n=pq,p?q都是素数,?(n)=(p-1)(q-1)是
n的 Euler数
? Euler定理推论,
若 n=pq,p?q都是素数,k是任意整数,则
mk(p-1)(q-1)+1 ? m mod n,对任意 0?m?n
? 只要选择 e,d,满足 ed=k?(n)+1,即
ed ? 1 mod ?(n) ? d ? e-1 mod ?(n)
? 公钥, KP={e,n},私钥, KS={d,n}
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA算法描述 (3/6)
? RSA密钥生成与使用
? 产生密钥对
? 选择两个大素数 p,q,p?q
? 计算 n=pq,?(n)=(p-1)(q-1)
? 选择整数 e,使得 gcd(e,?(n))=1
? 计算 d ? e-1 mod ?(n)
? 公钥, KP={e,n},私钥, Ks={d,n}
? 使用
? 加密, C = Me mod n
? 解密, M = Cd mod n
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA算法描述 (4/6)
? 计算乘幂
? 计算 d=am,m=bkbk-1… b0(二进制 表示 )
d?1
for i?k downto 0
do d?(d?d) mod n
if bi = 1
then d?(d?a) mod n
return d
? 原理,
M = ((((((bk2+bk-1)2+bk-2)2+bk-3)2+… )2+b0
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA算法描述 (5/6)
? RSA密钥产生
? 产生两个素数
? 由于 n = pq是公开的,所以,为了防止攻
击者利用 n获得 p和 q,必须选择足够大的素
数 p和 q
? 大素数产生算法
? 选择 e或者 d,然后求出另一个
第 2章




上一页
下一页
目录
结束
10:22
? 大素数产生
? 素数生成过程,
?随机选择一个奇数 n(如通过伪随机数发生器 )
?随机选择 a,使 a<n
?进行素性测试 (例如用 Miller-Rabin算法 ),若
n没有通过测试,抛弃 n,转到 ?
?如果通过了足够次数的测试,认为 n是素数,否
则转到 ?,
? 素数理论, 在 N附近,每 ln(N)个整数中有一个
素数
公钥密码体制
RSA算法
RSA算法描述 (6/6)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
RSA算法的由来
RSA算法描述
RSA密码体制的实现
RSA的性能
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
密钥生成流程
选择 p,q为互异素数
计算 n=p*q,?(n)=(p-1)*(q-1)
选择整数 e使 e与 ?(n)互质
计算 d,使满足 d*e=1mod ?(n)
公钥 PK={n,e}
私钥 SK={n,d}
例 1,
取 P=47,q=71,则
n=p*q=3337,
?(n)=
(p-1)*(q-1)=46*70=3220
随机选取 e使 e与 ?(n)互质,
取 e=79,则可以计算出
d=e-1mod ?(n)
= 79-1mod3220=1019
则可得,
公钥 pk={n,e}={3337,79}
私钥 sk={n,d}={3337,1019}
RSA密码体制的实现 (1/6)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
加密(用 {n,e})
明文,M < n
密文,C = Me(mod n)
例如,
M=688
则密文
C = Me(mod n)
= 68879(mod 3337)
= 1570
解密(用 {n,d})
密文,C
明文,M =Cd (mod n)
例如,
C=1570
则密文
M = Cd (mod n)
= 15701019(mod 3337)
= 688
RSA密码体制的实现 (2/6)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
例 2,
取 P=3,q=11,则
n=p*q=33,
?(n)=
(p-1)*(q-1)=2*10=20
随机选取 e使 e与 ?(n)互质,取 e=3,则可以计算出
d=e-1mod ?(n)
= 3-1mod20=7
则可得,
公钥 pk={n,e}={33,3}
私钥 sk={n,d}={33,7}
RSA密码体制的实现 (3/6)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
若明文 P=“SUZANNE”,则
明文 P 密文 C
字母 序号 P3 P3(mod 33)
S 19 6859 28
U 21 9261 21
Z 26 17576 20
A 01 1 1
N 14 2744 5
N 14 2744 5
E 05 125 26
解密
C7 C7(mod 33) 字母
13492928512 19 S
1801088541 21 U
128000000 26 Z
1 1 A
78125 14 N
78125 14 N
8031810176 5 E
RSA密码体制的实现 (4/6)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA密码体制的实现 (5/6)
? 实现要求
? 若使 RSA安全,p与 q必为足够大的素数,使分析
者没有办法在多项式时间内将 n分解出来。建议
选择 p和 q大约是 100位的十进制素数。 模 n的长
度要求至少是 512比特。 EDI攻击标准使用的 RSA
算法中规定 n的长度为 512至 1024比特位之间,
但必须是 128的倍数。国际数字签名标准
ISO/IEC 9796中规定 n的长度位 512比特位,至
1996年,建议使用 768位的模 n。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA密码体制的实现 (6/6)
? 实现要求 (续 )
? 为了抵抗现有的整数分解算法,对 RSA模 n的素
因子
p和 q还有如下要求,
(1)|p-q|很大,通常 p和 q的长度相同;
(2)p-1 和 q-1分别含有大素因子 p1和 q1
(3)P1-1和 q1-1分别含有大素因子 p2和 q2
(4)p+1和 q+1分别含有大素因子 p3和 q3
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
RSA算法的由来
RSA算法描述
RSA密码体制的实现
RSA的性能
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA的性能 (1/4)
1) RSA的安全性
RSA算法的安全性取决于从公开密钥 (n,e)计算
出秘密密钥 (n,d)的困难程度。因此,
RSA算法的安全性完全依赖于分解大数的难度。
即:只要能够将已知的 n分解为 p和 q的乘积后,
即可破解 RSA。
因此,为了保证 RSA算法的安全性,n必须选大
数,一般认为要达到 1024位二进制数才算安全。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA的性能 (2/4)
由于 RSA采用大数运算,使得 RSA最快的情况也比
DES慢 100倍。
由于 RSA速度远比对称算法(如 DES)慢,RSA一般
来说只用于少量数据加密。
例如,RSA可用于通信双方交换对称密钥。当交换
完成后,可转换到对称密码算法中进行大量的数据
加密。
2) RSA的速度
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
RSA算法
RSA的性能 (3/4)
3) RSA的实现
RSA可以采用硬件或软件方法实现。
?硬件实现方法,
已经研制出高速 RSA专用芯片。
硬件实现时,RSA比 DES慢大约 1000倍。
?软件实现方法,
软件实现时,DES比 RSA快大约 100倍。
第 2章




上一页
下一页
目录
结束
10:22
RSA在实现方面的主要缺点,
? 产生密钥受到素数产生技术的限制。
大多数用于计算素数的算法有可能产生不是素
数的概率。
? 分组长度太长,
为了保证安全性,n至少需要 600bit以上,使运
算速度降低;
随着大数分解技术的发展,n需要不断地增加,
不利于数据格式的标准化。
公钥密码体制
RSA算法
RSA的性能 (4/4)
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
EIGamal密码体系 (1/3)
EIGamal公钥体制是基于离散对数问题的难解性。
? 离散对数的计算,
y?gx mod p
? 已知 g,x,p,计算 y是容易的
? 已知 y,g,p,计算 x是困难的
随机选取一个大素数 p(200位十进制数 ),选一个数
g(模 p的本原根 ),把 p,g对每个用户公开。
1,密钥生成
1) 随机选取一整数 x作为用户的秘密密钥,记为
D=(x);
2) 计算 y=gx mod p;
3) 将 E=(y)公开,作为用户的公开密钥;
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
EIGamal密码体系 (2/3)
2,加密过程
1) 在公开密钥数据库中查得用户的公开密钥:
E=(y);
2) 随机地在 0与 p-1之间取一整数 k;
3) 计算 K=yk mod p,C1=gk mod p,C2=Km mod p;
4) 取 (C1,C2)作为 m的密文传送给用户 U。
3,解密过程
1) 计算 K=C1x mod p;
2) 计算 m=C2K-1 mod p。
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
EIGamal密码体系 (3/3)
例:选取 p = 2576,g=2 (2为 2576的本原根 );
1,密钥生成
选取 x=765作为私钥;
计算 y=2765 mod 2576=949为公钥。
2,加密 m=1299 A→B
选取 k=853,计算,
1) K=yk mod p,949853 mod 2576
2) C1=gk mod p,2853 mod 2576 = 435
3) C2=Km mod p,1299× 949853 mod 2576 = 2396
3,解密
计算 K=C1x mod p; m=C2K-1 mod p。
m=2396× (435765)-1 mod 2576 =1299
第 2章




上一页
下一页
目录
结束
10:22
公钥密码体制
公钥密码体制的基本原理
RSA算法
背包算法
EIGamal密码体系
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
? 所谓椭圆曲线,就是由方程,
y2+axy+by=x3+cx2+dx+e 确定的平面曲线
? 曲线上的点连同无穷远点 O的集合
? 运算定义,
? 若曲线三点在一条直线上,则其和为 O
? O用作加法的单位,O = -O; P+O = P
? 一条竖直线交 X轴两点 P1,P2,则 P1+P2+O=O,于是 P1
= -P2
? 如果两个点 Q和 R的 X轴不同,则画一连线,得到第
三点 P1,则 Q+R+P1=O,即 Q+R=-P1
? 2倍,一个点 Q的两倍是,找到它的切线与曲线的另
一个交点 S,于是 Q+Q=2Q=-S
椭圆曲线密码介绍
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
椭圆曲线密码示意图
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
有限域上椭圆曲线 (1/2)
? 有限域上椭圆曲线
y2?x3+ax+b mod p
p是奇素数,且 4a3+27b2?0 mod p
? 针对所有的 0<=x<p,可以求出有效的 y,
得到曲线上的点 (x,y),其中 x,y<p。记为
Ep(a,b)
? Ep(a,b)中也包括 O
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
有限域上椭圆曲线 (2/2)
? 加法公式,
? P+O=P
? 如果 P=(x,y),则 P+(x,-y)=O,(x,-y)点是 P
的负点,记为 -P。而且 (x,-y)也在 Ep(a,b)中
? 如果 P=(x1,y1),Q=(x2,y2),则 P+Q=(x3,y3)
为,
x3=?2-x1-x2 (mod p)
y3=?(x1-x3)-y1 (mod p)
其中,如果 P?Q,则 ? = (y2-y1)/(x2-x1)
如果 P=Q,则 ? = (3x12+a)/(2y1)
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
椭圆曲线用于加密
? 找到一个难题,
? 考虑等式 Q=kP,其中 Q,P属于 Ep(a,b),k<p
? 已知 k和 P,计算 Q,是容易的
? 已知 Q和 P,计算 k,是困难的
? 选择 Ep(a,b)的元素 G,使得 G的阶 n是一个大素数
? G的阶是指满足 nG=O的最小 n值
? 秘密选择整数 r,计算 P=rG,然后
? 公开 (p,a,b,G,P),P为公钥
? 保密 r
? 加密 M:先把消息 M变换成为 Ep(a,b)中一个点 Pm
? 然后,选择随机数 k,计算密文 Cm={kG,Pm+kP)
? 如果 k使得 kG或者 kP为 O,则要重新选择 k,
? 解密 Cm,(Pm+kP)-r(kG)=Pm+krG-rkG=Pm
? 加密信息有扩张
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
椭圆曲线密码的安全性
?难点, 从 P和 kP获得 k
?对椭圆曲线研究的时间短
?椭圆曲线要求密钥长度短,速度快
?对比, ECC RSA
*Pollard rho分析方法
Key size MIPS-Yrs
150 3.8?1010
205 7.1?1018
234 1.6?1028
512 3?104
768 2?108
1024 3?1011
1280 1?1014
1536 3?1016
2048 3?1020
公钥密码体制
椭园曲线密码体系
第 2章




上一页
下一页
目录
结束
10:22
本节结束
请进入本章的下一节学习