第2讲密码学简介

第2讲密码学简介苏兆品主要内容1加密技术2数字签名3密钥管理1加密技术密码学的基本概念传统密码学对称密码学公钥密码学

密码体制密码学中的安全可能的攻击手段现代密码学的基本原则1.1密码学的基本概念一密码体制1.明文(Plaintext):须加密的消息或数据，是加密算法的输入。2.密文(Ciphertext):加密之后的数据，是加密算法的输出。3.密钥(Key)：加密或解密的参数。不同的密钥，会有不同的输出结果。一密码体制（续）4.加密(Encryption)：将明文变成密文的过程。C=EK(P)，K是密钥，P是明文，C是密文，E是加密算法。5.解密(Decryption)：将密文恢复成明文的过程。P=DK(C)，D是解密算法。一密码体制（续）EDC=EK1(P)P=DK2(C)K1K2不安全的信道AliceBob(发送方)(接收方)TRUDY(第三方，窃听者)K1=k2，对称密码体制K1

k2，非对称密码体制二密码学中的安全1.无条件安全（UnconditionalSecure)无论截获多少密文，都不能得到足够的信息唯一地决定明文。2.计算上安全（ComputationallySecure)在有限的资源内，不能通过系统分析的方法破解系统。3.理论上安全（PerfectSecure)Shannon:加密密钥长度和明文一致，密钥只能用一次（one-time-pad，OPT，一次一密密码）4.实际上安全（PracticalSecure)Shannon:给定一个n位的密文，必须有一个最小的工作时间来破解系统。这个时间为W(n)。当n趋于无穷时，w(n)w(∞)。当n大到一定程度，攻击者在合理的时间内无法破解此系统。三可能的攻击手段密码分析学是在不知道密钥的情况下，恢复出明文的科学。密码分析也可以发现密码体制的弱点。攻击的目的获取密钥常用的密码分析方法：三可能的攻击手段（续）1.仅知道密文攻击Trudy仅能得到一份密文的拷贝。2.已知明文攻击Trudy不仅有一份密文的拷贝，还有对应的明文3.选择明文攻击Trudy临时获取了加密的机器，她可以通过加密大量挑选出的明文，然后试着利用其产生的密文来推测密钥。4.选择密文攻击Trudy临时获得了用来解密的机器，利用它去“解密”几个符号，并利用可能结果推测出密钥。四现代密码学的基本原则设计加密系统时，总是假设密码算法是公开的，需要保密的是密钥。1.2传统密码学移位密码仿射密码代换密码置换密码一移位密码加密算法c=Ek(m)=(m+k)modq解密算法m=Dk(c)=(c-k)modq代表算法恺撒密码;例：(k=3)明文meetmeaftertheparty密文phhwphdiwhuwkhsduwb

二仿射密码加密算法c=Ek(m)=(am+b)modq解密算法m=Dk(c)=(c-b)/amodq密钥K=(a,b)

二仿射密码（续）举例设密钥K=(7,3),明文hot三个字母对应的数值是7、14和19。分别加密如下：

(7×7+3)mod26=52mod26=0

(7×14+3)mod26=101mod26=23

(7×19+3)mod26=136mod26=6三个密文数值为0、23和6，对应的密文是axg。三单表代换密码定义：密文是26个字母的任意置换,密钥是明文字母到密文字母的一个字母表.密钥明文iamaboy密文af…缺点：不能抵抗明文统计特性的攻击abcdefghijk…fzlxbhtwado…四多表代换密码(维吉尼亚密码）密钥K＝（

k1,k2,…,km)加密算法：Ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=c解密算法：Dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=m这里的所有的运算都是在（mod26)中进行的。四多表代换密码(续）密钥为:deceptive;明文：wearediscoveredsaveyourself密钥：deceptivedeceptivedeceptive密文：zicvtwqngrzgvtwavzhcqyglmgj五置换技术最简单的为栅栏技术以对角线顺序写下明文，以行顺序读出例：明文：meetmeaftertheparty深度为2的栅栏技术可写为：

mematrhpry

etefeteat密文为：mematrhpryetefeteat现代密码设计基本思想混乱(confusion)：即在加密变换过程中使明文、密钥及密文之间的关系复杂化。用于掩盖明文和密文间的关系。散布(diffusion)：即将每一位明文信息的变化尽可能地散布到多个输出的密文信息中，即改变一个明文尽可能多的改变多个密文，以便隐蔽明文信息的统计特性。单独用一种方法，容易被攻破。1.3对称密码学1.3对称密码学（续）对称密码学分类流密码（序列密码）每次一位地对明文进行操作和运算流密码只依赖于混乱块密码（分组密码）一次若干位一组地对明文进行操作和运算分组密码使用混乱和散步1.3对称密码学（续）流密码RC4混沌密码块密码-DES一RC4算法设计者：RonRivest设计时间：1987年公开时间：1994密钥：支持可变的密钥长度（通常为256位）速度：快原理：初始化算法伪随机子密码生成算法一RC4算法（续）初始化算法一RC4算法（续）伪随机子密码生成算法应用：无线通信网络安全分析存在部分弱密钥，在不到100万字节内就发生了完全的重复使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。二混沌密码什么是混沌？混沌（Chaos）是非线性动力系统中出现的一种确定性的、貌似无规则的运动，它不需要附加任何随机因素也可以出现类似随机的行为，即存在内在随机性，这种运动既非周期又不收敛，并且对初始值有极其敏感的依赖性。特征：类随机性：由确定性方程产生的，初始状态决定混沌信号序列就可以精确地再生长期不可预测性举例：随机性实验--掷硬币初值敏感性失之毫厘，差之千里遍历性典型的混沌系统Logistic映射即虫口模型，它是目前研究非常广泛的一种混沌映射。意义可解释为：在某一范围内单一种类的昆虫繁殖时，其子代数量远远大于其亲代数量，这样可以认为，在子代出生后，其亲代的数量可忽略不计。设xn是某种昆虫第n年的个体数目，这个数目与年份有关，n只取整数值，第n+1年的数目为xn+1。其中，0≤x≤1，μ为控制参数，0<μ≤4。当0<μ≤1时，序列会最终收敛于0。当1<μ≤3时，定常解为0和11/μ，多次迭代后序列会收敛于这两个值中的一个。当3<μ≤4时，系统由倍周期通向混沌。而且μ取值越接近4，混沌性越强。Arnold变换遍历理论又被称为猫脸变换。原理：Cat映射可以把图像中各像素点的位置进行置换，使其达到加密的目的

modN当a=b=1，N=1时，Cat映射的方程可写为：思想：拉伸和折叠。Cat映射通过与矩阵C相乘使x、y都变大，相当于拉伸；取模运算使x、y又折回单位矩形内，相当于折叠。单位矩阵内的每一点唯一地变换到单位矩阵内的另一点。Cat映射可以用于图像置乱加密，而且基于Arnold的Cat图像置乱也是目前研究最为广泛的一种置乱方案。分析：适合于图像信息的加密周期性问题课后阅读A5序列密码算法分析三DES算法数据加密标准（DataEncryptionStandard）1976年被美国联邦政府的国家标准局确定为联邦资料处理标准，随后在国际上广泛流传开来。DES的过程初始置换IP64位明文第一轮第16轮32位互换逆初始置换IP-164位密文置换选择PC-164位密钥循环左移循环左移置换选择PC-2K1置换选择PC-2K16DES的安全性密钥长度不够（56位+8位奇偶校验）存在弱密钥密钥为0，1时若k1=k2=…=k16

，则DESk(m)=DESk-1(m)S-box问题S盒是不公开的，人们怀疑S盒的构造方法是否有弱点不能抗差分分析对称密码体制小结规模复杂进行安全通信前需要以安全方式进行密钥交换。提供数据的机密性，不能用于认证。1.4公钥密码学公钥密码体制RSA算法公钥密码和与对称密码的区别和应用场合?是否前者更加安全?问题一公钥密码体制每方均有2个密码公钥私钥功能保密认证一公钥密码体制（续）1、保密加密：C=Ekub(P)用接收方的公钥加密解密：P=DKRb(C)用自己的私钥解密TrudyAliceEDBob密钥对C=Ekub(p)KubpP=DkRb(c)KRbP=?kRb=?一公钥密码体制（续）2、认证签名：C=Ekra(P)

用自己的私钥签名验证：P=DKua(C)

用发送方的公钥验证AliceED密钥对PC=Ekra(P)P=DKua(C)Bobkrakua2.1.4.1公钥密码体制（续）AliceED密钥对源PC’=EkRa(P)C=DKua(C’)BobkRakuaEC=Ekub(C’)DC’=DkRa(C)密钥对源kubkRb发送方：C=Ekub[Ekra(p)]

先用自己的私钥签名，再用接收方的公钥加密接收方:P=Dkua[Dkrb(C)]用自己的私钥解密，再用发送方的公钥验证3、既认证又保密（先签名后加密）主要应用加密/解密数字签名密钥管理二RSA算法1、背景1976年Diffie和Hellman指出新的密码学方法（公钥体制）定义1.单向函数f,已知x计算y=f(x)容易，但给定y,求x=f-1(y)非常难。定义2.单向陷门函数ft，已知x计算y=f(x)容易。不知参数t的情况下，计算x=f-1(y)难，但知道t，计算x=f-1(y)易。背景(续)1978年，Rivest,Shamir和Adleman提出。基于“大数分解的素数检测”基础上。已知大素数p和q，求n=p*q容易，但反过来，知道大数n，分解出素数p和q困难。算法描述密钥产生选择p,q，使得p,q是素数，且p≠q计算n=p×q计算t=(p-1)×(q-1)

选择整数e,使得gcd(t,e)=1(1<e<t)计算d,使得e*d=1modt公钥KU={e,n},私钥KR={d,p,q}算法描述(续)加密C=C=MemodN,其中0≤M<N解密M=CdmodN举例找两个素数：p=47，q=59n=p*q=2773t=(p-1)*(q-1)=2668取e=63，满足e<t并且e和t互素计算d,使得e*d=1modt，d=847公钥KU={e=63,n=2773},私钥KR={d=847,p=47,q=59}设消息M=244，对此进行认证，用私钥加密，公钥解密加密：c=M**d%n=244**847mod2773＝465解密：m=c**e%n=465**63mod2773=2442数字签名

数字签名的概念利用RSA密码实现数字签名

数字签名和认证有何区别和联系？问题2.1数字签名概念日常生活中的签名，盖章数字签名满足的条件签名者事后不能抵赖自己的签名任何其他人不能伪造签名如果当事人双方关于签名的真伪发生争执，能够在公正的仲裁者面前通过验证来确认其真伪。2.1数字签名概念（续）需要解决的问题A如何在文件M上签名？B如何验证A的签名真伪？A如何鉴别别人伪造自己的签名？B如何阻止A签名后又抵赖？数字签名过程签名：SA=D(M,KdA)=(MdA)modn

用自己的私钥签名验证：E(SA，keA)=(MdA)eAmodn=M

用发送方的公钥验证AliceED密钥对PC=Ekra(P)P=DKua(C)Bobkrakua2.2利用RSA密码实现数字签名RSA的选择密文攻击TRUDY要伪造A对M3的签名，容易找M1和M2，使得

M3=M1*M2modn设法让A对M1和M2进行签名S1=(M1)dAmodnS2=(M2)dAmodnTURDY可以伪造：（S1S2)modn=((M1)dA(M2)dA)modn=(M3)dAmodn=S3主要措施有两条采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名决不对陌生人送来的随机文档签名RSA数字签名的应用PGP(PrettyGoodPrivacy)相当好的隐私，是PGP公司的加密和／或签名工具套件加密：IDEA算法；签名：RSA免费3密钥管理密钥的重要性（不言而喻）近代密码学的基本原则主要内容传统密码体制的密钥管理公开密钥体制的密钥管理3.1密钥管理原则密钥管理一般来说，从密钥管理途径进行攻击比单纯破译密码算法的代价小得多。因此，引入密钥管理机制，进行有效的控制，对于提高网络及系统的安全性和抗攻击性非常重要全程安全原则密钥的产生、存储、分配、组织、使用、停用、变换、更新和销毁的全过程3.1密钥管理原则（续）最小权利原则指“应当只分发给用户进行某一事务处理所需的最小的密钥集合"。包括2个含义：一方面给予主体“必不可少”的特权，这就保证了所有的主体都能在所赋予的特权之下完成所需要完成的任务或操作；另一方面，它只给予主体"必不可少"的特权，这就限制了每个主体所能进行的操作。3.1密钥管理原则（续）责任分离原则一个密钥应当专职一个功能，不要让一个密钥兼任几种功能密钥分级原则主密钥，二级密钥，初级密钥高级密钥保护低级密钥好处：可减少保护密钥的数量，又可简化密钥的管理工作密钥更换原则密钥必修按时更新：即使是采用很强的密码算法，使用时间越长，攻击者获得的密文越多，破译密码的可能性越多最理想的是一个密钥只使用一次（一次一密）密钥应当有足够的长度密码安全的必要条件是密钥有足够的长度。密钥越长，密钥空间越大，破译的可能性越小密码体制不同，密钥管理也不相同传统密码体制与公开密码体制性质不同，密钥管理也不同3.2

传统密码的密钥管理1、密钥组织：将密钥分为三级：初级密钥二级密钥主密钥(高级密钥)高级密钥二级密钥初级密钥①初级密钥我们称直接用于加解密数据(通信，文件)的密钥为初级密钥，记为K。其中:用于通信保密的初级密钥为初级通信密钥，并记为Kc

。称用于保护会话的初级密钥为会话密钥(SessionKey)，记为Ks

。称用于文件保密的初级密钥为初级文件密钥(FileKey)，记为Kf

。说明：初级密钥可通过硬件或软件方式自动产生，也可由用户自己提供。初级通信密钥和初级会话密钥原则上采用一个密钥只使用一次的“一次一密”方式。初级通信密钥的生存周期很短。初级文件密钥与其所保护的文件有一样长的生存周期。初级密钥必须受更高一级的密钥保护，直到它们的生存周期结束为止。二级密钥(SecondaryKey)用于保护初级密钥，记作KN，这里N表示节点，源于它在网络中的地位。当二级密钥用于保护初级通信密钥时称为二级通信密钥，记为KNC。当二级密钥用于保护初级文件密钥时称为二级文件密钥，记为KNF。②二级密钥二级密钥可经专职密钥安装人员批准，由系统自动产生。可由专职密钥安装人员提供。二级密钥的生存周期一般较长，它在较长的时间内保持不变。二级密钥必须接受更高级的密钥的保护。主密钥(MasterKey)是密钥管理方案中的最高级密钥，记作KM。主密钥用于对二级密钥和初级密钥进行保护。主密钥由密钥专职人员随机产生，并妥善安装。主密钥的生存周期很长。③主密钥对密钥的一个基本要求是要具有良好的随机性：长周期性、非线性、等概性以及不可预测性等。一个真正的随机序列是不可再现的。任何人都不能再次产生它(真随机)高效地产生高质量的真随机序列，并不是一件容易的事。2、密钥产生①主密钥的产生主密钥应当是高质量的真随机序列。真随机数应该从自然界的随机现象中提取。基于力学噪声源：利用硬币、骰子等抛散落地的随机性产生密钥。例如，用1表示硬币的正面，用0表示硬币的反面，选取一定数量随机地抛撒并纪录其落地后的状态，便产生出二进制的密钥。这种方法效率低，而且随机性较差。基于电子学噪声源：利用电子方法对噪声器件（如真空管、稳压二极管等）的噪声进行放大、整形处理后产生密钥随机序列基于混沌理论：混沌理论的方法，不仅可以产生噪声，而且噪声序列的随机性好，产生效率高两种方法：第一种方法：可以象产生主密钥那样产生真随机的二级密钥。在主密钥产生后，可借助于主密钥和一个强的密码算法来产生二级密钥。第二种方法：用产生主密钥的方法产生两个真随机数RN1，RN2，再产生一个随机数RN3，然后分别以它们为密钥对一个序数进行四层加密，最后产生出二级密钥KN

。

KN＝E(E(E(E(i，RN1)，RN2)，RN1)，RN3)

要想根据序数i预测出密钥KN，必须同时知道两个真随机数RN1，RN2和一个随机数RN3，这是极困难的。②二级密钥的产生③初密钥的产生为了安全和简便，通常总是把随机数直接视为受高级密钥加密过的初级密钥：

RD＝E(Ks，KM)或RD＝E(Kf，KM)，

RD＝E(Ks，KNC)或RD＝E(Kf，KNF)。使用初级密钥时，用高级密钥将随机数RN解密：

Ks＝D(RD，KM)或Kf＝D(RD，KM)，

Ks＝D(RD，KNC)或Kf＝D(RD，KNF)好处：安全，一产生就是密文。 方便二级密钥和初级密钥的产生都需要伪随机数。伪随机性：长周期，均匀分布，独立性，非线性一般采用基于强密码算法的产生方法（DES，AES）ANSIX9.17（基于3DES）

④伪随机数的产生ANSIX9.17密钥产生的过程V0是一个秘密的64bit种子时间戳随机密钥(64bit)对于128位和192位密钥，可以通过上法生成几个64位的密钥后，串接起来即可2、密钥分配密钥分配自古以来就是密钥管理中重要而薄弱的环节。过去，密钥的分配主要采用人工分配。现在，应当利用计算机网络实现密钥分配的自动化。①主密钥的分配一般采用人工分配主密钥，由专职密钥分配人员分配并由专职安装人员妥善安装。由专职密钥分配人员分配并由专职安装人员安装。虽然这种人工分配和安装的方法很安全，但是效率低。另一种方法是直接利用已经分配安装的主密钥对二级密钥进行加密保护，并利用计算机网络自动传输分配。两种方案：②二级密钥的分配C=E(KNC,KM)KNC=D(C,KM)主密钥KM主密钥KM网络信道C发端收端方案1产生KNC产生RNKNC=D(RN,KM)主密钥KM主密钥KM网络信道RN发端收端KNC=D(RN,KM)RN方案2③初级密钥的分配通常总是把一个随机数直接视为是二级密钥）加密过的初级密钥，这样初级密钥一产生便成为密文形式。发端直接把密文形式的初级密钥通过计算机网络传给收方，收端用高级密钥解密便获得初级密钥。产生随机数RN接受随机数RN二级密钥KN二级密钥KNKC=D(RN,KN)KC=D(RN,KN)KCKC网络信道RN发端收端3、密钥的存储密钥的安全存储就是要确保密钥在存储状态下的秘密性、真实性和完整性。安全可靠的存储介质是密钥安全存储的物质条件，安全严密的访问控制是密钥安全存储的管理条件。密钥安全存储的原则是不允许密钥以明文形式出现在密钥管理设备之外。密钥的存储形态有以下几种：明文形态：明文形式的密钥。密文形态：被密钥加密密钥加密过的密钥。分量形态：密钥分量不是密钥本身，而是用于产生密钥的部分参数。①主密钥的存储主密钥是最高级的密钥，所以它只能以明文形态存储，否则便不能工作。要求存储器必须是高度安全的，物理上是安全的，而且逻辑上也是安全的。通常是将其存储在专用密码装置中。②二级密钥的存储二级密钥可以以明文形态存储，也可以以密文形态存储。如果以明文形态存储，则要求存储器必须是高度安全的。如果以密文形态存储，则对存储器的要求可适当降低。通常采用以高级密钥加密的形式存储二级密钥。这样可减少明文形态密钥的数量，便于管理。③初级密钥的存储初级文件密钥和初级会话密钥是两种性质不同的初级密钥，因此其存储方式也不相同。初级文件密钥的生命周期与受保护的文件的生命周期一样长。因此初级文件密钥需要妥善的存储。一般采用密文形态存储，通常采用以二级文件密钥加密的形式存储初级文件密钥。初级会话密钥按“一次一密”的方式工作，使用时动态产生，使用完毕后即销毁，生命周期很短。因此，初级会话密钥的存储空间是工作存储器，应当确保工作存储器的安全。3.3公开密码体制的密钥管理与传统密钥的区别传统密码体制只有一个密钥，加密钥等于解密钥，故密钥的秘密性、真实性和完整性都必须保护。公开密码体制中密钥有两个，加密钥不等于解密钥，加密钥可以公开加密钥（公钥）的完整性和真实性要严格保护(为什么？)解密钥（私钥）的秘密性，完整性和真实性都要保护一公开密码体制的密钥产生传统密码体制的密钥本质是一个随机数，故对随机性的要求较高公开密钥密码体制本质是一个单向陷门函数，是建立在数学难题基础上的，密钥必须满足该数学难题的要求公开密钥密码的密钥产生（续）RSA密码体制（回忆）秘密钥p,q,d,公开钥n,e要求p和q至少有512位p和q钥随机产生p和q的差要大

(p-1)和(q-1)的最大公因子要小e和d不能太小二公开密码体制的密钥分配和传统密码一样，公开密码体制也需要进行密钥分配。但是，公钥密码的密钥分配与传统密码体制的密钥分配有着本质的差别。对于私钥：分配时必须确保秘密性、真实性和完整性。对于公钥：公开的，因此不需确保秘密性，却必须确保真实性和完整性，绝对不允许攻击者替换或篡改用户的公钥。如果公钥的真实性和完整性受到危害，则基于公钥的各种应用的安全将受到危害。C冒充A欺骗B的攻击方法：①攻击者C在PKDB中用自己的公钥KeC替换用户A的公钥KeA

。②C用自己的解密钥签名一个消息冒充A发给B。③B验证签名：因为此时PKDB中A的公开钥已经替换为C的公开钥，故验证为真。 于是B以为攻击者C就是A。结果导致：④若B要发送加密的消息给A，则B要用A的公开钥进行加密，但A的公开钥已被换成C的公开钥，因此B实际上是用C的公开钥进行了加密。⑤C从网络上截获B发给A的密文。由于这密文实际上是用C的公开钥加密的，所有C可以解密。A反而不能正确解密。AKeABKeBCKeCAKeCBKeBCKeC攻击者C篡改PKDB上述攻击成功的原因：①对存入PKDB的公开钥没有采取保护措施，致使公钥被替换而不能发现；②存入PKDB的公钥与用户的标识符之间没有绑定关系，致使A的公钥替换成C的公钥后不能发现，公钥与用户的标识符之间的对应关系被破坏。采用数字签名技术可以克服上述两个弱点，确保公开钥的安全分配。－－公钥证书PKC是一种包含持证主体标识、持证主体公钥等信息，并由可信任的签证机构（CA）签署的信息集合。公钥证书主要用于确保公钥及其与用户绑定关系的安全。这个公钥就是证书所标识的那个主体的合法的公钥。公钥证书的持证主体可以是人、设备、组织机构或其它主体。公钥证书能以明文的形式进行存储和分配。公钥证书PKC（PublicKeyCertificate）简单公钥证书示意图主体身份信息主体的公钥CA的信息其它信息CA的签名签名公钥证书CA的私钥问题：如何验证证书真伪？公钥与用户的标识符之间的对应关系使用公钥证书的主要好处是：①用户只要获得其它用户的证书，就可以获得其它用户的公钥。②用户只要获得CA的公钥，就可以安全地认证其它用户的公钥。③因此公钥证书为公钥的分发奠定了基础，成为公钥密码在大型网络系统中应用的关键技术。

这就是电子政务、电子商务等大型网络应用系统都采用公钥证书技术的原因。版本号证书序列号签名算法标识符颁发者的名称有效期（不早于/不晚于）主体名称主体的公钥信息颁发者唯一标识符（可选）主体唯一标识符（可选）扩展项（可选）颁发者的签名扩展类型扩展类型……扩展类型关键/非关键关键/非关键……关键/非关键扩展字段值扩展字段值……扩展字段值X.509版本3的证书结构公开密钥基础设施提供一系列支持公开密钥密码应用（加密与解密、签名与验证签名）的基础服务。公钥证书是PKI中最基础的组成部分。此外，PKI还包括签发证书的机构（CA），注册登记证书的机构（RA），存储和发布证书的目录，密钥管理，时间戳服务，管理证书的各种软件和硬件设备，证书管理与应用的各种政策和法律，以及证书的使用者。所有这些共同构成了PKI。本质上，PKI是一种标准的公钥密码体制的密钥管理平台。3.4公钥基础设施PKI在PKI中，CA负责签发证书、管理和撤销证书。CA严格遵循证书策略机构所制定的策略签发证书。CA是所有注册用户所信赖的权威机构。CA在给用户签发证书时要加上自己的签名，以确保证书信息的真实性。为