E-mail: hjbin@infosec.pku.edu.cn 密码学基础（2） 胡建斌 北京大学网络与信息安全研究室 E-mail: hjbin@infosec.pku.edu.cn http://infosec.pku.edu.cn/~hjbin

目 录 数据加密标准 公开密钥算法

数据加密标准 （Data Encryption Standard,DES)

背景 发明人：美国IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制成功 基础：1967年美国Horst Feistel提出的理论 产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告， 公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳 了IBM的LUCIFER方案 标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标 准局颁布为数据加密标准（Data Encryption Standard），于 1977年7月15日生效

背景 美国国家安全局（NSA, National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位 1979年，美国银行协会批准使用DES 1980年，DES成为美国标准化协会(ANSI)标准 1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作

DES概述 分组加密算法：明文和密文为64位分组长度 对称算法：加密和解密除密钥编排不同外，使用同一算法 密钥长度：56位，但每个第8位为奇偶校验位，可忽略 密钥可为任意的56位数，但存在弱密钥，容易避开 采用混乱和扩散的组合，每个组合先替代后置换，共16轮 只使用了标准的算术和逻辑运算，易于实现

DES加密算法的一般描述

DES加密过程 输入64比特明文数据 初始置换IP 在密钥控制下 16轮迭代 初始逆置换IP-1 输出64比特密文数据 交换左右32比特

DES加密过程 令i表示迭代次数，表示逐位模2求和，f为加密函数

DES解密过程 令i表示迭代次数，表示逐位模2求和，f为加密函数

DES中的各种置换、扩展和替代

初始置换IP和初始逆置换IP—1

IP和IP—1 IP IP—1

DES的 一轮迭代 Li-1（32比特） Ri-1（32比特） Li（32比特） 48比特寄存器 选择扩展运算E 子密钥Ki （48比特） 32比特寄存器 选择压缩运算S 置换运算P Ri（32比特） Li=Ri-1

扩展置换Ｅ-盒－32位扩展到48位 扩展

压缩替代S-盒－48位压缩到32位 共8个S盒

S-盒1 S-盒5 S-盒6 S-盒2 S-盒3 S-盒7 S-盒4 S-盒8

S-盒的构造

S-盒的构造 DES中其它算法都是线性的，而S-盒运算则是非线性的 S-盒不易于分析，它提供了更好的安全性 所以S-盒是算法的关键所在

S-盒的构造准则 S盒的每一行是整数0，…，15的一个置换 没有一个S盒是它输入变量的线性函数 改变S盒的一个输入位至少要引起两位的输出改变 对任何一个S盒和任何一个输入X，S（X）和 S(X001100）至少有两个比特不同（这里X是长度为6的比特串） 对任何一个S盒，对任何一个输入对e,f属于{0,1}, S(X) S(X11ef00) 对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目

S-盒的构造要求 S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度 提供了密码算法所必须的混乱作用 非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门

置换p-盒的构造

p-盒的构造准则 P置换的目的是提供雪崩效应 明文或密钥的一点小的变动都引起密文的较大变化

DES中的子密钥的生成

密钥置换算法的构造准则 设计目标：子密钥的统计独立性和灵活性 实现简单 速度 不存在简单关系：( 给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系) 种子密钥的所有比特对每个子密钥比特的影响大致相同 从一些子密钥比特获得其他的子密钥比特在计算上是难的 没有弱密钥

DES的 一轮迭代 Li-1（32比特） Ri-1（32比特） Li（32比特） 48比特寄存器 选择扩展运算E 子密钥Ki （48比特） 32比特寄存器 选择压缩运算S 置换运算P Ri（32比特） Li=Ri-1

DES加密算法的一般描述

DES的工作模式

电子密码本 ECB (electronic codebook mode) 密码分组链接 CBC (cipher block chaining) 密码反馈 CFB (cipher feedback) 输出反馈 OFB (output feedback)

电子密码本ECB

ECB的特点 简单和有效 可以并行实现 不能隐藏明文的模式信息 相同明文生成相同密文，同样信息多次出现造成泄漏 对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放 误差传递：密文块损坏仅对应明文块损坏 适合于传输短信息

密码分组链接CBC

CBC的特点 没有已知的并行实现算法 能隐藏明文的模式信息 需要共同的初始化向量IV 相同明文生成不同密文 初始化向量IV可以用来改变第一块 对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏两明文块损坏 安全性好于ECB 适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec

密码反馈CFB CFB:分组密码流密码 假定：Si 为移位寄存器,传输单位为jbit 加密: Ci =Pi(EK(Si)的高j位) Si+1=(Si<<j)|Ci 解密: Pi=Ci(EK(Si)的高j位)

Ci =Pi(EK(Si)的高j位) ; Si+1=(Si<<j)|Ci 密码反馈CFB加密

Pi=Ci(EK(Si)的高j位); Si+1=(Si<<j)|Ci 密码反馈CFB解密

CFB的特点 分组密码流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 对于不同的消息，IV必须唯一 误差传递：一个单元损坏影响多个单元

输出反馈OFB OFB:分组密码流密码 假定：Si 为移位寄存器,传输单位为jbit 加密: Ci =Pi(EK(Si)的高j位) Si+1=(Si<<j)|(EK(Si)的高j位) 解密: Pi=Ci(EK(Si)的高j位)

Ci =Pi(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位) 输出反馈OFB加密

Pi=Ci(EK(Si)的高j位); Si+1=(Si<<j)|(EK(Si)的高j位) 输出反馈OFB解密

0FB的特点 分组密码流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 对于不同的消息，IV必须唯一 误差传递：一个单元损坏只影响对应单元 对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放 安全性较CFB差

多重DES

两重DES

三重DES

DES的安全性

F函数(S-Box)设计原理未知 密钥长度的争论 DES的破译 弱密钥与半弱密钥

DES密钥长度 关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个 早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元

DES密钥长度 在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥 美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元

DES密钥长度 1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥

破译DES 1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击 线性密码分析比差分密码分析更有效

弱密钥与半弱密钥 弱密钥: EKEK = I ，DES存在4个弱密钥 即： 半弱密钥: EK1 = EK2 ，至少有12个半弱密钥

其它常规分组加密算法

Triple DES IDEA RC5 RC6 AES 其他一些较实用的算法，如Blowfish，CAST，以及RC2等

使用常规加密进行保密通信

易受攻击的位置 电话公司 市话局 接线盒

链路加密和端到端加密

存储转发通信的加密覆盖范围

各种加密策略包含的内容

链路层加密 对于在两个网络节点间的某一次通信链路,链路加密能为网上传输的数据提供安全保证 所有消息在被传输之前进行加密,在每一个节点对接收到的消息进行解密,然后先使用下一个链路的密钥对消息进行加密,再进行传输

链路层加密的优点 由于在每一个中间传输节点消息均被解密后重新进行加密,因此,包括路由信息在内的链路上的所有数据均以密文形式出现。这样,链路加密就掩盖了被传输消息的源点与终点 由于填充技术的使用以及填充字符在不需要传输数据的情况下就可以进行加密,这使得消息的频率和长度特性得以掩盖,从而可以防止对通信业务进行分析

链路层加密的缺点 链路加密通常用在点对点的同步或异步线路上,它要求先对在链路两端的加密设备进行同步,然后使用一种链模式对链路上传输的数据进行加密。这就给网络的性能和可管理性带来了副作用 在一个网络节点,链路加密仅在通信链路上提供安全性,消息以明文形式存在,因此所有节点在物理上必须是安全的,否则就会泄漏明文内容 在传统的加密算法中,用于解密消息的密钥与用于加密的密钥是相同的,该密钥必须被秘密保存,并按一定规则进行变化。这样,密钥分配在链路加密系统中就成了一个问题,因为每一个节点必须存储与其相连接的所有链路的加密密钥,这就需要对密钥进行物理传送或者建立专用网络设施。而网络节点地理分布的广阔性使得这一过程变得复杂,同时增加了密钥连续分配时的费用

节点加密 节点在操作方式上与链路加密是类似的:两者均在通信链路上为传输的消息提供安全性;都在中间节点先对消息进行解密,然后进行加密。因为要对所有传输的数据进行加密,所以加密过程对用户是透明的 然而,与链路加密不同,节点加密不允许消息在网络节点以明文形式存在,它先把收到的消息进行解密,然后采用另一个不同的密钥进行加密,这一过程是在节点上的一个安全模块中进行 节点加密要求报头和路由信息以明文形式传输,以便中间节点能得到如何处理消息的信息。因此这种方法对于防止攻击者分析通信业务是脆弱的

端到端加密 端到端加密允许数据在从源点到终点的传输过程中始终以密文形式存在 采用端到端加密(又称脱线加密或包加密),消息在被传输时到达终点之前不进行解密,因为消息在整个传输过程中均受到保护,所以即使有节点被损坏也不会使消息泄露

端到端加密的优点 端到端加密系统的价格便宜些,与链路加密和节点加密相比更可靠,更容易设计、实现和维护 端到端加密避免了其它加密系统所固有的同步问题,因为每个报文包均是独立被加密的,所以一个报文包所发生的传输错误不会影响后续的报文包 从用户对安全需求的直觉上讲,端到端加密更自然些。单个用户可能会选用这种加密方法,以便不影响网络上的其他用户,此方法只需要源和目的节点是保密的即可

端到端加密的缺点 通常不允许对消息的目的地址进行加密,这是因为每一个消息所经过的节点都要用此地址来确定如何传输消息 由于这种加密方法不能掩盖被传输消息的源点与终点,因此它对于防止攻击者分析通信业务是脆弱的

目 录 数据加密标准 公开密钥算法

公开密钥算法 公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了20多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用

公开密钥算法的提出 公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654

公开密钥算法的提出 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的 参见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126 该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上

公开密钥算法的基本要求 加密与解密由不同的密钥完成 加密： 解密： 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的）

基于公开密钥的加密过程

用公钥密码实现保密 用户拥有自己的密钥对(KU,KR) 公钥 KU公开，私钥KR保密

基于公开密钥的鉴别过程

用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外一个用作解密 鉴别： 鉴别＋保密

公开密钥算法 公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于离散对数难题（DLP）算法体制 基于椭圆曲线离散对数难题（ECDLP）的算法体制

Diffie-Hellman密钥交换算法

单向陷门函数函数 满足下列条件的函数f： (1) 给定x，计算y=f(x)是容易的 (2) 给定y, 计算x使y=f(x)是困难的 (3) 存在z，已知z 时, 对给定的任何y，若相应的x存 在，则计算x使y=f(x)是容易的 所谓计算x= f-1(Y)困难是指计算上相当复杂，已无实际意义

单向陷门函数说明 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，z 称为陷门信息 当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为Pk f函数的设计者将z保密，用作解密密钥，此时z称为秘密钥匙，记为Sk。由于设计者拥有Sk，他自然可以解出x=f-1(y) 单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的

Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换算法的原理 基于有限域中计算离散对数的困难性问题之上：设F为有限域，g∈F是F的乘法群 F*=F\{0}=<g>，并且对任意正整数x，计算gx是容易的；但是已知g和y求x使y= gx，是计算上几乎不可能的 这个问题称为有限域F上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FP

Diffie-Hellman密钥交换协议描述 Alice和Bob协商好一个大素数p，和大的整数g，1<g<p，g最好是FP中的本原元，即FP*＝<g> p和g无须保密，可为网络上的所有用户共享

Diffie-Hellman密钥交换协议描述 当Alice和Bob要进行保密通信时，他们可以按如下步骤来做： (1) Alice选取大的随机数x，并计算 X = gx(mod P) (2) Bob选取大的随机数x，并计算 X  = gx (mod P) (3) Alice将X传送给Bob；Bob将X 传送给Alice (4) Alice计算K= (X )X(mod P); Bob计算K  =（X) X (mod P), 易见，K = K  =g xx (mod P) 由(4)知，Alice和Bob已获得了相同的秘密值K 双方以K作为加解密钥以传统对称密钥算法进行保密通信

RSA 算法

Euler 函数 所有模m和r同余的整数组成剩余类[r] 剩余类[r]中的每一个数和m互素的充要条件是r和m互素 和m互素的同余类数目用φ(m)表示，称m的Euler函数 当m是素数时，小于m的所有整数均与m互素，因此φ(m)=m-1 对n=pq, p和q 是素数，φ(n)=φ(p)φ(q)=(p-1)(q-1)

Euler 函数举例 设p=3, q=5, 那么 φ（15）=（3-1）*（5-1）=8 这8个模15的剩余类是： {1，2，4，7，8，11，13，14}

RSA算法的实现 实现的步骤如下：Bob为实现者 密码分析者攻击RSA体制的关键点在于如何分解n。若分 (1) Bob寻找出两个大素数p和q (2) Bob计算出n=pq 和φ(n)=(p-1)(q-1) (3) Bob选择一个随机数e (0<e< φ(n))，满足(e,φ(n))=1 (4) Bob使用辗转相除法计算d=e-1(modφ(n)) (5) Bob在目录中公开n和e作为公钥 密码分析者攻击RSA体制的关键点在于如何分解n。若分 解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公 开的e，解出秘密的d

RSA算法编制 参数T={N}； 私钥SK=D； 公钥PK=E； 设：明文M，密文C，那么： 用公钥作业：ME mod N = C 用私钥作业：MD mod N = M

RSA算法举例 设 p=7, q=17, n=7*17=119; 参数T={n=119}; φ(n)=(7-1)(17-1)=96; 选择e=5, gcd(5,96)=1; 公钥pk=5; 计算d, ( d*e) mod 96=1; d=77; 私钥sk=77; 设:明文m=19 加密：（19）5 mod 119 = 66 脱密：（66）77 mod 119 = 19

RSA算法的安全性分析 密码分析者攻击RSA体制的关键点在于如何分解n 若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d 若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来

RSA算法的安全性分析 建议选择p和q大约是100位的十进制素数 模n的长度要求至少是512比特 EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数 国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位

RSA算法的安全性分析 为了抵抗现有的整数分解算法，对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

RSA算法的安全性分析 为了提高加密速度，通常取e为特定的小整数 如EDI国际标准中规定 e＝216＋1 ISO/IEC9796中甚至允许取e＝3 这时加密速度一般比解密速度快10倍以上