《可信计算课件资源》第2章密码学技术

第二章密码学技术122安全需求1/31/2023完整性Integrity真实性authenticity保证数据来源的真实性可追究性accountability确保一个主体能够对他的行为/结果负责隐私性privacy维护个人身份信息的机密性维护数据的有效性及正确性，抵御恶意的或意外的更改机密性Confidentiality确保信息仅可被授权的用户访问可用性Availability维护资源/服务能够传递到有效用户2基本的安全路径Identification身份证明Authentication认证Authorization授权你是谁？你来自于什么地方？你所声称的你是你；你所声称的内容是真实的。允许主体对其所请求资源所执行的访问。3身份证明(Identification)是一个动作或一个过程，用于向系统表明一个实体的身份，这样系统就可以将其与所有其他的实体区分开来。身份证明有两个作用：可追查性与访问控制。4认证是一个过程，通过这个过程，一个实体向另一个实体证明其声称的属性。认证一般分为三种数据源认证 验证消息的某个声称属性，用它验证消息是否来源于所声称的消息源实体认证验证消息发送者的身份认证的密钥建立（密钥交换、密钥协商）产生一条安全通道，用于后继的应用层安全通信会话认证5授权授权是一个过程，对于一个给定的物理或逻辑资源，该过程需要判断哪种访问类型允许对资源进行访问。一旦用户的身份已经被授权了，那么他会允许访问一个指定的区域、系统或服务。强制性授权：访问控制列表细粒度加密67密码学因应用需求而产生,因应用需求而发展。Cryptographyisoriginatedanddevelopedfromtherequirementsofapplication.8

2.1安全中的密码问题2.2对称加密DES2.3公钥密码学2.4密钥管理92.1安全中的密码问题10以数据加密、用户认证为基础的开放型网络安全保障技术，可望成为网络安全问题的最终的、一体化解决方案。利用加密技术来保护网络系统中包括用户数据在内的所有数据流，在不对网络环境作特殊要求的前提下，从根本上解决网络服务中的可用性和信息的完整性这两大要求。不需要网络拓扑结构的支持，在数据传输中不对所经的网络的安全有要求，实现网络通信过程端到端的安全保障。目前的防火墙系统都支持基于密码技术的私有虚拟网（virtualprivatenetwork），可以说密码是任何安全技术所不可缺少的部分。（1）密码是安全技术核心11举例：保险柜保护珍贵的物品或机要的信息通常可以借助一个保险库，例如银行的金库。保险柜中的每一件东西是以物理的方式进行保护的，只有授权者用钥匙或输入相应的组合密码才能打开库房的门。安全要求较高的地方，保险柜的需要多把门锁并按“分权原则”进行管理，即由多人分别掌管不同的钥匙，当至少两个以上的授权人同时在场，才能打开保险库。12举例：纸币

纸币的安全问题，则完全属于不同的类型。此时，钞票安全的关键是真实性的鉴别，而不在于是否保密，因为钞票决不允许被任何形式的伪造和更改。防伪：精制的版刻画面、水印、特制的金属丝线、隐藏在画面内的微写以及各种其它标记…，可以通过观察和触摸来验证。安全性好的货币，其防伪检验措施应简洁而有效，用户能较容易掌握。

13传统的安全机制有两个特点：安全性基于不可更改的物理标记不论是保险库的钥匙还是纸币上的水印，它们基本上是保持不变的。正是标记的不可更改，才使检验系统真实性成为可能。安全性有时依赖于众所周知的特征。为了保险库的安全，对钥匙和组合密码要求保密；但纸币上标识其真伪的各种记号应做到尽人皆知，这样才便于人们检验钞票的真伪。（2）安全机制的特点14问题：系统的安全取决于物理标记的不可复制及人们对系统的熟悉程度和经验。随着新技术的发展，专家所掌握的绝技很快成为大众技术，“不可复制”的东西会一再地被复制出来。如果一个系统的安全基本上依赖于经验这类人为的因素，这样的安全是靠不住的，也是很危险的。密码学所追求的安全，是一种客观的、可以被证明的安全。也就是：安全性不仅仅建立在静止不变的物理特征上；安全判别不能只凭经验，还要能逻辑地证明无限制的安全强度。

（2）安全机制的特点15密码学的目标正是要设计这样的安全体系，它将提供可证明的各种强度的安全等级。数学相对于其它科学的优势在于它的逻辑体系，它的每一个推断和结论都来自严格的证明。现代密码学正是一门数学背景极强的学科，它自然带有数学的许多特征。设想一种货币（譬如电子货币），如果其安全强度可以借助密码学的手段和数学方法证明，那样货币发行银行就无需因为科技发展而担惊受怕，因为货币的安全不是建立在今天的技术上，而是基于可以证明的、具有超前的安全强度。16密码学除了提供在原理上可证明（数学上可分析）的安全性，还有“安全强度可加”等优点。举例：身份认证的入口控制自动取款机ATM。使用ATM之前，首先要作的是检验用户的身份，即用户向ATM输入个人密码PIN，ATM经过与系统的联机查询来判断用户是否合法。这种安全体系实际是通过静态的PIN来鉴别身份，它的弱点是一但攻击者从线路上截获到PIN，就可以假冒用户的身份进行欺骗。为了避免静态密码潜在的不安全因素，考虑一种改良的身份认证协议，它的基本特点是认证过程不传递任何秘密，而是代以交换具有随机特征的数据来实现问答，使攻击者无从下手。这就是所谓的挑战/应答式协议C&R（ChallengenandResponse）17优点：通过简单的协议和密码函数，可将系统的安全性提高一大步：即仅有卡而不知PIN仍无法通过检查。缺点：系统同时也掌握用户的密钥k。鉴于这一点，可采用公钥算法或无任何信息泄漏的零知识证明（Zero-Knowledge）算法。18动态口令（挑战/应答）一个令牌每分钟产生一个不同的口令服务器也同样产生这样的口令通过对比，如果一样就通过认证客户端服务器(1)客户端向服务器发送请求(1)服务器收到请求(1)请求验证(2)服务器产生随机数(2)随机数(2)收到服务器发来的随机数(3)客户端将随机数通过USB接口传送给ePass，产生口令(3)产生口令(4)服务器产生口令，验证S(口令)=C(口令)(4)验证结果19密码学是信息安全的核心，围绕着密码理论和应用分为几个不同的层次，最底层是数学、逻辑等基础；然后是基本的密码算法，接下来是在此基础上具有普适性的密码协议，最上面是一些针对具体应用的协议。数学基础：数论、抽象代数、常用数学难题基本密码学算法：对称加密、非对称加密、Hash基础协议：数字签名、零知识证明、VSS、盲签名高级协议：电子选举、电子拍卖、门限签名,SSL20（3）密码中的困难问题什么是计算计算模型可计算问题计算复杂度21随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。在大众的意识里，计算首先指的就是数的加减乘除，其次则为方程的求解、函数的微分积分等；懂的多一点的人知道，计算在本质上还包括定理的证明推导。可以说，“计算”是一个无人不知元人不晓的数学概念，事实上，直到1930年代，由于哥德尔K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、图灵(A.M.TUI-ing，1912-1954)等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。22所谓计算，就是从一个符号串f变换成另一个符号串g。例如:从符号串2+3变换成5就是一个加法计算;如果符号串f是x2

，而符号串g是2x,从f到g的计算就是微分。定理证明也是如此，令f表示一组公理和推导规则，令g是一个定理,那么从f到g的一系列变换就是定理g的证明。文字翻译也是计算，如f代表一个英文句子，而g为含意相同的中文句子，那么从f到g就是把英文翻译成中文。这些变换间有什么共同点？为什么把它们都叫做计算？因为它们都是从己知符号(串)开始，一步一步地改变符号(串)，经过有限步骤，最后得到一个满足预先规定的符号(串)的变换过程。23计算主要有两大类：数值计算：包括实数和函数的加减乘除、幕运算、开方运算、方程的求解等。符号推导：包括代数与各种函数的恒等式、不等式的证明,几何命题的证明等。无论是数值计算还是符号推导,它们在本质上是等价的、一致的，即二者是密切关联的，可以相互转化，具有共同的计算本质。随着数学的不断发展,还可能出现新的计算类型。24计算的实质：为了回答究竟什么是计算、什么是可计算性等问题，人们采取的是建立计算模型的方法。四种模型：一般递归函数、λ可计算函数、图灵机和波斯特(E.L.Post，1897-1954)系统。在此基础上，最终形成了如今著名的丘奇-图灵论点：凡是可计算的函数都是一般递归函数(或是图灵机可计算函数等)。这就确立了计算与可计算性的数学含义。25Turing机用机器来模拟人们用纸笔进行运算的过程：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；在每个阶段，人要决定下一步的动作，依赖于(a)此人当前所关注的纸上某个位置的符号(b)此人当前思维的状态。图灵构造出一台假想的机器，由以下几个部分：一条无限长的纸带一个读写头一个状态寄存器一套控制规则26可计算问题若某问题，若存在一个Turing机，对于相应的初始状态，Turing机经过有限步最终停机。称该问题是（Turing）可计算的。对于可计算的问题，计算复杂性的定义：计算所需的步数或指令条数(这叫时间复杂度)。计算所需的存储单元数量(这叫空间复杂度)。27密码的强度依赖于构造密码算法问题的计算复杂度。但计算上困难的问题不一定就意味着密码算法的强度是足够安全的（复杂度和安全的不平衡）密码算法需要的是在不知道密钥的情况下解密是困难的问题，但是在知道密钥的情况下，解密应该是容易的。（依赖陷门信息的困难）(4)密码学28密码学发展:大体分三个阶段历史时期的古典密码学加密手段恺撒密码二战尤其是计算机出现以来的现代阶段

-Shannon公钥体系阶段

Diffie/Hellman、RSA2920世纪早期密码机30密码学发展在密码学的发展中，有一条原则就是秘而不宣。虽然历史上早就有密码学应用的痕迹，但是是一战刺激了其需求，而在二战中得到了充分发展和应用，并极大的影响了战争进程。1949年，Shannon关于保密系统通信理论的发表，奠定了密码学在公开领域研究的基础。然后是广泛商业应用的DES标准。1975年，Hellman和Diffie提出了公钥算法，这是现代密码学的里程碑。随后响应这一号召而提出的RSA算法，至今仍是当今网络安全的基石。此后，随着互联网络的发展，开创了密码学应用的新领域。31

Alice加密

E（P，K）＝C Bob解密

D（C，K）＝P

（1）函数公开，且一般D＝E

（2）K只有A、B知道（3）P明文，C为密文加密与解密32安全的问题1、D＝E＝XOR2、K是真随机的，且和P等长

One-timePad（一次一密）这个算法也是理论上安全的唯一的算法理论安全性只有当密钥和明文一样长时才能完全保密 即onetimepad计算安全性理论上并不完美，但在实践中难以攻破33密码学中两个加密方法（申农）Confusion混乱（替代）所谓混乱，是指在加密变换过程中是明文、密钥以及密文之间的关系尽可能地复杂化，以防密码破译者采用统计分析法进行破译攻击。混乱可以用“搅拌机”来形象地解释，将一组明文和一组密文输入到算法中，经过充分混合，最后变成密文。同时要求，执行这种“混乱”作业的每一步都必须是可逆的，即明文混乱以后能得到密文，反之，密文经过逆向的混乱操作以后能恢复出明文。Substitution替代密码 以掩盖明文和密文的关系34密码学中两个加密方法（申农）Diffusion扩散

所谓扩散，是指要将算法设计得使每一比特明文的变化尽可能多地影响到输出密文序列的变化，以便隐蔽明文的统计特性；扩散的另一层意思是将每一位密钥的影响也尽可能迅速地扩展到较多的输出密文比特中去。即扩散的目的是希望密文中的任一比特都要尽可能与明文、密文相关联，或者说，明文和密钥中任何一比特值得改变，都会在某种程度上影响到密文值的变化，以防止统计分析攻击。无扩散技术的加密

p1:00000000c1:00000010p2:00000001c2:00000011有扩散技术的加密

p1:00000000c1:01011010p2:00000001c2:1110101135如果把一封信锁在保险柜中，把保险柜藏在纽约的某个地方…，然后告诉你去看这封信。这并不是安全，而是隐藏。相反，如果把一封信锁在保险柜中，然后把保险柜及其设计规范和许多同样的保险柜给你，以便你和世界上最好的开保险柜的专家能够研究锁的装置。而你还是无法打开保险柜去读这封信，这样才是安全的。

36(5)基本概念和术语常规加密简化模型37(5)基本概念和术语Shannon保密通信模型38

基本概念

•密码学-研究加密技术的原理/方法（如何创建的秘密代码）•密码分析/密码破译-研究如何破译密文的原则/解密的方法。

-目的：评估此加密系统是脆弱•Kerkhoffs‘的原则-密码分析，假设敌手知道：加密/解密算法，但不知道密钥KEY。39破译是试图恢复明文或找出密钥的尝试唯密文攻击攻击者只有一些密文(目的：找明文，可能找密钥)已知明文攻击知道一些过去的(明文及其密文所用过的密钥)作参考和启发选择明文攻击特定明文进行加密，可得到密文（明密文的加密密钥）选择密文攻击有一台解密机（能使用解密密钥）密码分析的攻击类型40两个用户A,B,攻击者C[假设D(x1x2)=D(x1)D(x2)]41C随机选择rEB(r)EB(x)DB(EB(r)EB(x))rxC随机选择

rrxDB(EB(r)EB(x))EB(r)EB(x)41五元组（P，C，K，E，D）明文空间P 可能的明文的有限集密文空间C 可能的密文的有限集密钥空间K 可能的密钥的有限集对k∈K，决定一个加密规则ek∈E：P→C

和解密规则dk∈D：C→P，满足对明文x∈P

dk（ek（x））＝x密码体制42一个密码系统的特点是：

使用的加密类型

-替代/置换

密钥的使用

-单密钥（或对称）/双密钥（或公钥）

对明文的处理方式

-块（分组）/流43基本原则算法公开假设使用的算法和体制是公开的标准化：商用领域的互通性商用密码体制的安全依赖于密钥，而非算法密钥的随机性生成字典攻击dictionaryattack没有规律，不好猜蛮力攻击bruteforceattack密钥空间要大存储、传输、使用软件、硬件44密码算法分类：按照密钥的特点分类对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)

。公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥.解密密钥必须保密,又称私人密钥（privatekey)私钥.简称私钥。45单密钥加密技术密钥原文ABCD原文ABCD密文%#%￥密钥生成与分发密钥互连网络密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥原文ABCD原文ABCD密文%#%￥密文%#%￥原文ABCD密文%#%￥一个箱子一把锁，箱子运输锁上锁，关锁与开锁用一把钥匙，交换钥匙是关键，如何让钥匙不被窃取？双钥匙加密技术公钥（m,n=pq)私钥(r,p,q)原文ABCD原文ABCD密文%#%￥公钥(m,n=pq)乱文;~@‘互连网络密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘乱文;~@‘密文%#%￥乱文;~@‘原文ABCD原文ABCD密文%#%￥密文%#%￥原文ABCD密文%#%￥一个箱子一把锁，两把钥匙对付锁，一把关锁一把开锁，关锁的不能开锁，开锁的不能关锁，接收者提供钥匙，把关锁钥匙交给对方，开锁钥匙留给自己。密码算法分类：按照明文的处理方法分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流48安全性分类理论安全性one-timepad [P=?NP]P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE实际安全性计算安全性 成本大于解密所得利益(机时和耗电)

周期长于所需保密时间可证明安全性

RSA算法的安全性等价于大数分解?49无条件安全（Unconditionallysecure）无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.如：Onetimepad可证明安全性（provablesecurity）如果能证明挫败一个密码学方法跟某个著名的困难问题（如整数素因子分解、计算机离散对数）的困难程度相同，则称这个密码学方法是可证明安全的；计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期.密码体制评价50蛮力攻击bruteforceattack密钥空间 Mkey/s Gkey/s2^32 35.8分2^56 10^3年2^128 10^24年 10^18年计算安全性51（1）常用对称加密算法52DES和三重DES数据加密标准(DES)是加密方案中最广泛的应用使用64位明文块和56位密钥产生64位密文块关注算法及56位密钥的使用

三重DES将基本的DES算法重复三次使用两个或三个独立的密钥更加安全的同时速度变慢53高级加密标准(AES)DES的替代品1997年NIST公开征集的高级加密标准2001年被选为美国联邦信息处理标准作为FIPS197颁布——对称分组密码使用128位分组数据&128/192/256位密钥目前广泛的应用于商业54（2）消息认证防止主动攻击证明接收的消息是可信的内容未被篡改可靠的消息来源以正确的顺序及时发送利用对称加密的认证（共享密钥）只有发送方和接收方有共享密钥独立的认证机制（数字签名）附加信息来验证消息55消息认证码56消息认证57（3）公钥——加密58公钥——认证59公钥算法RSA(Rivest,Shamir,Adleman)产生于1977年被认为是使用最广泛的且被实现的公钥加密算法大概需要1024密钥长度Diffie-Hellman密钥交换算法用于共享密钥的交换数字签名标准(DSS)使用SHA-1提供了数字签名功能椭圆曲线密码(ECC)和RSA相比，使用更短的密钥长度得到相同的安全性60公钥证书612.2对称加密DES62古典密码思想替代和置换其技术、思想以及破译方法虽然很简单，但是反映了密码设计和破译的思想，是学习密码学的基本入口。替代substitution 把明文的比特模式替换成密文的比特模式置换transpostion（换位）打乱明文的顺序排列方式，即置乱63恺撒密码（替代）破译以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密码本）

ABCDEFGHIJKLMNOPQRSTUVWXYZ

defghijklmnopqrstuvwxyzabc64通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式置换652413×3421a 1213A a1213 Ab 2424B 即 b2424 Bc 3132C c3132 Cd 4341D d4341 D

a 1213 1224 1232 A 1241b 2424 2432 2441 B 2413c 3132 3141 3113 C 3124d 4341 4313 4324 D 4332（a－A） （b－B） （c－A） （d－A）abcd－ABAAa 2413 2424 2432 A 2441b 3124 3132 3141 B 3113c 4332 4341 4313 4324d 1241 1213 1224 1232（a－B） （b－A） （c－C） （d－A）abcd－BACAa 3113 3124 3132 3141b 4324 4332 4341 4313c 1232 1241 1213 1224d 2441 2413 2424 2432（b－B） （b－C） （a－D） （b－B）bbab－BCDBa 4313 4324 4332 4341b 1224 1232 1241 1213c 2432 2441 2413 2424d 3141 3113 3124 3132（a－A） （a－A） （c－D） （d－A）aacd－AADAa 1213 1224 1232 1241b 2424 2432 2441 2413c 3132 3141 3113 3124d 4341 4313 4324 4332（a－A） （b－B） （c－A） （d－A）abcd－ABAA 明文abcd

abcd

bbab

aacd

abcd

密文ABAABACABCDBAADAABAA4个字母的例子66DES及后来的许多分组密码设计中都充分体现了Shannon在1949年的论文中所提出的设计强密码的思想。

由简易实现的密码系统进行组合，构造复杂的、密钥量大的密码系统。Shannon曾给出两种组合方式，即概率加权法（分段）和乘积法（多次迭代）。

扩散（Diffusion）概念：将每一位明文及密钥尽可能迅速地散布到较多个密文数字中去，以便隐蔽明文的统计特性。

混淆（Confusion）概念：使明文和密文、密钥和密文之间的统计相关性极小化。使统计分析更为困难。现代密码与Shannon密码思想67对称加密算法分类分组密码算法（blockcipher）明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密分组一般为n＝64比特，或更长(Padding)密文分组和明文分组同样长对某个密钥可以构造一个明密文对照表Codebook(SubstitutionTable)所以分组的长，至少64比特才好密钥空间2^k<<可逆映射个数(2^n)!68对称加密算法分类流加密算法streamcipher每次可以加密一个比特适合：如远程终端输入等应用流密码的一类可用伪随机数发生器实现密钥做为随机数种子，产生密钥流keystream(不重复,或极大周期)

XOR(plaintext，keystream)One-timePad69流密码例：明文m=m1,m2,…….mk

伪随机序列k=k1,k2,…….kk

密文ci=miki,i=1,2,…….k解密过程与加密过程一致序列密码的安全性完全依赖于伪随机数的强度移位寄存器是产生序列密码的有效方法RC4、SEAL（SoftwareOptimizedEncryptionAlgorithm，软件优化加密算法）70分组加密与流加密比较基本区别粒度8字节分组vs.1比特或1字节各自适应不同的应用数据格式Padding（填充）对相同的明文分组，总是输出相同的密文分组； 而流密码却输出不同的密文比特流密码一般快很多分组密码多些，是主流分组密码也可以用作流模式7172（1）Feistel/DES加密框架明文分组的长n＝2w分左右两半L0R0密钥K产生子钥：K→k1，k2，…，kr

r是轮数，比如16轮⊕是异或函数XORp⊕x⊕x=p函数F是散列混乱函数可以是手工精心构造的查表函数73FeistelNetwork74Feistel–‘for’Loop加密计算序列

L0＝左半 R0＝右半

L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1) L3＝R3

R3＝L2⊕F(k3,R2) … Li＝Ri-1

Ri＝Li-1⊕F(ki,Ri-1) …

Ln＝Rn-1

Rn＝Ln-1⊕F(kn,Rn-1)

密文即（Ln，Rn）解密计算75Feistel

加密/解密续下页76接上页772轮加解密举例假设n＝2轮，C＝（L2，R2） 加密 明文＝半＋半＝L0+R0 L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1)解密 密文＝半＋半＝L2＋R2 R1＝L2 L1＝R2⊕F(k2,R1) R0＝L1 L0＝R1⊕F(k1,R0)

明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L078Feistel–特征分组大小密钥大小循环次数一般仅几轮是不够的，得十几轮才好，如16轮子钥产生算法越复杂越好轮函数Round关键其他考虑速度（尤其是软件实现的速度）便于分析（使用简洁的结构）79Feistel类算法举例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel结构的AES、IDEA*绝大数分组密码属于或类似Feistel结构多轮每轮有XOR（或能恢复的操作）轮函数80DES加密算法的背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功。基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效。（2）数据加密标准DES81DES特点分组大小SIZE=64bits密钥大小SIZE=56bits轮数=16轮16个子密钥=48bits82DES的描述DES是一种分组对称加密算法，输入的明文为64位，密钥64位（实际可用密钥长度为56位），生成的密文为64位；83DataEncryptionStandard（DES）DES同时用到了换位（置换）和替代参数Feistel体制分组密码分组大小64bit，密钥大小56bit，轮数16轮S-Boxes 84DESEncryption

OverviewPC-1PC-2连接PC-1连接PC－2连接初始置换Round1/31/202385Key:PermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成为C0D0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263641/31/202386Key:PermutedChoiceTwo(PC-2)14171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入选的：9、18、22等每轮从56比特中选取48比特即为Ki，并同时左移Roundnumber12345678910111213141516Bitsrotated11222222122222211/31/202387Keyi48bit28×21/31/20238858504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157IP&IP-18×81在第40比特位置40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddeven1/31/202389Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代1/31/202390RoundKi48bit1/31/202391ExpansionPermutation3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit两边的是重复选中的6×81/31/202392RoundFunction6×84×81/31/202393S-Boxes：1-4两边2比特选择行号中间4比特选择列号1/31/202394S-Boxes：5-81/31/202395PermutationFunctionP16720212912281711523265183110282414322739191330622114258×4从S盒出来后重排1/31/202396DESEncryption

Review置换……1/31/202397OneSamplep=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB4051/31/202398DES（64位）已经破译DES算法仍值得信赖但是关键场合不要用DES对一般个人用户仍是安全的RSAchallenge反而给了信心DES还是AES，或者其他DES模块仍广泛存在，AES还没有普及如果软件实现，任何一个经过考验的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open99DES总结DES算法本身没有大的缺陷对DES攻击方法复杂度为2^47DES使用的2^56密钥空间不够大蛮力攻击目前已能够奏效(DESChanllengeIII)DES已经不再是推荐标准AESDES模块仍广泛存在保护和延续投资对DES的改造使用现存的软件硬件在强度上提高100DESModesofOperation

-FIPS81

DESbasicfunction:

DES(IN,Key,Enc/Dec)=OUTKey56bits(randombits!)Enc -IN64bitsplaintextblock -OUT64bitsciphertextblockDec -IN64bitsciphertextblock -OUT64bitsplaintextblock101

ApplyDEStwiceusingtwokeys,K1andK2.C=EK2[EK1[P]]P=DK2[DK1[C]]双重DES可以是密钥空间增大，Thisleadstoa2x56=112bitkey,soitismoresecurethanDES.Isit?Goal:giventhepair(P,C)findkeysK1andK2?中间人攻击102分组密码的工作模式：（1）电码本（ECB）（2）密码分组链接（CBC）（3）密码反馈（CFB）（4）输出反馈（OFB）（5）计数器（CTR）103104分组密码的工作模式（1）电码本模式（ECB）：用相同的密钥分别对64位明文组加密，报文被顺序分割分成8字节分组各个分组独立加密，解密时需等齐整个分组填充典型应用：单个数据安全传输105（1）FigureECB106（2）CBC:CipherBlockChaining

密码分组链接方式

当前明文分组先和前一个密文异或，再加密初始向量IV－initializationvector IV不必保密，但必须一致*优点避免明密对应还可以用做鉴别authentication*缺点等待缓冲区凑足8字节分组，否则需padding不能并行加密、随机存取107108CFB:CipherFeedback

密码反馈方式IV64bit，IV用Key加密得到RIV不必保密，但是必须相同明文s比特，与R的高位s比特XOR，得密文s比特s比特的密文同时从R的低位进入，挤掉R的高位的s比特*优点流密码streamcipher也有校验的效果109110CTR:CounterMode 计数方式（也是一种流方式应用）重复加密初始counter＋＋，得密钥流明文与之XOR优点适合随机存取*注意：Counter的初值须不能预测111112使用常规加密进行保密通信易受攻击的位置113链路加密和端到端加密114链路加密在一段同质线路的两端链路两端分别设置加密设备(硬件)要求所有线路段上都加密才行可以加密整个包【目的地址＋源地址＋控制＋数据＋校验】但是在路由器中可解密成明文*位于第一二层即物理层和数据链路层*对于在两个网络节点间的某一次通信链路,链路加密能为网上传输的数据提供安全保证所有消息在被传输之前进行加密,在每一个节点对接收到的消息进行解密,然后先使用下一个链路的密钥对消息进行加密,再进行传输115端到端加密端到端加密存在于两个程序进程之间只是在源和目的两端架设保密设备只能加密有效[数据]载荷部分适合公共商用网*因此不能避免流量分析*位于在3＋层网络层VPN、传输层SSL、应用层PGP*适合分散用户如一般的个人、公众、商业应用等116端到端加密端到端加密允许数据在从源点到终点的传输过程中始终以密文形式存在采用端到端加密(又称脱线加密或包加密),消息在被传输时到达终点之前不进行解密,因为消息在整个传输过程中均受到保护,所以即使有节点被损坏也不会使消息泄露117Linkvs.End-to-end118Applayervs.Linklayer1192.3公钥密码学120密码学重要进步从Rotor到DES

在对称密钥体制中，加密与解密使用同一密钥，因此在公网上传送和管理密钥是一个严峻问题。NewDirectionsinCryptography

WhitfieldDiffie，Hellman1976提出了公钥密码算法的概念和思路提出了鉴别和签名问题提出了D-H密钥协商协议121公钥密码算法的思路对称算法的缺陷为事先协商密钥，需另外的安全信道或KDC不能满足签名的需求非对称算法密钥K＝（Kd，Ke），Kd即私钥Ke即公钥加密：E（P，Ke）＝C解密：D（C，Kd）＝P要求从Ke

Kd理论上能够 实际上需要计算量太大因而很难122公钥密码算法的实现基于某些数学特性从公钥推导私钥理论可能，但计算困难

(从私钥到公钥容易)单向函数(one-wayfunction)123One-wayFunction单向性单向函数函数函数值计算很容易：已知x，很容易计算y=f(x)逆计算是不可行的：已知y，很困难计算x=f-1(y)困难程度举例打碎/拼接、平方/开方、乘法/分解*单向函数存在否尚无严格的数学证明124TrapdoorOne-wayFunction单向陷门函数如果知道某个陷门(秘诀)，即能容易恢复x（陷门即为私钥）举例魔方的置乱/恢复如果有那个口诀，就能很快恢复加密/解密125公钥算法参数建立及加解密每个用户生成密钥对(Ke、Kd)Ke或Kd是一个或几个数(大数)Ke需要公开Kd得自己秘密保留(公钥publickey私钥privatekey密钥secretkey)公钥的发布从Ke推导Kd的困难性使Ke不怕被公开公开的目录服务公钥Ke要在专门机构（CA）登记126加密系统解密系统明文(P)乙方公钥乙方密钥密文(C)明文(P)甲方乙方加密（如果有人要给该用户发送消息P）先获得该用户的公开钥Ke加密C=E（P，Ke）传输解密D（C，Kd）＝P除非拥有Kd，否则不能解开*一般用于传输会话密钥（和签名及鉴别）127公钥算法用来加密图示128消息来源认证和数字签名公钥不仅可用于加密，还能提供数据和消息来源的认证（RSA）对消息H签名：

S=Sig（H，Kd）验证

Ver（C，Ke）＝？H

消息H必然是Kd的持有人签署的129公钥算法用来认证图示130具有机密性与认证性的公钥体制131RSA算法由MIT的Rivest,Shamir&Adleman

在1977提出，R,S,ARonRivest

http:///~rivest/AdiShamir http://www.wisdom.weizmann.ac.il/~shamir/LenAdleman

http:///dept/molecular-science/基本参数分组密码算法基于整数乘法明/密文分组以及公/私钥被看作小于n的整数加/解密是模乘运算132RSA参数建立选择素数选取两个512bit的随机素数p,q计算模n和Euler函数φ(n)n＝pq

φ(n)=(p-1)(q-1)选取一个与φ(n)互素的整数e<n找ed≡1modφ(n)用扩展Euclid算法求数d发布发布(e,n)，这是公钥ked保密，(d,n)是私钥kd133RSA加密解密加密明文分组m做为整数须小于n c=memodn解密

m=cdmodn134RSA实例选p＝7，q＝17则n＝pq＝119且φ(n)＝(p-1)(q-1)＝6×16＝96取e＝5则d＝77(5×77＝385＝4×96＋1≡1mod96)公钥（5，119），私钥（77，119）加密m＝19则c＝memodn=195mod119=66mod119解密c＝66m＝cdmodn=6677mod119＝19mod119135RSA考虑必须做到确定两个大素数：

p,q

选择e或者d，并计算d或者e素数测试是重要的算法必须够大，否则对手可能很快分解n判定，试除法不可行判定，采用Miller-Rabin概率测试方法强素数：(p-1)/2和(q-1)/2应是素数由e求d要使用到扩展Euclid算法选取较小的e（较大的d）：e：3、65537快速计算X^Y%Z136RSA考虑必须做到确定两个大素数：

p,q

选择e或者d，并计算d或者e素数测试是重要的算法必须够大，否则对手可能很快分解n判定，试除法不可行判定，采用Miller-Rabin概率测试方法强素数：(p-1)/2和(q-1)/2应是素数由e求d要使用到扩展Euclid算法选取较小的e（较大的d）：e：3、65537快速计算X^Y%Z137RSA中基本计算的复杂度大数的加、减计算复杂度O(k),O(k) {字加法}K是大数的字宽度大数的乘、除(逆元)计算复杂度O(k2),O(k2logk) {字乘法}大数指数运算xcmodnO(k2logc) {字乘法}注：都是在modn下138攻击RSA枚举枚举所有可能明文m，用e加密和c比较枚举所有可能的私钥d（已知明文）数学方法分解n=pq，就可以计算φ(n)，就可从e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d大家相信：由n确定ø(n)等价于因子分解139Diffie-HellmanD-H方案提供两个用户生成共享密钥，是基于离散对数问题。步骤：选取大素数q和它的一个公共的生成元g，这些参数公开A选择随机数Xa，B选择随机数Xb

A计算Ya＝g^Xamodq，B计算Yb＝g^Xbmodq交换Ya，YbA计算K＝Yb^Xamodq，B计算K'＝Ya^Xbmodq事实上，K＝K'140分析（别人怎么计算K?）：别人看到了Ya和Yb，但需要计算Xa或Xb，即要算离散对数

Ya＝g^Xamodq，或Yb＝g^Xbmodq

从公钥计算出对应私钥也是计算上不可行的。141Diffie-Hellman的例子A，B一起选择了q=53,g=17步骤：A，B分别选择秘密密钥XA=5,Xb=7

A计算公钥Ya＝gXamodq=40，B计算公钥Yb＝gXbmodq=6交换Ya，YbA计算共享密钥K＝Yb^Xamodq=38，B计算共享密钥K'＝Ya^Xbmodq=38K＝K'142对称算法vs.公钥算法安全性（下屏）速度典型相差1000倍密钥管理对称算法需要额外安全信道公钥：证书中心CA混合密码体制公钥算法用于签名和认证用公钥算法传输会话密钥用会话密钥/对称算法加密批量数据143

对称密码vs.

公钥密码一般要求：1、加密解密用相同的密钥2、收发双方必须共享密钥安全性要求：1、密钥必须保密2、没有密钥，解密不可行3、知道算法和若干密文不足以确定密钥一般要求：1、加密解密算法相同，但使用不同的密钥2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥安全性要求：1、两个密钥之一必须保密2、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥1442.4密钥管理145密钥产生与分配一方产生，传递到另一方另外的安全信道，如面对面、电话、信函、信使等如果从前有一旧密钥，可以借以传递新密钥有中心的可通过第三方中心转交(或中心产生,分发给双方)中心可能和用户有各自的通信密钥分布式秘密计算使用不安全信道协商计算密钥(DH密钥协商协议)146交换密钥：是与某个通信参与者相关联的密钥（与身份相关）。会话密钥（sessionkey

）：是与通信本身相关联的密钥（与实体身份无关）。密钥仅用于加密传输数据。1471、对称密钥的管理148密钥传递问题密钥的管理：主要手段是密钥传递，是通过秘密信道进行。秘密信道：（1）派遣专递人员将密钥送到对方。（2）数据的机密性不是很高，可通过邮递系统传送密钥（银行和信用卡中心在给客户传送口令时就是通过这种方式）。（3）秘密专用电缆用作秘密信道。问题：既然存在用于传递密钥的秘密信道，为什么不直接通过该秘密信道传递数据呢？只有（3）

秘密信道并不保证信息的机密性149传递密钥的秘密信道一般不适合用于直接传递机密信息。内容需要保护的数据量远远大于密钥量，而秘密信道传送数据的代价要比公开信道高很多。密钥的传递一般在秘密通信开始前进行，可以容忍较长时间的延迟，而对保密数据的传输，一般不能容忍长时间延迟。密钥传递实际问题：假定有n个用户需要在两两之间建立一个共同密钥，由于保密的原因，这些密钥应该互不相同，那么需要建立n(n+1)/2个不同的密钥（不包括更新）。如何利用公开信道传递密钥：Diffie-Hellman

1502、Diffie-Hellman密钥协商交换协议通信相互传递部分信息，再分别根据对方的部分信息计算出秘密信息，使得双方计算结果相同，而攻击者却不能根据所截获的信息计算出这个秘密信息，于是就达到了密钥传递的目的。这种方法不是密钥传递，而是密钥协商，最终得到的密钥不是某一方选取的，而是根据双方选取的随机数产生的。151DH76，Diffie-Hellman步骤选取大素数q和它的一个生成元g，这些参数公开A选择随机数Xa，B选择随机数Xb

A计算Ya＝g^Xamodq，B计算Yb＝g^Xbmodq交换Ya，YbA计算K＝Yb^Xamodq，B计算K'＝Ya^Xbmodq事实上，K＝K‘其困难程度被认为等同于求解有限域上的离散对数问题。152证明、分析和例子证明K＝K’ K＝Yb^Xamodq K’＝Ya^Xb modq

＝(g^Xb)^Xamodq ＝(g^Xa)^Xbmodq

＝g^(XbXa)modq ＝g^(XaXb)modq举例q＝97，g＝5 A选Xa＝36，B选Xb＝58，则

Ya＝5^36％97＝50，Yb＝5^58％97＝44