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

目 录 密码学的起源、发展和现状 密码学基本概念 常规加密的现代技术

密码学发展阶段 1949年之前 密码学是一门艺术 1949～1975年 密码学成为科学 1976年以后 密码学的新方向——公钥密码学

第1阶段－古典密码 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段出现，针对的是字符 简单的密码分析手段出现 主要特点：数据的安全基于算法的保密

第1阶段－古典密码 Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。

20世纪早期密码机

第1阶段－古典密码 1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。 这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。

第2阶段 1949~1975 计算机使得基于复杂计算的密码成为可能 相关技术的发展 第2阶段 1949~1975 计算机使得基于复杂计算的密码成为可能 相关技术的发展 1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的《The Codebreakers》 1971-73年IBM Watson实验室的Horst Feistel等几篇技术报告 主要特点：数据的安全基于密钥而不是算法的保密

第3阶段 1976~ 1976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不对称密钥密 1977年Rivest,Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其他公钥算法 主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能

第3阶段 1976~ 1977年DES正式成为标准 80年代出现“过渡性”的“Post DES”算法,如IDEA,RCx,CAST等 第3阶段 1976~ 1977年DES正式成为标准 80年代出现“过渡性”的“Post DES”算法,如IDEA,RCx,CAST等 90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现 2001年Rijndael成为DES的替代者

目 录 密码学的起源、发展和现状 密码学基本概念 常规加密的现代技术

信息传递的一般问题 信源、信道、信宿 攻击的种类： 角色：通信双方、可信第三方、不可信第三方 介质：软件、硬件、数据 中断（Interruption)（干扰） 截取（Interception) (侦听） 修改（Modification） 伪造（Fabrication) 角色：通信双方、可信第三方、不可信第三方 介质：软件、硬件、数据

数据的性质 Availability Interruption -- Interception -- Modification -- Fabrication -- Availability Confidentiality Integrity Authenticity

攻击分类 主动攻击 中断 修改 伪造 破坏可用性 破坏完整性 破坏真实性 被动攻击 窃听 获取消息内容 流量分析

基本概念 密码学(Cryptology): 是研究信息系统安全保密的科学. 密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽. 密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.

基本概念 明文（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))

基本概念 需要密钥的加密算法，记为：C=E(K,P),即密文消息同时依赖于初始明文和密钥的值。实际上，E是一组加密算法，而密钥则用于选择其中特定的一个算法。 加密与解密的密钥相同，即：P=D(K,E(K,P)) 加密与解密的密钥不同，则：P=D(KD,E(KE,P))

常规加密简化模型

常规加密的安全性 加密算法足够强大：仅知密文很难破译出明文 基于密钥的安全性，而不是基于算法的安全性：基于密文和加/解密算法很难破译出明文 算法开放性：开放算法，便于实现

常规加密系统的模型

密码体系形式化描述 密码体系是一个五元组（P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （4）任意k∈ K，有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数， 满足dk(ek(x))=x ，这里 x ∈P。

密码编码系统分类 保密内容 密钥数量 明文处理的方式

保密内容 受限制的（restricted)算法 算法的保密性基于保持算法的秘密 基于密钥（key-based)的算法 算法的保密性基于对密钥的保密

密钥数量 对称密码算法（symmetric cipher) 非对称密钥算法（asymmetric cipher) 加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个 又称秘密密钥算法或单密钥算法 非对称密钥算法（asymmetric cipher) 加密密钥和解密密钥不相同，从一个很难推出另一个 又称公开密钥算法（public-key cipher) 公开密钥算法用一个密钥进行加密, 而用另一个进行解密 其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥（private key)私钥，简称私钥

明文处理方式 分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码（stream cipher) 又称序列密码。序列密码每次加密一位或一字节的明文。

密码分析 试图破译单条消息 试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息 试图找到加密算法中的普遍缺陷（无须截取任何消息）

密码分析的条件与工具 已知加密算法 截取到明文、密文中已知或推测的数据项 数学或统计工具和技术 语言特性 计算机 技巧与运气

密码分析类型

加密方案的安全性 无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文 除了一次一密的方案外，没有无条件安全的算法 安全性体现在： 破译的成本超过加密信息的价值 破译的时间超过该信息有用的生命周期

攻击的复杂性分析 数据复杂性（data complexity）用作攻击输入所需要的数据 处理复杂性（processing complexity）完成攻击所需要的时间 存储需求（storage requirement）进行攻击所需要的数据量

密钥搜索所需平均时间

经典加密技术 替代 置换 转子机

替代 明文的字母由其它字母或数字或符号代替 若该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式

恺撒密码 wuhdwb lpsrvvleoh TREATY IMPOSSIBLE 破译以下密文： 加密算法： Ci=E(Pi)=Pi+3 字母表：(密码本） ABCDEFGHIJKLMNOPQRSTUVWXYZ defghijklmnopqrstuvwxyzabc

恺撒密码的特点 单字母密码（简单替换技术） 简单，便于记忆 缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构

恺撒密码的改进 已知加密与解密算法 25个可能的密钥k，适用Brute-Force Cryptanalysis 明文的语言是已知的且易于识别 C=E(p)=(p+k)mod(26) p=D(C)=(C-k)mod(26) 25个可能的密钥k，适用Brute-Force Cryptanalysis 明文的语言是已知的且易于识别

其它单字母替换 使用密钥 ABCDEFGHIJKLMNOPQRSTUVWXYZ keyabcdfghijlmnopqrstuvwxz spectacular spectaulrbdfghijkmnoqvwxyz 泄露给破译者的信息更少

其它单字母替换 对字母进行无规则的重新排列 E(i)=3*i mod 26 ABCDEFGHIJKLMNOPQRSTUVWXYZ adgjmpsvybehknqtwzcfilorux

单字母变换 任意替换：26！>4x1026 可能的key，大于56位DES的密钥空间。 基于语言统计规律仍可破译

例： UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

多字母替换密码--平稳分布 单字母替换E1和E2 ，分别用于明文信息中奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性（通常E2应为的E1补充） 例1：E1(T)=a, E2(T)=b E1(X)=b, E2(X)=a E1(a)=(3*a)mod26 E2(a)=((5*a)+13)mod 26) TREAT YIMPO SSIBL E fumnf dyvtf czysh h

多字母替换密码--平稳分布 例2： E1(a)=a E2(a)=25-a ABCDEFGHIJKLMNOPQRSTUVWXYZ zyxwvutsrqponmlkjihgfedcba It was the best of times, it was the worst of times… Ig wzs ghv bvsg ou trmvs rt dah tse doisg ou trmvs

对多字母替换的攻击 借助于计算机程序和足够数量的密文，经验丰富的密码分析员能在一小时内攻破这样的密码。 克思斯基方法：用于确定什么时候加密模式的结构重复出现 复合指数方法：用于预测替换所使用的字母数目

有关多字母密码的结论要点 1、使用克思斯基方法预测加密字母可能的数目。若数据无 规律性，则加密不可能简单地为多字母替换； 2、计算重合指数验证第一步中得出的预测； 3、若步1和步2指示一个预定值，则将密文分成适当的子集 合，并独立地计算每个子集合的重合指数。

“完美”的替换密码 使用非重复的加密字母序列加密会使密码分析至今能使用的任何工具失效。 一次性密钥（One Time Pad) 打印、分发、保存与使用问题 长随机数序列（对OTP的近似实现） ri+1=ri*c+b mod w c和b为常数,w为计算机能表示的最大整数

总结 替换是密码学中有效的加密方法。本世纪上半叶用于外交通信 破译威胁来自 频率分布 重合指数 考虑最可能的字母及可能出现的单词 重复结构分析及克思斯基方法 持久性、组织性、创造性和运气

置换 通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。 若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式

K是一个m*m矩阵,在Z/(26)上可逆,即存在K-1使得: KK-1 = I (在Z/(26)) 对每一个k∈ K, 定义ek(x)=xK (mod 26) 和 dk(y)=yK-1 (mod 26) 注： 明文与密文都是 m元的向量（x1, x2 …, xm );(y1, y2,…,ym)，Z/(26)为同余类环 在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值∈ Z*/(26),它为Z/(26)中全体可逆元的集合。 Z*/(26)= {a ∈Z/(26)|(a,26)=1}，Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}

设m为固定的正整数，P=C=(Z/(26))m, K是由{1,2,..,m}的所有置换构成，对一个密钥π∈K，定义 e π(x1, x2,.., xm)=(xπ(1),,..,xπ(m)) 和 d π(y1, y2,.., ym)=(yπ(1),,..,yπ(m)) 这里π－1为π的逆置换 注：这里的加密与解密仅仅用了置换，无代数运算 例子： 设m=6，取密钥 而

若给定的明文是：cryptography 首先找分成6个字母长的明文组：crypto|graphy 求得的密文是：YTCOPRAHGYPR

对上面例子决定的置换π 对应：

转子机 通过多个加密阶段的组合，能使密码分析变得极为困难 对置换和替代都适合

具有连线的三转子机器（用编号的触点表示）

目 录 密码学的起源、发展和现状 密码学基本概念 常规加密的现代技术

安全密码的特性 Shannon特性（1949） 所需的保密程度决定了用于加密和解密过程的相应的工作量 密钥的组或加密算法应该不受其复杂性的影响 处理的实现应尽可能简单 编码中的错误不应传播及影响后面的消息 加密后正文的尺寸不应大于明文的尺寸

Feistel加密过程 输入： 长为2w比特的明文分组 密钥k 输出： 长为2w比特的密文分组

Feistel网络的特点 明文分组分为：L0，R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组 每i次循环都以上一循环产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，相互之间也不同，它是用子密钥生成算法从密钥生成的

Feistel网络的特点 所有循环的结构都相同，置换在数据的左半部分进行，其方法是先对数据的右半部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR) 循环函数对每次循环都有相同的通用结构，但由循环子密钥Ki来区分 在置换之后，执行由数据两部分互换构成的交换

Feistel网络的特点 解密过程与加密过程基本相同。规则如下：用密文作为算法的输入，但以相反顺序使用子密钥Ki 意味着加密和解密不需要用两种不同的方法。

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网络的设计特点 分组大小：较大的分组意味着较强的安全性，但会降低加密解密速度。64位的分组大小是合理的折中，几乎所有的分组设计中都使用它 密钥大小：较大的密钥意味着较强的安全性，但会降低加密解密速度。现代算法中最常用的是128位密钥 循环次数：本质是单一循环的不足，多重循环能够加强安全性。典型的循环次数为16 子密钥生成算法：较大的复杂性会增大密钥分析的难度 循环函数：较大的复杂性意味着给密码分析带来更大的难度

Feistel网络的实现 快速软件加/解密：常将加密嵌入到应用程序中，以预防硬件实现的方式，因此速度很重要 分析的简易性：算法表示简洁清晰，则易于分析算法中加密技术的缺陷

安全密码的特性 Shannon特性（1949） 所需的保密程度决定了用于加密和解密过程的相应的工作量 密钥的组或加密算法应该不受其复杂性的影响 处理的实现应尽可能简单 编码中的错误不应传播及影响后面的消息 加密后正文的尺寸不应大于明文的尺寸。

安全密码的特性 混乱与扩散 信息的理论测试 单一距离

分组密码的一般设计原理 分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列

两个基本设计方法 Shannon称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立 扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性 ,使得明文和密文之间的统计关系尽量复杂 混乱(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂

软件实现的设计原则 使用子块和简单的运算 密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。 应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。 最好是用处理器的基本运算，如加法、乘法、移位等。

硬件实现的设计原则 加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。 尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。

简化的DES Simplified DES方案，简称S-DES方案。 加密算法涉及五个函数： (1) 初始置换IP(initial permutation) (2) 复合函数fk1，它是由密钥K确定的，具有置换和替代的运算。 (3) 转换函数SW (4) 复合函数fk2 (5) 初始置换IP的逆置换IP-1

加密算法的数学表示 加密算法的数学表示 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的密钥生成 设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7, k8,k9,k10) 置换P10是这样定义的 P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 相当于 P10= LS-1为循环左移，在这里实现左移2位 P8=

S-DES的密钥生成 按照上述条件,若K选为(1010000010), 产生的两个子密钥分别为 K1=(1 0 1 0 0 1 0 0)

S-DES的密钥生成

S-DES的加密运算 IP-1= 1 2 3 4 5 6 7 8 初始置换用IP函数: IP= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易见 IP-1(IP(X))=X