智能信息安全 Intelligent Information Security 孙松林 北京邮电大学 Email: slsun@bupt.edu.cn

密码技术 – 现代密码学 1，密码学简介 2，密码系统模型 3，古典密码 4， 对称密钥（单钥）密码体制 5，非对称密钥（公钥）密码体制

现代密码学分类 对称密钥密码(单钥密码) 非对称密钥密码(公钥密码/双钥密码) DES － 3DES FEAL（快速数据加密算法） IDEA AES 非对称密钥密码(公钥密码/双钥密码) RSA

古典密码学特点 要求的计算强度小 DES之前 以字母表为主要加密对象 置换和代替技术 数据安全基于算法的保密 密码分析方法基于明文的可读性以及字母及其组合的频率特性

密码系统模型

现代密码学中分组密码算法 设计指导原则 Diffusion(发散) Confusion(混淆) 结构简单、易于分析 小扰动的影响波及到全局 明文或密钥的一位影响密文的多位，密文没有统计特征 Confusion(混淆) 强调密钥的作用 增加密文与明文及密钥之间关系的复杂性 无法从数学上描述，或从统计上去分析 结构简单、易于分析

4. 对称密钥密码体制 对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES 多重DES FEAL IDEA AES

对称密钥密码的历史 美国国家标准局 (NBS) 1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准（DES: Data Encryption Standard） 于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。 1975年3月17日DES首次被公布在联邦记录中。

对称密钥密码的历史 1977年1月15日美国政府决定采纳IBM公司设计的方案作为非机密数据的正式数据加密标准DES，被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。 该方案是在1971年，由Horst Feistel领导的IBM密码研究项目组研究出的LUCIFER算法，并已应用于商业领域。

对称密钥密码的历史 规定日后由美国国家保密局（national security agency, NSA）作评估，并重新批准它是否继续作为联邦加密标准。 在1994年1月的评估中，美国决定1998年12月以后将不再使用DES。

对称密钥密码的历史 1997年4月15日，美国NIST发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。 此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。 1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。

对称密钥密码的历史 1998年8月12日，在首届AES候选会议（first AES candidate conference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。

对称密钥密码的历史 1999年3月，在第2届AES候选会议（second AES candidate conference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个：RC6、Rijndael、SERPENT、Twofish和MARS。

对称密钥密码的历史 2000年4月13日至14日，召开了第3届AES候选会议（third AES candidate conference），继续对最后5个候选算法进行讨论。 2000年10月2日，NIST宣布Rijndael作为新的AES。

对称密钥密码的历史 Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计，开发者提出以下几种发音供选择“Reign Dahl”，“Rain doll”和 “Rhine Dahl”。

4. 对称密钥密码体制 对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES 多重DES FEAL IDEA AES

DES概述 1973/1974年提出加密算法要达到的目的（通常称为DES 密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。

DES概述 1977年由美国的标准化局(NBS，现为NIST)采纳 64位数据分组、56位密钥 历史： IBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥 改进算法，降低为56位密钥，IBM提交给NBS(NIST)

4. 对称密钥密码体制 对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES 多重DES FEAL IDEA AES

Feistel结构图

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)

Feistel结构分析 数据分组Block size(64  128) 密钥长度Key size(56  128~256) 轮数Number of rounds(16) 该结构的关键: 子密钥Subkey generation F函数Round function(F)

Feistel结构优点 易于软硬件实现 结构简单 易于分析

4. 对称密钥密码体制 对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES 多重DES FEAL IDEA AES

S-DES Simplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。

S-DES方案示意图 IP:Initial Permutation 初始置换 SW:交换函数 P10:10bit置换 P8 : 8bit置换 解密 8bit明文 P10 IP 移位 IP-1 P8 fk SW 8bit密文 K2 K1 加密 IP:Initial Permutation 初始置换 SW:交换函数 P10:10bit置换 P8 : 8bit置换

S-DES加密算法的数学表示 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(密文)))))

S-DES 加解密算法涉及五个函数： (1)初始置换IP(initial permutation) (2)复合函数fk1，它由密钥K1确定，具有置换和代换的运算。 (3)交换函数SW (4)复合函数fk2，它由密钥K2确定，具有置换和代换的运算。 (5)初始置换IP的逆置换IP-1

S-DES －－ IP函数 初始置换IP函数: IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7 4 1 3 5 7 2 8 6 易见IP-1(IP(X))=X

S-DES －－ 复合函数fk fk K1 F 复合函数fk，是加密方案中最重要的部分，它可表示为： fk(L,R)=(LF(R,SK),R) 其中 L、R为8位输入，左右各为4位。 F为从4位集到4位集的一个映射，并不要求是单射。 SK（SubKey）为子密钥，左图中为K1。 IP L R 4 E/P 4 fk 8 + K1 F 4 4 S0 S1 P4 +

S-DES加密图 IP: Initial Permutation初始置换 fk E/P：扩张/置换 S0、S1：S盒 P4：4bit置换 8 + K1 F 4 4 S0 S1 2 2 P4 +

S-DES加密图(续) SW fk K2 F SW：交换函数 4 4 E/P 8 8 + 4 4 S0 S1 2 2 P4 + 4 IP-1 8-bit 密文

S-DES －－ F函数 1，E/P（R） 2，与K1异或运算 3，S0，S1 4，P4 K1 F R 4 E/P 8 + 4 4 S0

S-DES －－ E/P运算 输入一个4位数（n1,n2,n3,n4），进行扩张/置换（E/P）运算： 4 1 2 3 2 3 4 1 4 1 2 3 2 3 4 1 直观表现形式为： n4, n1, n2, n3 n2, n3, n4, n1

S-DES －－ 子密钥异或运算 8-bit子密钥K1=(k11,k12,k13,k14,k15,k16,k17,k18) 与E/P的结果作异或运算得： n4+k11,n1+k12,n2+k13,n3+k14 n2+k15,n3+k16,n4+k17,n1+k18 把它们重记为8位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3 上述第一行输入进S盒S0，产生2位的输出； 第二行输入进S盒S1，产生2位的输出。

S-DES －－ S0、S1运算 S盒按下述规则运算： 将第1和第4的输入比特做为2位数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列，如此确定为S盒矩阵的（i,j）数。 例如： （P0,0, P0,3）=(00), (P0,1,P0,2)=(10) 由此确定S0中的第0行2列（0，2） 其系数为3，因此记为（1 1）输出。

S-DES －－ P4置换 1 2 3 4 2 4 3 1

S-DES －－ 密钥的生成 P10 5 5 LS-1 5 P8 8 K1 LS-2 K2 设10bit的密钥为（ k1,k2,…,k10 ) 置换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) P10 LS-1 LS-2 P8 K1 8 K2 5 5 5

S-DES方案示意图 10bit密钥 解密 8bit明文 P10 IP 移位 IP-1 P8 fk SW 8bit密文 K2 K1 加密

课堂练习（需提交） 用S-DES算法对下列明文数据进行加密： Plaintext(8bit): 00010111 如：班内序号为10号，则密钥为0000001010 请写出各步步骤！

4. 对称密钥密码体制 对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES 多重DES FEAL IDEA AES

DES

DES轮加密的简图 Li-1 Ri-1 F + Li Ri Ki

DES轮加密

4. 对称密码体制 DES的加密过程 64位明文经过初始置换IP，将数据重新排列并分成左右两半。左边32位构成L0，右边32位构成R0 64位密钥经过变换产生16个子密钥：K1,K2,…,K16,分别供第1次加密迭代，第2次加密迭代，…，第16次加密迭代使用 由加密函数f实现子密钥K1对R0的加密，结果为32位数据组f(R0,K1)；f(R0,K1)再与L0模2相加，又得到一个32位的数据组L0  f(R0,K1)；以f(R0,K1)作为第2次加密迭代的R1，以R0作为第2次加密迭代的L1。至此，第1次加密迭代过程结束

第2次加密迭代至第16次加密迭代分别用子密钥K2,K3,…,K16进行，其过程与第1次加密迭代相同 第16次加密迭代结束后，产生一个64位数据组，以其左边32位作为R16，以其右边32位作为L16，此结果再经过逆初始置换IP-1，将数据重新排列，便得到64位密文。至此，加密过程全部结束。 加密过程可用如下数学公式描述： Li=Ri-1 Ri = Li-1f(Ri-1,Ki) i=1,2,…,16

图2 DES的整体结构

DES的加密细节 初始置换IP：初始置换的作用在于将64位明文打乱重排，并分成左右两半，供后面加密迭代使用。置换后的64位数据的1,2,…,64位依次对应原明文的58,50, …,7位 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 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

子密钥的产生：64位密钥经过置换选择1(PC-1)、循环左移(LS)、置换选择2(PC-2)等变换，产生16个子密钥 图3 子密钥产生的流程图

表3 循环左移位数表 迭代次数 循环左移位数 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16

⑴置换选择1工作过程 64位密钥分为8个字节，每个字节的前7位用于加密过程，第8位是奇偶校验位。置换选择1的作用有两个：一是从64位密钥中去掉8个奇偶校验位；二是将其余56位数据打乱重排，且将前28位作为C0，后28位作为D0。置换选择规定：C0的各位依次为密钥中的第57，49，…，44，36位；D0的各位依次为密钥中的63，55，…，12，4位。如图所示

图4 置换选择1框图

⑵置换选择2的工作过程 置换选择2从Ci和Di(共56位)中选择出一个48位的子密钥Ki。其中规定：子密钥Ki中的各位依次是Ci和Di中的14，17，…，5，3，…，29，32位 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

⑶加密函数f的生成 ①选择运算E：对32位的数据组A的各位进行选择和排列，产生 一个48位的结果。加密时A为Ri，解密时A为Li，见图6。 ②选择函数组S：由8个选择函数(或称S盒)组成，8个选择函 数分别记为S1,S2,…,S8。选择函数组输入是一个48位的数据组。 每个选择函数有6个输入，4个输出，6个输入组成一个二进制数 字组。每个选择函数有一个选择矩阵，选择规则是：输入二进制 字组中的第1和第6两位所组成的二进制数值代表选中的行号，其 余4位所组成的二进制数值代表选中的列号，而处在被选中的行 和列的交点处的数字便是选择函数的输出(以二进制形式输出)。

图5 加密框图 图6 选择运算E框图

性变换，IBM和NSA(美国国家保密局)迄今尚未公布其 设计细节。研究表明，选择函数S至少满足以下准则： 输出不是输入的线性和仿射变换 选择函数S是DES保密性的关键所在，它是一种非线 性变换，IBM和NSA(美国国家保密局)迄今尚未公布其 设计细节。研究表明，选择函数S至少满足以下准则： 输出不是输入的线性和仿射变换 改变其中1位，输出至少有2位发生变化 保持1位不变，其余5位变化，输出中的0和1个数接近相等 ③置换运算P：把选择函数输出的32位数据打乱重 排，得到32位的加密函数结果。

第2次加密迭代到第16次加密迭代过程与第1次加密迭代相同 逆初始置换IP-1：初始置换IP的逆变换。它把第16次加密迭代结果的各位打乱重排，形成64位密文。至此，加密过程完全结束

DES的解密过程 把64位密文作为明文输入，第1次解密迭代使用子密 钥K16，第2次解密迭代使用子密钥K15，…，第16次解密 解密过程可用如下数学公式描述： Ri-1=Li Li-1=Rif(Li,Ki) i=16,15,…,1

DES的设计思想和特点 综合使用了置换、代替、代数多种密码技术，是一种乘积密码。 在算法结构上采用迭代结构，从而使结构紧凑，条理清楚，而且算法为对合运算，便于实现 保密性的关键是选择函数组S，其余变换均为线性变换 算法中使用了迭代，大大提高了保密性 子密钥的产生与使用确保了原密钥中各位的使用次数基本上相等，保密性得到进一步提高 DES的弱点：56位的密钥显然短了一些，且存在一些弱密钥和半弱密钥

2)快速数据加密算法(FEAL) 由日本学者清水明宏和宫口庄司在DES的基础上提出 FEAL与DES相比的特点 增大了有效密钥长度； 增强了密钥的控制作用； 增大了加密函数f的复杂性； 减少了迭代次数；

FEAL与DES的比较 都是单密钥分组密码，分组长度为64位 加密运算均是对合运算 密钥均是64位，但DES密钥中包含8位奇偶校验位，有效密钥为56位，因此FEAL的抗穷举性能大大提高 DES的初始置换和逆初始置换与密钥无关，FEAL的初始变换和末尾变换均受密钥控制，从而提高了保密性

DES使用的变换主要是置换、代替和模2加，非线性由S盒提供；FEAL使用的变换主要是循环移位、mod 256加和模2加，非线性由S函数提供 DES迭代次数为16，FEAL迭代次数为4，因而FEAL软件实现速度更快 FEAL不使用置换、代替变换，因此在硬件实现中可省去大量存储器 FEAL的密钥长度仍然不够，且迭代次数也少了一些

对AES的基本要求是： 比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。

AES 算法的原型是Square算法，它的设计策略是宽轨迹策略（wide trail strategy）。 宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。

密码技术 1，密码学简介 2，密码系统模型 3，古典密码 4， 对称密钥（单钥）密码体制 5，非对称密钥（公钥）密码体制

5. 公钥密码体制 对称密码体制的缺陷： 密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现； 密钥管理问题：在有多个用户的网络中，任何两个用户之间都需要有共享的密钥，当网络中的用户n很大时，需要管理的密钥数目非常大，为 n(n-1)/2 没有签名功能：当主体A收到主体B的电子文挡(电子数据)时，无法向第三方证明此电子文档确实来源于B。

5. 公钥密码体制 公钥密码的基本思想 公开密钥ke用于加密或验证签名 私钥kd用于解密或签名 在算法上不能由ke推出kd

RSA Ronald Rivest 、Adi Shamir和Leonard Adleman于1977年一起发明了RSA公钥算法，也是RSA数据安全公司的联合创始人。 他们分享了2002年度美国计算机协会(ACM)颁发的图灵奖。 1991年Ronald Rivest设计了MD5算法。

5. 公钥密码体制 公钥密码应满足的条件 解密算法D与加密算法E互逆，即对于明文M都有 M= D(E(M,Ke),Kd) 算法E和D都是高效的 对于所有明文M都有M= E(D(M, Kd), Ke) 满足前3个条件可构成一个确保数据秘密性的公钥密码。 如果还要求确保数据的真实性，则还应满足第4个条件。

5. 公钥密码体制 公钥密码的工作方式 设M为明文，C为密文，E为公钥密码的加密算 法，D为解密算法，Ke为公开的加密钥（公钥）， Kd为保密的解密钥（私钥），每个用户都分配一对 密钥，而且将所有用户的公开密钥Ke存入共享的公 钥密码库PKDB。再设用户A要把数据M安全保密地 传送给用户B。给出以下3种通信协议

5. 公钥密码体制 1）确保数据的保密性 发方：A查PKDB，得到B的公钥KeB； A用KeB加密M得到C：C=E(M,KeB); A发C给B 收方：B接收C； B用自己的私钥KdB解密C，得到明文M=D(C，KdB) 此时可以确保数据的保密性，却不能保证数据的真实性(因 为任何人都可以冒充A)

5. 公钥密码体制 2）确保数据的真实性 发方：A首先用自己私钥KdA加密M得到C： C=E(M,KdA)； A发C给B 收方：B接收C； B查PKDB，得到A的公钥KeA； B用KeA解密C，得到明文M=D(C，KeA) 此时可以确保数据的真实性，却不能保证数据的保密性(因 为任何人都可以获得M)

3）同时确保数据的保密性和真实性 发方：A用自己私钥KdA加密M，得到中间密文S为S=E(M,KdA)； A查PKDB，得到B的公钥KeB； A用KeB加密S得到C：C=E(S,KeB)； A发C给B； 收方：B接收C； B用自己的私钥KdB解密C，得到中间密文S=D(C,KdB) ； B查PKDB，得到A的公钥KeA； B用KeA解密S，得到明文M=D(S，KeA)

RSA公钥密码 选择一对不同的素数pq，并且保密 计算n=pq，f(n)=(p-1)(q-1)，其中f(n)是n的欧拉函数值 选择一个整数a，满足1<a<f(n)，且f(n)与a互素 计算d，满足da=1 mod f(n) 以{a,n}为公钥，{d,n}为私钥，则密钥空间为K=(n,p,q,d,a) 加密过程为c≡ma mod n 解密过程为m≡cd mod n，其中m、c分别为明文和密文，n和a公开，而p、q、d保密

RSA的实现问题 大数分解是一个十分困难的问题，一般认为RSA保密性能良好 涉及高次幂的计算，用软件实现速度较慢，用硬件实现速度较快 加、解密变换是可交换的互逆变换，可用来作数字签名

Homework 古典密码学特点是什么？ 现代密码学中分组密码算法设计指导原则是什么？ 请画出Feistel结构图。