1、密码学基础（1）,胡建斌北京大学网络与信息安全研究室E-mail: http:/ 录密码学的起源、发展和现状密码学基本概念常规加密的现代技术,密码学发展阶段,1949年之前 密码学是一门艺术19491975年 密码学成为科学1976年以后 密码学的新方向公钥密码学,第1阶段古典密码,密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段出现，针对的是字符 简单的密码分析手段出现 主要特点：数据的安全基于算法的保密,第1阶段古典密码,Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。
2、,20世纪早期密码机,第1阶段古典密码,1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。,计算机使得基于复杂计算的密码成为可能 相关技术的发展1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的The Codebreakers1971-73年IBM Watson实验室的Horst Feistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密
3、,第2阶段 19491975,1976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不对称密钥密1977年Rivest,Shamir & Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能,第3阶段 1976,1977年DES正式成为标准80年代出现“过渡性”的“Post DES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现2001年Rijn
4、dael成为DES的替代者,第3阶段 1976,目 录密码学的起源、发展和现状密码学基本概念常规加密的现代技术,信息传递的一般问题,信源、信道、信宿攻击的种类：中断（Interruption)（干扰）截取（Interception) (侦听）修改（Modification）伪造（Fabrication)角色：通信双方、可信第三方、不可信第三方介质：软件、硬件、数据,数据的性质,Interruption -Interception -Modification -Fabrication -,Availability,Confidentiality,Integrity,Authenticity,攻击
5、分类,基本概念,密码学(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),基本概念,需要密钥的加密算法，记为：
6、C=E(K,P),即密文消息同时依赖于初始明文和密钥的值。实际上，E是一组加密算法，而密钥则用于选择其中特定的一个算法。 加密与解密的密钥相同，即：P=D(K,E(K,P) 加密与解密的密钥不同，则：P=D(KD,E(KE,P),基本概念,常规加密简化模型,加密算法足够强大：仅知密文很难破译出明文 基于密钥的安全性，而不是基于算法的安全性：基于密文和加/解密算法很难破译出明文 算法开放性：开放算法，便于实现,常规加密的安全性,常规加密系统的模型,密码体系是一个五元组（P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一
7、切可能密钥构成的有限集；（密钥空间） （4）任意k K，有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数， 满足dk(ek(x)=x ，这里 x P。,密码体系形式化描述,保密内容 密钥数量 明文处理的方式,密码编码系统分类,受限制的（restricted)算法 算法的保密性基于保持算法的秘密 基于密钥（key-based)的算法 算法的保密性基于对密钥的保密,保密内容,对称密码算法（symmetric cipher) 加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个 又称秘密密钥算法或单密钥算法 非对称密钥算法（asymmetric cipher) 加密密钥和解密
8、密钥不相同，从一个很难推出另一个 又称公开密钥算法（public-key cipher) 公开密钥算法用一个密钥进行加密, 而用另一个进行解密 其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥（private key)私钥，简称私钥,密钥数量,分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码（stream cipher) 又称序列密码。序列密码每次加密一位或一字节的明文。,明文处理方式,密码分析,试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续
9、的消息试图找到加密算法中的普遍缺陷（无须截取任何消息）,密码分析的条件与工具,已知加密算法 截取到明文、密文中已知或推测的数据项 数学或统计工具和技术 语言特性 计算机 技巧与运气,密码分析类型,加密方案的安全性,无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法安全性体现在：破译的成本超过加密信息的价值破译的时间超过该信息有用的生命周期,攻击的复杂性分析,数据复杂性（data complexity）用作攻击输入所需要的数据处理复杂性（processing complexity）完成攻击所需要的时间存储
10、需求（storage requirement）进行攻击所需要的数据量,密钥搜索所需平均时间,替代 置换 转子机,经典加密技术,明文的字母由其它字母或数字或符号代替 若该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式,替代,恺撒密码,破译以下密文：,wuhdwb lpsrvvleoh,TREATY IMPOSSIBLE,Ci=E(Pi)=Pi+3,加密算法：,字母表：(密码本） ABCDEFGHIJKLMNOPQRSTUVWXYZ defghijklmnopqrstuvwxyzabc,恺撒密码的特点,单字母密码（简单替换技术）简单，便于记忆缺点：结构过于简单，密码分析员只使用
11、很少的信息就可预言加密的整个结构,恺撒密码的改进,已知加密与解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25个可能的密钥k，适用Brute-Force Cryptanalysis明文的语言是已知的且易于识别,其它单字母替换,使用密钥keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露给破译者的信息更少,其它单字母替换,对字母进行无规则的重新排列E(i)=3*i mod
12、26ABCDEFGHIJKLMNOPQRSTUVWXYZadgjmpsvybehknqtwzcfilorux,单字母变换,任意替换：26！4x1026 可能的key，大于56位DES的密钥空间。基于语言统计规律仍可破译,例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ,多字母替换密码-平稳分布,单字母替换E1和E2 ，分别用于明文信息中奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性（通常E2应
13、为的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-aABCDEFGHIJKLMNOPQRSTUVWXYZzyxwvutsrqponmlkjihgfedcbaIt was the best of times, it was the worst of timesIg wzs ghv bvsg ou trmvs rt dah tse do
14、isg ou trmvs,对多字母替换的攻击,借助于计算机程序和足够数量的密文，经验丰富的密码分析员能在一小时内攻破这样的密码。克思斯基方法：用于确定什么时候加密模式的结构重复出现复合指数方法：用于预测替换所使用的字母数目,有关多字母密码的结论要点,1、使用克思斯基方法预测加密字母可能的数目。若数据无 规律性，则加密不可能简单地为多字母替换；2、计算重合指数验证第一步中得出的预测；3、若步1和步2指示一个预定值，则将密文分成适当的子集 合，并独立地计算每个子集合的重合指数。,“完美”的替换密码,使用非重复的加密字母序列加密会使密码分析至今能使用的任何工具失效。一次性密钥（One Time Pa
15、d)相同的PAD，发方与收方绝对同步；打印、分发、保存与使用问题长随机数序列（对OTP的近似实现）ri+1=ri*c+b mod wc和b为常数,w为计算机能表示的最大整数,总结,替换是密码学中有效的加密方法。本世纪上半叶用于外交通信破译威胁来自频率分布重合指数考虑最可能的字母及可能出现的单词重复结构分析及克思斯基方法持久性、组织性、创造性和运气,通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。 若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式,置换,K是一个m*m矩阵,在Z/(26)上可逆,即存在K-1使得:KK-1 = I (在Z/(26)对每一个k
16、 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
17、) 和 d (y1, y2,., ym)=(y(1),.,y(m) 这里1为的逆置换 注：这里的加密与解密仅仅用了置换，无代数运算例子： 设m=6，取密钥 而,若给定的明文是：cryptography 首先找分成6个字母长的明文组：crypto|graphy 求得的密文是：YTCOPRAHGYPR,对上面例子决定的置换 对应：,通过多个加密阶段的组合，能使密码分析变得极为困难 对置换和替代都适合,转子机,具有连线的三转子机器（用编号的触点表示）,目 录密码学的起源、发展和现状密码学基本概念常规加密的现代技术,安全密码的特性,Shannon特性（1949）所需的保密程度决定了用于加密和解密过程的
18、相应的工作量密钥的组或加密算法应该不受其复杂性的影响处理的实现应尽可能简单编码中的错误不应传播及影响后面的消息加密后正文的尺寸不应大于明文的尺寸,Feistel加密过程,输入： 长为2w比特的明文分组 密钥k输出： 长为2w比特的密文分组,Feistel网络的特点,明文分组分为：L0，R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组每i次循环都以上一循环产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，相互之间也不同，它是用子密钥生成算法从密钥生成的,Feistel网络的特点,所有循环的结构都相同，置换在数据的左半部分进行，其方法是先对数据的右半
19、部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR)循环函数对每次循环都有相同的通用结构，但由循环子密钥Ki来区分在置换之后，执行由数据两部分互换构成的交换,Feistel网络的特点,解密过程与加密过程基本相同。规则如下：用密文作为算法的输入，但以相反顺序使用子密钥Ki意味着加密和解密不需要用两种不同的方法。,Feistel结构定义,加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki)解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki),Feistel网络的设计特点,分组大小：较大的分组意味着较强的安全性，但会降低加密解
20、密速度。64位的分组大小是合理的折中，几乎所有的分组设计中都使用它密钥大小：较大的密钥意味着较强的安全性，但会降低加密解密速度。现代算法中最常用的是128位密钥循环次数：本质是单一循环的不足，多重循环能够加强安全性。典型的循环次数为16子密钥生成算法：较大的复杂性会增大密钥分析的难度循环函数：较大的复杂性意味着给密码分析带来更大的难度,Feistel网络的实现,快速软件加/解密：常将加密嵌入到应用程序中，以预防硬件实现的方式，因此速度很重要分析的简易性：算法表示简洁清晰，则易于分析算法中加密技术的缺陷,安全密码的特性,Shannon特性（1949）所需的保密程度决定了用于加密和解密过程的相应的
21、工作量密钥的组或加密算法应该不受其复杂性的影响处理的实现应尽可能简单编码中的错误不应传播及影响后面的消息加密后正文的尺寸不应大于明文的尺寸。,安全密码的特性,混乱与扩散信息的理论测试单一距离,分组密码的一般设计原理,分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列,两个基本设计方法,Shannon称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立 扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性 ,使得明文和密文之间的统计关系尽量复杂 混乱(co
22、nfusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂,软件实现的设计原则,使用子块和简单的运算密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用处理器的基本运算，如加法、乘法、移位等。,硬件实现的设计原则,加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。,简化的DES,Simplified DES方案，简称S-DES方案。 加密算法涉及
23、五个函数： (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
24、,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) K2=(0 1 0 0 0 0 1 1),S-DES的密钥生成,初始置换用IP函数:IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7末端算法的置换为IP的逆置换: IP-1= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6易见 IP-1(IP(X)=X,S-DES的加密运算,
